一種Overlay網絡及其轉發節點部署方法

2023-06-21 20:40:11

專利名稱：一種Overlay網絡及其轉發節點部署方法
技術領域：
本發明涉及計算機網絡領域，特別是涉及一種基於底層網絡信息感知的Overlay 網絡及其轉發節點部署方法。
背景技術：
隨著網絡規模的不斷擴大，新型網絡應用層出不窮，網際網路自身在不斷地演化和發展，從單一的數據傳輸網絡演變成為一個集數據、語音、視頻等多媒體業務於一體的綜合傳輸網絡，與此同時網際網路也面臨著許多亟需解決的問題。一方面，新應用對網絡傳輸服務質量的需求越來越迫切，另一方面，由於網際網路的核心路由協議BGP的選路方式簡單，標準單一，且容錯性較差，無法保證傳輸質量。近年來，研究者們提出採用在已有網絡上架設覆蓋網(Overlay)的方式，來繞過某些低效的鏈路以提升端到端的傳輸性能，縮短故障恢復時間，根據目的終端和業務類型進行不同的路由方式已成為一個新的研究熱點。在Detour和RON等典型的Overlay技術中(如圖1所示)，研究者們已通過建設相應的實驗網，驗證了採用Overlay網絡相對BGP在快速響應、故障恢復、業務QoS保證等方面的巨大優勢。覆蓋網的一個關鍵技術就是轉發節點部署，通過在適當的位置部署轉發節點，能夠充分利用底層網絡中節點的連接關係，挖掘潛在冗餘路徑，構造大量性能更優的覆蓋網路徑，提高端到端的傳輸性能，增強網絡抗毀能力。但迄今為止，大量Overlay技術方案在進行轉發節點部署時較少考慮底層網絡信息，導致其構建的備用路徑與預設路徑相關程度大，路由優化性能受限。而考慮了底層網絡結構信息的Overlay技術方案，僅僅是簡單地把所有的鏈路和節點平等對待，轉發節點部署的效率不高。

發明內容
本發明的目的在於提供一種Overlay網絡及其轉發節點部署方法，其是針對現有Overlay網絡轉發節點部署(路徑分離不夠的問題)問題，提出了一種基於底層網絡信息感知的高效覆蓋網節點部署算法(TTOP)。相對於現有Overlay網絡採用的不考慮底層網絡信息的節點部署方法，或者簡單基於節點度的節點部署方法，本發明引入統計流量信息，並結合底層網絡特點部署轉發節點，只需部署少數節點，即可為網絡中多數源目的 (source-destination, SD)節點對提供與預設路徑相獨立的冗餘傳輸路徑，更有效地提高網絡抗毀能力。為實現本發明的目的而提供的一種Overlay網絡，包括多個轉發節點，所述轉發節點是基於對底層網絡信息的感知進行部署，具體包括根據網絡流量分布信息TD，獲取每個源目的節點SD對之間的統計流量信息；根據統計流量的大小，對所有SD對排序，得到非升序排列的SD對集合SDkUSD1, SD2, SD3,... SDm} , t! ^ t2 ^ t3tM ；從網絡節點集合V中選出一個包含K個節點的子集Elected，作為部署轉發節點的位置，優先為擁有大流量的節點對提供與其預設路徑獨立的冗餘路徑。所述子集Elected，採用下述方法獲得初始化部署位置集合Elected，置其為0;判斷SDkt中節點對是否全部取完，若是，則返回Elected集合；否則，.判斷是否 Selected = K ；若 Selected = K，則返回 Selected 集合；若 Selected 乒 K，則判斷Elected中是否存在某個節點N—能夠滿足在Nselected部署轉發節點後，節點對SDi 之間存在至少一條獨立於Clpath(SDi)的路徑，若存在這樣的節點，則取出新的SD按照上述方法處理；若不存在這樣的節點，則從節點對集合SDkt中取出一個SD對，設為SDj,計算節點Nj,使得在Nj部署轉發節點後，節點對SDj之間存在至少一條獨立於Clpath(SDj)的冗餘路徑，將Nj加入Elected集合，重新判斷SDkt中節點對是否全部取完。節點Ns^rtral的選取方法，包括判斷所述Elected中是否還有節點沒有被考察過，若是，則從所述Elected中沒有被考察過的節點中取出一個節點Nseleeted ；否則，從節點對集合SDSet中取出一個新的SD 對；判斷所述節點Nseleeted是否可以為節點對SDi之間建立一條獨立於Clpath(SDi)的路徑；若是，則重新判斷SDkt中節點對是否全部取完，否則，判斷所述Elected中是否還有節點沒有被考察過。計算節點Nj的方法，包括為SDj計算當前候選部署位置的集合V」，Vj = V-nodes (dpath (SDj)) -Selected ；判斷所述候選部署位置的集合\是否存在沒有被考察過的節點，若是，則從所述候選部署位置的集合Vj中取出一個節點Nj ；否則，重新判斷SDSet中節點對是否全部取完；判斷在所述節點 部署轉發節點後，節點對SDj之間是否存在至少一條獨立於 dpath (SDj)的冗餘路徑，若是，則將Nj加入Elected集合，重新判斷SDSet中節點對是否全部取完；否則判斷\中是否存在沒有被考察過的節點。為實現本發明的目的還提供一種Overlay網絡的轉發節點部署方法，所述方法， 包括下列步驟步驟100.根據網絡流量分布信息TD，獲取每個源目的節點(SD)對之間的統計流量信息；根據統計流量的大小，對所有SD對排序，得到非升序排列的SD對集合SDkUSD1, SD2, SD3, -SDJ，、彡 t2 彡 t3 tM ；步驟200.從網絡節點集合V中選出一個包含K個節點的子集Elected，作為部署轉發節點的位置，優先為擁有較大流量的節點對提供與其預設路徑獨立的冗餘路徑。所述步驟200，包括下列步驟步驟210.初始化部署位置集合Elected，置其為0;步驟220.判斷SDkt中節點對是否全部取完，即是否SDSet =0，若是，則執行步驟260 ；否則，執行步驟230 ；步驟230.判斷是否I Selected = K，若是則執行步驟260 ；否則，執行步驟240 ；步驟M0.判斷Elected中是否存在某個節點Nselerted能夠滿足在N—部署轉發節點後，節點對SDi之間存在至少一條獨立於Clpath(SDi)的路徑，若是，則返回步驟220 ；否則，執行步驟250;步驟250.從節點對集合SDSet中取出一個SD對，設為SD」，計算節點N」，使得在Nj 部署轉發節點後，節點對SDj之間存在至少一條獨立於Clpath(SDj)的冗餘路徑，將Nj加入 Selected集合，返回步驟220 ；步驟洸0 返回Selected集合。所述步驟M0，包括下列步驟步驟Ml.判斷所述Elected中是否還有節點沒有被考察過，若是，則執行步驟 242 ；否則，執行步驟250 ；步驟M2.從所述Elected中沒有被考察過的節點中取出一個節點Nselected，步驟M3.判斷所述節點Nseleeted是否可以為節點對SDi之間建立一條獨立於 Clpath(SDi)的路徑；若是，則返回步驟220，否則，返回步驟Ml。所述步驟250，包括下列步驟步驟251.為SDj計算當前候選部署位置的集合Vj, Vj = V-nodes (dpath (SDj)) -Selected ；步驟252.判斷所述候選部署位置的集合Vj是否存在沒有被考察過的節點，若是， 則執行步驟253 ；否則，返回步驟220 ；步驟253.從所述候選部署位置的集合Vj中取出一個節點Nj ；步驟254.判斷在所述節電Nj部署轉發節點後，節點對SDj之間是否存在至少一條獨立於dpath (SDj)的冗餘路徑，若是，則將Nj加入Elected集合，返回步驟220 ；否則返回步驟252。所述步驟252中，按照節點度降序依次考察Vj中的節點N」。本發明的有益效果是本發明的一種Overlay網絡及其轉發節點部署方法，特別適用於以提升網絡抗毀能力為目標的Overlay網絡進行轉發節點部署，它以儘可能小的成本為儘可能多的源目的節點對構建與預設路徑獨立的冗餘路徑，對網絡承載的業務流量實施保護，大大增強了傳輸的可靠性，這對於Overlay網絡終端使用多路徑傳輸和承載實時業務具有重要的意義， 可以預見，如果Overlay技術能得以普及，該節點部署算法將具有非常廣闊的應用前景。


圖1是本發明中Overlay網絡的轉發節點的部署方法的步驟流程圖；圖2是本發明中選取子集Elected作為部署轉發節點的位置的步驟流程圖；圖3是本發明中考察已經選出的Elected中是否包含滿足條件的節點的步驟流程圖；圖4是本發明中為SD選出滿足條件的節點Nj的步驟流程圖；圖5是現有技術中Abilene Network的拓撲結構圖；圖6是各種算法對網絡抗毀能力的提升效果圖。
具體實施例方式為了使本發明的目的、技術方案及優點更加清楚明白，以下結合附圖及實施例，對本發明的一種Overlay網絡及其轉發節點部署方法進行進一步詳細說明。應當理解，此處所描述的具體實施例僅僅用以解釋本發明，並不用於限定本發明。本發明的一種Overlay網絡及其轉發節點部署方法，其實質是在現有Overlay網絡採取的簡單基於節點度來選擇轉發節點部署位置的方案上，對節點和鏈路進行了區分， 根據節點對之間的流量大小對所有源目的節點對進行排序，部署轉發節點時，優先為擁有較大流量的節點對提供與其預設路徑獨立的冗餘路徑，這種貪心式的部署，可以較少的部署節點，為儘量多的流量提供冗餘路徑，同時，本發明中還優先考慮在節點度較大的位置部署轉發節點，可使轉發節點服務於儘量多的源目的節點對，提供轉發節點資源利用率，降低部署成本。此外，本發明計算簡單、易於實施、可增量部署節點。下面結合上述目標詳細介紹本發明的一種Overlay網絡，所述Overlay網絡，包括多個轉發節點，所述轉發節點是基於對底層網絡信息的感知進行部署。為了便於描述本發明方法的步驟，首先對本發明的應用場景與參數做簡要說明假定覆蓋網轉發節點可在網絡上任意節點處部署，且轉發能力充足。已知網絡的統計流量分布信息TD (Traffic Distribution)和AS級靜態拓撲G (V, E)，V是節點集合， 每一個節點代表一個AS，E是邊的集合，每條邊代表節點之間的物理鏈路；SD之間的路徑構成的集合記為I^athkt ；某個SD對SDi之間的統計流量記為ti;其預設路徑為Clpath(SDi)； 某個路徑Pathx所包含的全部節點構成的集合用Iiodes(Pathx)表示，路徑長度用Ipathx 表示；Pathi與path」擁有同樣的源和目的節點S和D5Snodes(Pathi) Π nodes (pathj)= {S，D}，即兩條路徑，除了源節點和目的節點之外，沒有共有節點，則稱Pathi與path」相互獨立。本發明根據已知的底層網絡拓撲結構G(V，Ε)和流量分布信息TD，從節點集合V 中選出一個包含K個節點的子集Elected，作為部署轉發節點的位置。圖1是本發明中 Overlay網絡的轉發節點的部署方法的步驟流程圖，如圖1所示，具體步驟如下步驟100.根據網絡流量分布信息TD，獲取每個源目的節點(SD)對之間的統計流量信息；根據統計流量的大小，對所有SD對排序，得到非升序排列的SD對集合SDkUSD1, SD2, SD3, -SDJ，、彡 t2 彡 t3 tM ；步驟200.從網絡節點集合V中選出一個包含K個節點的子集Elected，作為部署轉發節點的位置，優先為擁有較大流量的節點對提供與其預設路徑獨立的冗餘路徑。圖2是本發明中選取子集Elected作為部署轉發節點的位置的步驟流程圖，如圖 2所示，所述步驟200，包括下列步驟步驟210.初始化部署位置集合Elected，置其為0;步驟220.判斷SDkt中節點對是否全部取完，即是否SDSet =0，若是，則執行步驟260 ；否則，執行步驟230 ；步驟230.判斷是否I Selected = K，若是則執行步驟260 ；否則，執行步驟240 ；步驟M0.判斷Elected中是否存在某個節點Nseleeted能夠滿足在Nseleeted部署轉發節點後，節點對SDi之間存在至少一條獨立於Clpath(SDi)的路徑，若是，則返回步驟220 ； 否則，執行步驟250;圖3是本發明中考察已經選出的Elected中是否包含滿足條件的節點的步驟流程圖，如圖3所示，所述步驟240，包括下列步驟
7
步驟Ml.判斷所述Elected中是否還有節點沒有被考察過，若是，則執行步驟 242 ；否則，執行步驟250 ；步驟M2.從所述Elected中沒有被考察過的節點中取出一個節點Ns+。ted，步驟M3.判斷所述節點Nseleeted是否可以為節點對SDi之間建立一條獨立於 Clpath(SDi)的路徑；若是，則返回步驟220，否則，返回步驟Ml ；步驟250.從節點對集合SDSet中取出一個SD對，設為SD」，計算節點N」，使得在Nj 部署轉發節點後，節點對SDj之間存在至少一條獨立於Clpath(SDj)的冗餘路徑，將Nj加入 Selected集合，返回步驟220 ；圖4是本發明中為SD選出滿足條件的節點 的步驟流程圖，如圖4所示，所述步驟250，包括下列步驟步驟251.為SDj計算當前候選部署位置的集合Vj, Vj = V-nodes (dpath (SDj)) -Selected ；步驟252.判斷所述候選部署位置的集合Vj是否存在沒有被考察過的節點，若是， 則執行步驟253 ；否則，返回步驟220 ；按照節點度降序依次考察Nj中的節點 步驟253.從所述候選部署位置的集合Vj中取出一個節點Nj ；步驟254.判斷在所述節電 部署轉發節點後，節點對SDj之間是否存在至少一條獨立於dpath (SDj)的冗餘路徑，若是，則將Nj加入Elected集合，返回步驟220 ；否則返回步驟252。步驟洸0 返回Selected集合。為了更好的說明本發明的技術方案，下面採用美國的科研骨幹網Abilene Network[]為對象，以在Abilene Network上部署Overlay轉發節點為例詳細說明本發明的技術方案。Abilene Network是一個由hternet2團體創建的高性能骨幹網絡，互聯了美國各地的大學和研究機構，用於開發先進網際網路應用和部署尖端的網絡服務。Abilene Network通過連接區域網絡的聚合點，為分布在全美所有50個州、哥倫比亞特區以及波多黎各的超過230個成員，包括大學、企業、附屬成員機構，提供高帶寬的網絡連接。圖5是現有技術中Abilene Network的拓撲結構圖，如圖5所示，共有12個節點，15條骨幹鏈路，各節點對之間的統計流量如表1所示。表1 Abilene Network的統計流量分布(單位Mbps)
權利要求
1.一種Overlay網絡，包括多個轉發節點，其特徵在於，所述轉發節點是基於對底層網絡信息的感知進行部署，具體包括根據網絡流量分布信息TD，獲取每個源目的節點SD對之間的統計流量信息；根據統計流量的大小，對所有SD對排序，得到非升序排列的SD對集合SDSetiSD1, SD2, SD3, -SDmI，^ ^2 ^ 》…》^M ；從網絡節點集合V中選出一個包含K個節點的子集Elected，作為部署轉發節點的位置，優先為擁有較大流量的節點對提供與其預設路徑獨立的冗餘路徑。
2.根據權利要求1所述的Overlay網絡，其特徵在於，所述子集Elected，採用下述方法獲得初始化部署位置集合Elected，置其為0;判斷SDkt中節點對是否全部取完，若是，則返回Elected集合；否則，.判斷是否 Selected = K ；若 Selected = K，則返回 Elected 集合；若 Selected 乒 K，則判斷 Selected中是否存在某個節點N—能夠滿足在Nselected部署轉發節點後，節點對SDi之間存在至少一條獨立於Clpath(SDi)的路徑，若存在這樣的節點，則取出新的SD按照上述方法處理；若不存在這樣的節點，則從節點對集合SDSet中取出一個SD對，設為SDj,計算節點Nj, 使得在Nj部署轉發節點後，節點對SDj之間存在至少一條獨立於Clpath(SDj)的冗餘路徑， 將 加入Elected集合，重新判斷SDSet中節點對是否全部取完。
3.根據權利要求2所述的Overlay網絡，其特徵在於，節點Nselerted的選取方法，包括 判斷所述Elected中是否還有節點沒有被考察過，若是，則從所述Elected中沒有被考察過的節點中取出一個節點Nseleeted ；否則，從節點對集合SDSet中取出一個新的SD對；判斷所述節點Nseleeted是否可以為節點對SDi之間建立一條獨立於Clpath(SDi)的路徑； 若是，則重新判斷SDSet中節點對是否全部取完，否則，判斷所述Elected中是否還有節點沒有被考察過。
4.根據權利要求2所述的Overlay網絡，其特徵在於，計算節點 的方法包括 為SDj計算當前候選部署位置的集合V」，Vj = V-nodes (dpath (SDj)) -Selected ；判斷所述候選部署位置的集合\是否存在沒有被考察過的節點，若是，則從所述候選部署位置的集合、中取出一個節點 ；否則，重新判斷SDkt中節點對是否全部取完；判斷在所述節點Nj部署轉發節點後，節點對SDji間是否存在至少一條獨立於 dpath (SDj)的冗餘路徑，若是，則將Nj加入Elected集合，重新判斷SDSet中節點對是否全部取完；否則判斷\中是否存在沒有被考察過的節點。
5.根據權利要求4所述的Overlay網絡，其特徵在於，按照節點度降序依次考察Vj中的節點Nj。
6.一種Overlay網絡的轉發節點部署方法，其特徵在於，所述方法包括下列步驟 步驟100.根據網絡流量分布信息TD，獲取每個源目的節點(SD)對之間的統計流量信息；根據統計流量的大小，對所有SD對排序，得到非升序排列的SD對集合SDkUSD1, SD2, SD3, ...SDM}，、彡 t2 彡 t3 tM ；步驟200.從網絡節點集合V中選出一個包含K個節點的子集Elected，作為部署轉發節點的位置，優先為擁有較大流量的節點對提供與其預設路徑獨立的冗餘路徑。
7.根據權利要求6所述的Overlay網絡的轉發節點部署方法，其特徵在於，所述步驟 200，包括下列步驟步驟210.初始化部署位置集合Elected，置其為0;步驟220.判斷SDkt中節點對是否全部取完，即是否SDSet =0，若是，則執行步驟 260 ；否則，執行步驟230 ；步驟230.判斷是否Selected = K，若是則執行步驟260 ；否則，執行步驟240 ； 步驟MO.判斷Elected中是否存在某個節點N—能夠滿足在Nselected部署轉發節點後，節點對SDi之間存在至少一條獨立於Clpath(SDi)的路徑，若是，則返回步驟220 ；否則，執行步驟250;步驟250.從節點對集合SDSet中取出一個SD對，設為SDj,計算節點Nj,使得在Nj部署轉發節點後，節點對SDj之間存在至少一條獨立於Clpath(SDj)的冗餘路徑，將Nj加入 Selected集合，返回步驟220 ；步驟沈0.返回Elected集合。
8.根據權利要求7所述的Overlay網絡的轉發節點部署方法，其特徵在於，所述步驟 MO，包括下列步驟步驟Ml.判斷所述Elected中是否還有節點沒有被考察過，若是，則執行步驟242 ； 否則，執行步驟250;步驟M2.從所述Elected中沒有被考察過的節點中取出一個節點Ns&。ted， 步驟M3.判斷所述節點Nseleeted是否可以為節點對SDi之間建立一條獨立於 Clpath(SDi)的路徑；若是，則返回步驟220，否則，返回步驟Ml。
9.根據權利要求7所述的Overlay網絡的轉發節點部署方法，其特徵在於，所述步驟 250，包括下列步驟步驟251.為SDj計算當前候選部署位置的集合、Vj = V-nodes (dpath (SDj)) -Selected ；步驟252.判斷所述候選部署位置的集合\是否存在沒有被考察過的節點，若是，則執行步驟253 ；否則，返回步驟220 ；步驟253.從所述候選部署位置的集合Nj中取出一個節點Nj ； 步驟254.判斷在所述節電Nj部署轉發節點後，節點對SDj之間是否存在至少一條獨立於dpath (SDj)的冗餘路徑，若是，則將Nj加入Elected集合，返回步驟220 ；否則返回步驟 252。
10.根據權利要求9所述的Overlay網絡的轉發節點部署方法，其特徵在於，所述步驟 252中，按照節點度降序依次考察Vj中的節點 。
全文摘要
本發明公開了一種Overlay網絡及其轉發節點部署方法。所述方法，包括下列步驟根據網絡流量分布信息TD，獲取每個源目的節點(SD)對之間的統計流量信息；根據統計流量的大小，對所有SD對排序，得到非升序排列的SD對集合SDSet{SD1，SD2，SD3，…SDM}，t1≥t2≥t3≥…≥tM；從網絡節點集合V中選出一個包含K個節點的子集Selected，作為部署轉發節點的位置，優先為擁有較大流量的節點對提供與其預設路徑獨立的冗餘路徑。
文檔編號H04L12/56GK102215169SQ20111014982
公開日2011年10月12日 申請日期2011年6月3日 優先權日2011年6月3日
發明者張國清, 李 東, 李彥君, 林濤, 覃毅芳 申請人:中國科學院計算技術研究所