(57)【要約】複数のホストプロセッサー（１０）、複数のノード（１６）、これらのノード（１６）を接続する複数のセグメント（１４）を有している通信ネットワークにおける望ましくないループを検出して除去する方法、装置、およびコンピュータ可読型メディア。方法の実施形態は、少なくとも１つのネットワーク流れについて、上記ノード（１６）および上記セグメント（１４）を経るネットワーク（１）トラフィック流れの方向に関する一組の定常状態データを収集するとともに記憶するステップ、新たにサンプル抽出された流れを記憶済み定常状態データと比較して、それらのパスがそれらの定常状態方向と矛盾した流れを検出するステップ、および、あるセグメント（１４）がそのような矛盾した流れを搬送するときにネットワークループを認識するステップを含んでいる。  【選択図】  図４
2015517284.tif 000002
【特許請求の範囲】
【請求項１】
あるネットワークにおけるデータ流れの方向に関する情報を受信するステップ、
定常状態におけるデータ流れの方向に関する情報をメモリー構成要素から受信し、前記ネットワークが前記定常状態においてループのないものであるステップ、
前記ネットワークにおける前記データ流れの前記方向が定常状態におけるデータ流れの前記方向と矛盾するかどうかについての判断を行うステップ、および
前記ネットワークにおけるデータ流れの前記方向と前記定常状態におけるデータ流れの前記方向との間の矛盾に応じて、前記ネットワークにおける閉ループの存在を認識するステップ
を含んでいる方法。
【請求項２】
前記ネットワークにおけるデータ流れの前記方向と前記定常状態におけるデータ流れの前記方向との間の矛盾に応じて複数のループポインターを作成し、前記複数のループポインターのうちのあるループポインターが前記定常状態におけるデータ流れの方向を指し示すステップ、および前記複数のループポインターに基づいて前記ネットワークのセグメントを前記閉ループの一部として認識し、前記セグメントが、第１ネットワークノードを第２ネットワークノードへ連結するとともに、これらの間にデータパスをもたらすステップ
をさらに含んでいる請求項１に記載の方法。
【請求項３】
前記セグメントを前記閉ループの一部として認識するステップに応じて前記セグメントを機能無効にするステップ
をさらに含んでいる請求項２に記載の方法。
【請求項４】
前記閉ループの存在を認識するステップに先立って、前記ネットワークにおけるセグメントに関連した定常状態情報の欠如があるかどうかについての判断を行い、前記セグメントが、第１ネットワークノードを第２ネットワークノードへ連結するとともに、これらの間にデータパスをもたらし、さらに、２つのループポインターが、互いに逆の方向に、かつ、前記定常状態情報の欠如に応じて作成されるステップ、および
前記セグメントが前記閉ループの一部であるかどうかについての判断を前記２つのループポインターを利用して行うステップ
をさらに含んでいる請求項１に記載の方法。
【請求項５】
前記ネットワークにおけるデータ流れをある時間帯にわたってサンプル抽出し、このサンプル抽出するステップがさらに別のデータ流れの方向を認識するステップ、
前記定常状態におけるものと同一の方向における前記さらに別のデータ流れの速度が前記のある時間帯にわたって減少しているかどうかについての判断を行うステップ、
前記定常状態におけるものと逆の方向における前記さらに別のデータ流れの速度が前記のある時間帯にわたって増大しているかどうかについての判断を行うステップ、および
前記同一の方向における前記さらに別のデータ流れの前記速度が減少しているとともに前記逆の方向における前記さらに別のデータ流れの前記速度が増大しているとの判断に応じて、前記ネットワークに閉ループがないことについての判断を行うステップ
をさらに含んでいる請求項１に記載の方法。
【請求項６】
前記ネットワークにおけるあるセグメントが前記閉ループの一部であるかどうかについての判断を行い、前記セグメントが、前記ネットワークにおけるネットワークノードどうしを連結するとともに、前記ネットワークノードへかつ前記ネットワークノードから流れるデータのためのパスをもたらすステップ、
前記セグメントに関連した帯域幅についての判断を行うステップ、および
前記セグメントが低い帯域幅を有しているという判断に応じて、さらに、前記セグメントが前記閉ループの一部であるという判断に応じて、前記セグメントを前記ネットワークから機能無効にするステップ
をさらに含んでいる請求項１に記載の方法。
【請求項７】
前記ネットワークは、ネットワークスイッチ、ルータ、ホストコンピュータ、および、前記ネットワークスイッチ、前記ルータおよび前記ホストコンピュータを連結するセグメントの組み合わせを備えている請求項１に記載の方法。
【請求項８】
あるネットワークにおけるある機器と交信するように構成されたネットワークインターフェイス、および
前記ネットワークが閉ループを含んでいるかどうかについての判断を行うとともに、
前記ネットワークが前記閉ループを含んでいるとの判断に応じて、前記閉ループを前記ネットワークから除去する
ように構成されたモジュール
を備えてなる装置。
【請求項９】
前記ネットワークが閉ループを含んでいるかどうかについての前記判断は、
前記ネットワークにおけるデータ流れの方向に関する情報を受信するステップ、
定常状態におけるデータ流れの方向に関する情報を受信し、前記ネットワークが前記定常状態においてループのないものであるステップ、
前記ネットワークにおける前記データ流れの前記方向が定常状態におけるデータ流れの前記方向と矛盾するかどうかについての判断を行うステップ、および
前記ネットワークにおけるデータ流れの前記方向と前記定常状態におけるデータ流れの前記方向との間の矛盾に応じて、前記ネットワーク流れにおける前記閉ループの存在を認識するステップ
を含んでいる請求項８に記載の装置。
【請求項１０】
前記モジュールは、
前記ネットワークにおけるデータ流れの前記方向と前記定常状態におけるデータ流れの前記方向との間の矛盾の判断に応じて複数のループポインターを作成し、前記複数のループポインターのうちのあるループポインターが、前記定常状態におけるデータ流れの方向を指し示し、
かつ、前記複数のループポインターに基づいて前記閉ループを含んでいる前記ネットワークのセグメントを認識し、前記セグメントが、第１ネットワークノードを第２ネットワークノードへ連結するとともに、これらの間にデータパスをもたらし、さらに、前記閉ループの前記除去が、前記セグメントを作動しないようにするように構成されている請求項９に記載の装置。
【請求項１１】
前記モジュールは、
前記ネットワークにおけるあるセグメントに関連した定常状態情報の欠如があるかどうかについての判断を行い、前記セグメントが、第１ネットワークノードを第２ネットワークノードへ連結するとともに、これらの間に第１データパスをもたらし、
前記セグメントが前記閉ループの一部であるかどうかについての判断を行うように
さらに構成され、２つのループポインターが、互いに逆方向に、かつ、定常状態情報の欠如に応じて作成され、
前記セグメントが前記閉ループの一部であるかどうかについての前記判断は、前記２つのループポインターを利用するものであり、さらに、
前記閉ループの除去は、前記セグメントが前記閉ループの一部であるとの判断に応じて前記セグメントのリンク解除プロセスを起動するように構成されている請求項８に記載の装置。
【請求項１２】
前記モジュールは、
前記ネットワークにおけるあるセグメントが、前記閉ループの一部であるかどうかについての判断を行い、前記セグメントが、第１ネットワークノードを第２ネットワークノードへ連結するとともに、これらの間にデータパスをもたらし、前記セグメントに関連した帯域幅についての判断を行い、
前記閉ループの除去は、前記セグメントが低い帯域幅を有しているとの判断に応じて、さらに、前記セグメントが前記閉ループの一部であるとの判断に応じて、前記セグメントを前記ネットワークから作動しないように構成されている請求項８に記載の装置。
【請求項１３】
この装置はネットワーク用機器である請求項８に記載の装置。
【請求項１４】
前記モジュールは、
前記ネットワークにおけるデータ流れを、ある時間帯にわたってそのデータ流れの方向を認識することでサンプル抽出し、
定常状態におけるものと同一の方向におけるデータ流れの速度が前記のある時間帯にわたって減少しているかどうかについての判断を行い、
前記定常状態におけるものと逆の方向におけるデータ流れの速度が前記のある時間帯にわたって増大しているかどうかについての判断を行い、さらに
前記同一の方向におけるデータ流れの速度が減少しているとともに前記逆の方向におけるデータ流れの速度が増大しているとの判断に応じて、前記ネットワークに閉ループがないことについての判断を行うように
さらに構成されている
請求項８に記載の装置。
【請求項１５】
ある機器によって実行された場合には、
ネットワークが閉ループを含んでいるかどうかについての判断を行うステップ、および
前記ネットワークが閉ループを含んでいるとの判断に応じて、前記閉ループの一部であるセグメントを認識するステップであって、前記セグメントが、第１ネットワークノードを第２ネットワークノードへ連結するとともに、これらの間にデータパスをもたらすステップを含む方法をその機器に実行させる、
そこに記憶されたコンピュータ実行可能命令を有している非一時的コンピュータ可読型メディア。
【請求項１６】
前記セグメントを前記閉ループの一部として認識するステップに応じて前記セグメントを前記ネットワークから機能無効にするステップ
をさらに含んでいる請求項１５に記載の方法。
【請求項１７】
前記セグメントに関連した帯域幅についての判断を行うステップ、および
前記セグメントが低い帯域幅を有しているという判断に応じて、さらに、前記セグメントを前記閉ループの一部として認識することに応じて、前記セグメントを前記ネットワークから機能無効にするステップ
をさらに含んでいる請求項１５に記載の方法。
【請求項１８】
前記ネットワークが閉ループを含んでいるかどうかについての判断を行うステップは、
前記ネットワークにおけるデータ流れの方向に関する情報を受信するステップ、
定常状態におけるデータ流れの方向に関する情報を受信するステップであって、前記ネットワークが前記定常状態においてループのないものであるステップ、
前記ネットワークにおける前記データ流れの前記方向が定常状態におけるデータ流れの前記方向と矛盾するかどうかについての判断を行うステップ、および
前記ネットワークにおけるデータ流れの前記方向と前記定常状態におけるデータ流れの前記方向との間の矛盾に応じて、前記ネットワークにおける前記閉ループの存在を認識するステップ
を含んでいる請求項１５に記載の方法。
【請求項１９】
前記ネットワークにおける前記データ流れの方向が定常状態におけるデータ流れの方向と矛盾するかどうかについての判断を行うステップであって、前記ネットワークが前記定常状態においてループのないものであるステップ、および
前記ネットワークにおけるデータ流れの前記方向と定常状態におけるデータ流れの前記方向との間の矛盾の判断に応じて複数のループポインターを作成するステップであって、前記複数のループポインターのうちのあるループポインターが定常状態におけるデータ流れの方向を指し示すステップ
をさらに含み、
前記セグメントを前記閉ループの一部として認識するステップは、前記複数のループポインターに基づくものである
請求項１５に記載の方法。
【請求項２０】
前記セグメントに関連した定常状態情報の欠如があるかどうかについての判断を行うステップをさらに含み、２つのループポインターが、互いに逆の方向に、かつ、前記定常状態情報の欠如に応じて作成され、さらに、前記セグメントを認識するステップは、前記２つのループポインターに基づくものである
請求項１５に記載の方法。
【発明の詳細な説明】
【関連出願】
【０００１】
この出願は、同一の発明者であるSachin Surendranによって２０１２年４月１９日に提出された米国出願番号第１３／４５２，０２２号についての利益および優先権を主張するものであり、その開示はこの明細書の中に、全体としてかつあらゆる目的のために組み入れられている。
【技術分野】
【０００２】
この明細書の中に開示された実施形態は、デジタル・パケット・ネットワークのような通信ネットワークの分野に関連するものであり、また、さらに詳しくは、望ましくないネットワークループの問題に関連するものである。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
望ましくないネットワークループは、大規模通信ネットワークおよび小規模通信ネットワークにおける共通の問題である。このようなループは、ネットワーク・ブロードキャスト・ストームを引き起こすことがあり、それによってネットワークの帯域幅および性能の劣化を招きかねない。このようなストームは、ホストプロセッサーを重複するパケットであふれさせることがあり、それによってそのホストにおけるＣＰＵ稼働率の低下を招きかねない。
【課題を解決するための手段】
【０００４】
複数のホストプロセッサー（１０）、複数のノード（１６）、これらのノード（１６）を接続する複数のセグメント（１４）を有している通信ネットワークにおける望ましくないループを検出して除去する方法、装置、およびコンピュータ可読型メディア。方法の実施形態は、少なくとも１つのネットワーク流れについて、上記ノード（１６）および上記セグメント（１４）を経るネットワーク（１）トラフィック流れの方向に関する一組の定常状態データを収集するとともに記憶するステップ、新たにサンプル抽出された流れを記憶済み定常状態データと比較して、それらのパスがそれらの定常状態方向と矛盾した流れを検出するステップ、および、あるセグメント（１４）がそのような矛盾した流れを搬送するときにネットワークループを認識するステップを含んでいる。
【図面の簡単な説明】
【０００５】
複数の実施形態が、添付図面における複数の図において、例示として、また限定によることなく示されており、さらに、それらの図において、類似した符号は類似した要素を意味している。
【０００６】
【図１】図１は、１つの実施形態に係るネットワークのネットワークトポロジーを示している。
【０００７】
【図２】図２は、図１のネットワーク１の概略図であり、ホストプロセッサー１０（Ａ）から出るブロードキャスト流れを示している。
【０００８】
【図３】図３は、図２のネットワーク１の概略図であり、その中には、スイッチ１２（５）とスイッチ１２（６）との間に生じる新たなセグメント１４（５，６）によってループが存在している。
【０００９】
【図４】図４は、図３のネットワークを示しており、その中において、ループポインター１７が上記ループを集合的に指し示している。
【００１０】
【図５】図５は、意図的なネットワーク１の再構成が望ましくないループから区別された方法の実施形態を示しているフローチャートである。
【発明を実施するための形態】
【００１１】
この明細書の中に記載されたいくつかの実施形態では、望ましくないネットワークループを正確に検出するとともに認識することができる。取得されたネットワークループ情報は、改善措置を教唆してそのループを除去するために利用することができる。この処理手続は、自動化することができ、それによって自己回復型ネットワークが自己診断型ネットワークとともにもたらされる。
【００１２】
この明細書の中に開示された複数の実施形態は、レイヤー２のデータネットワークへ適用することができる。レイヤー２のデータネットワークについての複数の実施形態を説明することは、代表的なことであり、これらの実施形態の適用範囲を制限することを意図していない。例えば、この明細書の中に記載された複数の実施形態は、レイヤー３デジタルネットワークにおいても、レイヤー２ネットワークおよびレイヤー３ネットワーク以外のデジタルネットワークにおいても、またアナログネットワークにおいても使用することができる。デジタルネットワークについては、データは、これらのデータを観察することでそれらの流れを識別することができる限り、分解する必要がない。
【００１３】
いくつかの実施形態では、意図的なネットワーク再構成とネットワークループとは区別することができる（図５を参照のこと）。この特性によって、フォールスポジティブが最小限になる。
【００１４】
いくつかの実施形態では、ネットワーク１のリアルタイム状態についての情報を収集するために、パケットサンプル抽出法が利用される。パケットサンプルは、エス流れ、ネット流れ、あるいは他のパケットサンプル抽出用プログラムのようなプロセス（プログラム）によって取得することができる。この明細書の中で使用されたように、「トラフィック流れ」とは、類似した特性（例えば、ソース１０および宛先１０）を共有するトラフィック（可動データ）の流れである。ループが存在しないときにある時間帯にわたって上記サンプルから収集された流れ情報は、「定常状態情報」と称される。
【００１５】
この定常状態において、上記ネットワーク１は、図２に示されたように、閉じられたデータパス（ループ）のないツリーとして表すことができる。すべてのトラフィックの流れについて、ソース１０から宛先１０までパスをたどることができる。このパスは、ノード１６（ネットワーク１の中に存在しているスイッチ１２のそれぞれのポートがネットワークノード１６である）どうしを接続する個々のセグメント１４に分けることができる。それぞれのトラフィック流れについて、トラフィックはそれぞれのセグメント１４に沿って単一方向へ流れることができる。この方向は、習得されるとともに、上記定常状態に記録される。
【００１６】
ある集中型実施形態では、記録されたこの状態は、収集されるとともに、サンプル抽出されたパケットを処理するネットワーク管理コンピュータ（処理用要素）に記憶される。ホストプロセッサー１０がその処理用要素の役割を実行することができる。ある代わりの実施形態では、上記処理用要素は別個のコレクター１１であってもよく、その場合、そのコレクター１１は、任意の種類の接続部によってネットワーク１へ接続することができる。
【００１７】
ネットワーク１の中に望ましくない閉ループパスが作成されると、ネットワークストームが起きることがある。パケットは、ある閉ループの中でこのパスに沿って際限なく移動するおそれがある。このことは、以下で図３および図４とともに、いっそう充分に説明される。望ましくないループが生じると、多くのセグメント１４における流れの単一方向性が乱されて、これらのセグメント１４は、同一の全ネットワーク流れのための双方向性流れを搬送する。これらの流れによって、それらの定常状態方向と矛盾するパスの取得が始まる。流れ方向のこの乱れは、記憶済み定常状態情報を利用することと、その情報を新たにサンプル抽出されたパケット情報と比較することとによって、検出することができるが、そのパケット情報は、進入方向および退出方向の両方におけるすべてのポート（ノード）１６についてサンプル抽出されたものである。
【００１８】
この明細書の中に記載されたいくつかの実施形態には、ループポインター１７の概念が含まれている。ループポインター１７とは、すべてのセグメント１４に対してローカルである方向性ポインターをいう。すべてのポインター１７は、ネットワーク１におけるループの方向を指し示す。
【００１９】
矛盾したパケットサンプル、すなわち、特定のセグメント１４におけるその特定の流れの記憶済み定常状態方向を乱すパケットサンプルが検出されたあらゆる時点で、そのセグメント１４についてのループポインター１７が作成される。このループポインター１７は、上記矛盾したパケットサンプルの移行方向とは逆の方向を向いている。
【００２０】
時間が経過すると、ネットワーク１における望ましくないループによって一組のループポインター１７が作成されることになる。これらのループポインター１７によって、ネットワーク１における複数のノード１６を通過する連続的な連結リストが形成される。これらのループポインター１７は、ネットワーク１の至る所に作成される。ネットワーク１におけるすべてのループポインター１７は、解析される流れの数にかかわりなく、また、これらのループポインター１７がネットワーク１のどこに位置するかにかかわりなく、そのループの方向を常に指し示す。これらの多重流れの場合には、これらのループポインター１７は、相異なるトラフィック流れによって作成されるにもかかわらず、常にループを指し示すとともに、そのループに導かれる。
【００２１】
ループポインター１７は、上記定常状態情報と矛盾した流れ情報について作成されるものであって、現存する定常状態情報と一致する流れ情報について作成されるものではない、ということに留意すべきである。
【００２２】
上記集中型実施形態では、ループ位置情報は、分散された複数のノード１６から（または、上記ノードに関連した複数のルータあるいはスイッチ１２から）収集されるが、単一のネットワーク管理要素（処理用要素）１０，１１によって集合的に記憶されるとともに処理される。
【００２３】
ある代わりの実施形態（上記「分散型」実施形態）では、上記定常状態情報の記憶作業および処理作業は分散された方式で実行される。この実施形態では、それぞれのノード１６に関連したソフトウェア、ファームウェア、および／またはハードウェアモジュールによって、あるセグメントに双方向流れが存在しているかどうかが判断される。従って、ループポインター１７はそのセグメントに作成される。上記モジュールは、ループポインター１７の存在を明らかにすることができるとともに、ループポインター１７の方向における情報をセグメント１４の他方端部で同等ノード１６へ伝達することができる。さらにまた、ループのスパンが認識されると、そのループの中に存在する任意のノード１６は、そのループを切断することができるとともに、それによってそのストームを終わらせることができる。
【００２４】
あらかじめ定義された規則を利用することで、ネットワーク管理ホスト１０あるいはコレクター１１（上記集中型実施形態における）、またはネットワーク用ノード１６（上記分散型実施形態における）は、ネットワーク１のループを完全に自律的なやり方で診断することができるとともに終わらせることができる。このようにして、この明細書の中に記載された複数の実施形態によれば、ネットワークを自己回復させるとともに自己診断させることのできる機構がもたらされる。
【００２５】
上記集中型実施形態および上記分散型実施形態は互いに排他的なものではなく、それらは同時に機能することができる。
【００２６】
図１は、６つのスイッチ１２と８つのホストプロセッサー１０とがある代表的なネットワーク１を示している。図１は、例示を目的として、レイヤー２型デジタルパケット切換ネットワークを示している。全部で６つのスイッチ１２におけるすべてのポート１６には、進入方向および退出方向の両方において作動可能にされたサンプル抽出機能が備わっている。すべてのサンプルは、この例では単一のコレクター１１へ送信される。コレクター１１は、図面の雑然性を回避するために、たとえそれがすべてのノード１６へ接続されているときでも、単一破線で示されている。コレクター１１が使用されているこの特定の事例では、この明細書の中に記載されたすべての方法ステップは一般に、上記処理用要素としてのコレクター１１によって実行される。
【００２７】
それぞれのポート１６はこのネットワーク１の中におけるノードと称され、また、２つのノード１６どうしを接続するリンクはセグメント１４と称される。これらのセグメント１４は、銅線、マイクロ波信号、光ケーブルなどが含まれる現在あるいは未来の任意の手段によって物理的に具体化することができる。図１は、実際の任意のトラフィックが上記パスを流れるかどうかにかかわりなく、上記パスが存在していることを指し示すために、これらのセグメント１４を実線として示している。これらのセグメント１４はまた、物理的なリンクというよりも、２つのノード１６どうしの間における論理的接続部であってもよい。例えば、１つの実施形態では、個々のＶＬＡＮの内部における複数のループが検出される。
【００２８】
図２は、ソースホストプロセッサー１０（Ａ）からの、ブロードキャストフレームについてのトラフィック流れ（単一流れ）の定常状態方向を（破線で）示している。ブロードキャストメッセージはネットワーク１の中におけるすべてのホスト１０へ送信される。この流れについてのパケットは、これらのサンプルをコレクター１１へ送信する複数のノード１６によってあらかじめ設定されたサンプル抽出速度でサンプル抽出される。これらのサンプルから収集された情報は、コレクター１１の中に記録される。この情報の本体は定常状態情報と呼ばれる。このコレクター１１によって、特定のトラフィック流れについて、それぞれのセグメント１４における流れの方向が記録される。
【００２９】
図３は、スイッチ１２（５）とスイッチ１２（６）との間に新たな望ましくない接続部１４（５，６）が生じたことを示している。この接続部は、設計のまずさ、あるいは人為ミス、またはこれら２つの組み合わせによって、例えばソフトウェアエラーによって起きることがあり、また、新たな閉ループパスを作成することがある。この望ましくないループは、このループを完全なものにする新たに形成された上記接続部１４（５，６）によって、スイッチ１２（４）、１２（５）、および１２（６）を経て進行する。
【００３０】
図３において、ポート１６（６，１）とポート１６（６，２）との間、およびポート１６（５，１）とポート１６（５，２）との間における新たな破線がそのループを完全なものにする、ことに留意すべきである。
【００３１】
図４は、新たに導入されたループが、この特定の流れについて、ループ状に折り返されるホスト１０（Ａ）からネットワーク１の中へのブロードキャストトラフィックを引き起こす、ということを示している。図４では、この矛盾した流れは、元の流れを表示する破線におけるダッシュ記号よりも短いダッシュ記号を有している破線によって表示されている。この矛盾した流れは、２つの箇所で生じる。
・スイッチ１２（５）では、ポート１６（５，２）。
・スイッチ１２（６）では、ポート１６（６，２）。
【００３２】
図４では、図面の雑然性を回避するために、１つの流れが示されているが、実際には、１つのネットワーク流れあるいはいくつかのネットワーク流れを観察することで、ループを検出することができる。あらかじめ設定されたサンプル抽出時間の間に、１つのホスト１０、あるいは２つ以上のホスト１０が、ネットワーク１にわたってデータを送信することができる。
【００３３】
スイッチ１２（５）およびスイッチ１２（６）は、ループ状に折り返された上記トラフィックをスイッチ１２（５)，１２（６）へ入るブロードキャストトラフィックとして扱い、従って、ループ状に折り返されたそのトラフィックをネットワーク１の全体にわたって送信する。このブロードキャストトラフィックは、ネットワーク１の全体にわたって送信されるだけでなく、スイッチ１２（４）、１２（５）、および１２（６）を接続するパスの中にループ状態を維持することも行う。これによって、パケットストームが引き起こされる。
【００３４】
このストームの間に、セグメント１４に収集されたサンプル抽出済みパケットに関する流れの矛盾した方向は、処理用要素１０，１１，１６によって保存済み上記定常状態からの流れの方向と比較されるときに、処理用要素１０，１１，１６が一組のループポインター１７を作成することになる。
【００３５】
ある時間帯（サンプル抽出速度のようなシステムのパラメータに基づいた）の後に、これらのループポインター１７は、ホスト１０（Ａ）から始まって上記ループへ至る１つ以上のパスをたどるであろう。図４の例では、これらのループポインター１７は、上記ループで終わる２つのパスをたどる。
パス１：スイッチ１２（１）→スイッチ１２（３）→スイッチ１２（４）（ポート１６（４，１））→スイッチ１２（６）（ポート１６（６，１））→スイッチ１２（５）（ポート１６（５，２））
パス２：スイッチ１２（１）→スイッチ１２（３）→スイッチ１２（４）（ポート１６（４，１））→スイッチ１２（５）（ポート１６（５，１））→スイッチ１２（６）（ポート１６（６，２））
【００３６】
この例では、流れのループポインター１７は、それらが上記ループの中に入ると別れ、次いで、再び出会ってそのループを完全なものにする。そのため、上記事例の場合には、パス１およびパス２におけるループポインター１７は、スイッチ１２（４）（ポート１６（４，１））で別れ、次いで、スイッチ１２（５）（ポート１６（５，２））およびスイッチ１２（６）（ポート１６（６，２））で合流してそのループを完全なものにする。この情報を利用することで、処理用要素１０，１１，１６によってループが検出される。
【００３７】
処理用要素１０，１１，１６は、集中型実施形態におけるものであろうと分散型実施形態におけるものであろうと、ループを引き起こした新たなセグメント１４を自律的に検出することができる。この実施形態では、ポート１６（５，２）とポート１６（６，２）とを接続しているリンク１４（５，６）が、そのループの原因として自動的に認識される。不良セグメント１４を認識するファイル属性は次のとおりである。
・その不良セグメント１４が、サンプルをトラフィック流れについての矛盾する方向情報とともに送信する。
・その不良セグメント１４が、定常状態を備えていない。
【００３８】
これら２つの条件は、ループを作成するとともに逆方向に向けられる新たなセグメント１４についての２つのループポインター１７をもたらす上記新たなセグメント１４の事例において、満たされる。これらのファイル属性によって、上記ループの位置的原因が一義的に認識される。
【００３９】
ストームの間には高い蓋然性でパケット損失が存在しており、このため、コレクター１１へのサンプルパケットの確実な移送が必要である。このことは、次の２つの方法によって達成することができる。
１.  帯域外管理型ＶＬＡＮ（仮想ローカル・エリア・ネットワーク）を利用して、上記サンプル抽出データをコレクター１１へ送信すること。このＶＬＡＮは上記ストームの一部ではないので、それは影響を受けることがない。このＶＬＡＮはネットワーク１をソフトウェアオーバーレイの形態で監視する。
２.  パケットのヘッダーに含まれた情報に基づいて上記サンプル抽出パケットを優先順位付けすること。これによって、上記サンプル抽出パケットが上記ストームを存続させてコレクター１１へ至らせる蓋然性が増大する。
【００４０】
２、３のサンプルの損失は、上記ループを検出するアルゴリズムの機能に影響を及ぼすことがないであろうし、また、その効果は検出処理を遅らせることであろう。
【００４１】
上記の分散型ループ検出実施形態では、ループの検出は、個々のネットワーク用ノード１６（ルータに関連したものであろうとスイッチ１２に関連したものであろうと）のそれぞれで実行されるか、または関連したルータ自体あるいはスイッチ１２自体によって実行される。従って、この実施形態における諸要素１６は、このネットワーク１の内部にすべて含まれており、また、単一の破損箇所は存在しない。この実施形態は、外部コレクター１１あるいは他の要素を必要とすることがなく、また、自己回復することのできるネットワーク１を実現する。
【００４２】
ある分散型実施形態では、それぞれのネットワーク用ノード１６は、上記サンプルを収集するとともに、流れおよび方向の情報を導き出す。このプロセスは、図４とともに説明されたように、ループポインター１７の作成をもたらす事象を検出するとともに、直接接続された（同等の）ノード１６において実行される同等プロセスと交信する。このプロセスが矛盾した流れを検出すると、このプロセスは、ただちにメッセージを同等ノード１６へ送信する。このループポインターメッセージには、ループポインター１７の作成をもたらした流れに関する情報が含まれている。このメッセージは、ループポインター１７が観察されたリンク１４に関して送信される。これらのメッセージは、ループポインター１７の方向に送信される。
【００４３】
すべてのループポインター１７によって、接続された同等ノード１６へメッセージが送信される。最終的に、そのメッセージは、特定のセグメント１４についての逆方向におけるループポインター１７をも有しているノード１６へ至るであろう。図４では、この事象は、ポート１６（６，２）およびポート１６（５，２）に関して起きる。あるセグメント１４についての両方向におけるループポインターメッセージの存在は、完全なループを意味している。この時点までの諸ステップはループ検出機構を構成している。
【００４４】
この明細書の中に記載された集中型実施形態および分散型実施形態のすべてについて、処理用要素１０,１１,１６は、上記ネットワークループを相異なる２つのやり方で除去することができる。
・ 上記ループをもたらした新たに作成されたリンク１４をリンクダウン(切断)すること。
・  上記ループの最下位の帯域幅のリンクセグメント１４におけるリンクダウンをすること。これによって、上記ループの進行が止まるが、好都合なことに、ネットワーク１の高帯域幅部分はアクティブのままに維持される。この目的のために、「最下位の帯域幅」は、このセグメント１４によって実際に搬送されるトラフィックの量にかかわりなく、そのセグメント１４の帯域幅を表している。
【００４５】
処理用要素１０,１１,１６は、図５に示されたように、望ましくないネットワークループを意図的なネットワーク再構成から識別することができる。
【００４６】
ネットワーク１がシステム管理者によって再構成されると、ホスト１０の接続部は異なったスイッチ１２へ変わるであろう。従って、そのホスト１０は、トラフィックを、異なった方向に、すなわち、それがトラフィックを初めに送信した方向とは逆の方向に送信するであろう。われわれは、ネットワークループのフォールスポジティブ宣言を誘発するこの現象を望んでいない。
【００４７】
処理用要素１０,１１,１６は、以下の規則を利用して、意図的なネットワーク再構成とネットワークループとを識別する。意図的なネットワーク再構成は、次の場合に診断される。
１．  上記定常状態方向にある流れの新たなサンプルが、あらかじめ設定された時間帯にわたってゼロまで減少するとともに、
２．  （定常状態に対して）逆の方向にある流れの新たなサンプルが、上記のあらかじめ設定された時間帯にわたって増加する場合。
【００４８】
ネットワークループは、以下の矛盾が維持される場合に診断される。
１．  上記定常状態方向にある流れの新たなサンプルが、あらかじめ設定された時間帯の終了時点で記録され続けていて、また
２．  （定常状態に対して）逆の方向にある流れの新たなサンプルもまた、条件（１）におけるのと同一の時点で記録され続けていて、さらに
３．  上記ループがネットワーク１の中に存在する限り、条件（１）および条件（２）のサンプルが存続している場合。
【００４９】
上記３条件が満たされると、ネットワークループが示される。上記の規則を利用することで、処理用要素１０,１１,１６は、意図的なネットワーク再構成からネットワークループを識別する。図５はこのことを達成する方法ステップを示している。
【００５０】
図５に示された方法ステップは、この明細書の中に例示されかつ記載された他のすべての方法と同様に、処理用要素１０,１１,１６に関連した１つ以上のモジュールによって実行される。これらのモジュールは、ハードウェア、ソフトウェア、ファームウェア、またはこれらの任意の組み合わせにおいて実施される。これらのモジュールがソフトウェアにおいて実施されるときには、上記モジュールは、一連のコンピュータプログラム命令として、１つ以上のコンピュータ可読型メディアに常駐させることができる。
【００５１】
このコンピュータ可読型メディアは、コンピュータプログラム命令を記憶するための任意の手段であり、ハードディスク、フロッピー（登録商標）ディスク、光ディスク、ＣＤ、ＤＶＤ、サムドライブなどがこれに含まれる。
【００５２】
図５の方法はステップ５１で開始され、そこでは、処理用要素１０,１１,１６は例示の目的のために流れＸと称される特定の流れのサンプルを受け取る。
【００５３】
ステップ５２では、上記サンプルが上記定常状態において先に記録されたものと同一の方向に流れているかどうかについて、処理用要素１０,１１,１６が判断を行う。それに対する答えが「はい」であるときには、処理用要素１０,１１,１６は、ステップ５３において、受けた正常流れと称されるパラメータが真実であると定める。その処理用要素１０,１１,１６は、ステップ５２についての上記質問に対する答えが「いいえ」であるときには、受けた矛盾流れと称されるパラメータが真実であると定めるとともに、上記の受けた正常流れのパラメータが虚偽であると定める。
【００５４】
この方法はその後、ステップ５５へ進む。処理用要素１０,１１,１６は、正常流れのパラメータが真実であるかどうか、さらに、矛盾流れのパラメータもまた真実であるかどうかについて尋ねる。これらに対する答えが両方とも「はい」であるときには、ループの存在が表明され、この方法はステップ５６へ進む。そうでないときには、この方法はステップ５１へ戻る。
【００５５】
ステップ５６では、ループ検出個数というカウンターが増やされ、受けた正常流れが虚偽であると定められ、受けた矛盾流れが虚偽であると定められ、そして、この方法はステップ５７へ進む。
【００５６】
ステップ５７では、処理用要素１０,１１,１６は、カウンターであるループ検出個数があらかじめ設定された閾値を超えているかどうかについて尋ねる。この閾値は経験的に設定されており、また、ネットワークループのフォールスポジティブ判断を最小限にするために充分高いものに設定されている。ステップ５７において発せられた質問に対する答えが「はい」であるときには、この方法はステップ５８へ進み、そこで、ネットワークループが実際に存在したことが確認される。この時点で、適切な自己回復ステップが採用されて、上記ループが除去される。
【００５７】
ステップ５７において発せられた質問に対する答えが「いいえ」であるときには、この方法はステップ５１へ戻る。
【００５８】
上記の説明は、いくつかの実施形態の作用を例示することを含んでおり、特許請求された発明の適用範囲を制限することを意味していない。上記考察から、この発明の精神および適用範囲によってさらに包含される多くの変形例が、当業者にとって明らかであろう。
【図１】
2015517284.tif 000003
【図２】
2015517284.tif 000004
【図３】
2015517284.tif 000005
【図４】
2015517284.tif 000006
【図５】
2015517284.tif 000007
【国際調査報告】
2015517284.tif 000008
2015517284.tif 000009
2015517284.tif 000010