[發明專利]確定路由路徑的方法

有效

• 申請號: 200910150962.4
• 申請日: 2009-06-29
• 公開（公告）號: CN101616089A
• 公開（公告）日: 2009-12-30
• 發明（設計）人: N·施萬;T·施特勞斯;M·湯姆蘇
• 申請（專利權）人: 阿爾卡特朗訊
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 北京市金杜律師事務所
• 代理人: 王茂華;黃耀鈞

技術領域

本發明涉及確定端到端覆蓋網絡中的路由路徑的方法，以及執 行所述方法的計算機程序產品和網絡節點。

背景技術

端到端(＝P2P)覆蓋網絡用于多種應用，諸如VoIP(例如，Skype) 或者文件共享(例如，eMule)(VoIP＝互聯網協議語音)。通過分 布式架構以及將數據存儲在集中提供和使用的資源上，實現了例如 高可擴展性、自組織以及容錯之類的特征。P2P網絡包括充當端的 節點，也即充當網絡的客戶端和服務器二者。在下文描述中，術語 “節點”和“端”將互換使用。網絡的每個節點維護去往其他節點 的一個或多個邏輯鏈路，這些鏈路是按照覆蓋算法建立的，并且用 于消息傳輸。

現有技術P2P網絡基于覆蓋特定的算法來構建邏輯拓撲結構， 這些算法并不了解底層網絡基礎設施。每個節點維護去往其他節點 的一個或多個鏈路，這些鏈路用于按照廣播方式的消息路由(非結 構化覆蓋，例如Gnutella)或者基于ID方式的消息路由(使用分布 式哈希表(＝DHT)的結構化覆蓋，例如Chord)(ID＝標識/標識符)。 某些系統使用具有非結構化端群組的混合型架構，并且這些群組在 較大的拓撲(例如，Skype)中是結構化的。對路由算法進行優化， 以便最小化邏輯覆蓋中的中間轉發端的跳數。

圖1a示出了一個現有技術的結構化P2P覆蓋網絡N，其包括多 個節點0、20、50、87、112、140、179、200、211、223和240。特 別地，圖1a示出了Chord環N。Chord環N中的路由基于節點20 維護的去往多個鄰居0、50、87、112、179的鏈路PL、SL、SC1、 SC2、SC3、SC4。這些鏈路用于向目的地端逐跳地轉發消息。在源 和目的地端之間不需要直接連接。在Chord中，節點維護去往其前 驅節點和后繼結點的直接連接，這導致了環形拓撲。例如，在圖1a 中所示的Chord環N中，節點20維護去往其前驅節點0的直接連接 PL以及去往其后繼結點50的直接連接SL。此外，節點維護具有額 外快捷路徑(shortcut)的指針表(finger?table)，這些快捷路徑用 于消息路由，并且包括在ID空間中位于2的指數距離的端之后的那 些節點。例如，在圖1a所示的Chord環N中，節點20維護去往節 點50、87、112、179的快捷路徑鏈路SC1、SC2、SC3、SC4。圖1b 示出了與節點20相關聯的指針表FT，其中列出了節點20維護有去 往這些節點的快捷路徑鏈路的節點。通過維護指針表FT，具有Chord 架構的網絡內的節點實現了log?n階(即，O(log?n))的最大跳數， 其中n是網絡中的節點數。

發明內容

本發明的目的是提供一種在端到端覆蓋網絡中確定路由路徑的 改進方法。而且，本發明的目的是提供執行該改進方法的相應計算 機程序產品以及相應網絡節點。