具有資料庫削減以及控制速率的狀態恢復的基於泛洪的路由協議的製作方法

2023-04-27 21:36:06 1

專利名稱：具有資料庫削減以及控制速率的狀態恢復的基於泛洪的路由協議的製作方法
技術領域：
本發明涉及計算機網絡，更具體地，涉及計算機網絡內所使用的路由協議。
背景技術：
計算機網絡是交換數據和共享資源的互連計算設備的集合。在基於數據包的網絡 (例如，網際網路)中，計算設備通過將數據分成稱作數據包的小塊來通信數據，其中通過網絡將數據包分別從源設備路由到目的設備。目的設備從數據包中提取數據，並且將數據組合成其原始形式。網絡內稱作路由器的一些設備使用路由協議來交換和收集描述網絡的拓撲信息。 這使得路由器構建其自己的網絡路由拓撲圖。在接收到輸入數據包時，路由器檢查數據包內的鍵控信息，並且根據收集到的拓撲信息轉發該數據包。許多路由協議使用基於泛洪的分配機制將拓撲信息通知給網絡內的路由器。這些路由協議通常基於要求每個路由器具有同步的路由拓撲信息的路由算法。即，基於泛洪的路由協議要求路由區域中的所有路由器存儲根據協議所分配的所有路由信息。以這種方式，路由器能夠選擇一致且無環路的路線。此外，路由信息的到處存在使得泛洪過程是可靠的、有效的且保證終止。在操作中，每個路由器通常保存內部鏈路狀態資料庫，並且以規定的間隔掃描整個資料庫以產生和輸出鏈路狀態消息，從而使資料庫同時存在於路由區域內的鄰居路由器。以這種方式，鏈路狀態在整個路由區域中傳播，並且完整地存儲在區域內的每個路由器中。例如，開放最短路徑優先(OSPF)和中間系統到中間系統(IS-IS)路由協議是使用鏈路狀態消息來確保他們的路由拓撲關於可利用的接口、量度(metric)以及與網絡鏈路相關聯的其他變量是同步的鏈路狀態協議。OSPF利用鏈路狀態通告(LSA)來交換信息， 而IS-IS使用鏈路狀態協議數據單元(LSP)來交換信息。產生鏈路狀態消息的路由器通常將鏈路狀態消息在整個網絡泛洪，使得每個其它的路由器接收到鏈路狀態消息。在路由器以點對點連接方式連接的網絡拓撲中，每個路由器將鏈路狀態消息泛洪到每個接口上可到達的路由器以確保同步。在利用多路訪問媒體的網絡(例如，乙太網)中，網絡內的路由器將鏈路狀態消息泛洪到所有其它的路由器。在另一情況下，接收路由器利用經由鏈路狀態消息接收到的鏈路信息構建並保存它們自己的網絡拓撲。在「htermediate system to Intermediate system routing information exchange protocol for use in conjunction with the Protocol for providing the Connectionless-mode Network Service(IS0 8473)」，ISO，IS0/IEC 10589 :2002 中具體說明了 IS-IS，其全部內容結合於此作為參考。近來，基於泛洪的路由協議已擴展到在路由器之間傳送用於輔助路由控制的重要信息。例如，除了攜帶拓撲信息之外，路由協議已經擴展到攜帶實施專用的信息，例如配置數據、硬體清單、附加性能信息以及其它信息。

發明內容
大體上，描述了一種提供用於以路由器對路由器為基礎削減鏈路狀態資料庫的技術的增強型基於泛洪的路由協議。該技術允許每個路由器獨立地且本地地確定其內部鏈路狀態資料庫內所需的鏈路狀態信息。每個路由器能夠丟棄鏈路狀態數據的任何部分而保留其它部分。該技術提供了實現基於泛洪方案的幫助和保證，然而一旦路由器已將狀態信息可靠地泛洪到它的鄰居路由器，那麼該技術允許每個路由器獨立地削減狀態信息。此外，本文中所描述的技術允許路由器將路由區域的完整狀態數據恢復 (refresh)給新添加至路由區域的、重新啟動的、或者以其他方式需要該區域的完整狀態的路由器。即，保證新的可利用的路由器經由基於泛洪的路由協議接收先前在路由區域內泛洪的所有鏈路狀態信息，而不管其鄰居路由器可能已從他們的鏈路狀態資料庫中削減鏈路狀態信息的哪些部分。以這種方式，新的可利用的路由器的任何鄰居路由器能夠將泛洪區域中聚集的狀態的全部傳遞給新的路由器，可以要求該新的路由器嚴格遵從某些基於泛洪的路由協議。新的可利用的路由器像其它路由器一樣能夠選擇性地確定要丟棄哪條狀態信肩、ο即使在當在整個網絡中恢復泛洪狀態以支持一個或多個新啟動的路由器時的瞬時基礎上，關於路由器的本地鏈路狀態資料庫所消耗的資源量(例如，內存佔用量)是有限的。例如，通過路由區域將整個狀態數據刷新給新的可利用的路由器可以以在臨時恢復和泛洪狀態數據時不會使路由器過載的控制速率的方式執行。即，在一些情況下，每個路由器能夠減少或甚至能夠臨時停止將路由區域的狀態數據恢復給新的可利用的路由器所需的基於泛洪的傳輸。通過實施這種機制，網絡內基於泛洪的路由協議的分配機制可實施為負責為新的可利用的路由器進行恢復的各個路由器最終控制狀態信息流經網絡的猝發速率和平均速率的「拉」模式。因此，根據本文中所描述的原理，基於泛洪的路由區域內的每個路由器可以單獨地控制恢復先前削減的鏈路狀態信息時所經歷的資源衝突，因此信息根據基於泛洪協議的同步要求可以最終被泛洪到新的可利用的路由器。關於諸如IS-IS的可擴展的基於泛洪的路由協議，可以以反向兼容的方式運用本文中描述的機制。在一個實施方式中，路由設備包括通過層二(U)通信媒體發送和接收數據包的網絡接口。路由設備包括耦接至網絡接口的控制單元，以及在控制單元的處理器上執行的基於泛洪的鏈路狀態路由協議。鏈路狀態路由協議通過層二(U)通信媒體與對等路由器建立鄰接關係。路由設備的資料庫包括存儲用於鏈路狀態路由協議的泛洪區域的多條鏈路狀態消息的條目，其中，資料庫中的至少一個條目存儲具有報頭部分和含有削減的鏈路狀態數據的淨荷的部分鏈路狀態消息。在另一實施方式中，一種方法包括根據基於泛洪的鏈路狀態路由協議通過層二 (L2)通信媒體在第一路由器與第二路由器之間建立鏈路狀態路由鄰接。該方法包括使用第一路由設備根據鏈路狀態路由協議接收鏈路狀態消息，其中，鏈路狀態消息包含用於鏈路狀態路由協議的泛洪區域的鏈路狀態數據；以及將鏈路狀態消息存儲到第一路由器的資料庫中。該方法還包括將鏈路狀態消息從第一路由器泛洪到泛洪區域中的至少第三路由器， 以及在從第三路由器接收到確認之後從存儲在資料庫內的鏈路狀態消息中至少削減部分鏈路狀態數據，而不是刪除整個鏈路狀態消息。在附圖和下面的描述中將闡明本發明的一個或多個實施方式的細節。本發明的其它特徵、目的以及優點將從描述和附圖以及從權利要求中變得顯而易見。


圖1是示出了根據本發明原理的一個或多個路由器利用增強型鏈路狀態協議的示例性網絡系統的框圖，其中該增強型鏈路狀態協議採用資料庫削減和速率控制恢復。圖2是示出了實施本文中所描述的技術的路由器的示例實施方式的框圖。圖3是示出了圖2的示例路由器的進一步細節的框圖。圖4是由圖2的路由器所保存的鏈路狀態資料庫內的條目的示例。圖5是示出了路由器保存和削減鏈路狀態資料庫的示例性操作的流程圖。圖6是示出了路由器響應於可以觸發其鏈路狀態資料庫內先前被削減的狀態數據的軟恢復的事件的示例性操作的流程圖。
具體實施例方式圖1是示出了根據本發明原理的支持增強型鏈路狀態協議的示例性泛洪區域10 的框圖。為了便於描述，將示例性泛洪區域10示為包括使用基礎層二(U)通信媒體的不同形式的兩個網絡12A、12B。例如，網絡12A使用其中網絡的所有L2通信被發送(S卩，被廣播)至耦接至網絡的所有路由器14A-14F的「多路訪問媒體」 15。廣播網絡的一個示例是乙太網，例如其中乙太網幀被通信至網絡的所有節點。與之相比，網絡12B使用點對點L2 通信媒體，例如光學鏈路16A-16D。在這種情況下，路由協議更新消息以點對點方式在鄰近路由器之間發送，並且由那些路由器處理和終止。在該示例中，路由器14E、14F利用由路由器提供的不同物理接口而物理存在於網絡12A和12B中。儘管在圖1中沒有示出，但是泛洪區域10可以包括其它網絡設備，例如交換機和集線器。此外，儘管在圖1中沒有示出， 但是路由器14中的每一個通常服務於各種用戶終端計算設備，例如可攜式計算機、臺式計算機、工作站、個人數字助理(PDA)及蜂窩電話。儘管為了示例性目的，描述為路由器，但是路由器14可以是除其他集成功能之外還結合有路由功能的其他網絡設備。為了便於說明本文所描述的技術，關於利用L2多路訪問媒體15和L2點對點媒體16的網絡12A、12B示出了泛洪區域10。關於本文中諸如L2和L3的層，指的是開放系統互連(OSI)模型中的相應層。具體地，L2指的是OSI模型內的數據鏈路層。數據鏈路層可以提供用以在網絡設備之間傳送數據以及檢測和儘可能地糾正可能發生在物理層中的錯誤的功能上和程序上的方法。L2通信媒體的示例是乙太網。L3指的是OSI模型內的網絡層。網絡層可以提供用以在保持由更高層要求的服務質量的同時經由一個或多個網絡將可變長度數據序列從源傳輸到目的地的功能上和程序上的方法。L3協議的示例是網際網路協議(IP)。關於OSI模型的更多信息可以在1980年4月出版的IEEE Transactionson Communications, vol. 28, no. 4 中由 Hubret Zimmermann 所著的題為 「OSI Reference Model-the ISO Model of Architecture for Open Systems Interconnection，，的IEEE出版物中找到，將其通過引證結合於此，好像在本文中所完整闡述似的。通常，路由器14使用基於泛洪的路由協議來將拓撲信息通告給彼此，並且使由每個路由器所保存的路由拓撲資料庫同步。如本文中所描述的，路由器14支持以本文所描述的方式已擴展的增強型鏈路狀態協議(LSP)，其中使用拓撲信息的接收路由器能夠利用增強型鏈路狀態協議控制通過發送路由器進行的基於泛洪的傳輸的平均速率和猝發速率。在一個示例中，定義能夠由在泛洪區域10內已經使用的各種鏈路狀態消息攜帶的新的、不透明類型、長度、值(TLV)。TLV可以包括用於攜帶允許路由器控制另一路由器將信息泛洪給鄰接的平均速率的傳輸信用(transmission credit)的第一欄位。此外，TLV可以包括用於攜帶發送路由器在每個連續數據包傳輸之間必須延遲的最小時間間隔(例如，微秒)的第二欄位。這允許接收路由器控制發送路由器內的策略(Policer)，從而以非常低的反向帶寬消耗控制數據包猝發速率。通過實施這種機制，用於泛洪區域10內的基於泛洪的路由協議的鏈路狀態消息可被實施為其中各個接收路由器14使用拓撲信息的速率最終控制通過網絡系統的數據流的「拉」模式。此外，在2010年8月19日提交的由Katz等所著的題為 「FLOODING-BASED ROUTING PROTOCOL HAVING AVERAGE-RATE AND BURS T-RATE CONTROL」 的美國專利申請第61/375，166號中可以找到增強型鏈路狀態路由協議的示例性細節，其全部內容結合於此作為參考。根據基於泛洪的協議，每個路由器14均保存內部鏈路狀態資料庫且輸出鏈路狀態消息以在整個泛洪區域10內傳播全部鏈路狀態。例如，泛洪區域10內的路由器14通常首先交換鏈路狀態消息以建立鄰接關係。例如，路由器14可以交換IS-IS HELLO協議數據單元(PDU)以與其它路由器建立鄰接關係。此外，路由器14利用基於泛洪的鏈路狀態消息以將由每個路由器所保存的路由拓撲資料庫同步。每條鏈路狀態消息通常在網絡上被定期地恢復，並且通過接收路由器確認。例如，路由器14可以利用用於使它們的路由拓撲資料庫同步的周期IS-IS鏈路狀態PDU以及利用部分序列號數據包數據單元PDU (PSNP)和完整序列號PDU(CSNP)以確認收到信息。作為一個示例，網絡12B內的路由器141通常與作為對等路由器的路由器14G和 14H建立分離的鄰接。路由器14G-14I通過鏈路16定期地交換鏈路狀態消息以確保路由器保存同步的鏈路狀態資料庫。例如，路由器14G、14H定期地向泛洪區域輸出鏈路狀態消息 18。在接收到鏈路狀態消息18時，路由器141以諸如IS-IS PSNP或CSNP的確認鏈路狀態消息20做出響應。當在廣播網絡12A內分布鏈路狀態數據時，路由器14A-14F通過諸如交換式乙太網媒體的多路訪問媒體15將組播鏈路狀態消息泛洪。繼續上面的示例，響應於從路由器14G接收到的鏈路狀態消息，路由器14E可以在多路訪問媒體15上輸出一條或多條組播鏈路狀態消息22以將鏈路狀態數據泛洪到多路訪問媒體，並且從路由器14A-14D中的每一個接收確認24。在一個示例中，路由器14E定期地向多路訪問媒體15輸出鏈路狀態消息22作為IS-IS鏈路狀態PDU，並且以IS-IS CSNP形式接收來自路由器14A-14D中的每一個的確認24，以確認收到信息。這種相互作用繼續，使得路由器14被同步為所有的路由器已經被通知到整個泛洪區域10的完整狀態數據並且已將完整狀態數據通知給他們的鄰居路由器。在該處理期間，每個路由器14獨立地且本地地確定需要保存在其內部鏈路狀態資料庫內的鏈路狀態信息。根據各個確定，一旦路由器已可靠地將狀態信息泛洪到其鄰居路由器，那麼路由器14 從其內部鏈路狀態資料庫獨立地削減某些鏈路狀態信息。以這種方式，內部鏈路狀態資料庫可以具有存儲完整鏈路狀態消息和部分鏈路狀態消息的資料庫條目，其中在部分鏈路狀態消息中，消息的鏈路狀態數據的一些或全部已被削減。此外，該技術允許路由器14將用於路由區域的全部狀態數據恢復給新加入路由區域的、重新啟動的、或者以其他方式需要泛洪區域10的完整狀態的路由器。例如，該技術保證新的可利用的路由器14J經由基於泛洪的路由協議接收到先前在泛洪區域10內泛洪的所有鏈路狀態信息，而不管其鄰居路由器141已從它的鏈路狀態資料庫削減了鏈路狀態消息的哪部分。即，鄰居路由器141能夠將傳遞泛洪區域10中的全部聚集狀態(aggregate state)的鏈路狀態消息17輸出到新的路由器14J，可以要求新的路由器14J嚴格遵從基於泛洪的路由協議。然後，新的可利用的路由器14J同其它路由器14 一樣能夠選擇性地確定要丟棄哪條狀態信息。例如，在檢測到新的可利用的路由器14J或需要路由器141向路由器14J泛洪鏈路狀態數據的另一事件時，路由器141發起所有「所需的」部分鏈路狀態消息的檢索，使得可以從其它鄰居路由器檢索到相應的完整鏈路狀態消息。此外，在檢索削減的鏈路狀態消息期間，路由器141可以利用鏈路狀態協議的確認機制以從泛洪區域的其它路由器中選擇性地檢索削減的鏈路狀態消息。例如，路由器141可以整理(formulate)並以一條或多條IS-IS PSNP的形式輸出作為資料庫同步消息的確認消息20，其中資料庫同步消息指出用於所需的部分鏈路狀態消息的標識符。在該示例中，路由器141形成PSNP以為所需的鏈路狀態消息指定低於當前序列號的序列號，其中所需的鏈路狀態消息在被鄰近的路由器 14G、14H接收到時，通過鄰近的路由器14G、14H觸發鏈路狀態消息的再泛洪。例如，路由器 141可以為所需的鏈路狀態消息將PSNP中的序列號設定為零。作為另一示例，路由器141 可以以CSNP的形式輸出描述路由器141的鏈路狀態資料庫的全部內容的確認消息20。在這種情況下，路由器141從CSNP去除鏈路狀態消息的條目以指示路由器14G和14H將丟失的鏈路狀態消息再泛洪到路由器14J。因此，確認消息20被用以觸發對先前接收到的但是是削減的鏈路狀態消息的另外的副本的獲取，而非僅用作用於先前接收的鏈路狀態消息的確認消息。如果路由器14G、14H具有類似削減的所需的鏈路狀態消息，則路由器可以以確認消息的形式再次輸出資料庫同步消息以從它們的鄰居路由器請求任何所需的鏈路狀態消息。如果泛洪區域10內的任一路由器通過具有完整的鏈路狀態資料庫或不具有削減的鏈路狀態消息而具有所需的鏈路狀態消息，那麼該路由器通過泛洪區域將所需的鏈路狀態消息泛洪回到路由器141以進行處理和向新的可利用的路由器14J泛洪。在最壞的情況下， 可以通過整個路由區域10轉發用於恢復鏈路狀態消息的請求直到請求到達鏈路狀態消息的發起者，其通過區域10再將請求的鏈路狀態消息泛洪回，並且恢復處理終止，在恢復處理終止的點處泛洪區域內的中間路由器可以再次削減鏈路狀態消息。在一些方面，可以以控制速率的方式執行將全部狀態數據通過泛洪區域10恢復給新的可利用的路由器14J，該方式在路由器14A-14I臨時恢復或泛洪狀態數據時不會使路由器14A-14I過載。即，在一些情況下，每個路由器能夠減少或甚至臨時停止正在發送以將路由區域的狀態數據恢復給新的可利用的路由器的基於泛洪的傳輸。以這種方式，即使在整個泛洪區域10恢復泛洪狀態以支持新的可利用的路由器14J時的瞬時基礎上，關於每個路由器14由它的部分鏈路狀態資料庫消耗的資源量(例如，內存佔用量)是有限的。通過實施這種機制，用於泛洪區域10內的基於泛洪的路由協議的分配機制可以實施為其中負責為新的可利用的路由器14J進行恢復的各個路由器14A-14I最終控制狀態信息流經網絡的猝發速率和平均速率的「拉」模式。因此，根據本文中所描述的原理，基於泛洪的路由區域10內的每個路由器14A-14I可以單獨地控制恢復先前削減的鏈路狀態信息時所經歷的資源衝突，因此信息可以根據基於泛洪協議的同步要求被最終泛洪到新的可利用的路由器 14J。圖2是示出了根據本發明原理構造的示例路由器104的框圖。路由器104可以例如代表圖1的路由器14的任何一個。在圖2示出的示例性實施方式中，路由器104包括使用網絡鏈路112和113發送和接收數據包的一個或多個接口卡(IFC) 106。接口卡106通常經由多個物理接口埠耦接至網絡鏈路112、113。通常，路由器104接收來自網絡鏈路 112的入站數據包，確定所接收到的數據包的目的地，並且根據目的地通過網絡鏈路113輸出數據包。以這種方式，網絡鏈路112、113提供用於傳輸數據包的L2通信媒體。網絡鏈路 112、113中的任何一個可以是諸如乙太網的多路訪問媒體或諸如光學連接的點對點媒體。通常，路由器104具有提供控制平面103和數據平面105的控制單元108。控制平面103主要負責保存鏈路狀態資料庫(DB)IlO以反映泛洪區域的當前鏈路狀態數據。例如，控制單元108為鏈路狀態路由協議112的執行提供操作環境，其中路由器104使用鏈路狀態路由協議112來與對等路由器進行通信以及定期地更新鏈路狀態DB 110以準確地反映路由器104運作所在的泛洪區域(例如，圖1的泛洪區域10)的鏈路狀態數據。示例性鏈路狀態路由協議包括路由和標籤交換協議，例如IS-IS和0SPF。在一個示例中，鏈路狀態資料庫110被構造為存儲鏈路狀態消息(例如，OSPF LSA 或ISIS PDU)以及例如以每條鏈路狀態消息為基礎提供訪問。在諸如OSPF的一些協議中， 鏈路狀態路由協議112可以發起資料庫交換過程以交換各條鏈路狀態消息。在諸如IS-IS 的其它示例中，鏈路狀態路由協議112可以通過輸出將鏈路狀態資料庫110內的每條鏈路狀態消息列出的CSNP來將其完整的鏈路狀態DB 110定期地描述給它的鄰居。在這種情況下，鏈路狀態路由協議112可以整理CSPN以包括已被削減且當前不需要被恢復的部分鏈路狀態消息的標識符，從而防止鏈路狀態消息被其它路由器再泛洪。然而，鏈路狀態路由協議 112可以整理CSPN以包括已被削減且當前需要被恢復的部分鏈路狀態消息的標識符，從而通過泛洪區域中的一個或多個其它路由器觸發鏈路狀態消息的再泛洪。鏈路狀態路由協議112可以保存鏈路狀態DB 110以存儲感興趣的狀態數據的完整鏈路狀態消息和已削減鏈路狀態的全部或部分的削減的鏈路狀態消息。在另一情況下， 鏈路狀態路由協議112操作鏈路狀態DB以存儲在泛洪區域內泛洪的每條鏈路狀態消息的條目。對於完整的鏈路狀態消息，每條對應的條目可以存儲鏈路狀態報頭信息和來自消息的淨荷的狀態數據。對於削減的鏈路狀態消息，在鏈路狀態消息已泛洪到路由器的所有鄰居之後，鏈路狀態路由協議112指示鏈路狀態DB 110削減(例如，刪除)淨荷數據的全部或部分。鏈路狀態路由協議112將條目標記為存儲不完整的鏈路狀態數據，並且該消息被稱為「部分」鏈路狀態消息。鏈路狀態路由協議112可以應用對由管理員或部署系統指定
11的策略進行定義的削減規則115，以識別鏈路狀態DB 110內被選擇為要削減的鏈路狀態消息。削減規則115可以指定用於匹配的條件或布爾邏輯算符，例如，鏈路狀態消息的報頭信息的一部分、鏈路狀態消息的淨荷內攜帶的鏈路狀態數據的一部分、接收鏈路狀態消息所經由的接口或鏈路、路由器104的當前資源容量(例如，存儲量或可利用的存儲空間)的閾值或其它標準。根據鏈路狀態DB 110，轉發元件114保存與網絡目的地相關聯的轉發信息116或具有特定下一跳和路由器108的輸出接口卡106的對應接口埠的其它鍵控信息。控制平面103通常處理鏈路狀態DB 110以執行路徑選擇，並且基於所選擇的路徑生成轉發信息 116。以這種方式，轉發信息可以編入數據平面105中。控制平面103可以以表格、列表、根樹或其它數據結構的形式生成轉發信息116。美國專利第7，184，437號提供了關於使用用於路由方案的根樹的路由器的示例性實施方式的細節，其全部內容結合於此作為參考。當轉發臨時數據包時，轉發元件114基於數據包的報頭內的鍵控信息檢查轉發信息116以最終選擇數據包要轉發至的下一跳和輸出接口。基於選擇，轉發元件114可以將數據包直接輸出到輸出接口 113，或在高端路由器的多級交換結構的情況下，可以將數據包轉發至下一級以交換至正確的輸出接口。題為「MULTI-CHASSIS ROUTER WITH MULTIPLEXED OPTICAL INTERCONNECTS」的美國專利申請第2008/0044181號描述了多級交換結構(例如， 3級Clos交換結構)用作高端轉發平面來在多機架路由器的多個路由節點之間中繼數據包的多機架路由器。美國專利申請第2008/0044181號的全部內容結合於此作為參考。該公開的技術不限於這種結構。在其它實施方式中，可以以各種方式構造路由器104。在一個實施方式中，例如，控制平面103和數據平面105的全部或部分可以複製和直接結合在IFC 106 內。如本文中所描述的，鏈路狀態路由協議112是已經擴展為提供速率被控制的狀態恢復的基於泛洪的通信協議。控制平面103包括用於存儲由鏈路狀態路由協議112所保存的各個路由鄰接的鏈路狀態消息的輸出隊列120。例如，輸出隊列120A可以存儲第一路由鄰接的出站鏈路狀態消息，而輸出隊列120B可以存儲第二路由鄰接的出站鏈路狀態消息。 當使輸出鏈路狀態消息離隊以經由轉發元件114傳輸時，調度器(scheduler) 122基於猝發速率流控制(例如，最小數據包間隔)以及在經由點對點通信媒體鄰接是可到達的情況下為鄰接指定的平均速率流控制(例如，信用)來控制鏈路狀態消息的傳輸。數據平面105的轉發元件114將入站鏈路狀態消息117通信至入站隊列119以投遞至鏈路狀態路由協議112。鏈路狀態路由協議112處理入站鏈路狀態消息以通過產生鏈路狀態消息並經由輸出隊列120將鏈路狀態消息傳輸來向其他鄰居路由器泛洪每條入站鏈路狀態消息。在從所有鄰居接收到給定鏈路狀態消息的確認消息時，鏈路狀態路由協議112應用削減規則以確定鏈路狀態消息是否要如本文中所述的從鏈路狀態DB 110中削減。在處理入站鏈路狀態消息時，鏈路狀態路由協議112還更新鄰接數據112以保存與另一路由器建立的每個鄰接的條目。例如，鄰接數據111內的每個條目指出鄰接的標識符(例如，IP位址)、由其它路由器為鄰接分配的當前信用、由其它路由器為鄰接設定的最小數據包間隔以及可到達鄰接所經由的L2通信媒體的類型(即，點對點或多路訪問)。鏈路狀態路由協議112在接收到給定鄰接的入站鏈路狀態消息(例如，IS-IS HELL0、PSNP或CSNP)時更新該鄰接的猝發速率和平均速率流控制數據。在這種情況下，鏈路狀態路由協議 112分析由唯一 TLV攜帶的信用分配和當前的最小數據包間隔，並且更新鄰接數據111，從而調節調度器122傳輸該鄰接的輸出鏈路狀態消息的速率。可以在鄰接數據111內對通過相同的L2通信媒體(S卩，多路訪問媒體)可達到的鄰接做標記以對鄰接記錄進行分組。當該組的任一輸出鏈路狀態消息離隊時，調度器122 基於由任一鄰接指定的最長的最小時間間隔控制傳輸，而不管用於鄰接的任何當前傳輸信用。調度器122保持用於每個鄰接或多路訪問媒體情況下鄰接組的計時器124，並且在已滿足給定鄰接的最小數據包間隔時僅輸出該鄰接的鏈路狀態消息。圖3是更詳細地示出鏈路狀態路由協議112的示例實施方式的框圖。在該示例中，鏈路狀態路由協議112包括狀態管理器130，其根據規定的狀態機運作來處理鏈路狀態消息，並且根據鏈路狀態協議的要求定期地使鏈路狀態DB 110同步到鄰居路由器。此外， 如圖3所示，狀態管理器130包括削減模塊132，其在鏈路狀態消息已泛洪到路由器的所有鄰居之後削減條目的淨荷數據的全部或部分。在削減之後，鏈路狀態路由協議112將條目標記為存儲不完整的鏈路狀態數據。削減模塊132應用對由管理員或部署系統指定的策略進行定義的削減規則115， 以識別鏈路狀態DB 110內被選擇為進行削減的鏈路狀態消息。削減規則115可以指定條件或布爾邏輯算符，以匹配鏈路狀態消息的報頭信息的一部分、鏈路狀態消息的淨荷內攜帶的鏈路狀態數據的一部分、接收鏈路狀態消息所經由的接口或鏈路、路由器104的當前資源容量(例如，存儲量或可利用的存儲空間)的閾值或其它標準。通常，狀態管理器130保存鏈路狀態資料庫110以存儲用於泛洪區域的全部狀態的每條鏈路狀態消息的條目。即，在接收到新的鏈路狀態消息時，狀態管理器130可以存儲包括報頭信息以及來自消息的淨荷的狀態數據的完整鏈路狀態消息。一旦新的鏈路狀態信息被泛洪到鄰居路由器且被確認，則削減模塊132應用削減規則115(例如，根據指定的時間間隔)，並且可以從鏈路狀態資料庫110中削減鏈路狀態消息。例如，削減模塊132可以從條目中刪除淨荷數據，而不是從鏈路狀態消息的條目中去除報頭信息的一些或全部，而留下的可被稱為「部分」鏈路狀態消息。以這種方式，泛洪區域的狀態數據的完整集合內的每條鏈路狀態消息的條目可以保留在鏈路狀態資料庫110內，但是與鏈路狀態資料庫相關聯的存儲量和存儲需求會減少。此外，在重建模塊134需要恢復泛洪區域的全部狀態數據的情況下(例如，以傳輸至新的可利用的路由器)，重建模塊134通過向鄰居路由器請求鏈路狀態消息來重建鏈路狀態資料庫110內不完整的鏈路狀態消息的狀態數據。以這種方式，新的可利用的路由器能夠經由基於泛洪的路由協議接收之前在路由區域內泛洪的所有鏈路狀態信息，而不管鏈路狀態信息的哪部分可能已經從鏈路狀態資料庫110中削減。如以下詳細描述的，在一個實施方式中，重建模塊134利用提取定時器136來觸發從泛洪區域內的鄰居路由器提取當前需要的任何不完整的(即，部分)鏈路狀態信息。例如，如果在泛洪區域內發生任何需要路由器104將鏈路狀態消息發送到泛洪區域內的另一路由器的動作，則重建模塊134確定鏈路狀態消息是否是鏈路狀態資料庫110內的當前部分鏈路狀態消息(即，經削減的)。如果是，那麼狀態管理器130設定標誌(例如，「需要」 位)來將部分鏈路狀態消息標記為已被削減的鏈路狀態而需要被恢復。在提取計時器136終止時，重建模塊134觸發所有「所需的」部分鏈路狀態消息的檢索，使得可以從其它鄰居路由器檢索到相應的完整鏈路狀態消息。如果那些路由器具有類似削減的所需鏈路狀態消息，那麼路由器再向它們的鄰居路由器請求鏈路狀態消息。如果任何鄰居通過具有完整的鏈路狀態資料庫或不具有削減的鏈路狀態消息而具有所需的鏈路狀態消息，那麼路由器通過泛洪區域將所需的鏈路狀態消息泛洪回到路由器104，以進行處理並潛在地泛洪到新的可利用的路由器。在該重建和恢復過程中，泛洪區域內的路由器根據本文中所指定的猝發速率和平均速率控制運作。例如，向路由器104發送鏈路狀態消息的任何路由器根據由路由器104 指定的猝發速率和平均速率流控制設定傳輸這些鏈路狀態消息。此外，路由器104根據由那些路由器中的每一個指定的猝發速率和平均速率流控制設定再將已恢復的鏈路狀態消息泛洪到鄰居路由器。該處理繼續直到已恢復的鏈路狀態消息到達新的可利用的路由器。 以這種方式，該技術允許基於泛洪的路由協議通信機制恢復鏈路狀態數據，而作為其中接收數據的路由器對其通過路由鄰接接收數據的速率具有良好的微控制的拉模式。結果，即使在整個泛洪區域內恢復泛洪狀態以支持一個或多個新開啟的路由器時的瞬時基礎上，也可以限制關於路由器的部分鏈路狀態資料庫所消耗的資源量(例如，內存佔用量)。削減量 (部分和整體)越大，為這種事件所產生的通信量越高。在一些情況下，當首先是路由器變得可利用時，對於要被初始化的路由器，這是相對昂貴的操作，這是因為每條鏈路狀態消息需要儘可能地從發起者恢復。然而，這與泛洪影響完全停留於新路由器的直接鄰居以及在每個路由器中存儲整個泛洪區域的完整鏈路狀態數據的潛在的巨大負擔的傳統基於泛洪的協議IS-IS的情況是有差異的。圖4是鏈路狀態資料庫110內的單條鏈路狀態消息的條目140的示例。在該示例中，存儲在資料庫中的鏈路狀態消息被示為具有報頭145以及鏈路狀態數據的淨荷154(可選的)的IS-IS鏈路狀態協議數據單元(PDU)。報頭145包括唯一識別泛洪區域內的鏈路狀態消息的鏈路狀態PDU(LSP)標識符 142。可以將LSP ID 142的形式編排成指示鏈路狀態消息的擁有者(即，發起路由器)以及鏈路狀態消息本身。此外，報頭145包括序列號143、剩餘使用期144、SRM標誌146、需要位148、不完整位150以及校驗和152。剩餘使用期144表示開始於所定義的最大使用期(例如，1200 秒)而消耗至零的鏈路狀態消息的使用期，，在零點上不再認為淨荷是泛洪區域的當前鏈路狀態，並且可以從鏈路狀態資料庫中完全去除。序列號143表示鏈路狀態消息的當前版本。例如，發信路由器通常用序列號標記鏈路狀態消息以將老副本與新副本區分開。路由器無論何時產生新的鏈路狀態消息來替代過時的版本，鏈路狀態消息的序列號都增加一。現有鏈路狀態消息的新版本通常在路由器的局部環境中發生的變化需要報告給泛洪區域的其他部分時發布。IS-IS路由器定期地發布具有與先前鏈路狀態消息相同的信息的新的鏈路狀態消息以在它終止前恢復鏈路狀態消息。發送路由消息(SRM)標誌146是路由器104為鏈路狀態資料庫110內的每條鏈路狀態消息定義的內部標誌，其中對於每條鏈路狀態消息，條目包含用於路由器的每個接口的SRM標誌。當鏈路狀態消息需要在特定鏈路上發送時，狀態管理器130設定用於那個鏈路的接口的相應SRM標誌146。在開始鏈路狀態資料庫110的下一掃描時，具有一個或多個 SRM標誌146的任何鏈路狀態消息的條目觸發狀態管理器130整理相應的鏈路狀態消息並在設定有SRM標誌的每條鏈路上輸出該相應的鏈路狀態消息。發送序列號(SSN)標誌147是用在資料庫同步過程中的附加內部標誌。如同SRM 標誌146 —樣，每條鏈路狀態消息對於路由器的IS-IS接口中的每一個具有一個SSN標誌。 當設定SSN標誌時，其表示鏈路狀態消息要描述在經由關聯的接口所發送的PSNP中以執行與用於特定的鏈路狀態消息的鏈路狀態請求類似的功能。當發送描述鏈路狀態消息的PSNP 時清除SSN標誌。由削減模塊132控制不完整位150以指示淨荷IM的全部或部分是否已從資料庫條目中清除並去除。由重建模塊134控制需要位148以響應於需要恢復泛洪區域的狀態數據的事件指示當前是否需要用於部分鏈路狀態消息的完整狀態數據。校驗和152用於保持存儲和泛洪期間鏈路狀態消息的完整性。校驗和的值由發信路由器插入到鏈路狀態消息中，並且由接收副本的任一路由器驗證。如果校驗和與為鏈路狀態消息計算的值不匹配，即，鏈路狀態消息未通過校驗和的確認，那麼認為鏈路狀態消息被破壞。淨荷IM表示由鏈路狀態消息攜帶的狀態數據，並且可以根據削減規則115削減淨荷的全部或部分。淨荷巧4通常採用一個或多個TLV的形式，每個TLV均可以獨立地從資料庫條目中被整體削減或部分削減。儘管用於示例性目的而沒有示出，但是條目140可以存儲由鏈路狀態消息攜帶的或與之相關聯的其它信息。圖5是示出了路由器在從用於基於泛洪的路由協議的其內部鏈路狀態資料庫處理和削減鏈路狀態消息時的示例性操作的流程圖。儘管關於路由器104進行了描述，但是可以在利用基於泛洪的協議參與狀態數據的交換的任何路由器或其它設備(例如，圖1的路由器14中的任一個)中可以實施該示例性操作。首先，路由器104與其鄰居路由器中的每一個交換會話建立消息以建立用於基於泛洪的路由協議的相應鄰接(160)。例如，路由器可以交換IS-ISHELLO PDU以創建鄰接。 這時，路由器可以在其傳輸的IS-IS HELLO PDU內包括TLV以指定初始的猝發速率和平均速率流控制參數，以在發送其攜帶數據的路由協議數據包時被其它路由器使用。會話建立消息中的猝發速率和平均速率控制信息用於建立用於控制初始傳輸和來自鄰居的狀態數據的恢復的初始信用和數據包間隔。在建立基於泛洪的路由協議鄰接之後，路由器利用泛洪的鏈路狀態消息定期地同步它們的路由拓撲資料庫。在該處理期間，路由器104定期地整理一個或多個鏈路狀態消息(諸如IS-IS鏈路狀態PDU)並將其排隊以進行傳輸、以將鏈路狀態消息恢復給其它路由器(16 。這時，路由器104根據從其它路由器接收到的當期猝發速率和平均速率流控制參數以控制速率的方式傳輸出站鏈路狀態消息。響應，路由器104接收確認接收到被泛洪至鄰接的鏈路狀態更新消息的鏈路狀態確認消息(166)。例如，路由器104可以接收部分序列號PDU或完整序列號PDU以確認信息的接收。這時，鏈路狀態路由協議112分析每個PDU以提取傳達當前最小數據包間隔和由其它路由器(即，從其接收特定確認的路由器)分配給鄰接的任何信用的TLV。以這種方11/12 頁
式，該技術允許基於泛洪的路由協議通信機制更可能地運作為其中接收數據的路由器對其通過路由鄰接接收數據的速率具有良好的微控制的基於拉的模式。在接收到給定鏈路狀態消息條目140的所有確認(168的是)時，削減模塊132應用削減規則115以確定是否要從鏈路狀態DB 110中削減鏈路狀態消息的淨荷154的全部或部分(170)。如果是，那麼削減模塊132根據削減規則115去除淨荷154的全部或部分 (174)。圖6是示出了路由器104響應於對請求路由器104恢復鏈路狀態資料庫110內先前削減的鏈路狀態數據以將鏈路狀態數據的整個和完整版本泛洪給泛洪區域(180)的事件進行的識別的示例性操作的流程圖。作為這種事件的一個示例，狀態管理器130可以確定已經從另一路由器接收到入站LSP，其中入站LSP與鏈路狀態資料庫110內的條目140匹配，但是具有比條目內存儲的序列號更舊的序列號。類似地，狀態管理器130可以確定已接收到用於LSP的PSNP確認，但是指出用於LSP的序列號比鏈路狀態資料庫110中的序列號更舊。作為另一示例，狀態管理器可以確定已接收到用於鄰接的CNSP，但是指定的LSP沒有列在CNSP中。在這些情況的每一種情況下，狀態管理器130確定鏈路狀態消息的當前版本需要被泛洪至觸發事件的接口(180的是)。作為觸發事件的另一示例，狀態管理器130可以確定在接口上檢測到新的點對點鄰接並且泛洪區域的所有狀態數據(即，所有LSP)需要被泛洪至鄰接。響應於觸發事件，狀態管理器130確定需要被泛洪的每個LSP是否如鏈路狀態資料庫110的相應條目140內的不完整位150的狀態所指示的當前已被削減(181)。如果要被泛洪的LSP已被削減而使得當前僅存儲部分鏈路狀態消息，那麼重建模塊134發起用於恢復鏈路狀態消息的資料庫同步消息的輸出(183)，而不是設定SRM標誌146來觸發鏈路狀態消息的輸出。例如，重建模塊可以將條目140內的序列號143設定為零，設定需要位148， 為該LSP在所有接口上設定SSN標誌147，並且啟動提取計時器136 (182)。SSN標誌147的設定可以使狀態機130整理並輸出一個或多個用於部分鏈路狀態消息的PSNP，其中PSNP為 LSP指定序列號零。作為另一示例，通過整理和輸出已去除用於部分鏈路狀態消息的條目的 CSNP, SSN標誌147的設定可以使狀態機130在下一資料庫掃描期間以不同的方式運作。在接收到入站鏈路狀態消息(184)時，路由器104根據鏈路狀態協議處理每條消息以更新鏈路狀態資料庫110。如果鏈路狀態消息包括之前未被路由器104注意到的鏈路狀態消息標識符142，那麼狀態管理器130在鏈路狀態資料庫110內創建新的條目140，並且存儲泛洪的消息。然而，如果入站鏈路狀態消息是所需要的LSP的副本，並且已經響應於由路由器104發送的一個PSNP被接收，那麼接收到的LSP的LSP標識符與存儲部分LSP的現有條目不匹配，並且接收到的鏈路狀態消息的序列號超過條目的已被設定為零的序列號 143。結果，狀態管理器130更新條目的淨荷154以包括所提取的鏈路狀態消息的狀態數據的完整版本。這時，狀態管理器130重置條目的需要位148以指示鏈路狀態信息已被接收並且重置不完整的位150以指示條目現在存儲LSP的狀態數據的全部。狀態管理器130設定用於新創建的或新更新的條目的SRM標誌146以在下一資料庫掃描期間觸發鏈路狀態消息的泛洪(186)。這時，路由器104再次根據與特定鄰接相關聯的當前猝發速率和平均速率流控制參數以控制速率的方式傳輸出站鏈路狀態消息。在提取定時器136終止的情況下(187)，重建模塊134掃描鏈路狀態拓撲資料庫
16110以識別仍設定有需要位148的部分LSP (189)。如果附加的部分LSP存在且被指定為需要進行恢復(191)，那麼重建模塊重新啟動提取計時器(193)，並且設定SSN標誌147以觸發另一批PSNP的輸出以請求所需的鏈路狀態消息(183)。提取定時器136可以被設定為足夠高的值以避免不必要的PSNP產生，從而為穿過網絡並返回的潛在的最大距離行程留出充足的時間，但是足夠低使得在丟失PSNP的情況下相當快地復原。該處理繼續直到所有所需的但被削減的鏈路狀態消息已由鏈路狀態路由協議112 接收，並且已為需要的鄰接恢復(191的否)。以這種方式，所有「所需的」部分鏈路狀態消息將被其它鄰近的路由器檢索到的相應的完整鏈路狀態消息替代。如果那些路由器具有類似被削減的所需的鏈路狀態消息，那麼路由器再向它們的鄰居路由器請求鏈路狀態消息。一旦已接收到所需要的鏈路狀態消息，向鄰接泛洪並已被確認，則削減模塊132會再次如參照圖5的流程圖所描述的削減鏈路狀態消息。已經描述了本發明的多個實施方式。這些以及其它實施方式落在所附權利要求的範圍內。
權利要求
1.一種方法，包括根據基於泛洪的鏈路狀態路由協議通過層二(U)通信媒體在第一路由器與第二路由器之間建立鏈路狀態路由鄰接；通過所述第一路由器根據所述鏈路狀態路由協議接收鏈路狀態消息，其中所述鏈路狀態消息包含用於所述鏈路狀態路由協議的泛洪區域的鏈路狀態數據；將所述鏈路狀態消息存儲到所述第一路由器的資料庫中；將所述鏈路狀態消息從所述第一路由器泛洪到所述泛洪區域中的至少第三路由器；以及在從所述第三路由器接收到確認之後，從存儲在所述資料庫內的所述鏈路狀態消息削減至少部分所述鏈路狀態數據，而不是刪除整個所述鏈路狀態消息。
2.根據權利要求1所述的方法，還包括識別要求所述第一路由器將含有削減的鏈路狀態數據的所述鏈路狀態消息泛洪到所述泛洪區域的事件；從所述第一路由器輸出資料庫同步消息，以指示所述第二路由器將所述鏈路狀態消息再泛洪到所述第一路由器；從所述第二路由器接收所述鏈路狀態消息的副本，其中所述鏈路狀態消息的所述副本包含所述鏈路狀態數據；以及將所述鏈路狀態消息的所述副本從所述第一路由器泛洪到所述泛洪區域。
3.根據權利要求2所述的方法，還包括在接收到所述鏈路狀態消息的所述副本之後，更新所述資料庫以存儲複製的所述鏈路狀態消息；以及在接收到所述鏈路狀態消息的所述副本的確認之後，從存儲在所述資料庫內的所述鏈路狀態消息的所述副本削減至少部分所述鏈路狀態數據。
4.根據權利要求2所述的方法，其中，輸出資料庫同步消息包括輸出指定所述鏈路狀態消息的部分序列號數據包數據單元(PSNP)，其中所述第一路由器形成PNSP以為所述鏈路狀態消息指定低於與所述鏈路狀態消息相關聯的當前序列號的序列號，以指示所述第二路由器將所述鏈路狀態消息再泛洪到所述第一路由器。
5.根據權利要求2所述的方法，其中，輸出資料庫同步消息包括向所述第二路由器輸出描述所述資料庫的全部內容的完整序列號數據包數據單元(CSNP)，其中，所述第一路由器從CSNP去除所述鏈路狀態消息的條目以指示所述第二路由器將所述鏈路狀態消息再泛洪到所述第一路由器。
6.根據權利要求3所述的方法，其中，將所述鏈路狀態消息存儲到所述第一路由器的資料庫包括創建條目以存儲所述鏈路狀態消息的報頭的至少一部分和包含所述鏈路狀態數據的所述鏈路狀態消息的淨荷， 以及其中，從存儲在所述資料庫內的所述鏈路狀態消息削減至少部分所述鏈路狀態數據包括從所述鏈路狀態資料庫內的所述條目去除所述淨荷的至少部分所述鏈路狀態數據，而不是從所述條目中刪除所述報頭。
7.根據權利要求6所述的方法，其中，更新所述資料庫以存儲複製的所述鏈路狀態消息包括將來自所述鏈路狀態消息的所述副本的所述鏈路狀態數據重寫入存儲在所述資料庫的所述條目內的所述淨荷。
8.根據權利要求2所述的方法，還包括在識別到要求所述第一路由器向所述泛洪區域泛洪所述鏈路狀態消息的事件時，更新所述資料庫以將所述鏈路狀態消息的所述鏈路狀態數據標記為需要恢復； 啟動提取計時器以觸發所述鏈路狀態數據的檢索；以及根據鏈路狀態時間定期地從所述第一路由器輸出所述資料庫同步消息直至接收到所述鏈路狀態消息的所述副本。
9.根據權利要求2所述的方法，其中，在所述第一路由器與所述第二路由器之間建立所述鏈路狀態路由鄰接包括向所述第二路由器發送指定所述路由鄰接的最小數據包間隔的消息；以及其中，從所述第二路由器接收所述鏈路狀態消息的所述副本包括通過L2通信媒體接收從所述第二路由器向所述第一路由器泛洪的多條鏈路狀態消息，其中以至少保持每條所述鏈路狀態消息間的指定的最小數據包間隔的速率接收泛洪的鏈路狀態消息。
10.根據權利要求9所述的方法，其中，接收從所述第二路由器泛洪的多條所述鏈路狀態消息包括通過所述第一路由器接收多條所述鏈路狀態消息的子集直至達到由所述第一路由器分配的數據包信用；使用所述第一路由器為所述鄰接分配附加數據包信用； 將所述附加的數據包信用通信給所述第二路由器；以及接收多條所述鏈路狀態消息的剩餘部分。
11.根據權利要求10所述的方法，其中，所述數據包信用指定為所述路由協議鄰接分配的多個數據包或多個字節中的一個。
12.根據權利要求9所述的方法，其中，向所述泛洪區域泛洪所述鏈路狀態消息的所述副本包括從所述第一路由器向所述第三路由器泛洪所述鏈路狀態消息的所述副本作為多條所述鏈路狀態消息中的一條所述鏈路狀態消息，以及其中，當泛洪多條所述鏈路狀態消息滿足或超過由所述第三路由器指定的最小數據包間隔時，所述第一路由器保持多條所述鏈路狀態消息中的各條所述鏈路狀態消息間的間隔。
13.根據權利要求12所述的方法，其中，從所述第一路由器向所述第三路由器泛洪所述鏈路狀態消息的所述副本而作為多條所述鏈路狀態消息中的一條所述鏈路狀態消息包括，使用所述第一路由器泛洪多條所述鏈路狀態消息的子集直至達到分配的數據包信用以及在泛洪多條所述鏈路狀態消息的剩餘部分之前等待直到從所述第三路由器接收到附加信用。
14.根據權利要求13所述的方法，其中，在所述第一路由器與所述第二路由器之間建立所述鏈路狀態路由鄰接包括交換包括用以指定所述鄰接的最小數據包間隔的第一子欄位和用以指定分配給所述鄰接的數據包信用的第二子欄位的類型、長度以及值(TLV)。
15.根據權利要求1所述的方法，其中，從所述鏈路狀態消息削減至少部分所述鏈路狀態數據包括對所述鏈路狀態消息的淨荷應用一組削減規則並削減滿足由所述規則指定的標準的淨荷的一個或多個部分。
16.一種路由設備，包括網絡接口，用以通過層二(U)通信媒體發送和接收數據包；控制單元，耦接至所述網絡接口 ；基於泛洪的鏈路狀態路由協議，在所述控制單元的處理器上執行，其中所述鏈路狀態路由協議通過所述層二(U)通信媒體與對等路由器建立鄰接；以及資料庫，具有存儲用於所述鏈路狀態路由協議的泛洪區域的多條鏈路狀態消息的條目，其中所述資料庫中的至少一個所述條目存儲具有報頭部分和鏈路狀態數據已被削減的淨荷的部分鏈路狀態消息。
17.根據權利要求16所述的路由設備，其中，所述鏈路狀態路由協議從所述泛洪區域的第二路由器接收所述鏈路狀態消息，以及其中，所述鏈路狀態路由協議將所述鏈路狀態消息存儲到所述第一路由器的所述資料庫的所述條目，將所述鏈路狀態消息泛洪到所述泛洪區域的第三路由器，並且在接收到來自所述第三路由器的確認之後，從存儲在所述資料庫內的所述鏈路狀態消息中的至少一條所述鏈路狀態消息削減至少部分所述鏈路狀態數據而不刪除整個所述鏈路狀態消息，以形成所述部分鏈路狀態消息。
18.根據權利要求16所述的路由設備，還包括一組削減規則，指定用於識別要從所述資料庫削減的鏈路狀態數據的標準；以及在所述控制單元上執行的削減模塊，對所述資料庫內的所述條目應用所述削減規則， 並且從存儲在所述資料庫內且滿足標準的任一條所述鏈路狀態消息中削減至少部分所述鏈路狀態數據，而不是從所述條目中刪除所述鏈路狀態消息的所述報頭部分。
19.根據權利要求16所述的路由設備，還包括重建模塊，在所述控制單元上執行，以確認要求從所述資料庫削減的至少一些所述鏈路狀態數據需要被泛洪至所述泛洪區域的事件，其中，所述重建模塊輸出對指示所述第二路由器將所述部分鏈路狀態消息的完整版本再泛洪進行描述的資料庫同步消息。
20.根據權利要求19所述的路由設備，其中，所述資料庫同步消息包括為所述部分鏈路狀態消息指定標識符的部分序列號數據包數據單元(PSNP)和為所述鏈路狀態消息指定低於記錄在所述資料庫內用於所述部分鏈路消息的當前序列號的序列號，以指示所述第二路由器再泛洪所述部分鏈路狀態消息的完整版本。
21.根據權利要求19所述的路由設備，其中，所述資料庫同步消息包括對所述第二路由器的所述資料庫的全部內容進行描述的完整序列號數據包數據單元(CSNP)，其中所述第一路由器從CSNP去除所述鏈路狀態消息的條目以指示所述第二路由器再泛洪所述部分鏈路狀態消息的完整版本。
22.根據權利要求19所述的路由設備，其中，在接收到由所述第二路由器再泛洪的所述鏈路狀態消息的完整版本時，所述鏈路狀態路由協議向所述泛洪區域泛洪所述鏈路狀態消息。
23.根據權利要求19所述的路由設備，還包括用於觸發削減的鏈路狀態數據的檢索的提取計時器，其中，所述資料庫的每個所述條目包括用於將所述鏈路狀態數據標記為需要恢復的標誌，以及其中，在識別到所述事件時，所述重建模塊更新所述資料庫以將所述部分鏈路狀態消息的所述鏈路狀態數據標記為需要恢復，啟動提取，並且根據鏈路狀態時間定期地從所述第一路由器輸出所述資料庫同步消息直至接收到所述鏈路狀態消息的所述副本。
24.根據權利要求16所述的路由設備，還包括資料庫，存儲由所述泛洪區域內的對等路由器指定的最小數據包間隔；出站數據包隊列，存儲由所述鏈路狀態路由協議產生的多條鏈路狀態消息以通過所述 L2通信媒體泛洪到所述對等路由器；以及調度器，使所述鏈路狀態消息從所述出站數據包隊列離隊，並且將每條所述鏈路狀態消息泛洪到所述L2通信媒體，其中，在將多條所述鏈路狀態消息泛洪到所述L2通信媒體時，所述調度器至少保持多條所述鏈路狀態消息中的各條間的指定最小數據包間隔。
25.根據權利要求M所述的路由設備，其中，所述資料庫包括用於所述對等路由器的記錄，每條所述記錄指定由各個路由器指定的最小數據包間隔，以將所述鏈路狀態消息泛洪到所述路由器，其中，當所述L2通信媒體包括點對點通信媒體時，所述調度器運行在所述調度器以連續鏈路狀態消息間的時間間隔將多條所述鏈路狀態消息泛洪到所述L2通信媒體的第一模式下，其中所述時間間隔超出由對等路由器指定的所述最小數據包間隔，以及其中，當所述L2通信媒體包括多路訪問通信媒體時，所述調度器運行在第二模式下， 其中所述調度器(a)通過所述L2通信媒體訪問所述資料庫以識別由具有鄰接關係的所述多個路由器中的任一個指定的最長的最小數據包間隔，以及(b)以連續鏈路狀態消息間的時間間隔將多條所述鏈路狀態消息泛洪到所述L2通信媒體，其中所述時間間隔超出為多個所述路由器所識別的最小數據包間隔。
全文摘要
記載了一種增強型基於泛洪的鏈路狀態路由協議，其提供鏈路狀態數據的削減以及需要時從泛洪區域的其它路由器提供削減的鏈路狀態數據的速率控制恢復。路由設備包括通過層二(L2)通信媒體發送和接收數據包的網絡接口。路由設備包括耦接至網絡接口的控制單元，以及在控制單元的處理器上執行的基於泛洪的鏈路狀態路由協議。鏈路狀態路由協議與對等路由器建立鄰接關係。路由設備的資料庫包括存儲用於鏈路狀態路由協議的泛洪區域的多條鏈路狀態消息的條目，其中，資料庫中的至少一個條目存儲具有報頭部分和含有削減的鏈路狀態數據的淨荷的部分鏈路狀態消息。
文檔編號H04L12/56GK102387065SQ20111024023
公開日2012年3月21日 申請日期2011年8月19日 優先權日2010年8月19日
發明者戴維·M·卡特茲, 戴維·沃德 申請人:叢林網絡公司