覆蓋網備用路徑生成方法和裝置的製作方法

2023-05-31 10:37:46 2

專利名稱：覆蓋網備用路徑生成方法和裝置的製作方法
技術領域：
本發明涉及網際網路中的路由優化，特別涉及基於分域協作的覆蓋網備 用路徑生成方法和裝置。
背景技術：
網際網路在最初設計時只針對數據傳輸服務，因此它所採用的best-effort 數據傳輸方式僅僅提供了基本的端到端的連接，並不對丟包率、延遲、抖 動和帶寬等提供特別保證。然而，隨著網際網路規模的擴張，大量新型應用 開始興起，其中很多應用對網絡傳輸性能的要求非常苛刻，例如，以網絡 視頻、在線遊戲和虛擬實境等為代表的新型業務對網際網路提出了高帶寬、 低延遲、低抖動的需求。
同時，作為傳統Internet網最核心的路由協議-BGP協議，自1995 年完成修訂後，迄今為止沒有進行過較大的修改，隨著網絡的飛速擴展與 互聯關係的日益複雜，BGP路由協議在處理端到端傳輸時，其收斂慢、冗 餘性差、效率低的問題日漸凸顯，已很難適應大量實時業務的傳輸要求。
早在90年代，為了解決實時業務傳輸質量難以保證的問題，許多研 究人員先後提出了大量方案，IETF也制定了 Intserv和Diffserv兩種QoS 架構，試圖建立統一的解決方案。然而，由於網際網路的底層網絡資源分別 歸屬於不同的國家機構和ISP，各自不同的利益追求很難達成整體的 一致， 因此，跨越多個網絡的傳輸無法實現可操作的端到端服務質量保證方案。
近年來，研究者們提出釆用在應用層架設覆蓋網(Overlay)的方式，來 繞過某些低效的BGP路徑以提升端到端的連接性能，縮短故障恢復時間。 所謂的覆蓋網是在現有網際網路上構建一個完全位於應用層的網絡系統，即 在IPv4底層網絡的基礎上通過節點之間單播機制將主機兩兩連接起來， 形成一個虛擬、獨立的網絡。它存在於網際網路基礎設施和應用程式之間， 利用ISP (Internet Service Provider,網際網路服務提供商)提供的服務來向 其用戶提供更加優化的服務。可以認為，覆蓋網是分布在網際網路上的一組 提供服務的終端主機的集合，它們為 一個或多個應用程式提供下層的傳輸基礎設施，並在某種程度上處理和轉發應用程式的數據。覆蓋網主要包括 兩個部分，分別為覆蓋網節點和邏輯鏈路。覆蓋網節點可以是各種網絡功 能節點，如路由器、伺服器等，甚至可以是終端，這些節點通常具有路由、
數據處理和數據保存等功能；而邏輯鏈路是由底層網絡組成，通常對應底 層的一條或多條物理路徑。在Detour和RON等典型的Overlay技術中， 研究者們已通過建設相應的實驗網，驗證了採用Overlay網絡相對BGP在 快速響應、故障恢復、業務QoS保證等方面的巨大優勢。
覆蓋網的主要功能之一是實現對業務數據傳輸的優化，而實現覆蓋網 傳輸優化的關鍵就是其路由方式。基於對現有路由覆蓋網絡技術方案的分 析，最常見的覆蓋網路由傳輸方式是基於選取轉發節點繞路路由的方式。 這種路由方式主要採用了中繼轉發路由的技術，即數據發送方把數據包發 給轉發節點，然後轉發節點將數據包中繼給數據接收方，從而構造相應的 Overlay路徑。已有研究發現2-跳的Overlay路徑提供的傳輸性能、可靠性 及路徑多樣程度(path diversity )與多跳Overlay路徑提供的近似，因此大 多數覆蓋網出於簡便和易於實現(不需要通過覆蓋網絡層實現非常複雜的 路由機制)的目的，均採用這種經過一個轉發節點轉發的2-跳覆蓋網路徑。
對於這樣的繞路路由構建方案，決定其所構建路由的質量的一個核心 因素就是轉發節點的選擇是否恰當。現有的大多數的Overlay網絡都是基 於覆蓋網自身的Overlay結構進行轉發節點的選取和備用路徑的構建。比 如，在參考文獻1 "D. Andersen, H. Balakrishnan， M. Kaashoek, and R. Morris.Resilient Overlay Networks. In Proc. of the l她Symposium on Operating System Principles, Banff, Canada, October 2001"中，RON對路徑 性能進行探測，基於探測結果進行路徑篩選；而在參考文獻2"C. Cheng,Y. Huan, H. Kung, C. Wu. Path probing relay routing for achieving high end-to-end performance. GLOBECOM 2004"中，Cheng提出了使用隨機搜 索的算法來發現可用的替換路徑。上述算法在實現路徑選取時，都只是基 於對Overlay路徑的分析，由於缺乏對底層網絡拓樸信息的分析和利用， 使得Overlay網絡中所使用的備用路徑與默認底層IP路徑所使用的物理鏈 路或路由器具有關聯性，即備用路徑可能會與默認路徑同時失效，因此實 際運行中所遇到的路徑故障大約有40 - 50%無法在此類Overlay網絡中避 免。基於上述原因，在覆蓋網中選擇鄰居轉發節點時，應當充分考慮底層 網絡的信息。

發明內容
本發明的一個目的是克服現有技術中鄰居轉發節點所構建的備用路 徑與默認路徑存在相關性的缺陷，從而提供一種備用路徑生成方法。 本發明的另一個目的是提供一種備用路徑生成裝置。
為了實現上述目的，本發明提供了一種覆蓋網備用路徑生成方法，用 於在包括接入伺服器節點、標誌伺服器節點、轉發節點和用戶節點的覆蓋 網上為源用戶節點選取合適的轉發節點以構建從源用戶節點到目的用戶
節點的備用路徑，該方法包括
步驟1 )、利用所述覆蓋網中的標誌伺服器節點對所述轉發節點做網絡
測距，根據網絡測距結果計算任意兩個轉發節點間的綜合性能相似度，由
所述綜合性能相似度為具有相近性能的轉發節點構建邏輯轉發網絡；其
中，在所述覆蓋網的一個自由域內屬於同一邏輯轉發網絡的轉發節點擁有 同一個入口轉發節點；
步驟2 )、所述接入伺服器節點根據所述用戶節點的請求轉發節點消息 在所述用戶節點所在的自由域中選擇邏輯轉發網絡，然後通過所述邏輯轉 發網絡的入口轉發節點找到與所述入口轉發節點在同 一 自由域且同 一邏 輯轉發網絡的轉發節點作為服務轉發節點；所述服務轉發節點在所在的邏 輯轉發網絡上運行BFBB算法，根據該算法的運行結果選擇轉發節點作為 一次候選轉發節點；其中，
所述的BFBB算法在計算網絡拓樸圖中每個節點的度和核度後，在當 前節點上通過廣度優先算法在所述網絡拓樸圖上選取核度值大於當前節 點的核度值，且度與核度的商大於當前節點的度與核度的商的節點；若所 能找到的節點的數目無法滿足要求，則將當前節點的度與核度的商的值遞 減後，重新在當前節點上利用廣度優先算法選取核度值大於當前節點的核 度值，且度與核度的商大於當前節點的度與核度的商的節點，直到滿足對 所選取節點的數目要求；
步驟3)、對候選轉發節點所能形成的路徑做性能檢測，保留通過性能 檢測的候選轉發節點，在所述用戶節點間進行業務通信時，根據業務從所 保留的候選轉發節點中選擇合適的轉發節點以構建備用路徑。
上述技術方案中，在所述步驟2)中所得到的一次候選轉發節點的數 目小於用戶的需求時，在所述的步驟2)和所述的步驟3)之間還包括選取二次候選轉發節點的步驟，該步驟包括
在所述覆蓋網的網絡拓樸圖上運行BFBB算法；
根據所述BFBB算法的計算結果，從所述覆蓋網中選取一個自由域， 在該自由域內選擇轉發節點作為二次候選轉發節點；所選取的轉發節點盡 量不屬於所述第 一用戶節點所在自由域內的邏輯轉發網絡。
上述技術方案中，所述的步驟l)包括
步驟1-1)、所述覆蓋網中的所有轉發節點對所述覆蓋網中的所有標誌 伺服器節點做網絡測距，得到關於延遲、丟包率和瓶頸帶寬的指標；
步驟1-2)、根據所述指標計算任意兩個轉發節點間的綜合性能相似
度；
步驟l-3)、對所有的綜合性能相似度結果做排序，然後為所述排序結 果分段，將具有相近綜合性能的轉發節點分配到同一個邏輯轉發網絡。 上述技術方案中，所述的步驟l)還包括
步驟1-4)、由所述邏輯轉發網絡的入口轉發節點向鄰居域的入口轉發 節點做鏈路性能探測；所述鏈路性能包括路徑的延遲、丟包率和瓶頸帶寬；
步驟1-5)、所述鏈路性能探測的結果保存到入口轉發節點的鏈路狀態 表中，所述鏈路狀態表的信息定時向鄰居域的入口轉發節點更新。
上述技術方案中，在所述的步驟1-2)中，所述綜合性能相似度採用 下列公式計算
^表示節點A與節點B之間的綜合性能相似度，D"表示節點A與節 點B間的延遲相似度，L、表示節點A與節點B間的丟包率相似度，Bwav 表示節點A與節點B間的瓶頸帶寬相似度，《、 "、 Z為網絡系統對性能 的要求有關的常量值；其中，
formula see original document page 11
D亂表示節點A與覆蓋網中第i個標誌伺服器節點間的延遲指標，Ls亂表示節點A與覆蓋網中第i個標誌伺服器節點間的丟包率指標，Bv^表示 節點A與覆蓋網中第i個標誌伺服器節點間的瓶頸帶寬指標。 上述技術方案中，所述的步驟2)包括
步驟2-1 )、所述接入伺服器節點根據所述用戶節點發起的請求轉發節 點消息在所述用戶節點所在自由域中選擇邏輯轉發網絡，並將所述邏輯轉 發網絡的入口轉發節點的地址通知所述用戶節點；
步驟2-2 )、所述入口轉發節點根據所迷用戶節點發起的請求轉發節點 消息選取一個與該入口轉發節點具有相同自由域和相同邏輯轉發網絡的 轉發節點，作為為所述用戶節點服務的服務轉發節點；
步驟2-3 )、所述服務轉發節點在自身的邏輯轉發網絡上運行BFBB算 法，根據算法的運行結果在所述覆蓋網中選擇有別於所述服務轉發節點所 在自由域的自由域，然後在所述自由域內選擇與該服務轉發節點具有相同 邏輯轉發網絡的轉發節點作為 一次候選轉發節點，所述一次候選轉發節點 返回給所述的第一用戶節點。
上述技術方案中，所述的步驟2)還包括
步驟2-4)、所述用戶節點將接收到的一次候選轉發節點與自身的一次
候選轉發節點列表進行比較；
步驟2-5 )、所述用戶節點向不存在於所述列表中的新的轉發節點發送
自身的信息，從而在所述新的轉發節點的鏈路狀態表中查詢所述新的轉發
節點所在自由域與所述用戶節點所在自由域之間的鏈路屬性信息； 步驟2-6 )、所述鏈路屬性信息返回並保存到所述用戶節點。 上述技術方案中，在所述的步驟2-1)中，所述接入伺服器節點根據
用戶節點發起的請求轉發節點消息在所述用戶節點所在自由域中選擇邏
輯轉發網絡時，選擇儘可能多的邏輯轉發網絡。
上述技術方案中，在所述的選取二次候選轉發節點的步驟後，還包括 所述的用戶節點對所述的二次候選轉發節點做周期性的路徑性能探
測，並將探測結果保存到所述用戶節點的鏈路狀態表中。
上述技術方案中，在所述的步驟3)中，對候選轉發節點所能形成的
路徑做性能檢測包括
步驟3-l )、用戶節點根據業務的類型確定路徑的門限指標；
步驟3-2 )、從所述一次候選轉發節點中選擇轉發節點；
步驟3 -3 )、獲取一 用戶節點經由所選擇的轉發節點至另 一 用戶節點的路徑性能；
步驟3_4)、將步驟3-3)所獲取的路徑性能與步驟3-l)中所確定的門 限指標進行比較，根據比較結果確定路徑是否通過了性能檢測。
上述技術方案中，對候選轉發節點所能形成的路徑做性能檢測還包
括
步驟3-5 )、當所述一次候選轉發節點中能夠通過路徑性能檢測的轉發 節點數目無法滿足用戶要求時，從所述二次候選轉發節點中選擇轉發節 點；
步驟3-6 )、獲取一用戶節點經由所選擇的轉發節點至另 一用戶節點的 路徑性能；
步驟3-7)、將步驟3-6)所獲取的路徑性能與步驟3-l )中所確定的門 限指標進行比較，根據比較結果確定路徑是否通過了性能檢測。
上述技術方案中，在所述的步驟3-3)中，獲取所述第一用戶節點經 由所選擇的轉發節點至所述第二用戶節點的路徑性能包括
從所選擇的轉發節點的鏈路狀態表中查詢從所述轉發節點所在自由 域到所述第二用戶節點所在自由域間的鏈路屬性，從所述第一用戶節點的 鏈路狀態表中獲取從所述第 一用戶節點所在自由域到所述轉發節點所在 自由域的鏈路屬性，進而獲取所述第一用戶節點經由所選擇的轉發節點至 所述第二用戶節點的路徑性能；
或所選擇的轉發節點通過路徑探測，得到從所述轉發節點所在自由域 到所述第二用戶節點所在自由域間的鏈路屬性，從所述第 一用戶節點的鏈 路狀態表中獲取從所述第 一 用戶節點所在自由域到所述轉發節點所在自 由域的鏈路屬性，進而獲取所述第一用戶節點經由所選擇的轉發節點至所 述第二用戶節點的路徑性能。
上述技術方案中，在所述的步驟3-6)中，獲取所述第一用戶節點經 由所選擇的轉發節點至所述第二用戶節點的路徑性能包括
所選擇的轉發節點通過路徑探測，得到從所述轉發節點所在自由域到 所述第二用戶節點所在自由域間的鏈路屬性，從所述第一用戶節點的鏈路 狀態表中獲取從所述第一用戶節點所在自由域到所述轉發節點所在自由 域的鏈路屬性，進而獲取所述第一用戶節點經由所選擇的轉發節點至所述 第二用戶節點的路徑性能。
本發明還提供了 一種覆蓋網備用路徑生成裝置，用於在包括接入伺服器節點、標誌伺服器節點、轉發節點和用戶節點的覆蓋網上為源用戶節點 選取合適的轉發節點以構建從源用戶節點到目的用戶節點的備用路徑，該 裝置包括邏輯轉發網絡創建模塊、 一次候選轉發節點選取模塊以及性能檢
測模塊；其中，
所述的邏輯轉發網絡創建模塊利用所述覆蓋網中的標誌伺服器節點 對所述轉發節點做網絡測距，根據網絡測距結果計算任意兩個轉發節點間 的綜合性能相似度，由所述綜合性能相似度為具有相近性能的轉發節點構 建邏輯轉發網絡；其中，在所述覆蓋網的一個自由域內屬於同一邏輯轉發 網絡的轉發節點擁有同 一 個入口轉發節點；
所述的一次候選轉發節點選取模塊用於由所述接入伺服器節點根據
所述用戶節點的請求轉發節點消息在所述用戶節點所在的自由域中選擇 邏輯轉發網絡，然後通過所述邏輯轉發網絡的入口轉發節點找到與所述入 口轉發節點在同 一 自由域且同 一邏輯轉發網絡的轉發節點作為服務轉發 節點；所述服務轉發節點在所在的邏輯轉發網絡上運行BFBB算法，根據 該算法的運行結果選擇轉發節點作為 一次候選轉發節點；其中，
所述的BFBB算法在計算網絡拓樸圖中每個節點的度和核度後，在當 前節點上通過廣度優先算法在所述網絡拓樸圖上選取核度值大於當前節 點的核度值，且度與核度的商大於當前節點的度與核度的商的節點；若所 能找到的節點的數目無法滿足要求，則將當前節點的度與核度的商的值遞 減後，重新在當前節點上利用廣度優先算法選取核度值大於當前節點的核 度值，且度與核度的商大於當前節點的度與核度的商的節點，直到滿足對 所選取節點的數目要求；
所述的性能檢測模塊用於對候選轉發節點所能形成的路徑做性能檢 測，保留通過性能檢測的候選轉發節點，在所述用戶節點間進行業務通信 時，根據業務從所保留的候選轉發節點中選擇合適的轉發節點以構建備用 路徑。
上述技術方案中，還包括二次候選轉發節點選取模塊，該模塊用於在 所述覆蓋網的網絡拓樸圖上運行BFBB算法，然後根據所述BFBB算法的 計算結果，從所述覆蓋網中選取一個自由域，在該自由域內選擇轉發節點 作為二次候選轉發節點；所選取的轉發節點儘量不屬於所述第一用戶節點 所在自由域內的邏輯轉發網絡。
本發明的優點在於本發明能夠顯著地提高轉發鄰居節點的命中率，降低所構建備用路徑 與默認路徑同時發生故障的可能性。


圖1為本發明中所涉及的覆蓋網的一個實施例的示意圖； 圖2為將覆蓋網中的轉發節點構建邏輯轉發網絡的示意圖； 圖3為一個AS內且屬於同一邏輯轉發網絡的所有轉發節點對外所提 供的入口轉發節點的示意圖4為邏輯轉發網絡中的各個節點發送鏈路狀態表的示意圖； 圖5為已經為轉發節點構建邏輯轉發網絡的覆蓋網的示意圖； 圖6為對圖5中的用戶節點Cl與用戶節點C2建立業務通信的示意
圖7為本發明的備用路徑生成方法的流程圖。
具體實施例方式
下面結合附圖和具體實施方式
對本發明做進一步說明。
在本發明中，所涉及的覆蓋網可以應用在多種類型的網絡，如P2P網 絡、CDN網絡以及各種Overlay網絡，如RON、 QRON、 NIRA.OverQos 等。在下面的實施例中，所涉及的覆蓋網不限於具體的網絡類型，可在前 面所提到的各種網絡上應用。
在本發明中，覆蓋網中的各個節點可分為三種類型，包括服務節點、 轉發節點以及用戶節點，其中的服務節點又可進一步分為接入伺服器節點 (Server)和標誌伺服器節點(Landmark)。所述的接入伺服器節點用於存 儲和維護系統信息，而標誌伺服器節點則用於實現網絡測距，在本發明中， 所述的網絡測距主要包括測量延遲、抖動和瓶頸帶寬。所迷的轉發節點用 於向用戶提供穩定的轉發服務，或在系統啟動時啟動路由轉發服務。所述 的用戶節點是網絡系統中接受路由優化服務的客戶。上述的服務節點、轉 發節點以及用戶節點之間相互連接，從而構成所述的覆蓋網。覆蓋網中各 種類型的節點都不限於一個。
在上述覆蓋網中，不同用戶節點間做數據通信時存在默認的路徑，但 這些默認路徑會由於各種各樣的原因而發生故障，因此需要採用本發明的 方法從網絡中選擇合適的轉發節點，進而構建最適合的備用路徑，使得默
15換到這些備用路徑上實現用戶節點間的繼續通 信。本發明在為用戶節點選擇轉發節點時，需要首先為覆蓋網中的各個轉
發節點構建邏輯轉發網絡(LFN， Logical Forward Network),將具有相似 性能的轉發節點分配到同 一個邏輯轉發網絡中，將性能存在明顯差異的轉 發節點分配到不同的邏輯轉發網絡中；然後再根據需要從各個邏輯轉發網 絡選擇候選鄰居轉發節點，從所述候選鄰居轉發節點中得到某一用戶節點 的轉發節點；最後就可以根據所選取的轉發節點構建備用路徑。在對本發 明的上述實現方法做進一步說明前，首先對其中所涉及到的概念、算法做 統一的i兌明。
一、綜合性能相似度計算方法
在前面已經提到，本發明需要將整個覆蓋網中具有相近性能的轉發節 點分配到同一邏輯轉發網絡中。對轉發節點的這一分配過程可通過綜合性 能相似度計算方法實現。
在這一計算方法中，首先從覆蓋網中選取一個轉發節點，然後用這一 轉發節點對覆蓋網中所有的標誌伺服器節點做網絡測距，得到關於延遲、 丟包率和瓶頸帶寬的指標。若覆蓋網中的標誌伺服器節點有n個，則轉發 節點的網絡測距結果由n個分量組成，每個分量包括該轉發節點對一個標 志伺服器節點的網絡測距結果。對覆蓋網中的所有轉發節點都做上述搡 作，即可得到所有轉發節點的網絡測距結果。
在得到轉發節點的網絡測距結果後，就可以根據網絡測距結果計算轉 發節點間的兩兩相似度。在前面已經提到，網絡測距結果包括關於延遲、 丟包率和瓶頸帶寬的指標，因此，轉發節點間的相似度可分為延遲相似度 DAV 、丟包率相似度LsAv和瓶頸帶寬相似度BwAv 。
假設要計算某一覆蓋網中的兩個轉發節點A、 B間的相似度，該覆蓋 網中的標誌伺服器節點有n個，用Li, L2…Ln表示，則用D化表示轉發節
點X與某一標誌伺服器節點Li間的延遲，其中Xe(A,B)， Lje(L,，L2,…,Ln)。 同樣的，可以用Lsxt,表示轉發節點X與某 一標誌伺服器節點Li間的丟包率， 用Bw&表示轉發節點X與某一標誌伺服器節點Lj間的瓶頸帶寬。轉發節 點A、 B間的延遲相似度D^、丟包率相似度Ls^和瓶頸帶寬相似度Bw^可 採用如下公式計算
formula see original document page 16lsav = V(Lsal, —lsbLi)2十(Ls亂2 — LsBL2)2 + —LsBLn)
BwAv = V(Bw^ — BwBL| )2 + (Bw亂2 - BwBL2 )2 +…+ (Bw亂。-
BwBL )
在得到延遲相似度D^、丟包率相似度LsAv和瓶頸帶寬相似度Bw^後, 可進一步計算兩個轉發節點間的綜合性能相似度I^,其計算公式如下
在上述公式中，《、 "、 y為常量值，它們的大小與網絡系統對具體性 能的要求有關，若網絡系統對丟包率的要求較高，則〃的數值與"、y相比 就相對4交高。
二、 限界廣度優先算法BFBB
限界廣度優先算法BFBB是在覆蓋網的網絡拓樸圖中基於拓樸分析尋 找轉發節點的方法。該方法包括以下步驟
步驟1)、計算拓樸圖中每個節點的度(degree)和核度(coreness )。 度的大小由拓樸圖中與節點相交的邊的個數而定，而核度的大小也可通過 現有技術計算得到。在參考文獻3 "A. Hamelin， J. Lgnacio， D. A. Luca, B. Alain and V. Alessandro. k-core decomposition: a tool for the visualization of large scale networks, http:〃arxiv.org/abs/cs.NI/0511007, 2005"中有對如何計 算核度的詳細說明。
步驟2)、在拓樸圖中選擇一個節點作為當前節點，並計算兩個變量 REF和Cornref的值,其中REF = degree/coreness, Cornref = coreness。
步驟3)、在當前節點調用廣度優先算法，在拓樸圖上選取coreness >= Cornref且degree/coreness 〉 REF的節點，若所能找到的節點個數無法達到 用戶的要求，則繼續執行下一步。
步驟4 )、令REF=REF-1後，重新執行前一步驟。
步驟5)、將查找到的節點返回後，結束計算過程。
三、 IPtoAS算法
該算法主要用於通過IP位址查找該IP位址所屬的AS (自治域)，其 實現包括以下步驟
1、 得到熟知的AS號及其所擁有IP前綴的對照表
2、 將所有IP前綴存儲為一顆Trie樹，葉子節點為AS號3、依據所輸入的IP位址IPi，查詢Trie樹，依據最長匹配的原則，選 取對應的AS號ASj，然後將結果返回。
在對本發明所涉及的算法統一做解釋說明後，下面結合附圖對本發明 進行說明。
在圖1所示的覆蓋網絡中，包括有標誌伺服器節點(用L表示)、接 入伺服器節點(用S表示)、轉發節點(用F表示)以及用戶節點(用C 表示)。上述各類節點存在於不同的AS域內。
在某 一 時刻，如覆蓋網絡初次啟動時，將覆蓋網中的所有轉發節點(包 括有轉發功能的服務節點)按照性能構建邏輯轉發網絡，從而將具有近似 性能的轉發節點分配到同一邏輯轉發網絡中。在構建邏輯轉發網絡時，根 據前述的綜合性能相似度計算方法所述，由各個轉發節點對所有的標誌服 務器節點進行探測，測量其到標誌伺服器節點的延遲，丟包率和瓶頸帶寬， 進而利用前述的公式(1) 一公式(4)對各個轉發節點間的綜合性能相似 度進行計算。在得到所有轉發節點相互間的綜合性能相似度後，可對所有 的相似度結果進行排序，然後再將排序結果分段，從而把綜合性能相近的 轉發節點分配到一起，從而構建出多個邏輯轉發網絡。由於在邏輯轉發網 絡中，轉發節點之間需要定期地進行路徑性能的探測，並發布探測結果， 因此需要對邏輯轉發網絡中轉發節點的數目進行控制，以避免由於轉發節 點的數量太多而導致系統開銷太大的問題。因此，在本實施例中，將一個 邏輯轉發網絡規模限制為50個轉發節點，如果某一邏輯轉發網絡內所包 含的轉發節點數超過50,則可將這一邏輯轉發網絡拆分。以圖2為例，從 AS1到AS7的多個自由域中，各自有不同數目的轉發節點，這些轉發節點 按照性能分別被分配到了 LFN1、 LFN2、 LFN3三個邏輯轉發網絡中，一 個邏輯轉發網絡所包含的轉發節點並不局限於某一 AS，而是不同AS內轉 發節點的集合。此外，雖然在圖2中在一個AS內對於某一邏輯轉發網絡 只示出了一個節點，但這一節點實際上由多個轉發節點組成，只是對外以 一個節點的形式表示。這類節點也被稱為邏輯轉發網絡中的邏輯節點 (LN)。如圖3所示， 一個邏輯轉發網絡在一個AS內的一個邏輯節點擁 有多個(這裡是5)個轉發節點，這些屬於同一邏輯節點的所有轉發節點 間卩波此全互連。
為了適應前述邏輯節點的現象，所有在一個AS內且屬於同一邏輯轉 發網絡的所有轉發節點會對外推選出一個入口轉發節點(AC)，由該節點向用戶節點分配具體的轉發節點以及負責本邏輯轉發網絡內不同邏輯節
點之間鏈路性能的探測。如圖3所示，轉發節點F6就是在一個AS內所擁 有的5個轉發節點的入口轉發節點。入口轉發節點在做鏈路性能探測時， 主要探測該入口轉發節點與鄰居域的入口轉發節點間路徑的延遲、丟包率 和瓶頸帶寬，所得到的探測結果會存儲在鏈路狀態表中。在一個實例中， 假設一入口轉發節點ACi向鄰居域的入口轉發節點ACj發起鏈路性能探 測，所得到的探測結果保存在自身的鏈路狀態表中。ACi每過30秒，將自 己的鏈路狀態表定期發送給鄰居ACj,鄰居ACj收到後，跟自己的鏈路狀 態表進行比較更新。 一種優選的更新順序是優先比較延遲，其次是丟包率， 最後比較瓶頸帶寬，當然這一更新順序也可根據需要改變。每個AC要將 自己的鏈路狀態表同本AS內的其他同屬一個邏輯轉發網絡的轉發節點進 行共享。每隔15分鐘重複上述過程，以保持鏈路的實時狀態。在圖4中 對鏈路狀態表的上述傳遞過程做了示意性說明。需要說明的是，此次所涉 及的鏈路狀態表更新時間的間隔只是舉例說明之用，在實際應用中並不限 於上述時間間隔。
在為覆蓋網絡中的各個轉發節點構建邏輯轉發網絡後，若有新的轉發 節點加入覆蓋網絡(可以是新部署的專用轉發節點，也可以是由性能優異、 在線時間穩定的用戶節點所提升的轉發節點)，則利用新的轉發節點對標 志伺服器節點做網絡測距，測量其到標誌伺服器節點的延遲，丟包率和瓶 頸帶寬。然後從每個已經產生的邏輯轉發網絡中隨機選取一個轉發節點， 調用前述的綜合性能相似度計算方法，計算新增加的轉發節點與這些隨機 選擇的轉發節點之間的綜合性能相似度。在前面的說明中已經提到，在生 成邏輯轉發網絡時，是將所有轉發節點間的綜合性能相似度做排序、分段 後得到的，因此每個邏輯轉發網絡對應有一段特定的綜合性能相似度區 間。因此，在得到新增加的轉發節點與隨機選擇的轉發節點間的綜合性能 相似度後，先選擇其中的最大值，然後將該最大值與所對應的隨機選擇的 轉發節點所在邏輯轉發網絡的綜合性能相似度區間進行比較，若最大值在 這一區間內，則新增加的轉發節點就在該隨機選擇的轉發節點所在邏輯轉 發網絡內。若最大值並不在這一區間內，則從新增加的轉發節點與這些隨 機選擇的轉發節點間的綜合性能相似度中選擇次大值，繼續前述的比較過 程，根據比較結果決定新增加的轉發節點是否能夠加入到相應的邏輯轉發 網絡內。如果新增加的轉發節點無法加入任何已有的邏輯轉發網絡，則該新增加的轉發節點形成一個新的邏輯轉發網絡。在將新增加的轉發節點加 入已有邏輯轉發網絡的過程中，如果邏輯轉發網絡在加入新的轉發節點 後，超出了規模限制，則分裂該邏輯轉發網絡。
覆蓋網絡在如前所述構建邏輯轉發網絡後，即可向用戶節點提供選取 轉發節點從而構建備用路徑的服務。以圖5所示的覆蓋網絡為例，在整個
網絡中包括有三個邏輯轉發網絡，分別用LFN1、 LFN2、 LFN3表示。LFN1 所包含的轉發節點在AS1、 AS2、 AS3、 AS4、 AS5內，而LFN2所包含的 轉發節點在AS1、 AS3、 AS4、 AS5和AS6內，LFN3所包含的轉發節點 在AS1、 AS2、 AS3、 AS4、 AS5和AS6內。在AS1內有一個用戶節點， 用Cl表示。在某一時刻，用戶節點C1發起請求轉發節點的消息，為該 用戶節點選取轉發節點的操作如下。
覆蓋網絡中的接入伺服器節點在收到用戶節點Cl的請求轉發節點消 息後，運行前述的IPtoAS算法，知道用戶節點所在的AS,從圖5可以知 道，Cl所在的AS為AS1。然後對AS1內所包含的邏輯轉發網絡的個數 進行查詢，根據請求轉發節點消息中所請求的轉發節點的個數，選擇盡可 能多的邏輯轉發網絡，並將這些邏輯轉發網絡在AS1內的入口轉發節點通 知Cl。假設在一個實例中，用戶節點Cl所請求的轉發節點的個數有4個， 由於AS1內所包含的邏輯轉發網絡的個數有3個，因此邏輯轉發網絡 LFN1 、 LFN2、 LFN3都被選中，並將它們的入口轉發節點的地址都發送給 Cl。當然，如果用戶節點Cl所請求的轉發節點的數目小於AS1內所包含 的邏輯轉發網絡的個數，則在AS1內可任意選擇與所請求的轉發節點數目 相同的邏輯轉發網絡。
用戶節點Cl在得到各個邏輯轉發網絡的入口轉發節點的地址後，向 這些入口轉發節點各自發出請求轉發節點的消息。各個入口轉發節點在收 到請求轉發節點的消息後，依據負載平衡的原則，在所屬LN中選取一個 合適的轉發節點以服務於用戶節點Cl,幫助用戶節點Cl進一步查找所需 要的轉發節點。由於本步驟選取的轉發節點起到服務的作用，因此，這一 轉發節點也被稱為服務轉發節點，用LFNs表示。如圖5所示，用戶節點 C1在LFN1、 LFN2、 LFN3中各自查找一個服務轉發節點，分別用LFNs,、 LFNs,和LFN&表示。由於這些服務轉發節點都是由入口轉發節點在自身所 屬的LN中找到的，因此它們都存在於AS1中。
在得到服務轉發節點LFNSi後，由這些服務轉發節點在各自的邏輯轉發
20網絡上運行前述的BFBB算法，選取拓樸位置合適的n個AS，並隨機地 從這n個AS中選擇m個屬於該邏輯轉發網絡的轉發節點。其中，所述的 n的大小為用戶請求的轉發節點數目與伺服器在用戶節點所在AS中選中 的LFN網絡的個數的商；所述的m的個數通常為1或2，也可根據系統 情況確定。此次計算過程中所得到的轉發節點被稱為 一次候選轉發節點。 仍然以圖5所示的實例為例，用戶節點Cl通過服務轉發節點LFNs,、 LFNs2 和LFN&分別在LFN1、 LFN2、 LFN3上找到了一個轉發節點，這3個轉發 節點形成了一次候選轉發節點。由於轉發節點的作用是在不同AS域間建 立路徑，因此所得到的一次候選轉發節點一定不存在於用戶節點Cl所在 的AS1中，而是在其他AS內，如對於LFN1而言，可能在AS2或AS3 或AS4或AS5內。假設LFN1內所選取的轉發節點位於AS3內，LFN2 所選取的轉發節點位於AS5內，LFN3所選取的轉發節點也位於AS5內。
在得到一次候選轉發節點後，需要將它們返回給用戶節點Cl。在用 戶節點Cl上保存有一張一次候選轉發節點列表，將新得到的一次候選轉 發節點與所述的 一次候選轉發節點列表進行比較，若某一一 次候選轉發節 點已經存在於用戶節點Cl的一次候選轉發節點列表中，則忽略，否則用 戶節點Cl將自身的IP(SourceIP)地址信息發送給該一次候選轉發節點，由 這一一次候選轉發節點根據IP位址信息和IPtoAS算法得到用戶節點Cl 所在的AS，然後在該候選轉發節點所保存的鏈路狀態表中查詢候選轉發 節點所在AS到用戶節點Cl所在AS的鏈路性能，所得到的結果返回給用 戶節點Cl並保存。對新得到的一次候選轉發節點重複執行上述操作。
前述操作所得到的 一 次候選轉發節點的數目可能已經滿足用戶節點 對轉發節點的數目要求，也可能不能滿足要求。如在本實施例中，用戶節 點Cl所要求的轉發節點為4個，而一次候選轉發節點只有3個，並不能 滿足要求。對於此類情況，需要由用戶節點再次向接入伺服器節點發起請 求轉發節點消息，以第二次進行候選轉發節點的選取。在進行第二次候選 轉發節點的選取時，為了避免所選取的轉發節點與一次候選轉發節點相衝 突，採用與選取一次候選轉發節點時不同的選取方法。具體的說，接入服 務器節點在收到請求轉發節點的消息後，在整個AS網絡拓樸圖上運行 BFBB算法尋找合適的AS,在找到AS後，從中選出所需數目的轉發節點， 在選取過程中應當儘量保證所選擇的轉發節點不屬於用戶節點所在AS內 的邏輯轉發網絡。例如，在圖5中已經知道，Cl所在的AS為AS1，而AS1中所包含的邏輯轉發網絡有LEN1、 LEN2、 LEN3。那麼在第二次選 取轉發節點的過程中，儘量不要選取LEN1、 LEN2、 LEN3中所包含的轉 發節點。如在AS3中存在F4，它不屬於前述的LEN1、 LEN2、 LEN3,因 此可以將它作為所要選擇的候選轉發節點。只有在整個覆蓋網絡中，不存 在獨立於用戶節點所在AS內的邏輯轉發網絡的轉發節點時，才在這些邏 輯轉發網絡中選擇相應的轉發節點。即使如此，也要儘量避免選擇那些已
經被選入一次候選轉發節點中的轉發節點。為了與 一次候選轉發節點相區 別，此次選擇所得到的轉發節點被稱為二次候選轉發節點。對於每個二次 候選轉發節點，由於不是通過用戶節點Cl所在AS內的邏輯轉發網絡選 取的，因此不能通過查詢Cl所在AS內的邏輯轉發網絡的鏈路狀態表， 獲取C1到每個二次候選轉發節點的路徑性能，因此，Cl需要對每個二次 候選轉發節點進行周期型的路徑性能探測，並將探測結果保存到用戶節點 Cl的鏈路狀態表中，以備構造備用路徑之用。
用戶節點Cl在得到候選轉發節點後，就可以根據業務的需求選擇具 體的轉發節點，從而構建相應的備用路徑。如圖6所示，在本實施例中， 假設要在圖5所示的覆蓋網絡的基礎上，實現用戶節點Cl與用戶節點C2 間的通信。
用戶節點Cl首先需要確定業務的類型，然後根據業務類型確定該業 務對哪一個性能指標更為敏感，從而決定路徑的門限指標Th。假設用戶節 點C1、 C2間的業務為文件傳輸業務，則該業務對丟包率和瓶頸帶寬更加 敏感，因此將與丟包率和瓶頸帶寬有關的數值作為路徑的門限指標。此外， 還要提取出業務傳輸源地址(即Cl的IP位址)和業務傳輸目的地址(即 C2的IP位址)。
用戶節點Cl的候選轉發節點中至少包括一次候選轉發節點，因此首 先從一次候選轉發節點中選取節點做性能檢測，以得到可行的轉發節點。 已知用戶節點C1的一次候選轉發節點有3個，按序選擇其中的一個候選 轉發節點，假設先選擇LFN1中且位於AS3內的候選轉發節點，對所選擇 的候選轉發節點做性能檢測。在性能檢測過程中，用戶節點C1將業務傳 輸目的地址(即C2的IP位址)發送給所選擇的候選轉發節點，該節點運 行所述的IPtoAS算法後查找到用戶節點C2所在的AS，然後在候選轉發 節點自身的鏈路狀態表中查詢從候選轉發節點所在的AS到用戶節點C2 所在的AS的鏈路屬性，如果能夠找到，則將所找到的鏈路屬性信息返回給用戶節點Cl,如果不能找到，則候選轉發節點發起對用戶節點C2的探 觀'J，將探測得到的鏈路屬性信息返回給用戶節點Cl。用戶節點Cl得到從
候選轉發節點到用戶節點C2的鏈路屬性信息後，將該信息與用戶節點Cl 的鏈路狀態表中所記錄的用戶節點Cl到候選轉發節點的鏈路屬性信息進 行加權，從而得到從用戶節點Cl (即業務傳輸源)經由候選轉發節點到 用戶節點C2 (即業務傳輸目的)的整條路徑的鏈路屬性信息。在前面的 說明中已經提到，鏈路屬性信息包括延遲、丟包率和瓶頸帶寬等多個性能 的相關信息，因此可以將所得到的鏈路屬性信息與為該業務設定的路徑門 限指標Th進行比較，若能達到路徑門限指標Th,則所述的候選轉發節點 將作為可行的轉發節點並保存相關的信息，若不能達到路徑門限指標Th， 則忽略該候選轉發節點。對於一次候選轉發節點中的其它候選轉發節點做 類似的操作，從而得到這些候選轉發節點能否成為可行的轉發節點的結 論。
從一次候選轉發節點得到可行的轉發節點後，可行的轉發節點的數目 可能多於用戶的需求，此時從可行的轉發節點中選取若干個轉發節點作為 最佳的轉發節點，若可行的轉發節點的數目少於用戶的需求，則需要繼續 從二次候選轉發節點中選取可行轉發節點。雖然在本實施例中，用戶節點
Cl的二次候選轉發節點只有1個，但在多數情況下，二次候選轉發節點 的數目多於1個，因此同樣按序依次選擇一個節點做性能檢測。在性能檢 測過程中，由於在多數情況下，二次候選轉發節點不屬於用戶節點所在 AS內的邏輯轉發網絡中的節點，因此，無法通過查詢鏈路狀態表的方式 得到二次候選轉發節點到作為業務傳輸目的的用戶節點C2的鏈路屬性信 息。因此，作為業務傳輸源的用戶節點Cl將用戶節點C2的IP位址發送 給候選轉發節點，由該節點對用戶節點C2發起探測，探測所得到的從候 選轉發節點到用戶節點C2的鏈路屬性信息將返回給用戶節點Cl。用戶節 點Cl將候選轉發節點所返回的候選轉發節點到用戶節點C2的鏈路屬性信 息與用戶節點ci的鏈路狀態表中所記錄的用戶節點Cl到候選轉發節點的 鏈路屬性信息進行加權，從而得到從用戶節點Cl (即業務傳輸源)經由 候選轉發節點到用戶節點C2 (即業務傳輸目的)的整條路徑的鏈路屬性 信息。在得到整條路徑的鏈路屬性信息後，可將其與路徑門限指標Th進 行比較，根據比較結果確定是否將該候選轉發節點作為可行的轉發節點。 當二次候選轉發節點中的節點數目多於1個時，對於其它節點同樣做此類操作。
從上述說明可以看出，由一次候選轉發節點和二次候選轉發節點可得 到可行轉發節點，並由可行轉發節點進而得到最佳可行轉發節點。在一個 可選實現方式中，若所要執行的業務不僅僅是對延遲，丟包率和瓶頸帶寬 等鏈路性能中的 一個或者多個敏感，則需要對由最佳可行轉發節點確定的 備用路徑進一步探測最能影響該業務性能的其他指標，如抖動、可用帶寬 等，並根據探測結果對最佳可行轉發節點做進一步的篩選。
在得到最佳可行轉發節點後，當所監測的原路徑性能在此期間發生了 從良好到惡化的變化，從而需要做路徑切換時，切換至最佳可行轉發節點，
通過這些轉發節點轉發數據，或通過Overlay路徑與默認路徑的組合同時 發送數據，增加通信魯棒性，並同時監測原路徑的性能。在此期間，如果 原路徑性能恢復，則切換回原路徑。
本發明還提供了與前述方法相對應的覆蓋網備用路徑生成裝置，用於 在包括接入伺服器節點、標誌伺服器節點、轉發節點和用戶節點的覆蓋網 上為源用戶節點選取合適的轉發節點以構建從源用戶節點到目的用戶節 點的備用路徑，該裝置包括邏輯轉發網絡創建模塊、 一次候選轉發節點選 取模塊以及性能檢測模塊；其中，
所述的邏輯轉發網絡創建模塊利用所述覆蓋網中的標誌伺服器節點 對所述轉發節點做網絡測距，根據網絡測距結果計算任意兩個轉發節點間 的綜合性能相似度，由所述綜合性能相似度為具有相近性能的轉發節點構 建邏輯轉發網絡；其中，在所述覆蓋網的一個自由域內屬於同一邏輯轉發 網絡的轉發節點擁有同 一個入口轉發節點；
所述的 一次候選轉發節點選取模塊用於由所述接入伺服器節點根據
所述用戶節點的請求轉發節點消息在所述用戶節點所在的自由域中選擇 邏輯轉發網絡，然後通過所述邏輯轉發網絡的入口轉發節點找到與所述入 口轉發節點在同 一 自由域且同 一邏輯轉發網絡的轉發節點作為服務轉發 節點；所述服務轉發節點在所在的邏輯轉發網絡上運行BFBB算法，根據 該算法的運行結果選擇轉發節點作為 一次候選轉發節點；其中，
所述的BFBB算法在計算網絡拓樸圖中每個節點的度和核度後，在當 前節點上通過廣度優先算法在所述網絡拓樸圖上選取核度值大於當前節 點的核度值，且度與核度的商大於當前節點的度與核度的商的節點；若所 能找到的節點的數目無法滿足要求，則將當前節點的度與核度的商的值遞
24減後，重新在當前節點上利用廣度優先算法選取核度值大於當前節點的核 度值，且度與核度的商大於當前節點的度與核度的商的節點，直到滿足對 所選取節點的數目要求；
所述的性能檢測模塊用於對候選轉發節點所能形成的路徑做性能檢 測，保留通過性能檢測的候選轉發節點，在所述用戶節點間進行業務通信 時，根據業務從所保留的候選轉發節點中選擇合適的轉發節點以構建備用 路徑。
在另一個實施例中，覆蓋網備用路徑生成裝置還包括二次候選轉發節
點選取模塊，該模塊用於在所述覆蓋網的網絡拓樸圖上運行BFBB算法， 然後根據所述BFBB算法的計算結果，從所述覆蓋網中選取一個自由域， 在該自由域內選擇轉發節點作為二次候選轉發節點；所選取的轉發節點盡 量不屬於所述第 一用戶節點所在自由域內的邏輯轉發網絡。
本發明的方法與現有的Overlay技術中採用的簡單大強度探測和全互 聯路由通告方式相比，通過獲取並有效分析、利用底層的拓樸知識以及對 轉發節點進行合理的分域，從而顯著地提高轉發鄰居節點的命中率。而轉 發節點內部通過提前探測，實時地感知鏈路狀態，不僅顯著降低了 Overlay 節點的探測強度和規模，也可以有效地對轉發節點進行篩選，優化Overlay 路由，當網絡故障或性能不穩定時，可通過路徑切換，有效提高網絡的傳 輸和容錯能力，保證通信的穩定性。
本發明不僅適用於Overlay網絡中的終端^各徑切換，也可作為進行 Internet路徑分集傳輸系統的多路徑創建基礎，具有相當廣闊的應用前景。
最後所應說明的是，以上實施例僅用以說明本發明的技術方案而非限 制。儘管參照實施例對本發明進行了詳細說明，本領域的普通技術人員應當 理解，對本發明的技術方案進行修改或者等同替換，都不脫離本發明技術方 案的精神和範圍，其均應涵蓋在本發明的權利要求範圍當中。
權利要求
1、一種覆蓋網備用路徑生成方法，用於在包括接入伺服器節點、標誌伺服器節點、轉發節點和用戶節點的覆蓋網上為源用戶節點選取合適的轉發節點以構建從源用戶節點到目的用戶節點的備用路徑，該方法包括步驟1)、利用所述覆蓋網中的標誌伺服器節點對所述轉發節點做網絡測距，根據網絡測距結果計算任意兩個轉發節點間的綜合性能相似度，由所述綜合性能相似度為具有相近性能的轉發節點構建邏輯轉發網絡；其中，在所述覆蓋網的一個自由域內屬於同一邏輯轉發網絡的轉發節點擁有同一個入口轉發節點；步驟2)、所述接入伺服器節點根據所述用戶節點的請求轉發節點消息在所述用戶節點所在的自由域中選擇邏輯轉發網絡，然後通過所述邏輯轉發網絡的入口轉發節點找到與所述入口轉發節點在同一自由域且同一邏輯轉發網絡的轉發節點作為服務轉發節點；所述服務轉發節點在所在的邏輯轉發網絡上運行BFBB算法，根據該算法的運行結果選擇轉發節點作為一次候選轉發節點；其中，所述的BFBB算法在計算網絡拓撲圖中每個節點的度和核度後，在當前節點上通過廣度優先算法在所述網絡拓撲圖上選取核度值大於當前節點的核度值，且度與核度的商大於當前節點的度與核度的商的節點；若所能找到的節點的數目無法滿足要求，則將當前節點的度與核度的商的值遞減後，重新在當前節點上利用廣度優先算法選取核度值大於當前節點的核度值，且度與核度的商大於當前節點的度與核度的商的節點，直到滿足對所選取節點的數目要求；步驟3)、對候選轉發節點所能形成的路徑做性能檢測，保留通過性能檢測的候選轉發節點，在所述用戶節點間進行業務通信時，根據業務從所保留的候選轉發節點中選擇合適的轉發節點以構建備用路徑。
2、 根據權利要求1所述的覆蓋網備用路徑生成方法，其特徵在於， 在所述步驟2)中所得到的一次候選轉發節點的數目小於用戶的需求時， 在所述的步驟2)和所述的步驟3)之間還包括選取二次候選轉發節點的 步驟，該步驟包括在所述覆蓋網的網絡拓樸圖上運行BFBB算法；根據所述BFBB算法的計算結果，從所述覆蓋網中選取一個自由域，在該自由域內選擇轉發節點作為二次候選轉發節點；所選取的轉發節點盡 量不屬於所述第一用戶節點所在自由域內的邏輯轉發網絡。
3、 根據權利要求1或2所述的覆蓋網備用路徑生成方法，其特徵在 於，所述的步驟1 )包括步驟1-1)、所述覆蓋網中的所有轉發節點對所述覆蓋網中的所有標誌 伺服器節點做網絡測距，得到關於延遲、丟包率和瓶頸帶寬的指標；步驟1-2)、根據所述指標計算任意兩個轉發節點間的綜合性能相似度；步驟l-3)、對所有的綜合性能相似度結果做排序，然後為所述排序結 果分段，將具有相近綜合性能的轉發節點分配到同一個邏輯轉發網絡。
4、 根據權利要求3所述的覆蓋網備用路徑生成方法，其特徵在於， 所述的步驟1 )還包括步驟i_4)、由所述邏輯轉發網絡的入口轉發節點向鄰居域的入口轉發 節點做鏈路性能探測；所述鏈路性能包括路徑的延遲、丟包率和瓶頸帶寬；步驟1-5)、所述鏈路性能探測的結果保存到入口轉發節點的鏈路狀態 表中，所述鏈路狀態表的信息定時向鄰居域的入口轉發節點更新。
5、 根據權利要求3或4所述的覆蓋網備用路徑生成方法，其特徵在 於，在所述的步驟l-2)中，所述綜合性能相似度釆用下列公式計算I旭表示節點A與節點B之間的綜合性能相似度，D^表示節點A與節 點B間的延遲相似度，"Av表示節點A與節點B間的丟包率相似度，Bwav 表示節點A與節點B間的瓶頸帶寬相似度，"、〃、Z為網絡系統對性能 的要求有關的常量值；其中，DAv = V(D— DBL| )2 + ("°亂2 — dbl2 )2 +…+ (D al — DBLn )2LS八v = V(lsal, - lsbl|)2 +(lsal2 - lsbl2)2 + .'. + (lsal - lsbl fBwAv = ^(Bw亂，—BwBL' )2 + (BWaL2 - BwBL2 )2 +…+ (Bw亂。_ BwBLn )2表示節點A與覆蓋網中第i個標誌伺服器節點間的延遲指標，LSal, 表示節點A與覆蓋網中第i個標誌伺服器節點間的丟包率指標，Bw^表示節點A與覆蓋網中第i個標誌伺服器節點間的瓶頸帶寬指標。
6、 根據權利要求1或2所述的覆蓋網備用路徑生成方法，其特徵在 於，所述的步驟2)包括步驟2-l )、所述接入伺服器節點根據所述用戶節點發起的請求轉發節 點消息在所述用戶節點所在自由域中選擇邏輯轉發網絡，並將所述邏輯轉 發網絡的入口轉發節點的地址通知所述用戶節點；步驟2-2 )、所述入口轉發節點根據所述用戶節點發起的請求轉發節點 消息選取一個與該入口轉發節點具有相同自由域和相同邏輯轉發網絡的 轉發節點，作為為所述用戶節點服務的服務轉發節點；步驟2-3 )、所述服務轉發節點在自身的邏輯轉發網絡上運行BFBB算 法，根據算法的運行結果在所述覆蓋網中選擇有別於所述JI良務轉發節點所 在自由域的自由域，然後在所述自由域內選擇與該服務轉發節點具有相同 邏輯轉發網絡的轉發節點作為 一次候選轉發節點，所述一次候選轉發節點 返回給所述的第一用戶節點。
7、 根據權利要求6所述的覆蓋網備用路徑生成方法，其特徵在於， 所述的步驟2)還包括步驟2-4)、所述用戶節點將接收到的一次候選轉發節點與自身的一次 候選轉發節點列表進行比較；步驟2-5)、所述用戶節點向不存在於所述列表中的新的轉發節點發送 自身的信息，從而在所述新的轉發節點的鏈路狀態表中查詢所述新的轉發 節點所在自由域與所述用戶節點所在自由域之間的鏈路屬性信息；步驟2-6 )、所述鏈路屬性信息返回並保存到所述用戶節點。
8、 根據權利要求6或7所述的覆蓋網備用路徑生成方法，其特徵在 於，在所述的步驟2-1)中，所述接入伺服器節點根據用戶節點發起的請 求轉發節點消息在所述用戶節點所在自由域中選擇邏輯轉發網絡時，選擇 儘可能多的邏輯轉發網絡。
9、 根據權利要求2所述的覆蓋網備用路徑生成方法，其特徵在於， 在所述的選取二次候選轉發節點的步驟後，還包括所述的用戶節點對所述的二次候選轉發節點做周期性的路徑性能探 測，並將探測結果保存到所述用戶節點的鏈路狀態表中。
10、 根據權利要求1或2所述的覆蓋網備用路徑生成方法，其特徵在 於，在所述的步驟3)中，對候選轉發節點所能形成的路徑做性能檢測包括步驟3-l )、用戶節點根據業務的類型確定路徑的門限指標； 步驟3-2)、從所述一次候選轉發節點中選擇轉發節點； 步驟3-3 )、獲取一用戶節點經由所選擇的轉發節點至另 一用戶節點的 路徑性能；步驟3-4)、將步驟3-3)所獲取的路徑性能與步驟3-l)中所確定的門 限指標進行比較，根據比較結果確定路徑是否通過了性能檢測。
11、 根據權利要求IO所述的覆蓋網備用路徑生成方法，其特徵在於， 對候選轉發節點所能形成的路徑做性能檢測還包括步驟3-5 )、當所述一次候選轉發節點中能夠通過路徑性能檢測的轉發 節點數目無法滿足用戶要求時，從所述二次候選轉發節點中選擇轉發節 點；步驟3-6 )、獲取一用戶節點經由所選擇的轉發節點至另 一用戶節點的 路徑性能；步驟3-7 )、將步驟3-6 )所獲取的路徑性能與步驟3-1 )中所確定的門 限指標進行比較，根據比較結果確定路徑是否通過了性能檢測。
12、 根據權利要求10或11所述的覆蓋網備用路徑生成方法，其特徵 在於，在所述的步驟3-3)中，獲取所述第一用戶節點經由所選擇的轉發 節點至所述第二用戶節點的路徑性能包括從所選擇的轉發節點的鏈路狀態表中查詢從所述轉發節點所在自由 域到所述第二用戶節點所在自由域間的鏈路屬性，從所述第一用戶節點的 鏈路狀態表中獲取從所述第 一用戶節點所在自由域到所述轉發節點所在 自由域的鏈路屬性，進而獲取所述第一用戶節點經由所選擇的轉發節點至 所述第二用戶節點的路徑性能；或所選擇的轉發節點通過路徑探測，得到從所述轉發節點所在自由域 到所述第二用戶節點所在自由域間的鏈路屬性，從所述第一用戶節點的鏈 路狀態表中獲取從所述第 一 用戶節點所在自由域到所述轉發節點所在自 由域的鏈路屬性，進而獲取所述第 一 用戶節點經由所選擇的轉發節點至所 述第二用戶節點的路徑性能。
13、 根據權利要求11所述的覆蓋網備用路徑生成方法，其特徵在於， 在所述的步驟3-6)中，獲取所述第一用戶節點經由所選擇的轉發節點至 所述第二用戶節點的路徑性能包括所選擇的轉發節點通過路徑探測，得到從所述轉發節點所在自由域到 所述第二用戶節點所在自由域間的鏈路屬性，從所述第一用戶節點的鏈路 狀態表中獲取從所述第 一用戶節點所在自由域到所述轉發節點所在自由 域的鏈路屬性，進而獲取所述第 一用戶節點經由所選擇的轉發節點至所述 第二用戶節點的路徑性能。
14、 一種覆蓋網備用路徑生成裝置，其特徵在於，用於在包括接入服 務器節點、標誌伺服器節點、轉發節點和用戶節點的覆蓋網上為源用戶節 點選取合適的轉發節點以構建從源用戶節點到目的用戶節點的備用路徑， 該裝置包括邏輯轉發網絡創建模塊、 一次候選轉發節點選取模塊以及性能檢測模塊；其中，所述的邏輯轉發網絡創建模塊利用所述覆蓋網中的標誌伺服器節點 對所述轉發節點做網絡測距，根據網絡測距結果計算任意兩個轉發節點間 的綜合性能相似度，由所述綜合性能相似度為具有相近性能的轉發節點構 建邏輯轉發網絡；其中，在所述覆蓋網的一個自由域內屬於同一邏輯轉發 網絡的轉發節點擁有同 一 個入口轉發節點；所述的一次候選轉發節點選取模塊用於由所述接入伺服器節點根據 所述用戶節點的請求轉發節點消息在所述用戶節點所在的自由域中選擇 邏輯轉發網絡，然後通過所述邏輯轉發網絡的入口轉發節點找到與所述入口轉發節點在同 一 自由域且同 一邏輯轉發網絡的轉發節點作為服務轉發 節點；所述服務轉發節點在所在的邏輯轉發網絡上運行BFBB算法，根據 該算法的運行結果選擇轉發節點作為 一次候選轉發節點；其中，所述的BFBB算法在計算網絡拓樸圖中每個節點的度和核度後，在當 前節點上通過廣度優先算法在所述網絡拓樸圖上選取核度值大於當前節 點的核度值，且度與核度的商大於當前節點的度與核度的商的節點；若所 能找到的節點的數目無法滿足要求，則將當前節點的度與核度的商的值遞 減後，重新在當前節點上利用廣度優先算法選取核度值大於當前節點的核 度值，且度與核度的商大於當前節點的度與核度的商的節點，直到滿足對 所選取節點的數目要求；所述的性能檢測模塊用於對候選轉發節點所能形成的路徑做性能檢 測，保留通過性能檢測的候選轉發節點，在所述用戶節點間進行業務通信 時，根據業務從所保留的候選轉發節點中選擇合適的轉發節點以構建備用 路徑。
15、根據權利要求14所述的覆蓋網備用路徑生成裝置，其特徵在於， 還包括二次候選轉發節點選取模塊，該模塊用於在所述覆蓋網的網絡拓樸 圖上運行BFBB算法，然後根據所述BFBB算法的計算結果，從所述覆蓋 網中選取一個自由域，在該自由域內選擇轉發節點作為二次候選轉發節 點；所選取的轉發節點儘量不屬於所述第一用戶節點所在自由域內的邏輯 轉發網絡。
全文摘要
本發明提供一種覆蓋網備用路徑生成方法，該方法包括利用覆蓋網中的標誌伺服器節點對轉發節點做網絡測距，計算任意兩個轉發節點間的綜合性能相似度，由綜合性能相似度為具有相近性能的轉發節點構建邏輯轉發網絡；接入伺服器節點根據用戶節點的請求轉發節點消息在用戶節點所在的自由域中選擇邏輯轉發網絡，然後通過邏輯轉發網絡的入口轉發節點找到服務轉發節點；服務轉發節點在所在的邏輯轉發網絡上運行BFBB算法，根據運行結果選擇轉發節點作為一次候選轉發節點；對候選轉發節點所能形成的路徑做性能檢測，保留通過性能檢測的候選轉發節點，在用戶節點間進行業務通信時，根據業務從所保留的候選轉發節點中選擇合適的轉發節點以構建備用路徑。
文檔編號H04L12/56GK101562568SQ20091008546
公開日2009年10月21日 申請日期2009年5月26日 優先權日2009年5月26日
發明者張國清, 李彥君, 楊清峰 申請人:中國科學院計算技術研究所