(57)【要約】  コンピュータネットワーク（１）において複数のスパニング・ツリーを決定する方法及び装置であって、各スパニング・ツリーは、前記コンピュータネットワークのノード（１００，１０１，１０２，１０３）間の通信リンク（２００，２０１，２０２，２０３，２０４）に関する特定の構成を提供し、前記方法は、以前に決定されたスパニング・ツリーに特定の通信リンクが含まれる場合に当該通信リンクを使用することに関連するコストを増加させるステップを備える。
2010525638.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワークにおいて複数のスパニング・ツリーを決定する方法であって、
各スパニング・ツリーは、前記コンピュータネットワークのノード間の通信リンクに関する特定の構成を提供し、
前記方法は、以前に決定されたスパニング・ツリーに特定の通信リンクが含まれる場合に当該通信リンクを使用することに関連するコストを増加させるステップを備える
ことを特徴とする方法。
【請求項２】
以前に決定された、前記通信リンクを含むスパニング・ツリーの数の関数として、前記コストの前記増加を決定するステップを備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記特定の通信リンクが以前に決定されたスパニング・ツリーに含まれない場合、当該通信リンクのコストは変化しないことを特徴とする請求項１又は２に記載の方法。
【請求項４】
以下の公式に従って前記特定の通信リンクの前記コストを決定するステップを備えることを特徴とする請求項１乃至３のいずれか１項に記載の方法。
ｃｉｊ＝（ｍａｘ＿ｃｏｓｔｉ−ｍｉｎ＿ｃｏｓｔｉ）．（ｎｉｊ／ｍａｘ＿ｎ）ｉｎｓｔ＿ｃｕｒｖ
ここで、
ｃｉｊは、ｊ番目の繰り返しにおけるｉ番目のリンクのコストであり、
ｍａｘ＿ｃｏｓｔｉは、ｉ番目のリンクの帯域幅に関連する最大コストであり、
ｍｉｎ＿ｃｏｓｔｉは、ｉ番目のリンクの帯域幅に関連する最小コストであり、
ｎｉｊは、繰り返しｊにおいてリンクｉを使用するスパニング・ツリーの数であり、
ｍａｘ＿ｎは、スパニング・ツリーの最大数であり（ＭＳＴＰの場合は６４）、
ｉｎｓｔ＿ｃｕｒｖは、ｎｉｊベースのコスト曲線の曲率である（例えば、１に等しい場合、これは線形である）。
【請求項５】
請求項１乃至４のいずれか１項に記載の方法を含む、複数のスイッチングデバイス間の接続を構成するための方法。
【請求項６】
コンピュータネットワークにおいて複数のスパニング・ツリー・インスタンスを決定するための装置であって、
各スパニング・ツリーは、前記コンピュータネットワークのノード間の通信リンクに関する特定の構成を提供し、
前記装置は、以前に決定されたスパニング・ツリーに特定の通信リンクが含まれる場合に当該通信リンクを使用することに関連するコストを増加させるように構成される
ことを特徴とする装置。
【請求項７】
添付の図面を参照して本明細書において説明されたものと実質的に同じように複数のスパニング・ツリーを決定する方法。
【請求項８】
本明細書において説明したものと実質的に同じように複数のスパニング・ツリーを決定するための装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、コンピュータネットワークに関する。
【背景技術】
【０００２】
コンピュータネットワークは、情報及び／又はリソースの共有及び交換を可能にする。コンピュータネットワークは典型的には、複数のコンピュータエンティティ（例えば、ワークステーション、サーバ、プリンタ、及びデータ記憶装置）を含み、これらは１以上の通信リンクを用いて相互接続される。コンピュータエンティティは、通信リンクを介してデータを送受信することができる。一般的な種類のコンピュータネットワークは、所謂ローカル・エリア・ネットワーク（ＬＡＮ）であり、その中では、多様なコンピュータエンティティが特定の場所（例えば、ビル又はビル群の中）で接続される。イーサネット（登録商標）スイッチのような仲介デバイスを使用して所謂バーチャルＬＡＮ（ＶＬＡＮ）を形成することができる。典型的には、仲介デバイスは、データプロセッサ及び複数のポートを備え、複数のポートはコンピュータエンティティのネットワーク全体の分割（セグメンテーション）を可能にする。スイッチング機能は、入力ポートにおいてデータを受信し、そのデータを出力ポートへ転送することを含む。コンピュータエンティティは各仲介デバイスに接続されており、仲介デバイスは物理的な通信リンクを介して接続されている。
【０００３】
仲介デバイスを適切に構成することにより、多様なＶＬＡＮを構築可能である。そのようなネットワークは、より詳しくは、バーチャル・ブリッジ・ローカル・エリア・ネットワークとして知られている。単一の仲介デバイスが様々なＶＬＡＮのメンバーのために物理接続を提供してもよいということが理解されよう。ＶＬＡＮは、（ＶＬＡＮの多様な側面を規定する標準である）ＩＥＥＥ８０２．１Ｑにおけるマルチプル・スパニング・ツリー・プロトコルに従って構成可能である。そのような構成において、各ＶＬＡＮは、スパニング・ツリー・インスタンスによって決定される。
【０００４】
スパニング・ツリー・トポロジを有利に使用することは、ネットワークをダウンさせてしまうかもしれないデータフレームの無限ループを回避する。従って、物理ネットワークを介して複数のスパニング・ツリー・トポロジを同時に拡散させることを可能にするＶＬＡＮがもたらす結果は、個々のネットワーク間の物理リンクが、利用可能な物理リンクの全体に亘って拡散し、これにより高度なリソースの活用を実現するということである。
【０００５】
しかしながら、ＭＳＴＰによって導入されたネットワーク運用性における改善は、トラヒックを最適に割り当て可能な様々なアクティブ・スパニング・ツリーを定義するために必要とされる、ネットワーク管理者にとっての追加的な設定負担という代償をもたらす。複数のスパニング・ツリーを自動的に定義し、ひいては標準的なＭＳＴＰの構成のためのパラメータを導出することを、最小限の人的介在によりスパニング・ツリー・インスタンスを実装可能なやり方で行うことが望まれるであろうということに、我々は気付いた。すると、ネットワーク管理者は、自動的に生成されたＭＳＴインスタンスにＶＬＡＮを関連付けることしか必要としない。
【発明の概要】
【課題を解決するための手段】
【０００６】
本発明の第１の態様によれば、コンピュータネットワークにおいて複数のスパニング・ツリーを決定する方法であって、各スパニング・ツリーは、前記コンピュータネットワークのノード間の通信リンクに関する特定の構成を提供し、前記方法は、以前に決定されたスパニング・ツリーに特定の通信リンクが含まれる場合に当該通信リンクを使用することに関連するコストを増加させるステップを備えることを特徴とする方法が提供される。
【０００７】
本発明の極めて好適な実施形態においては、障害時にトラヒックを自動的に再ルーティングすることを可能にし、そしてネットワークの利用可能な全リソースに亘る良好なトラヒック分散を可能にする、複数のスパニング・ツリー・インスタンスのセットを自動的に定義する方法が提供される。この方法は、計算上の単純なアルゴリズムを含み、数学的に最適なソリューションを提供する訳ではないという意味において、実用的である。
【０００８】
本発明の第２の態様によれば、コンピュータネットワークにおいて複数のスパニング・ツリー・インスタンスを決定するための装置であって、各スパニング・ツリーは、前記コンピュータネットワークのノード間の通信リンクに関する特定の構成を提供し、前記装置は、以前に決定されたスパニング・ツリーに特定の通信リンクが含まれる場合に当該通信リンクを使用することに関連するコストを増加させるように構成されることを特徴とする装置が提供される。
【０００９】
添付の図面を参照して、あくまでも例として、本発明の多様な実施形態を説明する。
【図面の簡単な説明】
【００１０】
【図１】ローカル・エリア・ネットワーク（ＬＡＮ）とＬＡＮ間のブリッジ装置とを含むネットワークトポロジの概略図である。
【図２】第１のバーチャル・ローカル・エリア・ネットワーク（ＶＬＡＮ）を表す第１の決定されたスパニング・ツリー構成の概略図である。
【図３】第２のＶＬＡＮを表す第２の決定されたスパニング・ツリー構成の概略図である。
【発明を実施するための形態】
【００１１】
図１を参照すると、４つのブリッジ１００、１０１、１０２、及び１０３を介して接続される、複数のローカル・エリア・ネットワーク（ＬＡＮ）２００、２０１、２０２、２０３、及び２０４を含むネットワークが示されている。ＬＡＮは、イーサネット（登録商標）ブリッジ間の通信リンクを提供する。各イーサネット（登録商標）ブリッジには、１以上のコンピュータエンティティ（不図示）が接続されている。初期セットアップ手順を用いてネットワーク１における複数のバーチャル・ブリッジ・ローカル・エリア・ネットワークを決定することが望ましい。別々のイーサネット（登録商標）ブリッジに接続される少なくともいくつかのコンピュータエンティティが同一のＶＬＡＮのメンバーになるであろうということが理解されよう。
以下の手順の説明は、初期設定（Ｉｎｉｔ）、繰り返し（Ｉｔｅｒａｔｉｏｎ）、及び終了（Ｔｅｒｍ）のフェーズを含むハイレベルのステップの形式である。
【００１２】
ステップ１  （Ｉｎｉｔ）  最初に、ブリッジとブリッジを接続するＬＡＮとを伴う、物理トポロジが定義される。ＬＡＮには、所望のＬＡＮの利用を反映するべきコストという性質が与えられる。コストの割り当ては、関連するＩＥＥＥ標準によって提供されるガイドラインに関連し得るものであり、高容量のＬＡＮは比較的低いコストを持つことでその利用を促す。しかしながら、コストの割り当ては管理上の問題であって、多数の異なる基準により実現可能である。しかしながら、提案される公式は、ｃ＝ｋ１／ｂｉであり、ここで、ｉ番目のＬＡＮのコストｃｉは、適切な定数ｋ１をＬＡＮの帯域容量ｂｉで割ることによって与えられる。
【００１３】
ステップ２  （Ｉｎｉｔ）  次に、第１のスパニング・ツリーを発見するために、知られている最小コスト・スパニング・ツリー・アルゴリズム（例えば、Ｐｒｉｍの又はＫｒｕｓｋａｌのアルゴリズム）が実行される。より高い演算複雑性を受容できる場合、最小直径スパニング・ツリー（ＭＤＳＴ）を発見するためにより洗練されたアルゴリズムを使用してもよい。アルゴリズムが選択されると、スパニング・ツリーは、ステップ１で割り当てられた管理コストに依存する。このスパニング・ツリーは、ステップ１で割り当てられたＬＡＮのコストの総和の関数である総コストを持つ。
【００１４】
ステップ３  （Ｉｔｅｒａｔｉｏｎ）  各ＬＡＮのコストは、そのＬＡＮの初期コストと、そのＬＡＮを含む発見されたスパニング・ツリーの数との両方の関数である値によって置き換えられる。この関数は依然として、高容量ＬＡＮの利用を促すものであり、同時に、スパニング・ツリーのうちの最小数でカバーされるＬＡＮを優先させるものである。これにより、一様な数のスパニング・ツリーをトポロジ全体に亘って拡散させることが可能である。コスト関数の詳細については、ここでも、管理上の問題であって、トラヒック割り当てのポリシーに従って変化し得るものである。しかしながら、例としての公式を以下に提案する。合理的な関数は、ＬＡＮのコストを常に増加させるか又は変化させないという点において、単調であるべきである。即ち、以前の繰り返しにおいて何らかのスパニング・ツリーによってＬＡＮが使用された場合はそのＬＡＮのコストが増加し、そうでなければコストは変化しないままである。
【００１５】
ステップ４  （Ｉｔｅｒａｔｉｏｎ）  ステップ３で算出された新しいコストを持つトポロジにおいて、ステップ２で使用されたものと同一の最小コスト・スパニング・ツリー・アルゴリズムが実行される。ｊ番目の繰り返しにおいて、（ｊ＋１）番目のスパニング・ツリーが発見される（第１のものは、初期設定フェーズ中のステップ２の結果であるので）。このスパニング・ツリーは、ステップ３において算出されたコストの関数である総コストを持つ。ステップ３のコスト関数の単調な性質は、後続のスパニング・ツリーの総コストも漸増するということを暗示する。即ち、（ｊ＋１）番目のスパニング・ツリーのコストは、ｊ番目のスパニング・ツリーのコストよりも高い。
【００１６】
ステップ５  （Ｔｅｒｍ）  （ｊ＋１）番目のスパニング・ツリーのコストがｊ番目のそれよりも「極めて高い」場合、このことは、最後のスパニング・ツリーが（ｉ）低容量のＬＡＮ、又は、（ｉｉ）既にいくつかのスパニング・ツリーによって負荷がかけられているＬＡＮのいずれかを使用しており、従って、その貢献はトラヒック負荷に対する意味のある改善をもたらさないであろういうことを意味し、繰り返しは終了され、最後のスパニング・ツリーは破棄される。上述の通り、「極めて高い」ということは特定の状況のニーズに従って定義される条件である。より早期に（「極めて高い」にとっての低い値）終了することは、より少数のスパニング・ツリーを生み出し、このことは、より低い構成負荷と、より粗い負荷バランシングとを意味する。反対に、「実に極めて高い」コストは、より多数のスパニング・ツリーを導き、より高い構成上の複雑性を伴うが、きめ細かいトラヒック分散の機会をもたらす。ＭＳＴＰ標準によれば、いずれの場合でも６４のスパニング・ツリーが生み出されたら手順は終了しなければならない。
【００１７】
上の手順の完了後、ネットワークトポロジ上でのＶＬＡＮの好都合なトラヒック分散／バランシングを可能にする十分なルーティングダイバーシチ／選択肢を伴うスパニング・ツリーの集合が生み出される。上述の手順は、
−物理トポロジの全てのブリッジと、
−物理トポロジのＬＡＮのサブセットと、
に関してツリーを定義する。
【００１８】
（ＩＥＥＥ標準プロトコルによって使用される各ＭＳＴＩ（ＭＳＴプロトコルインスタンス）のための適切なパラメータが導出されなければならない。）
【００１９】
次にネットワークオペレータは、ＶＬＡＮを形成するために各スパニング・ツリー・インスタンスを手作業で割り当てることができる。
【００２０】
ステップ３において必要に応じて各繰り返しにおいてＬＡＮコストを適切に増加させる公式の例は、以下の通りである。
ｃｉｊ＝（ｍａｘ＿ｃｏｓｔｉ−ｍｉｎ＿ｃｏｓｔｉ）．（ｎｉｊ／ｍａｘ＿ｎ）ｉｎｓｔ＿ｃｕｒｖ
ここで、
ｃｉｊは、ｊ番目の繰り返しにおけるｉ番目のＬＡＮのコストであり、
ｍａｘ＿ｃｏｓｔｉは、ｉ番目のＬＡＮの帯域幅に関連する最大コストであり、
ｍｉｎ＿ｃｏｓｔｉは、ｉ番目のＬＡＮの帯域幅に関連する最小コストであり、
ｎｉｊは、繰り返しｊにおいてＬＡＮｉを使用するスパニング・ツリーの数であり、
ｍａｘ＿ｎは、スパニング・ツリーの最大数であり（ＭＳＴＰの場合は６４）、
ｉｎｓｔ＿ｃｕｒｖは、ｎｉｊベースのコスト曲線の曲率である（例えば、１に等しい場合、これは線形である）。
【００２１】
図２及び図３を参照すると、２つの可能なＶＬＡＮが示されており、各々は、算出されたスパニング・ツリー・インスタンスに対応する。
【００２２】
実際問題として、ネットワーク管理者は多様なスパニング・ツリー・インスタンスを決定するためにデータプロセッサを使用するであろうということが理解されよう。管理者は、それ以上のスパニング・ツリー・インスタンスが決定されないようにする受容可能な最大コストの指標を、データプロセッサに対して示していたかもしれない。次に管理者は、多様なＶＬＡＮを完成させるために、各イーサネット（登録商標）スイッチを（遠隔的に）設定することができる。
【図１】
2010525638.tif 000003
【図２】
2010525638.tif 000004
【図３】
2010525638.tif 000005
【国際調査報告】
2010525638.tif 000006
2010525638.tif 000007