(57)【要約】スパニング・ツリー構築部（１２）は、ネットワークのトポロジに基づいて複数のスパニング・ツリーを構築し、スパニング・ツリー情報格納テーブル（１３）に登録する。スパニング・ツリー選択部（１４）は、スパニング・ツリー情報格納テーブル（１３）に登録されている複数のスパニング・ツリーの中から、通信資源が最も有効に利用されるスパニング・ツリーを選択する。ノード設定部（１５）は、要求された仮想ＬＡＮと選択されたスパニング・ツリーとのマッピング情報を各ノードに設定する。
2004075486.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードが接続されたネットワークに仮想ＬＡＮを構築する装置であって、
上記ネットワークのトポロジを表すトポロジ情報を格納するトポロジ情報格納手段と、
上記トポロジ情報格納手段に格納されているトポロジ情報を参照して複数のスパニング・ツリーを構築するスパニング・ツリー構築手段と、
上記スパニング・ツリー構築手段により構築された複数のスパニング・ツリーのそれぞれを表すスパニング・ツリー情報を格納するスパニング・ツリー情報格納手段と、
上記スパング・ツリー情報格納手段に格納されているスパニング・ツリー情報により表される複数のスパニング・ツリーの中から、要求された仮想ＬＡＮに対応するスパニング・ツリーを選択するスパニング・ツリー選択手段と、
スパニング・ツリー情報格納手段に格納されているスパニング・ツリー情報、および上記スパニング・ツリー選択手段により選択されたスパニング・ツリーと上記要求された仮想ＬＡＮとの対応関係を表すマッピング情報を、上記複数のノードに設定するノード設定手段、
を有することを特徴とする仮想ＬＡＮ構築装置。
【請求項２】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記トポロジ情報格納手段に格納されているトポロジ情報に上記複数のノード間の各リンクの優先度を表すリンク優先度情報を付加するリンク優先度設定手段をさらに有し、
上記スパニング・ツリー構築手段は、上記リンク優先度情報を参照して複数のスパニング・ツリーを構築する。
【請求項３】
請求項２に記載の仮想ＬＡＮ構築装置であって、
上記リンク優先度設定手段は、ネットワーク管理者の指示に基づいて、上記各リンクに対してリンク優先度情報を付加する。
【請求項４】
請求項２に記載の仮想ＬＡＮ構築装置であって、
上記リンク優先度設定手段は、各リンクの帯域幅に基づいて、それら各リンクに対してリンク優先度情報を付加する。
【請求項５】
請求項２に記載の仮想ＬＡＮ構築装置であって、
上記リンク優先度設定手段は、各リンクの伝送遅延時間に基づいて、それら各リンクに対してリンク優先度情報を付加する。
【請求項６】
請求項２に記載の仮想ＬＡＮ構築装置であって、
上記リンク優先度設定手段は、各リンクの利用料金に基づいて、それら各リンクに対してリンク優先度情報を付加する。
【請求項７】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー構築手段は、上記複数のスパニング・ツリーを１つずつ順番に構築していく際に、各リンクがそれぞれスパニング・ツリーの一部として先に使用されている回数に応じて、次のスパニング・ツリーを構築する。
【請求項８】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー構築手段は、各リンクが少なくとも１回はいずれかのスパニング・ツリーに含まれるように上記複数のスパニング・ツリーを構築する。
【請求項９】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー構築手段は、
優先度の高いリンクを含むスパニング・ツリーを１つ構築する第１の構築手段と、
上記第１の構築手段によりスパニング・ツリーが構築された後、スパニング・ツリーを構成する要素として一度も使用されないリンクが無くなるまで１または複数のスパニング・ツリーを構築する第２の構築手段と、
上記第２の構築手段によりスパニング・ツリーが構築された後、予め決められた数に達するまで、優先度の高いリンクを含むスパニング・ツリーを構築していく第３の構築手段、
を有する。
【請求項１０】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際にトータルホップ数が最小となるスパニング・ツリーを選択する。
【請求項１１】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際に各リンクに新たに割り当てるべき帯域の和が最小となるスパニング・ツリーを選択する。
【請求項１２】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際にネットワーク全体のリンク利用率のばらつきが最小となるスパニング・ツリーを選択する。
【請求項１３】
請求項１１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー選択手段は、上記仮想ＬＡＮが要求する各リンクの帯域と各リンクに既に割り当てられている帯域との和に基づいて、上記リンク利用率を算出する。
【請求項１４】
請求項１１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー選択手段は、上記仮想ＬＡＮが要求する各リンクの帯域と各リンク上で実際に使用されている帯域との和に基づいて、上記リンク利用率を算出する。
【請求項１５】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際に仮想ＬＡＮトラヒックが流れる経路の伝送遅延時間の和が最小となるスパニング・ツリーを選択する。
【請求項１６】
請求項１に記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際に仮想ＬＡＮトラヒックが流れる経路の利用料金の和が最小となるスパニング・ツリーを選択する。
【請求項１７】
請求項１０〜１６のいずれか１つに記載の仮想ＬＡＮ構築装置であって、
上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容可能なスパニング・ツリーを選択する。
【請求項１８】
複数のノードが接続されたネットワークに仮想ＬＡＮを構築する装置であって、
上記ネットワークのトポロジに基づいて複数のスパニング・ツリーを構築するスパニング・ツリー構築手段と、
上記スパニング・ツリー構築手段により構築された複数のスパニング・ツリーが登録されるスパニング・ツリー情報格納手段と、
上記スパング・ツリー情報格納手段に登録されている複数のスパニング・ツリーの中から、要求された仮想ＬＡＮに対応するスパニング・ツリーを選択するスパニング・ツリー選択手段と、
上記スパニング・ツリー選択手段により選択されたスパニング・ツリーと上記要求された仮想ＬＡＮとの対応関係を表すマッピング情報を、上記複数のノードに設定するノード設定手段、
を有することを特徴とする仮想ＬＡＮ構築装置。
【請求項１９】
複数のノードが接続されたネットワークに仮想ＬＡＮを構築する方法であって、
上記ネットワークのトポロジに基づいて複数のスパニング・ツリーを構築し、
上記複数のスパニング・ツリーを記憶装置に登録し、
上記記憶装置に登録されている複数のスパニング・ツリーの中から、要求された仮想ＬＡＮに対応するスパニング・ツリーを選択し、
上記選択されたスパニング・ツリーと上記要求された仮想ＬＡＮとの対応関係を表すマッピング情報を、上記複数のノードに設定する、
を特徴とする仮想ＬＡＮ構築方法。
【請求項２０】
ネットワークを構成する複数のノードと、
上記ネットワークのトポロジに基づいて複数のスパニング・ツリーを構築するスパニング・ツリー構築手段と、
上記スパニング・ツリー構築手段により構築された複数のスパニング・ツリーが登録されるスパニング・ツリー情報格納手段と、
上記スパング・ツリー情報格納手段に登録されている複数のスパニング・ツリーの中から、要求された仮想ＬＡＮに対応するスパニング・ツリーを選択するスパニング・ツリー選択手段と、
上記スパニング・ツリー選択手段により選択されたスパニング・ツリーと上記要求された仮想ＬＡＮとの対応関係を表すマッピング情報を、上記複数のノードに設定するノード設定手段、
を有することを特徴とする仮想ＬＡＮサービスを提供するネットワークシステム。
【発明の詳細な説明】
【技術分野】  本発明は、仮想ＬＡＮを構築する装置および方法、並びに仮想ＬＡＮサービスを提供するネットワークシステムに係わり、特に、複数スパニング・ツリー・プロトコルを利用して仮想ＬＡＮを構築する装置および方法、並びに複数スパニング・ツリー・プロトコルを利用して仮想ＬＡＮサービスを提供するネットワークシステムに係わる。
【背景技術】    近年、ＩＥＥＥ委員会が標準化したイーサネット（登録商標）技術のギガビットクラスの実用化により、比較的広いエリアに渡ってイーサネットを利用した仮想ＬＡＮ（ＶＬＡＮ）サービスまたは仮想私設網（ＶＰＮ）を提供するサービスが注目されている。そして、このようなサービスを提供するための通信ネットワークは、一般に、多数のノード（ブリッジ・ノード）がメッシュ状に接続されることにより構築されている。
各ノードは、例えばスイッチであり、通常、複数の入出力ポートを備えている。このため、トラヒックが流れる経路が制限されないものとすると、トラヒックがループ状の経路を巡回してしまい、ネットワーク全体としてトラヒックが増加する現象が起こり得る。そして、極端な場合、トラヒックを伝送するためのフレームがループ状の経路を巡回するトラヒックによって満たされてしまい、ネットワークがその通信能力を失してしまうことがある。
従って、この種のブリッジ・ネットワークでは、リンクによるループの形成を回避する必要がある。そして、このための技術として、ＩＥＥＥ８０２．１ｄ準拠のスパニング・ツリー・プロトコル（ＳＴＰ：Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ  Ｐｒｏｔｏｃｏｌ）が知られている。
スパニング・ツリー・プロトコルでは、まず、根ノード（ｒｏｏｔ  ｎｏｄｅ）が決定され、その根ノードからツリー状にリンクを選択していくことによりスパニング・ツリーが定義される。そして、各ノードは、その定義されたスパニング・ツリーに含まれるリンク以外のリンクにトラヒックが流れることを禁止するように動作する。この動作は、例えば、各ノードにおいて、スパニング・ツリーに含まれていないリンクから受信したトラヒックを廃棄することにより実現される。そして、このような手順により、ループが形成されることが回避されている。
また、スパニング・ツリー・プロトコルは、ノード障害が発生した時に、ノード間で自律的にツリーの再構築を行う機能を有しているので、ネットワークを運用／管理するうえで大変有用であり、ブリッジ・ネットワークで広く用いられている。
ところで、ブリッジ・ネットワークを用いて仮想ＬＡＮサービスを提供する場合、サービスを受けるユーザのトラヒックは、ユーザを収容するノード間を、スパニング・ツリー・プロトコルによって設定されたツリーに沿って流れることになる。ところが、スパニング・ツリー・プロトコルでは、ネットワーク中で全く使用されないリンクが存在することがある。そして、このことは、ネットワークを運用するうえで有益ではなく、スパニング・ツリー・プロトコルの改善すべき問題点である。
ＩＥＥＥ８０２．１ｓでは、スパニング・ツリー・プロトコルの改良型プロトコルとして、複数スパニング・ツリー・プロトコル（ＭＳＴＰ：Ｍｕｌｔｉｐｌｅ  ＳＴＰ）が標準化されている。ここで、複数スパニング・ツリー・プロトコルは、与えられたネットワークに対して互いに異なる複数のツリーを設定し、且つこれらを同時に運用することを可能にするプロトコルである。そして、このプロトコルを利用すれば、ネットワークリソースの有効利用を図ることができると考えられている。ただし、複数スパニング・ツリー・プロトコルによるツリーの構築方法の詳細については、ＩＥＥＥの規定外であり、その具体的な手法は、まだ決定されていない。
また、仮想ＬＡＮトラヒックの流れる経路（仮想ＬＡＮトポロジ）は、スパニング・ツリーに沿ってユニークに決定される。このため、スパニング・ツリーが１つしか設定されないネットワークにおいては、ネットワーク管理者が仮想ＬＡＮトポロジを設計する必要は無い。しかし、複数スパニング・ツリー・プロトコルが動作するネットワークでは、複数のツリーが設定され得るので、互いに異なる複数の仮想ＬＡＮトポロジが存在し得ることになる。したがって、ネットワーク管理者は、どのような構造のツリーに仮想ＬＡＮトラヒックを収容するか、すなわち仮想ＬＡＮトポロジをどのように設計するかを決定する必要がある。
ネットワーク資源が有効に利用されるように仮想ＬＡＮトポロジを設計するためには、例えば、下記（１）〜（４）の手順でスパニング・ツリーの構築および仮想ＬＡＮトポロジの設計を行えばよいと考えられる。
（１）リンク毎に所定の通信パラメータに基づくコストを定義する。ここで、リンクのコストは、その通信パラメータに対して正の相関を持つ単調増加関数とする。
（２）与えられた仮想ＬＡＮのユーザ収容ノードを最小コストで結ぶサブ・ツリーを構築し、これを仮想ＬＡＮトポロジとする。
（３）上記（２）で得られた仮想ＬＡＮトポロジに従ってスパニング・ツリーを構築する。
（４）上記（３）で得られたスパニング・ツリーに、与えられた仮想ＬＡＮトラヒックを収容する。
上記（１）のコストを定義するための情報は、例えば、ネットワーク管理者によりキーボード等を利用して設定される。ただし、ネットワーク上にネットワークの運用に係わる統計情報を収集する装置を設け、その装置から各ノードに必要な情報が設定されるような形態も考えられる。この形態は、例えば、特定のノードが統計情報を収集し、各ノードに設定情報を返すことにより実現可能である。
上記（２）の手順は、ネットワーク内の一部のノードを結ぶサブ・ツリーを求めるスタイナー・ツリー問題であり、実時間で解く方法が存在しないので、ヒューリスティックな手法を用いて検索される。
最小コストのサブ・ツリーを検索する方法としては、例えば、スタイナー・ツリー問題のヒューリスティック解法として広く用いられている、Ｒａｙｗａｒｄ−Ｓｍｉｔｈ法（以下、ＲＳ法）を用いることができる。ＲＳ法では、まず、求めるサブ・ツリーに含まれるべきノード（この場合、ユーザを収容する２個以上のノード）からなる複数の単一ノードツリーの集合を用意する。次に、各単一ノードツリーの集合に含まれているノード以外のノード（中継ノードと呼ぶ）を１つずつ選択してゆき、これらを経由して単一ノードツリー同士を結ぶことにより１つのツリーを構築する。そして、全ての単一ノードツリーの集合が１つのツリーに含まれたら検索処理を終了する。ここで、選択される中継ノードには、ツリーに追加される際にリンクコストの増加が最小となるノードが選ばれる。すなわち、各ユーザ収容ノードと中継ノードとの間のリンクコストの和をユーザ収容ノード数で割った値が最小となるノードが選ばれる。この結果、最小コストのサブ・ツリーを発見することができる。
ＲＳ法によりユーザ収容ノードを含む最小コストのサブ・ツリー（仮想ＬＡＮトポロジ）を得たら、仮想ＬＡＮトポロジに含まれていない残りのノードを、上記（２）の仮想ＬＡＮトポロジに追加する際にコストの増加が小さいものから順に上記仮想ＬＡＮトポロジに１つずつ加えていく。このとき、閉路が形成されないことを前提とする。ここで、この手順は、例えば、Ｊ．Ｂ．ＫｒｕｓｋａｌのアルゴリズムやＲ．Ｓ．Ｐｒｉｍのアルゴリズムにより実現される。そして、全てのノードがツリーに含まれたら、これをスパニング・ツリーとする。
以上の手順により得られたスパニング・ツリーに仮想ＬＡＮを収容することにより、ネットワーク資源の有効利用を図ることができる。
なお、複数スパニング・ツリー・プロトコルについては、非特許文献１に詳しく記載されている。ただし、このプロトコルは、新しい技術であり、現時点で公開されている特許文献は発見されなかった。また、ＲＳ法については、非特許文献２に記載されている。
【非特許文献１】  ＩＥＥＥ  Ｐ８０２．１ｓ／Ｄ１５「Ｍｕｌｔｉｐｌｅ  Ｓｐａｎｎｉｎｇ  Ｔｒｅｅｓ」
【非特許文献２】  ＩＥＥＥ  ＪＯＵＲＮＡＬ  ＯＮ  ＳＥＬＥＣＥＤ  ＡＲＥＡＳ  ＩＮ  ＣＯＭＭＵＮＩＣＡＴＩＯＮＳ  Ｖｏｌ．６  Ｎｏ．９  Ｄｅｃｅｍｂｅｒ  １９８８  ｐ．１７１７−１６２２“Ｒｏｕｔｉｎｇ  ｏｆ  Ｍｕｌｔｉｐｏｉｎｔ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ”（Ｂｅｒｎａｒｄ  Ｍ．Ｗａｘｍａｎ）
ところが、上述の手法で仮想ＬＡＮトポロジの設計を行った場合、ＲＳ法による最小コストのサブ・ツリーの探索は、ネットワーク内の全ノード数に対するサブ・ツリーに含まれるノード数の割合が大きくなるほど、その探索計算時間が指数関数的に増加することが知られている。このため、ユーザから仮想ＬＡＮの構築の要求を受けたときにこの検索処理を行うと、仮想ＬＡＮサービスの提供を開始するまでに要する時間が非常に大きくなり、ユーザを収容するノード数が多いときはネットワークが不安定になる。また、スパニング・ツリーは、必要な情報がノードに設定されてからサービスの運用が可能になるまでに数秒〜数１０秒程度を要するため、仮想ＬＡＮユーザ個々に新規にスパニング・ツリーを設定すると、サービス提供の開始までにさらに待ち時間が発生する。
さらに、ＲＳ法による探索では、最小コストサブ・ツリーを探索することはできるが、任意のｎ番目にコストの小さいサブ・ツリーを探索することは不可能である。このため、ＲＳ法でスパニング・ツリーを検索する方法では、経路上のリンクの空き帯域が不足しているために要求された仮想ＬＡＮサービスを収容できなかった場合に、通信資源が有効に利用されるような代替の仮想ＬＡＮトポロジおよび／またはスパンニグ・ツリーを設計することができない。
【発明の開示】
本発明の目的は、複数スパニング・ツリー・プロトコルを利用するネットワークにおいて、仮想ＬＡＮサービスの提供の開始までに要する時間を短縮することである。また、本発明の他の目的は、複数スパニング・ツリー・プロトコルを利用するネットワークにおいて、通信資源の有効利用を図ることである。
本発明の仮想ＬＡＮ構築装置は、複数のノードが接続されたネットワークに仮想ＬＡＮを構築する装置であって、上記ネットワークのトポロジを表すトポロジ情報を格納するトポロジ情報格納手段と、上記トポロジ情報格納手段に格納されているトポロジ情報を参照して複数のスパニング・ツリーを構築するスパニング・ツリー構築手段と、上記スパニング・ツリー構築手段により構築された複数のスパニング・ツリーのそれぞれを表すスパニング・ツリー情報を格納するスパニング・ツリー情報格納手段と、上記スパング・ツリー情報格納手段に格納されているスパニング・ツリー情報により表される複数のスパニング・ツリーの中から要求された仮想ＬＡＮに対応するスパニング・ツリーを選択するスパニング・ツリー選択手段と、スパニング・ツリー情報格納手段に格納されているスパニング・ツリー情報および上記スパニング・ツリー選択手段により選択されたスパニング・ツリーと上記要求された仮想ＬＡＮとの対応関係を表すマッピング情報を上記複数のノードに設定するノード設定手段、を有する。
この発明においては、予め複数のスパニング・ツリーが用意される。そして、仮想ＬＡＮオーダを受け付けると、上記複数のスパニング・ツリーの中から１つスパニング・ツリーが選択され、そのツリー上に仮想ＬＡＮが収容される。このため、仮想ＬＡＮオーダを受け付ける毎に新たにスパニング・ツリーを構築する必要が無く、仮想ＬＡＮの設計に要する時間、および実際に仮想ＬＡＮサービスを提供できるようになるまでの時間が短縮される。
上記仮想ＬＡＮ構築装置において、上記トポロジ情報格納手段に格納されているトポロジ情報に上記複数のノード間の各リンクの優先度を表すリンク優先度情報を付加するリンク優先度設定手段をさらに有し、上記スパニング・ツリー構築手段が、上記リンク優先度情報を参照して複数のスパニング・ツリーを構築するようにしてもよい。この発明によれば、各リンクの優先度に応じたスパニング・ツリーが使用されるので、各リンクの優先度に応じた仮想ＬＡＮを提供することができる。
上記リンク優先度設定手段は、ネットワーク管理者の指示に基づいて、上記各リンクに対してリンク優先度情報を付加するようにしてもよい。この場合、ネットワーク管理者により指定されたリンクに優先的に仮想ＬＡＮトラヒックを収容することが可能となる。
また、上記リンク優先度設定手段は、各リンクの帯域幅に基づいて、それら各リンクに対してリンク優先度情報を付加するようにしてもよい。この場合、帯域幅の大きいリンクの優先度を高くすれば、帯域幅の大きいリンクを優先的に利用してスパニング・ツリーが構築されるので、仮想ＬＡＮトラヒックが帯域幅の大きいリンクに優先的に収容されることになり、特定のリンクが帯域不足になることが回避される。
なお、伝送遅延時間の小さいリンクの優先度の高くすれば、エンド−エンドの伝送遅延時間を低く抑えた仮想ＬＡＮを提供できる。また、利用料金の安いリンクの優先度の高くすれば、仮想ＬＡＮサービス提供者は、安価なリソース利用料金で仮想ＬＡＮサービスを提供できる。
上記スパニング・ツリー構築手段は、各リンクが少なくとも１回はいずれかのスパニング・ツリーに含まれるように上記複数のスパニング・ツリーを構築するようにしてもよい。この場合、全く使用される可能性のないリンクが存在しなくなるので、通信資源の無駄が少なくなる。
上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際にトータルホップ数が最小となるスパニング・ツリーを選択するようにしてもよい。この場合、仮想ＬＡＮトラヒックを流すリンクの数が少なくなるので、ネットワーク全体でトラヒック量を減らすことができ、限られた通信資源により多くの仮想ＬＡＮを収容できるようになる。また、仮想ＬＡＮごとに管理する情報（リンクの数）が減るので、仮想ＬＡＮサービス提供者が用いるシステムに必要なメモリ量を減らすことができ、システムを安価に構築できる。
また、上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際に各リンクに新たに割り当てるべき帯域の和が最小となるスパニング・ツリーを選択するようにしてもよい。この場合も、同様に、ネットワーク全体でトラヒック量を減らすことができる。また、仮想ＬＡＮの帯域サービスとして、フルメッシュ接続、スター接続など様々な形態が想定されるが、この発明によれば、帯域サービスの内容を考慮してスパニング・ツリーが選択されるので、ユーザの要求に好適な仮想ＬＡＮを提供できる。
さらに、上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際にネットワーク全体のリンク利用率のばらつきが最小となるスパニング・ツリーを選択するようにしてもよい。この場合、ネットワークを流れるトラヒック量が均一化されるので、局所的な帯域不足により特定のノード間を接続する仮想ＬＡＮを収容できないという事態が回避される。すなわち、限られた通信資源でより多くの仮想ＬＡＮを収容できる。
なお、収容すべき仮想ＬＡＮか要求する帯域と各リンクに既に割り当てられている帯域との和に基づいて、上記リンク利用率を算出するようにしてもよい。この場合、各仮想ＬＡＮサービスの要求帯域の累積値によりリンク利用率を求めることができるので、定期的なリンク情報の収集が必要なくなり、運用が容易となる。あるいは、収容すべき仮想ＬＡＮが要求する帯域と各リンク上で実際に使用されている帯域との和に基づいて、上記リンク利用率を算出するようにしてもよい。この場合、実際には使用されていない帯域を他の仮想ＬＡＮに割り当てることができるので、帯域非保証型トラヒック（ベストエフォート型サービスのトラヒック）を効率的に収容できる。
さらに、上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際に仮想ＬＡＮトラヒックが流れる経路の伝送遅延時間の和が最小となるスパニング・ツリーを選択するようにしてもよい。この場合、選択可能なスパニング・ツリーの中から、各仮想ＬＡＮを最小の伝送遅延で収容できるスパニング・ツリーが選択される。すなわち、音声や動画像などの遅延に厳しいアプリケーションを使うユーザを収容できる。
さらに、上記スパニング・ツリー選択手段は、要求された仮想ＬＡＮを収容した際に仮想ＬＡＮトラヒックが流れる経路の利用料金の和が最小となるスパニング・ツリーを選択するようにしてもよい。この場合、運用コストを抑えられるため、例えば、他社の回線を借りてサービス提供している事業者にとって経済面で有効である。
【図面の簡単な説明】  図１は、本発明の実施形態のネットワーク構成図である。
図２は、ネットワーク管理システムの構成図である。
図３は、トポロジ情報格納テーブルの例である。
図４は、スパニング・ツリー情報格納テーブルの構成を示す図である。
図５は、更新されたスパニング・ツリー情報格納テーブルの例（その１）である。
図６は、構築されたスパニング・ツリーの例である。
図７は、更新されたスパニング・ツリー情報格納テーブルの例（その２）である。
図８は、更新されたスパニング・ツリー情報格納テーブルの例（その３）である。
図９は、各ノードに設定される情報（スパニング・ツリーの設定）の例である。
図１０は、各ノードに設定される情報（仮想ＬＡＮの設定を含む）の例である。
図１１は、本発明の仮想ＬＡＮ構築方法の概略手順を示すフローチャートである。
図１２は、スパニング・ツリー構築部の基本動作を示すフローチャートである。
図１３は、スパニング・ツリー選択部の基本動作を示すフローチャートである。
図１４は、ノード設定部の基本動作を示すフローチャートである。
図１５は、第１の実施例におけるトポロジ情報格納テーブルの構成を示す図である。
図１６は、各リンクの優先度を決定する処理を説明する図である。
図１７は、優先度の高いリンクを利用してスパニング・ツリーを構築する手順を説明する図である。
図１８は、優先度の高いリンクを利用してスパニング・ツリーを構築する際に使用されるテーブルの例である。
図１９は、第１の実施例におけるスパニング・ツリー構築部の動作の要部を示すフローチャートである。
図２０〜図２３は、それぞれ、優先度設定部の動作を示すフローチャートである。
図２４は、リンク選択回数を参照して複数のスパニング・ツリーを構築する手順を説明する図である。
図２５は、リンク選択回数を考慮して構築されたスパニング・ツリーの例である。
図２６は、第２の実施例におけるスパニング・ツリー構築部の動作の要部を示すフローチャートである。
図２７は、第３の実施例におけるトポロジ情報格納テーブルの例である。
図２８は、ホップ数管理テーブルの例である。
図２９は、スパニング・ツリー情報格納テーブルの例である。
図３０は、予め構築されているスパニング・ツリーの例である。
図３１は、増加帯域管理テーブルの例である。
図３２は、第４の実施例においてスパニング・ツリーを選択する動作を説明するための図である。
図３３は、ばらつき管理テーブルの例である。
図３４は、リンク利用率のばらつきについて説明する図である。
図３５は、第３〜第５の実施例におけるスパニング・ツリー選択部の動作を示すフローチャートである。
図３６および図３７は、それぞれ、図３５に示すフローチャートの要部を説明する図である。
図３８および図３９は、それぞれ、シミュレーションの結果を説明する図である。
図４０は、ネットワーク管理システムとして動作するコンピュータのハードウェア構成図である。
【発明を実施するための最良の形態】  以下、本発明の実施形態について説明する。
図１は、本発明の実施形態のネットワーク構成図である。ここでは、複数のブリッジ・ノード（ノードＡ、ノードＢ、ノードＣ、ノードＤ）、それら複数のブリッジ・ノード間を接続するリンク、およびネットワーク管理システム１が描かれている。なお、図１では、説明を簡単にするために、４台のノードを有するネットワークが描かれているが、ノードの数は特に限定されるものではない。
各ノードは、例えば、スイッチであり、複数スパニング・ツリー・プロトコル（ＭＳＴＰ：Ｍｕｌｔｉｐｌｅ  Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ  Ｐｒｏｔｏｃｏｌ）をサポートしている。また、各ノードは、それぞれ、複数の入出力ポートを備えている。さらに、各ノードは、ネットワーク管理システム１からの指示に従って入出力ポートの開／閉を制御する機能を備えている。
ノード間は、通信回線（リンク）により接続されている。図１では、ノードＡのポート１とノードＢのポート１とを接続するリンク、ノードＡのポート２とノードＣのポート１とを接続するリンク、ノードＡのポート３とノードＤのポート１とを接続するリンク、ノードＢのポート２とノードＣのポート２とを接続するリンク、及びノードＣのポート３とノードＤのポート２とを接続するリンクが設けられている。そして、これらのノードおよびリンクにより、ブリッジ・ネットワークが構成されている。
ネットワーク管理システム１は、１台または複数台のコンピュータにより実現され、上述のブリッジ・ネットワーク上に仮想ＬＡＮを構築する機能を備えている。すなわち、ネットワーク管理システム１は、仮想ＬＡＮ構築装置として動作する。また、ネットワーク管理システム１は、公知の技術であるＤＣＮ（Ｄａｔａ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｎｅｔｗｏｒｋ）を利用して、各ノードを制御するための情報を送信する機能を備えている。即ち、ネットワーク管理システム１は、ＤＣＮを介して、Ｔｅｌｎｅｔにより、各ノードへ統計情報を収集するためのコマンドや各種制御コマンドを送信することができる。なお、ネットワーク管理システム１は、図１においてはノードＡのみに接続されているが、ノードＡ〜ノードＤにそれぞれ接続されていてもよい。また、ネットワーク管理システム１と各ノードとの間の通信方式は、特に限定されるものではない。
図２は、ネットワーク管理システム１の構成図である。ただし、図２では、仮想ＬＡＮ構築装置として動作する部分の機能ブロックのみが描かれている。
トポロジ情報格納テーブル１１は、図１に示すネットワークのトポロジを表すトポロジ情報を格納する。ここで、トポロジ情報は、例えば、ネットワーク管理者により入力される。あるいは、ネットワーク管理システム１から各ノードに対してネットワークのトポロジを調べるためのメッセージを送信し、そのメッセージに対する各ノードからの応答に基づいてトポロジ情報が収集されるようにしてもよい。
スパニング・ツリー構築部１２は、トポロジ情報格納テーブル１１に格納されているトポロジ情報を参照して複数のスパニング・ツリーを構築する。スパニング・ツリー情報格納テーブル１３は、スパニング・ツリー構築部１２により構築された複数のスパニング・ツリーのそれぞれを表すスパニング・ツリー情報を格納する。すなわち、スパニング・ツリー情報格納テーブル１３には、複数のスパニング・ツリーが登録される。
スパニング・ツリー選択部１４は、スパニング・ツリー情報格納テーブル１３に格納されているスパニング・ツリー情報により表される複数のスパニング・ツリーの中から、ユーザからの仮想ＬＡＮオーダに対応するスパニング・ツリーを選択する。ここで、仮想ＬＡＮオーダは、ユーザにより要求される仮想ＬＡＮを表す情報であって、そのユーザを収容するノードを識別する情報、および帯域（あるいは、トラヒック量）を表す情報などを含む。
ノード設定部１５は、スパニング・ツリー情報格納テーブル１３に格納されているスパニング・ツリー情報、およびスパニング・ツリー選択部１４により選択されたスパニング・ツリーと仮想ＬＡＮオーダにより要求された仮想ＬＡＮとの対応関係を表すマッピング情報を、ノードＡ〜ノードＤに設定する。
優先度設定部１６は、トポロジ情報格納テーブル１１に格納されているトポロジ情報に、ノード間の各リンクの優先度を表すリンク優先度情報を付加する。ここで、リンク優先度情報は、例えば、ネットワーク管理者により入力される。あるいは、各リンクの帯域幅、各リンクの伝送遅延時間、各リンクの利用料金に基づいてリンク優先度情報が生成されるようにしてもよい。
図３は、トポロジ情報格納テーブル１１の例である。ここでは、図１に示すブリッジ・ネットワークのトポロジを表すトポロジ情報が格納されている。たとえば、第１行目の記述は、ノードＡがノードＢに接続されており、その間のリンクのコストが「１０」であることを表している。なお、「コスト」とは、各リンクの重みを表すパラメータであり、例えば、各リンクの通信帯域により決められる。この場合、通信帯域が大きいほど、コストが小さくなるものとする。
図４は、スパニング・ツリー情報格納テーブル１３の構成を示す図である。ここで、スパニング・ツリー情報格納テーブル１３は、図４（ａ）に示すスパニング・ツリーテーブル、および図４（ｂ）に示す根ノード管理テーブルを含む。
スパニング・ツリーテーブルには、各スパニング・ツリーを識別するスパニング・ツリー識別子（ＭＳＴＩＤ）、および各スパニング・ツリーに属するノードの接続関係を表す情報が登録される。一方、根ノード管理テーブルは、複数のスパニング・ツリーを順番に構築していく際に、構築すべきスパニング・ツリーの根ノードを管理するために使用される。
次に、スパニング・ツリーを構築する手順を説明する。なお、ここでは、図１に示すブリッジ・ネットワークにおいて複数のスパニング・ツリーを構築するものとする。
スパニング・ツリー構築部１２は、まず、トポロジ情報格納テーブル１１を参照し、根ノードを決定する。複数のノードの中から根ノードを決定する方法は、特に限定されるものではなく、例えば、ランダムに選択される。ここでは、ノードＡが根ノードとして選択されたものとする。この場合、根ノード管理テーブルは、図５（ｂ）に示すように設定される。なお、「優先度＝１」は、根ノードとして選択されたことを表す。また、根ノード以外のノードには、「優先度＝１０」が付与される。
次に、スパニング・ツリー構築部１２は、図３に示すトポロジ情報格納テーブル１１および図５（ｂ）に示す根ノード管理テーブルを参照し、ノードＡを根ノードとするスパニング・ツリーを１つ構築する。ここで、スパニング・ツリーの構築は、例えば、公知の技術であるＩＥＥＥ８０２．１Ｄに記載の方法（ダイクストラアルゴリズム）により実現される。そして、この結果、図６（ａ）に示すスパニング・ツリーが構築される。すなわち、ノードＢ−Ｃ間のリンク、およびノードＣ−Ｄ間のリンクがＤｉｓａｂｌｅ（使用禁止）状態となっているスパニング・ツリーが構築される。そうすると、スパニング・ツリーテーブルには、図５（ａ）に示す情報が登録される。なお、この情報は、「ＭＳＴＩＤ＝１」により識別されるスパニング・ツリーが、ノードＡ−Ｂ間のリンク、ノードＡ−Ｄ間のリンク、ノードＡ−Ｃ間のリンクを含んでいることを表している。
なお、Ｄｉｓａｂｌｅ状態のリンクには、対応するトラヒックが流れないことが望ましい。ところが実際は、スパニング・ツリーに含まれていないリンク（以下、Ｄｉｓａｂｌｅリンク）の上流側のノードからそのリンクを介してフレームが送出されることがある。そして、この場合、そのＤｉｓａｂｌｅリンクの下流側のノードがそのフレームを廃棄することで、ループが形成されることを回避している。このように、Ｄｉｓａｂｌａｅリンクは、何らかのトラヒックが流れる場合であっても、そのトラヒックがさらに転送されることはないので、「有効に利用されていないリンク」となる。ただし、ＩＥＥＥ８０２．１Ｑにおいて規定されているＧＶＲＰプロトコルを利用すれば、スパニング・ツリーに含まれていないリンクを介してトラヒックを送信することを停止できる。
続いて、スパニング・ツリー構築部１２は、新たな根ノードを選択する。ここでは、根ノードとしてノードＢが選択され、根ノード管理テーブルが図７（ｂ）に示す状態に更新されたものとする。この場合、スパニング・ツリー構築部１２は、この根ノードに対応する新たなスパニング・ツリーを１つ構築する。この結果、図６（ｂ）に示すスパニング・ツリーが構築される。すなわち、ノードＡ−Ｃ間のリンク、およびノードＣ−Ｄ間のリンクがＤｉｓａｂｌｅ（使用禁止）状態となっているスパニング・ツリーが構築される。そうすると、スパニング・ツリーテーブルには、図７（ａ）に示す情報が登録される。なお、この情報は、「ＭＳＴＩＤ＝２」により識別されるスパニング・ツリーが、ノードＡ−Ｂ間のリンク、ノードＢ−Ｃ間のリンク、ノードＡ−Ｄ間のリンクを含んでいることを表している。
さらに、スパニング・ツリー構築部１２は、次の根ノードを選択する。ここでは、根ノードとしてノードＤが選択され、根ノード管理テーブルが図８に示す状態に更新されたものとする。そして、スパニング・ツリー構築部１２は、この根ノードに対応する新たなスパニング・ツリーを１つ構築する。しかし、上述の条件でスパニング・ツリーを構築すると、結果として、図６（ａ）に示したスパニング・ツリーが得られることになる。よって、この場合、新たに構築したスパニング・ツリーは、スパニング・ツリーテーブルには登録されない。
なお、新たに構築されたスパニング・ツリーと先に構築されているスパニング・ツリーとが一致しているか否かは、各スパニング・ツリーに含まれているリンクを互いに比較することにより判断してもよいし、Ｄｉｓａｂｌｅ状態のリンクを互いに比較することにより判断してもよい。
また、形状の異なるスパニング・ツリーを得る方法としては、根ノードをランダムに選ぶ方法を挙げているが、他には、例えば、新たなスパニング・ツリーを構築するごとにそのスパニング・ツリーに含まれることとなったリンクのコストを一定値（例えば、１）ずつ増加させる、という方法もある。
以下、同様に、スパニング・ツリーを１つずつ構築していく。そして、スパニング・ツリー構築部１２は、予め決められた数のスパニング・ツリーが構築されたとき、あるいは、スパニング・ツリーを構築する処理を所定回数（例えば、５０回）繰り返してもスパニング・ツリーテーブルが更新されなかったとき、に処理を停止する。
このように、スパニング・ツリー構築部１２は、複数のスパニング・ツリーを構築し、それらを表すスパニング・ツリー情報をスパニング・ツリー情報格納テーブル１３に格納する。これにより、スパニング・ツリー情報格納テーブル１３には、互いに異なる複数のスパニング・ツリーが登録されることになる。
上述のようにして複数のスパニング・ツリーが構築されると、ノード設定部１５は、それら複数のスパニング・ツリーを表す情報を各ノードＡ〜ノードＤに設定する。具体的は、ノード設定部１５は、各入出力ポートのコストを設定する。この場合、例えば、各スパニング・ツリーごとに、スパニング・ツリーに含まれているリンクが接続するノードの該当ポートのコストとして「１」が設定され、他のリンクが接続されているノードの該当ポートのコストとして「６５５３５」が設定される。また、ノード設定部１５は、各ノードのフォワーディングデータベース（Ｆｏｒｗａｒｄｉｎｇ  ＤＢ）に格納されるフォワーディング識別子（ＦＩＤ）と、スパニング・ツリー識別子（ＭＳＴＩＤ）とのマッピングのための情報を設定する。なお、ＦＩＤとＭＳＴＩＤとのマッピングについては、ＩＥＥＥ８０２．１ｓに記載されている。
図９は、各ノードＡ〜ノードＤに設定される情報の例である。ここでは、図７（ａ）に示すスパニング・ツリーテーブルに従って対応する情報が設定された状態を示している。すなわち、各ノードには、図６（ａ）に示すスパニング・ツリーおよび図６（ｂ）に示すスパニング・ツリーを表す情報が設定されている。
例えば、図６（ａ）に示すスパニング・ツリーでは、ノードＡのポート１とノードＢのポート１との間のリンクが使用されている。従って、図９において、ノードＡのポート１は、スパニング・ツリー１として使用されるときは「コスト＝１」となっている。同様に、ノードＢのポート１も、スパニング・ツリー１として使用されるときは「コスト＝１」となっている。
一方、図６（ａ）に示すスパニング・ツリーでは、ノードＢのポート２とノードＣのポート２との間のリンクは使用されていない。従って、図９において、ノードＢのポート２は、スパニング・ツリー１として使用されるときは「コスト＝６５５３５」となっている。同様に、ノードＣのポート２も、スパニング・ツリー１として使用されるときは「コスト＝６５５３５」となっている。
また、各ノードにおいて、フォワーディング識別子（ＦＩＤ）と、スパニング・ツリー識別子（ＭＳＴＩＤ）との対応関係が登録されている。ここでは、「ＦＩＤ＝１」と「ＭＳＴＩＤ＝１」とが対応しており、「ＦＩＤ＝２」と「ＭＳＴＩＤ＝２」とが対応している旨が登録されている。
上述の設定が終了すると、ネットワーク管理システム１は、仮想ＬＡＮオーダの入力を待ち受ける。ここで、仮想ＬＡＮオーダとは、例えば、仮想ＬＡＮサービスを受けようとするユーザを収容するノードを指定する情報、およびユーザが各ノード間で使用したい帯域を申告する情報を含む。そして、ネットワーク管理システム１に仮想ＬＡＮオーダが入力されると、スパニング・ツリー選択部１４は、スパニング・ツリー情報格納テーブル１３に登録されている複数のスパニング・ツリーの中から、仮想ＬＡＮオーダにより要求された仮想ＬＡＮを収容するためのスパニング・ツリーを１つ選択する。なお、スパニング・ツリーを選択する方法は、後で詳しく説明するが、ここでは特に限定しないものとし、例えば、ランダムに選ばれるものとする。
ここで、仮想ＬＡＮオーダにより、ユーザ収容ノードとしてノードＢおよびノードＣが指定されたものとする。また、スパニング・ツリー選択部１４により、その仮想ＬＡＮを収容するスパニング・ツリーとして、「ＭＳＴＩＤ＝２」により識別されるのスパニング・ツリー（すなわち、図６（ｂ）に示すスパニング・ツリー）が選択されたとものする。この場合、ノード設定部１５は、選択されたスパニング・ツリーを用いて仮想ＬＡＮを収容するための情報を対応するノードに設定する。具体的には、ノードＢおよびノードＣにおいて、フォワーディング識別子ＦＩＤとスパニング・ツリー識別子ＭＳＴＩＤとの対応テーブルを参照し、仮想ＬＡＮ識別子ＶＬＡＮＩＤとスパニング・ツリー識別子ＭＳＴＩＤとのマッピングを行う。この例では、「ＭＳＴＩＤ＝２」により識別されるのスパニング・ツリーが選択されているので、まず、スパニング・ツリー識別子ＭＳＴＩＤに対応するフォワーディング識別子ＦＩＤとして「ＦＩＤ＝２」が検出される。そして、この検出されたフォワーディング識別子ＦＩＤに対して、仮想ＬＡＮオーダにより要求された仮想ＬＡＮが割り当てられる。なお、図１０において、仮想ＬＡＮオーダにより要求された仮想ＬＡＮが「ＶＬＡＮＩＤ＝１」により表されている。したがって、仮想ＬＡＮオーダにより要求された仮想ＬＡＮ（ＶＬＡＮＩＤ＝１）は、ノードＢおよびノードＣにおいて、フォワーディング識別子（ＦＩＤ＝２）を介して、「ＭＳＴＩＤ＝２」により識別されるのスパニング・ツリーにマッピングされる。
上記設定が終了すると、以降、このユーザのトラヒック（即ち、「ＶＬＡＮＩＤ＝１」により識別される仮想ＬＡＮのトラヒック）は、「ＭＳＴＩＤ＝２」により識別されるのスパニング・ツリーのみを介して転送されることになる。なお、複数スパニング・ツリー・プロトコルでは、ツリーに含まれないＤｉｓａｂｌｅリンクを介して仮想ＬＡＮトラヒックが送信されることがあり、そのリンクの送信端で輻輳が発生するおそれがある。ただし、各ノードは、ＧＶＲＰなどの既存のプロトコルにより、Ｄｉｓａｂｌｅリンクへのトラヒックの送信を止めることは可能である。
上述の設定が行われたノードＢ、Ｃは、例えば、以下のように動作する。ただし、ここでは、やや正確性を欠くが、説明を簡単にするために、「コスト＝１」が設定されているポートは使用が許可されており、「コスト＝６５５３５」が設定されているポートは使用が禁止されているものとする。また、各ノードは、「コスト＝６５５３５」が設定されているポートに接続するリンク（すなわち、Ｄｉｓａｂｌｅリンク）へのデータの送信を止めることができるものとする。
ノードＢ、Ｃは、加入者線を介して仮想ＬＡＮデータフレームを受信すると、そのフレームに付与されている仮想ＬＡＮ識別子を参照する。このとき、このフレームの仮想ＬＡＮ識別子として「ＶＬＡＮＩＤ＝１」が付与されていたものとする。この場合、ノードＢ、Ｃは、この仮想ＬＡＮ識別子に対応するフォワーディング識別子（ＦＩＤ＝２）を取得し、さらにそのフォワーディング識別子に対応するスパニング・ツリー識別子（ＭＳＴＩＤ＝２）を取得する。ここで、例えばノードＣにおいて、「ＭＳＴＩＤ＝２」により識別されるスパニング・ツリーが使用される場合には、ポート１、３の使用が禁止されており、ポート２のみの使用が許可されている。したがって、ノードＣは、ポート２を介してノードＢに上記仮想ＬＡＮデータフレームを送信することはできるが、そのフレームをポート１、３を介してノードＡ、Ｄに送信することはできない。すなわち、仮想ＬＡＮデータフレームは、図６（ｂ）に示すスパニング・ツリー上のみの転送が許可される。
また、何らかの理由により、ノードＣが、ポート１を介して「ＶＬＡＮＩＤ＝１」により識別される仮想ＬＡＮデータフレームを受信したものとする。この場合、ノードＣは、上述のケースと同様に、そのポート１の使用が禁止されていることを認識する。そうすると、ノードＣは、受信したフレームを廃棄する。このように、各ノードは、対応するスパニング・ツリーに含まれていないリンクを介して仮想ＬＡＮデータフレームを受信すると、そのフレームを廃棄する。
そして、これらの動作により、ブリッジ・ネットワーク上にループ状の経路が形成されることが回避される。
図１１は、本発明の実施形態の仮想ＬＡＮ構築方法の概略手順を示すフローチャートである。
ステップＳ１では、まず、ブリッジ・ネットワークのトポロジを表すトポロジ情報がトポロジ情報格納テーブル１１に格納される。なお、トポロジ情報は、例えば、ネットワーク管理者から与えられるものとする。
ステップＳ２では、スパニング・ツリー構築部１２により複数のスパニング・ツリーが構築される。そして、これらのスパニング・ツリーを表すスパニング・ツリー情報は、スパニング・ツリー情報格納テーブル１３に格納される。すなわち、複数のスパニング・ツリーがスパニング・ツリー情報格納テーブル１３に登録される。
ステップＳ３では、ノード設定部１５により、スパニング・ツリー情報格納テーブル１３に登録されている複数のスパニング・ツリーが、ノードＡ〜ノードＤに設定される。
ステップＳ４及びＳ５では、仮想ＬＡＮオーダの入力を待ち受ける。そして、仮想ＬＡＮオーダが入力されると、ステップＳ６において、スパニング・ツリー情報格納テーブル１３に登録されている複数のスパニング・ツリーの中から、１つのスパニング・ツリーが選択される。そして、ステップＳ７において、ステップＳ６で選択したスパニング・ツリーが要求された仮想ＬＡＮを収容できるか否かを調べる。なお、これらの処理は、スパニング・ツリー選択部１４により実行される。
選択したスパニング・ツリーが仮想ＬＡＮを収容できるときは、ステップＳ８において、そのスパニング・ツリーと仮想ＬＡＮとの対応関係を表すマッピング情報を、対応するノードに設定する。一方、選択したスパニング・ツリーが仮想ＬＡＮを収容でききないときは、その旨をユーザに通知した後、ステップＳ４に戻る。なお、ネットワーク管理システム１は、動作を停止すべき旨の指示（ステップＳ９）が入力されるまでは、仮想ＬＡＮオーダを受け付けるモードで待機する。
このように、実施形態の仮想ＬＡＮ構築方法においては、予め複数のスパニング・ツリーが構築されて登録されている。そして、仮想ＬＡＮオーダが入力されると、その登録されている複数のスパニング・ツリーの中から１つのスパニング・ツリーが選択されて使用される。したがって、仮想ＬＡＮオーダが入力されてから、サービスの提供の開始までに要する時間が短い。
図１２は、スパニング・ツリー構築部１２の基本動作を示すフローチャートである。なお、このフローチャートは、図１１に示すステップＳ２の処理を詳細に示すものである。
ステップＳ１１では、トポロジ情報格納テーブル１１からトポロジ情報を取得する。ステップＳ１２では、複数のスパニング・ツリーを構築する際に使用される変数である「構築数」および「再現回数」を初期化する。なお、「構築数」は、ステップＳ１２の処理を実行することにより構築される互いに異なるスパニング・ツリーの数を表す。また、「再現回数」は、過去に構築されたスパニング・ツリーと同じスパニング・ツリーが繰り返し構築された回数を表す。
ステップＳ１３では、根ノードを選択する。なお、根ノードを選択する方法は、特に限定されるものではない。例えば、常に一番小さいノードＩＤを持つノードを選んでもよいし、すべてのノードを順番で選ぶようにしてもよいし、ランダムに選ぶようにしてもよい。ステップＳ１４では、ステップＳ１３で選択された根ノードに対応するスパニング・ツリーを１つ構築する。なお、スパニング・ツリーを構築する方法は、例えば公知の技術により実現することができる。
ステップＳ１５では、新たに構築したスパニング・ツリーが、過去に構築したスパニング・ツリーのいずれかと同じであるか否かを調べる。そして、新たに構築したスパニング・ツリーが過去に構築したいずれのスパニング・ツリーとも異なっていた場合には、ステップＳ１６において「再現数」をクリアする。また、ステップＳ１７では、新たに構築したスパニング・ツリーをスパニング・ツリー情報格納テーブル１３に登録する。さらに、ステップＳ１８において「構築数」をインクリメントする。
ステップＳ１９では、「構築数」が予め決められている目標数に達したか否かを調べる。そして、「構築数」が目標数に達していれば処理を終了し、そうでなければ、ステップＳ１３に戻って次のスパニング・ツリーを構築する。
新たに構築したスパニング・ツリーが過去に構築したスパニング・ツリーのいずれかと同じであった場合は、ステップＳ２０において、「再現回数」をインクリメントする。続いて、ステップＳ２１において、その「再現回数」が予め決められている閾値を越えたか否かを調べる。そして、「再現回数」がその閾値を越えていれば処理を終了し、そうでない場合は、ステップＳ１３に戻って次のスパニング・ツリーを構築する。
このように、スパニング・ツリー構築部１２は、所定数の互いに異なるスパニング・ツリーを構築する。ただし、所定数の互いに異なるスパニング・ツリーを構築できない場合であっても、同じスパニング・ツリーが繰り返し構築されてしまう場合は、その処理を終了する。そして、このようにして構築された互いに異なる複数のスパニング・ツリーは、スパニング・ツリー情報格納テーブル１３に登録される。
図１３は、スパニング・ツリー選択部１４の基本動作を示すフローチャートである。なお、このフローチャートは、図１１に示すステップＳ６およびＳ７の処理を詳細に示すものである。
ステップＳ３１では、トポロジ情報格納テーブル１１からトポロジ情報を取得する。ステップＳ３２では、スパニング・ツリー情報格納テーブル１３からスパニング・ツリー情報を取得する。
ステップＳ３３では、スパニング・ツリー情報格納テーブル１３に登録されている複数のスパニング・ツリーの中から１つのスパニング・ツリーを選択する。なお、スパニング・ツリーを選択する方法は、ここでは、特に限定されるものではない。例えば、スパニング・ツリー情報格納テーブル１３にエントリされている順に選択してもよいし、ランダムに選択してもよい。
ステップＳ３４およびＳ３５では、選択したスパニング・ツリー上にユーザから要求された仮想ＬＡＮを収容できるか否かを、そのスパニング・ツリーに含まれる各リンクについて調べる。具体的には、例えば、その仮想ＬＡＮを収容したと仮定した場合に、各仮想ＬＡＮに割り当てられる使用帯域の和が各リンクの帯域を越えるか否かを調べる。例えば、あるリンクの帯域が１００Ｍであり、そのうちの９０Ｍが既に他の仮想ＬＡＮに割り当てられている場合を想定する。この場合、ユーザから要求された仮想ＬＡＮの使用帯域が１０Ｍを越えていれば、その仮想ＬＡＮを収容できないことになる。
要求された仮想ＬＡＮを収容できる場合は、ステップＳ３６において、仮想ＬＡＮオーダに対応するサービスを提供するために、その仮想ＬＡＮを識別するための仮想ＬＡＮ識別子ＶＬＡＮＩＤおよびステップＳ３３で選択したスパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤを出力する。
一方、要求された仮想ＬＡＮを収容できない場合は、ステップＳ３７を介してステップＳ３３に戻り、次のスパニング・ツリーを選択する。ただし、スパニング・ツリー情報格納テーブルに登録されているいずれのスパニング・ツリー上にも要求された仮想ＬＡＮを収容できない場合には、ステップＳ３８において、要求された仮想ＬＡＮサービスを提供できない旨のメッセージを出力する。
このように、スパニング・ツリー選択部１４は、予め用意されている複数のスパニング・ツリーの中から、要求された仮想ＬＡＮを収容できるスパニング・ツリーを選択する。
図１４は、ノード設定部１５の基本動作を示すフローチャートである。なお、このフローチャートは、図１１に示すステップＳ３およびＳ８の処理を詳細に示すものである。
ステップＳ４１では、当該ノード設定部１５の呼出し元を調べる。そして、スパニング・ツリー構築部１２から呼び出されたのであれば、ステップＳ４２〜Ｓ４３の処理が実行され、スパニング・ツリー選択部１４から呼び出されたのであれば、ステップＳ４４の処理が実行される。
ステップＳ４２では、スパニング・ツリー情報格納テーブル１２に格納されている複数のスパニング・ツリーを表すスパニング・ツリー情報を取得する。ここで、スパニング・ツリー情報格納テーブル１２には、スパニング・ツリー毎に、各ノードにおいて各入出力ポートの「通過／ブロック」を表す情報が格納されている。ステップＳ４３では、各ノードに対して、各スパニング・ツリーを表す情報を設定する。例えば、通過ポートには、「ポートコスト＝１」が設定され、ブロックすべきポートには「コートコスト＝６５５３５」が設定される。
一方、ステップＳ４４では、各ノードに対して、仮想ＬＡＮ識別子ＶＬＡＮＩＤとスパニング・ツリー識別子ＭＳＴＩＤとのマッピング情報を設定する。ここで、このマッピング情報は、図１３に示すステップＳ３６で生成されたものである。
このように、ノード設定部１５は、仮想ＬＡＮを構築するために必要な情報を各ノードに設定する。このとき、ノード設定部１５から各ノードへの情報は、例えば、ＤＣＮを介して伝送される。
次に、本発明の実施例について説明する。
＜第１の実施例＞
第１の実施例のネットワーク管理システム１は、ノード間の各リンクに優先度を付与する優先度設定部１６を備える。ここで、優先度設定部１６は、例えば、ネットワーク管理者からの指示に従って各リンクの優先度を設定する。そして、スパニング・ツリー構築部１２は、そのリンク優先度を参照して複数のスパニング・ツリーを構築する。
図１５は、第１の実施例におけるトポロジ情報格納テーブル１１の構成を示す図である。図１５において、「パラメータ」としては、例えば、各リンクの帯域幅、伝送遅延時間、利用料金などが格納される。また、「優先度フラグ」としては、優先度設定部１６により優先度に係わるパラメータが格納される。
ネットワーク管理システム１が起動されると、優先度設定部１６は、図１５に示すトポロジ情報格納テーブル１１において、各リンクの優先度フラグを決定する。優先度フラグとしては、例えば、優先度の高いリンクに対して「１」が付与され、そうでないリンクに対して「０」が付与される。
各リンクの優先度は、例えば、ネットワーク管理者により指定される。あるいは、各リンク毎に設定されている「パラメータ」に基づいて優先度が決定されるようにしてもよい。この場合、閾値として「パラメータ」の平均値を算出し、各リンクの「パラメータ」とその平均値とを比較することによって各リンクの優先度を決定するようにしてもよい。例えば、各リンクのパラメータとして帯域幅が設定されている場合は、この帯域幅の平均値よりも大きな帯域幅を持つリンクに対して高い優先度（優先度フラグ＝１）が付与される。また、各リンクのパラメータとして伝送遅延時間または利用料金が設定されている場合は、これらの平均値を下回る伝送遅延時間または利用料金を持つリンクに対して高い優先度が付与される。
一例を示す。ここでは、トポロジ情報格納テーブル１１において図１６（ａ）に示す「パラメータ」が設定されているものとする。なお、「優先度フラグ」は、優先度設定部１６により書き込まれるものであり、この時点では、まだ何も書き込まれていない。「パラメータ」としては、各リンクの帯域幅がＭｂｐｓ単位で設定されている。この状態では、優先度設定部１６は、各リンクのパラメータの平均値を算出し、「平均帯域幅＝４．４Ｍｂｐｓ」を得る。ここで、この平均帯域幅と各リンクの帯域幅とを比較すると、ノードＡ−Ｂ間のリンク、ノードＡ−Ｃ間のリンク、およびノードＢ−Ｃ間のリンクの各帯域幅がそれぞれ平均帯域幅よりも大きくなっている。よって、これらの３つのリンクに対して「優先度フラグ＝１」が付与され、他のリンクに対して「優先度フラグ＝０」付与される。この結果、トポロジ情報格納テーブル１１は、図１６（ｂ）に示すように更新される。このようにして各リンクの優先度フラグを決定した後、優先度設定部１６の処理は終了する。
上述のようにして各リンクの優先度が決定されると、スパニング・ツリー構築部１２は、それらのリンク優先度を参照して複数のスパニング・ツリーを構築する。
すなわち、スパニング・ツリー構築部１２は、まず、図１６（ｂ）に示すトポロジ情報格納テーブル１１を読み込み、「優先度フラグ＝１」が付与されているリンク、およびそれらのリンクの両端に位置するノードを抽出する。なお、以下では、このようにして抽出されたリンクおよびノードを要素とする集合を「集合Ａ」と呼ぶことにする。ちなみに、集合Ａにより形成されるネットワークのトポロジは、図１７（ａ）に示す通りである。また、集合Ａのトポロジ情報は、図１８（ａ）に示す通りである。
続いて、スパニング・ツリー構築部１２は、集合Ａに属するノードの中から根ノードを１つ選択する。なお、根ノードは、例えば、ランダムに選択される。そして、この根ノードを基準として、集合Ａの中でスパニング・ツリーを構築する。ここで、図１７（ｂ）に示すように、根ノードとしてノードＡが選択されたものとする。そして、このノードＡを基準として集合Ａの中でスパニング・ツリーを構築すると、図１７（ｂ）に示すツリーが得られる。このとき、このスパニング・ツリーを表す情報は、図１７（ｃ）に示す通りである。なお、複数のノードが接続されたネットワークにおいてスパニング・ツリーを構築すること自体は、公知の技術である。
さらに、スパニング・ツリー構築部１２は、集合Ａの中で構築されたスパニング・ツリーに、集合Ａに含まれていない各ノードを追加する。このとき、追加すべきノードは、それぞれ、最もコストの小さいリンクを利用してスパニング・ツリーに接続される。例えば、図１７（ｂ）に示すスパニング・ツリーにノードＤを追加するケースを考える。ここで、ノードＤは、物理的には、図１に示すように、ノードＡおよびノードＣの双方に接続している。ところが、図１７（ｃ）に示すように、ノードＡ−Ｄ間のリンクのコストが「１０」であるのに対し、ノードＣ−Ｄ間のリンクのコストは「３０」である。したがって、この場合、ノードＤは、ノードＡに接続されることによりスパニング・ツリーに追加される。そして、この結果、図１７（ｄ）に示すスパニング・ツリーが得られる。また、このスパニング・ツリーを表す情報は、図１８（ｃ）に示す通りであり、スパニング・ツリー情報格納テーブル１３に格納される。この手順は、例えば、ＰｒｉｍアルゴリズムやＫｒｕｓｋａｌアルゴリズムにより実現される。
なお、集合Ａを抽出した際に、その集合Ａに属する要素だけでスパニング・ツリーを構築することができない場合、すなわち、集合Ａに属する複数のノードの中から根ノードを選択して集合Ａ内でダイクストラアルゴリズム等を適用したときに、その集合Ａの中に到達できないノードが存在する場合がある。このような構造は、非連結構造と呼ばれることがある。この場合、スパニング・ツリー構築部１２は、まず、集合Ａ内の互いに連結していない要素同士を、集合Ａに含まれないノードおよびリンクを補って互いに連結させる。そして、集合Ａの中でスパニング・ツリーを構築する。この手順は、例えば、根ノードを含むスパニング・ツリーとそのツリーに連結されていない集合Ａ内のノードとを、トポロジ全体を対象としたダイクストラアルゴリズム等で得られる最小コスト経路で接続する処理を、根ノードを含むツリーと連結していないノードが存在しなくなるまでこれを繰り返し、その結果得られるツリーを集合Ａとすることで実現される。なお、このようにして集合Ａを得た後の手順は、前述のとおりである。
スパニング・ツリー構築部１２は、上記手順を繰り返すことにより、複数のスパニング・ツリーを構築する。ここで、スパニング・ツリー構築部１２の処理は、予め指定された数のスパニング・ツリーが構築されたとき、或いは、スパニング・ツリーを構築する処理を所定回数（例えば、５０回）繰り返しても先に構築したスパニング・ツリーと異なるスパニング・ツリーが構築出来なかったときに停止する。
なお、仮想ＬＡＮオーダに応じて複数のスパニング・ツリーの中から１つのスパニング・ツリーを選択する処理、および選択したスパニング・ツリーと要求された仮想ＬＡＮとのマッピング情報を各ノードに設定する処理は、上述した通りである。
このように、第１の実施例では、各リンクの優先度に基づいて複数のスパニング・ツリーが構築され、それらの中から選択されたスパニング・ツリー上に仮想ＬＡＮが収容される。したがって、各リンクの優先度がネットワーク管理者により指定されるものとすると、ネットワーク管理者が所望するリンクを利用して仮想ＬＡＮトラヒックを収容することができる。また、帯域幅に基づいて各リンクの優先度が決められるとすると、通信資源の有効利用が図れる。さらに、伝送遅延時間、利用料金に基づいて各リンクの優先度が決められるとすると、伝送遅延の小さい仮想ＬＡＮ、利用料金の低い仮想ＬＡＮが実現される。
図１９は、第１の実施例におけるスパニング・ツリー構築部１２の動作の要部を示すフローチャートである。なお、このフローチャートの処理は、図１２に示したスパニング・ツリー構築部１２の基本動作におけるステップＳ１３およびＳ１４に相当する。また、第１の実施例におけるスパニング・ツリー構築部１２の他の動作は、図１２に従う。
ステップＳ５１では、トポロジ情報格納テーブル１１において優先度フラグが「１（ＯＮ）」であるリンク、およびそのリンクの両端に接続するノードを抽出する。ステップＳ５２では、抽出した複数のノードの中から根ノードを１つ選択する。ステップＳ５３では、抽出したリンクおよびノードから構成されるトポロジが連結構造であるか否かを調べる。
上記トポロジが連結構造であれば、ステップＳ５４において、抽出したリンクおよびノードを利用してスパニング・ツリーを構築する。以下、ステップＳ５４で構築されたスパニング・ツリーを「ＳＴ１」と呼ぶ。そして、全てのノードがスパニング・ツリーＳＴ１に含まれるようになるまで、ステップＳ５５およびＳ５６の処理を繰り返し実行する。
ステップＳ５５では、スパニング・ツリーＳＴ１に含まれていないノードの中で、そのスパニング・ツリーＳＴ１からのコストが最小のノードを選択する。ステップＳ５６では、スパニング・ツリーＳＴ１に、ステップＳ５５で選択したノードおよびそのノードとスパニング・ツリーＳＴ１とを接続するリンクを追加する。
上記トポロジが連結構造でなかった場合は、ステップＳ６１〜Ｓ６５を実行することにより、ステップＳ５１で抽出された各ノードが連結された状態を生成する。即ち、ステップＳ６１では、根ノードを含むスパニング・ツリー（以下、部分ツリー）に含まれていないノードを１つ選択する。ステップＳ６２では、その選択したノードをソースノードとしてダイクストラ（ｄｉｊｋｓｔｒａ）計算を行う。ステップＳ６３では、部分ツリーに含まれる各ノードへのダイクストラルートの中で、最短のルートを検出する。ステップＳ６４では、当該ノード、選択したダイクストラルート上のノード、および選択したダイクストラルートを構成するリンクを部分ツリーに加える。ステップＳ６５は、ステップＳ５１で抽出されたノードのすべてが部分ツリーに含まれるようになるまで、ステップＳ６１〜Ｓ６４を繰り返すために設けられている。
このように、第１の実施例におけるスパニング・ツリー構築手段は、優先度の高いリンクを使ったスパニング・ツリーを構築する。
図２０は、優先度設定部１６の動作を示すフローチャート（その１）である。ステップＳ７１では、トポロジ情報格納テーブル１１を参照する。ステップＳ７２では、ネットワーク管理者からの入力を待ち受ける。ここで、ネットワーク管理者は、全リンクの中から１または複数の優先度の高いリンクを指定するものとする。
続いて、トポロジ情報格納テーブル１１に登録されている各リンクに対してステップＳ７３〜Ｓ７５の処理を行う。ステップＳ７３では、当該リンクが、ネットワーク管理者により指定されたリンクであるか否かを調べる。そして、ネットワーク管理者により指定されたリンクであれば、ステップＳ７４において、そのリンクの優先度フラグとして「１（ＯＮ）」を付与する。一方、そうでなかった場合は、ステップＳ７５において、そのリンクの優先度フラグとして「０（ＯＦＦ）」を付与する。そして、ステップＳ７６では、ステップＳ７３〜Ｓ７５による結果に従って、トポロジ情報格納テーブル１１を更新する。
このように、優先度設定部１６は、このフローチャートの動作を行う場合は、ネットワーク管理者の指示に従って各リンクの優先度を設定する。
図２１は、優先度設定部１６の動作を示すフローチャート（その２）である。なお、このフローチャートの動作は、トポロジ情報格納テーブル１１において各リンクの帯域が設定されていることを前提とする。また、このフローチャートの動作は、図２０に示した動作と基本的には同じであるが、図２０のステップＳ７２、Ｓ７３の代わりに、ステップＳ８１、Ｓ８２が実行される。
ステップＳ８１では、各リンクの帯域の平均値を算出する。また、ステップＳ８２では、各リンクの帯域が、それぞれ、平均帯域よりも大きいか否かを調べる。そして、平均帯域よりも大きな帯域を持つリンクに対して「優先度フラグ＝１（ＯＮ）」が付与され、他のリンクに対して「優先度フラグ＝０（ＯＦＦ）」が付与される。
このように、優先度設定部１６は、このフローチャートの動作を行う場合は、各リンクの帯域に基づいてリンク優先度を設定する。
図２２は、優先度設定部１６の動作を示すフローチャート（その３）である。なお、このフローチャートの動作は、トポロジ情報格納テーブル１１において各リンクの伝送遅延時間が設定されていることを前提とする。また、このフローチャートの動作は、図２０に示した動作と基本的には同じであるが、図２０のステップＳ７２、Ｓ７３の代わりに、ステップＳ８３、Ｓ８４が実行される。
ステップＳ８３では、各リンクの伝送遅延時間の平均値を算出する。また、ステップＳ８４では、各リンクの伝送遅延時間が、それぞれ、平均伝送遅延時間よりも大きいか否かを調べる。そして、平均伝送遅延時間よりも小さい伝送遅延時間を持つリンクに対して「優先度フラグ＝１（ＯＮ）」が付与され、他のリンクに対して「優先度フラグ＝０（ＯＦＦ）」が付与される。
このように、優先度設定部１６は、このフローチャートの動作を行う場合は、各リンクの伝送遅延時間に基づいてリンク優先度を設定する。
図２３は、優先度設定部１６の動作を示すフローチャート（その４）である。なお、このフローチャートの動作は、トポロジ情報格納テーブル１１において各リンクの利用料金が設定されていることを前提とする。また、このフローチャートの動作は、図２０に示した動作と基本的には同じであるが、図２０のステップＳ７２、Ｓ７３の代わりに、ステップＳ８５、Ｓ８６が実行される。
ステップＳ８３では、各リンクの利用料金の平均値を算出する。また、ステップＳ８４では、各リンクの利用料金が、それぞれ、平均利用料金よりも高いか否かを調べる。そして、平均利用料金よりも低い利用料金のリンクに対して「優先度フラグ＝１（ＯＮ）」が付与され、他のリンクに対して「優先度フラグ＝０（ＯＦＦ）」が付与される。
このように、優先度設定部１６は、このフローチャートの動作を行う場合は、各リンクの利用料金に基づいてリンク優先度を設定する。
＜第２の実施例＞
第２の実施例のネットワーク管理システム１が備えるスパニング・ツリー構築部１２は、複数のスパニング・ツリーを構築する際に、各リンクがそれぞれスパニング・ツリーを構築するために使用された回数を考慮する。
図２４（ａ）は、第２の実施例におけるトポロジ情報格納テーブル１１の構成を示す図である。ここでは、各リンクの「パラメータ」としてそれぞれ帯域幅が格納されており、このパラメータに基づいて各リンクの「優先度フラグ」が決定されているものとする。なお、「優先度フラグ」は、例えば、第１の実施例で説明した優先度設定部１６により設定される。また、第２の実施例におけるトポロジ情報格納テーブル１１は、各リンクがそれぞれスパニング・ツリーを構築するために選択された回数を表す「リンク選択回数」を管理する。
スパニング・ツリー構築部１２は、複数のスパニング・ツリーを構築する際にトポロジ情報格納テーブル１１を参照する。このとき、スパニング・ツリー構築部１２は、リンク優先度を参照しつつ、いずれのスパニング・ツリーにも含まれないリンクが存在しないように複数のスパニング・ツリーを構築する。即ち、全てのリンクが少なくとも１回はいずれかスパニング・ツリーに含まれるように複数のスパニング・ツリーが構築される。そして、この構築処理は、例えば、下記の手順により実現される。
第１番目のスパニング・ツリー（すなわち、「ＭＳＴＩＤ＝１」により識別されるスパニング・ツリー）を構築するときは、第１の実施例と同様に、「優先度フラグ＝１」が付与されているリンク、およびそのリンクの両端に接続されているノードが優先的に使用される。そして、この結果、第１の実施例と同様にして図１７（ｄ）に示すスパニング・ツリーが構築されると、トポロジ情報格納テーブル１１において、そのスパニング・ツリーに含まれるリンク（すなわち、ノードＡ−Ｂ間のリンク、ノードＡ−Ｃ間のリンク、およびノードＡ−Ｄ間のリンク）の「リンク選択回数」がインクリメントされる。この結果、トポロジ情報格納テーブル１１は、図２４（ｂ）に示す状態に更新される。なお、この動作を「フェーズ１」と呼ぶことにする。
次に、第２番目のスパニング・ツリー（すなわち、「ＭＳＴＩＤ＝２」により識別されるスパニング・ツリー）を構築するときは、図２４（ｂ）に示すトポロジ情報格納テーブル１１の「リンク選択回数」を参照する。具体的には、トポロジ情報格納テーブル１１から「リンク選択回数＝０」である各リンク、およびそれら各リンクの両端に接続されているノードを抽出する。そして、これらのリンクおよびノードを要素とする集合Ａを定義し、第１の実施例と同様に、その集合Ａに基づいてスパニング・ツリーを構築する。この結果、図２５に示すスパニング・ツリーが構築されると、トポロジ情報格納テーブル１１において、そのスパニング・ツリーに含まれるリンク（すなわち、ノードＡ−Ｄ間のリンク、ノードＢ−Ｃ間のリンク、およびノードＣ−Ｄ間のリンク）の「リンク選択回数」がインクリメントされる。この結果、トポロジ情報格納テーブル１１は、図２４（ｃ）に示す状態に更新される。なお、この動作を「フェーズ２」と呼ぶことにする。そして、フェーズ２は、トポロジ情報格納テーブル１１に登録されているすべてのリンクの「リンク選択回数」が１以上になるまで繰り返し実行される。
続いて、フェーズ３に移る。フェーズ３では、フェーズ１と同じ手順を繰り返すことにより、複数のスパニング・ツリーを構築する。このとき、先の構築したスパニング・ツリーと同じスパニング・ツリーが構築されたときは、トポロジ情報格納テーブル１１の「リンク選択回数」は更新されない。そして、予め決められた互いに異なる所定数のスパニング・ツリーが構築されたとき、或いは、所定回数（例えば、５０回）繰り返しても新たなスパニング・ツリーが構築されなかったときは、フェーズ３を終了する。
なお、仮想ＬＡＮオーダに応じて複数のスパニング・ツリーの中から１つのスパニング・ツリーを選択する処理、および選択したスパニング・ツリーと要求された仮想ＬＡＮとのマッピング情報を各ノードに設定する処理は、上述した通りである。
このように、第２の実施例においては、複数のスパニング・ツリーを構築する際に、リンク優先度が考慮されながら、各リンクが少なくとも１回はいずれかのスパニング・ツリーに含まれることになる。すなわち、スパニング・ツリーの要素として選択されないリンクが存在しなくなるので、ネットワークが偏って利用されることが回避される。
図２６は、第２の実施例におけるスパニング・ツリー構築部１２の動作の要部を示すフローチャートである。なお、このフローチャートの処理は、図１２に示したスパニング・ツリー構築部の基本動作におけるステップＳ１３およびＳ１４に相当する。そして、第２の実施例におけるスパニング・ツリー構築部１２の他の動作は、図１２に従う。また、ステップＳ５２〜Ｓ５６、Ｓ６１〜Ｓ６５の処理は、第１の実施例において図１９を参照しながら説明した通りである。
ステップＳ９１では、構築すべきスパニング・ツリーが第１番目のスパニング・ツリーであるか否かを調べる。そして、第１番目のスパニング・ツリーを構築する場合は、ステップＳ９２において、「優先度フラグ＝１（ＯＮ）」が付与されている各リンク、およびそれらのリンクの両端に接続されているノードを抽出する。以降の動作は、第１の実施例と同じである。
第２番目以降のスパニング・ツリーを構築する場合は、ステップＳ９３において、トポロジ情報格納テーブル１１において「リンク選択回数＝０」であるリンクが存在するか否かを調べる。そして、「リンク選択回数＝０」であるリンクが存在する場合は、ステップＳ９４において、それらの「リンク選択回数＝０」であるリンク、およびそれらのリンクの両端に接続されているノードを抽出する。以降の動作は、第１の実施例と同じである。一方、第２番目以降のスパニング・ツリーを構築する際に、「リンク選択回数＝０」であるリンクが存在しない場合は、ステップＳ９２が実行される。
このように、第２の実施例では、各リンクは、少なくとも１回はいずれかのスパニング・ツリーに含まれることになる。
＜第３の実施例＞
第３の実施例では、予め構築されている複数のスパニング・ツリーの中から要求された仮想ＬＡＮを収容すべきスパニング・ツリーを選択する際に、その仮想ＬＡＮを収容したときに経路上のリンク数が最小となるスパニング・ツリーが選択される。すなわち、仮想ＬＡＮトラヒックが流れる経路のトータルホップ数が最小になるスパニング・ツリーが選択される。
図２７は、第３の実施例におけるトポロジ情報格納テーブル１１の例である。ここで、「帯域幅」は、リンクの帯域幅を表す。また、「使用中帯域」は、現在実際に使用されている帯域幅、または仮想ＬＡＮに対して既に割り当てられている帯域幅である。例えば、このテーブルの１行目のレコードは、ノードＡ−Ｂ間のリンクのコストが「１０」であり、帯域幅が「５」であり、使用中帯域が「０．５」であることを表している。なお、「帯域幅」および「使用中帯域」の単位は、例えば、Ｍｂｐｓである。
「使用中帯域」は、例えば、新たな仮想ＬＡＮが収容されたとき、および先に収容されていた仮想ＬＡＮが削除されるときに、ネットワーク管理者により更新される。或いは、ネットワークの使用状態を動的にモニタする装置を用意し、その装置により収集される情報が書き込まれるようにしてもよい。
次に、第３の実施例において、予め構築されている複数のスパニング・ツリーの中から１つのスパニング・ツリーを選択する処理を説明する。
スパニング・ツリー選択部１４は、図２８（ａ）に示すホップ数管理テーブルを用意する。ここで、このテーブルは、スパニング・ツリーを用いて仮想ＬＡＮを収容したときのホップ数を管理する。
また、スパニング・ツリー選択部１４は、スパニング・ツリー情報格納テーブル１３に登録されている各スパニング・ツリーについて、図２７に示すトポロジ情報格納テーブル１１を参照して、それぞれ、要求された仮想ＬＡＮを収容できるか否かを調べる。この収容の可否は、例えば、選択したスパニング・ツリー上に要求された仮想ＬＡＮオーダを収容したと仮定した場合に使用されるリンクについて、各リンクの「使用中帯域」に「要求された帯域」を加えた合計帯域がそのリンクの「帯域幅」を超えるか否かを調べることにより判定される。このとき、この合計帯域が「帯域幅」を超えていなければ収容可能と判定され、超えていれば収容不可能と判定される。そして、要求された仮想ＬＡＮを収容可能と判定されたときは、このスパニング・ツリー上で仮想ＬＡＮトラヒックの流れるリンクの数を「総ホップ（Ｔｏｔａｌ  Ｈｏｐ）数」としてホップ数管理テーブルに書き込む。なお、要求された仮想ＬＡＮを収容できないときは、ホップ数管理テーブルは更新されない。
スパニング・ツリー選択部１４は、上述のようにして、スパニング・ツリー情報格納テーブル１３に登録されている全てのスパニング・ツリーに対して「総ホップ数」を求める。そして、「総ホップ数」が最小のスパニング・ツリーを、要求された仮想ＬＡＮを収容すべきスパニング・ツリーとして選択する。
なお、スパニング・ツリー情報格納テーブル１３に登録されている全てのスパニング・ツリーに対して上記処理を行ったにもかかわらず、ホップ数管理テーブルのエントリが空であったときは、要求された仮想ＬＡＮを収容可能なスパニング・ツリーが存在しないものとみなし、その旨を表すメッセージ（例えば、ネットワーク管理者宛てのエラーメッセージ）を出力する。
一例を示す。ここでは、スパニング・ツリー情報格納テーブル１３に、図２９に示すスパニング・ツリー情報が格納されているものとする。すなわち、図３０に示す３つのスパニング・ツリーが構築されているものとする。また、ユーザが要求する仮想ＬＡＮオーダは、ユーザを収容するノードを指示する情報、および要求帯域を表す情報を含む。そして、以下の例では、仮想ＬＡＮを要求したユーザが３地点に拠点を有しており、それぞれノードＢ、Ｃ、Ｄに収容されているものとする。また、このユーザは、ノードＢ、Ｃ、Ｄを結ぶ経路上で「帯域＝０．５（Ｍｂｐｓ）」を要求しているものとする。なお、要求帯域は、ユーザ収容ノード間でフルメッシュに要求する帯域であってもよく、また、各ノード間で要求する帯域は互いに同じでなくてもよい。
このような状況において、スパニング・ツリー選択部１４は、まず、図２９に示すスパニング・ツリー情報格納テーブル１３から「ＭＳＴＩＤ＝１」により識別されるスパニング・ツリーを選択する。この場合、このスパニング・ツリーに上記仮想ＬＡＮを収容したものと仮定すると、ノードＡ−Ｂ間のリンク、ノードＡ−Ｃ間のリンク、ノードＡ−Ｄ間のリンクを介してその仮想ＬＡＮのトラヒックが流れることになる。したがって、これらの３本のリンクについて収容可否が判定される。すなわち、この例では、上記３本のリンクの「使用中帯域」は、図２７に示すように、それぞれ「０．５」「１．０」「０．８」である。したがって、これらの「使用中帯域」に「要求帯域（＝０．５）」を加算すると、各リンクの合計帯域は、それぞれ「１．０」「１．５」「１．３」になる。そうすると、ノードＡ−Ｄ間のリンクについては、その合計帯域がそのリンクの「帯域幅（＝１．０）」を越えてしまい、要求された仮想ＬＡＮを収容できない、と判定される。この場合、ホップ数管理テーブルには何も書き込まれない。
続いて、スパニング・ツリー選択部１４は、「ＭＳＴＩＤ＝２」により識別されるスパニング・ツリーを選択する。この場合、このスパニング・ツリーに上記仮想ＬＡＮを収容したものと仮定すると、その仮想ＬＡＮのトラヒックは、ノードＢ−Ｃ間のリンク、およびノードＣ−Ｄ間のリンクのみを介して流れることになる。従って、これらの２本のリンクについてその仮想ＬＡＮトラヒックを収容できるか否かが判定される。すなわち、この例では、上記２本のリンクの「使用中帯域」は、図２７に示すように、それぞれ「２．５」「１．０」である。そして、これらの「使用中帯域」に「要求帯域（＝０．５）」を加算すると、各リンクの合計帯域は、それぞれ「３．０」「０．６」になる。そうすると、これら２本のリンクについては、各合計帯域がそれぞれ対応するリンクの「帯域幅（５および１）」よりも小さく、要求された仮想ＬＡＮを収容できる、と判定される。そして、この場合、ホップ数管理テーブルには、「総ホップ数＝２」が書き込まれる。
さらに、スパニング・ツリー選択部１４は、「ＭＳＴＩＤ＝３」についても同様の処理を行う。この場合、このスパニング・ツリーに上記仮想ＬＡＮを収容したと仮定すると、ノードＡ−Ｂ間のリンク、ノードＡ−Ｃ間のリンク、ノードＣ−Ｄ間のリンクを介してその仮想ＬＡＮのトラヒックが流れることになり、要求された仮想ＬＡＮを収容できる、と判定される。そして、ホップ数管理テーブルには、「総ホップ数＝３」が書き込まれる。この結果、ホップ数管理テーブルは、図２８（ｂ）に示す状態に更新される。
スパニング・ツリー選択部１４は、図２８（ｂ）に示すホップ数管理テーブルを参照し、「総ホップ数」が最小のスパニング・ツリーを選択する。すなわち、この例では、「ＭＳＴＩＤ＝２」により識別されるスパニング・ツリーが選択されることになる。
なお、複数のスパニング・ツリーを構築する処理、および選択したスパニング・ツリーと要求された仮想ＬＡＮとのマッピング情報を各ノードに設定する処理は、上述した通りである。
このように、第３の実施例においては、総ホップ数が最小になるスパニング・ツリーが選択され、そのスパニング・ツリー上に仮想ＬＡＮが収容される。したがって、最も短い経路で仮想ＬＡＮサービスが提供される。
＜第４の実施例＞
第３の実施例では、新たに追加される仮想ＬＡＮトラヒックが流れる経路のトータルホップ数が最小になるスパニング・ツリーが選択されたが、第４の実施例では、新たに仮想ＬＡＮを追加することにより増加するトラヒック量（帯域）の和が最小になるスパニング・ツリーが選択される。
第４の実施例におけるスパニング・ツリー選択部１４の動作は、基本的には、第３の実施例と同じである。ただし、以下の動作が異なる。
スパニング・ツリー選択部１４は、図３１（ａ）に示す追加帯域管理テーブルを用意する。ここで、このテーブルは、スパニング・ツリーを用いて新たな仮想ＬＡＮを収容したときの使用帯域の増加量を管理する。
スパニング・ツリー選択部１４は、第３の実施例と同様に、スパニング・ツリー情報格納テーブル１３に登録されている各スパニング・ツリーについて、それぞれ、要求された仮想ＬＡＮを収容できるか否かを調べる。そして、要求された仮想ＬＡＮを収容可能と判定されたときは、その仮想ＬＡＮを追加することにより増加する帯域の合計値を「帯域増加量」として増加帯域管理テーブルに書き込む。なお、要求された仮想ＬＡＮを収容できないときは、増加帯域管理テーブルは更新されない。
スパニング・ツリー選択部１４は、上述のようにして、スパニング・ツリー情報格納テーブル１３に登録されている全てのスパニング・ツリーに対して「帯域増加量」を求める。そして、「帯域増加量」が最小のスパニング・ツリーを、要求された仮想ＬＡＮを収容すべきスパニング・ツリーとして選択する。
一例を示す。ここでは、第３の実施例と同様に、スパニング・ツリー情報格納テーブル１３に、図２９に示すスパニング・ツリー情報が格納されているものとする。すなわち、図３０に示す３つのスパニング・ツリーが構築されているものとする。また、仮想ＬＡＮを要求したユーザはノードＢ、Ｃ、Ｄに収容されているものとする。さらに、このユーザは、ノードＢ、Ｃ、Ｄを結ぶ経路上で「帯域＝０．５（Ｍｂｐｓ）」を要求しているものとする。
このような状況において、スパニング・ツリー選択部１４は、まず、図２９に示すスパニング・ツリー情報格納テーブル１３から「ＭＳＴＩＤ＝１」により識別されるスパニング・ツリーを選択する。しかし、第３の実施例で説明したように、このスパニング・ツリーは、要求された仮想ＬＡＮを収容することができない。よって、この場合、増加帯域管理テーブルには何も書き込まれない。
続いて、スパニング・ツリー選択部１４は、「ＭＳＴＩＤ＝２」により識別されるスパニング・ツリーを選択する。ここで、このスパニング・ツリーは、上述したように、要求された仮想ＬＡＮを収容できるので、スパニング・ツリー選択部１４は「帯域増加量」を算出する。すなわち、このスパニング・ツリー上に上述の仮想ＬＡＮを収容したと仮定すると、その仮想ＬＡＮのトラヒックは、２本のリンク（ノードＢ−Ｃ間のリンク、ノードＣ−Ｄ間のリンク）を介して流れることになる。ここで、ユーザの要求帯域が「０．５（Ｍｂｐｓ）」であるので、よって、この仮想ＬＡＮを追加することによって増加する使用帯域の和は、「１．０（Ｍｂｐｓ）」になる。そして、この計算結果が、増加帯域管理テーブルに書き込まれる。
さらに、スパニング・ツリー選択部１４は、「ＭＳＴＩＤ＝３」についても同様の処理を行う。この場合、このスパニング・ツリーに上記仮想ＬＡＮを収容したものと仮定する、その仮想ＬＡＮのトラヒックは、３本のリンク（ノードＡ−Ｂ間のリンク、ノードＡ−Ｃ間のリンク、ノードＣ−Ｄ間のリンク）を介して流れることになる。よって、増加帯域管理テーブルには、「帯域増加量＝１．５（Ｍｂｐｓ）」が書き込まれる。この結果、増加帯域管理テーブルは、図３１（ｂ）に示す状態に更新される。
この後、スパニング・ツリー選択部１４は、図３１（ｂ）に示す増加帯域管理テーブルを参照し、「帯域増加量」が最小のスパニング・ツリーを選択する。すなわち、この例では、「ＭＳＴＩＤ＝２」により識別されるスパニング・ツリーが選択されることになる。
なお、複数のスパニング・ツリーを構築する処理、および選択したスパニング・ツリーと要求された仮想ＬＡＮとのマッピング情報を各ノードに設定する処理は、上述した通りである。
ところで、上述の例のように、仮想ＬＡＮオーダにおけるユーザの要求帯域が全ての経路に渡って同じである場合には、第３および第４の実施例において同じスパニング・ツリーが選択されることになる。しかし、ユーザの要求帯域が経路によって偏りがある場合は、第３および第４の実施例において異なるスパニング・ツリーが選択されることがある。
例えば、図３２において、ユーザが３つの営業拠点を持っており、それらの拠点１、拠点２、拠点３が、それぞれノードＧ、ノードＩ、ノードＣに収容されているものとする。また、拠点２と拠点３との間でトラヒックが多く、他の拠点間はトラヒックが少ないものとする。なお、図３２においては、実線および二重線によりスパニング・ツリーが構築されているものとする。また、二重線は、仮想ＬＡＮトラヒックが流れる経路（すなわち、仮想ＬＡＮトポロジ）を表す。
この場合、図３２（ａ）に示すスパニング・ツリーでは、ノードＣとノードＩとの間の大容量トラヒックが、ノードＢ、Ａ、Ｄ、Ｇ、Ｈを介して流れることになる。すなわち、この経路上に存在する６本のリンクのそれぞれにおいて大きな帯域を確保する必要がある。よって、この場合、この仮想ＬＡＮを収容するために必要な帯域の総和は、かなり大きくなる。たとえば、上記６本のリンクに対してそれぞれ図３２（ａ）に示す帯域が割り当てられるとすると、その合計帯域は「６０（Ｍｂｐｓ）」になる。
一方、図３２（ｂ）に示すスパニング・ツリーでは、ノードＣとノードＩとの間の大容量トラヒックは、ノードＦを介して流れる。すなわち、ノードＣとノードＩとの間の２本のリンクには大きな帯域を割り当てる必要があるが、ノードＣとノードＧとの間の４本のリンクには大きな帯域を割り当てる必要がない。よって、この場合、この仮想ＬＡＮを収容するために必要な帯域の総和は、比較的小さくなる。例えば、上記６本のリンクに対してそれぞれ図３２（ａ）に示す帯域が割り当てられるとすると、その合計帯域は「２８（Ｍｂｐｓ）」になる。
そして、スパニング・ツリー選択部１４は、この例においては、図３２（ｂ）に示すスパニング・ツリーを選択することになる。なお、図３２（ａ）および図３２（ｂ）に示すいずれのスパニング・ツリーであっても、仮想ＬＡＮを収容したときの総ホップ数は、共に「６」である。よって、この場合、「総ホップ数」のみによって２つのスパニング・ツリーに優劣をつけることはできない。
このように、第４の実施例においては、各仮想ＬＡＮに割り当てられる通信資源が最小になるスパニング・ツリーが選択され、そのスパニング・ツリー上に仮想ＬＡＮが収容される。したがって、ネットワーク上を流れるトラヒック量が減少し、限られた通信資源を他の仮想ＬＡＮに割り当てることができるので、通信資源が有効に利用される。
＜第５の実施例＞
第５の実施例では、各リンクの利用率のばらつきが最小になるスパニング・ツリーが選択される。したがって、第５の実施例におけるスパニング・ツリー選択部１４の動作は、基本的には、第３または第４の実施例と同じであるが、以下の動作が異なる。
スパニング・ツリー選択部１４は、図３３（ａ）に示すばらつき管理テーブルを用意する。ここで、このテーブルは、各スパニング・ツリーについて各リンクの利用率のばらつきを管理する。
スパニング・ツリー選択部１４は、第３または第４の実施例と同様に、スパニング・ツリー情報格納テーブル１３に登録されている各スパニング・ツリーについて、それぞれ、要求された仮想ＬＡＮを収容できるか否かを調べる。そして、要求された仮想ＬＡＮを収容可能と判定されたときは、その仮想ＬＡＮを追加したと仮定した場合における各リンクの利用率のばらつきを「ばらつき量ＶＡＲ」としてばらつき管理テーブルに書き込む。なお、要求された仮想ＬＡＮを収容できないときは、ばらつき管理テーブルは更新されない。
スパニング・ツリー選択部１４は、上述のようにして、全てのスパニング・ツリーに対して「ばらつき量」を求める。そして、「ばらつき量」が最小のスパニング・ツリーを、要求された仮想ＬＡＮを収容すべきスパニング・ツリーとして選択する。
一例を示す。なお、ここでは、第３または第４の実施例と同様のスパニング・ツリーが構築されており、同様の仮想ＬＡＮが要求されたものとする。したがって、ここでも、「ＭＳＴＩＤ＝１」により識別されるスパニング・ツリーは、要求された仮想ＬＡＮを収容することができない。そして、ばらつき管理テーブルには何も書き込まれない。
続いて、スパニング・ツリー選択部１４は、「ＭＳＴＩＤ＝２」により識別されるスパニング・ツリーを選択する。そして、このスパニング・ツリー上に要求された仮想ＬＡＮを収容したときの「ばらつき量」を算出する。ここで、このスパニング・ツリー上に上述の仮想ＬＡＮを収容したと仮定すると、その仮想ＬＡＮのトラヒックは、２本のリンク（ノードＢ−Ｃ間のリンク、ノードＣ−Ｄ間のリンク）を介して流れることになる。よって、各リンクの利用率は、図３４（ａ）に示すようになる。具体的には、図２９に示すスパニング・ツリー情報格納テーブル１３を参照して下記のように算出される。
ノードＡ−Ｂ間のリンク：（０．５＋０）÷５＝０．１
ノードＡ−Ｃ間のリンク：（１．０＋０）÷１０＝０．１
ノードＡ−Ｄ間のリンク：（０．８＋０）÷１＝０．８
ノードＢ−Ｃ間のリンク：（２．５＋０．５）÷５＝０．６
ノードＣ−Ｄ間のリンク：（０．１＋０．５）÷１＝０．６
このとき、「ばらつき量」を算出するためにこれらの母分散を求めると、「ＶＡＲ＝０．０８２４」が得られる。そして、この値は、ばらつき管理テーブルに書き込まれる。
さらに、スパニング・ツリー選択部１４は、「ＭＳＴＩＤ＝３」についても同様の処理を行う。この場合、このスパニング・ツリーに上記仮想ＬＡＮを収容したと仮定すると、その仮想ＬＡＮのトラヒックは、３本のリンク（ノードＡ−Ｂ間のリンク、ノードＡ−Ｃ間のリンク、ノードＣ−Ｄ間のリンク）を介して流れることになる。よって、各リンクの利用率は、図３４（ｂ）に示すようになる。具体的には、下記のように算出される。
ノードＡ−Ｂ間のリンク：（０．５＋０．５）÷５＝０．２
ノードＡ−Ｃ間のリンク：（１．０＋０．５）÷１０＝０．１５
ノードＡ−Ｄ間のリンク：（０．８＋０）÷１＝０．８
ノードＢ−Ｃ間のリンク：（２．５＋０）÷５＝０．５
ノードＣ−Ｄ間のリンク：（０．１＋０．５）÷１＝０．６
この場合、「ばらつき量」として「ＶＡＲ＝０．０６」が得られる。そして、この値は、ばらつき管理テーブルに書き込まれる。この結果、ばらつき管理テーブルは、図３３（ｂ）に示すように更新される。
この後、スパニング・ツリー選択部１４は、図３３（ｂ）に示すばらつき管理テーブルを参照し、「ばらつき量」が最小のスパニング・ツリーを選択する。すなわち、この例では、「ＭＳＴＩＤ＝３」により識別されるスパニング・ツリーが選択されることになる。
なお、複数のスパニング・ツリーを構築する処理、および選択したスパニング・ツリーと要求された仮想ＬＡＮとのマッピング情報を各ノードに設定する処理は、上述した通りである。
また、上述の例では、各リンクの利用率のばらつきを評価する際に、母分散を利用したが、本発明はこれに限定されるものではない。例えば、標準偏差などを利用してばらつきの評価をしてもよい。
さらに、各リンクの利用率を検出する方法は、特に限定されるものではない。したがって、例えば、各リンクに対して既に割り当てられる帯域に、各リンクに新たに割り当てるべき帯域を加算し、その加算結果に基づいて各リンク利用率を算出するようにしてもよい。あるいは、各リンク上のトラヒック量を動的にモニタする装置を設け、その装置により検出される各リンク毎のトラヒック量に対応する帯域に、各リンクに新たに割り当てるべき帯域を加算し、その加算結果に基づいて各リンク利用率を算出するようにしてもよい。ちなみに、前者の方法は、各仮想ＬＡＮの帯域を補償するサービスに好適と考えられる。一方、後者の方法は、いわゆるベストエフォート型のサービスを提供する場合に好適と考えられる。
このように、第５の実施例においては、リンク利用率のばらつきが最小になるスパニング・ツリーが選択され、そのスパニング・ツリー上に仮想ＬＡＮが収容される。したがって、ネットワーク全体としては帯域に余裕があるにもかかわらず、局所的な帯域不足によって仮想ＬＡＮを収容できないような事態が回避される。すなわち、通信資源が有効に使用される。
なお、第３〜第５に実施例では、「総ホップ数」「帯域増加量」「リンク利用率のばらつき」に基づいてスパニング・ツリーが選択される方法を採り上げて説明したが、本発明はこれに限定されるものではない。
例えば、要求された仮想ＬＡＮを収容したときにその仮想ＬＡＮのトラヒックが流れる経路上のリンクの伝送遅延時間の和が最小となるスパニング・ツリーが選択されるようにしてもよい。この場合、トポロジ情報格納テーブル１１には、各リンクの伝送遅延時間が登録されていることが望ましい。そうすると、そのテーブルから該当するリンクに対応する伝送遅延時間を抽出して加算することにより、スパニング・ツリー上での総伝送遅延時間が得られる。
また、要求された仮想ＬＡＮを収容したときにその仮想ＬＡＮのトラヒックが流れる経路上のリンクの利用料金の和が最小となるスパニング・ツリーが選択されるようにしてもよい。この場合、トポロジ情報格納テーブル１１には、各リンクの利用料金が登録されていることが望ましい。そうすると、そのテーブルから該当するリンクに対応する利用料金を抽出して加算することにより、スパニング・ツリー上での総利用料金が得られる。
図３５は、第３〜第５の実施例におけるスパニング・ツリー選択部１４の動作を示すフローチャートである。
ステップＳ１０１では、トポロジ情報格納テーブル１１からトポロジ情報を取得する。ステップＳ１０２では、スパニング・ツリー情報格納テーブル１３からスパニング・ツリー情報を取得する。そして、スパニング・ツリー情報格納テーブル１３に登録されている全てのスパニング・ツリーについて、ステップＳ１０３〜Ｓ１０６の処理を実行する。
ステップＳ１０３では、スパニング・ツリーを１つ抽出する。ステップＳ１０４では、ステップＳ１０３で抽出したスパニング・ツリー上に要求された仮想ＬＡＮを収容したと仮定した場合の各リンクの使用帯域を計算する。ステップＳ１０５では、ステップＳ１０３で抽出したスパニング・ツリー上に要求された仮想ＬＡＮを収容できるか否かを調べる。すなわち、ステップＳ１０４で算出した使用帯域が、対応するリンクの帯域幅以下であるかを調べる。そして、要求された仮想ＬＡＮを収容可能な場合は、ステップＳ１０６において、パラメータ演算処理を実行する。なお、このパラメータ演算処理については、後で説明する。
全てのスパニング・ツリーについてステップＳ１０３〜Ｓ１０６の処理が終了すると、ステップＳ１０７において、要求された仮想ＬＡＮを収容可能なスパニング・ツリーが存在するか否かを調べる。そして、そのようなスパニング・ツリーが存在する場合は、ステップＳ１０８において、仮想ＬＡＮを収容すべきスパニング・ツリーを１つ選択する。なお、この選択処理については、後で説明をする。一方、そのようなスパニング・ツリーが存在しなかった場合は、ステップＳ１０９において、仮想ＬＡＮを収容できない旨のメッセージを出力する。
図３６（ａ）〜図３７（ｃ）は、それぞれ、図３５に示すステップＳ１０６およびＳ１０８の処理の具体例を説明する図である。
図３６（ａ）に示す例では、ステップＳ１０６の処理として、当該スパニング・ツリーに仮想ＬＡＮを収容したと仮定した場合の総ホップ数を調べる。そして、当該スパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤと対応づけて、その総ホップ数を記憶する。また、ステップＳ１０８の処理としては、仮想ＬＡＮオーダを受け付けた旨のメッセージを出力すると共に、総ホップ数が最小のスパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤを出力する。
図３６（ｂ）に示す例では、ステップＳ１０６の処理として、当該スパニング・ツリーに仮想ＬＡＮを収容したと仮定した場合の帯域増加量を調べる。そして、当該スパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤと対応づけて、その帯域増加量を記憶する。また、ステップＳ１０８の処理としては、仮想ＬＡＮオーダを受け付けた旨のメッセージを出力すると共に、帯域増加量が最小のスパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤを出力する。
図３６（ｃ）および図３７（ａ）に示す例では、ステップＳ１０６の処理として、当該スパニング・ツリーに仮想ＬＡＮを収容したと仮定した場合のリンク利用率のばらつきを調べる。そして、当該スパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤと対応づけて、そのばらつき量を記憶する。また、ステップＳ１０８の処理としては、仮想ＬＡＮオーダを受け付けた旨のメッセージを出力すると共に、リンク利用率のばらつきが最小のスパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤを出力する。
ただし、図３６（ｃ）に示す例では、既に他の仮想ＬＡＮに割り当てられている帯域に、新たに要求された仮想ＬＡＮの申告帯域を加算した結果に基づいて、リンク毎の利用率が算出される。一方、図３７（ａ）に示す例では、実際に使用されている帯域を測定し、その測定された帯域に新たに要求された仮想ＬＡＮの申告帯域を加算した結果に基づいて、リンク毎の利用率が算出される。
図３７（ｂ）に示す例では、ステップＳ１０６の処理として、当該スパニング・ツリーに仮想ＬＡＮを収容したと仮定した場合の伝送遅延時間の和を調べる。そして、当該スパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤと対応づけて、その伝送遅延時間の和を記憶する。また、ステップＳ１０８の処理としては、仮想ＬＡＮオーダを受け付けた旨のメッセージを出力すると共に、伝送遅延時間の和が最小のスパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤを出力する。
図３７（ｃ）に示す例では、ステップＳ１０６の処理として、当該スパニング・ツリーに仮想ＬＡＮを収容したと仮定した場合の利用料金の和を調べる。そして、当該スパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤと対応づけて、その利用料金の和を記憶する。また、ステップＳ１０８の処理としては、仮想ＬＡＮオーダを受け付けた旨のメッセージを出力すると共に、利用料金の和が最小のスパニング・ツリーを識別するスパニング・ツリー識別子ＭＳＴＩＤを出力する。
＜シミュレーション１＞
図３８（ａ）に示すネットワークを前提とする。なお、各リンクのコストは、すべて互いに同じであるものとする。また、収容すべき仮想ＬＡＮは、本社システム、および１または複数の支社システムを相互に接続するものであり、本社システムから各支社システムへのトラヒックのための帯域として１０Ｍｂｐｓ、各支社システムから本社システムへのトラヒックのための帯域として５Ｍｂｐｓ、支社システム間のトラヒックのための帯域として３Ｍｂｐｓが申告されたものとする。
そして、このような環境下で、本発明の方法、従来の方法、および単一スパニング・ツリーによる方法を比較する。なお、「本発明の方法」は、図１〜図３７を利用して説明したように、予め複数のスパニング・ツリーを構築しておき、仮想ＬＡＮオーダを受け付けたときに、それら複数のスパニング・ツリーの中から適切なツリーを選択して仮想ＬＡＮオーダに割り当てるものである。ここで、根ノードはランダムに選択され、また、仮想ＬＡＮのホップ数が最小になるようにスパニング・ツリーが選択されるものとしている。これに対して「従来の方法」は、仮想ＬＡＮオーダを受け付ける毎に新たなスパニング・ツリーを構築して、それを仮想ＬＡＮオーダに割り当てるものである。
図３８（ｂ）では、ユーザから仮想ＬＡＮオーダを受けたときから、仮想ＬＡＮサービスを開始するための設定が終了するまでの時間が比較されている。ここで、「アクセスノード」とは、ユーザを収容するノードを意味する。そして、例えば、「アクセスノード数＝５」は、本社システムおよび４つの支社システムが互いに異なるノードに収容されていることを意味するものとする。
図３８（ｂ）に示すように、「従来の方法」においては、サービス開始までに要する時間が、アクセスノード数が増えるに従って急激に（指数関数的に）長くなっていく。これに対して、「本発明の方法」においては、アクセスノード数が増加しても、サービス開始までに要する時間はさほど増加しない。
図３８（ｃ）では、収容可能な仮想ＬＡＮの数が比較されている。ここでは、各仮想ＬＡＮのアクセスノード数が「５」であるものとしている。そして、図３８（ｃ）に示すように、単一のスパニング・ツリーによる方法では、収容可能な仮想ＬＡＮの数は、約５００である。これに対して、本発明の方法では、約７００程度の仮想ＬＡＮを収容することができる。なお、収容可能な仮想ＬＡＮの数を比較した場合、この例では、「本発明の方法」よりも「従来の方法」の方が若干有利である。しかし、「従来の方法」では、収容される仮想ＬＡＮの数が増えると、上述したように、「サービス開始までに要する時間」が急激に劣化するという問題が生じる。
このように、本発明の方法は、サービス開始までの時間の短縮、および収容可能な仮想ＬＡＮの数の増加を、バランスよく実現することができる。
＜シミュレーション２＞
本発明に係わる第１の方法および第２の方法を比較する。ここで、第１の方法では、根ノードをランダムに選択しながら複数のスパニング・ツリーを構築する際に、各リンクがスパニング・ツリーに含まれる毎にそのコストを１ずつインクリメントすることで、ツリーの重複を回避するようになっている。また、複数のスパニング・ツリーから１つのスパニング・ツリーを選択する方法は、上述した第４の実施例に従い、総ホップ数が最小になるツリーが選択される。
一方、第２の方法では、複数のスパニング・ツリーを構築する方法は、上述した第２の実施例に従う。すなわち、各リンクの優先度を考慮しつつ、一度も利用されないリンクが存在しないように複数のスパニング・ツリーが構築される。また、複数のスパニング・ツリーから１つのスパニング・ツリーを選択する方法は、上述した第５の実施例に従い、リンク利用率のばらつきが最小になるようにツリーが選択される。
なお、シミュレーション２が前提とするネットワークモデルは、特に図示しないが、上述したシミュレーション１が前提とするネットワークモデルとは異なっている。
図３９は、収容可能な仮想ＬＡＮの数についての比較結果を示す図である。ここでは、予め構築しておくスパニング・ツリーの数を１６とする。そして、「アクセスノード数＝５」および「アクセスノード数＝１０」の場合のシミュレーション結果を、それぞれ図３９（ａ）および図３９（ｂ）に示す。
これらのシミュレーション結果から分かるように、収容可能な仮想ＬＡＮの数に注目すると、第２の方法の方が有利である。すなわち、第２の方法の方が、通信資源（或いは、帯域）が有効に利用されていると言える。この理由は、帯域幅の大きなリンクが優先的に使用されたスパニング・ツリーが予め用意されているので、局所的なリンク利用率の上昇が抑えられるからであると考えられる。
なお、上述した「複数のスパニング・ツリーを構築する方法」および「複数のスパニング・ツリーの中から１つのスパニング・ツリーを選択する方法」は、任意に組み合わせることができる。
図４０は、ネットワーク管理システム１として動作するコンピュータのハードウェア構成図である。なお、仮想ＬＡＮ構築機能は、コンピュータを用いて上述のフローチャートに示した処理を記述したプログラムを実行することによって実現される。
ＣＰＵ１０１は、上述のフローチャートに示した処理を記述したプログラムを記憶装置１０２からメモリ１０３にロードして実行する。記憶装置１０２は、例えばハードディスクであり、上記プログラムを格納する。なお、記憶装置１０２は、コンピュータ１００に接続される外部記憶装置であってもよい。メモリ１０３は、例えば半導体メモリであり、ＣＰＵ１０１の作業領域として使用される。
記録媒体ドライバ１０４は、ＣＰＵ１０１の指示に従って可搬性記録媒体１０５にアクセスする。可搬性記録媒体１０５は、例えば、半導体デバイス（ＰＣカード等）、磁気的作用により情報が入出力される媒体（フレキシブルディスク、磁気テープ等）、光学的作用により情報が入出力される媒体（光ディスク等）を含むものとする。入力装置は、例えば、キーボードおよびポインティングデバイスであり、ネットワーク管理者の入力をＣＰＵ１０１に伝える。通信制御装置１０７は、ＣＰＵ１０１の指示に従って、ネットワークを介してデータを送受信する。
トポロジ情報格納テーブル１１およびスパニング・ツリー情報格納テーブル１３は、例えば、記憶装置１２に格納されている。また、スパニング・ツリー構築部１２、スパニング・ツリー選択部１４、ノード設定部１５、優先度設定部１６は、上述したフローチャートの処理を記述したプログラムをＣＰＵ１０１を用いて実行することにより実現される。なお、ノード設定部１５は、通信制御装置１０７を介して各ノードに指示を送信する。
本発明によれば、仮想ＬＡＮサービスが要求されたときからそのサービスを開始できるようになるまでの時間が大幅に短縮される。また、各リンクの優先度に応じた経路で仮想ＬＡＮを提供できる。さらに、考慮すべき通信パラメータを参照して仮想ＬＡＮを設計できる。特に、リンク利用率のばらつきを考慮してスパニング・ツリーを選択する場合には、通信資源の有効利用が図れる。
【図１】
2004075486.tif 000003
【図２】
2004075486.tif 000004
【図３】
2004075486.tif 000005
【図４】
2004075486.tif 000006
【図５】
2004075486.tif 000007
【図６】
2004075486.tif 000008
【図７】
2004075486.tif 000009
【図８】
2004075486.tif 000010
【図９】
2004075486.tif 000011
【図１０】
2004075486.tif 000012
【図１１】
2004075486.tif 000013
【図１２】
2004075486.tif 000014
【図１３】
2004075486.tif 000015
【図１４】
2004075486.tif 000016
【図１５】
2004075486.tif 000017
【図１６】
2004075486.tif 000018
【図１７】
2004075486.tif 000019
【図１８】
2004075486.tif 000020
【図１９】
2004075486.tif 000021
【図２０】
2004075486.tif 000022
【図２１】
2004075486.tif 000023
【図２２】
2004075486.tif 000024
【図２３】
2004075486.tif 000025
【図２４】
2004075486.tif 000026
【図２５】
2004075486.tif 000027
【図２６】
2004075486.tif 000028
【図２７】
2004075486.tif 000029
【図２８】
2004075486.tif 000030
【図２９】
2004075486.tif 000031
【図３０】
2004075486.tif 000032
【図３１】
2004075486.tif 000033
【図３２】
2004075486.tif 000034
【図３３】
2004075486.tif 000035
【図３４】
2004075486.tif 000036
【図３５】
2004075486.tif 000037
【図３６】
2004075486.tif 000038
【図３７】
2004075486.tif 000039
【図３８】
2004075486.tif 000040
【図３９】
2004075486.tif 000041
【図４０】
2004075486.tif 000042
【国際調査報告】
2004075486.tif 000043
2004075486.tif 000044
2004075486.tif 000045
2004075486.tif 000046