経路最適化システム、プログラムおよび方法
【課題】同一ノードに至る複数の経路が存在する場合に、最適な経路を選択するためのシステム、プログラム及び方法を提供する。
【解決手段】始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、始点ノードから第２ノードを経由して終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択するシステムであって、リンクコストを記憶する記憶手段１５０と、始点ノードコスト、第１リンクコスト、第１ノードコスト、第２リンクコスト、及び終点ノードコストに基づいて算出される第１の経路コストと、始点ノードコスト、第３リンクコスト、第２ノードコスト、第４リンクコスト、及び終点ノードコストに基づいて算出される第２の経路コストとを比較し、コストが低い方の経路を選択することによって経路を最適化する経路計測最適化手段１３０とを備えることにある。
【解決手段】始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、始点ノードから第２ノードを経由して終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択するシステムであって、リンクコストを記憶する記憶手段１５０と、始点ノードコスト、第１リンクコスト、第１ノードコスト、第２リンクコスト、及び終点ノードコストに基づいて算出される第１の経路コストと、始点ノードコスト、第３リンクコスト、第２ノードコスト、第４リンクコスト、及び終点ノードコストに基づいて算出される第２の経路コストとを比較し、コストが低い方の経路を選択することによって経路を最適化する経路計測最適化手段１３０とを備えることにある。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同一ノードに至る複数の経路が存在する場合に、最適な経路を選択するためのシステム、プログラム及び方法に関する。
【背景技術】
【０００２】
インターネットに代表されるオープンネットワークで通信経路を決定する場合、RIP(Routing Information Protocol)やOSPF(Open Shortest Path First)により経路が決定される。経路を動的に決定するには、OSPFが用いられることが多い。
【０００３】
OSPFは、隣接するルータ間の回線速度（帯域幅）に基づいて、ルータ間の通信コストを算出し、目的のノードに至るまでの通信コストの合計が最小となるよう経路を決定する。計算には、ダイクストラ法や、A*アルゴリズムが使われる。
【０００４】
このようにして決定される経路には、パケット遅延やパケット廃棄率などのネットワーク特性が反映されないため、VoIP(Voice over Internet Protocol)などの準リアルタイム通信には不適当な経路が割り当てられることがある。この現象を「２つの通信加入者間」の問題と位置づけて解決策を与えた技術が開示されている（例えば、特許文献１参照）。
【特許文献１】特開平９−１２１２２８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、既に開示されている技術は、２つの通信加入者間の問題に限定されており、ある経路の通信に関する評価属性が動的に変化することが考慮されていない。例えば、ベストの通信品質を提供できるセッション数が５０程度と見積もられる経路に、１００の通信セッションが流入した場合、最適と評価された経路に負荷が集中することで、全セッションに於いて通信品質劣化が懸念される。特に、１つのノードが複数の経路に含まれていると、ノードの評価を行わないことが欠点になる。
【課題を解決するための手段】
【０００６】
本発明の第１の特徴は、始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、始点ノードから第２ノードを経由して終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択するシステムであって、（１）始点ノードの始点ノードコスト、始点ノードと第１ノードとをつなぐ第１リンクの第１リンクコスト、第１ノードの第１ノードコスト、第１ノードと終点ノードとをつなぐ第２リンクの第２リンクコスト、及び終点ノードの終点ノードコスト、並びに始点ノードと第２ノードとをつなぐ第３リンクの第３リンクコスト、第２ノードの第２ノードコスト、及び第２ノードと終点ノードとをつなぐ第４リンクの第４リンクコスト、を記憶する記憶手段と、（２）始点ノードコスト、第１リンクコスト、第１ノードコスト、第２リンクコスト、及び終点ノードコストに基づいて算出される第１の経路コストと、始点ノードコスト、第３リンクコスト、第２ノードコスト、第４リンクコスト、及び終点ノードコストに基づいて算出される第２の経路コストとを比較し、コストが低い方の経路を選択することによって経路を最適化する経路計測最適化手段とを備えることにある。
【０００７】
本発明の第２の特徴は、各ノードにおけるパケット遅延時間及びパケット廃棄率に基づいて各ノードのノードコストを計算することにある。
【０００８】
本発明の第３の特徴は、各ノードのノードコストを再計算し、再計算によって得られた新たなノードコストに基づいて各経路コストを再計算し、再計算によって得られた新たな経路コストを比較して、経路変更の要否を判断することにある。
【発明の効果】
【０００９】
本発明の第１の特徴によれば、経路（パス）コストを、リンクのみに附加するのではなく、ノードに附加することによって、ノードが最も効率的に稼働する経路を選択することができる。
【００１０】
本発明の第２の特徴によれば、各ノードにおけるパケット遅延時間及びパケット廃棄率に基づいて算出されたノードコストに基づいて最適な経路を選択することができる。
【００１１】
本発明の第３の特徴によれば、所定時間毎に又は所定イベントをトリガーとして、ノードコストを再計算することによって最適な経路を動的に選択することができる。
【発明を実施するための最良の形態】
【００１２】
以下に図面に基づいて、本発明を実施するための最良の形態を説明する。なお、以下の説明は、単なる例示に過ぎず、本発明の技術的範囲は以下の説明に限定されるものではない。
【実施例】
【００１３】
ネットワークを抽象化して扱うために「グラフ理論」が援用される。ここでも、グラフ理論で登場するノード，リンク，パスなどの用語を以下の意味で使用する。
【００１４】
ノードとは、ルータ，ブリッジ，スイッチなどのネットワーク通信機器、さらには PCやサーバなどネットワークアドレスを持つネットワーク端末を含めることもある。
【００１５】
リンクとは、ノード間を結ぶ配線を指す。１つのリンクは、少なくとも物理的な１本の配線に実体として対応付けることができる。ネットワークをモデル化する場合、リンクの両端でノードに接するポートの生死や、通信バッファの状態までをリンクに含める場合がある。
【００１６】
リンクとノードで形成され、孤立点・枝分れ・ループを含まないグラフをパス（経路）と呼ぶ。パスには、始点となるノードと、終点となるノードがあり、始点から終点まで情報が流れる順路を示す。
【００１７】
「グラフ理論」でパスを評価する場合には、リンクのコストを足し合わせ比較するが、ノードのコストは評価されない。ノードは、0次元の点と見なされ、距離などのコスト値も0（ゼロ）として取り扱われる。
【００１８】
通常、ルータは、パケットのヘッダを読み取り、ルータ内に記憶されているルーティングテーブルを参照して、次のホップ先（次の転送先ルータ）を決定する。ルータが一定時間のうちに処理できるパケット量をルータの仕様から考慮し、経路決定の要因として計量モデルに組み入れる。
【００１９】
なお、パケットを生成し送信するノードがパケットの通過経路を指定するソースルーティングを用いることもできる。ソースルーティングを利用するとパケットを生成し送信するノードが明示的に経路を指定することができる。途中のすべての経路を指定する「ストリクトソースルーティング」といくつかの経路を通過することを指定し、それ以外は途中のルータに任せる「ルーズソースルーティング」のいずれでも利用することができる。
【００２０】
図１（ａ）にルータ及びリンクからなる経路の一例であって、各リンクの通信速度を示す。同図に示すように、各ルータ間の通信速度は以下のとおりとする。
【００２１】
ルータＲ１−ルータＲ２間： ６４Ｋｂｐｓ
ルータＲ２−ルータＲ３間：１．５Ｍｂｐｓ
ルータＲ１−ルータＲ４間： ６４Ｋｂｐｓ
ルータＲ２−ルータＲ４間：１２８Ｋｂｐｓ
ルータＲ３−ルータＲ５間：１２８Ｋｂｐｓ
ルータＲ４−ルータＲ５間： ６４Ｋｂｐｓ
ルータＲ３−ルータＲ６間： ６４Ｋｂｐｓ
そして、経路コストを、帯域の逆数に比例して付値する。１．５Ｍｂｐｓ を コスト 1 とすると、
ルータＲ１−ルータＲ２間：１．５Ｍｂｐｓ／ ６４Ｋｂｐｓ＝２３
ルータＲ１−ルータＲ４間：１．５Ｍｂｐｓ／ ６４Ｋｂｐｓ＝２３
ルータＲ４−ルータＲ５間：１．５Ｍｂｐｓ／ ６４Ｋｂｐｓ＝２３
ルータＲ３−ルータＲ６間：１．５Ｍｂｐｓ／ ６４Ｋｂｐｓ＝２３
ルータＲ２−ルータＲ３間：１．５Ｍｂｐｓ／１．５Ｍｂｐｓ＝ １
ルータＲ２−ルータＲ４間：１．５Ｍｂｐｓ／１２８Ｋｂｐｓ＝１２
ルータＲ３−ルータＲ５間：１．５Ｍｂｐｓ／１２８Ｋｂｐｓ＝１２
というコストになる。
【００２２】
平均パケット長を１０２４Ｂｙｔｅとすると、
６４Ｋｂｐｓ回線では８ｐｐｓ （Packet Per Second）
１．５Ｍｂｐｓ回線では１８３ｐｐｓ
のパケットを１秒間に転送できることになる。
【００２３】
ルータＲ２とルータＲ３の処理能力が２００ｐｐｓ であったならば、ルータＲ２→ルータＲ３が飽和している時にはルータＲ２とルータＲ３の処理限界に達している可能性がある。
【００２４】
従って、静的に経路を決める条件の下では、リンクのコストだけでは最適な経路を選べないことがある。
【００２５】
表１に、各ルータの処理能力の一例を示す。
【表１】
【００２６】
処理コスト係数を、ルータ処理能力の逆数に比例して付値する。経路コストは１８３ｐｐｓを基準コストと定義したので、これに近いルータＲ３の処理能力（２００ｐｐｓ）を基準コスト（コスト 1）とする。１８３ｐｐｓ≠２００ｐｐｓで、若干の違いはあるが、１８３ｐｐｓはパケットサイズを１０２４Ｂｙｔｅと仮定しての数値であるから、許容範囲とみなせる。
【００２７】
ルータＲ１、Ｒ５、Ｒ６：２００ｐｐｓ／ ５０ｐｐｓ＝４
ルータＲ２、Ｒ３ ：２００ｐｐｓ／２００ｐｐｓ＝１
ルータＲ４ ：２００ｐｐｓ／１００ｐｐｓ＝２
というコスト係数になる。コスト係数のまま仮コストとしたコスト行列を表２に示す。
【００２８】
表２から、リンクコストとノードコストを対比できる。
【表２】
【００２９】
図１（ｂ）に、各リンクコストと各ノードコストとを示す。
【００３０】
＜経路コスト計算＞
リンクの経路コストを、ノードの処理コストと統合し、計量評価する。コスト計算には、リンクコスト行列にダイクストラ法を適用する方式が、一般に用いられる。本方式では、ノードコストまで考慮に入れて総コストを計算するために、ノードベクトルを附加した行列に拡張する。なお、ルータ処理コストは、ルータの入口と、出口とで、それぞれ発生するものとする。
【００３１】
例えば、ルータＲ１→ルータＲ２→ルータＲ３→ルータＲ５の経路では、まずルータＲ１の出口のコストが「４」、ルータＲ１とルータＲ２との間のコストが「２３」、ルータＲ２の入口のコストが「１」となる。同様に、ルータＲ２の出口のコストが「１」、ルータＲ２とルータＲ３との間のコストが「１」、ルータＲ３の入口のコストが「１」となる。同様に、ルータＲ３の出口のコストが「１」、ルータＲ３とルータＲ５との間のコストが「１２」、ルータＲ５の入口のコストが「４」となる。
【００３２】
つまり、
ルータＲ１→ルータＲ２：4 +23 + 1 = 28
ルータＲ２→ルータＲ３：1 + 1 + 1 = 3
ルータＲ３→ルータＲ５：1 +12 + 4 = 17
であるから、総コストは 28 + 3 + 17 = 48となる。
【００３３】
同様に、ルータＲ１→ルータＲ２→ルータＲ４→ルータＲ５の経路では、
ルータＲ１→ルータＲ２：4 + 23 + 1 = 28
ルータＲ２→ルータＲ４：1 + 12 + 2 = 15
ルータＲ４→ルータＲ５：2 + 23 + 4 = 29
であるから、総コストは 28 + 15 + 29 = 72となる。
【００３４】
同様に、ルータＲ１→ルータＲ４→ルータＲ５の経路では、
ルータＲ１→ルータＲ４：4 + 23 +2 = 29
ルータＲ４→ルータＲ５：2 + 23 +4 = 29
であるから、総コストは29 + 29 = 58となる。
【００３５】
＜動的評価＞
［ルータＲ２→ルータＲ３］リンクを経由する経路と、そうでない経路との差は、最小で 58−48 = 10、最大で72−48 = 24である。従って、ルータの処理負荷に応じて、ルータＲ２とルータＲ３の処理コストが１０倍程度変化すれば、ボトルネックとなる懸念がある経路が動的に切り替わる。
【００３６】
処理コストが１０倍変化することは、ルータの平常時の負荷を、最大負荷の１／１０と見積もることに相当する。最大負荷をベースにした試算では、２００ｐｐｓを標準コストとしていたが、その１／１０の２０ｐｐｓを標準コストとすることで、各ルータのコストは以下のような変数を含む計算式で算出される。
【００３７】
ルータＲ１、Ｒ５、Ｒ６：
（２００ｐｐｓ／ ５０ｐｐｓ）×（Ｘｐｐｓ／ ２０ｐｐｓ）
ただし Ｘは、Ｒ１，Ｒ５，Ｒ６の処理負荷で ０≦Ｘ≦５０
ルータＲ２、Ｒ３ ：
（２００ｐｐｓ／２００ｐｐｓ）×（Ｙｐｐｓ／ ２０ｐｐｓ）
ただし Ｙは、Ｒ２，Ｒ３の処理負荷で ０≦Ｙ≦２００
ルータＲ４ ：
（２００ｐｐｓ／１００ｐｐｓ）×（Ｚｐｐｓ／ ２０ｐｐｓ）
ただし Ｚは、Ｒ４の処理負荷で ０≦Ｚ≦１００
というコスト式になる。
【００３８】
平常時のコストは、上記の式にそれぞれＸ＝Ｙ＝Ｚ＝２０を代入して
ルータＲ１、Ｒ５、Ｒ６：２００／ ５０＝４
ルータＲ２、Ｒ３ ：２００／２００＝１
ルータＲ４ ：２００／１００＝２
を得る。
【００３９】
すべてのルータの負荷が、仮に最大となったとすれば
ルータＲ１、Ｒ５、Ｒ６：（２００／ ５０）×（ ５０／２０）＝１０
ルータＲ２、Ｒ３ ：（２００／２００）×（２００／２０）＝１０
ルータＲ４ ：（２００／１００）×（１００／２０）＝１０
といずれも等しくなる。
【００４０】
本実施例では、各ノードのコストは、各ルータのパケット処理負荷を、基準となるルータのパケット処理性能（ｐｐｓ）で除して求めている。このようにして求めたノードコストは、リンクコストとは異なる比例尺度となるため、コスト係数によってノードコストとリンクコストの整合性を図っている。本実施例では、ノードコストの方に係数を乗じて調整した。
【００４１】
ルータの処理負荷を調べるには、直接的な方法と、間接的な方法とがある。直接的な方法とは、ルータ内部に処理負荷の変化が記録される場合に利用できる、ルータにネットワーク上の他の機器から当該ルータに「処理負荷」の問い合わせを行う方法である。
【００４２】
間接的な方法とは、試験パケットの転送依頼を送って、パケットの転送に要した遅延時間や、パケット損失率などから、負荷を推定する方法である。高性能ルータがあれば、そのルータを起点にして負荷試験を行うこともできる。
【００４３】
パケット遅延はＣＰＵ負荷と因果関係があるので、直接的な方法でＣＰＵ負荷を監視しノードコストの評価に反映させる。パケット遅延がある閾値を超えるとタイムアウトを引き起こし、パケットは廃棄される。パケット廃棄は、パケット再送（リトライ）の原因となる。パケット廃棄率は、一般のルータでは、ＳＮＭＰ(Simple Network Management Protocol)によりＭＩＢ(Management Information Base)エントリーを監視することによって評価することが可能である。
【００４４】
＜通信コスト評価＞
通信可能な経路候補を準リアルタイムに再計算する。リンクコストの再計算は任意とする。リンクコストの再計算は例えばOSPFに基づいて行うことができる。ノードコストは、ノードにおけるパケット遅延時間，パケット廃棄率を用いて評価する。
【００４５】
直接的方法では、パケット遅延時間はＣＰＵ利用率から推定し、パケット廃棄率はＭＩＢより取得する。
【００４６】
間接的方法では、パケット遅延時間は試験パケットで計測する。パケット廃棄率は、Socketライブラリを使ったカスタムアプリケーションを用いて、パケットヘッダに記されたパケット連番を参照し、番号の抜けをチェックすることで計算できる。例えば、パケット連番が 1から10000までの通信セッションで、10, 20, 30 の番号のパケットが受信側に届かなければ、廃棄率は3/10000 = 0.03（％）である。
【００４７】
図２に、本実施の形態にかかる経路最適化システムにおけるルータのブロック構成図の一例を示す。同図に示すように、ルータ１００は、計測データ交換手段１１０と、試験データ生成手段１２０と、経路計測最適化手段１３０と、経路評価手段１４０と、計測データ記憶手段１５０とを備える。
【００４８】
同図に示すように、計測データ交換手段１１０は計測データ記憶手段１５０に、試験データ生成手段１２０は経路計測最適化手段１３０に、経路計測最適化手段１３０は計測データ記憶手段１５０に、計測データ記憶手段１５０は経路評価手段１４０にそれぞれ接続されている。
【００４９】
クライアントからプロトコル、通信相手を指定した経路要求があった場合における各手段の機能は以下のとおりである。
【００５０】
計測データ交換手段１１０は、隣接するルータと、ネットワークの利用状態を示す帯域利用、パケット遅延時間、パケット廃棄率などの計測情報を交換する。
【００５１】
試験データ生成手段１２０は、最適経路に含まれていない利用率の低いリンクの最新状態を評価すべく、プロトコルに応じた試験データを生成する。試験データは、計測の起点となるルータ（例えば、ルータＡ）においては、パケット発送時におけるルータＡの内部時計の時刻となる。起点となるルータＡからパケット（例えば、パケットＡ）を受け取り、別のパケット（例えば、パケットＢ）を送り返すルータ（例えば、ルータＢ）では、
・パケットＡ受信時におけるルータＢの内部時計の時刻に加えて、
・｛（パケットＡ受信時にルータＢの内部時計が示す時刻）−（パケットＡ内のタイムスタンプの時刻）｝により算出される値
となる。詳細は後述する。
【００５２】
経路計測最適化手段１３０は、試験データを用いて利用率の低いリンクを再評価し、再評価結果に基づいて例えばダイクストラ法等により新たな最適経路を求める。ソースルーティングによってパスを指定する場合は、クライアント１０に最適経路を回答する。
【００５３】
経路評価手段１４０は、帯域幅，パケット遅延時間，パケット廃棄率などの経路特性に合ったトラフィック配分になっているかを評価し、必要に応じ経路を追加する。例えば、最適な経路と、それ以外の経路とのコスト差が小さい場合は、最適な経路だけを使っていては転送効率が悪いので、そのような場合には、２番目以下の経路も推薦経路とすべく経路を追加する。
【００５４】
図３は、本実施の形態にかかる経路最適化処理の流れを示すフローチャートである。同図に示すように、経路最適化処理においては、各リンクコストを取得し（ステップＳ１１０）、各ノードコストを算出し（ステップＳ１２０）、リンクコスト及びノードコストに基づいて経路（パス）コストを算出する（ステップＳ１３０）。そして、同一目的地へ到達する複数の経路の各コストを比較し（ステップＳ１４０）、所定条件を満たす場合に現在利用している経路（現行経路）よりコストが低い経路（候補経路）を新たな現行経路とする（ステップＳ１５０）。
【００５５】
図４は、ノードコスト算出処理の流れを示すフローチャートである。同図に示すように、各ノードのパケット遅延時間、パケット廃棄率を取得し（ステップＳ１２１）、取得したパケット遅延時間、パケット廃棄率及び所定の計算式に基づいて各ノードの遅延時間コスト、廃棄率コストを算出し（ステップＳ１２２）、算出された遅延時間コスト、廃棄率コスト及び記憶されている旧コストを合算して各ノードの新コストを算出する（ステップＳ１２３）。
【００５６】
図５は、経路変更処理の流れを示すフローチャートである。同図に示すように、現在利用している経路（現行経路）とそれよりコストが低い経路（候補経路）とを比較し（ステップＳ１５１）、候補経路コストと現行経路コストとの関係は経路変更条件を満たすかを調べ（ステップＳ１５２）、経路変更条件が満たされる場合は候補経路を新たな現行経路とする（ステップＳ１５３）。
【００５７】
＜ノードの計測＞
リンクコストの高さ（帯域が狭いなどの理由）から利用経路から外れたリンクの両端に繋がるノードにSNMPパケットを送って、ノードコストを計測する。
【００５８】
パケット遅延時間は、前記の如く、直接的方法でも間接的方法でも求めることができる。直接的方法又は間接的方法いずれの方法で求めても実用上問題ない精度が得られる。また、パケット廃棄率は、MIBから取得したり、ＣＰＵ使用率から推定したり、ＴＣＰアプリケーションによって計測したりすることができる。さらに、処理能力は、ルータ仕様や、ルータ機器に負荷試験を行った結果得られたデータから決定する。
【００５９】
図６は、パケット遅延時間、パケット廃棄率に基づいてノードコストを計測する例を説明するための図である。同図に示す例では、
遅延時間により加算されるノードコスト＝｛（遅延時間 − 100msec）／100msec ｝ × 100
とし、
パケット廃棄率により加算されるノードコスト＝（廃棄率 − 0.1 ） × 100
とする。
【００６０】
例えば、ルータＲ１の遅延時間が50msec、パケット廃棄率が0.1％の場合、
遅延時間により加算されるノードコスト
＝{(50msec−100msec)／100msec }×100
＝−50
パケット廃棄率により加算されるノードコスト
＝（0.1 − 0.1 ） × 100
＝０
であるから、新たなノードコストは、旧コスト「1」と遅延時間コスト「−50」と廃棄率コスト「０」とを加算して、「−49」となる。
【００６１】
同様に、ルータＲ２の旧コストが4、遅延時間が120msec、パケット廃棄率が0.4％の場合、
遅延時間により加算されるノードコスト＝20
パケット廃棄率により加算されるノードコスト＝30
であるから、新たなノードコストは、「54」となる。
【００６２】
同様に、ルータＲ３の旧コストが1、遅延時間が90msec、パケット廃棄率が0.3％の場合、
遅延時間により加算されるノードコスト＝−10
パケット廃棄率により加算されるノードコスト＝20
であるから、新たなノードコストは、「11」となる。
【００６３】
同様に、ルータＲ４の旧コストが2、遅延時間が30msec、パケット廃棄率が0.1％の場合、
遅延時間により加算されるノードコスト＝−70
パケット廃棄率により加算されるノードコスト＝0
であるから、新たなノードコストは、「−68」となる。
【００６４】
＜SNMPによるCPU使用率計測（直接的方法）＞
パケット遅延時間を計測する方法（直接的方法）の一例について説明する。
【００６５】
図７は、ルータのプライベートMIBにアクセスしてＣＰＵ使用率を計測する例を説明するための図である。同図に示すように、測定対象のOID(Object ID)７０１をダイレクトに指定する。プライベートMIBとは、全てのネットワーク機器が共通に持っているMIBではなく、装置固有のMIBを意味する。
【００６６】
例えば、Cisco（登録商標）社のプライベートMIBを、NetVital（登録商標）というソフトウェアで指定するときは、最後に.0を付加して指定（指定例：1.3.6.1.4.1.9.2.1.57.0）する。
【００６７】
例えば、ラスト5秒のCPU使用率は、1.3.6.1.4.1.9.2.1.56によって、ラスト1分のCPU使用率は、1.3.6.1.4.1.9.2.1.57によって指定することができる。そして、使用率35％、50％などの値を得ることができる。
【００６８】
ＣＰＵ使用率からパケット遅延時間を推定する方法について説明する。例えば、予めルータ負荷実験によりCPU使用率と遅延時間との相関を表す式を作成するか、ルータベンダーから取得した係数によりCPU使用率から遅延時間に変換する式を作成し、作成された式を用いてパケット遅延時間を推定する。
【００６９】
＜SNMPによるMIBエントリー計測（直接的方法）＞
パケット廃棄率を計測する方法（直接的方法）の一例について説明する。OIDとそれに対応するMIBエントリーの一例を示す。
【００７０】
[interfaces.ifTable.ifEntry] group
1.3.6.1.2.1.2.2.1.1 : ifIndex
1.3.6.1.2.1.2.2.1.2 : ifDescr
1.3.6.1.2.1.2.2.1.3 : ifType
1.3.6.1.2.1.2.2.1.7 : ifAdminStatus
1.3.6.1.2.1.2.2.1.8 : ifOperStatus
1.3.6.1.2.1.2.2.1.10 : ifInOctets
1.3.6.1.2.1.2.2.1.16 : ifOutOctets
1.3.6.1.2.1.2.2.1.11 : ifInUcastPkts
1.3.6.1.2.1.2.2.1.17 : ifOutUcastPkts
1.3.6.1.2.1.2.2.1.13 : ifInDiscards
1.3.6.1.2.1.2.2.1.19 : ifOutDiscards
1.3.6.1.2.1.2.2.1.14 : ifInErrors
1.3.6.1.2.1.2.2.1.20 : IfOutErrors
ifAdminStatusはポート管理状態、ifInUcastPktsは受信パケット数、ifOutUcastPktsは送信パケット数、ifInDiscardsは廃棄パケット数、ifInErrorsはエラーパケット数を意味する。下記式よりパケット廃棄率を求めることができる。
【００７１】
パケット廃棄率＝廃棄パケット数／受信パケット数
＜遅延時間の計測（間接的方法）＞
パケット遅延時間を計測する方法（間接的方法）の一例について説明する。ルータ間の遅延時間は、実際の転送時間から、標準の転送時間を差し引いた値となる。
【００７２】
図８は、パケット遅延時間計測方法（間接的方法）を説明するための図である。同図に示すように、ルータＡとルータＢとの間に直接リンクが存在する場合を考える。なお、ルータＡとルータＢとの間に他のルータを挟む場合も、同様に遅延時間を評価できる。ルータＡにコンピュータＡが接続されている。ルータＡの内部時計は、ルータＢの内部時計より2秒進んでいる。つまり、ルータＡの内部時計が12:00:02の時、ルータＢの内部時計は12:00:00である。
【００７３】
コンピュータＡが計測を要求するLSA(Link State Advertisement)パケットＰ１を生成する。パケットＰ１内のタイムスタンプは12:00:02とする。そして、パケットＰ１が発信されてから5秒後に、ルータＢがパケットＰ１を受信する。その時、ルータＢの内部時計は12:00:05とする。パケットＰ１内のタイムスタンプは12:00:02であるため、ルータＢの内部時計を基準とすると転送時間（転送に要した時間）は3秒と計測されてしまう。そして、ルータＢは、受信時刻が12:00:05で、転送時間の計測値が３秒であることを示すパケットＰ２を生成し、送信する。
【００７４】
ルータＡはパケットＰ２を受信する。その時、ルータＡの内部時計は12:00:14とする。パケットＰ２内のタイムスタンプは12:00:05であるため、ルータＡの内部時計を基準として転送時間を計ると転送時間は9秒となってしまう。
【００７５】
よって、コンピュータＡは、
・往路に３秒
・復路に9秒
と転送時間を評価してしまう。
【００７６】
しかし、全二重通信でなければ通信帯域を共有するので、往路と復路の転送時間はほぼ等しくなる。すなわち平均転送時間を12/2 = 6（秒）と評価することができる。そして、標準転送時間が5（秒）であれば、遅延時間は1（秒）と評価することができる。
【００７７】
＜パケット廃棄率の計測（間接的方法）＞
パケット廃棄率を計測する方法（間接的方法）の一例について説明する。TCP（Transmission Control Protocol）通信で到着したパケットのシーケンス番号を調べ、番号の跳躍があれば、パケットが廃棄されたことがわかる。なお、廃棄の原因は、遅延だけでなく、ノイズなどによるエラーの場合もある。
【００７８】
例えば、TCP通信ライブラリに、シーケンス番号を調べるルーチンを挿入し、通信の両端ノードで計測することにより、特定セッションのパケット廃棄率を調べることができる。そして、再計算するルート上の全てのノードを網羅するように選択した複数ルートを計測し、
｛１−（ルートの廃棄率）｝=｛１−（ルート上に存在する各ノードにおける廃棄率）｝の積
という関係が成立するから、ルート上のノード数と等しい数の連立一次方程式を作成し、同方程式を解くことによって各ノードのパケット廃棄率を求めることができる。具体的には、両辺の対数を取って、積の式から、和の式へ変換する。そして、特定のセッションのパケット廃棄率から、全体のセッションの廃棄率を推定する。
【００７９】
なお、TCP通信ではなく、ICMP通信を使う ping コマンドの結果から、パケット廃棄率を推定する方法を用いても良い。ただし、TCPプロトコルを使う一般セッションより高い優先度で処理される可能性あるため、TCPプロトコルを使う一般セッションよりもパケット廃棄率が低く推定される可能性がある。
【００８０】
図９（ａ）は各ノードのパケット廃棄率の一例を示す図である。同図に示すように、ルータＲ１の廃棄率は１％、ルータＲ２の廃棄率は３％、ルータＲ３の廃棄率は４％、ルータＲ４の廃棄率は２％、ルータＲ５の廃棄率は１％であるとする。
【００８１】
この場合、R1 →R2 →R3 →R5 という経路の廃棄率の計測結果は
1 −（1.00 − 0.01）×（1.00 − 0.03）× （1.00 − 0.04）×（1.00 − 0.01）
= 1 − 0.99 × 0.97 × 0.96 × 0.99 = 1 − 0.913 = 0.09
すなわち 9%となる。なお、図９（ａ）の例では、廃棄率を誇張するため、実際は0.1% 〜 0.4%程度の値を、1%〜4%と一桁上げている。
【００８２】
＜経路コスト再計算＞
各ノードの処理コストを更新し、経路コストを再計算する場合の一例を説明する。表３及び図９（ｂ）に、III-1で求めた値で各ノードの処理コストを更新した結果を示す。
【表３】
【００８３】
II-4 に掲げた3経路のコストを再評価してみる。
【００８４】
ルータＲ１→ルータＲ２→ルータＲ３→ルータＲ５の経路では、
ルータＲ１→ルータＲ２：−49＋23 +54 = 28
ルータＲ２→ルータＲ３： 54＋ 1 +11 = 66
ルータＲ３→ルータＲ５： 11＋12 + 4 = 27
であるから、経路コストは 28 + 66 + 27 = 121となる。
【００８５】
ルータＲ１→ルータＲ２→ルータＲ４→ルータＲ５の経路では、
ルータＲ１→ルータＲ２：−49 + 23 + 54 = 28
ルータＲ２→ルータＲ４： 54 + 12−68 =−2
ルータＲ４→ルータＲ５：−68 + 23 + 4 =−41
であるから、経路コストは 28−2−41 =−15となる。
【００８６】
ルータＲ１→ルータＲ４→ルータＲ５の経路では、
ルータＲ１→ルータＲ４：−49 + 23−68 =−94
ルータＲ４→ルータＲ５：−68 + 23 + 4 =−41
であるから、経路コストは−94−41 =−135となる。
【００８７】
再計算の結果 ルータＲ２→ルータＲ３を通過する経路コストが、他の経路コストを上回る結果となった。ルータの稼働レベルが変化した結果であり、負荷の高いルータＲ２を通過しない経路が優先される。
【００８８】
上記の如く、本実施例によれば、動的に変化するノードのコストを含めてリンクのコストを評価した上で、最適なルートを選択することが可能となる。
【図面の簡単な説明】
【００８９】
【図１】（ａ）はノード及びリンクからなる経路の一例であって、各リンクの通信速度を示し、（ｂ）は各リンクコストと各ノードコストとを示す図である。
【図２】実施の形態にかかる経路最適化システムにおけるルータのブロック構成図の一例である。
【図３】実施の形態にかかる経路最適化処理の流れを示すフローチャートである。
【図４】実施の形態にかかるノードコスト算出処理の流れを示すフローチャートである。
【図５】実施の形態にかかる経路変更処理の流れを示すフローチャートである。
【図６】パケット遅延時間、パケット廃棄率に基づいてノードコストを計測する例を説明するための図である。
【図７】ルータのプライベートMIBにアクセスしてＣＰＵ使用率を計測する例を説明するための図である。
【図８】パケット遅延時間計測方法（間接的方法）を説明するための図である。
【図９】（ａ）は各ノードの廃棄率を示し、（ｂ）は更新後の各リンクコストと各ノードコストとを示す図である。
【符号の説明】
【００９０】
１００…ルータ
１１０…計測データ交換手段
１２０…試験データ生成手段
１３０…経路計測最適化手段
１４０…経路評価手段
１５０…計測データ記憶手段
【技術分野】
【０００１】
本発明は、同一ノードに至る複数の経路が存在する場合に、最適な経路を選択するためのシステム、プログラム及び方法に関する。
【背景技術】
【０００２】
インターネットに代表されるオープンネットワークで通信経路を決定する場合、RIP(Routing Information Protocol)やOSPF(Open Shortest Path First)により経路が決定される。経路を動的に決定するには、OSPFが用いられることが多い。
【０００３】
OSPFは、隣接するルータ間の回線速度（帯域幅）に基づいて、ルータ間の通信コストを算出し、目的のノードに至るまでの通信コストの合計が最小となるよう経路を決定する。計算には、ダイクストラ法や、A*アルゴリズムが使われる。
【０００４】
このようにして決定される経路には、パケット遅延やパケット廃棄率などのネットワーク特性が反映されないため、VoIP(Voice over Internet Protocol)などの準リアルタイム通信には不適当な経路が割り当てられることがある。この現象を「２つの通信加入者間」の問題と位置づけて解決策を与えた技術が開示されている（例えば、特許文献１参照）。
【特許文献１】特開平９−１２１２２８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、既に開示されている技術は、２つの通信加入者間の問題に限定されており、ある経路の通信に関する評価属性が動的に変化することが考慮されていない。例えば、ベストの通信品質を提供できるセッション数が５０程度と見積もられる経路に、１００の通信セッションが流入した場合、最適と評価された経路に負荷が集中することで、全セッションに於いて通信品質劣化が懸念される。特に、１つのノードが複数の経路に含まれていると、ノードの評価を行わないことが欠点になる。
【課題を解決するための手段】
【０００６】
本発明の第１の特徴は、始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、始点ノードから第２ノードを経由して終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択するシステムであって、（１）始点ノードの始点ノードコスト、始点ノードと第１ノードとをつなぐ第１リンクの第１リンクコスト、第１ノードの第１ノードコスト、第１ノードと終点ノードとをつなぐ第２リンクの第２リンクコスト、及び終点ノードの終点ノードコスト、並びに始点ノードと第２ノードとをつなぐ第３リンクの第３リンクコスト、第２ノードの第２ノードコスト、及び第２ノードと終点ノードとをつなぐ第４リンクの第４リンクコスト、を記憶する記憶手段と、（２）始点ノードコスト、第１リンクコスト、第１ノードコスト、第２リンクコスト、及び終点ノードコストに基づいて算出される第１の経路コストと、始点ノードコスト、第３リンクコスト、第２ノードコスト、第４リンクコスト、及び終点ノードコストに基づいて算出される第２の経路コストとを比較し、コストが低い方の経路を選択することによって経路を最適化する経路計測最適化手段とを備えることにある。
【０００７】
本発明の第２の特徴は、各ノードにおけるパケット遅延時間及びパケット廃棄率に基づいて各ノードのノードコストを計算することにある。
【０００８】
本発明の第３の特徴は、各ノードのノードコストを再計算し、再計算によって得られた新たなノードコストに基づいて各経路コストを再計算し、再計算によって得られた新たな経路コストを比較して、経路変更の要否を判断することにある。
【発明の効果】
【０００９】
本発明の第１の特徴によれば、経路（パス）コストを、リンクのみに附加するのではなく、ノードに附加することによって、ノードが最も効率的に稼働する経路を選択することができる。
【００１０】
本発明の第２の特徴によれば、各ノードにおけるパケット遅延時間及びパケット廃棄率に基づいて算出されたノードコストに基づいて最適な経路を選択することができる。
【００１１】
本発明の第３の特徴によれば、所定時間毎に又は所定イベントをトリガーとして、ノードコストを再計算することによって最適な経路を動的に選択することができる。
【発明を実施するための最良の形態】
【００１２】
以下に図面に基づいて、本発明を実施するための最良の形態を説明する。なお、以下の説明は、単なる例示に過ぎず、本発明の技術的範囲は以下の説明に限定されるものではない。
【実施例】
【００１３】
ネットワークを抽象化して扱うために「グラフ理論」が援用される。ここでも、グラフ理論で登場するノード，リンク，パスなどの用語を以下の意味で使用する。
【００１４】
ノードとは、ルータ，ブリッジ，スイッチなどのネットワーク通信機器、さらには PCやサーバなどネットワークアドレスを持つネットワーク端末を含めることもある。
【００１５】
リンクとは、ノード間を結ぶ配線を指す。１つのリンクは、少なくとも物理的な１本の配線に実体として対応付けることができる。ネットワークをモデル化する場合、リンクの両端でノードに接するポートの生死や、通信バッファの状態までをリンクに含める場合がある。
【００１６】
リンクとノードで形成され、孤立点・枝分れ・ループを含まないグラフをパス（経路）と呼ぶ。パスには、始点となるノードと、終点となるノードがあり、始点から終点まで情報が流れる順路を示す。
【００１７】
「グラフ理論」でパスを評価する場合には、リンクのコストを足し合わせ比較するが、ノードのコストは評価されない。ノードは、0次元の点と見なされ、距離などのコスト値も0（ゼロ）として取り扱われる。
【００１８】
通常、ルータは、パケットのヘッダを読み取り、ルータ内に記憶されているルーティングテーブルを参照して、次のホップ先（次の転送先ルータ）を決定する。ルータが一定時間のうちに処理できるパケット量をルータの仕様から考慮し、経路決定の要因として計量モデルに組み入れる。
【００１９】
なお、パケットを生成し送信するノードがパケットの通過経路を指定するソースルーティングを用いることもできる。ソースルーティングを利用するとパケットを生成し送信するノードが明示的に経路を指定することができる。途中のすべての経路を指定する「ストリクトソースルーティング」といくつかの経路を通過することを指定し、それ以外は途中のルータに任せる「ルーズソースルーティング」のいずれでも利用することができる。
【００２０】
図１（ａ）にルータ及びリンクからなる経路の一例であって、各リンクの通信速度を示す。同図に示すように、各ルータ間の通信速度は以下のとおりとする。
【００２１】
ルータＲ１−ルータＲ２間： ６４Ｋｂｐｓ
ルータＲ２−ルータＲ３間：１．５Ｍｂｐｓ
ルータＲ１−ルータＲ４間： ６４Ｋｂｐｓ
ルータＲ２−ルータＲ４間：１２８Ｋｂｐｓ
ルータＲ３−ルータＲ５間：１２８Ｋｂｐｓ
ルータＲ４−ルータＲ５間： ６４Ｋｂｐｓ
ルータＲ３−ルータＲ６間： ６４Ｋｂｐｓ
そして、経路コストを、帯域の逆数に比例して付値する。１．５Ｍｂｐｓ を コスト 1 とすると、
ルータＲ１−ルータＲ２間：１．５Ｍｂｐｓ／ ６４Ｋｂｐｓ＝２３
ルータＲ１−ルータＲ４間：１．５Ｍｂｐｓ／ ６４Ｋｂｐｓ＝２３
ルータＲ４−ルータＲ５間：１．５Ｍｂｐｓ／ ６４Ｋｂｐｓ＝２３
ルータＲ３−ルータＲ６間：１．５Ｍｂｐｓ／ ６４Ｋｂｐｓ＝２３
ルータＲ２−ルータＲ３間：１．５Ｍｂｐｓ／１．５Ｍｂｐｓ＝ １
ルータＲ２−ルータＲ４間：１．５Ｍｂｐｓ／１２８Ｋｂｐｓ＝１２
ルータＲ３−ルータＲ５間：１．５Ｍｂｐｓ／１２８Ｋｂｐｓ＝１２
というコストになる。
【００２２】
平均パケット長を１０２４Ｂｙｔｅとすると、
６４Ｋｂｐｓ回線では８ｐｐｓ （Packet Per Second）
１．５Ｍｂｐｓ回線では１８３ｐｐｓ
のパケットを１秒間に転送できることになる。
【００２３】
ルータＲ２とルータＲ３の処理能力が２００ｐｐｓ であったならば、ルータＲ２→ルータＲ３が飽和している時にはルータＲ２とルータＲ３の処理限界に達している可能性がある。
【００２４】
従って、静的に経路を決める条件の下では、リンクのコストだけでは最適な経路を選べないことがある。
【００２５】
表１に、各ルータの処理能力の一例を示す。
【表１】
【００２６】
処理コスト係数を、ルータ処理能力の逆数に比例して付値する。経路コストは１８３ｐｐｓを基準コストと定義したので、これに近いルータＲ３の処理能力（２００ｐｐｓ）を基準コスト（コスト 1）とする。１８３ｐｐｓ≠２００ｐｐｓで、若干の違いはあるが、１８３ｐｐｓはパケットサイズを１０２４Ｂｙｔｅと仮定しての数値であるから、許容範囲とみなせる。
【００２７】
ルータＲ１、Ｒ５、Ｒ６：２００ｐｐｓ／ ５０ｐｐｓ＝４
ルータＲ２、Ｒ３ ：２００ｐｐｓ／２００ｐｐｓ＝１
ルータＲ４ ：２００ｐｐｓ／１００ｐｐｓ＝２
というコスト係数になる。コスト係数のまま仮コストとしたコスト行列を表２に示す。
【００２８】
表２から、リンクコストとノードコストを対比できる。
【表２】
【００２９】
図１（ｂ）に、各リンクコストと各ノードコストとを示す。
【００３０】
＜経路コスト計算＞
リンクの経路コストを、ノードの処理コストと統合し、計量評価する。コスト計算には、リンクコスト行列にダイクストラ法を適用する方式が、一般に用いられる。本方式では、ノードコストまで考慮に入れて総コストを計算するために、ノードベクトルを附加した行列に拡張する。なお、ルータ処理コストは、ルータの入口と、出口とで、それぞれ発生するものとする。
【００３１】
例えば、ルータＲ１→ルータＲ２→ルータＲ３→ルータＲ５の経路では、まずルータＲ１の出口のコストが「４」、ルータＲ１とルータＲ２との間のコストが「２３」、ルータＲ２の入口のコストが「１」となる。同様に、ルータＲ２の出口のコストが「１」、ルータＲ２とルータＲ３との間のコストが「１」、ルータＲ３の入口のコストが「１」となる。同様に、ルータＲ３の出口のコストが「１」、ルータＲ３とルータＲ５との間のコストが「１２」、ルータＲ５の入口のコストが「４」となる。
【００３２】
つまり、
ルータＲ１→ルータＲ２：4 +23 + 1 = 28
ルータＲ２→ルータＲ３：1 + 1 + 1 = 3
ルータＲ３→ルータＲ５：1 +12 + 4 = 17
であるから、総コストは 28 + 3 + 17 = 48となる。
【００３３】
同様に、ルータＲ１→ルータＲ２→ルータＲ４→ルータＲ５の経路では、
ルータＲ１→ルータＲ２：4 + 23 + 1 = 28
ルータＲ２→ルータＲ４：1 + 12 + 2 = 15
ルータＲ４→ルータＲ５：2 + 23 + 4 = 29
であるから、総コストは 28 + 15 + 29 = 72となる。
【００３４】
同様に、ルータＲ１→ルータＲ４→ルータＲ５の経路では、
ルータＲ１→ルータＲ４：4 + 23 +2 = 29
ルータＲ４→ルータＲ５：2 + 23 +4 = 29
であるから、総コストは29 + 29 = 58となる。
【００３５】
＜動的評価＞
［ルータＲ２→ルータＲ３］リンクを経由する経路と、そうでない経路との差は、最小で 58−48 = 10、最大で72−48 = 24である。従って、ルータの処理負荷に応じて、ルータＲ２とルータＲ３の処理コストが１０倍程度変化すれば、ボトルネックとなる懸念がある経路が動的に切り替わる。
【００３６】
処理コストが１０倍変化することは、ルータの平常時の負荷を、最大負荷の１／１０と見積もることに相当する。最大負荷をベースにした試算では、２００ｐｐｓを標準コストとしていたが、その１／１０の２０ｐｐｓを標準コストとすることで、各ルータのコストは以下のような変数を含む計算式で算出される。
【００３７】
ルータＲ１、Ｒ５、Ｒ６：
（２００ｐｐｓ／ ５０ｐｐｓ）×（Ｘｐｐｓ／ ２０ｐｐｓ）
ただし Ｘは、Ｒ１，Ｒ５，Ｒ６の処理負荷で ０≦Ｘ≦５０
ルータＲ２、Ｒ３ ：
（２００ｐｐｓ／２００ｐｐｓ）×（Ｙｐｐｓ／ ２０ｐｐｓ）
ただし Ｙは、Ｒ２，Ｒ３の処理負荷で ０≦Ｙ≦２００
ルータＲ４ ：
（２００ｐｐｓ／１００ｐｐｓ）×（Ｚｐｐｓ／ ２０ｐｐｓ）
ただし Ｚは、Ｒ４の処理負荷で ０≦Ｚ≦１００
というコスト式になる。
【００３８】
平常時のコストは、上記の式にそれぞれＸ＝Ｙ＝Ｚ＝２０を代入して
ルータＲ１、Ｒ５、Ｒ６：２００／ ５０＝４
ルータＲ２、Ｒ３ ：２００／２００＝１
ルータＲ４ ：２００／１００＝２
を得る。
【００３９】
すべてのルータの負荷が、仮に最大となったとすれば
ルータＲ１、Ｒ５、Ｒ６：（２００／ ５０）×（ ５０／２０）＝１０
ルータＲ２、Ｒ３ ：（２００／２００）×（２００／２０）＝１０
ルータＲ４ ：（２００／１００）×（１００／２０）＝１０
といずれも等しくなる。
【００４０】
本実施例では、各ノードのコストは、各ルータのパケット処理負荷を、基準となるルータのパケット処理性能（ｐｐｓ）で除して求めている。このようにして求めたノードコストは、リンクコストとは異なる比例尺度となるため、コスト係数によってノードコストとリンクコストの整合性を図っている。本実施例では、ノードコストの方に係数を乗じて調整した。
【００４１】
ルータの処理負荷を調べるには、直接的な方法と、間接的な方法とがある。直接的な方法とは、ルータ内部に処理負荷の変化が記録される場合に利用できる、ルータにネットワーク上の他の機器から当該ルータに「処理負荷」の問い合わせを行う方法である。
【００４２】
間接的な方法とは、試験パケットの転送依頼を送って、パケットの転送に要した遅延時間や、パケット損失率などから、負荷を推定する方法である。高性能ルータがあれば、そのルータを起点にして負荷試験を行うこともできる。
【００４３】
パケット遅延はＣＰＵ負荷と因果関係があるので、直接的な方法でＣＰＵ負荷を監視しノードコストの評価に反映させる。パケット遅延がある閾値を超えるとタイムアウトを引き起こし、パケットは廃棄される。パケット廃棄は、パケット再送（リトライ）の原因となる。パケット廃棄率は、一般のルータでは、ＳＮＭＰ(Simple Network Management Protocol)によりＭＩＢ(Management Information Base)エントリーを監視することによって評価することが可能である。
【００４４】
＜通信コスト評価＞
通信可能な経路候補を準リアルタイムに再計算する。リンクコストの再計算は任意とする。リンクコストの再計算は例えばOSPFに基づいて行うことができる。ノードコストは、ノードにおけるパケット遅延時間，パケット廃棄率を用いて評価する。
【００４５】
直接的方法では、パケット遅延時間はＣＰＵ利用率から推定し、パケット廃棄率はＭＩＢより取得する。
【００４６】
間接的方法では、パケット遅延時間は試験パケットで計測する。パケット廃棄率は、Socketライブラリを使ったカスタムアプリケーションを用いて、パケットヘッダに記されたパケット連番を参照し、番号の抜けをチェックすることで計算できる。例えば、パケット連番が 1から10000までの通信セッションで、10, 20, 30 の番号のパケットが受信側に届かなければ、廃棄率は3/10000 = 0.03（％）である。
【００４７】
図２に、本実施の形態にかかる経路最適化システムにおけるルータのブロック構成図の一例を示す。同図に示すように、ルータ１００は、計測データ交換手段１１０と、試験データ生成手段１２０と、経路計測最適化手段１３０と、経路評価手段１４０と、計測データ記憶手段１５０とを備える。
【００４８】
同図に示すように、計測データ交換手段１１０は計測データ記憶手段１５０に、試験データ生成手段１２０は経路計測最適化手段１３０に、経路計測最適化手段１３０は計測データ記憶手段１５０に、計測データ記憶手段１５０は経路評価手段１４０にそれぞれ接続されている。
【００４９】
クライアントからプロトコル、通信相手を指定した経路要求があった場合における各手段の機能は以下のとおりである。
【００５０】
計測データ交換手段１１０は、隣接するルータと、ネットワークの利用状態を示す帯域利用、パケット遅延時間、パケット廃棄率などの計測情報を交換する。
【００５１】
試験データ生成手段１２０は、最適経路に含まれていない利用率の低いリンクの最新状態を評価すべく、プロトコルに応じた試験データを生成する。試験データは、計測の起点となるルータ（例えば、ルータＡ）においては、パケット発送時におけるルータＡの内部時計の時刻となる。起点となるルータＡからパケット（例えば、パケットＡ）を受け取り、別のパケット（例えば、パケットＢ）を送り返すルータ（例えば、ルータＢ）では、
・パケットＡ受信時におけるルータＢの内部時計の時刻に加えて、
・｛（パケットＡ受信時にルータＢの内部時計が示す時刻）−（パケットＡ内のタイムスタンプの時刻）｝により算出される値
となる。詳細は後述する。
【００５２】
経路計測最適化手段１３０は、試験データを用いて利用率の低いリンクを再評価し、再評価結果に基づいて例えばダイクストラ法等により新たな最適経路を求める。ソースルーティングによってパスを指定する場合は、クライアント１０に最適経路を回答する。
【００５３】
経路評価手段１４０は、帯域幅，パケット遅延時間，パケット廃棄率などの経路特性に合ったトラフィック配分になっているかを評価し、必要に応じ経路を追加する。例えば、最適な経路と、それ以外の経路とのコスト差が小さい場合は、最適な経路だけを使っていては転送効率が悪いので、そのような場合には、２番目以下の経路も推薦経路とすべく経路を追加する。
【００５４】
図３は、本実施の形態にかかる経路最適化処理の流れを示すフローチャートである。同図に示すように、経路最適化処理においては、各リンクコストを取得し（ステップＳ１１０）、各ノードコストを算出し（ステップＳ１２０）、リンクコスト及びノードコストに基づいて経路（パス）コストを算出する（ステップＳ１３０）。そして、同一目的地へ到達する複数の経路の各コストを比較し（ステップＳ１４０）、所定条件を満たす場合に現在利用している経路（現行経路）よりコストが低い経路（候補経路）を新たな現行経路とする（ステップＳ１５０）。
【００５５】
図４は、ノードコスト算出処理の流れを示すフローチャートである。同図に示すように、各ノードのパケット遅延時間、パケット廃棄率を取得し（ステップＳ１２１）、取得したパケット遅延時間、パケット廃棄率及び所定の計算式に基づいて各ノードの遅延時間コスト、廃棄率コストを算出し（ステップＳ１２２）、算出された遅延時間コスト、廃棄率コスト及び記憶されている旧コストを合算して各ノードの新コストを算出する（ステップＳ１２３）。
【００５６】
図５は、経路変更処理の流れを示すフローチャートである。同図に示すように、現在利用している経路（現行経路）とそれよりコストが低い経路（候補経路）とを比較し（ステップＳ１５１）、候補経路コストと現行経路コストとの関係は経路変更条件を満たすかを調べ（ステップＳ１５２）、経路変更条件が満たされる場合は候補経路を新たな現行経路とする（ステップＳ１５３）。
【００５７】
＜ノードの計測＞
リンクコストの高さ（帯域が狭いなどの理由）から利用経路から外れたリンクの両端に繋がるノードにSNMPパケットを送って、ノードコストを計測する。
【００５８】
パケット遅延時間は、前記の如く、直接的方法でも間接的方法でも求めることができる。直接的方法又は間接的方法いずれの方法で求めても実用上問題ない精度が得られる。また、パケット廃棄率は、MIBから取得したり、ＣＰＵ使用率から推定したり、ＴＣＰアプリケーションによって計測したりすることができる。さらに、処理能力は、ルータ仕様や、ルータ機器に負荷試験を行った結果得られたデータから決定する。
【００５９】
図６は、パケット遅延時間、パケット廃棄率に基づいてノードコストを計測する例を説明するための図である。同図に示す例では、
遅延時間により加算されるノードコスト＝｛（遅延時間 − 100msec）／100msec ｝ × 100
とし、
パケット廃棄率により加算されるノードコスト＝（廃棄率 − 0.1 ） × 100
とする。
【００６０】
例えば、ルータＲ１の遅延時間が50msec、パケット廃棄率が0.1％の場合、
遅延時間により加算されるノードコスト
＝{(50msec−100msec)／100msec }×100
＝−50
パケット廃棄率により加算されるノードコスト
＝（0.1 − 0.1 ） × 100
＝０
であるから、新たなノードコストは、旧コスト「1」と遅延時間コスト「−50」と廃棄率コスト「０」とを加算して、「−49」となる。
【００６１】
同様に、ルータＲ２の旧コストが4、遅延時間が120msec、パケット廃棄率が0.4％の場合、
遅延時間により加算されるノードコスト＝20
パケット廃棄率により加算されるノードコスト＝30
であるから、新たなノードコストは、「54」となる。
【００６２】
同様に、ルータＲ３の旧コストが1、遅延時間が90msec、パケット廃棄率が0.3％の場合、
遅延時間により加算されるノードコスト＝−10
パケット廃棄率により加算されるノードコスト＝20
であるから、新たなノードコストは、「11」となる。
【００６３】
同様に、ルータＲ４の旧コストが2、遅延時間が30msec、パケット廃棄率が0.1％の場合、
遅延時間により加算されるノードコスト＝−70
パケット廃棄率により加算されるノードコスト＝0
であるから、新たなノードコストは、「−68」となる。
【００６４】
＜SNMPによるCPU使用率計測（直接的方法）＞
パケット遅延時間を計測する方法（直接的方法）の一例について説明する。
【００６５】
図７は、ルータのプライベートMIBにアクセスしてＣＰＵ使用率を計測する例を説明するための図である。同図に示すように、測定対象のOID(Object ID)７０１をダイレクトに指定する。プライベートMIBとは、全てのネットワーク機器が共通に持っているMIBではなく、装置固有のMIBを意味する。
【００６６】
例えば、Cisco（登録商標）社のプライベートMIBを、NetVital（登録商標）というソフトウェアで指定するときは、最後に.0を付加して指定（指定例：1.3.6.1.4.1.9.2.1.57.0）する。
【００６７】
例えば、ラスト5秒のCPU使用率は、1.3.6.1.4.1.9.2.1.56によって、ラスト1分のCPU使用率は、1.3.6.1.4.1.9.2.1.57によって指定することができる。そして、使用率35％、50％などの値を得ることができる。
【００６８】
ＣＰＵ使用率からパケット遅延時間を推定する方法について説明する。例えば、予めルータ負荷実験によりCPU使用率と遅延時間との相関を表す式を作成するか、ルータベンダーから取得した係数によりCPU使用率から遅延時間に変換する式を作成し、作成された式を用いてパケット遅延時間を推定する。
【００６９】
＜SNMPによるMIBエントリー計測（直接的方法）＞
パケット廃棄率を計測する方法（直接的方法）の一例について説明する。OIDとそれに対応するMIBエントリーの一例を示す。
【００７０】
[interfaces.ifTable.ifEntry] group
1.3.6.1.2.1.2.2.1.1 : ifIndex
1.3.6.1.2.1.2.2.1.2 : ifDescr
1.3.6.1.2.1.2.2.1.3 : ifType
1.3.6.1.2.1.2.2.1.7 : ifAdminStatus
1.3.6.1.2.1.2.2.1.8 : ifOperStatus
1.3.6.1.2.1.2.2.1.10 : ifInOctets
1.3.6.1.2.1.2.2.1.16 : ifOutOctets
1.3.6.1.2.1.2.2.1.11 : ifInUcastPkts
1.3.6.1.2.1.2.2.1.17 : ifOutUcastPkts
1.3.6.1.2.1.2.2.1.13 : ifInDiscards
1.3.6.1.2.1.2.2.1.19 : ifOutDiscards
1.3.6.1.2.1.2.2.1.14 : ifInErrors
1.3.6.1.2.1.2.2.1.20 : IfOutErrors
ifAdminStatusはポート管理状態、ifInUcastPktsは受信パケット数、ifOutUcastPktsは送信パケット数、ifInDiscardsは廃棄パケット数、ifInErrorsはエラーパケット数を意味する。下記式よりパケット廃棄率を求めることができる。
【００７１】
パケット廃棄率＝廃棄パケット数／受信パケット数
＜遅延時間の計測（間接的方法）＞
パケット遅延時間を計測する方法（間接的方法）の一例について説明する。ルータ間の遅延時間は、実際の転送時間から、標準の転送時間を差し引いた値となる。
【００７２】
図８は、パケット遅延時間計測方法（間接的方法）を説明するための図である。同図に示すように、ルータＡとルータＢとの間に直接リンクが存在する場合を考える。なお、ルータＡとルータＢとの間に他のルータを挟む場合も、同様に遅延時間を評価できる。ルータＡにコンピュータＡが接続されている。ルータＡの内部時計は、ルータＢの内部時計より2秒進んでいる。つまり、ルータＡの内部時計が12:00:02の時、ルータＢの内部時計は12:00:00である。
【００７３】
コンピュータＡが計測を要求するLSA(Link State Advertisement)パケットＰ１を生成する。パケットＰ１内のタイムスタンプは12:00:02とする。そして、パケットＰ１が発信されてから5秒後に、ルータＢがパケットＰ１を受信する。その時、ルータＢの内部時計は12:00:05とする。パケットＰ１内のタイムスタンプは12:00:02であるため、ルータＢの内部時計を基準とすると転送時間（転送に要した時間）は3秒と計測されてしまう。そして、ルータＢは、受信時刻が12:00:05で、転送時間の計測値が３秒であることを示すパケットＰ２を生成し、送信する。
【００７４】
ルータＡはパケットＰ２を受信する。その時、ルータＡの内部時計は12:00:14とする。パケットＰ２内のタイムスタンプは12:00:05であるため、ルータＡの内部時計を基準として転送時間を計ると転送時間は9秒となってしまう。
【００７５】
よって、コンピュータＡは、
・往路に３秒
・復路に9秒
と転送時間を評価してしまう。
【００７６】
しかし、全二重通信でなければ通信帯域を共有するので、往路と復路の転送時間はほぼ等しくなる。すなわち平均転送時間を12/2 = 6（秒）と評価することができる。そして、標準転送時間が5（秒）であれば、遅延時間は1（秒）と評価することができる。
【００７７】
＜パケット廃棄率の計測（間接的方法）＞
パケット廃棄率を計測する方法（間接的方法）の一例について説明する。TCP（Transmission Control Protocol）通信で到着したパケットのシーケンス番号を調べ、番号の跳躍があれば、パケットが廃棄されたことがわかる。なお、廃棄の原因は、遅延だけでなく、ノイズなどによるエラーの場合もある。
【００７８】
例えば、TCP通信ライブラリに、シーケンス番号を調べるルーチンを挿入し、通信の両端ノードで計測することにより、特定セッションのパケット廃棄率を調べることができる。そして、再計算するルート上の全てのノードを網羅するように選択した複数ルートを計測し、
｛１−（ルートの廃棄率）｝=｛１−（ルート上に存在する各ノードにおける廃棄率）｝の積
という関係が成立するから、ルート上のノード数と等しい数の連立一次方程式を作成し、同方程式を解くことによって各ノードのパケット廃棄率を求めることができる。具体的には、両辺の対数を取って、積の式から、和の式へ変換する。そして、特定のセッションのパケット廃棄率から、全体のセッションの廃棄率を推定する。
【００７９】
なお、TCP通信ではなく、ICMP通信を使う ping コマンドの結果から、パケット廃棄率を推定する方法を用いても良い。ただし、TCPプロトコルを使う一般セッションより高い優先度で処理される可能性あるため、TCPプロトコルを使う一般セッションよりもパケット廃棄率が低く推定される可能性がある。
【００８０】
図９（ａ）は各ノードのパケット廃棄率の一例を示す図である。同図に示すように、ルータＲ１の廃棄率は１％、ルータＲ２の廃棄率は３％、ルータＲ３の廃棄率は４％、ルータＲ４の廃棄率は２％、ルータＲ５の廃棄率は１％であるとする。
【００８１】
この場合、R1 →R2 →R3 →R5 という経路の廃棄率の計測結果は
1 −（1.00 − 0.01）×（1.00 − 0.03）× （1.00 − 0.04）×（1.00 − 0.01）
= 1 − 0.99 × 0.97 × 0.96 × 0.99 = 1 − 0.913 = 0.09
すなわち 9%となる。なお、図９（ａ）の例では、廃棄率を誇張するため、実際は0.1% 〜 0.4%程度の値を、1%〜4%と一桁上げている。
【００８２】
＜経路コスト再計算＞
各ノードの処理コストを更新し、経路コストを再計算する場合の一例を説明する。表３及び図９（ｂ）に、III-1で求めた値で各ノードの処理コストを更新した結果を示す。
【表３】
【００８３】
II-4 に掲げた3経路のコストを再評価してみる。
【００８４】
ルータＲ１→ルータＲ２→ルータＲ３→ルータＲ５の経路では、
ルータＲ１→ルータＲ２：−49＋23 +54 = 28
ルータＲ２→ルータＲ３： 54＋ 1 +11 = 66
ルータＲ３→ルータＲ５： 11＋12 + 4 = 27
であるから、経路コストは 28 + 66 + 27 = 121となる。
【００８５】
ルータＲ１→ルータＲ２→ルータＲ４→ルータＲ５の経路では、
ルータＲ１→ルータＲ２：−49 + 23 + 54 = 28
ルータＲ２→ルータＲ４： 54 + 12−68 =−2
ルータＲ４→ルータＲ５：−68 + 23 + 4 =−41
であるから、経路コストは 28−2−41 =−15となる。
【００８６】
ルータＲ１→ルータＲ４→ルータＲ５の経路では、
ルータＲ１→ルータＲ４：−49 + 23−68 =−94
ルータＲ４→ルータＲ５：−68 + 23 + 4 =−41
であるから、経路コストは−94−41 =−135となる。
【００８７】
再計算の結果 ルータＲ２→ルータＲ３を通過する経路コストが、他の経路コストを上回る結果となった。ルータの稼働レベルが変化した結果であり、負荷の高いルータＲ２を通過しない経路が優先される。
【００８８】
上記の如く、本実施例によれば、動的に変化するノードのコストを含めてリンクのコストを評価した上で、最適なルートを選択することが可能となる。
【図面の簡単な説明】
【００８９】
【図１】（ａ）はノード及びリンクからなる経路の一例であって、各リンクの通信速度を示し、（ｂ）は各リンクコストと各ノードコストとを示す図である。
【図２】実施の形態にかかる経路最適化システムにおけるルータのブロック構成図の一例である。
【図３】実施の形態にかかる経路最適化処理の流れを示すフローチャートである。
【図４】実施の形態にかかるノードコスト算出処理の流れを示すフローチャートである。
【図５】実施の形態にかかる経路変更処理の流れを示すフローチャートである。
【図６】パケット遅延時間、パケット廃棄率に基づいてノードコストを計測する例を説明するための図である。
【図７】ルータのプライベートMIBにアクセスしてＣＰＵ使用率を計測する例を説明するための図である。
【図８】パケット遅延時間計測方法（間接的方法）を説明するための図である。
【図９】（ａ）は各ノードの廃棄率を示し、（ｂ）は更新後の各リンクコストと各ノードコストとを示す図である。
【符号の説明】
【００９０】
１００…ルータ
１１０…計測データ交換手段
１２０…試験データ生成手段
１３０…経路計測最適化手段
１４０…経路評価手段
１５０…計測データ記憶手段
【特許請求の範囲】
【請求項１】
始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、前記始点ノードから第２ノードを経由して前記終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択するシステムであって、
前記始点ノードの始点ノードコスト、前記始点ノードと前記第１ノードとをつなぐ第１リンクの第１リンクコスト、前記第１ノードの第１ノードコスト、前記第１ノードと前記終点ノードとをつなぐ第２リンクの第２リンクコスト、及び前記終点ノードの終点ノードコスト、並びに
前記始点ノードと前記第２ノードとをつなぐ第３リンクの第３リンクコスト、前記第２ノードの第２ノードコスト、及び前記第２ノードと前記終点ノードとをつなぐ第４リンクの第４リンクコスト、を記憶する記憶手段と、
前記始点ノードコスト、前記第１リンクコスト、前記第１ノードコスト、前記第２リンクコスト、及び前記終点ノードコストに基づいて算出される第１の経路コストと、前記始点ノードコスト、前記第３リンクコスト、前記第２ノードコスト、前記第４リンクコスト、及び前記終点ノードコストに基づいて算出される第２の経路コストとを比較し、コストが低い方の経路を選択することによって経路を最適化する経路計測最適化手段と
を備えることを特徴とする経路最適化システム。
【請求項２】
各ノードにおけるパケット遅延時間及びパケット廃棄率に基づいて各ノードのノードコストを計算する請求項１に記載の経路最適化システム。
【請求項３】
各ノードのノードコストを再計算し、再計算によって得られた新たなノードコストに基づいて各経路コストを再計算し、再計算によって得られた新たな経路コストを比較して、経路変更の要否を判断する請求項１又は２に記載の経路最適化システム。
【請求項４】
始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、前記始点ノードから第２ノードを経由して前記終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択するプログラムであって、コンピュータを
前記始点ノードの始点ノードコスト、前記始点ノードと前記第１ノードとをつなぐ第１リンクの第１リンクコスト、前記第１ノードの第１ノードコスト、前記第１ノードと前記終点ノードとをつなぐ第２リンクの第２リンクコスト、及び前記終点ノードの終点ノードコスト、並びに
前記始点ノードと前記第２ノードとをつなぐ第３リンクの第３リンクコスト、前記第２ノードの第２ノードコスト、及び前記第２ノードと前記終点ノードとをつなぐ第４リンクの第４リンクコスト、を記憶する記憶手段、
前記始点ノードコスト、前記第１リンクコスト、前記第１ノードコスト、前記第２リンクコスト、及び前記終点ノードコストに基づいて算出される第１の経路コストと、前記始点ノードコスト、前記第３リンクコスト、前記第２ノードコスト、前記第４リンクコスト、及び前記終点ノードコストに基づいて算出される第２の経路コストとを比較し、低コストの経路を選択することによって経路を最適化する経路計測最適化手段
として機能させることを特徴とする経路最適化プログラム。
【請求項５】
始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、前記始点ノードから第２ノードを経由して前記終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択する方法であって、
記憶手段が、前記始点ノードの始点ノードコスト、前記始点ノードと前記第１ノードとをつなぐ第１リンクの第１リンクコスト、前記第１ノードの第１ノードコスト、前記第１ノードと前記終点ノードとをつなぐ第２リンクの第２リンクコスト、及び前記終点ノードの終点ノードコスト、並びに
前記始点ノードと前記第２ノードとをつなぐ第３リンクの第３リンクコスト、前記第２ノードの第２ノードコスト、及び前記第２ノードと前記終点ノードとをつなぐ第４リンクの第４リンクコストを記憶するステップと、
経路計測最適化手段が、前記始点ノードコスト、前記第１リンクコスト、前記第１ノードコスト、前記第２リンクコスト、及び前記終点ノードコストに基づいて算出される第１の経路コストと、前記始点ノードコスト、前記第３リンクコスト、前記第２ノードコスト、前記第４リンクコスト、及び前記終点ノードコストに基づいて算出される第２の経路コストとを比較し、低コストの経路を選択することによって経路を最適化するステップと
を含むことを特徴とする経路最適化方法。
【請求項１】
始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、前記始点ノードから第２ノードを経由して前記終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択するシステムであって、
前記始点ノードの始点ノードコスト、前記始点ノードと前記第１ノードとをつなぐ第１リンクの第１リンクコスト、前記第１ノードの第１ノードコスト、前記第１ノードと前記終点ノードとをつなぐ第２リンクの第２リンクコスト、及び前記終点ノードの終点ノードコスト、並びに
前記始点ノードと前記第２ノードとをつなぐ第３リンクの第３リンクコスト、前記第２ノードの第２ノードコスト、及び前記第２ノードと前記終点ノードとをつなぐ第４リンクの第４リンクコスト、を記憶する記憶手段と、
前記始点ノードコスト、前記第１リンクコスト、前記第１ノードコスト、前記第２リンクコスト、及び前記終点ノードコストに基づいて算出される第１の経路コストと、前記始点ノードコスト、前記第３リンクコスト、前記第２ノードコスト、前記第４リンクコスト、及び前記終点ノードコストに基づいて算出される第２の経路コストとを比較し、コストが低い方の経路を選択することによって経路を最適化する経路計測最適化手段と
を備えることを特徴とする経路最適化システム。
【請求項２】
各ノードにおけるパケット遅延時間及びパケット廃棄率に基づいて各ノードのノードコストを計算する請求項１に記載の経路最適化システム。
【請求項３】
各ノードのノードコストを再計算し、再計算によって得られた新たなノードコストに基づいて各経路コストを再計算し、再計算によって得られた新たな経路コストを比較して、経路変更の要否を判断する請求項１又は２に記載の経路最適化システム。
【請求項４】
始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、前記始点ノードから第２ノードを経由して前記終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択するプログラムであって、コンピュータを
前記始点ノードの始点ノードコスト、前記始点ノードと前記第１ノードとをつなぐ第１リンクの第１リンクコスト、前記第１ノードの第１ノードコスト、前記第１ノードと前記終点ノードとをつなぐ第２リンクの第２リンクコスト、及び前記終点ノードの終点ノードコスト、並びに
前記始点ノードと前記第２ノードとをつなぐ第３リンクの第３リンクコスト、前記第２ノードの第２ノードコスト、及び前記第２ノードと前記終点ノードとをつなぐ第４リンクの第４リンクコスト、を記憶する記憶手段、
前記始点ノードコスト、前記第１リンクコスト、前記第１ノードコスト、前記第２リンクコスト、及び前記終点ノードコストに基づいて算出される第１の経路コストと、前記始点ノードコスト、前記第３リンクコスト、前記第２ノードコスト、前記第４リンクコスト、及び前記終点ノードコストに基づいて算出される第２の経路コストとを比較し、低コストの経路を選択することによって経路を最適化する経路計測最適化手段
として機能させることを特徴とする経路最適化プログラム。
【請求項５】
始点ノードから第１ノードを経由して終点ノードへ至る第１経路と、前記始点ノードから第２ノードを経由して前記終点ノードへ至る第２経路とを含むマルチノードネットワークにおいて最適な経路を選択する方法であって、
記憶手段が、前記始点ノードの始点ノードコスト、前記始点ノードと前記第１ノードとをつなぐ第１リンクの第１リンクコスト、前記第１ノードの第１ノードコスト、前記第１ノードと前記終点ノードとをつなぐ第２リンクの第２リンクコスト、及び前記終点ノードの終点ノードコスト、並びに
前記始点ノードと前記第２ノードとをつなぐ第３リンクの第３リンクコスト、前記第２ノードの第２ノードコスト、及び前記第２ノードと前記終点ノードとをつなぐ第４リンクの第４リンクコストを記憶するステップと、
経路計測最適化手段が、前記始点ノードコスト、前記第１リンクコスト、前記第１ノードコスト、前記第２リンクコスト、及び前記終点ノードコストに基づいて算出される第１の経路コストと、前記始点ノードコスト、前記第３リンクコスト、前記第２ノードコスト、前記第４リンクコスト、及び前記終点ノードコストに基づいて算出される第２の経路コストとを比較し、低コストの経路を選択することによって経路を最適化するステップと
を含むことを特徴とする経路最適化方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００６−２３７８３７（Ｐ２００６−２３７８３７Ａ）
【公開日】平成１８年９月７日（２００６．９．７）
【国際特許分類】
【出願番号】特願２００５−４７３５６（Ｐ２００５−４７３５６）
【出願日】平成１７年２月２３日（２００５．２．２３）
【出願人】（０００１５５４６９）株式会社野村総合研究所 (1,067)
【Ｆターム（参考）】
【公開日】平成１８年９月７日（２００６．９．７）
【国際特許分類】
【出願日】平成１７年２月２３日（２００５．２．２３）
【出願人】（０００１５５４６９）株式会社野村総合研究所 (1,067)
【Ｆターム（参考）】
[ Back to top ]