(57)【要約】【課題】ユーザの要求に応えて複数パスの同時予約の可否を事前にチェックしてユーザに提示する。【解決手段】本発明は、経路予約装置が予約端末から、複数のメンバパス毎にメンバパスＩＤ及びメンバパスに対する制約条件を付与し、該複数のメンバパスをグループ化し、グループ毎に１つ以上のグループ識別子を割り当てた一括問い合わせメッセージ受信し、一括問い合わせメッセージのグループＩＤからメンバパスを検索し、全てのメンバパスの制約条件を読み出して経路計算を行い、パス群の制約条件とを比較して、該制約条件を満たすか否かを判定し、判定結果をクライアント装置に通知する。【選択図】図１
2008278007.tif 000002
【特許請求の範囲】
【請求項１】
経路予約装置において複数のパスを管理し、パス予約クライアント装置（以下、クライアント装置と記す）空の要求に基づいてパスの予約を行うためのグループパス予約制御方法であって、
経路予約装置は、予め、ネットワーク及び該ネットワーク上の機器の情報を収集し、ネットワーク・機器情報記憶手段に格納しておき、
前記クライアント装置は、予約要求対象のパスが１つの場合には、該パスに対する単一問い合わせメッセージを前記経路予約装置に送信し、予約要求対象のパスが複数ある場合には、複数のメンバパス毎にメンバパスＩＤ及びメンバパスに対する制約条件を付与し、該複数のメンバパスをグループ化し、グループ毎に１つ以上のグループ識別子を割り当て、グループ化されたそれぞれのパス群に対する制約条件を含む一括問い合わせメッセージを、該経路予約装置に送信する問い合わせメッセージ送信ステップと、
前記経路予約装置は、前記一括問い合わせメッセージを受信して、インスタンス記憶手段に格納するメッセージ受信ステップと、
前記インスタンス記憶手段に格納されている前記グループＩＤからメンバパスを検索し、全てのメンバパス及びパス群に対する制約条件を読み出して、前記ネットワーク・機器情報記憶手段を参照して、全てのメンバパスの経路計算を行う経路計算ステップと、
前記メンバパスに基づいてメンバパスパラメータを読み出して、パス群パラメータを生成し、前記インスタンス記憶手段の該グループＩＤに関連付けて、該パス群に対する該パス群パラメータを該インスタンス記憶手段に格納するグループパラメータ生成ステップと、
経路計算された全ての結果と、前記インスタンス記憶手段に格納されているパス群の制約条件とを比較して、該制約条件を満たすか否かを判定する制約条件判定ステップと、
前記制約条件判定ステップの判定結果を前記クライアント装置に通知する判定結果通知ステップと、
を行うことを特徴とするグループパス予約制御方法。
【請求項２】
前記経路予約装置において、
前記制約条件判定ステップにおいて、複数のパスのうち、１本でもパスの経路計算結果が前記制約条件を満たさない場合には、『予約不可』を前記クライアント装置に通知する
請求項１記載のグループパス予約制御方法。
【請求項３】
前記経路予約装置において、
前記制約条件判定ステップにおいて、前記制約条件を満たさない場合には、
前記経路計算ステップにおいて、前記ネットワーク・機器情報記憶手段の前回の検索とは異なる他の情報を参照して再度経路計算を行う
請求項１記載のグループパス予約制御方法。
【請求項４】
前記経路予約装置において、
前記予約完了後に、前記メンバパスのパラメータの変化が検出された場合に、新たなパス群パラメータを計算し、前記インスタンス記憶手段に格納するステップと、
前記制約条件判定ステップにおいて、前記制約条件を満たさないと判断された場合に、該制約条件が満たされるように前記インスタンス記憶手段内のパス群パラメータ及びメンバパスのパラメータを調整する調整ステップを更に行う
請求項１記載のグループパス予約制御方法。
【請求項５】
前記パス群に対する制約条件として、
経路が決定した時点で判定が可能な経路依存パスグループタイプ制約条件、経路と帯域が決定して初めて判定可能な帯域・経路依存パスグループタイプ制約条件、パスの設定本数に関するパス設定本数制約条件の少なくとも１つを用いる
請求項１乃至４記載のグループパス予約制御方法。
【請求項６】
複数のパスを管理し、パス予約クライアント装置（以下、クライアント装置と記す）からのパス予約要求に基づいてパスの予約を行うための経路予約装置であって、
予め、ネットワーク及び該ネットワーク上の機器の情報を収集し、ネットワーク・機器情報記憶手段に格納しておく情報収集手段と、
前記クライアント装置から、複数のメンバパス毎にメンバパスＩＤ及びメンバパスに対する制約条件が付与され、該複数のメンバパスがグループ化され、グループ毎に１つ以上のグループ識別子が割り当てられ、グループ化されたそれぞれのパス群に対する制約条件を含む一括問い合わせメッセージを受信して、インスタンス記憶手段に格納するメッセージ受信手段と、
前記インスタンス記憶手段に格納されているグループＩＤからメンバパスを検索し、全てのメンバパスの制約条件を読み出して、前記ネットワーク・機器情報記憶手段を参照して、全てのメンバパスの経路計算を行う経路計算手段と、
前記メンバパスに基づいてメンバパスパラメータを読み出して、パス群パラメータを生成し、前記インスタンス記憶手段の該グループＩＤに関連付けて、該パス群に対する該パス群パラメータを該インスタンス記憶手段に格納するグループパラメータ生成手段と、
経路計算された全ての結果と、前記インスタンス記憶手段に格納されているパス群の制約条件とを比較して、該制約条件を満たすか否かを判定する制約条件判定手段と、
前記制約条件判定手段の判定結果を前記クライアント装置に通知する判定結果通知手段と、を有する
ことを特徴とする経路予約装置。
【請求項７】
前記判定結果通知手段は、
前記制約条件判定手段において、複数のパスのうち、１本でもパスの経路計算結果が前記制約条件を満たさないと判定された場合には、『予約不可』を前記クライアント装置に通知する手段を含む
請求項６記載の経路予約装置。
【請求項８】
前記経路計算手段は、
前記制約条件判定手段において、前記制約条件を満たさない場合には、前記ネットワーク・機器情報記憶手段の前回の検索とは異なる他の情報を参照して再度経路計算を行う手段を含む
請求項６記載の経路予約装置。
【請求項９】
前記グループパラメータ生成手段は、
前記予約完了後に、前記メンバパスのパラメータの変化が検出された場合に、新たなパス群パラメータを計算し、前記インスタンス記憶手段に格納する手段を含み、
前記制約条件判定手段において前記制約条件を満たさないと判断された場合に、該制約条件が満たされるように前記インスタンス記憶手段内のパス群パラメータ及びメンバパスのパラメータを調整する調整手段を更に有する
請求項６記載の経路予約装置。
【請求項１０】
前記パス群に対する制約条件として、
経路が決定した時点で判定が可能な経路依存パスグループタイプ制約条件、経路と帯域が決定して初めて判定可能な帯域・経路依存パスグループタイプ制約条件、パスの設定本数に関するパス設定本数制約条件の少なくとも１つを用いる
請求項６乃至９記載の経路予約装置。
【請求項１１】
パス予約クライアント装置(以下、クライアント装置と記す)と、複数のパスを管理し、該クライアント装置からのパス予約要求に基づいてパスの予約を行うための経路予約装置からなる経路予約システムであって、
前記クライアント装置は、
複数のメンバパス毎にメンバパスＩＤ、メンバパスに対する制約条件を付与し、該複数のメンバパスをグループ化し、グループ毎に１つ以上のグループ識別子を割り当て、グループ化されたそれぞれのパス群に対する制約条件を含む一括問い合わせメッセージを、前記経路予約装置に送信する一括問い合わせ手段を有し、
前記経路予約装置は、
予め、ネットワーク及び該ネットワーク上の機器の情報を収集し、ネットワーク・機器情報記憶手段に格納しておく情報収集手段と、
前記クライアント装置から、前記一括問い合わせメッセージを受信して、インスタンス記憶手段に格納するメッセージ受信手段と、
前記インスタンス記憶手段に格納されているグループＩＤからメンバパスを検索し、全てのメンバパス及びパス群に対する制約条件を読み出して、前記ネットワーク・機器情報記憶手段を参照して、全てのメンバパスの経路計算を行う経路計算手段と、
前記メンバパスに基づいてメンバパスパラメータを読み出して、パス群パラメータを生成し、前記インスタンス記憶手段の該グループＩＤに関連付けて、該パス群に対するパス群パラメータを該インスタンス記憶手段に格納するグループパラメータ生成手段と、
経路計算された全ての結果と、前記インスタンス記憶手段に格納されているパス群の制約条件とを比較して、該制約条件を満たすか否かを判定する制約条件判定手段と、
前記制約条件判定手段の判定結果を前記クライアント装置に通知する判定結果通知手段と、を有する
ことを特徴とする経路予約システム。
【請求項１２】
コンピュータを、
請求項６乃至１０記載の経路予約装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループパス予約制御方法及び経路予約装置及びシステム及びプログラムに係り、特に、資源管理システム（ＮＲＭ）を用いてネットワーク資源の事前予約を行う際のグループパス群を制御するためのグループパス予約制御方法及び経路予約装置及びシステム及びプログラムに関する。
【背景技術】
【０００２】
計画管理されたネットワークに分散しているパス予約クライアントからＮＲＭ（資源管理システム）やＰＣＥ(Path Computation Element)等のパス経路予約装置に対して問い合わせを行い、計算資源・ネットワーク資源の事前予約を行う技術がある。
【０００３】
図２９に示すように、パス予約クライアントは、パス経路予約装置に対して、予約したいＮ本のパスからなるパス群について、パス１本ずつ設定可能であるか否かの問い合わせを行い、パス経路予約装置では、指定された個別のパス毎に経路計算を行い、予約が可能であるか否かを判定し、パス予約クライアントに応答する処理を、パスの本数分（Ｎ回）繰り返していた（例えば、非特許文献１，２参照）。
【非特許文献１】竹房あつ子、他「グリッドにおける計算資源と光パスネットワーク資源のコアロケーション実験」SACSIS(Symposium on Advanced Computing systems and Infrastructures) 2006
【非特許文献２】竹房あつ子、他「ミドルウェア連携による計算・ネットワーク資源の日米間グリッドコアロケーション実験」第１６４回計算機アーキテクチャ・第１０９回ハイパフォーマンスコンピューティング合同研究発表会
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記従来の技術では、以下のような問題がある。
【０００５】
・競合関係を考慮したパス設定が不可能：
従来は、同時に複数のパス問い合わせを行うインタフェースとメッセージ交換機能が存在しないため、ＮＲＭでは、パス予約クライアント（ユーザ）から通信路群の１本ずつの設定可否を問われて、"ユーザがある時間帯に本当に予約したい通信路群は何か"という情報を得られずに個別に仮予約を行っていたため、複数の通信路の間のネットワーク資源の競合関係を考慮できないという問題がある。
【０００６】
・複数パスの特有の制約条件を考慮したパス設定が不可能：
複数パス間の遅延差やパス本数など、複数パス特有の制約条件を考慮したパス計算ができない。
【０００７】
・複数パス特有の制約条件を考慮した複数パス制御が不可能：
複数パスに対する制約条件を考慮した経路計算機能がないため、経路・帯域変更を伴う複数パス制御ができない。
【０００８】
本発明は、上記の点に鑑みなされたもので、アプリケーションの利用の観点で相関関係にあるパス群をグループ化して管理し、ユーザの要求に応えて複数パスの同時予約の可否を事前にチェックしてユーザに提示することを可能とすることで、確実に通信路の予約が可能なグループパス予約制御方法及び経路予約装置及びシステム及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
図１は、本発明の原理を説明するための図である。
【００１０】
本発明（請求項１）は、経路予約装置において複数のパスを管理し、パス予約クライアント装置（以下、クライアント装置と記す）空の要求に基づいてパスの予約を行うためのグループパス予約制御方法であって、
経路予約装置は、予め、ネットワーク及び該ネットワーク上の機器の情報を収集し、ネットワーク・機器情報記憶手段に格納しておき（ステップ１）、
クライアント装置は、予約要求対象のパスが１つの場合には、該パスに対する単一問い合わせメッセージを経路予約装置に送信し、予約要求対象のパスが複数ある場合には、複数のメンバパス毎にメンバパスＩＤ及びメンバパスに対する制約条件を付与し、該複数のメンバパスをグループ化し、グループ毎に１つ以上のグループ識別子を割り当て、グループ化されたそれぞれのパス群に対する制約条件を含む一括問い合わせメッセージを、該経路予約装置に送信する問い合わせメッセージ送信ステップ（ステップ２）と、
経路予約装置は、一括問い合わせメッセージを受信して、インスタンス記憶手段に格納するメッセージ受信ステップ（ステップ３）と、
インスタンス記憶手段に格納されているグループＩＤからメンバパスを検索し、全てのメンバパス及びパス群に対する制約条件を読み出して、ネットワーク・機器情報記憶手段を参照して、全てのメンバパスの経路計算を行う経路計算ステップ（ステップ４）と、
メンバパスに基づいてメンバパスパラメータを読み出して、パス群パラメータを生成し、インスタンス記憶手段の該グループＩＤに関連付けて、該パス群に対する該パス群パラメータをインスタンス記憶手段に格納するグループパラメータ生成ステップ（ステップ５）と、
経路計算された全ての結果と、インスタンス記憶手段に格納されているパス群の制約条件とを比較して、該制約条件を満たすか否かを判定する制約条件判定ステップ（ステップ６）と、
制約条件判定ステップの判定結果をクライアント装置に通知する判定結果通知ステップ（ステップ７）と、を行う。
【００１１】
また、本発明（請求項２）は、経路予約装置において、
制約条件判定ステップにおいて、複数のパスのうち、１本でもパスの経路計算結果が制約条件を満たさない場合には、『予約不可』をクライアント装置に通知する。
【００１２】
また、本発明（請求項３）は、経路予約装置において、
制約条件判定ステップにおいて、制約条件を満たさない場合には、
経路計算ステップにおいて、ネットワーク・機器情報記憶手段の前回の検索とは異なる他の情報を参照して再度経路計算を行う。
【００１３】
また、本発明（請求項４）は、経路予約装置において、
予約完了後に、メンバパスのパラメータの変化が検出された場合に、新たなパス群パラメータを計算し、インスタンス記憶手段に格納するステップと、
制約条件判定ステップにおいて、制約条件を満たさないと判断された場合に、該制約条件が満たされるようにインスタンス記憶手段内のパス群パラメータ及びメンバパスのパラメータを調整する調整ステップを更に行う。
【００１４】
また、本発明（請求項５）は、パス群に対する制約条件として、
経路が決定した時点で判定が可能な経路依存パスグループタイプ制約条件、経路と帯域が決定して初めて判定可能な帯域・経路依存パスグループタイプ制約条件、パスの設定本数に関するパス設定本数制約条件の少なくとも１つを用いる。
【００１５】
図２は、本発明の原理構成図である。
【００１６】
本発明（請求項６）は、複数のパスを管理し、パス予約クライアント装置（以下、クライアント装置と記す）２００からのパス予約要求に基づいてパスの予約を行うための経路予約装置１００であって、
予め、ネットワーク及び該ネットワーク上の機器の情報を収集し、ネットワーク・機器情報記憶手段１８０に格納しておく情報収集手段１６５と、
クライアント装置２００から、複数のメンバパス毎にメンバパスＩＤ及びメンバパスに対する制約条件が付与され、該複数のメンバパスがグループ化され、グループ毎に１つ以上のグループ識別子が割り当てられ、グループ化されたそれぞれのパス群に対する制約条件を含む一括問い合わせメッセージを受信して、インスタンス記憶手段１７０に格納するメッセージ受信手段１１０と、
インスタンス記憶手段１７０に格納されているグループＩＤからメンバパスを検索し、全てのメンバパスの制約条件を読み出してネットワーク・機器情報記憶手段１８０を参照して、全てのメンバパスの経路計算を行う経路計算手段１３０と、
該メンバパスに基づいてメンバパスパラメータを読み出して、パス群パラメータを生成し、インスタンス記憶手段１７０の該グループＩＤに関連付けて、該パス群に対するパス群パラメータをインスタンス記憶手段１７０に格納するグループパラメータ生成手段１４０と、
経路計算された全ての結果と、インスタンス記憶手段に格納されているパス群の制約条件とを比較して、該制約条件を満たすか否かを判定する制約条件判定手段１５２と、
制約条件判定手段１５２の判定結果をクライアント装置に通知する判定結果通知手段１１５と、を有する。
【００１７】
また、本発明（請求項７）は、判定結果通知手段１１５において、
制約条件判定手段１５２において、複数のパスのうち、１本でもパスの経路計算結果が制約条件を満たさないと判定された場合には、『予約不可』をクライアント装置に通知する手段を含む。
【００１８】
また、本発明（請求項８）は、経路計算手段１３０において、
制約条件判定手段１５２において、制約条件を満たさない場合には、ネットワーク・機器情報記憶手段の前回の検索とは異なる他の情報を参照して再度経路計算を行う手段を含む。
【００１９】
また、本発明（請求項９）は、グループパラメータ生成手段１４０において、
予約完了後に、メンバパスのパラメータの変化が検出された場合に、新たなパス群パラメータを計算し、インスタンス記憶手段１７０に格納する手段を含み、
制約条件判定手段１５２において制約条件を満たさないと判断された場合に、該制約条件が満たされるようにインスタンス記憶手段１７０内のパス群パラメータ及びメンバパスのパラメータを調整する調整手段を更に有する。
【００２０】
また、本発明（請求項１０）は、パス群に対する制約条件として、
経路が決定した時点で判定が可能な経路依存パスグループタイプ制約条件、経路と帯域が決定して初めて判定可能な帯域・経路依存パスグループタイプ制約条件、パスの設定本数に関するパス設定本数制約条件の少なくとも１つを用いる。
【００２１】
本発明（請求項１１）は、パス予約クライアント装置(以下、クライアント装置と記す)と、複数のパスを管理し、該クライアント装置からのパス予約要求に基づいてパスの予約を行うための経路予約装置からなる経路予約システムであって、
クライアント装置は、
複数のメンバパス毎にメンバパスＩＤ及びメンバパスに対する制約条件を付与し、該複数のメンバパスをグループ化し、グループ毎に１つ以上のグループ識別子を割り当て、グループ化されたそれぞれのパス群に対する制約条件を含む一括問い合わせメッセージを、経路予約装置に送信する一括問い合わせ手段を有し、
経路予約装置は、
予め、ネットワーク及び該ネットワーク上の機器の情報を収集し、ネットワーク・機器情報記憶手段に格納しておく情報収集手段と、
クライアント装置から、一括問い合わせメッセージを受信して、インスタンス記憶手段に格納するメッセージ受信手段と、
インスタンス記憶手段に格納されているグループＩＤからメンバパスを検索し、全てのメンバパス及びパス群に対する制約条件を読み出して、ネットワーク・機器情報記憶手段を参照して、全てのメンバパスの経路計算を行う経路計算手段と、
該メンバパスに基づいてメンバパスパラメータを読み出して、パス群パラメータを生成し、インスタンス記憶手段の該グループＩＤに関連付けて、該パス群に対するパス群パラメータを該インスタンス記憶手段に格納するグループパラメータ生成手段と、
経路計算された全ての結果と、インスタンス記憶手段に格納されているパス群の制約条件とを比較して、該制約条件を満たすか否かを判定する制約条件判定手段と、
制約条件判定手段の判定結果をクライアント装置に通知する判定結果通知手段と、を有する。
【００２２】
本発明（請求項１２）は、コンピュータを、請求項６乃至１０記載の経路予約装置として機能させるプログラムである。
【発明の効果】
【００２３】
本発明では、パス予約クライアント（予約端末）が、グループ化されたパス群のパス群制約条件、パス群判別指標（グループＩＤ）を予約問い合わせメッセージに付加してＮＲＭに送信することで、複数パス本数分の設定要求を行うことなく、１回のメッセージ送信で予約の問い合わせが可能となる。また、問い合わせメッセージにグループＩＤを付与することにより、単一パスの問い合わせと区別することが可能となり、ＮＲＭにおいてグループＩＤが付与されている場合は、複数パスの一括計算処理を行い、一方、グループＩＤが付与されていない場合は、既存の単一パス計算処理を行うことができる。
【００２４】
また、パス群特有の制約条件をメッセージに追加することにより、予約端末が複数パスと特有の制約条件をパス群の問い合わせと関連付けて、ＮＲＭに送信することができる。
【００２５】
また、予約端末で指定されたパス群に対し、パス群一括でパス群制約条件付経路計算を行うことにより、予約端末で複数パス特有の制約条件を考慮したパス計算が可能になり、パス運用の多様な要求条件に対応でき、柔軟で効率的なパス資源の運用が可能となる。また、パス群の構成パスの１つでも制約条件を満たさない場合に、パス群予約のキャンセルが可能になる。
【００２６】
また、問い合わせのみでシーケンスを完了させる場合についても考慮することにより、相関のあるパス群の設定の可否を纏めて判断し、表示することができる。
【００２７】
また、複数のパスに対する制約条件（遅延特性の差等）を考慮したパス群制御機能を実現することで、複数パスの特性を考慮してパス制御が可能になるため、パス群に対する柔軟なトラフィックエンジニアリングが実現できる。特に、ＯＶＣ(Optical Virtual Concatenation)の制御や、無瞬断切り替えに対応した1+1プロテクションパスの経路変更において有用である。
【００２８】
上記のように本発明によれば、アプリケーションの利用の観点で相関関係にあるパス群をネットワークがグループ管理できる。
【００２９】
これにより、パス群のひとつでも履行不可能な障該などが発生した場合などにパス群の予約のキャンセルが可能となる。
【００３０】
また、相関のあるパス群の設定の可否をまとめて判断し、表示できる。
【発明を実施するための最良の形態】
【００３１】
以下、図面と共に本発明の実施の形態を説明する。
【００３２】
以下における『予約端末』とは、パス予約クライアントとして、ＮＲＭのユーザ装置や、MPLS(Multi Protocol Label Switching)をパケットだけではなく、Ｌ２，ＴＤＭ(Time Division Multiplexing)、波長、ファイバの単位でスイッチング技術に適用できるように拡張したＧＭＰＬＳ（Generalized Multi Protocol Label Switching）のネットワークエレメント等を指す。
【００３３】
また、パス予約装置として、ＮＲＭやＰＣＥ(Path Computation Element)があるが、以下ではＮＲＭを用いるものとする。
【００３４】
以下の説明において、『制約条件』とは、ユーザが指定するパスの帯域、経路、始点、終点、予約時間等のパスのスペックを指す。当該制約条件は、特定の値で指定される場合と、特定の値に範囲を持たせて指定される場合がある。
【００３５】
『パラメータ』とは、ＮＲＭが計算したパスの帯域、経路等のパラメータを指す。パスを設定する際には、このパラメータと同一のスペックで設定される。パスが実際に設定された後に、設定されたパスのパラメータに変動があった場合は、実際のパスの値に従い更新する。遅延等のように、時間と共に自律的に変化するパラメータもある。
【００３６】
『パス』には、図３に示すように、以下の４つの状態がある。
【００３７】
（１）ユーザの要求のみで、計算も本予約もされていない状態：
（２）経路計算が完了した状態：
（３）制約条件の判定がＯＫとなり、予約情報のネットワーク情報が更新された状態（仮予約）：
（４）物理的な設定が完了した状態（本予約状態）：
図４は、本発明の一実施の形態における動作イメージを示す図である。
【００３８】
同図において、
（１）ユーザは、予約端末からＮＲＭに対して、例えば、パスａ、パスｂ、パスｃの全ての設定が可能かを問い合わせるための一括問い合わせメッセージを送信する。当該メッセージには、メンバパスのパスａ、パスｂ、パスｃをグループ化し、当該グループに対するグループＩＤ及び予約したいパスの制約条件（品質等：例えば、通信路の始点・終点・帯域、時間等）が設定されている。
【００３９】
（２）これに対して、ＮＲＭは、予約端末から指定されたパス群の予約が可能かを経路計算を行い、予約が可能か否かを判定する。
【００４０】
（３）ＮＲＭは、指定されたパス群の設定可否を予約端末に応答する。
【００４１】
本実施の形態では、正常動作時におけるパス群の予約及びそのキャンセルについて説明する。
【００４２】
図５は、本発明の一実施の形態におけるＮＲＭの構成を示す。
【００４３】
同図に示すＮＲＭ１００は、ユーザ要求受付インタフェース（Ｉ／Ｆ）１１０、コア部１２０、経路計算機能部１３０、ループパラメータ・制約条件生成部１４０、パス制御機能部１５０、ネットワーク連携インタフェース（Ｉ／Ｆ）１６０、情報収集部１６５、インスタンスデータベース（ＤＢ）１７０、ネットワーク・機器情報データベース（ＤＢ）１８０から構成される。
【００４４】
ユーザ要求受付Ｉ／Ｆ１１０は、パスを予約するクライアントの予約端末２００に接続され、予約端末２００との間で通信を行う。
【００４５】
コア部１２０は、パス予約処理のために各構成要素と連携して予約を行う。なお、ユーザ要求受付Ｉ／Ｆ１１０で受け付けた予約端末２００からのメッセージの内容をインスタンスＤＢ１７０に書き込む。
【００４６】
経路計算機能部１３０は、インスタンスＤＢ１７０に格納されている情報に基づいて、ネットワーク・機器情報ＤＢ１８０を参照し、ダイクストラ法やK disjoint paths計算アルゴリズム等の経路計算アルゴリズムを用いて、パス群の予約のための経路を計算し、経路計算結果（パス）をパス制御機能部１５０に転送する。経路計算処理の詳細については後述する。
【００４７】
グループパスパラメータ生成部１４０は、図６に示すインスタンスＤＢ１７０のグループパスの管理情報領域に格納されているグループＩＤからメンバパスを検索し、当該メンバパスに基づいてメンバパスパラメータを読み出して、パス群パラメータを生成し、インスタンスＤＢ１７０の該グループＩＤに関連付けて、該パス群に対するパス群パラメータをインスタンスＤＢ１７０に格納する。
【００４８】
パス制御機能部１５０は、パス群のパスの制約条件、パスのパラメータを測定し、パラメータが制約条件を満たしているかを判定し、条件が満たされた場合にパスを設定する。また、ネットワーク連携Ｉ／Ｆ１６０によるネットワーク上の情報収集により、ネットワーク・機器情報ＤＢ１８０に格納されている制御対象のパスのパラメータが変化した場合、状況に応じて経路計算機能部１３０に対して経路計算要求を行うパス予約クライアントとしても機能する（例えば、ＯＶＣシステムで管理するパス間の遅延差が許容値を超えた場合、経路計算機能部１３０に経路の再計算を要求し、パスの経路変更で対応する場合）。なお、パス制御機能部１５０をＮＲＭ１００内に設けずに、外部に設けてもよい。パス制御機能部１５０の詳細は後述する。
【００４９】
ネットワーク連携Ｉ／Ｆ１６０は、ネットワークとの通信を行うインタフェースである。
【００５０】
情報収集部１６５は、随時または、一定の周期で、ネットワーク連携Ｉ／Ｆ１６０を介してネットワーク及びネットワーク上のネットワーク機器（ルータ）との通信を行い、ルーティングプロトコル、シグナリングプロトコル、システム管理者からの入力等のいずれかの手段によって収集したネットワーク情報及びネットワーク機器の情報（品質等）をネットワーク・機器情報ＤＢ１８０に格納する。ルーティングプロトコルとしては、ＯＳＰＦ−ＴＥ(Open Shortest Path First Traffic Engineering)、シグナリングプロトコルとしてはＲＳＶＰ−ＴＥ(Resource ReSerVation Protocol Traffic Engineering)、その他のプロトコルとしてＳＮＭＰ(Simple Network Management Protocol)、ＬＭＰ(Link Management Protocol)が想定できる。
【００５１】
インスタンスＤＢ１７０は、パス群インスタンス、メンバパスインスタンスからなるグループパスの管理情報、予約情報、ソース／ディスティネーションノードリスト、リンクタイプ制約条件、パスタイプ制約条件、経路依存パスグループタイプ制約条件、帯域依存パスグループタイプ制約条件、パス設定本数の許容数等が格納される。このうち、グループパスの管理情報の例を図６に示す。インスタンスＤＢ１７０には、パス群インスタンスとメンバパスインスタンスがグループＩＤとメンバパスＩＤで関連付けられて格納されている。パス群／メンバパスインスタンスは、それぞれのパラメータと制約条件をもつ。
【００５２】
ネットワーク・機器情報ＤＢ１８０は、情報収集部１６５で収集された経路計算に必要なネットワーク情報及びネットワーク機器（ルータ等）の情報を格納する。この情報には、帯域情報、メトリック、インタフェース種別、インタフェースＩＤ，ルータＩＤ，ラベル情報、遅延等の伝達特性、その他各種トラフィックエンジニアリング情報が含まれる。
【００５３】
図７は、本発明の一実施の形態におけるパス群予約／キャンセル動作のシーケンスチャートである。以下の処理に先立ち、システム管理者から設定された制約条件及び、情報収集部１６５を介してネットワーク情報、ネットワーク上のノードの情報等が収集され、ネットワーク・機器情報ＤＢ１８０に格納されているものとする。
【００５４】
ステップ１０１）  予約端末２００は、ＮＲＭ１００に対して、予約を行いたいパスのパス識別子に加え、複数のパスに対するグループＩＤが付与され、グループ化されたパス群に対する制約条件を含むパス群一括問い合わせのメッセージを送信する。当該メッセージには、グループＩＤ（複数のパスの問い合わせ時のみ）、パスの設定時間、ユーザ識別子、通信路の始点・終点のノード情報またはポート情報、容量、通信開始時刻、通信終了時刻、応答時のパス表示に利用するためのパス識別子、遅延時間、稼動率等の品質情報等の制約条件が含まれる。
【００５５】
ステップ１０２）  ＮＲＭ１００は、ユーザ要求受け付けＩ／Ｆ１１０において予約端末２００から問い合わせメッセージを受信し、コア部１２０を介して、メッセージに含まれるグループＩＤ、メンバパスＩＤ、メンバパスに対する制約条件等をインスタンスＤＢ１７０に書き込む。パス制御機能部１５０において、メッセージにグループＩＤが付与されている場合には、パス群の一括予約問い合わせメッセージであると判定し、グループＩＤが付与されていない場合は、単一パスの予約問い合わせメッセージであると判定する。グループＩＤが付与されている場合には、グループパラメータ生成部１４０においてメンバパスパラメータに基づいてパス群パラメータを生成し、インスタンスＤＢ１７０に格納する。ＮＲＭ１００は、経路計算機能部１３０において、インスタンスＤＢ１７０に格納されている制約条件に基づいて、ネットワーク・機器情報ＤＢ１８０を参照して経路計算を行い、パス制御機能部１５０において、インスタンスＤＢ１７０のパス群に対する制約条件を参照して、経路計算された経路が予約可能であるかを判定し、可能である場合は仮予約を行い、その予約情報をインスタンスＤＢ１７０に格納する。但し、一括予約問い合わせメッセージで指定されている複数のパスのうち、１本でも仮予約ができなければ、キャンセルする。なお、当該ステップの動作の詳細については、図９、図１１，１６にて後述する。
【００５６】
ステップ１０３）  ＮＲＭ１００は、全てのパスについて仮予約ができた場合には、「予約可能」を、キャンセルした場合には「予約不可」のメッセージを、ユーザ要求受付Ｉ／Ｆ１１０を介して予約端末２００に送信する。ＮＲＭ１００から予約端末２００に送信されるメッセージには、パスの設定時間、ＮＲＭ識別子、各種制約条件、経路計算結果、通信路の始点・終点、容量、開始時刻、終了時刻、予約可／予約不可、仮予約実施／仮予約中止、パスの始点・終点、パスＩＤ、予約ＩＤ、遅延時間や稼働率などの品質情報等が含まれる。
【００５７】
ステップ１０４）  予約端末２００は、パス群一括問い合わせに対する応答を表示手段上に表示し、ユーザが本予約を行うか否かを判断する。
【００５８】
ステップ１０５）  判断結果に基づいて、予約要求または、中止（キャンセル）要求をＮＲＭ１００に対して送信する。
【００５９】
図８は、本発明の一実施の形態におけるパス制御機能部の構成を示す。
【００６０】
パス制御機能部１５０は、パラメータ測定機能部１５１、制約条件判定機能部１５２、パスパラメータ・パス群パラメータ調整機能部１５３、及びパス設定機能部１５４から構成される。
【００６１】
パラメータ測定機能部１５１は、インスタンスＤＢ１７０のパス群のパスのパラメータ（例えば、遅延特性の差等）を測定し、制約条件判定機能部１５２に通知する。測定手段の例として、ネットワークのノード装置のパス監視情報を制御メッセージにより取得する方法がある。
【００６２】
制約条件判定機能部１５２は、経路計算機能部１３０により計算されたパスのパラメータを測定し、インスタンスＤＢ１７０のパス設定の制約条件を満たさない場合は、経路計算機能部１３０に新たな経路計算要求を行い、制約条件を満たす場合は、経路計算機能部１３０から返答された経路計算結果を、パス設定機能部１５４に通知する。
【００６３】
パスパラメータ・パス群パラメータ調整機能部１５３は、ユーザからの本予約要求に基づいてパス設定完了後に、インスタンスＤＢ１７０に格納されているパス群／メンバパスのパラメータが制約条件を満たさない場合は、遅延や損失等のパス・パス群パラメータを調整する。具体的には、ネットワーク連携Ｉ／Ｆ１６０を通してネットワークのノードと制御メッセージを交換し、装置内のバッファ量を増やしたり、パス中の光パワーを増幅することで調整する。これは、パス設定完了後に、時間の経過に伴って情報収集部１６５で収集され、インスタンスＤＢ１７０に格納されているネットワーク情報やネットワーク機器情報が更新されるためである。
【００６４】
パス設定機能部１５４は、経路変更等の際にネットワークのノード装置にパスを設定する。
【００６５】
次に、経路計算機能部１３０、パス制御機能部１５０において、ユーザから所望パス群の問い合わせ時、及び、パス制御機能部１５０から再計算要求があった場合のパス計算の処理について説明する。
【００６６】
以下の図９に示す全体フローから図１０に示す各処理（サブルーチン）を呼び出して処理を行うものとする。
【００６７】
図９は、本発明の一実施の形態における経路計算の概要動作のフローチャートである。
【００６８】
ステップ４００）  経路計算機能部１３０は、予約端末２００からユーザ要求受付Ｉ／Ｆ１１０、コア部１２０を介して、または、パス制御機能部１５０から経路計算要求が入力されると、インスタンスＤＢ１７０から読み込まれたソース／ディスティネーションノードリスト、リンクタイプ制約条件、パスタイプ制約条件、経路依存パスグループタイプ制約条件、帯域依存パスグループタイプ制約条件、パス設定本数の許容数を読み込む。
【００６９】
ステップ４１０）  複数のパスについて一括処理の必要性があるかを判定する。具体的には、グループＩＤが付与されているか否かを判定する。
【００７０】
ステップ４２０）  グループＩＤが付与されている場合には、複数パスの一括処理が必要であるので、ステップ６００に移行し、付与されていない場合（単一パス）は、ステップ５００に移行する。
【００７１】
ステップ５００）  経路計算機能部１３０は、図１１に示す単一パス計算処理を実行する。
【００７２】
ステップ６００）  経路計算機能部１３０は、図１６に示す複数パス一括計算処理を実行する。
【００７３】
ステップ９００）  コア部１２０は、経路計算要求元に、ユーザ要求受付Ｉ／Ｆ１１０を介して経路計算の結果（『予約可能』または、『予約不可』）を返却する。また、『予約不可』の場合は、原因となった制約条件を返却する。
【００７４】
次に、経路計算機能部１３０における、上記のステップ５００の単一パス計算処理について説明する。
【００７５】
単一パスに対する制約条件は以下の通りである。
【００７６】
・Path Type制約条件：パス全体に対しての判定条件で、パス計算が終了した後に判定可能となる条件。
【００７７】
・Link Type制約条件：パスが通過する単一リンクの属性で判定できる条件で、パスの通過リンク決定のタイミングで判定可能となる条件。
【００７８】
・Inclusion：特定箇所を通過するよう指定する条件。
【００７９】
・Exclusion：特定箇所を通過しないよう指定する条件。
【００８０】
図１１は、本発明の一実施の形態における単一パス計算処理のフローチャートである。
【００８１】
ステップ５００）  トポロジ情報Ｇ（Ｖ，Ａ）、各種制約条件が与えられる。このうち、トポロジ情報は、ネットワーク・機器情報ＤＢ１８０から読み込まれ、各種制約条件は、インスタンスＤＢ１７０から読み込まれる。
【００８２】
ステップ６００）  経路計算機能部１３０は、図１２に示すExclusion制約処理のサブルーチンを呼び出す。
【００８３】
ステップ７００）  経路計算機能部１３０は、図１３に示すLink Type制約処理のサブルーチンを実行する。
【００８４】
ステップ８００）  経路計算機能部１３０において、図１４に示す制約条件付き最短経路計算のサブルーチンを実行する。
【００８５】
ステップ５１０）  ユーザ要求受付Ｉ／Ｆ１１０において、上記の３つのサブルーチンの実行結果を取得して、単一パス計算処理の結果を作成し、経路が取得できた場合はその経路を応答として返却し、経路計算が失敗した場合は、「結果無し」をステップ９００の処理に返却する。
【００８６】
次に、上記の単一パス計算処理のステップ６００のExclusion制約処理を説明する。
【００８７】
図１２は、本発明の一実施の形態におけるExclusion制約処理のフローチャートである。
【００８８】
ステップ６１０）  制約条件判定機能部１５２において、インスタンスＤＢ１７０から読み出したパスに対する制約条件に"Exclusion"指定されているかを判定し、指定されている場合は、そのリソースを計算対象トポロジから除外する。
【００８９】
次に、上記の単一パス計算処理のステップ７００のLink Type制約処理を説明する。
【００９０】
図１３は、本発明の一実施の形態におけるLink Type制約処理のフローチャートである。なお、当該サブルーチンは、制限項目が複数ある場合は、項目毎に複数回呼び出される。
【００９１】
ステップ７００）  制約条件判定機能部１５２において、判定対象ａｒｃ、及びLink Type制約条件を入力する。
【００９２】
ステップ７１０）  ａｒｃが制約条件を満たすかを判定し、満たす場合には、「ＯＫ」を出力し、満たさない場合は「ＮＧ」を出力する。
【００９３】
次に、上記の単一パス計算処理のステップ８００の制約条件付最短経路計算処理を説明する。
【００９４】
図１４は、本発明の一実施の形態における制約条件付最短経路計算処理のフローチャートである。
【００９５】
ステップ８００）  ユーザから指定された制約条件として、経路計算機能部１３０にネットワーク・機器情報ＤＢ１８０からトポロジ情報Ｇ（Ｖ，Ａ）、インスタンスＤＢ１７０からIngress node（ｓ）、Egress node（ｄ）が入力される。また、メモリ（図示せず）に格納されている管理データとして、ｓからｖまでの距離ｄ［ｖ］、ｖの直前のノードπ［ｖ］、アークａのコストｗ［ａ］、確定ラベルの付けられたノードの集合Ｌ、確定ラベルが付けられていないノードの集合Ｍが入力される。
【００９６】
ステップ８１０）  上記の管理データの初期化処理（Initialization）を行う。
【００９７】
ステップ８２０）  Ｌ＝０、Ｍ＝Ｖとする。
【００９８】
ステップ８２１）  ｍ＝（Ｍのうちｄ［ｍ］が最小値をとるｍ）とする。
【００９９】
ステップ８２２）  ｄ［ｍ］＝∞であるかを判定し、そうであれば、「経路なし」を出力する。そうでなければステップ８２３に移行する。
【０１００】
ステップ８２３）  ｍ＝ｄであれば、ステップ８４４に移行する。
【０１０１】
ステップ８２４）  ｍ≠ｄであれば、Ｌ＝Ｌ＋｛ｍ｝とする。
【０１０２】
ステップ８２５）  ｍに隣接する全てのノードｖに対して以下の処理を行う。
【０１０３】
ステップ８２６）  ｖがＵに属し、かつ、ｄ［ｖ］＞ｄ［ｍ］＋ｗ（ａ）であるかを判定し、そうであれば、ステップ８３０に移行し、そうでなければ、ステップ８２１に移行する。
【０１０４】
ステップ８３０）  経路計算機能部１３０において、図１５に示すPath Type制限判定処理を呼び出して実行する。
【０１０５】
ステップ８４０）  パスが条件を満たすかを判定し、満たす場合はステップ８４１に移行し、満たさない場合はステップ８２１に移行する。
【０１０６】
ステップ８４１）  経路計算機能部１３０において、ｄ［ｖ］＝ｄ［ｍ］＋ｗ（ａ），π［ｖ］＝ｍとする。
【０１０７】
ステップ８４２）  Ｕの順位キューを更新する。
【０１０８】
ステップ８４３）  ステップ８２１に移行する。
【０１０９】
ステップ８４４）  ｓからｄまでの経路を作成し、コスト計算し、ｓからｄまでの経路を出力する。
【０１１０】
図１５は、本発明の一実施の形態におけるPath Type制限判定処理のフローチャートである。当該処理は、制限項目が複数ある場合は、項目毎に複数回呼び出される。
【０１１１】
ステップ８３０）  制約条件判定機能部１５２において、判定対象パスとPath Type制約条件が入力される。
【０１１２】
ステップ８３１）  判定対象パスが制約条件を満たすかを判定し、その結果を出力する。
【０１１３】
次に、複数パス一括計算処理について説明する。
【０１１４】
複数パスに対する制約条件として、Path Group Type制約とパス設定本数制約がある。
【０１１５】
Path Group Type制約には、経路依存Path group type制約と帯域・経路Path group type制約がある。
【０１１６】
・経路依存Path group type制約：経路が決定した時点で判定が可能な制約条件；
−合計ホップ数：複数パスの合計ホップ数についての制約条件；
−ホップ数差の許容最大値・最小値：複数パスのホップ数の差についての制約条件；
−遅延差の許容最大値・最小値：個々のパスが持つ遅延属性の差に対しての制約条件；
−遅延絶対値の和の許容最大値：個々のパスの持つ遅延時間の合計値に対しての制約条件；
−遅延絶対値の許容最大分散値：個々のパスの持つ遅延時間の最大分散値に対しての制約条件；
−ＦＯＭ：複数のパス候補を表示する際にユーザが指定する優先指標；
−全体に対する稼動率：全てのパスが正常に稼動する状態を正常とする場合の稼働率；
−始点ノードリスト／終点ノードリスト指定：複数パスの始点・終点を異にすることを許容する際、始点・終点ノードのリストを指定する；
−終点ノードグループ／終点ノードグループ指定：複数パスの始点・終点を異にすることを許容する際、始点・終点ノードのグループＩＤを指定する；
−ノードディスジョイント性指定：複数パス間でノードの重複がない経路を計算することを指定する制約条件；
−ＳＲＬＧディスジョイント性指定：複数パス間でＳＲＬＧ(Shared Risk Link Group)が重複しないことを指定する制約条件；
−通過ノード統一指定：複数パス間で通過ノードを統一させるよう指定する制約条件（統一されていればどのノードを通過してもよい）；
−通過エリア統一指定：複数パス間で通過エリアを統一させるよう指定する制約条件（統一されていればどのエリアを通過してもよい）；
−通過レイヤ統一指定：複数パス間で通過レイヤを統一させるよう指定する制約条件（統一されていればどのレイヤを通過してもよい）；
−通過リソースグループ統一指定：ネットワークリソースが運用ポリシによってグループ化されている場合、リソースグループを統一するように指定する制約条件；
・帯域・経路Path group type制約：経路と帯域が決定して初めて判定可能な制約条件；
−帯域の平均値：個々のパスの持つ帯域の平均値に対しての制約条件；
−帯域の合計値：個々のパスの帯域の合計値に対しての制約条件；
−帯域差の最大値・最小値：個々のパスの帯域の差についての制約条件；
また、パス設定本数制約には、パスの設定本数に関する制約条件がある。パス設定本数に関する制約条件を用いる際は、パス設定本数を特定の数値で指定せず、上限と下限により許容できる設定本数に幅を持たせて指定する。当該制約条件は、要求帯域が満たされれば、本数は何本でも良い場合などに適用可能である。例えば、『パス設定許容最大本数』、『パス設定許容最小本数』のように２つの条件が指定可能である。具体的には、「要求帯域８０Ｇ，パス設定許容最大本数＝８、パス設定許容最小本数１」の場合の解は、「４０Ｇ×２本」「１０Ｇ×８本」等となる。
【０１１７】
次に、図１０におけるステップ１０００の複数パス一括計算処理の概要を説明する。
【０１１８】
図１６は、本発明の一実施の形態における複数パス一括計算処理のフローチャートである。
【０１１９】
ステップ１０００）  制約条件としてインスタンスＤＢ１７０に格納されている、パス設定最小本数（Ｋｍｉｎ）、パス設定最大本数（Ｋｍａｘ）、ソースノード候補の集合（Ｓ）、ディスティネーション候補の集合（Ｄ）、各種制約条件が入力される。
【０１２０】
ステップ１１００）  経路計算機能部１３０において、図１７に示す複数パス計算用link Type制限生成のサブルーチンを呼び出して実行し、得られたパス群に対する制約条件をインスタンスＤＢ１７０に格納する。
【０１２１】
ステップ１２００）  経路計算機能部１３０において、複数パス計算用path type制限生成のサブルーチンを呼び出して実行し、得られたパス群に対する制約条件をインスタンスＤＢ１７０に格納する。
【０１２２】
ステップ１３００）  経路計算機能部１３０において、図１８に示す候補パスリスト作成のサブルーチンを呼び出す。
【０１２３】
ステップ１０１０）  経路計算機能部１３０において、候補パスリスト作成のサブルーチンを実行することにより得られたパス本数が入力されたパス設定最低本数Ｋｍｉｎ以内であるか判定する。
【０１２４】
ステップ１０２０）  パス設定最低本数Ｋｍｉｎをｋとし、メモリ（図示せず）に格納する。
【０１２５】
ステップ１４００）  経路計算機能部１３０において、図１９に示す候補パスグループリスト作成のサブルーチンを呼び出す。
【０１２６】
ステップ１５００）  経路計算機能部１３０において、図２０に示す解候補リスト作成のサブルーチンを呼び出す。
【０１２７】
ステップ１０３０）  解候補リストに候補が存在する場合は、ステップ１６００に移行し、存在しない場合は、ステップ１０４０に移行する。
【０１２８】
ステップ１０４０）  ｋ＜Ｋｍａｘであるかを判定し、そうである場合はステップ１０５０に移行し、そうでない場合は、「経路なし」を経路計算要求元に返却する。
【０１２９】
ステップ１０５０）  ｋ＋１＝ｋとし、ステップ１０２０に移行する。
【０１３０】
ステップ１６００）  経路計算機能部１３０において、図２２に示す、解候補の帯域・コスト計算処理のサブルーチンを呼び出す。
【０１３１】
ステップ１７００）  経路計算機能部１３０において、図２７に示すベスト候補選択のサブルーチンを呼び出す。当該処理は、解候補の中から最もコストの低い解を選択する。
【０１３２】
ステップ１０６０）  経路計算機能部１３０において、計算結果を作成し、経路計算要求元に返却する。
【０１３３】
上記のステップ１３００の候補パスリスト作成処理、ステップ１４００の候補パスグループリスト作成処理のサブルーチンにより、単一パスの経路候補を探索し、その経路候補の組み合わせで無数の複数パスグループの集合を作成する。
【０１３４】
また、ステップ１０１０〜ステップ１５００の処理において、経路計算要求元からのパス要求メッセージで指定されている設定本数の下限からの解を探索している。
【０１３５】
また、ステップ１５００の解候補の帯域・コスト計算処理とステップ１６００の解候補リスト作成処理により、可解な解を与える経路リストを作成し、その後、最適な帯域割当値を求める。
【０１３６】
次に、上記のステップ１１００のグループパラメータ生成部１４０における、複数パス計算用link type制約生成のサブルーチンについて説明する。
【０１３７】
図１７は、本発明の一実施の形態における複数パス計算用link type制約生成処理のフローチャートである。
【０１３８】
ステップ１１１０）  グループパラメータ生成部１４０において、インスタンスＤＢ１７０のメンバパスＩＤに対応するメンバパスに対する制約条件を読み出し、当該制約条件に含まれるlink type制約条件項目を参照し、最も厳しい条件を持つパスの制約条件をパス群に対する制約条件とする。
【０１３９】
次に、上記のステップ１２００のグループパラメータ生成部１４０における、複数パス計算用path type制約生成のサブルーチンについて説明する。当該処理においても、上記の複数パス計算用link type制約生成処理と同様に、インスタンスＤＢ１７０からメンバパスＩＤに対応するメンバパスに対する制約条件を読み出し、当該制約条件に含まれるpath type制約条件項目を参照し、最も厳しい条件を持つパスのpath type制約条件を複数パス計算用の制約条件とする。
【０１４０】
次に、複数パス一括計算処理（ステップ１０００）から呼び出される上記のステップ１３００の候補パスリスト作成処理のサブルーチンについて説明する。
【０１４１】
図１８は、本発明の一実施の形態における候補パスリスト作成処理のフローチャートである。
【０１４２】
ステップ６００）  経路計算機能部１３０において、図１２のExclusion判定処理のサブルーチンを実行する。
【０１４３】
ステップ７００）  経路計算機能部１３０において、図１３のlink type制約判定処理のサブルーチンを実行する。
【０１４４】
ステップ１３１０）  Ｐ←φとする。
【０１４５】
ステップ１３２０）  経路計算機能部１３０において、経路計算要求元からのパス要求メッセージで指定されたソースノード候補と宛先ノード候補の組み合わせを作成する。以下において、ｓはソースノード、ｄは宛先ノードを示す。
【０１４６】
（ｓ，ｄ）：ｓ∈Ｓ，ｄ∈Ｄのコンビネーションによりｓ，ｄの組み合わせ候補ｑを作成する。
【０１４７】
ステップ２１００）  全ての始点（ソースノード）、終点（宛先ノード）の組み合わせｑについて、以下の処理を行う。
【０１４８】
ステップ２１００）  解候補を作成する際の部品となる単一パスを無数に計算するためのサブルーチンである図２３に示す制約条件付きK shortest path計算処理を呼び出す。
【０１４９】
ステップ１３３０）  Ｐｑを作成する。
【０１５０】
ステップ１３４０）  Ｐ←Ｐ∪Ｐｑとし、当該候補パスリスト作成処理サブルーチンの呼び出し元に候補パスリストＰを返却する。
【０１５１】
次に、複数パス一括計算処理（ステップ１０００）から呼び出される、上記のステップ１４００の候補パスグループリスト作成処理のサブルーチンについて説明する。
【０１５２】
図１９は、本発明の一実施の形態における候補パスグループリスト作成処理のフローチャートである。
【０１５３】
ステップ１４００）  経路計算機能部１３０において、ステップ１３００からの出力Ｐ（候補パスリスト）、ステップ１０２０で求められ、メモリ（図示せず）に格納されているｋ（計算パス本数）を取得する。
【０１５４】
ステップ１４１０）
【０１５５】
【数１】
2008278007.tif 000003
とする。
【０１５６】
ステップ１４２０）  候補パスリストＰの全要素からｋ本のパス本数を選ぶ全ての組み合わせについて以下の処理を行う。
【０１５７】
ｋ本のパスを選んでその集合をπｋとする。
【０１５８】
ステップ２２００）  図２４に示す経路依存のPath group type制約条件の判定を行うための「経路依存Group type制約条件判定処理」のサブルーチンを呼び出して実行する。
【０１５９】
ステップ１４２０）  上記の経路依存Group type制約条件判定処理」のサブルーチンの処理の結果、パスグループが条件を満たす場合には、ステップ１４３０に移行し、満たさない場合は、次の組み合わせの判定を行う。
【０１６０】
ステップ１４３０）
【０１６１】
【数２】
2008278007.tif 000004
とし、
【０１６２】
【数３】
2008278007.tif 000005
を呼び出し元の処理に返却する。
【０１６３】
次に、複数パス一括計算処理（ステップ１０００）から呼び出される、経路計算機能部１３０における、上記のステップ１５００の解候補リスト作成処理のサブルーチンについて説明する。当該処理は、一括で帯域を割り当て可能なパスグループを解候補リストに追加するものである。
【０１６４】
図２０は、本発明の一実施の形態における解候補リスト作成処理のフローチャートである。
【０１６５】
ステップ１５１０）  以下の処理を、全てのパスグループ要素πｋに対して繰り返す。
【０１６６】
ステップ２３００）  図２１に示す複数パス一括空き帯域量判定処理のサブルーチンを呼び出して実行する。
【０１６７】
ステップ１５２０）  上記の複数パス一括空き帯域量判定処理の結果、「ＯＫ」が返却された場合は、ステップ１５３０に移行し、「ＮＧ」が返却された場合は、当該処理を終了する。
【０１６８】
ステップ１５３０）  解候補リストＵにπｋを追加し、解候補リストを呼び出し元の処理に返却する。
【０１６９】
次に、上記のステップ１５００から呼び出される複数パス一括空き帯域量判定処理（ステップ２３００）について説明する。
【０１７０】
図２１は、本発明の一実施の形態における複数パス一括空き帯域量判定処理のフローチャートである。
【０１７１】
ステップ２３１０）  経路計算機能部１３０において、以下の条件を満たすかを判定する。
【０１７２】
まず、以下の条件において、
ｐ：経路；
Ｑ：始点と終点のペアの集合；
ｑ：始点と終点のペア；
ｆｑ，ｐ：ペアｑ間の経路ｐに割り当てられた帯域；
Ｔｋ，ｉ：要素ｋ本の候補パスを含む候補パスグループ；
Ｂ：複数パスに対する要求合計帯域；
Ｓｅ：リンクｅの空き容量；
Ｅ：トポロジの全てのリンクの集合；
【０１７３】
【数４】
2008278007.tif 000006
条件１：個々のパスに帯域指定がある場合はそれを満たす。
【０１７４】
【数５】
2008278007.tif 000007
条件２：複数パス全体に与えられている帯域条件を満たす。
【０１７５】
【数６】
2008278007.tif 000008
条件３：リンクの空き帯域を越えない。
【０１７６】
【数７】
2008278007.tif 000009
上記の条件１，２，３を同時に満たすＦｋ＝（ｆ１，ｆ２，…，ｆｋ）が存在する場合には「ＯＫ」を、存在しない場合は「ＮＧ」をステップ１５００の解候補リスト作成処理のステップ１５２０に返却する。
【０１７７】
なお、ステップ２３１０における判定の計算は、総当りで計算する等、既存の技術を適用することが可能である。
【０１７８】
次に、図１６の複数パス一括計算処理（ステップ１０００）から呼び出されるステップ１６００の解候補の帯域割当・コスト計算処理のサブルーチンについて説明する。当該処理は、経路計算機能部１３０において、帯域を割り当て、各パスのメトリックにより該当パスグループのコストを決定するものである。
【０１７９】
図２２は、本発明の一実施の形態における解候補の帯域割当・コスト計算処理のフローチャートである。
【０１８０】
ステップ１６１０）  全ての解候補ｕについて以下の処理を実行する。
【０１８１】
ステップ２４００）  帯域割当処理のサブルーチンを呼び出して実行する。
【０１８２】
ステップ２５００）  図２５に示す帯域依存Group Type制約判定処理のサブルーチンを呼び出して実行する。
【０１８３】
ステップ１６２０）  パスグループが条件を満たす場合には、ステップ２６００に移行し、満たさない場合にはステップ１６３０に移行する。
【０１８４】
ステップ２６００）  図２６に示すコストＣｕ評価のサブルーチンを呼び出して実行し、その結果Ｃｕを返却する。当該処理は、割り当てられた帯域の合計値、また、パス間でのばらつきを元にコスト値を決定する。
【０１８５】
ステップ１６３０）  Ｕ←Ｕ−｛ｕ｝とし、Ｕを返却する。
【０１８６】
次に、ステップ１３００の候補パスリスト作成処理から呼び出される制約条件付K shortest path計算のサブルーチンについて説明する。
【０１８７】
当該処理は、経路計算機能部１３０において、ｋ本までの最小コストパスを計算する。候補パスリストの大きさは、解の探索範囲の大きさとなる。計算本数Ｋｃは、パス要求本数の最大値Ｋｍａｘより十分大きい値に設定する。
【０１８８】
図２３は、本発明の一実施の形態における制約条件付K shortest path計算処理のフローチャートである。
【０１８９】
ステップ２１１０）  結果候補のパスリストをＵｋ←φとする。
【０１９０】
ステップ２１２０）  │Ｕｋ│＝Ｋｃとなるまで以下の処理を繰り返す。
【０１９１】
ステップ８００）  図１４に示す制約条件付最短経路計算処理のサブルーチンを実行する。
【０１９２】
ステップ２１３０）  計算結果と同一の結果が結果候補Ｕｋに含まれない場合は、ステップ２１４０に移行し、含まれる場合は、ステップ２１５０に移行する。
【０１９３】
ステップ２１４０）  Ｕｋに結果を入れる。
【０１９４】
ステップ２１５０）  計算トポロジからリンクを一つ取り除く。
【０１９５】
次に、ステップ１５００の候補パスグループリスト作成処理から呼び出される経路依存group type制約判定処理（ステップ２２００）について説明する。当該処理は、経路計算機能部１３０から呼び出される、Group type制約を満たすかどうか判定する処理であり、制約項目が複数ある場合は、項目毎に複数回呼び出される。
【０１９６】
図２４は、本発明の一実施の形態における経路依存group type制約判定処理のフローチャートである。
【０１９７】
ステップ２２１０）  制約条件判定近傍部１５２において、パスグループが与えられたGroup type制約を満たすかを判定する。
【０１９８】
ステップ２２２０）  満たす場合は「ＯＫ」を、満たさない場合は「ＮＧ」を返却する。
【０１９９】
次に、上記のステップ１６００の解候補の帯域割当・コスト計算処理から呼び出される帯域依存Group Type制約判定処理（ステップ２５００）について説明する。
【０２００】
図２５は、本発明の一実施の形態における帯域依存Group Type制約判定処理のフローチャートである。当該処理は、帯域依存Group type制約を満たすかどうか判定する処理であり、制約項目が複数ある場合は、項目毎に複数回呼び出される。
【０２０１】
ステップ２５００）  制約条件判定機能部１５２において、インスタンスＤＢ１７０から判定対象ａｒｃとLink Type制約条件が読み込まれ、入力される。
【０２０２】
ステップ２５１０）  判定対象のａｒｃがLink Type制約条件を満たすかを判定し、ステップ１６００の処理に「ＯＫ」または、「ＮＧ」を返却する。
【０２０３】
次に、上記のステップ１６００の解候補の帯域割当・コスト計算処理から呼び出されるコストＣｕ評価処理（ステップ２６００）について説明する。
【０２０４】
図２６は、本発明の一実施の形態におけるコストＣｕ評価処理のフローチャートである。
【０２０５】
ステップ２６１０）  割り当てられた帯域の合計値、また、パス間でのばらつきを元にコスト値を決定し、ステップ１６００に返却する。
【０２０６】
次に、ステップ１０００から呼び出されるベスト候補選択処理（ステップ１７００）について説明する。
【０２０７】
図２７は、本発明の一実施の形態におけるベスト候補選択処理のフローチャートである。
【０２０８】
ステップ１７１０）  ステップ１６００で求められた解候補の中から最もコストの低い解を選択し、返却する。
【０２０９】
最後に、本予約完了後の処理について説明する。
【０２１０】
図２８は、本発明の一実施の形態における本予約完了後の動作のフローチャートである。
【０２１１】
ステップ３００１）  パラメータ測定機能部１５１において、メンバパスの制約条件を測定し、インスタンスＤＢ１７０に格納されている制約条件と比較し、制約条件に変化があった時点でステップ３００２に移行する。
【０２１２】
ステップ３００２）  パラメータ測定機能部１５１は、制約条件判定機能部１５２にメンバパスの制約条件の変化を通知する。
【０２１３】
ステップ３００３）  制約条件判定機能部１５２において、パラメータ測定機能部１５１から通知されたメンバパスパラメータに基づいて、新たなパス群パラメータを計算する。
【０２１４】
ステップ３００４）  制約条件判定機能部１５２は、計算されたパス群パラメータがインスタンスＤＢ１７０に格納されているパス群に対する制約条件を満たすかを判定し、満たす場合には、ステップ３００９に移行し、満たさない場合はステップ３００５に移行する。
【０２１５】
ステップ３００５）  パス群に対する制約条件を満たさない場合には、パスパラメータ・パス群パラメータ調整機能部１５３においてパラメータの調整が可能かを判定し、不可能な場合は、ステップ３００７に移行し、調整が可能な場合はステップ３００６に移行する。
【０２１６】
ステップ３００６）  パスパラメータ・パス群パラメータ調整機能部１５３でメンバパスのパラメータを変更し、ステップ３００９に移行する。
【０２１７】
ステップ３００７）  ステップ３００５において調整ができない場合は、経路計算機能部１３０に対して、再計算を指示する。
【０２１８】
ステップ３００８）  パス設定機能部１５４において、再計算されたパスを、ネットワーク上のルータに設定する。なお、この処理は、本予約処理において行われるものであり、ユーザが本予約までを望んでおらず、パス設定問い合わせのみである場合には、『予約可能』をメッセージとして予約端末２００に返却する。
【０２１９】
ステップ３００９）  インスタンスＤＢ１７０のパス群パラメータ、及びメンバパスパラメータを更新する。
【０２２０】
ステップ３０１０）  上記の処理が終了すると定常状態に遷移する。
【０２２１】
上記の実施の形態におけるＮＲＭ（経路予約装置）１００の動作をプログラムとして構築し、経路予約装置として利用されるコンピュータにインストールする、または、ネットワークを介して流通させることが可能である。
【０２２２】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【０２２３】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０２２４】
本発明は、ネットワーク資源の事前予約を行うシステムに適用可能である。
【図面の簡単な説明】
【０２２５】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態におけるパスの状態を示す図である。
【図４】本発明の一実施の形態における動作イメージを示す図である。
【図５】本発明の一実施の形態におけるＮＲＭの構成図である。
【図６】本発明の一実施の形態におけるＤＢのグループパスの管理情報の例である。
【図７】本発明の一実施の形態におけるパス群予約／キャンセル動作のシーケンスチャートである。
【図８】本発明の一実施の形態におけるパス制御機能部の構成図である。
【図９】本発明の一実施の形態における経路計算の全体処理のフローチャートである。
【図１０】本発明の一実施の形態における経路計算処理のサブルーチンの呼び出し関係を示す図である。
【図１１】本発明の一実施の形態における単一パス計算処理のフローチャートである。
【図１２】本発明の一実施の形態におけるExclusion判定処理のフローチャートである。
【図１３】本発明の一実施の形態におけるlink type制約処理のフローチャートである。
【図１４】本発明の一実施の形態における制約条件付き最短経路計算処理のフローチャートである。
【図１５】本発明の一実施の形態におけるPath Type制限判定のフローチャートである。
【図１６】本発明の一実施の形態における複数パス一括計算処理のフローチャートである。
【図１７】本発明の一実施の形態における複数パス計算用link type制約条件生成処理のフローチャートである。
【図１８】本発明の一実施の形態における候補パスリスト作成処理のフローチャートである。
【図１９】本発明の一実施の形態における候補パスグループリスト作成処理のフローチャートである。
【図２０】本発明の一実施の形態における解候補リスト作成処理のフローチャートである。
【図２１】本発明の一実施の形態における複数パス一括帯域判定処理のフローチャートである。
【図２２】本発明の一実施の形態における解候補の帯域割当・コスト計算処理のフローチャートである。
【図２３】本発明の一実施の形態における制約条件付きK shortest path計算処理のフローチャートである。
【図２４】本発明の一実施の形態における経路依存group type制約判定処理のフローチャートである。
【図２５】本発明の一実施の形態における帯域依存Group Type制約判定処理のフローチャートである。
【図２６】本発明の一実施の形態におけるコストＣｕ評価処理のフローチャートである。
【図２７】本発明の一実施の形態におけるベスト候補選択処理のフローチャートである。
【図２８】本発明の一実施の形態における本予約完了後の動作のフローチャートである。
【図２９】従来のパス予約クライアント・ＮＲＭ間の予約問い合わせの例である。
【符号の説明】
【０２２６】
１００  経路予約装置（ＮＲＭ）
１１０  メッセージ受信手段、ユーザ要求受付Ｉ／Ｆ
１１５  判定結果通知手段
１２０  コア部
１３０  経路計算手段、経路計算機能部
１４０  グループパラメータ生成手段、グループパラメータ生成部
１５０  制約条件判定手段、パス制御機能部
１５１  パラメータ測定機能部
１５２  制約条件判定機能部
１５３  パスパラメータ・パス群パラメータ調整機能部
１５４  パス設定機能部
１６０  ネットワーク連携Ｉ／Ｆ
１６５  情報収集手段、情報収集部
１７０  インスタンス記憶手段、インスタンスデータベース（ＤＢ）
１８０  ネットワーク・機器情報記憶手段、ネットワーク・機器情報データベース（ＤＢ）
２００  クライアント装置、予約端末
【図１】
2008278007.tif 000010
【図２】
2008278007.tif 000011
【図３】
2008278007.tif 000012
【図４】
2008278007.tif 000013
【図５】
2008278007.tif 000014
【図６】
2008278007.tif 000015
【図７】
2008278007.tif 000016
【図８】
2008278007.tif 000017
【図９】
2008278007.tif 000018
【図１０】
2008278007.tif 000019
【図１１】
2008278007.tif 000020
【図１２】
2008278007.tif 000021
【図１３】
2008278007.tif 000022
【図１４】
2008278007.tif 000023
【図１５】
2008278007.tif 000024
【図１６】
2008278007.tif 000025
【図１７】
2008278007.tif 000026
【図１８】
2008278007.tif 000027
【図１９】
2008278007.tif 000028
【図２０】
2008278007.tif 000029
【図２１】
2008278007.tif 000030
【図２２】
2008278007.tif 000031
【図２３】
2008278007.tif 000032
【図２４】
2008278007.tif 000033
【図２５】
2008278007.tif 000034
【図２６】
2008278007.tif 000035
【図２７】
2008278007.tif 000036
【図２８】
2008278007.tif 000037
【図２９】
2008278007.tif 000038