(57)【要約】【課題】網側に到着するサービス要求の内容に応じて光パスを効率的に設定することが可能な技術を提供する。【解決手段】光ネットワークの光パスの経路を設定する光パス設定方法において、ネットワークを用いたサービスを要求する為のサービス要求の内容を記憶手段に格納するステップと、そのサービスを受けるグループのメンバの情報とそのグループのメンバの属するノードの情報とサービスの提供時の要求帯域とを、前記記憶手段に格納したサービス要求の情報から読み出すステップと、ネットワーク内の各ノード間の空き帯域を格納している記憶手段から前記グループの各メンバの属するノード間の空き帯域を読み出し、その記憶手段から読み出した空き帯域と前記要求帯域とを比較して当該サービス要求を受け付けるかどうかを判定するステップとを有するものである。【選択図】  図１
2005064631.tif 000002
【特許請求の範囲】
【請求項１】
光ネットワークの光パスの経路を設定する光パス設定方法において、
ネットワークを用いたサービスを要求する為のサービス要求の内容を記憶手段に格納するステップと、そのサービスを受けるグループのメンバの情報とそのグループのメンバの属するノードの情報とサービスの提供時の要求帯域とを、前記記憶手段に格納したサービス要求の情報から読み出すステップと、
ネットワーク内の各ノード間の空き帯域を格納している記憶手段から前記グループの各メンバの属するノード間の空き帯域を読み出し、その記憶手段から読み出した空き帯域と前記要求帯域とを比較して当該サービス要求を受け付けるかどうかを判定するステップとを有することを特徴とする光パス設定方法。
【請求項２】
ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ノードで変換可能な波長を示す波長群の情報に応じて前記メンバの属するノード間の経路を選定することを特徴とする請求項１に記載された光パス設定方法。
【請求項３】
前記サービスを受けるメンバの追加を要求する為のメンバ追加要求の内容を記憶手段に格納するステップと、メンバの追加されるグループの情報とその追加メンバの属するノードの情報とサービスの提供時の要求帯域とを、前記記憶手段に格納したメンバ追加要求の情報から読み出すステップと、
ネットワーク内の各ノード間の空き帯域を格納している記憶手段から前記追加メンバの属するノードと前記グループの各メンバの属するノードとの間の空き帯域を読み出し、その記憶手段から読み出した空き帯域と前記要求帯域とを比較して当該メンバ追加要求を受け付けるかどうかを判定するステップとを有することを特徴とする請求項１または請求項２のいずれかに記載された光パス設定方法。
【請求項４】
前記サービスを受けるメンバの削除を要求する為のメンバ削除要求の内容を記憶手段に格納するステップと、メンバの削除されるグループの情報とその削除メンバの情報とを、前記記憶手段に格納したメンバ削除要求の情報から読み出すステップと、ネットワーク内の各ノード間の空き帯域を格納している記憶手段を参照し、前記削除メンバの属するノードと前記グループの各メンバの属するノードとの間の空き帯域を更新するステップとを有することを特徴とする請求項１乃至請求項３のいずれか１項に記載された光パス設定方法。
【請求項５】
リンク毎の使用率の分散を最小化することを目的関数として用いて解を求め、前記メンバの属するノード間の経路を選定することを特徴とする請求項１乃至請求項４のいずれか１項に記載された光パス設定方法。
【請求項６】
パス長の合計値を最小化することを目的関数として用いて解を求め、前記メンバの属するノード間の経路を選定することを特徴とする請求項１乃至請求項５のいずれか１項に記載された光パス設定方法。
【請求項７】
光ネットワークの光パスの経路を設定する光パス設定装置において、
ネットワークを用いたサービスを要求する為のサービス要求の内容を記憶手段に格納し、そのサービスを受けるグループのメンバの情報とそのグループのメンバの属するノードの情報とサービスの提供時の要求帯域とを、前記記憶手段に格納したサービス要求の情報から読み出す情報解析部と、
ネットワーク内の各ノード間の空き帯域を格納している記憶手段から前記グループの各メンバの属するノード間の空き帯域を読み出し、その記憶手段から読み出した空き帯域と前記要求帯域とを比較して当該サービス要求を受け付けるかどうかを判定する受付判定部とを備えることを特徴とする光パス設定装置。
【請求項８】
ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ノードで変換可能な波長を示す波長群の情報に応じて前記メンバの属するノード間の経路を選定するパス経路計算部を備えることを特徴とする請求項７に記載された光パス設定装置。
【請求項９】
前記情報解析部は、前記サービスを受けるメンバの追加を要求する為のメンバ追加要求の内容を記憶手段に格納し、メンバの追加されるグループの情報とその追加メンバの属するノードの情報とサービスの提供時の要求帯域とを、前記記憶手段に格納したメンバ追加要求の情報から読み出すものであり、
前記受付判定部は、ネットワーク内の各ノード間の空き帯域を格納している記憶手段から前記追加メンバの属するノードと前記グループの各メンバの属するノードとの間の空き帯域を読み出し、その記憶手段から読み出した空き帯域と前記要求帯域とを比較して当該メンバ追加要求を受け付けるかどうかを判定するものであることを特徴とする請求項７または請求項８のいずれかに記載された光パス設定装置。
【請求項１０】
前記情報解析部は、前記サービスを受けるメンバの削除を要求する為のメンバ削除要求の内容を記憶手段に格納し、メンバの削除されるグループの情報とその削除メンバの情報とを、前記記憶手段に格納したメンバ削除要求の情報から読み出すものであり、
前記受付判定部は、ネットワーク内の各ノード間の空き帯域を格納している記憶手段を参照し、前記削除メンバの属するノードと前記グループの各メンバの属するノードとの間の空き帯域を更新するものであることを特徴とする請求項７乃至請求項９のいずれか１項に記載された光パス設定装置。
【請求項１１】
前記パス経路計算部は、リンク毎の使用率の分散を最小化することを目的関数として用いて解を求め、前記メンバの属するノード間の経路を選定するものであることを特徴とする請求項７乃至請求項１０のいずれか１項に記載された光パス設定装置。
【請求項１２】
前記パス経路計算部は、パス長の合計値を最小化することを目的関数として用いて解を求め、前記メンバの属するノード間の経路を選定するものであることを特徴とする請求項７乃至請求項１１のいずれか１項に記載された光パス設定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、光ネットワーク上で、オンデマンド型であり、かつ品質保証型のＶＰＮ(Virtual Private Network)サービスを提供している場合において、サービス要求が網側に到着する場合に、各通信グループの端末が所属する光ルータ間にどの様な（仮想）光パスを設定すれば効率的かを定めるアルゴリズムに関する技術である。
【背景技術】
【０００２】
ＶＰＮは、仮想私設網とか仮想閉域網等と呼ばれ、ある限られたユーザグループのメンバ同士があたかも専用線で結ばれた様に他のユーザからは隔離された環境で通信を行うことができるサービスである（例えば非特許文献１乃至２参照）。公衆電話網においては、任意の電話番号体系を設定することにより、公衆網を専用線の様に利用できるサービスであり、一般に専用線を用いるよりも安価である。ＩＰ(Internet Protocol)網においてもＩＰ−ＶＰＮというサービスがあり、どのレイヤで実現するかにより、Ｌ２（レイヤ２）−ＶＰＮやＬ３（レイヤ３）−ＶＰＮと分類され、既に実際にサービスが開始されている。
【０００３】
また、本願出願人が先に出願した特願２００２−２４１４６６号、特願２００３−０６９０９３号、特願２００３−１０４２４７号には、光ネットワークの光パスの経路を設計する光パス設計方法において、ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ノードで変換可能な波長を示す波長群の情報に応じて現用経路や予備経路の経路設計を行うことが記載されている。
【非特許文献１】是友春樹監修、マルチメディア通信研究会編、「ＶＰＮ／ＶＬＡＮ教科書」、アスキー出版局、１９９９年８月２７日
【非特許文献２】“ＶＰＮソリューション”、［online］、平成１５年、［平成１５年７月１７日検索］、インターネット＜URL:http://www.allied-telesis.co.jp/solution/vpn/index.html＞
【発明の開示】
【発明が解決しようとする課題】
【０００４】
光ネットワークにおいて、仮想パスの経路設定法については、数理計画問題のＮＰ(Non-deterministic Polynomial)困難のクラスに入るため、厳密解法はルータ数が小さな範囲でしか解けず、メタヒューリスティック解法の様な例はまだ検討されていない。そのアルゴリズムをＶＰＮの場合に適用して、接続要求の受付可否判定を行い、受け付ける場合には各ルータ間に張るパスの設定経路を定めようというのが解決しようとしている課題であり、本発明の目的は上記問題を解決し、網側に到着するサービス要求の内容に応じて光パスを効率的に設定することが可能な技術を提供することにある。
【課題を解決するための手段】
【０００５】
本発明において、オンデマンド型のＶＰＮサービスを提供する場合、任意時点で任意のユーザ数のグループがある帯域を用いて接続要求を行う。網管理側はその接続要求を受信すると、あるアルゴリズムに基づいて受付の可否を判定し、受け付ける場合には、各リンクの空塞情報（リンクの使用率）を参考にしつつ、どのルートでそのグループ内の各端末が属するノードであるルータ間に光パスを設定するべきかを判断し、最適だと判断された経路でそれらのパスを設定する。要求帯域を満たせなくて受け付けない場合には、その旨をそのグループに返信する。具体的な方法は、次の通りである。
【０００６】
（１）ＶＰＮ受付判定法
まず、各メンバの属するノード間に要求を満たす帯域が存在するか否かを調べ、１つ以上の候補がある場合には受け付ける。各ノード間で必要な各パスの内、１本でも要求帯域を確保できないパスがある場合には受付を拒否する。
（２）光パス設定法
ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ノードで変換可能な波長を示す波長群の情報に応じて、グループの各メンバの属するノード間の経路を選定する。
（３）単独メンバの追加／終了の処理方法
あるグループへの追加メンバがある場合、追加メンバの属するノードと他のメンバの属するノードとの間に要求を満たす帯域が存在するか否かを調べ、１つ以上の候補がある場合には受け付け、またそのグループ中に単独で終了したいメンバがいる場合には、そのグループのメンバの属するノードと他のメンバの属するノードとの間の帯域情報を更新することにより、メンバ単独での追加または終了を可能にする。
（４）ＶＰＮにおける光パス設定法の目的関数の選択１
前記光パス設定法で目的関数を用いる際に、目的関数として各リンクの使用率の分散を用い、それを最小とする様なパス候補の組み合わせを準最適解として提示する。
（５）ＶＰＮにおける光パス設定法の目的関数の選択２
前記光パス設定法で目的関数を用いる際に、目的関数としてパス長の総合計値を用い、それを最小とする様なパス候補の組み合わせを準最適解として提示する。
【発明の効果】
【０００７】
本発明によれば、オンデマンド型ＶＰＮサービスにおいて、各グループからのある要求帯域を伴う接続要求に対して、その受付可否を短時間でサーチ、決定し、受付可能な場合にはそのグループの各メンバが属するルータ間に張る光パスの経路と使用する波長を提示することができる。
【発明を実施するための最良の形態】
【０００８】
以下に光ネットワークの光パスの経路を設定する一実施形態の光パス設定装置であるＶＰＮ管理ＯｐＳ(Operation System)について説明する。
【０００９】
図１は本実施形態のＶＰＮ管理ＯｐＳの概略構成を示す図である。図１に示す様に本実施形態のＶＰＮ管理ＯｐＳ１は、プロセッシング部２と、パス経路計算部３と、受付判定部４と、情報解析部５と、情報管理部６と、パス管理＆解析部７と、リンク情報管理部８と、メモリ９と、ＰＡＤ１０と、パケット送信部１１と、パケット受信部１２とを有している。
【００１０】
プロセッシング部２は、ＶＰＮ管理ＯｐＳ１内の各種情報を処理する手段である。パス経路計算部３は、ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ノードである各ルータで変換可能な波長を示す波長群の情報に応じて前記メンバの属するルータ間の経路を選定する手段である。
【００１１】
受付判定部４は、メンバの属するルータ間の空き帯域を情報管理部６経由でメモリ９から読み出し、そのメモリ９から読み出した空き帯域と要求帯域とを比較して当該サービス要求を受け付けるかどうかを判定する手段である。
【００１２】
情報解析部５は、ネットワークを用いたサービスを要求する為のサービス要求の内容をメモリ９に格納し、そのサービスを受けるグループのメンバの情報と、そのグループのメンバの属するルータの情報と、サービスの提供時の要求帯域とを、メモリ９に格納したサービス要求の情報から読み出す手段である。
【００１３】
情報管理部６は、メモリ９内に格納されている情報の入出力等の管理を行う手段である。パス管理＆解析部７は、メンバの属するルータ間のパスの管理と解析を行う手段である。リンク情報管理部８は、ＩＰ網１３内のルータ間のリンク情報を管理する手段である。
【００１４】
メモリ９は、各種情報を格納／蓄積する手段である。ＰＡＤ１０は、各種情報をＩＰパケットに変換したり、その逆にＩＰパケットから各種情報への変換を行ったりするパケット組み立て／分解手段である。パケット送信部１１は、網内の他の装置へＩＰパケットを送出する手段である。パケット受信部１２は、網内の他の装置からの到着パケットを受信する手段である。
【００１５】
本実施形態において、オンデマンド型のＶＰＮサービスを受けるユーザ側の情報処理装置から網の管理者側の光パス設定装置であるＶＰＮ管理ＯｐＳ１にサービス提供を申し込むと、その要求帯域（またはＶＰＮ内で選択するサービス名（例えば、ＣＤＮ(Content Delivery Network)、ＶＰＮ、テレビ会議等））、サービスを受けたいグループに属するユーザ名、それが属する光ルータ等の情報等がこのＶＰＮ管理ＯｐＳ１に到着する。
【００１６】
このＶＰＮ管理ＯｐＳ１では、これらの情報からその接続要求を受け付けるか否かを判定し、受け付ける場合にはその各パスのルートと波長を決定して結果を返し、受け付けない場合にはその旨を結果として返す。受け付けた場合にはパスやリンクの管理情報をアップデートし、実際に光パスを設定／解除する帯域設定ＯｐＳに対してその旨を指示する。サービスが終了したという情報を受信した場合には、管理情報をアップデートし、光パスを設定／解除する帯域設定ＯｐＳに対してその旨を指示する。
【００１７】
図１に示す様にＶＰＮ受付判定及びパス設定用のＯｐＳであるＶＰＮ管理ＯｐＳ１は、サーバント（サーバ及びクライアントのいずれにもなりうる端末装置）であり、通常のＰＣ(Personal Computer)の機能を持つ所謂端末であるが、Ｐ２Ｐ(Peer to Peer)アプリケーションレイヤとしてはサーバントとして見える装置である。
【００１８】
図２は本実施形態の受付判定処理の処理手順を示すフローチャートである。ステップ２０１でＶＰＮ管理ＯｐＳ１の情報解析部５は、ネットワークを用いたサービスを要求する為のサービス要求が、ＩＰ網１３を介し、パケット受信部１２及びＰＡＤ１０を経由して、オンデマンド型のＶＰＮサービスを受けるユーザ側の情報処理装置から到着しているかどうかを判定し、サービス要求が到着している場合にはそのサービス要求の内容をメモリ９に格納してステップ２０２へ進む。
【００１９】
ステップ２０２で情報解析部５は、メモリ９中に格納したサービス要求の内容を参照して解析し、そのサービスを受けるグループのメンバの情報としてそのグループのメンバ数Ｎと、そのグループのメンバの属するルータの情報としてそのルータの位置を示す情報と、サービスの提供時の要求帯域Ｍ[bit/sec]をサービス要求の情報から読み出して受付判定部４に渡す。
【００２０】
ステップ２０３で受付判定部４は、情報解析部５から受け取ったグループのメンバ数Ｎ、ルータの位置、要求帯域Ｍの値をメモリ９に格納し、変数ｉに「１」を代入した後、ステップ２０４へ進み、変数ｊにｉ＋１を代入する。
【００２１】
ステップ２０５で受付判定部４は、メモリ９に格納したルータの位置情報の中からメンバｉ及びメンバｊの属するルータの位置情報を選択した後、その位置情報を情報管理部６へ渡して当該ルータ間の空き帯域を情報管理部６へ問い合わせる。
【００２２】
情報管理部６のパス管理＆解析部７及びリンク情報管理部８は、受付判定部４からの問い合わせを受け付けると、メンバｉ及びメンバｊの属するルータ間の空き帯域の値をメモリ９から読み出して受付判定部４へ渡す。ここで、本実施形態では、各リンク毎に使用帯域と空き帯域がリアルタイムに管理され、各ルータ間の空き帯域がメモリ９に格納されているものとする。
【００２３】
ステップ２０５で受付判定部４は、情報管理部６から空き帯域の値を受け付けると、その空き帯域の値とステップ２０３でメモリ９に格納しておいた要求帯域Ｍとを比較して、メンバｉの属するルータとメンバｊの属するルータとの間に要求帯域Ｍの空きが有るかどうかを判定し、空きが有る場合にはステップ２０６へ進む。
【００２４】
ステップ２０６では、変数ｊがステップ２０３でメモリ９に格納しておいたグループのメンバ数Ｎと等しいかどうかを調べ、変数ｊがグループのメンバ数Ｎと等しくない場合にはステップ２０７へ進み、変数ｊに「１」を加算してステップ２０５へ戻る。
【００２５】
またステップ２０６で変数ｊがグループのメンバ数Ｎと等しい場合にはステップ２０８へ進み、変数ｉがグループのメンバ数Ｎから「１」を引いた数と等しいかどうかを調べる。その結果、変数ｉがグループのメンバ数Ｎから「１」を引いた数と等しくない場合にはステップ２０９へ進み、変数ｉに「１」を加算してステップ２０４へ戻る。
【００２６】
またステップ２０８で調べた結果、変数ｉがグループのメンバ数Ｎから「１」を引いた数と等しい場合にはステップ２１０へ進み、ステップ２０１で到着したサービス要求による接続要求を受け付け、このグループのメンバの情報処理装置に接続要求が受け付けられたことを通知した後、実際に光パスを設定／解除する帯域設定ＯｐＳへ接続要求が受け付けられたことを通知する。
【００２７】
そしてパス経路計算部３により光パスの経路が設定された後、情報管理部６に管理情報のアップデートを指示し、情報管理部６のパス管理＆解析部７及びリンク情報管理部８は、そのグループのメンバの属するルータ間の各パスについて、そのパスの各リンクにおける空き帯域の値をメモリ９から読み出して要求帯域Ｍを減算した後、再びメモリ９に格納して管理情報のアップデートを行う。
【００２８】
またステップ２０５で判定した結果、メンバｉの属するルータとメンバｊの属するルータとの間に要求帯域Ｍの空きが無い場合にはステップ２１１へ進み、接続要求を拒否する旨をこのグループのメンバの情報処理装置に通知する。
【００２９】
本実施形態のＶＰＮ管理ＯｐＳ１では、前記の様にしてサービス要求中の要求を満たす帯域がメンバの属するノード間に存在するか否かを調べてそのサービス要求を受け付けるかどうかを判定し、接続要求の受け付けた場合に、それらのノード間の経路及び波長の選択処理をパス経路計算部３により行う。
【００３０】
図３は本実施形態の光パスの経路及び波長の選択処理の処理手順を示すフローチャートである。ステップ３０１でパス経路計算部３は、グループのメンバ数Ｎ、それらが属するルータの位置、要求帯域Ｍ[bit/sec]、許容波長数ｇ、繰り返し数Ｒ、許容探索範囲α、β、波長変換機能付ルータの位置、予備パスの有無等を示す必要パラメータを呼び出し元から受け取って各値の入力を行い、入力した各値をメモリ９に格納する。
【００３１】
ステップ３０２では、ＶＰＮ管理ＯｐＳ１の起動時等に予め定められた目的関数の情報をメモリ９から読み出し、そのＶＰＮ管理ＯｐＳ１で用いられる目的関数が、コストであるパス長の合計値を最小化するものであるか、或いはリンク毎の平均使用率の分散を最小化するものであるかを調べ、ＶＰＮ管理ＯｐＳ１で用いられる目的関数がリンク毎の平均使用率の分散を最小化することを含むものである場合にはステップ３０３へ進み、ＶＰＮ管理ＯｐＳ１で用いられる目的関数がパス長の合計値を最小化するものである場合にはステップ３０６へ進む。
【００３２】
ステップ３０３では、ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ルータで変換可能な波長を示す波長群の情報に応じて、変数化、定式化、目的関数の設定を行い、その際、リンク毎の平均使用率の分散を最小化することを目的関数として設定する。そして、整数計画問題を解くソフトウェアの起動を行って、各メンバの属するルータ間の経路を求める。
【００３３】
ステップ３０４では、前記求めた結果が望み通りであるかどうかを調べる。例えば、求められた経路におけるリング毎の平均使用率の分散が予め定められた所定の値よりも小さいかどうかを調べることにより結果が望み通りであるかを判定する。結果が望み通りではない場合には、ステップ３０５で繰り返し数や探索範囲等の入力値を変更してステップ３０３へ戻り、結果が望み通りである場合には処理を終了する。
【００３４】
またステップ３０６では、ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ルータで変換可能な波長を示す波長群の情報に応じて、変数化、定式化、目的関数の設定を行い、その際、コストであるパス長の合計値を最小化することを目的関数として設定する。そして、整数計画問題を解くソフトウェアの起動を行って、各メンバの属するルータ間の経路を求める。
【００３５】
ステップ３０７では、前記求めた結果が望み通りであるかどうかを調べる。例えば、求められた経路におけるパス長の合計値が予め定められた所定の値よりも小さいかどうかを調べることにより結果が望み通りであるかを判定する。結果が望み通りではない場合には、ステップ３０８で繰り返し数や探索範囲等の入力値を変更してステップ３０６へ戻り、結果が望み通りである場合には処理を終了する。
【００３６】
ここで、前記ステップ３０３及びステップ３０６において、ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ルータで変換可能な波長を示す波長群の情報に応じて、変数化、定式化、目的関数の設定を行う際には、例えば本願出願人が先に出願した特願２００２−２４１４６６号、特願２００３−０６９０９３号、特願２００３−１０４２４７号に記載の様に行うものとする。
【００３７】
図４は本実施形態のグループ内のメンバの追加／終了がある場合の処理手順を示すフローチャートである。ステップ４０１でＶＰＮ管理ＯｐＳ１の情報解析部５は、光パスを用いたサービスを受けるメンバの追加を要求する為のメンバ追加要求が、ＩＰ網１３を介し、パケット受信部１２及びＰＡＤ１０を経由して、ユーザ側の情報処理装置から到着しているかどうかを判定し、メンバ追加要求が到着している場合にはそのメンバ追加要求の内容をメモリ９に格納してステップ４０２へ進む。
【００３８】
ステップ４０２で情報解析部５は、メモリ９中に格納したメンバ追加要求の内容を参照して解析し、そのメンバが追加されるグループの情報としてそのグループのメンバ数Ｎと、その追加メンバＡの属するルータの情報としてそのルータの位置を示す情報と、サービスの提供時の要求帯域Ｍ[bit/sec]をメンバ追加要求の情報から読み出して受付判定部４に渡す。
【００３９】
ステップ４０３で受付判定部４は、情報解析部５から受け取ったグループのメンバ数Ｎ、ルータの位置、要求帯域Ｍの値をメモリ９に格納し、変数ｉに「１」を代入した後、ステップ４０４へ進む。
【００４０】
ステップ４０４で受付判定部４は、メモリ９に格納されているルータの位置情報の中からメンバＡ及びメンバｉの属するルータの位置情報を選択した後、その位置情報を情報管理部６へ渡して当該ルータ間の空き帯域を情報管理部６へ問い合わせる。
【００４１】
情報管理部６のパス管理＆解析部７及びリンク情報管理部８は、受付判定部４からの問い合わせを受け付けると、メンバＡ及びメンバｉの属するルータ間の空き帯域の値をメモリ９から読み出して受付判定部４へ渡す。ここで、図２の処理と同様に本実施形態では、各リンク毎に使用帯域と空き帯域がリアルタイムに管理され、各ルータ間の空き帯域がメモリ９に格納されているものとする。
【００４２】
ステップ４０４で受付判定部４は、情報管理部６から空き帯域の値を受け付けると、その空き帯域と、ステップ４０３でメモリ９に格納しておいた要求帯域Ｍとを比較して、メンバＡの属するルータとメンバｉの属するルータとの間に要求帯域Ｍの空きが有るかどうかを判定し、空きが有る場合にはステップ４０５へ進む。
【００４３】
ステップ４０５では、変数ｉがステップ４０３でメモリ９に格納しておいたグループのメンバ数Ｎと等しいかどうかを調べ、変数ｉがグループのメンバ数Ｎと等しくない場合にはステップ４０６へ進み、変数ｉに「１」を加算してステップ４０４へ戻る。
【００４４】
またステップ４０５で変数ｉがグループのメンバ数Ｎと等しい場合にはステップ４０７へ進み、ステップ４０１で到着したメンバ追加要求を受け付け、このメンバＡの情報処理装置に追加要求が受け付けられたことを通知する。
【００４５】
ステップ４０８で受付判定部４は、実際に光パスを設定／解除する帯域設定ＯｐＳへ追加要求が受け付けられたことを通知する。そしてパス経路計算部３により光パスの経路が設定された後、情報管理部６に管理情報のアップデートを指示し、情報管理部６のパス管理＆解析部７及びリンク情報管理部８は、メンバＡの属するルータと他のメンバの属するルータとの間の各パスについて、そのパスの各リンクにおける空き帯域の値をメモリ９から読み出して要求帯域Ｍを減算した後、再びメモリ９に格納して管理情報のアップデートを行う。
【００４６】
またステップ４０４で判定した結果、メンバＡの属するルータとメンバｉの属するルータとの間に要求帯域Ｍの空きが無い場合にはステップ４０９へ進み、メンバ追加要求を拒否する旨をメンバＡの情報処理装置に通知する。
【００４７】
一方、ステップ４０１で判定した結果、メンバ追加要求が到着していない場合にはステップ４１０へ進む。
ステップ４１０で情報解析部５は、光パスを用いたサービスを受けるメンバの削除を要求する為のメンバ削除要求が、ＩＰ網１３を介し、パケット受信部１２及びＰＡＤ１０を経由して、ユーザ側の情報処理装置から到着しているかどうかを判定し、メンバ削除要求が到着している場合にはそのメンバ削除要求の内容をメモリ９に格納してステップ４１１へ進む。
【００４８】
ステップ４１１では、メモリ９中に格納したメンバ追加要求の内容を参照して解析し、そのメンバが削除されるグループの情報としてそのグループを識別する為の情報と、その削除されるメンバＫを識別する為の情報をメンバ削除要求の情報から読み出して受付判定部４に渡し、ステップ４０８へ進む。
【００４９】
ステップ４０８で受付判定部４は、実際に光パスを設定／解除する帯域設定ＯｐＳへ通知してメンバＫの属するルータと他のメンバの属するルータとの間の光パスの解除を指示した後、情報管理部６に管理情報のアップデートを指示する。
【００５０】
情報管理部６のパス管理＆解析部７及びリンク情報管理部８は、パスの設定時にメモリ９に格納しておいた各メンバの属するルータの位置情報と要求帯域Ｍの情報をメモリ９から読み出した後、メンバＫの属するルータと他のメンバの属するルータとの間の各パスについて、そのパスの各リンクにおける空き帯域の値をメモリ９から読み出して要求帯域Ｍを加算した後、再びメモリ９に格納して管理情報のアップデートを行う。
【００５１】
図５は本実施形態の目的関数としてリンク使用率の分散を用いる場合の処理手順を示すフローチャートである。ステップ５０１でＶＰＮ管理ＯｐＳ１のパス経路計算部３は、ネットワークを用いたサービスを要求する為のサービス要求の内容がメモリ９に格納されているかどうかを調べ、格納されている場合にはステップ５０２へ進む。
【００５２】
ステップ５０２では、Ｒ回だけ初期値から解を探索する処理を行う。すなわち、ネットワーク全体で使用できる波長数やネットワーク内の波長切替え機能、独立指定の行われているパスが独立となるかどうか、またはネットワーク内の各ルータで変換可能な波長を示す波長群の情報に応じて、変数化、定式化、目的関数の設定、整数計画問題を解くソフトウェアの起動を行って、Ｒ回だけ初期値から解を探索し、各メンバの属するルータ間のパスを求める。
【００５３】
ステップ５０３では、各リンクにおける空き帯域の値をメモリ９から読み出した後、メモリ９中に格納されているサービス要求の内容を参照し、そのサービスを受けるグループのメンバの情報としてそのグループのメンバ数Ｎと、そのグループのメンバの属するルータの情報としてそのルータの位置を示す情報と、サービスの提供時の要求帯域Ｍ[bit/sec]をサービス要求の情報から読み出す。
【００５４】
ステップ５０４では、前記読み出したグループのメンバ数Ｎ、ルータの位置、要求帯域Ｍの値をメモリ９に格納し、変数ｊに「１」を代入してステップ５０５へ進む。
【００５５】
ステップ５０５では、ステップ５０２で求めた解を基にそのグループに対する解候補（局所解）の計算を行う。すなわち、リンク毎の平均使用率の分散を最小化することを目的関数として設定し、整数計画問題を解くソフトウェアの起動を行って、各メンバの属するルータ間のパスを求める。
【００５６】
ステップ５０６では、ステップ５０５で得られた解候補における各リンクの使用率の分散を計算する。すなわち各リンクについて、そのリンクで利用可能な最大帯域に対する使用帯域の割合を求めて当該リンクの使用率とした後、その求めた各リンクにおけるリンク使用率の値の分散を算出する。
【００５７】
ステップ５０７では、ステップ５０６での分散の計算がステップ５０４で変数ｊに「１」を設定してから初めての計算であるか、またはステップ５０６で計算された分散が、これまでに計算した分散の最小値よりも小さいかどうかを調べ、今回の分散の計算が初めての計算であるか、またはこれまでに計算した分散の最小値よりも小さい場合にはステップ５０８へ進む。
【００５８】
ステップ５０８では、この解におけるパスの情報を最適解としてメモリ９に格納し、前記算出された分散の値を、これまでに計算された分散の最小値としてメモリ９に保持しておく。
【００５９】
ステップ５０９では、変数ｊが繰り返し回数Ｒと等しいかどうかを調べ、変数ｊが繰り返し回数Ｒと等しくない場合にはステップ５１０へ進み、変数ｊに「１」を加算してステップ５０５へ戻る。
【００６０】
またステップ５０９で判定した結果、変数ｊが繰り返し回数Ｒと等しい場合にはステップ５１１へ進み、この時点でメモリ９に格納されている最適解を計算結果としてステップ５１２へ進む。ステップ５１２では、計算結果を帯域設定ＯｐＳへ通知し、管理情報をアップデートする。
【００６１】
前記の様に本実施形態によれば、オンデマンド型ＶＰＮサービスにおいて、各グループからのある要求帯域を伴う接続要求に対して、その受付可否を短時間でサーチ、決定し、受付可能な場合にはそのグループの各メンバが属するルータ間に張る光パスの経路と使用する波長を提示することができる。
【００６２】
以上説明した様に本実施形態の光パス設定装置によれば、サービス要求中の要求を満たす帯域がメンバの属するノード間に存在するか否かを調べてそのサービス要求を受け付けるかどうかを判定するので、網側に到着するサービス要求の内容に応じて光パスを効率的に設定することが可能である。
【図面の簡単な説明】
【００６３】
【図１】本実施形態のＶＰＮ管理ＯｐＳの概略構成を示す図である。
【図２】本実施形態の受付判定処理の処理手順を示すフローチャートである。
【図３】本実施形態の光パスの経路及び波長の選択処理の処理手順を示すフローチャートである。
【図４】本実施形態のグループ内のメンバの追加／終了がある場合の処理手順を示すフローチャートである。
【図５】本実施形態の目的関数としてリンク使用率の分散を用いる場合の処理手順を示すフローチャートである。
【符号の説明】
【００６４】
１…ＶＰＮ管理ＯｐＳ、１３…ＩＰ網、２…プロセッシング部、３…パス経路計算部、４…受付判定部、５…情報解析部、６…情報管理部、７…パス管理＆解析部、８…リンク情報管理部、９…メモリ、１０…ＰＡＤ、１１…パケット送信部、１２…パケット受信部。
【図１】
2005064631.tif 000003
【図２】
2005064631.tif 000004
【図３】
2005064631.tif 000005
【図４】
2005064631.tif 000006
【図５】
2005064631.tif 000007