一種獲取多下一跳路由的方法、裝置和路由器的製作方法

2023-06-07 20:38:31 2

專利名稱：一種獲取多下一跳路由的方法、裝置和路由器的製作方法
技術領域：
本發明屬於網絡管理技術領域，尤其涉及一種獲取多下一跳路由的方法、裝置和
路由器。
背景技術：
現有路由協議，可分為最短路徑優先類單一下一跳路由協議和多徑路由協議，前者基於快速重路由技術實現快速自愈，具體策略是局部保護、重路由計算，其故障恢復時間較長，無法保證網絡故障時實時應用不中斷；多徑路由協議採用全局保護、多路徑備份的策略，由於其所建立的從源到目的地的路徑數量有限，無法應對網絡的並發多故障。針對現有路由協議在提高網絡快速自愈能力方面存在的問題，受自然界中水流順勢而流現象的啟發，吸取現有技術體系"逐跳轉發"和"基於路由備份快速切換"等思想，在不改變現有IP網絡基本技術架構的基礎上，設計提出一種新型的節點勢能導向多下一跳路由生成算法(Node Potential oriented Multi Next Hop Algorithm, NP-M薩)，在路由節點層面提供局部下一跳備份即路由備份。使得以該路由協議為基礎的網絡具有故障恢復時間短、自適應能力強等特徵，在以單一故障為主的一般網絡環境和並發多故障的網絡極端環境下均具有較好的網絡性能。

發明內容
有鑑於此，本發明的目的在於提供一種獲取多下一跳路由的方法、裝置和路由器，該方法、裝置和路由器自適應能力強，故障恢復時間短。 為實現上述目的，本發明實施例提供一種獲取多下一跳路由的方法，包括網絡層次圖構建步驟 對於出口節點，其層次值為零； 對於其他節點，其層次值為該節點的各個鄰居節點相對於出口節點所對應的層次值中的最小值再加1 ;從而獲得網絡中各個節點的層次值；
節點勢能構建步驟 如果當前節點為層次值為零的節點，則其勢能值為0 ; 如果當前節點為其它層次的節點，則在其同層或低層鄰居節點中選出實際鏈路帶寬最大的一個節點作為當前節點的勢能定義參考節點，然後將該鄰居節點的層數加1作為當前節點的勢能值； 當前節點的其它鄰居節點的勢能值為這些鄰居節點的層次值；
以勢能值小於當前節點的鄰居節點作為當前節點的可用下一跳路由。
優選地，所述網絡層次圖構建具體包括 由已經構建成f-1層的節點發起第f層的構建，向鄰居節點發送網絡層次圖構建觸發報文； 當鄰居節點接收到該網絡層次圖構建觸發報文，如果該鄰居節點的層次值尚未定
4義，則定義為f，並向該鄰居節點的鄰居節點發送網絡層次圖構建觸發報文；如果該鄰居節點的層次值已經定義為f、f-l或f-2，則不對該層次值做任何調整；如果該鄰居節點的層次值已經定義為大於f的值，則將該鄰居節點的層次值調整為f，並向該鄰居節點的鄰居節點發送網絡層次圖構建觸發報文。 優選地，所述方法還包括在當前節點的可用下一跳路由集合為空時，則進行當前節點層次值的更新過程； 所述當前節點層次值的更新過程包括 當前節點判斷該當前節點的同層鄰居節點集合是否為空，如果不為空，則將該當前節點的層次值加l，重新定義為該當前節點的勢能值，並生成網絡層次圖信息通告報文，將該當前節點的層次值的變化情況通告給該當前節點的鄰居節點； 如果判斷當前節點的同層鄰居節點集合為空，則當前節點泛洪發送網絡層次圖請求更新報文(NLG-RUP)，其中NLG-RUP報文中的層次值為所述當前節點的層次值減2，如果當前節點的層次值減2小於零，那麼該值設置為O，消息發送完後將關於該出口節點的所有信息刪除；當節點收到該NLG-RUP報文後，首先查看是否收到過此報文，如果是則不做任何處理；否則，查看該報文的層次值，如果大於當前節點的層次值，那麼丟棄該報文，如果小於當前節點的層次值，那麼將NLG-RUP報文繼續泛洪給當前節點的鄰居節點，並且將關於該出口節點的所有信息刪除；如果等於當前節點的層次值，那麼節點停止繼續泛洪發送NLG-RUP，將發送網絡層次圖構建觸發報文(NLG-CTP);節點收到NLG-CTP報文後，將按照節點勢能的計算方法進行相應的計算，當計算得到的層次值和當前節點原來的層次值相同時，那麼停止發送NLG-CTP報文，層次值算法更新結束。
優選地，所述方法還包括 根據鄰居節點發送過來的網絡層次圖信息通告報文對節點的勢能進行調整。
優選地，所述方法還包括當節點相對於某個目的地的層次值發生變化後，則按照所述勢能構建步驟對該節點和鄰居節點的勢能值進行相應的調整。 優選地，所述方法還包括在進行網絡層次圖的初始構建時，當節點發現自己相對於某個目的節點的層次信息發生變化後，則節點將自己相對於網絡中的各個目的節點所處的層次信息寫入網絡層次圖信息通告報文，並將所述網絡層次圖信息通告報文廣播發送給其鄰居節點。 優選地，所述方法還包括當節點的網絡層次檢測到所有的低層次節點均不可用時，或者收到其它路由器發送的網絡層次圖信息通告報文後該節點的網絡層次信息發生了變化，或者是新節點加入，則節點將自己相對於網絡中的各個目的節點所處的層次信息寫入網絡層次圖信息通告報文，並將所述網絡層次圖信息通告報文廣播發送給其鄰居節點。
優選地，所述方法還包括接收到鄰居節點發送過來的關於某目的節點的網絡層次圖路由請求，將自己相對於網絡中的各個目的節點所處的層次信息寫入網絡層次圖信息通告報文，並將所述網絡層次圖信息通告報文廣播發送給其鄰居節點。
另一方面，本發明還提供一種獲取多下一跳路由的裝置，包括 網絡層次圖構建單元，用於對於出口節點，將其層次值構建為零；還用於對於其他節點，將其層次值構建為該節點的各個鄰居節點相對於出口節點所對應的層次值中的最小值再加1 ;從而獲得網絡中各個節點的層次值；
節點勢能構建單元，用於對當前節點為層次值為零的節點，將其勢能值構建為O， 還用於對當前節點為其它層次的節點，在其同層或低層鄰居節點中選出實際鏈路帶寬最大 的一個節點作為當前節點的勢能定義參考節點，然後將該鄰居節點的層數加1作為當前節 點的勢能值。 再一方面，本發明還提供一種路由器，包括上述獲取多下一跳路由的裝置。 通過本發明實施例，網絡故障恢復時間短，自適應能力強，並且在以單一故障為主
的一般網絡環境和並發多故障的網絡極端環境下均具有較好的網絡性能。


為了更清楚地說明本發明實施例或現有技術中的技術方案，下面將對實施例或現 有技術描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖是本發明 的一些實施例，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據 這些附圖獲得其他的附圖。 圖1A是本發明實施例中的網絡拓撲圖；
圖IB是本發明實施例中的網絡層次圖； 圖2是本發明實施例中網絡層次圖的構建方法的計算過程示意圖；
圖3是本發明實施例中網絡層次圖的構建過程的具體實現示意圖；
圖4是本發明實施例中層次圖已構建完成的示意圖；
圖5和圖6是本發明實施例中節點層次值的觸發更新的流程示意圖；
圖7是本發明實施例中網絡層次圖構建觸發報文的協議格式的示意圖；
圖8是本發明實施例中網絡層次圖信息通告報文的協議格式的示意圖；
圖9是本發明實施例中網絡層次圖請求更新報文的協議格式的示意圖；
圖10是本發明另一實施例提供的獲取多下一跳路由的裝置的示意圖。
具體實施例方式
為使本發明實施例的目的、技術方案和優點更加清楚，下面將結合本發明實施例 中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例是 本發明一部分實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員 在沒有作出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
自然界中，水流具有從高處往低處流的特性，原因是水在流動中由於所流經地點 的海拔高度不同而具有相對的勢能，只要在高勢能點和低勢能點之間存在相通的通道，水 流就會沿著所有可行通道從高勢能點流向低勢能點。受此啟發，發明人提出一種節點勢能 導向多下一跳路由生成算法，該算法將勢能的概念引入IP網絡，並將節點勢能定義為網絡 中節點到零勢能點之間滿足一定要求的可達性度量。如果只簡單地考慮節點之間是否可 達，節點勢能就退化為從本節點到零勢能點的跳數。在設定零勢能節點後，通過勢能通告過 程，網絡中的其它節點就能夠獲得相對於零勢能節點的具體勢能。規定所有發送到零勢能 節點的網絡數據報文，均向所有勢能降低的下一跳節點轉發。由於網絡數據報文的流向是 節點勢能降低的方向，能保證轉發數據報文時不存在環路。 本發明實施例提供的導向多下一跳路由生成算法的核心是建立多下一跳路由信
6息，即定義節點的勢能值。節點勢能值是基於對網絡層次圖的劃分和節點的實際帶寬來定 義鄰居節點的勢能值，建立過程就是設定某個目的節點為零勢能點，通過網絡層次圖的劃 分過程，使網絡中其它所有節點獲知自己和所有鄰居對應於該零勢能節點所處的網絡層次 圖，然後再依據鏈路實際帶寬定義出自己和鄰居的勢能，從而節點可以從這些鄰居中選擇 低勢能節點作為多下一跳進行報文的轉發。以圖1A的網絡拓撲為例，經過網絡層次圖劃 分之後得到圖1B所示的相對於目的節點i的網絡層次圖，在層次劃分的過程中，所有節點 均知道自己鄰居節點的層次值，然後各個節點依據帶寬最大原則定義出自己的勢能值和鄰 居節點關於目的節點i的勢能值，各節點在進行報文轉發時選擇低勢能節點進行數據的轉 發。當網絡拓撲發生變化，如節點的移出或者加入，網絡層次圖要及時更新。節點層次值的 更新是由特定事件來進行觸發更新。 在詳細說明本發明實施例的方案前，首先詳細解釋下文將用到的術語的含義
1)零勢能點用戶網絡流流出網絡的出口節點； 2)網絡層次圖針對某個目的節點，網絡中所有其它節點相對於它的層次分布 圖； 3)節點勢能在網絡中，節點到零勢能點之間滿足一定要求的可達性度量值；
4)路由器ID :將節點i的所有接口中配置的最大IP位址定義為節點的路由器 ID ; 5)激活以下情況下我們稱節點S被激活。當節點S檢測到鏈路代價增加或鏈路 故障時，或者從某一下遊節點接收到激活請求消息時； 6)勢能定義參照節點如果某一個節點A定義自己的勢能值時參照了節點B的層 次，則將B的層次加1作為自己的勢能值，節點B稱為節點A的勢能定義參照節點；
7)可用下一跳集合，記為&」{}，表示節點i往目的節點j發送報文時的可用下一 跳集合； 8)網絡層次圖構建觸發報文(Network Layer Graph Construction TriggerPacket， NLG-CTP):主要功能是網絡層次圖構建的啟動報文；9)網絡層次HK言息通告矛艮文(Network Layer Graph InformationAdvertisement
Packet, NLG-IAP):主要功能是向鄰居節點通告自己相對於某個出口節點的層次信息； 10)網絡層次圖路由請求報文(Network Layer Graph Routing RequestPacket，
NLG-RRP):主要功能是要求得到鄰居節點相對於某指定出口節點所對應的層次； 11)網絡層次圖請求更新報文(Network Layer Graph Request Update Packet,
NLG-RUP):主要功能是通知網絡中指定相對於某目的節點對應層次上的節點進行層次的重
新構建。 在NP-MNHA中，勢能實際上是在概率意義上對從報文發送節點到接收節點之間連 接可用性的一種度量，根據節點之間勢能差值大小完成數據報文轉發決策。影響勢能差 (Potential Difference)的因素很多，包括網絡連接的有無、鏈路帶寬大小、接收節點的處 理負載、接收節點流量負載等歷史統計信息、網絡拓撲結構決定的接收節點拓撲分布特徵 等。在本發明中將勢能定義為基於跳數和鏈路的實際帶寬的一個混合度量值。跳數度量記 錄分組經過的路由器個數，每臺路由設備均為一跳；鏈路的實際帶寬為網絡初始化時路由 器配置的鏈路的帶寬。
基於上述基本思想，本發明提供一種獲取多下一跳路由的方法，包括 步驟S101 :網絡層次圖構建步驟 步驟S1011 :對於出口節點，其層次值為零； 步驟S1012 :對於其他節點，其層次值為該節點的各個鄰居節點相對於出口節點 所對應的層次值中的最小值再加1;從而獲得網絡中各個節點的層次值；
步驟S102 :節點勢能構建步驟 步驟S1021 :如果當前節點為層次值為零的節點，則其勢能值為0 ; 步驟S1022 :如果當前節點為其它層次的節點，則在其同層或低層鄰居節點中選
出實際鏈路帶寬最大的一個節點作為當前節點的勢能定義參考節點，然後將該鄰居節點的
層數加1作為當前節點的勢能值； 步驟S1023 :當前節點的其它鄰居節點的勢能值為這些鄰居節點的層次值；
步驟S1024:以勢能值小於當前節點的鄰居節點作為當前節點的可用下一跳路由。 以下以一個具體的實施例說明本發明的具體實現。 網絡層次圖的構建是由每個出口節點發起的，每個節點收到關於某出口節點的網 絡層次圖構建觸發報文後，將按照公式(1)計算自己的層次值。
|L(z.，)) = min[Z^，))] +1，C/e e《，a 其中L(i， j)表示節點i相對於出口節點j所對應的層次值；N為網絡中的節點集
合&為節點i的鄰居集合。
網絡層次圖的具體的構建過程如下 步驟1 :算法初始時，初始節點將自己賦值為0層，然後節點向其鄰居節點發送網 絡層次圖構建觸發報文NLG-CTP記為〈IDO， IDO，0〉，表示節點IDO相對於出口節點IDO的 層次為0 ; 步驟2 :鄰居節點收到IDO發送的報文後，將自己設為l層，並生成NLG-CTP報文 〈ID' ，ID0，0〉向其所有鄰居節點發送；下面層次的節點收到NLG-CTP報文後，按照公式(1) 計算得到自己的層次值，並生成對應的NLG-CTP報文發送給其所有鄰居節點；
...... 步驟f+l :由當前構造發起節點即層值為f-1的節點發起第f層構造，向其鄰居節 點發送NLG-CTP報文記為〈ID〃 ，IDO，O〉；當節點ID〃的鄰居收到該報文後分以下幾種情況
進行處理 如果節點已計算得到自己的層次值為f_2層時，節點收到消息後，由於自己的層 次值小於節點ID的層次值，由公式(1)可知，層次值不需要做任何調整，所以不做任何處 理； 如果節點已計算得到自己的層次值為f-l層時，節點收到消息後，由於自己的層 次值等於節點ID的層次值，由公式(1)可知，層次值不需要做任何調整，所以不做任何處 理； 如果該節點是第一次收到關於出口節點IDO的層次觸發報文，那麼按照公式(1) 得到自己的層次值為f，然後生成NLG-CTP報文記為〈ID〃 ' ，IDO，f〉發送給自己的鄰居；
如果節點已計算得到自己的層次值為f層時，節點收到消息後，按照公式(1)己的 層次不做調整，，所以不做任何處理； 如果節點已計算得到自己的層次值為大於f層時，節點收到消息後，將按照公式 (1)調整自己的層次值為f+l，並生成NLG-CTP報文記為〈ID" " ， ID0，f+l〉發送給自己的 鄰居。 當第f層構造完成時，第f層中的每個節點都知道自己在第f層，並且知道它鄰居 節點中的哪些節點在f-層，而f-l層中的節點知道自己所有的鄰居中哪些為f層，哪些為 f-l層，哪些為f-2層； 步驟f+2 :假設第f層構造完成，但是算法尚未終止，將開始第f+l層的構造。f層 的每個節點向所有鄰居節點進行通告，通告報文中將包括該節點和其鄰居之間鏈路的實際 帶寬； 圖2示出了網絡層次圖的構建方法的計算過程示意圖，可以看出，算法的主要特 點是近鄰同步由f-l層節點發起第f+l層節點的構建，不需要每次構建都由根節點發起。
針對網絡中的每個節點，網絡層次圖的構建過程的實現如圖3所示，包括
步驟S301 :判斷是否是出口節點，如果是，則執行步驟S302。 步驟S302 :初始化該節點的層次為零，然後執行步驟S303 :發送網絡層次圖構建 觸發報文，記為〈IDO， ID0，0〉，然後執行步驟S304。 步驟S305 :當S301的判斷結果為否時，則判斷是否接收到網絡層次圖構建觸發報 文，記為〈ID， IDO， f-l〉，如果是，則繼續執行一下步驟步驟S306若本層為第f-2層，則執行步驟S304 ;步驟S307若本層為第f-l層，則執行步驟S304 ;步驟S308若本層為第f層，則執行步驟S304 ;步驟S309若本層的層次值未知，則執行步驟S311 ;步驟S310若本層的層次值大於f層，則執行步驟S311 ;步驟S311將節點側層次值修改為f ;步驟S312發送網絡層次圖構建觸發報文，記為〈ID， IDO， f-l〉；步驟S304判斷是否接收到所有鄰居節點的網絡圖層次觸發報文，若果是，則結
束全部流程。 當網絡層次圖的構建算法執行完後，此時網絡中的所有節點均知道自己到達某節 點自己所處的層次、自己的鄰居節點的層次以及和鄰居節點之間的實際帶寬，接下來節點 將定義自己的勢能值，其步驟如下
步驟1 :零層直接定義自己的勢能值為0 ; 步驟2 :其它層次的節點在其同層或低層鄰居節點中選出實際鏈路帶寬最大的一 個節點作為自己的勢能定義參考節點，然後將該鄰居節點的層數加1作為自己的勢能值， 而其它鄰居節點的勢能值為這些鄰居節點的層次值； 步驟3 :當節點定義完成自己所有鄰居節點的勢能值之後，將勢能值小於自己的 鄰居節點作為可用下一跳。 通過以上的步驟，節點勢能定義完成。勢能值為一個局部變量，也就是說一個節點 僅僅對自己及其鄰居的勢能進行定義，並且定義完後並不將這個值告知其它的節點，僅僅
9用這些值作為參考選擇到達出口節點的可用下一跳。 圖4中假設網絡的層次圖已構建完成，以節點A為例說明勢能值的定義方法，假設 在節點A的同層和低層節點中，節點B提供的實際帶寬最大，那麼節點B就是自己的勢能定 義參考節點，所以得到自己的勢能為f+l，而節點B、C、D、E和F的勢能分別為他們自己的層 次值f 、 f_l、 f_l、 f+1和f+l，這樣節點B、 C和D就是節點A最為到達出口節點的可用下一 跳。 另外，本實施例提供的方法優選地還包括對節點層次值的更新過程，具體地，如圖 5和圖6所示，節點層次值的觸發更新是由於節點的可用下一跳集合為空這一特定事件導 致的，當節點的可用下一跳集合為空當時(即步驟S501)，節點進行以下的操作(l)假設節 點的層次值為n，節點查看自己的同層鄰居節點集合是否為空(即步驟S502)，如果不為空， 那麼節點將自己的層次值加1，重新定義節點的勢能值，並生成NLG-IAP報文，將自己層次 值的變化情況通告給自己的鄰居(即步驟S503和S504); (2)如果節點的同層鄰居節點集合為空，那麼節點按以下的步驟進行操作
泛洪發送網絡層次圖請求更新報文(NLG-RUP)，其中NLG-RUP中的層次值為自己 的層次值減2，如果自己的層次值減2小於零，那麼該值設置為0，消息發送完後將關於該出 口節點的所有信息刪除； 當節點收到該類NLG-RUP後，首先查看是否收到過此報文，如果是那麼不做任何 處理；否則，查看該報文的層次值，(即步驟S602)，那麼將NLG-RUP報文繼續泛洪給自己的 鄰居(即步驟S603)，並且將關於該出口節點的所有信息刪除；如果不大於自己的層次值且 小於自己的層次值，那麼丟棄該報文不做任何處理(即步驟S606);如果等於自己的層次， 那麼節點停止繼續泛洪發送NLG-RUP，將發送網絡層次圖構建觸發報文NLG-CTP(即步驟 S605)，並且將關於該出口節點的所有信息刪除；； 節點收到NLG-CTP報文後，將按照節點勢能的計算方法進行相應的計算，當計算 得到的層次值和自己原來的層次值相同時，那麼停止發送NLG-CTP報文，層次值算法更新 結束。 另外，本發明實施例提供的方法優選地還包括對節點勢能值的更新，節點勢能值
的更新主要在以下情況下對節點的勢能值進行更新 1.網絡層次圖信息通告報文(NLG-IAP)引起的勢能值更新 根據鄰居節點發送過來的網絡層次圖信息通告報文(NLG-IAP)進行調整， NLG-IAP報文的主要內容是關於該節點相對於各個/某個出口節點在網絡中的層次信息， 節點接收到NLG-IAP報文後執行以下步驟 提取NLG-IAP報文中的層次信息，假設每條路由條目包括RUIi = 〈ID， DeSi， Lay,， 而節點資料庫中存儲的信息為RUI' i = 〈ID， DeSi， Lay',，當其中的信息滿足如下三種 情況時，路由器根據獲得的信息對自己的路由表進行更新 如果收到的路由表項中的目的網絡在自身的路由表中不存在，那麼添加之，並向 其它鄰居發送關於該目的地址的網絡層次圖路由請求報文，按照接收到的NLG-IAP報文， 按照公式(1)計算得到節點和其鄰居對應的層次值，然後定義鄰居節點關於該目的節點的 勢能值，； 如果收到的路由表項中的目的網路存在於自身的路由表中，但是Lay' i < Layi，那麼相應的調整該鄰居節點的層次值和勢能值；如果鄰居節點調整後的勢能值大於自己的 勢能值，並且該鄰居節點在自己的下一跳集合中，那麼從下一跳集合中刪除該鄰居節點；如 果不在，則不做其它的處理； 如果Layi < Lay' i，那麼相應的調整鄰居資料庫中該鄰居節點的層次值和勢能 值；如果鄰居節點調整後的勢能值小於自己的勢能值，並且該鄰居節點原來不在自己的下 一跳集合中，那麼將其加入到下一跳集合中；如果在，則不做任何的處理；而此時節點並不 調整自己的層次值和勢能值。 2.節點的層次值發生變化導致的勢能值的更新 當節點相對於某個目的地的層次值變化了，那麼按照相應的調整策略對自己和鄰 居節點的勢能值進行相應的調整。 另外，本發明實施例提供的方法還包括在發生以下情況時需要節點生成網絡層 次圖信息通告報文廣播發送給其鄰居節點 A.在進行網絡層次圖的初始構建時，當節點發現自己相對於某個目的節點的層次 信息發生變化後，節點將自己相對於網絡中的各個目的節點所處的層次信息寫入網絡層次 圖信息通告報文NLG-IAP ; B.節點的網絡層次信息發生了變化(自己檢測到所有的低層次節點均不可用時， 或者收到其它路由器發送的網絡層次圖信息通告報文後該節點的網絡層次信息發生了變 化，或者是新節點加入)，節點將自己相對於網絡中的各個目的節點所處的層次信息寫入網 絡層次圖信息通告報文NLG-IAP ; C.接收到鄰居節點發送過來的關於某目的節點的網絡層次圖路由請求，將自己相 對於網絡中的各個目的節點所處的層次信息寫入網絡層次圖信息通告報文NLG-IAP ;。
當節點接收到網絡層次圖信息通告報文後進行的處理方法按照網絡層次圖構建 算法進行計算和操作。 最後說明實現本發明實施例的幾種協議報文格式。
1.網絡層次圖構建觸發報文NLG-CTP 圖7示出了網絡層次圖構建觸發報文的協議格式。網絡中某個出口節點加入網絡
時，發送該分組，啟動網絡節點建立以該節點為O層的網絡層次圖。 2.網絡層次圖信息通告報文NLI-IAP 圖8示出了網絡層次圖信息通告報文的協議格式。向所有鄰居節點採用組播地址
發送；表示自己相對於出口節點Ai的層次值(i = 1， 2，......， n)。該報文通常將啟動鄰
居節點進行勢能動態調整。 3.網絡層次圖請求更新報文NLG-RUP 圖9示出了網絡層次圖請求更新報文的協議格式。其中的層次值為節點的相對於 該出口節點的層次值減2。 本發明另一實施例相應提供一種獲取多下一跳路由的裝置，如圖10所示，該裝置 1000包括: 網絡層次圖構建單元1001，用於對於出口節點，將其層次值構建為零；還用於對 於其他節點，將其層次值構建為該節點的各個鄰居節點相對於出口節點所對應的層次值中 的最小值再加1 ;從而獲得網絡中各個節點的層次值；
節點勢能構建單元1002，用於對當前節點為層次值為零的節點，將其勢能值構建 為O，還用於對當前節點為其它層次的節點，在其同層或低層鄰居節點中選出實際鏈路帶寬 最大的一個節點作為當前節點的勢能定義參考節點，然後將該鄰居節點的層數加1作為當 前節點的勢能值。 另外，本發明再一實施例還提供一種路由器，該路由器中包含上述獲取多下一跳 路由的裝置。 以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域的普通技術人 員來說，在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改進和潤飾也應 視為本發明的保護範圍。
權利要求
一種獲取多下一跳路由的方法，其特徵在於，包括網絡層次圖構建步驟對於出口節點，其層次值為零；對於其他節點，其層次值為該節點的各個鄰居節點相對於出口節點所對應的層次值中的最小值再加1；從而獲得網絡中各個節點的層次值；節點勢能構建步驟如果當前節點為層次值為零的節點，則其勢能值為0；如果當前節點為其它層次的節點，則在其同層或低層鄰居節點中選出實際鏈路帶寬最大的一個節點作為當前節點的勢能定義參考節點，然後將該鄰居節點的層數加1作為當前節點的勢能值；當前節點的其它鄰居節點的勢能值為這些鄰居節點的層次值；以勢能值小於當前節點的鄰居節點作為當前節點的可用下一跳路由。
2. 根據權利要求1所述的方法，其特徵在於，所述網絡層次圖構建具體包括 由已經構建成f-1層的節點發起第f層的構建，向鄰居節點發送網絡層次圖構建觸發報文；當鄰居節點接收到該網絡層次圖構建觸發報文，如果該鄰居節點的層次值尚未定義， 則定義為f，並向該鄰居節點的鄰居節點發送網絡層次圖構建觸發報文；如果該鄰居節點 的層次值已經定義為f、f-l或f-2，則不對該層次值做任何調整；如果該鄰居節點的層次值 已經定義為大於f的值，則將該鄰居節點的層次值調整為f，並向該鄰居節點的鄰居節點發 送網絡層次圖構建觸發報文。
3. 根據權利要求1所述的方法，其特徵在於，所述方法還包括在當前節點的可用下一 跳路由集合為空時，則進行當前節點層次值的更新過程；所述當前節點層次值的更新過程包括當前節點判斷該當前節點的同層鄰居節點集合是否為空，如果不為空，則將該當前節 點的層次值加l，重新定義為該當前節點的勢能值，並生成網絡層次圖信息通告報文，將該 當前節點的層次值的變化情況通告給該當前節點的鄰居節點；如果判斷當前節點的同層鄰居節點集合為空，則當前節點泛洪發送網絡層次圖請求 更新報文(NLG-RUP)，其中NLG-RUP報文中的層次值為所述當前節點的層次值減2，如果當 前節點的層次值減2小於零，那麼該值設置為0，消息發送完後將關於該出口節點的所有 信息刪除；當節點收到該NLG-RUP報文後，首先查看是否收到過此報文，如果是則不做任 何處理；否則，查看該報文的層次值，如果大於當前節點的層次值，那麼丟棄該報文，如果 小於當前節點的層次值，那麼將NLG-RUP報文繼續泛洪給當前節點的鄰居節點，並且將關 於該出口節點的所有信息刪除；如果等於當前節點的層次值，那麼節點停止繼續泛洪發送 NLG-RUP，將發送網絡層次圖構建觸發報文(NLG-CTP);節點收到NLG-CTP報文後，將按照 節點勢能的計算方法進行相應的計算，當計算得到的層次值和當前節點原來的層次值相同 時，那麼停止發送NLG-CTP報文，層次值算法更新結束。
4. 根據權利要求3所述的方法，其特徵在於，所述方法還包括 根據鄰居節點發送過來的網絡層次圖信息通告報文對節點的勢能進行調整。
5. 根據權利要求3所述的方法，其特徵在於，所述方法還包括當節點相對於某個目的地的層次值發生變化後，則按照所述勢能構建步驟對該節點和鄰居節點的勢能值進行相應 的調整。
6. 根據權利要求4所述的方法，其特徵在於，所述方法還包括在進行網絡層次圖的初 始構建時，當節點發現自己相對於某個目的節點的層次信息發生變化後，則節點將自己相 對於網絡中的各個目的節點所處的層次信息寫入網絡層次圖信息通告報文，並將所述網絡 層次圖信息通告報文廣播發送給其鄰居節點。
7. 根據權利要求4所述的方法，其特徵在於，所述方法還包括當節點的網絡層次檢測 到所有的低層次節點均不可用時，或者收到其它路由器發送的網絡層次圖信息通告報文後 該節點的網絡層次信息發生了變化，或者是新節點加入，則節點將自己相對於網絡中的各 個目的節點所處的層次信息寫入網絡層次圖信息通告報文，並將所述網絡層次圖信息通告 報文廣播發送給其鄰居節點。
8. 根據權利要求4所述的方法，其特徵在於，所述方法還包括接收到鄰居節點發送過 來的關於某目的節點的網絡層次圖路由請求，將自己相對於網絡中的各個目的節點所處的 層次信息寫入網絡層次圖信息通告報文，並將所述網絡層次圖信息通告報文廣播發送給其 鄰居節點。
9. 一種獲取多下一跳路由的裝置，其特徵在於，包括網絡層次圖構建單元，用於對於出口節點，將其層次值構建為零；還用於對於其他節 點，將其層次值構建為該節點的各個鄰居節點相對於出口節點所對應的層次值中的最小值 再加1 ;從而獲得網絡中各個節點的層次值；節點勢能構建單元，用於對當前節點為層次值為零的節點，將其勢能值構建為O，還用 於對當前節點為其它層次的節點，在其同層或低層鄰居節點中選出實際鏈路帶寬最大的一 個節點作為當前節點的勢能定義參考節點，然後將該鄰居節點的層數加1作為當前節點的 勢能值。
10. —種路由器，其特徵在於，包括如權利要求9中的獲取多下一跳路由的裝置。
全文摘要
本發明提供一種獲取多下一跳路由的方法、裝置和路由器，其中該方法包括網絡層次圖構建步驟對於出口節點，其層次值為零；對於其他節點，其層次值為該節點的各個鄰居節點相對於出口節點所對應的層次值中的最小值再加1；從而獲得網絡中各個節點的層次值；節點勢能構建步驟如果當前節點為層次值為零的節點，則其勢能值為0；如果當前節點為其它層次的節點，則在其同層或低層鄰居節點中選出實際鏈路帶寬最大的一個節點作為當前節點的勢能定義參考節點，然後將該鄰居節點的層數加1作為當前節點的勢能值；當前節點的其它鄰居節點的勢能值為這些鄰居節點的層次值；以勢能值小於當前節點的鄰居節點作為當前節點的可用下一跳路由。
文檔編號H04L12/56GK101710895SQ200910224019
公開日2010年5月19日 申請日期2009年11月30日 優先權日2009年11月30日
發明者蘭巨龍, 劉宗海, 卜佑軍, 張建輝, 王濱, 王肖楠, 郭虹, 陳庶樵 申請人:中國人民解放軍信息工程大學