[發明專利]一種物理網絡感知的覆蓋網構建方法

無效

• 申請號: 201010161392.1
• 申請日: 2010-05-04
• 公開（公告）號: CN101826986A
• 公開（公告）日: 2010-09-08
• 發明（設計）人: 盧錫城;李東升;張一鳴
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/56
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

技術領域

本發明涉及計算機網絡和網絡計算系統中的覆蓋網構建方法，尤其是感知物理網絡延遲的覆蓋網構建方法。

背景技術

網絡計算的目標是將廣域分布的計算、存儲、信息以及儀器等各種資源通過網絡組織并集成起來，以實現網絡資源的有效共享和綜合利用。當前，網絡計算技術在科學研究、電子商務、電子政務和軍事應用等重要領域都有著廣闊的應用前景。

網絡資源的有效組織是網絡計算系統實現資源共享和利用的重要基礎，對網絡計算系統的性能和可擴展性等都有著關鍵的影響。覆蓋網是近年來興起的一種重要的網絡資源組織技術。覆蓋網(Overlay?Network)是指網絡計算系統中節點間根據其邏輯關聯關系形成的、架構在互聯網之上的邏輯網絡。近年來隨著覆蓋網技術的發展，利用覆蓋網技術組織大規模的網絡資源，展現出良好的可擴展性和自組織潛力，得到了學術界和工業界的關注和重視。

覆蓋網構建方法是在覆蓋網中的節點之間按照一定的規則建立邏輯上的連接關系，是形成覆蓋網拓撲結構、影響覆蓋網性能的基礎性關鍵技術。覆蓋網構建方法的評價通常是以該方法所構建的覆蓋網拓撲的節點度數和路由延遲等參數作為重要指標。節點度數是指覆蓋網中各節點的鄰居數量，涉及到覆蓋網中各節點的鄰居狀態存儲開銷和覆蓋網的動態維護開銷；路由延遲是指覆蓋網中一次消息路由的延遲，通常用覆蓋網中的邏輯跳步數或物理延遲來表示。為取得良好的實用性能，覆蓋網構建方法應該兼顧覆蓋網節點度數和路由延遲等多個方面的特性。但這幾個性能特性之間存在沖突，給覆蓋網構建帶來困難。典型的覆蓋網構建方法包括Chord、CAN和Tapestry等，下面予以簡要介紹。

(1)Chord方法

Chord方法采用環作為覆蓋網的靜態拓撲圖，覆蓋網中各節點的標識都是一個160位的二進制串(即0到2¹⁶⁰-1之間的整數)，可以根據節點的IP地址或名稱等屬性通過公開的SHA-1算法獲得。Chord方法將覆蓋網中所有節點根據標識的大小，順時針構成一個環形的拓撲結構。

由于Chord中每個節點都維護了與其后繼節點的鄰居關系，在環上沿后繼節點總可以正確地到達任何目標節點，但這種方法效率很低。因此Chord方法中，每個節點都維護一個finger表(即路由表)，finger表至多有log₂N項，節點n的finger表第i項是值n+2^i-1在環上對應的后繼節點。Chord方法所構建的覆蓋網的節點度數為O(log₂N)，路由延遲是O(log₂N)，平均路由延遲為1/2log₂N。

為提高覆蓋網性能，一些研究提出在Chord方法構建的覆蓋網基礎上增加額外的覆蓋網連接和路由信息，以提高覆蓋網性能，典型工作包括Kelips、OneHop和Accordion等。例如，Kelips方法將覆蓋網中的節點分成k個組，每個節點通過哈希函數分配到某一個組中。各節點維護的路由表包括：(i)同組中所有節點的視圖；(ii)其他各組中常量個數節點的信息；(iii)同一組節點上的全部資源的索引信息。Kelips把路由消息轉發到相應的組中，更新消息通過gossip方式來傳播。Kelips的路由延遲為O(1)，但節點度數和維護開銷為O(N^1/2)。

(2)CAN方法

CAN(Content?Addressable?Network)方法采用多維花環作為覆蓋網的靜態拓撲圖。CAN方法的基本思想是構造一個虛擬的d維笛卡爾坐標空間，覆蓋網中各個節點分別負責虛擬d維坐標空間中的一塊區域。CAN中的節點根據它們所負責的區域在坐標空間中的位置來建立鄰居關系，負責相鄰區域的節點互為鄰居。由于坐標空間是d維的，故每個節點有2d個鄰居，CAN方法所構建的覆蓋網的拓撲結構是類d-torus拓撲。

當節點加入或退出時，相關節點負責的區間會進行拆分或合并。新節點加入時，首先通過哈希函數將新節點映射到虛擬空間中的一點，然后將該點所在區域沿某一維拆分成兩半，一半區域由新節點負責。拆分時對維數的選擇是按照round-robin方式輪流進行。CAN方法所構建的覆蓋網的節點度數為O(d)，路由延遲和消息開銷為O(dN^1/d)。

(3)Tapestry方法