[發明專利]一種網絡相似域劃分和路由信息復用方法

無效

• 申請號: 200610140105.2
• 申請日: 2006-09-30
• 公開（公告）號: CN101155080A
• 公開（公告）日: 2008-04-02
• 發明（設計）人: 李祖鵬;徐澤明;趙曉睿;黃景楠
• 申請（專利權）人: 聯想（北京）有限公司
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L12/24
• 代理公司: 中科專利商標代理有限責任公司
• 代理人: 朱進桂

技術領域

本發明涉及計算機網絡，更具體地，涉及一種網絡相似域劃分和路由信息復用方法。在本發明中，通過分析和利用因特網的物理結構特征，將因特網劃分為不同等級的相似域(Similarity?Realm)，具有相似物理路由路徑特性的節點被劃分成為不同的相似域集合的成員節點。

背景技術

目前，采用基于IP(因特網協議)前綴(因特網自治域AS(Autonomous?System))的因特網區域劃分。

但是，基于IP前綴(因特網自治域AS)的因特網區域劃分存在以下缺陷(參考圖2和圖3)：

1)具有相同IP前綴(特別是較大AS的IP前綴)的兩個節點并不一定具有相似的網絡物理路由路徑。如圖2所示，四個因特網節點的IP分別為10.100.2.3、10.100.2.10、10.100.2.133、10.100.2.200，它們屬于同一個大的ISP(因特網服務供應商)，也具有相同的IP前綴10.100.2.*，但是分析其物理網絡路由路徑，可以發現10.100.2.3、10.100.2.10和10.100.2.133這三個節點是基本一致的，而節點10.100.2.200卻使用了與其完全不同物理網絡路由路徑。產生這種情況的主要原因是由于這四個節點所屬的ISP所覆蓋的范圍太大造成。

2)具有不同IP前綴的兩個節點可能具有相似的網絡物理路由路徑。如圖3所示，雖然屬于不同ISP的兩個節點10.100.2.3和11.110.2.133分別屬于不同的自治域AS1和AS2，但由于兩個節點所屬的ISP之間的路由策略不同，它們通往目的節點21.10.2.31的物理網絡路徑是基本一致的。

3)基于IP前綴(因特網自治域AS)的因特網區域劃分方法無法量化不同節點間網絡物理路由路徑的相似程度。

發明內容

本發明的目的是生成一個基于相似域(Similarity?Realm)劃分的因特網全局視圖(Global?view)，在該因特網全局視圖的基礎上構建一層覆蓋層P2P(點到點)網絡，以及利用相似域的對稱特性，降低因特網節點在進行覆蓋層網絡(Overlay?Network)路由的計算復雜度。

為了實現上述目的，根據本發明的第一方面，提出了一種網絡相似域劃分方法，包括：從網絡中選擇預定個數的節點，作為公用測試集合；通過對選定的公用測試集合進行預定的網絡路徑測試，計算兩個節點間的網絡物理路由路徑相似度；以及如果計算得到的路徑相似程度大于預定閾值，則將所述兩個節點劃分在同一相似域中。

優選地，采用Minimum?K-median算法在網絡范圍中選取預定個數的節點，作為公用測試集合。

優選地，采用以下公式，計算兩個節點間的網絡物理路由路徑相似度RSD(Si，Sj，SET)：

RSD(Si,Sj,SET)=2*Σd∈SETCommon(Si,Sj,d)Σd∈SETTotal(Si,Sj,d)]]>

其中Si和Sj分別代表所述兩個節點；SET代表公用測試集合；d代表公用測試集合SET中的任一測試節點；Common(Si，Sj，d)代表從Si和Sj到公用測試節點d的路徑相似程度；Total(Si，Sj，d)代表從Si和Sj到公用測試節點d的總路徑長度。