(57)【要約】【課題】  ＶＬＡＮにおいて、各リンクで流れるトラヒック（負荷）を均等にするためのマルチプルスパニングツリー（ＳＴ）を得る。【解決手段】  構築すべきスＳＴの構成ノード情報を有するＳＴ構築指令に応答して、通信網のトポロジ情報とリンクコスト情報とに基づいて、通信網にＳＴを構築する際に、ＳＴ構成ノードの各ノードペア間のユニキャストパスを、リンクコスト情報を用いて最短路探索アルゴリズムにより探索し（ステップＳ１）、この探索により得られた各パスを重ね合わせたグラフに閉路が存在するとき（ステップＳ２）、この閉路を構成するリンクのうち最もコストが高いリンクを閉鎖して（ステップＳ３）、この閉鎖したリンクを通っていた全てのパスについて、閉路を迂回するようパスを設定し（ステップＳ４）、各ユニキャストパスが通過するリンクで構築されるツリー構造のグラフを構築ＳＴとする（ステップＳ５）。【選択図】      図３                                                  
2005086460.tif 000002
【特許請求の範囲】
【請求項１】
構築すべきスパニングツリーの構成ノード情報を有するスパニングツリー構築指令に応答して、通信網のトポロジ情報とリンクコスト情報とに基づいて、前記通信網にスパニングツリーを構築する経路設計装置であって、
前記スパニングツリーの構成ノードそれぞれの間に、経路のコストが最小となるようなユニキャストパスを探索する最短路探索手段と、
前記最短路探索手段により得られた各パスを重ね合わせたグラフに閉路が存在する場合には、前記閉路が解消するようにパスを設定するパス設定手段と、
前記パス設定手段により得られたパスにおいて各ユニキャストパスが通過するリンクで構築されるグラフを前記スパニングツリーとするスパニングツリー設定手段と、
を含むことを特徴とする経路設計装置。
【請求項２】
前記パス設定手段は、前記最短路探索手段により得られた各パスを重ね合せたグラフに閉路が存在するときに、この閉路を構成するリンクのうち最もコストが高いリンクを閉鎖して、この閉鎖したリンクを通っていた全てのパスについて、前記閉路を迂回するようパスを設定することを特徴とする請求請１記載の経路設計装置。
【請求項３】
前記スパニングツリー構築指令は、前記構成ノードの各ノードペア間のトラヒック情報をも有し、前記トラヒック情報を用いて前記スパニングツリー設定後のリンクコストを、全てのリンクについて更新するリンクコスト更新手段を、更に含むことを特徴とする請求項１または２記載の経路設計装置。
【請求項４】
前記トラヒック情報はリンク利用帯域を示す情報であり、前記リンク利用帯域を用いて前記リンクコストを算出するリンクコスト算出手段を、更に含むことを特徴とする請求項１〜３いずれか記載の経路設計装置。
【請求項５】
前記リンクコスト算出手段は、リンク利用可能帯域に対する前記リンク利用帯域の割合であるリンク帯域利用率であることを特徴とする請求項４記載の経路設計装置。
【請求項６】
構築すべきスパニングツリーの構成ノード情報を有するスパニングツリー構築指令に応答して、通信網のトポロジ情報とリンクコスト情報とに基づいて、前記通信網にスパニングツリーを構築する経路設計方法であって、
前記スパニングツリーの構成ノードそれぞれの間に、経路のコストが最小となるようなユニキャストパスを探索する最短路探索ステップと、
前記最短路探索ステップにより得られた各パスを重ね合わせたグラフに閉路が存在する場合には、前記閉路が解消するようにパスを設定するパス設定ステップと、
前記パス設定ステップにより得られたパスにおいて各ユニキャストパスが通過するリンクで構築されるグラフを前記スパニングツリーとするスパニングツリー設定ステップと、
を含むことを特徴とする経路設計方法。
【請求項７】
前記パス設定ステップは、前記最短路探索ステップにより得られた各パスを重ね合せたグラフに閉路が存在するときに、この閉路を構成するリンクのうち最もコストが高いリンクを閉鎖して、この閉鎖したリンクを通っていた全てのパスについて、前記閉路を迂回するようパスを設定することを特徴とする請求請６記載の経路設計方法。
【請求項８】
前記スパニングツリー構築指令は、前記構成ノードの各ノードペア間のトラヒック情報をも有し、前記トラヒック情報を用いて前記スパニングツリー設定後のリンクコストを、全てのリンクについて更新するリンクコスト更新ステップを、更に含むことを特徴とする請求項６または７記載の経路設計方法。
【請求項９】
前記トラヒック情報はリンク利用帯域を示す情報であり、前記リンク利用帯域を用いて前記リンクコストを算出するリンクコスト算出ステップを、更に含むことを特徴とする請求項６〜８いずれか記載の経路設計方法。
【請求項１０】
前記リンクコスト算出ステップは、リンク利用可能帯域に対する前記リンク利用帯域の割合であるリンク帯域利用率であることを特徴とする請求項９記載の経路設計方法。
【請求項１１】
構築すべきスパニングツリーの構成ノード情報を有するスパニングツリー構築指令に応答して、通信網のトポロジ情報とリンクコスト情報とに基づいて、前記通信網にスパニングツリーを構築する経路設計方法をコンピュータにより実行させるためのプログラムであって、
前記スパニングツリーの構成ノードそれぞれの間に、経路のコストが最小となるようなユニキャストパスを探索する最短路探索処理と、
前記最短路探索処理により得られた各パスを重ね合わせたグラフに閉路が存在する場合には、前記閉路が解消するようにパスを設定するパス設定処理と、
前記パス設定処理により得られたパスにおいて各ユニキャストパスが通過するリンクで構築されるグラフを前記スパニングツリーとするスパニングツリー設定処理と、
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路設計装置及びその方法並びにプログラムに関し、特にマルチプルＳＴ（ＭＳＴ：Multiple Spanning Tree）の技術を使用してＶＬＡＮ（Virtual Local Area Network）毎にＳＴ（Spanning Tree ）を設定する場合におけるスパニングツリー設計方式に関するものである。
【背景技術】
【０００２】
ＳＴの形状を決定する公知の設計技術として、例えば、非特許文献１に開示のものがある。ここでの方法は、まず、各ＶＬＡＮサービスオーダ（ＶＬＡＮメンバとそのメンバ（ノードとも呼ばれる）間のトラヒックおよびブロードキャストトラヒック）が時系列で与えられることを仮定し、そのとき、ネットワーク管理システムがＳＴトポロジを設計する、というものである。この設計方法は、リンク利用率に基づくリンクコストを定義し、ＶＬＡＮサービスオーダ毎にリンクコストの和が最小となるＳＴトポロジを探索するというアプローチであって、すなわちツリー（木）のコストに関して最小コストとなる木を探索する最小木探索という手法である。
【０００３】
具体的な設計手順としては、以下のとおりである（事前にリンク利用率に基づく何らかの関数でリンクコストを定義しておく）。
（１）あらかじめ複数のＳＴをランダムに構築する。
（２）ＶＬＡＮサービスオーダが与えられた際、まず（１）で生成した各ＳＴに沿って、ＶＬＡＮメンバを全て含むリンク数最小の木を構築する。
（３）（２）で構築したそれぞれの木に対して、あらかじめ決められているリンクコストから、木のコストを算出する。この際、木のコストは、木を構成している全てのリンクのコストの和として算出する。
（４）それぞれの木のコストを比較し、コスト最小の木を、そのＶＬＡＮに対するＳＴとして選択する。
（５）（２）〜（４）までの手順を、ＶＬＡＮサービスオーダが与えられるたびに繰り返す。
【０００４】
なお、設計されたＳＴトポロジの実際のネットワークへの設定は、マルチプルスパンニングツリープロトコル（Multiple Spanning Tree Protocol;MSTP）を用いて、設定者が適切にブリッジやＩＤやリンクのコストを設定することによって行われる。
【０００５】
なお、２ノード間における最短路を探索する最短路木探索の手法が非特許文献２に開示されており、“Dijkstra”アルゴリズムとして広く知られている。ここで、最短路とは、２ノードを結ぶ経路に用いられる全てのリンクのコストの和が最小となる経路を意味する。
【０００６】
【非特許文献１】永田晃、上野仁、宮崎啓二、中後明、「ＭＳＴＰを用いた広域ＬＡＮサービスにおけるＶＬＡＮ設計手法の検討」（２００２年電子情報通信学会通信ソサエティ大会、Ｂ−１−５１、ｐ．８３、Ｓｅｐ．２００２）
【非特許文献２】滝根哲哉、伊藤大雄、西尾章治郎、「岩波講座  インターネット  第５巻  ネットワーク設計理論」（岩波書店、２００１年発行、ｐ．１５８−ｐ．１６２）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし上記非特許文献１（以下、従来技術とする）でのアプローチでは、木のコストとして、木を構成するリンクコストの和のみを考慮しているために、十分な負荷分散が実現できないという問題が挙げられる。また、上記特許文献２では、単に、互いに通信を行う２ノード間の経路探手法を述べたものにすぎず、ＭＳＴの構築手法については、何等述べられておらず、またその示唆さえもない。
【０００８】
本発明の目的は、ＶＬＡＮにおけるＭＳＴを構築するに際して、各リンクに流れるトラヒックを均等化して負荷分散を可能としたスパニングツリー設計装置及びその方法並びにプログラムを提供することである。
【課題を解決するための手段】
【０００９】
本発明による経路設計装置は、構築すべきスパニングツリーの構成ノード情報を有するスパニングツリー構築指令に応答して、通信網のトポロジ情報とリンクコスト情報とに基づいて、前記通信網にスパニングツリーを構築する経路設計装置であって、前記スパニングツリーの構成ノードそれぞれの間に、経路のコストが最小となるようなユニキャストパスを探索する最短路探索手段と、前記最短路探索手段により得られた各パスを重ね合わせたグラフに閉路が存在する場合には、前記閉路が解消するようにパスを設定するパス設定手段と、前記パス設定手段により得られたパスにおいて各ユニキャストパスが通過するリンクで構築されるグラフを前記スパニングツリーとするスパニングツリー設定手段とを含むことを特徴とする。
【００１０】
本発明による経路設計方法は、構築すべきスパニングツリーの構成ノード情報を有するスパニングツリー構築指令に応答して、通信網のトポロジ情報とリンクコスト情報とに基づいて、前記通信網にスパニングツリーを構築する経路設計方法であって、前記スパニングツリーの構成ノードそれぞれの間に、経路のコストが最小となるようなユニキャストパスを探索する最短路探索ステップと、前記最短路探索ステップにより得られた各パスを重ね合わせたグラフに閉路が存在する場合には、前記閉路が解消するようにパスを設定するパス設定ステップと、前記パス設定ステップにより得られたパスにおいて各ユニキャストパスが通過するリンクで構築されるグラフを前記スパニングツリーとするスパニングツリー設定ステップとを含むことを特徴とする。
【００１１】
本発明によるプログラムは、構築すべきスパニングツリーの構成ノード情報を有するスパニングツリー構築指令に応答して、通信網のトポロジ情報とリンクコスト情報とに基づいて、前記通信網にスパニングツリーを構築する経路設計方法をコンピュータにより実行させるためのプログラムであって、前記スパニングツリーの構成ノードそれぞれの間に、経路のコストが最小となるようなユニキャストパスを探索する最短路探索処理と、前記最短路探索処理により得られた各パスを重ね合わせたグラフに閉路が存在する場合には、前記閉路が解消するようにパスを設定するパス設定処理と、前記パス設定処理により得られたパスにおいて各ユニキャストパスが通過するリンクで構築されるグラフを前記スパニングツリーとするスパニングツリー設定処理とを含むことを特徴とする。
【００１２】
本発明の作用について述べる。構築すべきスパニングツリーの構成ノード情報を有するスパニングツリー構築指令に応答して、通信網のトポロジ情報とリンクコスト情報とに基づいて、通信網にスパニングツリーを構築する際に、スパニングツリー構成ノードの各ノードペア間のユニキャストパスを、リンクコスト情報を用いて最短路探索アルゴリズムにより探索し、この探索により得られたパスに閉路が存在するとき、この閉路を構成するリンクのうち最もコストが高いリンクを閉鎖して、この閉鎖したリンクを通っていた全てのパスについて、閉路を迂回するようパスを設定し、こうして得られたパスにおいて各ユニキャストパスが通過するリンクで構築されるツリー構造のグラフ（すなわちトポロジ）をスパニングツリーとするものである。
【発明の効果】
【００１３】
本発明によれば、ＶＬＡＮにおけるＳＴの構築に際して、負荷分散を可能としてリンク利用率の平均化が図かれるという効果があり、またこのようなＳＴをより高い精度で求めることができ、かつ最小コストＳＴの探索が高速に実現できるという効果もある。
【発明を実施するための最良の形態】
【００１４】
次に、本発明の第１の実施の形態について、図面を参照して詳細に説明する。図１を参照すると、本発明の第１の形態は、ＶＬＡＮが設定されるべき物理ネットワークトポロジや、事前に設定されたＶＬＡＮのＳＴトポロジなど、初期条件を入力する初期条件入力手段１と、時系列で与えられるＶＬＡＮメンバ及びＶＬＡＮメンバ間のトラヒック情報で与えられるＶＬＡＮサービスのオーダを入力するＶＬＡＮサービスオーダ入力手段２と、プログラム制御により動作するデータ処理装置３と、ネットワークの状態を記憶する記憶装置４と、設計の結果を表示する設計結果表示手段５とを含む。
【００１５】
これらの手段の各々について以下に説明する。初期条件入力手段１は、ＳＴを設定するプラットフォームとしての物理トポロジや、現在までに設定されたＳＴの履歴などの情報を、使用者が記憶装置４に対して入力するためのものである。入力されるデータは、物理トポロジを構成するためのノード、リンクの位置情報などの属性を含む。
【００１６】
ＶＬＡＮサービスオーダ入力手段２は、これから新たにＳＴを設定したいＶＬＡＮの情報（ＳＴ構築指令）を入力して、使用者がデータ処理装置に入力するためのものである。ここで入力されるデータは、物理ネットワーク上のノードから選択された複数のＶＬＡＮメンバとＶＬＡＮメンバ間のトラヒック情報とを含む。
【００１７】
設計結果表示手段５は、データ処理装置３から出力される物理トポロジとＳＴトポロジ、ＳＴ設定後のリンクの帯域利用状況、リンクコストなどを表示するためのものである。記憶装置４は、物理トポロジ記憶部４１と、設計履歴記憶部４２とを備えている。物理トポロジ記憶部４１は、初期条件入力手段１から入力される物理トポロジ情報を記憶する。設計履歴記憶部４２は、現在までに設定されているＶＬＡＮに対応するＳＴのトポロジの履歴や、ＳＴ内部を流れるトラヒックを記憶し、各記憶部４１および４２は、データ処理装置の要求に応じて記憶したデータを出力する。
【００１８】
データ処理装置３は、リンク利用帯域算出手段３１と、リンクコスト算出手段３２と、最小コストＳＴ導出手段３３とを備えている。リンク利用帯域算出手段３１は、物理トポロジ記憶部４１から出力された物理トポロジ情報と、設計履歴記憶部４２から出力されるこれまでのＳＴトポロジ情報と、ＶＬＡＮ内部のトラヒック情報から、各リンクの利用帯域を算出し、その結果をリンクコスト算出手段３２へ出力する。
【００１９】
リンクコスト算出手段３２は、リンク利用帯域算出手段３１から算出された各リンクの利用帯域を基に、リンク利用帯域に関する広義の単調増加関数を用いてリンクのコストを算出、その結果を最小コストＳＴ導出手段３３へと出力する。最小コストＳＴ導出手段３３は、物理トポロジ記憶部４１から出力された物理トポロジ情報と、リンクコスト算出手段３２から出力されたリンクコストを基に、コスト最小のＳＴを導出する。その結果を設計結果表示手段５へ出力する。
【００２０】
次に、図１の機能ブロック図および図２のフローチャートを参照して本実施の形態の全体の動作について詳細に説明する。まず、初期条件として、ＳＴが設定されるべき物理トポロジ情報を入力し、物理トポロジ記憶部４１に記憶させる。物理トポロジ情報は、ＶＬＡＮメンバであるレイヤ２スイッチ（以下、ノードと称す）、ノード間を接続するリンクで与えられ、さらにそれらの接続情報や位置情報が含まれる。また、これまでに設定されたＳＴのトポロジと、そのＶＬＡＮメンバ間トラヒック情報と、そのＶＬＡＮのブロードキャストトラヒック情報とを、設計履歴記憶部４２に記憶させる（ステップ２０１）。
【００２１】
次に、ＶＬＡＮサービスオーダを入力する。ＶＬＡＮサービスオーダには、物理ネットワーク上のノードのうちのＶＬＡＮメンバとなるノードの情報が含まれ、またＶＬＡＮメンバノード間のトラヒック情報やＶＬＡＮのブロードキャストトラフィック情報が含まれる（ステップ２０２）。
【００２２】
次に、これまでに設定されたＳＴにより、現在利用されている各リンクの帯域を算出する。設計履歴記憶部４２から、これまでに設計されたＳＴのトポロジと、そのＳＴに対応するＶＬＡＮのメンバ間トラヒック情報を取り出し、そこから各リンクの利用帯域を算出する。なお、その際、ＳＴを流れるトラヒックには、ＳＴを構成する各枝で流れるトラヒックが異なるＶＬＡＮメンバ間トラヒックと、各枝で均一のトラヒックが流れるブロードキャストトラヒックが含まれることに注意する。また、算出した各リンクの利用帯域を、リンクコスト算出手段３３へと出力する（ステップ２０３）。
【００２３】
なお、リンク利用帯域（ｂｐｓ：bit per second）はリンクのトラヒック量（ｂｐｓ）に比例する量であるために、リンクのトラヒックは、すなわちリンク利用帯域とみなすことができ、よってリンク利用帯域算出手段は３１では、入力されたリンクのトラヒック情報を、リンク利用帯域として導出する機能を有する。
【００２４】
次に、リンクコスト算出手段３２において、ステップ２０３にて算出された各リンクの利用帯域から、各リンクのリンクコストを算出する。具体的には、リンクの利用帯域から、あらかじめ定められた広義の単調増加関数を用いて算出するものであり、一例として、
リンクコスト＝リンク帯域利用率＝｛（リンクの利用帯域）／（リンクの利                  用可能帯域）｝×１００（％）…（１）
なる式を用いることができる。また、算出した結果である各リンクのリンクコストを、最小コストＳＴ導出手段３３へと出力する（ステップ２０４）。
【００２５】
ここで、リンクコスト算出手段３２において、リンク利用帯域算出手段３１によって算出されるリンク利用帯域と、物理トポロジ記憶部に記憶されている各リンクの利用可能帯域だけではなく、リンクの拡大可能帯域についても考慮した関数を用いることも可能である。Ｌ２スイッチで構成されたネットワークでは、スイッチ間を接続するリンクは物理層的には仮想パスとして扱われるため、その帯域を変更することが可能である。これを用いて、Ｌ２ネットワークにおいて、リンクの帯域が拡大できる可能性があることを考慮する。
【００２６】
この場合の各リンクのリンクコストの算出方法の例としては、
リンクコスト＝［（リンクの利用帯域）／｛（リンクの利用可能帯域）
＋（リンクの拡大可能帯域）｝］×１００（％）…（２）
とする方法がある。
【００２７】
次に、最小コストＳＴ導出手段３３において、ステップ２０４で算出された各リンクのリンクコストから、最小コストとなるＳＴを決定する。この最小コストＳＴ決定手法については、図３のフローチャートに示している。図３を参照すると、先ず、ＶＬＡＮメンバペア（２ノード）間の全てのユニキャストパスを、非特許文献２のｐ．１５８−ｐ．１６２に記載の“Dijkstra”アルゴリズムによって算出する（ステップＳ１）。このアルゴリズムは、上述したように、ＶＬＡＮメンバの２ノード間における最短路を探索する最短路木探索の手法である。
【００２８】
この最短路木探索手法により得られたトポロジにおいて、閉路の有無を検出する（ステップＳ２）。閉路が検出されると（ステップＳ２の“Ｙ”）、閉路を構成するリンクのうちもっともコストが高いリンクを閉鎖する（ステップＳ３）。そして、閉鎖したリンクを通っていた全てのパスについて、閉路上を迂回するようにパスを設定する（ステップＳ４）。
【００２９】
これらステップＳ３、Ｓ４を、全ての閉路に対して適用し、閉路がなくなると（ステップＳ２の“Ｎ”）、こうして得られたパスにおいて各ユニキャストパスが通過するリンクで構築されるツリー構造のグラフを、そのＶＬＡＮのスパニングツリーとする（ステップＳ５）。そして、当該スパニングツリーに沿って流れるトラヒックを考慮して、当該スパニングツリー設定後のリンクコストを、このスパニングツリーを構成する全てのリンクに対して更新する（ステップＳ６）。
【００３０】
こうして得られたＳＴトポロジや、ＳＴ内を流れる各リンクのトラヒックなどを設計結果表示手段５へと出力する。また、設計履歴記憶部４２に対し、決定したＳＴのトポロジおよびメンバ間のトラヒック情報を出力する（ステップ２０５）。
【００３１】
次に、設計結果を表示する。設計結果表示手段５において、ステップ２０５にて出力されたＳＴのトポロジや各リンクのトラヒックを表示する（ステップ２０６）。設計履歴記憶部４２において、ステップ２０５において出力されたＳＴトポロジ情報やメンバ間のトラヒック情報などを、今回のＳＴの設計結果を設計履歴として追加記憶する（ステップ２０７）。最後に、ＶＬＡＮサービスオーダ入力受付モードに移行し、ＶＬＡＮサービスオーダの入力があるまで待機する。
【００３２】
上述した図３のフローチャートに示した動作手順に従って、図１の最小コストＳＴ導出手段３３の機能ブロックを図示すると、図４のようになる。図４において、最短路探索部３３１は、スパニングツリーの構成ノードの各ノードペア間のユニキャストパスを、リンクコスト情報を用いて最短路探索アルゴリズムにより探索するものである。パス設定部３３２は、この最短路探索部３３１により得られたパスに閉路が存在するとき、この閉路を構成するリンクのうち最もコストが高いリンクを閉鎖して、この閉鎖したリンクを通っていた全てのパスについて、当該閉路を迂回するようパスを設定するものである。
【００３３】
そして、スパニングツリー設定部３３３は、各ユニキャストパスが通過するリンクで構築されるツリー構造のグラフを新たなスパニングツリーとするものである。また、リンクコスト更新部３３４は、トラヒック（リンク利用帯域と等価）情報を用いてスパニングツリー設定後のリンクコストを、全てのリンクについて更新するものである。
【００３４】
次に、ＭＳＴの設計を実現するプログラムの実施の形態について、図５を参照して説明する。図５において、図１と同等部分は同一符号により示している。本発明のプログラムの実施の形態は、初期条件入力手段１と、ＶＬＡＮサービスオーダ入力手段２と、データ処理装置７と、記憶装置４とを備え、さらに、ＭＳＴ設計プログラムを記録した記録媒体６を備える。この記録媒体６は磁気ディスク、半導体メモリ、ＣＤ−ＲＯＭ、その他の記録媒体であっても良い。
【００３５】
ＭＳＴ設計プログラムは記録媒体６または図示せぬ電気通信回線からデータ処理装置７に読み込まれ、データ処理装置７の動作を制御し、記憶装置４に物理トポロジ記憶部４１、設計履歴記憶部４２を生成する。データ処理装置７はＭＳＴ設計プログラムの制御により上述の実施の形態におけるデータ処理装置による処理と同一の処理を実行する。
【実施例】
【００３６】
次に、本発明の実施例を図面を参照して説明する。本実施例では、パーソナルコンピュータに実装したプログラムを実行することで本発明を実施する。本実施例を実現するプログラムの動作について、以下に示す。
【００３７】
プログラムを開始すると、初期条件の入力待ち画面が表示される。本実施例における初期条件入力手段１の具体的な実現方法を、以下に示す。実行者は、物理トポロジ情報と、ＶＬＡＮ設定履歴情報を入力する。ここで、物理トポロジ情報とは、ＶＬＡＮの構成メンバであるノードとその位置情報で構成されるノード情報と、ノード間を接続するリンクの有無およびリンクの帯域情報で構成されるリンク情報とを含む。
【００３８】
また、ＶＬＡＮ設定履歴の情報は、設定されている各ＶＬＡＮのそれぞれに対して、物理トポロジ上の各ノードを選択することによって入力される各ＶＬＡＮを構成するＶＬＡＮメンバ情報と、各リンクを選択することによって入力される各ＶＬＡＮに対応するＳＴのトポロジ情報と、ＶＬＡＮメンバ間のトラヒック情報（ユニキャストとブロードキャストの各トラヒック情報）とを入力することで与えられる。この場合のトラヒック情報は、前述したように、リンク利用帯域と等価である。
【００３９】
次に、ＶＬＡＮサービスオーダの入力画面に移る。本実施例におけるＶＬＡＮサービスオーダ入力手段２の具体的な実現方法を、以下に示す。実行者は、ここでＶＬＡＮサービスオーダ情報を入力する。ＶＬＡＮサービスオーダ情報は、物理トポロジ上の各ノードを選択することによって入力される各ＶＬＡＮを構成するＶＬＡＮメンバ情報と、ＶＬＡＮメンバ間のトラヒック情報（本例では、リンク利用帯域）とを入力することで与えられる。
【００４０】
次に、本実施例を実現するプログラムの動作について、図６〜図１３に示すような例に基づいて説明する。これら各図では、Ｌ２スイッチ（以下、ノードと呼ぶ）を丸印で表し、ノード間を結ぶリンクを線で表している。ノードに記載の文字はノード名を表し、また各リンク側（そば）に記載の数字は、そのリンクの現在までの利用済み帯域（リンク利用帯域：Ｍｂｐｓ）を表す。なお、各リンクの通信容量を、説明を簡単化するために、全て１００Ｍｂｐｓとする。
【００４１】
いま、図６に示す構成例において、新たにＶＬＡＮサービスオーダ要求がきたとする。ここで、この新たなＶＬＡＮサービスにおけるＳＴの構築のために与えられるＶＬＡＮサービスオーダは、図７に示すように、ＶＬＡＮメンバを黒いノード（Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ）、ＶＬＡＮメンバ間トラヒック情報であるユニキャストトラヒックを、全てのＶＬＡＮメンバペア間（Ａ−Ｂ、Ａ−Ｃ、…、Ｇ−Ｈ）において、等しく１Ｍｂｐｓ、ブロードキャストトラヒックを０Ｍｂｐｓとする。
【００４２】
このようなＶＬＡＮサービスオーダに対して、本発明のアルゴリズムでＳＴを設計することを考える。まず、初期条件入力手段１によって入力された物理トポロジ情報が、物理トポロジ記憶部４１に記憶される。図６の構成例においては、この過程で、ノードとリンクの接続状況が物理トポロジ記憶部４１に入力されることになる。また、ＶＬＡＮ設定履歴情報が設計履歴記憶部４２に記憶される。次に、リンク利用帯域算出手段３１が、設計履歴記憶部４２が保持する設計履歴情報を基に、現在までに設定されているＳＴによって、各リンクに流れるトラヒックを算出し、各リンクのリンク利用帯域を算出する。図６の構成例においては、これまでに図８に示されている６つのＶＬＡＮが設定されており、その結果算出されたリンク利用帯域が図６や図８の最下部の各リンク側（そば）に記載してある。
【００４３】
次に、リンクコスト算出手段３２が、リンク利用帯域算出手段３１によって算出されるリンク利用帯域と、物理トポロジ記憶部に記憶されている各リンクの利用可能帯域とに基づいて、各リンクのリンクコストを算出する。リンクコストの算出方法は、リンクの帯域利用率とする。すなわち、上記の（１）式で示したように、
｛（リンクの利用帯域）／（リンクの利用可能帯域）｝×１００％
で算出される値である。ここで、上記（２）式で示したように、リンクの利用帯域とリンクの拡大可能帯域とを変数とする関数で、リンクコストを計算する方法もある。本例では、理解を用意にするために、全てのリンクの利用可能帯域が１００Ｍｂｐｓとし、よって図６〜図１３及びそれ以降の図１４〜図１９おいては、各リンク側（そば）に示されている利用帯域［Ｍｂｐｓ］が、そのままリンクコストとなる。
【００４４】
次に、最小コストＳＴ導出手段３３が、リンクコスト算出手段３２によって算出される各リンクのリンクコストに基づいて、最小コストのＳＴを導出する。ここで求めるＳＴは、以下の（ａ）、（ｂ）、（ｃ）の条件を満たす。
（ａ）ＶＬＡＮメンバを全て通過する。
（ｂ）物理トポロジ上のノードとリンクで構成され、閉路を含まない木構造である。
（ｃ）（ａ）および（ｂ）の条件を満たすもののうち、ＳＴのコストが最小である。
【００４５】
次に、前述の（ａ）、（ｂ）、（ｃ）の全ての条件を満たすＳＴの算出方法を、具体的な手順を示した図１９を参照しつつ以下に示す。まず、ＶＬＡＮのメンバの任意の２つのノードで構成されるノードペアのうち、そのノードペア間のトラヒックが０でないものに対して、それぞれ独立に経路を設計する（図１９（１））。各ノードペアの経路の設計方法は、物理トポロジと各リンクのリンクコストが与えられた際の２ノード間の最短路探索アルゴリズムである“Dijkstra”アルゴリズムを用いる（図３のステップＳ１）。ここで、最短路とは、２ノードを結ぶ経路に用いられる全てのリンクのコストが最小となるものである。
【００４６】
図６の構成例では、まずＡを始点とする“Dijkstra”アルゴリズムを実行し、図９に示すように、Ａ−Ｂ間、Ａ−Ｃ間、…、Ａ−Ｈ間の各最短路を求める。この場合、例えばＡ−Ｅ間の最短路は、Ａ−Ｉ−Ｊ−Ｅとなり、そのコストは３０となる。
【００４７】
次に、Ｂを始点として、Ｂ−Ｃ間、Ｂ−Ｄ間、…、Ｂ−Ｈ間の最短路を求める。同様に始点をＣ、Ｄ、…、Ｇまで変えて、“Dijkstra”を実行することにより、Ａ−Ｂ間、…、Ｇ−Ｈ間の最短路を求める。こうして、各ＶＬＡＮメンバペア間の最短路が求まり、その経路を重ね合わせたトポロジは、図１０のようになる。
【００４８】
以下、図１９における（２）〜（４）は、条件（ｂ）を満たすために、閉路を検出、削除するための手順である（図３のステップＳ２〜Ｓ４の繰返し）。すなわち、（２）では、閉路を検出する。（１）で設計した各経路が用いたリンクで構成されるトポロジにおいて、閉路を検出する。具体的には、物理トポロジが与えられた段階で、閉路と、閉路を構成するリンク集合（タイセット）を検出しておき、（１）で設計された結果、各経路が用いたリンクで構成されるトポロジに、タイセットが含まれるかどうかを検出する。
【００４９】
ここで、閉路とそのタイセットの検出方法は、図２０を参照しつつ以下に説明する。まず、与えられた物理トポロジ上の全てのノードのうち、ランダムにルートノードを決定する。この場合の物理トポロジは、図の左上に示すような通信網の形状のものとする。次に、未使用リンクを経由して到達可能なノードを列挙していき、木構造を構築する。それぞれの葉の部分において、通過ノードと、通過リンクをそれぞれ記憶しておく。各葉において、ノードの重複を検出、あるいは未使用リンクではどこにも到達できなくなったとき、それ以降のノードの列挙を停止し、全ての葉においてノードの列挙を停止したとき、木構造の構築が終了する。
【００５０】
このように木構造を構築したとき、ノードの重複を検出して停止した各葉において、その葉が記憶している通過ノードと通過リンクが、閉路とタイセットとなる。但し、同じ閉路とタイセットを検出する葉が複数出ることもあるため、重複しないように、物理トポロジ上の閉路候補を検出する。なお、本実施例では、物理トポロジが与えられた段階であらかじめ閉路候補を検出し、（１）の手順後に閉路ができているかをチェックするが、（１）の手順後に初めて閉路を検出する方法も考えられる。
【００５１】
（３）では、閉路を構成するタイセットのうち、最もコストの高いものを一つ選択、閉鎖する（最もコストの高いリンクが複数存在した場合、その中からランダムに一つ選択、閉鎖する）（４）では、（３）で閉鎖されたリンクを通過していた経路を持つノードペアに対して、経路を再設定する。その方法は、閉鎖した閉路に対応するタイセット上を迂回するように行う。
【００５２】
図６の構成例では、例えば図１１の上部に示すようなＤ−Ｅ−Ｊ−Ｉの閉路について、最もリンクコストの高いＤ−Ｅ間のリンクを閉鎖する（図１１の中間部）。そして、Ｄ−Ｅ間のリンクを用いていたユニキャストパスＤ−Ｅについて、その経路を、閉路Ｄ−Ｅ−Ｊ−Ｉについて迂回するように設定しなおす（図１１の下部）。
【００５３】
また、閉路削除の方法としては、以下の方法も考えられる。閉路を閉鎖した際、閉鎖したリンクを用いていたユニキャストパスの経路を“Dijkstra”アルゴリズムを用いて再探索する方法である。この再探索を行うことで、より経路の最適化を図ることがができる。一方、この再探索を行った場合、再探索した結果得られた経路が再び別の閉路を生成する可能性もあり、再々探索を行う必要が生じ、経路再設定に時間がかかることが考えられる。これに対して、先に示した方法では、再設定経路を、一意に定まる閉路上の迂回経路として決定するため、最適性は保証されないが、再探索する手間が省けるので、高速に閉路削除をなすことができる。
【００５４】
このように、検出された全ての閉路に対して、閉鎖、経路再設定を行う。その結果得られた全経路を重ね合わせたトポロジが、図１２に示すように、最終的なＳＴトポロジとなる。以上の手順の結果得られたＳＴを、コスト最小のＳＴとして採用し、その結果を設計結果表示手段５および設計履歴記憶部４２へ出力する。設計履歴記憶部４２では、今回設計されたＳＴについて、そのＶＬＡＮ設計履歴情報を追加記憶する。設計結果表示手段５では、今回設計されたＳＴについて、その結果を物理トポロジ上に重ねて図示する。
【００５５】
図６の構成例において、最終的に得られたＳＴトポロジは図１２に示されたトポロジを持つＳＴである。その後、ＶＬＡＮサービスオーダ受付状態に戻り、ＶＬＡＮサービスオーダ入力手段を用いて再びＶＬＡＮサービスオーダが入力されるまで待機する。本発明による効果は、リンク利用率の平均化という目的を実現するＳＴを、従来技術に比べより高い精度で求めることができることである。
【００５６】
これを、図６の構成例で説明する。本構成例では、本発明の手法を用いることにより最終的に得られたＳＴトポロジは、図１２に示されたトポロジとなり、各ＶＬＡＮメンバ間のユニキャストの経路は一意に定まる。例えば、ユニキャストＣ−Ｆに用いられる経路は、リンクＣ−Ｉ、Ｉ−Ｊ、Ｊ−Ｆとなる。従って、このＳＴを設定した結果、リンク利用帯域がどう変化するかが計算できる。この計算方法は以下の通りである。
【００５７】
例えば、リンクＢ−Ｉを経路の一部として利用するユニキャストは、ユニキャストＡ−Ｃ、Ａ−Ｄ、Ａ−Ｅ、Ａ−Ｆ、Ａ−Ｇ、Ａ−Ｈ、Ｂ−Ｃ、Ｂ−Ｄ、Ｂ−Ｅ、Ｂ−Ｆ、Ｂ−Ｇ、Ｂ−Ｈである．これらの１２個のユニキャストのトラヒックは全て１（Ｍｂｐｓ）であるため、図１２のＳＴが設定されることでリンクＢ−Ｉでは、１２（Ｍｂｐｓ）だけ利用帯域が増加することになる。
【００５８】
今回、ＶＬＡＮサービスオーダのうち、ブロードキャストトラヒックを０と指定したが、ＶＬＡＮサービスオーダのブロードキャストトラヒックが０ではない場合、各リンクの増加帯域はブロードキャストトラヒックを加算したものとなる。すなわち、もしもブロードキャストトラヒックが１（Ｍｂｐｓ）であれば、リンクＢ−Ｉではユニキャスト分の１２（Ｍｂｐｓ）の利用帯域増加に加え、さらに１（Ｍｂｐｓ）だけ増加し、最終的な利用帯域の増加は１３（Ｍｂｐｓ）となる。
【００５９】
このブロードキャストの計算は、ＳＴを構成する全てのリンクに対して行う。但し、ブロードキャストはＳＴを構成したリンクのみを通過するので、今回設定したＳＴに含まれなかったリンクに関しては、増加帯域は０（Ｍｂｐｓ）である。例えば、リンクＡ−Ｉは、ブロードキャストトラヒックの値がいくつであっても、図１２のＳＴの構成リンクではないため、ユニキャストトラヒックによる利用帯域の増加も、ブロードキャストトラヒックによる利用帯域の増加も共に０（Ｍｂｐｓ）である。全てのリンクのＳＴ設定後の利用帯域を示した図が図１３である。
【００６０】
ここで、本発明との比較のために、従来手法のアルゴリズムを、図１４〜図１８に示す。従来手法では、図１４に示すように、最初に物理トポロジが与えられた段階で、ランダムにいくつか（図１４の例では、３つ）の全域木を選び、初期保持木として記憶しておく。ＶＬＡＮサービスオーダが与えられた段階で、あらかじめ記憶してある初期保持木から、図１５に示すように、そのＶＬＡＮのＳＴに必要のないリンク（ＶＬＡＮメンバのみを全て収容するのに必ずしも必要ではないリンク）を削除する。本例では、図１４の初期保持木１において、リンクＡ−Ｉ、Ｈ−ＪはＶＬＡＮメンバ全てを収容するのに必要なリンクではないので、削除する。
【００６１】
こうして得られたＳＴトポロジのうち、図１６に示すように、コストが最小なものを、最適ＳＴトポロジとする。但し、前述の通り、ＳＴのコストはＳＴを構成している各リンクのリンクコストの和である。このようにして得られたＳＴトポロジは図１７に示したものになり、このＳＴを設定した後の各リンクの利用帯域は、前述の方法と同様に計算し、図１８に示した通りになる。
【００６２】
この従来手法のアルゴリズムは、図１４の過程においてランダム性を持ち、そのため実行するたびに結果（得られるＳＴトポロジ）が変わる。但し、図１７のトポロジは、従来手法のコスト計算手法ではコスト最小となる。
【００６３】
実際に、ＳＴトポロジの優劣を定める規準は、各ＳＴを設定した後のリンク利用帯域の負荷分散であり、それをＳＴ設定後の各リンクのリンク利用帯域の分散で評価すると、本発明の手法で得られた図１３の例では、各リンクの利用帯域の分散値は約２１．８７２となり、従来手法で得られた図１８の例では、各リンクの利用帯域の分散値は約６５．１２１となる。
【００６４】
ＳＴ設定後のリンク利用帯域の分散が小さいほど、各リンクに均等に負荷が割り振られていることになるので、本発明で設計したＳＴは、従来手法で得られるＳＴと比較して、リンク利用帯域の分散化という意味でより効果的であることが分かる。
【図面の簡単な説明】
【００６５】
【図１】本発明の一実施の形態によるＭＳＴ設計装置のブロック図である。
【図２】本発明の一実施の形態によるＭＳＴ設計装置の動作を示したフローチャートである。
【図３】図２のフローチャートにおける最小コストＳＴ導出ステップ２０５の詳細を示すフローチャートである。
【図４】図１の最小コストＳＴ導出手段３３の機能ブロック図である。
【図５】本発明の他の実施の形態によるＭＳＴ設計装置のブロック図である。
【図６】本発明の実施例を説明するためのＶＬＡＮトポロジの構成例を示す図である。
【図７】新たなＶＬＡＮサービスオーダの入力例である。
【図８】図６の構成例における既設ＶＬＡＮの例を示す図である。
【図９】図７に示した新たなＶＬＡＮサービスオーダの入力時における最小コストＳＴ導出処理のＶＬＡＮメンバ間最短路探索アルゴリズムの例を説明する図である。
【図１０】図９のアルゴリズムにより得られた各経路の重ね合せ図である。
【図１１】図１０における閉路の検出とその閉鎖及び迂回路を説明するための図である。
【図１２】本発明により得られたＳＴトポロジを示す図である。
【図１３】図１２のＳＴを設定した後のリンク利用率を示す図である。
【図１４】従来例によるＶＬＡＮのＳＴを生成する場合の例を説明するための図である。
【図１５】従来例によるＶＬＡＮのＳＴを生成する場合の例を説明するための図である。
【図１６】従来例によるＶＬＡＮのＳＴを生成する場合の例を説明するための図である。
【図１７】従来例の手法により得られたＳＴトポロジを示す図である。
【図１８】図１７のＳＴを設定した後のリンク利用率を示す図である。
【図１９】本発明の実施例における最小コストＳＴ導出手段３３の具体的な実現方法のアルゴリズムを示した図である。
【図２０】最小コストＳＴ導出手段３３における閉路検出アルゴリズムの具体的な実現方法を示した図である。
【符号の説明】
【００６６】
１  初期条件入力手段
２  ＶＬＡＮサービスオーダ入力手段
３  データ処理装置
４  記憶装置
５  設計結果表示手段
６  記録媒体
７  データ処理装置
３１  リンク利用帯域算出手段
３２  リンクコスト算出手段
３３  最小コストＳＴ導出手段
４１  物理トポロジ記憶部
４２  設計履歴記憶部
３３１  最短路探索部
３３２  パス設定部
３３３  スパニングツリー設定部
３３４  リンクコスト更新部
【図１】
2005086460.tif 000003
【図２】
2005086460.tif 000004
【図３】
2005086460.tif 000005
【図４】
2005086460.tif 000006
【図５】
2005086460.tif 000007
【図６】
2005086460.tif 000008
【図７】
2005086460.tif 000009
【図８】
2005086460.tif 000010
【図９】
2005086460.tif 000011
【図１０】
2005086460.tif 000012
【図１１】
2005086460.tif 000013
【図１２】
2005086460.tif 000014
【図１３】
2005086460.tif 000015
【図１４】
2005086460.tif 000016
【図１５】
2005086460.tif 000017
【図１６】
2005086460.tif 000018
【図１７】
2005086460.tif 000019
【図１８】
2005086460.tif 000020
【図１９】
2005086460.tif 000021
【図２０】
2005086460.tif 000022
【手続補正書】
【提出日】平成16年6月7日(2004.6.7)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
【非特許文献１】永田晃、上野仁、宮崎啓二、中後明、「ＭＳＴＰを用いた広域ＬＡＮサービスにおけるＶＬＡＮ設計手法の検討」（電子情報通信学会大会講演論文集  ＶＯＬ．２００２，ソサイエティ  Ｂ，４６７頁、２００２）
【非特許文献２】滝根哲哉、伊藤大雄、西尾章治郎、「岩波講座  インターネット  第５巻  ネットワーク設計理論」（岩波書店、２００１年発行、ｐ．１５８−ｐ．１６２）