用於網絡路徑檢測的系統和方法

2023-10-07 01:31:29 2

專利名稱：用於網絡路徑檢測的系統和方法
用於網絡路徑檢測的系統和方法
背景技術：
計算機網絡通常提供不同計算機之間的物理互連，以允許方便地交換 程序和數據。多個連接裝置(例如交換機和路由器)互連連接到這種網絡 的每個用戶計算機。所述連接裝置維護關於計算機和其他連接裝置的路由 信息，並且執行關於經由連接裝置在計算機之間傳遞的消息流量的路由判 決。每個連接裝置(或路由器)對應於一個網絡路由前綴(前綴)，該前 綴指示其有權直接或間接訪問的其他計算機。因此，從一臺計算機路由到 另一臺計算機的數據沿通過網絡的一條由兩臺計算機之間的路由器限定的
路徑而行。以這種方式，網絡中路由器的聚集(aggregation)限定了連接 到該網絡的各個計算機之間的互連圖形。
因此，在圖形表示中，這種網絡可被設想為計算機之間的節點圖形。 該圖形限定了連接到網絡的每臺計算機之間的一條或多條路徑。因此，路 由器限定了網絡中的節點，並且數據按網絡上的一系列所謂"跳"在節點 之間行進。由於每個路由器通常被連接到多個其他路由器，因此在給定計 算機之間可能存在多條潛在路徑。通常，路由信息被用在每個路由器的路 由表中，所述路由表被用於確定到目的地計算機或網絡的路徑。路由器利 用路由表執行路由判決，以識別出下一 "跳"或下一路由器，從而按順序 發送數據以最終到達目的地計算機。但是，可能出現網絡問題，所述網絡 問題使得路由器和路由器之間的傳輸路徑無法工作。這種故障實際上消除 了由網絡限定的圖形中的節點或跳，因此對本應該通過受影響的路徑路由 的數據流量產生幹擾。
在典型的傳統網絡中，如上所述，數據採取在網絡裝置(例如路由 器)間行進的消息的形式按一系列跳從源到達目的地。在適合用於這裡論 述的方法和裝置的示例性網絡中，虛擬專用網(VPN)通過VPN服務來 互連兩個或更多個本地網絡(例如LAN)，所述VPN服務可操作用於向
子網之間的消息流量提供安全性，從而使得每個子LAN的節點可以與作
為同一 VPN的成員的其他子LAN的節點通信。在典型的VPN布置中， 特定子網可以是具有多個不同站點(其中每個站點具有一個真實的子網) 的大商業企業(例如銀行、零售企業或大公司)的單獨的站點。這種環境 中的傳統VPN非常適合於為子網之間的通信提供透明保護。

發明內容
因此，虛擬區域網或VPN已被普遍用作用於互連相關組織或企業的 遠程站點。VPN互連企業(例如公司、大學或批發商)的多個子網或局域 網(LAN)。子網進而經由公共接入網(例如網際網路)彼此互連。這種子 網互連通常被稱為核心網絡並且包括具有路由器和中繼線的高速骨幹的服 務提供商。每個子網和核心網絡具有被稱為邊緣路由器的進入點，從網絡 流進和流出的流量流過所述邊緣路由器。核心網絡具有被稱為提供商邊緣 (PE)路由器的節點所控制的進入/外出點，而子網具有被稱為用戶邊緣 (CE)路由器的進入/外出點。邊緣路由器通常採用可特別用於向網絡提 供網絡互連(即邊緣路由器連接)的專用協議。 一種這樣的協議是邊界網 絡協議。
邊界網關協議(BGP)是一種自治系統內的路由協議。自治系統是在 公共管理下和具有公共路由方針的一個網絡或一組網絡。BGP被用於交換 針對網際網路的路由信息，並且是在網際網路服務提供商(ISP)之間使用的 協議。用戶網絡(例如大學和公司)通常採用諸如RIP或OSPF之類的內 部網關協議(IGP)來在它們的網絡內交換路由信息。用戶連接到ISP，並 且ISP使用BGP來交換用戶和ISP路由。當BGP在自治系統之間被使用 時，協議被稱為外部BGP (EBGP)。如果服務提供商正在使用BGP在 AS內交換路由，該協議則被稱為內部BGP (IBGP)。在PE和CE之間是 採用IGP還是採用BGP的區別取決於為了從CE向PE通告路由而建立的 機制，該機制通常匹配系統配置，所述系統配置可能例如取決於吞吐量、 連接(節點數目)和流量類型(即到用戶子網或中繼線的邊緣節點)等若 幹因素。
因此，BGP是相當魯棒並且可擴展的路由協議，這從其被指定為因特
網上採用的主要路由協議可以證明。據估計，網際網路BGP路由表的數目在 100K個路由的數量級上。為了實現這種級別上的可擴展性，BGP使用很 多路由參數(被稱為屬性)來定義路由方針和維持穩定的路由環境。
BGP鄰居(相鄰節點)在鄰居之間的TCP連接首次建立時交換全部 路由信息。當檢測到路由表改變時，BGP路由器只將那些已經改變的路由 發送到它們的鄰居。BGP路由器不發送周期性的路由更新，並且BGP路 由更新只通告到目的地網絡的最佳路徑。因此，經由BGP獲知的路由或網 絡路徑具有關聯屬性，所述關聯屬性被用於在存在多條到特定目的地的路 徑時確定到目的地的最佳路由。這些屬性被稱為BGP屬性，BGP屬性可 被用於影響路由選擇。這種屬性例如包括權重(weight)、本地偏好
(local preference)、多出口區分器、源、AS路徑、下一跳和共有
(community)。
在典型VPN中，每個子網具有一個或多個網關節點或用戶設備 (CE)路由器，進入其他子網和來自其他子網的流量通過該CE路由器。
網關節點在核心網絡的邊緣處連接到網絡提供商路由器或提供商設備 (PE)，所述核心網絡可操作用於提供到VPN中其他子網的傳輸。CE和 PE路由器有時被稱為"邊緣"路由器，因為它們接近用戶或提供商網絡的 邊緣。核心網絡可以是公共接入網(例如網際網路)、物理上分開的內聯網 或其他互連，並且提供到遠程PE路由器的傳輸。遠程PE路由器耦合到遠 程CE路由器，遠程CE路由器代表到作為VPN的一部分的遠程子網或 LAN的入口。遠程CE路由器執行消息流量到遠程VPN (LAN)子網中的 目的地的轉發。
在這種VPN布置中，VPN源(或發起者)禾Q VPN目的地(或接收 者)之間的特定端對端路徑代表多個分段。每個分段是沿著該路徑的某些 節點之間的一個或多個跳的集合。多個分段代表一條路徑，— 並且包括從本 地CE路由器到核心網絡的本地CE分段、在核心網絡的PE路由器之間的 核心分段以及從遠程PE路由器到遠程CE路由器的遠程CE分段，這將在 後面進一步論述。可以定義其他分段。因此，這裡論述的CE-CE路徑核實(verification)指的是經由核心網絡在VPN子網之間的連接。
在傳統網絡中，可用節點(路由)的改變是響應於節點可用性、傳輸 線路中斷和其他操作異常而被更新和傳播的。因此，傳統的路由邏輯可以 周期性地分析可用路由並重路由繞過可識別的問題。 一種用於分析核心網 絡中的路由的特定方法採用收斂閾值。典型的路由信息作為對路由表的更 新在相鄰路由器之間傳播。路由表識別出已知路由，並隨時間消除或標記 無效或被中斷的路徑。收斂閾值指示路由表傳播將重路由繞過可疑壞路由 的時間間隔。因此，通過核心網絡的CE-CE路由可以通過等待收斂計時器 閾值來解決，並重試以確定特定路由是否仍在工作。如果是，則已經在核 心中被重路由。但是，這種方法需要延遲收斂閾值到期滿。這可能有益於 例如利用每個標識發起方CE的路由消息來立即識別出問題的CE。如上所 述，路由更新採用用於識別最佳路由的屬性。通過將發起者-擴展共有
(extended community)屬性附接到路由消息(即PVP消息)，發起方CE 可被識別出。
一種傳統的實現方式等待由收斂閾值所代表的預定時間間隔以等到發 生收斂，然後重試。在核心網絡問題中，所謂的收斂事件可以通過在核心 網絡中重路由來處理。用於處理這種收斂的特定方法在2004年12月1日 遞交的題為"SYSTEM AND METHODS FOR DETECTING NETWORK FAILURE"的序列號No.ll層,149 (代理案巻號No. CIS04-40(畫3)) 的未決美國專利申請中有所論述，該申請通過引用被結合於此。但是，收 斂時間可以取決於以下因素而變化例如網絡配置、在核心網絡中在PE 路由器之間行進的距離和總體流量的量。因此，以下做法將是有益的識 別通過核心網絡的從發起方CE到目的地CE或目的地前綴的可用路由路 徑，而不是對於可能超額的或最壞情況的收斂閾值而維持阻擋。可替換
地，以下做法可能是有益的確定地計算收斂事件可能發生的時間閾值，
並在計算機收斂完成間隔之後立即恢復對備用路由的診斷探測。 在某種連接驗證框架中(例如在上述未決美國專利申請中公開的)，
CE到CE核實檢查可能受到阻礙，因為數據平面連接檢査是針對經由一個 或多個CE可達的特定前綴發生的。在此上下文中，CE發起者可能不被發 送方CE所知，並且不需要將該知識告知CE。但是，擴展該框架以包括以
下要求可能是有益的任意給定CE應該能夠知道哪個是任意給定路由的
遠程CE發起者。這種擴展的目的在於使得CE-CE核實檢查可以發生，並 且因此提供經由這些CE可達的多個目的地的聚集。
因此，傳統的CE到CE路由傳播有以下缺陷接收傳播的路由的後 續PE在接收到的路由公開(消息)中覆寫下一跳。換言之，每個接收路 由的後續PE覆寫前一下一跳屬性，因此抹去關於發起方CE路由的信息。 因此，當目的地CE接收到傳播報告或消息時，無法獲得關於發起方CE 的信息，這是由於其間的PE路由器所造成的。
傳統路由器的特定缺點在支持網際網路RFC 2547bis (涉及虛擬專用網 (VPN))的裝置中尤其明顯。在某種實現方式中，在處理由PE從CE接 收的路由時，使得它們的下一跳屬性被PE所重寫。此外，當路由被傳播 遍歷MPLS-VPN骨幹時，其隨後通過一個或多個PE被通告到其他CE， 所述PE在將路由通告到CE之前再次重寫下一跳屬性。因此，發起者CE 信息丟失並且阻礙了 CE-CE核實檢查。
對於CE而言，當接收來自PE的路由時，檢測發起該路由的遠程CE 的身份將是有益的。下面公開的配置概括了一種用於這種機制的特定布 置。因此，這裡公開的配置通過提供CE-CE核實撿查而基本克服了上述路 由檢測機制所呈現的缺點，並因此能夠實現經這些CE可達的多個目的地 的聚集。此外，核實檢查可以基於CE到CE和基於CE到前綴(即VPN 子網中進一步的路由器節點)來執行。CE到CE路徑核實很有用，因為它 提供了對於來自VPN子網的哪些邊緣節點能夠到達為遠程VPN提供服務 的哪些邊緣節點的指示(即用於執行路由判決)，同時CE到前綴路徑核 實可被用於只有某些前綴的子集從CE可達的環境。而且，經核實的前綴 路由隱式地實現了其通過的CE-CE路由。
這裡論述的配置通過從可用CE發起作為一組路徑核實消息想去往為 遠程子網或VPN提供服務的遠程CE路由的路由來提供這些CE到CE裝 置(路由器)核實檢查。包括在路徑核實消息的屬性中的擴展共有屬性存 儲了發起方CE路由器的身份。路徑核實消息通過網絡傳播到遠程CE路
由器，並傳輸發起方CE路由器的身份，因為發起者身份沒有被後續路由
"跳"所覆寫。在被遠程CE接收之後，發起方CE可以從擴展共有屬性 中確定。可達性欄位也被包括在擴展共有屬性中，並且指示是每CE (per-CE)還是每前綴(per-prefDC)適合於所考慮的特定路由。如果每CE可達 性被請求，接收方CE則根據擴展共有屬性中的信息關聯發起方CE，作為 經核實的CE-CE路徑。以這種方式，CE-CE連接檢査識別從其他CE可達 的CE，從而允許基於哪些CE能夠"看見"特定遠程CE來有選擇地執行 重路由判決。因此，該機制允許基於每CE來進行路由可達性聚集，同時 仍舊允許每前綴可達性，該每前綴可達性可能針對某些重要路由(例如 LNS伺服器)被請求。
在特定布置中，該方法基於網絡故障的位置和本質來識別將改變流量 以重路由流量繞過故障的網絡點。這些點是中間網絡節點，並且識別中間 節點還對應於識別與測試發起者和目的地之間的網絡跳相對應的網絡前
伊 5雙。
更詳細地，這裡論述的識別網絡路徑的方法包括建立可操作用於從發 起者到目的地的發送的路徑核實消息，並且將發起者的身份存儲在所述路 徑核實消息中，其中該消息以不受後續路由操作幹擾的非易失性方式被存 儲。發起方路由器(節點)將路徑核實消息經由至少一個中間交換裝置發 送到目的地，並且如果所述發送成功，則在目的地處接收所述路徑核實消 息。接收者路由器通過恢復所述存儲的身份來從接收到的路徑核實消息中 恢復發送發起者的身份，以用於識別和/或映射通過核心網絡的CE之間的 有效和無效路由路徑。
因此，該方法允許基於恢復的發起者的身份將目的地和發起者之間的 路徑指定為經核實的路徑，並且在到目的地的發送不成功的情況下，將發 起者指定為到目的地的無效的路由路徑。在這裡論述的特定配置中，發起 者是本地用戶邊緣(CE)路由器，目的地是遠程CE路由器，其中發起者 和目的地通過包括至少一個提供商邊緣(PE)路由器的路徑互連。這種 PE路由器耦合到共同限定核心網絡的多個PE路由器，其中所述核心網絡 可操作用於採用路徑核實消息來將發起者的身份發送到目的地。 在以下將進一步論述的示例性配置中，路徑核實消息還包括可操作用 於在交換裝置之間傳輸控制信息的屬性，並且所述屬性包括指示路徑核實 消息的發起者的擴展共有欄位。所述路徑核實消息還包括可達性標誌，該 可達性標誌指示基於前綴或基於CE的可達性檢査。因此，所述路徑核實 消息包括根據預定路徑核實協議(PVP)的屬性，其中存儲接收者身份還 包括在路徑核實消息中標識保留屬性，該保留屬性可操作用於在發送期 間傳播到每個路由器，以及將發起者的地址作為身份存儲在保留屬性中。 該PVP還將指示前綴或路徑路由的可達性指示符存儲在保留屬性中，並且 採用該保留屬性來識別路由消息的發起路由器。
在示例性配置中，所述裝置是邊緣路由器，包括用戶邊緣和提供商邊 緣，其中所述用戶邊緣路由器標識到由用戶VPN邊界劃界的自治系統的 進入點，而所述提供商邊緣路由器標識到對網際網路服務提供商劃界的核心 網絡的進入點。
路徑核實消息是根據網內邊界協議(OGP)和網間邊界協議(BGP) 中的-一種來傳輸的，這將在後面進一步論述。所釆用的協議被確定為在採 用所述網間邊界協議的情況下，將可達性指示符分配給回送自路由，並且 將所述自路由經由網內邊界協議傳播到其他交換裝置。此外，路徑核實消 息允許在採用所述網內邊界協議的情況下，將所述發起者指示符分配給去 往其他路由裝置的後續路徑核實消息。
本發明的替換配置包括多編程或多處理的計算機化裝置，例如工作 站、手持或膝上型計算機或專用計算裝置等等，這些裝置被配置以用於處 理這裡作為本發明的實施例公開的方法操作中的任意一個或全部的軟體和Z 或電路(例如上述處理器)。本發明的其他實施例包括諸如Java Virtual Machine之類的軟體程序和/或作業系統，所述作業系統可以單獨操作或者 與多處理計算機化裝置彼此協同操作，以執行上面概括的並且隨後將詳細 公開的方法實施例步驟和操作。 一種這樣的實施例包括一種具有包括了計 算機程序邏輯的計算機可讀介質的電腦程式產品，當所述電腦程式邏 輯在具有存儲器和處理器的耦合的多處理計算機化裝置中被執行時，對處 理器編程以執行這裡作為本發明的實施例公開的操作從而執行數據接入請
求。本發明的這些布置通常作為軟體、代碼和/或其他數據(例如數據結 構)提供，所述軟體、代碼和/或其他數據被布置或編碼在計算機可讀介質
上，所述計算機可讀介質例如是光介質(例如CD-ROM)、軟或硬碟或其 他介質，例如一個或多個ROM或RAM或PROM晶片中的固件或微代 碼、現場可編程門陣列(FPGA)或作為專用集成電路(ASIC)。軟體或 固件或其他這樣的配置可以被安裝在計算機化裝置(例如在用於執行環境 安裝的作業系統期間)上，以使得計算機化裝置執行這裡作為本發明的實 施例說明的技術。


從以下對附圖所示的本發明的優選實施例的更具體描述中，本發明的 前述和其他目的、特徵和優點將變得顯而易見，其中不同附圖中的相同標 號指示相同部分。附圖不一定是按比例繪製的，相反在示出本發明的原理 之處進行了強調。
圖1是可操作用於本發明的網絡通信環境的場景圖，該網絡通信環境 包括限定經由多個提供商設備PE和用戶設備(CE)裝置(路由器)的路 徑的網絡節點；
圖2是在圖1的網絡中採用CE到CE路徑核實機制的流程圖； 圖3是示出在圖1的示例性網絡中的CE-CE路徑的驗證的框圖；以及 圖4-8是用於核實圖3中的路徑的路徑核實機制的操作的流程圖。
具體實施例方式
這裡論述的配置基本克服了上述通過提供CE-CE核實檢査而發生的 基於閾值的路由檢測機制所存在的缺點，因此實現了經由這些CE可達的 多個目的地的聚集。此外，核實檢查可基於CE到CE以及基於CE到前 綴(即進一步的VPN子網中的路由器節點)來執行。因此，這種CE到 CE裝置(路由器)核實檢查是通過從可用的CE發起作為一組路徑核實 消息的路由而發生的，所述路徑核實消息想去往為遠程子網(或VPN) 提供服務的遠程CE路由。擴展共有屬性(包括路徑核實消息的屬性)存
儲了發起方CE路由器的身份。路徑核實消息通過網絡傳播到遠程CE路 由器並且傳輸發起方CE路由器的身份，因為發起者身份不會被後續路由 "跳"所覆寫。在被遠程CE接收之後，發起方CE可從擴展共有屬性中 被確定。
此外，還包括可達性欄位屬性以指示是每CE還是每前綴適合於所考 慮的特定路由。如果每CE可達性被請求，接收方CE則根據擴展共有屬 性中的信息關聯發起方CE，作為經核實的CE-CE路徑。以這種方式， CE-CE連接檢查識別從其他CE可達的CE，從而允許基於哪些CE可以 "看見"特定遠程CE來有選擇地執行重路由判決。因此，這種機制在仍 舊允許每前綴可達性的同時允許基於每CE的路由可達性聚集，所述每前 綴可達性對於某些重要路由(例如LNS伺服器)來說可能是需要的。
圖1是可操作用於本發明的網絡通信環境100的場景圖，該網絡通信 環境100包括限定經由多個提供商設備PE和用戶設備(CE)裝置(路由 器)的路徑的網絡節點。參考圖1，網絡通信環境100包括互連多個本地 用戶114-1...114-3 (—般地稱為114)的本地VPNLAN子網110。如上 所述，典型的VPN包括經由核心網絡140互連的多個子網(例如 LAN)。為了圖示清晰，論述從作為本地VPN LAN 110的子網之一的視 角進行，該本地VPN LAN 110經由核心網絡耦合到其他遠程LAN 112子 網，其中為了清楚僅示出單個LAN 112。每個本地和遠程節點可作為本地 用戶設備(CE)路由器120工作，如圖詳細示出。因此，本地LAN 110 連接到網關用戶設備CE路由器120，其耦合到一臺或多臺提供商設備裝 置130-1和130-2 (—般地稱為130)。如下面將進一步詳細論述的，知曉 多個PE路由器130-1和130-2的CE路由器120可以基於這裡論述的考慮 因素(通常是在核心網絡140邊緣處的另一路由器)針對是否經由路由器 130-1或130-2路由流量執行路由判決。CE路由器120或初始路徑核實裝 置包括路由邏輯121、路徑核實處理器124和網絡接口 126，其中路由邏 輯121可操作用於典型的控制平面路由判決，路徑核實處理器124可操作 用於計算路由判決(如下面進一步公開的)，而網絡接口 126用於轉發和 接收網絡流量。交換架構128響應於路由邏輯121，其用於經由裝置(未
具體示出)上的物理埠實現交換判決。核心網絡140包括多個互連由提
供商提供服務的其他用戶的核心節點142-1... 142-2 (—般地稱為142)， 例如各種路由器、集線器、交換機和其他連接裝置。多個遠程提供商設備 路由器132-3... 132-4 (—般地稱為132)耦合到一個或多個為遠程VPN子 網(例如VPNLAN 112)提供服務的遠程用戶設備路由器122-2...122-3 (一般地稱為122)。作為其相對方的本地子網110，遠程VPN LAN 112 提供多個前綴116-1...116-3 (—般地稱為116)，它們代表為用戶118-1...118-N (—般地稱為118)的子網提供服務的其他路由器或連接節點。
包含在這裡論述的配置中的原理可以由圖l概括，並且參考圖3和圖 4-8中的流程圖被更詳細地論述。本地CE路由器120在本地LAN 110上 將從用戶114發送的分組路由到提供商設備路由器130之一，從而表明進 入核心網絡140。 PE路由器130-1或130-2通過核心網絡140分別經由特 定路徑146-1或146-2朝分組想去往的目的地轉發分組。為了簡化圖示， 假設PE 1例如通過調用PE1 130-1作為進入核心網絡140的入口來向節點 142-1轉發分組144。
如果在節點142-1處發生問題，例如，在CE路由器120上的路徑核 實處理器124調用PE路由器130以經由一組周期性的診斷消息150識別 該問題，並且PE路由器130經由一組路徑核實消息152來定位該問題， 以上兩種消息下面將進一步論述。因此，在CE路由器120上的路徑核實 處理器124指導路由邏輯121經由PE2路由器130-2來路由用戶流量分組 144。路徑核實消息152可操作用於通過識別本地和遠程CE路由器120、 122之間的路徑來識別通過核心網絡從本地子網120到遠程子網112的完 整路徑。此外，路徑核實消息152還可以識別從本地CE路由器120到遠 程前綴116的路徑。
通過保留髮起方本地(CE)路由器120的身份，遠程CE路由器122 或其他連接節點可以識別本地CE路由器120和遠程CE 122或遠程前綴 路由器116之間的經核實的路徑。在圖1中，路徑146-1和146-2分別代 表CE1-CE2 (120-122-2)和CE1-CE3 (120-122-3)之間的路徑。在以上 給出的示例中，在節點142-1故障的情況下，路徑146-1被中斷。因此，CE1和CE2之間的路徑146-1可被識別為無法操作的，但是CE1和CE3 之間的路徑146-2仍然是經核實的。魯棒性較低的方法可能僅僅指示在子 網110和112之間存在某條路徑。這裡，該信息可能是可採用的，例如以 使得CE1採用PE2 130-2作為到子網112或任意前綴116的下一跳，而不 依賴於失效節點PE1 130-1。
圖2是用於在圖1的網絡中採用CE到CE路徑核實機制的流程圖。 參考圖1和2，識別網絡路徑的方法包括建立可操作用於從發起者120發 送到目的地122的路徑核實消息152 (被示為步驟100)，以及在路徑核 實消息152中存儲發起者120的身份(被示為步驟101)，其中消息以不 會被後續路由操作幹擾的非易失性方式存儲。發起者120是用於VPN子 網110的CE路由器，並且標識是IP位址或其他唯一的標識符，例如 MAC地址。如步驟102所示，發起者CE路由器120將路徑核實消息經由 至少一個中間交換裝置(例如核心節點(路由器)142)發送到目的地。
核心網絡140互連多個遠程VPN子網112，並包括互連的路由裝置，例如 PE路由器130、 132、中間路由器142或可操作用於消息流量發送的其他 交換裝置。在典型實現方式中，核心網絡40是網際網路或其他公共接入網 絡。
如果發送成功，則遠程CE路由器122在到遠程VPN 112中的進入點 (CE2或CE3)處接收路徑核實消息152，如步驟103所示。消息的接收 者可以是在VPN子網112邊緣(即進入點)處的CE路由器122，或者是 進一步進入子網112的後續前綴116。接收者通過恢復已存儲的身份(例 如IP位址)從接收到的路徑核實消息152中恢復發送發起者120的身 份，如步驟104所示。成功的接收允許基於恢復的發起者120的身份指定 目的地122、 118和發起者120之間的路徑作為經核實的路徑。通過保留 發起方CE 120的身份，經驗證的路徑因此可被識別為CE-CE (或CE-前 綴，視情況而定)有效路由。
圖3是示出在圖1的示例性網絡中CE-CE路徑的驗證的框圖。參考 圖3，網絡環境IOO包括用戶設備120-11、 122-12、 122-13、提供商設備 130-11、 130-12、 132-13、 132-14以及中間節點142-11... 142-15 (—般地
被稱為142)。通過網絡100的路徑可被再細分成分段160，分段160被 用戶設備120-122和提供商設備130、 132所分開並由虛線168示出。本 地VPN分段162包括從本地VPN 110到提供商設備130-11禾n 130-12的路徑。
核心分段164包括到遠程提供商設備裝置132-13、 132-14的核心網絡 140，並且遠程VPN分段166覆蓋從遠程PE路由器132到遠程VPN 112 的路徑。進一步的多個前綴116-1...116-3可從遠程VPN LAN子網112進 行訪問，所述遠程VPN LAN子網112例如可以是本地LAN伺服器節 點，這將在下面進行描述。
在圖3所示的特定配置中，本地分段162包括多個PE路由器DO-ll, 130-12，以用於接入核心網絡164。此外，這些PE路由器130-11、 130-12可以分別連接到核心網絡140中的不同節點142，例如142-11和 142-14。因此，採用不同提供商設備路由器130的路由判決可以有效地繞 過核心網絡140中的故障。類似地，多個CE路由器122可以提供特定 VPN前綴116。因此，基於每個CE 122和每個前綴116的路徑識別和核 實允許基於可用的路徑和流量目的地進行智能化路由判決。在所示示例 中，遠程VPN LAN 112耦合到CE路由器122-12禾n 122-13 (CE2和 CE3)。因此，如果在132-11 (PE3)上的路徑核實處理器124識別出 CE2或CE3的問題，則它可以採用其他CE路由器來從提供商設備132接 入遠程子網112。
在圖3的核心網絡中，節點142-12的故障影響路徑CE1-CE2，如陰 影區域170所示。利用核心節點142的重路由對於重路由繞過這一故障是 無效的。但是，路徑CE1-CE3 146-2仍然可用。此外，到特定前綴CE1-116的路徑仍然可用。應該注意，前綴連接在子網112中可能不同，從而 取決於子網112中的連接，某一前綴116僅從某些CE 120可用。在此情 形中，每前綴路徑核實允許識別到特定前綴的路徑。例如，路徑CE1->116-1可用，而路徑CE1->116-2和CE1->116-3不可用。因此，如果某些 路由(路徑)被標註為基於每前綴116被核實，CE 122則可以識別經由 同一 CE 122可達的前綴116的集合，對於該CE 122，已經需要每CE可
達性檢查(如果存在的話)，並且應該使用經由所考慮的CE 122可達的
前綴116之一來報告CE可達性。
例如，假設兩個前綴Pl和P2是經由已經對其請求過每前綴可達性檢 査的CEx可達的，並且進一步假設一組前綴P3…Pn也是經由CEx可達 的，但是對於這組前綴，已經對其請求了每CE可達性檢查。在此情況 下，CE不應該發布對P3…Pn的CE可達性檢查，而應該附帶對Pl和P2 獲得的可達性結果，因為所有前綴都是經由同一遠程PE可達的。這種機 制有利地允許基於每CE的路由可達性聚集，同時仍舊允許每前綴可達性 (對於某些重要路由，例如LNS、伺服器等所需的)。
圖4-8是在圖3中用於核實路徑的路徑核實機制的操作的流程圖。參 考圖3-8，用於識別計算機網絡中的邊緣節點交換裝置之間的可靠路由的 方法還包括識別指示到子網的進入點的用戶邊緣(CE)節點120-11，如 步驟200所示。邊緣節點120-11是從為用戶站點提供服務的VPN子網 110外出的點。如上所述，若干協議可用在由PE路由器130指示的骨幹 或ISP網絡與用戶站點VPN之間。因此，該方法涉及識別在指示到核心 網絡的進入點的服務提供商邊緣(PE)節點和子網之間採用的網內路由 協議和網間路由協議中的至少一種，其中所述核心網絡可操作用於互連與 到備用子網的進入點相對應的多個其他PE節點，如歩驟201所示。換言 之，發送取決於是採用網間(BGP)還是網內(IGP)協議，如上所述。 IGP還是BGP的使用可以例如取決於吞吐量負載、邊緣或中繼線連接和 期望的通過節點的發送速度，如上所述。可以採用在路由器協議和內部互 連領域已知的其他因素。
更詳細的講，在用戶子網IIO和核心網絡140之間採用的裝置是邊緣 路由器，包括用戶邊緣節點120、 122和提供商邊緣節點130、 132，其中 用戶邊緣路由器標識到由用戶VPN邊界劃界的自治系統的進入點，而提 供商邊緣路由器標識到劃界網際網路服務提供商的核心網絡的進入點，如步 驟202所示。因此，預期可以獲得高性能和/或高吞吐量路由實踐和協 議。
如步驟203所示執行檢查，以確定是使用IGP還是BGP來進行發
送。如果網間協議(BGP)被用於本地PE節點130，發起方CE節點120 則建立路徑核實消息152，其包括指示到CE節點的回送(loopback)接口 路由的自路由(如步驟204所示)，作為將路徑核實消息152從發起者 120發送到目的地(遠程CE) 120-12、 120-13過程中的第一跳。因此，在 示例性環境100中，發起者是本地用戶邊緣(CE)路由器120-1，目的地 是遠程CE路由器122-12、 122-13，其中發起者和目的地通過包括至少一 個提供商邊緣(PE)路由器130的路徑互連。如步驟205所示，PE路由 器通常被耦合到共同限定核心網絡140的多個附加PE路由器130，其中 核心網絡140可操作用於採用路徑核實消息152來將發起者120的身份發 送到目的地122。
如步驟206所公開的，發起者120將發起者(自身)120的身份存儲 在路徑核實消息152中，其中消息以不會被後續路由操作所幹擾的非易失 性方式被存儲。為了提供完整的CE-CE路由核實檢查，發起者120的身 份被保留在一個欄位中，該欄位不會被沿核心網絡140的後續路由跳所覆 寫或修改。因此，根據路徑核實協議，路徑核實消息152還包括可操作用 於在交換裝置120、 130之間傳輸控制信息的屬性153，其中所述屬性包 括指示路徑核實消息152的發起者120的擴展共有欄位153-1，如步驟 207所示。
因此，更詳細地，路徑核實消息152包括根據預定的路徑核實協議的 屬性153，如步驟208所示。屬性153被用於通過識別路徑核實消息152 中的保留屬性153-1來存儲CE身份，其中保留屬性153-1可操作用於在 傳輸期間傳播到每個路由器(即節點)120、 130，如步驟209所公開的。 發起方CE路由器120作為路徑核實協議(PVP)的一部分將發起者120 的地址作為身份存儲在保留屬性153-1中，如步驟210所示，因此在路徑 核實消息中填充指示CE節點的身份的擴展共有屬性。
此外，發起方CE 120確定接收到路徑核實消息152的其他CE 120是 將採用每CE可達性檢查還是採用每前綴可達性檢査，如步驟211所示。 如以上參考圖1所示，CE-CE可達性檢查核實邊緣路由器122為到遠程 VPN LAN 112的進入點，而每前綴核實證明VPN LAN 112中的額外節點
為用於特定路由前綴(IP位址)116的用戶子集118提供服務。因此，發
起方CE路由器120確定將執行每前綴116還是每CE 122可達性檢查，並 據此基於確定結果在路徑核實消息152中設置可達性指示符153-2，如步 驟212所示。
接收方PE 122響應於可達性指示符，以使得如果可達性指示符(標 志)153-2被設置為每前綴檢查，則路徑核實消息的前綴基於擴展共有屬 性與CE節點的身份相關聯，其中每個接收方CE 122可操作用於將指示 接收的路徑的前綴116與發起方CE相關聯，如歩驟214所示。如果可達 性標誌153-2被設置為每CE檢查，則路徑核實消息152的接收者CE 122 基於擴展共有屬性153-1與CE節點120的身份相關聯，如步驟213所
不o
因此，路徑核實消息152還包括可達性標誌153-2，其中可達性標誌 153-2指示基於前綴116的可達性檢査或基於CE 122的可達性檢查，如步 驟215所公開的。發起方CE 120-11將指示前綴或路徑(每CE)路由的 可達性指示符153-2存儲在保留屬性153中，如步驟216所示。在示例性 配置中，保留屬性153還包括可操作用於標識發起者的四字節IP位址字 段和一字節可達性標誌欄位，該可達性標誌欄位指示是執行路徑可達性檢 查還是執行前綴可達性檢查，如步驟217所示。
簡要地返回步驟203處的協議檢查，如果在CE 120和PE之間採用網 內(IGP)協議，則建立具有相應的擴展共有屬性152-1的路徑核實消息 152，如步驟218所示。CE 120通過用CE節點120的身份來填充擴展共 有屬性來建立相應的擴展共有屬性153-1，其中PE節點130響應於擴展共 有屬性153-1來從CE 120接收擴展共有屬性153-1並將其通告到網絡140 中的後續節點142，如步驟219所示。
在後續路由跳期間，如果採用網內邊界協議，後續節點(即路由器) 則將發起者指示符(身份)分配給到其他路由裝置的後續路徑核實消息， 如步驟220所示。返回步驟221，如果採用網間邊界協議(BGP) ， CE路 由器120則將可達性指示符153-2分配給回送自路由，並將自路由經由網 內邊界協議傳播到其他交換裝置142，如步驟221所示。
在已經建立(生成)路徑核實消息152之後，發起方CE 120將路徑 核實消息152通告(即發送)到PE122，其中，這種通告可操作用於使得 PE 122能夠進一步將路徑核實消息通告到網絡中的其他CE，如歩驟122 所公開的，從而傳播經核實的路徑的可用性。因此，傳播包括將路徑核實 消息152經由至少一個中間交換裝置(例如其他節點142或邊緣路由器 130、 132)發送到目的地122，如步驟223所論述的。如上所述，路徑核 實消息152可以根據網內邊界協議和網間邊界協議中的一種(即IGP或 BGP)被傳輸，如步驟224所示。
在從發起方CE節點120到目的地CE節點122或前綴116的傳播之 後，在步驟225處執行檢査以確定診斷的路徑核實消息152是否指示問 題。如果到目的地的發送不成功，其他節點則可以隨後識別發起者120為 到目的地122、 116的無效路由路徑，如步驟226所示。由於發起方CE節 點120被維護在擴展共有屬性153-1中，因此發起者-目的地路徑可被識別 為在嘗試在目的地122、 116處接收它時是經核實的或有問題的。
相反，如果發送成功，目的地122、 116則接收路徑核實消息152， 如步驟227所示。這種接收指示可核實的CE-CE或CE-前綴路由路徑。接 收者122通過從擴展共有屬性153-1中恢復存儲的身份來從接收到的路徑 核實消息152中恢復發送發起者120的身份。有效路由的成功傳播可以基 於恢復出的發起者120的身份指定目的地122和發起者120之間的路徑是 經核實的路徑，如步驟229所示。
本領域技術人員應該容易意識到，這裡限定的用於識別網絡故障的程 序和方法可以很多形式遞送到處理裝置，所述形式包括但不限於a)永 久存儲在不可寫存儲介質(例如ROM器件)中的信息，b)可變地存儲 在可寫存儲介質(例如軟盤、磁帶、CD、 RAM器件和其他磁和光介質) 上的信息，或者c)通過通信介質傳達給計算機的信息，例如利用諸如因 特網或電話數據機線路之類的電子網絡中的基帶信令或寬帶信令技術 傳達給計算機的信息。操作和方法可被實現在軟體可執行對象中，或者實 現為包含在載波中的指令集合。可替換地，這裡公開的操作和方法可以整 體上或部分地用硬體組件來體現，或者用硬體、軟體和固件組件的組合來
實現，其中所述硬體組件例如是專用集成電路(ASIC)、現場可編程門
陣列(FPGA)、狀態機、控制器或其他硬體組件或器件。
雖然己經參考實施例具體示出並描述了用於識別網絡故障的系統和方 法，但是本領域技術人員將會理解，在不脫離所附權利要求書包含的本發 明的範圍的情況下，可以在形式和細節上進行各種修改。因此，本發明不 希望被所附權利要求書所限制。
權利要求
1.一種識別網絡路徑的方法，包括建立可操作用於從發起者到目的地的發送的路徑核實消息；將所述發起者的身份存儲在所述路徑核實消息中，該消息以不受後續路由操作幹擾的非易失性方式被存儲；將所述路徑核實消息經由至少一個中間交換裝置發送到所述目的地；如果所述發送成功，則在所述目的地處接收所述路徑核實消息；以及通過恢復所述存儲的身份來從所述接收到的路徑核實消息中恢復所述發送發起者的身份。
2. 如權利要求1所述的方法，還包括基於所述恢復的發起者的身份將 所述目的地和所述發起者之間的路徑指定為經核實的路徑。
3. 如權利要求2所述的方法，還包括如果到所述目的地的所述發送不 成功，則將所述發起者識別為到所述目的地的無效路由路徑。
4. 如權利要求3所述的方法，其中所述發起者是本地用戶邊緣(CE) 路由器，所述目的地是遠程CE路由器，所述發起者和所述目的地通過包 括至少一個提供商邊緣(PE)路由器的路徑互連，所述PE路由器被耦合 到共同限定核心網絡的多個PE路由器，所述核心網絡可操作用於採用所 述路徑核實消息來將所述發起者的身份發送到所述目的地。
5. 如權利要求4所述的方法，其中所述路徑核實消息還包括可操作用 於在所述交換裝置之間傳輸控制信息的屬性，所述屬性包括指示所述路徑 核實消息的發起者的擴展共有欄位。
6. 如權利要求5所述的方法，其中所述路徑核實消息還包括可達性標 志，該可達性標誌指示基於前綴或基於CE的可達性檢査。
7. 如權利要求1所述的方法，其中所述路徑核實消息包括根據預定協 議的屬性，所述存儲還包括在所述路徑核實消息中標識保留屬性，該保留屬性可操作用於在發送 期間傳播到每個路由器；將所述發起者的地址作為所述身份存儲在所述保留屬性中； 將指示前綴或路徑路由的可達性指示符存儲在所述保留屬性中；以及 識別所述路由消息的發起路由器。
8. 如權利要求7所述的方法，其中所述裝置是邊緣路由器，包括用戶 邊緣和提供商邊緣，其中所述用戶邊緣路由器標識到由用戶VPN邊界劃 界的自治系統的進入點，而所述提供商邊緣路由器標識到對網際網路服務提 供商劃界的核心網絡的進入點。
9. 如權利要求8所述的方法，其中所述路徑核實消息是根據網內邊界協議和網間邊界協議中的一種來傳輸的，並且如果採用所述網間邊界協議，則將可達性指示符分配給回送自路由，並且將所述自路由經由所述網內邊界協議傳播到其他交換裝置；以及如果採用所述網內邊界協議，則將所述發起者指示符分配給去往其他 路由裝置的後續路徑核實消息。
10. 如權利要求9所述的方法，其中所述保留屬性還包括 可操作用於標識所述發起者的4位元組IP位址欄位；以及 指示是執行路徑可達性檢查還是執行前綴可達性檢查的1位元組可達性標誌欄位。
11. 一種用於識別計算機網絡中的邊緣節點交換裝置之間的可靠路由 的方法，包括識別指示到子網的進入點的用戶邊緣(CE)節點；識別在指示到核心網絡的進入點的服務提供商邊緣(PE)節點和所述 子網之間採用的網間路由協議和網內路由協議中的至少一種，所述核心網 絡可操作用於互連與到備用子網的進入點相對應的多個其他PE節點；如果所述網間協議被用於所述PE節點，則建立路徑核實消息，該消息包括指示到所述CE節點的回送接口路由的自路由，還包括在所述路徑核實消息中填充指示所述CE節點的身份的擴展 共有屬性；將所述路徑核實消息通告到所述PE，該通告可操作用於使得 所述PE能夠進一步將所述路徑核實消息通告到網絡中的其他CE;確定接收所述路徑核實消息的所述其他CE將採用每CE可達 性檢查還是每前綴可達性檢查；以及據此基於所述確定在所述路徑核實消息中設置可達性指示 符，所述接收方PE響應於所述可達性指示符以使得如果所述可達性標誌被設置為每前綴檢查，則基於所述 擴展共有屬性將所述路徑核實消息的前綴關聯到所述CE節點的 身份，每個接收方CE可操作用於將指示接收到的路由的前綴與 所述發起方CE相關聯；以及如果所述可達性標誌被設置為每CE檢查，則基於所述擴展共有屬性將所述路徑核實消息的接收者CE與所述CE節點 的身份相關聯；如果所述網間協議被用於所述PE，則建立具有所述擴展共有屬性的路徑核實消息，所述建立還包括用所述CE節點的身份填充所述擴展共有屬性，所述PE節點 響應於所述擴展共有屬性以從所述CE接收所述擴展共有屬性並將其 通告到網絡中的後續節點。
12. —種數據通信裝置，包括路徑核實處理器，其可操作用於建立可操作用於從發起者到目的地的發送的路徑核實消息；所述路徑核實消息中的至少一個屬性，其適合於將所述發起者的身份 存儲在所述路徑核實消息中，該消息以不受後續路由操作幹擾的非易失性方式被存儲；以及網絡接口，其可操作用於將所述路徑核實消息經由至少一個中間交換裝置發送到所述目的地，所述路徑核實消息可操作用於在所述發送成功的 情況下在所述目的地處被接收，所述目的地可操作用於通過恢復所述存儲 的身份來從所述接收到的路徑核實消息中恢復所述發送發起者的身份。
13. 如權利要求12所述的數據通信，其中所述目的地可操作用於基於 所述恢復的發起者的身份將所述目的地和所述發起者之間的路徑指定為經 核實的路徑。
14. 如權利要求13所述的數據通信，還包括備用接收者節點，該備用 接收者節點可操作用於在到所述目的地的發送不成功的情況下，將所述發 起者識別為到所述目的地的無效路由路徑。
15. 如權利要求14所述的數據通信，其中所述發起者是本地用戶邊緣(CE)路由器，所述目的地是遠程CE路由器，所述發起者和所述目的地 通過包括至少一個提供商邊緣(PE)路由器的路徑互連，所述PE路由器 被耦合到共同限定核心網絡的多個PE路由器，所述核心網絡可操作用於 採用所述路徑核實消息來將所述發起者的身份發送到所述目的地。
16. 如權利要求15所述的數據通信，其中所述路徑核實消息還包括可 操作用於在所述交換裝置之間傳輸控制信息的屬性，所述屬性包括指示所 述路徑核實消息的發起者的擴展共有欄位。
17. 如權利要求16所述的數據通信，其中所述路徑核實消息還包括可 達性標誌，該可達性標誌指示基於前綴或基於CE的可達性檢查。
18. 如權利要求12所述的數據通信，其中所述路徑核實消息包括根據 預定協議的屬性，所述存儲還包括在所述路徑核實消息中標識保留屬性，該保留屬性可操作用於在發送 期間傳播到每個路由器；將所述發起者的地址作為所述身份存儲在所述保留屬性中； 將指示前綴或路徑路由的可達性指示符存儲在所述保留屬性中；以及 識別所述路由消息的發起路由器。
19. 如權利要求18所述的數據通信，其中所述裝置是邊緣路由器，包 括用戶邊緣和提供商邊緣，其中所述用戶邊緣路由器標識到由用戶VPN 邊界劃界的自治系統的進入點，而所述提供商邊緣路由器標識到對網際網路 服務提供商劃界的核心網絡的進入點。
20. —種具有可操作用於存儲電腦程式邏輯的計算機可讀介質的計 算機程序產品，所述電腦程式邏輯被包含在其上編碼的電腦程式代碼 中並用於識別網絡路徑，所述電腦程式代碼包括用於建立可操作用於從發起者到目的地的發送的路徑核實消息的計算 機程序代碼；用於將所述發起者的身份存儲在所述路徑核實消息中的電腦程式代碼，該消息以不受後續路由操作幹擾的非易失性方式被存儲；用於將所述路徑核實消息經由至少一個中間交換裝置發送到所述目的 地的電腦程式代碼，所述路徑核實消息還包括可達性標誌，該可達性標 志指示基於前綴或基於CE的可達性檢查；用於在所述發送成功的情況下，在所述目的地處接收所述路徑核實消 息的電腦程式代碼；用於通過恢復所述存儲的身份來從所述接收到的路徑核實消息中恢復 所述發送發起者的身份的電腦程式代碼；用於根據網內邊界協議和網間邊界協議之一來傳輸所述路徑核實消息 的電腦程式代碼；用於在採用所述網間邊界協議的情況下，將可達性指示符分配給回送 自路由並將所述自路由經由所述網內邊界協議傳播到其他交換裝置的計算 機程序代碼；以及用於在採用所述網內邊界協議的情況下，將所述發起者指示符分配給 去往其他路由裝置的後續路徑核實消息的電腦程式代碼。
全文摘要
用戶邊緣(CE)到CE裝置核實檢查從可用CE發起作為一組路徑核實消息的路由，所述一組路徑核實消息想去往為遠程VPN提供服務的遠程CE路由。在路徑核實消息的屬性中包括的擴展共有屬性存儲了發起方CE路由器的身份。路徑核實消息通過網絡傳播，並傳輸發起方CE路由器的身份，這是因為發起者身份不會被後續路由所覆寫。在遠程CE接收到後，可以從擴展共有屬性中確定發起者。另外的可達性欄位也被包括在擴展共有屬性中並指示是每CE還是每前綴適合於所考慮的特定路由。以這種方式，CE-CE連接檢查識別出從其他CE可達的CE。因此，這種機制允許基於每CE或每前綴可達性的路由可達性聚集。
文檔編號H04L12/56GK101099340SQ200680001672
公開日2008年1月2日 申請日期2006年1月31日 優先權日2005年2月1日
發明者戴維·D·沃德, 斯特凡諾·普雷維蒂, 詹姆斯·N·古伊查德, 讓-菲利普·瓦瑟爾 申請人:思科技術公司