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

制御装置および制御方法、ノードおよび送信方法 新技術説明会

国内特許コード P10P006922
掲載日 2010年7月9日
出願番号 特願2008-323060
公開番号 特開2010-147826
登録番号 特許第5376571号
出願日 平成20年12月19日(2008.12.19)
公開日 平成22年7月1日(2010.7.1)
登録日 平成25年10月4日(2013.10.4)
発明者
  • 大木 英司
出願人
  • 国立大学法人電気通信大学
発明の名称 制御装置および制御方法、ノードおよび送信方法 新技術説明会
発明の概要

【課題】トラヒックを効果的に分散させ、ネットワークの使用効率を向上させる。
【解決手段】ネットワーク12は、複数のノード21がリンク20を介して接続されることにより構成され、発ノード21に入力されたトラヒックを、中間ノード21を介して着ノード21に送信する。トラヒック量割合算出装置11は、ネットワークの構成、および、リンク20の使用可能な帯域の容量に基づいて、発ノード21と着ノード21の組み合わせごとに、各ノード21を中間ノードとしてトラヒックを分散させる割合を算出する。本発明は、例えば、ノードを制御する装置に適用することができる。
【選択図】図2

従来技術、競合技術の概要


ネットワークにおいては、適切な経路制御方式を採用することにより、リソースの使用効率を向上させ、スループットを増加させることができる(例えば、非特許文献1参照)。即ち、適切な経路制御方式では、トラヒックを最適に各経路に割り当て、より多くのトラヒックをネットワークに収容させることができる。また、適切な経路制御方式では、ネットワークの輻輳を抑制したり、トラヒック変動への耐久性を増加させたりすることができる。



経路制御の効果を向上させる1つの方法としては、ネットワークの全てのリンクの使用率の最大値(以下、ネットワーク輻輳率という)を最小化することが挙げられる。ネットワーク輻輳率を最小化することにより、ネットワークに収容可能なトラヒックを増加させることができる。



ところで、経路制御に関しては、様々な研究が行われている。その結果、例えば、非特許文献2では、一般的なトラヒックエンジニアリングの問題、即ちトラヒック需要が、発着ノード間で自由に経路を選択および分散できる問題として定式化されている。



また、非特許文献3には、精巧な経路制御は、例えば、MPLS-TE(Multi-Protocol Label Switching Traffic-Engineering)技術を用いて達成可能であることが記載されている。



しかしながら、既に構築されているネットワークでは、主に、OSPF(Open Shortest Path First)やIS-IS(Intermediate System to Intermediate System)のような最短経路ベースのルーチングプロトコルが採用されている。従って、既に導入されているIP(Internet Protocol)ルータなどのノードがMPLS-TEを採用するためには、ノードのアップグレードが必要となってしまう。そのため、可能な限り既存のルーチングプロトコルを有効利用することが必要であると考えられる。



そこで、非特許文献4乃至6に記載されているように、OSPFベースでネットワークのリンクの重みを最適化する経路制御方式が研究されている。この経路制御方式では、最短経路計算にあたって、リンクの重みがリンクの距離として計算される。また、トラヒック需要が変化すると、最適なリンクの重みが再計算され、再計算されたリンクの重みが、ネットワーク上のノードに再設定される。そして、最新のリンクの重みにしたがって、経路が再計算される。従って、経路が頻繁に変化すると、ネットワーク上の経路の不安定性を招き、これは、パケットロスやループを生じさせる原因となる。



また、トラヒックを分散させ、ネットワークの利用効率を向上させる分散経路制御方式も研究されている。例えば、非特許文献7では、TPR(two-phase routing) over shortest pathsが提案されている。TPRでは、発ノードから送出されたトラヒックのフローは、ネットワーク上の中間ノードへ分散され、中間ノードから着ノードへ向かう。TPRでは、分散させる経路数を増加させることができ、これにより、ネットワーク輻輳率を削減することができる。



なお、非特許文献7に記載されているTPRでは、発ノードから中間ノードまでの経路選択、および、中間ノードから着ノードまでの経路選択は、既存のルーチングプロトコルを使用するという制限が設けられている。これに対して、非特許文献8に記載されているTPRでは、既存のルーチングプロトコルを使用するという制限は設けられていない。



以下に、TPRの動作について説明するが、その前に、TPRを採用するネットワークモデルを以下のように定義する。



ネットワークは有効グラフ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}と表す。



また、ネットワーク輻輳率はrと表す。なお、現在のトラヒックに対して、1/rを乗じたトラヒックまで、ネットワークは受付可能であり、ネットワーク輻輳率rを最小化することは、受付可能なトラヒックを最大化することになる。従って、分散経路制御の目的関数の1つは、ネットワーク輻輳率rの最小化である。



さらに、非特許文献7および8に記載されているTPRでは、ネットワークモデルとしてT={dpq}が既知または推定可能なホースモデルが仮定されているため、ここでも同様の仮定を行う。そこで、αpを、ノードpからネットワークに送出するトラヒックの総量と定義する。従って、式【数1】が成り立つ。この式は、ホースモデルにおけるノードpの制約条件を表す。



また、βqを、ネットワークからノードqに流入するトラヒックの総量と定義する。従って、式【数2】が成り立つ。この式は、ホースモデルにおけるノードqの制約条件を表す。



なお、ネットワークモデルとしては、αp、βqが既知または推定可能なホースモデルが仮定されてもよい。



次に、以上のようにネットワークモデルが定義された場合のTPRの動作について説明する。



TPRでは、トラヒックは、ノードpからノードqに直接転送されず、中間ノードm∈Vに、トラヒックが分散される。そして、全ての発着ノードペア(p,q)に対して、dpqのフローは、中間ノードm∈Vに、kmの割合で分散される。ここで、割合kmについては、0≦km≦1、かつ、【数3】が成立する。中間ノードmに分散されたトラヒックは、着ノードqに転送される。



例えば、発ノードがノード1であり、着ノードがノード3である場合、図1に示すように、発ノードであるノード1から着ノードであるノード3へのトラヒックは、中間ノードとしてのノード2、ノード3、ノード4に、それぞれ、k2,k3,k4の割合で分散される。



従って、発ノードであるノード1から、中間ノードであるノード2を介して、着ノードであるノード3に分散されるトラヒックの割合は、k2となる。発ノードであるノード1から、中間ノードおよび着ノードであるノード3に分散されるトラヒックの割合は、k3となる。発ノードであるノード1から、中間ノードであるノード4を介して、着ノードであるノード3に分散されるトラヒックの割合は、k4となる。



また、発ノードがノード1であり、着ノードがノード2である場合も、図1に示すように、発ノードであるノード1から着ノードであるノード2へのトラヒックは、中間ノードとしてのノード2、ノード3、ノード4に、それぞれ、k2,k3,k4の割合で分散される。



従って、発ノードであるノード1から、中間ノードおよび着ノードであるノード2に分散されるトラヒックの割合は、k2となる。発ノードであるノード1から、中間ノードであるノード3を介して、着ノードであるノード2に分散されるトラヒックの割合は、k3となる。発ノードであるノード1から、中間ノードであるノード4を介して、着ノードであるノード2に分散されるトラヒックの割合はk4となる。



即ち、TPRでは、発着ノードペア(p,q)によらず、割合k2,k3,k4で、中間ノードとしてのノード2、ノード3、ノード4にトラヒックが分散される。



なお、ノードpから中間ノードmまでの経路選択、および、中間ノードmからノードqまでの経路選択の方式としては、例えば最短経路方式が用いられる。これは、ノードpと中間ノードmの間に、IP-in-IPやGRE(Generic Routing Encapsulation)トンネルを設定することで実現できる。



次に、TPRにおいてネットワーク輻輳率rを最小化するための割合kmの算出方法について説明する。



まず、ノードpから、中間ノードmを介して、ノードqへ転送されるトラヒックを考える。ここで、ノードpと中間ノードmの間のトラヒックをbpmで表すと、ノードpとノードmの間のトラヒックは、2つのコンポーネントから構成される。1つ目のコンポーネントは、ノードpを発ノードとし、中間ノードmを中間ノードとして分散されるトラヒックであり、2つ目のコンポーネントは、ノードpを中間ノードとし、中間ノードmを着ノードとして転送されるトラヒックである。



従って、1つ目のコンポーネントとしてのトラヒックをbpm(1)と定義し、2つ目のコンポーネントとしてのトラヒックをbpm(2)と定義すると、トラヒックbpmは、以下の式(1)で表される。



pm=bpm(1)+pm(2)
・・・(1)



また、上述したホースモデルにおけるノードpの制約条件を用いると、トラヒックbpm(1)は以下の式(2)で与えられ、トラヒックbpm(2)は以下の式(3)で与えられる。



【数4】【数5】



従って、トラヒックbpmは、トラヒックの総量αp,βqを用いた以下の式(4)で表される。



pm=kmαp+pβm
・・・(4)



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



【数6】



但し、ψmijは、次式(6)で定義される。



【数7】



また、ノードjに流入するトラヒックとノードjから流出するトラヒックの差は、次式(7)で与えられる。



【数8】



但し、ωmjは、次式(8)で定義される。



【数9】



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



【数10】



なお、式(9a)は、ネットワーク輻輳率rを最小化する目的関数を示している。式(9b)は、ネットワークのノードに関して、割合kmのすべての和が1であることを示している。式(9c)は、全てのリンクにおいて、リンクlink(i,j)を通過するトラヒックの総和がcij×r以下であることを示している。式(9d)は、フロー保存則を示している。



以上のようにして定式化された式(9a)乃至(9f)を解くことにより、TPRにおいてネットワーク輻輳率rを最小化するための割合kmが算出される。なお、式(9a)乃至(9f)は、線形計画問題(LP(Linear Programming))であるため、標準のLPソルバ(solver)で解くことができる。



【非特許文献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

産業上の利用分野


本発明は、制御装置および制御方法、ノードおよび送信方法に関し、特に、トラヒックを効果的に分散させ、ネットワークの使用効率を向上させることができるようにした制御装置および制御方法、ノードおよび送信方法に関する。

特許請求の範囲 【請求項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)によって、入力されたトラヒックを、前記ネットワーク内の複数のノードのうちの所定の中間ノードを介して、前記ネットワーク内の着ノードに送信するノードの送信方法において、
入力されたパケットから前記着ノードを特定する情報を認識する着ノード認識ステップと、
前記トラヒックが入力される発ノードとしての前記ノードと前記着ノードの組み合わせごとに求められた、前記ネットワーク内の各ノードを前記中間ノードとして前記トラヒックを分散させる割合に基づいて、前記トラヒックを送信する中間ノードを決定する決定ステップと、
前記決定ステップの処理により決定された前記中間ノードの情報を前記パケットに付加し、前記中間ノードの情報が付加された前記パケット前記中間ノードに送信する送信ステップと
を含む送信方法。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2008323060thum.jpg
出願権利状態 登録
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください


PAGE TOP

close
close
close
close
close
close
close