鏈路狀態協議控制的網絡中路由選擇信息的分布式存儲的製作方法

2023-10-08 19:41:04 3

專利名稱：鏈路狀態協議控制的網絡中路由選擇信息的分布式存儲的製作方法
技術領域：
本發明涉及路由選擇信息管理，並且更具體來說，涉及用於鏈路 狀態協議控制的網絡中的路由選擇信息的分布式存儲的方法和設備。
背景技術：
數據通信網絡可包括耦合在一起並且配置成相互傳遞數據的各種 計算機、伺服器、節點、路由器、交換機、網橋、集線器、代理和其 它網絡裝置。這些裝置在本文將稱作"網絡元件"。通過利用一條或 多條通信鏈路在網絡元件之間傳送例如數據幀、分組、信元或段等的 協議數據單元，經由數據通信網絡來傳遞數據。當特定的協議數據單 元(PDU)通過網絡在其源與其目的地之間傳播時，它可以由多個網絡 元件和交叉的多條通信鏈路來處理。
當網絡元件接收到向未知網絡地址傳送數據的請求時，網絡元件 可嘗試獲得到達該未知網絡地址所需的路由選擇信息。存在確定PDU 的路由選擇信息的若干常見方式。例如，在乙太網網絡中，請求可由 網絡元件廣播到網絡上，以便查看是否任何其它網絡元件知道如何到 達該特定地址。當廣播網絡元件接收到應答時，它知道如何將乙太網幀轉發給預期的地址。這通常結合提供商邊緣節點發生，所述提供商 邊緣節點需要將特定客戶地址映射到提供商MAC地址，使得幀可被 轉發通過提供商網絡。在這種情況下，提供商邊緣節點可具有到達所 有其它提供商邊緣節點的路由選擇信息，但是可能沒有通過所有其它 提供商邊緣節點可得到的所有客戶路由的路由選擇信息。提供商邊緣 節點將需要確定其它提供商邊緣節點的哪一個能夠到達該客戶路由，
之後將PDU轉發到那個提供商邊緣節點上。
在所請求地址是IP位址的情況下，查找與該IP位址關聯的資源
的網絡位置的常見方式是將請求傳遞到域名服務(DNS)。 DNS系統是 一種分級系統，它依靠將更通用的地址緩存到整個網絡的分布式DNS 伺服器上，使得下級伺服器能夠處理許多IP解析請求而無需DNS根 伺服器或者分級結構中更高級的那些伺服器涉及到其中。具體來說， 具有未知IP位址的節點將請求傳遞給它的本地DNS伺服器，並且如 果那個伺服器不具有必要的信息，那麼它將請求進一步沿分級結構向 上傳遞，直至到達具有所需信息的副本的伺服器。
隨著提供商網絡上的節點數量增加，以及通過網絡可得到的客戶 路由數量增加，通過對所有節點廣播請求來解析路由請求變得越來越 低效。具體來說，廣播請求需要網絡上的各節點處理每個請求，這在 節點數量增加以及請求數量增加時變得低效。
類似地，隨著IP電話的出現，對IP位址的一次性請求的數量預 計會增加。例如，如果所請求的IP位址與網絡上所進行的電話呼叫的 目的地關聯，則預計對與這些IP位址關聯的路由選擇信息的請求中的 大多數將是一次性請求，因為不可能許多人始終呼叫電話號碼的同一 小集合。隨著對IP位址的一次性請求的比例增加，DNS服務的分級性 質的效率可預計會降低，因為多個請求更加不可能對同一個IP位址進 行。具體來說，緩存對IP位址的相對近的請求可預計不太有價值，其 中在特定時間周期內將會^t妾收到對同 一個IP位址的第二次請求更加不 可能。這可預計增加對DNS根伺服器的需求，並且可能使DNS服務成為網絡上的瓶頸。
因此，有利的是提供一種使路由選擇信息在網絡上可得到的新方式。

發明內容
實現分布式哈希表以便存儲網絡上的路由選擇信息。根據本發明
的一個實施例，結合鏈路狀態路由選擇協議的實現來交換的節點ID用 作分布式哈希表中的密鑰，並且路由存儲在網絡上的一個或多個節點 處。當路由被獲知時，對照密鑰集合來處理該路由以便確定哪些節點 應當存儲該路由。當需要路由時，對照密鑰集合來處理該路由以便確 定哪些節點應當具有路由信息。對照密鑰集合來處理路由的方式在兩 種情況下都是相同的，使得DHT可用於存儲和檢索網絡上的路由信 息。DHT可實現為存儲MAC地址、IP位址、MPLS標籤或者其它受 關注信息，以便使路由能夠由網絡上的網絡元件存儲和獲知。


通過所附權利要求書中的詳細資料來指出本發明的方面。通過以 下附圖中示例來說明本發明，附圖中相似的參考標號表示相似元件。 以下附圖公開本發明的各種實施例，僅用於說明而不是要限制本發明 的範圍。為了簡潔起見，可能不是每一個組件都在每張附圖中標記。 附圖包括
圖1是可用來實現其中節點實現DHT的本發明的 一個實施例並且 示出路由添加和路由查詢操作的示例網絡的原理框圖2是根據本發明的一個實施例、可用來實現節點並且參與DHT 的網絡元件的原理框圖3是示出根據本發明的一個實施例、可用於建立和使用DHT來 存儲路由信息的過程的流程圖4-6是根據本發明的一個實施例、可用來實現由諸如圖2的網絡元件之類的網絡元件所存儲的表以便使網絡元件能夠參與DHT的 數據結構；
圖7-8示出根據本發明的一個實施例、與將節點添加到DHT有關 DHT進行變更的方式；以及
圖9-10示出根據本發明的一個實施例、與從DHT刪除節點有關 DHT進行變更的方式。
具體實施例方式
圖1示出示例通信網絡10,其中網絡元件12經由鏈路14而互連。 網絡元件可定義自主網絡，並且實現諸如中間系統到中間系統(IS-IS) 或開放最短路徑優先(OSPF)之類的鏈路狀態路由選擇協議，以便允許 計算網絡元件12之間的路由。網絡10上的網絡元件將交換問候消息 以便獲知節點之間的相鄰性，並且交換鏈路狀態通告以便使網絡上的 所有節點能夠構建表示網絡的拓樸的鏈路狀態資料庫。
雖然結合描述實施例將提供特別強調，在所述實施例中網絡是實 現鏈路狀態協議以便控制乙太網網絡上路由選擇的乙太網網絡，但是 本發明並不局限於這種方式，因為網絡10也可實現為IP網絡、MPLS 網絡或者另一種網絡。
通過採用無迴路最短路徑轉發(loop-free shortest path forwarding) 提供網絡容量的更有效使用，使用鏈路狀態協議來控制乙太網網絡使 乙太網網絡能夠從LAN空間縮放(scale)到WAN或提供商網絡空間。 不是通過使用與透明橋接結合的生成樹協議(STP)算法來利用各節點 處獲知的網絡視圖，而是在鏈路狀態協議控制的乙太網網絡中，形成 網狀網絡的網橋交換鏈路狀態通告，以便使各節點能夠具有網絡拓樸 的同步視圖。這經由鏈路狀態路由選擇系統的充分理解的機制來實現。 網絡中的網橋具有網絡拓樸的同步視圖，了解必要的單播和多播連通 性，能計算網絡中任一對網橋之間的最短路徑連通性，並且能根據網 絡的所計算視圖單獨裝載(populate)其轉發信息庫(FIB)。在2006年10月2日提交的標題為"提供商鏈路狀態橋接" ("Provider Link State Bridging")的申請No.ll/537，775中公開這種性質 的鏈路狀態協議控制的乙太網網絡的一個示例，由此通過引用將其內 容結合到本文中。正如那個申請中更詳細地描述，鏈路狀態協議控制 的乙太網網絡中的節點交換問候消息以便獲知網絡上的其它節點的相 鄰性，並且傳送鏈路狀態通告以便使網絡上的各節點能夠構建鏈路狀 態資料庫。鏈路狀態資料庫可用來計算通過網絡的最短路徑。然後， 各節點裝載轉發信息庫(FIB),它將由節點用來進行轉發判定，使得以 太網幀將通過所計算的最短路徑轉發到目的地。由於到特定目的地的
最短路徑將取決於業務的源，所以網絡業務可比一個或多個生成樹祐:
用來攜帶網絡上的業務的情況分布於更大數量的鏈路。
在給定管理域內，形成乙太網網絡的網絡元件可基於作為給定管
理域的部分的網絡上網絡元件的目標MAC地址來轉發分組。當業務 到達網絡的邊緣時，邊緣網絡元件將把業務映射到服務，並且在通過 與服務關聯的網絡的路徑上轉發業務。
這可能發生的一種常見情況是客戶業務將通過提供商的乙太網網 絡來路由。使用客戶MAC尋址空間來尋址的客戶幀將穿過(traverse) 客戶網絡，直至它到達客戶網絡的邊緣。當幀到達提供商網絡時，提 供商網絡將查看目標地址(C-MAC地址)，並且確定提供商網絡上的哪 一個節點能夠到達那個客戶MAC地址。正如下面更詳細地進行描述， 分布式哈希表可用於存儲提供商-客戶關聯，使得提供商網絡元件能 夠通過向DHT發出查詢來獲知這種關聯。
作為另一個示例，在IP網絡中，與IP位址關聯的資源的位置可 能需要由IP網絡上的路由器來查找。根據本發明的一個實施例，IP地 址和網絡位置可存儲在DHT中，其中網絡上的節點實現DHT的部分。 作為又一個示例，在MPLS網絡中，標籤邊緣路由器可能需要獲知哪 一個標籤將用於在通過網絡的標籤交換路徑上轉發業務。標籤可存儲 在網絡元件所實現的DHT中，以便允許才全索業務流的標籤。正如下面更詳細地進行描述，可形成分布式哈希表，使得網絡上 的各節點具有形成分布式哈希表中的密鑰的節點ID。各節點則配置成 存儲路由選擇數據總量的子集，其中哈希值充分接近其密鑰。當節點 獲知路由時，它存儲該路由的本地副本，並且將路由的副本轉發給網
絡中配置成存儲DHT的那個部分的那些節點(即，其ID '接近，路由 的密鑰/ID的節點)。節點ID和路由ID可以以一致的方式進行哈希(hash) 或者其它處理，使得節點ID和路由ID佔用同一空間。
實現鏈路狀態路由選擇協議還使所有節點能夠知道網絡上所有其 它節點的標識。具體來說，作為鏈路狀態路由選擇協議的部分，節點 均將傳送包含其節點ID以及與它們所連接的鏈路相關的信息的鏈路 狀態通告。這種信息將用來形成鏈路狀態資料庫。正如本文更詳細地 描述，根據本發明的一個實施例，結合鏈路狀態路由選擇協議所交換 的節點ID可與分布式哈希表中存儲的路由密鑰進行比較，使得各節點 從其鏈路狀態資料庫了解到哪些節點負責將哪些路由密鑰存儲在 DHT中。然後，密鑰可用於以確定性方式存儲以及檢索來自DHT的 路由信息。通過使用鏈路狀態資料庫中的節點信息來確定應當由那個 節點存儲的DHT的密鑰，能夠簡化密鑰的計算，以便使DHT更易於 實現。另外，對LSDB的變更可傳播入DHT,使得DHT成員可在網 絡拓樸改變時自動調整。
分布式哈希表是對等技術，在E.RESCORLA的標題為"分布式哈 希表入門，，("Introduction to Distributed Hash Tables")的論文以及 P.MAYMOUNKOV等人的標題為"Kademlia:基於XOR量度的對等 信息系統"(Kademlia:A Peer-to-Peer Information System Based on the XOR Metric)的論文中對它進行了更詳細地描述，由此通過引用將其內 容結合。根據本發明的一個實施例，通過使數據存儲在分布式哈希表 來將這類關聯的數據均勻地分布於網絡，諸如用戶到提供商地址關聯 和IP路由選擇信息之類的路由選擇信息可存儲在極大的網絡中，其中 網絡元件各自承擔存儲分布式哈希表的一部分的職責。從LSDB所確定的節點ID可與DHT中的路由/密鑰進行比較，以便使節點能夠確定 應當存儲已知路由選擇信息的位置以及可找到未知路由選擇信息的位置。
當節點接收到路由信息時，它將存儲該路由信息，並且使那個信 息在請求時可用。通過使各節點存儲路由選擇信息的一部分，不需要 節點存儲整個路由選擇表，使得對任一個節點的存儲要求可降低。通 過指定冗餘因子，信息的多個副本可存儲在DHT中，使得任一個節點 的故障不會影響其它節點查找特定路由信息的能力。
圖2示出可用於實現本發明的一個實施例的網絡元件的一個示 例。如圖2所示，網絡元件包括數據平面50和控制平面60。數據平 面50 —般包括配置成與網絡上的鏈if^4妾口的輸入/輸出卡、配置成對 於通過I/O卡52所接收的數據執行功能的數據卡54以及配置成在數 據卡/I/O卡之間交換數據的交換結構(switchfabric)56。控制平面包含處 理器62,所述處理器62包含配置成實現DHT進程64、消息傳遞進程 66和鏈路狀態路由選擇進程67的控制邏輯。消息傳遞進程可用於例 如格式化DHT添加消息和DHT查詢消息、將包含路由選擇信息的 DHT條目添加入DHT以及從DHT提取DHT條目。其它進程也可在 控制邏輯中實現。與DHT和消息傳遞進程關聯的數據和指令可作為 DHT軟體68存儲在存儲器70中。與鏈路狀態路由選擇進程67關聯 的數據和指令可作為協議棧軟體69存儲在存儲器70中。本地數據表 72、遠程數據表74、成員表76和鏈路狀態資料庫78的示例在本文更 詳細地描述，它們可保存在存儲器70中、保存在網絡元件16內的其 它存儲器中或者接口到網絡元件並且存儲在外部存儲器中。
圖3示出可用於實現本發明的一個實施例的進程。圖3提供該進 程的概覽；下面結合圖4-9來闡明附加細節，圖4-9示出根據本發明的 一個實施例、可用於實現分布式哈希表(DHT)的部分的示例表的數據 結構。
如圖3所示，節點交換鏈路狀態通告(IOO),以便獲知網絡上參與DHT的所有節點的MAC地址。各節點將使用節點ID來構建BHT成 員表(參見圖4)，它將使節點能夠確定節點的哪一個應當用於存儲特定 密鑰/路由，以及使節點能夠確定應當發送特定密鑰/路由的查詢的位 置。例如，網絡上的各節點將具有MAC地址。MAC地址可經過哈希 以便創建節點ID，然後可對節點ID排序(order)以便創建成員表(102)。 備選地，節點MAC地址本身可以是節點ID。雖然將描述其中節點 MAC地址用於創建節點ID的本發明的一個實施例，但是本發明並不 局限於這種方式，因為其它信息可用作DHT的基礎。例如，節點的IP 地址可用來形成節點的DHT ID的基礎。
網絡上的節點被連接到客戶LAN,並且獲知的=客戶-提供商關 聯(C-MAC至P-MAC對)，它們也將被稱作路由。路由與客戶MAC地 址(至該對的密鑰)關聯，所述客戶MAC地址可用於確定路由應當存儲 在分布式哈希表中的位置。
因此，如圖3所示，當節點獲知路由時，節點對與該路由關聯的 C-MAC地址執行哈希，以便獲得路由/密鑰ID(104)。該哈希函數與用 於創建節點ID的哈希函數相同，使得路由ID和節點ID具有同 一格式， 並且因此可易於使用XOR過程或其它數學過程進行比較。然後，節點 將對路由ID與(102)中找到的節點ID進行比較，以便確定節點的哪一 個充分"接近"該路由ID。結合圖1更詳細地描述如何執行比較的一 個示例。如圖1所示，假定節點1001獲知它要存儲在分布式哈希表中 的<密鑰，值〉對(本例中為OMAC/P-MAO),使得所有節點能夠有權 訪問對。例如，假定節點1001獲知路由〈1100,V1〉。節點 1001將對密鑰(1100)與所有其它節點ID執行XOR運算，以便確定哪 些節點具有最接近該密鑰ID的節點ID。然後，該節點根據所使用的 比較算法(本例中為XOR運算)將把〈密鑰，值>對發送給最接近的那些 節點，使得它們可存儲該對。在所示示例中，節點1101 和1110將與1100具有最小XOR距離，因此僅向那些節點發送 〈1100,Vl〉對供存儲。由於向兩個節點發送該路由供存儲，所以本例中的複製因子(r印lication factor)為2(K=2)。接收該路由的節點將在其遠程 數據表中存儲對。
如圖3所示， 一旦值被存儲，當節點需要獲知路由時，它將對設 法找到的C-MAC地址執行哈希，以便獲得路由/密鑰ID(108)。然後， 節點將通過對路由ID與成員表中節點的節點ID進行比較，來確定 DHT中的節點的哪一個應當用於查詢路由/密鑰ID的路由選擇信息。 例如，這可使用上述XOR距離過程來完成。然後，節點將把對對的請求傳送給節點ID最接近高於(immediately higher)路由ID的 K個節點的至少一個(110)或者傳送給具有糹皮認為最接近路由/密鑰ID 的節點ID的k個節點。接收請求的節點將從其遠程數據表(參見圖6) 提取路由信息，並且以路由條目的路由信息(在這種情況下為所請求 C-MAC的P-MAC)響應(112)。
在圖1所示的示例中，例如假定節點0011發現它需要其值的密鑰。 具體來說，假定節點0011發現密鑰1100，但是沒有與那個密鑰關聯 的值。密鑰可以是與從客戶LAN所接收的幀關聯的哈希C-MAC地址， 或者可表示諸如IP位址之類的另一實際量。節點將在密鑰與拓樸中的 所有其它節點ID之間執行XOR運算，以便查找兩個最接近已知密鑰 的節點ID。注意，節點使用如將對放入DHT時所執行的 相同值來執行同一XOR距離過程，因此可預計節點0011也將確定節 點1101和1110可能具有那個密鑰的值的副本。節點0011可向節點 1101和1110傳送請求密鑰1100的值的請求，並且預計節點的一個或 兩個將能夠以值VI響應。
雖然本文已經描述了實施例，在所述實施例中通過在節點ID與路 由ID之間執行XOR運算來確定節點ID與路由ID之間的距離，但是， 本發明並不局限於這種方式，因為對值進行比較以確定節點ID與路由 ID之間的相對距離的其它數學方式也可使用。
通過使值VI在DHT中存儲多次(特定數目取決於複製因子K)， 請求節點可接收多個響應。但是，將值存儲在DHT中的一個以上位置提供針對網絡中的任一個節點的故障的彈性(resiliency)，因為存儲在該 節點的信息可從形成DHT的其它剩餘節點重新創建和重新分發。下面 結合圖7-10更詳細地描述對DHT添加和刪除節點。
由於網絡元件正運行諸如OSPF或ISIS之類的鏈路狀態協議，所 以各節點具有節點的列表和節點地址。這種信息可用於確定:l是供商網
絡中的所有提供商節點的節點ID。當DHT用於存儲客戶端/提供商關 聯並且客戶端到提供商節點關聯被獲知時，完成DHT "添加"以便將 <客戶端，提供商〉信息插入DHT。因此，在這種情況下，該值是其中 可找到客戶端路由的提供商節點，並且客戶端MAC地址是與提供商 節點的節點ID進行XOR運算以便確定哪一個提供商節點應當存儲對的密鑰。
當客戶端首次想要與另 一個客戶端通話時，它通過對照DHT進行 查詢來向DHT請求與那個客戶端的提供商關聯。具體來說，客戶端值 與節點ID進行XOR運算，以便確定DHT中的哪些節點應當存儲那 個地址關聯，並且然後查詢將被發送給DHT中被 確定存儲那個關聯的提供商節點。DHT中的節點將以對響應，使得客戶端可獲知哪一個提供商節點能夠到達預計客戶端 地址。這樣，DHT添加/查詢操作使用鏈路狀態拓樸以確定性方式識別 存儲/查詢<客戶端，提供商〉關聯的少量(K)提供商節點。通過使用節 點ID作為對DHT的密鑰，密鑰計算過程可極大地簡化。另外，由於 所有節點具有鏈路狀態資料庫的更新副本，所以所有節點具有在DHT 中正i^f吏用的節點ID的集合的當前副本，因此當DHT成員/密鑰所有 權隨網絡拓樸的變更而變更時，無需附加信令機制來更新節點。
密鑰可以是乙太網MAC地址、諸如EPV4或IPv6地址之類的IP
的其它公共或專有地址。類似地，要隨特定密鑰一起存儲在DHT中的 值也可以是乙太網MAC地址、諸如IPV4或IPv6地址之類的IP位址、 NSAP地址或者包括MPLS標籤或其它標籤的其它公共或專有地址。一般來說，在所有正使用分級路由選擇系統並且必須存儲映射以便從 上級地址映射到下級地址的情況下，與任一個或兩個地址的格式無關，
DHT可用於以有效方式來存儲這種關係。類似地，節點和路由ID可 取自開放式系統互連基本參考模型(OSI)層的同 一層，或者可取自不同 的層。例如，節點和if各由ID都可以是第2層值(MAC地址)、都可以 是第3層值(IP位址)或者可以是它們兩者，即，節點ID可以是IP地 址而路由ID可以是MAC地址，或者相反地，節點ID可以是MAC地 址而if各由ID可以是IP位址。
圖4-6示出可由網絡上的節點的一個或多個保存以便實現本文所 述DHT的示例DHT表。在這些圖中，圖4示出包含節點ID的列表的 DHT成員表的示例。節點ID可以是如從鏈路狀態資料庫所獲知的網 絡上節點的地址值，或者備選地可以由這些地址值的^^合希來形成。在 所示示例中，節點ID表包含從路由選擇系統獲得的9個值。具體來說， 諸如圖1所示的網絡之類的網絡上的節點假定為實現鏈路狀態路由選 擇協議，其中各節點交換鏈路狀態通告以便使網絡上的各節點能夠構 建鏈路狀態資料庫。鏈路狀態通告和/或鏈路狀態資料庫將包含節點的 地址。參與DHT的那些節點的節點地址將用於裝載圖4的DHT成員 表。雖然成員表如圖4所示，但是這種信息可作為鏈路狀態資料庫的 部分而被包含，因而不需要存儲在獨立的表中。
圖5示出可由網絡上的節點保存而與DHT無關的本地數據表的示 例。具體來說，網絡上的節點可從與其附連的客戶設備獲知路由。這 種信息可存儲在本地表中，使得節點能夠保存通過它是可達的那些路 由的副本。本地表還可用於緩存從DHT所獲知的路由，使得可加速與 特定遠程路由交換數據的重複嘗試。
當獲知路由時，將它們添加到本地數據表。通過將路由值與節點 ID進行比較(即進行XOR運算)，路由也將被傳送給DHT以便查找K 個最接近的匹配節點ID。在圖4和圖5所示的示例中，複製因子K(DHT 中信息的複製副本的數量)設置為三，使得獲知路由的節點將把已獲知路由傳送給參與DHT、最接近路由的密鑰值的三個節點。例如，可將 路由發送給節點ID高於路由的密鑰值的三個節點。例如，假定DHT 成員表包含IP位址，並且本地節點獲知了到IP位址的路由。已獲知 路由的IP位址可與DHT成員表中的節點的IP位址進行XOR運算， 以便查找IP位址與已獲知IP位址最相似('接近，)的那三個節點。然 後可將路由發送給那三個節點，以便使那個IP位址的路由信息存儲在 分布式哈希表的正確節點處。當然，在比較發生之前IP位址可經過哈 希或者其它處理並且也可使用其它類型的地址，因為IP位址僅用作可 使用的一種類型的地址的示例。這個相同過程也可用於查找表中的IP 地址。
圖6示出可由DHT中的節點存儲的遠程數據表的示例。如圖6所 示，當節點接收到來自網絡上的其它節點之一的通告路由時，它將把 該路由存儲在其遠程數據表中。該表可按照與路由的地址關聯的密鑰 來組織，並且可包含與路由關聯的節點的值(即節點ID)。其它數據也 可與路由關聯。當網絡上的另一個節點需要和與路由的地址關聯的路 由進行通信時，該節點可將路由地址(路由密鑰)與節點ID(節點密鑰) 進行比較，以便確定DHT中的哪些節點應該保存該路由。然後，請求 節點可將請求轉發給DHT中的該節點，以便使該節點從其遠程數據表 檢索路由信息。
如圖6的示例遠程數據表所示，遠程數據表包含密鑰的列表以及 網絡上可用於到達(reach)那些密鑰的節點ID的列表。例如，密鑰221 可經由節點ID 598到達，密鑰245可經由節點ID 384到達，等等。存 儲在遠程數據表74中的密鑰集合是使用上述XOR距離計算過程確定 為充分接近保存遠程數據表的節點ID的數據的那個集合。當網絡上的 另一個節點發現諸如密鑰245之類的密鑰時，它可向保存遠程數據表 74的節點發送請求，以便獲得路由在網絡上所在的節點ID。具體來說， 在接收到該請求時，保存遠程數據表74的節點將獲得值<密鑰245,節 點ID384〉以及與該條目關聯的無論什麼數據，並且響應請求節點，使得發現密鑰245的節點可獲知它能夠經由節點ID 384而到達與密鑰 245關聯的路由。
在這方面要注意，進入表中的密鑰基於IP位址、乙太網MAC地 址等，使得DHT中的各節點在其遠程數據表中存儲與IP位址、以太 網MAC地址等的特定集合關聯的路由。通過將節點IP位址或乙太網 MAC地址與DHT中的那個節點以確定性方式所存儲的地址集合關 聯，其它節點在面臨未知地址時可執行同一計算，以便確定要查詢哪 一個節點以獲得那個地址的路由。
圖7-8示出根據本發明的一個實施例、與將節點添加到DHT有關 DHT進行變更的方式。如圖7所示，DHT成員表將存儲從網絡上的其 它節點在獲知路由時傳送給它的數據。當節點獲知路由時，它將4皮存 儲在本地數據表72中，並且隨後傳送給由節點通過查看DHT成員表 70所識別的其它節點。根據複製因子，路由信息將^fc^出一次或多次 到識別為需要將路由信息存儲在DHT中的節點。在所示示例中，複製 因子為三(K-3)，因此節點將發送路由信息給三個節點以便存儲在DHT 中。因此，在所示示例中，密鑰346(及其值/路由)將被發送到節點351、 378和384,而密鑰378(及其值/路由)將祐義送到節點384、 419和598。
這時假定以節點ID=380將新節點添加到DHT。這種情況的示例 如圖8所示。在將新節點添加到網絡時，該節點將開始發出鏈路狀態 通告，以便使節點將該節點添加到其鏈路狀態資料庫。在鏈路狀態數 據庫中包含該節點將自動使節點ID被添加到DHT成員表70。但是， 在DHT成員表中包含新節點將影響網絡上的節點執行路由查詢的方 式，因為在確定尋找具有特定密鑰的路由的位置時將諮詢更新DHT成 員表。因此，應當存儲在那個DHT中的路由應當傳送給新節點，使得 它在其遠程數據表中具有路由信息的副本。這樣做的 一種方式是使網 絡元件確定哪些路由受到成員表的變更影響，並且使節點將路由傳送 給新節點，好像它們原本已傳送到那裡 一樣(if they should originally have been transmitted there)。這可通過使各節點基於當前DHT成員表來確定其本地數據表中哪些密鑰應當存儲在節點上，並且使節點將那 些路由傳送給新節點來完成。因此，例如，圖8中的節點可確定新節
點380應當具有密鑰346的路由信息的副本，並且將那個路由傳送給 新節點。該節點也將確定密鑰377和378也應當糹皮傳送到節點380, 並且還傳送那些路由的DHT添加消息。
由於複製因子仍然為三，並且節點384已經提供有路由信息的副 本，因此，節點384將具有不會^皮任何其它節點請求的額外副本，只 要DHT成員表不再變更。因此，可指示節點384刪除與密鑰346關聯 的路由，或者節點384可允許與密鑰346關聯的路由超時，並且在特 定時間周期它未被請求之後被刪除。
圖9-10示出根據本發明的一個實施例、與從DHT刪除節點有關 DHT進行變更的方式。具體來說，圖9示出在結合圖7和圖8所述的 添加操作期間添加節點380之後的DHT成員表。圖9中，假定如以上 結合圖8所述，複製過程已經使無關的(extraneous)路由信息被刪除或 超時，使得各密鑰存儲在DHT中的三個不同節點處。
如圖IO所示，假定從DHT成員表移除節點380。在移除節點380 時，特定路由僅存儲在DHT中的兩個位置處。為了使那些路由存儲在 三個位置，各本地節點可回顧(review)其本地數據表中的信息，以便確 定它已經使哪些密鑰存儲在那個節點處的DHT中。對於受影響的那些 密鑰，節點可基於新的DHT成員來確定哪些節點應當存儲密鑰，並且 將密鑰傳送給那些節點。備選地，由於遠程節點中的一些將已經使密 鑰存儲在DHT遠程數據表中，所以節點可以僅向這個過程中確定的最 後一個節點傳送路由選擇信息。例如，如果複製因子為&=3，則本地 節點可確定DHT中的第三節點應當存儲數據的副本，並且僅向第三節 點傳送與那個密鑰關聯的路由信息。
雖然已經描述了 一個實施例，其中節點在DHT成員變更時使用存 儲在其本地表中的信息將路由複製到DHT節點，但是本發明並不局限 於這種方式，因為實現這個過程的其它方式也可^t實現。例如，如果節點被添加到DHT,則在新節點的複製因子之內、具有節點ID的DHT 節點可處理其DHT遠程數據表中的密鑰，以便確定哪些密鑰應當存儲 在新節點中，並且將那些密鑰傳送給新節點。作為這個過程的部分， 節點也可確定哪些密鑰不再需要存儲在其遠程數據表中，並且刪除那 些路由。
類似地，在從DHT移除節點時，在已經移除的節點的複製因子之 內的那些節點可處理其遠程數據表中的路由，以便確定哪些路由存儲 在不再是DHT的部分的節點中。存儲在舊節點中的那些路由則可根據 需要傳送給DHT的其它節點，以便使各路由的複製因子保持相同。因 此，對DHT成員的修改可由DHT節點來實現，而無需已獲知路由信 息的節點每當DHT成員變更時將路由信息重新通告到DHT中。
如上所述的功能可實現為一組程序指令，它們存儲在計算機可讀 存儲器中，並且在計算機平臺上的一個或多個處理器上運行。然而， 本領域的技術人員將明白，本文所述的所有邏輯可使用分立組件、諸 如專用集成電路(ASIC)之類的集成電路、與諸如現場可編程門陣列 (FPGA)或微處理器之類的可編程邏輯裝置結合使用的可編程邏輯、狀 態機或者包括它們的任何組合的其它任何裝置來體現。可編程邏輯能 暫時或永久固定在諸如只讀存儲器晶片、計算機存儲器、磁碟或其它 存儲介質之類的實體介質中。可編程邏輯也能固定在以載波體現的計 算機數據信號中，從而允許可編程邏輯通過諸如計算機總線或通信網 絡之類的接口來傳送。所有這類實施例意在落入本發明的範圍之內。
應當理解，附圖中所示以及說明書中所述的實施例的各種變更和 修改可在本發明的精神和範圍之內進行。因此，在以上說明書中包含 以及附圖中所示的所有事項意在被解釋為說明性而不是限制性的。本 發明僅由以下權利要求書及其等效物所定義的內容來限制。
權利要求
1.一種將路由選擇信息存儲在鏈路狀態協議控制的網絡中的方法，所述方法包括以下步驟在所述網絡上實現鏈路狀態路由選擇協議，以便使所述網絡上的多個節點中的每一個實現鏈路狀態資料庫；以及使用從所述鏈路狀態資料庫中的信息所得出的節點ID作為分布式哈希表中的密鑰，以便基於與路由關聯的路由ID和所述節點ID的比較而確定存儲與所述路由關聯的信息的所述網絡上的所述多個節點的子集。
2. 如權利要求1所述的方法，其中，使用節點ID的所述步驟包 括在所述路由ID與所述節點ID中的每一個之間執行XOR過程，以 便確定存儲所述路由信息的所述多個節點的所述子集。
3. 如權利要求l所述的方法，其中，所述子集基於所述分布式哈 希表的複製因子。
4. 如權利要求l所述的方法，還包括以下步驟將消息中的所述 路由信息傳送給所述子集中的所述節點中的每一個，以便使那些節點 將所述路由選擇信息存儲在它們的所述分布式哈希表的部分中，供所 述網絡上的其它節點的後續檢索。
5. 如權利要求l所述的方法，其中，所述節點ID是MAC地址或 者從所述網絡上的所迷節點的MAC地址得出，並且其中所述路由ID 是目標MAC地址或者從所述路由的目標MAC地址得出。
6. 如權利要求l所述的方法，其中，所述節點ID是IP位址或者 從所述網絡上的所述節點的IP位址得出，並且其中所述路由ID是目
7. 如權利要求l所述的方法，其中，所述節點ID是MAC地址或 者從所述網絡上的所述節點的MAC地址得出，並且其中所述路由ID
8. 如權利要求l所述的方法，其中，所述節點ID是IP位址或者 從所述網絡上的所述節點的IP位址得出，並且其中所述路由ID是目 標MAC地址或者從所述路由的目標MAC地址得出。
9. 如權利要求1所述的方法，其中，所述節點ID是笫一地址或 者從第一 OSI尋址層中的第 一地址得出，並且其中所述路由ID是笫二 地址或者從第二 OSI尋址層中的第二地址得出。
10. —種方法，包括以下步驟由鏈路狀態路由選擇協議控制的通信網絡中的節點來獲知路由信臺將與所述路由信息關聯的路由ID和與參與分布式哈希表的節點 關聯的節點ID進行比較，所述節點ID從鏈路狀態資料庫得出，所述 鏈路狀態資料庫包含從所述鏈路狀態路由選擇協議所指定的協議交換 所獲得的信息；以及將所述路由信息傳送給具有充分接近於所述路由ID的節點ID的 節點的子集。
11. 如權利要求10所述的方法，其中，所述路由ID是MAC地址； 並且其中所述節點ID是MAC地址。
12. 如權利要求11所述的方法，其中，所述路由ID是客戶端MAC 地址，並且其中所述節點ID是提供商MAC地址。
13. 如權利要求10所述的方法，其中，所述路由ID是IP位址， 並且其中所述節點ID是IP位址。
14. 如權利要求10所迷的方法，其中，將所述路由K)與所述節 點ID進行比較的所述步驟包括執行所述路由ID與所述節點ID的數學 比較。
15. 如權利要求14所述的方法，其中，所述數學比較是XOR運算。
16. 如權利要求IO所述的方法，還包括以下步驟 發現第二路由ID;將所述第二路由ID和與參與所述分布式哈希表的節點關聯的所述節點ID進行比較；以及將與所述第二路由ID關聯的第二路由信息的查詢發送給具有充 分接近於所述第二路由ID的節點ID的節點的第二集合。
17. —種網絡，包括多個互連網絡元件，其中的至少一些配置成實現鏈路狀態路由選 擇協議和包含路由選擇信息的分布式哈希表(DHT)，其中，從與所述 鏈路狀態路由選擇協議關聯的交換所得出的節點ID用於識別存儲在 所述DHT中的信息的集合。
18. 如權利要求17所述的網絡，其中，配置成實現所述DHT的 所述網絡元件配置成各自存儲包含參與所述DHT的節點的節點ID列 表的DHT成員表、包含由所述網絡元件所獲知的路由的本地數據表以 及包含從來自參與所述DHT的其它網絡元件的消息所獲知的路由的 遠程數據表。
19. 如權利要求18所述的網絡，其中，配置成實現所述DHT的 所述網絡元件配置成使用經由所述鏈路狀態路由選擇協議所傳遞的網 絡拓樸變更來更新它們的DHT成員表中它們的節點ID列表。
20. 如權利要求19所述的網絡，其中，配置成實現所述DHT的 所述網絡元件配置成在發生網絡拓樸變更時重新通告來自它們的本地 數據表的選擇信息。
21. —種網絡元件，包括 處理器，配置成實現鏈路狀態協議進程，配置成建立鏈路狀態資料庫，所述鏈路 狀態資料庫包含與網絡關聯的網絡拓樸信息，在所述網絡上所述網絡 元件配置成接收通信，分布式哈希表(DHT)進程，配置成從所述鏈路狀態資料庫提 取信息，以便確定與參與所述DHT的網絡元件關聯的節點ID,所述 DHT配置成存儲所述網絡上的路由信息；和消息傳遞進程，配置成接收和傳送包含將存儲在所述DHT中的路由信息的消息。
22.如權利要求21所述的網絡元件，其中，所述網絡元件還配置成實現存儲器，所述存儲器包含DHT成員表、本地數據表和遠程數據表，所述DHT成員表包含參與所述DHT的所述網絡元件的所述節點ID，所述本地數據表包含所述網絡元件所獲知的路由信息，所述遠程數據表包含經由所述消息傳遞進程從其它網絡元件所獲知的路由信 自
全文摘要
實現分布式哈希表以便存儲網絡上的路由選擇信息。結合鏈路狀態路由選擇協議的實現來交換的節點ID用作分布式哈希表中的密鑰，並且路由存儲在網絡上的一個或多個節點處。當路由被獲知時，對照密鑰集合來處理該路由以便確定哪些節點應當存儲該路由。當需要路由時，對照密鑰集合來處理該路由以便確定哪些節點應當具有路由信息。對照密鑰集合來處理路由的方式在兩種情況下都是相同的，使得DHT可用於存儲和檢索網絡上的路由信息。DHT可實現為存儲MAC地址、IP位址、MPLS標籤或者其它受關注信息，以便使路由能夠由網絡上的網絡元件來存儲和獲知。
文檔編號H04L12/24GK101529809SQ200780040352
公開日2009年9月9日 申請日期2007年11月1日 優先權日2006年11月2日
發明者G·殷, P·阿什伍德-史密斯, W·麥克科爾米克 申請人:北方電訊網絡有限公司