[發明專利]具有生存性的Overlay 網絡構建方法

有效

• 申請號: 201110305029.7
• 申請日: 2011-10-10
• 公開（公告）號: CN102355464A
• 公開（公告）日: 2012-02-15
• 發明（設計）人: 曲樺;趙季紅;馬文濤;王力;唐睿
• 申請（專利權）人: 西安交通大學
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L12/56
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

技術領域

本發明主要是為了提高IP網絡的生存性，通過使用重疊懲罰思想的路徑選擇算法來構建一種可以提供生存性保證的Overlay網絡，從而增強IP網絡的生存性。?

背景技術

隨著通信網絡技術的發展，各種新型業務不斷涌現，對網絡傳輸的需求提出了巨大的挑戰。傳統的盡力而為的IP網絡無法保證新的業務類型所需要的服務，因而導致業務的QoS無法得到滿足，出現資費不能根據業務進行收取的問題。并且在網絡中出現故障后，無法提供區分業務的生存性策略。現有網絡在保證業務QoS需求的同時，是以降低網絡生存性作為代價的。?

現有的IP網絡本身并不具備生存性能力，不能提供面向業務的服務，更不能提供面向業務的生存性機制，而且IP網絡中的物理結構和物理拓撲也不能隨便更改。為了改變IP網絡的這種缺陷，需要在IP網絡結構之上構建具有不同生存能力的Overlay網絡，使得該Overlay網絡可以增強底層網絡的生存性，滿足不同業務的請求。?

發明內容

鑒于此，本發明的主要目的在于提供一種面向業務的具有生存性的Overlay網絡構建方法，通過業務QoS來為每個源-目的對之間在IP層計算多條相異傳輸路徑，構成虛擬拓撲，這樣就可以在IP網絡結構之上構建具有不同生存能力的Overlay網絡，滿足不同業務的需求。在此Overlay網絡中可以將性能最優的路徑(主用路徑)作為業務的主要傳輸路徑，其他路徑作為保護路徑。若主用?路徑發生故障，系統可以啟動全局保護機制，順利的將業務倒換到滿足業務需求的保護路徑中進行傳輸，從而可以增強網絡的生存性。?

本發明的具有生存性的Overlay網絡構建方法，包括如下步驟：在構造Overlay層的虛擬鏈路之前，首先在IP層的拓撲結構中利用Dijkstra最短路徑算法計算源-目的對之間的最優路徑，將其映射成為一條虛擬鏈路；然后，對于出現在最優路徑上的鏈路進行懲罰，完成之后再利用Dijkstra算法去繼續計算次優路徑，如果新找到的路徑和前面找到的路徑都不相同，則繼續構造虛擬鏈路并對出現的鏈路進行懲罰，如果與前面找到的某條路徑相同，則只對鏈路進行懲罰，而不會將其放入相異路徑組中；最后接著尋找滿足條件的保護路徑，直到找到了指定數目的保護路徑，或者路徑的懲罰值大于某個預先約定的值。至此，通過以上過程可以計算出此源-目的對之間的多條路徑，則由這些路徑中的鏈路和節點可以構成一個Overlay網絡，此Overlay網絡就可提供該源-目的對之間的通信保證。根據此思想就可以在所有的源-目的對之間建立Overlay網絡，來保證整個網絡業務傳輸的生存性。如果所選的保護路徑和原始最優路徑的鏈路重復度比較高時，當原始最優路徑出現問題，替換路徑出現問題的概率也就會大大提高，從而不利于業務的倒換，本發明中所提到的基于重疊懲罰算法的“繞行”路徑選擇機制可以很好的避免這種問題。?

優選地，本發明還包括如下步驟：確定鏈路狀態，確定各條鏈路上的時延代價大小，確定所要找的路徑的初始節點和目的節點，確定懲罰因子大小和懲罰方式，并初始化目前找到的路徑數目為0。?

優選地，其中還包括如下步驟：利用Dijkstra算法計算給定拓撲圖中的最短時延代價路徑，并且記錄最短路徑長度，為了計算鏈路的懲罰因子。?

優選地，在計算路徑時，根據不同的QoS參數作為度量值。?

優選地，業務層首先根據業務的類型確定業務的QoS參數要求，然后相應地抽象出虛擬的拓撲結構。?

優選地，所述QoS參數要求為高時延要求或者低丟包率要求。?

本發明具體還包括：?

下面對該路徑選擇集中進行描述：?

模型描述：G＝(V，E)，其中V表示節點集，E表示鏈路集。對于網絡中的每條鏈路(i，j)均有一個廣義的時延代價與之對應。一條源-目的對之間的路徑，由一系列鏈路構成{(i_s，i₁)，(i₁，i₂)，...(i_d-1，i_d)}。這條路徑上的時延就是所有鏈路上的時延的代數和。?

定義1合理繞行路徑：一條非原始路徑，如果它不僅具有可接受的時延等其他一些屬性，而且與所選出的原始路徑在鏈路上存在較大的差異，則就被稱為是一條原始路徑的合理的繞行路徑。?

定義2路徑的s-相似：如果某條可繞行路徑k與原始路徑所共享的鏈路數與其總的鏈路數之比為s，就稱此繞行路徑與原始路徑s-相似。?