(57)【要約】【課題】特定のネットワーク回線においてトラフィックが増大する場合に、トラフィックが増大した回線のトラフィックの一部を他の回線に振り向けることができなかった。【解決手段】ソースｓから行先ｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定手段と、ネットワークを仮想的に２つに切断するネットワーク仮想切断手段と、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算手段と、仮想的に切断された回線の望ましい重みを計算する局所重み修正量計算手段と、前記局所重み修正量計算手段の出力を用いて仮想的に切断された回線の重みを修正する重み修正手段という構成を有するルーティング最適化装置により、特定の回線においてトラフィックが増大する場合に対応できる。【選択図】  図２
2004172713.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークのルーティングを最適化するルーティング最適化装置であって、ルータｓからルータｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定手段と、ネットワークを仮想的に２つに切断するネットワーク仮想切断手段と、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算手段と、仮想的に切断された回線の望ましい重みである修正切断コストベクトル信号を計算する局所重み修正量計算手段と、前記修正切断コストベクトル信号を用いて仮想的に切断された回線の重みを修正する重み修正手段とを有するルーティング最適化装置。
【請求項２】
ネットワークのルーティングを最適化するルーティング最適化装置であって、ルータｓからルータｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定手段と、ネットワークを仮想的に２つに切断するネットワーク仮想切断手段と、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算手段と、仮想的に切断された回線の望ましい重みの方向への微小な修正切断コストベクトル信号を計算する局所重み微小修正量計算手段と、微小な修正によって重みが修正が収束したか否かを判定する収束条件判定手段と、前記修正切断コストベクトル信号を用いて仮想的に切断された回線の重みを修正する重み修正手段とを有するルーティング最適化装置。
【請求項３】
ネットワークのルーティングを最適化するルーティング最適化方法であって、ルータｓからルータｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定ステップと、ネットワークを仮想的に２つに切断するネットワーク仮想切断ステップと、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算ステップと、仮想的に切断された回線の望ましい重みである修正切断コストベクトル信号を計算する局所重み修正量計算ステップと、前記修正切断コストベクトル信号を用いて仮想的に切断された回線の重みを修正する重み修正ステップとを有するルーティング最適化方法。
【請求項４】
ネットワークのルーティングを最適化するルーティング最適化方法であって、ルータｓからルータｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定ステップと、ネットワークを仮想的に２つに切断するネットワーク仮想切断ステップと、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算ステップと、仮想的に切断された回線の望ましい重みの方向への微小な修正切断コストベクトル信号を計算する局所重み微小修正量計算ステップと、微小な修正によって重みが修正が収束したか否かを判定する収束条件判定ステップと、前記修正切断コストベクトル信号を用いて仮想的に切断された回線の重みを修正する重み修正ステップとを有するルーティング最適化方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、インターネットなど情報通信分野において、トラフィックの増大による回線負荷を軽減させる技術に関する。
【０００２】
【従来の技術】
近年、インターネットの発展に伴い、ネットワークを流れるトラフィックは急速に増大し続けている。これに対応して、ネットワークの各所で回線の容量を上回る量のパケットが流入するという事態（回線のパンク）が発生し得る状況である。こうした回線のパンクを避けるために、ネットワークのトラフックを適切に制御する取り組みがなされており、この取り組みは、Ｔｒａｆｆｉｃ  Ｅｎｇｉｎｅｅｒｉｎｇと総称される。
【０００３】
Ｔｒａｆｆｉｃ  Ｅｎｇｉｎｅｅｒｉｎｇには大きく分けで２つの方法がある。ひとつは、パケットの統計的な分布に応じてネットワークを最適化する方法であり、もうひとつはＭｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ（ＭＰＬＳ）を使って明示的な経路を指定することでトラフィックを制御する方法である。
【０００４】
サービスの質の向上とネットワークリソースの効率的な利用を目的に、パケットの統計的な分布に応じてネットワークを最適化する試みとしては、ＦｏｒｔｓとＴｈｏｒｕｐによってなされた仕事がよく知られている（非特許文献１）。Ｆｏｒｔｚらは、ＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）の重みを最適化することによってトラフィックを分散させることを提案している。なお、ＯＳＰＦとは、最も良く利用されているルーティングプロトコルの一つである。彼らは、パケットが入っている境界ルータｓから出てゆく境界ルータｔの２つのルータ間を流れるトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）のデータからＯＳＰＦの重みを最適化するアルゴリズムを与え、ＡＴ＆Ｔ  ＷｏｒｌｄＮｅｔのバックボーン回線を対象にその有効性を確認している。
具体的には、Ｆｏｒｔｚらは、ルータ間のリンクａを流れるトラフィックの量がｌ（ａ）、そのリンクの容量がｃ（ａ）である場合に、その回線コスト（φａ（ｌ（ａ），ｃ（ａ）））は、［数１］で表した。
【０００５】
【数１】
2004172713.tif 000003
【０００６】
また、Ｆｏｒｔｚらは、ネットワーク全体のコスト（φ）を、［数２］で表わした。
【０００７】
【数２】
2004172713.tif 000004
【０００８】
そして、Ｆｏｒｔｚらは、回線コスト（φａ（ｌ（ａ），ｃ（ａ）））とネットワーク全体のコスト（φ）を最小とするＯＳＰＦの重みを求めている。ここで、関数φ（ｌ（ａ）／ｃ（ａ））は、リンクａを流れるパケット１個に対するコストであり、この関数は［数２］で表されるという性質を持っている。
【０００９】
【数３】
2004172713.tif 000005
【００１０】
Ｆｏｒｔｚらは、引用文献の中ではこれを区分線形関数で与えている。
この種のモデルでは、ＯＳＰＦの重みは、それぞれのリンクａを流れるトラフィックの量（ｌ（ａ））を通じてコストΦに反映される。この点をもう少し詳細に述べる。リンクａを流れるトラフィックの量（ｌ（ａ））は、［数４］と書ける。
【００１１】
【数４】
2004172713.tif 000006
【００１２】
ここで、Ｐ（ａ，ｓ，ｔ：ｗ）は、ＯＳＰＦの重みｗが与えられたときに、境界ルータｓから境界ルータｔに至る最短経路がリンクａを通る時に１をとり、その他の場合は０である関数である。この関数によって、ＯＳＰＦの重みはコスト関数に結び付けられる。
【００１３】
Ｆｏｒｔｚらのアイデアは、この様に定式化されたネットワークのトラフィック状態を表すモデルを使って［１］重みｗを修正する，［２］その結果、パケットの通過する経路が変化（関数Ｐが変化）する，［３］各リンクのトラフィックの量ｌ（ａ）が変化する，［４］コストが変化するという枠組みで、ネットワーク全体のコストΦを最小化しようというものである。このアイデアを実現する上で厄介なのは、コストを小さくするためにはＯＳＰＦの重みｗをどのように修正すればよいかを見つけることであり、Ｆｏｒｔｚらは一度にひとつの重みの値を変更してコストを再計算することを繰り返すことによりそれを求める方法を与えている。
【００１４】
Ｆｏｒｔｚらの方法はネットワークの重み全てを最適化するものであることから、どうしても計算量が多い。そのためネットワークを流れるトラフィック分布が時間的に安定している場合に最も有効と考えるべきである。
【００１５】
【非特許文献１】
Ｂｅｒｎａｒｄ  Ｆｏｒｔｚ  ａｎｄ  Ｍｉｋｋｅｌ  Ｔｈｏｒｕｐ著  ”Ｉｎｔｅｒｎｅｔ  Ｔｒａｆｆｉｃ  Ｅｎｇｉｎｅｅｒｉｎｇ  ｂｙ  Ｏｐｔｉｍｉｚｉｎｇ  ＯＳＰＦ  Ｗｅｉｇｈｔｓ”  Ｐｒｏｃ．  ＩＥＥＥ  ＩＮＦＯＣＯＭ，  ２０００年３月
【００１６】
【発明が解決しようとする課題】
しかしながら、実際のネットワークにおいては、特定の回線においてトラフィックが増大する場合がある。かかる場合、ネットワークの重み全てを最適化する上記の従来技術では、対応できない。
【００１７】
こうした場合には、トラフィックが増大した回線の負荷を、できるだけ早くトラフィックの一部を他の回線に振り向けることが望まれる。このような状況は、複数の拠点を持つＩＳＰの拠点間のトラフィック制御においてしばしば発生する。
【００１８】
【課題を解決するための手段】
そこで、本発明は、ソースｓから行先ｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定手段と、ネットワークを仮想的に２つに切断するネットワーク仮想切断手段と、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算手段と、仮想的に切断された回線の望ましい重みを計算する局所重み修正量計算手段と、前記局所重み修正量計算手段の出力を用いて仮想的に切断された回線の重みを修正する重み修正手段という構成を有するルーティング最適化装置である。
【００１９】
かかるルーティング最適化装置により、ネットワークにおいて少数の回線の負荷が他の回線と比較して著しく高い状態にある（もしくはそうなることが予測できる）場合、具体的には、ネットワークが図３のようなトポロジーを持つ場合に、回線ｎのトラフィックが多く回線ｎの負荷が高くなっている状態において、回線の重みを適切に設定することにより、回線ｎを流れるパケットの一部を回線ｐ，ｑに振り分けることで回線ｎの負荷を低減することができる。さらに簡潔に言えば、本発明の目的は、トラフィックが増大した回線の負荷をトラフィックの一部を他の回線に振り向けるためのＯＳＰＦの重み計算法を与えることである。ここで与えられる計算方法は、ネットワークの一部の重みだけを修正する方法である。なお、対象とするネットワークは複数の境界ルータがあるネットワークとする。
【００２０】
【発明の実施の形態】
請求項１に記載の発明は、ネットワークのルーティングを最適化する装置であって、ルータｓからルータｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定手段と、ネットワークを仮想的に２つに切断するネットワーク仮想切断手段と、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算手段と、仮想的に切断された回線の望ましい重みである修正切断コストベクトル信号を計算する局所重み修正量計算手段と、前記修正切断コストベクトル信号を用いて仮想的に切断された回線の重みを修正する重み修正手段とを有するルーティング最適化装置であり、仮想的に切断された回線のトラフィックを均質化することによりネットワークの負荷を低減するという作用を有する。
【００２１】
請求項２記載の発明は、ネットワークのルーティングを最適化する装置であって、ルータｓからルータｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定手段と、ネットワークを仮想的に２つに切断するネットワーク仮想切断手段と、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算手段と、仮想的に切断された回線の望ましい重みの方向への微小な修正切断コストベクトル信号を計算する局所重み微小修正量計算手段と、微小な修正によって重みが修正が収束したか否かを判定する収束条件判定手段と、前記修正切断コストベクトル信号を用いて仮想的に切断された回線の重みを修正する重み修正手段とを有するルーティング最適化装置であり、仮想的に切断された回線のトラフィックを均質化することによりネットワークの負荷を低減するという作用を有する。
【００２２】
請求項３記載の発明は、ネットワークのルーティングを最適化する装置であって、ルータｓからルータｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定ステップと、ネットワークを仮想的に２つに切断するネットワーク仮想切断ステップと、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算ステップと、仮想的に切断された回線の望ましい重みである修正切断コストベクトル信号を計算する局所重み修正量計算ステップと、前記修正切断コストベクトル信号を用いて仮想的に切断された回線の重みを修正する重み修正ステップとを有するルーティング最適化方法であり、仮想的に切断された回線のトラフィックを均質化することによりネットワークの負荷を低減するという作用を有する。
【００２３】
請求項４記載の発明は、ネットワークのルーティングを最適化する装置であって、ルータｓからルータｔへのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定ステップと、ネットワークを仮想的に２つに切断するネットワーク仮想切断ステップと、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算ステップと、仮想的に切断された回線の望ましい重みの方向への微小な修正切断コストベクトル信号を計算する局所重み微小修正量計算ステップと、微小な修正によって重みが修正が収束したか否かを判定する収束条件判定ステップと、前記修正切断コストベクトル信号を用いて仮想的に切断された回線の重みを修正する重み修正ステップとを有するルーティング最適化方法であり、仮想的に切断された回線のトラフィックを均質化することによりネットワークの負荷を低減するという作用を有する。
【００２４】
以下、本発明の実施の形態について、図１から図６を用いて説明する。
（実施の形態１）
以下、本発明の実施の形態１について、図１を参照しながら説明する。図１は、最適化装置のブロック図である。１００は、本発明のルーティング最適化装置が最適化の対象とするネットワークであり、複数の境界ルータがあるネットワークである。本発明は、測定開始信号入力端子１０から測定開始信号が入力されると前記ネットワークのルータｓ（ソース）からルータｔ（行先）へのトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定するネットワークトラフック測定手段１と、ネットワークを仮想的に２つに切断するネットワーク仮想切断手段２と、仮想的に切断された２つの部分ネットワークの経路コストと仮想的に切断された回線のコストを計算するコストベクトル計算手段３と、仮想的に切断された回線の望ましい重みを計算する局所重み修正量計算手段４と、前記局所重み修正量計算手段の出力を用いて仮想的に切断された回線の重みを修正する重み修正手段５という構成を有している。
【００２５】
以下、上記構成の動作について説明する。
ネットワークトラフック測定手段１は、測定開始信号入力端子１０から測定開始信号が入力されると、ネットワーク１００のルータ間を流れるトラフィックを表すデマンドマトリックスＤ（ｓ，ｔ）を測定し、測定結果をネットワーク状態信号ＮＳとしてネットワーク仮想切断手段２に送る。
【００２６】
なお、また、ネットワークを構成する各ルータが自身をソースとするデマンドマトリックスをネットワークトラフィック測定手段１に送信する構成をとることもできる。また、このトラフィックの測定は一定時間ごとに行われるようにすることは好ましい。
【００２７】
前記ネットワーク状態信号を受けた仮想ネットワーク切断手段２の好ましい形態は、ネットワークの状態をネットワーク管理者に示すネットワーク状態表示手段と、ネットワーク管理者が最適化したい（トラフィックを減らしたい）回線を選択する仮想切断回線選択信号入力手段とからなる。この場合、仮想ネットワーク切断手段２は、ネットワーク状態表示手段にネットワークの状態を提示し、ネットワーク管理者は前記前記ネットワーク状態表示手段に表示されたネットワーク状態を見て、ネットワークを２つの部分ネットワーク（以下、部分ネットワークＡ，部分ネットワークＢと呼ぶ）に仮想的に切断するように、負荷を低減したい回線（図３中の回線ｎ以下、対象回線と呼ぶ）を含む複数の回線（図３中の回線ｐ、ｑ）を仮想的に切断する回線として選び、その結果を仮想切断回線選択信号入力手段に入力する。すなわち、図４に示した破線でネットワークを２つに仮想的に切断する。この時、切断された回線の数をＮとし、対象回線以外の切断した回線をバイパス回線と、また両者をまとめて切断回線呼ぶ。仮想ネットワーク切断手段２は、仮想切断回線選択信号をコストベクトル計算手段３に送る。
【００２８】
なお、仮想的に切断する回線の選択を、各回線のトラフィックから自動的に計算するように構成することも好ましい。その際に、トラフィックと回線の容量の比が最も大きいもの（回線のパンクに一番近いもの）を対象回線とすることは好ましい。
【００２９】
コストベクトル計算手段３は、前記仮想切断回線選択信号を受けて、各デマンドマトリックスＤ（ｓ，ｔ）に属する各パケットがそれぞれの仮想切断回線を通る場合のコストを、部分ネットワークＡのコスト、通過する切断回線のコスト、部分ネットワークＢのコストに分けて計算する。以下、この計算の詳細を述べる。
【００３０】
ここで、部分ネットワークＡのソースｓから部分ネットワークＢの行先ｔへ送られるパケットを考える。このパケットは、部分ネットワークＡから部分ネットワークＢへはＮ本の回線のいずれかを通る。そして、パケットが回線ｉを通る場合のコスト（ｖｉ（ｓ，ｔ））は、［数５］に示すように、ｉの接続ルータまでの部分ネットワークＡ内の最短経路の部分コストｒｉＡ  （ｓ，ｔ）と、回線ｉのコストｗｉと、部分ネットワークＢ内の最短経路の部分コストｒｉＢ  （ｓ，ｔ）との和で与えられる。
【００３１】
【数５】
2004172713.tif 000007
【００３２】
ＯＳＰＦのアルゴリズムで選択される最短経路は、今考えているパケットが通る可能性のあるＮ本の経路のうち、［数６］で与えられる回線ｍを通る経路である。
【００３３】
【数６】
2004172713.tif 000008
【００３４】
ここで、関数ａｒｇｍｉｎ｛ｖｉ（ｓ，ｔ），ｉ＝１，２，・・・，Ｎ｝は、ｖｉ（ｓ，ｔ）が最小となる場合の数字ｉを値とする関数である。
さらに、切断された回線ごとに計算されるパケットのコストが張るＮ次元空間を導入し、かかるＮ次元空間（ベクトルｘ）を［数７］に示す。
【００３５】
【数７】
2004172713.tif 000009
【００３６】
このとき、パケットのとり得るＮ個のコスト（ベクトルｖ（ｓ，ｔ））は、［数８］で表される３つのベクトルの和である。
【００３７】
【数８】
2004172713.tif 000010
【００３８】
そして、部分ネットワークＡから部分ネットワークＢへと送られる個々のパケットのとり得るコストは、図５に示したように、このＮ次元空間内の一点に対応させることができる。こうして、各パケットに対応したＮ次元空間内の点の分布を我々は得る。以下、ｖ（ｓ，ｔ）をコストベクトル、ｒＸ（ｓ，ｔ）を部分ネットワークＸの部分コストベクトル（Ｘは、ＡやＢなどの値をとり得る変数）、ｗを回線コストベクトルと呼ぶ。
【００３９】
コストベクトル計算手段３は、こうして求められた２つの部分コストベクトル信号と切断回線信号を局所重み修正量計算手段４に送る。
【００４０】
次に、局所重み修正量計算手段４は、前記２つの部分コストベクトル信号と切断コストベクトル信号を受けて、切断回線の重みを修正する。以下、その処理の詳細を説明する。
【００４１】
まず、望ましい回線の状態を理解するために、切断回線の数が３の場合を説明する。今、ＯＳＰＦの選択は、各コストベクトルに対し、そのコストベクトルと成す角度が最も大きい軸ベクトルに自身を射影することに対応する。
【００４２】
また、ＯＳＰＦによって選択される回線は、Ｎ次元空間内の点の分布を各軸と成す角度を保って［数９］で示される超平面へ射影しても変わらない。
【００４３】
【数９】
2004172713.tif 000011
【００４４】
したがって、切断回線の数が３の場合には、図６の左図に示すような正三角形の値域と点で示されたパケットの分布を得る。正三角形の各頂点は、Ｎ次元空間の各軸に、すなわち一本の切断回線に対応している。図６の左図では、点は右側の２等辺三角形の内部に集中しているから、全てのパケットは左下の頂点に対応する切断回線を流れる状態にネットワークはある。
【００４５】
この時、望ましい回線の状態とは右図に示されたように、全ての回線をほぼ等しくパケットが流れる状態である。したがって、我々の解くべき問題は、図６の右図ようになるように、どの方向にどのくらい分布の位置を動かせばよいかを計算する方法を与えることである。
【００４６】
ここでは、切断された回線の容量が等しいという簡単な場合について説明する。このとき、パケットがバランスよく切断回線を流れるようにするためには、分布の中心を各軸から均等な角度を成す点に移動させればよい。それは、［数１０］で示される分布の中心（重心）が［数１１］で示される直線上にくるようにすればよいことに対応する。
【００４７】
【数１０】
2004172713.tif 000012
【００４８】
【数１１】
2004172713.tif 000013
ここで、Ｎｃの値は［数１２］の式で求められる。
【００４９】
【数１２】
2004172713.tif 000014
すなわち、
【００５０】
【数１３】
2004172713.tif 000015
となればよい。
ここで、ベクトル１は、［数１４］で示される。
【００５１】
【数１４】
2004172713.tif 000016
【００５２】
また、＜ベクトルｒＡＢ＞は、［数１５］で示される。
【００５３】
【数１５】
2004172713.tif 000017
【００５４】
このためには、我々が設定できる切断回線コストベクトルを［数１６］または［数１７］と修正すればよい。
【００５５】
【数１６】
2004172713.tif 000018
【００５６】
【数１７】
2004172713.tif 000019
【００５７】
ここで、ｔは切断コストベクトルの各成分の値がＯＳＰＦの許す範囲に収まる限り任意の値を取ることができるパラメータである。
【００５８】
局所重み修正量計算手段４は、［数１７］で与えられる修正切断コストベクトル信号を重み修正手段５に送る。
【００５９】
重み修正手段５は、前記仮想的に切断された回線の重みを前記局所重み修正量計算手段からの修正切断コストベクトル信号の各成分の値を対応する切断回線の重みとして設定する。
【００６０】
以上、本実施の形態によれば、負荷を低減したい対象回線のトラフィックをバイパス回線に流すことにより、ネットワークの負荷を低減することができる。
【００６１】
なお、上の議論は、部分ネットワークでパケットコストの分布が一定の広がりをもつことを前提としている。しかし、部分ネットワークに極めて特殊な設定をした場合、複数のデマンドマトリックスの成分に対し、部分ネットワークのコストベクトルは等しいという特殊な場合もありえる。この特殊な場合においては、切断経路の重みを適切に選択することにより複数の経路が等コストになるようにすることができる。したがって、この特殊な場合であっても、等コスト経路に等しい確率でパケットを流すようなルーティング方式を用いれば、トラフィックを分散することができる。
【００６２】
（実施の形態２）
回線の容量が等しくない場合は、パケットひとつあたりのコストが流れる回線の容量ごとに異なるために、パケットが流れる回線が変化するたびに「重心」を求める繰り返し計算が必要となる。
【００６３】
この課題を解決するために、実施の形態１の局所重み修正量計算手段４に換えて、局所重み微小修正量計算手段４１と収束条件判定手段４２を用いる。本実施の形態における最適化装置のブロック図を図２に示す。
【００６４】
以下、局所重み微小修正量計算手段４１の動作について説明する。
まず、切断回線の重みの初期値のベクトルｗ［０］は、［数１８］とする。
【００６５】
【数１８】
2004172713.tif 000020
【００６６】
また、コストベクトルの初期値（ベクトルｖ（ｓ，ｔ）［０］）は、［数１９］とする。
【００６７】
【数１９】
2004172713.tif 000021
【００６８】
デマンドマトリックスＤ（ｓ，ｔ）のコストベクトルは、ベクトルｖ（ｓ，ｔ）［０］であり、コストベクトルが与えられたときＯＳＰＦで選択される回線ｍ［０］とその容量の逆数（以下、密度と呼ぶ）は、［数２０］、［数２１］と計算される。
【００６９】
【数２０】
2004172713.tif 000022
【００７０】
【数２１】
2004172713.tif 000023
【００７１】
このとき、回線の容量の違いを考慮した分布の重心の初期値は、密度を使って［数２２］と計算される。
【００７２】
【数２２】
2004172713.tif 000024
【００７３】
これから、分布の重心を直線上に移動させる新しい切断回線コストベクトルは［数２３］となる。
【００７４】
【数２３】
2004172713.tif 000025
【００７５】
しかし、パケットがどの回線を通るかで密度は変化するので、切断回線コストベクトルを上のもので置き換えると、個々のパケットの密度が大きく変化し、そのため重心は異なった場所になる。
【００７６】
これを解決するために、局所重み微小修正量計算４１は、新しい切断回線コストベクトルを、ａを１より小さな正の値として、［数２４］とし、新しいコストベクトルを［数２５］とし、この新しいコストベクトルに対しＯＳＰＦで選択される回線ｍ［１］を計算する。
【００７７】
【数２４】
2004172713.tif 000026
【００７８】
【数２５】
2004172713.tif 000027
【００７９】
そして、局所重み微小修正量計算４１は、［数２４］で与えられる修正切断コストベクトル信号と［数２５］で与えられる修正コストベクトル信号を収束条件判定手段４２に送る。
【００８０】
収束条件判定手段４２は、前記修正コストベクトル信号を受けて、収束条件の判定を行う。収束と判定された場合には、前記修正切断コストベクトル信号を重み修正手段５に送る。収束と判定されなかった場合は、前記修正コストベクトル信号と前記修正切断コストベクトル信号を、それぞれコストベクトル信号、切断ベクトル信号として前記局所重み微小修正量計算手段４２に送る。
【００８１】
収束判定の好ましい方法の一例は、重心と直線との距離があらかじめ定められた値以下になった場合に収束と判定する方法である。
【００８２】
以下、上記の計算を繰り返すことにより、回線容量を考慮した分布の重心を前記直線に近づけてゆくことができる。
【００８３】
なお、切断回線のトラフィックの総計を最小にするためにはパラメータｔは可能な限り大きな値をとればよい。なぜなら、パラメータｔは、切断回線を２回以上通る経路についてのみコストとして効くパラメータであるからである。このことは極端な場合として、パラメータｔをほぼ無限の値をとった場合を考えれば、直ちに明確になる。部分ネットワークＡから部分ネットワークＢへと流れるパケットは、いずれにしても切断回線を通り、どの回線を通るかは切断回線間のコストの差（絶対値でなく）によってのみ決まる。
【００８４】
一方、部分ネットワークＡから部分ネットワークＢへ一度流れ、再び部分ネットワークＡに戻ってくるパケットにたいしては、パラメータｔは膨大なコストとして働き、こうした経路は最短経路ではなくなる。すなわち、ソースと行き先が同一部分ネットワークに属するパケットは、切断回線を通らなくなる。つまり、パラメータｔは２つの部分ネットワークの分離の強さを与えるパラメータである。
【００８５】
さらに、本発明のルーティング最適化装置は、デマンドマトリックスから切断回線の重みだけを変更する装置である。つまり、本発明のルーティング最適化装置は、ネットワークの局所的な重みを変更する装置である。「切断回線の重みだけを変更する」ということは、言い方を変えれば、部分ネットワーク内のコストを変えないこと（部分コストベクトルは不変）である。これは、局所トラフィック分散法は位置ベクトルの分布の形状を変化させることはできない（例えば、分布の回転はできない）ことを意味する。
【００８６】
したがって、分布の等方性が極端に悪い場合、局所トラフィック分散法を一度使うだけでは、ごく一部のパケットしかバイパス回線に回らないという可能性がある。しかし、本発明は、切断回線に対してトラフィックを均質化するルーティング最適化装置である。したがって、ネットワークの切り方を変えて繰り返し使用することにより、ネットワーク全体のトラフィックを均質化することが可能である。この観点からは、本発明のルーティング最適化装置は、上述した従来技術であるＦｏｒｔｚらの装置と比較して高速なルーティング最適化装置であるといえる。
【００８７】
境界ルータへの流入量Ｒｉとそこからの流出量Ｒｏしか測定できない場合に触れる。この場合、一般的には問題は不良設定となり、何らかの仮定を導入しなければ問題を解くことができない。但し、ルータをつなぐ回線が十分多く、かつそれらの回線にパケットが流れていれば、連立１次方程式を解くことでデマンドマトリックスを求めることが可能である。
【００８８】
ひとつの素直な仮定は、デマンドマトリックスを［数２６］［数２７］の式で表すものとすることである。
【００８９】
【数２６】
2004172713.tif 000028
【００９０】
【数２７】
2004172713.tif 000029
【００９１】
上記の方法は、パケットのソースと行き先の統計分布は独立と考えることに対応し、一般にネットワークが大規模でトラフィックが多い場合に有効である。
【００９２】
この方法の精度については、ネットワークのいくつかの回線を選びその回線を流れるトラフィックの測定値と上記デマンドマトリックスから計算される予測値の比を調べれば計測できる。
【発明の効果】
以上のように、本発明によれば、ネットワークにおいて少数の回線の負荷が他の回線と比較して著しく高い状態にある（もしくはそうなることが予測できる）場合、具体的には、ネットワークの回線ｎのトラフィックが多く回線ｎの負荷が高くなっている状態において、回線の重みを適切に設定することにより、回線ｎを流れるパケットの一部を、バイパスを成す回線ｐ，ｑに振り分けることで回線ｎの負荷を低減することができる。
【図面の簡単な説明】
【図１】実施の形態１におけるルーティング最適化装置のブロック図
【図２】実施の形態２におけるルーティング最適化装置のブロック図
【図３】実施の形態１におけるネットワークの概念図
【図４】実施の形態１におけるネットワークの概念図
【図５】実施の形態１における部分ネットワーク間を送信される個々のパケットのとり得るコストを示した図
【図６】実施の形態１におけるパケットの分布を説明する図
【符号の説明】
１  ネットワークトラフィック計測手段
２  ネットワーク仮想切断手段
３  コストベクトル計算手段
４  局所重み修正量計算手段
５  重み修正手段
４１  局所重み微小修正量計算手段
４２  収束判定手段
１００  ネットワーク
【図１】
2004172713.tif 000030
【図２】
2004172713.tif 000031
【図３】
2004172713.tif 000032
【図４】
2004172713.tif 000033
【図５】
2004172713.tif 000034
【図６】
2004172713.tif 000035