路徑設置伺服器、路徑設置方法和路徑設置程序的製作方法

2023-10-10 16:03:04

專利名稱：路徑設置伺服器、路徑設置方法和路徑設置程序的製作方法
技術領域：
本發明涉及通過使用路由設置伺服器來確定通信網絡中的流的通信路由的技術。
背景技術：
已知一種通信網絡系統，在該系統中，管理伺服器執行對包括多個節點的通信網絡的集中式管理。當接收到關於流的路由設置請求時，管理伺服器確定該通信網絡中的流的通信路由。此後也將確定流的通信路由的此類管理伺服器稱為「路由設置伺服器」。作為用於計算從源節點到目的地節點的最短路由的算法，「Di jkstra算法」是公知的。然而，在源節點與目的地節點之間執行多個流的通信的情況中，簡單地使用Dijkstra 算法導致相同的通信路由(最短路由)被用於多個流。這使得施加在通信路由上的負載增加並且因此降低通信效率。為了對負載進行分布，優選的是為同一對源節點和目的地節點之間的不同流設置不同的通信路由。為此，考慮不僅提取最短路由還提取源節點與目的地節點之間的其他通信路由。以下稱作用於計算從源節點到目的地節點的多個通信路由的技術。專利文獻1(日本專利公開JP-2003-233768)描述了一種通過使用雙Dijkstra 算法來計算從起點到終點的多個通信路由。更具體地，關於所有中間節點，Dijkstra算法從起點創建各個最短路由樹。而且，關於所有中間節點，Dijkstra算法從終點創建各個最短路由樹。然後，組合兩種最短路由樹來計算從起點到終點通過各個不同中間節點的多個通信路由。此外，在專利文獻2(日本專利公開JP-2003-23446)中還描述了通過組合多次 Dijkstra算法來計算多個路由的方法。1 (Jun Inagaki ^^"A method of Determining Various Solutions for Routing Application with a Genetic Algorithm，，，The Transactions of the Institute of Electronics, Information and Communication Engineers, D-I, Vol. J82-D-I，No. 8 (19990825), pp. 1102-1111。)描述了通過使用通用算法來同時計算多個通
信路由的方法。專利文獻3(日本專利公開JP-2007-515906)描述了多跳通信網絡中的代價確定方法。該代價確定方法包括關於網絡中從源節點到目的地節點的多個節點中的至少一個來確定多個同時的可能下一跳的步驟。多個同時可能的多個節點優化預定的代價函數。此外， 該代價確定方法包括確定多個節點中至少一個的最佳代價，從而等於預定代價函數的上述
最佳值。引用列表[專利文獻1]日本專利公開JP-2003-233768[專利文獻2]日本專利公開JP-2003-23446[專利文獻3]日本專利公開JP-2007-515906非專利文獻[非專利文獻 l]Jun Inagaki 等的 『『A method of Determining VariousSolutions for Routing Application with a Genetic Algorithm，，,The Transactions of the Institute of Electronics, Information and Communication Engineers, D-I, Vol. J82-D-I，No.8 (19990825)，pp.1102-1111。

發明內容
為了分發施加在通信網絡上的負載，期望針對相同的源節點和目的地節點對之間的不同流設置不同的通信路由。為此，考慮計算從源節點到目的地節點的多個通信路由，如上述相關技術中描述的。當新的流出現時，可以這樣來分發負載從多個通信路由中選擇合適的一個，並且繼而向新的流分配所選擇的通信路由。然而，根據上文描述的有關技術，確定通信路由的路由設置伺服器中的計算量變得巨大。在採用Dijkstra算法的情況中，計算量與節點的總數成比例地指數增加。例如，在 8維超立方體網絡的情況中，源節點與目的地節點之間的通信路由具有約四萬種模式，並且預先計算所有它們實際上是不可能的。而且，在採用通用算法的情況中，問題在於計算需要長的收斂時間並且計算量仍舊巨大。本發明的目的是當通過使用路由設置伺服器來確定流的通信路由時減少路由設置伺服器中的計算量。在本發明的一個方面中，提供了一種路由設置伺服器，該路由設置伺服器確定包括多個節點的通信網絡中的流的通信路由。路由設置伺服器具有存儲單元和路由設計單元。在存儲單元中存儲下一跳信息，其中對於所述多個節點中的每一個，所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選。響應於指定流的源節點和目的地節點的路由設置請求，路由設計單元設計從源節點到目的地節點的通信路由。更具體地，路由設計單元具有下一跳確定單元，被配置為參考下一跳信息執行「下一跳確定處理」；環檢測單元；以及環刪除單元。在下一跳確定處理中，下一跳確定單元從關於目標節點的下一跳節點的候選隨機地選擇一個下一跳節點，並且將目標節點更新為上述選擇的一個下一跳節點。下一跳確定單元通過如下方式來逐跳地確定通信路由將目標節點初始化為源節點，繼而重複下一跳確定處理直到目標節點成為目的地節點。環檢測單元檢查當前目標節點是否與過去的目標節點重疊，以檢測到那時為止確定的通信路由上的環。如果檢測到環，則環刪除單元通過將目標節點轉回到任何過去的目標節點來刪除環。在刪除環之後，下一跳確定單元從上述任何過去的目標節點重新開始下一跳確定處理。在本發明的另一方面中，提供一種通信網絡系統。該通信網絡系統具有通信網絡，包括多個節點；以及路由設置伺服器，確定通信網絡中的流的通信路由。路由設置伺服器具有存儲單元和路由設計單元。下一跳信息存儲在存儲單元中，其中對於多個節點中的每一個，下一跳信息指示作為數據轉發目的地的下一跳節點的候選。響應於指定流的源節點和目的地節點的路由設置請求，路由設計單元設計從源節點到目的地節點的通信路由。 更具體地，該路由設計單元具有下一跳確定單元，被配置為參考下一跳信息來執行「下一跳確定處理」；環檢測單元；以及環刪除單元。在下一跳確定處理中，下一跳確定單元從關於目標節點的下一跳節點的候選隨機地選擇一個下一跳節點，並且將目標節點更新為上述選擇的一個下一跳節點。下一跳確定單元通過如下方式逐跳地確定通信路由將目標節點初始化為源節點，繼而重複下一跳確定處理直到目標節點成為目的地節點。環檢測單元檢查當前目標節點是否與過去的目標節點重疊，以檢測到那時為止確定的通信路由上的環。如果檢測到環，則環刪除單元通過將目標節點轉回到任何過去的目標節點來刪除環。在刪除環之後，下一跳確定單元從上述任何過去的目標節點重新開始下一跳確定處理。在本發明的又一方面中，提供一種路由設置方法，該方法確定包括多個節點的通信網絡中的流的通信路由。該路由設置方法包括(A)在存儲設備中存儲下一跳信息，其中對於多個節點中的每一個，下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及(B)響應於指定流的源節點和目的地節點的路由設置請求來設計從源節點到目的地節點的通信路由。上述(B)步驟包括(Bi)參考下一跳信息執行「下一跳確定處理」。這裡， 下一跳確定處理包括從關於目標節點的下一跳節點的候選隨機地選擇一個下一跳節點。 上述(B)步驟還包括(B》通過將目標節點初始化為源節點並且繼而重複下一跳確定處理直到目標節點成為目的地節點來逐跳地確定通信路由；(Β； )檢查當前目標節點是否與過去的目標節點重疊以檢測到那時為止確定的通信路由上的環；(B4)如果檢測到環，則通過將目標節點轉回到任何過去的目標節點來刪除環；以及(BO在刪除環之後，從任何過去的目標節點重新開始下一跳確定處理。在本發明的又一方面中，提供一種路由設置程序，其使得計算機執行路由設置處理，該路由設置處理確定包括多個節點的通信網絡中的流的通信路由。該路由設置處理包括(A)在存儲設備中存儲下一跳信息，其中對於多個節點中的每一個，下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及⑶響應於指定流的源節點和目的地節點的路由設置請求來設計從源節點到目的地節點的通信路由。上述(B)步驟包括(B1)參考下一跳信息執行「下一跳確定處理」。這裡，下一跳確定處理包括從關於目標節點的下一跳節點的候選隨機地選擇一個下一跳節點；以及將目標節點更新為選擇的一個下一跳節點。上述(B)步驟還包括(B》通過將目標節點初始化為源節點並且繼而重複下一跳確定處理直到目標節點成為目的地節點來逐跳地確定通信路由；(Β； )檢查當前目標節點是否與過去的目標節點重疊以檢測到那時為止確定的通信路由上的環；(B4)如果檢測到環，則通過將目標節點轉回到任何過去的目標節點來刪除環；以及(BO在刪除環之後，從所述任何過去的目標節點重新開始下一跳確定處理。根據本發明，當通過使用路由設置伺服器來確定通信網絡中的流的通信路由時， 降低路由設置伺服器中的計算量是可能的。


結合附圖，根據某些示例性實施方式的以下描述，本發明的上述和其他目的、優勢和特徵將更明顯。圖1是示出了根據本發明一個示例性實施方式的通信網絡系統的示意圖。圖2是示出了從源節點到目的地節點的多個通信路由的概念圖。圖3是示出了根據本發明第一示例性實施方式的、路由設置伺服器的配置的框圖。圖4是示出了目標節點、目的地節點與下一跳節點之間的關係的概念圖。圖5是示出了路由表的概念圖。圖6是示出了根據第一示例性實施方式的路由設置方法的流程圖。
圖7是示出了路由節點列表的概念圖。圖8是示出了第一示例性實施方式中下一跳確定處理的流程圖。圖9是示出了根據本發明第二示例性實施方式的、路由設置伺服器的配置的框圖。圖10是示出了路由高速緩存信息的概念圖。圖11是示出了根據第二示例性實施方式的、路由設置方法的流程圖。圖12是示出了根據本發明第三示例性實施方式的、路由設置伺服器的配置的框圖。圖13是示出了鏈路代價表的概念圖。圖14是示出了路由代價表的概念圖。圖15是示出了第三示例性實施例中下一跳確定處理的流程圖。
具體實施例方式將參考附圖來描述本發明的示例性實施方式。1.通信網絡系統圖1是示出了根據本發明一個示例性實施方式的通信網絡系統1的示意圖。通信網絡系統1具有包括多個節點5的通信網絡NET。在本示例性實施方式中，通信網絡NET包括η個節點5-1到5-η (η是等於或大於2的整數)。該通信網絡系統1還具有路由設置伺服器10。路由設置伺服器10是管理伺服器 (管理計算機)，該管理伺服器執行通信網絡NET的集中式管理並且能夠與多個節點5-1到 5-η進行雙向通信。特別地，路由設置伺服器10確定在通信網絡NET中流的通信路由。更具體地，當流出現時，路由設置伺服器10從通信網絡NET接收關於流的路由設置請求。該路由設置請求指定流的源節點和目的地節點。響應於路由設置請求，路由設置伺服器10確定從源節點到目的地節點的通信路由。當通信路由被確定時，路由設置伺服器10指示確定通信路由上的每個節點5沿確定的通信路由轉發流的數據(分組、幀)。每個節點5根據該指令執行自身的設置。例如，每個節點5配備有「轉發表」。轉發表是指示流數據(分組、幀)的輸入源與轉發目的地之間對應關係的表。每個節點5可以通過參考轉發表向指定轉發目的地轉發從輸入源接收的流數據。在該情況中，路由設置伺服器10指示每個節點5設置轉發表，使得流數據沿著所確定的通信路被轉發。每個節點5根據來自於路由設置伺服器10的指令來設置其自己的轉發表的內容。各種接口作為路由設置伺服器10和節點5之間用於實現上述處理的接口都是可能的。例如，openflow(參考http://ww. openflowswith. org)是適用的。在該情況中， "Openflow控制器」伺服器作為路由設置伺服器10並且「Openflow交換機」伺服器作為每個節點5。通過使用Openflow的「源信道」設置轉發表是可能的。2.路由設置處理的概述圖2是示出了從源節點5-S到目的地節點5-D的多個通信路由的概念圖。在很多情況中，存在從源節點5-S到目的地節點5-D的多個通信路由，如圖2所示。每個通信路由包括某些中繼節點5-r，並且不同的通信路由通過中繼節點5-r的不同組合來配置。為了分布施加在通信網絡NET上的負載，期望針對同一對源節點5-S與目的地節點5-D之間的不同流設置不同的通信路由。根據本示例性實施方式的路由設置伺服器10確定流的通信路由，使得施加在通信網絡NET上的負載被分布。即，路由設置伺服器10可以針對同一對源節點5-S與目的地節點5-D之間的不同流確定了不同的通信路由。為此，當「隨機」地確定流的通信路由時，路由設置伺服器10逐跳地確定從流的源節點5-S朝向目的地節點5-D的中繼節點5-r。艮口， 在確定路由時，針對每跳引入隨機性。結果，非常可能為不同的流確定不同的通信路由。因此，施加在通信網絡NET上的負載被分布並且因此改進了通信效率。根據本示例性實施方式，當確定流的通信路由時，不需要計算從源節點5-S到目的地節點5-D的多個通信路由。相反，針對每跳選擇中繼節點5-r的候選中隨機的一個。在該情況中，在路由設置伺服器10中的計算次數最多是通信路由上的總跳數。因此，路由設置伺服器10中的計算量被大大降低。即，根據本示例性實施方式，可以分布施加在通信網絡NET上的負載並且降低路由設置伺服器10中的計算量。應該注意，如上所述的路由設置處理可以由執行路由設置程序的路由設置伺服器 10實現。路由設置程序是由路由設置伺服器10執行的電腦程式。路由設置程序可以記錄在有形計算機可讀記錄介質上。3.路由設置伺服器的各種示例3-1.第一示例性實施方式圖3是示出了根據本發明第一示例性實施方式的路由設置伺服器10的配置的框圖。路由設置伺服器10具有網絡信息收集管理單元100、存儲單元200和路由設計單元 300。網絡信息收集管理單元100收集網絡信息INF。網絡信息INF是關於通信網絡 NET的信息並且包括關於節點5之間的連接狀態以及鏈路代價的信息。基於收集的網絡信息INF，網絡信息收集管理單元100創建並且更新存儲在存儲單元200中的各種信息和表。 應該注意，網絡信息收集管理單元100由執行路由設置程序的路由設置伺服器10實現。存儲單元200是諸如RAM和HDD的存儲設備。拓撲信息210、路由表220-1到 220-n、路由節點列表230等存儲在存儲單元200中。拓撲信息210指示節點5之間的連接狀態，即通信網絡NET的物理拓撲。拓撲信息210由網絡信息收集管理單元100創建並且更新。接下來，為了闡釋路由表220，將參考圖4描述「目標節點，，和「下一跳節點」。目標節點5-i是5-1到5-n(i = 1到η)中的任意一個。目的地節點5_j是節點5_1到5_n 中的任意一個並且不同於目標節點5-i(j = 1到n，j興i)。考慮從目標節點5-i向目的地節點5-j傳送流數據的情況。在該情況中，作為來自於目標節點5-i的流數據的轉發目的地下一節點是「下一跳節點5-ij」。S卩，下一跳節點5-ij是數據流將要通過的、從目標節點5-i的下一跳的節點。關於目標節點5-i，可以存在下一跳節點5-ij的多個候選。當存在m個候選(m是自然數)時，各候選表示為5-ij (1)到5-ij (m)。一般而言，對於目標節點5-i，存在下一跳節點候選5-ij (k) ；k= 1到m。應該注意，下一跳節點候選5-ij (k)可以從目的地節點5-j後退。路由表220充當指示上述下一跳節點候選的「下一跳信息」。更具體地，路由表220-1到220-n分別為節點5-1到5-n而準備。即，目標節點5_i和路由表220-i相互關聯。路由表220-i指示關於目標節點5-i的下一跳節點候選5-i j (k)。圖5示出了關於目標節點5-i的路由表220-i的示例。如圖5所示，路由表220_i 指示關於每個目的地節點5-j (j = 1到n，j Φ i)的下一跳節點候選5-i j (k)。此外，路由表220-i指示針對每個下一跳節點候選5-i j(k)定義的「選擇概率Pij (k)」。選擇概率 Pij (k)是從m個下一跳節點候選5-i j(l)到5_ij(m)中選擇下一跳節點5_i j (k)的概率。 m個選擇概率Pij (k)的和是1。[公式1]
mX PlAk) = 1 ...(1)
k = \可以採用各種方法作為用於計算選擇概率Pij (k)的方法。例如，計算通過下一跳節點候選5-i j (k)從目標節點5-i到目的地節點5-j的最短路由的代價(路由代價)。路由代價是組成路由的各個鏈路的鏈路代價的和。當帶寬較低、可用容量較小、延遲時間較長以及分組丟失數量較大時，鏈路代價將會增力Π。然後，將與計算出的路由代價成反比例的值用作選擇概率Pij (k)。通過使用上述網絡信息INF和拓撲信息210，網絡信息收集管理單元100計算每個選擇概率Pij (k)並且創建和更新每個路由表220-i。再次參考圖3，存儲在存儲單元200中的路由節點列表230是指示由下文描述的路由設計單元300設計的通信路由的信息。路由設計單元300由執行路由設置程序的路由設置伺服器10實現。路由設計單元300包括下一跳確定單元330、環檢測單元350、環刪除單元370和節點設置單元390。這些功能塊參考存儲在存儲單元200中的信息和表以執行根據本示例性實施方式的路由設置處理。圖6是示出了根據第一示例性實施方式的路由設置處理的流程圖。圖7概念性地示出了路由節點列表230。此後，將更詳細地描述根據本示例性實施方式的路由設置處理。步驟SlO 當流出現時，路由設計單元300接收關於來自於通信網絡NET的流的路由設置請求REQ。路由設置請求REQ指定流的源節點5-S和目的地節點5-D。步驟S320 下一跳確定單元330接收路由設置請求REQ並且識別源節點5_S和目的地節點 5-D。然後，下一跳確定單元330將目標節點5-i初始化為源節點5-S。下一跳確定單元330 將源節點5-S寫作路由節點列表230的第一條目(參見圖7)。步驟S330 下一跳確定單元330關於當前目標節點5-i執行「下一跳確定處理」。在下一跳確定處理中，下一跳確定單元330通過參考與目標節點5-i相關聯的路由表220-i (下一跳信息)而「隨機地」選擇下一跳節點。圖8是示出了本示例性實施方式中下一跳確定處理的流程圖。步驟S331:下一跳確定單元330參考當前目標節點5-i的路由表220-i。然後，下一跳確定單元330提取朝向目的地節點5-j (=節點5-D)的下一跳節點候選5-i j (1)。步驟S335
隨後，下一跳確定單元330從提取的下一跳節點候選5-i j (1)到5_i j (m)隨機地選擇一個下一跳節點5-ij。例如，下一跳確定單元330利用隨機數和選擇概率Pij (k)。從路由表220-i讀出下一跳節點候選5-ij (k)的選擇概率Pij (k)。作為示例，考慮m = 3並且下一跳節點候選5_ij(l)到5_ij(3)的選擇概率Pij(I) 到Pij (3)分別是0.2、0.3和0.5的情況。在該情況中，關於下一跳節點候選5_ij (1)到 5-ij (3)的數值範圍根據各個選擇概率Pij(I)到Pij (3)來定義。例如，下一跳確定單元 330將不小於0. 0並且小於0. 2的範圍與下一跳節點候選5-ij (1)相關聯，將不小於0. 2並且小於0. 5的範圍與下一跳節點候選5-ij (2)相關聯，以及將不小於0. 5並且小於1. 0的範圍與下一跳節點候選5-ij (3)相關聯。然後，下一跳確定單元330生成不小於0. 0並且小於0.2的範圍內的隨機數X。下一跳確定單元330選擇與包括生成隨機數X的數值範圍相關聯的下一跳節點候選。例如，如果隨機數X是0. 3，則下一跳確定單元330選擇下一跳節點候選5-iK2)。這樣，一個下一跳節點5-ij可以根據上述選擇概率Pij(k)來隨機地選擇。步驟S336 當選擇下一跳節點5-ij時，下一跳確定單元330將所選的下一跳節點5-ij作為中繼節點5-r添加到路由節點列表230 (參見圖7)。而且，下一跳確定單元330將目標節點 5-i更新為所選的下一跳節點5-ij。步驟S340 返回到圖6，在完成了下一跳確定處理(步驟330)之後，下一跳確定單元330檢查過去更新的目標節點5-i (選擇的下一跳節點)是否變為目的地節點5-D。換言之，下一跳確定單元330檢查目標節點5-i是否達到目的地節點5-D。步驟S350 如果目標節點5-i仍舊沒有達到目的地節點5-D (步驟S340 ；否)，則環檢測單元 350確定到那時為止確定的路由上是否出現環。更具體地，環檢測單元350參考路由節點列表230以檢查當前的目標節點5-i (路由節點列表230中底部的條目)是否與過去的目標節點(除底部條目之外的條目)重疊。如果當前的目標節點5-i與任意過去的目標節點重疊，則環檢測單元350檢查到那時為止確定的路由上是否出現環。如果沒有出現環(步驟S350 ；否)，則處理返回到步驟S330，並且下一跳確定單元 330關於新的目標節點5-i執行下一跳確定處理。另一方面，如果檢測到環(步驟S350; 是)，則處理前進到步驟S370。步驟S370 環刪除單元370刪除檢測到的環。為此，環刪除單元370從底部刪除路由節點列表230上記錄的某些條目。即，環刪除單元370將目標節點5-i轉回到任何過去的目標節點。換言之，環刪除單元370使得到那時為止確定的路由退化。考慮用於條目刪除的某些策略。例如，環刪除單元370刪除路由節點列表230中的最後條目。這等於將目標節點5-i只轉回一跳。備選地，環刪除單元370可以刪除直到起始位置(重疊節點首次出現的位置)的條目。這等於將目標節點5-i從當前節點轉回到與當前節點重疊的過去的節點。備選地，環刪除單元370可以通過參考具有逐條返回的路由表220-i以刪除直到選擇概率Pij (k)開始減小的位置。
步驟S330，在環刪除單元370刪除環之後，下一跳確定單元330從新目標節點5_i重新開始下一跳確定處理(步驟S330)。在該重新確定處理中，下一跳確定單元330可以排除先前從候選選擇的下一跳節點5-ij。在該情況中，下一跳確定單元330隨機地選擇除先前從下一跳節點候選5-ij(l)到5-ij (m)中選擇的節點之外的一個下一跳節點。如果下一跳節點候選僅包括先前選擇的節點，則下一跳確定單元330進一步刪除路由節點列表230中的最後條目以將目標節點5-i僅轉回一跳，並且繼而重新開始下一跳確定處理。在下一跳確定處理之後，處理返回到步驟S340。重複上述處理，並且下一跳確定單元330從源節點5-S朝向目的地節點5_D逐跳地隨機確定中繼節點5-r。最終，目標節點5-i達到目的地節點5-D(步驟S340;是)。艮口， 確定了從源節點5-S到目的地節點5-D的通信路由。這樣，根據本示例性實施方式的下一跳確定單元330通過重複下一跳確定處理而隨機地並且逐跳地確定了從源節點5-S到目的地節點5-D的通信路由。步驟S390 在確定了通信路由之後，節點設置單元390指示所確定的通信路由上的每個節點 5沿確定的通信路由轉發流數據(分組、幀)。更具體地，節點設置單元390向路由節點列表230上註冊的每個節點5傳輸轉發表設置命令CMD。該轉發表設置命令CMD是用以指示設置轉發表從而沿上述確定的通信路由轉發流數據的指令。確定的通信路由上的每個節點5從路由設置伺服器10接收轉發表設置命令CMD 並且根據該命令設置其自己的轉發表內容。結果，從源節點5-D向目的地節點5-D傳輸流數據。3-2.第二示例性實施方式圖9是示出了根據本發明第二示例性實施方式的、路由設置伺服器10的配置的框圖。將適當省略與第一示例性實施方式重複的描述。根據第二示例性實施方式，路由高速緩存信息240進一步存儲在存儲單元200中。而且，路由設計單元300還包括高速緩存搜索單元310。圖10概念性地示出了路由高速緩存信息M0。路由高速緩存信息240指示關於源節點5-S和目的地節點5-D的組合的通信路由的候選(此後稱作「路由候選」)。這裡，路由候選是過去確定的通信路由(路由節點列表230)。多個路由候選可以已經針對源節點5-S 和目的地節點5-D的組合而存在。如圖10所示，還關於每個路由候選定義選擇概率。針對在確定路由候選(路由節點列表230)時選擇的所有下一跳節點5-ij (k)的選擇概率Pij (k)的乘積來獲得路由候選的概率。圖11是示出了根據本示例性實施方式的、路由設置處理的流程圖。步驟SlO與第一示例性實施方式的情況相同。根據第二示例性實施方式，高速緩存搜索單元310首先接收路由設置請求REQ。步驟S310:響應於路由設置請求REQ，高速緩存搜索單元310搜索路由高速緩存信息240。即， 高速緩存搜索單元310檢查路由高速緩存信息240是否包括關於路由設置請求REQ所指定
13的源節點5-S和目的地節點5-D的組合的路由候選(過去的路由節點列表230)。步驟S312:在高速緩存命中的情況下，即，在路由高速緩存信息240包括與路由設置請求REQ 相關聯的路由候選的情況下(步驟S311 ；是)，高速緩存搜索單元310從路由高速緩存信息240提取所有路由候選。存在多個路由候選的情況也是存在的。因此，高速緩存搜索單元310從提取的路由候選中隨機地選擇通信路由。更具體地，如同在上述下一跳節點候選選擇處理(步驟S33Q的情況一樣，隨機數和路由候選的選擇概率被使用。應該注意，對於路由候選，選擇概率的和不一定是1。因此，即使存在某些路由候選，但根據生成的隨機數， 可以不選擇一個路由候選。在這個意義上，從路由候選中對通信路由的選擇是隨機的。步驟S314:如果從路由候選選擇了一個通信路由(步驟S313 ；是)，高速緩存搜索單元310採用選擇的通信路由(路由節點列表230)作為此次的通信路由。此後，略過上述步驟S320 到S370並且處理前進到步驟S390。如果路由高速緩存信息240不包括與路由設置請求REQ相關聯的任何路由候選 (步驟S311 ；否)或沒有從路由候選選擇通信路由(步驟S313 ；否)，則高速緩存搜索單元 310向下一跳確定單元330轉發路由設置請求REQ。此後，如在第一示例性實施方式的情況中，執行步驟S320到S370，並且根據路由設置請求REQ確定通信路由。S380 下一跳確定單元330向路由高速緩存信息240添加所確定的新通信路由(路由節點列表230)。對於路由設置請求REQ此次所指定的源節點5-S和目的地節點5-D的組合而言，所添加的通信路由稱為新路由候選。此後，處理前進到步驟S390。根據本示例性實施方式，在高速緩存命中的情況下，可以縮短確定通信路由的時間。3-3.第三示例性實施方式圖12是示出了根據本發明第三示例性實施方式的、路由設置伺服器10的配置的框圖。與第一示例性實施方式的重複描述將適當省略。根據第三示例性實施方式，鏈路代價表250和路由代價表260代替路由表220-1到220_n存儲在存儲單元200中。圖13概念性地示出了鏈路代價表250。鏈路代價表250指示關於每個鏈路的代價。一個鏈路由鏈路起點節點和作為相鄰節點的鏈路終點節點定義。鏈路起點節點和鏈路終點節點彼此距離一跳。因此，鏈路代價表250也充當指示關於每個節點5的下一跳節點候選的「下一跳信息」。圖14概念性地示出了路由代價表沈0。路由代價表260指示針對源節點5_1到 5-n和目的地節點5-1到5-n的所有組合的路由代價。路由代價是構成從源節點到目的地節點的最短路由的各個鏈路的鏈路代價的和。任意兩個節點之間的路由代價可以通過參考路由代價表260獲得。鏈路代價表250和路由代價表260也由網絡信息收集管理單元100創建和更新。根據第三示例性實施方式，在下一跳確定處理中參考鏈路代價表250和路由代價表260而非路由表220(步驟S330)。其他方面與第一示例性實施方式中的情況相同。圖 15是示出了本示例性實施例中下一跳確定處理(步驟S330)的流程圖。
步驟S332:下一跳確定單元330參考鏈路代價表250以提取關於目標節點5_i的下一跳節點候選5-i j (k)。更具體地，下一跳確定單元330提取其鏈路起點節點與鏈路代價表250 中的目標節點5-i相同的條目。包括在所提取條目中的鏈路終點節點是下一跳節點候選 5_ij(k)。步驟S333:隨後，下一跳確定單元330計算通過下一跳節點候選5_ij(k)從目標節點5-i到目的地節點5-j的路由的路由代價。從目標節點5-i(鏈路起點節點)到下一跳節點候選 (鏈路終點節點)的路由代價是鏈路代價表250所指示的鏈路代價。可以從路由代價表 260獲得從下一跳節點候選5-i j(k)到目的地節點5-j的路由代價。兩個路由代價的和是要計算的路由代價。而且，下一跳確定單元330基於計算的路由代價來計算下一跳節點候選5-ij(k)的選擇概率Pij (k)。路由代價與選擇概率Pij (k)直接的關係與第一示例性實施方式情況中的相同。以此方式，下一跳確定單元330可以提取下一跳節點候選5-i j (k)並計算選擇概率Pij(k)。即，可以獲得如由第一示例性實施方式中的路由表220-i(參見圖5)給出的相同信息。此後，如第一示例性實施方式的情況中那樣執行步驟S335和S336。應該注意，還可以組合第二示例性實施方式與第三示例性實施方式。雖然已經參考附圖在上面描述了本發明的示例性實施方式，但是本發明不限於這些示例性實施方式並且可以本領域技術人員可以在不脫離本發明的精神和範圍的情況下進行適當修改。雖然可以將上述示例性實施方式的部分或整體描述為以下補充注釋，但是其不限於此。(補充注釋1)一種路由設置伺服器，所述路由設置伺服器確定包括多個節點的通信網絡中的流的通信路由，所述路由設置伺服器包括存儲單元，其中存儲有關於所述多個節點中每一個的下一跳信息，其中所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及路由設計單元，被配置為響應於指定流的源節點和目的地節點的路由設置請求而設計從所述源節點到所述目的地節點的通信路由，其中所述路由設計單元包括下一跳確定單元，被配置為參考所述下一跳信息執行下一跳確定處理；環檢測單元；以及環刪除單元，其中在所述下一跳確定處理中，所述下一跳確定單元從關於目標節點的所述下一跳節點的所述候選中隨機地選擇一個下一跳節點並且將所述目標節點更新為所述選擇的一個下一跳節點，其中所述下一跳確定單元通過將所述目標節點初始化為所述源節點並且繼而重複所述下一跳確定處理直到所述目標節點成為所述目的地節點來逐跳地確定所述通信路
其中所述環檢測單元檢查當前目標節點是否與過去的目標節點重疊以檢測到那時為止確定的所述通信路由上的環，其中如果檢測到所述環，則所述環刪除單元通過將所述目標節點轉回到任何過去的目標節點來刪除所述環，以及其中在刪除所述環之後，所述下一跳確定單元從所述任何過去的目標節點重新開始下一跳確定處理。(補充注釋2)根據補充注釋1所述的路由設置伺服器，其中所述環刪除單元通過將所述目標節點只轉回一跳來刪除所述環。(補充注釋3)根據補充注釋1所述的路由設置伺服器，其中所述環刪除單元通過將所述目標節點轉回到與所述當前目標節點重疊的節點來刪除所述環。(補充注釋4)根據補充注釋1至3中任一項所述的路由設置伺服器，其中當重新開始所述下一跳確定處理時，所述下一跳確定單元從所述候選排除先前選擇的下一跳節點。(補充注釋5)根據補充注釋4所述的路由設置伺服器，其中如果所述候選僅包括先前選擇的下一跳節點，則所述下一跳確定單元進一步將所述目標節點只轉回一跳並且繼而重新開始所述下一跳確定處理。(補充注釋6)根據補充注釋1至5中任一項所述的路由設置伺服器，其中關於所述目標節點的所述候選包括第一候選和第二候選，其中在所述下一跳確定處理中，所述下一跳確定單元生成預定範圍內的隨機數，其中如果所述生成的隨機數處於所述預定範圍內包括的第一範圍內，則所述下一跳確定單元選擇所述第一候選，以及其中如果所述生成的隨機數處於所述預定範圍內包括的第二範圍內，則所述下一跳確定單元選擇所述第二候選。(補充注釋7)根據補充注釋6所述的路由設置伺服器，其中根據所述第一候選被選擇的第一選擇概率來確定所述第一範圍，以及根據所述第二候選被選擇的第二選擇概率來確定所述第二範圍。(補充注釋8)根據補充注釋7所述的路由設置伺服器，其中所述第一選擇概率與通過所述第一候選從所述目標節點到所述目的地節點的路由的代價成反比，以及所述第二選擇概率與通過所述第二候選從所述目標節點到所述目的地節點的路由的代價成反比。(補充注釋9)根據補充注釋1至8中任一項所述的路由設置伺服器，其中路由高速緩存信息被進一步存儲在所述存儲單元中，其中所述路由高速緩存信息指示過去確定的、關於所述源節點和所述目的地節點的組合的所述通信路由作為路由候選，以及其中所述下一跳確定單元向所述路由高速緩存信息添加所述確定的通信路由，以作為關於所述路由設置請求所指定的所述源節點和所述目的地節點的組合的所述路由候選。(補充注釋10)根據補充注釋9所述的路由設置伺服器，其中所述路由設計單元還包括高速緩存搜索單元，其中所述高速緩存搜索單元響應於所述路由設置請求來搜索所述路由高速緩存信息，以及其中如果所述路由高速緩存信息包括與所述路由設置請求相關聯的所述路由候選，則所述高速緩存所述單元隨機地從所述路由候選選擇所述通信路由。(補充注釋11)根據補充注釋1至10中任一項所述的路由設置伺服器，其中所述路由設計單元還包括節點設置單元，其中所述節點設置單元指示所述確定的通信路由上的每個節點沿所述確定的通信路由轉發所述流的數據。(補充注釋12)一種通信網絡系統包括通信網絡，包括多個節點；以及路由設置伺服器，被配置為確定所述通信網絡中的流的通信路由，其中所述路由設置伺服器包括存儲單元，其中存儲有關於所述多個節點中的每一個的下一跳信息，其中所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及路由設計單元，被配置為響應於指定流的源節點和目的地節點的路由設置請求而設計從所述源節點到所述目的地節點的通信路由，其中所述路由設計單元包括下一跳確定單元，被配置為參考所述下一跳信息執行下一跳確定處理；環檢測單元；以及環刪除單元，其中在所述下一跳確定處理中，所述下一跳確定單元從關於目標節點的所述下一跳節點的所述候選隨機地選擇一個下一跳節點並且將所述目標節點更新為所述選擇的一個下一跳節點，其中所述下一跳確定單元通過將所述目標節點初始化為所述源節點並且繼而重複所述下一跳確定處理直到所述目標節點成為所述目的地節點來逐跳地確定所述通信路
其中所述環檢測單元檢查當前目標節點是否與過去目標節點重疊以檢測到那時為止確定的所述通信路由上的環，其中如果檢測到所述環，則所述環刪除單元通過將所述目標節點轉回到任何過去目標節點來刪除所述環，以及其中在刪除所述環之後，所述下一跳確定單元從所述任何過去目標節點重新開始下一跳確定處理。(補充注釋13)一種路由設置方法，用於確定包括多個節點的通信網絡中的流的通信路由，所述路由設置方法包括在存儲設備中存儲關於所述多個節點中的每一個的下一跳信息，所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及響應於指定流的源節點和目的地節點的路由設置請求，設計從所述源節點到所述目的地節點的通信路由，其中所述設計所述通信路由包括參考所述下一跳信息執行下一跳確定處理；其中所述下一跳確定處理包括從關於目標節點的所述下一跳節點的所述候選隨機地選擇一個下一跳節點；以及將所述目標節點更新為所述選擇的一個下一跳節點；通過將所述目標節點初始化為所述源節點並且繼而重複所述下一跳確定處理直到所述目標節點成為所述目的地節點來逐跳地確定所述通信路由，檢查當前目標節點是否與過去目標節點重疊以檢測到那時為止確定的所述通信路由上的環，如果檢測到所述環，則通過將所述目標節點轉回到任何過去目標節點來刪除所述環；以及在刪除所述環之後，從所述任何過去目標節點重新開始下一跳確定處理。(補充注釋14)一種其上記錄路由設置程序的記錄介質，其中所述路由設置程序使得計算機執行路由設置處理，所述路由設置處理確定包括多個節點的通信網絡中的流的通信路由，所述路由設置處理包括在存儲設備中存儲關於所述多個節點中的每一個的下一跳信息，所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及響應於指定流的源節點和目的地節點的路由設置請求來設計從所述源節點到所述目的地節點的通信路由，其中所述設計所述通信路由包括 參考所述下一跳信息執行下一跳確定處理；其中所述下一跳確定處理包括從關於目標節點的所述下一跳節點的所述候選隨機地選擇一個下一跳節點；以及
18
將所述目標節點更新為所述選擇的一個下一跳節點；通過將所述目標節點初始化為所述源節點並且繼而重複所述下一跳確定處理直到所述目標節點成為所述目的地節點來逐跳地確定所述通信路由，檢查當前目標節點是否與過去目標節點重疊以檢測到那時為止確定的所述通信路由上的環，如果檢測到所述環，則通過將所述目標節點轉回到任何過去目標節點來刪除所述環；以及在刪除所述環之後，從所述任何過去目標節點重新開始下一跳確定處理。本申請基於並且要求2009年3月23日提交的日本專利申請No. 2009-069794的優先權，通過引用將其全文公開合併於此。
權利要求
1.一種路由設置伺服器，用於確定包括多個節點的通信網絡中的流的通信路由， 所述路由設置伺服器包括存儲單元，其中存儲有下一跳信息，其中對於所述多個節點中的每一個，所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及路由設計單元，被配置為響應於指定流的源節點和目的地節點的路由設置請求而設計從所述源節點到所述目的地節點的通信路由， 其中所述路由設計單元包括下一跳確定單元，被配置為參考所述下一跳信息來執行下一跳確定處理； 環檢測單元；以及環刪除單元，其中在所述下一跳確定處理中，所述下一跳確定單元從關於目標節點的所述下一跳節點的所述候選中隨機地選擇一個下一跳節點，並且將所述目標節點更新為所述選擇的一個下一跳節點，其中所述下一跳確定單元通過將所述目標節點初始化為所述源節點並且繼而重複所述下一跳確定處理直到所述目標節點成為所述目的地節點來逐跳確定所述通信路由，其中所述環檢測單元檢查當前目標節點是否與過去的目標節點重疊，以檢測到那時為止確定的所述通信路由上的環，其中如果檢測到所述環，則所述環刪除單元通過將所述目標節點轉回到任何過去的目標節點來刪除所述環，以及其中在刪除所述環之後，所述下一跳確定單元從所述任何過去的目標節點重新開始所述下一跳確定處理。
2.根據權利要求1所述的路由設置伺服器，其中所述環刪除單元通過將所述目標節點只轉回一跳來刪除所述環。
3.根據權利要求1所述的路由設置伺服器，其中所述環刪除單元通過將所述目標節點轉回到與所述當前目標節點重疊的一個節點來刪除所述環。
4.根據權利要求1至3任一項所述的路由設置伺服器，其中當重新開始所述下一跳確定處理時，所述下一跳確定單元從所述候選中排除先前選擇的下一跳節點。
5.根據權利要求4所述的路由設置伺服器，其中如果所述候選僅包括先前選擇的下一跳節點，則所述下一跳確定單元進一步將所述目標節點只轉回一跳，繼而重新開始所述下一跳確定處理。
6.根據權利要求1至5任一項所述的路由設置伺服器， 其中關於所述目標節點的所述候選包括第一候選和第二候選，其中在所述下一跳確定處理中，所述下一跳確定單元生成預定範圍內的隨機數， 其中如果所述生成的隨機數處於所述預定範圍內包括的第一範圍內，則所述下一跳確定單元選擇所述第一候選，以及其中如果所述生成的隨機數處於所述預定範圍內包括的第二範圍內，則所述下一跳確定單元選擇所述第二候選。
7.根據權利要求6所述的路由設置伺服器，其中所述第一範圍根據所述第一候選被選擇的第一選擇概率而被確定，以及所述第二範圍根據所述第二候選被選擇的第二選擇概率而被確定。
8.根據權利要求7所述的路由設置伺服器，其中所述第一選擇概率與通過所述第一候選的、從所述目標節點到所述目的地節點的路由的代價成反比，以及所述第二選擇概率與通過所述第二候選的、從所述目標節點到所述目的地節點的路由的代價成反比。
9.根據權利要求1至8任一項所述的路由設置伺服器， 其中路由高速緩存信息被進一步存儲在所述存儲單元中，其中所述路由高速緩存信息指示過去確定的、關於所述源節點和所述目的地節點的組合的所述通信路由以作為路由候選，以及其中所述下一跳確定單元向所述路由高速緩存信息添加所述確定的通信路由，以作為關於所述路由設置請求所指定的所述源節點和所述目的地節點的組合的所述路由候選。
10.根據權利要求9所述的路由設置伺服器，其中所述路由設計單元還包括高速緩存搜索單元，其中所述高速緩存搜索單元響應於所述路由設置請求而搜索所述路由高速緩存信息，以及其中如果所述路由高速緩存信息包括與所述路由設置請求相關聯的所述路由候選，則所述高速緩存所述單元隨機地從所述路由候選中選擇所述通信路由。
11.根據權利要求1至10任一項所述的路由設置伺服器， 其中所述路由設計單元還包括節點設置單元，其中所述節點設置單元指示所述確定的通信路由上的每個節點沿所述確定的通信路由轉發所述流的數據。
12.一種通信網絡系統，包括 通信網絡，包括多個節點；以及路由設置伺服器，被配置為確定所述通信網絡中的流的通信路由， 其中所述路由設置伺服器包括存儲單元，在所述存儲單元中存儲下一跳信息，其中對於所述多個節點中的每一個，所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及路由設計單元，被配置為響應於指定流的源節點和目的地節點的路由設置請求而設計從所述源節點到所述目的地節點的通信路由， 其中所述路由設計單元包括下一跳確定單元，被配置為參考所述下一跳信息來執行下一跳確定處理； 環檢測單元；以及環刪除單元，其中在所述下一跳確定處理中，所述下一跳確定單元從關於目標節點的所述下一跳節點的所述候選中隨機地選擇一個下一跳節點，並且將所述目標節點更新為所述選擇的一個下一跳節點，其中所述下一跳確定單元通過將所述目標節點初始化為所述源節點並且繼而重複所述下一跳確定處理直到所述目標節點成為所述目的地節點來逐跳地確定所述通信路由，其中所述環檢測單元檢查當前目標節點是否與過去的目標節點重疊，以檢測到那時為止確定的所述通信路由上的環，其中如果檢測到所述環，則所述環刪除單元通過將所述目標節點轉回到任何過去目標節點來刪除所述環，以及其中在刪除所述環之後，所述下一跳確定單元從所述任何過去目標節點重新開始所述下一跳確定處理。
13.—種路由設置方法，用於確定包括多個節點的通信網絡中的流的通信路由， 所述路由設置方法包括在存儲設備中存儲下一跳信息，其中對於所述多個節點中的每一個，所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及響應於指定流的源節點和目的地節點的路由設置請求，設計從所述源節點到所述目的地節點的通信路由，其中所述設計所述通信路由包括 參考所述下一跳信息執行下一跳確定處理； 其中所述下一跳確定處理包括從關於目標節點的所述下一跳節點的所述候選隨機地選擇一個下一跳節點；以及將所述目標節點更新為所述選擇的一個下一跳節點；通過將所述目標節點初始化為所述源節點並且繼而重複所述下一跳確定處理直到所述目標節點成為所述目的地節點來逐跳地確定所述通信路由，檢查當前目標節點是否與過去目標節點重疊，以檢測到那時為止確定的所述通信路由上的環，如果檢測到所述環，則通過將所述目標節點轉回到任何過去目標節點來刪除所述環；以及在刪除所述環之後，從所述任何過去目標節點重新開始下一跳確定處理。
14.一種其上記錄有路由設置程序的記錄介質，其中所述路由設置程序使得計算機執行路由設置處理，所述路由設置處理確定包括多個節點的通信網絡中的流的通信路由， 所述路由設置處理包括在存儲設備中存儲下一跳信息，其中對於所述多個節點中的每一個，所述下一跳信息指示作為數據轉發目的地的下一跳節點的候選；以及響應於指定流的源節點和目的地節點的路由設置請求來設計從所述源節點到所述目的地節點的通信路由，其中所述設計所述通信路由包括 參考所述下一跳信息執行下一跳確定處理； 其中所述下一跳確定處理包括從關於目標節點的所述下一跳節點的所述候選隨機地選擇一個下一跳節點；以及將所述目標節點更新為所述選擇的一個下一跳節點；通過將所述目標節點初始化為所述源節點並且繼而重複所述下一跳確定處理直到所述目標節點成為所述目的地節點來逐跳地確定所述通信路由，檢查當前目標節點是否與過去目標節點重疊以檢測到那時為止確定的所述通信路由上的環，如果檢測到所述環，則通過將所述目標節點轉回到任何過去目標節點來刪除所述環；以及在刪除所述環之後，從所述任何過去目標節點重新開始下一跳確定處理。
全文摘要
一種路徑設置伺服器，具有存儲單元和路徑計算單元。指示每個節點的下一跳候選的下一跳信息被存儲在存儲單元中。響應於指示流的源節點和目的地節點的路由設置請求，路徑計算單元設計其間的通信路徑。更具體地，路徑設計單元包括下一跳確定單元，其在參考下一跳信息的同時執行「下一跳確定處理」。在下一跳確定處理中，下一跳確定單元為目標節點隨機地選擇下一跳候選節點之一，並且將目標節點更新為所選擇的候選。在將目標節點初始化為源節點之後，下一跳確定單元通過重複下一跳確定處理直到目標節點變為目的地節點而每次一跳地確定通信路徑。
文檔編號H04L12/56GK102362470SQ20108001359
公開日2012年2月22日 申請日期2010年3月23日 優先權日2009年3月23日
發明者下西英之 申請人:日本電氣株式會社