(57)【要約】【課題】通信ネットワークにおけるボトルネック箇所を回避し、なおかつ少ないホップ数で到達可能な経路を少ない計算量で導出する最適経路計算方法を提供する。【解決手段】経路を決定するための評価基準として、決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に、前記決定済みの経路から評価対象となる経路までのホップ数を乗算した値を用いることにより、ホップ数の要素を加味しているため、ボトルネックを回避した場合でも、ホップ数の増加を抑制できる。【選択図】　　　　図１
2004023473.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算方法であって、
経路を決定するための評価基準として、
決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に、前記決定済みの経路から評価対象となる経路までのホップ数を乗算した値を用いることを特徴とする最適経路計算方法。
【請求項２】
複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算方法であって、
経路を決定するための評価基準として、
決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に係数α（αは１以上の任意の正数）を乗算した値と、
前記決定済みの経路から評価対象となる経路までのホップ数を乗算した値に計数β（βは１以上の任意の正数）を乗算した値と、
を加算した加算値を用いることを特徴とする最適経路計算方法。
【請求項３】
複数の装置と、これらの装置を接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算方法であって、
経路が未決定の装置の中で評価値Ｃ（ｕ）が最小の装置ｖを選択する評価値最小装置選択工程と、
経路決定済みの装置群から前記装置ｖへ至る経路を決定する経路決定工程と、
前記経路決定工程により経路が決定した前記装置ｖを経路決定済みの装置群に登録する経路決定済み装置登録工程と、
経路未決定の装置のうち、装置ｖと直接伝送路で接続された、装置ｖに隣接する装置ｕについて、評価値Ｃ（ｕ）を算出する評価値算出工程と、
のループ処理により目的地までの経路を決定し、
前記評価値算出工程は、
出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする最大コスト算出工程と、
前記最大コスト算出工程で得られた最大コストと、出発点から装置ｕまでの経路におけるホップ数の値とを乗算し、装置ｕの評価値を得る評価値計算工程と、
装置ｕの評価値が既に算出済みであった場合に、該評価値と前記評価値計算工程で得られた評価値とを比較し、前記評価値計算工程で得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する評価値更新工程と、
を有することを特徴とする最適経路計算方法。
【請求項４】
複数の装置と、これらの装置を接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算方法であって、
経路が未決定の装置の中で評価値Ｃ（ｕ）が最小の装置ｖを選択する評価値最小装置選択工程と、
経路決定済みの装置群から前記装置ｖへ至る経路を決定する経路決定工程と、
前記経路決定工程により経路が決定した前記装置ｖを経路決定済みの装置群に登録する経路決定済み装置登録工程と、
経路未決定の装置のうち、装置ｖと直接伝送路で接続された、装置ｖに隣接する装置ｕについて、評価値Ｃ（ｕ）を算出する評価値算出工程と、
のループ処理により目的地までの経路を決定し、
前記評価値算出工程は、
出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする最大コスト算出工程と、
前記最大コスト算出工程で得られた最大コストに係数α（αは１以上の任意の正数）を乗算した値と、出発点から装置ｕまでの経路におけるホップ数に係数β（βは１以上の任意の正数）を乗算した値とを加算し、装置ｕの評価値を得る評価値計算工程と、
装置ｕの評価値が既に算出済みであった場合に、該評価値と前記評価値計算工程で得られた評価値とを比較し、前記評価値計算工程で得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する評価値更新工程と、
を有することを特徴とする最適経路計算方法。
【請求項５】
複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算プログラムであって、
経路を決定するための評価基準として、
決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に、前記決定済みの経路から評価対象となる経路までのホップ数を乗算した値を用いることを特徴とする最適経路計算プログラム。
【請求項６】
複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算プログラムであって、
経路を決定するための評価基準として、
決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に係数α（αは１以上の任意の正数）を乗算した値と、
前記決定済みの経路から評価対象となる経路までのホップ数を乗算した値に計数β（βは１以上の任意の正数）を乗算した値と、
を加算した加算値を用いることを特徴とする最適経路計算プログラム。
【請求項７】
複数の装置と、これらの装置を接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算プログラムであって、
経路が未決定の装置の中で評価値Ｃ（ｕ）が最小の装置ｖを選択する評価値最小装置選択処理と、
経路決定済みの装置群から前記装置ｖへ至る経路を決定する経路決定処理と、
前記経路決定処理により経路が決定した前記装置ｖを経路決定済みの装置群に登録する経路決定済み装置登録処理と、
経路未決定の装置のうち、装置ｖと直接伝送路で接続された、装置ｖに隣接する装置ｕについて、評価値Ｃ（ｕ）を算出する評価値算出処理と、
のループ処理により目的地までの経路を決定し、
前記評価値算出処理は、
出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする最大コスト算出処理と、
前記最大コスト算出工程で得られた最大コストと、出発点から装置ｕまでの経路におけるホップ数の値とを乗算し、装置ｕの評価値を得る評価値計算処理と、
装置ｕの評価値が既に算出済みであった場合に、該評価値と前記評価値計算処理で得られた評価値とを比較し、前記評価値計算処理で得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する評価値更新処理と、
を有することを特徴とする最適経路計算プログラム。
【請求項８】
複数の装置と、これらの装置を接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算プログラムであって、
経路が未決定の装置の中で評価値Ｃ（ｕ）が最小の装置ｖを選択する評価値最小装置選択処理と、
経路決定済みの装置群から前記装置ｖへ至る経路を決定する経路決定処理と、
前記経路決定処理により経路が決定した前記装置ｖを経路決定済みの装置群に登録する経路決定済み装置登録処理と、
経路未決定の装置のうち、装置ｖと直接伝送路で接続された、装置ｖに隣接する装置ｕについて、評価値Ｃ（ｕ）を算出する評価値算出処理と、
のループ処理により目的地までの経路を決定し、
前記評価値算出処理は、
出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする最大コスト算出処理と、
前記最大コスト算出工程で得られた最大コストに係数α（αは１以上の任意の正数）を乗算した値と、出発点から装置ｕまでの経路におけるホップ数に係数β（βは１以上の任意の正数）を乗算した値とを加算し、装置ｕの評価値を得る評価値計算処理と、
装置ｕの評価値が既に算出済みであった場合に、該評価値と前記評価値計算工程で得られた評価値とを比較し、前記評価値計算工程で得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する評価値更新処理と、
を有することを特徴とする最適経路計算プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信ネットワークにおけるボトルネック箇所を回避し、なおかつ少ないホップ数で到達可能な経路を、少ない計算量で導出する最適経路計算方法、及び最適経路計算プログラムに関する。
【０００２】
【従来の技術】
従来の代表的な経路計算アルゴリズムとして、ダイクストラ法がある。これは、経路における各リンクのコストの合計を評価値として、これが最小となる経路を選択るものである。このダイクストラ法は、経路計算時間が最も短い計算方法として広く用いられている。
【０００３】
しかしダイクストラ法は、ネットワーク中のトラフィックのボトルネックとなる、コストが極端に大きいリンクを経由した経路を選択する可能性がある。これは、経路選択の評価値にコストの合計値を用いるため、コストの極端に大きいリンクが含まれていても、合成すると相殺されてしまう可能性があるためである。
【０００４】
このような不具合を解消するためのシステムの一例が、特開２００１−２４４９７４号公報の経路計算方法に開示されている。この従来例は、端末装置と、中継装置と、これらの装置を相互に接続する複数のリンクとから構成されるコネクションレス型通信ネットワークであって、各リンクに経路選択のためのパラメータ（コスト）が付与されている場合に、通信ネットワーク内の任意の端末装置から任意の端末装置へ向かう経路を計算するとき、これら端末装置間を接続する複数の経路のうち、１経路に含まれる各リンクの最小コストが最大となる経路を計算することを特徴としている。
【０００５】
【発明が解決しようとする課題】
しかしながら、上述した特開２００１−２４４９７４号公報に開示された経路計算方法では、ボトルネックとなるリンクは回避できるが、コストの加算を行わないため、ホップ数が極端に多い経路が選択される可能性がある。ネットワークにおいてホップ数の増加は、転送遅延等の増大を招く可能性がある。
【０００６】
本発明は上記事情に鑑みてなされたものであり、通信ネットワークにおけるボトルネック箇所を回避し、なおかつ少ないホップ数で到達可能な経路を少ない計算量で導出する最適経路計算方法、及び最適経路計算プログラムを提供することを目的とする。
【０００７】
【課題を解決するための手段】
係る目的を達成するために請求項１記載の発明は、複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算方法であって、経路を決定するための評価基準として、決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に、決定済みの経路から評価対象となる経路までのホップ数を乗算した値を用いることを特徴とする。
【０００８】
請求項２記載の発明は、複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算方法であって、経路を決定するための評価基準として、決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に係数α（αは１以上の任意の正数）を乗算した値と、決定済みの経路から評価対象となる経路までのホップ数を乗算した値に計数β（βは１以上の任意の正数）を乗算した値と、を加算した加算値を用いることを特徴とする。
【０００９】
請求項３記載の発明は、複数の装置と、これらの装置を接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算方法であって、経路が未決定の装置の中で評価値Ｃ（ｕ）が最小の装置ｖを選択する評価値最小装置選択工程と、経路決定済みの装置群から装置ｖへ至る経路を決定する経路決定工程と、経路決定工程により経路が決定した装置ｖを経路決定済みの装置群に登録する経路決定済み装置登録工程と、経路未決定の装置のうち、装置ｖと直接伝送路で接続された、装置ｖに隣接する装置ｕについて、評価値Ｃ（ｕ）を算出する評価値算出工程と、のループ処理により目的地までの経路を決定し、評価値算出工程は、出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする最大コスト算出工程と、最大コスト算出工程で得られた最大コストと、出発点から装置ｕまでの経路におけるホップ数の値とを乗算し、装置ｕの評価値を得る評価値計算工程と、装置ｕの評価値が既に算出済みであった場合に、該評価値と評価値計算工程で得られた評価値とを比較し、評価値計算工程で得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する評価値更新工程と、を有することを特徴とする。
【００１０】
請求項４記載の発明は、複数の装置と、これらの装置を接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算方法であって、経路が未決定の装置の中で評価値Ｃ（ｕ）が最小の装置ｖを選択する評価値最小装置選択工程と、経路決定済みの装置群から装置ｖへ至る経路を決定する経路決定工程と、経路決定工程により経路が決定した装置ｖを経路決定済みの装置群に登録する経路決定済み装置登録工程と、経路未決定の装置のうち、装置ｖと直接伝送路で接続された、装置ｖに隣接する装置ｕについて、評価値Ｃ（ｕ）を算出する評価値算出工程と、のループ処理により目的地までの経路を決定し、評価値算出工程は、出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする最大コスト算出工程と、最大コスト算出工程で得られた最大コストに係数α（αは１以上の任意の正数）を乗算した値と、出発点から装置ｕまでの経路におけるホップ数に係数β（βは１以上の任意の正数）を乗算した値とを加算し、装置ｕの評価値を得る評価値計算工程と、装置ｕの評価値が既に算出済みであった場合に、該評価値と評価値計算工程で得られた評価値とを比較し、評価値計算工程で得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する評価値更新工程と、を有することを特徴とする。
【００１１】
請求項５記載の発明は、複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算プログラムであって、経路を決定するための評価基準として、決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に、決定済みの経路から評価対象となる経路までのホップ数を乗算した値を用いることを特徴とする。
【００１２】
請求項６記載の発明は、複数のノードと、これらのノードを接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算プログラムであって、経路を決定するための評価基準として、決定済みの経路と、評価対象となる経路とに含まれる各伝送路のコストの最大値に係数α（αは１以上の任意の正数）を乗算した値と、決定済みの経路から評価対象となる経路までのホップ数を乗算した値に計数β（βは１以上の任意の正数）を乗算した値と、を加算した加算値を用いることを特徴とする。
【００１３】
請求項７記載の発明は、複数の装置と、これらの装置を接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算プログラムであって、経路が未決定の装置の中で評価値Ｃ（ｕ）が最小の装置ｖを選択する評価値最小装置選択処理と、経路決定済みの装置群から装置ｖへ至る経路を決定する経路決定処理と、経路決定処理により経路が決定した装置ｖを経路決定済みの装置群に登録する経路決定済み装置登録処理と、経路未決定の装置のうち、装置ｖと直接伝送路で接続された、装置ｖに隣接する装置ｕについて、評価値Ｃ（ｕ）を算出する評価値算出処理と、のループ処理により目的地までの経路を決定し、評価値算出処理は、出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする最大コスト算出処理と、最大コスト算出工程で得られた最大コストと、出発点から装置ｕまでの経路におけるホップ数の値とを乗算し、装置ｕの評価値を得る評価値計算処理と、装置ｕの評価値が既に算出済みであった場合に、該評価値と評価値計算処理で得られた評価値とを比較し、評価値計算処理で得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する評価値更新処理と、を有することを特徴とする。
【００１４】
請求項８記載の発明は、複数の装置と、これらの装置を接続する複数の伝送路を備え、それぞれの伝送路にコストが定義されたネットワークにおいて最適な経路を計算する最適経路計算プログラムであって、経路が未決定の装置の中で評価値Ｃ（ｕ）が最小の装置ｖを選択する評価値最小装置選択処理と、経路決定済みの装置群から装置ｖへ至る経路を決定する経路決定処理と、経路決定処理により経路が決定した装置ｖを経路決定済みの装置群に登録する経路決定済み装置登録処理と、経路未決定の装置のうち、装置ｖと直接伝送路で接続された、装置ｖに隣接する装置ｕについて、評価値Ｃ（ｕ）を算出する評価値算出処理と、のループ処理により目的地までの経路を決定し、評価値算出処理は、出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする最大コスト算出処理と、最大コスト算出工程で得られた最大コストに係数α（αは１以上の任意の正数）を乗算した値と、出発点から装置ｕまでの経路におけるホップ数に係数β（βは１以上の任意の正数）を乗算した値とを加算し、装置ｕの評価値を得る評価値計算処理と、装置ｕの評価値が既に算出済みであった場合に、該評価値と評価値計算工程で得られた評価値とを比較し、評価値計算工程で得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する評価値更新処理と、を有することを特徴とする。
【００１５】
【発明の実施の形態】
次に、添付図面を参照しながら本発明の最適経路計算方法、最適経路計算プログラムに係る実施の形態を詳細に説明する。
【００１６】
本発明に係る実施形態のアルゴリズムを以下に示す。このアルゴリズムによって、ネットワークにおけるある装置を出発点とした時の、ネットワーク中の他の装置への経路が計算される。
【００１７】
まず、計算開始時、各パラメータを初期化する。すなわち、
・出発点から自身までの経路が決定した装置を示すパラメータは、「なし」。
・出発点から自身までの経路が未決定の装置を示すパラメータは、「すべての装置」。
・出発点となる装置の評価値を示すパラメータは０とする。それ以外の装置の評価値を示すパラメータは全て無限大とする。
【００１８】
なお、パラメータには、以下に示すものがある。
・出発点からの経路が決定した装置を示すパラメータ
（出発点から自身までの経路が決定した装置の集合を示すパラメータ）
・出発点からの経路が未決定の装置を示すパラメータ
（出発点から自身までの経路が未決定の装置の集合を示すパラメータ）
・決定経路を示すパラメータ
（計算の結果決定した、出発点から各装置までの経路を示すパラメータ）
・評価値を示すパラメータ
（各装置にそれぞれ付与されて、経路選択の際に比較対象となる。評価値が小さい装置が次の経路として選択される）
【００１９】
次に、経路計算のためのループ処理を実行する。一回ループを実行するごとに、ひとつずつ経路が求まっていき、全ての装置について、経路が計算されるまでループを繰り返す。ループ処理の内容は下記の通りである。
１．経路が未決定の装置の中で評価値が最小の装置ｖを選択する。
２．経路決定済の装置群から装置ｖへ至る経路を決定経路とする。
３．装置ｖを経路決定済の装置に加える。
４．経路未決定の装置のうち、装置ｖに隣接する（各）装置ｕについて、それぞれ評価値Ｃ（ｕ）を計算する。
【００２０】
また、評価値の計算手順は下記の通りである。
ａ：出発点から装置ｖまでの経路にあるリンク中での最大コストの値と、装置ｖ−装置ｕ間のリンクのコストを比較して大きい方をとり、出発点から装置ｕまでの経路における最大コストとする。
ｂ：ａで得られた最大コストと、出発点から装置ｕまでの経路におけるホップ数の値を乗算し、装置ｕの評価値を得る。
ｃ：ｂで得られた評価値と、ループ一回前の同装置の評価値とを比較する。ｂで得られた評価値の方が小さければ、これを装置ｕの新たな評価値Ｃ（ｕ）として更新する。ループ前の評価値のほうが小さければ、評価値は更新しない。
【００２１】
上記のｂにおいて、
評価値Ｃ＝（経路に含まれる各リンクのコスト中の最大値）×（この経路におけるホップ数）
とすることで、経路中の最大コストとホップ数の双方を同時に抑制した経路選択を行うことが可能となる。
【００２２】
次に、上記アルゴリズムに基づき、図１のネットワークにおける経路計算手順を図２に示されたフローチャートを参照しながら説明する。なお、図１に示されたシステムで、Ａ、Ｂは端末装置、１〜８はパケットの転送を行う中継装置であり、各装置間を結ぶリンクが直線で示されている。端末装置から送出されたパケットは、中継装置１〜８およびリンクを経由して順次転送される。各リンクには、コストが設定されており、この数値に基づいて経路が計算される。コストが極端に大きいリンクは通信ネットワークにおいてボトルネックと見なされる。
【００２３】
図１に示されたネットワークにおける各リンクのコストを表１に示す。
【００２４】
【表１】
2004023473.tif 000003
【００２５】
表１より、装置Ａ−装置６間のリンクと、装置６−装置７間のリンクが、相対的に大きな値となっており、これらのリンクがボトルネックとなり得る。
【００２６】
以下に、図１のネットワークに本アルゴリズムを適用し、端末装置Ａを出発点とした経路計算を実行する際の手順を説明する。計算開始時、各パラメータは初期化されて、表２の値となる（ステップＳ１）。
【００２７】
【表２】
2004023473.tif 000004
【００２８】
すなわち、
・経路が決定した装置は「なし」となる。
・経路が未決定の装置は、すべての装置Ａ，１，２，３，４，５，６，７，８，Ｂとなる。
・経路計算の出発点となる装置Ａの評価値Ｃ（Ａ）は０に初期化され、それ以外の装置ｖの評価値Ｃ（ｖ）は全て無限大に初期化される。
【００２９】
次に、経路を計算する１回目のループ処理に入る。経路が決定していない装置（すなわち全ての装置）の中で評価値が最小の装置を選択する（ステップＳ３）。この場合、装置Ａの評価値が０で最小となるため、装置Ａを選択する。Ａ→Ａの経路にはリンクがないので、この段階では決定経路はまだ存在しない。装置Ａを経路決定済の装置とする（ステップＳ５）。
【００３０】
次に、経路が未決定の装置（Ａ以外の装置）のうち、Ａに隣接する装置（１，６，７）について、それぞれ評価値Ｃを求める。
【００３１】
まず、装置１の評価値を計算する。装置Ａまでの経路におけるリンクのうち最大コストは０、装置Ａ−装置１間のリンクのコストは１であるので、装置Ａから装置１までの経路における最大コストは１である（ステップＳ６）。また、この経路において装置Ａから装置１へのホップ数は１であるので、最大コストとホップ数を乗算して装置１の評価値＝１を得る（ステップＳ７）。これは表２における現段階での評価値＝∞より小さいため（ステップＳ８／ＹＥＳ）、これを採用し、Ｃ｛１←（Ａ）｝＝１に更新する（ステップＳ９）。なお、｛１←（Ａ）｝は、Ａから１に至る経路の評価値であることを示す。
【００３２】
次に装置６の評価値を計算する。装置Ａまでの経路におけるリンクのうち最大コストは０、装置Ａ−装置６間のリンクのコストは７であるので、装置Ａから装置６までの経路における最大コストは７である（ステップＳ６）。また、この経路において装置Ａから装置６へのホップ数は１であるので、最大コストとホップ数を乗算して装置６の評価値＝７を得る（ステップＳ７）。これは表２における現段階での評価値＝∞より小さいため（ステップＳ８／ＹＥＳ）、これを採用し、Ｃ｛６←（Ａ）｝＝７に更新する（ステップＳ９）。
【００３３】
さらに装置７の評価値を計算する。装置Ａまでの経路におけるリンクのうち最大コストは０、装置Ａ−装置７間のリンクのコストは３であるので、装置Ａから装置７までの経路における最大コストは３である（ステップＳ６）。また、この経路において装置Ａから装置７へのホップ数は１であるので、最大コストとホップ数を乗算して装置７の評価値＝３を得る（ステップＳ７）。これは表２における現段階での評価値＝∞より小さいため（ステップＳ８／ＹＥＳ）、これを採用し、Ｃ｛７←（Ａ）｝＝３に更新する（ステップＳ９）。この結果、各パラメータと経路の状態は表３のようになる。
【００３４】
【表３】
2004023473.tif 000005
【００３５】
次に２回目のループ処理を実行する。経路が未決定の装置（すなわちＡ以外の装置）のうち、評価値が最小の装置を選択すると、Ｃ（１）＝１なので装置１を選択する（ステップＳ３）。Ａ→１の経路を決定経路とし（ステップＳ４）、装置１を経路決定済の装置とする（ステップＳ５）。残りの装置（Ａ，１以外の装置）のうち、装置１に隣接する装置（この場合装置２のみ）について、評価値Ｃを計算する。
【００３６】
装置１までの経路におけるリンクのうち最大コストは１、装置１−装置２間のリンクのコストは２であるので、装置Ａから装置２までの経路における最大コストは２となる（ステップＳ６）。また、この経路において装置Ａから装置２へのホップ数は２であるので、最大コストとホップ数を乗算して装置２の評価値＝４を得る（ステップＳ７）。これは表３における現段階での評価値＝∞より小さいため（ステップＳ８／ＹＥＳ）、これを採用しＣ｛２←（１）｝＝４とする（ステップＳ９）。この結果、各パラメータと経路の状態は表４のようになる。
【００３７】
【表４】
2004023473.tif 000006
【００３８】
同様の手順で、表５、表６、表７の経路が求まる。
【００３９】
【表５】
2004023473.tif 000007
【００４０】
【表６】
2004023473.tif 000008
【００４１】
【表７】
2004023473.tif 000009
【００４２】
表７の状態で、経路が未決定の装置は、４，５，６，８およびＢである。このうち、評価値が最も小さい８を選択する。装置７→装置８の経路を決定経路とし、装置８を経路決定済の装置とする。残りの装置（４，５，６およびＢ）のうち、装置８に隣接する装置（６，Ｂ）について、評価値Ｃを計算する。
【００４３】
装置６の評価値を計算する。装置８までの経路におけるリンクのうち最大コストは３、装置８−装置６間のリンクのコストは２であるので、装置Ａから装置６までの経路における最大コストは３である。また、この経路において装置Ａから装置６へのホップ数は３であるので、最大コストとホップ数を乗算して装置６の評価値＝９を得る。これは表７における現段階での評価値＝７より大きくなるため、これは採用せず、Ｃ｛６←（Ａ）｝＝７のままとする。
【００４４】
装置Ｂの評価値を計算する。装置８までの経路におけるリンクのうち最大コストは３、装置８−装置Ｂ間のリンクのコストは３であるので、装置Ａから装置Ｂまでの経路における最大コストは３である。また、この経路において装置Ａから装置Ｂへのホップ数は３であるので、最大コストとホップ数を乗算して装置Ｂの評価値＝９を得る。これは表７における現段階での評価値＝∞より小さいため、これを採用し、Ｃ｛Ｂ←（８）｝＝９に更新する。この結果、各パラメータと経路の状態は表８のようになる。なお、｛Ｂ←（８）｝は、確定した８までの経路からＢに至る経路の評価値であることを示す。
【００４５】
【表８】
2004023473.tif 000010
【００４６】
表８の状態で、経路が未決定の装置は、４，５，６およびＢである。このうち、評価値が最も小さい装置６を選択する。装置Ａ→装置６の経路を決定経路とし、装置６を経路決定済の装置とする。残りの装置（４，５およびＢ）のうち、装置６に隣接する装置Ｂについて、評価値Ｃを計算する。
【００４７】
装置６までの経路におけるリンクのうち最大コストは７、装置６−装置Ｂ間のリンクのコストは１であるので、装置Ａから装置Ｂまでの経路における最大コストは７である。また、この経路において装置Ａから装置Ｂへのホップ数は２であるので、最大コストとホップ数を乗算して装置Ｂの評価値＝１４を得る。これは表８における現段階での評価値＝９より大きくなるため、これは採用せず、Ｃ｛Ｂ←（８）｝＝９のままとする。この結果、各パラメータと経路の状態は表９のようになる。
【００４８】
【表９】
2004023473.tif 000011
【００４９】
同様の方法で表１０〜表１２が求まる。
【００５０】
【表１０】
2004023473.tif 000012
【００５１】
【表１１】
2004023473.tif 000013
【００５２】
【表１２】
2004023473.tif 000014
【００５３】
上記計算過程によって、装置Ａから全ての装置への経路が決定される。決定した経路のツリーは図３のようになる。括弧内の数値は、計算の結果得られた評価値である。装置Ａから装置Ｂへの経路は、Ａ→７→８→Ｂとなる。この経路は、最大コスト３、ホップ数３、合計コスト９である。
【００５４】
参考として、図１のネットワークに従来の手法を用いて経路計算を行った場合と比較する。まず、従来のダイクストラ法を適用して計算した場合、決定した経路のツリーは図４のようになる。ダイクストラ法は合計コストが最小となる経路を選択するため、装置Ａから装置Ｂへの経路はＡ→６→Ｂとなる（合計コスト：８）。しかしこの経路は、コストが極端に大きく、トラフィックのボトルネックとなり得るリンクＡ→６（コスト：７）を経由するものとなる。
【００５５】
一方、経路中における各リンクのコストの最大値を評価値としてそのまま用い、ホップ数を乗算しない方法で計算した場合、決定した経路のツリーは図５のようになる。この場合、なるべく小さいコストのリンク（経路中の最大コストは２）を経由するようになるため、ボトルネックは回避できる。しかし計算された経路は、中継装置を多数経由する経路（Ａ→１→２→３→４→５→Ｂ）となり、ホップ数が６と、効率の悪い経路を選択してしまう。
【００５６】
次に、本実施形態の経路計算方法を用いた場合、上述したように、装置Ａから装置Ｂへの経路は、Ａ→７→８→Ｂとなる。この経路は、最大コスト３、ホップ数３、合計コスト９であり、ネットワーク中のボトルネック箇所を回避しつつホップ数も少なく抑えた最適経路を計算可能であることが示されている。
【００５７】
以上のように本実施形態は、経路におけるリンク中の最大コストに基づいた経路計算を行うため、通信ネットワークにおけるトラフィックのボトルネックを回避した経路を計算できる。
【００５８】
また、評価値Ｃ＝（リンク中の最大コスト）×（ホップ数）とし、経路計算のための評価値に、ホップ数の要素を加味しているため、ボトルネックを回避した場合でも、ホップ数の増加を抑制できる。
【００５９】
また、アルゴリズムがダイクストラ（Ｄｉｊｋｓｔｒａ）法を元に拡張した計算方法であるためであるため、少ない計算量で経路を求めることができる。
【００６０】
次に、添付図面を参照しながら本発明に係る第２の実施形態について説明する。
図６に、本実施形態のアルゴリズムのフローチャートを示す。このアルゴリズムの、図２に示した第１のアルゴリズムとの差異は、評価値の計算式を、
評価値Ｃ＝（経路中の最大コスト）×係数α＋（その経路におけるホップ数）×係数β
とした点で異なる。なお、α、βは、１以上の任意の正数である。
【００６１】
上記に示したアルゴリズムにおいて、α＝２、β＝１として図１のネットワークに適用し、端末装置Ａを出発点とした経路計算を実行した結果を表１３に示す。また、決定した経路のツリーは図７のようになる。
【００６２】
【表１３】
2004023473.tif 000015
【００６３】
装置Ａから装置Ｂへの経路は、Ａ→７→８→Ｂとなり、図２のアルゴリズムを用いた場合と同一となる。この経路は、最大コスト３、ホップ数３、合計コスト９である。
【００６４】
また、α＝４、β＝１として、図１のネットワークにおける端末装置Ａを出発点とした経路計算を実行した結果を表１４に示す。決定した経路のツリーは図８のようになる。
【００６５】
【表１４】
2004023473.tif 000016
【００６６】
装置Ａから装置Ｂへの経路は、Ａ→１→２→３→４→５→Ｂとなる。この経路は、最大コスト２、ホップ数６、合計コスト１０である。α＝４、β＝１と、ホップ数よりも最大コストを重視して計算を行ったため、よりコストの小さいリンクを経由する経路が選ばれているが、ホップ数は多くなっている。
【００６７】
本実施形態では、経路中の最大コストとホップ数の各要素についてそれぞれ重み付けを行う計算を用いて評価値を求めている。このように評価値の計算式を変更することによって、経路選択を行う際に、最大コストとホップ数のどちらを重視するかを自由に調節することが可能となるという効果が得られる。
【００６８】
なお、上述した実施形態は本発明の好適な実施の形態である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施が可能である。また、本発明の最適経路計算プログラムに係る実施形態は、コンピュータに上述した手順で経路計算を行わせるプログラムを格納し、コンピュータがこのプログラムに従って経路計算を行うことで実現できる。
【００６９】
【発明の効果】
以上の説明より明らかなように本発明は、経路におけるリンク中の最大コストに基づいた経路計算を行うため、通信ネットワークにおけるトラフィックのボトルネックを回避した経路を計算できる。
【００７０】
また、評価値Ｃ＝（リンク中の最大コスト）×（ホップ数）とし、経路計算のための評価値に、ホップ数の要素を加味しているため、ボトルネックを回避した場合でも、ホップ数の増加を抑制できる。
【００７１】
また、アルゴリズムがダイクストラ（Ｄｉｊｋｓｔｒａ）法を元に拡張した計算方法であるためであるため、少ない計算量で経路を求めることができる。
【図面の簡単な説明】
【図１】通信ネットワークのシステム構成を示す図である。
【図２】経路計算のアルゴリズムを示すフローチャートである。
【図３】経路計算のアルゴリズムによって算出された経路を示す図である。
【図４】従来のダイクストラ法で決定された経路を示す図である。
【図５】リンクのコストの最大値を評価値として使用し、ホップ数を乗算しない方法で計算した経路を示す図である。
【図６】経路計算のアルゴリズムを示すフローチャートである。
【図７】最大コストとホップ数とに重みを付けて評価値を算出した場合の経路を示す図である。
【図８】最大コストとホップ数とに重みを付けて評価値を算出した場合の経路を示す図である。
【符号の説明】
Ａ　端末装置
Ｂ　端末装置
１、２、３、４、５、６、７、８　中継装置
【図１】
2004023473.tif 000017
【図２】
2004023473.tif 000018
【図３】
2004023473.tif 000019
【図４】
2004023473.tif 000020
【図５】
2004023473.tif 000021
【図６】
2004023473.tif 000022
【図７】
2004023473.tif 000023
【図８】
2004023473.tif 000024