JP2011523269A - ローカルピアグループ（ｌｐｇ）間ルーティング方法 - Google Patents

Abstract

複数のローカルピアグループ（ＬＰＧ）間でデータをルーティングするオンデマンドな方法。各ＬＰＧは、複数の移動ノードを含む。方法は、ソースノードからルート要求メッセージを伝送することと、ルート要求メッセージをネイティブ境界ノードへ中継することと、ルート要求メッセージを外部境界ノードへ転送することと、宛先ノードが外部境界ノードのＬＰＧ内であるかどうかを判定することと、もし宛先ノードが上記ＬＰＧ内でないならば、ルート要求メッセージを別の境界ノードへ中継することと、もし宛先ノードが上記ＬＰＧ内であるならば、ルート要求メッセージを宛先ノードへ中継することと、宛先ノードにおいてルート要求メッセージを受信することと、ルーティング応答をソースノードへ伝送することと、ルート要求によって発見された経路を通じてルーティング応答をソースノードへ中継することと、ソースノードにおいてルーティング応答を受信することと、データを伝送することとを含む。

Description

本出願は、「Method and Communication Device for Routing Unicast and Multicast Messages in an Ad-hoc Wireless Network（アドホック無線ネットワークにおいてユニキャストメッセージ及びマルチキャストメッセージをルーティングする方法及び通信デバイス）」と題された、２００６年１０月２３日出願の共同所有の米国同時係属特許出願第１１／５８５，０４７号（「’０４７出願」）に関連している。

本発明は、移動環境における通信ネットワークに関する。より詳細には、本発明は、複数のローカルピアグループ間でメッセージをルーティングするための方法に関する。

’０４７出願は、１つの移動車両をグループヘッダとして選択すること、そのグループヘッダを使用してローカルピアグループ（ＬＰＧ）を維持すること、及びローカルルーティング情報を生成することによって移動車両のグループをローカルピアグループに編成するための方法を記載している。移動車両は、シングルホップ伝送又はマルチホップ伝送のいずれかを使用してデータをルーティングするように適応される。‘０４７出願は、各ノード又は各移動車両内のローカルルーティングテーブルをもとにして具体的なＬＰＧ内ルートが決定されることを記載している。ローカルルーティングテーブルは、ノードによってＬＰＧ内の他のノードから受信される情報をもとにして作成される。ルーティング経路は、絶えず更新される。ＬＰＧのサイズは、ＬＰＧが管理サイズであることを保証するためにプリセットされる。サイズは、ホップカウント限界に基づいてプリセットされる。

ネットワークは、複数のＬＰＧを含むと考えられ、各ＬＰＧは、幾つかの移動車両を含む。メッセージは、例えばＬＰＧ内通信のようにＬＰＧ内で伝送される。しかしながら、例えばＬＰＧ間通信のように複数のＬＰＧの間での伝送を必要とするメッセージもある。道路障害物の緊急警告、交差点との連係、隠れた私道に関する警告、車線変更支援又は車線合流支援を非限定的に含むこれらのメッセージは、ＬＰＧ間で効率良く伝送可能でなければならない。

性能要件は、衝突回避などの様々なＶＳＣ応用形態を支援するために、待ち時間が短いこと（約１００ミリ秒）及びスループットを維持すること（別の言い方をすると、近くにある車両が警告メッセージの受信に成功する割合）を含む。

したがって、複数のローカルピアグループ間で伝送するための方法が必要とされる。

ゆえに、複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法が開示される。各ローカルピアグループ（Local Peer Group）は、複数の移動ノードを含む。本方法は、ソースノードからルート要求メッセージを伝送するステップであって、ルート要求メッセージは、宛先ノード、ソースノードのＬＰＧ識別子、及び前ＬＰＧ識別子を少なくとも含む、ステップと、ルーティング要求メッセージを宛先ノードへ中継するステップと、ルーティング応答を発行するステップと、応答をソースへルーティングするステップと、ルート要求メッセージをネイティブ境界ノードへ中継するステップと、ソースノードにおいてルーティング応答を受信するステップと、ルーティング応答の受信を受けてデータを伝送するステップと、を含む。データは、初めは、ルーティング応答を伝送したノードを使用して中継されるが、実際のルートは、更新後のローカルルーティングテーブルをもとにして決定される。

ルート要求メッセージは、ルート要求メッセージを外部境界ノードへ転送すること、宛先ノードが外部境界ノードのＬＰＧ内であるかどうかを判定すること、宛先ノードが上記ＬＰＧ内でないならば、ルート要求メッセージを別の境界ノードへ中継すること、及び宛先ノードが上記ＬＰＧ内であるならば、ルート要求メッセージを宛先ノードへ中継することによって、宛先ノードへ中継される。

宛先ノードは、ルート要求の受信を受けて、ルーティング応答をソースノードへ伝送する。ルーティング応答は、ルート要求を通じて発見された経路を通じてソースノードへ中継される。

オンデマンドな方法は、更に、ルート要求メッセージを受信するノードが宛先ノード又は宛先ノードのＬＰＧ内の境界ノードであるかどうかを判定するステップを含む。

オンデマンドな方法は、更に、宛先ノードがルート要求メッセージを受信しているノードと同じＬＰＧ内であるかどうかを判定するステップと、ルート要求メッセージを受信しているノードが入口境界ノードであるかどうかを判定するステップと、ソースノードの識別子によって宛先リストを更新するステップとを含む。

オンデマンドな方法は、更に、ルート要求メッセージを受信しているノードが中継ノードであるかどうかを判定することを含む。

オンデマンドな方法は、更に、ルート要求メッセージを受信しているノードが出口境界ノードであるかどうかを判定するステップと、ルート要求メッセージ内の前ＬＰＧ識別子を出口境界ノードのＬＰＧのＬＰＧ識別子で置き換えるステップとを含む。

オンデマンドな方法は、更に、ソースノードがルーティング応答を受信しているノードと同じＬＰＧ内であるかどうかを判定するステップと、ルーティング応答を受信しているノードが入口境界ノードであるかどうかを判定するステップと、宛先ノードの識別子によって宛先リストを更新するステップとを含む。

オンデマンドな方法は、更に、ルーティング応答を受信しているノードが中継ノードであるかどうかを判定するステップを含む。

オンデマンドな方法は、更に、ルーティング応答を受信しているノードが出口境界ノードであるかどうかを判定するステップと、ルーティング応答内の次ＬＰＧ識別子を出口境界ノードのＬＰＧのＬＰＧ識別子で置き換えるステップとを含む。

オンデマンドな方法は、更に、宛先ノードによってデータが受信されるまでソースノードから宛先ノードへのルートを維持するステップを含む。

ルートを維持するステップは、ノードがＬＰＧを変更したかどうかを検出するサブステップと、ノードがＬＰＧを変更したという通知をＬＰＧ内の全てのノードへ伝送するサブステップと、変更を検出されたノードが境界ノードであるかどうかを判定するサブステップと、ＬＰＧを変更したノードの識別子を義務外部宛先としてルーティングテーブルに追加するサブステップとを含む。

ルーティング要求メッセージは、宛先ノード識別子及び前ノード識別子を含む。

また、複数のローカルピアグループ間での通信のために境界ノードを選択するための方
法が開示される。方法は、既定のノードを発信元とする第１の制御パケットを受信するステップと、第１の制御パケットが同じローカルピアグループ内のグループヘッダからであるかどうかを判定するステップと、もし第１の制御パケットが外部ローカルピアグループを発信元とするならば、パケットをグループヘッダへ伝送することによって境界ノードへの立候補を宣言するステップと、少なくとも１つの候補からの伝送されたパケットをグループヘッダにおいて受信するステップと、受信されたパケットに基づいて候補のリストを作成するステップと、候補のリストから１つの候補を境界ノードとして選択するステップと、選択された境界ノードの識別子を含むデータパケットを伝送するステップとを含む。既定のノードは、グループヘッダである。

候補のリストは、プリセット期間にわたって有効である。期間は、Ｔｉｍｅ−ｔｏ−Ｌｉｖｅ値である。Ｔｉｍｅ−ｔｏ−Ｌｉｖｅ値は、第１の制御パケットの伝送期間の倍数である。方法は、更に、プリセット期間が満了したかどうかを判定するステップと、もしプリセット期間が満了したならば候補を削除するステップとを含む。方法は、更に、同じ候補の識別子を含むデータパケットをグループヘッダが受信したときにＴｉｍｅ−ｔｏ−Ｌｉｖｅ値をリフレッシュするステップを含む。

境界ノードは、各候補についての、グループヘッダからのホップカウントに基づいて選択される。

本方法は、更に、選択された境界ノードの識別子を含むデータパケットを受信するステップと、選択された境界ノードの識別子を受信ノードの識別子と比較するステップと、比較に基づいて受信ノードのステータスを境界ノードに変更するステップと、を含む。

本方法は、更に、ステータスを境界ノードに変更した後に定期的に第２の制御パケットを伝送するステップを含む。

本方法は、グループヘッダから上記境界ノードと反対の相対方向にある第２の境界ノードを選択するステップを含む。

本発明のこれらの及びその他の特徴、利益、及び利点は、以下の図面を参照することによって明らかになる。なお、図面を通じて、類似の参照符号は類似の構造を指している。

発明の一実施形態にしたがった、ＬＰＧ間通信に適応され尚且つ互いの近くにある複数のローカルピアグループを示している。 典型的なハートビートメッセージを示している。 典型的なメンバシップレポートメッセージを示している。 発明の一実施形態にしたがった、境界ノード（ＢＮ）を選択するための方法の流れ図を示している。 発明の一実施形態にしたがった、境界ノード（ＢＮ）を選択するための方法の流れ図を示している。 発明の一実施形態にしたがった、ＢＮの選択のための有限状態図を示している。 発明の一実施形態にしたがった、ルーティングテーブルを作成してルーティングテーブルのエントリを更新する方法の流れ図を示している。 別のローカルピアグループ内のノードから受信されたデータパケットを処理する方法の流れ図を示している。 発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。 発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。 発明の一実施形態にしたがった、オンデマンドなルート発見方法の流れ図を示している。 発明の一実施形態にしたがった、移動度検出方法の流れ図を示している。 発明の一実施形態にしたがった、ローカルピアグループからの離脱ノードが検出されたことをノードに知らせる方法の流れ図を示している。 発明の一実施形態にしたがった、義務外部宛先リストを広める方法の流れ図を示している。

本発明にしたがうと、ノード又は移動デバイスは、管理可能なグループに編成される。これらのグループは、ノード間でのデータの伝送を調整するために使用される。グループは、隣接するノードの相対位置に基づいて、又は固定位置に基づいて構築される。このグループ分けすなわちローカルピアグループ（「ＬＰＧ」）は、１つのＬＰＧ１１５内で及び複数のＬＰＧ間で電波信号をルーティングするための基礎である。電波信号は、車両の安全性の応用及び情報の応用を含む。

図１は、２つのＬＰＧ（一般に１として表示される）、すなわちＬＰＧ Ａ（１_a）及びＬＰＧ Ｂ（１_b）を示している。ＬＰＧ Ａ１_aは、３つの個々のノードを含む（ノードは、一般に「１０」として表示される）。ＬＰＧ１内の１つのノードが、グループのリーダになるべく選択される。リーダは、ＧＨと称され、ＬＰＧ Ａ１_aの場合はＧＨ_aとして表わされる（ＧＨは、一般に「２５」として表示される）。ＧＨ２５は、ＬＰＧ１を管理する。また、ＧＨ２５は、特殊なノードを境界ノード（ＢＮ：一般に「２０」として表示される）にするべく選択する。ＢＮ２０は、複数のＬＰＧ１間でデータを中継する役割を担うノード１０である。ＢＮ２０は、複数のＬＰＧ１の電波有効範囲が重なるエリア内に物理的に位置している。ＢＮ２０は、オンデマンドなルート検索及び維持管理の役割を担う。ＢＮ２０は、また、ＬＰＧ間通信のための有効ルートを維持する役割も担う。ＢＮ２０は、そのメンバシップレポート（ＭＲ）３００の一部として特定の外部宛先リストを他のノード１０に報告する。特定の外部宛先リストは、義務（obligated）外部宛先を含む。義務外部宛先は、通信経路がアクティブで尚且つ外部宛先の次ホップＬＰＧがＢＮの位置しているＬＰＧ１であるような宛先を含む。また、ＢＮ２０は、複数のＬＰＧ１からハートビートメッセージ２００及びＭＲ３００を横聞き（overhear）するので、ＢＮ２０は、離脱ノード又は移動ノードの通知も支援する。

ＬＰＧ１のサイズは、所定のＬＰＧ１内のノード１０が多くなりすぎないように制御される。より詳細には、ＧＨ２５は、特定のフォーマットを有する電波信号をブロードキャストし、ＧＨ２５の範囲内の他のノード１０は、その電波信号を受信する能力を有する。電波信号は、ホップカウント、又は信号が有効であるＴｉｍｅ−ｔｏ−Ｌｉｖｅ（ＴＴＬ）値を含む。すなわち、もし信号が、指定された値を上回るホップカウントにわたって中継されるならば、ノードは、ＬＰＧ１に参加しない。この電波信号は、ハートビートメッセージ２００と呼ばれる。ＧＨの形成、維持管理、及び選択、並びにＬＰＧ１の制御は、参照によって本明細書に組み込まれる’０４７出願に記載されている。

上記のように、２つの異なるＬＰＧ１からの電波信号がヒアリング可能な領域がある。この領域では、ノードは、２つの異なるハートビートメッセージ２００を受信するが、ノード１０が参加できるのは、１つのＬＰＧ１のみである。この重複エリアは、ＬＰＧ交差エリア（ＬＩＡ）と呼ばれる。ノード１０は、最も優先度の高いＬＰＧ１に参加する。一実施形態では、優先度は、ＬＰＧ識別子に基づいて判定される。例えば、図１では、２つのＬＰＧ１と２つのＧＨ２５がある。

ＬＩＡ内のノード１０は、ＢＮ２０の候補であることができる。しかしながら、ＬＩＡ内にノード１０がある保証はない。したがって、エッジハートビートが使用される。エッジハートビートは、有効ＨＣ限界よりも１ホップだけ大きいＨＣを伴うハートビートメッセージである。ノード１０は、エッジハートビートを受信した後はＬＰＧ１に参加することができない。ハートビートメッセージ２００と異なり、エッジハートビートは中継されない。

図２は、発明にしたがったハートビートメッセージ２００の一例を示している。ＧＨ２５は、ハートビートメッセージ２００を定期的に送出し、ＬＰＧを識別するとともにＬＰＧに関する情報を提供する。この期間は、固定間隔（Ｔ）である。間隔（Ｔ）の値は、設計上又は動作上の必要性に基づいて選択可能である。ＧＨ２５は、また、ＬＰＧ内の全てのノードのリストを維持する。このリストは、ノードがＬＰＧにいつ入ったか又はＧＨ２５がノード１０からいつステータス更新を受信したかについてのタイムスタンプを含む。リストは、ＬＰＧに対する様々な管理機能及び制御機能のために使用される。例えば、リストは、グループサイズの追跡、マルチキャストルーティングテーブルの作成及び更新、並びにヘッダ解決に使用することができる。また、このリストは、ＬＰＧ１内の他の全てのノードに定期的にブロードキャストされる。ＬＰＧハートビートメッセージ２００は、ＧＨ２５の電波周辺内の全てのノードにブロードキャストされる。

ハートビートメッセージ２００は、ＬＰＧの識別子、ＧＨ識別、シーケンス番号、及び例えば完全なグループリストを伴うハートビート、漸増性のグループリストを伴うハートビート、又はグループリストを伴わないハートビートなどのハートビートメッセージのタイプを含む。一実施形態では、ハートビートメッセージは、全てのメッセージ内に完全なグループリストを含む。完全なグループリストの使用は、ルーティングを制御するため及びグループメンバの正しいリストを維持するための最も正確な方法であるが、完全なグループを伴うハートビートメッセージには、大量の帯域幅が必要である。別の実施形態では、（ｎ−１）個おきの各ハートビートメッセージ２００が完全なグループリストを含む。例えば、２つおきの各ハートビートが完全なグループリストを含む。ＴｏＨｂ（type of heartbeat）は、ハートビートメッセージ２００のタイプを示す。ハートビートメッセージのタイプは、ＬＰＧ１のトポロジ変化速度と、ハートビートのブロードキャストの頻度とによって影響される。ＬＰＧ１のトポロジ変化速度が増すにつれて、全てのハートビートメッセージ２００に完全なグループリストが含まれている必要性が高まる。

ハートビートメッセージ２００は、ＧＨからのホップカウント（ＨＣ）を含む。最初、ＨＣは、例えば１などの既定の値に設定される。ハートビートメッセージ２００がノードによって中継されるたびに、中継ノードは、ＨＣの値を１だけ増加させる、すなわちＨＣ＝ＨＣ＋１とする。ＨＣ値は、ＬＰＧサイズを制限するため、ハートビートメッセージ２００内の情報の古さを示すため、及び制御パケットのルーティングを制御して上記のようにオーバーヘッドを低減させるために使用することができる。ＨＣが最大ホップカウントまで増分されると、制御パケットは、中継されなくなる。

最大ホップカウント、ＨＣ、及びＳｅｑ．Ｎｏ．を利用することによって、ＬＰＧ１内で制御パケットが無限に重複する事態が阻止される。ホップカウントは、中継戦略にも使用することができる。ノードは、ハートビートメッセージを転送するときに、そのハートビートメッセージ２００を誰がリレーしたのかを次ホップノードが知ることができるように、自身のＩＤ情報をメッセージ内に含ませる。

上記のように、ハートビートメッセージ２００は、グループリストも含むことができる。グループリストは、ＬＰＧ１内のメンバの数、各数のＩＰアドレス、ＧＨからのホップ
カウント、ＢＮ２０としてのステータス、ＢＮの有効期限、及び分類などの、ＬＰＧ１のメンバに関する情報を含むことができる。

分類は、例えばアップリンク、ダウンリンク、及びピアのような、ＧＨからの相対方向に言及したコードであってもよい。ピア分類は、ノードがＧＨ２５から同じ無線有効範囲内にあることを示す、すなわち、全てのピアノードは、ＧＨからのホップカウントが同じである。アップストリームノードは、ハートビートによって決定される。ダウンストリームノードは、後述されるメンバシップレポート（ＭＲ）３００に基づいて決定される。アップストリーム伝送は、ＧＨ２５に向かう通信を表し、ダウンストリーム伝送は、ＧＨ２５から離れる通信を表す。この分類は、相対的な表現である。各ノードは、自身に隣接するノードを３つの異なるクラスに分類することができる。もし別のノードのメンバシップレポートが、自身のホップカウント（ＨＣ）よりも１だけ小さいＨＣを有するならば、ノードは、アップストリームノードである。もし別のノードのＨＣが、自身のＨＣと同じであるならば、ノードは、ピアである。もし別のノードのＨＣが、自身のＨＣよりも１だけ大きいならば、ノードは、ダウンストリームノードである。分類は、ＢＮ候補のグループから、ＧＨ２５の各側について１つずつＢＮ２０を選択するために使用される。

図３は、メンバシップレポート（ＭＲ）３００の一例を示している。ＭＲ３００は、ＧＨ２５ではない他のノードによってブロードキャストされる制御パケットであり、その受け手はＧＨ２５である。ＭＲ３００は、ハートビートメッセージ２００に応答して生成される。ＭＲ３００は、メンバシップリスト、ダウンストリームノード識別、及びダウンストリームノードのための次ホップなどの、収集可能なルーティング情報を含む。ＭＲ３００は、ハートビートメッセージ２００と同じ情報を幾つか、すなわちＧＩＤ及びグループヘッダＩＤを含む。ＭＲ３００は、また、ＭＲ Ｓｅｑ．Ｎｏ．も含む。ＭＲ Ｓｅｑ．Ｎｏ．は、ハートビートメッセージ２００のＳｅｑ．Ｎｏ．と同様であり、ＭＲの順番を維持するために使用される。ＭＲ Ｓｅｑ．Ｎｏ．は、１つの特定のノードに対するＭＲの順番である。通常、ＭＲ Ｓｅｑ．Ｎｏ．は、ＭＲ３００をトリガしたハートビートメッセージ２００のＳｅｑ．Ｎｏ．と同じ値を有する。

発信元ノードすなわちＭＲ３００を生成したノードのノードＩＤも、ＭＲ３００に含まれる。

ＭＲ３００は、次ホップ中継ＩＤも含む。次ホップ中継ＩＤは、ＧＨ２５に向かうＭＲ３００のための中継命令である。次ホップ情報は、受信されたハートビートメッセージ２００をもとにして直接決定される。ノード１０は、新たなすなわち新着のハートビートメッセージ２００を受信すると、いかなるパケット処理よりも前に、ＩＰ層及びＭＡＣ層をもとにして前中継ノードの識別を回復させる。前中継ノードの識別は、メモリに格納されており、ＭＲ３００のための次ホップ中継ＩＤとして使用される。ノード１０は、ハートビートメッセージ２００を転送するときに、そのＩＤをパケット内に含ませる。受信する次ホップノードは、新たなすなわち新着のハートビートメッセージ２００を受信すると、このＩＤを、ＧＨ２５に到達するための次ホップ中継ＩＤとして格納する。新たなすなわち新着のハートビートメッセージ２００は、最低のＨＣを伴った、より新しいシーケンス番号を有する。

ＭＲ３００は、また、「ＭＲのタイプの指標」（Type of MR indicator, ＴｏＭＲ）も含む。ＭＲ３００には、２つのタイプ、すなわち単一メンバのレポートと、統合された複数メンバのレポートとがある。単一メンバのＭＲは、発信元ノードからのＭＲ３００のみを含む。統合された複数メンバのレポートは、２つ以上のノード１０のＭＲ３００を含む。統合されたレポートは、オーバーヘッド、及び制御パケットに必要な帯域幅を低減させるために使用することができる。複数のＭＲを含む１つのＭＲ３００が送信される。

また、ＭＲ３００は、ＧＨからのホップカウント（ＨＣ_GH）を含むことができる。（ＨＣ_GH）は、ＧＨからＭＲ３００の発信元ノードまでのＨＣ値である。ＭＲ３００は、報告ノードのための使用可能チャネルリストを含む。また、ＭＲ３００は、マルチキャストメッセージを中継することに対するそのステータス又は有効性、すなわち転送ノードステータスを含む。ＭＲは、また、ＢＮ２０の候補指名を含む、すなわちノード１０は、自身がＢＮ２０の候補であることを宣言してＧＨ２５に通知する。ＭＲは、もし可能な場合は、隣接ＬＰＧリスト及びアクティブＬＰＧ間ノードリストを含む。

図４及び図５は、発明の一実施形態にしたがった、ＢＮを選択するための方法を示している。図４は、ＧＨ２５ではない全てのノードについての機能ブロックを示している。図５は、ＧＨ２５であるノード１０の機能ブロックを示している。

ノード１０は、ハートビートメッセージ２００又はエッジハートビートのいずれかである外部ハートビートをヒアリングすると、ＢＮ候補になる。外部ハートビートは、同じＬＰＧ１からのノード１０によって生成されたのではないメッセージ又はパケットである。選択されたＢＮ２０のみが、エッジハートビートをブロードキャストする。もしＬＰＧのエッジにＢＮ２０がある場合は、ノード１０は、エッジハートビートをブロードキャストする。ＢＮ２０は、ハートビートメッセージのホップカウント限界にある場合にＬＰＧ１のエッジにある。エッジハートビートは、ハートビートメッセージのホップカウントに対する追加のホップでブロードキャストされ、隣接するＬＰＧが別のＬＰＧ１の存在に気づくことを可能にする。外部ノードは、エッジハートビートを受けると、ＬＰＧ１に参加しない。エッジハートビートは、転送されない。

機能ブロック４００において、非ＧＨノードはアイドル状態にある。説明のために、非ＧＨノードは、一般的ノード（ＧＮ：General Node）として言及される。ブロック４０５では、ハートビートメッセージ２００が到着する。ハートビートメッセージ２００は、ＬＰＧの識別子を含む。ＧＮは、パケットフォーマットに基づいて、パケットがハートビートメッセージ２００であるかどうかを判定する。ブロック４１０では、ＧＮは、ハートビートメッセージ２００が例えば別のＬＰＧ１からのハートビートメッセージ２００のような外部ＨＢであるかどうかを判定する。ＧＮは、ハートビートメッセージ２００に含まれるＬＰＧ識別子を、ＧＮが入っているＬＰＧの識別子と比較する。もしこれらの識別子が同じでないならば、ブロック４１５において、ＧＮは、自身をＢＮ候補として宣言する。ＧＮは、そのステータスを「ＢＮ候補」に変更する。ＧＨは、ＭＲ３００を使用して、ＢＮへの立候補をＧＨ２５に通知する。ブロック４２０において、ＧＮは、次のＭＲサイクル中にＧＨへＭＲ３００をブロードキャストする。ＭＲは、例えばＢＮへの立候補などの、ノードステータスのためのフィールドを含む。その後、ＧＮは、ブロック４００のアイドル状態に戻り、ＢＮ２０の決定のために、次のハートビートメッセージ２００を待つ。

もしブロック４１０において、ＧＮがＬＰＧ識別子を同じだと判定するならば、方法は、機能ブロック４２５に進む。ブロック４２５では、ＧＮは、ハートビートメッセージに含まれる任意のＢＮ情報を抽出する。ＢＮ情報は、選択されたＢＮのノード識別子と、その選択されたＢＮに対応する任意の有効期間（Ｔｉｍｅ−ｔｏ−Ｌｉｖｅ）値とを含む。有効期間値は、選択されたＢＮが境界ノードとして機能する期間を表わす。有効期間は、ハートビートサイクルで表わされる。

ブロック４３０では、ＧＮは、自身が選択されたＢＮであるかどうかを判定する。ＧＮは、ハートビートメッセージ２００に含まれる選択されたＢＮの識別子を、自身のノード識別子と比較する。もしこれらの識別子が同じならば、ブロック４３５において、ＧＮは、自身をＬＰＧのＢＮ２０であると宣言する。ＧＮは、そのステータスをＢＮ候補からＢ
Ｎ２０に変更する。ＧＮは、次のＭＲサイクルで、自身がＢＮ２０であることをＬＰＧの全てのメンバに通知する。ＭＲ３００は、新しいステータスを含む。

その後、ブロック４４０では、ＧＮ（今ではＢＮ２０）は、ノード１０がハートビートメッセージ２００を転送する必要があるかどうかを判定する。より詳細には、ＢＮ２０は、ノード１０がハートビートメッセージ２００のためのホップカウント限界に位置するかどうかを判定する。この判定は、ハートビートメッセージ２００に含まれるＧＨへのホップカウントと、ハートビートメッセージ２００のための最大ホップカウントとに基づく。ハートビートメッセージ２００が転送されるたびに、ＧＨへのホップカウントは、１だけ増分される。ＧＨへのホップカウントは、最大ホップカウントと比較される。もしＧＨへのホップカウントが、最大ホップカウントに等しいならば、ハートビートメッセージ２００は、転送されない、すなわち中継されない。その代わり、ブロック４５０において、ＢＮ２０は、エッジハートビートをブロードキャストする。エッジハートビートのフォーマットは、ハートビートメッセージ２００と同じであり、唯一の違いは、どのエッジハートビート内のＨＣも、ハートビートメッセージ２００が持つことのできる最大ホップカウントよりも１だけ大きいことである。ＢＮ２０は、次いで、ブロック４００のアイドル状態に戻る。

もしＧＨへのホップカウントが、最大ホップカウントよりも小さいならば、ブロック４４５において、ハートビートメッセージ２００は転送される、すなわち中継される。

もしブロック４３０において、選択されたＢＮ２０の識別子がＧＮの識別子と一致しないならば、プロセスは、ブロック４４０に移動し、ＧＮは、通常ハートビートメッセージ２００中継機能を実施する。ブロック４４０において、ＧＮは、ノード１０がハートビートメッセージ２００を転送する必要があるかどうかを判定する。ＧＨへのホップカウントが、最大ホップカウントと比較される。もしＧＨへのホップカウントが、最大ホップカウントに等しいならば、ハートビートメッセージ２００は、転送されない、すなわち中継されない。ＢＮ２０は、次いで、ブロック４００のアイドル状態に戻る。もしＧＨへのホップカウントが、最大ホップカウントよりも小さいならば、ブロック４４５において、ハートビートメッセージ２００は転送される、すなわち中継される。ＧＨへのホップカウントは、１だけ増分される。

次に、ＧＨ２５についてのＢＮ選択プロセスが説明される。ブロック４００において、ＧＨ２５ノードはアイドル状態にある。ブロック４０５では、ハートビートメッセージ２００が到着する。ハートビートメッセージ２００は、ＬＰＧの識別子を含む。ＧＨ２５は、パケットフォーマットに基づいて、パケットがハートビートメッセージ２００であるかどうかを判定する。ブロック４１０では、ＧＨ２５は、ハートビートメッセージ２００が例えば別のＬＰＧ１からのハートビートメッセージ２００のような外部ＨＢであるかどうかを判定する。ＧＨ２５は、ハートビートメッセージ２００に含まれるＬＰＧ識別子を、ＧＨ２５が制御しているＬＰＧの識別子と比較する。もしこれらの識別子が同じでないならば、ＧＨ２５は、ブロック５００において、自身をＢＮ候補として宣言する。ＧＨは、ハートビートがエッジハートビート又はハートメッセージ２００のいずれであるかに関係なく自身を候補として宣言する。ＧＨ２５は、そのステータスを「ＢＮ候補」に変更する。もしハートビートメッセージ２００に含まれるＬＰＧ識別子が、ＧＨ自身のＬＰＧ識別子と同じであるならば、ブロック５０５において、ハートビートメッセージ２００は、ＢＮ選択を目的として無視される。

もしＭＲ３００が到着する場合は、プロセスは、ブロック５１０から開始する。ブロック５１５において、ＧＨ２５は、ＭＲ３００からＢＮ候補情報を抽出する。ＧＨ２５は、ＢＮ候補について、ＭＲ３００のステータスフィールドを調べる。もしステータスフィー
ルドが、ノード１０がＢＮ候補であることを示すならば、ブロック５２０において、ＧＨ２５は、そのノード（ＧＮ）の識別子を候補リストに記録する。ＧＨ２５は、可能性のある全ての候補の候補リストを維持する。Ｇ２５は、このリストを使用して、少なくとも１つのＢＮ２０を選択する。

ブロック５２５において、ＧＨ２５は、既存のＢＮ２５及びＢＮ候補について、有効期間（ＴＴＬ）値を調整及びリフレッシュする。もしＧＨ２５が、ＢＮへの立候補を伴わないＭＲ３００をＢＮ２０から受信する場合は、ＧＨ２５は、ＢＮ候補のなかから新しいＢＮ２０を選ぶことによって、ＢＮ２０を直ちに置き換える。もしＧＨ２５が、ＢＮへの立候補を伴うＭＲ３００をＢＮ２０から受信する場合は、ＧＨ２５は、ＴＴＬをリセットする。もしＧＨ２５が、ハートビート間隔内にＭＲ３００を受信しない場合は、ＧＨ２５は、ＴＴＬ値を減らす。ＴＴＬ値が０になると、ＧＨ２５は、ＢＮ２０を再選する。その後、ＧＨ２５は、ブロック４００のアイドル状態になる。

上述のように、ＧＨ２５は、ハートビートメッセージ２００を定期的にブロードキャストする。この期間は、ハートビート間隔として知られる。ＧＨ２５内のタイマは、ハートビート間隔のタイミングを追跡記録する。ハートビート間隔の時間が満了すると、ブロック５３０において、タイマは、ハートビートメッセージ２００の生成をトリガする。ハートビートメッセージ２００のブロードキャストに先立って、ＧＨ２５は、ＢＮ候補リストからＢＮ２０を選択する。一実施形態では、選択基準は、ＧＨからのホップの数である。ＧＨ２５は、ＧＨからのホップカウントの数が最大であるノード１０（ＧＮ）を選択する。ＢＮ候補リストは、その場合、ホップカウント情報を含む。

別の実施形態では、選択基準は、ノード１０がＬＰＧ１のメンバになっている期間である。この実施形態では、ＧＨ２５は、各ノード１０について持続時間の履歴を維持している。持続時間の履歴は、ハートビートサイクルの数を単位として測られる。ＧＨ２５は、ＢＮ候補リストから、最も長い関係を持つノード１０をＢＮ２０として選択する。

別の実施形態では、選択基準は、ＢＮ候補が所定の時間内に受信した外部ハートビートの数である。この実施形態では、ノード１０（ＧＮ）は、外部ハートビートのシーケンス番号、及び外部ハートビートのＬＰＧ識別子を追跡する。ＧＨ２５に向けてブロードキャストされるＭＲ３００は、ＢＮ候補としてのステータス、オーバヒアリングされた外部ハートビートの数、外部ハートビートに対応する識別子、及び各外部ハートビートのシーケンス番号を含む。ＧＨ２５は、この情報をＭＲ３００から抽出し、ＢＮ候補リストに追加する。ＧＨ２５は、同じシーケンス番号を有する外部ハートビートメッセージ２００を最多数オーバヒアリングしているノード１０をＢＮ２０として選択する。

別の実施形態では、選択基準は、ＧＨ２５に対するＢＮ候補の相対移動度である。この実施形態では、ノードは、それらの平均速さを監視している。平均速さは、外部の速度測定装置又は速さ測定装置からの入力に基づいて決定することができる。速さ情報は、ＭＲ３００に追加され、ＧＨ２５へ発せられる。ＧＨは、各ＢＮ候補の平均速さを自身の平均速さと比較する。平均速さの差が小さいほど、ＢＮ候補としての優先度が高くなる。

別の実施形態では、ＢＮ候補リストから、ＧＨ２５からの相対方向ごとに１つずつ、計２つのＢＮ２０が選択される。ＢＮ候補の相対方向は、例えばアップストリーム又はダウンストリームなどのノードの分類に基づいて決定される。

（１つ又は２つ以上の）ＢＮ２０が選択された後は、ハートビートメッセージ２００にＢＮ情報が付加される。ブロック５４０では、ＧＨ２５は、ハートビートメッセージ２００をブロードキャストする。ハートビートメッセージ２００がブロードキャストされた後
、ＧＨ２５は、ＢＮ候補リスト内の全てのＢＮ候補について、ＴＴＬ値を減少させる。ＴＴＬ値は、１だけ減らされる。ＢＮ２０がＧＨ２５に報告を行うたびに、すなわち、ステータスをＢＮ２０としてＭＲ３００を送信するたびに、ＴＴＬは、例えばＴハートビートサイクルなどの元の状態にリフレッシュされる。

ブロック５５０において、ＧＨ２５は、次いで、ＢＮ候補が古いかどうかを判定する。ＢＮ候補は、ＴＴＬ値がゼロに等しい場合に古いとされる。もしＢＮ候補のＴＴＬ値がゼロであるならば、ブロック５５５において、そのＢＮ候補はＢＮ候補リストから外される。判定は、各ＢＮ候補について繰り返される。ＢＮ候補リストが更新されると、ブロック４３０において、ＧＨ２５は、選択されたＢＮ２０が例えば自身のようにＧＨ２５であるかどうかを判定する。ＧＨ２５は、ハートビートメッセージ２００に含まれる選択されたＢＮの識別子を、自身のノード識別子と比較する。もしこれらの識別子が同じならば、ブロック４３５において、ＧＨ２５は、自身をＬＰＧのＢＮ２０として宣言する。もしこれらの識別子が同じでないならば、ＧＨ２５は、ブロック４００のアイドル状態になる。

図６は、ＢＮ２０の選択のための有限状態マシンを示している。ノード１０は、３つの異なる状態、すなわちＢＮ候補状態６００、非ＢＮ状態６０５、及びＢＮ状態６１０になることができる。非ＢＮ状態６０５にあるノード１０は、外部ハートビート又はエッジハートビートを受信すると、ＢＮ候補状態６００に変わる。ＢＮ候補状態６００にあるノードは、ＧＨ２５がそれをＢＮ２０として選択すると、ＢＮ状態６１０に変わる。ノード１０は、外部ハートビート又はエッジハートビートを受信する限り、ＢＮ候補状態６００にとどまる。ノード１０は、外部ハートビート又はエッジハートビートを受信しなくなると、ＢＮ候補状態６００から非ＢＮ状態６０５に戻る。ノード１０は、外部ハートビート又はエッジハートビートを受信する限り、ＢＮ状態６１０にとどまる。

ノード１０は、外部ハートビート又はエッジハートビートを受信しなくなると、又はＴＴＬ値が古くなる、すなわちＴＴＬ＝０になると、ＢＮ状態６１０から非ＢＮ状態６０５に戻る。

ＢＮ２０は、ＬＰＧ間ルーティングを促進する。ルーティング経路は、各ノード内のルーティングテーブルに基づいて決定される。ルーティングテーブルは、データを中継するための次ホップ、次ＬＰＧ、及びＬＰＧ１のためのＢＮ２０に関する情報を含む。ルーティングテーブルは、ハートビートメッセージ２００及びＭＲ３００に含まれる情報をもとにして作成される。また、ルーティングテーブルは、外部ハートビート及びエッジハートビートからオーバヒアリングされる情報によって更新される。

図７は、ルーティングテーブルを作成及び更新するためにハートビートメッセージ２００及びＭＲ３００を処理するための方法を示している。最初、各ノード１０は、アイドルステップ７００にある。ステップ７０２において、パケットが到着すると、ステップ７０４において、ノード１０は、パケットがハートビートメッセージ２００であるか又はＭＲ３００であるかを判定する。制御パケットのタイプに応じて、ノード１０は、特別なパケット処理を実施する。もし制御パケットがハートビートメッセージ２００であるならば、ノード１０は、ステップ７０６から開始してパケットを処理する。ステップ７０６において、ノード１０は、パケットがネイティブであるかどうかを判定する。パケットは、同じＬＰＧ１に対するものである場合に、すなわち同じＧＩＤ（グループ識別子）を有する場合に、ネイティブである。ノード１０は、ＧＩＤを、メモリに格納されているグループ識別と比較する。もしＧＩＤが、メモリに格納されている識別と一致しないならば、ノード１０は、外部ＨＢ処理を開始し、ステップ８００に進む。外部ＨＢ処理は、図８において詳しく説明される。もしＧＩＤが、メモリに格納されている識別と一致するならば、ステップ７０８において、ノード１０は、ハートビートメッセージ２００が順序通りであるか
どうかを判定する。ノード１０は、Ｓｅｑ．Ｎｏ．を、メモリ内のシーケンス番号と比較する。もしＳｅｑ．Ｎｏ．が、メモリに格納されている値よりも小さいならば、ノード１０は、パケットを無視する。もしＳｅｑ．Ｎｏ．が、メモリに格納されている値よりも大きいならば、ハートビートメッセージ２００は、順序通りであり、ステップ７１０において、ノード１０は、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビートメッセージ２００が新しいかどうかを判定する。もしノード１０が、パケットを新しくないと判定するならば、ステップ７１２において、送信者のルーティングエントリのみが更新される。ハートビートメッセージ２００は、中継されない。もしノード１０が、メッセージ又はデータパケットを新しいと判定するならば、ノード１０は、ノードがＧＨ２５であるか又はＧＮであるかに応じて、２つの機能のうちの１つを実施する。ノードタイプの判定は、ステップ７１４において実施される。もしノード１０がＧＨ２５であるならば、ステップ７１６において、ノード１０は、送信者のルーティングエントリを更新する。ハートビートメッセージ２００は中継されず、ノードはアイドル状態７００になる。しかしながら、もしノード１０がＧＮであるならば、ステップ７１８において、ノード１０は、全てのＬＰＧ内ルーティングエントリ及びＬＰＧ間ルーティングエントリについてルーティングテーブルを更新し、ハートビートメッセージ２００を中継する。ＬＰＧ間ルーティング情報は、ノード１０が外部ＬＰＧからのメッセージを横聞き又はＢＮ２０から直接情報を受信するときに得られる。また、ＬＰＧ間ルーティング情報は、ＧＨ２５からのハートビートメッセージ２００に含められる。ノード１０は、任意の新しい宛先、宛先への次ホップ、新しい宛先があるＬＰＧの識別子、及びＬＰＧ１のためのＢＮ２０を、ルーティングテーブルに追加する。また、ルーティングテーブルは、宛先が義務宛先であればフラグを含む。義務外部宛先を伴うＢＮ２０又はＧＮは、フラグを使用し、義務宛先を外部宛先として自身のＭＲ３００に含ませる。ＧＨ２５を含むアップストリームノードは、義務外部宛先を伴うＢＮ２０又はＧＮからのＭＲ３００を横聞きすることによって、外部宛先を学習する。義務外部宛先については後述される。ＧＨは、ＬＰＧ１内の残りのノード１０に知らせるために、次のハートビートメッセージ２００に外部宛先を含ませる。ルーティングテーブルに既に挙げられている宛先については、ノード１０は、テーブル内の情報と異なる任意の情報を更新する。例えば、ノード１０は、次ホップ、ＬＰＧ、及びＢＮ２０を更新することができる。

もし制御パケットがＭＲ３００であるならば、ノード１０は、ステップ７２０から開始してパケットを処理する。ステップ７２０において、ノード１０は、パケットがネイティブであるかどうかを判定する。ノードは、ＧＩＤを、メモリに格納されているグループ識別と比較する。もしＧＩＤが、メモリに格納されている識別と一致しないならば、ノード１０は、外部ＭＲ処理を開始し、ステップ８００に進む。もしＧＩＤが、メモリに格納されている識別と一致するならば、ステップ７２２において、ノード１０は、そのＭＲ３００を送信したノード１０がＬＰＧ１（同じＬＰＧ）のメンバであるかどうかを判定する。ノード１０は、ノードＩＤを、メモリに格納されているメンバシップリストと比較する。もし一致がないならば、ステップ７２４において、ノード１０は、ＭＲ３００をただ中継する。ＭＲ３００の中継によって、新しいグループノード（ＧＮ）は、完全なハートビートサイクルにわたって待つ必要なくＬＰＧ１に参加することができる。

もしＭＲ３００を送信したノードが、参加リストに挙げられていない場合は、そのノード１０は、参加ノードであるとみなされる。ルーティングテーブルに、参加ノードについてのルーティングエントリはない。一実施形態では、ノード１０は、ＧＨ２５に向けてＭＲ３００を転送することができる。ノード１０は、ルーティングテーブルのいかなるエントリも更新しない。別の実施形態では、ノード１０は、（ＭＲ３００の）発信元ノードを宛先リストに追加することができる、すなわち発信元ノードについてのルーティングエントリを確保することができる。ノード１０は、中継ノードの情報を次ホップとして保存することができ、発信元ノードをメンバとして新たなハートビートメッセージ２００が受信
されると、ノード１０は、メモリに既に格納されている情報によってルーティングテーブルを自動的に更新することができる。新しいルーティングエントリが最終決定されると、発信元ノードは、ダウンストリームノードとして分類することができる。

もし一致があるならば、ステップ７２６において、ノード１０は、ＭＲ３００が順序通りであるかどうかを判定する。ノード１０は、ＭＲ Ｓｅｑ．Ｎｏ．を、メモリ内のシーケンス番号と比較する。もしＭＲ Ｓｅｑ．Ｎｏ．が、メモリに格納されている値よりも小さいならば、ノード１０はパケットを無視し、アイドル状態７００になる。もしＭＲ Ｓｅｑ．Ｎｏ．が、メモリに格納されている値よりも大きい又はその値と等しいならば、ＭＲ３００は順序通りであり、ステップ７２８において、ノード１０は、現シーケンス番号を伴う発信元からのＭＲ３００をノードが既に受信しているかどうかを（最後に格納されたシーケンス番号と比較することによって）チェックすることによって、ＭＲ３００が新しいかどうかを判定する。もしノード１０が、メッセージを新しくないと判定するならば、ステップ７３０において、送信者のルーティングエントリのみが更新される。ＭＲ３００は中継されない。もしノード１０が、メッセージを新しいと判定するならば、ノード１０は、ＧＨ２５であるか又はＧＮであるかに応じて、２つの機能のうちの１つを実施する。ノードタイプの判定は、ステップ７３２において実施される。もしノード１０がＧＨ２５であるならば、ステップ７３４において、ノード１０は、直接の送信者及び発信元のルーティングエントリを更新する。もしＭＲ３００が、少なくとも１つの外部宛先も運んでいるならば、ステップ７３４において、ノード１０は、エントリを外部宛先リストに追加する。ＬＰＧ１とのＬＰＧ間ルートを維持するために、収集された外部宛先リストは、次のハートビートメッセージ２００に含められる。更新は、ＬＰＧ内ルート及びＬＰＧ間ルートの両方を変更することを含む。もしＭＲ３００が、少なくとも１つの義務外部宛先を有するノード１０からであるならば、受信ノード１０は、義務外部宛先情報を使用して、ＬＰＧ間ルートを更新する。義務外部宛先情報をもとにして、受信ノード１０は、ＭＲ３００を発信したノード１０から到達することができる全ての外部宛先（ノード）を学習する。これらの外部宛先に向かう次ホップは、ＭＲ３００を発信したノード１０である。更新は、上述されており、再度の詳しい説明はされない。ＧＨ２５は、また、任意の新しい宛先ノードをメンバシップリストに追加することによって、メンバシップリストを更新する。新しいメンバシップリストは、次のハートビートメッセージ２００に含められる。ＭＲ３００は中継されず、ノードはアイドル状態７００になる。

しかしながら、もしノード１０がＧＮであるならば、ステップ７３６において、ノード１０は、送信者及び発信元についてルーティングテーブルを更新し、ＭＲ３００を中継する。例えば発信元の場合、発信元のための次ホップは、直接の送信者である。もしＭＲ３００が、外部宛先リスト、外部エントリも含むならば、外部宛先に向かう次ホップは、送信者である。発信元は、ダウンストリームノードである。更新は、ＬＰＧ内ルート及びＬＰＧ間ルートの両方を変更することを含む。更新は、上述されており、再度の詳しい説明はされない。

図８は、外部データパケット又はメッセージを処理するための方法を示している。外部データパケット又はメッセージは、異なるＬＰＧ内のノード１０を発信元とするメッセージである。外部データパケットの判定は、データパケット内のＬＰＧ識別子に基づく。ステップ８００において、外部ＬＰＧからデータパケットが受信される。ステップ８０５では、ノード１０は、外部データバケットがハートビートメッセージ２００であるか又はＭＲ３００であるかを判定する。制御パケットのタイプに応じて、ノード１０は、特別なパケット処理を実施する。ステップ８１０では、ノード１０は、データパケットが新しいＬＰＧを発信元とするかどうかを判定する。このステップは、ハートビートメッセージ２００及びＭＲ３００の両方に対して実施される。ノード１０は、外部データパケット内のＬＰＧ識別子を、ルーティングテーブル内のＬＰＧ識別子と比較する。もし外部データパケ
ットが新しいＬＰＧ１からでないならば、ステップ８１５において、ノード１０は、外部データパケットが順序通りに到着したかどうかを判定する。

もし外部データパケットが新しいＬＰＧからで、尚且つそのデータパケットがハートビートメッセージ２００であるならば、プロセスは、ステップ８２０に進む。ステップ８２０では、ＬＰＧ１が登録される。ＬＰＧ識別子がメモリに格納され、ルーティングテーブルに追加される。タイムスタンプも記録される。一実施形態では、タイムスタンプは、ルーティングテーブルから古い情報を消去するために使用される。既定期間の満了後、情報は、ルーティングテーブルから削除される。

また、ノード１０は、ＬＰＧ識別子、ＧＨ識別子、メンバリスト、及びＧＨへの次ホップなどの、新しいＬＰＧに関連した情報を含む新しいデータ構造を、新しいＬＰＧ用に作成する。この情報は、ルーティングテーブルとは別に格納される。ステップ８３０において、ノード１０は、ルーティングテーブル内のＬＰＧ間ルーティングエントリを更新する。ルーティングエントリは、ハートビートメッセージ２００に含まれるメンバシップリストから抽出される。ノード１０は、メンバシップリストからの各メンバを宛先として追加する。各宛先について、ルーティングテーブルは、次ホップ、ＢＮ２０、及びノードがあるＬＰＧ１を含む。また、ルーティングテーブルは、義務外部宛先のためのフラグを含む。義務外部宛先は、アクティブに通信しているノード１０であって、通信相手がＬＰＧ内にある又はＬＰＧ１を越えたところにあるノード１０である。ノード１０は、また、外部ハートビートメッセージを横聞きしたときからＢＮ候補にもなる。一実施形態では、ルーティングテーブルから古い情報を消去するために、外部ハートビートカウンタが使用される。既定期間の満了後、情報は、ルーティングテーブルから削除される。ステップ８３０では、外部ハートビートカウンタは、新しい外部ハートビートが受信されるたびにリセットされる。

もしハートビートメッセージ２００が新しくないならば、ステップ８１５において、ノード１０は、データパケットが順序通りに到着したかどうかを判定する。ノード１０は、Ｓｅｑ．Ｎｏ．を、メモリに格納されているシーケンス番号と比較する。もしＳｅｑ．Ｎｏ．が、メモリに格納されている値よりも小さいならば、ノード１０はパケットを無視し、外部データパケットは破棄される。もしＳｅｑ．Ｎｏ．が、メモリに格納されている値よりも大きいならば、ハートビートメッセージ２００は順序通りであり、ステップ８２５において、ノード１０は、現シーケンス番号を、最後に格納されたシーケンス番号と比較することによって、ハートビートメッセージ２００が新しいかどうかを判定する。もしノード１０が、パケットを新しくないと判定するならば、ステップ８３５において、ノード１０は、より良いルートが発見されたかどうかを判定する。新着のＨＢは、必ずしも最短経路を通って来たとは限らない。もし後のＨＢパケットが（たとえ新着でなくても）、より短い経路を通って来たならば、ＧＨへの経路は、更新されるべきである。ルーティングテーブルは、外部ハートビートメッセージ２００内の新しい情報に基づいて更新される。ステップ８２５において、もし外部データパケットが新しいと判定されるならば、プロセスは、ステップ８３０に進む。ステップ８３０は上述されており、再度の詳しい説明はされない。

もし外部データパケットがＭＲ３００であるならば、ステップ８１０において、ノード１０は、ＬＰＧ１が新しいか否かを判定する。もしＬＰＧ１が新しいならば、プロセスは、ステップ８４０に進む。ステップ８４０において、ノード１０は、送信者、発信元、及び外部ＧＨへの次ホップ中継について、ルーティングテーブル内のＬＰＧ間ルーティングエントリを更新する。ノードは、例えば送信者、発信元、及び次ホップ中継ノードなどの３タイプのノードについて、次ホップ情報及び宛先情報を更新する。また、ノード１０は、より良いルートがあるかもチェックする。より良いルートは、普通は、より短いホップ
のルートを意味する。たとえ、例えば送信者、発信元、及びＧＨへの次ホップ中継などの３つの外部宛先がＢＮ２０に知られている場合でも、ＧＮは、送信者への直接経路、発信元へのより短い経路、及び次ホップ中継を有する。もしＭＲ３００が新しくないならば、ノード１０は、ステップ８１５において、データパケットが順序通りに到着したかどうかを判定する。ノード１０は、Ｓｅｑ．Ｎｏ．を、メモリ内のシーケンス番号と比較する。もしＳｅｑ．Ｎｏ．が、メモリに格納されている値よりも小さいならば、ノード１０はパケットを無視し、外部データパケットは破棄される。もしＳｅｑ．Ｎｏ．が、メモリに格納されている値よりも大きいならば、ＭＲ３００は順序通りであり、プロセスはステップ８４０に進む。ステップ８４０は上述されており、再度の詳しい説明はされない。

ステップ８３０、８３５、及び８４０の各ステップの後、プロセスは、ステップ８４５に進む。ステップ８４５では、離脱ノードが検出される。検出プロセスは、後ほど詳しく説明される。

図９〜１１は、オンデマンドなルートの決定方法を示している。オンデマンドなルートは、ルート要求（Ｒ＿Ｒｅｑ）データパケット及びルート応答（Ｒ＿Ｒｅｓｐ）データパケットを使用して決定され維持される。アクティブ通信のためのルートが発見され維持される。とあるソースが外部宛先すなわち異なるＬＰＧ１内の宛先への通信を開始する必要があるとき、ノード１０は、ユニキャストＲ＿ＲｅｑメッセージをネイティブＢＮ２０に送信する。ネイティブＢＮは、同じＬＰＧ１内のＢＮ２０である。Ｒ＿Ｒｅｑは、中継ノードによって中継される。中継ノードは、自身によってＭＲ３００を中継される少なくとも１つのダウンストリームノードを有するノード１０である。具体的なルートは、ルーティングテーブル内の次ホップ情報によって決定される。Ｒ＿Ｒｅｓｐは、宛先ノード又は宛先ノードに対してネイティブなＢＮ２０のいずれかによって開始されるメッセージである。Ｒ＿Ｒｅｑは、宛先ノードが見つかるまで又は最大ホップカウントに達するまで中継される。最大ホップカウントは、Ｒ＿Ｒｅｑが誤った方向に無限に中継されるのを阻止する。Ｒ＿Ｒｅｑが中継されるたびに、ホップカウントは１だけ増分される。Ｒ＿Ｒｅｑは、中継ノードによってのみ中継され、フラッディングしない。

もしＢＮ２０がＲ＿Ｒｅｓｐを発行できないならば、ＢＮ２０は、Ｒ＿Ｒｅｑを隣接するＢＮに向けて中継する。ＢＮ２０は、最大ホップカウントに達するまで又はＢＮ２０がＲ＿Ｒｅｓｐを発行できるまで、Ｒ＿Ｒｅｑを他のＢＮ２０に転送する。ＢＮ２０がＲ＿Ｒｅｓｐを発行するとき、そのＲ＿Ｒｅｓｐは、隣接するＬＰＧに宛先があることを示す。

Ｒ＿Ｒｅｑは、Ｒ＿Ｒｅｑのタイプ、最大ホップカウント、前ＬＰＧ識別子、宛先、宛先シーケンス番号、ソース識別子、及びソースシーケンス番号を含む。Ｒ＿Ｒｅｑのタイプは、通常や応答済みなどであってよい。Ｒ＿Ｒｅｑのタイプは、Ｒ＿Ｒｅｑが宛先に達する前に応答されたかどうかを識別するために使用され、もしＲ＿Ｒｅｑが宛先ノードに達する前に既に応答されているならば、宛先ノードは、Ｒ＿Ｒｅｓｐを発行する必要はない。上述のように、最大ホップカウントは、ルーティング検索を制限するために使用される。前ＬＰＧ識別子は、すぐ隣りのＬＰＧ１の識別子であり、もしＲ＿Ｒｅｑが別のＬＰＧから来たものならば、そのＬＰＧ１は、Ｒ＿Ｒｅｑが直前に中継されていたところである。前ＬＰＧ識別子は、ソースノードが属しているＬＰＧ１における現ＬＰＧ識別子に等しい。宛先ＩＤは、宛先ノードの識別子である。ソースＩＤは、ソースノードの識別子である。ソースシーケンス番号は、各Ｒ＿Ｒｅｑデータパケット及びＲ＿Ｒｅｑの順番を一意に識別するために使用される。別の実施形態では、Ｒ＿Ｒｅｑは、更に、ターゲットＢＮ識別子、ターゲットＢＮに向かう次ホップ識別子、及び前ホップを含む。ターゲットＢＮ識別子は、ノード１０が同じＬＰＧ１内のＢＮ２０を区別することを可能にする。ＬＰＧ１内に２つ以上のＢＮ２０がある場合、ノード１０は、どの方向にＲ＿Ｒｅｑを中継す
るかを知ることができる。ターゲットＢＮに向かう次ホップ識別子は、中継ノードがＲ＿ＲｅｑをターゲットＢＮに向けて中継するために使用される。次ホップのみが、Ｒ＿Ｒｅｑを中継する。逆経路の場合、ノード１０は、前ホップを使用する。Ｒ＿Ｒｅｓｐは、中間ノードのルーティングテーブルに基づいて中継されてソースに戻される。ソースは、Ｒ＿Ｒｅｑが転送されるときにルーティングテーブルに挿入され、ルーティングエントリは、義務外部宛先としてソースノードを有するノードによって、各ＬＰＧ内において維持される。前ホップを含ませることによる利点は、Ｒ＿Ｒｅｓｐが複数のＬＰＧを通って移動する場合、中間ＬＰＧ１がルーティングテーブル内にソースノードを有さないかもしれないことにある。中間ＬＰＧは、ソースＬＰＧと宛先ＬＰＧとの間にあるＬＰＧである。ソースＬＰＧ、中間ＬＰＧ、宛先ＬＰＧを含むノードは、全て、ソース及び宛先のルーティング情報を有する。前ホップは、Ｒ＿Ｒｅｑから抽出され、後の使用に備えてメモリに格納される。

Ｒ＿Ｒｅｓｐは、ホップカウント、次ＬＰＧ識別子、宛先識別子、宛先シーケンス番号、ソース識別子、ソースシーケンス番号、及び次ホップ中継を含む。ホップカウントは、宛先ノードがソースノードから離れているホップ数である。次ＬＰＧ識別子は、Ｒ＿Ｒｅｓｐがこれから中継される次のＬＰＧの識別子である。

図９に示されるように、ノード１０は、ステップ４００においてアイドル状態にある。ステップ９００において、Ｒ＿Ｒｅｑ又はＲ＿Ｒｅｓｐが到着する。ステップ９０５では、ノード１０は、受信されたデータパケットがＲ＿Ｒｅｑであるか又はＲ＿Ｒｅｓｐであるかを判定する。この判定は、到着データパケットのフォーマット及びそれに含まれる情報に基づく。

もし到着データパケットがＲ＿Ｒｅｑであるならば、プロセスは、ステップ９１０に進む。ステップ９１０では、ノード１０は、Ｒ＿Ｒｅｑが新しい要求であるかどうかを判定する。判定は、データパケットのシーケンス番号、すなわちソースシーケンス番号に基づく。Ｒ＿Ｒｅｑパケットが受信されるたびに、パケットからソースシーケンス番号が抽出され、メモリに格納される。新しいＲ＿Ｒｅｑパケットが到着すると、最後に格納されたソースシーケンス番号が、到着Ｒ＿Ｒｅｑパケットのソースシーケンス番号と比較される。もしソースシーケンス番号が、メモリに格納されている値よりも小さいならば、ノード１０はパケットを無視し、パケットは破棄される。もしソースシーケンス番号が、メモリに格納されている値よりも大きいならば、Ｒ＿Ｒｅｑは新しく、ステップ９１５において、ノード１０は、Ｒ＿Ｒｅｑに対する応答が既に発行されているかどうかを判定する。判定は、Ｒ＿Ｒｅｑに含まれるＲ＿Ｒｅｑタイプの指標に基づく。もしＲ＿Ｒｅｑタイプが、Ｒ＿Ｒｅｑに対する応答が既に発行されたことを示すならば、ステップ９３０において、ノード１０は、Ｒ＿Ｒｅｑを宛先へ中継する。Ｒ＿Ｒｅｑが応答されていないときは、ステップ９２０において、ノード１０は、それが宛先のＬＰＧ内のＢＮ２０であるか又は宛先であるかを判定する。

もしノード１０が、宛先のＬＰＧ内のＢＮ２０又は宛先のいずれかであるならば、ステップ９２５において、ノード１０は、Ｒ＿Ｒｅｓｐを発行し、Ｒ＿Ｒｅｑのタイプを「応答済み」に変更する。その後、ノードは、ステップ９３０において、Ｒ＿Ｒｅｑ中継機能を実施する。Ｒ＿Ｒｅｑ中継機能は、後述される。Ｒ＿Ｒｅｑ中継機能が実施された後、ステップ９３５において、ノード１０は、Ｒ＿Ｒｅｑのソースのためのルーティングを更新する、すなわちソースの次ホップを、Ｒ＿Ｒｅｑが来たところにする。

もしＲ＿Ｒｅｑのタイプが、Ｒ＿Ｒｅｑに対する応答が発行されていないことを示すならば、ステップ９２０において、ノード１０は、自身が応答を発行できるかどうかを判定する。Ｒ＿Ｒｅｑを発行できるのは、宛先ノード又はＢＮ２０のみである。ノード１０は
、Ｒ＿Ｒｅｑから宛先識別子を抽出し、それを自身の識別子と比較する。もし識別子が一致するならば、ノード１０は宛先ノードである。もし識別子が一致しないならば、ノード１０は宛先ノードではない。また、宛先識別子を使用して、ノード１０は、宛先ノード用のＢＮ２０について、ルーティングテーブル内を調べる。ノード１０は、ＢＮ２０の識別子を自身の識別子と比較する。もし識別子が一致するならば、ノード１０は、宛先ノード用のＢＮ２０である。もし識別子が一致しないならば、ノード１０は、宛先ノード用のＢＮ２０ではない、すなわち宛先ノードがあるＬＰＧ１内のＢＮではない。

もしノード１０が、宛先ノード、又は宛先ノードのＬＰＧ１内のＢＮ２０のいずれかであるならば、ステップ９２５において、ＢＮ２０又はノード１０は、Ｒ＿Ｒｅｓｐを発行する。また、ノード１０は、Ｒ＿Ｒｅｑのタイプを応答済みに変更し、ステップ９３０において、Ｒ＿Ｒｅｑは宛先へ中継される。

（ステップ９２０において、）もしノード１０が、宛先ノード、又は宛先ノードのＬＰＧ１内のＢＮ２０のいずれでもないならば、ステップ９３０において、ノード１０は、Ｒ＿ＲｅｑをＢＮ２０又は宛先ノードに向けて中継する。ソースノードは、ＢＮ２０にとっての義務外部宛先になり、ＢＮ２０は、ソースノードにとっての入口ＢＮである。Ｒ＿Ｒｅｑ中継機能は、図１０に記載されており、後ほど詳しく説明される。

ステップ９３５において、ノード１０は、ルーティングテーブル内の、ソースノードについてのルーティング情報を、Ｒ＿Ｒｅｑからの情報によって更新する。例えば、ノード１０は、ソースノード識別子、ソースノードについてのＬＰＧ情報、及びソースノードについてのホップカウントを追加することができる。

もし到着データパケットがＲ＿Ｒｅｓｐであるならば、プロセスは、ステップ９４０に進む。ステップ９４０において、ノード１０は、Ｒ＿Ｒｅｓｐが新しい応答であるかどうかを判定する。判定は、データパケットのシーケンス番号、すなわち宛先シーケンス番号に基づく。データパケットが受信されるたびに、パケットから宛先シーケンス番号が抽出され、メモリに格納される。新しいデータパケットが到着すると、最後に格納された宛先シーケンス番号が、到着データパケットの宛先シーケンス番号と比較される。もし宛先シーケンス番号が、メモリに格納されている値よりも小さいならば、ノード１０はパケットを無視し、パケットは破棄される。もし宛先シーケンス番号が、メモリに格納されている値よりも大きいならば、Ｒ＿Ｒｅｓｐは新しく、ステップ９４５において、Ｒ＿Ｒｅｓｐは、ソースノードに向けて中継される。

Ｒ＿Ｒｅｓｐ中継機能は、図１１に記載されており、後ほど詳しく説明される。

ステップ９５０において、ノード１０は、ルーティングテーブル内の、宛先ノードについてのルーティング情報を、Ｒ＿Ｒｅｓｐからの情報によって更新する。例えば、ノード１０は、宛先ノード識別子、宛先ノードについてのＬＰＧ情報、及び宛先ノードについてのホップカウントを追加することができる。

図１０は、Ｒ＿Ｒｅｑのための中継プロセスを説明している。プロセスは、ステップ１０００から開始する。ステップ１００５において、ノード１０は、宛先ノードが同じＬＰＧ１内であるか、すなわちローカルな宛先であるかどうかを判定する。ノード１０は、ルーティングテーブルを調べ、宛先ノードがＬＰＧ内宛先であるかどうかをチェックする。もし宛先ノードがＬＰＧ内ルーティングエントリとして挙げられているならば、宛先は、同じＬＰＧ内である。もし宛先がローカルである、すなわちＬＰＧ内であるならば、ノード１０は、Ｒ＿Ｒｅｑが宛先ノードに到達したか、すなわち宛先ノードの識別子が現ノードの識別子と同じであるかどうかを判定する。宛先ノードは、自身に宛てられたＲ＿Ｒｅ
ｑを受信すると、Ｒ＿Ｒｅｑの転送を終了させる。

ステップ１０１０、１０１５、１０３０、及び１０３５は、ローカルな宛先及び非ローカルな宛先のどちらの場合も実施される。ステップ１０１０では、ノード１０は、自身がソースにとっての入口（ingress）ＢＮであるかどうかを判定する。入口ＢＮは、ＬＰＧ１内のノード１０のなかで別のＬＰＧ１内のノード１０からのＲ＿Ｒｅｑを最初に受信するＢＮ２０、又は義務外部宛先リスト内にＲ＿Ｒｅｑのソースを既に有しているＢＮ２０である。義務外部宛先は、そのＬＰＧの外側のノードについての特別なルーティングエントリである。とあるノードが義務外部宛先を有しているときは、そのノードを通じて外部宛先に到達可能であることを知らせるために、それらの義務外部宛先のノードＩＤがノードのＭＲ（メンバレポート）の一部として含まれる。中継ノードは、「ｋ」回の前制御メッセージサイクル内においてダウンストリームノードの少なくとも１つのＭＲ３００をアップストリームノードへ中継するノードである。

もしノード１０がソースの入口ＢＮであるならば、ステップ１０１５において、ノード１０は、ソースノードについてのエントリによって、ルーティングテーブルを更新する。ソースノードは、義務外部宛先になる。ノードは、義務フラグを設定する。ノード（入口ＢＮ）は、自身のＬＰＧ１にルーティング情報を知らせる又は公示する役割を担う。

ノード１０がルーティングテーブルを更新した後、ステップ１０３５において、ノード１０（入口ＢＮ）は、Ｒ＿Ｒｅｑをブロードキャストする。ブロードキャストに先立ち、ステップ１０３２において、ノード１０は、ホップカウントを１だけ増分させる。また、ステップ１０３４において、ノード１０は、Ｒ＿Ｒｅｑの最大ホップカウントに達したかどうかを判定する。最大ホップカウントは、Ｒ＿Ｒｅｑに含まれる。ノード１０は、最大ホップカウントを、例えば受信されたＲ＿Ｒｅｑのホップカウント＋１などの現ホップカウントと比較する。もし最大ホップカウントに達したならば、Ｒ＿Ｒｅｑは転送されず、ステップ１０４０において、ノード１０は停止する。

もし宛先ノードがローカルであり、ノード１０が入口ＢＮではないならば、ステップ１０３０において、ノード１０は、自身が中継ノードであるかどうかを判定する。次ホップ中継は、ルーティングテーブル内の情報に基づく。もしノード１０が中継ノードであるならば、ステップ１０３５において、Ｒ＿Ｒｅｑはブロードキャストされる。プロセスは、次いで、ステップ１０４０において終了する。ブロードキャストに先立ち、ステップ１０３２において、中継ノードは、ホップカウントを１だけ増分させる。また、ステップ１０３４において、中継ノードは、Ｒ＿Ｒｅｑについての最大ホップカウントに達したかどうかを判定する。最大ホップカウントは、Ｒ＿Ｒｅｑに含まれる。中継ノードは、最大ホップカウントを、例えば受信されたＲ＿Ｒｅｑのホップカウント＋１などの現ホップカウントと比較する。もし最大ホップカウントに達したならば、Ｒ＿Ｒｅｑは転送されず、ステップ１０４０において、中継ノードは停止する。

もし宛先ノードが非ローカルな宛先であり、ノード１０が入口ＢＮではないならば、ノード１０は、自身が出口（egress）ＢＮであるかどうかを判定する。出口ＢＮは、自身のＬＰＧ内のノード１０からＲ＿Ｒｅｑを受信するＢＮ、又は（義務宛先ではないが）その外部宛先としてＲ＿Ｒｅｑのソースを既に有しているＢＮである。出口ＢＮ機能は、隣接するＬＰＧがＲ＿Ｒｅｑを受信できるように、Ｒ＿Ｒｅｑを隣接するＬＰＧへブロードキャストすることである。もしノード１０が出口ＢＮであるならば、ステップ１０２５において、ノード１０は、前ＬＰＧ識別子を自身のＬＰＧ識別子で置き換え、ステップ１０３５において、Ｒ＿Ｒｅｑをブロードキャストする。ホップカウントが最大ホップカウントに達すると、Ｒ＿Ｒｅｑは、これ以上は再ブロードキャストされない。

もし宛先ノードが非ローカルであり、ノード１０が入口ＢＮでも出口ＢＮでもないならば、ステップ１０３０において、ノード１０は、自身が中継ノードであるかどうかを判定する。

次ホップ中継は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってＭＲ３００を中継される少なくとも１つのダウンストリームノードを有するノード１０である。もしノード１０が中継ノードでないならば、Ｒ＿Ｒｅｑは中継されない、すなわち転送されない。もしノード１０が中継ノードであるならば、ステップ１０３５において、Ｒ＿Ｒｅｑはブロードキャストされる。プロセスは、次いで、ステップ１０４０において終了する。

図１１は、Ｒ＿Ｒｅｓｐのための中継プロセスを説明している。プロセスは、ステップ１１００から開始する。ステップ１１０５において、ノード１０は、ソースノードが同じＬＰＧ１内であるか、すなわちローカルなソースであるかどうかを判定する。ノード１０は、ルーティングテーブル内を調べ、ソースノードのＬＰＧ１のＬＰＧ識別子を読み出す。ソースノードのＬＰＧ識別子は、ノード１０のＬＰＧ識別子と比較される。もし識別子が一致するならば、ソースノードは同じＬＰＧ１内である。中継プロセスは、非ローカルな宛先の場合に２つ余分にステップがあることを除き、ローカルな宛先及び非ローカルな宛先のどちらの場合も同様である。

ステップ１１１０、１１１５、１１３０、及び１１３５は、ローカルなソース及び非ローカルなソースのどちらの場合も実施される。ステップ１１１０では、ノード１０は、別のＬＰＧ内のノードからＲ＿Ｒｅｓｐを受信するときに、自身が宛先にとっての入口ＢＮであるかどうかを判定する。入口ＢＮは、別のＬＰＧ１内のノード１０からＲ＿Ｒｅｓｐを受信するＢＮである。

もしノード１０が入口ＢＮであるならば、ステップ１１１５において、ノード１０は、宛先ノードについてのエントリによって、ルーティングテーブルを更新（inserts updates）する。宛先ノードは、義務外部宛先になる。ノードは、義務フラグを設定する。ノード（入口ＢＮ）は、自身のＬＰＧ１にルーティング情報を知らせる又は公示する役割を担う。

ノード１０がルーティングテーブルを更新した後、ステップ１１３５において、ノード１０（入口ＢＮ）は、Ｒ＿Ｒｅｓｐをブロードキャストする。一実施形態では、Ｒ＿Ｒｅｓｐは、Ｒ＿Ｒｅｑと同じ経路を通って中継される。

もしソースノードがローカルであり、ノード１０が入口ＢＮではないならば、ステップ１１３０において、ノード１０は、自身が中継ノードであるかどうかを判定する。判定は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってＭＲ３００を中継される少なくとも１つのダウンストリームノードを有するノードである。もしノード１０が中継ノードでないならば、Ｒ＿Ｒｅｓｐは中継されない、すなわち転送されない。もしノード１０が中継ノードであるならば、ステップ１１３５において、Ｒ＿Ｒｅｓｐはブロードキャストされる。プロセスは、次いで、ステップ１１４０において終了する。

もしソースノードが非ローカルなソースであり、ノード１０が入口ＢＮではないならば、ステップ１１２０において、ノード１０は、自身が出口ＢＮであるかどうかを判定する。出口ＢＮ機能は、隣接するＬＰＧがＲ＿Ｒｅｓｐを受信できるように、Ｒ＿Ｒｅｓｐを隣接するＬＰＧへブロードキャストすることである。もしノード１０が出口ＢＮであるならば、ステップ１１２５において、ノード１０は、次ＬＰＧ識別子を自身のＬＰＧ識別子で置き換え、ステップ１１３５において、Ｒ＿Ｒｅｓｐをブロードキャストする。

もしソースノードが非ローカルであり、ノード１０が入口ＢＮでも出口ＢＮでもないならば、ステップ１１３０において、ノード１０は、自身が中継ノードであるかどうかを判定する。判定は、ルーティングテーブル内の情報に基づく。中継ノードは、自身によってＭＲ３００を中継される少なくとも１つのダウンストリームノードを有するノードである。もしノード１０が中継ノードでないならば、Ｒ＿Ｒｅｓｐは中継されない、すなわち転送されない。もしノード１０が中継ノードであるならば、ステップ１１３５において、Ｒ＿Ｒｅｓｐはブロードキャストされる。プロセスは、次いで、ステップ１１４０において終了する。

ひとたびソースノードがＲ＿Ｒｅｓｐを受信すると、ソースノードは、宛先ノードに対するメッセージやデータの伝送、又は通信を開始させる。

上述のように、ＢＮ２０は、アクティブな通信経路を維持する及び他のノードに移動ノード又は離脱ノードについて知らせる役割を担う。図１２は、離脱ノードを検出するプロセスを示している。プロセスは、ステップ４００においてＢＮ２０がアイドル状態にあるところから開始する。ステップ１２００において、離脱ノードが検出される。離脱ノードは、２つの方法のうちの１つを使用して検出される。離脱ノードは、外部ハートビートメッセージ２００のオーバヒアリングによって検出することができる。詳細には、離脱ノードは、外部ハートビートメッセージ２００に含まれるメンバシップリストに自身の識別子を含まれている。ＢＮ２０は、自身のＬＰＧ１内にあったノードが外部メンバシップリストに挙げられたときに、そのノードがＬＰＧを離脱したと判定する。或いは、離脱ノードは、その離脱ノードが外部ＬＰＧ１の識別子を伴うＭＲ３００をブロードキャストしたときに検出することができる。ＢＮ２０は、これまで同じＬＰＧ内にあったノードからＭＲ３００をオーバヒアリングする。ＢＮ２０は、自身のＬＰＧ識別子を、ＭＲ３００内の識別子と比較する。もし識別子が異なるならば、ノード１０は離脱している。１つのノード１０は、１つのＬＰＧ１のメンバであることしかできない。

ステップ１２０５において、ＢＮ２０は、自身のルーティングテーブルを離脱ノードについて更新する。具体的には、ＢＮ２０は、離脱ノードのＬＰＧを変更する。ルーティングテーブルが更新されたら、ＢＮは、ステップ４００のアイドル状態に戻る。ＢＮは、次いで、離脱ノードに関連した情報を公示する。

別の実施形態では、（ＢＮ２０だけでなく）任意のノードが、外部ハートヒート又は外部ＭＲ３００をオーバヒアリングすることによって離脱ノードを検出することができる。

ＢＮ情報は、ルーティングテーブルから取り出される。もしノード１０がＢＮ２０であるならば、ＢＮ２０は、次のＭＲ３００に離脱ノード通知を含ませる。通知は、ノードがＬＰＧ１から離れたことの肯定声明である。通知は、離脱ノードの識別子と、新しいＬＰＧの識別子とを含む。ステップ１３２５において、ＢＮ２０は、次いで、その離脱ノードについてアクティブな通信が継続中であるかどうかを判定する。通信は、もし離脱ノードが通信の宛先又はソースのいずれかであるならば継続中である。もしアクティブな通信が継続中でないならば、ＢＮ２０は、アイドル状態（ステップ４００）に戻る。しかしながら、もしアクティブな通信が継続中であるならば、ＢＮ２０は、ルートを維持しなければならない。ルートは、ステップ１３３０において、義務外部宛先のリストに離脱ノードを追加してルーティングテーブルを更新することによって維持される。このリストは、次のＭＲ３００に含められてブロードキャストされ、後に、ハートビートメッセージ２００に含められる。ＢＮ２０は、次いで、アイドル状態（ステップ４００）に戻る。

もしステップ１３０５において、ノード１０がＢＮ２０ではないならば、ノード１０は
、ＢＮ２０が離脱ノード通知を既に送信したかどうかを判定する。ステップ１３１０において、ノード１０は、ＢＮ２０から受信された最新のＭＲ３００を離脱ノード通知についてチェックする。もしＭＲ３００が離脱ノード通知を含んでいたならば、ノード１０は、アイドル状態に戻る。ノード１０は、離脱ノード通知に含まれる情報によって、ルーティングテーブルを更新する。

もしＢＮ２０からのＭＲ３００が離脱ノード通知を含んでいなかったならば、ノード１０は、別のノードが既に離脱ノート通知を送信したかどうかを判定する。ステップ１３１５において、ノード１０は、任意のノードから受信された最新のＭＲ３００を離脱ノード通信についてチェックする。もしＭＲ３００が離脱ノード通知を含んでいたならば、ノード１０は、アイドル状態に戻る。

もしどのノード１０からも離脱ノード通知が受信されなかったならば、プロセスは、ステップ１３２０に進み、ここで、ノード１０は、自身のＭＲ３００に離脱ノード通知を挿入する。ノード１０は、次いで、（あたかも自身がＢＮ２０であるかのように）ステップ１３２５及び１３３０を実施する。

図１４は、義務外部宛先を他のノードに公示又は通知するプロセスを示している。義務外部宛先リストの公示は、ハートビートメッセージ２００及びＭＲ３００を使用して達成される。義務外部宛先リストは、ハートビートメッセージ２００及びＭＲ３００に追加される。

図１４に示されるように、ノード１０は、ステップ４００のアイドル状態から開始する。ハートビートメッセージ２００及びＭＲ３００は、定期的にブロードキャストされる。期間は、ハートビートサイクル又はＭＲサイクルである。一連のハートビートメッセージ２００又はＭＲ３００の間の期間は、タイマ又は計時手段によってカウントされる。ハートビートメッセージ２００及びＭＲ３００は、サイクル期間の満了によってトリガされる。ステップ１４００において、ハートビートメッセージ２００又はＭＲ３００のいずれかが、タイマの１つの満了によってトリガされる。ステップ１４０５において、ノード１０は、自身が通常ノード（ＧＮ）であるか又はＧＨ２５であるかを判定する。もしノード１０がＧＨ２５であるならば、ステップ１４１０において、義務外部宛先リストは、ＬＰＧ１の外部宛先としてハートビートメッセージ２００に追加される又は符号化される。ステップ１４１５において、ハートビートメッセージ２００はブロードキャストされる。ＧＨ２５は、その後、アイドル状態（ステップ４００）に戻る。

もしノード１０がＧＮであるならば、ステップ１４２０において、義務外部宛先リストは、ＭＲ３００に追加される又は符号化される。ステップ１４２５において、ＭＲ２００はブロードキャストされる。ＧＮは、その後、アイドル状態（ステップ４００）に戻る。

ステップ１４３０において、ＧＨ２５は、ＭＲ３００を受信する。ステップ１４３５において、ＧＨは、義務外部宛先リストをＭＲ３００から抽出し、後のブロードキャストに備えて格納する。格納された義務宛先リストは、次のハートビートメッセージに含められる。その後、ＧＨ２５は、アイドル状態（ステップ４００）に戻る。

本明細書において、発明は、特定の典型的実施形態を参照にして説明されてきた。当業者にならば、発明の範囲から逸脱することなく特定の変更及び修正が明らかであろう。典型的実施形態は、例示的であることを意図されており、特許請求の範囲に定められた発明の範囲を制限しない。

Claims (20)

1. 各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、
   ソースノードからルート要求メッセージを伝送するステップであって、前記ルート要求メッセージは、宛先ノードの識別子、ソースノードの識別子、及び前ＬＰＧ識別子を少なくとも含む、ステップと、
   前記ルート要求メッセージをネイティブ境界ノードへ中継するステップと、
   前記ルート要求メッセージを外部境界ノードへ転送するステップと、
   前記宛先ノードの識別子に対応する宛先ノードが前記外部境界ノードのＬＰＧ内であるかどうかを判定するステップと、
   前記宛先ノードが前記ＬＰＧ内でないならば、前記ルート要求メッセージを別の境界ノードへ中継するステップと、
   前記宛先ノードが前記ＬＰＧ内であるならば、前記ルート要求メッセージを前記宛先ノードへ中継するステップと、
   前記宛先ノードにおいて前記ルート要求メッセージを受信するステップと、
   前記宛先ノードによって前記ソースノードへルーティング応答を伝送するステップと、
   前記ルート要求メッセージによって発見された第１の経路を通じて前記ルーティング応答を前記ソースノードへ中継するステップと、
   前記ソースノードにおいて前記ルーティング応答を受信するステップと、
   前記ルーティング応答の受信を受けて前記データを伝送するステップであって、前記データは、前記ルーティング応答によって発見された第２の経路を使用して中継される、ステップと、
   を備える方法。
2. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
   前記ルート要求メッセージを受信するノードが前記宛先ノード又は前記宛先ノードのＬＰＧ内の境界ノードであるかどうかを判定するステップを備える方法。
3. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
   前記宛先ノードが前記ルート要求メッセージを受信しているノードと同じＬＰＧ内であるかどうかを判定するステップと、
   前記ルート要求メッセージを受信しているノードが入口（ingress）境界ノードであるかどうかを判定するステップと、
   前記ソースノードの識別子によって宛先リストを更新するステップと、
   を備える方法。
4. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
   前記ルート要求メッセージを受信しているノードが中継ノードであるかどうかを判定するステップを備える方法。
5. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
   前記ルート要求メッセージを受信しているノードが出口（egress）境界ノードであるかどうかを判定するステップと、
   前記ルート要求メッセージ内の前記前ＬＰＧ識別子を前記出口境界ノードのＬＰＧのＬＰＧ識別子で置き換えるステップと、
   を備える方法。
6. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
   前記ソースノードが前記ルーティング応答を受信しているノードと同じＬＰＧ内であるかどうかを判定するステップと、
   前記ルーティング応答を受信しているノードが入口境界ノードであるかどうかを判定するステップと、
   前記宛先ノードの識別子によって宛先リストを更新するステップと、
   を備える方法。
7. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
   前記ルーティング応答を受信しているノードが中継ノードであるかどうかを判定するステップを備える方法。
8. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
   前記ルーティング応答を受信しているノードが出口境界ノードであるかどうかを判定するステップと、
   前記ルーティング応答内の次ＬＰＧ識別子を前記出口境界ノードのＬＰＧのＬＰＧ識別子で置き換えるステップと、
   を備える方法。
9. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
   前記宛先ノードによって前記データが受信されるまでソースノードから宛先ノードへのルートを維持するステップを備える方法。
10. 請求項９に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、
    ルートを維持する前記ステップは、
    ノードがＬＰＧを変更したかどうかを検出するサブステップと、
    ノードがＬＰＧを変更したという通知をＬＰＧ内の全てのノードへ伝送するサブステップと、
    変更を検出されたノードが境界ノードであるかどうかを判定するサブステップと、
    前記ノードが境界ノードであると判定されたならば、ＬＰＧを変更した前記ノードの識別子を義務外部宛先としてルーティングテーブルに追加するサブステップと、
    を含む、方法。
11. 請求項１に記載の、各々が複数の移動ノードを含む複数のローカルピアグループ間でデータをルーティングするオンデマンドな方法であって、更に、
    前記ソースノードによって前記ルーティング応答が受信されるまで前記第１の経路を維持するステップと、
    前記宛先ノードによって前記データが受信されるまで前記第２の経路を維持するステップと、
    を備える方法。
12. 複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
    既定のノードを発信元とする第１の制御パケットを受信するステップであって、前記既定のノードはグループヘッダである、ステップと、
    前記第１の制御パケットが同じローカルピアグループ内のグループヘッダからであるかどうかを判定するステップと、
    前記第１の制御パケットが外部ローカルピアグループを発信元とするならば、パケットを前記グループヘッダへ伝送することによって境界ノードへの立候補を宣言するステップと、
    少なくとも１つの候補からの前記伝送パケットを前記グループヘッダにおいて受信するステップと、
    前記受信された伝送パケットに基づいて候補のリストを作成するステップと、
    前記候補のリストから１つの候補を前記境界ノードとして選択するステップと、
    前記選択された境界ノードの識別子を含むデータパケットを伝送するステップと、
    を備える方法。
13. 請求項１２に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
    前記候補のリストは、プリセット期間にわたって有効であり、前記期間は、Ｔｉｍｅ−ｔｏ−Ｌｉｖｅ値である、方法。
14. 請求項１２に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
    前記Ｔｉｍｅ−ｔｏ−Ｌｉｖｅ値は、前記第１の制御パケットの伝送期間の倍数である、方法。
15. 請求項１３に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
    前記プリセット期間が満了したかどうかを判定するステップと、
    前記プリセット期間が満了したならば候補を削除するステップと、
    を備える方法。
16. 請求項１３に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
    同じ候補の識別子を含むデータパケットを前記グループヘッダが受信したときにＴｉｍｅ−ｔｏ−Ｌｉｖｅ値をリフレッシュするステップを備える方法。
17. 請求項１２に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
    前記選択された境界ノードの識別子を含む前記データパケットを受信するステップと、
    前記選択された境界ノードの前記識別子を受信ノードの識別子と比較するステップと、
    前記比較に基づいて受信ノードのステータスを境界ノードに変更するステップと、
    を備える方法。
18. 請求項１７に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
    ステータスを境界ノードに変更した後に定期的に第２の制御パケットを伝送するステップを備える方法。
19. 請求項１２に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、
    前記境界ノードは、各候補についての、前記グループヘッダからのホップカウントに基
    づいて選択される、方法。
20. 請求項１２に記載の、複数のローカルピアグループ間での通信のために境界ノードを選択するための方法であって、更に、
    前記グループヘッダから前記境界ノードと反対の相対方向にある第２の境界ノードを選択するステップを備える方法。

Images