(57)【要約】  本発明は、終端間データ転送を提供するトランスポート層プロトコルを備えるネットワーク内のノードにおける、仮想リング上でデータグラムをマルチキャストするためのシステム、方法、およびコンピュータプログラムを提供する。仮想リング上の各ノードは、ネットワークトランスポート層プロトコルに従って、上流隣接ノードおよび下流隣接ノードというただ２つの隣接ノードに対してのみ、仮想接続を介して論理的に接続されている。本方法は、仮想リングデータグラムであって、仮想リング識別子と、仮想リングデータグラムのノード発信者を識別するための手段と、データとを含む仮想リングデータグラムを仮想リング上の下流隣接ノードへ送出するステップ、トークンを受信し、仮想リングを識別し、識別した仮想リング上の下流隣接ノードへトークンを転送するステップと、受信されたデータグラムが仮想リングデータグラムである場合、仮想リングを識別し、受信した仮想リングデータグラムのノード発信者をチェックするステップと、受信された仮想リングデータグラムがローカルで発信されていなかった場合、前記仮想リングデータグラム内のデータを処理し、識別した仮想リング上の下流隣接ノードへ前記仮想リングデータグラムを転送するステップと、受信された仮想リングデータグラムがローカルで発信されていた場合、仮想リングデータグラムを仮想リングから除去するステップとを備える。【選択図】図３
2007515117.tif 000002
【特許請求の範囲】
【請求項１】
終端間データ転送を提供するトランスポート層プロトコルを備えるネットワーク内において使用される、データグラムを仮想リング上にマルチキャストするための方法であって、前記仮想リング上の各ノードは、前記ネットワークトランスポート層プロトコルに従って、上流隣接ノードおよび下流隣接ノードというただ２つの隣接ノードに対してのみ、仮想接続を介して論理的に接続され、前記方法は、
仮想リングデータグラムであって、仮想リング識別子、前記仮想リングデータグラムのノード発信元を識別するための手段、及びデータを含む前記仮想リングデータグラムを前記仮想リング上の前記下流隣接ノードへ送出するステップと、
データグラムが受信されると、
受信された前記データグラムを識別するステップと、
受信された前記データグラムがトークンである場合、
前記仮想リングを識別するステップと、
前記トークンが有効か否かをチェックするステップと、
前記トークンが有効な場合、
識別された前記仮想リング上の前記下流隣接ノードへ前記トークンを転送するステップと、
受信された前記データグラムが仮想リングデータグラムである場合、
前記仮想リングを識別するステップと、
受信された前記仮想リングデータグラムの前記ノード発信元をチェックするステップと、
受信された前記仮想リングデータグラムがローカルに発信されていなかった場合、
前記仮想リングデータグラム内にあるデータを処理するステップと、
識別された前記仮想リング上の前記下流隣接ノードへ前記仮想リングデータグラムを転送するステップと、
受信された前記仮想リングデータグラムがローカルに発信されていた場合、
前記仮想リングデータグラムを前記仮想リングから除去するステップとを含む
方法。
【請求項２】
トークンが受信された場合に前記仮想リングを識別する前記ステップは、識別された前記仮想リング上の前記上流隣接ノードによって前記トークンが送出されたことをチェックするステップをさらに含み、
仮想データグラムが受信された場合に前記仮想リングを識別する前記ステップは、識別された前記仮想リング上の前記上流隣接ノードによって前記仮想リングデータグラムが送出されたことをチェックするステップをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項３】
前記仮想リング上のある１つのノードは、仮想リングマネージャノードとして定められ、
前記トークンは、前記トークンが前記仮想リングマネージャノードによって受信される度に増分されるシーケンス番号を備え、
前記トークンが有効か否かをチェックする前記ステップは、前記トークンのシーケンス番号が、最終受信以降に増分されたか否かをチェックするステップをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項４】
前記トークンが有効か否かをチェックする前記ステップは、前記トークンが有効でない場合、回復工程を実行するステップをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項５】
識別された前記仮想リング上の前記下流隣接ノードへ前記トークンを転送する前記ステップは、
タイマを開始して、前記トークンの戻りを待つステップと、
前記タイマが期限切れの場合に、回復工程を実行するステップとをさらに含み、
前記トークンを受信する前記ステップは、
前記タイマを停止するステップをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項６】
ノードは、前記ネットワークにおいてデータグラムを経路設定するコンピュータシステム、好ましくはルータ、または前記ネットワーク上でデータグラムを交換するコンピュータシステム、好ましくはクライアントまたはサーバである、先の請求項のいずれか１つに記載の方法。
【請求項７】
仮想リングマネージャノードにおける使用のための、先の請求項のいずれか１つに記載の方法であって、
トークンを生成する予備ステップと、
前記トークンシーケンス番号を初期値に設定する予備ステップと、
前記仮想リング上の前記下流隣接ノードへ前記トークンを転送する予備ステップとを含み、
識別された前記仮想リング上の前記下流隣接ノードへ前記トークンを転送する前記ステップは、
前記トークンシーケンス番号を増分するステップをさらに含み、
前記タイマが期限切れの場合に回復工程を実行する前記ステップは、
新たなトークンを生成するステップと、
前記仮想リング上の前記下流隣接ノードへ前記トークンを転送するステップとをさらに含む、方法。
【請求項８】
前記トークンは、
前記送出ノードの送信元アドレスと、前記仮想リング上の次のノードの送信先アドレスとを含むヘッダと、
送信元ポートと、送信先ポートとを含むヘッダと、
前記データグラムをトークンであるとして識別するための手段と、
前記仮想リングを識別するための手段と、
前記トークンが前記仮想リングマネージャノードによって受信される度に増分されるシーケンス番号とを含むデータグラムである、先の請求項のいずれか１つに記載の方法。
【請求項９】
前記仮想リング上を循環する各仮想リングデータグラムは、
前記仮想リング上の前記送出ノードの送信元アドレスと、前記仮想リング上の次のノードの送信先アドレスとを含むヘッダと、
送信元ポートと、送信先ポートとを含むヘッダと、
前記仮想リング上の前記仮想リングデータグラムを識別するための手段と、前記仮想リングを識別するための手段と、前記仮想リングデータグラムの前記ノード発信元を識別するための手段とを含む仮想リングヘッダと、
データとを含む、先の請求項のいずれか１つに記載の方法。
【請求項１０】
前記仮想リングを識別するための手段、前記上流隣接ノードのアドレス、前記下流隣接ノードのアドレス、前記仮想リングマネージャノードのアドレス、及び必要に応じて、バックアップ仮想リングマネージャノードのアドレスを維持および更新するステップをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項１１】
仮想リングに参加する予備ステップを含み、当該ステップは、
前記仮想リング上で予め定められた仮想リングマネージャノードへ、前記ノードのアドレスと、前記仮想リングを識別するための手段とを含む挿入要求メッセージを送出するステップと、
前記仮想リングマネージャノードから、上流隣接ノードのアドレスと、下流隣接ノードのアドレスとを含む挿入確認メッセージを受信するステップとを含む、先の請求項のいずれか１つに記載の方法。
【請求項１２】
挿入要求メッセージを送出する前記ステップは、挿入タイマを開始するステップをさらに含み、
挿入確認メッセージを受信する前記ステップは、前記挿入タイマを停止するステップをさらに含み、
前記挿入タイマが期限切れの場合に、
前記仮想リング上で予め決められたバックアップリングマネージャノードへ、前記ノードのアドレスと、前記仮想リングを識別するための手段とを含む挿入要求メッセージを送出するステップと、
前記挿入タイマをリスタートするステップと、
前記バックアップ仮想リングマネージャノードから、上流隣接ノードのアドレスと、下流隣接ノードのアドレスとを含む挿入確認メッセージを受信するステップと、
前記挿入タイマを停止するステップとをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項１３】
前記仮想リングを離れるさらなるステップ含み、当該ステップは、
前記仮想リング上で予め定められた仮想リングマネージャノードへ、前記上流隣接ノードの前記アドレスと、前記下流隣接ノードの前記アドレスと、前記ノードの前記アドレスとを含む除去要求メッセージを送出するステップと、
前記仮想リングマネージャノードから除去確認メッセージを受信するステップとを含む、先の請求項のいずれか１つに記載の方法。
【請求項１４】
除去要求メッセージを送出する前記ステップは、除去タイマを開始するステップをさらに含み、
除去確認メッセージを受信する前記ステップは、前記除去タイマを停止するステップをさらに含み、
前記挿入タイマが期限切れの場合、
前記仮想リング上で予め決められたバックアップリングマネージャノードへ、前記上流隣接ノードの前記アドレスと、前記下流隣接ノードの前記アドレスと、前記ノードの前記アドレスとを含む除去要求メッセージを送出するステップと、
前記除去タイマをリスタートするステップと、
前記バックアップリングマネージャノードから除去確認メッセージを受信するステップと、
前記除去タイマを停止するステップとをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項１５】
前記仮想リング上で予め定められた仮想リングマネージャノードから、新規の上流隣接ノードのアドレス、または新規の下流隣接ノードのアドレス、あるいはその両方を備える隣接変更メッセージを受信するステップと、
前記新規の上流隣接ノードの前記アドレス、または前記新規の下流隣接ノードの前記アドレスあるいはその両方を維持するステップと、
前記仮想リングマネージャノードへ隣接変更済み確認メッセージを送出するステップとをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項１６】
前記仮想リングに挿入するべき新規のノードのＩＰアドレスを含む挿入要求メッセージを受信するステップと、
下流隣接ノードへ、新規ノードの前記アドレスを前記下流隣接ノードの新しい上流隣接ノードとして含む隣接変更メッセージを送出するステップと、
隣接変更済み確認メッセージを受信するステップと、
前記下流隣接ノードのアドレスを、前記新規のノードの前記アドレスで更新するステップと、
前記新規のノードへ、前記新規のノードの上流隣接ノードのアドレスと、前記新規のノードの下流隣接ノードのアドレスとを含む挿入確認メッセージを送出するステップとをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項１７】
前記仮想リング上のノードから、除去する前記ノードの上流隣接ノードのアドレスと、除去する前記ノードの下流隣接ノードのアドレスと、除去する前記ノードのアドレスとを含む除去要求メッセージを受信するステップと、
除去する前記ノードの前記下流隣接ノードへ、除去する前記ノードの前記上流隣接ノードの前記アドレスを含む隣接変更メッセージを送出するステップと、
除去する前記ノードの前記上流隣接ノードへ、除去する前記ノードの前記下流隣接ノードの前記アドレスを含む隣接変更メッセージを送出するステップと、
除去する前記ノードの前記上流隣接ノードおよび前記下流隣接ノードから隣接変更済み確認メッセージを受信するステップと、
除去する前記ノードへ除去確認メッセージを送出するステップとをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項１８】
前記仮想リング上の上流隣接ノードとの接続の消失を示す隣接消失指示メッセージであって、障害のある前記上流隣接ノードのアドレスと、前記隣接消失を示す指示メッセージを発信し、かつ前記上流隣接ノードとの接続の消失を検出したノードのアドレスとを含む前記隣接消失指示メッセージを受信するステップと、
障害のある前記ノードの下流隣接ノードへ、新規の上流隣接ノードのアドレスを含む隣接変更メッセージを送出するステップと、
障害のある前記ノードの下流隣接ノードから、隣接変更済みメッセージを受信するステップと、
前記仮想リング上の下流隣接ノードとの接続の消失を示す隣接消失指示メッセージであって、障害のある前記下流隣接ノードのアドレスと、前記隣接消失指示メッセージを発信し、かつ前記下流隣接ノードとの接続の消失を検出した前記ノードのアドレスとを含む、前記隣接消失指示メッセージを受信するステップと、
障害のある前記ノードの上流隣接ノードへ、新規の下流隣接ノードのアドレスを含む隣接変更メッセージを送出するステップと、
障害のある前記ノードの前記上流隣接ノードから、隣接変更済みメッセージを受信するステップとをさらに含む、先の請求項のいずれか１つに記載の方法。
【請求項１９】
前記ネットワークは、ＴＣＰ／ＩＰ（伝送制御プロトコル／インターネットプロトコル）ネットワークであり、
前記仮想リングのノード部分間の論理接続は、ＴＣＰセッションであり、
ノードは、当該ノードの隣接ノードと、前記仮想リング上で、前記ＴＣＰセッションを介してデータグラムをマルチキャストしており、
アドレスは、ＩＰアドレスである、先の請求項のいずれか１つに記載の方法。
【請求項２０】
ノードを挿入またはノードを除去するためにノード間で交換されるメッセージは、ＵＤＰ（ユーザデータグラムプロトコル）メッセージである、先の請求項のいずれか１つに記載の方法。
【請求項２１】
先の請求項のいずれか１つに記載の方法を実行するために適応された手段を備える、ノード。
【請求項２２】
ノードにおいて実行される場合に、請求項１から２０のいずれか１つに記載の方法を実行するための命令を備える、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルネットワーク上での通信に関し、より特定的には、インターネットプロトコル（ＩＰ）ネットワークにおけるノード間の仮想リングを作成するため、かつデータグラムをこの仮想リングのノード部分へマルチキャストするためのシステムおよび方法に関する。
【背景技術】
【０００２】
本説明において、「ネットワーク」という用語は、インターネットプロトコル（ＩＰ）技術に基づく通常のネットワークを示す。このネットワークは、構内情報通信網（ＬＡＮ）であってもよいが、企業（民間）イントラネット、またはさらには（公共の）イントラネットであってもよい。「ノード」という用語は、ルータなどの通信を経路設定するネットワークにおけるコンピュータシステム、また、ワークステーションおよびサーバなどのネットワーク上で情報を交換するコンピュータシステムを示す。
【０００３】
ネットワークにおいて、ノードは、同一のグループの他のノードと情報を交換できなくてはならない。たとえば、同一の情報を互いに異なる場所にある複数のノードへ同報通信することは、「マルチキャスト」と呼ばれる。図１に示すようなマルチキャストグループと呼ばれるＮ個のノードのグループにおいて、各ノード（１０１）は、（Ｎ−１）個の他のノード（１００）と通信する必要がある。これを行うには、各ノードは、他の各ノード（１００）とセッションを確立する。通常、ＩＰネットワークにおいては、伝送制御プロトコル（ＴＣＰ）を使用して、ノード間の通信を行う。なぜならば、このプロトコルは、セッションを通じて信頼性のあるデータ伝送を可能とし、フロー制御に対応するからである。これは、ベストエフォートに基づいた、どのセッション機構をも提供しないＵＤＰ（ユーザデータグラムプロトコル）と称されるトランスポートプロトコルについてはそうではない。
【０００４】
Ｎ個のノードのグループ内のノードがそのグループの他のすべてのノードに対して情報を通信したい場合には、Ｎ−１個のＴＣＰセッションが必要である。すべてのノードが一緒にフルメッシュ構成で通信する必要がある場合には、Ｎ×（Ｎ−１）／２個のＴＣＰセッションが必要である。ＴＣＰセッションは双方向であるので、セッションの必要数は、Ｎ×（Ｎ−１）／２であり、Ｎ×（Ｎ−１）ではない。
【０００５】
セッション数は、数百または数千のノードを備えるネットワークにおいては考慮すべきものとなりうる。これは、各ノードでのネットワークおよびリソース（データ処理およびメモリ）の使用における帯域幅の消費の点で、重大な影響力を及ぼすと共に、重要なオーバヘッドという結果になりうる。各ノードにおいて、ＴＣＰセッションの確立には、データ処理リソースが必要であり、これらのＴＣＰセッションの維持には、特にＴＣＰセッション（ＴＣＰ制御ブロック）の文脈を記憶するためのメモリが必要である。
【０００６】
アプリケーションレベルの同期がない状態で、ノードは、すべてのＴＣＰセッションについての同一の情報を同時に交換することができる（任意のものから任意のものへの通信）。これは、ネットワークレベルでは帯域幅を消耗するものであり、各ノードレベルではリソースを消耗するものである。この場合の一例は、ルータ間での経路設定情報の交換である。各ルータは、ネットワークにおいて使用される経路設定プロトコルに依存して、経路設定情報を他のルータへ周期的または変更が生じた場合に同報通信する。他の例は、分散型データベースにおける複数のサーバの同期である。
【０００７】
ノード間のセッション数を制限するためには、いくつかの解決策がある。図２に示す一解決策は、すべての他のノードが接続される「ランデブーポイント」、言い換えれば中央ノードを選択するものである。中央ノード（２００）は、ネットワークにおけるすべての他のノードへ情報を分散する役割を担う。「星型ネットワーク」と呼ばれるこの構成は、接続数（Ｎ−１個のセッション）を削減するものであるが、主な欠点は、中央ノードがネットワークの最も脆弱なポイントであるということによる。一般的に、中央ノードは、バックアップ中央ノード（２０１）によって二重化される。「二重星型ネットワーク」と呼ばれるこの構成は、（Ｎ−１）＋（Ｎ−２）個の接続を要求する。
【０００８】
注記：中央ノード（２００）は、バックアップ中央ノード（２０１）を含むすべての他のノードに接続されている。その結果、Ｎ−１個のＴＣＰセッションが確立される。バックアップ星型ノード（２０１）に基づく第２の星型構成を追加すると、さらにＮ−１個のＴＣＰセッションが必要となる。しかしながら、中央ノード（２００）とバックアップ中央ノード（２０１）との間のＴＣＰセッションが既に存在しているので、このセッションは、二重化される必要がない。結論として、二重星型構成において必要なセッション数は、（Ｎ−１）＋（Ｎ−２）＝２×Ｎ−３である。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、相互通信ノードを備えるＩＰネットワークにおける帯域幅の使用を削減することである。
【００１０】
本発明の他の目的は、相互通信ノードのリソース消費を削減することである。
【００１１】
本発明のさらなる目的は、ＩＰネットワークにおける相互通信ノードのいくつかのグループを規定することである。
【発明を解決するための手段】
【００１２】
本発明は、終端間データ転送を提供するトランスポート層プロトコルを備えるネットワーク内において使用される、仮想リング上でデータグラムをマルチキャストするためのシステム、方法、およびコンピュータプログラムを提供する。仮想リング上の各ノードは、ネットワークトランスポート層プロトコルに従って、上流隣接ノードおよび下流隣接ノードというただ２つの隣接ノードに対してのみ、仮想接続を介して論理的に接続されている。
【００１３】
本方法は、仮想リングデータグラムであって、仮想リング識別子と、仮想リングデータグラムのノード発信元を識別するための手段と、データとを含む仮想リングデータグラムを仮想リング上の下流隣接ノードへ送出するステップと、
データグラムが受信されると、受信されたデータグラムを識別するステップと、
受信されたデータグラムがトークンである場合、仮想リングを識別するステップと、
トークンが有効か否かをチェックするステップと、
トークンが有効な場合、識別された仮想リング上の下流隣接ノードへトークンを転送するステップと、
受信されたデータグラムが仮想リングデータグラムである場合、仮想リングを識別するステップと、受信された仮想リングデータグラムのノード発信元をチェックするステップと、
受信された仮想リングデータグラムがローカルに発信されていなかった場合、前記仮想リングデータグラム内にあるデータを処理するステップと、識別された仮想リング上の下流隣接ノードへ前記仮想リングデータグラムを転送するステップと、
受信された仮想リングデータグラムがローカルに発信されていた場合、仮想リングデータグラムを仮想リングから除去するステップとを含む。
【００１４】
本発明のさらなる実施例は、添付の従属請求項において与えられる。
【００１５】
本発明の上記の特徴および利点ならびに他の目的は、以下の明細書、請求項、および図面を参照することで、より理解できるだろう。
【００１６】
本発明の特徴と考えられる新規および進歩的な特色は、添付の請求項において述べられる。しかしながら、使用に好ましいモードならびにその目的および利点と共に、本発明自体は、添付の図面と共に例証となる詳細な実施形態の以下の詳細な説明を参照することで、最も理解されるだろう。
【発明を実施するための最良の形態】
【００１７】
本発明は、仮想リングに基づいてネットワーク接続形態を開示する。互いに通信する必要があるネットワークのＮ個のノードは、仮想リングに従って論理的／仮想的に接続され、各ノードは、ただ２つの隣接ノードである上流隣接ノードおよび下流隣接ノードと通信する。
【００１８】
本発明は、任意の種類のノードに適用されるが、本発明は、いくつかのノード間で同一の情報を交換する必要がある場合に特に興味深いものである。
【００１９】
いくつかの仮想リングが、同一の物理ネットワーク上に実施されてもよく、各仮想リングによって、ノードの一部が互いに通信できるようになる。同一のノードは、いくつかの仮想リングに同時に関与することができる。各仮想リングは、（仮想リング識別子と呼ばれる）固有の識別子によって識別される。仮想リング識別子は、仮想リングに関与するすべてのノードにおいて、静的に構成される。仮想リングが開始および管理されるやり方は、後述する。
【００２０】
ＴＣＰ／ＩＰプロトコル
好ましい一実施形態において、本発明は、今日、世界で最も広く使用されているプロトコルであるＴＣＰ／ＩＰプロトコルのＴＣＰ層の最上部において実施される。しかしながら、本発明は、ＴＣＰのトランスポート機能を使用するだけではない。ＩＰＸ（インターネットワークパケット交換）などのトランスポート機能を提供する任意の他のプロトコルスタックの最上部において、本発明を実施することもできる。ＩＰが本説明では選ばれているのは、このプロトコルは、ほとんどのネットワークで使用されているからである。ＴＣＰのトランスポート機能が何らかの信頼性をもたらすのは、この機能が、パケット損失などの送信上の問題を扱うからである。仮想リングに沿った情報の循環は、インターネットプロトコル（ＩＰ）と、伝送制御プロトコル（ＴＣＰ）とに基づく。ＴＣＰが選ばれてきたのは、損失という危険なくパケットを送ることができるからである。また、ＴＣＰは、遠隔ノードの消失を、接続を維持することによって通知する。ＴＣＰおよびＩＰを使用すると、インターネット自体を含むＩＰネットワークに任意の部分へ仮想リングを拡張することができる。そのような仮想リングと通信する、世界の異なる部分におけるノードを想定することができる。
【００２１】
本発明において、ユーザデータグラムプロトコル（ＵＤＰ）を使用して、例えば、Ｒｉｎｇ  ＩｎｓｅｒｔｉｏｎおよびＲｉｎｇ  Ｒｅｍｏｖａｌメッセージを、特定のノードと、仮想リングマネージャとの間で交換することもできる。これらのメッセージは、挿入または除去処理の間にのみ交換されるので、ＴＣＰプロトコルを使用してＴＣＰセッションを確立する必要がない。
【００２２】
本発明は、リングネットワークの各ノード部分において新たな特定のコードを必要とする。このコードは、本発明のために確保された特定のＴＣＰポートと特定のＵＤＰポートとを使用する。このコードを使用して、仮想リング接続形態を確立、維持、および取り壊す。
【００２３】
トークン
リング接続形態を維持するためには、互いに異なるノード間で何らかの情報を周期的に交換する必要がある。これらの情報の１つは、「トークン」と呼ばれ、ＩＢＭ（ＩＢＭは、インターナショナルビジネスマシン社の登録商標である）によってここ最近１０年間開発された「トークンリング」アーキテクチャのことを指す。図４は、仮想リング（４００）上のノードＡおよびノードＢ間で循環するトークン（４０１）を説明する。
【００２４】
トークンを周期的なキープアライブメッセージとして使用して、リング接続形態を確認する。トークンは、仮想リングマネージャ（４０２）によって周期的に生成され、各ノードによってその下流隣接ノードへ転送される。仮想リングマネージャによる（上流隣接ノードからの）トークンの受信は、リング接続形態が有効で、ループが切断されていないことを示す。リングが何らかの理由（１つのノードの消失、２つの隣接ノード間の接続の消失）で切断されている場合には、トークンの消失は、リング上に問題があることを示すことになる。各ノードは、トークンの受信を監視している。所定の時間量の後にトークンが受信されていない場合には、各ノードは、詳細に後述するリング回復処理をトリガする。トークンは、ちょうど任意の他の情報と同じように、ノードからノードへ転送される。これは、ノード間で設立されたＴＣＰセッションをトークンが使用することを意味する。
【００２５】
シーケンス番号フィールドを使用して、トークンの現在のコピーを識別する。
【００２６】
トークン構成
【００２７】
【表１】
2007515117.tif 000003
【００２８】
トークンを、図５を参照して説明する。
・ＩＰヘッダ（５００）：仮想リングにおける送出ノードの送信元ＩＰアドレスおよび次のノードの送信先ＩＰアドレス
・ＴＣＰヘッダ（５０１）：送信元および宛先ポート＝本発明のために確保された周知のポート
・仮想リングトークン（５０２）：このメッセージは、３つのフィールドを含む：
１．０×０００１に設定されたメッセージコード（５０３）。メッセージの種類はトークンであることを識別することが可能。
２．２バイトの仮想リング識別子（５０４）：仮想リングを識別。これにより、同一のノードが複数の仮想リングに関与可能。
３．４バイトのシーケンス番号（５０５）：仮想リングマネージャによって設定および増分される。これにより、仮想リングマネージャは、トークンの二重化の可能性を検出できる。
【００２９】
仮想リングに沿ったデータの伝搬
仮想リングに関与しているノードがその上流隣接ノードからデータグラムを受信する場合、このデータグラムを処理、すなわち受信されたメッセージのデータ部分を記憶し、データグラムが仮想リングに沿って循環することができるように、その下流隣接ノードへ転送する。しかしながら、仮想リングに接続されたノードは、仮想リングに沿って循環するデータグラムと、仮想リングに関与しない他のノードから受信された通常のＩＰデータグラムとを認識することができなくてはならない。このためには、仮想リング上で交換されるデータグラムは、以下のカプセル化を有する：
【００３０】
【表２】
2007515117.tif 000004
【００３１】
ＴＣＰデータグラム内へのデータのカプセル化は、以下の利点を有する：
１．メッセージコード：受信されたメッセージがデータグラムであることを示す。
２．仮想リング識別子：どの仮想リング上でメッセージが転送されなければならないかを示す。ノードは、複数の仮想リングに属していてもよい。
３．送信者ＩＰアドレス：これは、データを生成したＩＰアドレスである。
【００３２】
仮想リング上でのデータグラムの送信
１／ノードが仮想リング上でデータグラムを送出する必要がある場合、このノードは、上述の仮想リングヘッダを付加して、データをＴＣＰデータグラム内にカプセル化する。このデータグラムは、仮想リング上の下流隣接へ送出される。
２／仮想リング上の各ノードは、送出者アドレスをチェックして、どのノードがデータグラムを作成したかを確かめる。その後、各ノードはデータを読み出しおよび処理して、データグラムをその下流隣接へ転送する。
３／データグラムが送出者ノードによって受信し戻される（送出者ノードは、仮想リングヘッダ内の送出者ＩＰアドレスをチェックする）と、送出者ノードは、データグラムを仮想リングから除去する。これは、データグラムは削除されて、下流隣接ノードへ再び転送されないことを意味する。
【００３３】
仮想リング接続形態
仮想リングは、リングを形成するために接続されたノードのリストである。どのノードもリングを完全に見ることはできない。リングに関与するノードのこのリストは、ネットワークのどこにも記憶されない。各ノードは、以下の情報を備える（ノードリングレコード）。
【００３４】
【表３】
2007515117.tif 000005
【００３５】
仮想リングマネージャ
仮想リングに関与するノードのうちの１つは、「仮想リングマネージャ」の役割を果たす。仮想リングマネージャは、仮想リングの接続形態を維持する役割を担う。より特定的には、仮想リングマネージャは、ノードの挿入および除去の役割を担う。
【００３６】
重要なのは、仮想リングマネージャＩＰアドレスは、仮想リングの各ノードにおいて静的に構成されることである。仮想リングマネージャは、シングルポイント障害を構成するので、バックアップ仮想リングマネージャが一般的に使用される。バックアップ仮想リングマネージャのＩＰアドレスも、各ノードにおいて静的に構成される。ノードを仮想リングに挿入したいが仮想リングマネージャから何の応答も受信しない場合には、このノードは、バック仮想リングマネージャに連絡を取る。
【００３７】
仮想リングにおけるノードの挿入
図６は、ノードＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆを備える仮想リング（６００）に新規のノードＧ（６０１）を挿入することを説明する。新規のノードＧ（６０１）が仮想リング（６００）に参加したい場合には、以下の事項が生じる。
注記：好ましい一実施形態において、すべての挿入メッセージは、ＵＤＰプロトコルと、本発明において規定された予備のＵＤＰポートとを使用する。
【００３８】
・仮想リングに挿入するノード（ノードＧ）（６０１）は、仮想リングマネージャの構成済みのＩＰアドレスを使用して、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｓｉｏｎ  Ｒｅｑｕｅｓｔ」メッセージ（６０３）を仮想リングマネージャ（６０２）へ送信する。挿入するノード（６０１）は、「挿入要求」タイマを開始させて、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージ（６０４）を待つ。
【００３９】
・仮想リングマネージャ（６０２）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｒｅｑｕｅｓｔ」メッセージを受信して、ノードＧ（６０１）のＩＰアドレスであるメッセージの送信元ＩＰアドレスを確認する。
【００４０】
・仮想リングマネージャ（６０２）は、その下流隣接ノードＦ（６０６）へ「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージ（６０５）を送出する。仮想リングマネージャは、ノードリングレコード内にノードＦのＩＰアドレスを見つける。「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージは、上流隣接ＩＰアドレスとして、ノードＧ（６０１）のＩＰアドレスを含む。メッセージ内の下流隣接ＩＰアドレスは、０．０．０．０に設定される。なぜならば、このアドレスは、変更される必要がないからである。
【００４１】
・ノードＦ（６０６）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージ（６０５）を受信する。ノードＦは、「ＴＣＰ  Ｒｅｓｅｔ」メッセージを発行することによって、その上流隣接ノード（仮想リングマネージャ）とのＴＣＰセッションを取り壊す。ノードＦ（６０６）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージ（６０５）内のノードＧ（６０１）のＩＰアドレスをそのノードリングレコード（上流隣接ＩＰアドレス）に記憶させる。
【００４２】
・ノードＦ（６０６）は、新たな上流隣接ノード（ノードＧ（６０１））とのＴＣＰセッションを確立し、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージ（６０７）を仮想リングマネージャ（６０２）へ送出して、ノードＦがその上流隣接ノードを変更した旨を示す。
【００４３】
・仮想リングマネージャ（６０２）は、「ＴＣＰ  Ｒｅｓｅｔ」メッセージをノードＦ（６０６）から受信して、ＴＣＰセッションを取り壊す。仮想リングマネージャは、ノードＧ（６０１）との新たなＴＣＰセッションを確立して、ノードＧ（６０１）のＩＰアドレスをそのノードリングレコード、すなわち下流隣接ＩＰアドレスに記憶させる。
【００４４】
・仮想リングマネージャ（６０２）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージ（６０４）をノードＧ（６０１）へ送出する。このメッセージは、ノードＦ（６０６）のＩＰアドレスを含む。
【００４５】
・ノードＧ（６０１）は、そのノードリングレコードを、
・仮想リングマネージャＩＰアドレスに等しい上流隣接ＩＰアドレス、および
・ノードＦのＩＰアドレスに等しい下流隣接ＩＰアドレスで更新する。
【００４６】
ノードＧ（６０１）は、「挿入要求」タイマを停止させる。
【００４７】
・「「挿入要求」タイマが期限切れの場合、ノードＧ（６０１）は「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージ（６０４）を仮想リングマネージャ（６０２）から受信していないことを意味する。その場合には、ノードＧ（６０１）は、バックアップ仮想リングマネージャ（６０８）に連絡を取る。この処理は、バックアップ仮想リングマネージャに関する項で後述する。
【００４８】
ノードＧの挿入の結果を、図７を参照して説明する。現在、ノードＧ（７０１）が仮想リング（７００）上の仮想リングマネージャ（７０２）とノードＦ（７０３）との間に挿入されている。
【００４９】
仮想リングからの要求形ノード除去
本項において説明する要求形ノード除去の場合は、あるノードが、これ以上グループに関与したくないので仮想リングから除去してもらいたい場合に該当する。他のノード除去の場合は、ノードに障害があって、仮想リングが切断されている場合に該当する。この非要求形除去の場合は、別の項で説明する。
【００５０】
図８は、ノード要求形除去処理を説明する。ノードＣ（８０１）が仮想リングから除去されたい場合には、以下の事項が生じる：
【００５１】
・ノードＣ（８０１）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｒｅｑｕｅｓｔ」メッセージ（８０３）を仮想リングマネージャ（８０２）へ送出する。このメッセージは、
・ノードＣ（８０１）のＩＰアドレス、
・その上流隣接ノードであるノードＢ（８０４）のＩＰアドレス、および
・その下流隣接ノードであるノードＤ（８０５）のＩＰアドレスを備える。
【００５２】
ノードＣ（８０１）は、「リング除去」タイマを開始して、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージ（８０６）を待つ。
【００５３】
・仮想リングマネージャ（８０２）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｒｅｑｕｅｓｔ」メッセージ（８０３）をノードＣ（８０１）から受信して、除去処理を開始する。それには、ノードＣの上流隣接ノードおよび下流隣接ノードのＩＰアドレスが記載されている。
【００５４】
・仮想リングマネージャ（８０２）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージ（８０７）を、除去するノードであるノードＣ（８０１）の上流隣接ノードであるノードＢ（８０４）へ送出する。このメッセージは、
・変更されない上流ノードＩＰアドレス：０．０．０．０、および
・ノードＣ（８０１）の下流隣接ノードであるノードＤ（８０５）のＩＰアドレスに等しい下流ノードＩＰアドレスを備える。
【００５５】
・仮想リングマネージャ（８０２）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージ（８０８）を、除去するノードであるノードＣ（８０１）の下流隣接ノードであるノードＤ（８０５）へ送出する。このメッセージは、
・ノードＣ（８０１）の上流隣接ノードであるノードＢ（８０４）のＩＰアドレスに等しい上流ノードＩＰアドレス、および
・変更されない下流ノードＩＰアドレス：０．０．０．０を備える。
【００５６】
仮想リングマネージャ（８０２）は、例えば確認を３０秒待つ「隣接変更」タイマを開始する。
【００５７】
・ノードＢ（８０４）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージ（８０７）を仮想リングマネージャ（８０２）から受信して、そのノードリングレコードを修正する。このメッセージ内の上流ノードＩＰアドレスは、０．０．０．０である。これは、アドレスは変更する必要がないことを意味する。ノードＢ（８０４）は、ノードＡ（８０９）をその上流隣接ノードとして維持する。
【００５８】
一方で、ノードＢ（８０４）は、その下流隣接ＩＰアドレスを修正して、メッセージ内の受信されたアドレスを使用する。ノードＢ（８０４）は、その以前の下流隣接ノードであったノードＣ（８０１）とのＴＣＰ接続を取り壊して、新たな下流隣接ノードであるノードＤ（８０５）との新たなＴＣＰ接続を確立する。
【００５９】
ノードＢ（８０４）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージ（８１０）を仮想リングマネージャ（８０２）へ送出する。
【００６０】
・ノードＤ（８０５）は、ノードＢ（８０４）と同じことを行う。ノードＤは、そのノードリング記録を更新し、上流隣接であったノードＣ（８０１）と有していたＴＣＰセッションを取り壊し、新たな上流隣接であるノードＢ（８０４）とのＴＣＰセッションを確立する。ノードＤ（８０５）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージ（８１１）を仮想リングマネージャ（８０２）へ送出する。
【００６１】
・仮想リングマネージャが「「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージをノードＢおよびＣの両方から受信する場合には、「隣接変更」タイマを停止して、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージ（８０６）をノードＣ（８０１）へ送出して、除去処理が成功したことを示す。
【００６２】
・ノードＣ（８０１）が「リング除去」タイマを停止する。「リング除去」タイマが期限切れの場合には、仮想リングマネージャ（８０２）は除去処理を達成していないことを意味する。この場合、ノードＣ（８０１）は、バックアップ仮想リングマネージャ（８０４）に連絡を取らなければならない。
【００６３】
ノードの消失
仮想リングネットワークにおけるノードの消失は、ＴＣＰ接続の消失に伴って、その隣接ノードによって検出される。「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｒｅｑｕｅｓｔ」メッセージによって仮想リングマネージャに通知することなく、ノードが仮想リングから除去される場合（ノード障害が生じた場合のはずである）には、２つの隣接ノード（上流および下流）が、このノードとのＴＣＰ接続を（ＴＣＰタイムアウト後）所定の期間失っている。図９を参照して説明されるように、以下の事項が生じる：
【００６４】
・仮想リングネットワーク（９００）内のノードＣ（９０１）に障害が発生または電源オフとなる。
【００６５】
・ノードＣ（９０１）の上流隣接ノードであるノードＢ（９０３）が、ノードＣとのＴＣＰ接続を失う。ノードＢは、ＴＣＰ接続を再確立しようと試みるが、成功しない。
【００６６】
・ノードＣ（９０１）の下流隣接ノードであるノードＤ（９０４）が、ノードＣとのＴＣＰ接続を失う。ノードＤは、ＴＣＰ接続を再確立しようと試みるが、成功しない。
【００６７】
・ノードＢ（９０３）が、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｌｏｓｓ  Ｉｎｄｉｃａｔｉｏｎ」（９０７）メッセージを仮想リングマネージャ（９０２）へ送出する。このメッセージは、
・ノードＢのＩＰアドレス、および
・ノードＢの下流隣接ＩＰアドレス、すなわち、ノードＣ（９０１）のアドレスを含む。
【００６８】
上流隣接ＩＰアドレスは、０．０．０．０に設定される。なぜなら、ノードＢの上流隣接ノードには何の問題も見受けられなかったからである。
【００６９】
・ノードＤ（９０４）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｌｏｓｓ  Ｉｎｄｉｃａｔｉｏｎ」（９０５）メッセージを仮想リングマネージャ（９０２）へ送出する。このメッセージは、
・ノードＤのＩＰアドレス、および
・ノードＤの上流隣接ＩＰアドレス、すなわち、ノードＣ（９０１）のアドレスを含む。
【００７０】
下流隣接ＩＰアドレスは、０．０．０．０に設定される。なぜなら、ノードＤの下流隣接ノードには何の問題も見受けられなかったからである。
【００７１】
・仮想リングマネージャ（９０２）は、ノードＣの上流隣接ノードと、ノードＣの下流隣接ノードとの両方からメッセージを受信する。仮想リングは再構成される必要がある。
【００７２】
・仮想リングマネージャ（９０２）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージ（９０６）をノード（９０４）へ送出する。このメッセージは、
・ノードＢのＩＰアドレスに等しい上流隣接ＩＰアドレス、および
・０．０．０．０（ＩＰアドレスは変更される必要がない）に等しい、変更されない下流隣接ＩＰアドレスを備える。
【００７３】
・ノードＤ（９０４）は、ノードリングレコード内の上流隣接ＩＰアドレスを更新して、新たな上流隣接ノード（ノードＢ（９０３））とのＴＣＰ接続を確立する。
【００７４】
・ノードＤ（９０４）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｏｄｅ  Ｃｈａｎｇｅｄ」（９０９）メッセージを仮想リングマネージャ（９０２）へ送り戻して、変更を確認する。
【００７５】
・仮想リングマネージャ（９０３）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージ（９０８）をノードＢ（９０３）へ送出する。当該メッセージは、
・０．０．０．０（ＩＰアドレスは変更される必要がない）に等しい、変更されない上流隣接ＩＰアドレス、および
・ノードＤのＩＰアドレスに等しい下流隣接ＩＰアドレスを備える。
【００７６】
・ノードＢ（９０３）は、そのノードリングレコード内の下流隣接ＩＰアドレスを更新する。
【００７７】
・ノードＢ（９０３）は、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｏｄｅ  Ｃｈａｎｇｅｄ」メッセージ（９１０）を仮想リングマネージャ（９０２）に送り戻して、変更を確認する。
【００７８】
図１０は、ノードＣ（１００１）の消失後の仮想リング（１０００）再構成の結果を示す。
【００７９】
バックアップ仮想リングマネージャ
バックアップ仮想リングマネージャは、仮想リングマネージャと同一の処理を実行する。バックアップ仮想リングマネージャは、仮想リングマネージャからの応答がない場合に、挿入、除去、および回復メッセージをノードから受信して、これらのメッセージを仮想リングマネージャと同様に処理する。
【００８０】
トークン消失回復
仮想リングマネージャを含む全てのノードは、トークンの消失を検出するためにタイマを使用する。トークンが消失した場合には、リングは再構築される必要がある。このタイマの値は、「ノードの消失」の項で説明する処理がリングの再構成前に生じることが可能なように、ＴＣＰセッションタイマよりも大きくなければならない。ノードがトークンの消失を検出した場合には、ノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｒｅｑｕｅｓｔ」メッセージを仮想リングマネージャへ送出して、図８において説明したように（「要求形ノード除去」の項を参照）確認を待つ。所定の期間後に、ノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｒｅｑｕｅｓｔ」メッセージを仮想リングマネージャへ送出して、図６において説明したように（「ノードの挿入」の項を参照）リングに再び関与する。
【００８１】
挿入および除去メッセージ
これらのメッセージは、ユーザデータグラムプロトコル（ＵＤＰ）を使用して交換される。仮想リング識別子フィールドの値を使用して、現在の仮想リングを識別する。仮想リング識別子は、各関与ノードにおいて静的に構成される。
【表４】
2007515117.tif 000006
【００８２】
【表５】
2007515117.tif 000007
【００８３】
【表６】
2007515117.tif 000008
【００８４】
【表７】
2007515117.tif 000009
【００８５】
【表８】
2007515117.tif 000010
【００８６】
【表９】
2007515117.tif 000011
【００８７】
【表１０】
2007515117.tif 000012
【００８８】
【表１１】
2007515117.tif 000013
【００８９】
本発明に係る処理
ノードにおけるトークン処理
図１１は、ノードがトークンを受信後にこのノードによって実行されるアルゴリズムを説明する。
【００９０】
・（１１００）ノードがちょうど仮想リングに挿入されたところである。
・（１１０１）ノードは、待ちトークンタイマ（３０秒）を開始して、トークンの受信を待つ。
・（１１０２）ノードは、トークンが受信されたか否かをチェックする。
・（１１０３）トークンが受信されていない場合には、ノードは、トークンタイマが期限切れか否かをチェックする。トークンタイマが期限切れでない場合には、ノードは、トークンを待ち続ける。
・（１１０４）トークンが受信された場合には、ノードは、トークンシーケンス番号をチェックして、最終受信以降に増分されたことを確認する。トークンが最初に受信された場合（ノード挿入直後）には、このテストは実行されない。
・（１１０５）受信されたトークン内のトークンシーケンス番号が正しければ、ノードは、トークンを下流隣接ノードへ転送して、再びトークンを待つ。
・（１１０６）トークンが受信されておらず、トークンタイマが期限切れの場合、または受信されたトークンが予想トークンシーケンス番号を有していなかった場合（これは、トークンが消失したことを意味する）には、リング回復工程が実行される。
【００９１】
仮想リングマネージャにおけるトークン処理
図１２は、トークンの受領時に仮想リングマネージャにおいて実行されるアルゴリズムを説明する。
【００９２】
・（１２００）仮想リングマネージャがちょうど挿入されたところである。仮想リングマネージャは、トークンシーケンス番号を１に設定し、３０秒の待ちトークンタイマと、１秒のトークンタイマとを開始する。トークンタイマを使用して、新規のトークンを毎秒生成する。待ちトークンタイマを使用して、リング回復をトリガする。
・（１２０１）仮想リングマネージャは、その下流隣接ノードにトークンを転送し、トークンの戻りを待つ。
・（１２０２）仮想リングマネージャは、トークンが受信されたか否かをチェックする。
・（１２０３）トークンが受信されていない場合には、仮想リングマネージャは、トークンタイマが期限切れか否かをチェックする。
・（１２０４）トークンタイマが期限切れでない場合には、仮想リングマネージャは、待ちトークンタイマは期限切れか否かをチェックする。期限切れでない場合には、仮想リングマネージャは、トークンを再び待つ。
・（１２０５）トークンが受信されておらず、待ちトークンタイマが期限切れの場合には、トークンが消失されたことを意味する。その後、仮想リングマネージャは、リング回復工程を実行する。
・（１２０６）トークンが受信された場合には、仮想リングマネージャは、トークン内のシーケンス番号をチェックする。
・（１２０７）トークンが受信されたので、仮想リングマネージャは、待ちトークンタイマをリスタートし、トークンタイマが期限切れするのを待つ。
・（１２０８）トークンタイマが期限切れになると、仮想リングマネージャは、新たなトークンを生成して、シーケンス番号を増分する。
・（１２０９）仮想リングマネージャは、その下流隣接ノードへトークンを送出し、トークンの戻りを待つ。
【００９３】
ノード挿入−ノードにおけるアルゴリズム
図１３は、ノードにおいて実行される、当該ノードを仮想リングに挿入することを考慮したアルゴリズムを説明する。
【００９４】
・（１３００）新たなノードが、仮想リングへの挿入を希望している。このノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｒｅｑｕｅｓｔ」メッセージを仮想リングマネージャへ送出する。
・（１３０１）ノードは、挿入タイマを開始して、仮想リングマネージャからの「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージを待つ。
・（１３０２）ノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信されたか否かをチェックする。
・（１３０３）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信されていない場合には、ノードは、挿入タイマが期限切れかをチェックする。期限切れでなければ、ノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージの受信を待ち続ける。
・（１３０４）Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信された場合には、ノードは挿入タイマを停止して、その隣接アドレスを更新して、その隣接ノードとのＴＣＰセッションを確立する。
・（１３０５）新規のノードが、仮想リングに現在挿入されている。
・（１３０６）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信されておらず、挿入タイマが期限切れの場合、ノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｒｅｑｕｅｓｔ」メッセージをバックアップマネージャへ送出する。
・（１３０７）ノードは、挿入タイマを再び開始する。
・（１３０８）ノードは、Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信されたか否かをチェックする。
・（１３０９）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信されていない場合には、ノードは、挿入タイマが期限切れか否かをチェックする。期限切れでなければ、ノードは、「Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージの受信を待ち続ける。
・（１３１０）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信された場合には、ノードは、挿入タイマを停止して、その隣接アドレスを更新して、その隣接ノードとのＴＣＰセッションを確立する。
・（１３１１）新規のノードが、仮想リングに現在挿入されている。
・（１３１２）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージがバックアップマネージャから受信されていない場合には、仮想リングマネージャおよびバックアップマネージャの両方が利用不可能であることを意味する。この場合、ノードをリングに挿入するための処理は失敗となる。
【００９５】
ノード除去−ノードにおけるアルゴリズム
図１４は、ノードにおいて実行される、当該ノードを仮想リングから除去することを考慮したアルゴリズムを説明する。
【００９６】
・（１４０１）新たなノードが、仮想リングからの除去を希望している。このノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｒｅｑｕｅｓｔ」メッセージを仮想リングマネージャへ送信する。
・（１４０２）除去するノードは、リング除去タイマを開始する。
・（１４０３）除去するノードは、リングマネージャからの「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージを待つ。
・（１４０４）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信されると、ノードは、そのシャットダウンを終わらせる。
・（１４０５）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信されていないと、除去するノードは、リング除去タイマをチェックする。
・（１４０６）リング除去タイマが期限切れの場合は、除去するノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｒｅｑｕｅｓｔ」メッセージをバックアップリングマネージャへ送出する。
・（１４０７）除去するノードは、リング除去タイマを開始する。
・（１４０８）除去するノードは、リングマネージャからの「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージを待つ。
・（１４０９）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージが受信されない場合には、除去するノードは、リング除去タイマをチェックする。このタイマが期限切れの場合には、除去するノードは、リングマネージャからのいずれの応答を待つことなく、そのシャットダウンを終わらせる。
【００９７】
ノード挿入／除去−隣接ノードにおけるアルゴリズム
図１５は、隣接ノードが挿入または除去されたノードにおいて実行されるアルゴリズムを示す。
【００９８】
・（１５０１）（除去されるノードからみた）隣接ノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージが仮想リングマネージャから受信されたかをチェックする。
・（１５０２）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージが受信された場合には、隣接ノードは、メッセージ内に受信された上流および下流アドレスを使用して、その隣接テーブルを更新する。
・（１５０３）隣接ノードは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージを仮想リングマネージャに送り戻す。
【００９９】
ノード挿入／除去−仮想リングマネージャにおけるアルゴリズム
図１６は、ノードが仮想リングに挿入またはそこから除去された場合に仮想リングマネージャにおいて実行されるアルゴリズムを示す。
【０１００】
・（１６０１）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｔｉｏｎ  Ｒｅｑｕｅｓｔ」メッセージが受信されたかをチェックする。
・（１６０２）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｔｉｏｎ  Ｒｅｑｕｅｓｔ」メッセージが受信された場合には、仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージを自身の下流隣接へ送出し、隣接変更タイマを開始する。
・（１６０３）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージを待つ。「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージが受信されず、変更タイマが期限切れの場合には、処理は失敗となる。
・（１６０４）仮想リングマネージャは、その下流アドレスを新規のノードのアドレスで更新する。
・（１６０５）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージを、挿入するノードへ送出する。
・（１６０６）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｒｅｑｕｅｓｔ」メッセージが受信されたかをチェックする。
・（１６０７）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージを、除去するノードの下流隣接へ送出する。
・（１６０８）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージを、除去するノードの上流隣接へ送出する。
・（１６０９）仮想リングマネージャは、隣接変更タイマを開始する。
・（１６１０）「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージが上流および下流隣接ノードから受信されると、仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージを、除去するノードへ送出する。
・（１６１１）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｌｏｓｓ  Ｉｎｄｉｃａｔｉｏｎ」メッセージが受信されたかをチェックする。
【０１０１】
図１７は、ノード挿入処理を示す。
【０１０２】
・（１７０１）ノードＧは、挿入するノードである。そのリングテーブルには、仮想リングおよびバックアップリングマネージャアドレスが含まれている。
・（１７０２）ノードＥは、仮想リングマネージャである。
・（１７０３）ノードＦは、仮想リングマネージャの下流隣接ノードである。
・（１７０４）挿入ノードＧは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｒｅｑｕｅｓｔ」メッセージを仮想リングマネージャへ送出する。
・（１７０５）仮想リングマネージャは、新規のノードＧをノードＦのすぐ前に挿入するために、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージをその下流隣接ノード（ノードＦ）へ送出する。
・（１７０６）ノードＦは、その仮想リングテーブルを更新する。
・（１７０７）ノードＦは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージで仮想リングマネージャに応答する。
・（１７０８）仮想リングマネージャは、そのリングテーブルを更新して、新規のノードＧを自身のすぐ後に挿入する。
・（１７０９）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｉｎｓｅｒｔｉｏｎ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージを新規の挿入ノードＧへ送出する。
・（１７１０）ノードＧは、その仮想リングテーブルを、２つの隣接ノードのアドレスで更新する。
【０１０３】
要求形ノード除去のフローチャート
図１８は、要求形ノード除去処理を示す。
【０１０４】
・（１８０１）ノードＢは、除去するノードであるノードＣの上流隣接ノードである。
・（１８０２）ノードＣは、除去するノードである。
・（１８０３）ノードＤは、ノードＣの下流隣接ノードである。
・（１８０４）ノードＥは、仮想リングマネージャである。
・（１８０５）除去ノードＣは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｒｅｑｕｅｓｔ」メッセージを仮想リングマネージャへ送出する。
・（１８０６）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージをノードＤ（下流隣接ノード）へ送出する。
・（１８０７）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージをノードＢ（上流隣接ノード）へ送出して、隣接変更タイマを開始する。
・（１８０８）ノードＢは、そのリングテーブルを更新する。
・（１８０９）ノードＢは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージを仮想リングマネージャへ送出する。
・（１８１０）ノードＤは、そのリングテーブルを更新する。
・（１８１１）ノードＤは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージを仮想リングマネージャへ送出する。
・（１８１２）仮想リングマネージャは、隣接変更タイマを停止して、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｒｅｍｏｖａｌ  Ｃｏｎｆｉｒｍａｔｉｏｎ」メッセージを、除去するノードＣへ送出する。
【０１０５】
非要求形ノード除去（ノード消失）のフロー
図１９は、非要求形ノード除去処理を示す。
【０１０６】
・（１９０１）ノードＢは、除去するノードであるノードＣの上流隣接ノードである。
・（１９０２）ノードＣは、除去するノードである。
・（１９０３）ノードＤは、ノードＣの下流隣接ノードである。
・（１９０４）ノードＥは、仮想リングマネージャである。
・（１９０５）上流隣接ノードＢは、ノードＣとのＴＣＰ接続の消失を検出して、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｌｏｓｓ  Ｉｎｄｉｃａｔｉｏｎ」メッセージを仮想リングマネージャへ送出する。
・（１９０６）下流隣接ノードＤは、ノードＣとのＴＣＰ接続の消失を検出して、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｌｏｓｓ  Ｉｎｄｉｃａｔｉｏｎ」メッセージを仮想リングマネージャへ送出する。
・（１９０７）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージをノードＤ（下流隣接ノード）へ送出する。
・（１９０８）仮想リングマネージャは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｃｈａｎｇｅ  Ｎｅｉｇｈｂｏｒ」メッセージをノードＢ（上流隣接ノード）へ送出して、隣接変更タイマを開始する。
・（１９０９）ノードＢは、そのリングテーブルを更新する。
・（１９１０）ノードＢは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージを仮想リングマネージャへ送出する。
・（１９１１）ノードＤは、そのリングテーブルを更新する。
・（１９１２）ノードＤは、「Ｖｉｒｔｕａｌ  Ｒｉｎｇ  Ｎｅｉｇｈｂｏｒ  Ｃｈａｎｇｅｄ」メッセージを仮想リングマネージャへ送出する。
【０１０７】
本発明の利点
１）ネットワークにおけるＴＣＰセッション数の削減
本発明によって、Ｎ個のノードを相互接続するのに、フルメッシュネットワークではＮ（Ｎ−１）／２個のセッション、および二重星型構成では２×Ｎ−３個のセッションであるのに対して、Ｎ個のＴＣＰセッションを必要とするだけである。セッションとは、２つのノード間の仮想接続であり、これらのノード間のデータ交換を可能にし、かつ、フロー制御および再送信などの送信上の問題を扱うものである。ＴＣＰセッションとは、ＴＣＰ／ＩＰプロトコル対応の２つのノード間のセッションの一例である。本発明は、ＴＣＰ／ＩＰプロトコルスタックのＴＣＰ（伝送制御プロトコル）層の最上層において実施され、世界中で最も広く使用されているプロトコルであるＴＣＰ／ＩＰプロトコル対応の任意のノードによって使用されてもよい。図１に示すように、Ｎ個のノードのフルメッシュネットワークでは、各ノードはＮ−１個の他の各ノードとＴＣＰセッションを確立しなければならない。これは、Ｎ×（Ｎ−１）／２個のＴＣＰセッションの確立を意味する。本発明によれば、各ノードは、上流隣接ノードと、下流隣接ノードという２つの他のノードとのみＴＣＰセッションを確立すればよい。これは、Ｎ個のノードの仮想リングにおける合計Ｎ個のセッションを意味する。本発明の結果生じる節減は、以下のように計算できる：
フルメッシュネットワークでは、Ｎ×（Ｎ−１）／２個のセッションであるのに対し、仮想リング構成では、Ｎ個のセッションである。この差は、Ｎ×（Ｎ−１）／２−Ｎ＝Ｎ２／２−Ｎ／２−Ｎ＝Ｎ２／２−３Ｎ／２＝Ｎ×（Ｎ−３）／２に等しい。したがって、本発明は、ネットワークにおいてＮ×（Ｎ−３）／２個のセッションを節減可能である。
【０１０８】
ノード間のセッション数を削減すると、以下の点において説明するようないくつかの他の利点がもたらされる。
【０１０９】
２）ネットワークにおける帯域幅の使用の削減
各ノードは、同一のメッセージのただ１つのコピーを受信するので、本発明は、複数の不必要なコピーを回避する。図１に記載したようなフルメッシュ接続形態においては、各ノードは、すべての他のノードと通信する。各ノードが同一の情報を他のノードへ送出する必要がある場合には、各ノードは、この情報をすべての隣接ノードへ転送することになり、これは、ネットワークにおいて交換されるメッセージ数を二重化することになる。これは、ノードがＲＩＰ（経路指定情報プロトコル）のような経路設定プロトコルを使用して経路設定情報を交換するルータである場合に典型的である。周期的に、各ルータは、その経路設定テーブルを、ネットワーク内の他のルータに対して通信または大量に送りつける。他の例は、分散型データベースが同期される必要がある場合、および分散型データベースに関与するサーバが同じレコードを交換する必要がある場合である。通常、情報の同報通信は、アプリケーション層によって管理され、情報がノード間で分散されるようになされなければならない。
【０１１０】
本発明は、各ノードが情報のただ１つのコピーを受信するように、同一の情報をすべてのノード間において交換できるようにする。ノードは仮想リングに仮想的に接続されており、情報は当該リングに沿って循環して、リングに接続された各ノードによって認識されるので、ネットワークは、ノード間で交換されるメッセージの複数のコピーで溢れることはない。
【０１１１】
３）各ノードにおけるＣＰＵ使用の削減
ＴＣＰセッションを確立および維持することは、コンピュータリソースに対してフロー制御および再送、ならびに受領確認およびキープアライブを要求するものである。本発明は、ノードが通信するのに必要なＴＣＰセッション数を削減するので、ノードにおけるデータ処理リソースの仕様を削減する。
【０１１２】
４）各ノード内のメモリ消費の削減
各ノードにおいて、ＴＣＰセッションを維持するには、これらのセッションのコンテキストを維持する必要があり、この維持は、最後に送出されたセグメントのシーケンス番号または次に送信される受領確認のシーケンス番号などの情報と共に行われる必要がある。この情報の記憶は、メモリを消耗する。ＴＣＰセッションの数を削減すれば、ノードにおけるメモリ消費を削減する結果となる。
【０１１３】
本発明を好ましい実施形態を参照して特に図示および説明してきたが、形式および詳細の様々な変更が本発明の精神および範囲から逸脱せずに本実施形態において行われてもよいことは当然である。
【図面の簡単な説明】
【０１１４】
【図１】「フルメッシュネットワーク」の一例を示す。
【図２】「星型ネットワーク」の一例を示す。
【図３】本発明に係る「バーチャルリングネットワーク」の一例を示す。
【図４】本発明に係るバーチャルリング上のノードからノードへトークンがどのように転送されるかを示す。
【図５】本発明のトークンメッセージを示す。
【図６】本発明に係る仮想リングへ新規ノードがどのように挿入されるかを示す。
【図７】本発明に係る新規ノード挿入の結果を示す。
【図８】本発明に係るノードの要求形除去を示す。
【図９】本発明に係るノードの消失を示す。
【図１０】本発明に係るノードの消失後の再構成の結果を示す。
【図１１】本発明に係る、ノードがトークンを受信後にこのノードによって実行されるアルゴリズムを説明する。
【図１２】本発明に係るトークンの受領時に仮想リングマネージャにおいて実行されるアルゴリズムを説明する。
【図１３】本発明に係る、ノードにおいて実行される、このノードを仮想リングに挿入することを考慮したアルゴリズムを説明する。
【図１４】本発明に係る、ノードにおいて実行される、このノードを仮想リングから除去することを考慮したアルゴリズムを説明する。
【図１５】本発明に係る、隣接ノードが挿入または除去された場合にノードにおいて実行されるアルゴリズムを示す。
【図１６】本発明に係る、ノードが仮想リングに挿入またはそこから除去された場合に仮想リングマネージャにおいて実行されるアルゴリズムを示す。
【図１７】本発明に係るノード挿入処理を示す。
【図１８】本発明に係る要求形ノード除去処理を示す。
【図１９】本発明に係る非要求形ノード除去処理を示す。
【図１】
2007515117.tif 000014
【図２】
2007515117.tif 000015
【図３】
2007515117.tif 000016
【図４】
2007515117.tif 000017
【図５】
2007515117.tif 000018
【図６】
2007515117.tif 000019
【図７】
2007515117.tif 000020
【図８】
2007515117.tif 000021
【図９】
2007515117.tif 000022
【図１０】
2007515117.tif 000023
【図１１】
2007515117.tif 000024
【図１２】
2007515117.tif 000025
【図１３】
2007515117.tif 000026
【図１４】
2007515117.tif 000027
【図１５】
2007515117.tif 000028
【図１６】
2007515117.tif 000029
【図１７】
2007515117.tif 000030
【図１８】
2007515117.tif 000031
【図１９】
2007515117.tif 000032
【国際調査報告】
2007515117.tif 000033
2007515117.tif 000034
2007515117.tif 000035