(57)【要約】【課題】  スパニングツリーコンフィギュレーションメッセージが失われた場合にループの発生を防止する一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行すること。【解決手段】  動作中、システムは、ブリッジ上でスパニングツリープロトコルを実行する。このスパニングツリープロトコルは、ブリッジに結合された各ポートを、メッセージがポートへもポートからも転送される転送状態か、またはメッセージがポートへもポートからも転送されないバックアップ状態に構成する。システムは、さらに、ブリッジに結合されたポートをモニタリングし、メッセージがポートによって失われたかどうかを決定する。１つ以上のメッセージがポート上で失われた場合、システムは、メッセージがある時間にわたってポートによって失われなくなるまで、ポートへもポートからもメッセージの転送を控える。【選択図】  図３
2005110253.tif 000002
【特許請求の範囲】
【請求項１】
スパニングツリーコンフィギュレーションメッセージが失われた場合のループの発生を防止する一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行する方法であって、
該スパニングツリープロトコルをブリッジ上で実行するステップであって、該スパニングツリープロトコルは、該ブリッジに結合された各ポートを、メッセージが該ポートへも該ポートからも転送される転送状態か、あるいは、メッセージが該ポートへも該ポートからも転送されないバックアップ状態に構成する、ステップと、
メッセージが該ポートによって失われたのはいつかを決定するために、該ブリッジに結合されたポートをモニタリングするステップと、
１つ以上のメッセージがポート上で失われた場合、ある時間にわたって、メッセージがポートによって失われなくなるまで、メッセージを該ポートへも該ポートからも転送することを控えるステップと
を包含する、方法。
【請求項２】
前記ある時間は、連続したスパニングツリーコンフィギュレーションメッセージ間にブリッジによって提供されたタイムインターバルよりも大きい、請求項１に記載の方法。
【請求項３】
前記ブリッジに結合されたポートをモニタリングするステップは、メッセージが該ポートによって失われたかどうかを決定するために、該ポートと関連したハードウェアと通信するステップを包含する、請求項１に記載の方法。
【請求項４】
前記スパニングツリープロトコルを実行するステップは、前記ネットワーク内のブリッジを繋ぎ合せるスパニングツリーにわたって繰返すことなくメッセージが転送されることを保証するように、前記ブリッジに結合されたポートを前記転送状態または前記バックアップ状態にするステップを包含する、請求項１に記載の方法。
【請求項５】
前記スパニングツリープロトコルを実行するステップは、
前記ネットワーク上のすべてのリンクのすべてのブリッジのうちの１つのブリッジをルートブリッジに選出するステップと、
各ノードから該ルートブリッジへの最短経路の距離を計算するステップと、
リンクごとに指定されたブリッジを該リンクのすべてのブリッジから選出するステップであって、該指定されたブリッジが、該ルートブリッジに最も近く、かつ、パケットを該リンクから該ルートブリッジに転送する、ステップと、
最良の経路を該ルートブリッジに提供するルートポートをブリッジごとに選択するステップと、
該スパニングツリー内に含まれるべき各ブリッジ上のポートをセレクトするステップであって、該セレクトされたポートは、該ルートポートと、該ブリッジが該指定されたブリッジとして利用されるリンクに結合された任意のポートとを備える、ステップと、
セレクトされたポートを前記転送状態にするステップと、
すべての他のポートを前記バックアップ状態にするステップと
を包含する、請求項４に記載の方法。
【請求項６】
前記スパニングツリープロトコルは、概して、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）標準規格８０２．１Ｄに従って動作する、請求項１に記載の方法。
【請求項７】
前記リンクは、ＬＡＮ（ローカルエリアネットワーク）である、請求項１に記載の方法。
【請求項８】
コンピュータによって実行されると、スパニングツリーコンフィギュレーションメッセージが失われた場合のループの発生を防止する一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行する方法を該コンピュータに実行させる命令を格納するコンピュータ読み出し可能格納媒体であって、該方法は、
該スパニングツリープロトコルをブリッジ上で実行するステップであって、該スパニングツリープロトコルは、該ブリッジに結合された各ポートを、メッセージが該ポートへも該ポートからも転送される転送状態か、あるいは、メッセージが該ポートへも該ポートからも転送されないバックアップ状態に構成する、ステップと、
メッセージが該ポートによって失われたのはいつかを決定するために、該ブリッジに結合されたポートをモニタリングするステップと、
１つ以上のメッセージがポート上で失われた場合、ある時間にわたって、メッセージが該ポートによって失われなくなるまで、メッセージを該ポートへも該ポートからも転送することを控えるステップと
を包含する、コンピュータ読み出し可能格納媒体。
【請求項９】
前記ある時間は、連続的スパニングツリーコンフィギュレーションメッセージ間にブリッジによって提供されるタイムインターバルよりも大きい、請求項８に記載のコンピュータ読み出し可能格納媒体。
【請求項１０】
前記ブリッジに結合されたポートをモニタリングするステップは、メッセージが該ポートによって失われたかどうかを決定するために、該ポートと関連したハードウェアと通信するステップを包含する、請求項８に記載のコンピュータ読み出し可能格納媒体。
【請求項１１】
前記スパニングツリープロトコルを実行するステップは、前記ネットワーク内のブリッジを繋ぎ合せるスパニングツリーにわたって繰返すことなくメッセージが転送されることを保証するように、前記ブリッジに結合されたポートを前記転送状態または前記バックアップ状態にするステップを包含する、請求項８に記載の方法。
【請求項１２】
前記スパニングツリープロトコルを実行するステップは、
前記ネットワーク上のすべてのリンクのすべてのブリッジのうちの１つをルートブリッジに選出するステップと、
各ノードから該ルートブリッジへの最短経路の距離を計算するステップと、
リンクごとに指定されたブリッジを該リンクのすべてのブリッジから選出するステップであって、該指定されたブリッジは、該ルートブリッジに最も近く、かつ、パケットを該リンクから該ルートブリッジに転送する、ステップと、
最良の経路を該ルートブリッジに提供するルートポートをブリッジごとに選択するステップと、
該スパニングツリー内に含まれるべき各ブリッジ上のポートをセレクトするステップであって、該セレクトされたポートは、該ルートポートと、該ブリッジが該指定されたブリッジとして利用されるリンクに結合された任意のポートとを備える、ステップと、
セレクトされたポートを前記転送状態にするステップと、
すべての他のポートを前記バックアップ状態にするステップと
を包含する、請求項１１に記載の方法。
【請求項１３】
前記スパニングツリープロトコルは、概して、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）標準規格８０２．１Ｄに従って動作する、請求項８に記載の方法。
【請求項１４】
前記リンクは、ＬＡＮ（ローカルエリアネットワーク）である、請求項８に記載の方法。
【請求項１５】
スパニングツリーコンフィギュレーションメッセージが失われた場合のループの発生を防止する一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行する装置であって、
該スパニングツリープロトコルをブリッジ上で実行するように構成されたスパニングツリーメカニズムであって、該スパニングツリープロトコルは、該ブリッジに結合された各ポートを、メッセージが該ポートへもポートからも転送される転送状態か、あるいは、メッセージが該ポートへも該ポートからも転送されないバックアップ状態に構成する、スパニングツリーメカニズムと、
メッセージが該ポートによって失われたのはいつかを決定するために、該ブリッジに結合されたポートをモニタリングするように構成されたモニタリングメカニズムと
を備え、
１つ以上のメッセージがポート上で失われた場合、該スパニングツリーメカニズムは、ある時間にわたって、メッセージがポートによって失われなくなるまで、メッセージを該ポートへも該ポートからも転送することを控えるように構成される、装置。
【請求項１６】
前記ある時間は、連続したスパニングツリーコンフィギュレーションメッセージ間にブリッジによって提供されたタイムインターバルよりも大きい、請求項１５に記載の方法。
【請求項１７】
前記モニタリングメカニズムは、メッセージが該ポートによって失われたかどうかを決定するために、該ポートと関連したハードウェアと通信するように構成される、請求項１５に記載の方法。
【請求項１８】
前記スパニングツリーメカニズムは、前記ネットワーク内のブリッジを繋ぎ合せるスパニングツリーにわたって繰返すことなくメッセージが転送されることを保証するように、前記ブリッジに結合されたポートを前記転送状態または前記バックアップ状態にするように構成される、請求項１５に記載の装置。
【請求項１９】
前記スパニングツリーメカニズムは、
前記ネットワーク上のすべてのリンクのすべてのブリッジのうちの１つのブリッジをルートブリッジに選出し、
各ノードから該ルートブリッジへの最短経路の距離を計算し、
リンクごとに指定されたブリッジを該リンクのすべてのブリッジから選出し、ここで、該指定されたブリッジが、該ルートブリッジに最も近く、かつ、パケットを該リンクから該ルートブリッジに転送し、
最良の経路を該ルートブリッジに提供するルートポートをブリッジごとに選択し、
該スパニングツリー内に含まれるべき、各ブリッジ上のポートをセレクトし、ここで、該セレクトされたポートは、該ルートポートと、該ブリッジが該指定されたブリッジとして利用されるリンクに結合された任意のポートとを備え、
セレクトされたポートを前記転送状態にし、
すべての他のポートを前記バックアップ状態にするように構成される、請求項１８に記載の方法。
【請求項２０】
前記スパニングツリーメカニズムは、概して、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）標準規格８０２．１Ｄに従って動作する、請求項１５に記載の方法。
【請求項２１】
前記リンクは、ＬＡＮ（ローカルエリアネットワーク）である、請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータネットワークの設計に関する。より具体的には、本発明は、スパニングツリーコンフィギュレーションメッセージが失われた場合のループの発生を防止する一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行する方法および装置に関する。
【背景技術】
【０００２】
コンピュータネットワークは、トランスペアレントブリッジを通じて繋ぎ合わされることが多い。トランスペアレントブリッジの最も基本的な形態は、２つ以上のローカルエリアネットワーク（ＬＡＮ）に接続されるものである（ブリッジへの各接続部分は、「ポート」と呼ばれる）。このようなブリッジは、伝送されるあらゆるパケットを無差別に読み（ｌｉｓｔｅｎ）、かつ、パケットが受信されたものとは異なるＬＡＮで伝送され得るまで、受信されたそれぞれのパケットを格納する。
【０００３】
トランスペアレントブリッジは、１つのＬＡＮのみで動作するように設計されたステーションが、マルチＬＡＮ環境で作業することを可能にするために開発された。ステーションは、まさにシングルＬＡＮ環境かのように、パケットを伝送することを期待し、かつパケットを送達させる。従って、ブリッジは、パケットを受信したときのように正確に伝送しなければならない。ブリッジが任意の方法でパケットを（例えば、ヘッダのソースアドレス部分をそれ自身のアドレスで上書きすることによって）改変した場合、プロトコルはステーション上で適切に動作し得ない。
【０００４】
ブリッジは、潜在的にパケットをループさせ得、これは、パケットを指数関数的に複製させ得ることに留意されたい。この複製は、ネットワークが機能を停止する点までネットワークの輻輳を増加させ得る。
【０００５】
このルーピングの問題は、一般に、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ：米国電気電子学会）の標準規格８０２．１Ｄに定義されたスパニングツリープロトコルを用いて対処される。このスパニングツリープロトコルは、ループフリー（ツリー）であり、さらに、十分な接続性を有し、これにより、物理的に可能ならば、ＬＡＮの各ペア間に経路ができる（ツリーはスパニングである）ネットワークトポロジのサブセットを動的に発見するブリッジを用いることによって動作する。
【０００６】
スパニングツリープロトコルの背景にある基本的考え方は、ブリッジが、特別のコンフィギュレーションメッセージを周期的に伝送し合い、これにより、ブリッジがスパニングツリーを計算することが可能になるということである。図２を参照して、これらのコンフィギュレーションメッセージは、ブリッジが以下の動作を行うことを可能にするために十分な情報を含む。これらは、（１）すべてのＬＡＮ上のすべてのブリッジのうちの１つのブリッジをルートブリッジに選出する（ステップ２０２）。（２）すべてのブリッジ自身からルートブリッジへの最短経路の距離を計算する（ステップ２０４）。（３）各ＬＡＮの指定されたブリッジをそのＬＡＮに存在するブリッジから選出し（ステップ２０６）、ここで、選出されたブリッジは、ルートブリッジへの最も近いブリッジであり、ルートブリッジにパケットを転送する。（４）ルートブリッジへの最良の経路を与えるポートをブリッジごとに選択する（ステップ２０８）。（５）スパニングツリーに含まれるべき各ブリッジ上のポートをセレクトする（ステップ２１０）。（６）セレクトされたポートを、メッセージがポートへもポートからも転送される転送状態にする（ステップ２１２）。（７）他のポートを、メッセージがポートへもポートからも転送されないバックアップ状態にする（ステップ２１４）。
【０００７】
このプロトコルは、本発明の発明者であるＲａｄｉａ  Ｐｅｒｌｍａｎによる「Ａｌｇｏｒｈｙｍｅ」と称される詩
私は、ツリーよりも美しいグラフを見ることはないと思う。
【０００８】
ツリーの決定的なプロパティはループフリーの接続性にある。
【０００９】
ツリーは確実にスパニングしなければならず、パケットが全てのＬＡＮに到達する。
【００１０】
第１に、ルートが選択されなければならない。
【００１１】
ＩＤによって、それが選出される。
【００１２】
ルートからの最低のコストの経路がトレースされる。
【００１３】
ツリーでは、これらの経路が配置される。
【００１４】
私のような親しい人によってメッシュが作られる。
【００１５】
そして、ブリッジは、スパニングツリーを見つけ出す。
に要約される。
【００１６】
ブリッジを十分なＣＰＵパワーで操作し、これにより、ネットワークが輻輳した場合に、スパニングツリープロトコルが適切に動作することが重要である。そうでない場合、一時的に輻輳したネットワークは、コンフィギュレーションメッセージが失われる原因になり得、これは、スパニングツリープロトコルが、さらなるブリッジポートを誤ってオンにする原因となり得る。これは、ループを引き起こし得、スパニングツリーが決して回復しない転にまで輻輳の量を劇的に増加させ得る。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
残念ながら、ＩＥＥＥ８０２．ＩＤ標準規格は、性能要件を指定せず、その結果、現在開発されているブリッジハードウェアのいくつかが、最悪の事態のトラフィックの間、スパニングツリーコンフィギュレーションメッセージを処理することができない。従って、メッセージが失われ得、かつ、ループが生成され得る。
【００１８】
従って、必要とされるのは、スパニングツリーコンフィギュレーションメッセージが失われた場合にループが生じることを防止する方法および装置である。
【課題を解決するための手段】
【００１９】
本発明による方法は、スパニングツリーコンフィギュレーションメッセージが失われた場合のループの発生を防止する一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行する方法であって、該スパニングツリープロトコルをブリッジ上で実行するステップであって、該スパニングツリープロトコルは、該ブリッジに結合された各ポートを、メッセージが該ポートへも該ポートからも転送される転送状態か、あるいは、メッセージが該ポートへも該ポートからも転送されないバックアップ状態に構成する、ステップと、メッセージが該ポートによって失われたのはいつかを決定するために、該ブリッジに結合されたポートをモニタリングするステップと、１つ以上のメッセージがポート上で失われた場合、ある時間にわたって、メッセージがポートによって失われなくなるまで、メッセージを該ポートへも該ポートからも転送することを控えるステップとを包含し、これにより上記目的を達成する。
【００２０】
前記ある時間は、連続したスパニングツリーコンフィギュレーションメッセージ間にブリッジによって提供されたタイムインターバルよりも大きくてもよい。
【００２１】
前記ブリッジに結合されたポートをモニタリングするステップは、メッセージが該ポートによって失われたかどうかを決定するために、該ポートと関連したハードウェアと通信するステップを包含してもよい。
【００２２】
前記スパニングツリープロトコルを実行するステップは、前記ネットワーク内のブリッジを繋ぎ合せるスパニングツリーにわたって繰返すことなくメッセージが転送されることを保証するように、前記ブリッジに結合されたポートを前記転送状態または前記バックアップ状態にするステップを包含してもよい。
【００２３】
前記スパニングツリープロトコルを実行するステップは、前記ネットワーク上のすべてのリンクのすべてのブリッジのうちの１つのブリッジをルートブリッジに選出するステップと、各ノードから該ルートブリッジへの最短経路の距離を計算するステップと、リンクごとに指定されたブリッジを該リンクのすべてのブリッジから選出するステップであって、該指定されたブリッジが、該ルートブリッジに最も近く、かつ、パケットを該リンクから該ルートブリッジに転送する、ステップと、最良の経路を該ルートブリッジに提供するルートポートをブリッジごとに選択するステップと、該スパニングツリー内に含まれるべき各ブリッジ上のポートをセレクトするステップであって、該セレクトされたポートは、該ルートポートと、該ブリッジが該指定されたブリッジとして利用されるリンクに結合された任意のポートとを備える、ステップと、セレクトされたポートを前記転送状態にするステップと、すべての他のポートを前記バックアップ状態にするステップとを包含してもよい。
【００２４】
前記スパニングツリープロトコルは、概して、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）標準規格８０２．１Ｄに従って動作してもよい。
【００２５】
前記リンクは、ＬＡＮ（ローカルエリアネットワーク）であってもよい。
【００２６】
本発明によるコンピュータ読み出し可能媒体は、コンピュータによって実行されると、スパニングツリーコンフィギュレーションメッセージが失われた場合のループの発生を防止する一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行する方法を該コンピュータに実行させる命令を格納するコンピュータ読み出し可能格納媒体であって、該方法は、該スパニングツリープロトコルをブリッジ上で実行するステップであって、該スパニングツリープロトコルは、該ブリッジに結合された各ポートを、メッセージが該ポートへも該ポートからも転送される転送状態か、あるいは、メッセージが該ポートへも該ポートからも転送されないバックアップ状態に構成する、ステップと、メッセージが該ポートによって失われたのはいつかを決定するために、該ブリッジに結合されたポートをモニタリングするステップと、１つ以上のメッセージがポート上で失われた場合、ある時間にわたって、メッセージが該ポートによって失われなくなるまで、メッセージを該ポートへも該ポートからも転送することを控えるステップとを包含し、これにより、上記目的を達成する。
【００２７】
前記ある時間は、連続的スパニングツリーコンフィギュレーションメッセージ間にブリッジによって提供されるタイムインターバルよりも大きくてもよい。
【００２８】
前記ブリッジに結合されたポートをモニタリングするステップは、メッセージが該ポートによって失われたかどうかを決定するために、該ポートと関連したハードウェアと通信するステップを包含してもよい。
【００２９】
前記スパニングツリープロトコルを実行するステップは、前記ネットワーク内のブリッジを繋ぎ合せるスパニングツリーにわたって繰返すことなくメッセージが転送されることを保証するように、前記ブリッジに結合されたポートを前記転送状態または前記バックアップ状態にするステップを包含してもよい。
【００３０】
前記スパニングツリープロトコルを実行するステップは、前記ネットワーク上のすべてのリンクのすべてのブリッジのうちの１つをルートブリッジに選出するステップと、各ノードから該ルートブリッジへの最短経路の距離を計算するステップと、リンクごとに指定されたブリッジを該リンクのすべてのブリッジから選出するステップであって、該指定されたブリッジは、該ルートブリッジに最も近く、かつ、パケットを該リンクから該ルートブリッジに転送する、ステップと、最良の経路を該ルートブリッジに提供するルートポートをブリッジごとに選択するステップと、該スパニングツリー内に含まれるべき各ブリッジ上のポートをセレクトするステップであって、該セレクトされたポートは、該ルートポートと、該ブリッジが該指定されたブリッジとして利用されるリンクに結合された任意のポートとを備える、ステップと、セレクトされたポートを前記転送状態にするステップと、すべての他のポートを前記バックアップ状態にするステップとを包含してもよい。
【００３１】
前記スパニングツリープロトコルは、概して、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）標準規格８０２．１Ｄに従って動作してもよい。
【００３２】
前記リンクは、ＬＡＮ（ローカルエリアネットワーク）であってもよい。
【００３３】
本発明による装置は、スパニングツリーコンフィギュレーションメッセージが失われた場合のループの発生を防止する一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行する装置であって、該スパニングツリープロトコルをブリッジ上で実行するように構成されたスパニングツリーメカニズムであって、該スパニングツリープロトコルは、該ブリッジに結合された各ポートを、メッセージが該ポートへもポートからも転送される転送状態か、あるいは、メッセージが該ポートへも該ポートからも転送されないバックアップ状態に構成する、スパニングツリーメカニズムと、メッセージが該ポートによって失われたのはいつかを決定するために、該ブリッジに結合されたポートをモニタリングするように構成されたモニタリングメカニズムとを備え、１つ以上のメッセージがポート上で失われた場合、該スパニングツリーメカニズムは、ある時間にわたって、メッセージがポートによって失われなくなるまで、メッセージを該ポートへも該ポートからも転送することを控えるように構成され、これにより、上記目的を達成する。
【００３４】
前記ある時間は、連続したスパニングツリーコンフィギュレーションメッセージ間にブリッジによって提供されたタイムインターバルよりも大きくてもよい。
【００３５】
前記モニタリングメカニズムは、メッセージが該ポートによって失われたかどうかを決定するために、該ポートと関連したハードウェアと通信するように構成されてもよい。
【００３６】
前記スパニングツリーメカニズムは、前記ネットワーク内のブリッジを繋ぎ合せるスパニングツリーにわたって繰返すことなくメッセージが転送されることを保証するように、前記ブリッジに結合されたポートを前記転送状態または前記バックアップ状態にするように構成されてもよい。
【００３７】
前記スパニングツリーメカニズムは、前記ネットワーク上のすべてのリンクのすべてのブリッジのうちの１つのブリッジをルートブリッジに選出し、各ノードから該ルートブリッジへの最短経路の距離を計算し、リンクごとに指定されたブリッジを該リンクのすべてのブリッジから選出し、ここで、該指定されたブリッジが、該ルートブリッジに最も近く、かつ、パケットを該リンクから該ルートブリッジに転送し、最良の経路を該ルートブリッジに提供するルートポートをブリッジごとに選択し、該スパニングツリー内に含まれるべき、各ブリッジ上のポートをセレクトし、ここで、該セレクトされたポートは、該ルートポートと、該ブリッジが該指定されたブリッジとして利用されるリンクに結合された任意のポートとを備え、セレクトされたポートを前記転送状態にし、すべての他のポートを前記バックアップ状態にするように構成されてもよい。
【００３８】
前記スパニングツリーメカニズムは、概して、ＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）標準規格８０２．１Ｄに従って動作してもよい。
【００３９】
前記リンクは、ＬＡＮ（ローカルエリアネットワーク）であってもよい。
【００４０】
（要旨）
本発明のある実施形態は、スパニングツリーコンフィギュレーションメッセージが失われた場合にループが生じることを防止する一方で、ネットワーク内のブリッジ上でスパニングツリープロトコルを実行するシステムを提供する。動作中、システムは、ブリッジ上でスパニングツリープロトコルを実行する。このスパニングツリープロトコルは、ブリッジに結合された各ポートを、メッセージがポートへもポートからも転送される転送状態か、または、メッセージがポートへもポートからも転送されないバックアップ状態に構成する。システムは、さらに、ブリッジに結合されたポートをモニタリングし、メッセージがポートによって失われたかどうかを決定する。１つ以上のメッセージがポート上で失われた場合、システムは、ある時間の間、ポートによってメッセージが失われなくなるまで、メッセージをポートへもポートからも転送することを控える。
【００４１】
この実施形態のある変形では、この時間の量は、連続したスパニングツリーコンフィギュレーションメッセージ間にブリッジによって提供されたタイムインターバルよりも大きい。
【００４２】
この実施形態のある変形では、ブリッジに結合されたポートをモニタリングするステップは、ポートと関連したハードウェアと通信して、メッセージがポートによって失われたかどうかを決定するステップを包含する。
【００４３】
この実施形態のある変形では、スパニングツリープロトコルを実行するステップは、ブリッジに結合されたポートを、ネットワークのブリッジを繋ぎ合せるスパニングツリーにわたって繰返すことなくメッセージが転送されることを保証するように、転送状態またはバックアップ状態にするステップを包含する。
【００４４】
この実施形態のある変形では、スパニングツリープロトコルを実行するステップは、ネットワーク上のすべてのリンクのすべてのブリッジ間の１つのブリッジをルートブリッジに選出するステップと、各ノードからルートブリッジへの最短経路の距離を計算するステップと、リンクごとに指定されたブリッジをそのリンクのすべてのブリッジから選出するステップであって、指定されたブリッジは、ルートブリッジに最も近く、かつ、そのリンクからルートブリッジにパケットを転送する、ステップと、ルートブリッジへの最良経路を提供するルートポートをブリッジごとに選択するステップと、スパニングツリーに含まれるべき各ブリッジ上のポートをセレクトするステップであって、セレクトされたポートは、ルートポートと、ブリッジが指定されたブリッジとして利用されるリンクに結合された任意のポートとを備える、ステップと、セレクトされたポートを転送状態にするステップと、すべての他のポートをバックアップ状態にするステップとを包含する。
【００４５】
この実施形態のある変形では、スパニングツリープロトコルは、概して、ＩＥＥＥ（Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ）標準規格８０２．１Ｄにより動作する。
【００４６】
この実施形態のある変形では、リンクはＬＡＮ（ローカルエリアネットワーク）である。
【発明の効果】
【００４７】
本発明によれば、スパニングツリーコンフィギュレーションメッセージが失われた場合にループの発生を防止することができる一方で、ネットワーク内のブリッジにわたってスパニングツリープロトコルを実行することができる。
【発明を実施するための最良の形態】
【００４８】
（詳細な説明）
以下の記載は、当業者が本発明を作製および使用することができるように提供され、かつ、特定のアプリケーションおよびその要件の文脈で提供される。開示された実施形態への種々の改変が、当業者に容易に明らかになり、かつ、本明細書中に定義された一般的原理は、本発明の主旨および範囲から逸脱することなく、他の実施形態および用途に適用され得る。従って、本発明は、示される実施形態に限定されることを意図されず、本明細書中に開示された原理および特徴と一致する極めて広い範囲と一致することを意図する。
【００４９】
この詳細な説明に記載されたデータ構造およびコードは、通常、コンピュータシステムが使用するコードおよび／またはデータを格納し得る任意のデバイスまたは媒体であり得るコンピュータ読み出し可能格納媒体に格納される。これは、ディスクドライブ、磁気テーブ、ＣＤ（コンパクトディスク）、およびＤＶＤ（デジタル多用途ディスクまたはデジタルビデオディスク）等の磁気および光学式格納デバイス、ならびに伝送媒体（信号が変調される搬送波をともなうか、ともなわない）で具現化されたコンピュータ命令信号を含むが、これらに限定されない。例えば、伝送媒体は、インターネット等の通信ネットワークを含み得る。
【００５０】
（ネットワーク）
図１は、本発明の実施形態によるブリッジを有する例示的ネットワーク１００を示す。図１に示されるように、ネットワーク１００は、複数のリンク１０６〜１１０を備える。本発明のある実施形態では、リンク１０６〜１１０は、イーサネット（登録商標）ベースのネットワーク等の、ローカルコンピューティングノード（ステーション）を繋ぎ合せるＬＡＮ（ローカルエリアネットワーク）である。より具体的には、図１において、リンク１０６は、ノード１１２〜１１４およびブリッジ１０２を繋ぎ合わせ、リンク１０７は、ノード１１５〜１１６およびブリッジ１０２〜１０３を繋ぎ合せ、リンク１０８は、ノード１１９〜１２０およびブリッジ１０３〜１０４を繋ぎ合わせ、リンク１０９は、ノード１１７〜１１８およびブリッジ１０３〜１０４を繋ぎ合わせ、リンク１１０は、ノード１２１〜１２３およびブリッジ１０４を繋ぎ合せる。
【００５１】
ブリッジ１０２〜１０４は、リンク１０６〜１１０をトランスペアレントに繋ぎ合せ、これにより、これらが組み合わされた単一のネットワークの一部分であるように見えるように設計されていることに留意されたい。
【００５２】
（スパニンツグリープロトコル）
スパニングツリープロトコルは、概して、図２を参照してすでに記載されたように動作する。しかしながら、いくつかの場合、ネットワークの輻輳がスパニングツリーコンフィギュレーションメッセージを失わせ得、これは、スパニングツリープロトコルがさらなるブリッジポートを誤ってオンにする原因となり得る。これは、ループを引き起こす可能性もあり得、ループは、スパニングツリープロトコルが決して回復しない点にまで輻輳の量を劇的に増加させ得る。
【００５３】
図３は、本発明の実施形態により、スパニングツリープロトコルが失われたメッセージを処理して、このようなループの発生を防止する態様を示すフローチャートを提供する。このシステムは、概して、図２を参照してすでに記載されたようにスパニングツリープロトコルを実行する（ステップ３０２）。同時に、システムは、ブリッジに結合されたポートをモニタリングする（ステップ３０４）。このモニタリングプロセスの間、システムは、メッセージが任意のポートによって「失われた」かどうかを決定する。システムがポートを通じて一つ以上のメッセージを送受信することができない場合に（ステップ３０６）、メッセージがポート上で「失われている」ことに留意されたい。
【００５４】
トラフィックを維持していないことをブリッジが知る態様に応じた実装例がある。本発明のある実施形態では、ＮＩＣカードは、カウンタをインクリメントして入来するメッセージが失われたことを示してドライバに通知する（例えば、バッファのオーバラン状態が原因で入来するメッセージが失われた場合）。これらのカウンタは、上層による検査のために利用可能である。
【００５５】
スパニングツリーメルトダウンが発生する別のケースは、ブリッジがそのスパニングツリーメッセージを伝送することができない場合である。これが発生する典型的なケースは、一方の方向に半２重として、もう一方の方向に全２重として構成されたリンクがある場合である。この場合、全２重側が十分なトラフィックを有する場合、半２重側は、伝送することができない。（このシステムは、放棄する前に、メッセージを１回以上送信しようとし得ることに留意されたい。）この状況は、半２重側によってのみ検出可能である。そのブリッジ（そのリンク上で半２重であると考えられるブリッジ）がそのリンクの指定されたブリッジであり、かつ、このブリッジがそのスパニングツリーメッセージを伝送し得ないと確信する場合、前述のシナリオにおけるように、このブリッジは、スパニングツリーアルゴリズムそれ自体を動作させるために最前をつくし続けるが、データトラフィックをリンクにおよびリンクから転送しない。
【００５６】
ステップ３０６にて、システムは、メッセージが失われていないと決定し、このシステムは、ステップ３０２に戻り、スパニングツリープロトコルの実行を継続する。
【００５７】
そうでない場合、メッセージがポートによって失われた場合、メッセージをポートへもポートからも転送する前に、システムは、十分な時間にわたってメッセージがポートによって失われなくなるまで待ち、次のスパニングツリーコンフィギュレーションメッセージがポート上で受取られることを保証する（ステップ３０８）。これは、ポートが、スパニングツリーコンフィギュレーションメッセージが失われた結果として、誤ってメッセージを転送しないことを保証する。これは、スパニングツリープロトコルによってループが誤って生成される確率を低減する。
【００５８】
転送状態にあるポート上でメッセージが失われた場合、関連したブリッジは、これがポートをバックアップ状態に変更すべきであったことを認識し得ず、なぜなら、別のブリッジが、指定されたブリッジであるための資格をより満たしているからであることに留意されたい。他方、メッセージがバックアップ状態にあるポート上で失われた場合、ブリッジは、そのブリッジがポート（おそらく、ルートブリッジ）に指定されたブリッジであると想定し得、そして、実際に資格をより満たすブリッジが存在するときに、そのポートを誤って転送状態に変更し得る。
【００５９】
本発明の実施形態のこれまでの記載は、例示および説明の目的で提供されたにすぎない。これらの記載は、本発明を網羅すること、または、開示された形態に限定することを意図しない。従って、複数の改変および変種が当業者に明らかである。当業者は、本発明の具体的な好ましい実施形態の記載から、本発明の記載および技術常識に基づいて等価な範囲を実施することができることが理解される。さらに、上述の開示は、本発明を限定することを意図しない。本発明の範囲は、添付の請求の範囲によって定義される。
（要約）
本発明のある実施形態は、スパニングツリーコンフィギュレーションメッセージが失われた場合にループが生じることを防ぐ一方で、ネットワーク内のブリッジ上でスパニングツリープロトコルを実行するシステムを提供する。動作中、システムは、ブリッジ上でスパニングツリープロトコルを実行する。このスパニングツリープロトコルは、ブリッジに結合された各ポートを、メッセージがポートへもポートからも転送される転送状態か、またはメッセージがポートへもポートからも転送されないバックアップ状態に構成する。システムは、さらに、ブリッジに結合されたポートをモニタリングし、メッセージがポートによって失われたかどうかを決定する。１つ以上のメッセージがポート上で失われた場合、システムは、メッセージがある時間にわたってポートによって失われなくなるまで、ポートへもポートからもメッセージの転送を控える。
【図面の簡単な説明】
【００６０】
【図１】図１は、本発明の実施形態による、ブリッジを有する例示的ネットワークを示す。
【図２】図２は、スパニングツリープロトコルを示すフローチャートを提供する。
【図３】図３は、本発明の実施形態による、スパニングツリープロトコルが、失われたメッセージを処理する態様を示すフローチャートを提供する。
【符号の説明】
【００６１】
１００  ネットワーク
１０２〜１０４  ブリッジ
１０６〜１１０  リンク
１１２〜１２３  ノード
【図１】
2005110253.tif 000003
【図２】
2005110253.tif 000004
【図３】
2005110253.tif 000005