[發明專利]一種基于層次化IP網絡坐標系統的路由選擇方法

無效

• 申請號: 201110258855.0
• 申請日: 2011-09-05
• 公開（公告）號: CN102291312A
• 公開（公告）日: 2011-12-21
• 發明（設計）人: 張敏;陽小龍;王文琳;周亮
• 申請（專利權）人: 電子科技大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 成都華典專利事務所(普通合伙) 51223
• 代理人: 楊保剛;徐豐

技術領域

本發明涉及計算機網絡性能優化技術領域，尤其涉及一種基于層次化的IP網絡坐標系統的路由選擇方法。

背景技術

IP網絡坐標系統能夠利用部分節點間實測時延，預測出全網任意節點間的時延，與傳統的直接測量方式相比(如Ping主動測量)，這種非直接測量的方法能快速獲取網絡時延，時間復雜度從O(N²)降到O(N)；并且可以采用幾何方法相互獨立地對網絡時延進行存儲和計算等操作，極大方便了獲取時延。目前網絡性能測量領域熱點問題是快速獲取時延，因為時延作為反映網絡性能狀況的重要指標，在網絡性能優化中發揮著重要作用，如在EIGRP(增強網關內部路由協議)中，正是利用時延等進行負載均衡，為數據包的轉發提供多條可選路徑，避免網絡擁塞、性能惡化。而如何利用IP網絡坐標系統所具有的時延預測能力，為數據包的轉發提供基于網絡位置感知的路由決策，能夠對優化網絡應用提供新思路。

但是目前，傳統的IP網絡坐標系統僅具有時延預測能力，缺乏對其它網絡性能信息的了解，如節點間路由跳數，對全網拓撲狀況認識存在局限性，導致應用受限，表現為僅僅利用IP網絡坐標系統所提供的時延信息，而節點并不了解相互鄰接關系等缺陷，導致在為數據包進行路由轉發過程中，節點并不知道數據包的下一跳出口地址，所以難以形成有效的路由轉發路徑。因此，傳統IP網絡坐標系統無法為數據包轉發生成有效路徑、難以實際優化網絡應用。

發明內容

針對上述現有技術，本發明要解決的技術問題是提供一種改善傳統IP網絡坐標系統僅能預測時延，難以提供更多網絡性能信息，導致對數據包路由轉發效率低下的基于層次化IP網絡坐標系統的路由選擇方法。

為了解決上述技術問題，本發明采用如下技術方案：一種基于層次化IP網絡坐標系統的路由選擇方法，其特征在于，包括以下步驟：

①構建具有上下層次關系的全局坐標系統和局部坐標系統；?

②坐標信息共享

節點通過集中式方法或分布式方法共享彼此的全局坐標和局部坐標信息，在共享坐標信息時，節點通過IP數據報文中的TTL字段來獲取路由跳數，路由選擇表根據節點全局坐標系統信息和節點局部坐標系統信息形成反映全網拓撲結構的無向加權圖，所述全網拓撲結構中包括節點間方向性關系、相對位置排序、路由跳數及節點間時延大??；

③IP數據包的路由轉發

在路由選擇表中，全局坐標從若干候選節點中，以選取相對位置最近的節點進行信息交互，并預測源節點與目的節點的方向性關系和相對位置排序，指引IP數據包的路由轉發方向，局部坐標也沿此方向，通過預測節點間時延，為IP數據包選取最佳下一跳地址，局部坐標還結合路由跳數所了解的節點間路徑及連通性，通過一系列局部坐標短距離時延預測累加達到長距離時延預測的目的，預測出至少一條時延代價最小的路徑，IP數據包沿該時延代價最小的路徑進行轉發。

進一步地，所述全局坐標系統由可擴展性高、冗余通信量小的算法構建，所述局部坐標系統由時延預測精度高的算法構建。

進一步地，所述坐標信息共享的集中式方法包括以下步驟：

預先選取性能優越、網絡帶寬容量大的節點作為服務節點；

通過服務節點維護IP網絡坐標系統信息，普通節點定期與服務節點進行信息交互，將其所知坐標信息告訴服務節點，服務節點負責整理，了解全網拓撲信息。

進一步地，所述坐標信息共享的分布式方法包括以下步驟：

節點定期將所知坐標信息告訴直接相鄰節點，該相鄰節點結合已有信息，完善對全網拓撲的認識。

進一步地，所述最佳下一跳地址的選取包括沿著以源節點與目的節點全局坐標為中心線的方向上，在弧度為R的扇形區域內，選取若干直接相連的鄰居節點，并從中依據局部坐標來預測與候選中繼節點時延值大小，以預測時延值最大、直接相鄰的中繼節點作為最佳下一跳地址。

與現有技術相比，本發明具有以下有益效果：通過構建具有上下層次關系全局坐標系統和局部坐標系統并共享坐標信息，進一步了解全局拓撲狀況，再相互配合來優化路由選擇，即全局坐標預測節點的方向性和相對位置排序，確定數據轉發的方向，而局部坐標結合路由跳數，精確預測節點間時延，找到最佳下一跳地址，搜索路由轉發路徑，從路由選擇表的無向加權圖中預測出至少一條時延代價最小路徑與遠端節點進行數據交互，沿此路徑進行IP數據包的轉發以達到優化網絡應用的目的。