網絡系統、路徑計算方法和路徑計算程序的製作方法

2023-05-05 23:23:26 2

專利名稱：網絡系統、路徑計算方法和路徑計算程序的製作方法
技術領域：
本發明涉及網絡系統、路由計算方法以及程序，並且更具體地，涉及使用面向連接 的路徑連接來提供通信服務的網絡系統、路由計算方法以及這種網絡系統中的程序。
背景技術：
現在，從網絡服務的嚴格管理以及通信服務的質量保證的角度來說，使用對通信 服務顯式的面向連接的路徑來對通信服務的路由進行清晰管理的網絡變得普遍。這種面向 連接的路徑的示例是MPLS (多協議標籤交換)路徑、ATM(異步傳輸模式)路徑、面向連接 的乙太網(註冊商標)路徑、TDM路徑以及波長路徑。當在這種網絡中控制和管理面向連 接的路徑時，在具有大量節點的大規模網絡的情況中，一般將網絡劃分為多個域，並且由於 網絡的可擴展性以及操作效率的提高，每個域單元詳細地控制和管理路徑。將被劃分為多 個域的網絡稱作多域網絡。在多域網絡中，由路由協議在每一個域中專有地公布設置路徑路由時使用的詳細 拓撲信息。然而，難以僅使用這種部分詳細的拓撲信息來最合適地並且共同地計算跨越多 個域的路徑，使得使用下述方法在每一個域中計算區間路由並且通過將相應域的計算結 果組合在一起來獲得總路由。在計算這種區間路由時，必須至少考慮下列限制實現所需路徑的通帶的配置的路由；以及當前路徑和備份路徑經過不共享起始節點(SN)(路徑的起始點)和結束節點(DN) (路徑的結束點)之間的相同網絡資源的相應路由。注意，不共享相同網絡資源的路由是在當前路徑和備份路徑之間不共享節點、鏈 路以及SRLG(共享風險鏈路組)中的任一個或者全部的路由。這稱作路由分集。在專利文獻1中公開了上述多域網絡中的路徑設置方法。圖20示出了使用專利文 獻1中公開的路由判定系統的網絡配置。該多域網絡系統包括多個域(域DM1至域DMn)、 路徑的起始節點1001、路徑的結束節點1002、路徑的中間節點(T1至T4) 1004、以及與域間 的相應邊界節點(Bm至Bmo) 1005相連的路由判定系統(PSS1至PSS4) 1000。在圖20所示的多域網絡中，當計算從起始節點1001到結束節點1002的路由時， 路由判定系統如下操作。起始節點1001選擇與可以到達目標域(域DM2)的中間域(假定 選擇域DM3)相連的路由判定系統PSS1，並且發送路由計算請求消息。路由判定系統PSS1 根據優先級順序選擇邊界節點，基於路徑的路由分集來計算從起始節點1001到所選的相 應邊界節點1005的路由(例如選擇邊界節點Bm用於當前路徑，選擇邊界節點BN3用於備 份路徑)，並且向路由判定系統PSS3發送路由計算結果以及針對從邊界節點Bm到結束節 點1002的後續路由以及從邊界節點BN3到結束節點1002的路由的路由計算請求。路由判 定系統PSS3基於路徑的路由分級來計算由先前階段的路由判定系統PSS1計算的路由的後 續路由。當設定了從起始節點1001到結束節點1002的路由時，從路由判定系統PSS3通過 路由判定系統PSS1向請求發起方的起始節點1001發送與所計算的路由相關的信息，作為
6用於當前路徑的路由和用於備份路徑的路由。起始節點1001根據與這些路由相關的信息， 分別發出針對當前路徑和針對備份路徑的信令。相應地，在起始節點1001和結束節點1002 之間設置了當前路徑和備份路徑。當路由計算失敗時，路由計算失敗的路由判定系統或者失敗的路由判定系統的先 前階段的路由判定系統根據優先級順序信息來選擇不同的邊界節點，並且重新開始路由計 算。重複該操作直到路由計算成功。在圖20的網絡配置中路由計算失敗的示例是路由判 定系統PPS1選擇邊界節點Bm用於當前路徑以及選擇邊界節點BN2用於備份路徑的情況。 在該情況中，在路由判定系統PSS3的路由計算中，當前路徑和備份路徑經過中間節點T1處 的相同節點，使得路由判定系統PSS3返迴路由計算失敗。專利文獻1 未審查日本專利申請特許公開號2005-252368。

發明內容
本發明要解決的問題根據前述相關技術的路由計算系統，存在下列問題。第一個問題是可能存在必須 多起重新開始邊界節點的選擇以及每次重新開始選擇時執行路由計算以設置屬於不同域 的起始節點和結束節點之間的端到端路由的情況，並且路由計算花費大量的時間。域的數 量越大並且邊界節點的數量越大，則計算所需的時間就增加越多，並且當執行包括多個域 的大規模網絡的路由計算時該問題將變為不可忽視的性能問題。路由計算花費時間的原因 是由於根據優先級來選擇邊界節點，並且，根據拓撲形狀，不滿足當前路徑的路由分集的限 制以及備份路徑的路由分集的限制，使得路由計算失敗的數量增加。第二個問題是不能保證所計算的當前路徑的最優性以及所計算的備份路徑的最 優性。原因在於，為了根據與最優索引無關的優先級來選擇邊界節點，如果存在變為最合適 路由的另一邊界節點，則在不考慮該路由的情況下執行路由計算。第三個問題是在有多個 中間域的情況下，不存在選擇要經過的合適域的機制以及控制該域的路由計算系統。原因 在於，難以僅通過使用傳統路由機制(如0SPF和BGP)來選擇域或者檢測邊界節點。例如， 當路由判定系統不具有與邊界節點相同的標識符時，難以自動選擇這樣的域。本發明的目的是提供一種網絡系統、路由判定系統、路由計算方法和程序，可以有 效地計算多域網絡中滿足限制的冗餘路徑(當前路徑和備份路徑)。解決問題的方案根據第一方面，本發明提供了一種網絡系統，包括多個路由判定系統，所述多個路 由判定系統分布並布置在被分為多個路由計算域的多域網絡中，其中每個路由判定系統包 括拓撲信息收集單元，收集拓撲信息；路由計算請求響應單元，接收請求對從起始節點到 結束節點的冗餘路徑進行路由計算的路由計算請求；以及路由計算單元，響應於路由計算 請求，使用拓撲信息並考慮限制來執行路由計算，並且在設置了從所述起始節點所在的路 由計算域至所述結束節點所在的路由計算域要經過的路由計算域之後，通過使從所述結束 節點所在的路由計算域向所述起始節點所在的路由計算域的每個路由判定系統中的路由 計算單元順序執行冗餘路徑的路由計算，並且通過將相應路由判定系統計算的冗餘路徑的 路由組合在一起，來計算所述起始節點和所述結束節點之間的冗餘路徑的路由。根據第二方面，本發明還提供了一種路由判定系統，與多域網絡中的多個路由計算域中的至少一個相對應地布置，所述路由判定系統包括拓撲信息收集單元，收集拓撲信息；路由計算請求響應單元，接收請求對從起始節點到結束節點的冗餘路徑進行路由計 算的路由計算請求；路由判定系統選擇單元，當所述結束節點不在所述路由判定系統所屬 的本地路由計算域時，選擇要將所述路由計算請求發送至的路由判定系統所屬的路由計算 域；以及路由計算單元，當所述結束節點在所述路由判定系統所屬的本地路由計算域時，使 用拓撲信息並考慮限制來執行冗餘路徑的路由計算，並向所述路由計算請求的發送發起方 發出包括路由計算結果在內的路由計算響應。根據第三方面，本發明還提供了一種由多個路由判定系統來計算從起始節點到結 束節點的跨越路由計算域的冗餘路徑的路由的方法，所述多個路由判定系統分布並布置在 多域網絡中並且一起工作，所述方法包括以下步驟使用每個路由判定系統保持的相鄰信 息來設置從所述起始節點到所述結束節點的路由所經過的路由計算域；以及使屬於所設置 的路由計算域的路由判定系統從屬於所述結束節點所在的路由計算域的路由判定系統向 屬於所述起始節點所在的路由計算域的路由判定系統遞歸地執行路徑計算。根據第四方面，本發明還提供了一種程序，允許計算機執行計算多域網絡中計算 從起始節點到結束節點的跨越路由計算域的冗餘路徑的路由的過程，所述程序允許計算機 執行以下過程接收請求對所述冗餘路徑進行路由計算的路由計算請求；當所述結束節點 不在路由判定系統所屬的本地路由計算域時，選擇要將所述路由計算請求發送至的路由判 定系統所屬的路由計算域；以及當所述結束節點在路由判定系統所屬的本地路由計算域 時，使用拓撲信息並考慮限制來執行所述冗餘路徑的路由計算，以及向所述路由計算請求 的發送發起方發出包括路由計算結果在內的路由計算響應。本發明的效果本發明的網絡系統、路由判定系統、路由計算方法以及程序可以有效地計算滿足 限制的冗餘路徑(當前路徑和備份路徑)。參照附圖，通過下面的解釋，本發明的上述目的和其他目的、特徵以及優點將變得 顯而易見。


圖1是示出了使用根據本發明第一實施例的路由判定系統的網絡配置的框圖；圖2是示出了路由判定系統的配置的框圖；圖3是示出了當多個路由判定系統執行冗餘路徑的路由計算時的過程的序列圖；圖4是示出了路由判定系統選擇過程的過程的流程圖；圖5是示出了對與路由判定系統相關的可達性信息進行通知的示例路由的框圖；圖6是示出了對與結束節點相關的可達性信息進行通知的示例路由的框圖；圖7是示出了可達性信息的特定示例的圖；圖8是示出了路由計算過程的過程的流程圖；圖9是示例了多域網絡中的拓撲的框圖；圖10是示出了用於結束點路由計算域中的路由計算的拓撲的框圖；圖11是示出了在結束點路由計算域中計算的冗餘路徑的候選的圖；圖12是示出了用於中間路由計算域的路由計算的拓撲的框圖13是示出了在中間路由計算域計算的冗餘路徑的候選的圖；圖14是示出了用於起始點路由計算域的路由計算的拓撲的框圖；圖15是示出了在起始點路由計算域中計算的冗餘路徑的候選的圖；圖16是示出了根據本發明第二實施例的路由判定系統的配置的框圖；圖17是示出了當多個路由判定系統執行冗餘路徑的路由計算時的過程的序列 圖；圖18是示出了根據第二實施例的路由判定系統選擇過程的過程的流程圖；圖19是示出了根據第二實施例的冗餘路徑的路由計算結果的圖；以及圖20是示出了使用相關技術的路由判定系統的網絡配置的框圖。
具體實施例方式參照附圖給出對本發明實施例的詳細解釋。注意，在附圖中相同參考數字指示相 同的元素。圖1示出了使用根據本發明的第一實施例的路由判定系統的網絡配置。將網絡 劃分為多個域(域DMl至域DM4)。多個邊界節點103 (BN 邊界節點)布置在域之間。多個 路由判定系統(PSS1至PSS4) 100與相應域相對應地布置，並且執行相對應域的路由計算。 請求發起方106是發出路由計算請求的系統。請求發起方106還可以作為起始節點(SN)IOl 中的功能塊來操作。注意，在圖1中，儘管路由判定系統100被配置為布置在相應域中，但是還可以跨 越多個域來布置路由判定系統100。將由路由判定系統100管理的域或者多個域的集合稱 為路由計算域90。在圖1中，域DMl至DM4中的每一個配置為路由計算域90。圖2示出了每一個路由判定系統100的配置。路由判定系統(PSS) 100包括拓撲 信息收集單元201、路由計算域管理單元202、路由計算請求響應單元203、路由判定系統選 擇單元(PSS選擇單元)204、區間路徑抽象單元205、以及路由計算單元206。由計算機系統 來配置路由判定系統100，並且通過運行安裝在計算機系統中的程序來實現路由判定系統 100中的每個單元的功能。拓撲信息收集單元201收集來自一個或者多個拓撲信息源207的路由計算域90 中的詳細拓撲信息、以及來自路由判定系統的可達性信息和來自同時屬於另一路由計算域 90的節點的可達性信息。圖2中的拓撲信息源207與圖1中的邊界節點Bm至Bmo、相應 域的路由判定系統PSSl至PSS4、以及未示出的其他節點相對應。備選地，當提供一種對域 中的拓撲信息進行集中管理的管理設備時，拓撲信息源207與該管理設備相對應。可以由 管理信息收集協議(類似於SNMP (簡單網絡管理協議))或者路由協議(如OSPF TE (具有 業務量工程的開放最短路徑優先)、IS-IS TE(具有業務量工程的中間系統-中間系統)、 或者IGP(內部網關協議))來收集拓撲信息。路由計算域管理單元202基於拓撲信息收集單元201收集的信息來生成路由計算 域信息210、可達性信息211、以及拓撲信息212，並且作為資料庫來管理這些信息。拓撲信 息212指示了域中詳細的拓撲。在拓撲信息212中包括與域中的鏈路相關的鏈路信息。鏈 路信息包括節點標識符、鏈路標識符、剩餘通帶以及鏈路代價。路由計算域信息210管理與路由計算域相關的邊界節點信息、以及路由判定系統 之間的相鄰信息。在邊界節點信息中包括節點標識符，並且在相鄰信息中包括鄰接的路由判定系統的標識符。通過參照路由計算域信息210，可以確定路由判定系統所屬的域與邊界 節點所通過的路由計算域鄰接。可達性信息211管理至所有路由判定系統以及至節點的可達性信息。可達性信息 包括從路由計算域到另一路由計算域的邊界節點信息、以及到達該域的路由代價。通過參 照可達性信息211，可以確定例如是否有可能通過包括圖1的邊界節點Bm在內的路由到達 域DM2中的結束節點102，以及當到達結束節點102時的代價。可以通過分析由拓撲信息收 集單元201收集的可達性信息來獲得路由計算域信息210以及可達性信息211。路由計算請求響應單元203是與請求發起方106以及另一路由判定系統100的通 信接口，並且發送/接收針對路由計算的請求及其響應。通過參照由路由計算域管理單元 202管理的路由計算域信息210以及可達性信息211，PSS選擇單元204具有選擇後續路由 判定系統的功能，該後續路由判定系統用於對結束節點102 (圖1)所屬的域進行路由計算。 區間路徑抽象單元205具有對已經由另一路由判定系統計算的多個路由候選進行抽象的 功能，並且具有在拓撲信息中註冊所抽象的路由候選的功能。更具體地，區間路徑抽象單元 205具有將由另一路由判定系統100計算的冗餘路徑路由轉換為具有反映代價的限制條件 的虛擬鏈路的功能，以及具有基於限制條件來創建虛擬結束節點的功能。路由計算單元206 考慮限制來執行路由計算。
當通過路由計算請求響應單元203接收來自另一路由判定系統100或者來自請求 發起方106的路由計算請求時，每個路由判定系統100確定計算請求所指定的結束節點是 否在每個路由判定系統100所屬的本地域中。當結束節點不在時，使PSS選擇單元選擇要 發出路由計算請求的路由判定系統，並且執行向該路由判定系統發出路由計算請求的過程 (PSS選擇過程)。當結束節點在路由判定系統100所屬的本地域時，使路由計算單元206 執行路由計算，並且執行向發出路由計算請求的發起方返回包括計算所獲得的路由候選在 內的路由計算響應的過程(路由計算過程)。圖3示出了當多個路由判定系統執行冗餘路徑的路由計算時的過程。假定屬於域 DMl的請求發起方106發出從域DMl中的起始節點101 (圖1)到域DM2中的結束節點102 的路由計算請求。該請求發起方106向路由判定系統PSSl發出路由計算請求。由於結束 節點102不在路由判定系統PSSl所屬的本地域DMl中，路由判定系統PSSl執行PSS選擇 過程150。在PSS選擇過程150中，路由判定系統PSSl在與路由判定系統PSSl所屬的本地 域DMl相鄰的路由計算域中，選擇屬於通過可以到達結束節點102的邊界節點鄰接的路由 計算域的路由判定系統作為該路由計算請求的發出目的地(發送目的地)。在PSS選擇過 程150中，路由判定系統PSSl選擇例如屬於域DM3的路由判定系統PSS3，並且向所選的路 由判定系統PSS3發出路由計算請求。接收到路由計算請求的路由判定系統PSS3以與路由判定系統PSSl相同的方式來 執行PSS選擇過程150，並且選擇例如屬於域DM2的路由判定系統PSS2。此後，路由判定系 統PSS3向所選的路由判定系統PSS2發出路由計算請求。按照這種方式，在每個路由判定 系統100中重複PSS選擇過程150允許最終將路由計算請求發送至屬於結束節點102所在 的路由計算域DM2的路由判定系統PSS2。通過前述過程來設定從起始節點101到結束節 點102的冗餘路徑經過的路由計算域。在設定了要經過的域之後，從結束節點102所在的 路由計算域DM2側轉移執行路由計算的過程。
由於結束節點102在路由判定系統PSS2所屬的本地域DM2中，因此路由判定系統PSS2首先執行路由計算過程160。路由判定系統PSS2向路由判定系統PSS3發送包括路由 計算過程160所獲得的路由候選在內的路由計算響應。該路由計算響應包括作為路由判定 系統PSS2計算的路由計算結果的冗餘路徑的路由候選。當接收來自路由判定系統PSS2的 路由計算響應時，路由判定系統PSS3執行路由計算過程160。在由路由判定系統PSS3執行 的路由計算過程160中，首先使區間路徑抽象單元205對路由計算響應中包括的冗餘路徑 的路由候選進行抽象，並且將抽象的路由候選的拓撲添加到域DM3的拓撲信息中。接下來， 使路由計算單元206使用添加有抽象的路由候選的拓撲信息來計算域DM3中的冗餘路徑的 路由候選。此後，使路由計算請求響應單元203向路由判定系統PSSl發出路由計算響應 所計算的路由候選被添加到接收的路由計算響應中包括的路由候選。當接收來自路由判定系統PSS3的路由計算響應時，路由判定系統PSSl以與路由 判定系統PSS3相同的方式執行路由計算過程160。此後，路由判定系統PSSl向請求發起 方106發出路由計算響應本地計算的路由候選被添加到接收的路由計算響應中包括的路 由候選。這樣，通過每個路由判定系統100重複路由計算過程160並且通過添加計算獲得 的路由，最終向請求發起方106發送包括從起始節點101到結束節點102的冗餘路徑的計 算結果在內的路由計算響應。圖4示出了路由判定系統選擇過程(PSS選擇過程)150的過程。當接收路由計算 請求時(步驟S310)，路由計算請求響應單元203檢查結束節點是否在路由計算請求響應單 元203所屬的本地路由計算域中(步驟S320)。當結束節點在時，路由計算請求響應單元 203指示路由計算單元206起始具有限制的路由計算(步驟S350)。當結束節點不在時，路 由計算請求響應單元203請求PSS選擇單元204選擇向其請求後續計算的路由判定系統， 換言之，路由計算請求的發送目的地的路由判定系統100。接收該請求的PSS選擇單元204 使用路由計算域信息210以及可達性信息211來選擇路由計算請求的發送目的地的路由判 定系統(步驟S330)。此後，路由計算請求響應單元203向在步驟S330中選擇的路由判定 系統發送路由計算請求(步驟S340)。詳細地給出將至結束節點102的可達性信息與至路由判定系統100的可達性信息 進行比較的技術的解釋，作為步驟S330中的路由判定系統100的選擇技術。將該技術稱作 網關映射。網關指示與另一路由計算域相連的邊界節點。這種可達性信息的示例是作為IP 網絡中的傳送路由的可達性信息、以及由ITU-T ASON規範的多層網絡中的可達性信息、以 及由路由協議(比如OSPF、IS-IS或者BGP)通知的可達性信息。圖5示出了通知與路由判定系統PSS3相關的可達性信息的示例路由。箭頭指示了 與路由判定系統PSS3相關的可達性信息的流動。此外，圖6示出了通知與結束節點相關的 可達性信息的示例路由。類似地，箭頭以相同方式指示了可達性信息的流動。與路由判定 系統PSS3相關的可達性信息從域DM3到域DM1，並且到達域DMl中的路由判定系統PSS1。 與路由判定系統PSS3相關的可達性信息還通過域DM2和域DM4從域DM3到域DM1，並且到 達路由判定系統PSS1。與結束節點102相關的可達性信息通過域DM3或者域DM4從域DM2 到域DMl，並被通知給路由判定系統PSSl。路由判定系統PSSl可以通過參照通過圖5和圖6中所示的路由來通知的到達信 息，來確定來自路由判定系統PSS3的信息等通過哪個邊界域BN到達域DMl。此外，到達信息包括與從離開路由判定系統PSS3到達路由判定系統PSSl的路由代價相關的信息，使得 路由判定系統PSSl可以通過分析到達信息來確定哪個邊界節點可以以多少代價到達路由 判定系統PSS3。
圖7示出了通過分析圖5和圖6所示的路由到達的可達性信息而獲得的可達性信 息的特定示例。將通知給每個路由判定系統100的可達性信息以圖7所示的表T200的形式 存儲到所有路由判定系統和節點。表T200的內容與圖2中的可達性信息211相對應。此 夕卜，圖7所示的表210與圖2中的路由計算域信息210相對應。注意，在表T210中，省略了 邊界節點和鄰接的路由計算域之間的對應關係。當接收路由計算請求時，路由判定系統PSSl基於路由計算請求中包括的結束節 點標識符，通過參照圖7所示的表T200來選擇可以以最小代價到達結束節點的邊界節點 (BN2)。接下來，搜索具有該邊界節點BN2作為邊界節點候選的路由判定系統100，並且獲得 路由判定系統PSS2、路由判定系統PSS3以及路由判定系統PSS4。此後，使用相鄰信息(圖 7中的表T210)將所獲得的路由判定系統100的候選縮窄至僅有鄰接的路由判定系統。通 過縮窄，留下路由判定系統PSS3和路由判定系統PSS4。此後，將留下的路由判定系統的代 價互相比較，並且最終選擇具有最小代價的路由判定系統PSS3。這樣，有可能使用與路由判 定系統相關的可達性信息以及與結束節點相關的可達性信息來選擇具有最優代價的鄰接 路由判定系統。注意，在圖7中，由矩形虛線圍繞的信息(不確定信息T201)是不確定信息，具有 根據路由協議的不進行通知的可能性。即，不清楚要通知該信息還是不通知該信息。已經 給出了對通知這些不確定信息的情況的解釋。當不存在不確定信息時，即當不通知可達性 信息時，該欄位變為空，並且僅由PSS選擇單元204從選擇過程中的選擇中排除，使其不影 響操作。此外，即使通知這些不確定信息，由於代價比較，PSS選擇單元204在選擇過程中 不選擇這些信息，這是由於存在路由判定系統與以較低代價到達的邊界節點的組合。圖8示出了路由計算過程160的過程。在PSS選擇過程150中選擇的路由計算域 中，將起始節點所屬的路由計算域DMl稱作起始點路由計算域，將結束節點所屬的路由計 算域DM2稱作結束點路由計算域，並且將其它路由計算域DM3和DM4都稱作中間路由計算 域。屬於結束點路由計算域DM2的路由判定系統PSS2以圖4中的步驟S350中具有限制的 路由計算的開始作為觸發，來開始路由計算過程160，屬於中間路由計算域或者起始點路由 計算域的路由判定系統100以作為對路由計算請求的響應的路由計算響應的接收作為觸 發，來開始路由計算過程160 (步驟S410)。在路由計算過程的開始，路由判定系統100確定路由判定系統100所屬的本地域 是否是結束點路由計算域，以及路由判定系統100所屬的本地域是否是起始點域(步驟 S420、步驟S440)。當路由判定系統100所屬的本地域是結束點路由計算域時，使路由計算 單元206執行路由計算，以計算結束點路由計算域中的冗餘路徑的路由候選(步驟S450)。 在該過程中，路由計算單元206通過參照拓撲信息212以及路由計算域信息210，計算從連 接至中間路由計算域的所有邊界節點對至結束節點的冗餘路徑的候選。此後，使路由計算 請求響應單元203向發出路由計算請求的發起方的路由判定系統發出包括計算結果在內 的路由計算響應(步驟S460)。當路由判定系統100所屬的本地域不是結束點域時，即當路由判定系統100所屬的本地域是中間路由計算域或者起始點路由計算域時，路由判定系統100使區間路徑抽象 單元205將路由計算響應中包括的路由候選作為具有限制的鏈路與虛擬結束節點一起注 冊到拓撲信息中(步驟S430)。此後，當路由判定系統100所屬的本地域是中間路由計算 域時，該過程從步驟S440轉移至步驟S450，計算從連接至起始點路由計算域或者連接至 中間路由計算域的所有邊界節點對至虛擬結束節點的冗餘路由的候選，並且在步驟S460 中向屬於起始點路由計算域或者另一中間路由計算域的路由判定系統100發出包括這些 路由計算結果在內的路由計算響應。當路由判定系統100所屬的本地域是起始點路由計 算域時，路由判定系統100使路由計算單元206計算從起始節點到虛擬結束節點的冗餘路 由(步驟S470)，並且向請求發起方106發出包括該計算結果在內的路由計算響應(步驟 S480)。
給出對前述路由計算的示例的解釋。圖9示出了多域網絡的示例拓撲。圖9示出 了在PSS選擇過程150設置路由計算域之後路由計算域的序列，並且域DMl配置為起始點 路由計算域，域DM3配置為中間路由計算域，域DM2配置為結束點路由計算域。在圖9中， 由S來表示起始節點101，由D來表示結束節點102，由Bm至BN3來表示位於路由計算域 的邊界上的邊界節點103，並且由Tl至T6來表示其它節點(中間節點104)。注意，在連接 每個節點的鏈路中，將用於路由計算的代價統一設置為10。此外，儘管沒有在圖9中示出， 在每個路由計算域中逐以布置路由判定系統。給出對計算圖9所示的樣本拓撲中從節點S到節點D的冗餘路徑的路由的過程的 解釋。由請求發起方發出的路由計算請求從起始點路由計算域DMl通過中間路由計算域 DM3到達屬於結束點路由計算域DM2的路由判定系統PSS2。首先，給出對結束點路由計算 域DM2中的路由計算的解釋。圖10和圖11分別示出了用於結束點路由計算域DM2中的計 算的拓撲以及所計算的冗餘路徑的候選。結束點路由計算域DM2的路由判定系統100計算 在中間路由計算域DM3和結束點路由計算域DM2之間的所有邊界節點對與結束節點之間路 由不重疊的冗餘路徑。下面示出了一種計算從每個邊界節點對到結束節點D的路由不重疊的冗餘路徑 的有效算法。首先，在圖10所示的拓撲中，使用Dijkstra算法來計算從結束節點D到邊界 節點BN6的最短路徑，並且在將所獲得的最短路徑所使用的鏈路從拓撲信息中刪除的拓撲 中，以相同方式使用Dijkstra算法來計算從結束節點D到邊界節點BN7和BN8的最短樹的 路徑。接下來，在圖10所示的拓撲中，在將通過使用Dijkstra算法計算的從結束節點D到 邊界節點BN7的最短路徑而獲得的最短路徑所使用的鏈路從拓撲信息中刪除的拓撲中，以 相同方式使用Dijkstra算法來計算從D到BN8的最短樹的路徑。下面是這些路由的總結。當BN6與BN7配對時(對1)的冗餘路徑的候選到D的冗餘路由D至T4至BN6 20代價，D至T6至T5至BN7 30代價當BN6與BN8配對時(對2)的冗餘路徑的候選到D的冗餘路由D至T4至BN6 20代價，D至T6至BN8 20代價，以及當BN7與BN8配對時(對3)的冗餘路徑的候選到D的冗餘路由D至T6至BN8 20代價，D至T4至T5至BN7 30代價通過前述計算得到圖11的表T220中所示的冗餘路徑的候選對。將這些對通知給 屬於中間路由計算域DM3的路由判定系統100。這樣，使用從結束節點到邊界節點的最短樹計算，可以通過嘗試Dijkstra算法來計算到所有邊界節點對的冗餘路徑對的路由(少於到每個邊界節點對的冗餘路徑的路由計算)。圖11示出了與相應冗餘路徑中的邊界節點對相 對應的虛擬結束節點D」、D」以及D」』。接下來，給出對中間路由計算域DM3中的路由計算的解釋。圖12和圖13分別示 出了用於中間路由計算域DM3中的計算的拓撲以及所計算的冗餘路徑的候選。中間路由 計算域DM3的路由判定系統PSS3使用下述拓撲來執行路由計算將在結束點路由計算域 DM2中計算的冗餘路徑的路由作為具有關於虛擬結束節點105的限制的鏈路添加到中間路 由計算域DM3的拓撲中。針對每個虛擬結束節點105創建具有限制的鏈路是為了維護限制 信息在結束點路由計算域DM2中計算的冗餘路徑的路由不互相共享網絡資源，並且結束 點路由計算域DM2中的每一個路徑候選對1、2、3與至D』、D」或者D」』 (作為虛擬結束節點 105)的具有限制的鏈路相對應。中間路由計算域DM3的路由判定系統PSS4計算具有在起始點路由計算域DMl和 中間路由計算域DM3之間的所有邊界節點對與所有虛擬結束節點105之間不重疊的路由 的冗餘路徑。計算具有從每個邊界節點對到每個虛擬結束節點105不重疊的路由的冗餘 路徑的算法是與結束點路由計算域DM2中的冗餘路徑計算的算法相同的算法。即，首先在 圖12所示的拓撲中，使用Dijkstra算法來分別計算從D、D』以及D」』到Bm的最短路徑， 並且在將分別獲得的最短路徑所使用的鏈路從拓撲信息中刪除的拓撲中，以相同方式使用 Dijkstra算法來分別計算從D、D」以及D」』到BN2和BN3的最短樹路徑。接下來在圖12所 示的拓撲中，使用Di jkstra算法來分別計算從D』、D」以及D」』到BN2的最短路徑，並且在將 分別獲得的最短路徑所使用的鏈路從拓撲信息中刪除的拓撲中，以相同方式使用Dijkstra 算法來分別計算從D』、D」以及D」』到BN3的最短樹路徑。下面是通過前述計算獲得的路由的總結。當Bm與BN2配對時的冗餘路徑的候選到D，的冗餘路由D，至BN6至Tl至Bm 40代價，D，至BN7至T2至BN2 50代 價到D」的冗餘路由D」至BN6至Tl至Bm 40代價，D」至BN8至T3至T2至BN2 50代價到D」，的冗餘路由D」，至BN7至T2至Tl至Bm 60代價，沒有冗餘路由當Bm與BN3配對時的冗餘路徑的候選到D，的冗餘路由D，至BN6至Tl至Bm 40代價，D，至BN7至T2至T3至BN3 60代價到D」的冗餘路由D」至BN6至Tl至Bm 40代價，D」至BN8至T3至BN3 40代 價到D」，的冗餘路由D」，至BN7至T2至Tl至Bm 60代價，D」，至BN8至T3至 BN3 40代價當BN2與BN3配對時的冗餘路徑的候選到D，的冗餘路由D，至BN7至T2至BN2 50代價，沒有冗餘路由到D」的冗餘路由D」至BN6至Tl至T2至BN2 50代價，D」至BN8至T3至BN3 40代價
到D」，的冗餘路由D」，至BN8至T3至BN3 40代價，D」，至BN7至T2至BN2 50 代價虛擬結束節點D』、D」以及D」』指示相同的結束節點，使得可以通過代價比較來選 擇到邊界節點對的最合適的路由。注意，作為選擇路徑的準則，儘管考慮冗餘路徑的代價和 最小的冗餘路徑候選、具有最小代價路由的冗餘路徑候選等等，但是假定選擇具有最小代 價和的冗餘路徑候選。此外，當存在具有最小代價和的多個冗餘路徑候選時，儘管可以選擇 全部多個冗餘路徑候選作為具有相等代價的路徑，但是假定在本情況中選擇單個冗餘路徑 候選。
通過前述操作，設置了圖13中表T230中所示的冗餘路徑候選對。這樣，使用從結 束節點到邊界節點的最短樹計算，可以通過嘗試Di jkstra算法來計算到所有邊界節點對 的冗餘路徑對的路由(少於到每個邊界節點對的冗餘路徑的路由計算)。接下來，給出對起始點路由計算域DMl中的路由計算的解釋。圖14和圖15分別 示出了用於起始點路由計算域DMl中的計算的拓撲以及冗餘路徑的計算結果。起始點路由 計算域DMl中的路由判定系統PSSl使用下述拓撲來執行路由計算將在中間路由計算域 DM3中計算的冗餘路徑的路由作為每個虛擬結束節點105的具有限制的鏈路添加至起始點 路由計算域DMl的拓撲中。針對每個虛擬結束節點創建具有限制的鏈路是為了維護限制信 息在中間路由計算域DM3中計算的冗餘路徑的路由不互相重疊，並且中間路由計算域DM3 中的每個路徑候選對1、2、3與到DD』、DD」或者DD」』的具有限制的鏈路相對應。起始點路由計算域DMl中的路由判定系統PSSl計算在起始節點S和所有虛擬結 束節點之間不具有重疊路由的冗餘路徑。首先，在圖14所示的拓撲中，使用Dijkstra算法 分別計算從DD』、DD」以及DD」』到節點S的最短路徑，並且在將分別獲得的最短路徑所使用 的鏈路從拓撲信息中刪除的拓撲中，以相同方式使用Dijkstra算法分別計算從DD』、DD」以 及DD」』到節點S的最短樹的路徑。下面是通過前述計算獲得的路由的總結。到DD，的冗餘路由DD，至層1至S 50代價，DD，至BN2至S 60代價到DD，，的冗餘路由DD」至BNl至S :50代價，DD，，至BN3至S :50代價到DD」，的冗餘路由DD」，至BN2至S 60代價，DD」，至BN3至S 60代價虛擬結束節點DD』、DD」以及DD」』指示相同的結束節點，使得可以基於代價來選擇 從起始節點S到結束節點N的最合適的路由。注意，作為選擇路徑的準則，儘管考慮冗餘路 徑的代價和最小的冗餘路徑候選、具有最小代價路由的冗餘路徑候選等等，但是假定選擇 具有最小代價和的冗餘路徑候選。此外，當存在具有最小代價和的多個冗餘路徑候選時，盡 管可以選擇全部多個冗餘路徑候選作為具有相等代價的路徑，但是假定在本情況中選擇單 個冗餘路徑候選。通過前述操作，將圖15中表T240中所示的冗餘路徑設置為最合適的路 徑，並且可以獲得跨越多個域的路由計算結果。根據實施例，通過下述步驟來計算起始節點和結束節點之間的冗餘路徑的路由 設置從起始節點所在的路由計算域到結束節點所在的路由計算域要經過的路由計算域、使 從結束節點所在的路由計算域側到起始節點所在的路由計算域的每個路由判定系統100 中的路由計算單元206順序執行冗餘路徑的路由計算，並且將相應路由判定系統計算的冗 餘路徑的路由組合在一起。將結束節點所在的路由計算域側的路由判定系統的計算結果包 括在計算響應中並通知給起始節點所在的路由計算域側的路由判定系統或者通知給發出請求的發起方。這樣，在劃分為多個路由計算域的多域網絡中，在每個路由計算域中的路由計算中不重新開始反覆試驗的情況下，可以多個路由判定系統一起工作來計算冗餘路徑， 以不共享網絡資源。此外，根據實施例，PSS選擇單元204在從與路由判定系統所屬的本地域相鄰的路 由計算域中選擇路由計算請求的發送目的地的路由判定系統(路由計算域)時，選擇與可 以到達結束節點的邊界節點鄰接的路由計算域作為要將路由計算請求發送至的路由計算 域。這允許選擇可到達結束節點的路由計算域，使得可以抑制由選擇不能到達結束節點的 路由計算域而導致重新開始對路由計算域的選擇。此外，在選擇路由計算域時，可以通過選 擇以最小代價到達結束點域的路由計算域來維持冗餘路徑的代價較低。接下來，給出對本發明的第二實施例的解釋。圖16示出了根據第二實施例的路 由判定系統的配置。路由判定系統IOOa包括拓撲信息收集單元201、路由計算域管理單元 202、路由計算請求響應單元203、PSS選擇單元204、路由計算請求複製單元250、區間路徑 抽象單元205、以及路由計算單元206。由計算機系統來配置路由判定系統100a，並且通過 運行安裝在計算機系統中的程序來實現路由判定系統IOOa中的每個單元的功能。與第一 實施例的不同之處在於，添加了將接收的路由計算請求複製為等於或者多於兩個路由計算 請求的路由計算請求複製單元250，並且省略了路由計算域管理單元202中的可達性信息 211。第二實施例中的網絡配置與圖1所示的網絡配置相同。根據第二實施例，PSS選擇單元204通過參照路由計算域信息210來選擇屬於與 PSS選擇單元204鄰接的路由計算域的路由判定系統作為要將路由計算請求發送至的路由 判定系統。當存在PSS選擇單元204要選擇的多個路由判定系統時，路由計算請求複製單 元205以與所需數量相對應的倍數來複製路由計算請求，並且將路由計算請求發送至PSS 選擇單元204選擇的相應路由判定系統。重複路由計算請求的複製和發送，直到路由計算 請求到達屬於結束節點102所在的路由計算域DM2的路由判定系統PSS2。此後，通過下述 步驟來設置冗餘路徑的路由從結束點路由計算域DM2側開始，對已經到達屬於結束點路 由計算域DM2的路由判定系統PSS2的路由計算請求順序執行路由計算，並且在屬於起始點 路由計算域101的路由判定系統PSSl中比較代價。圖17示出了第二實施例中當多個路由判定系統IOOa執行冗餘路徑的路由計算 時的過程。當路由計算的請求發起方106 (圖1)發出路由計算請求時，路由判定系統PSSl 執行路由判定系統選擇過程170，並且將與路由判定系統PSSl所屬的本地域DMl鄰接的域 DM3和域DM4設置為路由計算請求的發送目的地。路由判定系統PSSl使路由計算請求複製 單元205複製路由計算請求，並且將路由計算請求傳送至路由判定系統PSS3和路由判定系 統PSS4。接收路由計算請求的路由判定系統PSS3和路由判定系統PSS4以與路由判定系統 PSSl相同的方式來執行路由判定系統選擇過程170，將與路由判定系統PSS3和路由判定系 統PSS4分別鄰接的域DM2設置為路由計算請求的發送目的地，並且將路由計算請求傳送至 路由判定系統PSS2。這樣，在每個路由判定系統IOOa中重複PSS選擇過程允許請求發起方 發出的路由計算請求到達屬於結束節點102所在的域DM2的路由判定系統PSS2。在圖17中，路由計算請求通過兩個路由到達路由判定系統PSS2 —個從域DMl通 過域DM3到達域DM2 ；另一個從域DMl通過域DM4到達域DM2。路由判定系統PSS2對每個接收的路由計算請求執行路由計算過程180，並且向路由計算請求的發送發起方的路由判定系統發出包括路由計算結果在內的路由計算響應。即，向路由判定系統PSS3發出包括對 從路由判定系統PSS3接收的路由計算請求的路由計算結果在內的路由計算響應(響應1)， 以及向路由判定系統PSS4發出包括對從路由判定系統PSS4接收的路由計算請求的路由計 算結果在內的路由計算響應(響應2)。分別接收路由計算響應的路由判定系統PSS3和路由判定系統PSS4分別執行路由 計算過程180，向接收的路由計算響應中包括的計算結果添加本地計算的結果，並且向路由 判定系統PSSl發出路由計算響應。當分別接收到來自路由判定系統PSS3和路由判定系統 PSS4的路由計算響應時，路由判定系統PSSl對每個路由計算響應執行路由計算過程180。 此後，對使用從路由判定系統PSS3接收的路由計算響應1計算的冗餘路徑的計算結果與使 用從路由判定系統PSS4接收的路由計算響應2計算的冗餘路徑的計算結果互相進行比較， 選擇其中一個計算結果，並且向請求發起方106發出包括所選計算結果在內的路由計算響 應。圖18示出了 PSS選擇過程170的過程。當路由計算請求響應單元203接收路由 計算請求時(步驟510)，路由判定系統IOOa確定結束節點102是否在路由判定系統IOOa 所屬的本地路由計算域中(步驟S520)。當結束節點102在時，使路由計算單元206開始具 有限制的路由計算(步驟S550)。當結束節點102不在時，路由判定系統IOOa使用路由計 算域信息210的相鄰信息(圖7中的T210)來搜索要將路由計算請求發送至的路由判定系 統，即屬於與路由判定系統IOOa所屬的本地路由計算域鄰接的路由計算域的路由判定系 統(步驟S530)。當存在要將路由計算請求發送至的多個路由判定系統IOOa時，使路由計 算請求複製單元250複製與所需數量相對應倍數的路由計算請求，並且向步驟S530中搜索 到的相應路由判定系統發送路由計算請求(步驟S540)。注意，當在步驟S530中在屬於鄰接路由計算域的所有路由判定系統IOOa中搜索 路由判定系統IOOa時，選擇除已經通過重疊的路由接收到路由計算請求的路由判定系統 之外的路由判定系統100a。例如在圖17中，儘管路由判定系統PSSl分別向路由判定系統 PSS3和路由判定系統PSS4發送路由計算請求，但是路由判定系統PSS3和路由判定系統 PSS4不向作為要接收路由計算請求的發起方的路由判定系統PSSl發送路由計算請求。此 夕卜，在搜索路由判定系統時，當不存在相應的路由判定系統時，假定丟棄該路由計算請求。在每個路由判定系統中執行的路由計算過程180與在第一實施例中圖8中所示的 過程中執行的路由計算過程160相同。注意，在第二實施例中，存在路由計算請求通過多個 路由到達屬於結束點路由計算域DM2的路由判定系統PSS2的情況，並且在該情況中，多個 路由計算響應到達屬於起始點路由計算域DMl的路由判定系統PSS1。當接收到多個路由計 算響應時，路由判定系統PSSl對這些相應響應執行路由計算，從這些響應中選擇具有最小 代價的路由，然後向請求發起方106發送所選路由。當屬於起始點路由計算域DMl的路由判定系統PSSl對多個路由計算響應的路由 計算結果進行互相比較時，必須等待直到接收到所有多個路由計算響應。為了等待，屬於起 始點路由計算域DMl的路由判定系統PSSl需要確定多少個路由計算請求已經到達屬於結 束點路由計算域DM2的路由判定系統PSS2。相應地，由屬於結束點路由計算域DM2的路由 判定系統PSS2發出的路由計算響應包括已經到達結束點路由計算域DM2的路由計算請求的總數。這允許屬於起始點路由計算域DMl的路由判定系統PSSl確定要接收的路由計算響應的總數。圖19示出了冗餘路徑的路由計算結果。當在屬於起始點路由計算域DMl的路由 判定系統PSSl中基於對通過從域DMl經由域DM3到達域DM2的路由發送的路由計算請求 的路由計算響應來執行路由計算時，得到冗餘路徑，如當前路徑1 :S至BN3至BN8至D (50代價)；以及備份路徑1 S至BN2至BN7至D (50代價)此外，當在路由判定系統PSSl中基於對通過從域DMl經由域DM4到達域DM2的路 由發送的路由計算請求的路由計算響應來執行路由計算時，得到冗餘路徑，如當前路徑2 :S至BN4至BN9至D (30代價)；以及備份路徑2 :S至BN5至BWO至D (100代價)這樣，根據第二實施例，獲得多個當前路徑對和多個備份路徑的多個對。在從多對當前路徑和備份路徑中選擇路徑中，可以選擇當前路徑代價以及備份路 徑代價的和最小的對作為當前路徑和備份路徑。在圖19中，當前路徑1的代價和備份路徑 1的代價之和是100，當前路徑2的代價和備份路徑2的代價之和是130，使得選擇當前路徑 1和備份路徑1這一對作為當前路徑和備份路徑。備選地，作為該對的替代，可以選擇當前 路徑的代價最小的對作為當前路徑和備份路徑。在圖19中，當前路徑1的代價是50，當前 路徑2的代價是30，使得選擇當前路徑2和備份路徑2這一對作為當前路徑和備份路徑。 此外，可以選擇代價最小的任意對作為當前路徑和備份路徑。在圖19中，以代價的升序來 選擇兩個路徑，並且選擇具有30代價的當前路徑2以及具有50代價的當前路徑1的配對 作為當前路徑和備份路徑。根據第二實施例，路由判定系統PSSl分別向屬於相應路由計算域DM3和DM4的 路由判定系統PSS3和PSS4發送路由計算請求，路由計算域DM3和DM4都與路由判定系統 PSSl所屬的本地路由計算域DMl鄰接，並且最終從結束點路由計算域DM2側開始，對已經到 達屬於結束節點102所在的路由計算域DM2的路由判定系統PSS2的相應路由計算請求順 序執行路由計算。這允許通過從起始點路由計算域DMl可到達結束點路由計算域DM2的路 由來設置路由計算使用的路由計算域，並且可以在每個路由計算域中的路由計算中不重複 進行反覆試驗的情況下，計算被分為多個路由計算域的多域網絡中不共享網絡資源的冗餘 路徑。此外，在第二實施例中使用的是下述方案在鄰接的路由計算域中向屬於除已經接收 到路由計算請求的路由計算域之外的路由計算域的路由判定系統發送路由請求，使得可以 將多個路由計算域作為路由計算的候選，從而實現在更寬的範圍中計算最合適的路徑。注意，在前述每一個實施例中，儘管已經給出了對順序使用Dijkstra算法作為計 算冗餘路徑的路由的算法的示例情況的解釋，本發明並不限於這種情況，其它算法也適用。 此外，在前述每一個實施例中，儘管已經給出了對域的邊界是節點的情況的解釋，但是本發 明還以相同方式適用於邊界是鏈路的情況。儘管已經通過參照具體示出本發明的示例實施例給出了解釋，本發明並不限於這 些實施例及其修改實施例。對於本領域技術人員顯而易見地，可以在不背離由所附權利要 求定義的本發明的精神和範圍的情況下，以各種形式來改變和修改本發明。本申請基於並且要求於2007年10月18日提交的日本專利申請號No. 2007-271687的優先權，在本申請的說明書中其公開以全文引用的形式併入本文中。工業適用性本發明可以用於路由判定系統的應用，以便在將大規模通信網絡劃分為多個域的多域網絡中設置冗餘路徑的路由。此外，本發明不僅可以用於通信網絡，還可以用於汽車、 蜂窩式電話等中配備的導航系統的路由設置功能的應用。
權利要求
一種網絡系統，包括多個路由判定系統，分布並布置在被分為多個路由計算域的多域網絡中，其中每個路由判定系統包括拓撲信息收集單元，收集拓撲信息；路由計算請求響應單元，接收請求對從起始節點到結束節點的冗餘路徑進行路由計算的路由計算請求；以及路由計算單元，響應於路由計算請求，使用拓撲信息並考慮限制來執行路由計算，以及在設置了從所述起始節點所在的路由計算域至所述結束節點所在的路由計算域要經過的路由計算域之後，通過使從所述結束節點所在的路由計算域向所述起始節點所在的路由計算域的每個路由判定系統中的路由計算單元順序執行冗餘路徑的路由計算，並且通過將相應路由判定系統計算的冗餘路徑的路由組合在一起，來計算所述起始節點和所述結束節點之間的冗餘路徑的路由。
2.根據權利要求1所述的網絡系統，其中，來自發出請求的發起方的路由計算請求從 屬於所述起始節點所在的路由計算域的路由判定系統順序發送至屬於所述結束節點所在 的路由計算域的路由判定系統，並且，已經將路由計算請求發送至的路由判定系統所屬的 路由計算域被設置為要用於路由計算的路由計算域。
3.根據權利要求2所述的網絡系統，其中，在執行冗餘路徑的路由計算時，每個路由判 定系統向路由計算請求的發送發起者發出包括冗餘路徑的路由計算結果在內的路由計算 請求。
4.根據權利要求3所述的網絡系統，其中，每個路由判定系統還包括路由計算域管理 單元，基於來自另一路由判定系統、並由拓撲信息收集單元收集的可達性信息來創建相鄰 信息，所述相鄰信息包括指定與每個路由判定系統所屬的本地路由計算域鄰接的路由計算 域的信息；以及路由判定系統選擇單元，使用所述相鄰信息來選擇要將路由計算請求響應 單元接收的路由計算請求發送至的路由判定系統所屬的路由計算域。
5.根據權利要求4所述的網絡系統，其中，路由計算域管理單元分析來自所述另一路 由判定系統、以及來自所述結束節點的可達性信息，並且將路由計算域管理單元所屬的本 地路由計算域與另一路由計算域之間的邊界節點與在從路由計算域管理單元到屬於另一 路由計算域的路由判定系統以及到所述結束節點使用每個邊界節點時的代價相關聯地存 儲為可達性信息表，並且，路由判定系統選擇單元通過參照所述可達性信息表以及所述相 鄰信息，在與路由判定系統選擇單元所屬的本地路由計算域鄰接的路由計算域中選擇通過 能夠到達所述結束節點的邊界節點鄰接的路由計算域作為要將路由計算請求發送至的路 由判定系統。
6.根據權利要求5所述的網絡系統，其中，在選擇要將路由計算請求發送至的路由判 定系統時，在能夠到達所述結束節點的邊界節點中指定具有最小代價的邊界節點，並且選 擇通過所指定的邊界節點鄰接的路由計算域中具有最小代價的路由判定系統作為要將路 由計算請求發送至的路由判定系統。
7.根據權利要求4所述的網絡系統，其中，路由判定系統選擇單元將與路由判定系統 選擇單元所屬的本地路由計算域鄰接的路由計算域設置為路由計算請求的發送目的地，並 且，當存在多個發送目的地時，路由判定系統選擇單元複製路由計算請求，並且將路由計算 請求發送至屬於被設置為發送目的地的每個相應路由計算域的相應路由判定系統。
8.根據權利要求7所述的網絡系統，其中，當接收到來自所述多個路由判定系統的路由計算響應時，屬於所述起始節點所在的路由計算域的路由判定系統的路由計算單元使用 所接收的相應路由計算響應來執行路由計算，比較路由計算結果，並設置要發送至所述起 始節點的路由計算響應中要包括的路由。
9.根據權利要求4至8中任一項所述的網絡系統，其中，當路由計算請求響應接收到路 由計算請求時，路由計算單元確定所述結束節點是否在路由計算單元所屬的本地路由計算 域中，並且，當確定所述結束節點不在路由計算單元所屬的本地路由計算域中時，請求路由 判定系統選擇單元選擇路由計算請求的發送目的地的路由計算域。
10.根據權利要求9所述的網絡系統，其中，當確定所述結束節點在路由計算單元所屬 的本地路由計算域時，路由計算單元使用拓撲信息來計算路由計算單元所屬的本地路由計 算域和作為路由計算請求的發送發起方的路由計算系統所屬的路由計算域之間的邊界節 點與所述結束節點之間的冗餘路徑的路由候選，並且通過路由計算請求響應單元向路由計 算請求的發送發起方發出包括所計算的冗餘路徑的路由候選在內的路由計算響應。
11.根據權利要求10所述的網絡系統，其中，當路由計算請求響應單元接收到來自路 由計算請求發送目的地的路由判定系統的路由計算結果時，路由計算單元確定所述起始節 點是否在路由計算單元所屬的本地路由計算域中，並且，當確定所述起始節點不在路由計 算單元所屬的本地路由計算域中時，使用通過將具有在路由計算請求發送目的地的路由判 定系統中計算的冗餘路徑的抽象路由候選的拓撲添加到上述拓撲信息中而獲得的拓撲信 息來計算路由計算單元所屬的本地路由計算域中的冗餘路徑的路由候選，並且通過路由計 算請求響應單元向路由計算請求的發送發起方的路由判定系統發出包括所計算的冗餘路 徑的路由候選在內的路由計算響應。
12.根據權利要求11所述的網絡系統，其中，當確定所述起始節點在路由計算單元所 屬的本地路由計算域中時，路由計算單元使用通過將具有在路由計算請求發送目的地的路 由判定系統中計算的冗餘路徑的抽象路由候選的拓撲添加到上述拓撲信息中而獲得的拓 撲信息來計算路由計算單元所屬的本地路由計算域中的冗餘路徑的路由候選，從所獲得的 路由候選中選擇路由候選，並且通過路由計算請求響應單元向路由計算請求的請求發起方 發出路由計算響應，所述路由計算響應包括將相應路由判定系統計算的相應路由計算域中 的冗餘路徑的路由組合在一起的路由。
13.根據權利要求11或12所述的網絡系統，其中，在對路由候選進行抽象時，將從另一 路由判定系統獲得的冗餘路徑的路由候選註冊到拓撲信息中作為與虛擬結束節點相關聯 的限制。
14.根據權利要求4至13中任一項所述的網絡系統，其中，所述可達性信息由IGP內部 網關協議獲得。
15.根據權利要求4至13中任一項所述的網絡系統，其中，所述可達性信息由SNMP簡 單網絡管理協議獲得。
16.一種路由判定系統，與多域網絡中的多個路由計算域中的至少一個相對應地布置， 所述路由判定系統包括拓撲信息收集單元，收集拓撲信息；路由計算請求響應單元，接收請求對從起始節點到結束節點的冗餘路徑進行路由計算 的路由計算請求；路由判定系統選擇單元，當所述結束節點不在所述路由判定系統選擇單元所屬的本地 路由計算域時，選擇要將所述路由計算請求發送至的路由判定系統所屬的路由計算域；以 及路由計算單元，當所述結束節點在所述路由計算單元所屬的本地路由計算域時，使用 拓撲信息並考慮限制來執行冗餘路徑的路由計算，並向所述路由計算請求的發送發起方發 出包括路由計算結果在內的路由計算響應。
17.根據權利要求16所述的路由判定系統，還包括區間路徑抽象單元，對路由計算響 應中包括的路由計算結果進行抽象，並且將所抽象的路由計算結果添加至拓撲信息，其中， 當路由計算請求響應單元接收到來自另一路由判定系統的路由計算響應時，路由計算單元 使區間路徑抽象單元使用抽象和添加了路由計算響應中包括的路由計算結果的拓撲信息 來計算冗餘路徑的路由，並且向路由計算請求的發送發起方發出包括路由計算的結果在內 的路由計算響應。
18.一種由多個路由判定系統來計算從起始節點到結束節點的跨越路由計算域的冗餘 路徑的路由的方法，所述多個路由判定系統分布並布置在多域網絡中並且一起工作，所述 方法包括使用每個路由判定系統保持的相鄰信息來設置從所述起始節點到所述結束節點的路 由所經過的路由計算域的步驟；以及使屬於所設置的路由計算域的路由判定系統從屬於所述結束節點所在的路由計算域 的路由判定系統向屬於所述起始節點所在的路由計算域的路由判定系統遞歸地執行路徑 計算的步驟。
19.根據權利要求18所述的路由計算方法，其中，在設置路由計算域的步驟中，從所述 起始節點所在的路由計算域開始，在鄰接的路由計算域中順序選擇能夠到達所述結束節點 所在的路由計算域的路由計算域。
20.根據權利要求18所述的路由計算方法，其中，在設置路由計算域的步驟中，選擇從 所述起始節點所在的路由計算域到所述結束節點所在的路由計算域能夠經過的所有路由 計算域，執行路徑計算的步驟對每個所選擇的路由計算域來執行，並且通過對路徑計算所 獲得的冗餘路徑的路由的代價進行比較來設置所述起始節點和所述結束節點之間的路由。
21.根據權利要求18至20中任一項所述的路由計算方法，其中，在執行路徑計算的步 驟中，接收在比本地路由計算域更接近於所述結束節點的路由計算域中計算的冗餘路徑的 計算結果，並且使用路由計算域中添加具有關於虛擬結束節點的限制的鏈路的拓撲來執行 路由計算，所述鏈路維護與冗餘限制相關的信息。
22.根據權利要求21所述的路由計算方法，其中，從虛擬結束節點到每個邊界節點的 路由被共同計算為添加具有關於虛擬結束節點的限制的鏈路的拓撲的最短樹路由。
23.根據權利要求21或22所述的路由計算方法，其中，在執行路徑計算的步驟中，在選 擇冗餘路徑的路由候選時，選擇冗餘路徑的當前路徑的代價與冗餘路徑的備份路徑的代價 之和最小的路由。
24.根據權利要求21所述的路由計算方法，其中，在執行路徑計算的步驟中，在選擇冗 餘路徑的路由候選時，選擇冗餘路徑的當前路徑的代價最小的路由。
25.一種程序，允許計算機執行計算多域網絡中從起始節點到結束節點的跨越路由計算域的冗餘路徑的路由的過程，所述程序允許計算機執行以下過程 接收請求對所述冗餘路徑進行路由計算的路由計算請求；當所述結束節點不在路由判定系統所屬的本地路由計算域時，選擇要將所述路由計算請求發送至的路由判定系統所屬的路由計算域；以及當所述結束節點在路由判定系統所屬的本地路由計算域時，使用拓撲信息並考慮限制 來執行所述冗餘路徑的路由計算，以及向所述路由計算請求的發送發起方發出包括路由計 算結果在內的路由計算響應。
全文摘要
本發明提供了一種布置在多域網絡的每個域中的路由判定系統。所述路由判定系統包括拓撲信息收集單元，收集拓撲信息；路由計算請求響應單元，接收請求對從起始節點到結束節點的冗餘路徑進行路由計算的路由計算請求；以及路由計算單元，響應於所述路由計算請求，使用拓撲信息並考慮限制來執行路由計算。在設置了從所述起始節點所在的起始點域至所述結束節點所在的結束點域的域之後，在從結束點域通過中間域向起始點域的每個域中順序執行冗餘路徑的路由計算。
文檔編號H04L12/56GK101828363SQ20088011186
公開日2010年9月8日 申請日期2008年10月17日 優先權日2007年10月18日
發明者西岡到, 飯澤洋平 申請人:日本電氣株式會社