(57)【要約】【課題】inclusive route指定をした経路計算において、遅延制約値を満たす最短経路を計算する。【解決手段】経路計算装置１が、始点ノード２Ａから終点ノード２Ｄまでの経路の遅延制約値を、inclusive route指定により区切られる区間（中継ノード２Ｂ，２Ｃで区切られる区間）で分割する。そして、各区間ごとに、その分割された遅延制約値を満たし、かつリンクコストが最も小さい経路（最短経路）を探索する。ここで、分割された遅延制約値を満たす経路が見つからなかった区間については、遅延制約値を満たす区間から遅延制約値を分け与え、変更する。そして、その変更後の遅延制約値を満たす経路を再度探索し、遅延制約値を満たす経路を探索する。【選択図】図１
2008048114.tif 000002
【特許請求の範囲】
【請求項１】
各種データの入出力を司る入出力部と、ネットワーク経由で通信を行う通信部と、前記ネットワークを構成するノードのトポロジ情報および前記ノードを接続するリンクのリンクコスト情報を記憶する記憶部と、前記トポロジ情報および前記リンクコスト情報を参照して経路計算を行う処理部とを備える経路計算装置が、
前記入出力部経由で、前記ネットワーク内の経路における始点ノードから終点ノードまでの間で経由する中継ノードの識別情報の入力を受け付ける中継ノード入力ステップと、
前記入出力部経由で、前記始点ノードから前記終点ノードまでの通信における遅延時間の上限値である遅延制約値の入力を受け付ける遅延制約値入力ステップと、
前記入力された遅延制約値を、前記始点ノードから前記終点ノードまでの経路を前記中継ノードで区切った各区間に分割して割り当てる遅延制約値割り当てステップと、
前記通信部経由で、前記各ノード間の実際の遅延時間を取得し、前記記憶部に記憶する遅延時間取得ステップと、
前記取得した前記各ノード間の実際の遅延時間、前記トポロジ情報およびリンクコスト情報を参照して、前記各区間ごとに、当該区間における実際の遅延時間が、当該区間に割り当てた遅延制約値以下となり、かつ、リンクコストが最小となる経路の経路計算を行い、前記計算した経路を前記記憶部に記憶する経路計算ステップと、
を実行することを特徴とする経路計算方法。
【請求項２】
前記経路計算ステップにおいて、前記各区間のうち、当該区間における実際の遅延時間が、当該区間に割り当てた遅延制約値以下となる経路が計算できなかった区間である第１の区間と、当該区間に割り当てた遅延制約値以下となる経路が計算できた区間である第２の区間とがあったとき、
前記第２の区間に割り当てた遅延制約値を、前記第１の区間に割り当てられた遅延制約値に分配して、前記記憶部に記憶された当該第１の区間における遅延制約値を変更し、前記変更した遅延制約値に基づき、前記第１の区間の前記経路計算を再度実行することを特徴とする請求項１に記載の経路計算方法。
【請求項３】
各種データの入出力を司る入出力部と、ネットワーク経由で通信を行う通信部と、前記ネットワークを構成するノードのトポロジ情報および前記ノードを接続するリンクのリンクコスト情報を記憶する記憶部と、前記トポロジ情報および前記リンクコスト情報を参照して経路計算を行う処理部とを備える経路計算装置が、
前記入出力部経由で、前記ネットワーク内の経路における始点ノードから終点ノードまでの間で経由する中継ノードの識別情報の入力を受け付け、前記記憶部に記憶する中継ノード入力ステップと、
前記入出力部経由で、前記始点ノードから前記終点ノードまでの通信における遅延時間の上限値である遅延制約値の入力を受け付け、前記記憶部に記憶する遅延制約値入力ステップと、
前記トポロジ情報および前記リンクコスト情報を参照して、前記始点ノードから前記終点ノードまでの経路を、前記中継ノードで区切った各区間ごとに、当該区間のリンクコストが最小となる最短経路を計算し、前記記憶部に記憶する最短経路計算ステップと、
前記通信部経由で、前記各ノード間の実際の遅延時間を取得し、前記記憶部に記憶する遅延時間取得ステップと、
前記取得した前記各ノード間の実際の遅延時間から、前記各区間における実際の遅延時間を計算し、この計算した遅延時間の合計値が、前記入力された遅延制約値を超えるか否かを判断する遅延時間判断ステップと、
を実行し、
前記遅延時間判断ステップにおいて、前記計算した実際の遅延時間の合計値が、前記入力された遅延制約値を超えると判断されたとき、
前記リンクコスト情報を参照して、前記各区間のリンクコストを計算し、前記計算したリンクコストが大きい区間から順に、当該区間において遅延時間が最短となる経路を計算する経路計算ステップと、
前記記憶部に記憶された当該区間の経路を、前記計算した遅延時間が最短となる経路に置き換える経路置き換えステップとを、
前記経路置き換え後における前記各区間の実際の遅延時間の合計値が、前記入力された遅延制約値以下になるまで実行すること
を特徴とする経路計算方法。
【請求項４】
前記遅延時間判断ステップにおいて、前記計算した実際の遅延時間の合計値が、前記入力された遅延制約値を超えると判断されたとき、
前記各区間のうち、前記計算した実際の遅延時間が長い区間から順に、前記最短経路計算ステップと前記経路置き換えステップとを実行することを特徴とする請求項３に記載の経路計算方法。
【請求項５】
請求項１ないし請求項４のいずれか１項に記載の経路計算方法を、コンピュータである前記経路計算装置に実行させることを特徴とする経路計算プログラム。
【請求項６】
遅延制約を考慮した経路計算装置であって、
ネットワークを構成するノードのトポロジ情報および前記ノードを接続するリンクのリンクコスト情報を記憶する記憶部と、
前記ネットワーク経由で通信を行う通信部と、
前記ネットワーク内の経路における始点ノードから終点ノードまでの間で経由する中継ノードの識別情報の入力を受け付け、前記記憶部に記憶する中継ノード入力部と、
前記入出力部経由で、前記始点ノードから前記終点ノードまでの通信における遅延時間の上限値である遅延制約値の入力を受け付け、前記記憶部に記憶する遅延制約値入力部と、
前記入力された遅延制約値を、前記始点ノードから前記終点ノードまでの経路を前記中継ノードで区切った各区間に分割して割り当てる遅延制約値割り当て部と、
前記通信部経由で、前記各ノード間の実際の遅延時間を取得し、前記記憶部に記憶する遅延時間取得部と、
前記取得した前記各ノード間の実際の遅延時間、前記トポロジ情報およびリンクコスト情報を参照して、前記各区間ごとに、当該区間における実際の遅延時間が、当該区間に割り当てた遅延制約値以下となり、かつ、リンクコストが最小となる経路の経路計算を行い、前記計算した経路を前記記憶部に記憶する経路計算部と、
を備えることを特徴とする経路計算装置。
【請求項７】
遅延制約を考慮した経路計算装置であって、
ネットワークを構成するノードのトポロジ情報および前記ノードを接続するリンクのリンクコスト情報を記憶する記憶部と、
前記ネットワーク経由で通信を行う通信部と、
前記ネットワーク内の経路における始点ノードから終点ノードまでの間で経由する中継ノードの識別情報の入力を受け付け、前記記憶部に記憶する中継ノード入力部と、
前記入出力部経由で、前記始点ノードから前記終点ノードまでの通信における遅延時間の上限値である遅延制約値の入力を受け付け、前記記憶部に記憶する遅延制約値入力部と、
前記トポロジ情報および前記リンクコスト情報を参照して、前記始点ノードから前記終点ノードまでの経路を、前記中継ノードで区切った各区間ごとに、当該区間のリンクコストが最小となる最短経路を計算し、前記記憶部に記憶する経路計算部と、
前記各ノード間の実際の遅延時間を取得し、前記記憶部に記憶する遅延時間取得部と、
前記取得した前記各ノード間の実際の遅延時間から、前記各区間における実際の遅延時間を計算し、この計算した遅延時間の合計値が、前記入力された遅延制約値を超えるか否かを判断する遅延時間判断部と、
を備え、
前記経路計算部は、
前記遅延時間判断部において、前記計算した実際の遅延時間の合計値が、前記入力された遅延制約値を超えると判断されたとき、
前記リンクコスト情報を参照して、前記各区間のリンクコストを計算し、前記計算したリンクコストが大きい区間から順に、当該区間において遅延時間が最短となる経路を計算し、前記記憶部に記憶された当該区間の経路を、前記計算した遅延時間が最短となる経路に置き換え、前記経路置き換え後における前記各区間の実際の遅延時間の合計値が、前記入力された遅延制約値以下になるまで実行することを特徴とする経路計算装置。
【請求項８】
前記経路計算部は、
前記遅延時間判断部において、前記計算した実際の遅延時間の合計値が、前記入力された遅延制約値を超えると判断されたとき、
前記計算した実際の遅延時間が大きい区間から順に、当該区間において遅延時間が最短となる経路を計算し、前記記憶部に記憶された当該区間の経路を、前記計算した遅延時間が最短となる経路に置き換え、前記経路置き換え後における前記各区間の実際の遅延時間の合計値が、前記入力された遅延制約値以下になるまで実行することを特徴とする請求項７に記載の経路計算装置。
【請求項９】
請求項６ないし請求項８のいずれか１項に記載の経路計算装置の機能を備えることを特徴とするノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の制約条件を考慮した経路計算技術に関する。
【背景技術】
【０００２】
近年、ネットワークの高速大容量化に伴い、音声・映像のストリーミングサービスが普及している。これらのサービスを提供するアプリケーションには、遅延やパケットロスによる品質劣化を防ぐために、ＱｏＳ（Quality of Service）制約と充分な帯域が与えられる必要がある。
【０００３】
ここで、限りある帯域を効率よく利用し、かつ、要求されるＱｏＳに対応できるような経路を設定するため、ネットワーク内のサーバまたはルータにはＣＳＰＦ(Constrained Shortest Path First)機能が備えられている。このＣＳＰＦ機能とは、シグナリング情報をやりとりするモジュール等、外部からの要求に基づいて、制約を満たすパスの経路を計算し、外部に対して経路を回答する機能、つまり制約付きの最短経路（リンクコストが最短になる経路）の計算を行う機能である。
【０００４】
また、音声や映像のストリーミングといった厳しいＱｏＳが要求されるトラヒックにおいては、特に遅延の制約条件を満たすことが重要である。このため、遅延の制約条件を満たす経路を計算する様々なアルゴリズムが提案されている（例えば、非特許文献１，２参照）。これらのアルゴリズムは、リンクコストと遅延に関する情報とに基づいて、遅延の制約条件（遅延制約値）を満たす最短経路を計算するものである。
【０００５】
ところで、限られたネットワーク資源の有効活用や、ＱｏＳ制御、または事業者の運用上の都合により、パス設定時に必ず経由すべき箇所を指定する（inclusive route指定する）場合がある。このinclusive route指定を考慮して経路計算を行うには、始点ノードと指定ノード（inclusive route指定したノード）１、指定ノード１と指定ノード２、以下同様に指定ノードＮと終点ノード、という具合に区間に分けて、各区間独立に経路計算を行い、最後にそれら経路を足し合わせることでend-to-endの経路を得る。
【非特許文献１】X Douglas S.Reeves, and Hussein F.Salama,”A Distributed Algorithm for Delay-Constrained Unicast Routing,”IEEE/ACM TRANSACTIONS ON NETWORKING,VOL.8,NO.2,APRIL2000.
【非特許文献２】XinJin; Xiande Liu;Shiyuan Xiao, ”An effective algorithm for delay Constrained least cost unicast routing,”Circuits and Systems,2005.IEEE International Symposium on.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、前記したアルゴリズムはいずれも、inclusive route指定をした場合の制約条件を考慮したものではない。このため、inclusive route指定した各区間ごとの経路計算を行うと、各区間における遅延時間の合計がend-to-endでの遅延制約値を満たさないことがある。
【０００７】
そこで、本発明は、前記した問題を解決し、inclusive route指定をした場合において、end-to-endでの遅延制約値を満たす最短経路を計算する手段を提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記した課題を解決するため、経路計算装置において、遅延制約値をinclusive route指定により区切られた区間、つまりinclusive node（中継ノード）により区切られた各区間に分割し、各区間ごとにその分割された遅延制約値を満たし、かつ、リンクコストが最も小さい経路（最短経路）を計算する構成とした。また、経路計算装置において、まず、各区間ごとにリンクコストが最も小さい経路（最短経路）を計算する。そして、全区間を最短経路としたときの遅延時間を計算し、この計算した遅延時間が、遅延制約値を超えなければ、その計算した経路を計算結果として出力する。一方、遅延時間の合計値が、遅延制約値を超えるときは、リンクコストが大きい区間（あるいは遅延時間が長い区間）から順に、遅延時間が最も短くなる経路を計算する。そして、遅延時間の合計値が、その遅延制約値を満たすようになったとき、当該区間における最短経路を、遅延時間が最も短い経路に置き換えて出力する構成とした。
【０００９】
すなわち、請求項１に記載の発明は、各種データの入出力を司る入出力部と、ネットワーク経由で通信を行う通信部と、前記ネットワークを構成するノードのトポロジ情報および前記ノードを接続するリンクのリンクコスト情報を記憶する記憶部と、前記トポロジ情報および前記リンクコスト情報を参照して経路計算を行う処理部とを備える経路計算制御装置が、前記入出力部経由で、前記ネットワーク内の経路における始点ノードから終点ノードまでの間で経由する中継ノードの識別情報の入力を受け付ける中継ノード入力ステップと、前記入出力部経由で、前記始点ノードから前記終点ノードまでの通信における遅延時間の上限値である遅延制約値の入力を受け付ける遅延制約値入力ステップと、前記入力された遅延制約値を、前記始点ノードから前記終点ノードまでの経路を前記中継ノードで区切った各区間に分割して割り当てる遅延制約値割り当てステップと、前記通信部経由で、前記各ノード間の実際の遅延時間を取得し、前記記憶部に記憶する遅延時間取得ステップと、前記取得した前記各ノード間の実際の遅延時間、前記トポロジ情報およびリンクコスト情報を参照して、前記各区間ごとに、当該区間における実際の遅延時間が、当該区間に割り当てた遅延制約値以下となり、かつ、リンクコストが最小となる経路の経路計算を行い、前記計算した経路を前記記憶部に記憶する経路計算ステップとを実行する方法とした。
【００１０】
請求項６に記載の発明は、遅延制約を考慮した経路計算装置であって、ネットワークを構成するノードのトポロジ情報および前記ノードを接続するリンクのリンクコスト情報を記憶する記憶部と、前記ネットワーク経由で通信を行う通信部と、前記ネットワーク内の経路における始点ノードから終点ノードまでの間で経由する中継ノードの識別情報の入力を受け付け、前記記憶部に記憶する中継ノード入力部と、前記入出力部経由で、前記始点ノードから前記終点ノードまでの通信における遅延時間の上限値である遅延制約値の入力を受け付け、前記記憶部に記憶する遅延制約値入力部と、前記入力された遅延制約値を、前記始点ノードから前記終点ノードまでの経路を前記中継ノードで区切った各区間に分割して割り当てる遅延制約値割り当て部と、前記通信部経由で、前記各ノード間の実際の遅延時間を取得し、前記記憶部に記憶する遅延時間取得部と、前記取得した前記各ノード間の実際の遅延時間、前記トポロジ情報およびリンクコスト情報を参照して、前記各区間ごとに、当該区間における実際の遅延時間が、当該区間に割り当てた遅延制約値以下となり、かつ、リンクコストが最小となる経路の経路計算を行い、前記計算した経路を前記記憶部に記憶する経路計算部とを備える構成とした。
【００１１】
このようにすることで、経路計算装置は、始点ノードから終点ノードまでの遅延制約値（end-to-endでの遅延制約値）を、inclusive route指定により区切られた各区間、つまり中継ノードにより区切られた区間に分割する。そして、各区間ごとにその分割された遅延制約値を満たし、かつ、リンクコストが最も小さい経路（最短経路）を計算する。従って、inclusive route指定をした場合においても、end-to-endでの遅延制約値を満たす最短経路を計算することができる。
【００１２】
請求項２の発明は、請求項１に記載の経路計算方法において、経路計算ステップにおいて、前記各区間のうち、当該区間における実際の遅延時間が、当該区間に割り当てた遅延制約値以下となる経路が計算できなかった区間である第１の区間と、当該区間に割り当てた遅延制約値以下となる経路が計算できた区間である第２の区間とがあったとき、前記第２の区間に割り当てた遅延制約値を、前記第１の区間に割り当てられた遅延制約値に分配して、前記記憶部に記憶された当該第１の区間における遅延制約値を変更し、前記変更した遅延制約値に基づき、前記第１の区間の前記経路計算を再度実行する方法とした。
【００１３】
この方法によれば、経路計算装置は、各区間のうち、遅延制約値以下となる経路が計算できた区間の遅延制約値を、遅延制約値以下となる経路が計算できなかった区間に分配して変更し、この変更後の遅延制約値を満たす経路を再度計算するので、end-to-endでの遅延制約値を満たす経路を発見しやすくなる。
【００１４】
請求項３に記載の発明は、各種データの入出力を司る入出力部と、ネットワーク経由で通信を行う通信部と、前記ネットワークを構成するノードのトポロジ情報および前記ノードを接続するリンクのリンクコスト情報を記憶する記憶部と、前記トポロジ情報および前記リンクコスト情報を参照して経路計算を行う処理部とを備える経路計算制御装置が、前記入出力部経由で、前記ネットワーク内の経路における始点ノードから終点ノードまでの間で経由する中継ノードの識別情報の入力を受け付け、前記記憶部に記憶する中継ノード入力ステップと、前記入出力部経由で、前記始点ノードから前記終点ノードまでの通信における遅延時間の上限値である遅延制約値の入力を受け付け、前記記憶部に記憶する遅延制約値入力ステップと、前記トポロジ情報および前記リンクコスト情報を参照して、前記始点ノードから前記終点ノードまでの経路を、前記中継ノードで区切った各区間ごとに、当該区間のリンクコストが最小となる最短経路を計算し、前記記憶部に記憶する最短経路計算ステップと、前記通信部経由で、前記各ノード間の実際の遅延時間を取得し、前記記憶部に記憶する遅延時間取得ステップと、前記取得した前記各ノード間の実際の遅延時間から、前記各区間における実際の遅延時間を計算し、この計算した遅延時間の合計値が、前記入力された遅延制約値を超えるか否かを判断する遅延時間判断ステップと、を実行し、前記遅延時間判断ステップにおいて、前記計算した実際の遅延時間の合計値が、前記入力された遅延制約値を超えると判断されたとき、前記リンクコスト情報を参照して、前記各区間のリンクコストを計算し、前記計算したリンクコストが大きい区間から順に、当該区間において遅延時間が最短となる経路を計算する経路計算ステップと、前記記憶部に記憶された当該区間の経路を、前記計算した遅延時間が最短となる経路に置き換える経路置き換えステップとを、前記経路置き換え後における前記各区間の実際の遅延時間の合計値が、前記入力された遅延制約値以下になるまで実行する方法とした。
【００１５】
請求項７に記載の発明は、遅延制約を考慮した経路計算装置であって、ネットワークを構成するノードのトポロジ情報および前記ノードを接続するリンクのリンクコスト情報を記憶する記憶部と、前記ネットワーク経由で通信を行う通信部と、前記ネットワーク内の経路における始点ノードから終点ノードまでの間で経由する中継ノードの識別情報の入力を受け付け、前記記憶部に記憶する中継ノード入力部と、前記入出力部経由で、前記始点ノードから前記終点ノードまでの通信における遅延時間の上限値である遅延制約値の入力を受け付け、前記記憶部に記憶する遅延制約値入力部と、前記トポロジ情報および前記リンクコスト情報を参照して、前記始点ノードから前記終点ノードまでの経路を、前記中継ノードで区切った各区間ごとに、当該区間のリンクコストが最小となる最短経路を計算し、前記記憶部に記憶する経路計算部と、前記各ノード間の実際の遅延時間を取得し、前記記憶部に記憶する遅延時間取得部と、前記取得した前記各ノード間の実際の遅延時間から、前記各区間における実際の遅延時間を計算し、この計算した遅延時間の合計値が、前記入力された遅延制約値を超えるか否かを判断する遅延時間判断部と、を備え、前記経路計算部は、前記遅延時間判断部において、前記計算した実際の遅延時間の合計値が、前記入力された遅延制約値を超えると判断されたとき、前記リンクコスト情報を参照して、前記各区間のリンクコストを計算し、前記計算したリンクコストが大きい区間から順に、当該区間において遅延時間が最短となる経路を計算し、前記記憶部に記憶された当該区間の経路を、前記計算した遅延時間が最短となる経路に置き換え、前記経路置き換え後における前記各区間の実際の遅延時間の合計値が、前記入力された遅延制約値以下になるまで実行する構成とした。
【００１６】
このような経路計算装置は、まず、inclusive route指定により区切られた（中継ノードにより区切られた）各区間の最短経路を計算する。そして、各区間ごとの遅延時間を合計した値が、遅延制約値を満たすか否かを確認する。つまり、全区間を最短経路としたときの遅延時間が遅延制約値を満たすか否かを確認する。そして、全区間を最短経路としたときの遅延時間が遅延制約値を満たす場合、その最短経路を計算結果として出力する。従って、inclusive route指定をした場合において、end-to-endでの遅延制約値を満たしつつ、リンクコストが最も小さい経路(最短経路)を計算することができる。
【００１７】
請求項４に記載の発明は、請求項３に記載の経路計算方法において、前記遅延時間判断ステップにおいて、前記計算した実際の遅延時間の合計値が、前記入力された遅延制約値を超えると判断されたとき、前記各区間のうち、前記計算した実際の遅延時間が長い区間から順に、前記最短経路計算ステップと前記経路置き換えステップとを実行する方法とした。
【００１８】
請求項８に記載の発明は、請求項７に記載の経路計算装置において、前記経路計算部は、前記遅延時間判断部において、前記計算した実際の遅延時間の合計値が、前記入力された遅延制約値を超えると判断されたとき、前記計算した実際の遅延時間が大きい区間から順に、当該区間において遅延時間が最短となる経路を計算し、前記記憶部に記憶された当該区間の経路を、前記計算した遅延時間が最短となる経路に置き換え、前記経路置き換え後における前記各区間の実際の遅延時間の合計値が、前記入力された遅延制約値以下になるまで実行する構成とした。
【００１９】
このようにすることで、経路計算装置は、全区間を最短経路にしたときの遅延時間の合計値が、遅延制約値を満たさないときでも、遅延制約値を満たす経路を計算することができる。このとき、リンクコストの大きい区間から順に経路再計算を行うので、遅延制約値を満たす最短経路を計算するときの計算量を、できるだけ少なくすることができる。
【００２０】
請求項５に記載の発明は、請求項１ないし請求項４のいずれか１項に記載の経路計算方法を、コンピュータである前記経路計算装置に実行させることを特徴とする経路計算プログラムとした。
【００２１】
このようにすることで、コンピュータに、請求項１ないし請求項４のいずれか１項に記載の経路計算方法を実行させることができる。
【００２２】
請求項９に記載の発明は、請求項６ないし請求項８のいずれか１項に記載の経路計算装置の機能を備えるノードとした。
【００２３】
このようにすることで、ノードとは別個に経路計算装置を設ける必要がなくなる。
【発明の効果】
【００２４】
本発明によれば、経路設定においてinclusive route指定をした場合に、end-to-endでの遅延制約を満たす最短経路を計算することができる。従って、厳しいＱｏＳが要求されるトラヒックにおいて、ネットワークの管理者等は所望の経路を設定しやすくなる。
【発明を実施するための最良の形態】
【００２５】
以下、本発明を実施するための最良の形態（以下、実施の形態という）を、第１の実施の形態および第２の実施の形態に分けて説明する。
【００２６】
≪第１の実施の形態≫
まず、本発明の第１の実施の形態の経路計算装置を説明する。この経路計算装置は、inclusive route指定により区切られた区間それぞれに、end-to-endの遅延制約値を分割し割り当て、各区間に割り当てられた遅延制約値を満たす経路を計算することを特徴とする。
【００２７】
図１は、第１の実施の形態の経路計算装置を説明する図である。図１に示すように、ネットワークは、ノード２（２Ａ，２Ｂ，２Ｃ，２Ｄ）と、このノード２との間に設定されるパスの経路計算を行う経路計算装置１とを含んで構成される。このノード２と経路計算装置１とは、通信可能に接続されている。
【００２８】
なお、このネットワークは、ＴＤＭ（Time Division Multiplexing）やＷＤＭ（Wavelength Division Multiplexing）等の回線交換ネットワーク、または、ＩＰ（Internet Protocol）やイーサネット（登録商標）、ＭＰＬＳ（Multi-Protocol Label Switching）により実現され、ノード２は、ＭＰＬＳ網のＭＰＬＳルータ、パケット網のルータ、光網の光クロスコネクト等により実現される。ここで、ノード２Ａからノード２Ｄまでの間にはパス（論理パス）が設定される。
【００２９】
＜動作概要＞
ここで、第１の実施の形態の経路計算装置１の動作概要を、図１を参照しながら説明する。
【００３０】
まず、経路計算装置１は、始点ノード（ノード２Ａ）から終点ノード（ノード２Ｄ）までの経路において、中継ノード（ノード２Ｂ，２Ｃ）の指示入力を受け付ける。つまりinclusive route指定において経由すべきノード（inclusive node）の入力を受け付ける。また、経路計算装置１は、このノード２Ａからノード２Ｄまでの経路における遅延時間の上限値（end-to-endの遅延制約値）の入力を受け付ける。例えば、「遅延制約値＝３０ｍｓ以下」という情報の入力を受け付ける。
【００３１】
経路計算装置１は、中継ノードで区切られた各区間＃１〜区間＃３それぞれに、end-to-endでの遅延制約値を分割し、割り当てる。例えば、end-to-endでの遅延制約値を各区間に均等に１０ｍｓずつ分割し、割り当てる。そして、経路計算装置１は、各区間に割り当てられた遅延制約値を満たす経路を計算する。つまり、ここでは図示を省略しているが、区間＃１〜区間＃３はそれぞれリンク接続されたノードが設置され、遅延制約値を満たすには、どのリンクを経由すればよいかを計算（探索）する。計算した結果、すべての区間について、遅延制約値を満たす経路を計算できれば（経路を発見できれば）、その経路を計算結果として出力する。一方、遅延制約値を満たす経路を計算できない区間（第１の区間）があれば、その区間に、遅延制約を満たす経路を計算できた区間（第２の区間）において余った遅延制約値を分け与える。
【００３２】
例えば、図１に例示するネットワークにおいて、経路計算装置１が、区間＃１および区間＃３については、遅延制約値１０ｍｓを満たす経路を発見できたが、区間＃２においては、遅延制約値１０ｍｓを満たす経路を発見できなかったとき、区間＃１および区間＃３において余った遅延制約値（その区間の遅延制約値から実際の遅延時間を差し引いた値）を、区間＃２へ分け与える。すなわち、区間＃１および区間＃２において、遅延制約値が５ｍｓ余った場合、この値を区間＃２に分け与えて、この区間の遅延制約値を１０ｍｓ＋５ｍｓ＋５ｍｓ＝２０ｍｓに変更する。そして、経路計算装置１は、その結果、この区間＃２についてend-to-endの遅延制約値２０ｍｓを満たす経路を計算する。
【００３３】
＜経路計算装置の構成＞
次に、図２を用いて、経路計算装置１の構成を詳細に説明する。図２は、図１の経路計算装置の構成を示したブロック図である。
【００３４】
図２に示すように、経路計算装置１は、入出力部１１と、処理部１２と、記憶部１３と、通信部１４とを備える。
【００３５】
入出力部１１は、この経路計算装置１に接続されるキーボードやマウス等の入力装置（図示せず）、液晶モニタ等の出力装置（図示せず）等のインタフェースである。この入出力部１１は、入力装置から入力された情報を処理部１２に出力したり、処理部１２により処理された情報を出力装置へ出力したりする。この入出力部１１は、中継ノード入力部１１１と、遅延制約値入力部１１２とを備える。中継ノード入力部１１１は、中継ノード（inclusive node）の識別情報の入力を受け付ける。また、遅延制約値入力部１１２は、end-to-endの遅延制約値の入力を受け付ける。なお、この中継ノードの識別情報および遅延制約値の入力は、通信部１４経由で行うようにしてもよい。
【００３６】
処理部１２は、この経路計算装置１全体の制御を司り、入出力部１１および記憶部１３の制御と、入力された情報の処理とを行う。この処理部１２は、経路計算を行う経路計算部１２１と、各ノード２における遅延時間を取得する遅延時間取得部１２２と、end-to-endでの遅延制約値を分割して各区間に割り当てる遅延制約値割り当て部１２３と、各ノード２のリンクコストや、トポロジ情報等のルーティング情報を取得するルーティング情報取得部１２４と、計算された経路に基づくパスの設定命令をノード２へ出力するパス制御部１２５とを備える。
【００３７】
経路計算部１２１は、入出力部１１あるいは通信部１４経由で、経路計算命令を受信すると、各区間ごとに、当該区間に割り当てられた遅延制約値を満たし、かつ、リンクコストが最小となる経路（最短経路）を計算する。このときの最短経路の計算は、制約付きdijkstra法等、公知のアルゴリズムを用いてよい。また、経路計算部１２１は、各区間のうち、当該区間に割り当てた遅延制約値を満たす経路が発見できなかった区間（第１の区間）と、経路が発見できた区間（第２の区間）とがあったとき、この第２の区間に割り当てた遅延制約値を、第１の区間に割り当てられた遅延制約値に分配して、この第１の区間における遅延制約値を変更する。そして、この変更した遅延制約値を満たす経路を再計算する。
【００３８】
遅延時間取得部１２２は、通信部１４経由で、各ノード２の遅延時間を取得し、この遅延時間をルーティング情報記憶部１３１に記憶する。なお、遅延時間の取得は、後記するルーティング情報取得部１２４が行うようにしてもよい。
【００３９】
遅延制約値割り当て部１２３は、end-to-endでの遅延制約値を各区間に分割して割り当てる。そして、各区間に割り当てた遅延制約値をパス情報記憶部１３２に記憶しておく。
【００４０】
ルーティング情報取得部１２４は、通信部１４経由で、各ノード２のリンクコスト（各リンクにおける残余帯域等）を取得し、ルーティング情報記憶部１３１に記憶する。
【００４１】
パス制御部１２５は、入出力部１１または通信部１４からパスの設定命令を受け付けると、経路計算部１２１へ経路計算命令を出力する。そして、経路計算部１２１からの経路計算結果を受け取ると、この経路計算結果に基づくパスの設定命令を、通信部１４経由で各ノード２へ出力する。
【００４２】
なお、この処理部１２の機能は、ＣＰＵ（Central Processing Unit）等が記憶部１３に記憶された所定のプログラムを実行することで実現される。
【００４３】
記憶部１３は、この経路計算装置１の機能を実現するプログラムのほかに、処理部１２が経路計算を行うときに参照する各種データを記憶する。この記憶部１３はルーティング情報（リンク情報およびトポロジ情報）を記憶するルーティング情報記憶部１３１と、経路計算部１２１が計算した経路（パス）を記憶するパス情報記憶部１３２と、入力されたend-to-endでの遅延制約値や、中継ノードの識別情報等、経路計算を行うときの制約条件を記憶する制約条件記憶部１３３とを備える。なお、この記憶部１３は、ＲＡＭ（Random Access Memory）、フラッシュメモリ、ＨＤＤ（Hard Disk Drive）等の記憶装置により実現される。
【００４４】
ルーティング情報記憶部１３１は、各ノード２を接続するリンク情報と、ネットワークのトポロジ情報とを記憶する。このリンク情報は、以下の表１に例示するように、リンクＩＤごとに、そのリンクのリンクコスト、遅延時間、Ａ端ノードＩＤ、Ａ端ノードＩＦ（interface）  ＩＤ、Ｚ端ノードＩＤ、Ｚ端ノードＩＦ  ＩＤ等を示した情報である。なお、このリンクコストの値は、そのリンクの残余帯域から求めた値でもよいし、遅延時間から求めた値でもよい。ノードＩＤおよびＩＦ  ＩＤは、例えば、ＩＰアドレス等により記述される。
【００４５】
【表１】
2008048114.tif 000003
【００４６】
また、トポロジ情報は、ネットワーク内に設置されるノード２の識別情報と、そのノード同士がどのように接続されているかを示した情報である。
【００４７】
なお、ここでは、トポロジ情報と、リンク情報とは別個のものとしているが、トポロジ情報に前記したリンク情報を含めるようにしてもよい。
【００４８】
パス情報記憶部１３２は、前記したとおり、経路計算部１２１が計算した経路（パス）情報を記憶する。以下の表２にパス情報を例示する。
【００４９】
【表２】
2008048114.tif 000004
【００５０】
例えば、パス情報は、表２に例示するように、経路計算部１２１が計算した経路（パス）のパスＩＤ、そのパスの始点ノードＩＤ、始点ノードＩＦ  ＩＤ、終点ノードＩＤ、終点ノードＩＦ  ＩＤ、経由リンクＩＤリスト、リンクコスト、遅延時間（実際の遅延時間）等を示した情報である。
【００５１】
なお、このパス情報は、end-to-endの経路に関するものと、その経路をinclusive route指定で区切った区間ごとのものと、両方用意するようにしてもよい。その場合、区間ごとのパス情報は、例えば、以下のように、経路（パス）のパスＩＤごとに、そのパスを区切った各区間における始点ノードＩＤ、始点ノードＩＦ  ＩＤ、終点ノードＩＤ、終点ノードＩＦ  ＩＤ、経由リンクＩＤリスト、リンクコスト、当該区間に割り当てられた遅延制約値（後記する遅延制約値sub-delay（k，i））等を示した情報である。なお、この遅延制約値は、前記した遅延制約値割り当て部１２３が当該区間に割り当てた遅延制約値が書き込まれる。また、この区間ごとのパス情報における、経由リンクＩＤリスト、リンクコスト、遅延時間は、経路計算部１２１が当該区間の経路を再計算したときに書き換えられる。
【００５２】
【表３】
2008048114.tif 000005
【００５３】
制約条件記憶部１３３は、前記したとおり、経路計算における制約条件を記憶する。制約条件は、以下の表４に例示するようにパスＩＤごとに、そのパスにおけるend-to-end遅延制約値と、そのパスにおいて経由する中継ノードの識別情報等を示した情報である。
【００５４】
【表４】
2008048114.tif 000006
【００５５】
ルーティング情報記憶部１３１、パス情報記憶部１３２および制約条件記憶部１３３の情報は、経路計算部１２１が経路計算を行うときに参照される。
【００５６】
通信部１４は、各ノード２との通信インタフェースを司る。処理部１２は、この通信部１４経由で、各ノード２の遅延時間やルーティング情報を取得したり、各ノード２へパスの設定命令を出力したりする。
【００５７】
＜経路計算装置の動作＞
次に、図３を用いて、経路計算装置１の動作を説明する。図３は、図２の経路計算装置の動作を示したフローチャートである。なお、この経路計算装置１は、経路計算開始前に、各ノード２のルーティング情報およびノード２間に発生している遅延時間（実際の遅延時間）を取得し、ルーティング情報記憶部１３１に記憶しておくものとする。
【００５８】
まず、経路計算装置１は中継ノード入力部１１１経由で、inclusive route指定の入力を受け付ける（Ｓ３０１）。つまり、始点ノードおよび終点ノードのＩＤと、そのノード間で経由する中継ノードのＩＤ（識別情報）の入力を受け付ける。ここでの中継ノードの個数は、例えば、Ｎ個とする。
【００５９】
また、遅延制約値入力部１１２経由で、始点ノードから終点ノードまでの間での遅延制約値の入力を受け付ける（Ｓ３０２）。入力された中継ノードのＩＤおよび遅延制約値は、制約条件記憶部１３３に記憶される。
【００６０】
そして、パス制御部１２５が、入出力部１１等からパスの設定命令を受け付けると、経路計算部１２１へ経路計算命令を出力する。そして、経路計算部１２１は、これをトリガとして始点ノードから終点ノードまでの経路を、中継ノードでＮ＋１個の区間Ｒｉ（１≦ｉ≦Ｎ＋１）に区切る。次に、遅延制約値割り当て部１２３は、Ｓ３０２で入力された遅延制約値（end-to-endでの遅延制約値）を、Ｎ＋１個に分割し、中継ノードで区切られた各区間Ｒｉに、この分割した遅延制約値sub-delay（0，i）を割り当てる（Ｓ３０３）。なお、各区間Ｒｉに割り当てた遅延制約値sub-delay（0，i）は、パス情報記憶部１３２に記憶しておく。また、sub-delayの括弧内の値はそれぞれ、（遅延制約値の再計算回数，分割された区間のＩＤ）を示す。
【００６１】
次に、経路計算部１２１は、各区間Ｒｉごとに、この遅延制約値sub-delay（0，ｉ）を満たす経路を探索（計算）する（Ｓ３０４）。計算結果は、パス情報記憶部１３２に記録していく。ここで、計算対象であるすべての区間Ｒｉについて遅延制約値sub-delay（k，i）を満たす経路を発見できたとき（Ｓ３０５のＹｅｓ）、経路計算部１２１は、計算した経路を計算結果としてパス制御部１２５あるいは入出力部１１へ出力し（Ｓ３０８）、処理を終了する。
【００６２】
一方、経路計算部１２１は、計算対象であるすべての区間Ｒｉについては遅延制約値sub-delay（k，i）を満たす経路を発見できなかったが（Ｓ３０５のＮｏ）、いずれか１以上の区間Ｒｉについてsub-delay（k，i）を満たす経路を発見できたとき（Ｓ３０６のＹｅｓ）、つまり、遅延制約値sub-delay（k，i）を満たす経路が発見できなかった区間と、発見できた区間とがあったとき、Ｓ３０９へ進む。そして、遅延制約値割り当て部１２３は、この遅延制約値sub-delay（k，i）を満たす経路が発見できなかった区間に新たな遅延制約値sub-delay（k＋1，i）を設定する（Ｓ３０９）。
【００６３】
このときの新たな遅延制約値sub-delay（k＋1，i）は、以下の式（１）に基づき計算する。
sub-delay（k＋1，i）＝{Σ（sub-delay（k，j）−Ｒｊの遅延時間）／遅延制約値を満たさなかった区間数}＋sub-delay（k，i）…式（１）
ｊ：遅延制約値を満たす経路が発見できた区間のＩＤ
【００６４】
つまり、遅延制約値割り当て部１２３は、遅延制約値を満たす区間において、当該区間における実際の遅延時間を上回る遅延時間（つまり余った遅延時間）を、遅延制約値を満たさない区間に分け与える。そして、遅延制約値割り当て部１２３は、この新たな遅延制約値sub-delay（k＋1，i）を、パス情報記憶部１３２に記憶しておく。
【００６５】
そして、経路計算部１２１は、この新たな遅延制約値sub-delay（k＋1，i）を設定した区間Ｒｉ、つまり、遅延制約値を変更した区間Ｒｉについて、この変更後の遅延制約値sub-delay（k＋1，i）を満たす経路を探索する（Ｓ３１０）。この後、この遅延制約値を変更した区間Ｒｉについて、この遅延制約値sub-delay（k＋1，i）を満たす経路が発見でき、計算対象であるすべての区間Ｒｉについて遅延制約値を満たす経路を発見できたとき（Ｓ３０５のＹｅｓ）、この計算した経路を計算結果として出力する（Ｓ３０８）。
【００６６】
なお、計算対象であるいずれの区間Ｒｉについても遅延制約値を満たす経路を発見できなかったとき（Ｓ３０６のＮｏ）、経路計算部１２１は、遅延制約値を満たす経路が発見できなかったことを出力し（Ｓ３０７）、処理を終了する。
【００６７】
また、計算対象である区間Ｒｉについて、遅延制約値sub-delay（k，i）を満たす経路が発見できなかった区間と、発見できた区間とがあったとき（Ｓ３０５のＮｏ→Ｓ３０６のＹｅｓ）、Ｓ３０９へ進み、再度、遅延制約値割り当て部１２３は、遅延制約値sub-delay（k，i）を満たす経路が発見できなかった区間に、新たな遅延制約値sub-delay（k＋1，i）を設定する（Ｓ３０９）。そして、経路計算部１２１は、この変更後の遅延制約値sub-delay（k＋1，i）を満たす経路を探索（計算）する（Ｓ３１０）。変更後の遅延制約値sub-delay（k＋1，i）を満たす経路が発見できたときは、その経路をパス情報記憶部１３２に記憶する。経路計算装置１は、このような処理を繰り返し、最終的に計算対象であるすべての区間Ｒｉについて遅延制約値sub-delay（k，i）を満たす経路を発見できたとき（Ｓ３０５のＹｅｓ）、パス情報記憶部１３２に記憶された各区間のパス情報をend-to-endでつなげたものを計算結果として出力する（Ｓ３０８）。
【００６８】
一方、遅延制約値割り当て部１２３が遅延制約値の分配を繰り返しても、遅延制約値sub-delay（k，i）を満たす経路を発見できなかったとき（Ｓ３０６のＮｏ）、遅延制約値を満たす経路が発見できなかったことを入出力部１１あるいはパス制御部１２５部へ出力し（Ｓ３０７）、処理を終了する。
【００６９】
このようにすることで、経路計算装置１は、inclusive route指定をした場合において、end-to-endでの遅延制約を満たす最短経路を計算することができる。
【００７０】
なお、Ｓ３０４およびＳ３１０で経路計算部１２１が探索する経路は、区間毎の遅延制約値を満たし、かつ、リンクコストが最小となる経路であることが好ましい。つまり、経路計算部１２１は、遅延制約値を満たす経路が複数発見されたときは、その中で、リンクコストが最小となる経路を選択する。このようにすることで、遅延制約値を満たしつつ、リンクコストが最小となる経路を発見することができる。
【００７１】
また、遅延制約値割り当て部１２３における、end-to-endの遅延制約値の分割は、各区間に均等に分割したものでもよいし、各区間のリンクコストに比例して分割したものでもよい。つまり、遅延制約値割り当て部１２３は、リンクコストが大きい区間には、より長い遅延制約値sub-delay（k，i）を割り当て、リンクコストが小さい区間には、より短い遅延制約値sub-delay（k，i）を割り当てるようにしてもよい。このようにすることで、各区間の経路計算（経路探索）に要する計算量を低減することができる。さらに、このときのend-to-endの遅延制約値の分割は、各区間の遅延時間(実際の遅延時間)に比例して分割するようにしてもよい。このようにすることで、遅延制約値の分割をするとき、ルーティング情報を用いずに分割することができる。
【００７２】
なお、経路計算部１２１は、各区間ごとに、当該区間に割り当てられた遅延制約値を満たし、かつ、リンクコストが最大になる経路を計算するようにしてもよい。
【００７３】
≪第２の実施の形態≫
次に、第２の実施の形態の経路計算装置を説明する。第２の実施の形態の経路計算装置は、inclusive route指定により区切られた各区間における最短経路の遅延時間の合計値が、end-to-endでの遅延制約値を超えるとき、リンクコストの大きい区間から順に、遅延時間が最短となる経路の再計算を行い、end-to-endでの遅延制約値以下となる経路を探索（計算）することを特徴とする。
【００７４】
＜動作概要＞
図４は、第２の実施の形態の経路計算装置を説明する図である。ネットワークの構成は第１の実施の形態と同様なので、説明を省略する。なお、ノード２Ａからノード２Ｄまでの経路におけるend-to-endでの遅延制約値は、第１の実施の形態と同様に、３０ｍｓ以下として説明する。
【００７５】
まず、経路計算装置１ａは、中継ノードで区切られた各区間＃１〜区間＃３それぞれの最短経路を計算する。そして、各区間ごとに、その最短経路における実際の遅延時間を計算し、合計する。つまり、end-to-endでの最短経路の実際の遅延時間を求める。ここで、end-to-endでの最短経路の実際の遅延時間が、遅延制約値（３０ｍｓ）を超えていなければ、その最短経路を計算結果として出力する。一方、end-to-endでの最短経路の実際の遅延時間が、前記した遅延制約値を超えていれば以下の処理を行う。
【００７６】
すなわち、経路計算装置１ａは、中継ノードで区切られた各区間のうち、まず、リンクコストが最も大きい区間について、経路再計算を行う。例えば、リンクコストが最も大きい区間＃３について、この区間において取りうる経路のうち、遅延時間が最も短くなる経路を計算する。そして、経路計算装置１ａは、計算後におけるend-to-endの遅延時間が、遅延制約値以下となっているか否かを確認し、計算後におけるend-to-endの遅延時間が、遅延制約値以下となっていれば、区間＃３の経路を、再計算した経路に置き換えたものを出力する。
【００７７】
図４に示す例でいうと、区間＃３について、ノード２Ｅを経由する経路（遅延時間：１０ｍｓ×２＝２０ｍｓ）と、ノード２Ｆ，２Ｇを経由する経路（遅延時間：５ｍｓ×３＝１５ｍｓ）とがあった場合、ノード２Ｅを経由する経路の方がホップ数は少ないが、ノード２Ｆ，２Ｇを経由する経路の方が遅延時間は短い。従って、このノード２Ｆ，２Ｇを経由する経路を選択する。ここで、このノード２Ｆ，２Ｇを経由する経路の遅延時間（１５ｍｓ）と、他の区間の遅延時間（１０ｍｓ＋５ｍｓ）との合計値（３０ｍｓ）は、前記したend-to-endの遅延制約値以下（３０ｍｓ以下）になっている。よって、パス情報記憶部１３２に記憶された区間＃３のパス情報について、ノード２Ｅを経由する経路から、ノード２Ｆ，２Ｇを経由する経路に置き換えたものを出力する。
【００７８】
一方、このノード２Ｆ，２Ｇを経由する経路の遅延時間と、残りの区間の遅延時間との合計値が、end-to-endでの遅延制約値（３０ｍｓ以下）を満たさない場合、経路計算装置１ａは、残りの区間についてリンクコストが大きい区間（例えば、区間＃１）から順に、同様の経路計算を繰り返し、計算した経路をパス情報記憶部１３２に記憶していく。そして、end-to-endでの遅延制約値（３０ｍｓ以下）を満たす経路を発見した段階で、計算を終了する。
【００７９】
このようにすることで、経路計算装置１ａは、end-to-endの遅延制約と、inclusive route指定の制約とを満たす最短経路を求めることができる。
【００８０】
＜経路計算装置の構成＞
次に、図５を用いて、経路計算装置１ａの構成を詳細に説明する。図５は、図４の経路計算装置の構成を示したブロック図である。前記した第１の実施の形態と同様の構成要素は同じ符号を付して、説明を省略する。
【００８１】
経路計算装置１ａは、図２の経路計算部１２１に代えて、リンクコストが最小となる経路（最短経路）の計算および遅延時間が最も短くなる経路の計算を行う経路計算部１２１ａを備える。また、図２の遅延制約値割り当て部１２３に代えて、全区間の遅延時間の合計が、制約条件記憶部１３３に記憶されたend-to-endの遅延制約値を超えるか否かを判断する遅延時間判断部１２６を備える。
【００８２】
経路計算部１２１ａは、まず、中継ノードで区切られた各区間の最短経路を計算する。このときの最短経路の計算は、制約付きdijkstra法等、公知のアルゴリズムを用いてよい。そして、遅延時間判断部１２６において、各区間に最短経路における実際の遅延時間を計算し、合計する。そして、合計した実際の遅延時間が、制約条件記憶部１３３に記憶された遅延制約値を超えると判断されたとき、リンクコストが最も大きい区間から順に、遅延時間が最も短くなる経路を再計算する。
【００８３】
＜経路計算装置の動作＞
次に、図６を用いて、経路計算装置１ａの動作を説明する。図６は、図５の経路計算装置の動作を示したフローチャートである。なお、この経路計算装置１ａも、経路計算開始前に、各ノード２のルーティング情報および各ノード間に発生している遅延時間（実際の遅延時間）を取得し、ルーティング情報記憶部１３１に記憶しておく。
【００８４】
Ｓ６０１およびＳ６０２は、前記した図３のＳ３０１およびＳ３０２と同様の処理であるので、説明を省略し、Ｓ６０３から説明する。
【００８５】
経路計算部１２１ａは、中継ノードで区切られた各区間Ｒｉ（１≦ｉ≦Ｎ＋１）の最短経路（リンクコストが最小となる経路）を計算（探索）する（Ｓ６０３）。この各区間Ｒｉごとの最短経路は、パス情報記憶部１３２における経由リンクＩＤリストとして記憶しておく。
【００８６】
そして、経路計算部１２１ａは、ルーティング情報記憶部１３１に記録されたリンクごとの遅延時間から、各区間Ｒｉの遅延時間（各区間Ｒｉにおいて最短経路をとったときの実際の遅延時間）を計算する。そして、この計算した各区間Ｒｉの遅延時間を合計し、end-to-endでの遅延時間を計算する（Ｓ６０４）。
【００８７】
次に、遅延時間判断部１２６は、この計算したend-to-endでの遅延時間が、制約条件記憶部１３３に記憶された遅延制約値を超えるか否かを判断する（Ｓ６０５）。ここで、計算したend-to-endでの遅延時間が、制約条件記憶部１３３に記憶された遅延制約値を超えなければ（Ｓ６０５のＮｏ）、経路計算部１２１ａは、パス情報記憶部１３２に記憶される経路を計算結果として出力し（Ｓ６１０）、処理を終了する。
【００８８】
一方、計算したend-to-endでの遅延時間が、制約条件記憶部１３３に記憶される遅延制約値を超えるときは（Ｓ６０５のＹｅｓ）、経路計算部１２１ａは、ルーティング情報記憶部１３１を参照して、各区間Ｒｉのリンクコストを計算し、このリンクコストが最も大きい区間Ｒｉにおいて、遅延時間が最も短くなる経路を計算する（Ｓ６０６）。なお、各区間Ｒｉのリンクコストは、例えば、遅延時間や残余帯域のほかに、ホップ数等を考慮して計算する。
【００８９】
そして、経路計算部１２１ａは、パス情報記憶部１３２に記憶しておいた最短経路を、遅延時間が最も短くなる経路に置き換え（Ｓ６０７）、経路置き換え後における各区間Ｒｉの遅延時間を合計し、end-to-endの遅延時間を再計算する（Ｓ６０８）、そして、遅延時間判断部１２６において、この遅延時間の合計値が、前記した遅延制約値を超えるか否かを判断する（Ｓ６０９）。
【００９０】
ここで、遅延時間判断部１２６において、この遅延時間の合計値が、前記した遅延制約値を超えないと判断されたとき（Ｓ６０９のＮｏ）、経路計算部１２１ａは、パス情報記憶部１３２に記憶しておいた経路を計算結果として出力し（Ｓ６１０）、処理を終了する。つまり、経路置き換え後の経路を計算結果として出力する。
【００９１】
一方、遅延時間判断部１２６において、この遅延時間の合計値が、前記した遅延制約値を超えると判断されたとき（Ｓ６０９のＹｅｓ）、経路計算部１２１ａは、計算対象である区間Ｒｉにおけるｉの値をインクリメント（＋１）して（Ｓ６１１）、インクリメントしたｉの値がＮ＋１以下であれば（Ｓ６１２のＮｏ）、Ｓ６０６へ戻る。そして、経路計算部１２１ａは、今回の計算対象とした区間Ｒｉを除き、リンクコストが最も大きい区間Ｒｉについて遅延時間が最も短くなる経路を計算し、当該区間Ｒｉの経路を計算後の経路に置き換える。
【００９２】
経路計算部１２１ａは、以上の処理を、各区間Ｒｉについて、end-to-endの遅延時間の合計値が遅延制約値以下となるまで繰り返す。そして、end-to-endの遅延時間の合計値が遅延制約値以下となったとき（Ｓ６０５のＮｏ）、Ｓ６１０へ進み、経路置き換え後の各区間Ｒｉの経路を出力する。
【００９３】
なお、ｉの値がＮ＋１を超えたとき（Ｓ６１２のＹｅｓ）、つまり、すべての区間Ｒｉについて遅延時間が最も短くなる経路の計算を終了したとき、経路計算部１２１ａは、inclusive route指定した経路において、遅延制約値を満たす発見できなかったことを計算結果として出力し（Ｓ６１３）、処理を終了する。
【００９４】
以上の処理を行うことで、経路計算装置１ａは、inclusive route指定をした場合においても、end-to-endでの遅延制約を満たす最短経路を計算することができる。
【００９５】
なお、前記した実施の形態において、経路計算部１２１ａは、リンクコストが最も大きい区間Ｒｉから順に経路再計算を行うこととしたが、遅延時間が最も長い区間Ｒｉから順に経路再計算を行うようにしてもよいし、リンクコストが大きく、かつ、遅延時間が長い区間から順に経路再計算を行うようにしてもよい。また、各区間Ｒｉのうち、最短経路以外にとりうる経路が多い区間Ｒｉから順に計算するようにしてもよい。このようにすることでも、inclusive route指定した場合において、end-to-endでの遅延制約値を満たす経路を発見しやすくなる。
【００９６】
さらに、経路計算部１２１ａにおいて、遅延制約値を満たす経路が見つからなかったとき、この経路計算装置１ａに接続される出力装置にinclusive route指定の再指定や、遅延制約値の再設定を促す画面を表示するようにしてもよい。
【００９７】
また、経路計算部１２１ａは、図６のＳ６０３において、中継ノードで区切られた各区間Ｒｉにおいてリンクコストが最大になる経路を計算（探索）するようにしてもよい。このようにすることで、経路計算装置１ａは、遅延制約値を満たし、かつ、リンクコストが最大となる経路を計算することができる。
【００９８】
さらに、前記した実施の形態において、経路計算装置１，１ａは、ノード２とは別個の装置であるものとして説明したが、ノード２を経路計算装置１，１ａとして機能させるようにしてもよい。
【００９９】
本実施の形態に係る経路計算装置１，１ａは、前記したような処理を実行させるコンピュータプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記憶媒体（ＣＤ−ＲＯＭ等）に記憶して提供することが可能である。また、そのプログラムを、ネットワークを通して提供することも可能である。
【図面の簡単な説明】
【０１００】
【図１】第１の実施の形態の経路計算装置を説明する図である。
【図２】図１の経路計算装置の構成を示したブロック図である。
【図３】図２の経路計算装置の動作を示したフローチャートである。
【図４】第２の実施の形態の経路計算装置を説明する図である。
【図５】図４の経路計算装置の構成を示したブロック図である。
【図６】図５の経路計算装置の動作を示したフローチャートである。
【符号の説明】
【０１０１】
１，１ａ      経路計算装置
２（２Ａ〜２Ｇ）  ノード
１１    入出力部
１２    処理部
１３    記憶部
１４    通信部
１１１  中継ノード入力部
１１２  遅延制約値入力部
１２１，１２１ａ  経路計算部
１２２  遅延時間取得部
１２３  遅延制約値割り当て部
１２４  ルーティング情報取得部
１２５  パス制御部
１２６  遅延時間判断部
１３１  ルーティング情報記憶部
１３２  パス情報記憶部
１３３  制約条件記憶部
【図１】
2008048114.tif 000007
【図２】
2008048114.tif 000008
【図３】
2008048114.tif 000009
【図４】
2008048114.tif 000010
【図５】
2008048114.tif 000011
【図６】
2008048114.tif 000012