[發明專利]用于提供覆蓋網絡的路由選擇體系結構的方法和系統

無效

• 申請號: 201310528517.3
• 申請日: 2007-11-23
• 公開（公告）號: CN103546372A
• 公開（公告）日: 2014-01-29
• 發明（設計）人: A.韋林;V.索扎
• 申請（專利權）人: 艾利森電話股份有限公司
• 主分類號: H04L12/701
• 分類號: H04L12/701;H04L12/773
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 葉曉勇;王忠忠

相關申請的交叉引用

本申請要求2006年11月27日提交的標題為“覆蓋網絡的路由選擇體系結構”的美國臨時申請序號60/867347的權益。上面提及的申請的內容通過引用結合到本文中。

技術領域

一般來說，本申請涉及網絡，而具體來說，涉及異構第3層網絡。更具體來說，本申請涉及異構第3層網絡的覆蓋路由選擇體系結構。

背景技術

過去幾年來，覆蓋網絡已在學術界以及在工業中得到關注。各種覆蓋應用通過因特網擴展，使它普遍存在并且被終端用戶大量使用。覆蓋網絡能夠改進現有基礎設施網絡的可靠性、性能以及可用性。覆蓋網絡提供解決若干組網問題的優良方式，特別是在不應當對現有網絡進行變更并且網絡為異構時。

目前，在文獻中很少找到解決在構建于平面標識符(flat?identifier)之上的覆蓋網絡中的分組路由選擇的問題的解決方案。基于平面標識符的路由選擇所存在的基本問題在于，平面標識符空間不能聚合。現有路由選擇的大多數基于分級結構和因特網協議(IP)地址到網絡地址的聚合，即所謂的子網化(sub-netting)。將子網掩碼應用于IP地址允許你來識別地址的網絡和節點部分。

文件共享覆蓋應用通常根據平面標識符來構建。這種類型的覆蓋應用依靠分布式哈希表(DHT)，以便找到給定資源。DHT是一種類型的分散分布式數據結構。參與DHT的各節點具有一個唯一的覆蓋標識符，通常為平面標識符。但是，標識符不用于數據分組路由選擇；它們用于路由查找給定資源(例如文件)的消息。這些覆蓋網絡中的會話通信建立通過將(資源的)覆蓋標識符解析為(資源持有者的)基礎(underlay)地址來實現，然后完全在基礎級進行數據分組路由選擇。因此，數據分組路由選擇依靠基礎網絡的路由選擇機制(例如IPv4)。這種解決方案是適當的，因為僅假定一個同構基礎網絡。注意，這要求用于參與覆蓋網絡的所有節點的一個唯一同構第3層技術。但是，當異構第3層網絡(或域)共存時，節點的網絡地址對另一個對等體可能無意義。

在過去數年已經提出實現DHT的概念的若干協議，例如CAN、Chord、Pastry和Tapestry協議。雖然這些協議具有某些差異，但是它們都利用相同的原理；密鑰通常通過對文件名進行哈希來產生。生成的密鑰用于在作為DHT的成員的節點所形成的覆蓋網絡中存儲或查找文件的定域性(1ocality)信息。

DHT內部路由選擇算法、即用于路由存儲和查找消息的機制是DHT協議的中心。成員節點形成覆蓋網絡，其中各節點具有作為相鄰節點的一組其它節點。當繼續進行給定密鑰的查找時，消息通過覆蓋網絡路由到負責那個密鑰的節點。系統的整體可縮放性和性能與路由選擇算法效率直接關聯。

為了分發處理和存儲負荷，各節點處理哈希空間的一部分，并因此負責某個密鑰范圍。在給定密鑰的情況下，所有節點可有效地將消息路由到負責那個密鑰的唯一節點。DHT提供例如分散化、可縮放性、負荷平衡、容錯性和自修復等性質。分散化通過節點分發密鑰，以及發生系統的組織而沒有任何中央協調。沒有節點比任何其它節點更重要。可縮放性允許系統處理甚至具有高變動(churn)的大量節點(頻繁地加入和離開結構的節點)。一般來說，查找過程的成本隨節點數量的對數增長。

使用一致哈希函數的負荷平衡使密鑰范圍遍布于具有高概率的節點，從而提供進行負荷平衡的固有方式。系統的容錯甚至在發生一些節點的故障時也提供可靠性。自修復實現系統的自動重組，從而反映新加入、離開或者出故障的節點。

DHT節點可加入或離開網絡。協議必須解決這個問題，以便使系統保持一致(consistent)。通過在節點加入或離開網絡時適當地更新路由選擇表來確保一致性。基本結構圍繞抽象平面密鑰空間構建，它按照密鑰空間分區方案在參與節點之間劃分。各實現使用一致哈希的某種變體將對象(例如文件名)映射到密鑰。一致哈希意味著高變動率僅影響相鄰節點擁有的密鑰集合，所有其它節點未受影響。存儲對象從一個節點到另一個節點的移動的最小化減少重組時間，從而允許系統中的節點的高到達和離開率。這與其中一個哈希桶(hash?bucket)的添加或刪除需要整個密鑰空間的再映射的常規哈希表形成對照。