通信方法、節點及控制程序的製作方法

2023-05-09 18:44:21 1

專利名稱：通信方法、節點及控制程序的製作方法
技術領域：
本發明涉及通信方法、節點及控制程序，特別涉及具有多個路徑的多 路復用通信的通信方法、節點及控制程序。
背景技術：
作為對多個通信路徑進行多路復用構成1條理論上的廣域鏈的技術， 有如下已知的例子。其中，只對地上的通信路徑進行多路復用的方法有
非專利文獻1中記載的Multilink PPP和非專利文獻2記載的ATM反向多 路復用方法。另外，非專利文獻2中作為對無線鏈進行多路復用的方法記 載了反多路復用技術。這些方法都通過把負荷分散到路徑之間的方式，提 供比單一路徑的帶域更廣的廣域傳送鏈。
作為分散負荷的方法，非專利文獻4記載了對地上的通行路徑進行多 路復用的方法，該方法常採用加權輪詢方式，即根據各路徑的速度進行加 權，周期地選擇發送路徑。但是，這個方法中需要預先設定各路徑的假想 速度，如果應用於對路徑的多路復用中，並且該路徑包含了速度或延遲頻 繁變化的無限鏈，則即使將無限鏈的平均速度等設定為假想速度，也因為 假想速度和實際速度不同，產生傳送效率降低的問題。
作為解決這個問題的技術，非專利文獻3記載了假設對無限鏈進行多 路復用的負荷分散方法。這個技術是如下方法像在反多路復用方式中， 基於各鏈的發送緩衝器的富餘選擇發送路徑。但是，這種方法有如下問
題該方法中發送節點直接連接到了瓶頸鏈，因此只有在可以從發送緩衝
器的富餘估計出瓶頸鏈的負荷時才有效，由於在含有多個鏈的路徑中任意 節點都不能直接連接在瓶頸鏈，因此不適用於雙向通信。
作為解決這個問題的負荷分散方法，非專利文獻5記載了 Mobile InverseMux技術，該技術中兩個節點相互交換對各路徑的速度及延遲的估計結果，根據其估計結果，通過比較各鏈中預測的延遲，來選擇發送路 徑。
非專利文獻1: RFC1990
非專利文獻2: Langdon, Robin D., "Imuxing ATM, Bit by Bit. "Larscom white paper, 1997
非專利文獻3:磯村學、今井尚樹、吉原貴仁、堀內浩規、"千
/k/P—夕(Dt i6(Z)異種通信乂 f 7(D逆多重方式(Z)性能評価"、 FIT2004 (第3回情報科學技術7才一，厶)、論文M-070、 pp.239-240(2004)
非專禾U文獻4 : Cisco Systems, "Load Balancing with Cisco Exprss Forwarding," Cisco Application Note, Jan. 1998
非專利文獻5: T. Nakata. et al., "Efficient bundling of heterogeneous radio resources for broadband Internet access from moving vehicles," in proceedings of Global Mobile Congress 2004,Oct. 11-13 2004， Shanghai, China.

發明內容
上述的已有技術都是通過將負荷分散在路徑間的方法，提供了單一路 徑難以實現的大容量的傳送鏈。
對於只由速度穩定的地上鏈組成的路徑來說，可以用現有技術加權輪 詢方式分散負荷，均衡各路徑的負荷，當各路徑的延遲不同時，多路復用 鏈整體的延遲等於延遲最長的路徑的延遲。因此，多路復用鏈的延遲大於 多路復用對象的路徑中延遲小的路徑。結果，多路復用一方面通過擴大帶 域提高了性能， 一方面因延遲的增加而降低了性能。
另外，在包含無線鏈的路徑間用現有技術Mobile InverseMux分散負 荷時，只給預測的延遲最小的路徑發送分組時，不會出現由於多路復用的 延遲，但如果這樣做，只有在對延遲小的路徑加上了兩路徑的延遲差以上 的負荷時，才會對延遲大的路徑加負荷，也只有在這種時候，才能顯現出 擴大帶域的效果。即，當路徑間的延遲差大的時候，很難分散負荷。為了 避免這個問題，設定了各路徑允許延遲的最大值，對原來延遲小的路徑設定的此允許延遲也小，此時延遲大的路徑也能較容易分散到負荷，但此時 與加權輪詢方法一樣，也因多路復用而增加延遲。
由此可知，已有的所有技術在對延遲不同的路徑進行多路復用時，出 現路徑間負荷的最佳分配和防止多路復用產生的延遲增加難以兩全的問 題。
因此，鑑於上述課題，本發明的目的在於提供一種技術，使得可以同 時實現對路徑間的負荷進行最佳分配和防止多路復用產生的延遲增加的目 的。
解決上述課題的第1項發明，是至少可以利用包含第一路徑和第二路 徑的多個路徑的兩節點間的通信方法，其特徵在於，當預測或檢測出第二
路徑的擁擠時，從到達第一節點的2個以上的分組中，把到達時刻晚的第 二分組從第一路徑發送，然後把到達時刻早的第一分組從第二路徑發送。 解決上述課題的第2項發明，對於上述的第1項發明，其特徵在於， 在預測或檢測出上述第二路徑的擁擠已解除後，將上述的第一分組從上述 第二路徑發送。
解決上述課題的第3項發明，對於上述的第1或第2項發明，其特徵 在於，上述擁擠的預測或擁擠解除的預測是基於各路徑的發送經歷決定 的。
解決上述課題的第4項發明，對於上述的第1或第2項發明，其特徵 在於，上述擁擠的預測或擁擠解除的預測是基於各路徑的估計速度決定 的。
解決上述可的第5項發明，是至少可以利用包含第一路徑和第二路徑 的多個路徑的兩節點間的通信方法，其特徵在於，在把到達第一節點的多 個分組發送到第二節點時，從各路徑的延遲及速度的估計值，決定上述多 個分組的發送路徑，使上述多個分組到達上述第二節點的預測時刻的順序 與上述多個分組到達上述第一節點的順序相同，在上述多個分組中，只把 通過預測認為不會引起各路徑的擁擠而到達第二節點的分組，發送到決定 的發送路徑。
解決上述課題的第6項發明，對於上述的第5項發明，其特徵在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的發送經歷進行的。
解決上述課題的第7項發明，對於上述的第5項發明，其特徵在於， 上述到達預測時刻或上述擁擠的判斷是基於各路徑的估計速度進行的。
解決上述可的第8項發明，是至少可以利用包含第一路徑和第二路徑 的多個路徑的節點，其特徵在於，基於各路徑的延遲及速度的估計值，求 接收的多個分組到達另一節點的預測時刻，基於上述的到達預測時刻，決 定上述多個分組的發送路徑，使上述多個分組到達上述另一個節點的順序 與上述多個分組的到達順序相同。
解決上述課題的第9項發明，對於上述的第8項發明，其特徵在於， 在上述多個分組中，只把通過預測認為不會引起各路徑的擁擠而到達第二 節點的分組，發送到決定的發送路徑。
解決上述課題的第IO項發明，對於上述的第8或第9項發明，其特徵 在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的發送經歷進行 的。
解決上述課題的第ll項發明，對於上述的第8或第9項發明，其特徵 在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的估計速度進行 的。
解決上述可的第12項發明，是至少可以利用包含第一路徑和第二路 徑的節點的控制程序，其特徵在於，基於各路徑的延遲及速度的估計值， 求接收的多個分組到達另一節點的預測時刻，基於上述的到達預測時刻， 使節點決定上述多個分組的發送路徑，使上述多個分組到達上述另一個節 點的順序與上述多個分組的到達順序相同。
解決上述課題的第13項發明，對於上述的第12項發明，其特徵在 於，使節點進行如下處理在上述多個分組中，只把通過預測認為不會引 起各路徑的擁擠而到達第二節點的分組，發送到決定的發送路徑。
解決上述課題的第14項發明，對於上述的第12或第13項發明，其特 徵在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的發送經歷進 行的。
解決上述課題的第15項發明，對於上述的第12或第13項發明，其特徵在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的估計速度進 行的。
為了解決上述的課題，本發明從各路徑的延遲及速度估計值，決定發 送的各分組的預定發送路徑，使到達接收節點的預測時刻順序與到達發送 節點的順序相同，並在其中只發送預測可以在各路徑允許的最大延遲內到 達的分組。
例如，當發送先到達發送節點的分組l及後到達的分組2時，多路復 用對象路徑中低速的第一路徑的預測延遲大於高速的第二路徑的預測延
遲，當第二路徑的預測延遲超過最大延遲時，在第一路徑發送分組2，當
第二路徑的擁擠狀態(預測延遲超過最大延遲的狀態)解除後，在第二路 徑發送分組1。通過這種處理，發送節點的分組發送順序與到達發送節點
的順序不同，但是到達接收節點的順序是分組1在前分組2在後，與到達 發送節點的順序相同，並與分組1、 2都只利用高速路徑2的情況相比， 可以用相等或更小的延遲到達，可以將負荷分散到路徑1和2。
根據本發明，可以對路徑間的負荷進行最佳分配的同時，防止多路復 用引起的延遲的增加。


圖l是示出實施方式的一個結構圖； 圖2是示出實施方式的一個結構圖3是示出時序安排部202的操作流程圖(SDL過程圖)；
圖4是示出路徑選擇部203的操作流程圖(SDL過程圖)；
圖5是用以說明實施方式的圖6是用以說明實施方式的圖。
符號說明
101、 102通信節點
201輸入隊列
202時序安排部
203路徑選擇部204分組發送部 205存儲部 206分組接收部 207分組解析部
具體實施例方式
下面說明本發明的具體實施方式
。
本發明的實施方式可在利用多個通信路徑進行通信的2個節點間實 施。如圖1所示的例子，通信節點101具有各1個分組發送部204和分組 接收部206，另一個通信節點102具有各2個分組發送部204和分組接收 部206。
從節點101到節點102的路徑有兩條， 一條是以節點101的分組發送 部204為起點，經由網絡400，以節點102的分組接收部206-1為終點， 另一條是以節點101的分組發送部204為起點，經由網絡400，以節點 102的分組接收部206-2為終點。另外，從節點102到節點101的路徑也有 兩條， 一條是以節點102的分組發送部204-1為起點，經由網絡400，以 節點101的分組接收部206為終點，另一條是以節點102的分組發送部 204-2為起點，經由網絡400，以節點101的分組接收部206為終點。由此 可知，即使一個節點101的分組發送部只有一個，但如果對應節點102有 多個分組接收部，則可以構成多個路徑，以下說明的實施例也同樣適用於 圖2所示的兩邊的節點都擁有多個信息發送和接收部的情況。
兩邊節點的分組解析部207，從分組的到達時間和到達間隔分析各路 徑的狀態，將該路徑狀態發送給對方節點。 一方面，若接收了通知，則將 基於通知內容的最新路徑信息存儲到存儲部205。時序安排部202基於存 儲部205中存儲的路徑信息，決定分組的發送順序、分組發送時刻及各分 組的發送路徑，並通知路徑選擇部。路徑選擇部203基於從時序安排部 202接到的通知，從輸入隊列201中取出輸入分組，在時序安排部指定的 時刻從指定的路徑發送。
接著，說明節點101的輸入隊列201中有多個分組時時序安排部202的操作。節點101的時序安排部202按照如圖3所示的操作流程圖(SDL 過程圖)操作。即根據路徑選擇部的時序安排請求啟動以下的操作。
首先，從路徑選擇部203接到了 j個分組的時序安排請求時(步驟 100)，令i=l (步驟101)，對提出時序安排請求的分組，按照到達輸入 隊列201的順序，求假設從各路徑發送時的預測時刻(步驟102)。這裡 的預測接收延遲是預測分組的末端到達對方節點102的時刻。把預測接收 時間最短的路徑決定為該分組的發送路徑(步驟103)。圖5是示出預測 最初的分組300-1的到達時刻的例子的圖。在路徑1的分組排頭的預測到 達時刻更早，但是路徑2的速度比路徑l快，因此分組末端的預測到達時 刻、即預測接收時刻早的路徑2將成為發送路徑。對第2個以後到達輸入 隊列201的分組，假設最近到達的分組全部從按照以上的順序決定的發送 路徑發送，來預測接收時刻。
圖6是示出預測第二分組300-2接收時刻的例子的圖。這裡因為發送 了 300-1，路徑2的延遲增加，因此路徑1的預測接收時刻早，隨之路徑l 將成為分組300-2的發送路徑。
接著，確認各路徑的擁擠狀態，並進行預測，判斷可發送時刻(步驟 104)。所謂的擁擠狀態是指由於路徑的預測延遲大於允許值，而無法 即時發送分組的狀態。延遲允許值可以提前設定，或者根據線路狀態由時 序安排部202決定。圖6中路徑2應當發送的300-1的預測接收時刻在現 在時刻加上路徑2的允許延遲之後，因此路徑2是擁擠狀態。為了使分組 300-1的預測延遲、即分組300-1的預測接收時刻和發送時刻的差在路徑2 的延遲允許值以下，需要使發送時刻在tl之後。將此tl作為分組300-1的 可發送時刻。另一方面，作為分組300-2的發送路徑的路徑1不是擁擠狀 態，因此可以即時發送。
時序安排部202邊增加i (步驟107)邊進行以上的處理，直到i=j， 當i叫時(步驟105)，將輸入隊列201中各分組的發送路徑及可發送時刻 通知給路徑選擇部203 (步驟106)。
接下來，說明路徑選擇部203的操作。
路徑選擇部203從時序安排部202接到通知之後，在通知的可發送時刻，將各分組從通知的發送路徑所對應的分組發送部204發送。此時路徑 選擇部203遵循的操作流程(SDL過程圖)如圖4所示。
給時序安排部202發送完時序請求的路徑選擇部203成為活動 (active)狀態，此時若從時序安排部202收到k個分組的發送路徑及可發 送時刻的通知(步驟200)，將a=l作為初始值(步驟201)，從輸入隊 列201取出可發送時間第a個早的分組(步驟202)。然後，等到可發送 時間第a個早的分組的可發送時間(步驟203),把可發送時間第a個早 的分組從時序安排部指定的路徑所對應的分組發送部204發送(步驟 204)。
增加a (步驟205)，直到a等於k時進行以上的處理。
當a等於k (步驟206)，輸入隊列201沒有分組時(步驟207)，成
為空閒(idle)狀態，等待下一個分組的到達(步驟208)。
當輸入隊列201中有分組(步驟207)，或者輸入隊列201接到了新
的分組接收通知的時候(步驟209)，給時序安排部202發送時序安排請
求(步驟210)。
進行時序安排請求的分組數是一個低於輸入隊列201中分組數的任意 數。例如，可以設為輸入隊列201中的分組總數，也可以設定任意的上 限。
根據以上的操作發送2個分組的圖6的例中，先到達輸入隊列201的 分組300-1反而在分組300-2之後發送，對方節點預測的接收順序與到達 輸入隊列201的順序相同。即，從節點101的分組發送部204輸出的時候 與到達節點101的順序相反，但是網絡400中分組的順序再次發生逆轉， 預測到達節點102的順序與到達節點101的順序相同。此時，任意分組的 延遲都小於或等於只使用路徑1、或者只使用路徑2的情況，並且負荷分 散在了兩條路徑。
上面雖然說明了將本發明的操作應用於有2條可用路徑的結構的例 子，但是圖3、圖4中所示的原理也可以適用於有3條以上的可用路徑的 情況。此時裝置的結構，例如圖2所示，此時圖2的節點101及節點102 之間傳送分組的延遲都小於或等於只用2個節點之間任意一條時，並且可以通過對各路徑進行負荷分散，來擴大帶域。
另外，雖然上述的實施方式中各部件由硬體構成，但是也可以用可實 現各部件操作的控制程序下操作的信息處理裝置構成。
權利要求
1. 一種通信方法，是至少可以利用包含第一路徑和第二路徑的多個路徑的兩節點間的通信方法，其特徵在於，當預測或檢測出第二路徑的擁擠時，從到達第一節點的2個以上的分組中，將到達時刻晚的第二分組用第一路徑發送，然後將到達時刻早的第一分組用第二路徑發送。
2. 如權利要求1所述的通信方法，其特徵在於，在預測或檢測出第二路徑的擁擠解除後，將上述第一分組從上述第二 路徑發送。
3. 如權利要求1所述的通信方法，其特徵在於， 上述擁擠的預測或擁擠解除的預測是基於各路徑的發送經歷決定的。
4. 如權利要求1所述的通信方法，其特徵在於， 上述擁擠的預測或擁擠解除的預測是基於各路徑的估計速度決定的。
5. —種通信方法，是至少可以利用包含第一路徑和第二路徑的多個路 徑的兩節點間的通信方法，其特徵在於，當把到達第一節點的多個分組發送給第二節點時，根據各路徑的延遲 及速度的估計值，決定上述多個分組的發送路徑，使上述多個分組到達上 述第二節點的預測時刻順序與上述多個分組到達第一節點的時刻的順序相 同，並僅將所述多個分組中被預測為不會引起各路徑擁擠而到達第二節點 的分組發送到所決定的發送路徑。
6. 如權利要求5所述的通信方法，其特徵在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的發送經歷進行的。
7. 如權利要求5所述的通信方法，其特徵在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的估計速度進行的。
8. —種節點，是至少可以利用包含第一路徑和第二路徑的多個路徑的 節點，其特徵在於，具有如下裝置基於各路徑的延遲及速度的估計值，求接收到的多個 分組到達另一個節點的預測到達時刻，基於上述的預測到達時刻，決定上 述多個分組的發送路徑，使上述多個分組到達上述另一個節點的順序與上 述多個分組的到達順序相同。
9. 如權利要求8所述的節點，其特徵在於，具有如下裝置僅將上述多個分組中被預測為不會引起各路徑的擁擠 而到達上述另一個節點的分組發送到所決定的發送路徑。
10. 如權利要求8所述的節點，其特徵在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的發送經歷進行的。
11. 如權利要求8所述的節點，其特徵在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的估計速度進行的。
12. —種控制程序，是至少可以利用包含第一路徑和第二路徑的多個路徑的節點的控制程序，其特徵在於，使節點進行如下處理基於各路徑的延遲及速度的估計值，求接收到 的多個分組到達另一個節點的預測到達時刻，基於上述的預測到達時刻， 決定上述多個分組的發送路徑，使上述多個分組到達上述另一個節點的順 序與上述多個分組的到達順序相同。
13. 如權利要求12所述的控制程序，其特徵在於，使節點進行如下處理僅將上述多個分組中被預測為不會引起各路徑 的擁擠而到達上述另一個節點的分組發送到所決定的發送路徑。
14. 如權利要求12所述的控制程序，其特徵在於，上述到達預測時刻或上述擁擠的判斷是基於各路徑的發送經歷進行的。
15. 如權利要求12所述的控制程序，其特徵在於， 上述到達預測時刻或上述擁擠的判斷是基於各路徑的估計速度進行的。
全文摘要
從各路徑的延遲及速度的估計值，決定要發送的各分組的預定發送路徑，使到達接收節點的預測時刻的順序與到達發送節點時刻的順序相同，其中只發送通過預測認為在各路徑允許的最大延遲時間內可到達的分組。由此，可以同時達到對路徑間的負荷進行最佳分配和防止由多路復用產生的延遲增加的效果。
文檔編號H04L12/56GK101416456SQ20078001205
公開日2009年4月22日 申請日期2007年3月27日 優先權日2006年3月29日
發明者中田恆夫 申請人:日本電氣株式會社