區分路由信息更新的優先級的製作方法

2023-09-23 07:16:10

專利名稱：區分路由信息更新的優先級的製作方法
技術領域：
此處公開的各種示例性實施例整體涉及網絡業務路由。
背景技術：
分組交換網絡用於提供數量不斷增長的現今各種形式的通信。除了經由網絡(諸如網際網路)的計算機到計算機的通信之外，分組交換網絡還實現關聯於其它應用(諸如電視、電話和無線電)的信息的通信。通過這些和其它應用，終端用戶可以越過大距離來傳送和接收眾多信息類型。為了將所述信息從其源移至其目的地，分組交換網絡採用一些互連的路由設備。當一個路由器接收到數據的分組時，該路由器將確定該分組的目的地位於何處，並將該分組轉發給下一個最靠近的路由器。該下一個路由器將遵循類似的過程，並且由此，分組將最終被遞送到其目的地，很像「救火隊列(bucket brigade)」。分組交換網絡中的一個重大問題在於:為每個網絡提供對於確定每個分組應當被傳送到哪個「下一跳」路由器來說必要的信息。雖然理論上可以將該信息手動地編程到路由器中，但是網絡拓撲的規模和動態本質經常致使該方法不可行。作為代替，已開發了各種協議來自動確定針對每個路由器的去往每個目的地的最佳路徑。例如，開放最短路徑優先標準規定自治系統內的路由器共享關於該系統內的鏈路狀態的信息。通過使用該信息，每個路由器可以獨立開發轉發表，以便在確定每個接收分組應當被發送到何處時使用。當網絡狀態改變時，每個路由器更新其轉發表，以便確保每個目的地仍然可達，並且每個所選路徑是最優的。

發明內容
雖然諸如開放最短路徑優先這樣的標準提供了針對生成路由信息這一問題的有效解決方案，但是這些標準生效起來耗費時間。例如，在發生網絡改變之後的瞬間，在每個節點處的路由信息從某種程度上來說是過時和不正確的。直到每個節點接收到對該改變的指示、確定網絡的新狀態、確定最優路由路徑以及更新轉發表之前，該信息都仍會是過時的。在可能頻繁地將節點添加到網絡、將節點從網絡中移除、節點進入故障狀態、節點從故障狀態恢復以及其它網絡改變事件的情況下，相當一部分的路由器操作時間可能花費在根據過時的路由信息來轉發業務或者等待最新的路由信息上。更新轉發表的步驟可在更新路由信息時引入特別大的延遲。除了關聯於自治系統內的其它節點的路由信息之外，每個表可以包括數以千計的針對自治系統外部的子網和/或其它節點的必須響應於網絡中的改變而被更新的條目。然而，各種其它的路由協議可以取決於最新的轉發表來更新其它路由信息。舉例來說，諸如標籤分發協議(LDP)或資源預留協議-業務工程(RSVP-TE)的多協議標籤交換(MPLS)相關協議可以使用轉發表中的路由來建立MPLS路徑。作為進一步的示例，2層隧道協議(L2TP)也可以按照類似方式來使用該轉發表。
相應地，存在對這樣的方法的需求，所述方法減少網絡改變事件與多個路由協議當中的網絡路由信息收斂之間的時間量。特別地，會期望提供一種方法和網絡節點，所述方法和網絡節點減少在一個協議可以開始更新路由信息之前花費在為另一協議更新其它路由信息上的時間量。根據當前對於減少網絡收斂時間的方法的需求，給出了各種示例性實施例的簡要概述。在以下概述中可以做出一些簡化和省略，以下概述旨在突出和介紹各種示例性實施例的一些方面，而非限制本發明的範圍。足以允許本領域的普通技術人員構造和使用本發明概念的對優選示例性實施例的詳細描述將跟隨在稍後的章節中。各種示例性實施例提供了一種網絡路由器，所述網絡路由器區分對於特定轉發表條目的更新的優先級。一旦實施了這樣的關鍵更新，便可以在實施剩餘的轉發表更新時根據其它協議來更新其它路由信息。在各種示例性實施例中，可以區分針對OSPF自治系統內的節點的路由信息的優先級，從而使得可以在應用對轉發表的剩餘更新時使用所述信息來更新MPLS路徑。各種示例性實施例涉及一種方法及相關網絡節點，所述方法包括以下中的一個或多個:在所述節點處接收網絡狀態更新消息；基於所述網絡狀態更新消息，更新路由信息的第一集合的第一部分；在更新了所述路由信息的第一集合的第一部分之後，開始對路由信息的第二集合的更新；以及在開始對所述路由信息的第二集合的更新之後，更新所述第一集合的第二部分。在各種備選實施例中，更新所述第一部分的步驟包括以下中的一個或多個:確定所述網絡內的至少一個其它節點，其中，應當使用針對所述至少一個其它節點的路由信息來更新所述路由信息的第二集合；以及更新所述路由信息的第一集合中與所述至少一個其它節點相關聯的路由信息。各種示例性實施例涉及一種網絡節點，所述網絡節點包括以下中的一個或多個:第一接口，其從另一節點接收分組；網絡狀態更新消息標識器，其確定所述分組是網絡狀態更新消息；第一路由信息存儲器，其存儲路由信息的第一集合；第二路由信息存儲器，其存儲路由信息的第二集合；第一路由信息生成器，其基於所述網絡狀態更新消息來更新所述路由信息的第一集合的第一部分，在更新了所述第一部分之後，指示所述第一部分已被更新，以及在指示所述第一部分已被更新之後，基於所述網絡狀態更新消息來更新所述路由信息的第一集合的第二部分；以及第二路由信息生成器，其響應於指示所述第一部分已被更新，基於所述路由信息的第一集合的第一部分來更新第二路由信息。應當顯而易見，按照這樣的方式，各種示例性實施例實現了對網絡收斂時間的降低。特別地，通過首先選擇性地更新特定路由信息並且觸發第二路由信息生成器，網絡節點可以減少其針對網絡中的全部節點收斂到普通路由狀態所花費的時間。


為了更好地理解各種示例性實施例，參考附圖，其中:圖1示出了用於對數據分組進行路由的示例性網絡；圖2示出了用於確定從一個節點到多個其它可能的節點的最優路徑的示例性最短路徑樹；圖3示出了用於基於分組目的地來確定分組應當被傳送到的下一跳的示例性轉發表；圖4示出了用於對分組進行路由並減少針對多個集合的路由信息的網絡收斂時間的示例性網絡節點；圖5示出了用於減少針對多個集合的路由信息的網絡收斂時間的示例性方法；以及圖6示出了用於減少針對多個集合的路由信息的網絡收斂時間的備選方法。
具體實施例方式現在參考附圖，其中，類似標號指代類似組件或步驟，公開了各種示例性實施例的寬泛方面。如在此處所使用的，術語「路由信息」一般指的是對於路由分組有用的任何數據和/或數據結構，包括但不限於最短路徑樹、轉發表、路由表、MPLS路徑和/或L2TP路徑。圖1示出了用於對數據分組進行路由的示例性網絡100。示例性網絡100可以是用於為各種應用提供數據傳輸的分組交換通信網絡。示例性網絡100可以進一步實現一種標準，該標準用於響應於網絡內的改變而對路由信息進行自動更新。例如，群組101可以構成實現開放最短路徑優先(OSPF)標準的自治系統。示例性網絡可以包括多個節點A-G110-170。每個節點A_G110_170可以是路由器、交換機或其它適於接收並向分組的相應目的地轉發數據分組的網絡設備。每個節點A-G110-170可以進一步關聯於一個或多個網絡地址，諸如網際網路協議(IP)地址和/或媒體訪問控制(MAC)地址。儘管每個節點的每個埠可以關聯於獨立的地址，但是為了簡單起見，示例性網絡100中的每個節點被示為關聯於單個地址。一個或多個節點A-G110-170還可以是實現各種協議(例如像多協議標籤交換(MPLS)、標籤分發協議(LDP)、資源預留協議-業務工程(RSVP-TE)和/或2層隧道協議(L2TP))的標籤交換路由器。每個節點還可以連接到多個附加設備(諸如附加的網絡設備和終端用戶設備)。例如，節點AllO連接到至少兩個其它設備112、114(其各自關聯於一個或多個網絡地址)。在各種實施例中，設備112、114可以屬於類似的子網。例如，設備112、114可以都屬於由IP前綴135.24.0.0/16標識的子網。同樣地，節點G170可以連接到至少兩個其它設備172、174，所述兩個其它設備172、174可以屬於187.50.144.0/24子網。每個節點A-G110-170可以類似地連接到眾多其它設備(未示出)。節點A-Gl 10-170可以分別經由一個或多個鏈路連接到一個或多個其它節點A-G110-170。每個鏈路可以與鏈路開銷相關聯。例如，節點C130可以經由具有開銷2的鏈路連接到節點D140。可以基於各種因素(例如像節點間的地理距離、節點間的中間設備的數目、關聯於鏈路的比特率和/或在鏈路上的當前負載)來指派該鏈路開銷。某些鏈路(諸如節點B120與節點G170之間的鏈路)可能會出故障，並且因而不可用於轉發分組。可以相應地為所述鏈路指派非常高或無窮大的鏈路開銷以便阻止使用。每個節點A-Gl 10-170可以存儲示例性網絡100的本地表示。可以根據在其它節點A-G110-170按照OSPF傳輸的鏈路狀態通告(LSA)消息中所傳送的信息來在本地構造所述本地表示。例如，每個節點可以在鏈路狀態資料庫(LSDB)中存儲所有節點和邊的指示。所述表示可由每個節點A-G110-170用於構造最短路徑樹，以及最終的在將分組轉發到其目的地時使用的轉發表。
圖2示出了用於確定從一個節點到多個其它可能的節點的最優路徑的示例性最短路徑樹(SPT) 200。可以使用諸如示例性網絡100的網絡的當前狀態的表示，使用本領域技術人員已知的任何方法，從節點C130的視角來構造SPT200。例如，節點可以使用Djikstra的最短路徑樹算法來構造SPT。SPT200可以是考慮示例性網絡100而由節點C130構造的SPT。SPT200可以包括對應於節點A-G110-170的多個節點表示A-G210-270。SPT200可以指示從節點C130到網絡內的每個節點的最優路徑。例如，SPT200指示:從節點C130到節點G170的最短路徑是通過節點D140，而非通過節點B120或某個其它路徑。相應地，根據SPT200，由節點C130接收到的去往節點G170的分組應當被轉發到節點D140。節點D140進而可以包括其自己的路由信息，所述路由信息使其能夠將分組轉發到節點G170。在計算了 SPT200之後，節點C130可以更新其轉發表以便反映示例性網絡100的狀態。特別地，節點C130可以分析SPT200來確定對於每個潛在的目的地節點應當使用的下一跳節點。然後可以將該信息存儲在轉發表中用於在轉發分組時的快速訪問。圖3示出了用於基於分組目的地來確定分組應當被傳送到的下一跳的示例性轉發表300。轉發表300可以是例如存儲在節點C130處的資料庫中的表。替代地，轉發表300可以是一系列鍊表、數組或類似的數據結構。因而應當顯而易見，轉發表300是對底層數據的抽象；可以使用適於存儲底層數據的任何數據結構。轉發表300可以包括目的地欄位302和下一跳欄位304。目的地欄位302可以指示與每個條目相關聯的目的地設備，而下一跳欄位304可以指示哪個下一跳設備適於所關聯的目的地設備。應當顯而易見，轉發表300在某些方面是簡化表示。例如，轉發表可以含有附加欄位，諸如傳出(outgoing)埠號、目的地MAC地址和/或備選的下一跳。各種修改對於本領域的技術人員將顯而易見。轉發表可以包括多個條目310-370。條目310可以指示:以IP位址135.24.36.110為目的地的分組應當被轉發到節點B120。取代全地址，還可以在目的地欄位中使用子網或其它群組。例如，條目315可以指示:以135.24.0.0/16子網為目的地的分組也應當被轉發到節點B120。通過使用該條目，可以正確地對以設備112或設備114為目的地的分組進行路由。附加條目320-375可以指示針對示例性網絡100中的每個設備的下一跳路由器。表300可以含有眾多附加條目(未示出)，其為附加節點和/或子網提供了路由信息。已描述了示例性網絡100的組件，將提供對示例性網絡100的操作的簡要概述。應當顯而易見，下面的描述旨在提供對示例性網絡100的操作的概覽，並且因此在某些方面是簡述。下面將結合圖4-6進一步詳細描述示例性網絡100的詳細操作。節點C130可以接收指示了網絡中的改變的LSA。例如，LSA可以指示:節點AllO與節點B120之間的鏈路出故障了。節點C130然後可以計算新的SPT，提供用於到達節點AllO的新的最優路徑。節點C130然後可以開始更新其轉發表300。在更新轉發表300時，節點C130可以區分特定更新的優先級。例如，節點C130可以首先更新條目320、340，因為它們關聯於相鄰節點。節點C130然後可以繼續接著更新條目310、350、360、370，在此之後，轉發表針對群組101內的節點將是最新的。最後，節點C130可以更新條目315、375，以便提供去往群組101外部的設備的路徑。在節點C130結束更新轉發表300之前的某一點，節點C還可以開始更新路由信息的第二集合，例如像MPLS路徑或L2TP路徑。節點C130可以例如在僅是條目320、340已被更新之後或者在針對群組101內的全部節點的條目已被更新之後開始該第二更新過程。第二更新過程可以利用表300中的已更新信息。因而，可以並行地實施路由信息更新過程的一些部分，減少在網絡改變事件之後路由器保持過時的時間量。圖4示出了用於對分組進行路由以及減少針對多個集合的路由信息的網絡收斂時間的示例性網絡節點400。網絡節點400可以對應於示例性網絡100中的一個或多個節點A-G110-170。網絡節點400可以包括分組接收機405、鏈路狀態通告標識器410、路由處理器420、分組發射機425、轉發表存儲器430、鏈路狀態資料庫440、最短路徑樹生成器450、轉發表生成器460、MPLS路徑生成器470和MPLS路徑存儲器480。分組接收機405可以是接口，所述接口包括硬體和/或被編碼在機器可讀存儲介質上的可執行指令，其被配置以便從其它網絡設備接收分組。分組接收機405可以包括多個埠，並且可以從多個網絡設備接收分組。例如，分組接收機405可以接收鏈路狀態通告分組以及關聯於常規網絡業務的分組。鏈路狀態通告(LSA)標識器410可以包括硬體和/或在計算機可讀存儲介質上的可執行指令，其被配置以便確定所接收到的分組是否是節點400應當處理的LSA。如果分組是LSA，則LSA標識器410可以解譯該LSA，並將所指示的網絡改變存儲在鏈路狀態資料庫440中，以便進行進一步處理。否則，LSA標識器可以將分組傳遞給路由處理器420用於進行進一步的路由。應當指出，儘管此處描述的各種實施例涉及使用根據OSPF而構造的鏈路狀態通告的系統，但是各種實施例可以使用備選的網絡更新消息結合其它標準來運行。相應地，可以將LSA標識器410看作通用網絡更新消息標識器。對結合所述其它標準的實現方式有用的修改對於本領域技術人員來說將是顯而易見的。路由處理器420可以包括硬體和/或在機器可讀存儲介質上的可執行指令，其被配置以便將分組路由到其目的地。路由處理器420可以從每個所接收到的分組中提取目的地，並且通過使用存儲在轉發表存儲器430中的轉發表來確定針對該目的地的下一跳。路由處理器420然後可以經由發射機425將分組轉發到合適的下一跳。路由處理器420可以進一步被配置以便根據存儲在MPLS路徑存儲器480中的路由信息來處理和轉發MPLS分組。分組發射機425可以是接口，所述接口包括硬體和/或被編碼在機器可讀存儲介質上的可執行指令，其被配置以便將分組傳送到其它網絡設備。分組發射機425可以包括多個埠，並且可以將多類分組傳送到多個網絡設備。例如，分組發射機425可以傳送鏈路狀態通告分組以及關聯於常規網絡業務的分組。轉發表存儲器430可以是能夠存儲轉發表的任何計算機可讀介質。相應地，轉發表存儲器430可以包括機器可讀存儲介質，諸如只讀存儲器(ROM)、隨機訪問存儲器(RAM)、磁碟存儲介質、光存儲介質、快閃記憶體設備和/或類似的存儲介質。鏈路狀態資料庫(LSDB) 440可以是能夠存儲當前網絡狀態的表示的任何機器可讀介質。LSDB440可以例如存儲自治系統內每個節點和鏈路的指示。相應地，LSDB440可以包括機器可讀存儲介質，諸如只讀存儲器(ROM)、隨機訪問存儲器(RAM)、磁碟存儲介質、光存儲介質、快閃記憶體設備和/或類似的存儲介質。LSDB440可以是節點400內的獨立存儲設備，或者可以與轉發表存儲器430相同。最短路徑樹(SPT)生成器450可以包括硬體和/或在機器可讀存儲介質上的可執行指令，其被配置以便根據網絡的表示來生成最短路徑樹。例如，SPT生成器450可以使用Djikstra的算法或者本領域技術人員已知的任何其它方法來根據存儲在LSDB440中的數據生成最短路徑樹。在生成SPT之後，SPT生成器450可以將SPT傳送到轉發表生成器460。替代地，SPT生成器450可以在每個節點被添加到SPT時向轉發表生成器460傳送信息，從而允許轉發表生成器460在SPT完成之前開始更新轉發表。轉發表生成器460可以包括硬體和/或在機器可讀存儲介質上的可執行指令，其被配置以便基於SPT來生成或更新轉發表。例如，轉發表生成器460可以基於網絡節點400的當前SPT來確定轉發表存儲器430中的任何條目是否應當被添加或修改。轉發表生成器460然後可以實施所述更新，例如通過添加或移除條目或者修改一個或多個條目的下一跳。轉發表生成器460可以進一步適於區分轉發表的更新順序的優先級。例如，轉發表生成器460可以認為與自治系統內的節點相關聯的條目是關鍵的，並且因此首先實施對所述條目的更新。可以根據本領域技術人員已知的任何方法(例如，檢查SPT，使用已從其接收到LSA的路由器標識符的列表和/或搜索與全32比特前綴相關的條目)來標識所述條目。在完成所述關鍵更新之後，轉發表生成器460可以通知MPLS路徑生成器470完成了關鍵更新。MPLS路徑生成器470然後可以開始更新附加的路由信息，如將參考該組件進一步詳細描述的那樣。在此期間，轉發表生成器460可以完成對轉發表的非關鍵更新。根據各種備選實施例，轉發表生成器460可以進一步區分關鍵更新的優先級。例如，轉發表生成器460可以利用當前SPT來標識相鄰節點，並且首先更新對應的轉發表條目。轉發表生成器460然後可以繼續實施與相隔兩跳的節點相關的更新。轉發表生成器460可以按照這樣的方式繼續，直到所有關鍵更新已被實施。在每個所述階段之後，轉發表生成器460可以向MPLS路徑生成器470指示已完成特定的關鍵更新，從而允許MPLS路徑生成器470開始更新MPLS路由信息。根據附加的備選實施例，轉發表生成器460可以區分與特定類型設備相關的更新的優先級。例如，一旦針對緊靠的鄰居的條目被更新，轉發表生成器460就可以處理針對自治系統的網關路由器，諸如區域邊界路由器和/或區域概要邊界路由器。轉發表生成器460然後可以繼續按照不斷擴大的波狀(expanding wave)以逐跳方式處理剩餘的更新。應當指出，儘管將節點400描述為根據OSPF的各種方面來起作用，但是此處描述的方法可以適用於其它標準。符合其它標準的適當修改對於本領域技術人員來說將是顯而易見的。相應地，SPT生成器450和轉發表生成器460可以單獨地或是一起被看作是通用「路由信息生成器」。MPLS路徑生成器470可以包括硬體和/或在計算機可讀存儲介質上的可執行指令，其被配置以便生成或更新MPLS路由信息。MPLS路徑生成器470可以使用來自轉發表存儲器430的信息來建立或修改最優MPLS路徑，並將所述路由信息存儲在MPLS路徑存儲器480中。MPLS路徑生成器470可以適於在從轉發表生成器460接收到關於已發生網絡改變和/或已對轉發表實施了至少一些關鍵更新的指示之後開始所述更新過程。應當指出，儘管將節點400描述為根據MPLS的各個方面來起作用，但是此處描述的方法可以適用於其它標準。符合其它標準的適當修改對於本領域技術人員來說將是顯而易見的。例如，可以由根據L2TP生成路徑的L2TP路徑生成器(未示出)來替代MPLS路徑生成器470。相應地，MPLS路徑生成器470可被看作是第二通用「路由信息生成器」。MPLS路徑存儲器480可以是能夠存儲MPLS路由信息的任何機器可讀介質。MPLS路徑存儲器480可以例如存儲眾多記錄,所述記錄指定了傳入(incoming)標籤、傳出標籤、傳入接口和/或傳出接口。相應地，MPLS路徑存儲器480可以包括機器可讀存儲介質，諸如只讀存儲器(ROM)、隨機訪問存儲器(RAM)、磁碟存儲介質、光存儲介質、快閃記憶體設備和/或類似的存儲介質。MPLS路徑存儲器480可以是節點400內的獨立存儲設備，或者可以與轉發表存儲器430和/或LSDB440相同。圖5示出了用於減少針對多個集合的路由信息的網絡收斂時間的示例性方法500。方法500可以由網絡節點400的各種組件來實施，例如像LSA標識器410、SPT生成器450、轉發表生成器460和/或MPLS路徑生成器470。方法500可以開始於步驟505，並且繼續到步驟510，在此處，節點400可以接收指示了網絡狀態方面的改變的LSA。節點400然後可以在步驟515中計算新的SPT。接下來，在步驟520中，節點400可以確定關鍵節點的列表。例如，節點400可以確定OSPF自治系統內的每個節點均是關鍵節點。方法500然後可以繼續到步驟525，在此處，節點400可以定位要處理的第一關鍵節點。在步驟530中,節點400可以根據新計算出的SPT來更新與關鍵節點相關聯的一個或多個條目。例如，節點400可以在轉發表中定位包括了用於關鍵節點的32比特前綴地址的條目，並且修改下一跳標識。方法500然後可以繼續到步驟535，在此處，節點400可以確定是否存在要處理的附加關鍵節點。如果存在，則方法500可以繼續到步驟540，在此處，節點400可以定位下一關鍵節點以便進行處理，並且循環回到步驟530。一旦已經處理了所有關鍵節點，則方法500可以繼續到步驟545，在此處，節點400可以開始基於轉發表來更新MPLS路由信息的過程。方法500可以繼續到步驟550，在此處，節點400可以通過處理非關鍵條目來結束更新轉發表。應當指出，可以與重新計算MPLS路由信息同時實施該步驟，要麼在分離的處理器上並行地實施，要麼通過共享單個處理器上的處理時間來實施。在重新計算MPLS路由信息之後或在此期間，節點400可以例如根據LDP或RSVP-TE協議向其它節點傳送一個或多個MPLS更新消息。替代地，節點400可以在發送任何MPLS更新消息之前等待完成轉發表更新。方法500然後可以結束於步驟560。圖6示出了用於減少針對多個集合的路由信息的網絡收斂時間的備選方法600。方法600可以由網絡節點400的各種組件來實施，例如像LSA標識器410、SPT生成器450、轉發表生成器460和/或MPLS路徑生成器470。方法600可以與方法500類似，但進一步區分了轉發表的更新的優先級。方法600可以開始於步驟605，並且與方法500類似，分別在步驟610和615中接收LSA和計算新的SPT。在步驟620中，節點400可以確定系統中最關鍵節點的集合。例如，節點400可以將處於SPT的根下面的第一層級上的那些節點認為是最關鍵的。可以將這些節點稱為相鄰節點。方法600然後可以繼續到步驟625，在此處，節點400可以從最關鍵節點的該集合中確定要處理的第一節點。在步驟630中，與方法500中的步驟530類似，節點400可以鑑於新的SPT來更新與關鍵節點相關聯的一個或多個條目。方法600然後可以繼續到步驟635，在此處，節點400可以確定當前層級中是否存在要處理的附加關鍵節點。如果存在，則節點400可以在步驟640中定位當前層級中的下一關鍵節點，並且方法600可以循環回到步驟630。一旦已經處理了一層級內的所有關鍵節點，則方法600可以繼續到步驟645，在此處，節點400可以基於對轉發表的最近更新來對MPLS路由信息實施至少一部分更新過程。當該過程被實施時，方法600可以繼續到步驟647，在此處，節點400可以確定是否仍要處理附加的關鍵層級。如果是的話，則方法600可以繼續到步驟649，在此處，節點400可以檢索下一組關鍵節點。例如，節點400可以在SPT上檢索從最新處理的層級往下的下一層級上的一組節點。以這樣的方式，節點400可以順序處理「一跳」、「兩跳」等節點。方法600然後可以循環回到步驟625以便處理新的關鍵層級。一旦已經實施了所有的關鍵更新，則方法600可以繼續到步驟650。如在方法500中那樣，節點可以通過處理所有的非關鍵更新來結束更新轉發表。節點400然後可以在步驟655中傳送一個或多個MPLS更新消息，並且方法600可以結束於步驟660。根據前面的討論，各種示例性實施例使得能夠減少網絡收斂時間。特別地，通過首先選擇性地更新特定的路由信息，並且觸發第二路由信息生成器，網絡節點可以減少其針對網絡中的所有節點收斂到普通路由狀態所花費的時間。根據前面的描述應當顯而易見的是，本發明的各種示例性實施例可以在硬體和/或固件中實現。此外，各種示例性實施例可以被實現為存儲在機器可讀存儲介質上的指令，所述指令可被至少一個處理器讀取並執行以便實施此處詳細描述的操作。機器可讀存儲介質可以包括用於以機器可讀形式存儲信息的任何機制，諸如個人或膝上型計算機、伺服器或其它計算設備。因而，機器可讀存儲介質可以包括只讀存儲器(ROM)、隨機訪問存儲器(RAM)、磁碟存儲介質、光存儲介質、快閃記憶體設備和類似的存儲介質。可以通過使用專用硬體以及能夠關聯合適的軟體執行處理步驟的硬體來提供附圖中所示的各種元件的功能，包括標記為「處理器」的任何功能框。當由處理器來提供時，可以由單個的專用處理器、由單個的共享處理器或者由多個單獨的處理器(其中一些可被共享)來提供所述功能。此外，對術語「處理器」或「控制器」的明確使用不應當被解釋為排他性地指代能夠執行軟體的硬體，而是可以非限制性地暗含包括數位訊號處理器(DSP)硬體、網絡處理器、專用集成電路(ASIC)、現場可編程門陣列(FPGA)、用於存儲軟體的只讀存儲器(ROM)、隨機訪問存儲器(RAM)和非易失性存儲器。還可以包括其它常規和/或定製硬體。類似地，附圖中所示的任何開關僅是概念性的。可以通過程序邏輯的操作、通過專用邏輯、通過程序控制與專用邏輯的交互或者甚至手動地實現其功能，可由實現者根據來自上下文的更多特定理解來選擇特定技術。本領域的技術人員應當認識到，此處的任何框圖代表了體現本發明原理的說明性電路的概念圖。類似地，應當認識到，任何流程圖表、流程圖、狀態轉移圖、偽代碼等代表了大體上可在機器可讀介質中表示並且因此可由計算機或處理器執行的各種過程，而不論是否明確示出了所述計算機或處理器。儘管已經特別參考其特定的示例性方面詳細描述了各種示例性實施例，但是應當理解，本發明能夠具有其它實施例，並且其細節能夠在各種顯而易見的方面進行修改。如本領域的技術人員顯而易見的，可以實現仍處於本發明的精神和範圍內的變型和修改。相應地，前面的公開、描述和附圖僅出於說明性目的，而絕不以任何方式來限制僅由權利要求限定的本發明。
權利要求
1.一種由網絡節點實施的減少針對網絡中的路由信息的更新時間的方法，所述方法包括: 在所述網絡節點處接收網絡狀態更新消息； 基於所述網絡狀態更新消息，更新路由信息的第一集合的第一部分； 在更新了所述路由信息的第一集合的第一部分之後，開始對路由信息的第二集合的第一更新；以及 在開始對所述路由信息的第二集合的更新之後，更新所述路由信息的第一集合的第二部分。
2.根據權利要求1的方法，其進一步包括: 在開始對所述路由信息的第二集合的更新之後，基於所述路由信息的第一集合的第一部分來更新所述路由信息的第二集合。
3.根據權利要求1的方法，其中，更新所述路由信息的第一集合的第一部分的步驟進一步包括: 確定所述網絡內的至 少一個其它節點，其中，針對所述至少一個其它節點的路由信息應當被用於更新所述路由信息的第二集合；以及 更新所述路由信息的第一集合中與所述至少一個其它節點相關聯的路由信息。
4.根據權利要求1的方法，其中，所述路由信息的第一集合的第一部分僅包括與所述網絡節點所屬的自治路由系統內的其它節點相對應的路由信息。
5.根據權利要求1的方法，其中，所述路由信息的第一集合的第一部分僅包括與所述網絡節點的相鄰節點相對應的路由信息，並且所述路由信息的第一集合的第二部分僅包括與距離所述網絡節點兩跳遠的節點相對應的路由信息，所述方法進一步包括: 在更新了所述路由信息的第一集合的第二部分之後，開始對所述路由信息的第二集合的第二更新；以及 在開始對所述路由信息的第二集合的第二更新之後，更新所述路由信息的第一集合的第三部分。
6.根據權利要求1的方法，其中，所述第一部分和所述第二部分中的至少一個僅包括與作為特定類型的設備的節點相對應的路由信息。
7.根據權利要求1的方法，其進一步包括: 在所述路由信息的第二集合的至少一部分被更新之後，基於所述路由信息的第二集合來構造路由信息更新消息；以及 將所述路由信息更新消息傳送到至少一個其它節點。
8.根據權利要求1的方法，其中，所述路由信息的第一集合包括IP路由信息，並且所述路由信息的第二集合包括以下中的至少一個=MPLS路徑信息和2層隧道協議(L2TP)路徑信肩、O
9.一種用於減少針對網絡中的路由信息的更新時間的網絡節點，所述網絡節點包括: 第一接口，其從另一節點接收分組； 網絡狀態更新消息標識器，其確定所述分組是網絡狀態更新消息； 第一路由信息存儲器，其存儲路由信息的第一集合； 第二路由信息存儲器，其存儲路由信息的第二集合；第一路由信息生成器，其: 基於所述網絡狀態更新消息，更新所述路由信息的第一集合的第一部分； 在更新了所述第一部分之後，指示所述第一部分已被更新；以及在指示所述第一部分已被更新之後，基於所述網絡狀態更新消息來更新所述路由信息的第一集合的第二部分；以及 第二路由信息生成器，其響應於指示所述第一部分已被更新，基於所述路由信息的第一集合的第一部分來更新所述第二路由信息。
10.根據權利要求9的網絡節點，其中，在更新所述路由信息的第一集合的第一部分時，所述第一路由信息生成器進一步: 確定所述網絡中的至少一個 關鍵節點，其中，與所述至少一個關鍵節點相關聯的路由信息將被用於更新所述路由信息的第二集合；以及 更新所述路由信息的第一集合中與所述至少一個關鍵節點相關聯的路由信息。
全文摘要
各種示例性實施例涉及一種方法及相關網絡節點，所述方法包括以下中的一個或多個在所述節點處接收網絡狀態更新消息；基於所述網絡狀態更新消息來更新路由信息的第一集合的第一部分；在更新了所述路由信息的第一集合的第一部分之後，開始對路由信息的第二集合的更新；以及在開始對所述路由信息的第二集合的更新之後，更新所述第一集合的第二部分。在各種備選實施例中，更新所述第一部分的步驟包括以下中的一個或多個確定所述網絡內的至少一個其它節點，其中，針對所述至少一個其它節點的路由信息應當被用於更新所述路由信息的第二集合；以及更新所述路由信息的第一集合中與所述至少一個其它節點相關聯的路由信息。
文檔編號H04L12/757GK103201987SQ201180053859
公開日2013年7月10日 申請日期2011年10月5日 優先權日2010年11月12日
發明者T·南達戈帕爾, K·M·雷熱, T·吳, W·亨德裡克斯 申請人:阿爾卡特朗訊公司