利用路由優先級值的動態重定義的可擴展路由策略結構的製作方法

2023-09-23 07:15:30 1

專利名稱：利用路由優先級值的動態重定義的可擴展路由策略結構的製作方法
技術領域：
本發明涉及計算機網絡，更具體地，涉及在計算機網絡中路由數據。
背景技術：
計算機網絡是交換數據以及共享資源的多個互連計算機的集合。在基於數據包 (packet)的網絡(諸如網際網路)中，計算裝置通過將數據分成多個稱為數據包的小塊來傳 遞數據。這些數據包各自通過網絡從源裝置路由到達目的裝置。目的裝置從這些數據包中 提取數據，並將這些數據組合成其初始形式。將數據分成多個數據包使得源裝置能夠只重 新發送在傳輸過程中可能丟失了的那些單個的數據包。計算機網絡中的一類計算機裝置(稱為路由器)負責通過計算機網絡將各數據包 從發出每個數據包的源裝置路由到達所述數據包去往的目的裝置。為了路由這些數據包， 計算機網絡中的每個路由器均可以存儲描述通過網絡從每個源裝置到達每個目的裝置的 路由的信息。這些路由可以包括通過網絡的多個「跳」，其中每條路由的第一跳用於標識源， 其後的每條路由的一個或多個中間跳用於標識中間裝置(諸如路由器)，而每條路由的最 後一跳用於標識目的地。這些路由器可以執行諸如邊界網關協議(BGP)的路由協議來相互 交互路由，從而了解該計算機網絡中的所有路由(其可以稱為網絡拓撲)。在了解了該網絡拓撲之後，每個路由器均可以對該網絡拓撲進行解析來選擇從給 定源到達給定目的地的一條路徑。通常，可以利用多條路由來從源到達給定目的地，且每個 路由器均可以通過稱為路由解析的處理來選擇這些交疊路由中的一條。這些路由器可以執 行由每個路由器執行的特定路由協議定義的默認形式的路由解析，或者備選地可以執行定 制形式的路由解析。為了定製路由解析處理，網絡管理員或其他用戶可以定義在路由解析過程中影響 路由器的路由選擇的策略。例如，管理員可以定義有關對等裝置(peer)的信任等級的策 略，其中，例如根據源是已經通過驗證的或是未知或無效的來從該策略了解路由。又例如， 為了考慮路由是否源自用戶、對等裝置或轉接提供商，管理員可以定義強制進行路由決定 的策略。因此，在進行路由解析時，通常強制路由器評估豐富且複雜的變量的集合以對路由 進行排序和選擇。儘管定製可以使網絡管理員能夠設計出路由器如何進行路由解析，例如， 以滿足特定的合同性商務協議或契約，但是定義和維護這些策略會進一步增加已經超負荷 的網絡管理員的負擔。儘管這些策略在如何匹配路由方面非常豐富，但是在確定分配給這些路由的優先 級時卻存在著挑戰，這是因為他們最終都必須由路由協議進行排序。此外，許多傳統的路 由協議(例如，BGP)在允許根據從開始就未被考慮的任意標準進行任意排序方面不是很靈 活。從而，試圖定義路由的複雜排序的策略通常最終會迫使管理員來定義所有經過考慮的 狀態和變量的交叉乘積的窮舉。這樣的策略會變得非常大並且變得難以管理，尤其是從人 為因素以及機器資源方面考慮。例如，考慮以下偽碼來定義基於一個數或變量V1 Vn分配本地優先級值的策略(policy)，其中每個變量都具有「M」個狀態，S1 Sm :policy {when [ (V1 = = S1) && (V2 = = S1) &&... (VN = = S1) ] then local_pref = 1 ；when [ (V1 == S2)&&(V2 == S^M— (VN == S1)] then local_pref = 2 ；
when [ (V1 = = S2) && (V2 = = S2) &&... (VN = = S1) ] then local_pref = 3 ；
…when [ (V1 == SM)&&(V2 == SM)&& …(VN == Sm)] then local_pref = N*M ；} end policy ；考慮上述用於定義策略的偽碼，需要定義多個本地優先級示例以說明變量V1 Vn 的狀態S1 Sm的每個變量組合。具體地，如上所述，該示例策略由用於定義等於變量數量 N和狀態數量M的交叉乘積的本地優先級值的多條線路組成。因此，這些類型的策略會變得 非常大並且變得難以管理，尤其是從人為因素以及機器資源方面考慮。

發明內容
總體上，本發明描述了網絡裝置在進行路由解析過程中動態重新定義對路由進行 排序所根據的優先級值的技術。即，路由協議優先級值可以集合多個用戶定義的變量，並可 以在路由解析過程中被動態看做單個基本值(atomic value)，從而符合路由協議的要求。 諸如路由器的網絡裝置可以實現這些技術以在人為可用性方面對路由器進行改進，從而只 需輸入很少的命令或規則來定義用於在路由解析過程中的交疊路由之間進行優先級選擇 的策略。本文中使用的這些交疊路由指的是(例如，利用地址或地址前綴)到達或指定同 一目的地的路由。路由器可以進行路由解析以選擇或「解析」這些交疊路徑中的一條，通過該路逕到 達目的地址或地址前綴。在一些實例中，路由器可以基於每條交疊路由的多個特性的比較 來選擇這些交疊路由中的一條。這些特性中的每一個均可包括兩個或多個狀態，這就導致 了唯一組合(unique combination)的多樣性。除了輸入定義將這些唯一組合中的每一個均映射到特定的優先級值的策略的數 據以外，路由器還可以實現在本公開中描述的技術，以動態地將如由路由協議定義的基本 的優先級值重新定義為兩個或更多的比特欄位，其中，每個比特欄位各自代表對應的一個 路由特性，並定義該對應的一個路由特性的狀態的優先級值。這些技術可以使管理員與用 戶界面進行交互以輸入數據，該數據指定了用於定義比特欄位和路由特性之間的映射的線 性(而不是指數)數量的規則。因此，這些技術可以在繼續允許路由協議將路由優先級值 看作單個基本值的同時，通過使用較少的規則或命令使能映射的說明而在人為可用性方面 對路由器進行改進，從而避免了對路由協議實現的改變。在操作過程中，路由器可以接收根據諸如邊界網關協議(BGP)的路由協議定義多 條路由的數據或信息。路由器還可以存儲定義包含上述規則集合的策略的數據或信息。該 策略通常可以動態地將優先級值或由路由協議定義的其它量度或屬性(其通常被服從路 由協議的軟體當作是整數值)重新定義為多個比特欄位。此外，由裝置的用戶界面支持的 語法可以對該動態重新定義進行應用和識別，而對該裝置的下層(underlying)路由處理 是透明的。
例如，用戶界面可以支持其中的策略具有比特欄位示例的結構，該比特欄位示例 映射用於將整數優先級值表示為兩個或更多比特欄位的多個位的特定連續部分。於是，該 策略可以將這些比特欄位中的每一個都映射至與給定路由相關的特性。這些所謂的路由特 性可以包括定義該路由器與負責生成和傳輸路由數據的路由器之間關係的鄰近關係、表示 通告路由是否已經通過驗證的驗證狀態、通告路由的帶寬以及其它共同路由特性。於是該 策略可以將映射定義為多個子映射，其中每個子映射都將與給定的一個比特欄位相關的路 由特性的所有已知或可能的狀態映射至與狀態相關的優先級值。換言之，該策略為每個比 特欄位定義子映射，以將路由特性的每個已知或可能的狀態映射至對應的優先級值。在這 方面，該策略包括一組以每個路由特性的可能狀態的相加得到而不是相乘得到的量為階的 規則。路由器可以將該策略應用於新接收的路由，以確定路由的優先級值。例如，路由器 可以接收定義新路由的BGP更新消息並為該路由確定優先級值(在與BGP有關的領域中稱 為本地優先級值)。路由器可以基於BGP更新消息確定被該策略映射至比特欄位的路由特 性的每一狀態，並應用該策略來將這些狀態中的每一個映射至對應的優先級值。然後，路由 器可以將本地優先級值中的邏輯定義的每個比特欄位設置為對應的優先級值，並將這些本 地優先級值與例如路由表中的路由進行關聯。然後，路由器可以使用該本地優先級值來解 析通過網絡的路由。在路由解析過程中，路由器可以將該本地優先級值看作或當作整數。 即，對於交疊路由，在路由解析過程中的路由器可以選擇那些具有較高本地優先級的交疊 路由。這些技術可以使能對路由解析過程的控制，這是因為路由器可以更為有效地指定一 種策略，該策略以允許一個以上路由特性對本地優先級值的值產生影響的方式定義路由的 優先級值。如下文中的詳細描述，該影響可以促進對路由解析的優先級控制。在一個實施例中，一種方法包括利用網絡中的路由器存儲描述多條路由的信息， 其中，每條路由均定義通過網絡到達目的地的跳的序列；以及利用該路由器存儲定義規則 的數據，該路由器通過該規則確定多條路由中至少一條的本地優先級值，其中，所述本地優 先級值被由路由器實現的路由協議指定為整數值，其中，該路由器在路由解析過程中根據 路由協議利用該本地優先級值對一條或多條路由進行排序和選擇，以及其中，這些規則根 據由路由協議指定的整數值將本地優先級值重新定義為兩個或更多比特欄位，以及其中， 這些規則將每個比特欄位與不同的路由特性進行關聯，並針對每個不同的路由特性定義將 比特欄位優先級值與對應的路由特性的每個可能的狀態進行關聯的映射。該方法還包括利 用路由器確定由映射定義的每個不同路由特性的狀態，利用路由器，通過使比特欄位優先 級值中的一個與策略映射中的所確定的狀態相關聯來設置本地優先級值的兩個或更多比 特欄位中的每一個，從而確定本地優先級值的整數值，以及利用路由器將至少一條路由與 本地優先級值的所確定的整數值進行關聯。在另一實施例中，一種路由器包括至少一個接口卡，用於根據路由協議接收路由 協議消息，每個接口卡均定義描述多條路由中的一條或多條的信息，其中，每條路由均定義 通過網絡到達目的地的跳的序列。該路由器還包括控制單元，用於存儲定義規則的數據， 該路由器通過該規則確定多條路由中至少一條的本地優先級值，其中，優先級值被由路由 器實現的路由協議指定為整數值，其中，該路由器在路由解析過程中根據路由協議利用該 優先級值對一條或多條路由進行排序和選擇，以及其中，這些規則將由路由協議指定的本
8地優先級值重新定義為兩個或更多比特欄位，以及其中，這些規則將每個比特欄位與不同的路由特性進行關聯，並針對每個不同的路由特性定義將比特欄位優先級值與對應的路由 特性的每個可能的狀態進行關聯的映射。所述控制單元還確定由映射定義的每個不同的路 由特性的狀態，通過使比特欄位優先級值中的一個與映射中的所確定的狀態相關聯來設置 本地優先級值的兩個或更多比特欄位中的每一個，並將至少一條路由與本地優先級值的所 確定的整數值進行關聯。在另一實施例中，一種網絡系統包括第一自治系統，包括第一路由器；以及第二 自治系統，包括第二路由器。第二路由器包括至少一個接口卡，用於根據路由協議從第一 路由器接收路由協議消息，每個接口卡均定義描述多條路由中的一條或多條的信息，其中， 每條路由均定義通過網絡到達目的地的跳的序列；以及控制單元，用於存儲定義規則的數 據，該路由器通過該規則確定多條路由中至少一條的本地優先級值。所述優先級值被由第 二路由器實現的路由協議指定為整數值，其中，第二路由器在路由解析過程中根據路由協 議利用該優先級值對一條或多條路由進行排序和選擇。這些規則將由路由協議指定的本地 優先級值重新定義為兩個或更多比特欄位。這些規則還將每個比特欄位與不同的路由特性 進行關聯，並針對每個不同的路由特性定義將比特欄位優先級值與對應的路由特性的每個 可能的狀態進行關聯的映射。控制單元還確定由映射定義的每個不同路由特性的狀態，通 過使比特欄位優先級值中的一個與映射中的所確定的狀態相關聯來設置本地優先級值的 兩個或更多比特欄位中的每一個，並將至少一條路由與本地優先級值的所確定的整數值進 行關聯。在另一個實施例中，一種計算機可讀存儲介質包括使可編程處理器執行以下操 作的指令利用網絡中的路由器存儲描述多條路由的信息，其中，每條路由均定義通過網絡 到達目的地的跳的序列，以及利用該路由器存儲定義規則的數據，該路由器通過該數據確 定多個路由中至少一個的本地優先級值。本地優先級值被由路由器實現的路由協議指定為 整數值。該路由器在路由解析過程中根據路由協議利用該本地優先級值對一條或多條路由 進行排序和選擇。這些規則根據由路由協議指定的整數值將本地優先級值重新定義為兩個 或更多比特欄位。這些規則還將每個比特欄位與不同的路由特性關聯起來，並針於每個不 同的路由特性定義將比特欄位優先級值與對應的路由特性的每個可能的狀態進行關聯的 映射。這些指令還使可編程處理器利用路由器確定由映射定義的每個不同的路由特性的狀 態，利用路由器，通過使比特欄位優先級值中的一個與映射中的所確定的狀態相關聯來設 置本地優先級值的兩個或更多比特欄位中的每一個，從而確定本地優先級值的整數值，以 及利用路由器將至少一條路由與所確定的本地優先級值的整數值進行關聯。本發明的一個或多個實施例的細節將在下面的附圖和說明書中進行描述。本發明 的其它特徵、目的和優點將通過了解說明書和附圖以及權利要求書而變得顯而易見。


圖1是示出示例性網絡系統的框圖，在該網絡系統中，路由器實現本公開中描述 的技術，以動態地重新定義在路由解析中由路由協議使用的優先級值。圖2是示出圖1的路由器的示例性實施例的框圖。圖3是示出路由器在實現本公開中描述的技術時的示例性操作的流程圖。
圖4是示出定義路由和相關本地優先級值的示例性路由協議消息的框圖。圖5A 圖5B是更詳細地示出包含在路由協議消息中的示例性屬性類型欄位和對應的示例性屬性值欄位的框圖。
具體實施例方式圖1是示出示例性網絡系統10的框圖，在該網絡系統中，路由器12A實現了本公 開中描述的技術，以動態地重新定義在路由解析過程中使用的優先級值。如下所述，路由器 12A可以實現這些技術以在路由器12A的人為可用性方面進行改進，從而只需輸入很少的 命令和/或不複雜的結構性數據來定義用於在路由解析過程中在交疊的路由之間進行優 先選擇的策略。本文中使用的這些交疊路由指的是到達同一目的地址或地址前綴的路由。路由器12A可以進行路由解析來選擇或「解析」出這些交疊路徑中的一條，通過該 路逕到達目的地址或地址前綴。在一些實例中，路由器12A可以基於每條交疊路由的多個 特性的比較來選擇這些交疊路由中的一條。為了影響該路由選擇處理，路由協議標準通常 將本地優先級變量定義為單個基本的整數值，該值可以被引入由路由協議應用的排序和選 擇算法中。通過將不同的本地優先級值與不同的路由進行關聯，管理員能夠將網絡中的路 由器配置為基於這些路由的特性而優先選擇某些路由。然而，這些特性中的每一個都可能 表示為兩個或更多的狀態(例如，信任或不信任，內部或外部)，這造成了要求管理員根據 路由協議標準指定交叉乘積這樣多的唯一組合。相反，路由器12A可以實現本公開中描述的這些技術，以動態地將整數優先級值 定義為包含兩個或更多比特欄位的數據字，其中，每個比特欄位各自代表對應的一個路由 特性，並定義該特定路由特性的優先級值，而不要求管理員輸入定義將這些唯一組合中的 每一個映射到由路由協議確認的特定整數優先級值的策略的數據。因此，管理員可以獨立 地定義每個路由特性的排序，然後，路由器將其透明地聚集到路由協議優先級值的比特字 段中，以作為單個基本值輸入到路由協議中。這些技術可以使管理員能夠首先輸入獨自定 義任意比特欄位和對應的一個路由特性之間的線性映射的數據，隨後輸入作為獨立本地優 先級值的針對路由特性的策略數據，而無需考慮其他的特性。在操作過程中，路由器12A根 據所定義的映射將不同的路由特性的本地優先級值動態地組合到比特欄位中，從而以符合 路由協議標準要求格式的格式計算出單個的合成本地優先級值，例如，基本的整數本地優 先級值。以此方式，滿足了與路由協議標準兼容的要求，而這些技術使得用戶可不必將指定 用於路由協議的本地優先級值的策略數據定義為路由特性及其相應的可能狀態的多種唯 一組合。在這方面，路由器12A可以實現這些技術，以在人為可用性方面對路由器12A進行 改進，同時避免了在根據單個的本地優先級值對路由進行排序和選擇時對路由協議實現的 下層路由協議或算法進行改變。儘管參照特定網絡裝置(例如，路由器12A)進行了描述，但是這些技術還可以利 用能夠執行或實施路由協議的任意類型的網絡裝置(通過其來接收描述通過網絡的路由 的信息)來實現。此外，以下的公開參照被稱為邊界網關協議(BGP)的特定路由協議和由 稱為本地優先級(「l0Cal_pref」)值的由BGP定義的優先級值來描述這些技術。更多的 關於BGP和本地優先級值以及BGP路由解析或決定處理的信息可以在2006年1月期的題 為"A Border GatewayProtocol 4 (BGP-4)，，的 Request For Comments (RFC) 4271 中找至Ij，其全部內容通過引用結合於此。然而，這些技術也可以參照其他的路由協議(諸如中間系 統到中間系統(IS-IS)路由協議、內部邊界網關協議(iBGP)、開放最短路徑優先(OSPF)路 由協議以及增強型內部網關路由協議(EIGRP))來實現，以將通常由路由協議定義的優先 級或其他值動態地重新定義成作為有多個的兩個或更多比特欄位的整數值。如圖1所示，網絡系統10包括自治系統14A( "AS 14A」)和自治系統14B( "AS 14B」)。自治系統14A、14B中的每一個(「自治系統14」或「AS 14」)可以包括可由一個 或多個地址前綴尋址的獨立計算機網絡。通常，AS 14包括基於數據包的計算機網絡，用 於實現第三層(L3)的基於數據包的協議，諸如網際網路協議(IP)，其中，L3是指開放系統互 連(OSI)模型的第三層。為此，AS 14每一個均可稱為「基於數據包」的網絡或「IP」網絡。 對於基於數據包的網絡，AS 14可以利用一個或多個IP位址前綴進行尋址，其可以根據在 2006 年 8 月期的題為 「Classless Inter-domainRouting(CIDR) :The Internet Address Assignment and AggregationPlan，，的 Request For Comments 4632 中描述的注釋進行定 義，其全部內容通過引用結合於此。AS 14每一個均可以包括較大的公共網絡(諸如網際網路)的子網絡或簡稱子網。通 常，單獨的月艮務提供商(諸如Verizon通信公司，Verizon Communications Incorporated) 將其網絡作為單個的自治系統進行維護和運行。然而，在一些實例中，單獨的服務提供商可 以將其網絡作為兩個或更多的自治系統進行維護和運行。這種多重AS示例通常只在一個 服務提供商要求或購買另一服務提供商的網絡但又不出於商業或技術原因而組合這兩個 AS時才發生。為了示例，本文中假設單獨的服務提供商(諸如Verizon通信公司)維護並 運行AS 14A，而另一服務提供商(諸如美國電話電報公司，AT&T)維護並運行AS 14B。盡 管在圖1中被示為連結在一起的雲，但是AS 14中的每一個都可以跨越較大的地理距離，並 有可能跨越大陸(甚至大洋，從而到達多個大陸)。如圖1的實例進一步所示，AS 14A包括路由器12A，而AS 14B包括路由器12B和 12C。路由器12A 12C( 「路由器12」)如果不是完全相同，也是在功能操作方面彼此類似 的，儘管路由器12每個均可以包括實現相似或相同功能的不同的硬體和/或軟體。在任何 情況下，每個路由器12通常都駐留在相應的AS 14的邊緣，且路由器12A經由相應的網絡 鏈路16A和16B連接至路由器12B和12C。通常，這些鏈路16A、16B( 「鏈路16」)包括高帶 寬或高容量的網際網路鏈路，其包括較大的公共網絡(諸如網際網路)的中樞鏈路。為此，鏈路 16可以稱為中樞鏈路16。路由器12每個均實施路由協議(諸如BGP)來交換描述通過其各自的AS 14的路 由的拓撲數據。該交換通常根據網絡的拓撲改變而採取路由通告或路由撤回的形式。路由 被表示為到達網絡目的地(例如由網絡地址或網絡地址前綴表示)的多個跳(例如，由地 址表示)。路由器12可以包括資料庫，用於存儲定義通過其各自AS14的路由的數據。這些 路由稱為內在(internal)或內部(interior)路由。路由器12可以實施其他的路由協議 以了解這些內部路由。這類內部路由協議通常可以稱為內部網關協議(IGP)。IGP通常包 括用在自治系統中的任何路由協議。示例性的IGP包括路由信息協議(RIP)、內部網關路由 協議(IGRP)以及上面提到的OSPF和IS-IS路由協議。與IGP類的路由協議不同，BGP通常進行工作以在不同自治系統的路由器之間進 行路由交換。路由器12可以利用一個或多個已了解的路由來了解經由一個或多個IGP的內部路由，並生成可以包含資料庫或其他存儲裝置的路由信息庫(RIB)。在一些情況中，路由器12在將一個或多個已了解的路由插入RIB中之前可以拒絕這些路由。RIB可以存 儲路由表或其他數據結構，通過這些來存儲接受或非拒絕的路由和與插入到路由表中的每 個路由有關的路由特性。路由特性可以包括路由驗證狀態、提供路由的路由器所屬的團 體(community)、相鄰路由器的對等狀態、沿該路由的通信量消耗的最大總帶寬、當前或可 用帶寬、保留帶寬、與路由、顏色、不穩定性、傳輸介質類型、傳輸速度相關的成本、自治系統 (AS)路徑(「AS_Path」)、源路由的IGP區或等級、源協議、源示例、初始屬性(例如，BGP ORIGIN屬性或由路由器為路由定義的、或該路由可確定的、通常與之相關的其他任何特 性)。每個路由器12均可以在利用這些路由生成路由表之後根據BGP選擇存儲到路由 表的路由，以輸出至其他路由器12。路由器12可以生成稱為BGP更新消息的BGP消息，該 BGP更新消息定義單條路由(通常也可以是多條路由)以及與該路由(或該多條路由)相 關的一些路由特性。該單條路由可以代表由路由器12A選擇的從路由器12A到達特定目的 地址或地址前綴的路由。路由器12A可以例如生成表示通過AS 14A的路由或路徑的BGP 更新消息。路由器12A可以將路由器12A選擇輸出的每條路由或多條路由的BGP更新消息 發送至AS 14B。同樣，路由器12B、12C可以生成路由器12B、12C分別選擇輸出的每條路由 或多條路由的BGP更新消息，並將其傳送至路由器12A。圖1示出了作為各BGP更新消息 18A、18B( "BGP更新消息18」)從路由器12B、12C到路由器12A的這些BGP更新消息。響應於這些更新消息18，路由器12A可以首先確定為包含在BGP更新消息18中的 每條路由分配什麼樣的優先級值。該優先級值在與BGP有關的領域中稱為「本地優先級」， 而「localpref」指的是存儲表示該本地優先級值的整數的整數變量。通常，路由器12A只 為從外部對等裝置或鄰近或相鄰路由器接收到的路由分配本地優先級值，其中，那些鄰近 或相鄰路由器駐留在路由器12A所在的自治系統外部的不同自治系統中。路由器12B和 12C是這種外部BGP對等裝置的實例，因此其可以統稱為外部對等裝置12或外部BGP對等 裝置12。由於這些路由是從外部對等裝置接收的，因此根據BGP，路由器12A可以為這些路 由中的每一條分配本地優先級。路由器12A在路由解析過程中可以利用該確定的如由「localpref」變量定義的 本地優先級值，這是路由器12A選擇或解析多條交疊路由中的一條的過程。如上所述，交疊 路由可以指兩條均到達同一目的地址或地址前綴的路由。為了示出，假設由BGP更新消息 18A中的一個定義的至少一條路由和由BGP更新消息18B中的一個定義的至少一條路由以 上述方式交疊。BGP指定了七步流程來解析這些交疊路由。路由器12A可以實施這七步BGP路由解析(或「決定處理」，因為其與上文引入的 RFC 4271相關)來首先考慮與每條路由相關的整數本地優先級值。當執行BGP協議時， 路由器12A可以選擇交疊路由中與路由協議的最高本地優先級值(即，本實例中的最高整 數值)相關的一個。第二，如果兩條或更多的交疊路由與相同的本地優先級值相關，則路 由器12A嘗試基於這些交疊路由中的哪一個與最低AS路徑長度值相關聯來解決這種平局 (tie)。如果兩條或更多條交疊路由之間仍然存在平局，則路由器12A嘗試基於這些交疊 路由中的哪一個與最低初始類型值相關聯來解決這種平局。如果兩條或更多條交疊路由 之間仍然存在平局，則路由器12A接下來嘗試基於這些交疊路由中的哪一個與最低Multi_Exit_Disc (MED)值相關聯來解決這種平局。第五，如果兩條或更多條交疊路由之間仍然存 在平局，則路由器12A嘗試基於這些交疊路由中的哪一個是通過BGP而不是IGP(諸如內部 BGP(iBGP))進行了解而來解決這種平局。第六，如果兩條或更多條交疊路由之間仍然存在 平局，則路由器12A嘗試基於這些交疊路由中的哪一個與到達路由器12的最低成本相關聯 而來解決這種平局。第七，如果兩條或更多條交疊路由之間仍然存在平局，則路由器12A嘗 試基於這些交疊路由中的哪一個與最低路由器標識符(ID)值相關聯而來解決這種平局。實施BGP的路由器12可以提供該BGP路由解析或決定處理作為默認決定處理。換 言之，BGP可以要求路由器實施BGP以提供該路由解析或決定處理作為默認路由解析處理。 在這方面，默認路由解析處理包括定義默認決定處理的「彙編(complied in)」規則集。然 而，每個路由器12還可以使能設計或定製的路由解析或決定處理。路由器12提供該設計 或定製的路由解析處理來使網絡管理員出於技術和/或商業目的而偏好或選擇一條路由。例如，假設Verizon擁有AS 14A，而AT&T擁有AS 14B，Verizon可以不建立AS 14A 以進入特定地理位置，而是與AT&T (其AS 14B已經跨越了該地理位置)籤訂合同而使其承 載等於AS 14B內消耗的帶寬的一定資金的Verizon通信量。然而，Verizon路由器12A可 以從路由器12B和12C接收交疊路由，並期望總是選擇最短的路由，從而減少了消耗帶寬的 路由以降低合同成本。不利用某種形式的可定製或設計的解析處理，路由器12A就不能總 是選擇到達目的地的最低成本路由。因此，每個路由器12通常都使能設計或定製的路由解 析或決定處理。路由器12A可以包括例如用戶界面，通過該用戶界面接收定義控制或定製默 認路由解析處理的策略的數據。管理員可以通過路由策略描述語言(RPSL)來定義這 些策略，其在多個不同的RFC中均進行了定義，例如，在1999年6月期的題為「Routing PolicySpecification Language (RPSL) 」的RFC 2622中進行了定義。管理員可以與提供的 系統(provisioning system)或其他計算裝置進行交互以按照RPSL生成策略，其中，該提 供的系統或其他計算裝置可以將其轉換成路由器配置腳本或文件，然後該路由器配置腳本 或文件作為「策略」由管理員經由用戶界面輸入至路由器12A。在任一情況中，管理員通常 都通過定義將特定路由映射至特定本地優先級值的策略來控制默認BGP路由解析處理。以 此方式，網絡管理員可以通過向多條交疊路由中的一個而不是向其他所有的多條交疊路由 分配較高的本地優先級值來控制上述定義的路由解析處理。以此方式，路由器12可以使網 絡管理員以設定的方式控制路由解析。根據本發明的技術，路由器12A通過用戶界面接收定義比特元(bit-wise)策略的 數據，該比特元策略定義了規則，路由器通過這些規則確定單個參數的本地優先級值，該值 是由經由BGP更新消息18中的一個接收到的多條路由中的至少一條的工業標準路由協議 定義的。儘管根據工業標準，該本地優先級值被由路由器12A實施的BGP看作整數值，但是 該策略允許路由器在與用戶進行交互時將本地優先級值動態地重新定義為兩個或更多的 比特欄位。在這方面，路由器12A將本地優先級值看作關於用戶界面語法和數據表示的多 個比特欄位，但在進行路由操作過程中是根據工業標準路由協議將本地優先級值用作單個 整數值的。該策略將每個比特欄位與上述路由特性中不同的一個進行關聯，並對不同路由 特性中的每一個均定義將優先級值與對應路由特性的每個可能狀態進行關聯的映射。例如，可以將策略定義為包含比特欄位示例，該示例指示路由器12A將本地優先
13級整數欄位細分為兩個比特欄位，並將這些比特欄位中的每一個與以下兩個路由特性中相 應的一個進行關聯路由的驗證類型和相鄰關係類型。如圖1所示，AS 14A可以包括驗證 伺服器20，其包括用於存儲與特定路由相關聯的驗證狀態的驗證資料庫(圖1中未示出)。 驗證伺服器20可以用作資源公共密鑰基礎架構(RPKI)的一部分。具體地，驗證伺服器 20可以作為有關BGP領域中的RPKI的一部分以在2008年10月6日的題為「Validation ofRoute Origination in BGP using Resource Certificate PKI，，的 InternetDraft 中更 詳細地描述的方式進行工作。路由器12A可以生成驗證請求並將其傳輸給驗證伺服器20 以請求驗證伺服器20對特定路由進行驗證。獨立的驗證伺服器20被示為路由器12A可以與其進行通信以了解或確定與路由 相關的驗證狀態，路由器12A可以維護用於AS14A的內部驗證資料庫。在一些情況中，驗證 狀態可以經由BGP更新消息進行傳輸並存儲在路由表中，從而該路由表可以包括內部驗證 資料庫。在其他情況中，驗證伺服器20可以由多個AS進行維護，並用於驗證每個成員AS 的路由。備選地，驗證伺服器20可以包括網際網路路由註冊庫(IRR)。IRR可以包括存儲數 據的資料庫，該數據定義了確定和共享路由和用於配置路由器的相關信息的一個或多個互 聯網路由對象。通常，IRR用於避免網際網路服務提供商(諸如Verizon和AT&T)及其各自 的AS 14之間的問題。這些對象可以包括RPSL對象，而每個AS 14的網絡管理員可以改變 定義相應AS 14的路由對象的那些RPSL對象。其他的網絡管理員可以查詢那些未對其一 個AS 14進行維護的路由對象，而可以不對其進行改變。以此方式，IRR代表資料庫，該數 據庫可以由管理員用來進行查詢從而了解策略以及通過相鄰AS的路由。這些RPSL對象可 以定義一條路由或多條路由的驗證狀態，路由器12A可以查詢該IRR以了解特定路由的驗 證狀態。公共驗證狀態包括有效狀態、無效狀態和未知狀態。路由器12A可以利用BGP更新消息或通過查詢驗證伺服器20來了解鄰近類型。 備選地，這些鄰近關係可以定義為通常由網絡管理員指定的路由器配置的一部分。這些鄰 近關係通常可以定義與除了路由器12A所在的AS以外的不同AS的相鄰網絡裝置的商業關 系。公共類型的鄰近關係可以包括轉接(transit)關係、客戶關係和對等關係。在任一情況中，路由器12A可以確定由策略映射定義的不同路由特性中的每一個 的狀態。繼續上面的實例，路由器12A可以確定經由BGP更新消息18接收到的每條路由的 驗證狀態和鄰近關係狀態。路由器12A於是可以利用與策略映射中所確定的狀態相關聯的 優先級值中相應的一個來設置本地優先級值的兩個或更多比特欄位中的每一個。再次，關 於上述實例，路由器12A可以確定由BGP更新消息18A、有效狀態和轉接關係定義的路由中 的一條，並利用與策略映射中的有效狀態相關聯的第一比特欄位優先級值來設置由策略比 特欄位示例描述的第一比特欄位，以及利用與策略映射中的轉接關係狀態相關聯的第二比 特欄位優先級值來設置由策略比特欄位示例描述的第二比特欄位。以此方式，路由器12A 可以利用單獨的、獨立的比特欄位優先級值設置本地優先級值的動態定義的每個比特字 段。通過動態地將本地優先級值重新定義為比特欄位，路由器12A可以使管理員能夠 更容易地定義有優先級地選擇兩個或更多交疊路由所依據的策略。為了示例，假設管理員 希望首先基於驗證狀態、其次基於相鄰關係來選擇路由，管理員可以定義上述示例性策略，該策略將32位的本地優先級值的前16位示例為驗證狀態比特欄位，將32位的本地優先級 值的後16位示例為相鄰關係比特欄位。然後，管理員可以定義比特欄位示例下的將驗證路 由特性的每個可能狀態映射至第一組比特欄位優先級值的第一映射，並定義將鄰近路由特 性的每個可能狀態映射至第二組比特欄位優先級值的第二映射。例如，第一映射可以將有效狀態映射至比特欄位優先級值IO2，將未知狀態映射至 比特欄位優先級值Ol2，而將無效狀態映射至比特欄位優先級值002。第二映射可以將用 戶鄰近關係映射至比特欄位優先級值102，將對等鄰近關係映射至比特欄位優先級值012， 以及將轉接對等關係映射至比特欄位優先級值OO2。在確定了第一路由與有效狀態和轉接 關係相關聯時，路由器12A可以根據第一和第二策略映射將該路由與本地優先級值0002 OOOO16進行關聯。在確定了第二路由與有效狀態和對等關係相關聯時，路由器12A可以根 據上述兩個示例性策略映射將該路由與本地優先級值0002 OOOO16進行關聯。儘管稱為第一和第二映射，但是多個獨立的映射通常也可以稱為策略映射，從而 可以理解為組成或形成策略映射的每一特性映射或子映射。無論怎樣，該策略映射包含總 共六個映射，這些映射將有效路由特性的三個可能狀態映射至本地優先級值的較高或最高 有效位的比特欄位優先級值，並將鄰近關係路由特性的三個可能狀態映射至本地優先級值 的較低的一半或最低有效位的比特欄位優先級值。換言之，策略映射包括多個映射，這些映 射隨著每個路由特性的可能狀態的總和而線性增長。 此外，儘管以上參照二進位和十六進位表示進行了描述，諸如網絡管理員的操作 者可以將這些值定義為0、1和2。從而，為了示出本公開中描述的與本地優先級值的實際計 算相關的這些技術的不同方面，示出了作為二進位和十六進位數字的表示。然而，這些技術 可以自動將這些數字的十進位表示轉換成如上所示的通常用於大多數計算機的二進位和 十六進位表示。在根據這些技術設置或確定了每條路由的本地優先級值後，路由器12A可以將每 條路由與所確定的本地優先級值進行關聯。路由器12A可以通過將本地優先級值以及每條 路由存儲到RIB的路由表中而將這些本地優先級值與各路由進行關聯。路由器12A接下來 可以進行路由解析以對交疊路由進行解析。如上所述，假設經由獨立的BGP消息18接收到達同一目的地的至少兩條路由。為 了示出，進一步假設，根據上述技術將第一交疊路由與所確定的本地優先級值0002 OOOO16 進行關聯，再次根據上述技術將第二交疊路由與所確定的本地優先級值0002 OOOl16進行 關聯，路由器12A可以選擇第二交疊路由，這是因為與該第二交疊路由相關聯的本地優先 級值大於與第一交疊路由相關聯的本地優先級值。換言之，路由器12A執行上述默認BGP 路由解析或決定處理，以解析這兩條交疊路由，從而影響該默認、內置或彙編的BGP決定處 理，以利用該動態地重新定義的本地優先級值。BGP決定處理繼續將該本地優先級值看作整數，因此，無需將該BGP決定處理修改 為適應這些技術。即，例如，BGP決定處理將與第一交疊路由相關聯的第一本地優先級值看 作81931(|，以及將與第二交疊路由相關聯的第二本地優先級值看作81941(|。由於8194大於 8193，因此，路由器12A根據BGP決定處理選擇第二交疊路由，而不是第一交疊路由。然而， 通過根據這些技術對本地優先級值進行重新定義，管理員只需定義一種策略，該策略包括 線性數量的映射而不是例如三乘三階的映射或九個映射的指數數量的映射。
儘管上述實例只考慮了具有較少幾個狀態的路由特性的兩個比特欄位，在管理員希望控制對各具有多個狀態的多個路由特性進行路由解析時，這些技術基本上可以改進人 為可用性方面。例如，考慮了在管理員期望基於三個路由特性來控制路由解析的情況，其 中，每個路由特性都具有10個可能狀態。根據這些技術，管理員可以定義一種策略，該策 略將本地優先級值重新定義到三個比特欄位中並指定三個子映射，每個子映射均定義將10 個狀態中的每一個都映射至比特欄位優先級值的10條規則。因此，該策略利用等於30或 30的階個規則定義策略映射，30與每個路由特性的可能狀態的總和(即，10+10+10)成線 性。除了將映射定義為10X10X10(或IO3)階的(其等於1000個映射)指數個規則或命 令以外，管理員還可以將映射定義為30個規則的集合，這相對於控制路由解析處理可以大 大改進路由器12A的人為可用性。在以上述方式對這些交疊路由進行解析之後，路由器12A可以經由一個或多個路 由協議(諸如IBGP)將解析出來的路由傳送至AS 14A。這些內部通信在圖1中示出為消息 22。路由器12A可以傳遞以上確定的本地優先級值，而AS 14A內部的其他網絡裝置(例如 路由器)可以將該本地優先級值看作整數。在這方面，這些技術不需要對BGP協議或其他 任何協議進行改變，並且其他內部路由器可以利用該本地優先級值，這是因為這些技術只 動態地邏輯地重新定義了該本地優先級值，而不改變或擴展BGP更新消息或利用該本地優 先級值的任何其他消息。因此，這些技術保持了與其他路由器的功能互用性。此外，這些技 術不需要任何附加的屬性或對更新消息進行任意添加，從而可以保存AS 14A的帶寬。圖2是示出圖1的路由器12A的示例性實施例的框圖。如圖2所示，路由器12A 包括具有路由平面26A和轉發平面26B的控制單元24。控制單元24可以包括實現本公開 中描述的技術的硬體和軟體的任意組合。控制單元24可以包括一個或多個處理器、特定用 途集成電路(ASIC)、集成電路或任何其他處理或控制單元或元件或其組合、以及存儲器或 存儲裝置。在一些情況中，存儲器或存儲裝置(通常例如，計算機可讀存儲介質)可以包括 使可編程處理器執行本文中所述技術的上述指令。這些指令可以構成計算機或軟體程序或 由可編程處理器執行來實現本文中所述的功能(包括屬於本公開中這些技術的功能)的其 他可執行模塊。路由平面26A通常可以代表控制單元24的負責實現路由協議、存儲和保存反映網絡拓撲的數據(諸如路由信息)、以及解析交疊路由的一部分。路由平面26A可以稱為控制 平面，這是因為路由平面26A通過關於通用路由功能(諸如路由解析)的決定來提供控制。 路由平面26A還可以稱為路由引擎，這是因為路由平面26A在很多方面均提供執行該功能 的一個或多個引擎或模塊。轉發平面26B通常可以代表控制單元24的負責轉發數據單元(諸如數據包)的 另一部分。轉發平面26B可以從路由平面26B接收解析得到的路由，並經由解析的路由轉 發數據包。轉發平面26B可以包括專門設計用於儘可能快(更好地表述為，高速)地轉發 數據包的專用硬體，以提供高帶寬轉發。轉發平面26B還可以稱為轉發引擎，這是因為轉發 平面26B可以提供專用硬體和/或軟體模塊來轉發數據包。轉發平面26B還可以稱為數據 平面，這是因為轉發平面26B處理數據單元(諸如數據包)的轉發，而路由平面26A處理通 過路由功能的控制或決定。儘管上述描述為駐留在同一控制單元(例如控制單元24)中，但是路由平面26A和轉發平面26B可以各自實現為，路由平面26A在第一控制單元中執行或實現，而轉發平面 26B在與第一控制單元不同或完全分離的第二控制單元中執行或實現。因此，這些技術不應 該限於圖2所示的示例性實施例。路由器12A還包括多個接口卡(IFC)28A 28N( "IFC 28」)，用於經由入站鏈路 30A 30N( 「入站鏈路30」)和出站鏈路32A 32N( 「出站鏈路32」)傳送數據包。每個 IFC 28均可以經由開關連接至控制單元24並(圖2中未示出)與控制單元進行通信。該 開關可以包括能夠可通信地連接一個或多個端點(例如IFC 28和控制單元24)的任何通 信介質。IFC 28被示為經由鏈路34連接至控制單元24。這些鏈路34可以包括或者也可 以不包括上述開關。在路由器12A不包括該開關的情況中，鏈路34每一個均包括IFC 28 與控制單元24進行通信所通過的專用鏈路或總線。轉發平面26B可以接收經由鏈路34從 IFC 28轉發的數據包，並經由鏈路34和IFC 28將那些數據包轉發到出站鏈路32上。以此 方式，轉發平面26B提供了路由器12A的轉發功能。路由平面26A包括用戶界面模塊36 ( "UI模塊36」)、路由策略模塊38、BGP模塊 40 ( "BGP 40」)和路由解析模塊42。UI模塊36包括提供管理員(諸如管理員44)可以用 來交互以錄入或輸入定義策略46的數據的一個或多個用戶界面的硬體和/或軟體模塊。UI 模塊36可以包括圖形用戶界面(GUI)或命令行界面(CLI)。路由平面26還可以包括存儲 定義策略46的數據的策略資料庫48 ( 「策略DB 48」)。路由器策略模塊38可以包括將一個或多個策略46應用至從BGP模塊40接收到 的路由50中的硬體和/或軟體模塊。策略46可以包括將本地優先級整數值動態地重新定 義為多個比特欄位的至少一個上述策略。路由策略模塊38可以根據本公開中描述的這些 技術應用策略46中的一個以返回與路由50相關的本地優先級值52。BGP40可以包括實現 BGP以實現至少接收和處理BGP更新消息(諸如BGP更新消息18)、生成和轉接BGP更新消 息、另外還保存路由表54的硬體和/或軟體模塊。路由平面26A還可以包括路由信息庫 56 ( "RIB 56」)，其可以包括存儲路由表54的資料庫或其他存儲裝置。儘管示出為兩個獨 立的資料庫48和56，但是路由平面26A可以包括同時存儲策略46和路由表54的單個數據 庫。圖2中示出的獨立資料庫48和56僅用於示例性目的。路由解析模塊42可以包括根據BGP執行路由解析的硬體和/或軟體模塊。換言 之，路由解析模塊42可以實現以上結合的RFC4271中所述的默認決定處理。路由解析模 塊42可以執行該路由解析處理，以如上所述在交疊路由之間進行選擇，並將所選擇的一個 交疊路由建立到轉發平面26B的轉發表58中。轉發平面26B可以包括轉發信息庫(「FIB 60」)，其包括存儲轉發表58的資料庫或其他存儲裝置。為了建立路由，路由解析模塊42可 以向FIB 60發出命令62，以使FIB 60利用定義與給定的源地址或地址前綴相關的下一跳 的項來更新轉發表58。最初，管理員44可以與由UI模塊36提供的用戶界面交互，以輸入定義策略46的 數據。儘管以上描述為直接與用戶界面進行交互，但是管理員44通常可以根據RPSL與提供 的系統或其他中間配置系統進行交互，以指定策略。然後，該中間配置系統可以將RPSL兼 容策略轉換成腳本或定義上述映射的其他數據，之後經由與由UI模塊36提供的用戶界面 進行自動交互而自動將策略46中的這一個加載到策略DB 48中。在這方面，管理員44可 以與用戶界面直接進行交互。無論怎樣，UI模塊36可以接收定義策略46的該數據並將該數據加載到將該數據存儲為策略46的策略DB 48中。然後，管理員44可以激活、啟動或使 得路由器12A開始接收數據包。轉發平面26B可以經由IFC 28和各入站鏈路30接收數據包，訪問FIB 60的轉發 表58，並確定轉發該數據包所到的「下一跳」。轉發平面26B可以從每個數據包 的報頭解析 或提取五元組，其中，五元組包括源IP位址、目的IP位址、源埠、目的埠和協議標識符。 轉發平面26B可以利用五元組或其某一部分(諸如目的地址)作為密鑰以定位對應於該五 元組的轉發表58的項，從而訪問轉發表58。該項可以識別IFC 28中的一個，或備選地，在 數據包去往路由器12B的情況中，其表示數據包應該被轉發至路由平面26A。例如，轉發平面26B可以接收去往路由器12A的BGP更新消息(諸如BGP更新消 息18中的一個)。轉發平面26B可以提取五元組或其某一部分(諸如目的地址)，並訪問 轉發表58以找到表示該數據包將被轉發至路由平面26A的項。轉發平面26B可以將這一 BGP更新消息18轉發至路由平面26A。路由平面26A可以調用BGP40來處理這一 BGP更新 消息18。BGP 40可以抽取由BGP更新消息18中的一個定義的路由50，並確定是否計算該 路由的本地優先級值。BGP 40可以基於BGP對等裝置的已知配置進行該確定。如果BGP 對等裝置是外部對等裝置(例如，該對等裝置具有與和AS14A相關的AS數量不同的AS數 量)，則BGP 40可以計算該路由的本地優先級數。然而，如果BGP對等裝置被配置為內部對 等裝置(例如，該對等裝置具有與和AS 14A(或其中駐留有路由器12的AS)相關的AS數 量相同的AS數量)，則BGP 40可以確定不計算該路由的本地優先級數。由於假設了這一 BGP更新消息18是從被配置為外部BGP對等裝置的對等裝置中 接收到的，因此BGP 40決定計算該路由的本地優先級值，並提取由這一 BGP更新消息18定 義的路由。為了計算該本地優先級數，BGP 40將該路由作為路由50轉發至路由策略模塊 38，其應用策略46中的一個確定該路由50的本地優先級值。具體地，如工業標準路由協議所指定的，路由策略模塊38將根據整數動態地重新 定義本地優先級值的一個策略46應用至關於用戶交互和配置數據提供的多個比特欄位。 路由50不僅可以定義從源裝置到目的裝置的一些列跳，而且在一些情況中還定義路由特 性。備選地，路由策略模塊38可以訪問RIB 56來確定與路由50相關聯的路由特性。在任 一情況中，路由策略模塊38確定與由策略46中的一個的比特欄位示例定義的每個比特字 段相關聯的每個路由特性的狀態。基於所確定的在比特欄位示例中識別的每一路由特性中 的確定的狀態，路由策略模塊38可以利用也是由這一策略46定義的子映射確定每個動態 重新定義的比特欄位的比特欄位優先級值，如上述實例所示。在設置動態地重新定義的本地優先級值的每個比特欄位後，路由策略模塊38可 以將本地優先級值52以工業標準要求的格式返回至BGP 40。BGP 40可以在路由表54中 的為路由50創建的項中將該本地優先級值存儲為由路由協議定義的單個參數。換言之， BGP40可以利用本地優先級值52更新路由表54中為路由50保存的項，從而將本地優先級 值52與路由50進行關聯。在某一方面，路由解析模塊42可以以上述方式解析路由表54， 並將解析出的路由建立到FIB 60的轉發表58中。假設路由50包括與另一路由到達相同目的地的路由，這兩條路由(路由50和另 一路由)代表交疊路由。路由解析模塊52可以通過首先將本地優先級值看作整數值來解 析這些路由。路由解析模決52可以選擇最高本地優先級值。儘管參照選擇具有最高本地優先級值的路由進行了描述，但是路由解析模塊52可以相反地選擇具有最小本地優先 級值的路由，這可以相對於實現不同協議或對這些以及其他協議(包括BGP多出口標識 (multi-exit descriminator))進行擴展的路由解析模塊52而進行。如在上述實例中，這些技術動態地重新定義本地優先級值，但是不影響BGP 40或 路由解析模塊42的任何其他功能方面。路由解析模塊42可以以上述方式進行選擇與最高 本地優先級值相關聯的交疊路由中的一個。然而，由於路由器12A實現了本文中描述的這 些技術，因此管理員44可以控制路由解析模塊42而不輸入指數數量的命令來定義一個策 略46。相反，管理員44可以僅輸入線性數量的命令，從而這些技術可以在可用性方面對路 由器12A進行改進。在任一情況中，在將經解析的路由建立到轉發表58中時，轉發平面26B可以接收 數據包，抽取五元組或其一部分(例如，目的地址)，基於抽取的五元組或其一部分(例如， 目的地址)訪問轉發表58，在所訪問的轉發表58的項中確定與五元組或其一部分(還是例 如，目的地址)相關聯的下一跳(例如，IFC 28中的一個)，以及經由識別出的IFC 28中的 一個轉發數據包。以此方式，轉發表26B可以提供路由器12A的轉發功能以經由解析出來 的路由(通常高效地)轉發數據包。圖3是示出路由器在實現本公開中描述的這些技術的過程中的示例性操作的流 程圖。為了示例，下面將參照圖2的路由器12A描述這些技術。然而，儘管參照該特定類型 的網絡裝置(例如，路由器12A)進行了描述，但是這些技術還可以通過能夠實現路由協議 的任意網絡裝置來實現，以將整數值正常地重新定義為兩個或更多比特欄位的集合，從而 改進該網絡裝置的可用性。此外，儘管下面將參照路由器12A的特定實施例進行描述，但是 這些技術還可以應用至路由器12A的其他實施例。最初，UI模塊36可以呈現一個管理員44可以與其進行交互以直接或間接地輸入 定義策略46中的一個的數據的用戶界面(61)。這一個策略46可以包括決定策略而不是輸 入或輸出策略。因此，這一個策略46可以稱為決定策略46，這是因為這一策略46定義一組 規則(例如，策略映射)，其通過設置本地優先級值而以上述方式影響決定處理。然而，決 定策略可以代表一個修改的輸入或輸出策略，從而，這一個策略46可以包括修改的輸入策 略。以此方式，管理員能夠首先指定一組相關的路由特性，並將這些特性中的每一個都映射 至本地優先級值中的比特的對應集合。管理員還可以指定每個路由特性的可接受的狀態。 因此，管理員可以以輸入策略和輸出策略的形式輸入一個或多個附加策略46，其中，輸入策 略用於控制將路由輸入至RIB 56，輸出策略用於控制將路由從RIB 56輸出至實現路由協 議的其他路由或網絡裝置。UI模塊首先使用由管理員提供的映射信息，從而僅將這些附加 策略表達為必要和相關的路由特性，從而允許用戶避免輸入這些特性及其狀態的全部交叉 乘積唯一組合的配置。UI模塊28接收定義這些策略的該輸入，並將這些策略存儲至策略數 據庫48。同時，轉發平面26B可以經由IFC 28中的一個接收定義新的路由或更新現有路 由的BGP更新消息(例如，BGP更新消息18中的一個)(62)。轉發平面26B可以從這一個 BGP更新消息18的報頭(例如，IP報頭)抽取五元組或其一部分(例如，目的地址)，並在 訪問FIB 60的轉發表58時將該五元組用作密鑰。轉發平面26B可以找到使轉發平面26B 將BGP更新消息18中的一個轉發至路由平面26A的轉發表項。如上所述，路由平面26A可以調用BGP 40，來確定是否設置接收到的路由的loCal_pref值(64)。如上所述，BGP40可 以基於BGP對等裝置的已知配置進行該確定，其實際上表示該對等裝置的AS數量是否與路 由器的AS數量相同(66)。如果AS數量不同於標識AS 14A的AS數量(例如，消息18來自 外部BGP對等裝置)，則BGP 40可以進行設置local_pref值(66中的「是」)。為了設置l0Cal_pref值，BGP 40可以抽取路由和由BG P更新消息18中的一個定 義的任何路由特性作為至路由策略模塊38的路由50。如下更詳細描述的，這些路由特性 可以被定義在BGP更新消息18中的一個的所謂路徑屬性欄位中。這些路由特性還可以通 過操作者或網絡管理員或二者結合來配置，或備選地經由BGP更新消息18來接收這些路由 特性。路由策略模塊38可以響應於路由50訪問策略DB 48，以找到策略46中的一個(例 如，上述決定策略46)，從而將localpref值動態地重新定義為兩個或更多比特欄位，而不 是將該Iocalpref值看作整數(68)。接下來，如上所述，路由策略模塊38可以利用由決定 策略46定義的比特欄位示例來確定與給定的一個比特欄位相關聯的每個路由特性的狀態 (70)。然後，如上所述，路由策略模塊38基於每個對應路由特性的確定的狀態來設置由 決定策略46動態定義的每個比特欄位(72)。即，路由策略模塊38可以訪問將與第一比特 欄位相關聯的第一路由特定的每一可能狀態映射至比特欄位優先級值的第一子映射，並確 定與所確定的第一路由特性的狀態相關聯的比特欄位優先級值。然後，路由策略模塊38可 以利用所確定的比特欄位優先級值來設置識別的比特欄位。路由策略模塊38可以針對策 略46中的一個的比特欄位示例中定義的每個比特欄位重複上述操作。下面的偽碼提供了策略的一種示例性表示//示例本地優先級值的比特欄位(bit field)bit_field_l = local_pref[3116]bit_field_2 = local_pref [15:0],//將比特欄位映射至路由特性policy—mapping (validation—state，neighbor—relationship) {sub_map_l (bit_field_l, validation_state)；sub_map_2 (bit_f ield_2, neighbor_relationship)；}sub_map_l (bit_field_l, validation_state) {if (validation_state == "valid" ) bit_field_l. set (2)；if (validation_state = = "uknown" ) bit_f ield_l. set(l)；if (validation_state ==「 invalid」)bit_field_l. set (0)；return ；}sub_map_2 (bit_f ield_2, neighbor_relationship) {if (neighbor_relationship = = "customer" ) bit_field_2. set (2)；if (neighbor_relationship = = "peer" ) bit_field_2. set(l)；if (neighbor一relationship == "transit" ) bit_field_2. set (0)；return ；
}上述示例性決定策略首先通過比特欄位示例將兩個比特欄位(例如，bit_ field, 1和bit_field_2)示例為本地優先級(loCal_pref)值的16個最高有效位(例如 位31至16)以及本地優先級(loCal_pref)值的16個最低有效位(例如位15至0)。接 下來，該示例性決定策略提供了一種策略映射，該映射接收兩個輸入，由變量validati0n_ state表示的驗證狀態和由neighbour_relationship變量表示的鄰近關係。該策略映射包 括兩個子映射(例如，sub_map_l和sub_map_2)，這兩個子映射各用於兩個比特欄位中。第 一子映射基於由validatior^state變量標識的狀態設置第一示例比特欄位。第二子映射 基於由neighboui^relationship變量標識的狀態設置第二示例比特欄位。路由策略模塊 38可以應用表示為上述偽碼的該示例性決定策略，以將Iocalpref的16個最 高有效位映 射至比特欄位優先級值2(其為000216)到0(其為OOOO16)中的一個，以及將16個最低有效 位映射至比特欄位優先級值2到O中的一個。此處應注意，用戶可以以十進位符號指定這 些值，而不是以十六進位或二進位指定這些值。然而，這些技術可以通過將這些值從十進位 變換為十六進位來以比特方式設置該本地優先級值。在根據決定策略(諸如以上提供的示例性決定策略)設置了所有的比特欄位之 後，路由策略模塊38可以將l0Cal_pref值返回至BGP 40，這可以將loCal_pref值與路由 50在路由表54中進行關聯，如上所述(74，76)。然而，如果BGP 40確定不應該設置local_ pref值(例如，BGP更新消息18中的一個的AS數量與其中駐留有路由器12A的AS的數 量相同，這可以在通過表示對等裝置是內部對等裝置而不是外部對等裝置的配置中表示)， BGP 40可以將該路由存儲到RIB 56的路由表54中，而無需確定local_pref值(66、76中 的「否」)。通常，在BGP 40不確定或設置l0Cal_pref值的情況中，l0Cal_pref值已經由 AS 14A中的另一路由器分配，並且BGP 40可以將該路由與之前由AS 14A的不同路由器確 定的Iocalpref值一起存儲到路由表54中。路由解析模塊42可以以上述方式執行路由解析(例如，實現BGP決定處理)，從而 如上所述首先基於與路由表54中的這些路由中的每一個都相關的Iocalpref值對存儲在 路由表54中的路由進行解析(78)。在完成路由解析時，路由解析模塊42可以將解析出來 的這些路由建立到由轉發平面26B維護的FIB 60的轉發表58中。然後，轉發平面26B可 以接收數據包並根據存儲在FIB 60的轉發表58中的更新路由來轉發這些數據包。圖4是示出定義路由和相關本地優先級值的示例性路由協議消息80的框圖。路 由協議消息80可以代表示例性BGP更新消息，因此可以稱為BGP更新消息80。儘管參照特 定類型的路由協議進行描述，但是這些技術不應該嚴格限於BGP。相反，這些技術可以應用 至任何路由協議。如圖4所示，BGP更新消息80包括BGP頭82和BGP有效載荷84。BGP頭82包括 標記欄位86A、長度欄位86B和類型欄位86C。標記欄位86A提供欄位，以存儲用於BGP對 等裝置(諸如路由器12A和路由器12B或12C)之間的同步和認證的信息。長度欄位86B 包括以字節存儲定義BGP更新消息80的全部長度的數據的欄位，包含頭的欄位。類型欄位 86C包括存儲BGP消息的類型的欄位，其中，該類型通常表示為整數值。對於BGP更新消息， 類型欄位86C可以存儲整數值二(2)。BGP有效載荷84可以包括不能實施(unfeasibility)路由長度欄位(「URL欄位88」)，撤迴路由長度欄位90A 90N(「WRL欄位90」)以及對應的撤迴路由前綴欄位92A 92N( 「WR前綴欄位92」)、全部路徑屬性長度欄位94( 「全部路徑屬性長度欄位94」)、屬性 類型欄位96A 96N(「屬性類型欄位96」)和相關屬性長度欄位98A 98N(「AL欄位98」) 和屬性值欄位100A 100N( 「屬性值欄位100」 )、以及網絡層可達信息長度欄位102A 102N( "NLRIL欄位102，，)、以及相關NLRI前綴欄位104A 104N( "NLRI前綴欄位104，，)。 URL欄位88包括存儲定義對應WRL欄位90加上WR前綴欄位90的全部長度的數據的欄位。 每個WRL欄位90包括存儲定義由有效的WR前綴欄位90中對應的一個定義的IP位址中的 比特數的的數據的欄位。每個WR前綴欄位90都包括存儲定義其路由被撤回的網絡的IP 地址前綴的數據的欄位。如果URL欄位88存儲零值，則BGP更新消息80可以省略WRL字 段90和WR前綴欄位92。WRL欄位90和對應的WR前綴欄位92中的每一個均可以表示撤 迴路由(例如，不再被BGP考慮且從路由表54去除的路由)。全部路徑屬性長度欄位94包括存儲定義以字節為單位的每個「路徑屬性」欄位的 全部長度總和的總長的數據的欄位。路徑屬性欄位可以包括欄位96中的一個和欄位98與 100中的對應一個。每個屬性類型欄位96都可以包括存儲定義由對應的一個欄位100定義 的路徑屬性值的類型的數據的欄位。每個屬性長度欄位98可以包括定義對應的一個欄位 100的字節長度的欄位。屬性值欄位100每個均可以包括存儲定義由對應的一個屬性類型 欄位96表示的類型的屬性值的數據的欄位。
每對NLRI長度欄位102和NLRI前綴欄位104均可以定義被通告的路由的IP地 址前綴。與WLR欄位90 —樣，每個NLRI長度欄位102可以包括存儲定義由有效的對應的 一個NLRI前綴欄位102定義的IP位址中的比特數的數據的欄位。每個NLRI前綴欄位104 可以包括存儲定義其路由正被通告的網絡的IP位址前綴的數據的欄位。路由器12A以及更具體的BGP 40可以產生BGP更新消息80，並將根據本文中描述 的這些技術計算出來的本地優先級值存儲在由對應的一組欄位96 100定義的路徑屬性 之一中。下面將參照圖5A更詳細地描述示例性屬性類型欄位，其中對應的一個屬性值欄位 存儲localpref值的該類型欄位信號將在下面參照圖5A更加詳細地進行描述。下面還將 參照圖5B更加詳細地描述存儲根據本文中描述的這些技術確定的localpref值的示例性 屬性值欄位。圖5A 圖5B是更詳細示出包含在路由協議消息中的示例性屬性類型欄位106和 對應的示例性屬性值欄位108的框圖。屬性類型欄位106可以基本類似於任何一個屬性類 型欄位96。同樣，屬性值欄位108可以基本類似於任何一個屬性值欄位100。如圖5A所示，屬性類型欄位106可以由用戶根據本文中描述的技術進行重新定 義，以便包括子欄位、屬性類型代碼欄位IlOA(「ATC欄位IlOA」)和屬性標誌欄位IlOB(「標 志欄位110B」)。子欄位110A、110B中的每一個都可以包括一個或多個孫欄位，其可以稱為 比特分區(bit partition)，從而不會與上述比特欄位混淆。然而，這些位分區可以包括比 特欄位。在任一情況中，稱為ATC欄位IlOA的子欄位IlOA都可以存儲標識存儲至對應屬 性值欄位108的數據的「類型」的整數值。ATC欄位IlOA存儲定義整數值五(5)以向BGP 模塊40發送信號或指出對應的屬性值欄位108存儲localpref值的數據。子欄位IlOB可以包括多個比特分區，這些比特分區雖然在圖5A中詳細示出，但其 可以存儲定義可選標誌、轉接標誌、部分標誌以及擴展長度標誌中的每一個的狀態的數據。這些標誌中的每一個都可以表示由對應屬性值欄位108存儲或定義的屬性的不同特性。例 如，可選標誌可以表示由對應屬性值欄位108定義的屬性是否可選。這些標誌通常反映由 ATC欄位IlOA和對應屬性值108定義的屬性的狀態。如圖5A所示，屬性值欄位108包括用於存儲值的32個比特欄位。假設對應的屬 性類型欄位106的ATC欄位1IOA存儲5，故其表示屬性值欄位108定義loCal_pref值，屬 性值欄位108包括存儲l0Cal_pref值的32比特欄位。關於BGP，local_pref值被看作32 比特整數值。然而，如圖5A進一步示出的，路由策略模塊38可以動態地將該欄位定義為多 個比特欄位，諸如比特欄位112A和112B( 「比特欄位112」)。這些比特欄位112中的每一 個均可以包括存儲與對應路由特性的狀態相關聯的優先級值的16比特欄位。應該注意，這 些比特欄位112是邏輯比特欄位，這是因為BGP將該loCal_pref值看作整數值，而不是將 該值看作多個獨立比特欄位112的合成。
在這方面，為了更好地以上述方式控制路由解析或BGP決定處理，這些技術可以 在邏輯上重新定義Iocalpref值。應該注意，通過如此重新定義Iocalpref值，當再次將 其看作整數值時，每個比特欄位112被自然(inherently)排序，從而對管理員(諸如管理 員44)應該注意到的相關路由特性之間的優先級選擇施加設定的順序。例如，假設比特欄位112A與驗證狀態路由特性相關聯，以及比特欄位112B與鄰 近關係路由特性相關聯，這類似於上述為了示例性目的所假設的，比特欄位112A由於包括 在比特欄位112B之前被考慮的Iocalpref值的16個最高有效位，此時loCal_pref值被 看作整數。換言之，如果與優先級值OOOl16相關聯的驗證狀態被設置為第一交疊路由的第 一 local_pref值，而與優先級值000216相關聯的驗證狀態被設置為第二交疊路由的第二 localpref值，不管對比特欄位112B設置了什麼值，路由解析模塊42都可以優先於第一交 疊路由而選擇第二交疊路由，這是因為不管比特欄位112B對於第一和第二 localpref值 為何值，得到的第二 Iocalpref值當被看作整數時總是會大於第一 loCal_pref值。在這 方面，驗證狀態路由特性具有上述鄰近關係路由特性的重要性或優先級的自然順序。實際上，路由解析模塊42可以只基於比特欄位(其包含localpref值的最高有 效位)進行路由解析，而且僅當兩個Iocalpref值的該最高有效位表示與兩個Iocalpref 值相同的相同值時，路由解析模塊42基於包含localpref值的較低有效位的比特欄位進 行路由解析。在上述實例中，如果這兩個Iocalpref值都與具有相同驗證狀態但具有不同 鄰近關係的交疊路由相關聯，則路由解析模塊42選擇具有與最高優先級值相關聯的鄰近 關係的交疊路由中的一個。因此，被示例為包含loCal_pref值的較低有效位的連續比特字 段可以定義通信斷路器(tie-breaker)值，用於斷開導致被示例為包含l0Cal_pref值的較 高有效位的比特欄位的通信。值得注意的是，如上所述，該固有順序作為BGP連續將localpref路徑屬性值看 作整數的結果而出現，但卻保存了該整數值從而提供了許多附加優點。首先，通過如此保存 該整數值而不提供另一路徑屬性(諸如新的BGP團體類型)，這些技術可以節約帶寬，由於 附加又一個新的BGP團體會進一步增加BGP更新消息的尺寸。第二，如上所述，保存該整數 值，使得這些技術能夠保持互操作性，這是因為通常將loCal_pref值看作整數的其他路由 器可以繼續如此將Iocalpref值看作整數。在這方面，這些技術可以使能可升級性，並在 給定AS中提供對這些技術的慢速應用。即，例如，路由器12A可以實現這些技術並且還與AS 14A的其他路由器互操作。由於AS14A的服務提供商追求實現這些技術的連續路由器， 因此，這些連續的路由器可以遞增地設置到AS 14A中，且仍與舊的路由器互操作，其可以 通過手動調整來輕鬆地實現本文中描述的這些技術。第三，如果不防止組成Iocalpref值 的邏輯比特欄位所需的路由解析模塊42的改變，這些技術可以保存該整數值以進行限制。 路由解析模塊42通常是在選擇通過網絡的適當路由時起作用的高度複雜的路由處理。如 果需要對路由解析模塊42進行改變，則這些改變可能會不適當地實現或提供可能導致路 由故障的軟體程序錯誤。考慮到網際網路依賴於高速和高效，以滿足用戶對網際網路接入的高 標準要求，這些路由故障會極大影響網際網路服務並極大影響商業關係。此 外，如上所述，這些技術可以使得策略可以被定義為指定較少規則。這樣不僅在 人員或其他可用性方面有助於實現這些技術的路由器，而且這些策略還可以因為規則數量 的減少而在尺寸上更小。考慮到將定義策略所需的規則數量從指數數量的規則減少為線性 數量的規則，根據這些技術定義的這些策略可以要求非常少的路由器資源(例如路由器存 儲器)來進行保存或存儲。儘管上述描述為由用戶(諸如管理員44)進行輸入，這些技術還可以對用戶透明 地實現，使得路由器12A在定義localpref值時自動保留並設置一些比特欄位。因此，這 些技術在其透明性方面可以理解為「秘密地(under the covers)」發生。這些技術不應被 理解為要求管理員定義策略。相反，這些技術可以實現為自動產生該策略，而用戶無需響應 於特定配置進行輸入，或者在一些情況中，使得該策略在傳遞至用戶之前被靜態定義，並通 過配置命令而使能。本文已經描述了本發明的各個實施例。這些以及其他實施例都落入所附權利要求 的範圍內。
權利要求
一種方法，包括利用網絡中的路由器存儲描述多條路由的信息，其中，所述多條路由中的每一條均定義通過網絡到達目的地的跳的序列；利用所述路由器存儲定義規則的數據，所述路由器通過所述規則確定所述多條路由中至少一條的本地優先級值，其中，所述本地優先級值被由所述路由器實現的路由協議指定為整數值，其中，所述路由器在路由解析過程中根據所述路由協議利用所述本地優先級值對所述多條路由中的一條或多條進行排序和選擇，以及其中，所述規則根據由所述路由協議指定的整數值將所述本地優先級值重新定義為兩個或更多比特欄位，以及其中，所述規則將每個所述比特欄位與不同的路由特性進行關聯，並針對每個所述不同的路由特性定義將比特欄位優先級值與對應的路由特性的每個可能的狀態進行關聯的映射；利用所述路由器確定由所述映射定義的每個所述不同的路由特性的狀態；利用所述路由器，通過使所述比特欄位優先級值中的一個與策略映射中的所確定的狀態相關聯來設置所述本地優先級值的兩個或更多比特欄位中的每一個，從而確定所述本地優先級值的整數值；以及利用所述路由器將所述多條路由中的至少一條與所述本地優先級值的所確定的整數值進行關聯。
2.根據權利要求1所述的方法，進一步包括提供具有輸入語法的用戶界面，用戶使用所述用戶界面輸入獨立於其他路由特性的每 個路由特性的所述比特欄位優先級值，以使所述比特欄位優先級值作為獨立的參數；以及利用所述路由器執行所述路由協議以進行路由解析，從而利用所述本地優先級值作為 所述路由協議中的單個參數而基於所確定的所述本地優先級值的整數值來對所述多條路 由中的一條或多條進行排序和選擇。
3 根據權利要求1所述的方法，其中，存儲定義多條規則的數據包括相關於每個所述 路由特性的可能狀態的總數，來存儲定義線性數量的規則的數據。
4.根據權利要求1所述的方法，進一步包括根據定義至少一條路由和為所述至少一條路由確定的本地優先級值的路由協議生成 消息；以及將所述消息轉發至另一路由器，所述另一路由器包含在所述網絡中，且不同於描述至 少一條路由和為所述至少一條路由所確定的本地優先級值的路由器。
5.根據權利要求4所述的方法，其中，所述消息包括根據邊緣網關協議(BGP)生成的更新消息，其中，所述BGP更新消息包括定義為所述至少一條路由所確定的本地優先級值的本地 優先級(loCal_pref)欄位。
6.根據權利要求1所述的方法，其中，所述不同的路由特性中的每一個包括鄰近關係、 路由驗證狀態、社區類型、可用帶寬、總帶寬、自治系統(AS)路徑(「AS_Path」)、源路由的 IGP區域或等級、源協議、源示例以及初始屬性中的不同的一個。
7.根據權利要求1所述的方法，其中，所述多條路由中的所述至少一條包括定義通過所述網絡到達目的地的多個跳的第一路由，其中，所述本地優先級值包括與所述第一路由相關聯的第一本地優先級值， 其中，所述多條路由中的第二路由定義通過所述網絡到達由所述第一路由定義的同一 目的地的不同的多個跳，以及其中，所述多條路由中的所述第二路由與第二本地優先級值相關聯， 所述方法進一步包括利用所述路由器進行路由解析以基於所述第一本地優先級值和 所述第二本地優先級值選擇所述第一路由或所述第二路由。
8.根據權利要求7所述的方法，其中，執行路由解析包括 確定所述第一本地優先級值是否大於所述第二本地優先級值；以及 基於對所述第一本地優先級值大於所述第二本地優先級值的確定來選擇所述第一路
9.根據權利要求7所述的方法，其中，執行路由解析包括確定所述第一本地優先級值是否大於所述第二本地優先級值；以及基於對所述第一本地優先級值小於所述第二本地優先級值的確定來選擇所述第一路
10.根據權利要求7所述的方法，進一步包括將所述第一路由或所述第二路由中所選擇的一個建立到所述路由器的轉發平面中；以及利用所述路由器的所述轉發平面根據所建立的路由轉發數據包。
11.根據權利要求1所述的方法，其中，利用所述路由器將所述多條路由中的至少一條 與所確定的本地優先級值進行關聯包括將所述本地優先級值和所述多條路由中的至少一條存儲到由所述路由器的路由平面 維護的路由表的單獨項中。
12.根據權利要求1所述的方法，進一步包括通過路由協議接收定義所述多條路由的信息；以及通過由包含在所述路由器中的用戶界面模塊呈現的用戶界面接收來自管理員的定義 規則的數據。
13.—種路由器，包括至少一個接口卡，用於根據路由協議接收路由協議消息，每個所述至少一個接口卡均 定義描述多條路由中的一條或多條的信息，其中，所述多條路由中的每一條均定義通過網 絡到達目的地的跳的序列；以及控制單元，用於存儲定義規則的數據，所述路由器通過所述規則確定所述多條路由中 至少一條的本地優先級值，其中，所述優先級值被由所述路由器實現的路由協議指定為整 數值，其中，所述路由器在路由解析過程中根據所述路由協議利用所述優先級值對所述多 條路由中的一條或多條進行排序和選擇，以及其中，所述規則將由所述路由協議指定的所 述本地優先級值重新定義為兩個或更多比特欄位，以及其中，所述規則將每個所述比特字 段與不同的路由特性進行關聯，並針對每個所述不同的路由特性定義將比特欄位優先級值 與對應的路由特性的每個可能的狀態進行關聯的映射，其中，所述控制單元還確定由所述映射定義的每個所述不同的路由特性的狀態，通過 使所述比特欄位優先級值中的一個與映射中的所確定的狀態相關聯來設置所述本地優先級值的兩個或更多比特欄位中的每一個，並將所述多條路由中的至少一條與所述本地優先 級值的所確定的整數值進行關聯。
14.根據權利要求13所述的路由器，其中，所述控制單元包括用戶界面模塊，用於呈現具有輸入語法的用戶界面，用戶使用所述用戶界面輸入獨立 於其他路由特性的關於每個路由特性的比特欄位優先級值，以使所述比特欄位優先級值作 為獨立的參數；以及路由協議模塊，用於執行所述路由協議以進行路由解析，從而利用所述本地優先級值 作為所述路由協議中的單個參數而基於所確定的所述本地優先級值的整數值來對所述多 條路由中的一條或多條進行排序和選擇。
15.根據權利要求13所述的路由器，進一步包括策略資料庫，用於相關於每個所述路 由特性的可能狀態的總數來存儲定義線性數量的規則的數據。
16.根據權利要求13所述的路由器，其中，所述控制單元包括路由協議模塊，用於根據定義至少一條路由和為所述至少一 條路由確定的本地優先級值的路由協議生成消息；以及其中，所述至少一個接口卡將所述消息轉發至另一路由器，所述另一路由器包含在所 述網絡中，且不同於描述至少一條路由和為所述至少一條路由所確定的本地優先級值的路由器。
17.根據權利要求16所述的路由器，其中，所述消息包括根據邊緣網關協議(BGP)生成的更新消息， 其中，所述BGP更新消息包括定義為所述至少一條路由所確定的本地優先級值的本地 優先級(loCal_pref)欄位。
18.根據權利要求13所述的路由器，其中，所述不同的路由特性中的每一個包括鄰近 關係、路由驗證狀態、社區類型、可用帶寬、總帶寬、自治系統(AS)路徑(「AS_Path」)、源路 由的IGP區域或等級、源協議、源示例、以及初始屬性中的不同的一個。
19.根據權利要求13所述的路由器，其中，所述多條路由中的所述至少一條包括定義通過所述網絡到達目的地的多個跳的第一路由，其中，所述本地優先級值包括與所述第一路由相關聯的第一本地優先級值， 其中，所述多條路由中的第二路由定義通過所述網絡到達由所述第一路由定義的同一 目的地的不同的多個跳，其中，所述多條路由中的所述第二路由與第二本地優先級值相關聯，以及 其中，所述控制單元進一步進行路由解析以基於所述第一本地優先級值和所述第二本 地優先級值選擇所述第一路由或所述第二路由。
20.根據權利要求19所述的路由器，其中，所述控制單元包括路由解析模塊，用於確定 所述第一本地優先級值是否大於所述第二本地優先級值；並基於對所述第一本地優先級值 大於所述第二本地優先級值的確定來選擇所述第一路由。
21.根據權利要求19所述的路由器，其中，所述控制單元包括路由解析模塊，用於確定 所述第一本地優先級值是否大於所述第二本地優先級值；並基於對所述第一本地優先級值 小於所述第二本地優先級值的確定來選擇所述第一路由。4
22.根據權利要求19所述的路由器，其中，所述控制單元包括 轉發平面；以及路由平面，包括路由解析模塊，其中，所述路由解析模塊將所述第一路由或所述第二路 由中所選擇的一個建立到所述路由器的轉發平面中；以及 其中，所述轉發平面根據所建立的路由轉發數據包。
23.根據權利要求13所述的路由器，進一步包括路由信息庫，用於將所述本地優先級 值和所述多條路由中的至少一條存儲到路由表的單獨項中。
24.根據權利要求13所述的路由器，其中，所述控制單元包括路由協議模塊，用於通過路由協議接收定義所述多條路由的信息；以及 用戶界面模塊，用於呈現用來接收來自管理員的定義規則的數據的用戶界面。
25.—種網絡系統，包括第一自治系統，包括第一路由器；以及 第二自治系統，包括第二路由器， 其中，所述第二路由器包括至少一個接口卡，用於根據路由協議從所述第一路由器接收路由協議消息，每個所述 至少一個接口卡均定義描述多條路由中的一條或多條的信息，其中，所述多條路由中的每 一條均定義通過網絡到達目的地的跳的序列；以及控制單元，用於存儲定義規則的數據，所述第二路由器通過所述規則確定所述多條路 由中至少一條的本地優先級值，其中，所述優先級值被由所述第二路由器實現的路由協議 指定為整數值，其中，所述第二路由器在路由解析過程中根據所述路由協議利用所述優先 級值對所述多條路由中的一條或多條進行排序和選擇，以及其中，所述規則將由所述路由 協議指定的所述本地優先級值重新定義為兩個或更多比特欄位，以及其中，所述規則將每 個所述比特欄位與不同的路由特性進行關聯，並針對每個所述不同的路由特性定義將比特 欄位優先級值與對應的路由特性的每個可能的狀態進行關聯的映射，其中，所述控制單元還確定由所述映射定義的每個所述不同的路由特性的狀態，通過 使所述比特欄位優先級值中的一個與映射中的所確定的狀態相關聯來設置所述本地優先 級值的兩個或更多比特欄位中的每一個，並將所述多條路由中的至少一條與所述本地優先 級值的所確定的整數值進行關聯。
全文摘要
本發明描述了動態地重新定義在路由解析過程中使用的優先級值的技術。諸如路由器的網絡裝置可以實現這些技術以在可用性方面對路由器進行改進。該路由器可以包括接口卡，用於接收描述多條路由中的一條或多條的消息。該路由器還可以包括控制單元，用於存儲定義策略的數據。該策略可以包括路由器確定多條路由中的一個的優先級值所遵循的規則。該策略動態地將優先級值重新定義為兩個或更多的比特欄位，而不是將該優先級值看作整數值。該控制單元進一步根據該策略設置該本地優先級值的兩個或更多比特欄位中的每一個，並將這些路由中的至少一條與所確定的本地優先級值進行關聯。
文檔編號H04L12/56GK101888334SQ20101017823
公開日2010年11月17日 申請日期2010年5月11日 優先權日2009年5月11日
發明者約翰·加倫·斯卡德 申請人:叢林網絡公司