(57)【要約】【課題】トラヒックを効果的に分散させ、ネットワークの使用効率を向上させる。【解決手段】ネットワーク１２は、複数のノード２１がリンク２０を介して接続されることにより構成され、発ノード２１に入力されたトラヒックを、中間ノード２１を介して着ノード２１に送信する。トラヒック量割合算出装置１１は、ネットワークの構成、および、リンク２０の使用可能な帯域の容量に基づいて、発ノード２１と着ノード２１の組み合わせごとに、各ノード２１を中間ノードとしてトラヒックを分散させる割合を算出する。本発明は、例えば、ノードを制御する装置に適用することができる。【選択図】図２
2010147826.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードがリンクを介して接続されることにより構成されるネットワークにおいて、発ノードに入力されたトラヒックを、中間ノードを介して着ノードに送信する場合に、前記トラヒックの通信を制御する制御装置において、
前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合を算出する算出手段
を備える制御装置。
【請求項２】
前記算出手段は、前記ネットワークの構成、前記リンクの使用可能な帯域の容量、および前記トラヒックに関する情報に基づいて、前記割合を算出する
請求項１に記載の制御装置。
【請求項３】
前記算出手段は、前記ネットワークのモデルとしてパイプモデルを仮定し、前記割合を算出する
請求項２に記載の制御装置。
【請求項４】
前記算出手段は、前記ネットワークのモデルとしてホースモデルを仮定し、前記割合を算出する
請求項１に記載の制御装置。
【請求項５】
複数のノードがリンクを介して接続されることにより構成されるネットワークにおいて、発ノードに入力されたトラヒックを、中間ノードを介して着ノードに送信する場合に、前記トラヒックの通信を制御する制御装置の制御方法において、
前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合を算出する算出ステップ
を含む制御方法。
【請求項６】
ネットワークを構成するノードであって、入力されたトラヒックを、前記ネットワーク内の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードにおいて、
前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定手段と、
前記決定手段により決定された前記中間ノードに前記トラヒックを送信する送信手段と
を備えるノード。
【請求項７】
ネットワークを構成するノードであって、入力されたトラヒックを、前記ネットワーク内の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードの送信方法において、
前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定ステップと、
前記決定ステップの処理により決定された前記中間ノードに前記トラヒックを送信する送信ステップと
を含む送信方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、制御装置および制御方法、ノードおよび送信方法に関し、特に、トラヒックを効果的に分散させ、ネットワークの使用効率を向上させることができるようにした制御装置および制御方法、ノードおよび送信方法に関する。
【背景技術】
【０００２】
ネットワークにおいては、適切な経路制御方式を採用することにより、リソースの使用効率を向上させ、スループットを増加させることができる（例えば、非特許文献１参照）。即ち、適切な経路制御方式では、トラヒックを最適に各経路に割り当て、より多くのトラヒックをネットワークに収容させることができる。また、適切な経路制御方式では、ネットワークの輻輳を抑制したり、トラヒック変動への耐久性を増加させたりすることができる。
【０００３】
経路制御の効果を向上させる１つの方法としては、ネットワークの全てのリンクの使用率の最大値（以下、ネットワーク輻輳率という）を最小化することが挙げられる。ネットワーク輻輳率を最小化することにより、ネットワークに収容可能なトラヒックを増加させることができる。
【０００４】
ところで、経路制御に関しては、様々な研究が行われている。その結果、例えば、非特許文献２では、一般的なトラヒックエンジニアリングの問題、即ちトラヒック需要が、発着ノード間で自由に経路を選択および分散できる問題として定式化されている。
【０００５】
また、非特許文献３には、精巧な経路制御は、例えば、MPLS-TE（Multi-Protocol Label Switching Traffic-Engineering）技術を用いて達成可能であることが記載されている。
【０００６】
しかしながら、既に構築されているネットワークでは、主に、OSPF（Open Shortest Path First）やIS-IS（Intermediate System to Intermediate System）のような最短経路ベースのルーチングプロトコルが採用されている。従って、既に導入されているＩＰ（Internet Protocol）ルータなどのノードがMPLS-TEを採用するためには、ノードのアップグレードが必要となってしまう。そのため、可能な限り既存のルーチングプロトコルを有効利用することが必要であると考えられる。
【０００７】
そこで、非特許文献４乃至６に記載されているように、OSPFベースでネットワークのリンクの重みを最適化する経路制御方式が研究されている。この経路制御方式では、最短経路計算にあたって、リンクの重みがリンクの距離として計算される。また、トラヒック需要が変化すると、最適なリンクの重みが再計算され、再計算されたリンクの重みが、ネットワーク上のノードに再設定される。そして、最新のリンクの重みにしたがって、経路が再計算される。従って、経路が頻繁に変化すると、ネットワーク上の経路の不安定性を招き、これは、パケットロスやループを生じさせる原因となる。
【０００８】
また、トラヒックを分散させ、ネットワークの利用効率を向上させる分散経路制御方式も研究されている。例えば、非特許文献７では、TPR（two-phase routing) over shortest pathsが提案されている。TPRでは、発ノードから送出されたトラヒックのフローは、ネットワーク上の中間ノードへ分散され、中間ノードから着ノードへ向かう。TPRでは、分散させる経路数を増加させることができ、これにより、ネットワーク輻輳率を削減することができる。
【０００９】
なお、非特許文献７に記載されているTPRでは、発ノードから中間ノードまでの経路選択、および、中間ノードから着ノードまでの経路選択は、既存のルーチングプロトコルを使用するという制限が設けられている。これに対して、非特許文献８に記載されているTPRでは、既存のルーチングプロトコルを使用するという制限は設けられていない。
【００１０】
以下に、TPRの動作について説明するが、その前に、TPRを採用するネットワークモデルを以下のように定義する。
【００１１】
ネットワークは有効グラフＧ(Ｖ,Ｅ)で表現する。ここで、Ｖはノードの集合、Ｅはリンクの集合を表している。また、ノードｉ∈Ｖからノードｊ∈Ｖまでのリンクはlink(i,j)∈Ｅと表す。link(i,j)∈Ｅの使用可能な帯域の容量はcijと表し、link(i,j)∈Ｅの使用率はＬijと表す。ノードｐからノードｑまでのトラヒック需要ｄpqを表すトラヒック行列は、Ｔ＝｛ｄpq}と表す。
【００１２】
また、ネットワーク輻輳率はｒと表す。なお、現在のトラヒックに対して、1/rを乗じたトラヒックまで、ネットワークは受付可能であり、ネットワーク輻輳率ｒを最小化することは、受付可能なトラヒックを最大化することになる。従って、分散経路制御の目的関数の１つは、ネットワーク輻輳率rの最小化である。
【００１３】
さらに、非特許文献７および８に記載されているTPRでは、ネットワークモデルとしてＴ＝｛ｄpq｝が既知または推定可能なホースモデルが仮定されているため、ここでも同様の仮定を行う。そこで、αpを、ノードｐからネットワークに送出するトラヒックの総量と定義する。従って、式
【数１】
2010147826.tif 000003
が成り立つ。この式は、ホースモデルにおけるノードｐの制約条件を表す。
【００１４】
また、βqを、ネットワークからノードｑに流入するトラヒックの総量と定義する。従って、式
【数２】
2010147826.tif 000004
が成り立つ。この式は、ホースモデルにおけるノードｑの制約条件を表す。
【００１５】
なお、ネットワークモデルとしては、αp、βqが既知または推定可能なホースモデルが仮定されてもよい。
【００１６】
次に、以上のようにネットワークモデルが定義された場合のTPRの動作について説明する。
【００１７】
TPRでは、トラヒックは、ノードｐからノードｑに直接転送されず、中間ノードｍ∈Ｖに、トラヒックが分散される。そして、全ての発着ノードペア(ｐ,ｑ)に対して、ｄpqのフローは、中間ノードｍ∈Ｖに、ｋmの割合で分散される。ここで、割合ｋmについては、０≦ｋm≦１、かつ、
【数３】
2010147826.tif 000005
が成立する。中間ノードｍに分散されたトラヒックは、着ノードｑに転送される。
【００１８】
例えば、発ノードがノード１であり、着ノードがノード３である場合、図１に示すように、発ノードであるノード１から着ノードであるノード３へのトラヒックは、中間ノードとしてのノード２、ノード３、ノード４に、それぞれ、ｋ2，ｋ3，ｋ4の割合で分散される。
【００１９】
従って、発ノードであるノード１から、中間ノードであるノード２を介して、着ノードであるノード３に分散されるトラヒックの割合は、ｋ2となる。発ノードであるノード１から、中間ノードおよび着ノードであるノード３に分散されるトラヒックの割合は、ｋ3となる。発ノードであるノード１から、中間ノードであるノード４を介して、着ノードであるノード３に分散されるトラヒックの割合は、ｋ4となる。
【００２０】
また、発ノードがノード１であり、着ノードがノード２である場合も、図１に示すように、発ノードであるノード１から着ノードであるノード２へのトラヒックは、中間ノードとしてのノード２、ノード３、ノード４に、それぞれ、ｋ2，ｋ3，ｋ4の割合で分散される。
【００２１】
従って、発ノードであるノード１から、中間ノードおよび着ノードであるノード２に分散されるトラヒックの割合は、ｋ2となる。発ノードであるノード１から、中間ノードであるノード３を介して、着ノードであるノード２に分散されるトラヒックの割合は、ｋ3となる。発ノードであるノード１から、中間ノードであるノード４を介して、着ノードであるノード２に分散されるトラヒックの割合はｋ4となる。
【００２２】
即ち、TPRでは、発着ノードペア（ｐ，ｑ）によらず、割合ｋ2，ｋ3，ｋ4で、中間ノードとしてのノード２、ノード３、ノード４にトラヒックが分散される。
【００２３】
なお、ノードｐから中間ノードｍまでの経路選択、および、中間ノードｍからノードｑまでの経路選択の方式としては、例えば最短経路方式が用いられる。これは、ノードｐと中間ノードｍの間に、IP-in-IPやGRE（Generic Routing Encapsulation)トンネルを設定することで実現できる。
【００２４】
次に、TPRにおいてネットワーク輻輳率ｒを最小化するための割合ｋmの算出方法について説明する。
【００２５】
まず、ノードｐから、中間ノードｍを介して、ノードｑへ転送されるトラヒックを考える。ここで、ノードｐと中間ノードｍの間のトラヒックをｂpmで表すと、ノードｐとノードｍの間のトラヒックは、２つのコンポーネントから構成される。１つ目のコンポーネントは、ノードｐを発ノードとし、中間ノードｍを中間ノードとして分散されるトラヒックであり、２つ目のコンポーネントは、ノードｐを中間ノードとし、中間ノードｍを着ノードとして転送されるトラヒックである。
【００２６】
従って、１つ目のコンポーネントとしてのトラヒックをｂpm(1)と定義し、２つ目のコンポーネントとしてのトラヒックをｂpm(2)と定義すると、トラヒックｂpmは、以下の式（１）で表される。
【００２７】
ｂpm＝ｂpm(1)+ｂpm(2)
・・・（１）
【００２８】
また、上述したホースモデルにおけるノードｐの制約条件を用いると、トラヒックｂpm(1)は以下の式（２）で与えられ、トラヒックｂpm(2)は以下の式（３）で与えられる。
【００２９】
【数４】
2010147826.tif 000006
【数５】
2010147826.tif 000007
【００３０】
従って、トラヒックｂpmは、トラヒックの総量αp，βqを用いた以下の式（４）で表される。
【００３１】
ｂpm＝ｋmαp+ｋpβm
・・・（４）
【００３２】
ここで、リンクlink(i,j)がノードｐと中間ノードｍの経路上にあれば、値１をとり、それ以外であれば値０をとる関数をＦpmijと定義すると、リンクlink(i,j)の使用率Ｌijは、次式（５）で与えられる。
【００３３】
【数６】
2010147826.tif 000008
【００３４】
但し、ψmijは、次式（６）で定義される。
【００３５】
【数７】
2010147826.tif 000009
【００３６】
また、ノードｊに流入するトラヒックとノードｊから流出するトラヒックの差は、次式（７）で与えられる。
【００３７】
【数８】
2010147826.tif 000010
【００３８】
但し、ωmjは、次式（８）で定義される。
【００３９】
【数９】
2010147826.tif 000011
【００４０】
以上により、TPRにおいて、割合ｋmを決定する最適経路問題は、次式（９ａ）乃至（９ｆ）で定式化される。
【００４１】
【数１０】
2010147826.tif 000012
【００４２】
なお、式（９ａ）は、ネットワーク輻輳率rを最小化する目的関数を示している。式(９ｂ)は、ネットワークのノードに関して、割合ｋmのすべての和が１であることを示している。式(９ｃ)は、全てのリンクにおいて、リンクlink(i,j)を通過するトラヒックの総和がｃij×ｒ以下であることを示している。式（９ｄ）は、フロー保存則を示している。
【００４３】
以上のようにして定式化された式（９ａ）乃至（９ｆ）を解くことにより、TPRにおいてネットワーク輻輳率ｒを最小化するための割合ｋmが算出される。なお、式（９ａ）乃至（９ｆ）は、線形計画問題(LP（Linear Programming)）であるため、標準のLPソルバ（solver）で解くことができる。
【００４４】
【非特許文献１】R. Zhang-Shen and N. McKeown, “Designing a Fault-Tolerant Network Using Valiant Load-Balancing”, IEEE Infocom 2008, April 2008
【非特許文献２】Y. Wang and Z. Wang, “Explicit routing algorithms for internet traffic engineering,” IEEE International Conference on Computer Communications and Networks (ICCCN), 1999
【非特許文献３】D. Awduche et al., “Requirements for Traffic Engineering Over MPLS”, RFC 2702, Sept. 1999
【非特許文献４】Y. Wang and M. R. Ito, “Dynamics of load sensitive adaptive routing”, IEEE International Conference on Communications (ICC), 2005
【非特許文献５】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
【非特許文献６】J. Chu and C. Lea, “Optimal Link Weights for Maximizing QoS Traffic”, IEEE ICC 2007, pp. 610-615, 2007
【非特許文献７】M. Antic and A. Smiljanic, “Oblivious Routing Scheme Using Load Balancing Over Shortest Paths”, IEEE ICC 2008, 2008
【非特許文献８】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
【発明の開示】
【発明が解決しようとする課題】
【００４５】
以上のように、TPRでは、中間ノードｍにトラヒックを分散させる割合ｋは、発着ノードペアには依存せず、中間ノードｍにだけ依存するｋmである。そのため、トラヒックが効果的に分散できない恐れがある。
【００４６】
本発明は、このような状況に鑑みてなされたものであり、トラヒックを効果的に分散させ、ネットワークの使用効率を向上させることができるようにするものである。
【課題を解決するための手段】
【００４７】
本発明の第１の側面は、複数のノードがリンクを介して接続されることにより構成されるネットワークにおいて、発ノードに入力されたトラヒックを、中間ノードを介して着ノードに送信する場合に、前記トラヒックの通信を制御する制御装置において、前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合を算出する算出手段を備える制御装置である。
【００４８】
本発明の第１の側面は、複数のノードがリンクを介して接続されることにより構成されるネットワークにおいて、発ノードに入力されたトラヒックを、中間ノードを介して着ノードに送信する場合に、前記トラヒックの通信を制御する制御装置の制御方法において、前記ネットワークの構成、および、前記リンクの使用可能な帯域の容量に基づいて、前記発ノードと前記着ノードの組み合わせごとに、各ノードを前記中間ノードとして前記トラヒックを分散させる割合を算出する算出ステップを含む制御方法である。
【００４９】
本発明の第２の側面は、ネットワークを構成するノードであって、入力されたトラヒックを、前記ネットワーク内の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードにおいて、前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定手段と、前記決定手段により決定された前記中間ノードに前記トラヒックを送信する送信手段とを備えるノードである。
【００５０】
本発明の第２の側面は、ネットワークを構成するノードであって、入力されたトラヒックを、前記ネットワーク内の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードの送信方法において、前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定ステップと、前記決定ステップの処理により決定された前記中間ノードに前記トラヒックを送信する送信ステップとを含む送信方法である。
【００５１】
本発明の第１の側面においては、複数のノードがリンクを介して接続されることにより構成されるネットワークにおいて、発ノードに入力されたトラヒックを、中間ノードを介して着ノードに送信する場合に、ネットワークの構成、および、リンクの使用可能な帯域の容量に基づいて、発ノードと着ノードの組み合わせごとに、各ノードを中間ノードとしてトラヒックを分散させる割合が算出される。
【００５２】
本発明の第２の側面においては、入力されたトラヒックを、ネットワーク内の中間ノードを介して、ネットワーク内の着ノードに送信する場合に、トラヒックが入力される発ノードと着ノードの組み合わせごとに求められた、ネットワーク内の各ノードを中間ノードとしてトラヒックを分散させる割合に基づいて、トラヒックを送信する中間ノードが決定され、その中間ノードにトラヒックが送信される。
【発明の効果】
【００５３】
以上のように、本発明によれば、トラヒックを効果的に分散させ、ネットワークの使用効率を向上させることができる。
【発明を実施するための最良の形態】
【００５４】
＜第１実施の形態＞
［ネットワークシステムの一実施の形態の構成例］
図２は、本発明を適用したネットワークシステムの一実施の形態の構成例を示す図である。
【００５５】
図２のネットワークシステム１０は、トラヒック量割合算出装置１１と、リンク２０−１乃至２０−５を介して接続されたノード２１−１乃至２１−４よりなるネットワーク１２とから構成される。ネットワークシステム１０は、TPRを改良した方式（ここでは、FTPR（Fine Two Phase Routing）という）で、発ノードに入力されたトラヒックを、中間ノードを介して着ノードに送信する。
【００５６】
なお、以下では、リンク２０−１乃至２０−５を特に区別する必要がない場合、それらをまとめてリンク２０という。また、ノード２１−１乃至２１−４についても同様にノード２１という。さらに、発ノード、中間ノード、着ノードとなるノード２１を、それぞれ、発ノード２１、中間ノード２１、着ノード２１ともいう。
【００５７】
トラヒック量割合算出装置１１は、ネットワーク１２の各ノード２１に接続されている。トラヒック量割合算出装置１１は、ネットワーク１２の構成およびリンク２０の使用可能な帯域の容量に基づいて、発ノード２１に入力されるトラヒックを、中間ノード２１に分散させる割合を、発着ノードペアごとに算出する。トラヒック量割合算出装置１１は、ノード２１が発ノードであるときの割合を、そのノード２１に供給する。
【００５８】
ノード２１−１乃至２１−４は、それぞれ、トラヒック分散部２２−１乃至２２−４を有する。なお、以下では、トラヒック分散部２２−１乃至２２−４を特に区別する必要がない場合、それらをまとめてトラヒック分散部２２という。
【００５９】
ノード２１のトラヒック分散部２２は、トラヒック量割合算出装置１１から供給される割合に基づいて、そのノード２１を発ノードとして入力されるトラヒックを中間ノード２１に分散して転送する。
【００６０】
具体的には、トラヒック分散部２２は、トラヒック量割合算出装置１１から供給される割合に基づいて、そのトラヒック分散部２２を備えるノード２１を発ノードとして入力されるトラヒックを送信する中間ノード２１を決定する。そして、トラヒック分散部２２は、その中間ノード２１にトラヒックを送信する。
【００６１】
次に、図３を参照して、図２のネットワークシステム１０におけるトラヒックの分散について説明する。
【００６２】
ネットワークシステム１０では、発着ノードペアごとに、中間ノード２１にトラヒックが分散される割合が算出されるので、図３Ａに示すように、発ノードがノード２１−１であり、着ノードがノード２１−３である場合と、図３Ｂに示すように、発ノードがノード２１−１であり、着ノードがノード２１−２である場合とでは、中間ノード２１に分散されるトラヒックの割合が異なる。
【００６３】
具体的には、例えば、図３Ａに示すように、発ノード２１−１から着ノード２１−３へのトラヒックは、中間ノード２１−２、中間ノード２１−３、中間ノード２１−４に、それぞれ、ｋ213，ｋ313，ｋ413の割合で分散される。
【００６４】
従って、発ノード２１―１から中間ノード２１−２を介して着ノード２１−３に分散されるトラヒックの割合はｋ213となる。発ノード２１−１から中間ノードおよび着ノードであるノード２１−３に分散されるトラヒックの割合はｋ313となる。発ノード２１−１から中間ノード２１−４を介して着ノード２１−３に分散されるトラヒックの割合はｋ413となる。
【００６５】
なお、発ノードがノード２１−ｐであり、着ノードがノード２１−ｑである場合にノード２１−ｍに分散される割合をｋmpqと表している。
【００６６】
一方、着ノードがノード２１−３である場合には、図３Ｂに示すように、発ノード２１−１から着ノード２１−３へのトラヒックは、中間ノード２１−２、中間ノード２１−３、中間ノード２１−４に、それぞれ、ｋ213，ｋ313，ｋ413とは異なるｋ212，ｋ312，ｋ412の割合で分散される。
【００６７】
従って、発ノード２１−１から着ノード２１−２に分散されるトラヒックの割合はｋ212となる。発ノード２１―１から中間ノード２１―３を介して着ノード２１−２に分散されるトラヒックの割合はｋ312となる。発ノード２１−１から中間ノード２１−４を介して着ノード２１−２に分散されるトラヒックの割合はｋ412となる。
【００６８】
以上のように、ネットワークシステム１０では、発着ノードペアによって異なる割合で、中間ノード２１−２、中間ノード２１−３、中間ノード２１−４にトラヒックが分散されるので、TPRで分散される場合に比べて、より最適な割合で効果的にトラヒックを分散することができる。その結果、ネットワーク輻輳率を削減することができる。
【００６９】
［分散の割合の算出方法の第１の例］
次に、割合ｋmpqの算出方法について説明する。
【００７０】
まず、ネットワークシステム１０のネットワークモデルを以下のように定義する。
【００７１】
ネットワーク１２は有効グラフＧ(Ｖ,Ｅ)で表現する。ここで、Ｖはノード２１の集合、Ｅはリンク２０の集合を表している。また、ノードｉ∈Ｖからノードｊ∈Ｖまでのリンク２０はlink(i,j)∈Ｅと表す。link(i,j)∈Ｅの使用可能な帯域の容量はcijと表し、link(i,j)∈Ｅの使用率はＬijと表す。ノードｐからノードｑまでのトラヒック需要ｄpqを表すトラヒック行列は、Ｔ＝｛ｄpq}と表す。また、ネットワーク輻輳率をｒと表す。ネットワークモデルとしてはパイプモデルを仮定する。
【００７２】
以上のようにネットワークシステム１０のネットワークモデルが定義されると、ノードｐを発ノードとし、中間ノードｍを中間ノードとして分散されるトラヒックｂpm(1)は、次式（１０）で与えられる。
【００７３】
【数１１】
2010147826.tif 000013
【００７４】
また、ノードｐを中間ノードとし、中間ノードｍを着ノードとして転送されるトラヒックｂpm(2)は、次式（１１）で与えられる。
【００７５】
【数１２】
2010147826.tif 000014
【００７６】
ここで、リンクlink(i,j)がノードｐと中間ノードｍの経路上にあれば、値１をとり、それ以外であれば値０をとる関数をＦpmijと定義すると、リンクlink(i,j)の使用率Ｌijは、次式（１２）で与えられる。
【００７７】
【数１３】
2010147826.tif 000015
【００７８】
但し、ψpqmijは、次式（１３）で定義される。
【００７９】
【数１４】
2010147826.tif 000016
【００８０】
また、ノードｊに流入するトラヒックとノードｊから流出するトラヒックの差は、次式（１４）で与えられる。
【００８１】
【数１５】
2010147826.tif 000017
【００８２】
但し、ωpqmjは、次式（１５）で定義される。
【００８３】
【数１６】
2010147826.tif 000018
【００８４】
以上により、ネットワークシステム１０において、割合ｋmpqを決定する最適経路問題は、次式（１６ａ）乃至（１６ｆ）で定式化される。
【００８５】
【数１７】
2010147826.tif 000019
【００８６】
なお、式（１６ａ）は、ネットワーク輻輳率rを最小化する目的関数を示している。式(１６ｂ)は、ノード２１に関して、割合ｋmpqのすべての和が１であることを示しており、割合ｋmpqは、式（１６ｂ）を満たす全ての実数値をとることができる。
【００８７】
また、式(１６ｃ)は、全てのリンク２０において、リンクlink(i,j)を通過するトラヒックの総和がｃij×ｒ以下であることを示している。式（１６ｄ）は、フロー保存則を示している。
【００８８】
以上のようにして定式化された式（１６ａ）乃至（１６ｆ）を解くことにより、ネットワーク輻輳率ｒを最小化するための割合ｋmpqが算出される。なお、式（１６ａ）乃至（１６ｆ）は、線形計画問題であるため、標準のLPソルバ（solver）で解くことができる。
【００８９】
従って、トラヒック量割合算出装置１１は、式（１６ａ）乃至（１６ｆ）を解くことにより、割合ｋmpqを算出する。
【００９０】
［トラヒック割合算出装置の詳細構成例］
図４は、図２のトラヒック量割合算出装置１１の詳細構成例を示すブロック図である。
【００９１】
図４において、トラヒック量割合算出装置１１は、トラヒック量入力部３１、ネットワーク構成入力部３２、およびトラヒック量割合算出部３３により構成される。
【００９２】
トラヒック量入力部３１には、外部から各ノード２１のトラヒックに関する情報としてトラヒック需要ｄpqが入力される。このトラヒック需要ｄpqは、例えば、各ノード２１から実際に検出されたものであってもよいし、オペレータにより入力される予想トラヒック量であってもよい。トラヒック量入力部３１は、入力されたトラヒック需要ｄpqを取得し、トラヒック量割合算出部３３に供給する。
【００９３】
ネットワーク構成入力部３２には、オペレータなどにより外部から、リンクlink(i,j)の使用可能な帯域の容量cij、有効グラフＧ(Ｖ,Ｅ)などのネットワーク１２の構成を表す情報（以下、ネットワーク情報という）が入力される。ネットワーク構成入力部３２は、入力された容量cijおよびネットワーク情報を取得し、トラヒック量割合算出部３３に供給する。
【００９４】
トラヒック量割合算出部３３は、トラヒック量入力部３１から供給されるトラヒック需要ｄpqと、ネットワーク構成入力部３２から供給される容量cijおよびネットワーク情報とに基づいて、上述した式（１６ａ）乃至（１６ｆ）にしたがって、発着ノードペアごとに割合ｋmpqを算出する。トラヒック量割合算出部３３は、ノード２１に、それぞれを発ノードとするときの割合ｋmpqを供給する。
【００９５】
［トラヒック量割合算出装置の処理の説明］
次に、図５のフローチャートを参照して、図４のトラヒック量割合算出装置１１による割合算出処理について説明する。
【００９６】
ステップＳ１において、トラヒック量入力部３１は、入力されたトラヒック需要ｄpqを取得し、トラヒック量割合算出部３３に供給する。
【００９７】
ステップＳ２において、ネットワーク構成入力部３２は、入力された容量cijおよびネットワーク情報を取得し、トラヒック量割合算出部３３に供給する。
【００９８】
ステップＳ３において、トラヒック量割合算出部３３は、トラヒック量入力部３１から供給されるトラヒック需要ｄpqと、ネットワーク構成入力部３２から供給される容量cijおよびネットワーク情報とに基づいて、上述した式（１６ａ）乃至（１６ｆ）にしたがって、発着ノードペアごとに割合ｋmpqを算出する。そして、トラヒック量割合算出部３３は、ノード２１に、それぞれを発ノードとするときの割合ｋmpqを供給し、処理は終了する。
【００９９】
［トラヒック分散部の詳細構成例］
図６は、図２のトラヒック分散部２２の詳細構成例を示している。
【０１００】
図６において、トラヒック分散部２２は、トラヒック量割合入力部５１、経路テーブル記憶部５２、パケット入力部５３、パケットヘッダ解析部５４、次ノード決定部５５、およびスイッチ部５６により構成される。
【０１０１】
トラヒック量割合入力部５１は、トラヒック量割合算出装置１１から、自分のノード２１を発ノードとする割合ｋmpqを取得する。そして、トラヒック量割合入力部５１は、その割合ｋmpqを経路テーブル記憶部５２に供給し、記憶させる。経路テーブル記憶部５２は割合ｋmpqを記憶する。
【０１０２】
パケット入力部５３は、トラヒックとして入力されるパケットのうち、自分のノード２１が発ノードとなるパケットを取得し、パケットヘッダ解析部５４に供給する。
【０１０３】
パケットヘッダ解析部５４は、パケット入力部５３から供給されるパケットのヘッダを解析し、そのパケットの着ノード２１を認識する。そして、パケットヘッダ解析部５４は、パケット入力部５３から供給されるパケットと、それに対応する着ノード２１を特定する情報を次ノード決定部５５に供給する。
【０１０４】
次ノード決定部５５は、パケットヘッダ解析部５４から供給される着ノード２１を特定する情報に基づいて、経路テーブル記憶部５２から、その着ノード２１に対応する割合ｋmpqを全て読み出す。そして、次ノード決定部５５は、その割合ｋmpqにしたがって中間ノードｍを決定し、その中間ノードｍへの経路（ＩＰトンネル）を決定する。次ノード決定部５５は、決定された中間ノードｍへの経路を特定する経路特定情報、中間ノードｍを特定する情報などをヘッダとしてパケットに付加し、経路特定情報とともにスイッチ部５６に供給する。
【０１０５】
スイッチ部５６は、経路特定情報に対応する経路を介して、パケットを転送する。その結果、パケットは、中間ノードｍに転送され、その後、着ノード２１に転送される。
【０１０６】
［トラヒック分散部の処理の説明］
次に、図７のフローチャートを参照して、図６のトラヒック分散部２２によるトラヒック分散処理について説明する。
【０１０７】
ステップＳ１１において、パケット入力部５３は、トラヒックとして入力されるパケットのうち、自分のノード２１が発ノードとなるパケットを取得し、パケットヘッダ解析部５４に供給する。
【０１０８】
ステップＳ１２において、パケットヘッダ解析部５４は、パケット入力部５３から供給されるパケットのヘッダを解析し、そのパケットの着ノード２１を認識する。そして、パケットヘッダ解析部５４は、パケット入力部５３から供給されるパケットと、それに対応する着ノード２１を特定する情報を次ノード決定部５５に供給する。
【０１０９】
ステップＳ１３において、次ノード決定部５５は、パケットヘッダ解析部５４から供給される着ノード２１を特定する情報に基づいて、経路テーブル記憶部５２から、その着ノードに対応する割合ｋmpqを全て読み出す。
【０１１０】
ステップＳ１４において、次ノード決定部５５は、ステップＳ１３で読み出された割合ｋmpqにしたがって中間ノードｍを決定し、その中間ノードｍへの経路（ＩＰトンネル）を決定する。そして、次ノード決定部５５は、決定された中間ノードｍへの経路を特定する経路特定情報、中間ノードｍなどをヘッダとしてパケットに付加し、経路特定情報とともにスイッチ部５６に供給する。
【０１１１】
ステップＳ１５において、スイッチ部５６は、経路特定情報に対応する経路を介して、ステップＳ１４で決定された中間ノードｍへパケットを転送し、処理は終了する。このパケットは、その後、着ノード２１に転送される。
【０１１２】
［効果を示す実験］
次に、図８乃至図１０を参照して、FTPRの効果について説明する。
【０１１３】
まず、図８および図９は、ネットワークシステム１０における効果を示す実験に用いたサンプルネットワーク＃１乃至＃６の構成を示している。なお、図８において、黒丸はノードを表し、線はリンクを表している。
【０１１４】
図８および図９に示すように、サンプルネットワーク＃１は、ノード数（No.of nodes）が６、リンク数（No.of links）が２４、平均ノード次数（Ave. node degree）が4.00のネットワークである。なお、平均ノード次数とは、１つのノードに接続されるリンクの数の平均値である。
【０１１５】
また、サンプルネットワーク＃２は、ノード数が１２、リンク数が３６、平均ノード次数が3.00のネットワークである。サンプルネットワーク＃３は、ノード数が１２、リンク数が４８、平均ノード次数が4.00のネットワークである。サンプルネットワーク＃４は、ノード数が１５、リンク数が５６、平均ノード次数が3.73のネットワークである。
【０１１６】
サンプルネットワーク＃５は、ノード数が２０、リンク数が６８、平均ノード次数が3.40のネットワークである。サンプルネットワーク＃６は、ノード数が３５、リンク数が１００、平均ノード次数が2.86のネットワークである。
【０１１７】
次に、図１０を参照して、以上のようなサンプルネットワーク＃１乃至＃６を用いて行った実験結果について説明する。
【０１１８】
なお、この実験では、リンクlink(i,j)の使用可能な帯域の容量cijとして、80から120までの間で一様に分布するようなランダムな100種類の値を設定した。また、トラヒック需要ｄpqとして、0から100までの間で一様に分布するようなランダムな100種類の値を設定した。
【０１１９】
さらに、FTPRとTPRでは、リンクの重みは容量cijの逆数となるように設定し、発ノードから中間ノードまでの経路、および、中間ノードから着ノードまでの経路は、そのリンクの重みを距離として、最短経路となるように設定した。
【０１２０】
以上のような条件で行われた実験において、TPRを用いてトラヒックを分散して転送した場合、FTPRを用いてトラヒックを分散して転送した場合、および、MPLS-TEを用いて経路制御を行った場合のネットワーク輻輳率ｒは、図１０に示すようになる。
【０１２１】
但し、３つの場合のネットワーク輻輳率ｒを比較するために、FTPRの場合のネットワーク輻輳率ｒFTPRとMPLS-TEの場合のネットワーク輻輳率ｒMPLS-TEは、TPRの場合のネットワーク輻輳率ｒTPRを1.0として規格化されている。また、図１０に示すネットワーク輻輳率ｒFTPR，ｒMPLS-TE，ｒTPRは、ランダムに設定された100種類の容量cijとトラヒック需要ｄpqの下での値の平均値である。
【０１２２】
図１０に示すように、ネットワーク輻輳率ｒFTPRは、ネットワーク輻輳率ｒTPRに比べて非常に小さくなっている。具体的には、ネットワーク輻輳率ｒFTPRの値の範囲は、0.46乃至0.59であり、FTPRでは、TPRの場合に比べて、ネットワーク輻輳率を４０％以上削減できることがわかる。
【０１２３】
また、図１０に示すように、ネットワーク輻輳率ｒFTPRは、ネットワーク輻輳率ｒMPLS-TEと同等になっている。そこで、ネットワーク輻輳率ｒFTPRとｒMPLS-TEの差を詳細に検討するために、ネットワーク輻輳率ｒFTPRとｒMPLS-TEの偏差δを、次式（１７）で定義すると、サンプルネットワーク＃１乃至＃６の全てにおいて偏差δのεは１０-6以下となった。
【０１２４】
【数１８】
2010147826.tif 000020
【０１２５】
即ち、εは、各方式のＬＰ問題を特にあたって、解の精度の上限値の値となった。従って、FTPRによれば、MPLS-TEのような精巧な経路制御を用いずに、MPLS-TEと同等の経路制御の性能を提供できることがわかる。
【０１２６】
［分散の割合の算出方法の第２の例］
なお、上述した説明では、分散の割合ｋmpqが実数値をとるようにしたが、割合ｋmpqの値が０または１をとるようにしてもよい。即ち、発着ノードペアに対して中間ノード２１が１つに固定されるようにしてもよい。この場合、トラヒック分散部２２の実装をより簡単に行うことができる。
【０１２７】
また、この場合、割合ｋmpqを決定する最適経路問題は、次式（１８ａ）乃至（１８ｆ）で定式化される。
【０１２８】
【数１９】
2010147826.tif 000021
【０１２９】
即ち、上述した割合ｋmpqを決定する最適経路問題の式（１６ｅ）が（１８ｅ）に変更される。
【０１３０】
［分散の割合の算出方法の第３の例］
また、上述した説明では、ネットワークモデルとしてパイプモデルを仮定し、分散の割合ｋmpqを算出したが、ネットワークモデルとしてホースモデルを仮定し、分散の割合ｋmpqを算出するようにしてもよい。
【０１３１】
この場合、割合ｋmpqを決定する最適経路問題は、次式（１９ａ）乃至（１９ｇ）で定式化される。
【０１３２】
【数２０】
2010147826.tif 000022
【０１３３】
なお、式（１９ａ）乃至（１９ｇ）において、αpは、ノードｐから送出するトラヒックの総量を表し、βqは、ノードｑに流入するトラヒックの総量を表している。
【０１３４】
また、式（１９ａ）乃至（１９ｇ）において、ψ，τは次式（２０），（２１）でそれぞれ定義される。
【０１３５】
【数２１】
2010147826.tif 000023
【数２２】
2010147826.tif 000024
【０１３６】
さらに、式（１９ａ）乃至（１９ｇ）において、π，λ，ξは次式（２２）で定義される。
【０１３７】
【数２３】
2010147826.tif 000025
【０１３８】
式（１９ａ）乃至（１９ｇ）に示すように、ネットワークモデルとしてホースモデルを仮定する場合、割合ｋmpqの算出において、トラヒック需要ｄpqの代わりに、トラヒックの総量αp，βqが用いられる。従って、トラヒック量割合入力部５１には、トラヒック需要ｄpqではなく、トラヒックの総量αpおよびβqが入力されることになる。
【０１３９】
トラヒック需要ｄpqは、発着ノードペア数、即ちノード２１の数の二乗個存在するが、トラヒックの総量αp，βqは、それぞれ、発ノード，着ノードの数、即ちノード２１の数だけ存在する。従って、ネットワークモデルとしてホースモデルを仮定する場合、パイプモデルを仮定する場合に比べて、トラヒック量割合入力部５１に入力するパラメータの数は少なくて済む。但し、経路制御の性能は少し低下する。
【０１４０】
なお、上述した説明では、ノード２１間の経路は分散しないものとし、Ｆpmijの値は１または０であるようにしたが、ノード２１間の経路は分散してもよい。
【０１４１】
また、ネットワーク１２内の全てのノード２１がFTPRでトラヒックを分散させて転送する必要はない。ネットワーク１２内にFTPRでトラヒックを分散させて転送しないノード２１がある場合、そのノード２１をノード２１−ｐ´として、次の条件式（２３）を上述した式（１６ａ）乃至（１６ｆ）、式（１８ａ）乃至（１８ｆ）、または式（１９ａ）乃至（１９ｇ）に加えることで、割合ｋmpqを算出することができる。
【０１４２】
【数２４】
2010147826.tif 000026
【０１４３】
さらに、ネットワーク１２内のノード２１ごとに、式（１６ａ）乃至（１６ｆ）を用いて割合ｋmpqを算出するか、式（１８ａ）乃至（１８ｆ）を用いて割合ｋmpqを算出するかを決定してもよい。
【０１４４】
なお、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０１４５】
また、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０１４６】
【図１】TPRの動作について説明する図である。
【図２】本発明を適用したネットワークシステムの一実施の形態の構成例を示す図である。
【図３】図２のネットワークシステムにおけるトラヒックの分散について説明する図である。
【図４】図２のトラヒック割合算出装置の詳細構成例を示すブロック図である。
【図５】図４のトラヒック量割合算出装置による割合算出処理について説明するフローチャートである。
【図６】図２のトラヒック分散部の詳細構成例を示す図である。
【図７】図６のトラヒック分散部によるトラヒック分散処理について説明するフローチャートである。
【図８】サンプルネットワークの構成を示す図である。
【図９】サンプルネットワークの構成をまとめた表を示す図である。
【図１０】実験結果を示す図である。
【符号の説明】
【０１４７】
１１  トラヒック量割合算出装置，  １２  ネットワーク，  ２０−１乃至２０−５  リンク，  ２１−１乃至２１−４  ノード，  ２２−１乃至２２−４  トラヒック分散部，  ５５  次ノード決定部，  ５６  スイッチ部
【図１】
2010147826.tif 000027
【図２】
2010147826.tif 000028
【図３】
2010147826.tif 000029
【図４】
2010147826.tif 000030
【図５】
2010147826.tif 000031
【図６】
2010147826.tif 000032
【図７】
2010147826.tif 000033
【図８】
2010147826.tif 000034
【図９】
2010147826.tif 000035
【図１０】
2010147826.tif 000036