(57)【特許請求の範囲】
【請求項１】
ネットワークを構成するノードにおいて、輻輳を回避するために、受信したパケットを次にどのノードへ配送するかを決定する経路制御装置であって、
前記ネットワークのネットワークトポロジおよび前記ネットワークを構成するノード間のリンクに割当てたコストを示すリンクコストを記憶している記憶部と、
受信したパケットの宛先ノードを読出し、前記宛先ノードが隣接ノードか否かを判定する宛先ノード読出部と、
前記宛先ノード読出部によって前記宛先ノードが隣接ノードでないと判定された場合、前記ネットワークトポロジおよび前記リンクコストを用いて、前記宛先ノードに至る経路上のリンクのリンクコストの合計が最小となる最小コスト経路を抽出し、前記抽出した最小コスト経路の総数に対する、次にパケットを配送するノードから前記宛先ノードに至る経路の最小コスト経路数の割合を示すパケット配送確率を算出するとともに、前記パケット配送確率の重みを示すパラメータを、輻輳状態と非輻輳状態との境界点において極値を持つ評価関数の変数に用いて、前記評価関数が前記極値を持つときの前記パラメータの値を算出し、そのパラメータの値を重みとして前記パケット配送確率を補正するパケット配送確率行列演算部と、
前記宛先ノード読出部によって前記宛先ノードが隣接ノードであると判定された場合、次に配送するノードを前記宛先ノードに決定し、前記宛先ノード読出部によって前記宛先ノードが隣接ノードでないと判定された場合、乱数を０から１の範囲で発生させ、隣接ノードのパケット配送確率を順番に加算していき、ある隣接ノードで発生した乱数より大きくなったとき、その隣接ノードを次に配送するノードとして決定する配送先決定部と、
前記配送先決定部によって決定された前記次に配送するノードを宛先としてパケットを配送するパケット配送部と
を備えることを特徴とする経路制御装置。
【請求項２】
ネットワークを構成するノードにおいて、輻輳を回避するために、受信したパケットを次にどのノードへ配送するかを決定する経路制御装置において用いられる経路制御方法であって、
前記経路制御装置は、
前記ネットワークのネットワークトポロジおよび前記ネットワークを構成するノード間のリンクに割当てたコストを示すリンクコストを記憶している記憶部と、処理部とを備え、
前記処理部は、
受信したパケットの宛先ノードを読出し、前記宛先ノードが隣接ノードか否かを判定する宛先ノード読出ステップと、
前記宛先ノード読出ステップによって前記宛先ノードが隣接ノードでないと判定された場合、前記ネットワークトポロジおよび前記リンクコストを用いて、前記宛先ノードに至る経路上のリンクのリンクコストの合計が最小となる最小コスト経路を抽出し、前記抽出した最小コスト経路の総数に対する、次にパケットを配送するノードから前記宛先ノードに至る経路の最小コスト経路数の割合を示すパケット配送確率を算出するとともに、前記パケット配送確率の重みを示すパラメータを、輻輳状態と非輻輳状態との境界点において極値を持つ評価関数の変数に用いて、前記評価関数が前記極値を持つときの前記パラメータの値を算出し、そのパラメータの値を重みとして前記パケット配送確率を補正するパケット配送確率行列演算ステップと、
前記宛先ノード読出ステップによって前記宛先ノードが隣接ノードであると判定された場合、次に配送するノードを前記宛先ノードに決定し、前記宛先ノード読出ステップによって前記宛先ノードが隣接ノードでないと判定された場合、乱数を０から１の範囲で発生させ、隣接ノードのパケット配送確率を順番に加算していき、ある隣接ノードで発生した乱数より大きくなったとき、その隣接ノードを次に配送するノードとして決定する配送先決定ステップと、
前記配送先決定ステップによって決定された前記次に配送するノードを宛先としてパケットを配送するパケット配送ステップと
を実行することを特徴とする経路制御方法。
【請求項３】
請求項２に記載の経路制御方法を、コンピュータである前記経路制御装置に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークにおけるパケットの経路制御技術に関する。
【背景技術】
【０００２】
通信ネットワークは、ノードおよびリンクによって構成され、ネットワークに配置されるルータ等のノードには、ＰＣ（Personal Computer）等の端末が接続される。ノードは、そのノードにおいて発生したパケットや他のノードから転送されてきたパケットを蓄積し、リンクで繋がっているノードへ転送する、中継機能を持つ。なお、発生したとは、そのノードに接続されている端末からパケットを受信することを意味している。任意のノードにおいて発生したパケットは、宛先ノードが定められており、リンクを伝達して宛先ノードまで配送される。そして、ノードは、複数の隣接ノード（リンク）を持つ場合、どの隣接ノードにパケットを伝達するかを決定する。これを経路制御という。
【０００３】
インターネットでは、通常、パケットの伝達経路の途中に存在するノードを中継ノードと呼び、その中継ノードにおいて、次のノードまでの経路を決定するホップバイホップルーティングを用いて経路制御が行われる。具体的には、各中継ノードは、パケットの目的地となる宛先ノードとその宛先ノードに至る経路とが書き込まれた経路表を備え、受信したパケットの宛先ノードに基づいて、次に経由すべき隣接ノードを決定する。各ノードは、ネットワーク状況に関する情報を交換し合って、必要に応じて経路表を更新する。ネットワーク状況に関する情報を交換し合う方法としては、各ノードがノードの接続情報およびノード間の接続情報を交換するＯＳＰＦ(Open Shortest Path First)が一般的である。なお、例えば、各ノードの接続情報とはネットワークトポロジやリンクコストのことである。リンクコストは、リンクに割当てたコストであり、一般的に、コストが小さいほどそのリンクが選ばれやすくなっている。そして、これらの交換した情報から、経路を構成するリンクのリンクコストの合計を示す合計コストを最小にする経路表を作成する代表的な方法がダイクストラ法（Dijkstra's algorithm）である（非特許文献１、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】「コンピュータネットワーク」、宮原秀夫、尾家祐二、共立出版社 (1999)
【非特許文献２】「Data Networks (2nd Edition)」、D.Bertsekas、R.Gallager、Prentice-Hall (1992)
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ダイクストラ法は、合計コストが最小となる経路（以降、最小コスト経路と称す。）を計算し、その最小コスト経路に基づいてパケットを配送するものである。そして、発生したパケット数が限りなく０に近い場合には、このダイクストラ法は、最適となる。しかし、発生したパケット数が増大して、その最小コスト経路上のノードに輻輳が発生した場合、その輻輳が発生したノードを避けた経路を再計算し、その再計算した経路に基づいてパケットを配送するようにしなければならない。このように輻輳が発生した場合、従来技術では、一部のパケットを最小コスト経路とは異なる経路を用いて、輻輳が発生したノードを迂回するように配送し、輻輳を回避することが考えられてきた。しかしながら、どれくらいの量のパケットを迂回させれば輻輳が回避できるのかといった問題、および迂回先のノードにおいてパケットが輻輳しないようにするにはどのようにするかといった問題を解決し、輻輳を回避するためのネットワーク全体の経路制御については、未検討である。
【０００６】
そこで、本発明は、輻輳を回避するためのネットワーク全体の経路制御を行う技術を提供することを課題とする。
【課題を解決するための手段】
【０００７】
本発明は、ネットワークを構成するノードにおいて、輻輳を回避するために、受信したパケットを次にどのノードへ配送するかを決定する経路制御装置であって、前記ネットワークのネットワークトポロジおよび前記ネットワークを構成するノード間のリンクに割当てたコストを示すリンクコストを記憶している記憶部と、受信したパケットの宛先ノードを読出し、前記宛先ノードが隣接ノードか否かを判定する宛先ノード読出部と、前記宛先ノード読出部によって前記宛先ノードが隣接ノードでないと判定された場合、前記ネットワークトポロジおよび前記リンクコストを用いて、前記宛先ノードに至る経路上のリンクのリンクコストの合計が最小となる最小コスト経路を抽出し、前記抽出した最小コスト経路の総数に対する、次にパケットを配送するノードから前記宛先ノードに至る経路の最小コスト経路数の割合を示すパケット配送確率を算出するとともに、前記パケット配送確率の重みを示すパラメータを、輻輳状態と非輻輳状態との境界点において極値を持つ評価関数の変数に用いて、前記評価関数が前記極値を持つときの前記パラメータの値を算出し、そのパラメータの値を重みとして前記パケット配送確率を補正するパケット配送確率行列演算部と、前記宛先ノード読出部によって前記宛先ノードが隣接ノードであると判定された場合、次に配送するノードを前記宛先ノードに決定し、前記宛先ノード読出部によって前記宛先ノードが隣接ノードでないと判定された場合、乱数を０から１の範囲で発生させ、隣接ノードのパケット配送確率を順番に加算していき、ある隣接ノードで発生した乱数より大きくなったとき、その隣接ノードを次に配送するノードとして決定する配送先決定部と、前記配送先決定部によって決定された前記次に配送するノードを宛先としてパケットを配送するパケット配送部とを備えることを特徴とする。
【０００８】
また、本発明は、ネットワークを構成するノードにおいて、輻輳を回避するために、受信したパケットを次にどのノードへ配送するかを決定する経路制御装置において用いられる経路制御方法であって、前記経路制御装置が、前記ネットワークのネットワークトポロジおよび前記ネットワークを構成するノード間のリンクに割当てたコストを示すリンクコストを記憶している記憶部と、処理部とを備え、前記処理部が、受信したパケットの宛先ノードを読出し、前記宛先ノードが隣接ノードか否かを判定する宛先ノード読出ステップと、前記宛先ノード読出ステップによって前記宛先ノードが隣接ノードでないと判定された場合、前記ネットワークトポロジおよび前記リンクコストを用いて、前記宛先ノードに至る経路上のリンクのリンクコストの合計が最小となる最小コスト経路を抽出し、前記抽出した最小コスト経路の総数に対する、次にパケットを配送するノードから前記宛先ノードに至る経路の最小コスト経路数の割合を示すパケット配送確率を算出するとともに、前記パケット配送確率の重みを示すパラメータを、輻輳状態と非輻輳状態との境界点において極値を持つ評価関数の変数に用いて、前記評価関数が前記極値を持つときの前記パラメータの値を算出し、そのパラメータの値を重みとして前記パケット配送確率を補正するパケット配送確率行列演算ステップと、前記宛先ノード読出ステップによって前記宛先ノードが隣接ノードであると判定された場合、次に配送するノードを前記宛先ノードに決定し、前記宛先ノード読出ステップによって前記宛先ノードが隣接ノードでないと判定された場合、乱数を０から１の範囲で発生させ、隣接ノードのパケット配送確率を順番に加算していき、ある隣接ノードで発生した乱数より大きくなったとき、その隣接ノードを次に配送するノードとして決定する配送先決定ステップと、前記配送先決定ステップによって決定された前記次に配送するノードを宛先としてパケットを配送するパケット配送ステップとを実行することを特徴とする。
【０００９】
このような構成によれば、経路制御装置は、宛先ノードに至る最小コスト経路の数を用いて算出したパケット配送確率に対して、そのパケット配送確率の重みを表すパラメータを、輻輳状態と非輻輳状態との境界点において極値を持つ評価関数の変数として、前記評価関数が前記極値を持つときの前記パラメータの値を算出し、そのパラメータの値を重みとして前記パケット配送確率を補正する。このように、重みによって補正したパケット配送確率（以降、重み付きパケット配送確率と称す。）を用いることによって、輻輳状態と非輻輳状態との境界点において、輻輳を回避するためのネットワーク全体の経路制御を行うことができる。
【００１０】
また、本発明は、前記経路制御方法を、コンピュータである前記経路制御装置に実行させるためのプログラムとした。このようなプログラムをインストールされたコンピュータは、このプログラムに基づいた機能を実現することができる。
【発明の効果】
【００１１】
本発明によれば、輻輳を回避するためのネットワーク全体の経路制御を行う技術を提供することができる。
【図面の簡単な説明】
【００１２】
【図１】本実施形態におけるネットワーク構成例を示す図である。
【図２】経路制御装置の構成例を示す図である。
【図３】経路制御装置の処理フローの例を示す図である。
【図４】パケット配送確率行列演算部における評価関数が極値となるパラメータｒを算出する処理フローの例を示す図である。
【図５】パケット配送確率行列演算部における最短コスト経路制御に基づくパケット配送確率行列を算出する処理フローの例を示す図である。
【図６】変形例２におけるネットワーク構成例を示す図である。
【図７】変形例２における経路制御装置の構成例を示す図である。
【図８】変形例２における配送先取得装置の構成例を示す図である。
【発明を実施するための形態】
【００１３】
本発明を実施するための形態（以降、「本実施形態」と称す。）について、適宜図面を参照しながら詳細に説明する。
【００１４】
本実施形態におけるネットワーク構成例について、図１を用いて説明する。図１に示すように、ネットワーク２０は、ルータ等のノード１０（１０Ａ，１０Ｂ，１０Ｃ，１０Ｄ，１０Ｅ，１０Ｆ）と各ノード１０間のリンクとによって構成されている。ＰＣ等の端末３０は、いずれかのノード１０に接続される。図１では、端末３０Ａはノード１０Ｂに接続され、端末３０Ｂはノード１０Ｅに接続されている。各ノード１０は、それぞれ経路制御装置１１を備えている。経路制御装置１１は、どの隣接ノードにパケットを配送するかについて、所定の演算に基づいて決定する。そして、ノード１０は、端末３０から受信したパケット（以降、発生したパケットと称す。）や、他のノード１０から到着したパケットを、経路制御装置１１によって決定した隣接ノードに配送する。
【００１５】
（経路制御装置の構成）
次に、経路制御装置１１の構成例について、図２を用いて説明する。図２に示すように、経路制御装置１１は処理部１２、記憶部１３、通信部１４を備える。処理部１２は、図示しないＣＰＵ（Central Processing Unit）およびメインメモリによって構成され、記憶部１３に記憶されているアプリケーションプログラムをメインメモリに展開して、後記するパケット取得部１２１、宛先ノード読出部１２２、パケット配送確率行列演算部１２３、配送先決定部１２４、およびパケット配送部１２５を具現化する。
【００１６】
パケット取得部１２１は、後記する記憶部１３のバッファ１３１に一時的に蓄積されたパケットの中から、最も古くに到着していたパケットを取得する。
宛先ノード読出部１２２は、パケット取得部１２１によって取得したパケットの宛先ノードを読出す。
パケット配送確率行列演算部１２３は、どの隣接ノードに配送するかを決定するために、後記するパケット配送確率を演算し、パケット配送確率行列を生成する。
配送先決定部１２４は、隣接ノードごとに図示しない乱数発生手段に乱数（０〜１）を発生させ、その乱数とパケット配送確率行列のパケット配送確率とを比較して、パケットを配送する隣接ノードを確率的に決定する。例えば、乱数を０から１の範囲で発生させ、隣接ノードのパケット配送確率を順番に加算していき、ある隣接ノードで発生した乱数より大きくなったとき、その隣接ノードを、次にパケットを配送するノードとして決定する。
パケット配送部１２５は、配送先決定部１２４によって決定された隣接ノードを宛先としてパケットを配送する。
【００１７】
記憶部１３は、ネットワークトポロジ１３２、キュー長１３３、リンクコスト１３４、および配送確率行列１３５を記憶し、バッファ１３１を備えている。
バッファ１３１は、宛先ノードに辿り着く途中のパケットや、発生したパケットを一時的に蓄積する。新しく蓄積するパケットは、既に蓄積されているパケットの最後尾に追加される。そして、パケット取得部１２１によって、最も古くに蓄積されているパケットから読み出される。
ネットワークトポロジ１３２は、各ノード１０の接続形態に関する情報である。例えば、図１では、ノード１０Ａが、ノード１０Ｂ，１０Ｄ，１０Ｅ，１０Ｆと接続されているという情報である。
キュー長１３３は、バッファ１３１で配送を待っているパケットのことをキューと呼び、そのキューの数をキュー長として表したものである。
リンクコスト１３４は、ノード１０間のリンクに割当てたコストのことである
配送確率行列１３５は、他のノード１０において算出されたパケット配送確率を記憶している。これは、パケット配送確率は、自身のノードと隣接ノードとに関係するものしか演算できないので、他のノード１０のパケット配送確率については、他のノード１０から受信する必要があるからである。
【００１８】
通信部１４は、隣接ノードと通信を行うためのインタフェースあり、パケットの送受信制御を行う。
【００１９】
（経路制御装置の処理フロー）
次に、経路制御装置１１の処理フローの例について、図３を用いて説明する（適宜、図２参照）。
ステップＳ３０１では、パケット取得部１２１が、バッファ１３１から、キューの先頭の（最も古くに蓄積された）パケットを取得する。
ステップＳ３０２では、宛先ノード読出部１２２が、パケット取得部１２１によって取得したパケットの宛先ノードを読出す。
ステップＳ３０３では、宛先ノード読出部１２２が、宛先ノードが隣接ノードであるか否かを判定する。宛先ノードが隣接ノードでない場合（ステップＳ３０３でＮｏ）、処理はステップＳ３０４へ進む。また、宛先ノードが隣接ノードである場合（ステップＳ３０３でＹｅｓ）、処理はステップＳ３０６へ進む。
【００２０】
ステップＳ３０４では、パケット配送確率行列演算部１２３が、パケット配送確率を演算し、パケット配送確率行列を生成する。このパケット配送確率の演算の詳細については、後記する。
ステップＳ３０５では、配送先決定部１２４が、乱数を発生させ、その乱数とパケット配送確率行列から算出されるパケット配送確率とに基づいて、配送先（配送する隣接ノード）を確率的に決定する。そして、処理は、ステップＳ３０７へ進む。
ステップＳ３０６では、配送先決定部１２４が、隣接ノードを配送先に設定する。
ステップＳ３０７では、パケット配送部１２５が、ステップＳ３０５またはステップＳ３０６において決定した配送先へ、パケットを配送する。そして、処理は、ステップＳ３０１へ進む。
【００２１】
（パケット配送確率の算出）
次に、パケット配送確率の算出例について、以下に説明する。
まず、パケット配送確率行列を生成するときの前提条件（ａ）〜（ｅ）を示す。
（ａ）パケットは、各ノード１０において任意の時間に生成される。
（ｂ）パケットは、そのパケットが発生したノードにおいて、その目的に応じて宛先ノードが決められる。
（ｃ）パケットの宛先ノードは、パケットのヘッダ部分等、パケット内部に記述されている。
（ｄ）宛先ノードは、必ずパケットが発生したノード以外のノードである。
（ｅ）１つのノードにおいて、同時に複数のパケットが発生することがある。
【００２２】
（パケット配送確率行列とパケット到着率）
次に、パケット配送確率行列とパケット到着率について説明する。図３のステップＳ３０５に示したように、パケットを次にどのノードへ配送するかは、パケット配送確率と乱数とに基づいて確率的に決められる。ここで、パケット配送確率行列Ｐの行列要素であるパケット配送確率をｐijと表記する。パケット配送確率ｐijは、いまノードｉにあるパケットが次に隣接ノードｊへ配送される確率を表す。そして、パケット配送確率行列Ｐは、すべてのｉおよびｊの組についてパケット配送確率ｐijを２次元配列状に並べたものとなる。このようなパケット配送確率行列Ｐに基づく経路制御は、これまで辿ってきた過去の経路の記憶に因らずマルコフ性に基づいた制御となる。ここで、本実施形態では、パケット配送確率ｐijが、比較的少数の変数ｒでパラメータ化されている場合を考える。すなわち、パケット配送確率ｐijの値が、あるポリシに基づいて決められるようにするために、パラメータｒを導入する。なお、ポリシを、パラメータｒを変数とする評価関数によって表現する。例えば、そのポリシとは、ネットワーク内のパケット数を最小化することによって輻輳を回避する、または、輻輳状態に陥るパケットの発生数を最大化する、といったものである。評価関数の具体例は、ネットワーク内のパケット数を最小化するための関数、または、輻輳状態に陥るパケットの発生数を最大化するための関数である。これらの評価関数は、その値が極値となるときに、輻輳状態と非輻輳状態との境界点を表すような関数とする。また、前記した評価関数では、ノードにおける輻輳状態を示すパケット到着率（後記）を変数として用いる。このパケット到着率は、パラメータｒを変数として表現され、輻輳状態の判定のために重要となる。例えば、パケット到着率が大きい場合には、輻輳状態が発生しやすくなると考えられる。そこで、パラメータｒによって決定されるパケット配送確率行列とパケット到着率について、以下に説明する。
【００２３】
パケット配送確率ｐijは、式（１）のように表される。なお、以降、数式中の文字の上部に矢印（→）を付した文字は、ベクトルを表している。ただし、文中では、→を省略して記載する。
【数１】
0005361001.tif 000002
【００２４】
ここで、ノードｊへの平均パケット到着率ｂjは、ノードｊで単位時間当りに発生したパケットの数（パケット発生率）λと、単位時間当りに隣接ノードｉから転送されてきたパケット数ｂiｐijとの和になり、式（２）で表される。
【数２】
0005361001.tif 000003
【００２５】
式（２）を、ｅ＝(1,1,…,1)ｔ（ただし、行列要素１の数がｎ個）、b=(b1, b2, …, bn)ｔ、ｒ=(r1, r2, …, rn)ｔ、[Ｐ(ｒ)]ij=ｐij(ｒ)を用いて、行列で表現すると式（３）で表せる。なお、上付きｔは転置を表す。
【数３】
0005361001.tif 000004
【００２６】
したがって、式（３）を解くことにより、平均パケット到着率ｂ（パラメータｒの関数）は式（４）となる。
【数４】
0005361001.tif 000005
ただし、式（４）中のＩは単位行列を示す。
【００２７】
ここで、最短経路制御等のように、各パケットの宛先ノードｋによってパケット配送確率が異なる場合のパケット配送確率を
【数５】
0005361001.tif 000006
のように表す。
【００２８】
この場合、宛先ノードｋの平均パケット到着率ｂkは、宛先ノードが自分のノード以外でランダムに選ばれるとすると、式（５）のように表される。
【数６】
0005361001.tif 000007
ただし、ｅkは、(1,…,1,0,1,…,1)ｔ、つまり、ｋ番目の要素だけ０であとはすべて１のベクトルのことである。また、Ｎは、ノード数である。
【００２９】
したがって、全宛先ノードに関する平均パケット到着率ｂ(ｒ)は、式（６）として求まる。
【数７】
0005361001.tif 000008
【００３０】
（パラメータｒの決定）
ここで、パラメータｒの決定方法について説明する。まず、パケットの配送に関して、以下の２事案をポリシの例として説明する。
（事案Ａ）ネットワーク内のパケット数を最小化すること
（事案Ｂ）輻輳状態に陥るパケット発生数を最大化すること
【００３１】
（（事案Ａ）ネットワーク内のパケット数を最小化するケース）
Littleの法則によれば、ネットワーク内のパケット数はパケットの平均配送時間（パケットが発生したノードから宛先ノードに配送されるのに掛かる時間の平均値）に比例する。したがって、ネットワーク内のパケット数を減少させれば、目的地となる宛先ノードに至るまでに要する時間を減少させられることになる。
あるノードｉでバッファ１３１に溜ったパケット数ｑiは、待ち行列理論より、式（７）で表せる。
【数８】
0005361001.tif 000009
【００３２】
ただし、μは、ノードｉが単位時間当りに転送する平均パケット数、転送レート、または待ち行列理論でいうところの、サービスレートである。
したがって、全パケット数Ｎ（ｒ）は、ｑiの合計なので、式（８）で表せる。つまり、式（８）が前記した評価関数である。
【数９】
0005361001.tif 000010
【００３３】
そこで、ネットワーク内のパケット数Ｎ（ｒ）を最小化するケースでは、Ｎ（ｒ）が極値となるときのパラメータｒmの値は、式（９）として定式化される。
【数１０】
0005361001.tif 000011
つまり、Ｎ（ｒ）が最小となるパラメータｒが、ネットワーク内のパケット数を最小化するパケット配送確率のパラメータとなる。
【００３４】
（（事案Ｂ）輻輳状態に陥るパケット発生数を最大化するケース）
次に、事案Ｂの場合について説明する。時刻ｔ＝０でパケットが発生し始め、現在、時刻ｔまでに発生したパケット総数をＧ（ｔ）とすると、<Ｇ（ｔ）>＝λＮｔとなる。ここで、<  >は期待値を表し、λはパケット発生率を表し、Ｎはノード数を表す。また、現在、ネットワーク中に滞在しているパケット数をＭ（ｔ）とすると、過渡期の影響を無視できる充分大きな時間ｔで考えると、Ｍ（ｔ）は、式（１０）で表される。
【数１１】
0005361001.tif 000012
【００３５】
パケット発生率λがある閾値λｃより小さい場合、ネットワーク中のパケット総数はパケット発生率λによって決まる一定値ｆ（λ）となる。この場合、Littleの法則によれば、パケットは有限時間で宛先ノードに到着することになる。そして、この状態は、ネットワークが非輻輳状態にあるという。それに対して、λが閾値λｃ以上の場合、ネットワーク中のパケット総数は一定率ｈ（λ）で時間ｔに比例して増加する。この場合には、パケット到着時間はいくらでも大きくなることになり、この状態は、ネットワークが輻輳状態にあるという。
ここで、ネットワークの輻輳状態を判定する指標として、式（１１）に示すηを用いる。
【数１２】
0005361001.tif 000013
【００３６】
式（１１）では、非輻輳状態の場合にはη＝０となり、輻輳状態の場合にはη＝ｂ（λ）／（λＮ）＞０となるので、ηの値が０か正かを判定することによって、非輻輳状態か輻輳状態かを判別することができる。ここで、非輻輳状態から輻輳状態に転移するλｃを臨界パケット発生率と呼ぶと、すべてのノードｉに対して、式（１２）を満足する場合、式（７），（８）より、ネットワーク内のパケット数はほぼ一定に保たれるので、η＝０となり、非輻輳状態にあると言える。
【数１３】
0005361001.tif 000014
【００３７】
なお、λを徐々に大きくしていったときに、初めて式（１３）を満たすλがλｃであり、当然、λｃもｒの関数である。つまり、式（１３）が前記した評価関数である。
【数１４】
0005361001.tif 000015
【００３８】
この場合、輻輳状態に陥るパケット発生数を最大化するケースでは、λｃを最大にするパラメータｒmの値は、式（１４）として定式化される。
【数１５】
0005361001.tif 000016
【００３９】
つまり、λｃ（ｒ）を最大とするｒが、非輻輳状態から輻輳状態に転移するパケット発生率を最大化するときの、パケット配送確率のパラメータとなる。
【００４０】
以上、前記した事案（Ａ），（Ｂ）で説明した処理フローをまとめて、パケット配送確率行列演算部１２３において、評価関数が極値となるパラメータｒを算出するための処理フローについて、図４を用いて説明する。
ステップＳ４０１では、パケット配送確率を、式（１）のように、パラメータｒの関数で表現する。
ステップＳ４０２では、各ノード１０における平均パケット到着率を算出する。平均パケット到着率は、式（６）で表される。
ステップＳ４０３では、評価関数（変数ｒ）が極値となるパラメータｒを算出する。例えば、パラメータｒは、事案（Ａ）については式（９）、事案（Ｂ）については式（１４）によって算出される。そして、パラメータｒが算出されれば、式（１）で定義したパケット配送確率ｐij（ｒ）を算出することができる。
【００４１】
なお、パラメータｒを算出する方法としては、式（１５）に示すように、事案（Ａ）については式（９）のＮ（ｒ）を微分して極値を算出する。また、事案（Ｂ）については式（１４）のλｃ（ｒ）を微分して極値を算出する。なお、線形計画法、２次計画法、または最急降下法等を用いても構わない。
【数１６】
0005361001.tif 000017
【００４２】
（パケット配送確率行列演算部の処理フロー）
次に、パケット配送確率計算部の処理フローについて以下に説明する。その処理フローにおいて、パケットが次にどのノードへ配送されるかは、パケット配送確率と乱数とによって確率的に決められる。パケット配送確率ｐijkは、いまノードｉにあるパケットの宛先ノードがｋである場合、次に隣接ノードｊへ配送される確率を表している。このようなパケット配送確率ｐijkを行列要素とするパケット配送確率行列を導入することによって、これまで辿ってきた過去の経路の記憶に因らないような経路制御を実現することができる（第１処理）。さらに、第１処理において最短経路制御を可能とするパケット配送確率ｐijkを算出した上で、そのパケット配送確率ｐijkに各ノード毎の配送重みを付加することで、特定のノードのパケット集中を回避することができる（第２処理）。
そこで、まず、第１処理として、最短経路制御を可能とするパケット配送確率行列を算出する処理フローについて説明する。次に、第２処理として、配送重みを考慮したパケット配送確率行列を算出する処理フローについて説明する。
【００４３】
（第１処理）
ここでは、最短経路として、合計コストが最小となる最小コスト経路を用いる。最小コスト経路によってパケットを配送する場合には、パケットの発生したノードＳから宛先ノードまでのリンクコストの合計が最小となるようなノード系列の経路が用いられる。また、宛先ノードまでの最小コスト経路が複数ある場合、それぞれの最小コスト経路は等確率でランダムに選ばれるものとする。つまり、パケット配送確率ｐijkは、隣接ノードｊを通る最小コスト経路の数を宛先ノードｋへの最小コスト経路総数で割ったもので表される。以下に、具体的なパケット配送確率の計算アルゴリズムについて説明する。
【００４４】
まず、あるノードｋを固定する。ノードｋを宛先ノードとした場合、各ノードｉでのパケット配送確率ｐijkを求める。パケット配送確率ｐijkは、ｋは固定であるので、簡略表記して、上付きのｋは省略する。また、アルゴリズムで用いる記号は次の通りである。
Ｖ: 全ノード集合
Ｐ: 最小コストが確定したノード集合
Ｅj: ノードｊから配送されるべきノード集合
Ｎj: ノードｊからの最短コスト経路の数
ｄj: ノードｊからノードｋまでのコストの合計；すなわち、ノードｊからノードｋに至る経路上のノード間のリンクコストｃをすべて加算した値
ｃij: ノードｉからノードｊへのリンクコスト
【００４５】
パケット配送確率行列演算部１２３における、第１処理の処理フローについて、図５を用いて説明する（適宜、図２参照）。
ステップＳ５０１では、パケット配送確率行列演算部１２３は、ネットワークトポロジ１３２およびリンクコスト１３４を記憶部１３から取得する。
ステップＳ５０２では、パケット配送確率行列演算部１２３は、演算用の変数の初期化を、式（１６）のように行う。なお、式（１６）中のバックスラッシュは、除外することを意味する。また、｛Ｓ｝は、経路の起点となるノードＳを含むノード集合を表す。
【数１７】
0005361001.tif 000018
【００４６】
ステップＳ５０３では、パケット配送確率行列演算部１２３は、最小コストが確定したノードを抽出し、そのノードのパケット配送確率を算出する。
具体的には、式（１７）を満足するノード集合Ｑを算出する。
【数１８】
0005361001.tif 000019
【００４７】
式（１７）の右辺は、ｄjが最小になるノードｋを返す関数である。つまり、ノード集合Ｑは、今回最小コストが確定したノード集合となる。そして、ノード集合Ｑに含まれるすべてのノードｊの最小コスト経路数Ｎjと、そのノードｊから配送されるべきノードｌの最小コスト経路数Ｎlについて、式（１８）に示すように、パケット配送確率をｐijを定義する。
【数１９】
0005361001.tif 000020
【００４８】
そして、式（１９）に示すように、現在のノード集合Ｐ（最小コストが確定したノード集合）にノード集合Ｑを加えたものを、新たなノード集合Ｐとする。
【数２０】
0005361001.tif 000021
【００４９】
次に、ステップＳ５０４では、パケット配送確率行列演算部１２３は、最小コストが未確定のノードの仮最小コストを更新し、その仮最小コストを実現する配送先ノードを抽出し、その時の最小コスト経路数を算出する。また、パケット配送確率行列演算部１２３は、算出した最小コスト経路数を式（１８）に適用して、パケット配送確率を算出する。
具体的には、式（２０）に示すように、ノードｊから配送されるべきノード集合Ｅjと、ノードｊからノードｋまでのコストｄjと、ノードｊからの最小コスト経路数Ｎjとを更新する。
【数２１】
0005361001.tif 000022
【００５０】
ステップＳ５０５では、パケット配送確率行列演算部１２３は、最小コストが未確定のノードがあるか否かを判定する。具体的には、Ｐ＝Ｖ（最小コストがすべて確定した）か否かを判定する。最小コストが未確定のノードがある場合（ステップＳ５０５でＹｅｓ）、処理はステップＳ５０３へ戻る。また、最小コストが未確定のノードがない場合（ステップＳ５０５でＮｏ）、ステップＳ５０６では、パケット配送部１２５は、算出したパケット配送確率を、他のノードにおけるパケット配送確率行列の生成のために配送する。
【００５１】
（第２処理）
第２処理では、パケット配送確率行列演算部１２３は、第１処理において算出した最小コスト経路のパケット配送確率に対して、各ノードに配送重みを勘案した、重み付きパケット配送確率を算出する。なお、配送重みは、第１処理において算出した最小コスト経路のパケット配送確率を、前記したポリシによって調整することを意味する。ここで、第１処理において算出した最小コスト経路のパケット配送確率を下記のように表す。なお、（Ｓ）は、最小コスト経路であることを意味している。
【数２２】
0005361001.tif 000023
【００５２】
ここで、ノードｉに割当てる配送重みをｒiとすると、パケット配送確率は、式（２１）で表せる。
【数２３】
0005361001.tif 000024
【００５３】
式（２１）を正規化した値を、重み付きパケット配送確率として、式（２２）のように表し直す。
【数２４】
0005361001.tif 000025
【００５４】
すなわち、第２処理においては、平均パケット到着率ｂjは、式（２）を変形して式（２３）として表される。ただし、式（２３）の右辺のｃiは、式（２４）で表せる。つまり、式（２）の右辺のｐij(ｒ)を、ｐijｒj(ｒ)で置き換えて表せる。
【数２５】
0005361001.tif 000026
【数２６】
0005361001.tif 000027
【００５５】
式（２３）を、行列で表現すると、式（２５）のように表される。
【数２７】
0005361001.tif 000028
【００５６】
ただし、diag(r)は、対角成分が、ｒ1，ｒ2，・・，ｒnである対角行列を表し、1./cは、各成分が1/cjのベクトルを表す。したがって、平均パケット到着率ｂは、式（２６）のように表される。
【数２８】
0005361001.tif 000029
【００５７】
そして、式（２６）のｂ（ｒ）を、式（６）に適用して、前記した事案（Ａ），（Ｂ）に示したような式（９），（１４）の極値を算出することによって、評価関数が極値となるパラメータｒを算出することができる。そして、算出した当該パラメータｒを式（２１）に適用することによって、第１処理において算出したパケット配送確率を補正する。
【００５８】
（シミュレーション例）
計算機シミュレーションにより、ランダムネットワークにおいて、前記した第２処理に示した、重み付き最小コスト経路制御を行った場合の評価結果について以下に説明する。
計算機シミュレーションでは、各ノードのパケット発生率を、単位時間当り０．１とし、ネットワーク内のパケット数を最小化する事案（Ａ）の場合について、ネットワーク内のパケット数を最小化するための最適重みｒを算出した。
パケットの配送モデルは、前記した、パケット配送確率行列を生成するときの前提条件（ａ）〜（ｅ）に基づいて、図３のステップＳ３０１〜Ｓ３０７を実行した。また、配送重みｒは、前記した第２処理に従って算出した。なお、極値の算出は、matlab（登録商標）のoptimization tool boxを用いて実行した。また、ランダムネットワークは、人為的に構成し、そのノード数は１０とした。
【００５９】
計算機シミュレーションの結果を、表１に示す。表１中の「重みなし」の場合は、重みｒがすべて等しい（１．００の）ケースであり、ネットワーク内パケット数の平均値は７．３５であった。また、「最適重み」の場合は、ネットワーク内パケット数の平均値は６．７８であり、明らかに「重みなし」の場合より小さくなっている。
【表１】
0005361001.tif 000030
【００６０】
したがって、本実施形態で説明した計算方法によって各ノードへ割当てる重みを算出することによって、ネットワーク内のパケット数が減少し、輻輳状態を緩和する効果があることが分かった。
【００６１】
（変形例１）
前記した経路制御手法は、一般のネットワークを対象として、ハードウェアおよびソフトウェア上で処理可能であるが、この変形例１では、前記した経路制御手法が、仮想的に生成されるオーバーレイネットワークにおいても適用できることを説明する。
オーバーレイネットワークは、端末間で確立されるコネクションによって構築されるネットワークである。端末は、ソフトウェア、またはサーバ等のハードウェア機器であってもよい。低遅延および高スループットが求められるオーバーレイネットワークの経路制御に、前記した経路制御手法を適用することで、輻輳状態を回避する経路遅延およびスループットが実現される。さらに，本実施形態では、各ノードにおける平均パケット到着率を算出しているが、オーバーレイネットワークにおいて端末をノードと考えた場合、端末はルータ機器に比べてパケット処理能力が劣る。そのため、端末については、算出した平均パケット到着率に小さな重みを付加して評価関数に組み入れることで端末の処理負荷を低減可能にする等、評価関数を工夫することにより、様々な観点からの輻輳状態の回避を行うことができる。
【００６２】
（変形例２）
前記した実施形態では、図１に示すように、各ノード１０に、経路制御装置１１を備える構成について説明した。この変形例２では、経路制御装置１１のパケット配送確率行列演算部１２３および配送先決定部１２４の処理を、図６に示す経路制御装置４１において実行させる。すなわち、経路制御装置４１は、ネットワーク２０を構成するノード１０すべてについて、パケット配送確率を算出し、配送先を決定する。なお、経路制御装置４１は、ネットワーク２０を構成するノード１０のいずれかと通信可能に接続する。そして、ノード１０の配送先取得装置５１は、経路制御装置４１によって決定された配送先の情報を受信して、その配送先にパケットを配送する。以下に、経路制御装置４１および配送先取得装置５１の構成例について説明する。なお、図６では、経路制御装置４１を１台しか記載していないが、配送先の決定を担当するノード１０を２以上のグループに分割して、そのグループごとに経路制御装置４１を備えるようにしても構わない。
【００６３】
まず、経路制御装置４１の構成例について、図７を用いて説明する。なお、図２と同じ構成には、同じ符号を付し、説明を省略する。
図７に示すように、経路制御装置４１は処理部４２、記憶部４３、通信部１４を備える。処理部４２は、図示しないＣＰＵおよびメインメモリによって構成され、記憶部４３に記憶されているアプリケーションプログラムをメインメモリに展開して、宛先ノード情報取得部４２１、パケット配送確率行列演算部１２３、配送先決定部１２４、および配送先情報送信部４２２を具現化する。
【００６４】
宛先ノード情報取得部４２１は、バッファ１３１を介して、ノード１０の配送先取得装置５１から宛先ノードに関する情報を取得する。
配送先情報送信部４２２は、パケット配送確率行列演算部１２３および配送先決定部１２４によって決定された配送先に関する情報を、宛先ノードに関する情報を送信してきたノード１０の配送先取得装置５１に送信する。
記憶部４３は、少なくとも、バッファ１３１、ネットワークトポロジ１３２、およびリンクコスト１３４を記憶している。
【００６５】
次に、配送先取得装置５１の構成例について、図８を用いて説明する。図８に示すように、配送先取得装置５１は処理部５２、記憶部５３、通信部１４を備える。処理部５２は、図示しないＣＰＵおよびメインメモリによって構成され、記憶部５３に記憶されているアプリケーションプログラムをメインメモリに展開して、パケット取得部１２１、宛先ノード読出部１２２、宛先ノード情報送信部５２３、配送先情報取得部５２４、およびパケット配送部１２５を具現化する。
【００６６】
宛先ノード情報送信部５２３は、宛先ノードに関する情報を経路制御装置４１に送信する。
配送先情報取得部５２４は、経路制御装置４１から、配送先に関する情報を取得する。
【００６７】
なお、図６に示すように、経路制御装置４１を、ノード１０とは独立して備える利点は、図５に示すステップＳ５０６において他のノード１０にパケット配送確率を配送する必要がなくなること、および、ノード１０におけるパケット配送確率を算出するための処理負荷を軽減することができること、である。
【００６８】
以上、本実施形態で説明した経路制御装置１１のパケット配送確率行列演算部１２３は、パケットを次にどのノードへ配送するかを、パケット配送確率と乱数とに基づいて決定する。具体的には、パケット配送確率の算出に用いるパラメータｒを導入し、輻輳状態と非輻輳状態との境界点を算出するための評価関数の変数となる平均パケット到着率を算出する。すなわち、平均パケット到着率は、パラメータｒを変数として表される。次に、評価関数において、境界点となるパラメータｒの値を算出し、そのパラメータｒの値を用いてパケット配送確率を算出する。このようにして算出したパケット配送確率を用いることよって、輻輳を回避するためのネットワーク全体の経路制御を行うことができる。
なお、第１処理では、最短経路として最小コスト経路を用いたが、リンクのコストの代わりに、リンクのホップ数が最小となる経路を最短経路としても構わない。
【００６９】
また、本実施形態において説明した、経路制御装置１１は、一般的なコンピュータに、前記した各処理のプログラムを実行させることで実現することができる。このプログラムは、通信回線を介して提供することが可能であるし、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体に書き込んで配布することも可能である。
【符号の説明】
【００７０】
１０  ノード
１１，４１  経路制御装置
１２，４２  処理部
１３，４３  記憶部
１２１  パケット取得部
１２２  宛先ノード読出部
１２３  パケット配送確率行列演算部
１２４  配送先決定部
１２５  パケット配送部
１３１  バッファ
１３４  リンクコスト
１３５  配送確率行列
【図１】
0005361001.tif 000031
【図２】
0005361001.tif 000032
【図３】
0005361001.tif 000033
【図４】
0005361001.tif 000034
【図５】
0005361001.tif 000035
【図６】
0005361001.tif 000036
【図７】
0005361001.tif 000037
【図８】
0005361001.tif 000038