在快速重路由受保護鏈路發生故障時避免微環的製作方法
2023-04-25 08:34:36 2
專利名稱：在快速重路由受保護鏈路發生故障時避免微環的製作方法
技術領域：
本發明涉及數據聯網，更具體而言涉及在採用受保護鏈路的數據網絡中避免微環。
背景技術：
計算機網絡是由在比如計算機這樣的末端站之間傳輸數據的通信鏈路和網段互連的節點的地理上分散的集合。有許多類型的網段可用，其類型從區域網(LAN)到廣域網(WAN)不等。LAN一般經由位於諸如建築物或校園之類的同一個總的物理位置中的專用私有通信鏈路連接個人計算機和工作站。LAN還可連接同處於較近範圍內的路由器。
另一方面，WAN一般經由比如公共載波電話線這樣的長距離通信鏈路連接大量地理上分散的節點。網際網路是WAN的一個示例，其連接世界上的不同網絡，提供各種網絡上的節點之間的全球通信。節點一般通過根據預定的協議交換分立的數據幀或分組來經由網絡通信，所述協議例如是傳輸控制協議/網際網路協議(TCP/IP)。在此上下文中，協議由限定節點如何與彼此交互的一組規則構成。
某些節點，例如路由器，常被配置為在網絡中的各種節點之間「路由」數據，例如分組。路由一般是在開放系統互連(OSI)參考模型的網絡層或第3層(L3)執行的。路由器通常維護著轉發資料庫(FDB)，所述轉發資料庫一般被配置為保存路由器用來確定數據(例如數據分組)要被轉發到何處以到達其目的地的路由信息和接口信息，所述路由信息包括L3地址。例如，路由器可以具有包含一個或多個條目的路由資料庫，其中每個條目包含目的地節點的L3目的地地址和關於路由器上經由其可到達目的地節點的接口的接口信息。包含與路由表中的條目的目的地地址相匹配的目的地地址的數據分組被路由器轉發到由匹配條目指定的接口，以傳送到目的地節點。
路由器可執行一個或多個路由協議，這些協議使得路由器能夠路由分組並與網絡中的其他路由器交換路由信息。路由器常使用此信息來配置(例如計算)其FDB。路由協議可包括距離向量協議，例如路由信息協議(RIP)，或者鏈路狀態協議，例如中間系統到中間系統(IS-IS)協議或開放最短路徑優先(OSPF)協議。路由信息一般以通告消息的形式是在路由器之間交換的。例如，執行IS-IS協議的節點利用被稱為鏈路狀態分組(LSP)的通告消息交換信息。類似地，執行OSPF協議的節點利用被稱為鏈路狀態通告(LSA)的通告消息交換路由信息。這裡所使用的通告消息一般是指路由協議用來向網絡中的其他中間節點(例如路由器、交換機)傳達路由信息的消息。獲取通告消息的中間節點可使用其中包含的信息來更新其FDB。
路由器可利用面向連接的協議以「面向連接」的方式通過源和目的地之間的網絡傳送數據分組。面向連接的協議經由在源和目的地之間建立的預定的路徑通過網絡傳送數據分組，所述路徑常被稱為連接或電路。在這裡，連接或電路是在任何數據被傳送之前建立在源和目的地之間的。在連接被建立之後，數據經由連接所限定的路徑在源和目的地之間被傳送。當不再需要連接時，連接一般被「拆卸」，並且被連接所利用的諸如節點、接口、協議之類的資源被提供給其他連接使用。面向連接的協議的一個示例是多協議標籤交換(MPLS)協議。這裡所使用的資源是指與中間節點相關聯的實體。這些實體可包括中間節點本身、中間節點上的接口(例如埠)以及運行在中間節點上的協議。
一些面向連接的協議利用單向連接，即在從源到目的地的一個方向上傳送數據的連接。例如，路由器A和路由器B之間的單向連接在從路由器A到路由器B的一個方向上傳送數據。為了在另一方向，即從路由器B到路由器A的方向上傳送數據，就必須建立從路由器B到路由器A的另一單向連接。可利用比如資源預留協議(RSVP)這樣的信令協議端到端地「通知」連接。連接的發起連接信令的那一端通常被稱為連接的「頭端」，連接的端接信令的那一端通常被稱為連接的「尾端」。容宿著連接的頭端的路由器通常被稱為頭端節點，容宿著連接的尾端的路由器通常被稱為尾端節點。從而，例如，在其中路由器A容宿著連接的「頭端」而路由器B容宿著連接的尾端的從源到目的地的連接中，路由器A是頭端節點，路由器B是尾端節點。
為了提供高可用性，一些面向連接的協議可包括使承載連接的主路徑在主路徑包含發生故障的鏈路的情況下迅速被重路由的技術。例如，可從網際網路工程任務組(IETF)http://www.ietf.org獲得的P.Pan等人的「FastReroute Extensions to RSVP-TE for LSP Tunnels」，draft-ietf-mpls-rsvp-fastreroute-04.txt描述了可用於迅速重路由以避開MPLS標籤交換路徑中的故障網絡元件(例如鏈路、節點)的MPLS「快速重路由」(FRR)技術。根據該技術，主路徑中的一條或多條鏈路是受保護鏈路(即它們被備用路徑所保護)。如果在受保護鏈路或節點上發生故障，則流量工程MPLS標籤交換路徑(TE LSP)上承載的流量被故障上遊緊接著的那個節點本地重路由到例如適當的備用路徑上。備用路徑充當主標籤交換路徑的FRR，消除了求助於其他可能更昂貴的措施的必要，所述其他措施例如是拆卸主標籤交換路徑並建立繞開故障網絡元件的新的主標籤交換路徑。注意，本地重路由之後可進行由頭端標籤交換路由器(LSR)觸發的端到端重優化，以使流量遵循更適宜的標籤交換路徑。
FRR技術的一個問題是由於例如因中間節點對發生故障的鏈路作出響應而可能形成的微環，其優點(例如迅速重路由以避開故障的能力)可能會有所減弱。例如，在IP網絡中，微環一般由於中間節點響應於發生故障的受保護鏈路重新計算其FDB所花費的時間的差異而發生。圖1示出IP數據網絡100，其包括經由各種中間節點110a-d和數據鏈路130a-f通過數據網絡100耦合的末端節點120a-b。假定鏈路130c是與經由節點110b、110a和110d到節點110c的備用路徑相關聯的受保護鏈路。還假定主路徑從末端節點120a經由節點110a、110b和110c延伸到末端節點120b。現在假定鏈路130c發生故障，並且中間節點110b已檢測到了鏈路故障並重新計算其FDB，以將以末端節點120b為目的地的流量引導到備用路徑。還假定中間節點110a尚未重新計算其FDB以將發生故障的鏈路130c考慮在內，因而繼續在主路徑上轉發以末端節點120b為目的地的數據。以末端節點120b為目的地的數據被中間節點110a轉發到中間節點110b，中間節點110b進而又將數據轉發到去往中間節點110a的備用路徑上。由於其尚未更新FDB以將發生故障的鏈路130c考慮在內，因此中間節點110a將數據轉發回中間節點110b。因此，節點110a和110b之間的微環形成了。該微環持續存在，直到中間節點110a更新其FDB以將發生故障的鏈路130c考慮在內為止。
在典型的網絡布置中，在FRR方案中從主路徑切換到備用路徑所涉及的時間量可能是數十毫秒的量級。另一方面，網絡中的中間節點使其FDB收斂到某個網絡拓撲所花費的時間可能是數百毫秒的量級。收斂過程還可能由於在中間節點使其FDB收斂到網絡拓撲的同時在網絡中的各個點形成的微環而進一步延遲。在中間節點收斂其FDB的時間期間，網絡可能是不可用的。其後果是減弱了快速重路由(即迅速從主路徑切換到備用路徑的能力)的價值。即使在FRR實現中從主路逕到備用路徑的切換已迅速地發生(例如在數十毫秒中發生)，由於例如由FDB收斂導致的、因微環發生而進一步惡化的網絡中斷，備用路徑也可能在或許數百毫秒中是不可用的。
發明內容
所發明的技術通過結合用於避免採用受保護鏈路的計算機網絡中的微環的高效裝置，克服了現有技術的缺點。根據該技術，中間節點基於該中間節點與發生故障的鏈路之間的距離來延遲更新其轉發資料庫(FDB)。具體而言，根據所發明的技術，與更遠離發生故障的鏈路(即與發生故障的鏈路的距離相對較長)的中間節點相比，靠近發生故障的受保護鏈路(即與發生故障的受保護鏈路的距離相對較短)的中間節點將更新其FDB的操作延遲更長的一段時間。通過以這種方式更新FDB，可避免微環，從而加速網絡中的FDB收斂和中間節點。
在所例示的實施例中，中間節點利用通告消息將受保護鏈路通告給其鄰近的節點。當中間節點檢測到受保護鏈路發生故障時，它生成新的FDB和將發生故障的鏈路考慮在內的通告消息。中間節點隨後將通告消息洪泛(flood)到其鄰近的節點。此外，中間節點將更新其FDB的操作延遲一定量的時間，該時間量與中間節點與發生故障的鏈路的距離有關。在該時間量過去之後，中間節點更新其FDB並開始使用經更新的FDB在例如與發生故障的受保護鏈路相關聯的後備路徑上轉發數據。
有利地，通過將更新FDB的操作更新延遲一定量的時間並且該時間量與中間節點與到生故障的受保護鏈路之間的距離有關，所發明的技術避免了在其他情形下可能發生在網絡中的微環的形成。
通過結合附圖參考以下描述，可以更好地理解本發明的上述和其他優點，在附圖中類似的標號指代相同的或功能上類似的元件圖1是採用受保護快速重路由鏈路的數據網絡的高級示意框圖；圖2是可有利地用於本發明的數據網絡的高級示意框圖；圖3是可有利地用於本發明的中間節點的高級示意框圖；圖4是可用於本發明的監督引擎的部分示意框圖；圖5是可有利地用於本發明的線路卡的部分示意框圖；圖6是可有利地用於本發明的包含類型長度值(TLV)類型22的中間系統到中間系統(IS-IS)鏈路狀態分組(LSP)的部分示意框圖；圖7是可有利地用於本發明的鏈路屬性子TLV的示意框圖；圖8是根據所發明的技術可用於將中間節點配置為檢測數據網絡中的發生故障的鏈路並對其作出響應的步驟序列的流程圖；以及圖9是根據所發明的技術可用於將中間節點配置為對通告消息中指示的拓撲變化作出響應的步驟序列的流程圖。
具體實施例方式
圖2是可有利地用於本發明的數據網絡200的示意框圖。數據網絡200包括連接到多個網絡實體以形成計算機節點的互連網的通信(數據)鏈路204的集合，所述網絡實體例如是末端節點208和中間節點300。這些互連成網的節點通過根據比如傳輸控制協議/網際網路協議(TCP/IP)這樣的預定的協議集交換數據分組來進行通信。這裡所使用的協議是描述如何在數據網絡中的兩個實體之間傳送數據的一組形式規則。
圖3是中間節點300的高級部分示意框圖，該中間節點300例如是路由器。可用於本發明的合適的中間節點包括可從San Jose，CA的CiscoSystems Incorporated獲得的Cisco 7200、7600和12000系列路由器。中間節點300包括由背板320互連的一個或多個線路卡500和監督引擎卡400。節點300被配置為(除其他功能外)根據所發明的技術執行各種傳統的第2層(L2)和第3層(L3)交換和路由功能，包括轉發和處理數據分組。這裡所使用的L2和L3分別是指開放系統互連(OSI)參考模型的數據鏈路層和網絡層。節點300還被配置為提供對包括開放最短路徑優先(OSPF)、中間系統到中間系統(IS-IS)、多協議標籤交換(MPLS)、TCP/IP、IP快速重路由(FRR)、MPLS FRR、乙太網、異步傳送模式(ATM)和幀中繼(FR)在內的協議的各種組合的支持。
背板320包括互連各種卡並允許數據和信號從一個卡傳送到另一個的點到點互連總線。線路卡500使中間節點300與網絡200相連接(接口)。線路卡500利用諸如ATM和乙太網之類的各種協議經由埠315將數據分組傳送到網絡和從網絡獲取數據分組。從功能上來說，線路卡500經由埠315從網絡200獲取數據分組和將數據分組轉發到數據總線320，以及將接收自數據總線320的數據分組經由埠315發送到網絡200。埠315例如可包括ATM、乙太網、快速乙太網(FE)、吉比特乙太網(GE)和FR埠。
監督引擎400包括(除其他功能外)被配置為管理節點300、維護它分發到線路卡500的集中轉發資料庫(FDB)，執行諸如OSPF、IS-IS和MPLS之類的各種協議，並執行其他功能，其中包括結合所發明的技術的多個方面的功能。圖4是可有利地用於本發明的監督引擎的高級部分示意框圖。監督引擎400包括處理器420、系統控制器430、接口邏輯460和存儲器440。存儲器440包括可由系統控制器430尋址的隨機訪問存儲器(RAM)位置，用於存儲例如數據結構和軟體程序。接口邏輯460耦合到背板320，並且被配置為在背板320和處理器420之間傳送數據。
存儲器440是包括被配置為實現128兆字節(Mb)隨機訪問存儲器的動態隨機訪問存儲器(DRAM)設備的計算機可讀介質。存儲器440包含被處理器420使用的各種軟體和數據結構，其中包括轉發資料庫(FDB)444、作業系統442和路由進程446。FDB 444包含傳統的轉發信息，例如網絡中節點的L2和L3地址以及標識經由其可到達與FDB 444中包含的地址相關聯的節點的接口(例如埠315)的接口標識符(ID)。作業系統442包含例如通過調用支持在監督引擎400上執行的軟體進程的網絡操作而從功能上組織中間節點300的計算機可執行指令。這些進程包括路由進程446，該路由進程446被配置為實現由中間節點300支持的各種路由和交換協議，以及本發明的多個方面。本領域的技術人員將會了解到，其他計算機可讀介質，例如盤存儲設備和快閃記憶體設備，也可用來存儲實現本發明的多個方面的計算機可執行指令。此外，本領域的技術人員將會了解到，可生成電磁信號來經由例如無線數據鏈路或比如網際網路這樣的數據網絡運送實現本發明的多個方面的計算機可執行指令。
系統控制器430耦合到處理器420和存儲器440，並且包括被配置為使處理器420能夠訪問(例如讀、寫)存儲器440中包含的存儲器位置的電路。處理器420是被配置為執行存儲器440中包含的用於(除其他目的外)維護FDB 444的指令的傳統中央處理單元(CPU)。具體而言，處理器420執行獲取關於被各種線路卡500處理的分組的信息(例如與分組相關聯的VLAN ID、埠以及L2和L3地址)的指令並利用該信息來維護FDB 444。此外，處理器420執行指令以根據所發明的技術更新FDB444，並將FDB 444分發到各種線路卡500，這些線路卡500可處理該信息以更新和維護它們的轉發資料庫版本。
圖5是可有利地用於本發明的示例性線路卡500的高級部分示意框圖。線路卡500包括網絡接口邏輯520、編碼地址識別邏輯(EARL)540、背板接口邏輯560和輸出排隊邏輯550。此外，線路卡500可包括耦合到網絡200的一個或多個埠315。
網絡接口邏輯520將線路卡500接口到網絡200，並使得線路卡500能夠經由埠315傳送去往和來自網絡200的數據。為此，邏輯520包括傳統的接口電路，所述傳統接口電路可包含將線路卡500與網絡的物理介質和在該介質上運行的協議相接口所需的信號、電氣和機械特性以及交換電路。
背板接口邏輯560包含將線路卡500接口到背板320並使線路卡500能夠將數據傳送到耦合到背板320的其他卡並從其他卡獲取數據的電路。輸出排隊邏輯550包含被配置為控制經由埠315將數據分組傳送到網絡200上的電路，例如輸出隊列和調度控制邏輯。EARL 540例如實現在專用集成電路(ASIC)中，該ASIC包括被配置為(除其他功能外)獲取和處理數據分組的電路，其中包括例如利用EARL 540中包含的線路卡轉發資料庫(LCFDB)542為分組作出轉發判決。LCFDB 542包含使得EARL540能夠確定被EARL 540處理的分組的目的地的信息，例如目的地地址和相關聯的目的地埠。
從操作上來說，數據分組被網絡接口520經由埠315從網絡200獲取，並被傳送到EARL 540，在這裡分組被處理。此處理可包括利用LCFDB 542來確定每個分組的目的地，例如耦合到背板320的另一個卡或線路卡500上的埠315。在分組的目的地被確定之後，EARL 540指示背板接口560將分組經由背板320傳送到目的地(如果目的地是另一個卡的話)或者傳送到輸出排隊邏輯550(如果目的地是線路卡400上的埠315的話)。以監督引擎400為目的地的數據分組被接口邏輯460從背板320獲取，並被置於分組緩衝器450中，在該分組緩衝器450中它們被保存以供處理器420將來處理。
本發明結合了一種用於消除因網絡中的中間節點更新其FDB以適應網絡拓撲變化而可能在數據網絡中形成的微環的影響的技術。根據該技術，受網絡拓撲變化影響的中間節點延遲更新其FDB，以便與更遠離拓撲變化的節點相比，更靠近發生拓撲變化的點的節點將更新其FDB的操作延遲更長的一段時間。通過以這種方式延遲FDB的更新，可避免在其他情況下可能發生的微環。
作為示例，中間節點300執行一個或多個路由協議，包括IS-IS路由協議。將按照例如用於IS-IS協議和MPLS FRR協議來描述所發明的技術；但是應當注意其他協議，例如OSPF和IP FRR，也可利用所發明的技術。
中間節點300利用被稱為鏈路狀態分組(LSP)的通告消息交換IS-IS路由信息。圖6是可有利地用於本發明的LSP 600的示意框圖。LSP 600包含LSP頭部信息610和可選的「類型長度值(TLV)22」欄位620。LSP頭部欄位610包含傳統的LSP頭部信息，例如域內路由協議鑑別符、長度指示符、版本/協議標識符(ID)擴展、剩餘壽命、LSP ID、序列號、校驗和等等。「TLV 22」欄位620例如包含擴展的IS「可達性」TLV類型22對象，該對象在可從網際網路工程任務組(IETF)http://www.ietf.org獲得的H.Smit等人的「draft-ietf-isis-traffic-05.txt」中有所描述，這裡通過引用將其結合進來，就好像在這裡完整闡述了一樣。
應當注意，通告消息600可包含可被中間節點300用於維護其FDB444的其他路由信息，例如IP路由信息。可用於在LSP中通告IP路由信息的技術在可從IETF獲得的R.Callon的「Use of OSI IS-IS for Routing inTCP/IP and Dual Enviroments」請求評論(RFC)1195中有所描述，這裡通過引用將其結合進來，就好像在這裡完整闡述了一樣。
TLV 22對象620可包含(除其他內容外)一個或多個子TLV對象。例如，TLV 22對象620可包含鏈路屬性子TLV對象，其描述網絡200中的受保護鏈路的屬性，例如MPLS快速重路由鏈路或IP快速重路由鏈路。可用於本發明的鏈路屬性子TLV對象在可從IETF獲得的J.Vasseur等人的「Definition of an IS-IS Link Attribute sub-SLV」draft-vasseur-isis-link-attr-00.txt中有所描述，這裡通過引用將其結合進來，就好像在這裡完整闡述了一樣。
圖7是可用於本發明的鏈路屬性子TLV對象700的示意框圖。子TLV700包括類型欄位720、長度欄位730和標誌欄位770。類型欄位720保存著將子TLV標識為鏈路屬性子TLV的值。優選地，此值為19。長度欄位730包含著指示子TLV 700的長度的值。優選地，此值為4，以指示子TLV的長度為4個八位字節。
標誌欄位770例如保存著代表描述與數據鏈路相關聯的屬性的標誌的按位掩碼值。例如，這些標誌包括「本地保護可用」(LPA)標誌771、「本地保護路徑中排除的鏈路」(LE)標誌773和未使用的標誌欄位774。未使用的標誌欄位774例如包含足夠數目的位，這些位被設置為零並將標誌欄位770的整體長度填充到2個八位字節。LPA標誌771例如是一個一位標誌，當其被設置為1時，指示由鏈路屬性子TLV 700所表示的鏈路受本地保護機制的保護，所述本地保護機制例如是基於MPLS FRR協議或IP FRR協議的機制。LE標誌773例如是一個一位標誌，當其被設置為1時，指示在計算備用路徑(即作為採用該鏈路的發生故障的主路徑的備用的路徑)時不應當排除該鏈路。
如上所述，中間節點300利用通告消息(例如LSP)交換路由信息。在中間節點300接收到通告消息之後，它檢查消息並確定網絡的拓撲是否已經變化(例如鏈路發生了故障)。如果是，則中間節點300通過基於變化的拓撲生成新的FDB來對變化的拓撲作出響應。根據所發明的技術，為了避免例如微環，中間節點還延遲利用新FDB更新其FDB 444和將更新後的FDB分發到線路卡500的操作。
圖8是根據所發明的技術可用於將中間節點300配置為對拓撲變化作出響應的步驟序列的流程圖。假定主MPLS標籤交換路徑經由中間節點300a、300b、300c和300d被建立在末端節點208a和208b(圖2)之間。此外，假定鏈路204d是受保護的FRR鏈路，並且鏈路204d的後備MPLS標籤交換路徑被經由節點300b、300a、300e、300f和300g從節點300c建立到節點300d。
該序列開始於步驟805，並進行到步驟810，在該步驟中，中間節點300c生成指示鏈路204d為受保護鏈路的通告消息。具體而言，在步驟810，中間節點300c生成包含鏈路204d的鏈路屬性子TLV 700的通告消息，其指示該鏈路是「受保護」的(例如LPA 771被設置為1)。中間節點300c隨後將該通告消息洪泛到其附近的節點300b和300d(步驟820)。
在步驟830，鏈路204d發生故障，並且在步驟840，中間節點300c檢測到發生故障的鏈路204d。在步驟850，響應於發生故障的鏈路，中間節點300c生成將發生故障的鏈路204d考慮在內的新的FDB。例如，中間節點300c通過確定排除鏈路204d的新網絡拓撲來將發生故障的鏈路204d考慮在內並且基於新的網絡拓撲生成新的FDB。在步驟860和870，中間節點300c生成將發生故障的鏈路204d考慮在內的新的通告消息，並將該新通告消息洪泛到其附近的節點(例如節點300b和300d)，如上所述。新的通告消息可例如通過從消息中排除(忽略)發生故障的鏈路204d來將發生故障的鏈路204d考慮在內。或者，新的通告消息可包含明確指示鏈路204d發生了故障的信息。
在步驟880，中間節點300c基於其與發生故障的鏈路204d的點的距離將利用新FDB中包含的信息更新其FDB 444這一操作延遲一段時間。例如，該時間段是利用以下公式確定的T＝(D-N)*K其中「T」是該時間段，「D」是網絡直徑，「N」是節點300c與拓撲變化點(例如鏈路204d)之間的跳數，「K」是常數。「K」是可配置的常數，其值取決於各種網絡動態，例如通知網絡的中間節點鏈路204d發生故障所花費的最少時間。優選地，「K」約為500毫秒(ms)。最大網絡直徑優選不大於20跳。這裡所使用的網絡直徑是指網絡中的兩個最遠點之間的最大跳數。例如，假定末端節點208a和208b處於網絡100中的最遠點，則最大跳數將為5(即從末端節點208a經由中間節點300a、300e、300f、300g和300d到末端節點208b的路徑)。
在所述時間段過去之後，序列進行到步驟890，在該步驟中，中間節點300基於新FDB中包含的信息更新其FDB 444。例如，中間節點利用新FDB中包含的信息更新其FDB 444，並將經更新的FDB 444分發到線路卡500。線路卡進而又基於分發的經更新的FDB 444的內容來更新其LCFDB542，並開始基於其經更新的LCFDB來轉發數據。序列在步驟895結束。
應當注意，上述用於確定中間節點延遲更新其FDB 444的時間段的公式是可用於本發明的公式的一個示例。其他公式，不論是線性的還是非線性的，也可用於所發明的技術。可使用的非線性公式的一個示例是
T＝K1+K2*(log(D-N)2)其中「T」是該時間段，「D」是網絡直徑，「N」是中間節點300與拓撲變化點(例如發生故障的鏈路204d)之間的跳數，「K1」和「K2」是如上所述的取決於各種網絡動態的常數，「log」是以10為底的對數函數。
網絡200中的某些中間節點300可通過檢查由該中間節點接收到的通告消息來確定特定受保護鏈路發生了故障。響應於斷定受保護鏈路發生了故障，中間節點生成新的FDB，並且根據所發明的技術，延遲利用來自新FDB的信息更新其當前FDB，如上所述。圖9是根據所發明的技術可用於將中間節點300配置為處理指示發生故障的受保護鏈路的通告消息的步驟序列的流程圖。
假定數據鏈路204d是受保護鏈路，並且鏈路204d發生了故障。此外，假定中間節點300c檢測到了發生故障的鏈路，並且已經如上所述將指示鏈路204d發生了故障的通告消息洪泛到了網絡200的與其相鄰的中間節點(例如中間節點300b)。該序列開始於步驟905，並且進行到步驟910，在該步驟中，中間節點300b接收通告消息。接下來，在步驟920，中間節點300b檢查通告消息並確定鏈路204d發生了故障。該確定例如可通過將通告消息中表示的網絡拓撲與由先前接收到的通告消息所表示的網絡拓撲相比較並斷定由於鏈路204d發生了故障因而鏈路204d的狀態已從可用變為不可用來進行。
在步驟930，中間節點300b生成將發生故障的鏈路204d考慮在內的新FDB，如上所述。在步驟950，中間節點300b將它從中間節點300c接收到的通告消息洪泛到其鄰近中間節點(例如中間節點300a)。例如，通告消息被洪泛到除它從其接收到指示鏈路204d發生了故障的通告消息的節點(即節點300c)之外的所有鄰近節點。在步驟960，中間節點300b基於其到發生故障的鏈路204d的距離將更新其FDB 444的操作延遲一段時間，如上所述。在步驟970，在所述時間段過去之後，中間節點300b基於新FDB中包含的信息更新其FDB 444，如上所述。序列在步驟995結束。
以上描述針對了本發明的特定實施例。很明顯，可以對所描述的實施例作出其他變化和修改，同時仍能獲得其優點中的一些或全部。因此，所附權利要求的一個目的是覆蓋處於本發明的真實精神和範圍之內的所有這樣的變化和修改。
權利要求
1.在包括多個中間節點和發生故障的受保護數據鏈路的數據網絡中包含的中間節點中，一種用於避免所述數據網絡中的微環的方法包括以下步驟在所述多個中間節點中提供第一轉發資料庫(FDB)；以及將更新所述第一FDB的操作延遲一段時間，該時間段是基於所述中間節點到所述發生故障的受保護數據鏈路的距離的。
2.如權利要求1所限定的方法，包括以下步驟檢測所述發生故障的受保護數據鏈路。
3.如權利要求1所限定的方法，包括以下步驟接收指示所述受保護鏈路發生了故障的通告消息。
4.如權利要求1所限定的方法，包括以下步驟生成將所述發生故障的受保護鏈路考慮在內的第二FDB；以及在所述時間段過去之後基於所述第二FDB中包含的信息更新所述第一FDB。
5.如權利要求1所限定的方法，其中所述中間節點被耦合到一個或多個鄰近的中間節點。
6.如權利要求5所限定的方法，包括以下步驟生成通告消息，其中所述消息指示所述發生故障的受保護數據鏈路是受保護鏈路；以及將所述通告消息洪泛到所述一個或多個鄰近中間節點。
7.如權利要求6所限定的方法，其中所述通告消息包含鏈路屬性子類型長度值(TLV)，該鏈路屬性子類型長度值包含指示所述發生故障的受保護鏈路受到本地保護機制的保護的標誌。
8.如權利要求7所限定的方法，其中所述本地保護機制是基於多協議標籤交換(MPLS)快速重路由協議的。
9.如權利要求7所限定的方法，其中所述本地保護機制是基於網際網路協議(IP)快速重路由協議的。
10.如權利要求6所限定的方法，其中所述通告消息包含鏈路屬性子TLV，該鏈路屬性子TLV包含指示對所述鏈路的保護當前是活動的的標誌。
11.如權利要求5所限定的方法，包括以下步驟生成將所述發生故障的鏈路考慮在內的通告消息；以及將所述通告消息洪泛到所述一個或多個鄰近中間節點。
12.如權利要求11所限定的方法，其中，通過從所述通告消息中排除所述發生故障的鏈路來將所述發生故障的鏈路考慮在內。
13.如權利要求11所限定的方法，其中，通過在所述通告消息中包括明確指示所述發生故障的鏈路發生了故障的信息來將所述發生故障的鏈路考慮在內。
14.如權利要求1所限定的方法，其中所述時間段是利用以下公式來確定的T＝(D-N)*K其中「T」是所述時間段，「D」是網絡直徑，「N」是所述中間節點與所述發生故障的鏈路之間的跳數，「K」是常數。
15.如權利要求1所限定的方法，其中所述時間段是利用以下公式來確定的T＝K1+K2*(log(D-N)2)其中「T」是所述時間段，「D」是網絡直徑，「N」是所述中間節點與所述發生故障的鏈路之間的跳數，「K1」和「K2」是常數，「log」是以10為底的對數。
16.一種耦合到網絡的中間節點，其中所述網絡包含發生故障的數據鏈路，所述中間節點包括包含第一轉發資料庫(FDB)的存儲器；以及耦合到所述存儲器的處理器，該處理器被配置為基於所述中間節點到所述發生故障的鏈路的距離延遲更新所述第一FDB。
17.如權利要求16所限定的中間節點，其中所述處理器被配置為檢測所述發生故障的受保護鏈路。
18.如權利要求16所限定的中間節點，其中所述處理器被配置為生成將所述發生故障的受保護鏈路考慮在內的第二FDB；以及在所述時間段過去之後基於所述第二FDB中包含的信息更新所述第一FDB。
19.如權利要求18所限定的中間節點，其中所述中間節點被耦合到一個或多個鄰近的中間節點。
20.如權利要求19所限定的中間節點，其中所述處理器被配置為生成通告消息，其中所述消息指示所述發生故障的受保護數據鏈路是受保護鏈路；以及將所述通告消息洪泛到所述一個或多個鄰近中間節點。
21.如權利要求19所限定的中間節點，其中所述處理器被配置為生成將所述發生故障的鏈路考慮在內的通告消息；以及將所述通告消息洪泛到所述一個或多個鄰近中間節點。
22.一種耦合到網絡的設備，其中所述網絡包含發生故障的受保護數據鏈路，所述設備包括第一轉發資料庫；以及用於將更新所述第一FDB的操作延遲一段時間的裝置，該時間段是基於所述設備到所述發生故障的受保護數據鏈路的距離的。
23.如權利要求22所述的設備，包括用於生成將所述發生故障的受保護鏈路考慮在內的第二FDB的裝置；以及用於在所述時間段過去之後基於所述第二FDB中包含的信息更新所述第一FDB的裝置。
24.一種計算機可讀介質，包括用於執行以下步驟的計算機可執行指令檢測數據網絡中的發生故障的受保護鏈路；以及基於中間節點到所述發生故障的受保護數據鏈路的距離將更新轉發資料庫的操作延遲一段時間。
全文摘要
一種技術結合了用於避免與發生故障的受保護鏈路相關聯的後備路徑上的微環的高效裝置。中間節點基於中間節點與發生故障的鏈路的距離延遲更新中間節點中包含的轉發資料庫(FDB)(圖8)。具體而言，與更遠離發生故障的鏈路的節點相比，靠近發生故障的受保護鏈路的中間節點將更新其FDB的操作延遲更長的一段時間(880)。通過以這種方式更新FDB，在發生故障的鏈路的後備路徑上可避免微環，因為後備路徑上的靠近發生故障的鏈路的節點不會比後備路徑上更遠離發生故障的鏈路的節點更早更新其FDB。
文檔編號H04L12/56GK1973486SQ200580019393
公開日2007年5月30日 申請日期2005年5月26日 優先權日2004年6月15日
發明者讓-菲利普·瓦瑟爾, 斯特凡諾·普雷維蒂, 克拉倫斯·菲爾斯非斯 申請人:思科技術公司