(57)【要約】ネットワークは、あるタイプのフォルトに対するカバーを提供するルートノードを特定することにより、フォルトトレラントネットワークルーティングを提供する。このとき、特定タイプのフォルトの発生がパケットの送信をダウンさせないように、ノードは、これらのルートノードを介してパケットのコピーをルーティングする。
2005537754.tif 000002
【特許請求の範囲】
【請求項１】
フォルトトレラントネットワークルーティングのためのネットワークを構成する方法であって、
２−接続ネットワークを構成するノードを特定するステップと、
前記ノード間で通信されるパケットに対するルーティングパスを決定するステップと、
前記ルーティングパスを利用したパケットルーティングを与えたとき、あるクラスのフォルトに対するカバーを提供する前記ノードのルートノードを選択するステップと、
前記ルートノードへのパケットを重複化するよう前記ノードを構成するステップと、
から構成されることを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
前記ノードの各々に対し、前記ルーティングパスは、前記ノードから前記２−接続ネットワークのその他のノードの各々へのパスを特定するルーティングツリーを含むことを特徴とする方法。
【請求項３】
請求項２記載の方法であって、
前記ルートノードは、前記２−接続ネットワーク内の任意のシングルリンクフォルトに対するカバーを提供することを特徴とする方法。
【請求項４】
請求項３記載の方法であって、
前記ルートノードを選択するステップは、
前記ノードの各々に対し、前記ルーティングツリーを有する２−接続ネットワーク内の各リンクのインシデンスを示すリンクインシデンスマトリックスを生成するステップと、
前記２−接続ネットワーク内の任意のシングルリンクフォルトに対するカバーを提供するルーティングツリー群を特定するステップと、
前記ルーティングツリー群に対応するノードを前記ルートノードとして選択するステップと、
から構成されることを特徴とする方法。
【請求項５】
請求項１記載の方法であって、
前記ルーティングパスを決定するステップは、前記ノードにより維持されるルーティング情報を前記ノードの各々に問い合わせることからなることを特徴とする方法。
【請求項６】
フォルトトレラントパケットルーティング方法であって、
他の複数のネットワークノードに接続されるネットワークノードにおいて、前記他の複数のネットワークノードの送信先ノードへの送信のためのパケットを生成するステップと、
前記ネットワークノードと前記他の複数のネットワークノードにより構成されるネットワークセグメント内のあるクラスのフォルトに対するカバーを提供する前記他の複数のネットワークノードの複数のルートノードを特定するステップと、
前記複数のルートノードの各々に前記パケットのコピーをトンネリングするステップと、
から構成されることを特徴とする方法。
【請求項７】
請求項６記載のフォルトトレラントパケットルーティング方法であって、さらに、
前記他の複数のネットワークノードの１つからトンネリングされたパケットを受信するステップと、
前記トンネリングされたパケットからカプセル化されたパケットを抽出するステップと、
前記抽出されたパケットの送信先アドレスに基づき、前記抽出されたパケットを送信するリンクを選択するステップと、
前記抽出されたパケットを前記選択されたリンク上に送信するステップと、
を有することを特徴とする方法。
【請求項８】
請求項６記載のフォルトトレラントパケットルーティング方法であって、さらに、
前記ルートノードから通信される複数のパケットコピーを受信するステップと、
前記複数のパケットコピーが互いに重複しているか判断するステップと、
前記パケットコピーの余分なコピーを破棄するステップと、
を有することを特徴とする方法。
【請求項９】
請求項８記載のフォルトトレラントパケットルーティング方法であって、
前記複数のパケットコピーが互いに重複しているか判断するステップは、前記パケットコピーのＴＣＰ/ＩＰシーケンスナンバーを比較することからなることを特徴とする方法。
【請求項１０】
請求項６記載のフォルトトレラントパケットルーティング方法であって、
前記ネットワークセグメントは、少なくとも２−接続ネットワークであり、
前記パケットコピーは、前記ネットワークノードから該ネットワークノードからの少なくとも２つのリンク上に送信される、
ことを特徴とする方法。
【請求項１１】
請求項６記載のフォルトトレラントパケットルーティング方法であって、さらに、
前記ネットワークノードから前記送信先ネットワークノードへのルーティングパスを特定するステップと、
前記パケットを前記特定されたルーティングパス上に送信するステップと、
を有することを特徴とする方法。
【請求項１２】
請求項６記載のフォルトトレラントパケットルーティング方法であって、
前記ネットワークセグメント内の各ノードは、ミニマムホップルーティングツリーを利用して、前記ネットワークセグメント内の他の各ノードにパケットをルーティングすることを特徴とする方法。
【請求項１３】
請求項１２記載のフォルトトレラントパケットルーティング方法であって、
前記ルートノードからのルーティングツリーは、前記ネットワークセグメント内の任意のシングルリンクフォルトに対するカバーを提供することを特徴とする方法。
【請求項１４】
請求項１２記載のフォルトトレラントパケットルーティング方法であって、
前記ルートノードの１つへの前記パケットのコピーをトンネリングするステップは、
前記パケットのコピーをトンネリングされるパケットにカプセル化するステップと、
前記ルーティングツリーを前記ルートノードから前記ネットワークノードに逆探索する前記ルートノードへのパス上に前記トンネリングされるパケットを送信するステップと、
を有することを特徴とする方法。
【請求項１５】
ネットワークセグメントを構成する他の複数のネットワークノードに接続するため動作し、さらに、前記他の複数のネットワークノードに少なくとも２つに直接リンクするよう動作するインタフェースと、
前記他の複数のネットワークノードの送信先ノードへの送信のためのパケットを生成し、前記ネットワークセグメント内のあるクラスのフォルトに対するカバーを提供する前記他の複数のネットワークノードの複数のルートノードを特定するよう動作し、さらに、前記インタフェースを利用して、前記複数のルートノードの各々に前記パケットのコピーをトンネリングするよう動作するプロセッサと、
から構成されることを特徴とするネットワークノード。
【請求項１６】
請求項１５記載のネットワークノードであって、
前記インタフェースはさらに、前記他の複数のネットワークノードの１つからトンネリングされたパケットを受け取るよう動作し、
前記プロセッサはさらに、前記トンネリングされたパケットからカプセル化されたパケットを抽出し、前記抽出されたパケットの送信先アドレスに基づき、前記抽出されたパケットを送信するため、前記インタフェースからリンクを選択し、前記選択されたリンク上に前記抽出されたパケットを送信するよう動作する、
ことを特徴とするネットワークノード。
【請求項１７】
請求項１５記載のネットワークノードであって、
前記インタフェースはさらに、前記複数のルートノードから通信される複数のパケットコピーを受け取るよう動作し、
前記プロセッサはさらに、前記複数のパケットコピーが互いに重複しているか判断し、前記複数のパケットコピーの余分なコピーを破棄するよう動作する、
ことを特徴とするネットワークノード。
【請求項１８】
請求項１７記載のネットワークノードであって、
前記プロセッサはさらに、前記複数のパケットコピーのＴＣＰ/ＩＰシーケンスナンバーを比較することにより、前記複数のパケットコピーが重複しているか判断するよう動作することを特徴とするネットワークノード。
【請求項１９】
請求項１５記載のネットワークノードであって、
前記ネットワークセグメントは、少なくとも２−接続ネットワークであり、
前記プロセッサは、前記インタフェースからの少なくとも２つのリンク上に前記パケットコピーを送信する、
ことを特徴とするネットワークノード。
【請求項２０】
請求項１５記載のネットワークノードであって、
前記プロセッサはさらに、前記送信先ネットワークノードへのルーティングパスを特定し、前記特定されたルーティングパス上に前記パケットを送信するよう動作することを特徴とするネットワークノード。
【請求項２１】
請求項１５記載のネットワークノードであって、
前記ネットワークセグメント内の各ノードは、ミニマムホップルーティングツリーを利用して、前記ネットワークセグメント内の他の各ノードにパケットをルーティングすることを特徴とするネットワークノード。
【請求項２２】
請求項２１記載のネットワークノードであって、
前記複数のルートノードからのルーティングツリーは、前記ネットワークセグメント内の任意のシングルリンクフォルトに対するカバーを提供することを特徴とするネットワークノード。
【請求項２３】
請求項２１記載のネットワークノードであって、
前記プロセッサはさらに、前記複数のルートノードの１つへの前記パケットのコピーのトンネリングを、前記パケットのコピーをトンネリングされるパケットにカプセル化し、前記ルーティングツリーを前記ルートノードから前記ネットワークノードに逆に探索する前記ルートノードへのパス上に前記トンネリングされるパケットを送信することにより動作することを特徴とするネットワークノード。
【請求項２４】
請求項１５記載のネットワークノードであって、さらに、
前記複数のルートノードのリストを保持するメモリと、
前記ネットワークノードからのルーティングツリーを実現するルーティングテーブルと、
を有することを特徴とするネットワークノード。
【請求項２５】
フォルトトレラントパケットルーティングのための論理であって、
該論理は、媒体上に実現され、実行時に、
他の複数のネットワークノードに接続されるネットワークノードにおいて、前記他の複数のネットワークノードの送信先ノードへの送信のためのパケットを生成するステップと、
前記ネットワークノードと前記他の複数のネットワークノードにより構成されるネットワークセグメント内のあるクラスのフォルトに対するカバーを提供する前記他の複数のネットワークノードの複数のルートノードを特定するステップと、
前記複数のルートノードの各々に前記パケットのコピーをトンネリングするステップと、
を実行するよう動作することを特徴とする論理。
【請求項２６】
請求項２５記載の論理であって、さらに、
前記他の複数のネットワークノードの１つからトンネリングされたパケットを受信するステップと、
前記トンネリングされたパケットからカプセル化されたパケットを抽出するステップと、
前記抽出されたパケットの送信先アドレスに基づき、前記抽出されたパケットを送信するリンクを選択するステップと、
前記抽出されたパケットを前記選択されたリンク上に送信するステップと、
を実行するよう動作することを特徴とする論理。
【請求項２７】
請求項２５記載の論理であって、さらに、
前記ルートノードから通信される複数のパケットコピーを受信するステップと、
前記複数のパケットコピーが互いに重複しているか判断するステップと、
前記パケットコピーの余分なコピーを破棄するステップと、
を実行するよう動作することを特徴とする論理。
【請求項２８】
請求項２７記載の論理であって、
前記複数のパケットコピーが互いに重複しているか判断するステップは、前記パケットコピーのＴＣＰ/ＩＰシーケンスナンバーを比較することからなることを特徴とする論理。
【請求項２９】
請求項２５記載の論理であって、
前記ネットワークセグメントは、少なくとも２−接続ネットワークであり、
前記パケットコピーは、前記ネットワークノードから該ネットワークノードからの少なくとも２つのリンク上に送信される、
ことを特徴とする論理。
【請求項３０】
請求項２５記載の論理であって、さらに、
前記ネットワークノードから前記送信先ネットワークノードへのルーティングパスを特定するステップと、
前記パケットを前記特定されたルーティングパス上に送信するステップと、
を実行するよう動作することを特徴とする論理。
【請求項３１】
請求項２５記載の論理であって、
前記ネットワークセグメント内の各ノードは、ミニマムホップルーティングツリーを利用して、前記ネットワークセグメント内の他の各ノードにパケットをルーティングすることを特徴とする論理。
【請求項３２】
請求項２５記載の論理であって、
前記ルートノードからのルーティングツリーは、前記ネットワークセグメント内の任意のシングルリンクフォルトに対するカバーを提供することを特徴とする論理。
【請求項３３】
請求項２５記載の論理であって、
前記ルートノードの１つへの前記パケットのコピーをトンネリングするステップは、
前記パケットのコピーをトンネリングされるパケットにカプセル化するステップと、
前記ルーティングツリーを前記ルートノードから前記ネットワークノードに逆探索する前記ルートノードへのパス上に前記トンネリングされるパケットを送信するステップと、
を有することを特徴とする論理。
【請求項３４】
他の複数のネットワークノードに接続されるネットワークノードにおいて、前記他の複数のネットワークノードの送信先ノードへの送信のためのパケットを生成する手段と、
前記ネットワークノードと前記他の複数のネットワークノードにより構成されるネットワークセグメント内のあるクラスのフォルトに対するカバーを提供する前記他の複数のネットワークノードの複数のルートノードを特定する手段と、
前記複数のルートノードの各々に前記パケットのコピーをトンネリングする手段と、
から構成されることを特徴とするネットワークノード。
【請求項３５】
第１動作モードにおいて、
他の複数のネットワークノードに接続されるネットワークノードにおいて、前記他の複数のネットワークノードの送信先ノードへの送信のためのパケットを生成するステップと、
前記ネットワークノードと前記他の複数のネットワークノードにより構成されるネットワークセグメント内のあるクラスのフォルトに対するカバーを提供する前記他の複数のネットワークノードの複数のルートノードを特定するステップと、
前記複数のルートノードの各々に前記パケットのコピーをトンネリングするステップと、から構成され、
前記ネットワークセグメント内の各ノードは、ミニマムホップルーティングツリーを利用して、前記ネットワークセグメント内の他の各ノードにパケットをルーティングし、
前記複数のルートノードからのルーティングツリーは、前記ネットワークセグメント内の任意のシングルリンクフォルトに対するカバーを提供することを特徴とし、
第２動作モードにおいて、
前記他の複数のネットワークノードの１つからトンネリングされたパケットを受け取るステップと、
前記トンネリングされたパケットからカプセル化されたパケットを抽出するステップと、
前記抽出されたパケットの送信先アドレスに基づき、前記抽出されたパケットを送信するためのリンクを選択するステップと、
前記抽出されたパケットを前記選択されたリンク上に送信するステップと、
から構成されることを特徴とし、
第３動作モードにおいて、
前記複数のルートノードから通信される複数のパケットコピーを受け取るステップと、
前記複数のパケットコピーが互いに重複しているか判断するステップと、
前記複数のパケットコピーの余分なものを破棄するステップと、
から構成されることを特徴とするフォルトトレラントパケットルーティング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にネットワークルーティングに関し、より詳細にはフォルトトレラント（ｆａｕｌｔ  ｔｏｌｅｒａｎｔ）ネットワークルーティングに関する。
【背景技術】
【０００２】
通信ネットワークは、現実の状態の下で動作しているため、しばしば通常の動作を妨げるフォルトに被る。例えば、光ネットワークでは、利用されるファイバは、ノード間のあらゆるトラフィックを停止しうる。フォルトによりサービスの完全な中断を回避するため、いくつかのネットワークは緊急時対策を検討している。例えば、光リングでは、あるノードが１つの方向におけるフォルトを検出すると、このフォルトとは反対方向での通信を開始する。
［発明の概要］
本発明によると、フォルトトレラントネットワークルーティングのための技術が提供される。
【０００３】
一実施例によると、フォルトトレラントネットワークルーティングのためのネットワークを構成する方法は、２−接続ネットワークを構成するノードを特定し、前記ノード間で通信されるパケットに対するルーティングパスを決定し、前記ルーティングパスを利用したパケットルーティングを与えたとき、あるクラスのフォルトに対するカバーを提供する前記ノードのルートノードを選択する。本方法はまた、前記ルートノードへのパケットを重複化するよう前記ノードを構成する。
【０００４】
他の実施例によると、フォルトトレラントパケットルーティング方法は、他の複数のネットワークノードに接続されるネットワークノードにおいて、前記他の複数のネットワークノードの送信先ノードへの送信のためのパケットを生成する。本方法は、前記ネットワークノードと前記他の複数のネットワークノードにより構成されるネットワークセグメント内のあるクラスのフォルトに対するカバーを提供する前記他の複数のネットワークノードの複数のルートノードを特定する。本方法はまた、前記複数のルートノードの各々に前記パケットのコピーをトンネリングする。
【０００５】
本発明の実施例は、様々な技術的効果を提供する。これらの技術は、送信先へのパケットのフォルトトレラントな送信を可能にする。利用可能な帯域幅に依存して、当該技術は、制御パケット及び/またはデータパケットなどの一部のパケットまたはすべてのパケットに適用されてもよい。
【０００６】
実施例によると、本システムは、ノード間のパケットのルーティングのためミニマムホップスパニングツリーを利用する。このため、上記技術は、既存の多数のネットワークプロトコルと共に利用するため、役立てることができる。例えば、ある光ネットワークは、光学的最短パス優先ルーティングを利用する。このようなルーティング技術はさらに、光学以外の送信媒体を用いたネットワークに適用可能である。
【０００７】
上記技術はさらに、様々な程度のフォルトトレラントを可能にする。すなわち、ネットワーク設計パラメータなどの情報に基づき、ネットワークは、リンク及び/またはノードフォルトなどの異なるフォルトの深刻度に対する保護を提供することが可能である。
【０００８】
本発明の他の技術的効果は、以下の図面、説明及びクレームから当業者には容易に明らかとなるであろう。さらに、特定の効果が上述されたが、各種実施例は、上記効果のすべてまたは一部を有するか、あるいはそれらの何れをも有しないかもしれない。
［発明の詳細な説明］
図１は、ネットワーク１４の一部を構成するいくつかのネットワークノード１２を有する通信システム１０を示す。システム１０はさらに、ネットワーク１４を管理するためのネットワーク管理システム（ＮＭＳ）１６を有する。一般に、ノード１２は、パケットのフォルトトレラントルーティングを提供するよう動作する。ある実施例によると、ＮＭＳ１６は、あるフォルトをカバーするルートノード１２を特定し、このルートノード１２を利用してフォルトに対しプロテクトするようノード１２を構成する。この構成に基づき、ノード１２は、パケットの送達を保証するため、重複するパケットをルートノードにトンネリングする。各ルートノード１２は、所与のネットワークにフォルトが発生しても送達を保障するようパケットを各自の宛先に個別に送信しようとする。
【０００９】
ＮＭＳ１６は、ネットワーク１４の構成要素を管理する制御論理を有するコンポーネントの任意の適切な集まり及び構成を表す。独立した単一の構成要素として示されているが、システム１０は、ＮＭＳ１６の構成及び機能が任意数の構成要素間に分散化されている可能性も考慮される。例えば、ＮＭＳ１６の構成及び機能は、１以上のノード１２の間に分散化されてもよい。動作中、ＮＭＳ１６は、フォルトトレラントネットワークルーティングを提供するネットワーク１４の構成を特定し、その後、このルーティングを提供するようノード１２を構成する。具体的には、ＮＭＳ１６は、あるフォルトに対するカバーを提供するルートノード１２を特定する。その後、ＮＭＳ１６は、これらのルートノード１２を利用してパケットのルーティングを行うよう選択されたノード１２を構成する。
【００１０】
ノード１２は、パケットベーストラフィックの処理が可能なネットワーク構成要素を表す。例えば、ノード１２は、スイッチ、ルータ、ゲートウェイ及び他の適切なネットワーク構成要素を有するようにしてもよい。システム１０は、任意の適切な伝送技術を用いたノード１２を考慮する。動作中、ノード１２は、ネットワーク１４の選択された部分の範囲内におけるパケットのフォルトトレラントルーティングを提供するよう動作する。選択されたノード１２は、これらのパケットの各自の意図された受け手に送信されることを保証するため、ルートとして機能し、他のノード１２のパケットのコピーをルーティングする。
【００１１】
図示された実施例では、ノード１２は、ネットワークグラフを構成するよう相互に接続する。このグラフは、１−接続（ｏｎｅ−ｃｏｎｎｅｃｔｅｄ）されるという性質を示す。すなわち、いくつかのノード１２は、他のノード１２に到達するのに１つのリンクに頼っている。この例では、１つのリンクにより、Ａとラベル付けされた第１セグメント１８（セグメントＡ）とＢとラベル付けされた第２セグメント１８（セグメントＢ）とが接続される。さらなるリンクを設けない場合、セグメントＡとセグメントＢとの間のリンクフォルトにより、当該セグメント間の通信をダウンさせるであろう。
【００１２】
セグメントＡとＢの各々は、２−接続（ｔｗｏ−ｃｏｎｎｅｃｔｅｄ）であるというグラフ性質を示す。すなわち、セグメント内部では、各ノード１２は、少なくとも２つのパスにより他の各ノード１２と接続している。従って例えば、セグメントＡ内の１つのリンクが故障しても、各ノード１２は、依然として他の各ノード１２への利用可能なパスを有するであろう。このタイプのフォルトは、シングルリンクフォルト（ｓｉｎｇｌｅ  ｌｉｎｋ  ｆａｕｌｔ）として通常呼ばれている。他のタイプのフォルトには、ノード１２の１つのフォルトなどのノードフォルトがある。開示される技術は、重大性の異なるフォルトに対してカバーする様々な保護程度を提供する。典型的には、ノードフォルトは、リンクフォルトより深刻であると考えられている。
【００１３】
動作中、ＮＭＳ１６は、ネットワーク１４の様々な部分内のパケットのフォルトトレラントルーティングを提供するようノード１２を構成する。フォルトトレラントルーティングに対しノード１２を構成するため、ＮＭＳ１６は、２−接続のグラフ性質を示すネットワーク１４の部分を特定する。例えば、ＮＭＳ１６は、セグメントＡを特定するかもしれない。その後、ＮＭＳ１６は、特定されたセグメント内のノード１２の一部またはすべてに対するルーティング情報を決定する。ある実施例によると、ＮＭＳ１６は、セグメント内の各ノード１２に対するミニマムホップスパニングツリー（ｍｉｎｉｍｕｍ  ｈｏｐ  ｓｐａｎｎｉｎｇ  ｔｒｅｅ）を決定する。これにより、セグメント内の各ノード１２に対して、ＮＭＳ１６は、当該セグメント内の他のすべてのノード１２に対するミニマムホップルーティングパス（ｍｉｎｉｍｕｍ  ｈｏｐ  ｒｏｕｔｉｎｇ  ｐａｔｈ）を決定する。
【００１４】
図示された実施例では、セグメントＡは、ノードＡ、Ｂ、Ｃ、Ｄ、Ｅ及びＦを有する。前述のように、ＮＭＳ１６は、これらのノード１２の各々に対するルーティングツリーを特定することにより、ルーティング情報を構成するかもしれない。ルーティングツリーは、ノード１２とセグメントＡとの間でわたされるパケットが経由するルートを反映している。セグメントＡ内のノード１２に対するルーティングツリーの例が、図２Ａ〜２Ｆに与えられている。
【００１５】
セグメント内の一部またはすべてのノード１２に対するルーティング情報の決定後、ＮＭＳ１６は、あるタイプのフォルトに対するカバーを与えるルートノード１２を特定する。例えば、ＮＭＳ１６は、任意のシングルリンクフォルトに対するカバーを提供するルートノード１２を特定するようにしてもよい。任意のシングルリンクフォルトに対するカバーは、セグメント内の何れかのリンクのフォルトが、すべてのルートノード１２からのルーティングパスに影響を及ぼさないことを意味する。従って、１つのリンクが故障したとしても、ルートノード１２の少なくとも１つが、セグメント内の他のすべてのノード１２への無傷のルーティングツリーを有するであろう。しかしながら、ＮＭＳ１６はこの例でシングルリンクフォルトに対するカバーを特定するが、システム１０は、ＮＭＳ１６がリンクフォルトとノードフォルトの任意の適切な組み合わせに対するカバーを特定する可能性を考慮している。
【００１６】
カバーを提供するルートノード１２の特定後、ＮＭＳ１６は、ルートノード１２を利用してフォルトトレラントパケットルーティングを提供するため、セグメント内のノード１２を構成する。構成が行われると、セグメント内のノード１２は、パケットの重複化と各ルートノード１２へのパケットのコピーのトンネリングを開始する。ある実施例によると、ノード１２は、すべてのネットワークトラフィックの重複化から生じる混雑を回避するため、制御パケットのみを重複化する。制御パケットとは、ネットワーク１４内の構成要素の動作を制御する管理メッセージを表す。例えば、ネットワーク１４が光ネットワークである場合、ノード１２は、光パスを管理するためのＯＳＣ（Ｏｐｔｉｃａｌ  Ｓｕｐｅｒｖｉｓｏｒｙ  Ｃｈａｎｎｅｌ）メッセージを交換し、他の適切な管理および制御機能を実行するようにしてもよい。利用可能な帯域幅に基づき、ノード１２は、制御及び/またはデータパケットを重複化するようにしてもよい。しかしながら、本説明の残りでは、ノード１２は、制御パケットのみを重複化すると仮定される。
【００１７】
一例として、ＮＭＳ１６が、セグメントＡ内の任意のシングルリンクフォルトに対するカバーを提供するノードＣ、Ｄ及びＦを選ぶ場合を考える。動作中、ノードＡがノードＥとの通信のため制御パケットを生成する場合、ノードＡは、当該パケットのコピーを各ルートノード１２（ノードＣ、Ｄ及びＦ）にトンネリングする。ノードＡは、これら重複パケットをルートノード１２にトンネリングするための任意の適切な技術を利用するようにしてもよい。例えば、ノードＡは、各ルートノード１２に送信されるパケットのデータ部分として重複パケットをカプセル化してもよい。同様に、ノードＡは、ＭＰＬＳ（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｅｄ）プロトコルを利用して、重複パケットを各ルートノード１２にトンネリングするようにしてもよい。パケットのコピーを各ルートノード１２にトンネリングするのに加えて、ノードＡは、ノードＡからの従来のルーティングパスを用いてノードＥにパケットを送信するようにしてもよい。例えば、パケットは、ノードＡからノードＥへのミニマムホップスパニングツリー上を経由するようにしてもよい。
【００１８】
各ルートノード１２は、トンネリングされたパケットを受信すると、当該パケットを予定された送信先へ転送する。従って、潜在的には、パケットのコピーは、送信先へ到達するためいくつかの異なる送信ルートにより送信される。与えられた例では、ノードＥは、制御パケットの４つのコピーを受け取る（セグメントＡ内にフォルトがない場合）。パケット内の透かしや他の適切な情報に基づき、ノードＥは重複するパケットを破棄するようにしてもよい。例えば、ＴＣＰ/ＩＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ/Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）シーケンスナンバーを利用して、ノードＥは、重複パケットの特定及び破棄を行うことができる。フォルトイベントでは、ノードＥは、ノードＡから制御パケットの４つのコピーを受け取らないかもしれない。しかしながら、任意のシングルリンクフォルトが発生すると、ノードＥは、制御パケットの少なくとも１つのコピーを受け取るであろう。例えば、ルートノードＣ、Ｄ及びＦは、任意のシングルリンクフォルトに対するカバーを提供するため、セグメントＡ内のリンクフォルトは、すべてのルートからの制御パケットの送達を不能にすることはない。
【００１９】
図２Ａ〜２Ｆは、ネットワーク１４のセグメントＡ内の各ノード１２に対するミニマムホップスパニングツリーを示すルーティング図である。これらの図は、フォルトに対するカバーを特定するためＮＭＳ１６により用いられる一例となるルーティング情報を示す。適切には、各図は、マッチした文字が付されたノードに対するミニマムホップスパニングツリーに対応する。例えば、図２Ａは、ルートとしてノードＡを有するミニマムホップスパニングツリーに対応する。図２Ａ〜２Ｆの各図は、セグメントＡ内の様々なノード１２からの可能性のあるパケットのルーティングを示す。しかしながら、特定のミニマムホップスパニングツリーが上記図では示されているが、それらはミニマムホップスパニングツリーに対する唯一の解法を表すものでないということは明らかであるべきである。例えば、図２Ａは、ルートとしてノードＡを有する２つの可能性のあるミニマムホップスパニングツリーの１つのみを示している。ＮＭＳ１６は、各ノード１２に対する特定のルーティングツリーを特定するための任意の適切な技術を利用するようにしてもよい。さらに、上記図は、パケットをルーティングするためのミニマムホップスパニングツリーを示すが、ＮＭＳ１６は、任意の適切な技術を利用してルーティングツリーを生成するようにしてもよい。このため、ルーティング情報は、各ノード１２からの最短パスルーティングを反映させる必要はない。しかしながら、ＮＭＳ１６により分析されるルーティング情報は、特定されたセグメント内のパケットをルーティングするのに利用されるべき実際の送信パスを反映すべきである。
【００２０】
決定されたルーティング情報に基づき、ＮＭＳ１６は、あるタイプのフォルトに対するカバーを提供するルートノード１２を特定する。ある実施例によると、ＮＭＳ１６は、各ノード１２に対するミニマムホップスパニングツリー上のリンクフォルトの影響を示すリンクインシデンスマトリックス（ｌｉｎｋ  ｉｎｃｉｄｅｎｃｅ  ｍａｔｒｉｘ）を生成する。その後、ＮＭＳ１６は、生成されたマトリックスを利用して、あるフォルトのクラスに対するカバーを提供するノード１２を選択する。リンクインシデンスマトリックスにより、ＮＭＳ１６は、リンクフォルトに対するカバーを提供するノード１２を特定することができる。
【００２１】
ある実施例によると、ＮＭＳ１６はまた、ノード１２へのルーティング情報を構成する。例えば、ノード１２に対するルーティングツリーの決定後、ＮＭＳ１６は、ルーティングテーブルまたはパケットのルーティングを行うためノード１２により利用される他の適切な構成を備えるようにしてもよい。あるいは、ノード１２は、ルーティングパスを決定し、その後に自己設定を実行するためのメッセージを交換するようにしてもよい。これらの状況では、ＮＭＳ１６は、当該セグメントに対するルーティング情報を取得するため、ノード１２に問い合わせを行うようにしてもよい。
【００２２】
図３は、セグメントＡ内のノード１２に対するリンクインシデンスマトリックスを示すテーブル３０を示す。各ノード１２に対して、テーブル３０は、当該ノード１２からのルーティングツリーを形成するリンクを指定する。これにより、テーブル３０内の情報は、セグメントＡ内のノードＡ〜Ｆのための各ミニマムホップスパニングツリーに対するリンクフォルトの影響を示す。テーブル３０内の第１列は、セグメントＡ内のノード１２間の９つのリンクを列挙している。残りの６つの列は、セグメントＡ内の６つのノードから構成されるミニマムホップスパニングツリーに対するリンクフォルトの影響を示す。例えば、Ｔ（Ａ）によりラベル付けされた第２列は、ノードＡからのミニマムホップスパニングツリーの構成に利用されるリンクを指定する。これにより、当該列は、ルートとしてノードＡにより構成されるミニマムホップスパニングツリーに対するリンクフォルトの影響を示すことになる。これら６つの列では、「１」の値は、対応するリンクフォルトによりルーティングツリーをダウンさせることを示す。「０」の値は、対応するリンクのフォルトはルーティングツリーをダウンさせないことを示す。例えば、ノードＡから構成されるルーティングツリーに対して、リンクＡＢ、ＡＣ、ＡＤ、ＢＦあるいはＤＥのフォルトは、ルーティングツリーをダウンさせてしまう。しかしながら、リンクＢＣ、ＢＤ、ＣＦまたはＥＦのフォルトは、ルーティングツリーをダウンさせない。
【００２３】
この情報を利用して、ＮＭＳ１６は、リンクフォルトに対するカバーを提供するノード１２を特定することが可能である。例えば、任意のシングルリンクフォルトに対するカバーを決定するため、ＮＭＳ１６は、合成されるとき、セグメントＡ内の任意の１つのリンクフォルトによりすべてが影響を受けることがない選択されたルーティングツリーを特定する。例えば、ルーティングツリーＡ、Ｂ、Ｃ及びＦは、任意のシングルリンクフォルトに対するカバーを提供する。同様に、ルーティングツリーＣ、Ｄ及びＦもまた、任意のシングルリンクフォルトに対するカバーを提供する。これは、あるセグメントが、いくつかの利用可能な異なるカバーを有するようにしてもよいということを示すものであり、異なるカバーは異なる個数のルートノードを利用するようにしてもよい。セグメント内のパケットの重複を減らすため、ＮＭＳ１６は、最小のルートノード１２を利用するカバー解法を選択するようにしてもよい。従ってこの例では、ＮＭＳ１６は、任意のシングルリンクフォルトに対するカバーを提供するため、ルートノードとしてノードＣ、Ｄ及びＦを選択することができる。
【００２４】
図４は、セグメントＡ内のノード１２に対するノードインシデンスデグリーマトリックス（ｎｏｄｅ  ｉｎｃｉｄｅｎｃｅ  ｄｅｇｒｅｅ  ｍａｔｒｉｘ）を指定するテーブル４０を示す。当該マトリックスは、各ルーティングツリー内の各ノード１２の関連するデグリーを特定する。ＮＭＳ１６は、テーブル４０内の情報を利用して、セグメントＡ内のノードフォルトに対するカバーを特定するようにしてもよい。テーブル３０に関連して、テーブル４０は、図２Ａ〜２Ｆに示されるようなミニマムホップスパニングツリーを利用して計算されたインシデンス情報を有する。テーブル４０内の第１列は、セグメントＡ内の６つのノード１２を列挙している。残りの列は、６つのルーティングツリーの各々の内部のノードに対するリンクインシデンスのデグリーを特定する。リンクインシデンスのデグリーは、ルーティングツリー内の特定のノード１２への入力及び出力リンクの個数を記録したものである。
【００２５】
例えば、第２列は、ルートとしてノードＡを有するよう構成されるルーティングツリー内の各ノード１２に対するリンクインシデンスのデグリーを列挙している。このツリーでは、ノードＡは、ノードＢ、Ｃ及びＤにリンクしている。このため、ルーティングツリーＡの第１行の値は「３」となる。ルーティングツリーＡでは、ノードＢは、ノードＡとＦにリンクしている。従って、第２行の値は「２」である。ノードＣはノードＡのみとリンクしている。従って、第３行の値は「１」である。この「１」の値は、ノードＣの故障により、ノードＡから構成されるルーティングツリー内の残りのノード１２へのパケットのルーティングに影響を与えるものでないということを示している。同様に、ルーティングツリーＡのその他のリーフ（ノードＥおよびＦ）もまた、各自のリンクインシデンスのデグリーに対して、「１」の値を有する。従って、ルーティングツリーＡは、ノードＣ、ＥあるいはＦのフォルトに対するカバーを提供する。
【００２６】
しかしながら、ＮＭＳ１６がセグメントＡ内のどのノード１２がフォルトの可能性があるか予測することはできないかもしれない。従って、ＮＭＳ１６は、セグメントＡ内の任意の１つのノード１２のフォルトに対するカバーを提供するルーティングツリーの集合を特定するようにしてもよい。例えば、ノードＤ、Ｅ及びＦが、セグメントＡ内の任意の１つのノード１２のフォルトに対するカバーを提供する。すなわち、１つのノード１２の故障が発生すると、残りのノード１２のすべてが、選択されたカバーノード１２のルーティングツリーの少なくとも１つを利用して到達することができる。従って、ＮＭＳ１６は、任意の１つのノードフォルトにより残りのノード１２との通信がダウンしないように、パケットのコピーをルーティングするためのセグメントＡ内のノード１２の構成を行うようにしてもよい。
【００２７】
テーブル３０及び４０があるクラスのフォルトに対するカバーを特定するための情報の構成を示しているが、システム１０は、ＮＭＳがあるクラスのフォルトに対するカバーを特定する任意の適切な技術を利用することを考慮している。さらに、特定されたネットワークセグメントのグラフ特性が、利用可能なカバーのタイプを導き出すようにしてもよい。例えば、３−接続グラフが与えられると、ＮＭＳ１６は、任意の２つのリンクフォルトに対するカバー特定することができる。従って、ＮＭＳ１６により利用される特定の情報は、ネットワーク１４の性質、カバーを提供する選択されたフォルトのクラス及び他の適切な基準に依存するものであってもよい。
【００２８】
さらに、ＮＭＳ１６は、複数のクラスのフォルトに対するカバーを特定する技術の組み合わせを利用してもよい。例えば、ＮＭＳ１６は、シングルリンクフォルトに対するカバーのための解法と１つのノードフォルトに対するカバーのための解法を特定するようにしてもよい。このとき、ＮＭＳ１６は、任意の１つのリンクまたはノードフォルトに対するカバーを提供するこれらの解法の共通部分を選択するようにしてもよい。
【００２９】
図５は、ノード１２の一例となる機能構成を示すブロック図である。図示された実施例では、ノード１２は、インタフェース５０、コントローラ５２及びメモリ５４を有する。インタフェース５０を利用して、ノード１２は、他のノード１２やＮＭＳ１６などのシステム１０の他の構成要素とリンクする。インタフェース５０は、他の装置と接続するための１以上のポートを備える。これにより、インタフェース５０を利用して、ノード１２は、いくつかの他のノード１２とリンクすることができる。
【００３０】
コントローラ５２は、ノード１２の動作を制御する。コントローラ５２は、マイクロプロセッサ、コントローラ、論理デバイスまたは他の適切な制御要素の任意の適切な組み合わせを有するようにしてもよい。例えば、コントローラ５２は、論理ルーチンを実行するマイクロプロセッサを有するようにしてもよい。動作中、コントローラ５２は、メモリ５４の内部に維持される情報にアクセスするようにしてもよい。図示された実施例では、メモリ５４は、コード５６と設定情報５８を有する。コード５６は、ノード１２の動作盛業に利用される任意の適切な論理ルーチンを表す。設定情報５８は、ノード１２の特定動作を制御するための設定及び他の情報を有する。例えば、設定情報５８は、ルートノード１２と当該ルートノードへの重複化のためのパケットタイプを指定するものであってもよい。設定情報５８はさらに、他のノード１２への送信のためのパケット送信を支配するルーティングテーブルを有するようにしてもよい。例えば、設定情報５８は、ノード１２のルーティングツリーを実現するルーティング情報を有するようにしてもよい。
【００３１】
ノード１２は、潜在的には、いくつかの異なる動作モードを提供する。これらのモードは、送信元ノード、送信先ノード及びルートノードとしての動作を含む。送信元として動作するとき、ノード１２は、各ルートノード１２に対してパケットを重複化させる。前述のように、ノード１２は、生成するすべてのパケットを重複化してもよいし、あるいは制御パケットなどの一部のみを重複化するようにしてもよい。生成するパケットを重複させるのに加えて、ノード１２はまた、「カバーされた」セグメントに入るパケットを重複化するようにしてもよい。例えば、ノードＣがセグメントＢから制御パケットを受け取る場合、ノードＣは、当該パケットの送信元ノードとして動作するかもしれない。これにより、カバーされたネットワークセグメントの外部で生成されるパケットをカバーするようフォルトトレランスが拡張される。
【００３２】
ルートへのパケットのトンネリングを行うため、ノード１２は、ルートからルーティングツリーを逆探索するパスを利用するようにしてもよい。例えば、ノードＡが図２Ａに示されるようなルーティングツリーを有するルートであると仮定する。ノードＦからノードＡにパケットをトンネリングするため、当該パケットは、ノードＢを通過し、ルーティングツリーの特定されたフローをノードＡから逆に探索する。ノードＦは、この逆のルーティングを利用して、ルーティングツリーＡに影響を与えないリンクフォルトが同様にしてノードＡへのパケットのトンネリングに影響を与えないことを保証する。例えば、ノードＦからノードＡへのルーティングツリーがノードＣを通過する場合、リンクＣＦの故障はルーティングツリーＡをダウンはさせないが、ノードＦからノードＡへの送信をダウンさせるかもしれない。このシナリオを回避するため、ＮＭＳ１６は、送信元ノード１２と送信先ノード１２との間の同様のパスを使用するルーティングツリーを特定するようにしてもよい。例えば、ルーティングツリーＡがノードＢを介しノードＦに到達する場合、ルーティングツリーＦはまたノードＤを介してノードＡに到達するであろう。
【００３３】
ルートとして動作するとき、ノード１２は、他のノード１２からトンネリングされたパケットを受け取る。トンネリングされたパケットを受信すると、ルートノード１２は、当該パケットをそれの予定されている送信先へ転送する。ルートからのこのパスは、しばしば送信元ノード及び他のノードから異なるリンクを介してパスを探索する。例えば、詳細なミニマムホップスパニングツリーが与えられると、ルートとして動作するノードＣがノードＥに対するトンネリングされたパケットを受け取る場合、ノードＣは、ノードＦを介したノードＥへのルート上にパケットを転送する。当該パケットがノードＡからのものである場合、ノードＡはまた、ノードＤを介してノードＥにパケットのコピーを送信するようにしてもよい。これにより、リンクＡＤあるいはＤＥの何れかのフォルトにより、当該パケットの１つのコピーがノードＥに到達することができなくなるが、ノードＣからのコピーは依然としてノードＥに到達するであろう。
【００３４】
パケットを転送するため、ルートノード１２は、送信元ノード１２から受け取ったパケットを変更してもよい。ルートノード１２は、ルートへのパケットのトンネリングに用いられる方法が適切に与えられると、トンネリングされたパケットの変更及び処理を実行する。例えば、制御パケットがパケットのデータ部分としてトンネリングされる場合、ルートノード１２は、カプセル化されたパケットを抽出し、この抽出されたパケットを送信する。このとき、ルートノード１２により用いられる処理は、送信元ノード１２からルートノード１２へのパケットのトンネリングに利用される処理により駆動される。
【００３５】
送信先として、ノード１２は、パケットの複数のコピーを受け取るかもしれない。このため、ノード１２は、典型的には、不要なコピーを破棄する。重複したパケットを破棄するため、ノード１２は、受け取ったパケット内の透かしを利用する。例えば、ＴＣＰ/ＩＰシーケンスナンバーを利用して、ノード１２は、重複したパケットの特定及び破棄を行うことができる。しかしながら、ＴＣＰ/ＩＰシーケンスナンバーなどの既存の透かしが都合のよい解法を提供する一方、システム１０は、ノード１２が重複したパケットの追跡及び破棄を行うための任意の適切な技術を利用することを考慮する。
【００３６】
上記説明は、ノード１２に対する３つの動作モードを設けている。ネットワーク構成に依存して、各ノード１２は、必要に応じて各時点において上記モードの一部またはすべてにより動作するかもしれない。従って例えば、ノード１２は、各時点において、送信元、送信先及びルートとして動作するかもしれない。しかしながら、これらの動作モードは、ノード１２により実行されるすべての動作を提供するものでない。このため、システム１０は、ノード１２が必要に応じて他の動作を実行することを考慮する。例えば、前述のように、１以上のノード１２が、ＮＭＳ１６の一部またはすべての動作を実行するようにしてもよい。
【００３７】
また、ノード１２の図示された実施例及びそれに伴う説明による具体的な構成要素及び機能が与えられているが、システム１０は、ノード１２がパケットのフォルトトレラントルーティングを提供する構成要素の任意の適切な組み合わせ及び構成を有することを考慮している。従って、図示された特定の構成要素により実行される機能は、必要に応じて分離または合成されてもよく、これら構成要素の一部またはすべての機能は、メディアに符号化された論理により実現されてもよい。
【００３８】
図６は、パケットのフォルトトレラントルーティングを実行するようＮＭＳ１６によるノード１２の構成方法を示すフローチャートである。具体的には、当該フローチャートは、シングルリンクフォルトに対するカバーを提供するルートの選択におけるＮＭＳ１６の動作を詳述するものである。ＮＭＳ１６は、ステップ８０において、２−接続ネットワークを構成するノード１２を初期的に特定する。例えば、ネットワーク１４内部で、ＮＭＳ１６は、セグメントＡなどの２−接続部分を特定するようにしてもよい。ＮＭＳ１６は、ステップ８２において、リンクインシデンスマトリックスを初期化する。例えば、ＮＭＳ１６は、特定されたセグメント内のリンクを特定するテーブル３０などのテーブルを設定するようにしてもよい。
【００３９】
ＮＭＳ１６は、ステップ８４において、処理されていないノード１２を選択する。初期的には、この選択では、特定されたセグメント内のノード１２の何れか１つを選択する。ＮＭＳ１６は、ステップ８６において、ルートとして選択されたノード１２を利用するミニマムホップスパニングツリーを生成する。これは、図２Ａ〜２Ｆに示されるルーティングツリーの１つなどのルーティング図を生成する。生成されたルーティング情報を利用して、ＮＭＳ１６は、ステップ８８において、リンクインシデンスマトリックスにおける選択されたノード１２に対するエントリを有する。例えば、ＮＭＳ１６は、ルーティングツリーによるリンクインシデンスを示す「１」及び「０」を有する選択されたノードに対応する列を有するようにしてもよい。ＮＭＳ１６は、ステップ９０において、他の未処理ノード１２が残っているか決定する。未処理ノードが残っている場合、ＮＭＳ１６は、ステップ８４〜９０を繰り返す。このプロセスを利用して、ＮＭＳ１６は、特定されたセグメント内のノード１２に対する完全なリンクインシデンスマトリックスを有する。
【００４０】
リンクインシデンスマトリックスを利用して、ＮＭＳ１６は、ステップ９２において、カバーのためのルートノード１２を決定する。前述のように、シングルリンクフォルトに対するカバーを提供するノード群１２を特定する任意の適切な技術を利用するようにしてもよい。その後、ＮＭＳ１６は、ステップ９４において、ノード１２を構成する。例えば、ＮＭＳ１６は、特定されたセグメント内のすべてのノード１２に選択されたルートを通知するようにしてもよい。このとき、セグメント内のノード１２は、パケットのフォルトトレラントルーティングを開始するようにしてもよい。ＮＭＳ１６は、フローチャートに詳述される処理を繰り返すことにより、フォルトトレラントネットワークルーティングを提供するネットワーク１４の他のセグメントの特定および構成を行うようにしてもよい。例えば、ＮＭＳ１６は、ネットワーク１４内のセグメントＡ、セグメントＢ及び他の適切なセグメントに対してこれらのステップを実行するようにしてもよい。
【００４１】
前述のフローチャート及びこれに関する説明は、ＮＭＳ１６がシングルリンクフォルトに対するカバーの特定及びノード１２の構成を行うための一例となる方法のみを示すものである。しかしながら、システム１０は、ＮＭＳ１６がこれらのタスクを実行するのに適切な任意の技術を利用することを考慮している。従って、上記フローチャートのステップの多くは、同時及び/または図示されたものと異なる順序で行われてもよい。さらに、ＮＭＳ１６は、適切なものである限り、追加的なステップ、より少ないステップ及び/または異なるステップを有する方法を利用するようにしてもよい。また、前述のフローチャートは、シングルリンクフォルトに対するカバーの提供におけるＮＭＳ１６の動作を示す。前述のように、システム１０は、ＮＭＳ１６が他のタイプのフォルトに対するカバーを決定する同様の処理を実行することを考慮する。
【００４２】
図７は、送信元として動作するノード１２によるパケットのフォルトトレラントルーティングをサポートする方法を示すフローチャートである。ノード１２は、ステップ１００において、制御パケットを生成する。ノード１２は、ステップ１０２において、カバーを提供するルートを特定する。例えば、ノード１２は、ＮＭＳ１６により選択されたルートノードを特定するため、設定情報５８にアクセスするようにしてもよい。ノード１２は、ステップ１０４においてルートの１つを選択し、ステップ１０６において選択されたルートへの送信のために制御パケットをカプセル化し。ステップ１０８においてカプセル化されたパケットを送信する。上記ステップは、制御パケットのコピーを選択されたルートにトンネリングする。前述のように、ノード１２は、任意の適切な技術を利用して、ネットワーク１４内で利用される構成及びプロトコルに基づき、パケットのトンネリングを実行する。ノード１４は、ステップ１１０において、すべてのルートにコピーをトンネリングしたか判断する。さらなるルートが残っている場合、ノード１２は、ステップ１０４〜１０８を再び実行する。当該プロセスにより、ノード１２は、制御パケットのコピーを特定されたすべてのルートにトンネリングする。制御パケットのコピーをルートにトンネリングした後、ステップ１１２において、ノード１２は当該パケットを送信先に送信する。このステップでは、ノード１２は、従来のルーティングを用いてパケットを送信先に送信する。しかしながら、ルートノードはカバーを提供するため、ノード１２は、従来のルーティングを利用してパケットを通信する必要はない。
【００４３】
従って、上記フローチャート及びこれに関する説明は、ノード１２による制御パケットのフォルトトレラントルーティングの提供方法を示す。しかしながら、図６に示されるフローチャートに関して、システム１０は、ノード１２がパケットの送信元としてフォルトトレラントルーティングを提供するよう動作するための任意の適切な技術を利用することを考慮する。従って、このフローチャートにおけるステップの多くは、同時及び/または図示されるものと異なる順序で行われてもよい。さらに、ノード１２は、適切なものである限り、追加的なステップ、より少ないステップ及び/または異なるステップを有する方法を利用するようにしてもよい。
【００４４】
図８は、ノード１２がルートとして動作するための方法を示すフローチャートである。ノード１２は、ステップ１３０において、カプセル化された制御パケットを受け取る。例えば、ノード１２は、ＭＰＬＳプロトコルまたは他の適切なトンネリング技術を利用してルーティングされるパケットを受け取るようにしてもよい。ノード１２は、ステップ１３２において制御パケットを抽出し、ステップ１３４においてパケットの送信先を決定する。これにより、当該パケットの本来予定されていた送信先が特定される。例えば、ノードＣは、ノードＥへの送信のため予定されている制御パケットと共に、ノードＡからトンネリングされた制御パケットを受け取るようにしてもよい。
【００４５】
ノード１２は、ステップ１３６において、構成されたミニマムホップスパニングツリーに基づき、送信先へのルーティングを特定する。例えば、ノード１２内のルーティングテーブルは、予定されている送信先に基づく隣接するノード１２を示すようにしてもよい。ノードＡからノードＣに受け取られるトンネリングされたパケットに対して、ノードＣは、ノードＥへのルートを特定する。ノード１２は、ステップ１３８において、制御パケットを特定されたルート上に送信する。これにより、ノードＣは、ノードＥへの送信のため、パケットをノードＦに送信するであろう。
【００４６】
前述のフローチャート及びこれに関する説明は、ノード１２がルートとして動作するための一例となる方法を示す。しかしながら、他のフローチャートに関して、システム１０は、ノード１２がルートとして動作するための任意の適切な技術を利用することを考慮している。従って、上記フローチャートのステップの多くは、同時及び/または図示されるものと異なる順序で行われてもよい。さらに、ノード１２は、適切なものである限り、追加的なステップ、より少ないステップ及び/または異なるステップを有する方法を利用するようにしてもよい。
【００４７】
複数の実施例により本発明が説明されてきたが、多くの変更及び改良が当業者には示唆されるかもしれず、本発明は、添付されたクレームの範囲内に属する変更及び改良を含むものであるとされる。
【図面の簡単な説明】
【００４８】
【図１】本発明の実施例によるフォルトトレラントネットワークルーティングを実現するノードを有する通信システムを示す。
【図２】本システム内のネットワークセグメントの各ノードに対するミニマムホップスパニングツリーを示す図である。
【図３】ネットワークセグメント内のノードのルーティングツリーを構成するリンクを記録するテーブルである。
【図４】ネットワークセグメントのルーティングツリーに対するノードインシデンスのデグリーを記録するテーブルである。
【図５】本システムのノードの一例となる機能コンポーネントを示すブロック図である。
【図６】ネットワーク部分内のシングルリンクフォルトをカバーするノードを決定するための方法を示すフローチャートである。
【図７】フォルトトレラントを提供する制御パケットをルーティングするための方法を示すフローチャートである。
【図８】ルートノードによるカプセル化された制御パケットを処理するための方法を示すフローチャートである。
【図１】
2005537754.tif 000003
【図２】
2005537754.tif 000004
【図３】
2005537754.tif 000005
【図４】
2005537754.tif 000006
【図５】
2005537754.tif 000007
【図６】
2005537754.tif 000008
【図７】
2005537754.tif 000009
【図８】
2005537754.tif 000010
【国際調査報告】
2005537754.tif 000011
2005537754.tif 000012
2005537754.tif 000013