(57)【特許請求の範囲】
【請求項１】
メッシュネットワークを構成するフレーム転送装置であって、
隣接ノードの各々から、低遅延転送が必要なフレームを送受信するノードか否かを示す属性情報および通信相手のノードを示す通信相手ノード情報を含んだ隣接ノード情報を収集する隣接ノード情報収集手段と、
前記隣接ノード情報収集手段が収集した前記隣接ノード情報を前記メッシュネットワーク内に広告する隣接ノード情報広告手段と、
前記隣接ノード情報収集手段が収集した前記隣接ノード情報と、他のフレーム転送装置により前記メッシュネットワーク内へ広告された前記隣接ノード情報とに基づいて、前記メッシュネットワークを構成している各リンクについて、低遅延転送が必要なフレームを送受信するためのパスを決定する際に使用する第１のリンクメトリックと、低遅延転送が必要ないフレームを送受信するためのパスを決定する際に使用する第２のリンクメトリックと、を決定する決定手段と、
を備えることを特徴とするフレーム転送装置。
【請求項２】
前記決定手段は、
前記隣接ノード情報と、前記メッシュネットワークのトポロジー情報と、前記メッシュネットワークを構成している各フレーム転送装置の隣接ノードの情報とに基づいて、低遅延転送が必要なフレームを送受信するノード間のパスを仮決定する低遅延転送用パス決定手段と、
前記低遅延転送用パス決定手段が仮決定したパスのパスコストと、前記メッシュネットワークのトポロジー情報と、低遅延転送が必要ではないフレームを送受信するノードが必要としている帯域の情報とに基づいて、前記第１のリンクメトリックおよび前記第２のリンクメトリックを決定するリンクメトリック決定手段と、
を備えることを特徴とする請求項１に記載のフレーム転送装置。
【請求項３】
前記低遅延転送用パス決定手段は、低遅延転送が必要なフレームを送受信するノード間のパスであるＥｘｐｒｅｓｓパスを複数仮決定する場合、前記メッシュネットワークを構成しているリンクの各々について、Ｅｘｐｒｅｓｓパスで重複使用される回数が少なくなるよう、各Ｅｘｐｒｅｓｓパスを仮決定する、
ことを特徴とする請求項２に記載のフレーム転送装置。
【請求項４】
前記低遅延転送用パス決定手段は、前記Ｅｘｐｒｅｓｓパスが使用するリンクの重なりが最大となるリンクの重なりが最小となるように線形計画問題を解くことにより、前記Ｅｘｐｒｅｓｓパスを仮決定する、
ことを特徴とする請求項３に記載のフレーム転送装置。
【請求項５】
前記リンクメトリック決定手段は、低遅延転送が必要なフレームを送受信するノードのペアの数と同じ数の複数のリンクメトリックを決定して前記第１のリンクメトリックとし、前記複数のリンクメトリックの各々は、前記低遅延転送が必要なフレームを送受信するノードのペアのいずれか一つと１対１で対応付けられていることを特徴とする請求項２、３または４に記載のフレーム転送装置。
【請求項６】
前記決定手段は、
前記隣接ノード情報と、前記メッシュネットワークのトポロジー情報と、前記メッシュネットワークを構成している各フレーム転送装置の隣接ノードの情報とに基づいて、低遅延転送が必要なフレームを送受信するノード間のパスが使用するリンクの重なりが最大となるリンクの重なりが最小となるように線形計画問題を解くことにより、前記第１のリンクメトリックを決定する第１のリンクメトリック決定手段と、
前記メッシュネットワークのトポロジー情報と、低遅延転送が必要ではないフレームを送受信するノードが必要としている帯域の情報とに基づいて、前記第２のリンクメトリックを決定する第２のリンクメトリック決定手段と、
を備えることを特徴とする請求項１に記載のフレーム転送装置。
【請求項７】
前記決定手段で決定された各リンクの前記第１のリンクメトリックおよび前記第２のリンクメトリックに基づいて、前記メッシュネットワークを介してフレームを送受信する各ノードの間のパスを決定するパス決定手段、
を備えることを特徴とする請求項１から６のいずれか一つに記載のフレーム転送装置。
【請求項８】
メッシュネットワークを構成するフレーム転送装置が、前記メッシュネットワークを介してフレームを送受信する各ノードの間のパスを決定する処理で使用するリンクメトリックを決定するリンクメトリック決定方法であって、
隣接ノードの各々から、低遅延転送が必要なフレームを送受信するノードか否かを示す属性情報および通信相手のノードを示す通信相手ノード情報を含んだ隣接ノード情報を収集する隣接ノード情報収集ステップと、
前記隣接ノード情報収集ステップで収集した前記隣接ノード情報を前記メッシュネットワーク内に広告する隣接ノード情報広告ステップと、
前記隣接ノード情報収集ステップで収集した前記隣接ノード情報と、他のフレーム転送装置により前記メッシュネットワーク内へ広告された前記隣接ノード情報とに基づいて、前記メッシュネットワークを構成している各リンクについて、低遅延転送が必要なフレームを送受信するためのパスを決定する際に使用する第１のリンクメトリックと、低遅延転送が必要ないフレームを送受信するためのパスを決定する際に使用する第２のリンクメトリックと、を決定する決定ステップと、
を含むことを特徴とするリンクメトリック決定方法。
【請求項９】
前記決定ステップは、
前記隣接ノード情報と、前記メッシュネットワークのトポロジー情報と、前記メッシュネットワークを構成している各フレーム転送装置の隣接ノードの情報とに基づいて、低遅延転送が必要なフレームを送受信するノード間のパスを仮決定する低遅延転送用パス決定ステップと、
前記低遅延転送用パス決定ステップで仮決定したパスのパスコストと、前記メッシュネットワークのトポロジー情報と、低遅延転送が必要ではないフレームを送受信するノードが必要としている帯域の情報とに基づいて、前記第１のリンクメトリックおよび前記第２のリンクメトリックを決定するリンクメトリック決定ステップと、
を含むことを特徴とする請求項８に記載のリンクメトリック決定方法。
【請求項１０】
前記決定ステップは、
前記隣接ノード情報と、前記メッシュネットワークのトポロジー情報と、前記メッシュネットワークを構成している各フレーム転送装置の隣接ノードの情報とに基づいて、低遅延転送が必要なフレームを送受信するノード間のパスが使用するリンクの重なりが最大となるリンクの重なりが最小となるように線形計画問題を解くことにより、前記第１のリンクメトリックを決定する第１のリンクメトリック決定ステップと、
前記メッシュネットワークのトポロジー情報と、低遅延転送が必要ではないフレームを送受信するノードが必要としている帯域の情報とに基づいて、前記第２のリンクメトリックを決定する第２のリンクメトリック決定ステップと、
を含むことを特徴とする請求項８に記載のリンクメトリック決定方法。
【請求項１１】
メッシュネットワークを構成するフレーム転送装置におけるパス決定方法であって、
隣接ノードの各々から、低遅延転送が必要なフレームを送受信するノードか否かを示す属性情報および通信相手のノードを示す通信相手ノード情報を含んだ隣接ノード情報を収集する隣接ノード情報収集ステップと、
前記隣接ノード情報収集ステップで収集した前記隣接ノード情報を前記メッシュネットワーク内に広告する隣接ノード情報広告ステップと、
前記隣接ノード情報収集ステップで収集した前記隣接ノード情報と、他のフレーム転送装置により前記メッシュネットワーク内へ広告された前記隣接ノード情報とに基づいて、前記メッシュネットワークを構成している各リンクについて、低遅延転送が必要なフレームを送受信するためのパスを決定する際に使用する第１のリンクメトリックと、低遅延転送が必要ないフレームを送受信するためのパスを決定する際に使用する第２のリンクメトリックと、を決定する決定ステップと、
前記第１のリンクメトリックおよび前記第２のリンクメトリックに基づいて、前記メッシュネットワークを介してフレームを送受信する各ノードの間のパスを決定するパス決定ステップと、
を含むことを特徴とするパス決定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッシュネットワークにおいてフレームを転送するフレーム転送装置、リンクメトリック決定方法およびパス決定方法に関する。
【背景技術】
【０００２】
近年、車、工場、列車などのネットワークにイーサネット（登録商標）の適用が検討されている。しかしながら、これらのネットワークにイーサネット（登録商標）を適用する場合、フレームの転送遅延の抑制、ネットワークの信頼性確保などが課題となる。これらの課題を解決するため、ＩＥＴ（Interspersing  Express  Traffic）およびＳＰＢ（Shortest  Path  Bridging）が着目されている。ＩＥＴはフレームの低遅延転送を実現する技術であり、ＩＥＥＥ８０２．３ｂｒにて標準化が進められている。ＩＥＴは、低遅延転送を必要とするＥｘｐｒｅｓｓフレームと低遅延転送を必要としないＮｏｒｍａｌフレームとがスイッチにて競合したときに、Ｎｏｒｍａｌフレームの転送を中断して、Ｅｘｐｒｅｓｓフレームを割り込み転送し、Ｅｘｐｒｅｓｓフレームの転送が完了した後にＮｏｒｍａｌフレームの転送を再開することで、Ｅｘｐｒｅｓｓフレームの転送遅延を低減する技術である。一方、ＳＰＢはメッシュネットワークにおけるパスの決定方法に関する技術であり、ＩＥＥＥ８０２．１ａｑにて標準化が進められている。ＳＰＢは、ＥＣＭＰ（Equal  Cost  Multi  Path）を構成することにより、障害発生時の高速なパス切り替え、冗長経路の構成、トラフィックの分散を可能とする技術である。
【０００３】
また、メッシュネットワークにおけるトラフィックの分散を実現するための技術として、リンクメトリックの決定方法が非特許文献１に記載されている。非特許文献１に記載された技術では、全リンクの使用率の最大値が最小となるように線形計画問題を解くことで、トラフィックの負荷分散を実現するリンクメトリックを決定している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“Internet  Traffic  Engineering  without  Full  Mesh  Overlaying”,  Yufei  Wang,  Zheng  Wang,  Leah  Zhang,  IEEE  INFOCOM  2001
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述したＩＥＴを適用した場合、Ｅｘｐｒｅｓｓフレームの低遅延転送が可能となる。しかしながら、ＩＥＴはＮｏｒｍａｌフレームとＥｘｐｒｅｓｓフレームとが競合したときにＥｘｐｒｅｓｓフレームを低遅延転送することは可能であるが、異なる種類のＥｘｐｒｅｓｓフレームが競合した場合には遅延が発生する。そのため、Ｅｘｐｒｅｓｓフレームの競合発生頻度が低くなるよう、パスを決定する必要がある。ここで、ＳＰＢを適用した場合、トラフィックが分散されるように、すなわち各ノードにおいてフレームの競合が発生する頻度が低くなるように、パスを決定することが可能である。しかしながら、ＳＰＢでは、メッシュネットワーク内で送受信されるフレームの種別を考慮することなくパスを決定するため、ＩＥＴと組み合わせて使用することが難しい。すなわち、ＳＰＢでは、ＮｏｒｍａｌフレームとＥｘｐｒｅｓｓフレームが混在する場合でも、これらのフレームを同じ種類のものとして扱うため、Ｅｘｐｒｅｓｓフレーム同士の競合発生頻度が低くなるようにパスを決定できるとは限らない。また、非特許文献１に記載された技術も、Ｅｘｐｒｅｓｓフレームを送受信するノードとＮｏｒｍａｌフレームを送受信するノードが混在する場合を想定してリンクメトリックを決定するものではない。
【０００６】
本発明は、上記に鑑みてなされたものであって、低遅延転送を必要とするフレームを送受信するノードと低遅延転送を必要としないフレームを送受信するノードが混在する構成のネットワークに対してＳＰＢを適用する場合においても低遅延転送を必要とするフレーム同士の競合発生頻度を低く抑えたパスが決定されるリンクメトリックを導出することが可能なフレーム転送装置を得ることを目的とする。
【課題を解決するための手段】
【０００７】
上述した課題を解決し、目的を達成するために、本発明は、メッシュネットワークを構成するフレーム転送装置であり、隣接ノード情報収集手段、隣接ノード情報広告手段および決定手段を備えている。隣接ノード情報収集手段は、隣接ノードの各々から、低遅延転送が必要なフレームを送受信するノードか否かを示す属性情報および通信相手のノードを示す通信相手ノード情報を含んだ隣接ノード情報を収集し、隣接ノード情報広告手段は、隣接ノード情報収集手段が収集した隣接ノード情報をメッシュネットワーク内に広告する。決定手段は、隣接ノード情報収集手段が収集した隣接ノード情報と、他のフレーム転送装置によりメッシュネットワーク内へ広告された隣接ノード情報とに基づいて、メッシュネットワークを構成している各リンクについて、低遅延転送が必要なフレームを送受信するためのパスを決定する際に使用する第１のリンクメトリックと、低遅延転送が必要ないフレームを送受信するためのパスを決定する際に使用する第２のリンクメトリックと、を決定する。
【発明の効果】
【０００８】
本発明によれば、低遅延転送を必要とするフレームを送受信するノードと低遅延転送を必要としないフレームを送受信するノードが混在する状態においても低遅延転送を必要とするフレームの転送処理が競合する頻度を低く抑えたパスが決定されるようにリンクメトリックを導出することができる、という効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施の形態１にかかるフレーム転送装置により構成されているメッシュネットワークの一例を示す図
【図２】実施の形態１のフレーム転送装置であるスイッチの構成例を示す図
【図３】スイッチを実現するハードウェア構成の一例を示す図
【図４】フレーム処理部の動作例を示すフローチャート
【図５】Ｈｅｌｌｏフレームの構成例を示す図
【図６】隣接ノード情報収集部の動作例を示すフローチャート
【図７】隣接ノード情報広告部の動作例を示すフローチャート
【図８】ノード情報収集部の動作例を示すフローチャート
【図９】Ｅｘｐｒｅｓｓトラフィックパス決定部の動作例を示すフローチャート
【図１０】リンクメトリック決定部の動作例を示すフローチャート
【図１１】ＳＰＢ処理部の動作例を示すフローチャート
【図１２】カプセリング部の動作例を示すフローチャート
【図１３】フレーム転送部の動作例を示すフローチャート
【図１４】Ｈｅｌｌｏ生成部の動作例を示すフローチャート
【図１５】実施の形態１のスイッチがメッシュネットワークに接続しているノード間のパスを決定する手順を示す図
【図１６】スイッチがメッシュネットワーク内へ広告するフレームの構成例を示す図
【図１７】実施の形態２のフレーム転送装置であるスイッチの構成例を示す図
【図１８】線形計画問題解決部の動作例を示すフローチャート
【図１９】リンクメトリック決定部の動作例を示すフローチャート
【図２０】実施の形態２のスイッチがメッシュネットワークに接続しているノード間のパスを決定する手順を示す図
【発明を実施するための形態】
【００１０】
以下に、本発明の実施の形態にかかるフレーム転送装置、リンクメトリック決定方法およびパス決定方法を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００１１】
実施の形態１．
図１は、本発明の実施の形態１にかかるフレーム転送装置により構成されているメッシュネットワークの一例を示す図である。
【００１２】
本実施の形態のメッシュネットワークは、フレーム転送装置であるスイッチ２1〜２7により構成されている。スイッチ２1は、スイッチ２2、２3および２4との間でリンクが確立した状態、すなわち、スイッチ２2、２3および２4と通信が可能である。スイッチ２2は、スイッチ２1および２5との間でリンクが確立した状態である。スイッチ２3は、スイッチ２1および２6との間でリンクが確立した状態である。スイッチ２4は、スイッチ２1、２5および２6との間でリンクが確立した状態である。スイッチ２5は、スイッチ２2、２4および２7との間でリンクが確立した状態である。スイッチ２6は、スイッチ２3、２4および２7との間でリンクが確立した状態である。スイッチ２7は、スイッチ２5および２6との間でリンクが確立した状態である。
【００１３】
スイッチ２1には、ベストエフォートトラフィックを送受信するノードであるベストエフォートノード１1と、Ｅｘｐｒｅｓｓトラフィックを送受信するノードであるＥｘｐｒｅｓｓノード３1および４1とが接続されている。ここで、ベストエフォートトラフィックは低遅延転送を必要としないフレームであるＮｏｒｍａｌフレームで送受信されるデータである。また、Ｅｘｐｒｅｓｓトラフィックは低遅延転送が必要なフレームであるＥｘｐｒｅｓｓフレームで送受信されるデータである。図１では、スイッチを‘○’で表現し、ベストエフォートノードを‘△’で表現し、Ｅｘｐｒｅｓｓノードを‘□’で表現している。なお、以下の説明において、単に「フレーム」と記載した場合、ＮｏｒｍａｌフレームとＥｘｐｒｅｓｓフレームの双方を示すものとする。また、単に「ノード」と記載した場合、ベストエフォートノードとＥｘｐｒｅｓｓノードの双方を示すものとする。
【００１４】
スイッチ２2には、ベストエフォートノード１2が接続されている。スイッチ２3には、ベストエフォートノード１4が接続されている。スイッチ２7には、ベストエフォートノード１3と、Ｅｘｐｒｅｓｓノード３2および４2とが接続されている。なお、Ｅｘｐｒｅｓｓノード３1とＥｘｐｒｅｓｓノード３2がＥｘｐｒｅｓｓトラフィックを相互に送受信し、Ｅｘｐｒｅｓｓノード４1とＥｘｐｒｅｓｓノード４2がＥｘｐｒｅｓｓトラフィックを相互に送受信するものとする。
【００１５】
なお、スイッチ２1に接続されているベストエフォートノード１1、Ｅｘｐｒｅｓｓノード３1，４1を、スイッチ２1の隣接ノードと呼ぶ場合がある。同様に、ベストエフォートノード１2をスイッチ２2の隣接ノードと呼ぶ場合がある。ベストエフォートノード１4をスイッチ２3の隣接ノードと呼ぶ場合がある。ベストエフォートノード１3、Ｅｘｐｒｅｓｓノード３2，４2を、スイッチ２7の隣接ノードと呼ぶ場合がある。
【００１６】
図２は、実施の形態１のフレーム転送装置であるスイッチ２1〜２7の構成例を示す図である。スイッチ２1〜２7の構成は同一である。以下、スイッチ２1〜２7に共通の構成、動作などを説明する場合、スイッチ２1〜２7をまとめてスイッチ２と表現する場合がある。
【００１７】
スイッチ２において、受信部２１は、他のスイッチ２または隣接ノードからフレームを受信する。送信部２２は、他のスイッチ２または隣接ノードへフレームを送信する。Ｈｅｌｌｏ生成部２３は、Ｈｅｌｌｏフレームを生成する。隣接ノード情報広告部２４は、他のスイッチ２に広告するための隣接ノードの情報を含んだフレームを生成する。フレーム転送部２５は、他のスイッチ２または隣接ノードから受信したフレームのうち、自スイッチ宛ではないフレームを転送する。転送データベース２６は、フレームの転送先の情報を管理する。ＳＰＢ処理部２７は、フレームを送受信するノード間のパスをＩＥＥＥ８０２．１ａｑで標準化されているＳＰＢ（Shortest  Path  Bridging）により決定する。フレーム処理部２８は、他のスイッチ２または隣接ノードから受信したフレームの内容を確認して出力先を決定する。隣接ノード情報収集部２９は、隣接ノードの情報が含まれたフレームを受信した場合に、受信したフレームから隣接ノードに関する情報を取り出す。ノード情報収集部３０は、他のスイッチ２の隣接ノードの情報が含まれたフレームを受信した場合に、受信したフレームから他のスイッチ２の隣接ノードの情報を取り出す。ネットワークトポロジー情報管理部３１は、スイッチ２1〜２7が形成しているメッシュネットワークのトポロジー情報を管理する。リンクメトリック決定部３２は、メッシュネットワーク内の全てのリンクを対象としてリンクメトリックを決定する。Ｅｘｐｒｅｓｓトラフィックパス決定部３３は、Ｅｘｐｒｅｓｓトラフィックの転送パス、すなわちＥｘｐｒｅｓｓノード間のパスであるＥｘｐｒｅｓｓトラフィックパスを仮決定する。カプセリング部３４は、他のスイッチ２または隣接ノードから受信したフレームを転送する場合に、フレームのカプセリングまたはデカプセリングを行う。
【００１８】
図３は、スイッチ２を実現するハードウェア構成の一例を示す図である。スイッチ２は、送信機１０１、受信機１０２、ＣＰＵ（Central  Processing  Unit）などのプロセッサ１０３と、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）などで構成されるメモリ１０４と、により実現することが可能である。送信機１０１、受信機１０２、プロセッサ１０３およびメモリ１０４はバス１００に接続されており、バス１００を介してデータ、制御情報などの受け渡しを相互に行うことが可能である。
【００１９】
図２に示したスイッチ２の送信部２２は送信機１０１により実現される。スイッチ２の受信部２１は受信機１０２により実現される。Ｈｅｌｌｏ生成部２３、隣接ノード情報広告部２４フレーム転送部２５、ＳＰＢ処理部２７、フレーム処理部２８、隣接ノード情報収集部２９、ノード情報収集部３０、ネットワークトポロジー情報管理部３１、リンクメトリック決定部３２、Ｅｘｐｒｅｓｓトラフィックパス決定部３３およびカプセリング部３４は、それぞれに対応するプログラムをプロセッサ１０３が実行することにより実現される。転送データベース２６はメモリ１０４が必要な情報を記憶することにより実現される。ネットワークトポロジー情報管理部３１は、メモリ１０４により実現される。なお、複数のプロセッサおよび複数のメモリが連携してスイッチ２の各部を実現するようにしてもよい。
【００２０】
次に、スイッチ２の各部の動作について説明する。
【００２１】
受信部２１は、メッシュネットワークを構成している他のスイッチ２または隣接ノードからフレームを受信し、受信したフレームをフレーム処理部２８へ出力する。
【００２２】
フレーム処理部２８は、図４に示したフローチャートに従って動作する。具体的には、フレーム処理部２８は、受信部２１からフレームを受信したか否かを継続的に監視している（ステップＳ１１：Ｎｏ）。フレーム処理部２８は、フレームを受信した場合（ステップＳ１１：Ｙｅｓ）、すなわち、受信部２１からフレームを受け取ると、フレームの内容を確認し、フレームの種類に応じた出力先へフレームを出力する。詳細には、フレーム処理部２８は、受信部２１から受け取ったフレームが隣接ノードから送付されたＨｅｌｌｏフレームか否かを確認し（ステップＳ１２）、Ｈｅｌｌｏフレームの場合（ステップＳ１２：Ｙｅｓ）、隣接ノード情報収集部２９へフレームを出力する（ステップＳ１４）。Ｈｅｌｌｏフレームには隣接ノード情報が格納されている。ここで、Ｈｅｌｌｏフレームについて説明する。図５はＨｅｌｌｏフレームの構成例を示す図である。図５に示したようにＨｅｌｌｏフレームは、ヘッダと、隣接ノード情報である、識別情報、属性情報、通信相手ノードおよび帯域需要とを含んで構成されている。ヘッダは、Ｈｅｌｌｏフレームの宛先情報、送信元情報、フレーム種別情報などにより構成されている。宛先情報は、フレームを受信する装置のＭＡＣアドレスである。送信元情報は、フレームを送信した装置のＭＡＣアドレスである。フレーム種別情報は、受信したフレームの種別を示し、Ｈｅｌｌｏフレームの場合はＨｅｌｌｏフレームを一意に示す値が設定される。フレームがＨｅｌｌｏフレームではない場合、フレーム種別情報の値は別の値となる。フレーム処理部２８は、フレーム種別情報を確認することにより、受信したフレームがＨｅｌｌｏフレームか否かを判別できる。隣接ノード情報を構成している識別情報は、隣接ノードの識別情報であり、例えばＭＡＣアドレスである。隣接ノード情報を構成している属性情報は、隣接ノードがＥｘｐｒｅｓｓノードとベストエフォートノードのどちらに該当するかを示す情報である。通信相手ノードは、隣接ノードがフレームを送受信する相手のノードを示す情報（以下、通信相手ノード情報）である。帯域需要は、隣接ノードがベストエフォートノードである場合、すなわち、属性情報がベストエフォートノードを示している場合に含まれる情報である。帯域需要は、隣接ノードが必要としている帯域の情報（以下、ベストエフォートトラフィックの帯域需要）である。その他の情報をＨｅｌｌｏフレームに格納するようにしてもよい。識別情報はＭＡＣアドレス以外であってもよい。識別情報は隣接ノードを一意に示すものであればよい。図５に示した構成のＨｅｌｌｏフレームは、メッシュネットワークに接続している各ノードから定期的に送信される。
【００２３】
フレーム処理部２８の動作説明に戻り、フレーム処理部２８は、受信部２１から受け取ったフレームがＨｅｌｌｏフレームではない場合（ステップＳ１２：Ｎｏ）、他のスイッチから広告されたフレームか否かを確認する（ステップＳ１３）。フレーム処理部２８は、受信部２１から受け取ったフレームが他のスイッチから広告されたフレームではない場合（ステップＳ１３：Ｎｏ）、受信部２１から受け取ったフレームをカプセリング部３４へ出力する。フレーム処理部２８は、受信部２１から受け取ったフレームが他のスイッチから広告されたフレームの場合（ステップＳ１３：Ｙｅｓ）、隣接ノード情報が格納されているか否かを確認する（ステップＳ１５）。フレーム処理部２８は、受信部２１から受け取ったフレームに隣接ノード情報が格納されている場合（ステップＳ１５：Ｙｅｓ）、受信部２１から受け取ったフレームをカプセリング部３４およびノード情報収集部３０へ出力する（ステップＳ１７）。フレーム処理部２８は、受信部２１から受け取ったフレームに隣接ノード情報が格納されていない場合（ステップＳ１５：Ｎｏ）、受信部２１から受け取ったフレームをカプセリング部３４へ出力する（ステップＳ１６）。
【００２４】
なお、他のスイッチ２から広告されたフレームに格納されている隣接ノード情報は、フレームを公告した他のスイッチ２が、図５に示した構成のＨｅｌｌｏフレームを使用して隣接ノードから収集した情報である。例えばフレーム処理部２８が、図１のスイッチ２1が広告したフレームを受け取り、受け取ったフレームに隣接ノード情報が格納されている場合、受け取ったフレームに格納されている隣接ノード情報は、スイッチ２1がベストエフォートノード１1、Ｅｘｐｒｅｓｓノード３1，４1から収集した隣接ノード情報である。すなわち、このフレームに格納されている隣接ノード情報は、ベストエフォートノード１1、Ｅｘｐｒｅｓｓノード３1，４1がＨｅｌｌｏフレームにて送信した隣接ノード情報である。
【００２５】
隣接ノード情報収集手段である隣接ノード情報収集部２９は、図６に示したフローチャートに従って動作する。具体的には、隣接ノード情報収集部２９は、フレーム処理部２８からＨｅｌｌｏフレームを受信したか否かを継続的に監視している（ステップＳ２１）。隣接ノード情報収集部２９は、Ｈｅｌｌｏフレームを受信した場合（ステップＳ２１：Ｙｅｓ）、すなわち、フレーム処理部２８からＨｅｌｌｏフレームを受け取ると、Ｈｅｌｌｏフレームに格納されている隣接ノード情報を収集し（ステップＳ２２）、取り出した隣接ノード情報を隣接ノード情報広告部２４およびネットワークトポロジー情報管理部３１へ出力する（ステップＳ２３）。
【００２６】
隣接ノード情報広告手段である隣接ノード情報広告部２４は、図７に示したフローチャートに従って動作する。具体的には、隣接ノード情報広告部２４は、隣接ノード情報収集部２９から隣接ノード情報を受信したか否かを継続的に監視している（ステップＳ３１）。隣接ノード情報広告部２４は、隣接ノード情報を受信した場合（ステップＳ３１：Ｙｅｓ）、すなわち、隣接ノード情報収集部２９から隣接ノード情報を受け取ると、受け取った隣接ノード情報および自スイッチの識別情報が格納されたフレームを生成し（ステップＳ３２）、生成したフレームを送信部２２を介してメッシュネットワーク内に広告する（ステップＳ３３）。自スイッチの識別情報はＭＡＣアドレスとするが、これに限定するものではない。自スイッチの識別情報は広告されたフレームの受信側でフレームの広告元が認識できるのであればどのような識別情報であってもよい。自スイッチの識別情報としてＭＡＣアドレスを使用する場合、広告するフレームのヘッダにはフレーム送信元の情報としてＭＡＣアドレスが格納されているため、自装置の識別情報として別途ＭＡＣアドレスをフレームに格納しなくてもよい。すなわち、ヘッダ内のフレーム送信元情報と自装置の識別情報とを兼用してもよい。
【００２７】
ノード情報収集部３０は、図８に示したフローチャートに従って動作する。具体的には、ノード情報収集部３０は、他のスイッチから広告されたフレームをフレーム処理部２８から受信したか否かを継続的に監視している（ステップＳ４１：Ｎｏ）。ノード情報収集部３０は、他のスイッチから広告されたフレームを受信した場合（ステップＳ４１：Ｙｅｓ）、すなわち、フレーム処理部２８からフレームを受け取ると、受け取ったフレームに格納されている隣接ノード情報およびフレーム送信元のスイッチ２の識別情報を取り出し（ステップＳ４２）、取り出した隣接ノード情報およびフレーム送信元のスイッチ２の識別情報をネットワークトポロジー情報管理部３１へ出力する（ステップＳ４３）。ここで、ノード情報収集部３０がフレーム処理部２８から受け取ったフレームに格納されている隣接ノード情報は、受け取ったフレームの送信元のスイッチ２に隣接しているノードの隣接ノード情報である。例えば、ノード情報収集部３０が受け取ったフレームの送信元が図１のスイッチ２1の場合、受け取ったフレームに格納されている隣接ノード情報は、ベストエフォートノード１1がＨｅｌｌｏフレームにてスイッチ２1へ送信した隣接ノード情報、Ｅｘｐｒｅｓｓノード３1がＨｅｌｌｏフレームにてスイッチ２1へ送信した隣接ノード情報およびＥｘｐｒｅｓｓノード４1がＨｅｌｌｏフレームにてスイッチ２1へ送信した隣接ノード情報となる。なお、ノード情報収集部３０は、送信元がスイッチ２1のフレームを受け取った場合、ベストエフォートノード１1の隣接ノード情報、Ｅｘｐｒｅｓｓノード３1の隣接ノード情報、Ｅｘｐｒｅｓｓノード４1の隣接ノード情報およびスイッチ２1の識別情報を取り出し、取り出した各隣接ノード情報および識別情報をネットワークトポロジー情報管理部３１へ出力する。ネットワークトポロジー情報管理部３１は、ベストエフォートノード１1の隣接ノード情報、Ｅｘｐｒｅｓｓノード３1の隣接ノード情報、Ｅｘｐｒｅｓｓノード４1の隣接ノード情報およびスイッチ２1の識別情報を受け取った場合、スイッチ２1の隣接ノードがベストエフォートノード１1、Ｅｘｐｒｅｓｓノード３1および４1であることを把握する。すなわち、ネットワークトポロジー情報管理部３１は、スイッチ２1に対してベストエフォートノード１1、Ｅｘｐｒｅｓｓノード３1および４1が接続されていることを把握する。スイッチ２1が送信元のフレームを受け取った場合について説明したが、スイッチ２1以外が送信元のフレームを受け取った場合も同様である。
【００２８】
ネットワークトポロジー情報管理部３１は、メッシュネットワークを構成している各スイッチ２の識別情報と、メッシュネットワークを構成している各スイッチ２が隣接ノードから収集し、メッシュネットワーク内へ広告した隣接ノード情報と、を保持している。また、ネットワークトポロジー情報管理部３１は、ＳＰＢのルーティングプロトコルであるＩＳ−ＩＳ（Intermediate  System  to  Intermediate  System）によって収集したネットワークのトポロジー情報、すなわち、どのスイッチ２とどのスイッチ２の間でリンクが確立しているかを示す情報を保持している。また、すでに説明したように、隣接ノード情報には、隣接ノードの識別情報、隣接ノードの属性情報、隣接ノードの通信相手ノード情報、ベストエフォートノードが必要としている帯域を示すベストエフォートトラフィックの帯域需要が含まれているため、ネットワークトポロジー情報管理部３１は、ネットワークのトポロジー情報に加えて、各スイッチ２に接続している各ノードの属性情報、どのノード同士が通信を行うか、すわなち、どのノードの間でパスを設定する必要があるかを示す情報も保持していることになる。また、ベストエフォートトラフィックを送受信する各ノードの帯域需要（ベストエフォートトラフィックの帯域需要）も保持している。
【００２９】
低遅延転送用パス決定手段であるＥｘｐｒｅｓｓトラフィックパス決定部３３は、図９に示したフローチャートに従ってＥｘｐｒｅｓｓトラフィックパスを決定する。具体的には、Ｅｘｐｒｅｓｓトラフィックパス決定部３３は、Ｅｘｐｒｅｓｓトラフィックパスの決定処理の開始条件を満足したか否かを継続的に監視している（ステップＳ５１）。ここで、処理の開始条件とは、例えば、前回Ｅｘｐｒｅｓｓトラフィックパスを決定してから規定時間が経過した場合、ユーザが処理開始を指示する操作を行った場合、自スイッチに対して新しいノードが接続した場合、自スイッチとともにメッシュネットワークを形成している他のスイッチに新しいノードが接続されたことを検出した場合、などが考えられる。Ｅｘｐｒｅｓｓトラフィックパスの決定処理の開始条件を満足した場合（ステップＳ５１：Ｙｅｓ）、Ｅｘｐｒｅｓｓトラフィックパス決定部３３は、ネットワークトポロジー情報管理部３１が保持している、ネットワークのトポロジー情報および隣接ノード情報を読み出す（ステップＳ５２）。次に、Ｅｘｐｒｅｓｓトラフィックパス決定部３３は、読み出した情報、具体的には、ネットワークのトポロジー情報と、各スイッチ２に接続している各ノードの隣接ノード情報のうち、属性情報、および通信相手先情報と、に基づいて、Ｅｘｐｒｅｓｓノードが接続されているスイッチ２の間でＥｘｐｒｅｓｓトラフィックを転送する場合のパスを仮決定する（ステップＳ５３）。このステップＳ５３で仮決定するパスをＥｘｐｒｅｓｓトラフィックパスと呼ぶ。ステップＳ５３において、Ｅｘｐｒｅｓｓトラフィックパス決定部３３は、メッシュネットワークを構成しているリンクの各々について、Ｅｘｐｒｅｓｓトラフィックパスを複数設定する場合にＥｘｐｒｅｓｓトラフィックパスで重複使用される回数が少なくなるよう、各Ｅｘｐｒｅｓｓトラフィックパスを仮決定する。具体的には、Ｅｘｐｒｅｓｓトラフィックパス決定部３３は、ネットワーク内の各Ｅｘｐｒｅｓｓトラフィックパスが使用するリンクの重なりが最大となるリンクの重なりが最小となるように線形計画問題を解くことにより、各Ｅｘｐｒｅｓｓトラフィックパスを仮決定する。Ｅｘｐｒｅｓｓトラフィックパス決定部３３は、仮決定した各Ｅｘｐｒｅｓｓトラフィックパスの情報をリンクメトリック決定部３２へ出力する（ステップＳ５４）。Ｅｘｐｒｅｓｓトラフィックパスの情報は、Ｅｘｐｒｅｓｓトラフィックを送受信するＥｘｐｒｅｓｓノードの識別情報と、Ｅｘｐｒｅｓｓトラフィックパスを構成するスイッチ２すなわちＥｘｐｒｅｓｓトラフィックを中継するスイッチ２の識別情報とを含んで構成される。仮に、図１に示したＥｘｐｒｅｓｓノード３1とＥｘｐｒｅｓｓノード３2との間で送受信するＥｘｐｒｅｓｓトラフィックを送受信するためのＥｘｐｒｅｓｓトラフィックパスがスイッチ２1、スイッチ２2、スイッチ２5およびスイッチ２7により構成されている場合のＥｘｐｒｅｓｓトラフィックパスの情報は、例えば、以下のようにできる。「Ｅｘｐｒｅｓｓトラフィックパスの情報＝Ｅｘｐｒｅｓｓノード３1の識別情報＋スイッチ２1の識別情報＋スイッチ２2の識別情報＋スイッチ２5の識別情報＋スイッチ２7の識別情報＋���ｘｐｒｅｓｓノード３2の識別情報」この情報を受信したリンクメトリック決定部３２は、Ｅｘｐｒｅｓｓノード３1とＥｘｐｒｅｓｓノード３2との間のＥｘｐｒｅｓｓトラフィックパスがスイッチ２1、スイッチ２2、スイッチ２5およびスイッチ２7により構成されていることを把握できる。
【００３０】
リンクメトリック決定手段であるリンクメトリック決定部３２は、図１０に示したフローチャートに従い、メッシュネットワーク内の各リンクのリンクメトリックを決定する。具体的には、リンクメトリック決定部３２は、Ｅｘｐｒｅｓｓトラフィックパス決定部３３からＥｘｐｒｅｓｓトラフィックパスの情報を受信したか否かを継続的に監視している（ステップＳ６１）。リンクメトリック決定部３２は、Ｅｘｐｒｅｓｓトラフィックパスの情報を受信した場合（ステップＳ６１：Ｙｅｓ）、ネットワークトポロジー情報管理部３１が保持しているネットワークのトポロジー情報およびベストエフォートトラフィックの帯域需要の情報を読み出す（ステップＳ６２）。次に、リンクメトリック決定部３２は、ネットワークトポロジー情報管理部３１から読み出したネットワークのトポロジー情報およびベストエフォートトラフィックの帯域需要の情報と、Ｅｘｐｒｅｓｓトラフィックパス決定部３３から受け取った、各Ｅｘｐｒｅｓｓトラフィックパスの情報と、に基づき、メッシュネットワーク内の各リンクのリンクメトリックを決定する（ステップＳ６３）。具体的には、リンクメトリック決定部３２は、各リンクについて、Ｅｘｐｒｅｓｓトラフィックの数に１を加算した数のリンクメトリックを決定する。ここで、Ｅｘｐｒｅｓｓトラフィックの数とは、Ｅｘｐｒｅｓｓトラフィックを送受信するＥｘｐｒｅｓｓノードの組み合わせの数である。リンクメトリック決定部３２は、Ｅｘｐｒｅｓｓトラフィックパス決定部３３から受け取った、各Ｅｘｐｒｅｓｓトラフィックパスの情報を確認することによりＥｘｐｒｅｓｓトラフィックの数をカウントし、Ｅｘｐｒｅｓｓトラフィックの数に１を加算した数のリンクメトリックを決定する必要があると判断する。本実施の形態では、図１の構成を想定しているため、Ｅｘｐｒｅｓｓトラフィックの数は２となる。すなわち、リンクメトリック決定部３２は、３つのリンクメトリックを決定する必要があると判断する。リンクメトリックは、ルーティングプロトコルを使用してノード間の通信経路であるトラフィックパスを決定する際に必要な情報である。
【００３１】
リンクメトリック決定部３２は、各Ｅｘｐｒｅｓｓトラフィックにはトラフィックごとに一つのリンクメトリックすなわち第１のリンクメトリックを割り当て、ベストエフォートトラフィックにはベストエフォートトラフィック全体で一つのリンクメトリックすなわち第２のリンクメトリックを割り当てる。リンクメトリック決定部３２は、これらのリンクメトリックに基づいてＳＰＢで最短経路を計算したときに各Ｅｘｐｒｅｓｓトラフィックおよびベストエフォートトラフィックが所望のパスで転送されるように、具体的には、Ｅｘｐｒｅｓｓトラフィックの競合が発生する頻度が低くなるよう、リンクメトリックを決定する。このように、リンクメトリック決定部３２は、従来は一つのリンクに対して一つのリンクメトリックを決定していたのに対し、一つリンクに対して複数のリンクメトリックを決定する。リンクメトリック決定部がリンクメトリックを決定する動作の詳細については後述する。リンクメトリック決定部３２を拡張リンクメトリックと呼ぶ。リンクメトリック決定部３２は、決定したリンクメトリックをＳＰＢ処理部２７へ出力する（ステップ６４）。なお、リンクメトリック決定部３２は、Ｅｘｐｒｅｓｓトラフィックパス決定部３３とともに決定手段を構成する。
【００３２】
ＳＰＢ処理部２７は、図１１に示したフローチャートに従い、メッシュネットワークを介してフレームを送受信する各ノード間のフレーム転送経路を決定する。具体的には、ＳＰＢ処理部２７は、リンクメトリック決定部からリンクメトリックを受信したか否かを継続的に監視している（ステップＳ７１）。ＳＰＢ処理部２７は、リンクメトリックを受信した場合（ステップＳ７１：Ｙｅｓ）、ネットワークのトポロジー情報をネットワークトポロジー情報管理部３１から読み出す（ステップＳ７２）。次に、ＳＰＢ処理部２７は、読み出したトポロジー情報とリンクメトリック決定部３２から受け取った各リンクのリンクメトリックとに基づき、ＳＰＢを使用して、各ノードが送受信するフレームの最短経路を計算する（ステップＳ７３）。リンクメトリック決定部３２から受け取った各リンクのリンクメトリックとは、上述した、Ｅｘｐｒｅｓｓトラフィックの数に１を加算した数のリンクメトリック、すなわち、一つのリンクのリンクメトリックを複数に拡張したリンクメトリックである。次に、ＳＰＢ処理部２７は、最短経路の計算結果に基づき、受信したフレームを自スイッチのどのポートに転送するか、すなわち、ノード間で送受信されるフレームの出力ポートを決定する（ステップＳ７４）。具体的には、ＳＰＢ処理部２７は、決定した各最短経路上の次のスイッチ２またはノードが接続されているポートを受信したフレームの転送先に決定する。ＳＰＢ処理部２７は、受信したフレームの転送先のポートを決定すると、決定結果を転送データベース２６へ出力する（ステップＳ７５）。
【００３３】
カプセリング部３４は、図１２に示したフローチャートに従って動作する。具体的には、カプセリング部３４は、フレーム処理部２８からフレームを受信したか否かを継続的に監視している（ステップＳ８１）。カプセリング部３４は、フレームを受信した場合（ステップＳ８１：Ｙｅｓ）、他のスイッチ２から広告されたフレームか否かを確認する（ステップＳ８２）。カプセリング部は、フレームの送信元が他のスイッチ２、かつフレームの宛先がブロードキャスト用のアドレスの場合、他のスイッチから広告されたフレームと判断する。フレーム処理部２８から受け取ったフレームが他のスイッチ２から広告されたフレームの場合（ステップＳ８２：Ｙｅｓ）、そのままフレーム転送部２５へ出力する（ステップＳ８８）。また、カプセリング部３４は、フレーム処理部２８から受け取ったフレームが他のスイッチ２から広告されたフレームではない場合（ステップＳ８２：Ｎｏ）、受け取ったフレームが自スイッチの隣接ノード宛てのフレームか否かを確認する（ステップＳ８３）。受け取ったフレームが自スイッチの隣接ノード宛の場合（ステップＳ８３：Ｙｅｓ）、フレームはメッシュネットワーク内での転送用のヘッダが他のスイッチ２により付加された状態、すなわちカプセル化された状態であるため、他のスイッチ２により付加されたヘッダを取り外すデカプセリングを行い（ステップＳ８６）、フレーム転送部２５に出力する（ステップＳ８７）。一方、受け取ったフレームが自スイッチの隣接ノード宛ではない場合（ステップＳ８３：Ｎｏ）、受け取ったフレームの送信元が自スイッチの隣接ノードか否かを確認する(ステップＳ８４）。受け取ったフレームの送信元が自スイッチの隣接ノードである場合（ステップＳ８４：Ｙｅｓ）、カプセリング部３４は、受け取ったフレームに対してメッシュネットワーク内での転送用のヘッダを付加する処理、すなわちカプセリングを行い（ステップＳ８６）、フレーム転送部２５に出力する（ステップＳ８７）。また、カプセリング部３４は、フレーム処理部２８から受け取ったフレームの送信元が自スイッチの隣接ノードではない場合（ステップＳ８４：Ｎｏ）、フレームに対して何も処理を行わず、フレーム転送部２５に出力する（ステップＳ８７）。
【００３４】
なお、上記ステップＳ８６のカプセリング処理において、カプセリング部３４は、隣接ノードが送信元のフレームに対して、送信元に自スイッチのＭＡＣアドレスを設定し、かつ宛先にはフレームの宛先のノードが接続されているスイッチのＭＡＣアドレスを設定したヘッダを付加する。また、上記ステップＳ８５のデカプセリング処理において、カプセリング部３４は、フレームに付加されているヘッダ、すなわち、自スイッチのＭＡＣアドレスが宛先に設定されているヘッダ取り外し、ヘッダが付加される前の元のフレームに戻す。
【００３５】
フレーム転送部２５は、図１３に示したフローチャートに従って動作する。具体的には、フレーム転送部２５は、カプセリング部３４からフレームを受信したか否かを継続的に監視している（ステップＳ９１）。フレーム転送部２５は、フレームを受信した場合（ステップＳ９１：Ｙｅｓ）、すなわち、カプセリング部３４からフレームを受け取ると、転送データベース２６からフレームの転送先の情報を読み出し（ステップＳ９２）、カプセリング部３４から受け取ったフレームの転送先を決定する。そして、フレーム転送部２５は、カプセリング部３４から受け取ったフレームを転送先に向けて、送信部２２を介して転送する（ステップＳ９３）。
【００３６】
Ｈｅｌｌｏ生成部２３は、図１４に示したフローチャートに従い、Ｈｅｌｌｏフレームを送信する。具体的には、Ｈｅｌｌｏ生成部２３は、規定時間が経過したか否かを継続的に監視している（ステップＳ１０１）。このステップＳ１０１では、Ｈｅｌｌｏ生成部２３は、前回Ｈｅｌｌｏフレームを生成してから規定時間経過したか否かを確認する。Ｈｅｌｌｏ生成部２３は、規定時間が経過した場合（ステップＳ１０１：Ｙｅｓ）、Ｈｅｌｌｏフレームを作成し（ステップ）、送信部２２を介してメッシュネットワーク内へ送信する（ステップＳ１０３）。このとき、Ｈｅｌｌｏ生成部２３は、Ｈｅｌｌｏフレームの宛先にブロードキャスト用のＭＡＣアドレスを設定する。
【００３７】
つづいて、図１に示した実施の形態１のメッシュネットワークにおいてスイッチ２がリンクメトリックを決定し、決定したリンクメトリックに基づいてノード間のパスを決定する手順について説明する。
【００３８】
図１５は、実施の形態１のスイッチ２がメッシュネットワークに接続しているノード間のパスを決定する手順を示す図である。各スイッチ２は、以下で説明する手順＃１−１〜手順＃１−４を実行することにより、通信を行う各ノード間のパスを決定する。ここでは、図１に示した構成のメッシュネットワークにおいて、スイッチ２1〜２7が、ベストエフォートノード１1，１2，１3，１4、Ｅｘｐｒｅｓｓノード３1，３2，４1，４2の各々についてのパスを決定する動作について説明する。
【００３９】
＜手順＃１−１＞
メッシュネットワークを構成しているスイッチ２1〜２7は、隣接ノードとの間でＨｅｌｌｏフレーム５1〜５8を送受信し、隣接ノードから各種情報を収集する。ここで、Ｈｅｌｌｏフレーム５1〜５8は各隣接ノードから情報を収集できれば良く、ＬＬＤＰ（Link  Layer  Discovery  Protocol）などのプロトコルによって生成されるＨｅｌｌｏフレームを使用することが可能である。収集する情報は、隣接ノードの識別情報であるＭＡＣアドレス、隣接ノードがＥｘｐｒｅｓｓノードとベストエフォートノードのどちらに該当するのかを示す属性情報、各隣接ノードがフレームの送受信を行う相手ノードの情報（通信相手ノード情報）、などである。隣接ノードがベストエフォートノードの場合には、帯域需要の情報も併せて収集する。具体的な動作を説明すると、各スイッチ２は、自スイッチの識別情報であるＭＡＣアドレスを格納したＨｅｌｌｏフレームをブロードキャストする。一方、ベストエフォートノード１1、１2、１3および１4は、自ノードのＭＡＣアドレス、自ノードがベストエフォートノードであることを示す属性情報、通信相手ノード情報、帯域需要の情報、などを格納したＨｅｌｌｏフレームをブロードキャストする。Ｅｘｐｒｅｓｓトラフィックノード３1、３2、４1および４2は、自ノードのＭＡＣアドレス、自ノードがＥｘｐｒｅｓｓノードであることを示す属性情報、通信相手ノード情報、などを格納したＨｅｌｌｏフレームをブロードキャストする。各スイッチ２は、隣接ノードが送信したＨｅｌｌｏフレームを受信し、Ｈｅｌｌｏフレームから各種情報を取り出すことにより、隣接ノードのＭＡＣアドレス、属性情報、通信相手ノード情報、帯域需要の情報、などを収集する。各スイッチ２が隣接ノードから収集した各種情報は隣接ノード情報である。
【００４０】
スイッチ２1〜２7においては、Ｈｅｌｌｏ生成部２３が、Ｈｅｌｌｏフレームを生成してブロードキャストする。また、隣接ノード情報収集部２９が、隣接ノードから受信したＨｅｌｌｏフレームをフレーム処理部２８から受け取り、受け取ったＨｅｌｌｏフレームから隣接ノード情報を取り出す。
【００４１】
Ｈｅｌｌｏフレームの送受信を実行して各隣接ノードから隣接ノード情報を収集したスイッチ２1〜２7は、次に、自スイッチのＭＡＣアドレスと、各隣接ノードから収集した隣接ノード情報とを他のスイッチ２へ広告する。この処理は隣接ノード情報広告部２４が行う。スイッチ２1〜２7の隣接ノード情報広告部２４が自スイッチのＭＡＣアドレスおよび隣接ノードから収集した隣接ノード情報をメッシュネットワーク内へ広告する際に使用するフレームは、図１６に示した構成となる。図１６は、スイッチ２1〜２7が他のスイッチ２、すなわちメッシュネットワーク内へ広告するフレームの構成例を示す図である。スイッチ２1〜２7が隣接ノード情報を広告する際に使用するフレーム（以下、隣接ノード情報広告用フレーム）は、ヘッダ、自装置識別情報、隣接ノード情報＃１，＃２，＃３…を含んで構成されている。ヘッダは、フレームの宛先情報、送信元情報、フレーム種別情報などにより構成されている。自装置識別情報には自装置のＭＡＣアドレスを設定こととするが、これに限定されない。装置を一意に示す情報であればよい。隣接ノード情報＃１，＃２，＃３，…には、隣接ノードから収集した隣接ノード情報を格納する。例えば、スイッチ２1が隣接ノード情報広告用フレームを送信する場合、スイッチ２1は、自スイッチのＭＡＣアドレスを自装置識別情報に設定し、ベストエフォートノード１1から収集した隣接ノード情報を隣接ノード情報＃１に設定し、Ｅｘｐｒｅｓｓノード３1から収集した隣接ノード情報を隣接ノード情報＃２に設定し、Ｅｘｐｒｅｓｓノード４1から収集した隣接ノード情報を隣接ノード情報＃３に設定したフレームを生成してスイッチ２2〜２7へ送信する。なお、隣接ノード情報広告用フレームに隣接ノード情報を格納する順番はこれに限定されない。ここで、スイッチ２1〜２7は、ＩＥＥＥ８０２．１ａｑで標準化されているＳＰＢのルーティングプロトコルであるＩＳ−ＩＳを実行済みであり、ネットワークのトポロジー情報を保持しているものとする。
【００４２】
また、スイッチ２1〜２7は、他のスイッチ２から広告された隣接ノード情報広告用フレームを受信すると、他のスイッチ２へ転送するとともに、受信した隣接ノード情報広告用フレームから隣接ノード情報を取出して保持しておく。スイッチ２1〜２7において、隣接ノード情報広告用フレームを他のスイッチ２へ転送する処理はフレーム転送部２５が行う。隣接ノード情報広告用フレームから隣接ノード情報を取り出す処理はノード情報収集部３０が行う。隣接ノード情報およびネットワークのトポロジー情報は、ネットワークトポロジー情報管理部３１が保持する。なお、ネットワークトポロジー情報管理部３１は、隣接ノード情報を受け取ると、ネットワーク内のどのスイッチ間でＥｘｐｒｅｓｓトラフィックが転送されるのかを示す情報と、ネットワーク内のどのスイッチ間でベストエフォートトラフィックが転送されるのかを示す情報とを生成して管理する。
【００４３】
＜手順＃１−２＞
次に、スイッチ２1〜２7は、Ｅｘｐｒｅｓｓトラフィックのパスを決定する。具体的には、スイッチ２1〜２7は、Ｅｘｐｒｅｓｓトラフィックのパスで使用するリンクの重なりが最小となるように線形計画問題を解くことにより、Ｅｘｐｒｅｓｓトラフィックのパスを仮決定する。これにより、メッシュネットワークを構成しているリンクの各々について、Ｅｘｐｒｅｓｓトラフィックパスで重複使用される回数が少なくなり、Ｅｘｐｒｅｓｓトラフィックがスイッチ２1〜２7において競合する頻度を低く抑えることができる。スイッチ２1〜２7は、例えば、図１５に示したように、第１のＥｘｐｒｅｓｓノードペアであるＥｘｐｒｅｓｓノード３1とＥｘｐｒｅｓｓノード３2の間のパスはパス６2に仮決定し、第２のＥｘｐｒｅｓｓノードペアであるＥｘｐｒｅｓｓノード４1とＥｘｐｒｅｓｓノード４2の間のパスはパス６1に仮決定する。
【００４４】
スイッチ２1〜２7においては、Ｅｘｐｒｅｓｓトラフィックパス決定部３３が、ネットワークトポロジー情報管理部３１で保持されている情報、すなわち、ネットワークのトポロジー情報とネットワーク内のどのスイッチ間でＥｘｐｒｅｓｓトラフィックが転送されるのかを示す情報とに基づいて上記の線形計画問題を解くことにより、Ｅｘｐｒｅｓｓトラフィックのパスを仮決定する。なお、スイッチ２1〜２7は、上述した手順＃１−１を実行することにより、隣接ノードから取得した隣接ノード情報を交換している。すなわち、スイッチ２1〜２7は、同じ情報を保持した状態となっている。そのため、スイッチ２1〜２7の各Ｅｘｐｒｅｓｓトラフィックパス決定部３３は、同じ情報を使用して同じアルゴリズムでＥｘｐｒｅｓｓトラフィックのパスを仮決定することになる。したがって、スイッチ２1〜２7の各Ｅｘｐｒｅｓｓトラフィックパス決定部３３で決定されるＥｘｐｒｅｓｓトラフィックのパスは同一となる。
【００４５】
＜手順＃１−３＞
次に、スイッチ２1〜２7は、ネットワーク内の各リンクのリンクメトリックを決定する。リンクメトリックは通常１つであるが、本実施の形態ではＥｘｐｒｅｓｓノードペアの数に１を加算した数のリンクメトリックを決定する。
【００４６】
図１に示したメッシュネットワークでは、Ｅｘｐｒｅｓｓノード３1と３2がＥｘｐｒｅｓｓトラフィックを送受信し、また、Ｅｘｐｒｅｓｓノード４1と４2がＥｘｐｒｅｓｓトラフィックを送受信するため、Ｅｘｐｒｅｓｓノードペアの数は２である。よって、各リンクのリンクメトリックの数を３に拡張する。各リンクのリンクメトリックの１つ目は、第１のＥｘｐｒｅｓｓノードペアであるＥｘｐｒｅｓｓノード３1とＥｘｐｒｅｓｓノード３2の間のパスを決定するために使用し、リンクメトリックの２つ目は、第２のＥｘｐｒｅｓｓノードペアであるＥｘｐｒｅｓｓノード４1とＥｘｐｒｅｓｓノード４2の間のパスを決定するために使用し、リンクメトリックの３つ目はベストエフォートトラフィックのパスを決定するために使用する。図１５では、リンクメトリックを“（Ａ，Ｂ，Ｃ）”という形式で表現している。“Ａ”の位置に記載された数値を１つ目のリンクメトリック、“Ｂ”の位置に記載された数値を２つ目のリンクメトリック、“Ｃ”の位置に記載された数値を３つ目のリンクメトリックとする。
【００４７】
スイッチ２1〜２7は、各リンクのリンクメトリック７1〜７9の１つ目のリンクメトリックについて、ＳＰＢで最短経路を計算した場合に手順＃１−２で決定した第１のＥｘｐｒｅｓｓノードペアであるＥｘｐｒｅｓｓノード３1とＥｘｐｒｅｓｓノード３2の間のパスがパス６2となり、かつ、このパス６2のパスコストが他のリンクのリンクメトリックより小さくなるように決定する。ここで、「他のリンクのリンクメトリック」は、パス６2を構成していないリンクの各々の１つ目のリンクメトリックを示す。図１５に示した例では、パス６2のパスコストが「３」となるため、パス６2を構成していないリンクである他のリンクの１つ目のリンクメトリックを「３」よりも大きな値、例えば「４」に決定する。リンクメトリックが満たすべき条件は、以下の式（１）で表すことができる。
【００４８】
【数１】
0006265930.tif 000002
【００４９】
上記の式（１）において、ｘimはリンクｉのｍ番目のリンクメトリック、ｘkmはリンクｋのｍ番目のリンクメトリック、Ｘは第ｍのＥｘｐｒｅｓｓノードペアの間のパスが使用するリンクの集合、Ｙはネットワーク内のＸ以外のリンクの集合を示す。
【００５０】
スイッチ２1〜２7は、各リンクのリンクメトリック７1〜７9の２つ目のリンクメトリックについて、１つ目のリンクメトリックと同様の方法で決定する。すなわち、ＳＰＢにて最短経路を計算した場合に手順＃１−２で決定した第２のＥｘｐｒｅｓｓノードペアであるノード４1とノード４2の間のパスがパス６1となり、かつ、このパス６1のパスコストが他のリンクのリンクメトリックより小さくなるように決定する。
【００５１】
スイッチ２1〜２7は、各リンクのリンクメトリック７1〜７9の３つ目のリンクメトリックについて、ベストエフォートトラフィックのロードバランシングが実現できるように決定する。例えば、非特許文献１で開示されている方法、具体的には、全リンクの使用率の最大値が最小となるように線形計画問題を解くことにより、各リンクの３つ目のリンクメトリックを決定する。その他の決定方法としては、リンク帯域の逆数をリンクメトリックに決定する、などが考えられる。各リンクのリンクメトリック７1〜７9の３つ目のリンクメトリックを決定する方法は、ベストエフォートトラフィックのロードバランシングが実現可能なリンクメトリックが得られるのであれば、どのような方法でも構わない。
【００５２】
スイッチ２1〜２7においては、リンクメトリック決定部３２が、ネットワークトポロジー情報管理部３１で保持されている情報およびＥｘｐｒｅｓｓトラフィックパス決定部３３で決定されたＥｘｐｒｅｓｓトラフィックパスの情報に基づいて、各リンクのリンクメトリックを決定する。
【００５３】
＜手順＃１−４＞
次に、スイッチ２1〜２7は、ＳＰＢを用いて各ノード間のパスを決定する。具体的には、スイッチ２1〜２7は、各リンクの１つ目のリンクメトリックを用いて、第１のＥｘｐｒｅｓｓノードペアであるＥｘｐｒｅｓｓノード３1と３2の間のパスを、最短経路となるように決定する。図１５の例ではパス８に決定する（手順＃１−４（１））。また、スイッチ２1〜２7は、各リンクの２つ目のリンクメトリックを用いて、第２のＥｘｐｒｅｓｓノードペアであるＥｘｐｒｅｓｓノード４1と４2の間のパスを、最短経路となるように決定する。図１５の例ではパス９に決定する（手順＃１−４（２））。また、スイッチ２1〜２7は、各リンクの３つ目のリンクメトリックを用いて、ベストエフォートノード間のパスを、最短経路となるように決定する（手順＃１−４（３））。
【００５４】
スイッチ２1〜２7においては、ＳＰＢ処理部２７が、ネットワークトポロジー情報管理部３１で保持されている情報と、リンクメトリック決定部３２が決定したリンクメトリックとに基づいて、各ノード間のパスを決定する。
【００５５】
なお、本実施の形態では、Ｅｘｐｒｅｓｓノードが１対１でフレームの送受信を行う場合について説明したが、１対多もしくは多対多でフレームの送受を行うようにしてもよい。この場合、各リンクのリンクメトリックとして、フレームの送受信を行うＥｘｐｒｅｓｓノードの組み合わせの数に１を加えた数のリンクメトリックを決定する。例えば、メッシュネットワークにおいて、ノードＮ１がノードＮ２〜Ｎ５との間でＥｘｐｒｅｓｓトラフィックのフレームを送受信する場合、スイッチ２は、ノードＮ１とノードＮ２の間のパスを決定するためのリンクメトリック、ノードＮ１とノードＮ３の間のパスを決定するためのリンクメトリック、ノードＮ１とノードＮ４の間のパスを決定するためのリンクメトリック、ノードＮ１とノードＮ５の間のパスを決定するためのリンクメトリック、ベストエフォートトラフィックのパスを決定するためのリンクメトリック、を決定する。また、ノードＮ１およびＮ２がノードＮ３およびＮ４との間でＥｘｐｒｅｓｓトラフィックのフレームを送受信する場合、スイッチ２は、ノードＮ１とノードＮ３の間のパスを決定するためのリンクメトリック、ノードＮ１とノードＮ４の間のパスを決定するためのリンクメトリック、ノードＮ２とノードＮ３の間のパスを決定するためのリンクメトリック、ノードＮ２とノードＮ４の間のパスを決定するためのリンクメトリック、ベストエフォートトラフィックのパスを決定するためのリンクメトリック、を決定する。
【００５６】
このように、本実施の形態のスイッチ２は、メッシュネットワークに接続している各ノードから、Ｅｘｐｒｅｓｓノードとベストエフォートノードのどちらに該当するかを示す属性情報と、フレームを送受信する相手のノードを示す通信相手ノード情報と、を収集し、収集した情報に基づいて、まず、Ｅｘｐｒｅｓｓトラフィックを送受信するＥｘｐｒｅｓｓノードの間のパスを、パスを構成しているリンクの重なりが最小となるように決定し、決定したパスのパスコスト基づいて、Ｅｘｐｒｅｓｓトラフィックを送受信するＥｘｐｒｅｓｓノードのペアの各々について、ＳＰＢでパスを決定する際に使用するリンクメトリックを個別に決定する。また、ベストエフォートトラフィックを送受信するベストエフォートノード間のパスをＳＰＢで決定する際に使用するリンクメトリックを決定する。これにより、Ｅｘｐｒｅｓｓノードとベストエフォートノードが混在している構成のメッシュネットワークに対してＳＰＢを適用する場合に、各スイッチにおいては、Ｅｘｐｒｅｓｓトラフィックの転送処理が競合する頻度を低く抑えたパスが決定されるようにリンクメトリックを導出することができる。
【００５７】
実施の形態２．
図１７は、実施の形態２のフレーム転送装置であるスイッチ２ａ1〜２ａ7の構成例を示す図である。
【００５８】
なお、スイッチ２ａ1〜２ａ7は、実施の形態１で説明したものと同じ構成のメッシュネットワークを構成しているものとする。すなわち、スイッチ２ａ1〜２ａ7は、図１においてスイッチ２1〜２7をスイッチ２ａ1〜２ａ7に置き換えた構成のメッシュネットワークを構成しているものとする。スイッチ２ａ1〜２ａ7とベストエフォートノードおよびＥｘｐｒｅｓｓノードとの接続関係も実施の形態１と同様とする。よって、スイッチ２ａ1には、ベストエフォートノード１1と、Ｅｘｐｒｅｓｓノード３1および４1とが接続されている。スイッチ２ａ2には、ベストエフォートノード１2が接続されている。スイッチ２ａ3には、ベストエフォートノード１4が接続されている。スイッチ２ａ7にはベストエフォートノード１3と、Ｅｘｐｒｅｓｓノード３2および４2とが接続されている。
【００５９】
本実施の形態のスイッチ２ａ1〜２ａ7は、図２に示した実施の形態１のスイッチ２1〜２7が備えているＥｘｐｒｅｓｓトラフィックパス決定部３３を線形計画問題解決部３５に置き換えるとともに、ＳＰＢ処理部２７およびリンクメトリック決定部３２をＳＰＢ処理部２７ａおよびリンクメトリック決定部３２ａに置き換えたものである。本実施の形態では、実施の形態１のスイッチ２1〜２7と共通の部分については説明を省略する。線形計画問題解決部３５、ＳＰＢ処理部２７ａおよびリンクメトリック決定部３２ａは、図３に示したハードウェアにより実現可能である。線形計画問題解決部３５は、線形計画問題解決部３５として動作するためのプログラムをプロセッサ１０３が実行することにより実現される。ＳＰＢ処理部２７ａは、ＳＰＢ処理部２７ａとして動作するためのプログラムをプロセッサ１０３が実行することにより実現される。リンクメトリック決定部３２ａは、リンクメトリック決定部３２ａとして動作するためのプログラムをプロセッサ１０３が実行することにより実現される。
【００６０】
本実施の形態のスイッチ２ａ1〜２ａ7においても、各リンクのリンクメトリックとして拡張したリンクメトリック、すなわち、複数のリンクメトリックを割り当て、フレームを送受信するノードの間のパスを決定する。
【００６１】
第１のリンクメトリック決定手段である線形計画問題解決部３５は、図１８に示したフローチャートに従い、Ｅｘｐｒｅｓｓトラフィックのパスを決定する際に使用するリンクメトリックを決定する。具体的には、線形計画問題解決部３５は、リンクメトリックを決定する処理の開始条件を満足したか否かを継続的に監視している（ステップＳ１１１）。ここで、処理の開始条件とは、例えば、前回リンクメトリックを決定してから規定時間が経過した場合、ユーザが処理開始を指示する操作を行った場合、自スイッチに対して新しいノードが接続した場合、自スイッチとともにメッシュネットワークを形成している他のスイッチに新しいノードが接続されたことを検出した場合、などが考えられる。リンクメトリックの決定処理の開始条件を満足した場合（ステップＳ５１：Ｙｅｓ）、線形計画問題解決部３５は、ネットワークトポロジー情報管理部３１が保持している、ネットワークのトポロジー情報および隣接ノード情報を読み出す（ステップＳ１１２）。次に、線形計画問題解決部３５は、読み出した情報、具体的には、ネットワークのトポロジー情報と、各スイッチ２に接続している各ノードの隣接ノード情報のうち、属性情報、および各ノードの通信相手先情報と、に基づいて、Ｅｘｐｒｅｓｓトラフィックのパスを決定する際に使用する、各リンクのリンクメトリックを決定する（ステップＳ１１３）。より詳細には、線形計画問題解決部３５は、線形計画問題を解くことにより、Ｅｘｐｒｅｓｓトラフィックのパスを決定する際に使用する、各リンクのリンクメトリックを決定する。例えば、非特許文献１に記載された手法と同様の手法により、各リンクのリンクメトリックを決定する。具体的には、非特許文献１では、全リンクの使用率の最大値が最小となるように線形計画問題を解くことによりリンクメトリックを決定する手法が開示されている。これに対して、線形計画問題解決部３５は、ネットワーク内の各Ｅｘｐｒｅｓｓトラフィックパスが使用するリンクの重なりが最大となるリンクの重なりが最小となるように線形計画問題を解くことにより、Ｅｘｐｒｅｓｓトラフィックのパスを決定する際に使用する各リンクのリンクメトリックを決定する。線形計画問題可決部３５は、決定したリンクメトリック、すなわち、Ｅｘｐｒｅｓｓトラフィックのパスを決定する際に使用するリンクメトリックをリンクメトリック決定部へ出力する（ステップＳ１１４）。
【００６２】
第２のリンクメトリック決定手段であるリンクメトリック決定部３２ａは、図１９に示したフローチャートに従い、メッシュネットワーク内の各リンクのリンクメトリックを決定する。具体的には、リンクメトリック決定部３２ａは、線形計画問題解決部３５からリンクメトリックを受信したか否かを継続的に監視している（ステップＳ１２１）。リンクメトリック決定部３２ａは、線形計画問題解決部３５で決定されたリンクメトリックを受信した場合（ステップＳ１２１：Ｙｅｓ）、ネットワークトポロジー情報管理部３１が保持している、ネットワークのトポロジー情報およびベストエフォートトラフィックの帯域需要の情報を読み出す（ステップＳ２１２）。次に、リンクメトリック決定部３２ａは、ネットワークトポロジー情報管理部３１から読み出したネットワークのトポロジー情報およびベストエフォートトラフィックの帯域需要の情報に基づいて、ベストエフォートトラフィックのパスを決定する際に使用する、各リンクのリンクメトリックを決定する（ステップＳ２１３）。次に、リンクメトリック決定部３２ａは、線形計画問題解決部３５から受け取ったリンクメトリックすなわち、Ｅｘｐｒｅｓｓトラフィックのパスを決定する際に使用するリンクメトリックと、決定したリンクメトリック、すなわちベストエフォートトラフィックのパスを決定する際に使用するリンクメトリックとを合わせて、拡張リンクメトリックとしてＳＰＢ処理部へ出力する（ステップＳ２１４）。本実施の形態の拡張リンクメトリックは、Ｅｘｐｒｅｓｓトラフィックのパスを決定する際に使用するリンクメトリックおよびベストエフォートトラフィックのパスを決定する際に使用するリンクメトリックの２つにより構成されている。なお、リンクメトリック決定部３２ａは、線形計画問題解決部３５とともに決定手段を構成する。
【００６３】
ＳＰＢ処理部２７ａは、ネットワークトポロジー情報管理部３１が保持しているネットワークのトポロジー情報およびリンクメトリック決定部３２ａが保持している拡張リンクメトリックに基づき、ＳＰＢを使用して、各ノードが送受信するフレームの最短経路を計算する。ＳＰＢ処理部２７ａの動作は、実施の形態１で説明したＳＰＢ処理部２７と同様である。すなわち、図１１に示したように、ＳＰＢ処理部２７ａは、リンクメトリックを受信した場合（ステップＳ７１：Ｙｅｓ）、ネットワークのトポロジー情報をネットワークトポロジー情報管理部３１から読み出す（ステップＳ７２）。次に、ＳＰＢ処理部２７ａは、読み出したトポロジー情報とリンクメトリック決定部３２から受け取った各リンクのリンクメトリックとに基づき、ＳＰＢを使用して、各ノードが送受信するフレームの最短経路を計算する（ステップＳ７３）。次に、ＳＰＢ処理部２７は、最短経路の計算結果に基づき、受信したフレームを自スイッチのどのポートに転送するかを決定し（ステップＳ７４）、決定結果を転送データベース２６へ出力する（ステップＳ７５）。ただし、ステップＳ７３において最短経路を計算する際に使用するリンクメトリックが実施の形態１とは異なる。最短経路の計算方法の詳細については後述する。
【００６４】
実施の形態１のスイッチ２1〜２7では、リンクメトリック決定部３２が、Ｅｘｐｒｅｓｓトラフィックのパスを決定する際に使用するリンクメトリックおよびベストエフォートトラフィックのパスを決定する際に使用するリンクメトリックの双方を決定していたが、本実施の形態のスイッチ２ａ1〜２ａ7では、線形計画問題解決部３５がＥｘｐｒｅｓｓトラフィックのパスを決定する際に使用するリンクメトリックを決定し、リンクメトリック決定部３２ａがベストエフォートトラフィックのパスを決定する際に使用するリンクメトリックを決定する。なお、線形計画問題解決部３５の機能をリンクメトリック決定部３２ａに持たせてもよい。すなわち、リンクメトリック決定部３２ａがＥｘｐｒｅｓｓトラフィックのパスを決定する際に使用するリンクメトリックおよびベストエフォートトラフィックのパスを決定する際に使用するリンクメトリックの双方を決定する構成としてもよい。
【００６５】
つづいて、実施の形態２のメッシュネットワークにおいてスイッチ２ａ1〜２ａ7がリンクメトリックを決定し、決定したリンクメトリックに基づいてノード間のパスを決定する手順について説明する。
【００６６】
図２０は、実施の形態２のスイッチ２ａがメッシュネットワークに接続しているノード間のパスを決定する手順を示す図である。各スイッチ２ａは、以下で説明する手順＃２−１〜手順＃２−３を実行することにより、通信を行う各ノード間のパスを決定する。ここでは、図１に示した構成と同様のメッシュネットワークにおいて、スイッチ２ａ1〜２ａ7が、ベストエフォートノード１1，１2，１3，１4、Ｅｘｐｒｅｓｓノード３1，３2，４1，４2の各々についてのパスを決定する場合の例を説明する。
【００６７】
＜手順＃２−１＞
この手順＃２−１は、実施の形態１で説明した手順＃１−１と同じ処理を実行し、各スイッチ２ａが、ベストエフォートノード１1，１2，１3，１4、Ｅｘｐｒｅｓｓノード３1，３2，４1，４2の各々についての情報、すなわち隣接ノード情報を収集する。手順＃１−１と同じ処理であるため、詳細動作の説明は省略する。
【００６８】
＜手順＃２−２＞
次に、スイッチ２ａ1〜ａ２7は、ネットワーク内の各リンクのリンクメトリックを決定する。リンクメトリックは通常１つであるが、本実施の形態では２つのリンクメトリックを決定する。
【００６９】
各リンクのリンクメトリックの１つ目は、Ｅｘｐｒｅｓｓトラフィックのパスを決定するために使用し、各リンクのリンクメトリックの２つ目はベストエフォートトラフィックのパスを決定するために使用する。図２０では、リンクメトリックを“（Ａ，Ｂ）”という形式で表現している。“Ａ”の位置に記載された数値を１つ目のリンクメトリック、“Ｂ”の位置に記載された数値を２つ目のリンクメトリックとする。
【００７０】
スイッチ２ａ1〜２ａ7は、各リンクのリンクメトリック１０1〜１０9の１つ目のリンクメトリックについて、ネットワーク内の各Ｅｘｐｒｅｓｓトラフィックパスが使用するリンクの重なりが最大となるリンクの重なりが最小となるように線形計画問題を解くことによりリンクメトリックを決定する。また、スイッチ２ａ1〜２ａ7は、各リンクのリンクメトリック１０1〜１０9の２つ目のリンクメトリックについて、ベストエフォートトラフィックのロードバランシングが実現できるように決定する。例えば、各ベストエフォートノードの帯域需要に基づいて全リンクの使用率の最大値が最小となるように線形計画問題を解くことにより、各リンクの２つ目のリンクメトリックを決定する。その他の決定方法としては、リンク帯域の逆数をリンクメトリックに決定する、などが考えられる。
【００７１】
スイッチ２ａ1〜２ａ7においては、線形計画問題解決部３５が１つ目のリンクメトリックを決定し、リンクメトリック決定部３２ａが２つ目のリンクメトリックを決定する。リンクメトリック決定部３２ａは１つ目のリンクメトリックと２つ目のリンクメトリックを合わせて拡張リンクメトリックとして保持する。
【００７２】
＜手順＃２−３＞
次に、スイッチ２ａ1〜２ａ7は、ＳＰＢを用いて各ノード間のパスを決定する。具体的には、スイッチ２ａ1〜２ａ7は、各リンクの１つ目のリンクメトリックを用いて、Ｅｘｐｒｅｓｓトラフィックのパスを、最短経路となるように決定する。ここでは、Ｅｘｐｒｅｓｓノードのペアが２つであるため、２つのＥｘｐｒｅｓｓトラフィックパス、すなわち図示したＥＣＭＰ１１および１２が決定される。スイッチ２ａ1〜２ａ7は、決定したＥＣＭＰ１１および１２を、各Ｅｘｐｒｅｓｓノードのペアに割り当てる。例えば、ＥＣＭＰ１１をＥｘｐｒｅｓｓノード３1とＥｘｐｒｅｓｓノード３2のペアに使用させるようにＶＩＤ（Virtual  Local  Area  Network  ID）を設定し、ＥＣＭＰ１２をＥｘｐｒｅｓｓノード４1とＥｘｐｒｅｓｓノード４2のペアに使用させるようにＶＩＤを設定する。また、スイッチ２ａ1〜２ａ7は、各リンクの２つ目のリンクメトリックを用いて、ベストエフォートトラフィックのパスを、最短経路となるように決定する。
【００７３】
スイッチ２ａ1〜２ａ7においては、ＳＰＢ処理部２７ａが、ネットワークトポロジー情報管理部３１で保持されている情報と、リンクメトリック決定部３２ａで保持されている拡張リンクメトリックとに基づいて、各ノード間のパスを決定する。
【００７４】
このように、本実施の形態のスイッチ２ａは、メッシュネットワークに接続している各ノードから、Ｅｘｐｒｅｓｓノードとベストエフォートノードのどちらに該当するかを示す属性情報と、フレームを送受信する相手のノードを示す通信相手ノード情報と、を収集し、収集した情報に基づいて、Ｅｘｐｒｅｓｓトラフィックを送受信するＥｘｐｒｅｓｓノードの間のパスを決定する際に使用するリンクメトリックと、ベストエフォートトラフィックを送受信するベストエフォートノードの間のパスを決定する際に使用するリンクメトリックとを決定する。Ｅｘｐｒｅｓｓトラフィックを送受信するＥｘｐｒｅｓｓノードの間のパスを決定する際に使用するリンクメトリックを決定する際には、各Ｅｘｐｒｅｓｓトラフィックノードの間のパスが使用するリンクの重なりが最大となるリンクの重なりが最小となるよう、すなわち、Ｅｘｐｒｅｓｓトラフィックパスを構成しているリンク同士の重なり数が最小となるよう、線形計画問題を解くことによりリンクメトリックを決定する。これにより、Ｅｘｐｒｅｓｓノードとベストエフォートノードが混在している構成のメッシュネットワークに対してＳＰＢを適用する場合に、各スイッチにおいては、Ｅｘｐｒｅｓｓトラフィックの転送処理が競合する頻度を低く抑えたパスが決定されるようにリンクメトリックを導出することができる。
【００７５】
以上の実施の形態に示した構成は、本発明の内容の一例を示すものであり、別の公知の技術と組み合わせることも可能であるし、本発明の要旨を逸脱しない範囲で、構成の一部を省略、変更することも可能である。
【符号の説明】
【００７６】
１1〜１4  ベストエフォートノード、２1〜２7，２ａ1〜２ａ7  スイッチ、３1，３2，４1，４2  Ｅｘｐｒｅｓｓノード、２１  受信部、２２  送信部、２３  Ｈｅｌｌｏ生成部、２４  隣接ノード情報広告部、２５  フレーム転送部、２６  転送データベース、２７，２７ａ  ＳＰＢ処理部、２８  フレーム処理部、２９  隣接ノード情報収集部、３０  ノード情報収集部、３１  ネットワークトポロジー情報管理部、３２，３２ａ  リンクメトリック決定部、３３  Ｅｘｐｒｅｓｓトラフィックパス決定部、３４  カプセリング部、３５  線形計画問題解決部。
【図１】
0006265930.tif 000003
【図２】
0006265930.tif 000004
【図３】
0006265930.tif 000005
【図４】
0006265930.tif 000006
【図５】
0006265930.tif 000007
【図６】
0006265930.tif 000008
【図７】
0006265930.tif 000009
【図８】
0006265930.tif 000010
【図９】
0006265930.tif 000011
【図１０】
0006265930.tif 000012
【図１１】
0006265930.tif 000013
【図１２】
0006265930.tif 000014
【図１３】
0006265930.tif 000015
【図１４】
0006265930.tif 000016
【図１５】
0006265930.tif 000017
【図１６】
0006265930.tif 000018
【図１７】
0006265930.tif 000019
【図１８】
0006265930.tif 000020
【図１９】
0006265930.tif 000021
【図２０】
0006265930.tif 000022