(57)【特許請求の範囲】
【請求項１】
通信サービスの品質を示すＱｏＳ情報であってリンク毎の複数種類のＱｏＳ情報を取得するＮＷ情報取得部と、
前記ＮＷ情報取得部が取得した複数種類のＱｏＳ情報から導かれる通信品質の指標に基づいて、通信経路を決定する通信経路決定部と、
を備え、
前記通信経路決定部は、
リンク毎の複数種類のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから対象ノードまでのコストを算出するコスト算出部と、
前記コスト算出部が算出した第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとを前記ＱｏＳ情報毎に比較し、全てのＱｏＳ情報において前記第１のコストが前記第２のコストより通信品質が悪いことを示す場合、前記第１のコストを、通信経路を決定するための対象から除外する比較処理部と、
前記比較処理部が処理した結果に基づいて、前記通信経路を決定する決定部と、
を備えることを特徴とする通信システム。
【請求項２】
前記決定部は、
サービス種別及び前記コスト算出部が算出したＱｏＳ情報毎のコストに対応する前記通信品質の指標を取得する品質指標取得部と、
前記品質指標取得部が取得した通信品質の指標に基づいて、前記通信経路を抽出する経路抽出部と、
を備えることを特徴とする請求項１に記載の通信システム。
【請求項３】
リンク毎の複数のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから対象ノードまでのコストを算出するコスト算出部と、
前記コスト算出部が算出した第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとを前記ＱｏＳ情報毎に比較し、全てのＱｏＳ情報において前記第１のコストが前記第２のコストより通信品質が悪いことを示す場合、前記第１のコストを、通信経路を決定するための対象から除外する比較処理部と、
前記比較処理部が処理した結果に基づいて、通信経路を決定する決定部と、
を備えることを特徴とする経路決定装置。
【請求項４】
コスト算出部が、リンク毎の複数のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから対象ノードまでのコストを算出する手順と、
比較処理部が、前記コスト算出部が算出した第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとを前記ＱｏＳ情報毎に比較し、全てのＱｏＳ情報において前記第１のコストが前記第２のコストより通信品質が悪いことを示す場合、前記第１のコストを、通信経路を決定するための対象から除外する手順と、
決定部が、前記比較処理部が処理した結果に基づいて、通信経路を決定する手順と、
を有することを特徴とする経路決定方法。
【請求項５】
コンピュータに、
リンク毎の複数のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから対象ノードまでのコストを算出するコスト算出ステップと、
前記コスト算出ステップにより算出された第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとを前記ＱｏＳ情報毎に比較し、全てのＱｏＳ情報において前記第１のコストが前記第２のコストより通信品質が悪いことを示す場合、前記第１のコストを、通信経路を決定するための対象から除外する比較処理ステップと、
前記比較処理ステップにより処理された結果に基づいて、通信経路を決定する決定ステップと、
を実行させるための経路決定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システム、経路決定装置、経路決定方法及び経路決定プログラムに関する。
【背景技術】
【０００２】
インターネット等の一般的なＩＰ通信網においては、パケットの通信経路はＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）等により決定される。その際、経路探索手法としてＤｉｊｋｓｔｒａ（ダイクストラ）法が利用されているため、通信経路は常に最短ホップ数の経路となる。そのため、ネットワーク内のある一部分への通信トラフィックが集中することによって輻輳が発生し、通信品質の低下が生じるという問題がある。
【０００３】
これを解決する手段として、非特許文献１には、各リンクのＱｏＳ値という複数の指標を用い、始点ノードから終点ノードまで（Ｅｎｄ−Ｅｎｄ）のＱｏＳ値が通信フローが要求する値以下となる経路を探索し、それを通信経路とすることで各フローの通信品質を維持することが開示されている。ここで、ＱｏＳ値は、通信サービスの品質のことで、伝送速度、伝送遅延、それらのゆらぎ又はパケットロスなどの数値指標である。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Concepts of Exact QoS Routing Algorithms, IEEE/ACM TRANSACTIONS ONNETWORKING, VOL. 12, NO. 5, OCTOBER 2004, http://www.nas.ewi.tudelft.nl/people/Piet/papers/IEEEsamcraton.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００５】
サービスの品質を表す指標の一つとして、ユーザの体感品質（ＱｏＥ：Ｑｕａｌｉｔｙ  ｏｆ  Ｅｘｐｅｒｉｅｎｃｅ）がある。サービスの利用可否はユーザが決定するものであり、体感品質が低下すると、サービス利用低下や解約率の増加等に繋がるため、ＱｏＥは重要な指標の一つと考えられる。非特許文献１のように、ある要求する（ＱｏＥがある一定以上となる）ＱｏＳ値を閾値と定めて、それを満足するような経路を選択することでＱｏＥの低下を抑制するという方法が考えられる。
【０００６】
例えば、次世代ネットワーク（Ｎｅｘｔ  Ｇｅｎｅｒａｔｉｏｎ  Ｎｅｔｗｏｒｋ：ＮＧＮ）で実施されているような、通信フロー種別毎に優先度を設け、優先度の高い通信フローについては優先的に品質の良い状態を確保し、それ以外はベストエフォートで通信が行われるようなネットワークを考える。このとき、優先度の高い通信フローに対して優先的に経路を割り当てる際の経路探索手法として非特許文献１を活用することができる。
しかしながら、通信フローとして最も多いベストエフォートの通信フローに対して、現状のネットワーク状態を鑑みて、ユーザの体感品質が良好な経路を見つけることができないという問題がある。
【０００７】
そこで本発明は、上記問題に鑑みてなされたものであり、ユーザの体感品質が良好な通信経路を決定することができる通信システム、経路決定装置、経路決定方法及び経路決定プログラムを提供することを課題とする。
【課題を解決するための手段】
【０００９】
（１）上記に記載の通信システムにおいて、本発明の一態様は、通信サービスの品質を示すＱｏＳ情報であってリンク毎の複数種類のＱｏＳ情報を取得するＮＷ情報取得部と、前記ＮＷ情報取得部が取得した複数種類のＱｏＳ情報から導かれる通信品質の指標に基づいて、通信経路を決定する通信経路決定部と、を備え、前記通信経路決定部は、リンク毎の複数種類のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから対象ノードまでのコストを算出するコスト算出部と、前記コスト算出部が算出した第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとを前記ＱｏＳ情報毎に比較し、全てのＱｏＳ情報において前記第１のコストが前記第２のコストより通信品質が悪いことを示す場合、前記第１のコストを、通信経路を決定するための対象から除外する比較処理部と、前記比較処理部が処理した結果に基づいて、前記通信経路を決定する決定部と、を備えることを特徴とする。
【００１０】
（２）上記に記載の通信システムにおいて、本発明の一態様は、前記決定部は、サービス種別及び前記コスト算出部が算出したＱｏＳ情報毎のコストに対応する前記通信品質の指標を取得する品質指標取得部と、前記品質指標取得部が取得した通信品質の指標に基づいて、前記通信経路を抽出する経路抽出部と、を備えることを特徴とする。
【００１２】
（３）本発明の一態様は、リンク毎の複数のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから対象ノードまでのコストを算出するコスト算出部と、前記コスト算出部が算出した第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとを前記ＱｏＳ情報毎に比較し、全てのＱｏＳ情報において前記第１のコストが前記第２のコストより通信品質が悪いことを示す場合、前記第１のコストを、通信経路を決定するための対象から除外する比較処理部と、前記比較処理部が処理した結果に基づいて、通信経路を決定する決定部と、を備えることを特徴とする経路決定装置である。
【００１４】
（４）本発明の一態様は、コスト算出部が、リンク毎の複数のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから対象ノードまでのコストを算出する手順と、比較処理部が、前記コスト算出部が算出した第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとを前記ＱｏＳ情報毎に比較し、全てのＱｏＳ情報において前記第１のコストが前記第２のコストより通信品質が悪いことを示す場合、前記第１のコストを、通信経路を決定するための対象から除外する手順と、決定部が、前記比較処理部が処理した結果に基づいて、通信経路を決定する手順と、を有することを特徴とする経路決定方法である。
【００１６】
（５）本発明の一態様は、コンピュータに、リンク毎の複数のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから対象ノードまでのコストを算出するコスト算出ステップと、前記コスト算出ステップにより算出された第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとを前記ＱｏＳ情報毎に比較し、全てのＱｏＳ情報において前記第１のコストが前記第２のコストより通信品質が悪いことを示す場合、前記第１のコストを、通信経路を決定するための対象から除外する比較処理ステップと、前記比較処理ステップにより処理された結果に基づいて、通信経路を決定する決定ステップと、を実行させるための経路決定プログラムである。
【発明の効果】
【００１７】
本発明によれば、ユーザの体感品質が良好な通信経路を決定することができる。
【図面の簡単な説明】
【００１８】
【図１】本実施形態における通信システムの概略ブロック図である。
【図２】本実施形態における経路決定装置の概略ブロック図である。
【図３】本実施形態における通信経路決定部の概略ブロック図である。
【図４】本実施形態における経路探索装置の処理の流れの一例を示すフローチャートである。
【図５】本実施形態における経路探索処理を説明するためのネットワークトポロジの図である。
【図６】本実施形態における経路探索処理の流れの一例を示すフローチャートである。
【図７】経路情報記憶部のデータ保存領域の一例を示すテーブルＴ１である。
【図８】通信ネットワークのトポロジおよびデータ保存領域の一例を示すテーブルＴ２である。
【図９】経路情報記憶部のデータ保存領域の一例を示すテーブルＴ３である。
【図１０】図９のテーブルＴ３のデータ保存領域が更新された後のデータ保存領域の一例を示すテーブルＴ４である。
【図１１】通信ネットワークのトポロジの一例である。
【図１２】経路情報記憶部のデータ保存領域の初期状態の一例である。
【図１３】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−２である。
【図１４】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−３である。
【図１５】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−４である。
【図１６】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−５である。
【図１７】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−６である。
【図１８】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−７である。
【図１９】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−８である。
【図２０】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−９である。
【図２１】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−１０である。
【図２２】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−１１である。
【図２３】通信経路決定部の処理過程における経路情報記憶部のデータ保存領域の一例を示すテーブルＴ５−１２である。
【図２４】ノードＩＤがゴールノードＧである経路情報の一例を示すテーブルＴ６である。
【図２５】図２４に示されたコストに対応するＱｏＥの一例を示すテーブルＴ７である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態について、図面を参照して詳細に説明する。図１は、本実施形態における通信システム１の概略ブロック図である。通信システム１は、ＮＷ情報収集装置１００と、経路決定装置２００と、品質指標算出装置３００と、通信フロー制御装置４００とを備える。また、同図に置いて、通信システム１が管理対象とする管理対象ネットワーク１０が示されている。管理対象ネットワーク１０は、一例として、パケット転送装置１１、…、１７の七つのパケット転送装置を備える。なお、パケット転送装置の数は管理対象ネットワーク１０に応じた任意の数を取り得るものとする。
【００２０】
パケット転送装置１１、…、１７は、例えば、ルータやスイッチ等である。パケット転送装置１１、…、１７は、通信フロー制御装置４００と接続しており、通信フロー制御装置４００からの指示に従って通信径路を変更する。
具体的には、例えば、パケット転送装置１１、…、１７がＯｐｅｎＦｌｏｗ対応スイッチの場合、パケット転送装置１１、…、１７は、通信フロー制御装置４００としてのＯｐｅｎＦｌｏｗコントローラからの指示に従って通信径路を変更する。
【００２１】
また、同図に、通信フローの一例として、通信フロー２０が示されている。通信フロー２０は、パケット転送装置１２、パケット転送装置１３、パケット転送装置１４、パケット転送装置１５を順に通る通信フローである。この通信フロー２０は、管理対象ネットワークを流れる何らかのサービスを実現するための通信フローである。以下、通信フローを単にフローともいう。
【００２２】
ＮＷ情報収集装置１００は、管理対象ネットワーク１０のトポロジ情報（パケット転送装置の接続関係）、各リンクのＱｏＳ情報および管理対象ネットワーク１０内を流れているフロー情報を管理する。ここで、ＱｏＳ情報は、通信サービスの品質を示す情報で、例えば、伝送遅延、ゆらぎまたはパケットロス率などの数値指標である。また、フロー情報は、管理対象ネットワーク１０内に存在する通信フローに関する情報であり、例えば、通過経路、使用帯域、要求帯域又はサービス種別である。
【００２３】
各情報の収集・管理方法は任意であるが、例えばＱｏＳ情報に関しては、各パケット転送装置のミラーポートにプローブ装置を設置する。そして、ＮＷ情報収集装置１００は、各プローブ装置でキャプチャしたパケット情報からＱｏＳ情報を算出し、ＱｏＳ情報を構築する。具体的には、例えば、ＮＷ情報収集装置１００は、遅延又はゆらぎをパケットの到達時刻の差を利用して計算する。また、例えば、ＮＷ情報収集装置１００は、パケットロス率をパケット数の差から計算する。
【００２４】
ＮＷ情報収集装置１００は、例えば、サービス種別をプロトコル又はポート番号から判別する。なお、ＮＷ情報収集装置１００は、サービス種別をパケットの密度等から推定しても良いし、コントロールプレーンのデータから次に流れるデータプレーンの情報を推定しても良い。具体的には、例えば、ＮＷ情報収集装置１００は、ＳＩＰ信号が流れた後に音声パケットが流れることを推定する。ただし、本通信システム１全体として識別するサービス種別の種類は同一であるとする。そして、ＮＷ情報収集装置１００は、判定したサービス種別からそのフローの要求帯域を認識する。そして、ＮＷ情報収集装置１００は、ＱｏＳ情報及びフロー情報を経路決定装置２００へ出力する。このフロー情報には、例えば、通過経路、使用帯域、要求帯域及びサービス種別が含まれている。
【００２５】
経路決定装置２００は、ＮＷ情報収集装置１００から取得したＱｏＳ情報に基づいて、経路探索対象となる通信フローの始点ノードから各ノードまでのコストを算出する。ここで、経路決定装置２００は、経路探索の際に用いる複数種類のＱｏＳ情報に使用帯域を含める場合に、ＮＷ情報収集装置１００から取得したフロー情報に含まれる使用帯域を利用して上記コストを算出する。そして、経路決定装置２００は、算出したコスト及びＮＷ情報収集装置１００から取得したサービス種別に対応するＱｏＥ情報を品質指標算出装置３００から取得する。そして、経路決定装置２００は、取得したＱｏＥ情報に基づいて、その通信フローの通信径路を決定する。経路決定装置２００は、決定した通信径路を示す通信経路情報を通信フロー制御装置４００へ出力する。
【００２６】
品質指標算出装置３００は、サービス種別毎にＱｏＥ情報の算出方式を保持する。品質指標算出装置３００は、経路決定装置２００から入力されたＱｏＳ情報及びサービス種別からＱｏＥ情報を算出する。この算出方式は、ＩＴＵ−Ｔ等で検討されている方法を利用しても良いし、独自に定めた方式で算出しても良い。なお、ＱｏＥの算出は、本システム全体で識別可能なサービス種別毎に算出可能であることとする。
【００２７】
通信フロー制御装置４００は、経路探索を実施したい対象フローを決定し、決定した対象フローを示す対象フロー情報を経路決定装置２００へ出力する。また、通信フロー制御装置４００は、経路決定装置２００から入力された通信経路情報が示す通信経路を上記決定したフローがとるように、管理対象ネットワーク１０内のパケット転送装置１１、…、１７に対して経路制御を行う。
【００２８】
図２は、本実施形態における経路決定装置２００の概略ブロック図である。経路決定装置２００は、フロー情報取得部２１０と、ＮＷ情報取得部２２０と、通信経路決定部２３０と、経路情報送信部２４０とを備える。
フロー情報取得部２１０は、通信フロー制御装置４００から対象フロー情報を取得し、取得した対象フロー情報をＮＷ情報取得部２２０へ出力する。
【００２９】
ＮＷ情報取得部２２０は、フロー情報取得部２１０から入力された対象フロー情報が示す対象フローについて、ＮＷ情報収集装置１００からリンク毎の複数種類のＱｏＳ情報及びフロー情報を取得し、取得したＱｏＳ情報及びフロー情報を通信経路決定部２３０へ出力する。
【００３０】
通信経路決定部２３０は、ＮＷ情報取得部２２０が取得したリンク毎の複数種類のＱｏＳ情報から導かれる通信品質の指標に基づいて、通信経路を決定する。本実施形態では、通信経路決定部２３０は、通信品質の指標の一例としてＱｏＥを用い、一例として以下の処理を行う。通信経路決定部２３０は、ＮＷ情報取得部２２０から入力されたＱｏＳ情報に基づいて、対象フローの始点ノードから各ノードまでのコストを算出する。そして、通信経路決定部２３０は、算出したコストに対応するＱｏＥ情報を品質指標算出装置３００から取得する。そして、通信経路決定部２３０は、取得したＱｏＥ情報に基づいて、その対象フローの通信径路を決定し、決定した通信径路を示す通信経路情報を経路情報送信部２４０へ出力する。
【００３１】
経路情報送信部２４０は、通信経路決定部２３０から入力された通信経路情報を通信フロー制御装置４００へ送信する。
これにより、通信フロー制御装置４００は、経路情報送信部２４０から受信した通信経路情報に基づき、パケット転送装置１１、…、１７内の経路情報を更新し、決定した通信経路にフローが流れるようにする。
【００３２】
図３は、本実施形態における通信経路決定部２３０の概略ブロック図である。通信経路決定部２３０は、隣接ノード抽出部２３１と、コスト算出部２３２と、比較処理部２３３と、判定部２３４と、経路情報記憶部２３７と、決定部２３８とを備える。
隣接ノード抽出部２３１は、処理対象となる対象ノードに隣接する隣接ノードを、トポロジ情報を利用して抽出する。隣接ノード抽出部２３１は、抽出した隣接ノードをコスト算出部２３２に出力する。
【００３３】
コスト算出部２３２は、リンク毎の複数種類のＱｏＳ情報に基づいて、該ＱｏＳ情報毎に、通信フローの始点ノードから隣接ノード抽出部２３１が抽出した隣接ノードまでのコストを算出する。そして、コスト算出部２３２は、コストを算出する毎に、算出したコストを比較処理部２３３に出力する。
【００３４】
比較処理部２３３は、コスト算出部２３２が算出した第１の経路による対象ノードまでのコストと、第１の経路とは異なる第２の経路による該対象ノードまでのコストとを比較し、比較に基づいて経路を決定する。より詳細には、比較処理部２３３は、コスト算出部２３２が算出した第１の経路による対象ノードまでの第１のコストと第１の経路とは異なる第２の経路による該対象ノードまでの第２のコストとをＱｏＳ情報毎に比較し、全てのＱｏＳ情報において第１のコストが第２のコストより通信品質が悪いことを示す場合、前記第１のコストを破棄する。ここで、第２の経路による該対象ノードまでのコストは、既に算出されて経路情報記憶部２３７に記憶されているものとする。具体的には、比較処理部２３３は、コスト算出部２３２が算出した第１の経路による対象ノードまでのコストが、第２の経路による該対象ノードまでのコストより品質が良い場合、第１の経路を選択する。そして、比較処理部２３３は、経路情報記憶部２３７に記憶されている第２の経路に関する経路情報を削除する。また、比較処理部２３３は、経路情報記憶部２３７に記憶されている第２の経路を内包する経路情報を削除する。
一方、比較処理部２３３は、第１の経路による対象ノードまでのコストより、第２の経路による該対象ノードまでのコストの品質が良い場合、第２の経路を選択する。そして、比較処理部２３３は、第１の経路に関する経路情報を破棄する。
【００３５】
判定部２３４は、次にコストを算出する対象となるノードがあるか否か判定する。具体的には、判定部２３４は、最後にコストを算出したノードに隣接するノードであってまだコストを算出していない経路に含まれるノードがあるか否か判定する。
【００３６】
次にコストを算出する対象となるノードがある場合、判定部２３４は、そのノード情報をコスト算出部２３２へ出力する。これにより、コスト算出部２３２は、ＱｏＳ情報毎に、通信フローの始点ノードからそのノードまでのコストを算出する。一方、次にコストを算出する対象となるノードがない場合、全てのノードにおいてコストを算出した旨を決定部２３８の後述する品質指標取得部２３５へ出力する。
【００３７】
決定部２３８は、経路情報記憶部２３７に記憶されている終点ノードまでのコストに基づいて、通信経路を決定する。すなわち、決定部２３８は、比較処理部が処理した結果に基づいて、前記通信経路を決定する。ここで、決定部２３８は、品質指標取得部２３５と、品質指標取得部２３５とを備える。
品質指標取得部２３５が、判定部２３４から全てのノードにおいてコストを算出した旨を受け取った場合、サービス種別及びコスト算出部２３２が算出したＱｏＳ情報毎のコストに対応する通信品質の指標（例えば、ＱｏＥ）を品質指標算出装置３００から取得する。そして、品質指標取得部２３５は、取得した通信品質の指標（例えば、ＱｏＥ）を経路抽出部２３６へ出力する。
【００３８】
経路抽出部２３６は、品質指標取得部２３５が取得した通信品質の指標に基づいて、通信経路を抽出する。そして、経路抽出部２３６は、抽出した通信経路を示す通信経路情報を経路情報送信部２４０へ出力する。
経路情報記憶部２３７には、経路情報を保持する。具体的には、例えば、経路情報記憶部２３７は、ノードＩＤ、経路及びコストが関連付けられて記憶されている。経路は、スタートノードＳから対応するノードＩＤまでの経路である。コストは、スタートノードＳから対応するノードＩＤまで移動するコストである。
【００３９】
図４は、本実施形態における経路探索装置の処理の流れの一例を示すフローチャートである。ここで、以下の処理フロー内で用いている用語について定義する。［ＸＸＸノード］は、ＸＸＸを意味するノードの集合である。（ｓ）は経路探索の開始のノードであるスタートノードである。（ｇ）は経路探索の終了のノードであるゴールノードである。Ｃｏｓｔ（ｘ，ｙ）は、新たに算出されたノード（ｘ）からノード（ｙ）までに移動するコストである。ＯｔｈｅｒＣｏｓｔ（ｘ，ｙ）は、保存されているノード（ｘ）からノード（ｙ）までに移動するコストである。例えば、ＯｔｈｅｒＣｏｓｔ（ｓ，ｇ）は、保存されているスタートノード（ｓ）からゴールノード（ｇ）までに移動するコストを表している。
【００４０】
まず、ステップＳ１０１において、フロー情報取得部２１０は、経路探索の対象となる対象フロー情報を取得する。具体的には、フロー情報取得部２１０は、通信フロー制御装置４００が予め決められた任意の方法で決定した通信径路の探索を実施したいフロー情報を取得する。通信径路探索を実施したいフローとしては、例えば、新たな通信フローの通過経路決定の際や、既に流れている通信フローの移動先経路決定の際等がある。
【００４１】
通信フロー制御装置４００より受け取る情報は、例えば、始点ノード（ソースノード）、終点ノード（ゴールノード）、サービス種別及び要求帯域である。ここで、ソースノードは、管理対象ネットワーク１０において経路探索実施フローが最初に通過するパケット転送装置である。ゴールノードは、管理対象ネットワーク１０において経路探索実施フローが最後に通過するパケット転送である。サービス種別は、経路探索実施フローのサービス種別であり、例えば、映像サービス等を指す。要求帯域は、経路探索実施フローの要求帯域であり、例えば、映像のビットレート等を指す。
【００４２】
次に、ステップＳ１０２において、ＮＷ情報取得部２２０は、ＱｏＳ情報及びフロー情報を取得する。具体的には、ＮＷ情報取得部２２０は、ＮＷ情報収集装置１００が管理している管理対象ネットワーク１０の情報を収集する。ＮＷ情報収集装置１００より受け取る情報は、例えば、リンクのＱｏＳ値、トポロジ情報及びフロー情報である。ここで、リンクのＱｏＳ値は、管理対象ネットワーク１０内の全ての方向別リンクのＱｏＳ値（例えば、伝送遅延、ゆらぎ又はパケットロス率等）である。トポロジ情報は、管理対象ネットワーク１０内のパケット転送装置１１、…、１７とその接続関係である。フロー情報は、通信経路決定部２３０が、経路探索の際に用いる複数種類のＱｏＳ情報に使用帯域を含める場合に利用される。
【００４３】
次に、ステップＳ１０３において、通信経路決定部２３０は、通信品質の指標（例えば、ＱｏＥ）が良好な経路を探索する。詳細な処理は後述するが、処理の概要を、図５を用いて説明する。図５は、本実施形態における経路探索処理を説明するためのネットワークトポロジの図である。同図において、通信ネットワーク５１〜５４は、スタートノードＳ、ノードＡ、ノードＢ、ゴールノードＧから構成されている。スタートノードＳは、ノードＡとノードＢと接続している。ノードＡは、スタートノードＳ、ノードＢ及びゴールノードＧと接続している。ノードＢは、スタートノードＳ、ノードＡ及びゴールノードＧと接続している。ゴールノードＧは、ノードＡ及びノードＢと接続している。
【００４４】
第１に、通信経路決定部２３０は、処理対象のノードを決める。通信経路決定部２３０は、隣接ノードに対するコスト計算が完了していないノードを順に処理対象ノードとする。図５の通信ネットワーク５１に示すように、最初はスタートノードＳのみが処理対象ノードに該当する。
【００４５】
第２に、通信経路決定部２３０は、処理対象ノード（ここでは、スタートノードＳ）の隣接ノード（ここでは、ノードＡ及びノードＢ）までのコストを算出する（図５の通信ネットワーク５２を参照）。ここで、通信経路決定部２３０は、経路がループとならない隣接ノードまでのコストを算出する。図５の例では、通信経路決定部２３０は、スタートノードＳからノードＡまでのコストと、スタートノードＳからノードＢまでのコストを算出する。ここでスタートノードＳは計算済みとなる。
【００４６】
第３に、通信経路決定部２３０は、コストの比較を行い、処理の無駄を省く。次に、図５の通信ネットワーク５３のように、処理対象としてＡが選ばれたとする。このとき、経路がループしない隣接ノードはノードＢ及びゴールノードＧの二つとなり、通信経路決定部２３０は、それぞれのコストを算出する。
【００４７】
ノードＢについては、スタートノードＳから隣接ノードまでのコスト計算により何らかのコストが存在している。そのため、通信経路決定部２３０は、スタートノードＳからノードＢに経路を辿った場合のコストと、スタートノードＳからノードＡ、ノードＢと順に経路をたどった場合のコストとの比較を行う。
【００４８】
通信経路決定部２３０は、いずれかのコストが、他のコストと大小関係にある場合は、品質の悪い方の処理は行わない。大小関係が無い場合は、通信経路決定部２３０は、両方について処理を継続する。つまり、例えば大小関係が無い場合は、通信経路決定部２３０は、処理対象がノードＢのとき、スタートノードＳからノードＢに辿った場合の経路を持つ情報については、ループしない隣接ノードであるノードＡ及びゴールノードＧに対するコスト計算を行う。一方、通信経路決定部２３０は、スタートノードＳからノードＡ、ノードＢの順に辿った経路を持つ情報については、ループしない隣接ノードであるゴールノードＧに対するコスト計算を行う。
【００４９】
次に、図４に戻って、ステップＳ１０４において、経路情報送信部２４０は、移動対象フローの情報と移動先経路情報を通信フロー制御装置４００へ送信する。これにより、通信フロー制御装置４００は、経路の変更処理を実施する。以上で、本フローチャートの処理を終了する。
【００５０】
続いて、通信経路決定部２３０における通信経路の決定処理の詳細について図６のフローチャートを用いて説明する。図６は、本実施形態における経路探索処理の流れの一例を示すフローチャートである。ここで、経路探索処理を実施する上で必要となるデータの保存領域には、一例として、ノードＩＤ、経路、コスト及び未計算フラグとが関連付けられて記憶されている。ここで、ノードＩＤは、パケット転送装置を一意に識別可能なＩＤ情報である。また、経路は、スタートノードからノードＩＤが示すノードまでの経路情報である。また、コストは、スタートノードからノードＩＤが示すノードまでの上記経路に従ってノードを辿って移動した際のコストである。未計算フラグは、このノードＩＤの経路情報に対して計算処理がなされたか否かを示すフラグであり、例えば、ブール値で表される。なお、これらの組合せで識別されるデータの保存領域内の１組のデータを、１エントリと呼ぶ。
【００５１】
上述のデータ保存領域を利用した場合を例に、経路探索処理の処理フローについて以下に説明する。
まず、ステップＳ２０１において、通信経路決定部２３０は、［次計算ノード］に対して最初に処理するスタートノードを格納する。［次計算ノード］が空でない場合、通信経路決定部２３０は、ステップＳ２０２〜Ｓ２１２の処理を実施する。
【００５２】
次に、ステップＳ２０２において、通信経路決定部２３０は、［現在ノード］に［次計算ノード］内の情報を代入する。通信経路決定部２３０は、通信経路決定部２３０が保持するデータ保存領域におけるノードＩＤが［現在ノード］に属しているノードであり、かつ通信経路決定部２３０が保持するデータ保存領域における未計算フラグが「ＴＲＵＥ」であるエントリが存在する場合に、［現在ノード］に属しているノード毎に、ステップＳ２０２〜Ｓ２１２の処理を実施する。すなわち、要素（ｖ）は［現在ノード］に属しているノードであるとすると、通信経路決定部２３０は、データ保存領域におけるノードＩＤが要素（ｖ）である未計算のエントリについてステップＳ２０２〜Ｓ２１２の処理を実施する。
例えば、［現在ノード］内の要素（ｖ）として、ノードＩＤが「Ｘ」のノードが存在したとする。このとき、通信経路決定部２３０はデータ保存領域において「ノードＩＤがＸかつ未計算フラグがＴＲＵＥ」であるエントリを検索し、存在した場合は以降の処理を実施する。
【００５３】
ここで、経路情報記憶部２３７のデータ保存領域が図７に示すテーブルＴ１のようであった場合を想定する。図７は、経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ１である。同図において、ノードＩＤ、経路、コスト及び未計算フラグの組が示されている。なお、この図における１行が１エントリに相当する。
図７に示すテーブルＴ１の４行目に「ノードＩＤがＸで、かつ未計算フラグがＴＲＵＥ」であるエントリが存在する。このとき、通信経路決定部２３０は、上記見つかったエントリを保持しておくと共に、以降の処理を実施する。
【００５４】
次に、図６に戻ってステップＳ２０３において、通信経路決定部２３０の隣接ノード抽出部２３１は、［現在ノード］内の要素（ｖ）に隣接するノードを示す隣接ノード情報を、ＮＷ情報取得部２２０が取得したトポロジ情報を利用して抽出する。ただし、隣接ノード抽出部２３１は、データ保存領域の経路情報を参照して、抽出する隣接ノードから経路がループとなるようなノードを除く。隣接ノード抽出部２３１は、抽出した隣接ノード情報を［隣接ノード］に代入する。
【００５５】
隣接ノード抽出部２３１は、前述の「ノードＩＤがＸで、かつ未計算フラグがＴＲＵＥ」を検索した結果見つかったエントリ全てに対して、上記ステップＳ２０３の処理を実施する。ここで、例えば、通信ネットワークのトポロジおよびデータ保存領域を図８に示したものであると仮定する。
【００５６】
図８は、通信ネットワークのトポロジおよびデータ保存領域の一例を示す図である。同図において、トポロジ８１と、データ保存領域のテーブルＴ２が示されている。トポロジ８１は、スタートノードＳ、ノードＡ、Ｂ、Ｃ、Ｄ及びＥを備える。テーブルＴ２において、ノードＩＤ、経路、コスト及び未計算フラグの組が示されている。例えば、テーブルＴ２の４行目のエントリは、ノードＩＤがＣで、経路が「Ｓ→Ａ→Ｃ」で、コストが「Ｃｏｓｔ（ｓ，ｃ）」で、未計算フラグが「ＴＲＵＥ」であることが示されている。ここで、右矢印（→）は、右矢印が指すノードへの移動を示しており、経路「Ｓ→Ａ→Ｃ」は、スタートノードＳからノードＡに移動し、ノードＡからノードＣに移動する経路を示している。
【００５７】
この条件で、［現在ノード］に「Ｃ」があり、ノードＣに対する隣接ノードを探索する場合を考える。データ保存領域にはノードＩＤがＣであるエントリとして、テーブルＴ２の４行目のＣ（※１）と５行目のＣ（※２）が存在しており、ともに未計算フラグが「ＴＲＵＥ」であるので、隣接ノード抽出部２３１は、この二つのエントリについて隣接ノードをそれぞれ抽出する。
【００５８】
ノードＣに接続するノードは、ノードＡ、Ｂ、Ｄ及びＥの四つであるが、テーブルＴ２の４行目のＣ（※１）については、辿った経路が「Ｓ→Ａ→Ｃ」であるため、仮に通信経路決定部２３０が隣接ノードとしてノードＡを選択した場合、経路にループが発生する。そこで、隣接ノード抽出部２３１は、経路にループが発生するノードＡを除外して、「Ｂ、Ｄ、Ｅ」の三つのノードを経路情報とともに［隣接ノード］に代入する。同様に、テーブルＴ２の５行目のＣ（※２）については、経路が「Ｓ→Ａ→Ｂ→Ｃ」であることから、隣接ノード抽出部２３１は、経路にループが発生するノードＡ及びＢを除外して、「Ｄ、Ｅ」の二つのノードを経路情報とともに［隣接ノード］に代入する。つまり、［隣接ノード］内の要素（ｗ）には、経路情報の異なる同一ノードが複数存在する可能性もある。
【００５９】
次に、図６に戻って、通信経路決定部２３０は、［隣接ノード］内の要素（ｗ）について、ステップＳ２０４〜Ｓ２１１の処理を実施する。
まず、ステップＳ２０４において、通信経路決定部２３０のコスト算出部２３２は、ステップＳ２０３において隣接ノード抽出部２３１が抽出した隣接ノードまでのコストを算出する。例えば、上述のテーブルＴ２の５行目Ｃ（※２）のエントリを例にコスト算出部２３２の処理を説明する。この場合、隣接ノードはノードＤ及びＥの二つであることから、コスト算出部２３２は、この二つのノードまでのコストを算出する。具体的には、例えば、コスト算出部２３２は、ノードＤまでの遅延を、スタートノードＳからノードＣまでの伝送遅延とリンクＣ−Ｄの伝送遅延との和をコストの一つとして算出する。ここで、リンクＣ−ＤはノードＣとノードＤの間の経路である。また、例えば、ＱｏＳ情報がゆらぎの場合も同様に、コスト算出部２３２は、スタートノードＳからノードＣまでのゆらぎとリンクＣ−Ｄのゆらぎとの和をコストの一つとして算出する。また、例えば、ＱｏＳ情報がパケットロス率の場合、コスト算出部２３２は、スタートノードＳからノードＣまでのパケットロス率とリンクＣ−Ｄ間のパケットロス率とに基づいて、スタートノードＳとノードＤ間のパケットロス率をコストの一つとして算出する。
【００６０】
また、例えば、ＱｏＳ情報が使用帯域の場合、コスト算出部２３２は、スタートノードＳからノードＣまでの使用帯域と下記の帯域Ｔとのうち、小さい方の帯域をコストの一つとして選択する。帯域Ｔは、リンクの空き帯域がフローの要求帯域より大きい場合、フローの要求帯域である。一方、リンクの空き帯域がフローの要求帯域以下の場合、（フローの要求帯域）×（フローの要求帯域）／Σ（当該リンクを通過するフローの要求帯域）である。例えば、フローの要求帯域が３０Ｍｂｉｔ／ｓで、リンクＣ−Ｄ間を通過するフローの要求帯域の合計が１１０Ｍｂｉｔ／ｓである場合、帯域Ｔは、３０×３０／１１０＝
８．２Ｍｂｉｔ／ｓである。これは、コスト算出部２３２が、スタートノードＳからノードＣまでの使用帯域が隣接ノードまでのリンクにおいて、そのまま通過可能なのか、あるいは絞り込まれてしまうのかを判断することを意味する。
【００６１】
次に、ステップＳ２０５及びステップＳ２０６において、比較処理部２３３は、算出した隣接ノードまでのコストと算出済みのコストを比較して、隣接ノードのエントリをデータ保存領域に追加するか否かを決定する。
【００６２】
ここで、コストの比較方法を、ＣｏｓｔＸ及びＣｏｓｔＹを用いて説明する。ＣｏｓｔＸ及びＣｏｓｔＹは伝送遅延やゆらぎ等からなる多次元ベクトルであり、ＣｏｓｔＸ＝｛ｘ１，ｘ２，ｘ３，…，ｘｎ｝でＣｏｓｔＹ＝｛ｙ１，ｙ２，ｙ３，…，ｙｎ｝であるとする。このとき、比較処理部２３３は、「ｘｉ＞ｙｉ（ｉ＝１，２，３，…，ｎ）」であるなら、比較処理部２３３は、「ＣｏｓｔＸ＞ＣｏｓｔＹ」と判定する。なお、不等号は、値の大小を意味しているのではなく、品質の善し悪しを示しており、「ＣｏｓｔＸ＞ＣｏｓｔＹ」はＣｏｓｔＹがＣｏｓｔＸよりも品質が悪いことを示している。
【００６３】
ステップＳ２０５において、比較処理部２３３は、隣接ノードｗまでのコストＣｏｓｔ（ｓ，ｗ）と、データ保存領域に既に存在するノードＩＤが「ｇ」であるエントリのコストＯｔｈｅｒＣｏｓｔ（ｓ，ｇ）とを比較する。ここで、図６のステップＳ２０５において、「ＯｔｈｅｒＣｏｓｔ（ｓ，ｇ）」の前に付されたＡが上下反転した符号は、「任意の」という意味である。隣接ノードｗまでのコストＣｏｓｔ（ｓ，ｗ）がゴールノードまでのコストＯｔｈｅｒＣｏｓｔ（ｓ，ｇ）のいずれか一つよりも品質が悪いか等しい場合（ステップＳ２０５  ＹＥＳ）、通信経路決定部２３０はステップＳ２０４の処理に戻る。一方、上記の条件が成立しない場合（ステップＳ２０５  ＮＯ）、比較処理部２３３はステップＳ２０６の処理へ遷移する。
【００６４】
ステップＳ２０６において、ステップＳ２０４でコスト算出部２３２が算出した隣接ノードｗまでのコストＣｏｓｔ（ｓ，ｗ）と、データ保存領域に既に存在するノードＩＤが「ｗ」であるエントリのコストＯｔｈｅｒＣｏｓｔ（ｓ，ｗ）それぞれとを比較する。ここで、図６のステップＳ２０６において、同様に「ＯｔｈｅｒＣｏｓｔ（ｓ，ｗ）」の前に付されたＡが上下反転した符号は、「任意の」という意味である。隣接ノードｗまでのコストＣｏｓｔ（ｓ，ｗ）が他に算出済みの隣接ノードｗまでのコストＯｔｈｅｒＣｏｓｔ（ｓ，ｗ）のいずれか一つよりも品質が悪いか等しい場合（ステップＳ２０６  ＹＥＳ）、通信経路決定部２３０はステップＳ２０４の処理に戻る。一方、上記の条件が成立しない場合（ステップＳ２０６  ＹＥＳ）、比較処理部２３３はステップＳ２０７の処理へ遷移する。
【００６５】
ここで、コストとＱｏＥの関係について説明する。上述のＣｏｓｔＸ及びＣｏｓｔＹのＱｏＥ値であるＱｏＥＸ＝Ｆ（ＣｏｓｔＸ）とＱｏＥＹ＝Ｆ（ＣｏｓｔＹ）を考える。ＦはＣｏｓｔからＱｏＥを算出するサービス種別毎に予め決められた単調減少の特性を持つ導出関数である。このとき、「ＣｏｓｔＸ＞ＣｏｓｔＹ」が成立する場合、「ＱｏＥＸ＞ＱｏＥＹ」が成立する。すなわち、ＣｏｓｔＹがＣｏｓｔＸよりも品質が悪い場合、ＱｏＥＹはＱｏＥＸより品質が悪いという関係が成り立つ。
【００６６】
上述の考え方より、「ＣｏｓｔＸ＞ＣｏｓｔＹ」が成立する場合、品質指標算出装置３００がＣｏｓｔＸよりも品質が悪いＣｏｓｔＹからＱｏＥを算出する必要は無い。そのため、ステップＳ２０４によって得られたコストより品質の悪いコストを持つ情報に基づいた探索は不要となる。そこで、比較処理部２３３は、ある隣接ノードまでの経路におけるコストが算出済みのコストよりも品質が悪いことを示す場合、その隣接ノードまでの経路及びその隣接ノードまでの経路を包含する経路を探索対象から除外することによって、探索処理量を削減する。具体的には、ステップＳ２０７において、隣接ノードｗまでのコストＣｏｓｔ（ｓ，ｗ）よりも品質が悪い、隣接ノードｗまでの他のコストＯｔｈｅｒＣｏｓｔ（ｓ，ｗ）が経路情報記憶部２３７に記憶されているか否か判定する。
【００６７】
隣接ノードｗまでのコストＣｏｓｔ（ｓ，ｗ）よりも品質が悪い、隣接ノードｗまでの他のコストＯｔｈｅｒＣｏｓｔ（ｓ，ｗ）が経路情報記憶部２３７に記憶されていない場合（ステップＳ２０７  ＮＯ）、比較処理部２３３はステップＳ２１０へ遷移する。
一方、隣接ノードｗまでのコストＣｏｓｔ（ｓ，ｗ）よりも品質が悪い、隣接ノードｗまでの他のコストＯｔｈｅｒＣｏｓｔ（ｓ，ｗ）が経路情報記憶部２３７に記憶されている場合（ステップＳ２０７  ＹＥＳ）、比較処理部２３３は、当該隣接ノードｗまでの他のコストＯｔｈｅｒＣｏｓｔ（ｓ，ｗ）の経路情報を持つエントリを経路情報記憶部２３７から削除し（ステップＳ２０８）、ステップＳ２０９へ遷移する。
【００６８】
ステップＳ２０９において、比較処理部２３３は、当該隣接ノードｗまでの他のコストＯｔｈｅｒＣｏｓｔ（ｓ，ｗ）とともに格納されている経路情報を内包する経路情報を有するエントリを経路情報記憶部２３７から削除し、ステップＳ２１０へ遷移する。
【００６９】
例えばノードＸにおいて新たに算出されたコストが「ＮｅｗＣｏｓｔ」であったとする。また、経路情報記憶部２３７のデータ保存領域が図９のテーブルＴ３のようであり、Ｃｏｓｔ１に対してのみ「ＮｅｗＣｏｓｔ＞Ｃｏｓｔ１」の関係であったとする。
図９は、経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ３である。同図のテーブルＴ１において、ノードＩＤ、経路、コスト及び未計算フラグの組が示されている。例えば、テーブルＴ３の１行目のエントリには、ノードＩＤが「Ｘ」で、経路が「Ｓ→（経路Ａ）→Ｘ」でコストがＣｏｓｔ１であることが示されている。また、例えば、テーブルＴ３の２行目のエントリには、ノードＩＤが「Ｘ」で、経路が「Ｓ→（経路Ｂ）→Ｘ」でコストがＣｏｓｔ２であることが示されている。
【００７０】
同図の例において、比較処理部２３３は、新たにコスト算出を行ったノードＸの経路情報を経路情報記憶部２３７のデータ保存領域から抽出する。このとき、比較処理部２３３は、同図のテーブルＴ３の１行目および２行目のエントリの経路情報を抽出する。
次に、比較処理部２３３は、コストを比較すると、１行目のＣｏｓｔ１は新たなコスト「ＮｅｗＣｏｓｔ」より品質が悪いことから、テーブルＴ３の１行目のエントリを削除する（ステップＳ２０８での処理）。
【００７１】
また、比較処理部２３３は、削除対象となったエントリの経路を内包する経路を保持するエントリを経路情報記憶部２３７のデータ保存領域から抽出する。本例の場合、比較処理部２３３は、同図のテーブルＴ３の３行目のエントリを抽出する。そして、比較処理部２３３は、抽出したテーブルＴ３の３行目のエントリを削除する（ステップＳ２０９での処理）。以上により、図９のテーブルＴ３に示されたデータ保存領域は、図１０のテーブルＴ４のように更新される。
【００７２】
図１０は、図９のテーブルＴ３のデータ保存領域が更新された後のデータ保存領域の一例を示すテーブルＴ４である。同図のテーブルＴ４において、データ保存領域が２エントリから構成されていることが示されている。図９のテーブルＴ３では、４エントリだったのに対し、図１０のテーブルＴ４では、図９のテーブルＴ３から２エントリ分の経路情報が削除されている。
【００７３】
次に、図６に戻ってステップＳ２１０において、比較処理部２３３は、新たに算出した隣接ノードまでのコストおよび経路情報を含むエントリをデータ保存領域に追記し、ステップＳ２１１へ遷移する。このとき、当該エントリのノードＩＤは「ｗ」、未計算フラグは「ＴＲＵＥ」である。次に、ステップＳ２１１において、比較処理部２３３は、［次計算ノード］に隣接ノードｗを追加する。
次に、判定部２３４は、［隣接ノード］内の全ての要素（ｗ）について、ステップＳ２０４〜Ｓ２１１の処理をしたか否か判定する。［隣接ノード］内の全ての要素について、ステップＳ２０４〜Ｓ２１１の処理をしていない場合、処理をしていない要素について、ステップＳ２０４〜Ｓ２１１の処理を行う。一方、［隣接ノード］内の全ての要素について、ステップＳ２０４〜Ｓ２１１の処理をした場合、ステップＳ２１２の処理へ遷移する。
【００７４】
ステップＳ２１２において、判定部２３４は、隣接ノードの探索等の処理を実施した［現在ノード］内の要素（ｖ）について、データ保存領域のノードＩＤが「ｖ」の全てのエントリの未計算フラグを「ＦＡＬＳＥ」に変更する。これにより、判定部２３４は、その要素（ｖ）を計算済みとする。
そして、判定部２３４は、［現在ノード］内の未計算の要素（ｖ）について処理し終わり、かつ［次計算ノード］が空である場合、ステップＳ２１３へ遷移する。
【００７５】
ステップＳ２１３において、品質指標取得部２３５は、経路情報記憶部２３７のデータ保存領域から、ノードＩＤが「ゴールノードＧ」のエントリを全て抽出し、抽出したそのコストとサービス種別を品質指標算出装置３００へ送信して、ＱｏＥ値を要求する。この要求に応じて、品質指標算出装置３００は、サービス種別に応じた算出方式で、コストに基づいて各経路のＱｏＥ値を算出し、算出した各経路のＱｏＥ値を品質指標取得部２３５に送信する。これにより、品質指標取得部２３５は、品質指標算出装置３００から各経路のＱｏＥ値を取得する。
次に、経路抽出部２３６は、品質指標取得部２３５が取得したＱｏＥ値の中で最も品質の良い経路を抽出し、抽出した径路を示す通信経路情報を経路情報送信部２４０へ出力する。
以上で、本フローチャートの処理を終了する。
【００７６】
続いて、本実施形態の一実施例について、具体例を用いて説明する。通信ネットワークが例えば、図１１のようなトポロジであるとき、スタートノードＳからゴールノードＧまでの経路探索処理の実施例について説明する。
図１１は、通信ネットワークのトポロジの一例である。同図において、各リンクに記載されている値はリンク毎のＱｏＳ値であり、１行目が伝送遅延で２行目がゆらぎである。ここでは簡単化のため、ＱｏＳ値を伝送遅延とゆらぎの二次元で説明する。同図において、スタートノードＳがノードＡ及びＢと接続されている。ノードＡはスタートノードＳに加えてノードＣ及びＤと接続している。また、ノードＢはスタートノードＳに加えて、ノードＤと接続している。また、ノードＣはノードＡに加えてノードＤ及びゴールノードＧと接続している。ノードＤはノードＡ、Ｂ及びＣに加えてゴールノードＧと接続している。
【００７７】
なお、図１１の例では、各リンクの方向性を無視し、同一のＱｏＳ値であるとしているが、方向性毎にＱｏＳ値が異なっていてもよい。
【００７８】
各情報の初期状態は図１２の通りである。なお「Ｉｎｄｅｘ」情報は、以下の説明の為に便宜上設けた情報である。図１２は、経路情報記憶部２３７のデータ保存領域の初期状態のテーブルの一例を示すＴ５−１である。同図にテーブルＴ５−１において、Ｉｎｄｅｘが「１」で、ノードＩＤが「Ｓ」で、経路が「Ｓ」で、コストが「（０,０）」で、未計算フラグが「ＴＲＵＥ」であることが示されている。ここで、コストの１列目が伝送遅延で２列目がゆらぎである。以下、コストを１行の配列で表し、１列目を伝送遅延で、２列目をゆらぎとする。
【００７９】
図１２の場合において、通信経路決定部２３０は、［次計算ノード］にスタートノードＳを示す情報を代入する。これにより、［次計算ノード］＝｛Ｓ｝となる。通信経路決定部２３０は、［次計算ノード］が空でないので以下の処理を実施する。まず、通信経路決定部２３０は、［現在ノード］に［次計算ノード］内の情報を代入する。これにより、［現在ノード］＝｛Ｓ｝となる。
【００８０】
［現在ノード］内の要素はＳのみであり、またデータ保存領域における当該ノードの未計算フラグが「ＴＲＵＥ」の情報が、Ｉｎｄｅｘが「１」の経路情報に存在するので、通信経路決定部２３０は、この情報について処理を実施する。
【００８１】
隣接ノード抽出部２３１は、トポロジ情報より、ノードＳの隣接ノードであるノードＡ及びＢを抽出する。また、このノードを経路とすることでループが発生することはないことから、隣接ノード抽出部２３１は、この二つのノードをコスト算出の対象ノードとする。これにより、［隣接ノード］＝｛Ａ，Ｂ｝となる。
このとき、コスト算出部２３２は、各リンクのコストとＩｎｄｅｘが「１」のコストとの和を各ノードのコストとして算出する。これにより、ノードＡまでのコストが（５，２）で、ノードＢまでのコストが（３，２）となる。
【００８２】
次に、比較処理部２３３は、コストの比較を行うが、現段階では算出したノードＡ、ＢおよびゴールノードＧのコストがデータ保存領域に存在しないため、新たに算出された情報をそのまま経路情報記憶部２３７のデータ保存領域に追記する。そして、比較処理部２３３は、Ｉｎｄｅｘが「１」のデータの未計算フラグを「ＦＡＬＳＥ」にする。これにより、ここまでのデータ保存領域は、図１３のテーブルＴ５−２のようになる。
【００８３】
図１３は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−２である。図１２に比べて、Ｉｎｄｅｘが「１」の未計算フラグが「ＦＡＬＳＥ」となっている点及びＩｎｄｅｘが「２」とＩｎｄｅｘが「３」の経路情報が追記されている点が異なる。
【００８４】
比較処理部２３３は、［次計算ノード］にノードＡ及びＢを示す情報を代入する。これにより、［次計算ノード］＝｛Ａ，Ｂ｝となる。
続いて、通信経路決定部２３０は、［次計算ノード］が空でないので、更に処理を続ける。通信経路決定部２３０は、［現在ノード］に［次計算ノード］の情報を代入させ、［現在ノード］＝｛Ａ，Ｂ｝とする。
【００８５】
例えば、まず、通信経路決定部２３０は、［現在ノード］の要素であるノードＡについて処理を実施する。このとき、通信経路決定部２３０はノードＩＤがＡでかつ未計算フラグがＴＲＵＥの情報としてＩｎｄｅｘとして「２」を抽出する。ここで、ノードＡに接続するノードは「ノードＳ、Ｃ及びＤ」であるが、Ｉｎｄｅｘが「２」における経路情報は「Ｓ→Ａ」である。そのため、通信経路決定部２３０は隣接ノードとして「ノードＣ及びＤ」を抽出する。これにより、［隣接ノード］＝｛Ｃ，Ｄ｝となる。
【００８６】
このとき、コスト算出部２３２は、Ｉｎｄｅｘが「２」におけるコスト（５，２）とノードＡからノードＣまでのリンクのコスト（３，６）を加算して、ノードＣまでのコスト（８，８）を算出する。また、コスト算出部２３２は、Ｉｎｄｅｘが「２」におけるコスト（５，２）とノードＡからノードＤまでのリンクのコスト（１，３）を加算して、ノードＤまでのコスト（６，５）を算出する。
【００８７】
ここでも、経路情報記憶部２３７のデータ保存領域内にノードＣ及びＤの情報が存在しないので、比較処理部２３３は、比較処理を実施せず、上記の情報を経路情報記憶部２３７のデータ保存領域に追記する。また、比較処理部２３３は、ノードＡに関する処理が完了したので、経路情報記憶部２３７のデータ保存領域の未計算フラグをＦＡＬＳＥに変更する。これにより、ここまでのデータ保存領域は、図１４のテーブルＴ５−３のようになる。
【００８８】
図１４は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−３である。図１３に比べて、Ｉｎｄｅｘが「２」の未計算フラグが「ＦＡＬＳＥ」となっている点及びＩｎｄｅｘが「４」とＩｎｄｅｘが「５」の経路情報が追記されている点が異なる。
【００８９】
比較処理部２３３は、［次計算ノード］にノードＣ及びＤを示す情報を代入する。これにより、［次計算ノード］＝｛Ｃ，Ｄ｝となる。
次に、通信経路決定部２３０は［現在ノード］のもう一つの要素であるノードＢについて処理を実施する。このとき、通信経路決定部２３０はノードＩＤがＡでかつ未計算フラグがＴＲＵＥの情報としてＩｎｄｅｘが「３」を抽出する。
そして、隣接ノード抽出部２３１は、ノードＢに隣接し、かつループとならないノードＤを隣接ノードとして抽出する。これにより、［隣接ノード］＝｛Ｄ｝となる。このとき、コスト算出部２３２は、同様の計算方式でＩｎｄｅｘが「３」におけるコスト（３，２）とノードＢからノードＤまでのコスト（１，４）を加算して、ノードＤまでのコスト（４，６）を算出する。
【００９０】
データ保存領域には、ゴールノードＧの情報は存在しないが、ノードＤ  の情報が存在するので、比較処理部２３３は、比較処理を実施する。比較処理部２３３は、ノードＩＤがＤであるＩｎｄｅｘが「５」の情報を参照して、Ｉｎｄｅｘが「５」のコスト（６，５）と新たに算出されたコストは（４，６）とを比較する。伝送遅延については新たに算出した経路の方が品質が良く、ゆらぎについてはデータ保存領域内の経路の方が品質がよい。つまり、比較処理部２３３は、この二つのコストに大小関係を付けることが出来ないため、新たに算出した経路情報を経路情報記憶部２３７のデータ保存領域に追記する。また、比較処理部２３３は、Ｉｎｄｅｘが「３」に関連付けられた未計算フラグを「ＦＡＬＳＥ」にする。ここまでのデータ保存領域は、図１５のテーブルＴ５−４のようになる。
【００９１】
図１５は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−４である。図１４に比べて、Ｉｎｄｅｘが「３」の未計算フラグが「ＦＡＬＳＥ」となっている点及びＩｎｄｅｘが「６」の経路情報が追記されている点が異なる。
【００９２】
次に、比較処理部２３３は、［次計算ノード］にはノードＣとＤが格納されているが、［次計算ノード］に含まれるノードＤを更新する。［次計算ノード］＝｛Ｃ，Ｄ｝のままとなる。次に、通信経路決定部２３０は、［次計算ノード］が空でないので、更に処理を続ける。次に、通信経路決定部２３０は、［現在ノード］に［次計算ノード］を示す情報を移動させ、［現在ノード］＝｛Ｃ，Ｄ｝とする。
【００９３】
例えば、まず、通信経路決定部２３０は、［現在ノード］の要素であるノードＣについて処理を実施することとする。このとき、通信経路決定部２３０は、ノードＩＤがＡでかつ未計算フラグがＴＲＵＥの経路情報としてＩｎｄｅｘが「４」の経路情報を抽出する。通信経路決定部２３０は、Ｉｎｄｅｘが「４」の経路情報について処理を実施する。
【００９４】
隣接ノード抽出部２３１は、「ノードＣ」に対する隣接ノードであるノードＤ及びゴールノードＧを抽出する。これにより、［隣接ノード］＝｛Ｄ，Ｇ｝となる。
このとき、コスト算出部２３２は、各隣接ノードまでのコストを算出する。具体的には、コスト算出部２３２は、Ｉｎｄｅｘが「４」のコスト（８,８）とノードＣからノードＤまでのコスト（１,１）を加算して、ノードＤまでのコスト（９，９）を算出する。また、コスト算出部２３２は、Ｉｎｄｅｘが「４」のコスト（８,８）とノードＣからゴールノードまでのコスト（２，１）を加算して、ノードＧまでのコスト（１０，９）を算出する。
【００９５】
経路情報記憶部２３７のデータ保存領域におけるノードＤに関する経路情報として、Ｉｎｄｅｘが「５」の経路情報及びＩｎｄｅｘが「６」の経路情報が存在し、そのコストはそれぞれ（６，５）及び（４，６）である。新たに算出したノードＤまでのコストは（９，９）であり、コストの全ての要素において「既存コスト＞新規コスト」が成立する経路情報（例えば、Ｉｎｄｅｘが５の経路情報）が存在することから、通信経路決定部２３０は、新たに算出したノードＤまでのコストを破棄する。
【００９６】
次にノードＧに関する情報はデータ保存領域に存在しないため、比較処理部２３３は比較処理を行わず、ノードＧまでの経路情報を経路情報記憶部２３７のデータ保存領域に追記する。また、比較処理部２３３はノードＣに関する未計算フラグをＦＡＬＳＥに変更する。ここまでのデータ保存領域は、図１６のテーブルＴ５−５のようになる。
【００９７】
図１６は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−５である。図１５に比べて、Ｉｎｄｅｘが「４」の未計算フラグが「ＦＡＬＳＥ」となっている点及びＩｎｄｅｘが「７」の経路情報が追記されている点が異なる。隣接ノードＧはゴールノードであるため、比較処理部２３３は隣接ノードＧを［次計算ノード］に追加しない。
【００９８】
続いて、通信経路決定部２３０は、［現在ノード］（＝｛Ｃ，Ｄ｝）におけるノードＣに対して処理が完了したので、次にＤに対する処理を実施する。通信経路決定部２３０は、データ保存領域からノードＩＤがＤでかつ未計算フラグがＴＲＵＥの情報であるＩｎｄｅｘが「５」とＩｎｄｅｘが「６」の二つの経路情報を抽出する。そして、通信経路決定部２３０は、Ｉｎｄｅｘが「５」とＩｎｄｅｘが「６」の二つの経路情報それぞれについて以下の処理を実施する。
【００９９】
隣接ノード抽出部２３１は、Ｉｎｄｅｘが「５」のノードＤに対して、経路がループとならない隣接ノードＢ、Ｃ及びＧを抽出する。これにより、［隣接ノード］＝｛Ｂ，Ｃ,Ｇ｝となる。このとき、コスト算出部２３２は、各隣接ノードまでのコストを同様に算出すると、以下のようになる。ノードＢまでのコストが（７，９）で、ノードＣまでのコストが（７，６）で、ノードＧまでのコストが（７，８）である。
【０１００】
続いて、比較処理部２３３は、ノードＢまでの新規コスト（７，９）と経路情報記憶部２３７のデータ保存領域に存在するゴールノードＧのコスト（１０，９）とを比較する。ノードＢまでの新規コスト（７，９）は、そのゴールノードＧのコスト（１０，９）より品質が良いので、比較処理部２３３は、このノードＢまでの新規コスト（７，９）と経路情報記憶部２３７のデータ保存領域に存在するノードＢのコストとを比較する。ここで、経路情報記憶部２３７のデータ保存領域にノードＢに関する情報としてＩｎｄｅｘが「３」の経路情報が存在し、そのコストは（３，２）であり、新たに算出したコスト（７，９）より品質が良い。そこで、比較処理部２３３は、新たに算出したコスト（７，９）を破棄する。
【０１０１】
続いて、比較処理部２３３は、ノードＣまでの新規コスト（７，６）と経路情報記憶部２３７のデータ保存領域に存在するゴールノードＧのコスト（１０，９）とを比較する。
ノードＣまでの新規コスト（７，６）は、そのゴールノードＧのコスト（１０，９）より良いので、比較処理部２３３は、ノードＣまでの新規コスト（７，６）と経路情報記憶部２３７のデータ保存領域に存在するノードＣのコストとを比較する。ここで、経路情報記憶部２３７のデータ保存領域に、ノードＣに関する情報としてＩｎｄｅｘが「４」の経路情報が存在し、そのコストは（８，８）であり、今回算出したコスト（７，６）より品質が悪い。そこで、比較処理部２３３は、経路情報記憶部２３７のデータ保存領域からＩｎｄｅｘが「４」の経路情報を削除する。
【０１０２】
ここで、削除対象となったＩｎｄｅｘが「４」の経路情報は「Ｓ→Ａ→Ｃ」であるので、比較処理部２３３はこの経路情報を内包する情報を検索する。このとき、Ｉｎｄｅｘが「７」の経路は「Ｓ→Ａ→Ｃ→Ｇ」であり、経路「Ｓ→Ａ→Ｃ」を内包しているため、比較処理部２３３は経路情報記憶部２３７のデータ保存領域からＩｎｄｅｘが「７」の経路情報を削除する。また、比較処理部２３３は隣接ノードＣに関する処理として、今回算出したコスト（７，６）の経路情報を経路情報記憶部２３７のデータ保存領域に追記する。ここまでのデータ保存領域は、図１７のテーブルＴ５−６のようになる。
【０１０３】
図１７は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−６である。図１６に比べて、Ｉｎｄｅｘが「４」の経路情報が削除されている点及びＩｎｄｅｘが「７」の経路情報が追記されている点が異なる。
【０１０４】
比較処理部２３３は、［次計算ノード］にノードＣを示す情報を代入する。これにより、［次計算ノード］＝｛Ｃ｝となる。
続いて、ノードＧに関しては、経路情報記憶部２３７のデータ保存領域に情報が存在しないため、比較処理部２３３は比較処理を行わず、算出したノードＧまでのコスト（７，８）の経路情報を経路情報記憶部２３７のデータ保存領域に追記する。ここまでのデータ保存領域は、図１８のテーブルＴ５−７のようになる。
【０１０５】
図１８は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−７である。図１７に比べて、Ｉｎｄｅｘが「８」の経路情報が追記されている点が異なる。
隣接ノードＧはゴールノードであるため、比較処理部２３３は［次計算ノード］に隣接ノードＧを追加しないため、［次計算ノード］＝｛Ｃ｝となる。
【０１０６】
続いて、隣接ノード抽出部２３１は、Ｉｎｄｅｘが「６」のノードＤに対する隣接ノードＡ、Ｃ及びＧを抽出し、［隣接ノード］＝｛Ａ，Ｃ，Ｇ｝とする。このとき、コスト算出部２３２は、上記各隣接ノードまでのコストを算出すると、ノードＡまでのコストは（５，９）で、ノードＣまでのコストは（５，７）で、ノードＧまでのコストは（５，９）である。
【０１０７】
比較処理部２３３は、ノードＡまでの新規コスト（５，９）と経路情報記憶部２３７のデータ保存領域に存在するゴールノードＧまでのコスト（７，８）とを比較する。コストの要素のうち遅延時間については、ノードＡまでの経路の方がゴールノードＧまでの経路よりも品質が良い。一方。コストの要素のうちゆらぎについては、ノードＡまでの経路の方がゴールノードＧまでの経路よりも品質が悪い。これにより、そのノードＡまでの経路の品質が悪いとは言えない。
【０１０８】
そこで、次に比較処理部２３３は、ノードＡまでの新規コスト（５，９）と経路情報記憶部２３７のデータ保存領域に存在するノードＡまでのコストとを比較する。ここで、ノードＡに関する情報としてＩｎｄｅｘが「２」の経路情報が経路情報記憶部２３７のデータ保存領域に存在し、そのコストは（５，２）である。遅延時間については品質が同じであるが、ゆらぎについては、Ｉｎｄｅｘが「２」の経路の方が新たにコストを算出したノードＡまでの経路よりも品質が良いため、Ｉｎｄｅｘが「２」の経路の方が新たにコストを算出したノードＡまでの経路より品質が良い。そのため、比較処理部２３３は、新たに算出したノードＡまでの新規コスト（５，９）を破棄する。
【０１０９】
続いて、比較処理部２３３は、ノードＣまでの新規コスト（５，７）と経路情報記憶部２３７のデータ保存領域に存在するゴールノードＧのコスト（７，８）とを比較する。ノードＣまでの新規コスト（５，７）は経路情報記憶部２３７のデータ保存領域に存在するゴールノードＧのコスト（７，８）より品質が良いので、次に比較処理部２３３は、ノードＣまでの新規コスト（５，７）と経路情報記憶部２３７のデータ保存領域に存在するノードＣまでのコストとを比較する。ここで、ノードＣに関する情報としてＩｎｄｅｘが「７」の経路情報が経路情報記憶部２３７のデータ保存領域に存在し、そのコストは（７，６）である。比較処理部２３３は、Ｉｎｄｅｘが「７」のコスト（７，６）と新規コスト（５，７）との間で大小関係が付けられない。そのため、比較処理部２３３は、新たにコストを算出したノードＣまでの経路情報を経路情報記憶部２３７のデータ保存領域に追加する。これにより、ここまでのデータ保存領域は、図１９のテーブルＴ５−８のようになる。
【０１１０】
図１９は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−８である。図１８に比べて、Ｉｎｄｅｘが「９」の経路情報が追記されている点が異なる。
【０１１１】
続いて、比較処理部２３３は、ノードＧまでの新規コスト（５，９）と経路情報記憶部２３７のデータ保存領域に存在するゴールノードＧのコスト（７，８）とを比較する。
遅延時間については新たにコストを算出したノードＧまでの経路の方がデータ保存領域に存在するゴールノードＧの経路より品質が良い。一方、ゆらぎについては、新たにコストを算出したノードＧまでの経路は、データ保存領域に存在するゴールノードＧの経路のよりも品質が悪い。このことから、比較処理部２３３は、ノードＧまでの新規コスト（５，９）と経路情報記憶部２３７のデータ保存領域に存在するゴールノードＧのコスト（７，８）との間で大小関係が付けられない。そのため、比較処理部２３３は、新たにコストを算出したノードＧまでの経路情報を経路情報記憶部２３７のデータ保存領域に追記する。これにより、ここまでのデータ保存領域は、図２０のテーブルＴ５−９のようになる。
【０１１２】
図２０は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−９である。図１９に比べて、Ｉｎｄｅｘが「１０」の経路情報が追記されている点が異なる。
【０１１３】
以上で、ノードＤに対する処理が終了したので、通信経路決定部２３０は、経路情報記憶部２３７のデータ保存領域においてノードＩＤが「Ｄ」であるＩｎｄｅｘが５とＩｎｄｅｘが６の経路情報の未計算フラグをＦＡＬＳＥに変更する。これにより、ここまでのデータ保存領域は、図２１のテーブルＴ５−１０のようになる。
【０１１４】
図２１は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−１０である。図２０に比べて、Ｉｎｄｅｘが「５及び６」の経路情報の未計算フラグが「ＦＡＬＳＥ」に変更になっている点が異なる。
【０１１５】
続いて、比較処理部２３３は、［次計算ノード］にノードＣを示す情報を移動させて、［次計算ノード］＝｛Ｃ｝とする。
次に、通信経路決定部２３０は、［現在ノード］に［次計算ノード］情報を移動させて、［現在ノード］＝｛Ｃ｝とする。通信経路決定部２３０は、［次計算ノード］が空でないので、更に処理を続ける。
【０１１６】
通信経路決定部２３０は、データ保存領域からノードＩＤがＣでかつ未計算フラグがＴＲＵＥの情報であるＩｎｄｅｘが「７」とＩｎｄｅｘが「９」の二つ経路情報を抽出する。そして、通信経路決定部２３０は、抽出した経路情報それぞれについて処理を実施する。
続いて、隣接ノード抽出部２３１は、Ｉｎｄｅｘが「７」のノードＣに対して、経路がループとならない隣接ノードＧを抽出し、［隣接ノード］にノードＧを示す情報を移動させて、［隣接ノード］＝｛Ｇ｝とする。
【０１１７】
このとき、コスト算出部２３２は、Ｉｎｄｅｘが「７」のコスト（７，６）と、ノードＣからノードＧまでのコスト（２，１）を加算して、隣接ノードＧまでのコストを（９，７）と算出する。
そして、比較処理部２３３は、この隣接ノードＧまでの新規コスト（９，７）と経路情報記憶部２３７のデータ保存領域に存在するノードＩＤがＧのコストとを比較する。ここで、図２１を参照すると経路情報記憶部２３７のデータ保存領域には、ノードＩＤがＧの経路情報が二つ（Ｉｎｄｅｘが「８」とＩｎｄｅｘが「１０」）存在し、そのコストはそれぞれ（７，８）／（５，９）である。このとき、比較処理部２３３は、そのどちらのコストも新規コスト（９，７）と大小関係を決定することが出来ないため、新たにコストを算出したノードＧまでの経路情報を経路情報記憶部２３７のデータ保存領域に追記する。これにより、ここまでのデータ保存領域は、図２２のテーブルＴ５−１１のようになる。
【０１１８】
図２２は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−１１である。図２１に比べて、Ｉｎｄｅｘが「１１」の経路情報が追加されている点が異なる。
【０１１９】
次に、隣接ノード抽出部２３１は、Ｉｎｄｅｘが「９」のノードＣに対して経路がループとならない隣接ノードＡ及びＧを抽出し、［隣接ノード］にノードＡ及びＧの情報を移動させて、［隣接ノード］＝｛Ａ，Ｇ｝とする。
このとき、同様の処理で、比較処理部２３３が、各隣接ノードまでのコストを算出すると、以下のようになる。ノードＡまでのコストは（８，１３）で、ノードＧまでのコストは（７，８）である。
【０１２０】
ノードＡまでの新規コスト（８，１３）は、経路情報記憶部２３７のデータ保存領域内のＩｎｄｅｘが８のノードＧのコスト（７，８）より大きく、品質が悪いので、比較処理部２３３は、ノードＡまでの新規コスト（８，１３）を破棄する。
また、ノードＧまでの新規コスト（７，８）は、経路情報記憶部２３７のデータ保存領域内のＩｎｄｅｘが８のノードＧのコスト（７，８）以上となるので、比較処理部２３３は、ノードＧまでの新規コスト（７，８）を破棄する。
以上により、通信経路決定部２３０は、ノードＣにおける処理が完了したので、データ保存領域においてノードＩＤがＣであるＩｎｄｅｘが７と９の経路情報の未計算フラグをＦＡＬＳＥに変更する。これにより、ここまでのデータ保存領域は、図２３のテーブルＴ５−１２のようになる。
【０１２１】
図２３は、通信経路決定部２３０の処理過程における経路情報記憶部２３７のデータ保存領域の一例を示すテーブルＴ５−１２である。図２２に比べて、Ｉｎｄｅｘが「７及び９」の経路情報の未計算フラグが「ＦＡＬＳＥ」に変更になっている点が異なる。
【０１２２】
ここまでの処理によって［次計算ノード］が空となったため、次に通信経路決定部２３０は、経路情報記憶部２３７のデータ保存領域内の経路情報に基づいて経路決定処理を行う。
まず、通信経路決定部２３０は、データ保存領域からノードＩＤがゴールノードＧであるＩｎｄｅｘが８、１０及び１１の経路情報を抽出する。ここで、抽出された経路情報は、図２４のテーブルＴ６に示された経路情報である。
【０１２３】
図２４は、ノードＩＤがゴールノードＧである経路情報の一例を示すテーブルＴ６である。同図において、Ｉｎｄｅｘが８、１０及び１１の経路情報が示されている。
品質指標取得部２３５は、図２４のテーブルＴ６に示された各コストとサービス種別を品質指標算出装置３００に出力する。品質指標算出装置３００は、サービス種別により決められる算出方式で、各コストに応じたＱｏＥを算出する。そして、品質指標取得部２３５は、品質指標算出装置３００が算出したＱｏＥを示すＱｏＥ情報を品質指標算出装置３００から取得する。ここで得られたＱｏＥが図２５のテーブルＴ７に示されたＱｏＥであったとする。
【０１２４】
図２５は、図２４に示されたコストに対応するＱｏＥの一例を示すテーブルＴ７である。このとき、品質指標取得部２３５が取得したＱｏＥが最大となる経路情報はＩｎｄｅｘが「１０」であることから、経路抽出部２３６は、Ｉｎｄｅｘが「１０」の経路「Ｓ→Ｂ→Ｄ→Ｇ」を通信経路として抽出する。
【０１２５】
以上、本実施形態の経路決定装置２００は、ネットワーク内のリンク毎の多次元のＱｏＳ情報に基づき、経路探索を実施する。本実施形態の経路決定装置２００は、その経路探索中に、同一のノードまでの経路について複数のＱｏＥが取り得る場合、コストの品質が悪い方の経路情報を削除する。これにより、経路決定装置２００は、コストの品質が悪い方の経路を包含する経路については、それ以上探索する必要がないので、良好なＱｏＥが得られる可能性がある経路を効率的に探索することができる。これにより、経路決定装置２００は、変化するネットワークの状態に応じてユーザの体感品質が最良となる経路を効率的に探索することができる。
また、経路決定装置２００が出力する通信経路は、ユーザの体感品質に基づき最良となる経路であることから、ＯＳＰＦ等の既存の経路決定方法と比べ、輻輳などの発生が抑制される。また、本制御が行われるネットワーク利用者の解約率の低減が期待できる。
【０１２６】
なお、複数の装置を備えるシステムが、本実施形態の経路決定装置２００の各処理を、それらの複数の装置で分散して処理してもよい。
また、本実施形態の経路決定装置２００と品質指標算出装置３００の処理を同一の装置が処理してもよい。
また、本実施形態の通信システム１及び経路決定装置２００の各処理を実行するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、当該記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、それぞれ通信システム１及び経路決定装置２００に係る上述した種々の処理を行ってもよい。
【０１２７】
なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【０１２８】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ））のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１２９】
以上、本発明の実施形態について図面を参照して詳述したが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【０１３０】
１  通信システム
１０  管理対象ネットワーク
１１、１２、１３、１４、１５、１６、１７  パケット転送装置
１００  ＮＷ情報収集装置
２００  経路決定装置
２１０  フロー情報取得部
２２０  ＮＷ情報取得部
２３０  通信経路決定部
２３１  隣接ノード抽出部
２３２  コスト算出部
２３３  比較処理部
２３４  判定部
２３５  品質指標取得部
２３６  経路抽出部
２３７  経路情報記憶部
２３８  決定部
２４０  経路情報送信部
３００  品質指標算出装置
４００  通信フロー制御装置
【図１】
0005651619.tif 000002
【図２】
0005651619.tif 000003
【図３】
0005651619.tif 000004
【図４】
0005651619.tif 000005
【図５】
0005651619.tif 000006
【図６】
0005651619.tif 000007
【図７】
0005651619.tif 000008
【図８】
0005651619.tif 000009
【図９】
0005651619.tif 000010
【図１０】
0005651619.tif 000011
【図１１】
0005651619.tif 000012
【図１２】
0005651619.tif 000013
【図１３】
0005651619.tif 000014
【図１４】
0005651619.tif 000015
【図１５】
0005651619.tif 000016
【図１６】
0005651619.tif 000017
【図１７】
0005651619.tif 000018
【図１８】
0005651619.tif 000019
【図１９】
0005651619.tif 000020
【図２０】
0005651619.tif 000021
【図２１】
0005651619.tif 000022
【図２２】
0005651619.tif 000023
【図２３】
0005651619.tif 000024
【図２４】
0005651619.tif 000025
【図２５】
0005651619.tif 000026