TOP > 国内特許検索 > 制御装置および制御方法、ノードおよび送信方法 > 明細書

明細書 :制御装置および制御方法、ノードおよび送信方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5376571号 (P5376571)
公開番号 特開2010-147826 (P2010-147826A)
登録日 平成25年10月4日(2013.10.4)
発行日 平成25年12月25日(2013.12.25)
公開日 平成22年7月1日(2010.7.1)
発明の名称または考案の名称 制御装置および制御方法、ノードおよび送信方法
国際特許分類 H04L  12/803       (2013.01)
H04L  12/701       (2013.01)
H04M   3/00        (2006.01)
H04M   3/22        (2006.01)
FI H04L 12/803
H04L 12/701
H04M 3/00 D
H04M 3/22 C
請求項の数または発明の数 7
全頁数 23
出願番号 特願2008-323060 (P2008-323060)
出願日 平成20年12月19日(2008.12.19)
審査請求日 平成23年12月9日(2011.12.9)
特許権者または実用新案権者 【識別番号】504133110
【氏名又は名称】国立大学法人電気通信大学
発明者または考案者 【氏名】大木 英司
個別代理人の代理人 【識別番号】100082131、【弁理士】、【氏名又は名称】稲本 義雄
【識別番号】100121131、【弁理士】、【氏名又は名称】西川 孝
審査官 【審査官】衣鳩 文彦
参考文献・文献 特開2004-048330(JP,A)
特開2004-336209(JP,A)
特開2002-252639(JP,A)
M.Kodialam et al.,Preconfiguring IP-over-Optical Networks to Handle Router Failures and Unpredictable Traffic,Selected Areas in Communications, IEEE Journal on,2007年 6月,Volume: 25 , Issue: 5 ,Page(s): 934 - 948
調査した分野 H04L 12/70
H04M 3/00
H04M 3/22
特許請求の範囲 【請求項1】
複数のノードがリンクを介して接続されることにより構成され、TPR(Two-Phase Routing)によって、発ノードから着ノードまでの間に、複数のノードのうちの所定の中間ノードを経由してトラヒックの通信が行われるネットワークにおいて、前記発ノードに入力されたトラヒックについて前記発ノードが、入力されたパケットから前記着ノードを特定する情報を認識し、前記着ノードに応じたトラヒックを分散させる割合にしたがって前記中間ノードを決定し、前記中間ノードの情報を前記パケットに付加して、前記中間ノードに向けて前記パケットを転送することによって、前記中間ノードを介して前記着ノードに前記パケットを送信する場合に、前記トラヒックの通信を制御する制御装置において、
前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合を算出する算出手段と、
前記複数のノードの各々に対して、そのノードが発ノードになるときの着ノードごとの前記トラヒックを分散させる割合を供給する供給手段と
を備える制御装置。
【請求項2】
前記算出手段は、前記ネットワークの構成、前記リンクの使用可能な帯域の容量、および前記トラヒックに関する情報に基づいて、前記割合を算出する
請求項1に記載の制御装置。
【請求項3】
前記算出手段は、前記ネットワークのモデルとしてパイプモデルを仮定し、前記割合を算出する
請求項2に記載の制御装置。
【請求項4】
前記算出手段は、前記ネットワークのモデルとしてホースモデルを仮定し、前記割合を算出する
請求項1に記載の制御装置。
【請求項5】
複数のノードがリンクを介して接続されることにより構成され、TPR(Two-Phase Routing)によって、発ノードから着ノードまでの間に、複数のノードのうちの所定の中間ノードを経由してトラヒックの通信が行われるネットワークにおいて、前記発ノードに入力されたトラヒックについて前記発ノードが、入力されたパケットから前記着ノードを特定する情報を認識し、前記着ノードに応じたトラヒックを分散させる割合にしたがって前記中間ノードを決定し、前記中間ノードの情報を前記パケットに付加して、前記中間ノードに向けて前記パケットを転送することによって、前記中間ノードを介して前記着ノードに前記パケットを送信する場合に、前記トラヒックの通信を制御する制御装置の制御方法において、
前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合を算出する算出ステップと、
前記複数のノードの各々に対して、そのノードが発ノードになるときの着ノードごとの前記トラヒックを分散させる割合を供給する供給ステップと
を含む制御方法。
【請求項6】
複数のノードがリンクを介して接続されることにより構成されるネットワークを構成するノードであって、TPR(Two-Phase Routing)によって、入力されたトラヒックを、前記ネットワーク内の複数のノードのうちの所定の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードにおいて、
入力されたパケットから前記着ノードを特定する情報を認識する着ノード認識手段と、
前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定手段と、
前記決定手段により決定された前記中間ノードの情報を前記パケットに付加し、前記中間ノードの情報が付加された前記パケット前記中間ノードに送信する送信手段と
を備えるノード。
【請求項7】
複数のノードがリンクを介して接続されることにより構成されるネットワークを構成するノードであって、TPR(Two-Phase Routing)によって、入力されたトラヒックを、前記ネットワーク内の複数のノードのうちの所定の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードの送信方法において、
入力されたパケットから前記着ノードを特定する情報を認識する着ノード認識ステップと、
前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定ステップと、
前記決定ステップの処理により決定された前記中間ノードの情報を前記パケットに付加し、前記中間ノードの情報が付加された前記パケット前記中間ノードに送信する送信ステップと
を含む送信方法。
発明の詳細な説明 【技術分野】
【0001】
本発明は、制御装置および制御方法、ノードおよび送信方法に関し、特に、トラヒックを効果的に分散させ、ネットワークの使用効率を向上させることができるようにした制御装置および制御方法、ノードおよび送信方法に関する。
【背景技術】
【0002】
ネットワークにおいては、適切な経路制御方式を採用することにより、リソースの使用効率を向上させ、スループットを増加させることができる(例えば、非特許文献1参照)。即ち、適切な経路制御方式では、トラヒックを最適に各経路に割り当て、より多くのトラヒックをネットワークに収容させることができる。また、適切な経路制御方式では、ネットワークの輻輳を抑制したり、トラヒック変動への耐久性を増加させたりすることができる。
【0003】
経路制御の効果を向上させる1つの方法としては、ネットワークの全てのリンクの使用率の最大値(以下、ネットワーク輻輳率という)を最小化することが挙げられる。ネットワーク輻輳率を最小化することにより、ネットワークに収容可能なトラヒックを増加させることができる。
【0004】
ところで、経路制御に関しては、様々な研究が行われている。その結果、例えば、非特許文献2では、一般的なトラヒックエンジニアリングの問題、即ちトラヒック需要が、発着ノード間で自由に経路を選択および分散できる問題として定式化されている。
【0005】
また、非特許文献3には、精巧な経路制御は、例えば、MPLS-TE(Multi-Protocol Label Switching Traffic-Engineering)技術を用いて達成可能であることが記載されている。
【0006】
しかしながら、既に構築されているネットワークでは、主に、OSPF(Open Shortest Path First)やIS-IS(Intermediate System to Intermediate System)のような最短経路ベースのルーチングプロトコルが採用されている。従って、既に導入されているIP(Internet Protocol)ルータなどのノードがMPLS-TEを採用するためには、ノードのアップグレードが必要となってしまう。そのため、可能な限り既存のルーチングプロトコルを有効利用することが必要であると考えられる。
【0007】
そこで、非特許文献4乃至6に記載されているように、OSPFベースでネットワークのリンクの重みを最適化する経路制御方式が研究されている。この経路制御方式では、最短経路計算にあたって、リンクの重みがリンクの距離として計算される。また、トラヒック需要が変化すると、最適なリンクの重みが再計算され、再計算されたリンクの重みが、ネットワーク上のノードに再設定される。そして、最新のリンクの重みにしたがって、経路が再計算される。従って、経路が頻繁に変化すると、ネットワーク上の経路の不安定性を招き、これは、パケットロスやループを生じさせる原因となる。
【0008】
また、トラヒックを分散させ、ネットワークの利用効率を向上させる分散経路制御方式も研究されている。例えば、非特許文献7では、TPR(two-phase routing) over shortest pathsが提案されている。TPRでは、発ノードから送出されたトラヒックのフローは、ネットワーク上の中間ノードへ分散され、中間ノードから着ノードへ向かう。TPRでは、分散させる経路数を増加させることができ、これにより、ネットワーク輻輳率を削減することができる。
【0009】
なお、非特許文献7に記載されているTPRでは、発ノードから中間ノードまでの経路選択、および、中間ノードから着ノードまでの経路選択は、既存のルーチングプロトコルを使用するという制限が設けられている。これに対して、非特許文献8に記載されているTPRでは、既存のルーチングプロトコルを使用するという制限は設けられていない。
【0010】
以下に、TPRの動作について説明するが、その前に、TPRを採用するネットワークモデルを以下のように定義する。
【0011】
ネットワークは有効グラフG(V,E)で表現する。ここで、Vはノードの集合、Eはリンクの集合を表している。また、ノードi∈Vからノードj∈Vまでのリンクはlink(i,j)∈Eと表す。link(i,j)∈Eの使用可能な帯域の容量はcijと表し、link(i,j)∈Eの使用率はLijと表す。ノードpからノードqまでのトラヒック需要dpqを表すトラヒック行列は、T={dpq}と表す。
【0012】
また、ネットワーク輻輳率はrと表す。なお、現在のトラヒックに対して、1/rを乗じたトラヒックまで、ネットワークは受付可能であり、ネットワーク輻輳率rを最小化することは、受付可能なトラヒックを最大化することになる。従って、分散経路制御の目的関数の1つは、ネットワーク輻輳率rの最小化である。
【0013】
さらに、非特許文献7および8に記載されているTPRでは、ネットワークモデルとしてT={dpq}が既知または推定可能なホースモデルが仮定されているため、ここでも同様の仮定を行う。そこで、αpを、ノードpからネットワークに送出するトラヒックの総量と定義する。従って、式
【数1】
JP0005376571B2_000002t.gif
が成り立つ。この式は、ホースモデルにおけるノードpの制約条件を表す。
【0014】
また、βqを、ネットワークからノードqに流入するトラヒックの総量と定義する。従って、式
【数2】
JP0005376571B2_000003t.gif
が成り立つ。この式は、ホースモデルにおけるノードqの制約条件を表す。
【0015】
なお、ネットワークモデルとしては、αp、βqが既知または推定可能なホースモデルが仮定されてもよい。
【0016】
次に、以上のようにネットワークモデルが定義された場合のTPRの動作について説明する。
【0017】
TPRでは、トラヒックは、ノードpからノードqに直接転送されず、中間ノードm∈Vに、トラヒックが分散される。そして、全ての発着ノードペア(p,q)に対して、dpqのフローは、中間ノードm∈Vに、kmの割合で分散される。ここで、割合kmについては、0≦km≦1、かつ、
【数3】
JP0005376571B2_000004t.gif
が成立する。中間ノードmに分散されたトラヒックは、着ノードqに転送される。
【0018】
例えば、発ノードがノード1であり、着ノードがノード3である場合、図1に示すように、発ノードであるノード1から着ノードであるノード3へのトラヒックは、中間ノードとしてのノード2、ノード3、ノード4に、それぞれ、k2,k3,k4の割合で分散される。
【0019】
従って、発ノードであるノード1から、中間ノードであるノード2を介して、着ノードであるノード3に分散されるトラヒックの割合は、k2となる。発ノードであるノード1から、中間ノードおよび着ノードであるノード3に分散されるトラヒックの割合は、k3となる。発ノードであるノード1から、中間ノードであるノード4を介して、着ノードであるノード3に分散されるトラヒックの割合は、k4となる。
【0020】
また、発ノードがノード1であり、着ノードがノード2である場合も、図1に示すように、発ノードであるノード1から着ノードであるノード2へのトラヒックは、中間ノードとしてのノード2、ノード3、ノード4に、それぞれ、k2,k3,k4の割合で分散される。
【0021】
従って、発ノードであるノード1から、中間ノードおよび着ノードであるノード2に分散されるトラヒックの割合は、k2となる。発ノードであるノード1から、中間ノードであるノード3を介して、着ノードであるノード2に分散されるトラヒックの割合は、k3となる。発ノードであるノード1から、中間ノードであるノード4を介して、着ノードであるノード2に分散されるトラヒックの割合はk4となる。
【0022】
即ち、TPRでは、発着ノードペア(p,q)によらず、割合k2,k3,k4で、中間ノードとしてのノード2、ノード3、ノード4にトラヒックが分散される。
【0023】
なお、ノードpから中間ノードmまでの経路選択、および、中間ノードmからノードqまでの経路選択の方式としては、例えば最短経路方式が用いられる。これは、ノードpと中間ノードmの間に、IP-in-IPやGRE(Generic Routing Encapsulation)トンネルを設定することで実現できる。
【0024】
次に、TPRにおいてネットワーク輻輳率rを最小化するための割合kmの算出方法について説明する。
【0025】
まず、ノードpから、中間ノードmを介して、ノードqへ転送されるトラヒックを考える。ここで、ノードpと中間ノードmの間のトラヒックをbpmで表すと、ノードpとノードmの間のトラヒックは、2つのコンポーネントから構成される。1つ目のコンポーネントは、ノードpを発ノードとし、中間ノードmを中間ノードとして分散されるトラヒックであり、2つ目のコンポーネントは、ノードpを中間ノードとし、中間ノードmを着ノードとして転送されるトラヒックである。
【0026】
従って、1つ目のコンポーネントとしてのトラヒックをbpm(1)と定義し、2つ目のコンポーネントとしてのトラヒックをbpm(2)と定義すると、トラヒックbpmは、以下の式(1)で表される。
【0027】
pm=bpm(1)+pm(2)
・・・(1)
【0028】
また、上述したホースモデルにおけるノードpの制約条件を用いると、トラヒックbpm(1)は以下の式(2)で与えられ、トラヒックbpm(2)は以下の式(3)で与えられる。
【0029】
【数4】
JP0005376571B2_000005t.gif

【数5】
JP0005376571B2_000006t.gif

【0030】
従って、トラヒックbpmは、トラヒックの総量αp,βqを用いた以下の式(4)で表される。
【0031】
pm=kmαp+pβm
・・・(4)
【0032】
ここで、リンクlink(i,j)がノードpと中間ノードmの経路上にあれば、値1をとり、それ以外であれば値0をとる関数をFpmijと定義すると、リンクlink(i,j)の使用率Lijは、次式(5)で与えられる。
【0033】
【数6】
JP0005376571B2_000007t.gif

【0034】
但し、ψmijは、次式(6)で定義される。
【0035】
【数7】
JP0005376571B2_000008t.gif

【0036】
また、ノードjに流入するトラヒックとノードjから流出するトラヒックの差は、次式(7)で与えられる。
【0037】
【数8】
JP0005376571B2_000009t.gif

【0038】
但し、ωmjは、次式(8)で定義される。
【0039】
【数9】
JP0005376571B2_000010t.gif

【0040】
以上により、TPRにおいて、割合kmを決定する最適経路問題は、次式(9a)乃至(9f)で定式化される。
【0041】
【数10】
JP0005376571B2_000011t.gif

【0042】
なお、式(9a)は、ネットワーク輻輳率rを最小化する目的関数を示している。式(9b)は、ネットワークのノードに関して、割合kmのすべての和が1であることを示している。式(9c)は、全てのリンクにおいて、リンクlink(i,j)を通過するトラヒックの総和がcij×r以下であることを示している。式(9d)は、フロー保存則を示している。
【0043】
以上のようにして定式化された式(9a)乃至(9f)を解くことにより、TPRにおいてネットワーク輻輳率rを最小化するための割合kmが算出される。なお、式(9a)乃至(9f)は、線形計画問題(LP(Linear Programming))であるため、標準のLPソルバ(solver)で解くことができる。
【0044】

【非特許文献1】R. Zhang-Shen and N. McKeown, “Designing a Fault-Tolerant Network Using Valiant Load-Balancing”, IEEE Infocom 2008, April 2008
【非特許文献2】Y. Wang and Z. Wang, “Explicit routing algorithms for internet traffic engineering,” IEEE International Conference on Computer Communications and Networks (ICCCN), 1999
【非特許文献3】D. Awduche et al., “Requirements for Traffic Engineering Over MPLS”, RFC 2702, Sept. 1999
【非特許文献4】Y. Wang and M. R. Ito, “Dynamics of load sensitive adaptive routing”, IEEE International Conference on Communications (ICC), 2005
【非特許文献5】B. Fortz and M. Thorup, “Optimizing OSPF/IS-IS weights in a changing world”, IEEE Journal on Selected Areas in Communications, vol. 20, no. 4, pp. 756-767, 2002
【非特許文献6】J. Chu and C. Lea, “Optimal Link Weights for Maximizing QoS Traffic”, IEEE ICC 2007, pp. 610-615, 2007
【非特許文献7】M. Antic and A. Smiljanic, “Oblivious Routing Scheme Using Load Balancing Over Shortest Paths”, IEEE ICC 2008, 2008
【非特許文献8】M. Kodialam, T. V. Lakshman, J. B. Orlin, and S. Sengupta, “Pre-Conguring IP-over-Optical Networks to Handle Router Failures and Unpredictable Traffic”, IEEE Infocom 2006, April 2006
【発明の開示】
【発明が解決しようとする課題】
【0045】
以上のように、TPRでは、中間ノードmにトラヒックを分散させる割合kは、発着ノードペアには依存せず、中間ノードmにだけ依存するkmである。そのため、トラヒックが効果的に分散できない恐れがある。
【0046】
本発明は、このような状況に鑑みてなされたものであり、トラヒックを効果的に分散させ、ネットワークの使用効率を向上させることができるようにするものである。
【課題を解決するための手段】
【0047】
本発明の第1の側面は、複数のノードがリンクを介して接続されることにより構成され、TPR(Two-Phase Routing)によって、発ノードから着ノードまでの間に、複数のノードのうちの所定の中間ノードを経由してトラヒックの通信が行われるネットワークにおいて、前記発ノードに入力されたトラヒックについて前記発ノードが、入力されたパケットから前記着ノードを特定する情報を認識し、前記着ノードに応じたトラヒックを分散させる割合にしたがって前記中間ノードを決定し、前記中間ノードの情報を前記パケットに付加して、前記中間ノードに向けて前記パケットを転送することによって、前記中間ノードを介して前記着ノードに前記パケットを送信する場合に、前記トラヒックの通信を制御する制御装置において、前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合を算出する算出手段と、前記複数のノードの各々に対して、そのノードが発ノードになるときの着ノードごとの前記トラヒックを分散させる割合を供給する供給手段とを備える制御装置である。
【0048】
本発明の第1の側面は、複数のノードがリンクを介して接続されることにより構成され、TPR(Two-Phase Routing)によって、発ノードから着ノードまでの間に、複数のノードのうちの所定の中間ノードを経由してトラヒックの通信が行われるネットワークにおいて、前記発ノードに入力されたトラヒックについて前記発ノードが、入力されたパケットから前記着ノードを特定する情報を認識し、前記着ノードに応じたトラヒックを分散させる割合にしたがって前記中間ノードを決定し、前記中間ノードの情報を前記パケットに付加して、前記中間ノードに向けて前記パケットを転送することによって、前記中間ノードを介して前記着ノードに前記パケットを送信する場合に、前記トラヒックの通信を制御する制御装置の制御方法において、前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合を算出する算出ステップと、前記複数のノードの各々に対して、そのノードが発ノードになるときの着ノードごとの前記トラヒックを分散させる割合を供給する供給ステップとを含む制御方法である。
【0049】
本発明の第2の側面は、複数のノードがリンクを介して接続されることにより構成されるネットワークを構成するノードであって、TPR(Two-Phase Routing)によって、入力されたトラヒックを、前記ネットワーク内の複数のノードのうちの所定の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードにおいて、入力されたパケットから前記着ノードを特定する情報を認識する着ノード認識手段と、前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定手段と、前記決定手段により決定された前記中間ノードの情報を前記パケットに付加し、前記中間ノードの情報が付加された前記パケット前記中間ノードに送信する送信手段とを備えるノードである。
【0050】
本発明の第2の側面は、複数のノードがリンクを介して接続されることにより構成されるネットワークを構成するノードであって、TPR(Two-Phase Routing)によって、入力されたトラヒックを、前記ネットワーク内の複数のノードのうちの所定の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードの送信方法において、入力されたパケットから前記着ノードを特定する情報を認識する着ノード認識ステップと、前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定ステップと、前記決定ステップの処理により決定された前記中間ノードの情報を前記パケットに付加し、前記中間ノードの情報が付加された前記パケット前記中間ノードに送信する送信ステップとを含む送信方法である。
【0051】
本発明の第1の側面においては、複数のノードがリンクを介して接続されることにより構成され、TPR(Two-Phase Routing)によって、発ノードから着ノードまでの間に、複数のノードのうちの所定の中間ノードを経由してトラヒックの通信が行われるネットワークにおいて、前記発ノードに入力されたトラヒックについて前記発ノードが、入力されたパケットから前記着ノードを特定する情報を認識し、前記着ノードに応じたトラヒックを分散させる割合にしたがって前記中間ノードを決定し、前記中間ノードの情報を前記パケットに付加して、前記中間ノードに向けて前記パケットを転送することによって、前記中間ノードを介して前記着ノードに前記パケットを送信する場合に、前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合が算出され、前記複数のノードの各々に対して、そのノードが発ノードになるときの着ノードごとの前記トラヒックを分散させる割合が供給される。
【0052】
本発明の第2の側面においては、TPR(Two-Phase Routing)によって、入力されたトラヒックを、複数のノードがリンクを介して接続されることにより構成されるネットワーク内の複数のノードのうちの所定の中間ノードを介して、前記ネットワーク内の着ノードに送信する場合に、入力されたパケットから前記着ノードを特定する情報が認識され、前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードが決定され、その中間ノードの情報が前記パケットに付加され、前記中間ノードの情報が付加された前記パケット前記中間ノードに送信される。
【発明の効果】
【0053】
以上のように、本発明によれば、トラヒックを効果的に分散させ、ネットワークの使用効率を向上させることができる。
【発明を実施するための最良の形態】
【0054】
<第1実施の形態>
[ネットワークシステムの一実施の形態の構成例]
図2は、本発明を適用したネットワークシステムの一実施の形態の構成例を示す図である。
【0055】
図2のネットワークシステム10は、トラヒック量割合算出装置11と、リンク20-1乃至20-5を介して接続されたノード21-1乃至21-4よりなるネットワーク12とから構成される。ネットワークシステム10は、TPRを改良した方式(ここでは、FTPR(Fine Two Phase Routing)という)で、発ノードに入力されたトラヒックを、中間ノードを介して着ノードに送信する。
【0056】
なお、以下では、リンク20-1乃至20-5を特に区別する必要がない場合、それらをまとめてリンク20という。また、ノード21-1乃至21-4についても同様にノード21という。さらに、発ノード、中間ノード、着ノードとなるノード21を、それぞれ、発ノード21、中間ノード21、着ノード21ともいう。
【0057】
トラヒック量割合算出装置11は、ネットワーク12の各ノード21に接続されている。トラヒック量割合算出装置11は、ネットワーク12の構成およびリンク20の使用可能な帯域の容量に基づいて、発ノード21に入力されるトラヒックを、中間ノード21に分散させる割合を、発着ノードペアごとに算出する。トラヒック量割合算出装置11は、ノード21が発ノードであるときの割合を、そのノード21に供給する。
【0058】
ノード21-1乃至21-4は、それぞれ、トラヒック分散部22-1乃至22-4を有する。なお、以下では、トラヒック分散部22-1乃至22-4を特に区別する必要がない場合、それらをまとめてトラヒック分散部22という。
【0059】
ノード21のトラヒック分散部22は、トラヒック量割合算出装置11から供給される割合に基づいて、そのノード21を発ノードとして入力されるトラヒックを中間ノード21に分散して転送する。
【0060】
具体的には、トラヒック分散部22は、トラヒック量割合算出装置11から供給される割合に基づいて、そのトラヒック分散部22を備えるノード21を発ノードとして入力されるトラヒックを送信する中間ノード21を決定する。そして、トラヒック分散部22は、その中間ノード21にトラヒックを送信する。
【0061】
次に、図3を参照して、図2のネットワークシステム10におけるトラヒックの分散について説明する。
【0062】
ネットワークシステム10では、発着ノードペアごとに、中間ノード21にトラヒックが分散される割合が算出されるので、図3Aに示すように、発ノードがノード21-1であり、着ノードがノード21-3である場合と、図3Bに示すように、発ノードがノード21-1であり、着ノードがノード21-2である場合とでは、中間ノード21に分散されるトラヒックの割合が異なる。
【0063】
具体的には、例えば、図3Aに示すように、発ノード21-1から着ノード21-3へのトラヒックは、中間ノード21-2、中間ノード21-3、中間ノード21-4に、それぞれ、k213,k313,k413の割合で分散される。
【0064】
従って、発ノード21—1から中間ノード21-2を介して着ノード21-3に分散されるトラヒックの割合はk213となる。発ノード21-1から中間ノードおよび着ノードであるノード21-3に分散されるトラヒックの割合はk313となる。発ノード21-1から中間ノード21-4を介して着ノード21-3に分散されるトラヒックの割合はk413となる。
【0065】
なお、発ノードがノード21-pであり、着ノードがノード21-qである場合にノード21-mに分散される割合をkmpqと表している。
【0066】
一方、着ノードがノード21-3である場合には、図3Bに示すように、発ノード21-1から着ノード21-3へのトラヒックは、中間ノード21-2、中間ノード21-3、中間ノード21-4に、それぞれ、k213,k313,k413とは異なるk212,k312,k412の割合で分散される。
【0067】
従って、発ノード21-1から着ノード21-2に分散されるトラヒックの割合はk212となる。発ノード21—1から中間ノード21—3を介して着ノード21-2に分散されるトラヒックの割合はk312となる。発ノード21-1から中間ノード21-4を介して着ノード21-2に分散されるトラヒックの割合はk412となる。
【0068】
以上のように、ネットワークシステム10では、発着ノードペアによって異なる割合で、中間ノード21-2、中間ノード21-3、中間ノード21-4にトラヒックが分散されるので、TPRで分散される場合に比べて、より最適な割合で効果的にトラヒックを分散することができる。その結果、ネットワーク輻輳率を削減することができる。
【0069】
[分散の割合の算出方法の第1の例]
次に、割合kmpqの算出方法について説明する。
【0070】
まず、ネットワークシステム10のネットワークモデルを以下のように定義する。
【0071】
ネットワーク12は有効グラフG(V,E)で表現する。ここで、Vはノード21の集合、Eはリンク20の集合を表している。また、ノードi∈Vからノードj∈Vまでのリンク20はlink(i,j)∈Eと表す。link(i,j)∈Eの使用可能な帯域の容量はcijと表し、link(i,j)∈Eの使用率はLijと表す。ノードpからノードqまでのトラヒック需要dpqを表すトラヒック行列は、T={dpq}と表す。また、ネットワーク輻輳率をrと表す。ネットワークモデルとしてはパイプモデルを仮定する。
【0072】
以上のようにネットワークシステム10のネットワークモデルが定義されると、ノードpを発ノードとし、中間ノードmを中間ノードとして分散されるトラヒックbpm(1)は、次式(10)で与えられる。
【0073】
【数11】
JP0005376571B2_000012t.gif

【0074】
また、ノードpを中間ノードとし、中間ノードmを着ノードとして転送されるトラヒックbpm(2)は、次式(11)で与えられる。
【0075】
【数12】
JP0005376571B2_000013t.gif

【0076】
ここで、リンクlink(i,j)がノードpと中間ノードmの経路上にあれば、値1をとり、それ以外であれば値0をとる関数をFpmijと定義すると、リンクlink(i,j)の使用率Lijは、次式(12)で与えられる。
【0077】
【数13】
JP0005376571B2_000014t.gif

【0078】
但し、ψpqmijは、次式(13)で定義される。
【0079】
【数14】
JP0005376571B2_000015t.gif

【0080】
また、ノードjに流入するトラヒックとノードjから流出するトラヒックの差は、次式(14)で与えられる。
【0081】
【数15】
JP0005376571B2_000016t.gif

【0082】
但し、ωpqmjは、次式(15)で定義される。
【0083】
【数16】
JP0005376571B2_000017t.gif

【0084】
以上により、ネットワークシステム10において、割合kmpqを決定する最適経路問題は、次式(16a)乃至(16f)で定式化される。
【0085】
【数17】
JP0005376571B2_000018t.gif

【0086】
なお、式(16a)は、ネットワーク輻輳率rを最小化する目的関数を示している。式(16b)は、ノード21に関して、割合kmpqのすべての和が1であることを示しており、割合kmpqは、式(16b)を満たす全ての実数値をとることができる。
【0087】
また、式(16c)は、全てのリンク20において、リンクlink(i,j)を通過するトラヒックの総和がcij×r以下であることを示している。式(16d)は、フロー保存則を示している。
【0088】
以上のようにして定式化された式(16a)乃至(16f)を解くことにより、ネットワーク輻輳率rを最小化するための割合kmpqが算出される。なお、式(16a)乃至(16f)は、線形計画問題であるため、標準のLPソルバ(solver)で解くことができる。
【0089】
従って、トラヒック量割合算出装置11は、式(16a)乃至(16f)を解くことにより、割合kmpqを算出する。
【0090】
[トラヒック割合算出装置の詳細構成例]
図4は、図2のトラヒック量割合算出装置11の詳細構成例を示すブロック図である。
【0091】
図4において、トラヒック量割合算出装置11は、トラヒック量入力部31、ネットワーク構成入力部32、およびトラヒック量割合算出部33により構成される。
【0092】
トラヒック量入力部31には、外部から各ノード21のトラヒックに関する情報としてトラヒック需要dpqが入力される。このトラヒック需要dpqは、例えば、各ノード21から実際に検出されたものであってもよいし、オペレータにより入力される予想トラヒック量であってもよい。トラヒック量入力部31は、入力されたトラヒック需要dpqを取得し、トラヒック量割合算出部33に供給する。
【0093】
ネットワーク構成入力部32には、オペレータなどにより外部から、リンクlink(i,j)の使用可能な帯域の容量cij、有効グラフG(V,E)などのネットワーク12の構成を表す情報(以下、ネットワーク情報という)が入力される。ネットワーク構成入力部32は、入力された容量cijおよびネットワーク情報を取得し、トラヒック量割合算出部33に供給する。
【0094】
トラヒック量割合算出部33は、トラヒック量入力部31から供給されるトラヒック需要dpqと、ネットワーク構成入力部32から供給される容量cijおよびネットワーク情報とに基づいて、上述した式(16a)乃至(16f)にしたがって、発着ノードペアごとに割合kmpqを算出する。トラヒック量割合算出部33は、ノード21に、それぞれを発ノードとするときの割合kmpqを供給する。
【0095】
[トラヒック量割合算出装置の処理の説明]
次に、図5のフローチャートを参照して、図4のトラヒック量割合算出装置11による割合算出処理について説明する。
【0096】
ステップS1において、トラヒック量入力部31は、入力されたトラヒック需要dpqを取得し、トラヒック量割合算出部33に供給する。
【0097】
ステップS2において、ネットワーク構成入力部32は、入力された容量cijおよびネットワーク情報を取得し、トラヒック量割合算出部33に供給する。
【0098】
ステップS3において、トラヒック量割合算出部33は、トラヒック量入力部31から供給されるトラヒック需要dpqと、ネットワーク構成入力部32から供給される容量cijおよびネットワーク情報とに基づいて、上述した式(16a)乃至(16f)にしたがって、発着ノードペアごとに割合kmpqを算出する。そして、トラヒック量割合算出部33は、ノード21に、それぞれを発ノードとするときの割合kmpqを供給し、処理は終了する。
【0099】
[トラヒック分散部の詳細構成例]
図6は、図2のトラヒック分散部22の詳細構成例を示している。
【0100】
図6において、トラヒック分散部22は、トラヒック量割合入力部51、経路テーブル記憶部52、パケット入力部53、パケットヘッダ解析部54、次ノード決定部55、およびスイッチ部56により構成される。
【0101】
トラヒック量割合入力部51は、トラヒック量割合算出装置11から、自分のノード21を発ノードとする割合kmpqを取得する。そして、トラヒック量割合入力部51は、その割合kmpqを経路テーブル記憶部52に供給し、記憶させる。経路テーブル記憶部52は割合kmpqを記憶する。
【0102】
パケット入力部53は、トラヒックとして入力されるパケットのうち、自分のノード21が発ノードとなるパケットを取得し、パケットヘッダ解析部54に供給する。
【0103】
パケットヘッダ解析部54は、パケット入力部53から供給されるパケットのヘッダを解析し、そのパケットの着ノード21を認識する。そして、パケットヘッダ解析部54は、パケット入力部53から供給されるパケットと、それに対応する着ノード21を特定する情報を次ノード決定部55に供給する。
【0104】
次ノード決定部55は、パケットヘッダ解析部54から供給される着ノード21を特定する情報に基づいて、経路テーブル記憶部52から、その着ノード21に対応する割合kmpqを全て読み出す。そして、次ノード決定部55は、その割合kmpqにしたがって中間ノードmを決定し、その中間ノードmへの経路(IPトンネル)を決定する。次ノード決定部55は、決定された中間ノードmへの経路を特定する経路特定情報、中間ノードmを特定する情報などをヘッダとしてパケットに付加し、経路特定情報とともにスイッチ部56に供給する。
【0105】
スイッチ部56は、経路特定情報に対応する経路を介して、パケットを転送する。その結果、パケットは、中間ノードmに転送され、その後、着ノード21に転送される。
【0106】
[トラヒック分散部の処理の説明]
次に、図7のフローチャートを参照して、図6のトラヒック分散部22によるトラヒック分散処理について説明する。
【0107】
ステップS11において、パケット入力部53は、トラヒックとして入力されるパケットのうち、自分のノード21が発ノードとなるパケットを取得し、パケットヘッダ解析部54に供給する。
【0108】
ステップS12において、パケットヘッダ解析部54は、パケット入力部53から供給されるパケットのヘッダを解析し、そのパケットの着ノード21を認識する。そして、パケットヘッダ解析部54は、パケット入力部53から供給されるパケットと、それに対応する着ノード21を特定する情報を次ノード決定部55に供給する。
【0109】
ステップS13において、次ノード決定部55は、パケットヘッダ解析部54から供給される着ノード21を特定する情報に基づいて、経路テーブル記憶部52から、その着ノードに対応する割合kmpqを全て読み出す。
【0110】
ステップS14において、次ノード決定部55は、ステップS13で読み出された割合kmpqにしたがって中間ノードmを決定し、その中間ノードmへの経路(IPトンネル)を決定する。そして、次ノード決定部55は、決定された中間ノードmへの経路を特定する経路特定情報、中間ノードmなどをヘッダとしてパケットに付加し、経路特定情報とともにスイッチ部56に供給する。
【0111】
ステップS15において、スイッチ部56は、経路特定情報に対応する経路を介して、ステップS14で決定された中間ノードmへパケットを転送し、処理は終了する。このパケットは、その後、着ノード21に転送される。
【0112】
[効果を示す実験]
次に、図8乃至図10を参照して、FTPRの効果について説明する。
【0113】
まず、図8および図9は、ネットワークシステム10における効果を示す実験に用いたサンプルネットワーク#1乃至#6の構成を示している。なお、図8において、黒丸はノードを表し、線はリンクを表している。
【0114】
図8および図9に示すように、サンプルネットワーク#1は、ノード数(No.of nodes)が6、リンク数(No.of links)が24、平均ノード次数(Ave. node degree)が4.00のネットワークである。なお、平均ノード次数とは、1つのノードに接続されるリンクの数の平均値である。
【0115】
また、サンプルネットワーク#2は、ノード数が12、リンク数が36、平均ノード次数が3.00のネットワークである。サンプルネットワーク#3は、ノード数が12、リンク数が48、平均ノード次数が4.00のネットワークである。サンプルネットワーク#4は、ノード数が15、リンク数が56、平均ノード次数が3.73のネットワークである。
【0116】
サンプルネットワーク#5は、ノード数が20、リンク数が68、平均ノード次数が3.40のネットワークである。サンプルネットワーク#6は、ノード数が35、リンク数が100、平均ノード次数が2.86のネットワークである。
【0117】
次に、図10を参照して、以上のようなサンプルネットワーク#1乃至#6を用いて行った実験結果について説明する。
【0118】
なお、この実験では、リンクlink(i,j)の使用可能な帯域の容量cijとして、80から120までの間で一様に分布するようなランダムな100種類の値を設定した。また、トラヒック需要dpqとして、0から100までの間で一様に分布するようなランダムな100種類の値を設定した。
【0119】
さらに、FTPRとTPRでは、リンクの重みは容量cijの逆数となるように設定し、発ノードから中間ノードまでの経路、および、中間ノードから着ノードまでの経路は、そのリンクの重みを距離として、最短経路となるように設定した。
【0120】
以上のような条件で行われた実験において、TPRを用いてトラヒックを分散して転送した場合、FTPRを用いてトラヒックを分散して転送した場合、および、MPLS-TEを用いて経路制御を行った場合のネットワーク輻輳率rは、図10に示すようになる。
【0121】
但し、3つの場合のネットワーク輻輳率rを比較するために、FTPRの場合のネットワーク輻輳率rFTPRとMPLS-TEの場合のネットワーク輻輳率rMPLS-TEは、TPRの場合のネットワーク輻輳率rTPRを1.0として規格化されている。また、図10に示すネットワーク輻輳率rFTPR,rMPLS-TE,rTPRは、ランダムに設定された100種類の容量cijとトラヒック需要dpqの下での値の平均値である。
【0122】
図10に示すように、ネットワーク輻輳率rFTPRは、ネットワーク輻輳率rTPRに比べて非常に小さくなっている。具体的には、ネットワーク輻輳率rFTPRの値の範囲は、0.46乃至0.59であり、FTPRでは、TPRの場合に比べて、ネットワーク輻輳率を40%以上削減できることがわかる。
【0123】
また、図10に示すように、ネットワーク輻輳率rFTPRは、ネットワーク輻輳率rMPLS-TEと同等になっている。そこで、ネットワーク輻輳率rFTPRとrMPLS-TEの差を詳細に検討するために、ネットワーク輻輳率rFTPRとrMPLS-TEの偏差δを、次式(17)で定義すると、サンプルネットワーク#1乃至#6の全てにおいて偏差δのεは10-6以下となった。
【0124】
【数18】
JP0005376571B2_000019t.gif

【0125】
即ち、εは、各方式のLP問題を特にあたって、解の精度の上限値の値となった。従って、FTPRによれば、MPLS-TEのような精巧な経路制御を用いずに、MPLS-TEと同等の経路制御の性能を提供できることがわかる。
【0126】
[分散の割合の算出方法の第2の例]
なお、上述した説明では、分散の割合kmpqが実数値をとるようにしたが、割合kmpqの値が0または1をとるようにしてもよい。即ち、発着ノードペアに対して中間ノード21が1つに固定されるようにしてもよい。この場合、トラヒック分散部22の実装をより簡単に行うことができる。
【0127】
また、この場合、割合kmpqを決定する最適経路問題は、次式(18a)乃至(18f)で定式化される。
【0128】
【数19】
JP0005376571B2_000020t.gif

【0129】
即ち、上述した割合kmpqを決定する最適経路問題の式(16e)が(18e)に変更される。
【0130】
[分散の割合の算出方法の第3の例]
また、上述した説明では、ネットワークモデルとしてパイプモデルを仮定し、分散の割合kmpqを算出したが、ネットワークモデルとしてホースモデルを仮定し、分散の割合kmpqを算出するようにしてもよい。
【0131】
この場合、割合kmpqを決定する最適経路問題は、次式(19a)乃至(19g)で定式化される。
【0132】
【数20】
JP0005376571B2_000021t.gif

【0133】
なお、式(19a)乃至(19g)において、αpは、ノードpから送出するトラヒックの総量を表し、βqは、ノードqに流入するトラヒックの総量を表している。
【0134】
また、式(19a)乃至(19g)において、ψ,τは次式(20),(21)でそれぞれ定義される。
【0135】
【数21】
JP0005376571B2_000022t.gif

【数22】
JP0005376571B2_000023t.gif

【0136】
さらに、式(19a)乃至(19g)において、π,λ,ξは次式(22)で定義される。
【0137】
【数23】
JP0005376571B2_000024t.gif

【0138】
式(19a)乃至(19g)に示すように、ネットワークモデルとしてホースモデルを仮定する場合、割合kmpqの算出において、トラヒック需要dpqの代わりに、トラヒックの総量αp,βqが用いられる。従って、トラヒック量割合入力部51には、トラヒック需要dpqではなく、トラヒックの総量αpおよびβqが入力されることになる。
【0139】
トラヒック需要dpqは、発着ノードペア数、即ちノード21の数の二乗個存在するが、トラヒックの総量αp,βqは、それぞれ、発ノード,着ノードの数、即ちノード21の数だけ存在する。従って、ネットワークモデルとしてホースモデルを仮定する場合、パイプモデルを仮定する場合に比べて、トラヒック量割合入力部51に入力するパラメータの数は少なくて済む。但し、経路制御の性能は少し低下する。
【0140】
なお、上述した説明では、ノード21間の経路は分散しないものとし、Fpmijの値は1または0であるようにしたが、ノード21間の経路は分散してもよい。
【0141】
また、ネットワーク12内の全てのノード21がFTPRでトラヒックを分散させて転送する必要はない。ネットワーク12内にFTPRでトラヒックを分散させて転送しないノード21がある場合、そのノード21をノード21-p´として、次の条件式(23)を上述した式(16a)乃至(16f)、式(18a)乃至(18f)、または式(19a)乃至(19g)に加えることで、割合kmpqを算出することができる。
【0142】
【数24】
JP0005376571B2_000025t.gif

【0143】
さらに、ネットワーク12内のノード21ごとに、式(16a)乃至(16f)を用いて割合kmpqを算出するか、式(18a)乃至(18f)を用いて割合kmpqを算出するかを決定してもよい。
【0144】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【0145】
また、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【0146】
【図1】TPRの動作について説明する図である。
【図2】本発明を適用したネットワークシステムの一実施の形態の構成例を示す図である。
【図3】図2のネットワークシステムにおけるトラヒックの分散について説明する図である。
【図4】図2のトラヒック割合算出装置の詳細構成例を示すブロック図である。
【図5】図4のトラヒック量割合算出装置による割合算出処理について説明するフローチャートである。
【図6】図2のトラヒック分散部の詳細構成例を示す図である。
【図7】図6のトラヒック分散部によるトラヒック分散処理について説明するフローチャートである。
【図8】サンプルネットワークの構成を示す図である。
【図9】サンプルネットワークの構成をまとめた表を示す図である。
【図10】実験結果を示す図である。
【符号の説明】
【0147】
11 トラヒック量割合算出装置, 12 ネットワーク, 20-1乃至20-5 リンク, 21-1乃至21-4 ノード, 22-1乃至22-4 トラヒック分散部, 55 次ノード決定部, 56 スイッチ部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9