ローカル・ピア・グループ(LPG)に基づく車両アドホックネットワークにおける高信頼度マルチキャスト方法
マルチキャストメッセージのルーティング方法は、少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、前記メッセージが以前に受信したものであるか判断するステップと、前記メッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、前記マルチキャストメッセージを受信したノードが転送ノードであるか判断するステップと、前記マルチキャストメッセージを転送するための待機時間をランダムに設定するステップと、前記待機時間が満了したときに、前記マルチキャストメッセージを転送するステップと、を含む。
【発明の詳細な説明】
【技術分野】
【0001】
[関連出願の相互参照]
本発明は、共同所有され同時に係属中である、アドホック無線ネットワークにおけるユニキャストおよびマルチキャストメッセージをルーティングするための方法および通信装置と題する、2006年10月23日出願の出願番号第11/585,047の米国特許出願(「’047出願」)に関連する。
【0002】
[技術分野]
この発明は、移動環境における通信ネットワークに関連する。より具体的には、本発明は、複数の移動装置間のマルチホップ・マルチキャストメッセージをルーティングするための方法に関連する。
【背景技術】
【0003】
無線ホームネットワークや、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーン又はホテルにおけるいわゆる「ホットスポット」ネットワークや、さらには都市全体でのWiFi技術の実現であれ、無線技術は今日の生活のあらゆる面において一般的なものとなっている。社会においてこのように無線を推し進める目的は、情報へのアクセスを提供し、社会全体がコンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することで享受してきた生産性をさらに向上させるためである。
【0004】
無線通信社会になるという願望は、移動車両のような移動装置にまで広がっている。この種の無線通信ネットワークは、限定はしないが、緊急路上障害物警告、交差点での協調、隠れた車道に関する警告、車線変更または合流の支援などを含む、車両安全アプリケーションの多くの態様において現れる。
【0005】
車両安全通信(「VSC」)は大きく分類して、車車間通信とインフラ協調車両通信とに分けることができる。車車間通信では、固定インフラストラクチャからの支援なしに車両同士がお互いに通信する。車両同士が同じ無線通信範囲内に位置する場合や、他の車両を介したマルチホップ通信が可能な場合に、車両同士がお互いに通信する。インフラ協調車両通信では、路側無線アクセスポイントなどのインフラストラクチャの支援を受けて、車両同士がお互いに通信する。この場合、車両はインフラストラクチャのみと通信することもできる。
【0006】
衝突回避のような種々のVSCアプリケーションを支援するために、重要なVSC性能要件には、遅延時間が短いこと(100ミリ秒のオーダー)と、スループット(近くの車両が警告メッセージを受信に成功する確率と同等)を維持することが含まれる。
【0007】
’047出願には、1台の移動車両をグループヘッダとして選択し、このグループヘッダを利用してローカル・ピア・グループを維持し、ローカルルーティング情報を生成することで、移動車両のグループをローカル・ピア・グループに組織化することが記述されている。移動車両はユニキャストおよびマルチキャストのルーティングに適合される。しかしながら依然として、スループットをさらに向上し遅延が少ないマルチキャストのルーティング方法に対する要求がある。
【発明の概要】
【0008】
したがって、マルチキャストメッセージのルーティング方法が開示される。この方法は
、少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、前記メッセージが以前に受信したものであるか判断するステップと、前記メッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、前記マルチキャストメッセージを受信したノードが転送ノードであるか判断するステップと、前記マルチキャストメッセージを転送するための待機時間をランダムに設定するステップと、前記待機時間が満了したときに、前記マルチキャストメッセージを転送するステップと、を含む。
【0009】
前記メッセージが以前に受信したものである場合に、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを前記ランダムに設定された待機時間内に下流ノードから受信したときは、前記待機時間を停止する。待機時間が停止された場合は、マルチキャストメッセージは転送されない。
【0010】
第2のマルチキャストメッセージが下流ノードから受信されたかの判断は、第2のマルチキャストメッセージからTime−to−Live値を抽出する工程と、前記Time−to−Live値にプリセット値を加えてオフセットTime−to−Live値を生成する工程と前記マルチキャスト転送テーブルから同一のメッセージを含むマルチキャストメッセージのTime−to−Live値を取り出す工程と、前記オフセットTime−to−Live値と前記取り出されたTime−to−Live値とを比較する工程とを含み、前記取り出されたTime−to−Live値が前記オフセットTime−to−Live値よりも大きい場合に、前記待機時間が停止される。
【0011】
前記取り出されたTime−to−Live値が前記オフセットTime−to−Live値と等しい場合は、前記待機時間はランダム値にリセットされる。
【0012】
本方法は、転送後にACKフラグを未確認に設定するステップと、再送時間を所定時間に設定するステップと、をさらに含む。前記メッセージが以前に受信されたものである場合に、本方法は、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを下流ノードから受信したときは、前記再送時間を停止するステップをさらに含む。前記再送時間を停止した後に、ACKフラグを確認済みに設定される。
【0013】
本方法は、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、再送後に前記送信時間を所定時間に設定するステップと、をさらに含む。
【0014】
本方法は、再送の上限に達したか判断するステップと、前記判断に基づいて、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、再送カウンタを増加させるステップと、再送後に前記再送時間を所定時間に設定するステップと、をさらに含む。再送の上限に達した場合には、再送時間が停止される。
【0015】
前記マルチキャスト転送テーブルは、前記グループ宛先と前記送信元識別子と前記シーケンス番号と前記メッセージと前記ACKフラグと前記再送時間値と前記再送カウンタと前記Time−to−Live値とを含む。
【0016】
マルチキャストメッセージをルーティングするための別の方法も開示される。本方法は、少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと
、前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、前記メッセージが以前に受信したものであるか判断するステップと、前記マルチキャストメッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、前記マルチキャストメッセージを受信したノードがマルチキャスト受信ノードであるか判断するステップと、マルチキャスト受信ノードに確率値をランダムに割り当てるステップと、前記ランダムに割り当てられた確率値とプリセット確率閾値とを比較するステップと、前記比較に基づいて前記マルチキャストメッセージを転送するステップと、を含む。
【0017】
本方法は、前記プリセット確率閾値を設定するステップをさらに含む。
【0018】
前記マルチキャスト転送テーブルは、前記グループ宛先と前記送信元識別子と前記シーケンス番号とを含む。
【0019】
本方法は、転送後にACKフラグを未確認に設定するステップと、再送時間を所定時間に設定するステップと、をさらに含む。
【0020】
本方法は、再送カウンタを増加させるステップをさらに含む。
【0021】
前記メッセージが以前に受信されたものである場合に、本方法は、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを下流ノードから受信したときに、前記再送時間を停止する工程をさらに含む。
【0022】
前記再送時間を停止した後に、ACKフラグを確認済みに設定される。
【0023】
本方法は、再送カウンタの値に基づいて、再送の上限に達したか判断するステップと、前記判断に基づいて、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、再送カウンタを増加させるステップと、再送後に前記再送時間を所定時間に設定するステップと、をさらに含む。再送の上限に達した場合には、再送時間が停止される。
【0024】
マルチキャストメッセージをルーティングするための別の方法も開示される。本方法は、少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、前記メッセージが以前に受信したものであるか判断するステップと、を含み、前記メッセージが以前に受信されたものである場合に、前記Time−to−Live値にプリセット値を加えてオフセットTime−to−Live値を生成する工程と、前記オフセットTime−to−Live値と前記マルチキャスト転送テーブル内のTime−to−Live値を比較する工程と、前記オフセットTime−to−Live値が前記マルチキャスト転送テーブル内のTime−to−Live値以上である場合に、前記マルチキャストメッセージを破棄する工程と、を含む。
【0025】
前記マルチキャストメッセージが以前に受信したものではない場合に、本方法は、ACKフラグを未確認に設定する工程と、再送カウンタを増加させる工程と、再送時間を所定値に設定する工程と、マルチキャストメッセージを転送する工程と、を含む。
【0026】
前記オフセットTime−to−Live値が前記マルチキャスト転送テーブル内のTime−to−Live値よりも小さい場合に、本方法は、ACKフラグを確認済みに設
定する工程と、前記再送時間を停止する工程と、をさらに含む。
【0027】
本発明のこれらおよび他の特徴、利益や利点は、以下の図面を参照することによって明らかになる。なお、図面を通して、類似の参照符号は類似の構造を指している。
【図面の簡単な説明】
【0028】
【図1】図1は、マルチキャストメッセージ用に設定されたローカル・ピア・グループの例を説明する。
【図2】図2は、ハートビートメッセージの例を説明する。
【図3】図3は、メンバシップレポートメッセージの例を説明する。
【図4】図4は、本発明の第1の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図5】図5は、本発明の第1の実施形態に係る、転送ノードおよびマルチキャスト受信ノードのためのMPキャッシュテーブルの例を説明する。
【図6】図6は、本発明の第2の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図7】図7は、本発明の第2の実施形態に係るルーティング方法の例を説明する。
【図8】図8は、本発明の第3の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図9】図9は、本発明の第3の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図10】図10は、本発明の第3の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図11】図11は、本発明の第3の実施形態に係る、転送ノードのためのMPキャッシュテーブルの例を説明する。
【図12】図12は、本発明の第4の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図13】図13は、本発明の第4の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図14A】図14Aは、本発明の第4の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図14B】図14Bは、本発明の第4の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図15A】図15Aは、本発明の第4の実施形態に係る、転送ノードのためのMPキャッシュテーブルの例を説明する。
【図15B】図15Bは、本発明の第4の実施形態に係る、マルチキャスト受信ノードのためのMPキャッシュテーブルの例を説明する。
【図16】図16は、本発明の第5の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図17】図17は、本発明の第6の実施形態に係る、マルチキャスト受信ノードによるマルチキャストパケットのルーティング方法を説明する。
【図18】図18は、本発明の第7の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図19】図19は、本発明の第8の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図20】図20は、本発明の第9の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図21】図21は、本発明の第7〜第9の実施形態の係る、転送ノードのためのMPキャッシュテーブルの例を説明する。
【発明を実施するための形態】
【0029】
[定義]
「ノード」は、チャネルの決定・選択処理や以下の説明で記載される方法を実行するルータである。例えば、通信装置を備える移動車両はノードである。この出願では、ノードと移動車両は同じ意味で使われている。
【0030】
「マルチキャストメッセージ」は1つまたはそれ以上の宛先を持つメッセージである。詳細な説明では、マルチキャストメッセージはマルチキャストパケット(MP)と称される。「ホップ」はメッセージを中継するノードである。2ノード間、すなわち送信元と宛先の間の「ホップカウント」は、中継ノードの数に1を足したものに等しい。
【0031】
本発明によれば、ローカル・ピア・グループ(LPG)に組織化されたノードまたは移動車両は、マルチキャストルーティングテーブルを生成するために相対位置、一意の識別子、LPGに関する情報を交換する。後述するハートビートメッセージやメンバシップレポートメッセージのような制御パケット内の情報に基づいて、ルーティングテーブルが生成される。マルチキャストは、1つのマルチキャストセッションについて複数の送信元ノード700とマルチキャスト受信ノード20に対応する。
【0032】
LPG1は、近くの複数のノード10から動的に形成される。具体的には、第1のノードが無線信号をブロードキャストし、第1のノードの範囲内の他のノード10は、この無線信号を受信する能力がある。LPG1は無線通信範囲に基づいて形成されるので、LPG1内のノードは、固定インフラストラクチャを必要とせずに、1ホップまたはマルチホップで互いに通信できる。ハートビートメッセージおよびメンバシップレポートの送信に基づいて、LPG1は形成および維持される。
【0033】
図1は、マルチキャストメッセージ用に設定されたモードを持つLPG1を示す。マルチキャストを行うために、ノード10は、マルチキャスト受信ノードと転送ノード90の2つのグループに分けられる。マルチキャスト受信ノード20はマルチキャストメッセージの受信が意図されるノードである。転送ノード90はメッセージを転送する。LPG1内の全てのノード10は、転送ノードにもマルチキャスト受信ノード20にもなりうる。さらに、LPG1内の1つのノードがグループヘッダ(GH)として選択される。GHは、他のノードやインフラストラクチャからの命令なしにLPG1を維持および制御することを指定されたLPG1内の移動装置またはノード10である。ノード10は、メンバシップレポートをGHへ中継するために用いられるときに、FN90になる。LPG1の形成、維持、GHの選択、制御は’047出願に記載されており、その内容は参照により本明細書に含まれる。
【0034】
図2は、本発明に係るハートビートメッセージ200の例を示す。GHは、ハートビートメッセージ200を定期的に送出して、LPG1を識別(identify)するとともにLPG1に関する情報を提供する。この周期は固定間隔(T)である。この間隔(T)の値は、設計や運用の要求に基づいて選択可能である。GHは、LPG1に含まれる全ノードのリストの維持も行う。このリストには、ノードがLPG1に参加した時のタイムスタンプ、あるいは、GHがノードからステータス更新を受信した時のタイムスタンプが含まれる。このリストは、LPG1に対する種々の維持・管理機能のために用いられる。例えば、このリストは、グループサイズを追跡したり、マルチキャストルーティングテーブルを作成・更新したり、ヘッダ解決のために用いることができる。さらに、このリストは、LPG1内の他の全てのノードに周期的にブロードキャストされる。ハートビートメッセージ200がLPG1内の全ノード10にブロードキャストされる。
【0035】
ハートビートメッセージ200は、LPG1の識別子、GH ID、シーケンス番号、
ハートビートメッセージの種類(例えば、完全なグループリスト付きのハートビートか、増分(incremental)グループリスト付きのハートビートか、グループリストなしのハートビートか)を含む。ある実施形態では、ハートビートメッセージは全てのパケットにおいて完全なグループリストを含む。完全なグループリストを使うことが、ルーティング制御と正しいグループメンバのリストを維持するための最も正確な方法であるが、完全なグループ付きのハートビートのためには相当量の帯域幅が必要となる。別の実施形態では、ハートビートメッセージ200は、n回おきに完全なグループリストを含む。例えば、3回おきにハートビートが完全なグループリストを含むようにする。ToHbは、ハートビートメッセージの種類を意味する。ハートビートメッセージの種類は、LPG1のトポロジー変化の早さとハートビートのブロードキャスト頻度の影響を受ける。LPG1のトポロジー変化速度が速くなると、全てのハートビートメッセージ200に完全なグループリストを含める必要性が高まる。
【0036】
ハートビートメッセージ200は、GHからのホップカウント(HC)も含む。最初は、HCは所定値、たとえば1に設定される。ハートビートメッセージ200がノードによって中継されるたびに、中継ノードがHC値を1増加させる。すなわち、HC=HC+1とする。HC値は、LPGのサイズを限定したり、ハートビートメッセージ200内の情報の古さを示したり、オーバヘッドを減らすための制御パケットのルーティングを制御したりするために用いることができる。各LPG1に対して、ルーティングの最大ホップカウント(例えば10)がある。HCが最大ホップカウントに達すると、その制御パケットはそれ以上中継されない。
【0037】
最大ホップカウント、HCおよびシーケンス番号を用いることで、LPG1内で制御パケットが無限に複製されることを防止できる。ホップカウントは中継戦略のためにも利用される。ノードがハートビートメッセージを転送するときにメッセージにID情報を含めるので、次ホップのノードは、このハートビートメッセージ200を誰が中継するのかを知ることができる。
【0038】
上述したように、ハートビートメッセージ200はグループリストも含むことができる。グループリストは、LPG1のメンバに関する情報を含むことができる。たとえば、LPG1内のメンバ数、各メンバのIPアドレス、GHからのホップカウントや分類などである。
【0039】
分類は、たとえばアップリンク、ダウンリンク、ピアのような、GHからの相対的な方向を示すコードであり得る。ピア分類は、ノードがGHと同じ無線通信範囲内であることを示す。すなわち、全てのピアノードは、GHから同じホップカウントを有する。上流ノードはハートビートから決定される。下流ノードは、後述するメンバシップレポート(MR)300に基づいて決定される。上流送信はGH25に向かう方向の通信を意味し、下流送信はGH25からの離れる方向の通信を意味する。分類は相対的な用語である。各ノードはその近隣ノードを異なる3つの種類に分けることができる。他のノードのメンバシップレポートのホップカウント(HC)が自ノードのHCよりも1少なければ、自ノードは上流ノードである。そのHCが自身のHCと同じであれば、自ノードはピアである。そのHCが自身のHCよりも1大きければ、自ノードは下流ノードである。
【0040】
図3はメンバシップレポート(MR)300の例を示す。MR300はGH以外のノードからブロードキャストされる制御パケットであり、その受取人はGH25である。MR300は、ハートビートメッセージ200に対する応答として生成される。MR300は、メンバシップリスト、下流ノードID、下流ノードに対する次ホップのような収集可能なルーティング情報を含む。MR300は、GIDやグループヘッダIDのような、ハートビートメッセージ200と同じ情報のいくつかを含む。MR300は、MRシーケンス
番号も含む。MRシーケンス番号は、ハートビートメッセージ200のシーケンス番号と同様のものであり、MRの順序を維持するために用いられる。MRシーケンス番号はある特定のノードに対するMRの順序である。典型的には、MRシーケンス番号は、MR300のきっかけとなったハートビートメッセージ200のシーケンス番号と同じ値を有する。
【0041】
MR300には、発信元ノード、すなわち、MR300を生成したノードのノードIDも含まれる
【0042】
MR300は次ホップ中継IDも含む。次ホップ中継IDは、GHへ向かうMR300に対する中継の指示である。次ホップの情報は、受信したハートビートメッセージ200から直接決定される。ノード10が新しいすなわち新規のハートビートメッセージ200を受信すると、何らかのパケット処理を行う前にIP層およびMAC層から直前の中継ノードのIDを取り戻す。直前の中継ノードのIDはメモリに格納され、MR300の次ホップ中継IDとして用いられる。ノード10がハートビートメッセージ200を転送するときは、ノード10は自身のIDをパケットに含める。これを受信する次ホップノードは、新しいすなわち新規のハードビートメッセージ200を受信すると、このIDをGH25に達するための次ホップ中継IDとして格納する。新しいすなわち最新のハートビートメッセージ200は、最も小さいHCと新しいシーケンス番号を有する。
【0043】
MR300は「MR標識の種類」ToMRも含む。MR300には、単一メンバレポートおよび複数集約メンバレポート(aggregated multiple member report)の2つの種類がある。単一メンバMRは発信元ノードからのMR300のみを含む。複数集約メンバレポートは2つ以上のノードのMR300を含む。1つのMR300が複数のMRを含んで送られる。
【0044】
さらに、MR300はGHからのホップカウント(HCGH)を含んでも良い。(HCGH)は、GHから発信ノードまでのMR300のHC値である。MR300は、報告ノードが利用可能なチャネルのリストを含む。さらに、MRは、MR300をGHに向かって中継した全ノードについての利用可能なチャネルのリストを含んでも良い。さらに、MR300は、その状態またはマルチキャストメッセージを中継可能であるか、すなわち転送ノードステータスを含む。
【0045】
マルチキャストルーティングテーブルは、マルチキャストセッションが開始された後に、ハートビートメッセージ200およびMR300から作成される。マルチキャストルーティングテーブルは木構造またはメッシュとして視覚化するのが最も適切といえる。木構造またはメッシュは、任意の送信元ノード700からFNを介してマルチキャスト受信ノード20に至る経路またはリンクを提供する。マルチキャストセッションを確立するために、マルチキャストセッションに参加したいノード10はマルチキャストセッションに対応したマルチキャストアプリケーションプログラムを起動する。このアプリケーションプログラムはメモリに格納される。そして、ノードはFNかマルチキャスト受信ノードになり、セッション参加の要求を示す信号(MR300)を発する。これらの信号によって、マルチキャストセッションに対するマルチキャストツリーの生成が開始される。
【0046】
ノードがMR300をGHに向かって中継すると、そのノードはマルチキャストグループのFN90になる。FN90は、ここで説明される1つまたはそれ以上の方法によって、マルチキャストセッションに関連づけられたマルチキャストパケットを受け付けて転送することができる。木構造またはメッシュ、すなわちマルチキャストルーティングテーブルは、ここに参照によって明示的に組み入れられる’047出願において説明されるいずれかの方法を用いて作成される。マルチキャストルーティングテーブルは、ハートビート
期間ごとに更新される。マルチキャストパケットはマルチキャストルーティングテーブルを用いて経路が定められる。
【0047】
図4は、本発明の第1の実施形態に係るマルチキャストルーティング方法を示す。本ルーティング方法を、その機能ブロックを用いて説明する。異なる実施形態における同一の機能ブロックは、同一の番号を用いて参照される。
【0048】
ブロック400で、マルチキャストパケットがノードに到着する。ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10は、FN90かマルチキャスト受信ノード20のいずれかであれば、マルチキャストセッションのメンバである。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック415で、ノード10は、MPキャッシュテーブル(例えば図5、500)内に、受信したマルチキャストパケットと一致するものがあるか探す。本発明の第1の実施形態では、MPキャッシュテーブル500はFN90とマルチキャスト受信ノード20の両方に対して同一である。MPキャッシュテーブル500は、グループ識別子、送信元識別子、つまりマルチキャストパケットの元々の送信元ノード700、およびシーケンス番号を含む。パケットのシーケンス番号と送信元識別子の両方が同じであれば、マルチキャストパケットは受信パケットと同一である。マルチキャストパケットが同一であれば、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。
【0049】
マルチキャストパケットがMPキャッシュテーブル500内のいずれのパケットとも一致しない場合は、ブロック420で、ノード10は、グループ識別子、送信元識別子、マルチキャストパケットの順番のようなマルチキャストに関連する情報をMPキャッシュテーブル500に追加する。マルチキャストパケットがMPキャッシュテーブル500に加えられると、ブロック425で、ノード10はマルチキャストセッションのFN90であるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのFN90でなければ、ブロック430で、マルチキャストパケットは破棄される。その後、ブロック440でノード10はアイドルになる。
【0050】
ノード10がマルチキャストセッションのFN90であれば、ブロック435で、ノードはマルチキャストパケットをN回再マルチキャストすなわち転送する。ある実施形態では、FN90はマルチキャストパケットをN回連続して転送する。パケットが転送される数字「N」回は予め定められていて変更可能である。到達率の増加とデータオーバヘッドの増加にはトレードオフがある。数字「N」が増えるにしたがって、データオーバヘッドが著しく増加するが、到達率もまた増加する。別の実施形態では、FN90はパケットをN回同時に転送する。
【0051】
マルチキャストパケットを転送した後、ブロック440で、FN90はアイドルになる。
【0052】
図5は、本発明の第1の実施形態におけるMPキャッシュテーブル500の例を示す。図5に示すように、MPキャッシュテーブル500は、IPアドレスのようなセッションやグループの識別子である追加グループ(GroupAdd)、マルチキャストパケットの送信元ノード700の識別子である送信元識別子、およびパケットのシーケンス番号(SeqNum)を含む。
【0053】
図6は、本発明の第2の実施形態に係るマルチキャストルーティング方法を示す。ブロ
ック400で、マルチキャストパケットがノード10に到着する。ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10は、FN90かマルチキャスト受信ノード20のいずれかであれば、マルチキャストセッションのメンバである。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック415で、ノード10は、MPキャッシュテーブル内に、受信したマルチキャストパケットと一致するものがあるか探す。本発明の第2の実施形態では、MPキャッシュテーブル500はFN90と受信ノードの両方に対して同一である。MPキャッシュテーブル500は、グループ識別子、送信元識別子、およびシーケンス番号を含む。パケットのシーケンス番号と送信元識別子の両方が同じであれば、マルチキャストパケットは受信パケットと同一である。マルチキャストパケットが同一であれば、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。
【0054】
マルチキャストパケットがMPキャッシュテーブル500内のいずれのパケットとも一致しない場合は、ノード10は、ブロック420で、受信したマルチキャストパケットについての情報をMPキャッシュテーブル500に追加する。マルチキャストパケットに関連する情報がMPキャッシュテーブル500に加えられると、ブロック425で、ノード10はマルチキャストセッションのFN90であるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がFN90であれば、ブロック605で、ノード10はマルチキャストパケットを一度転送する。ブロック440で、ノード10はアイドルになる。
【0055】
ノード10がFN90でなければ、ノード10はマルチキャスト受信ノード20である。本実施形態によれば、FN90による通常の転送に加えて、いくつかのマルチキャスト受信ノード20がマルチキャストパケットの転送のために選択される。この追加的な転送によって、マルチキャストセッションのメンバがパケットを受信し損ねる可能性が抑えられる。受け取ったマルチキャストデータパケットごとに割り当てられる確率に基づいて、いくつかのマルチキャスト受信ノード20が選択される。各マルチキャスト受信ノード20は確率閾値とともにプログラムされる。確率閾値は0と1の間の値である。確率閾値は、複数のマルチキャスト受信ノード20について同じではない。ある実施形態では、確率閾値はランダムにプログラムされる。別の実施形態では、確率閾値は、LPG1内のノード10の数またはマルチキャストセッション内のノード数に基づいて割り当てられる。言い換えると、確率閾値は周期的に変化しても良い。ある実施形態では、マルチキャストセッションの送信元ノード700が確率閾値を割り当てても良い。代替として、GHが確率閾値を割り当てても良い。
【0056】
ブロック600で、マルチキャスト受信ノード20であるノード10は、マルチキャストパケットに割り当てられたランダムな確率と、確率閾値とを比較する。マルチキャストパケットに割り当てられたランダムな確率が確率閾値よりも小さければ、ブロック605で、マルチキャスト受信ノードは受信したマルチキャストパケットを転送する。そして、ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0057】
マルチキャストパケットに割り当てられたランダムな確率が確率閾値以上であれば、ブロック430で、マルチキャスト受信ノード20は受信したマルチキャストパケットを破棄する。そして、ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0058】
図7は、本発明の第2の実施形態に係る方法を実行するマルチキャストセッションの例を示す。送信元ノード700がマルチキャストセッションを開始し、マルチキャストパケ
ットをマルチキャストする。FN1 901、FN2 902、およびFN3 903は、マルチキャストパケットを受信した後に、ブロック605で、マルチキャストパケットを転送する。マルチキャスト受信ノード201、202、203はマルチキャストデータパケットを転送せずにマルチキャストパケットを破棄する(ブロック430)。しかしながら、マルチキャスト受信ノード204、205、206は、マルチキャストパケットを転送する(ブロック605)。MPキャッシュテーブルは本発明の第1の実施形態と同様である(例えば、500)。MPキャッシュテーブル500は、FN90とマルチキャスト受信ノード20の両方に対して同一である。
【0059】
図8〜図10は、本発明の第3の実施形態に係るルーティング方法を示す。本発明の第3の実施形態によれば、次ホップノードは転送されたマルチキャストパケットの受信通知を行う。この受信通知(acknowledgement)はパッシブ受信通知方式をとる。FN90によって転送されたマルチキャストパケットは、その次ホップFNによって転送されたマルチキャストパケットによって受信通知が行われる。次ホップFNから転送されたマルチキャストパケットは、傍受(overheard)される。
【0060】
ブロック400で、マルチキャストパケットがノード10に到着する。マルチキャストパケットは、マルチキャストグループID、シーケンス番号、Time−to−Live(TTL)値、およびデータを含む。TTL値は、マルチキャストパケットが中継されるホップ数である。各ホップで、FN90はTTL値を減少させる。TTL値は、同一のマルチキャストデータパケットが転送させる回数を制限する機能を果たす。
【0061】
ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック800で、ノード10はFN90かマルチキャスト受信ノードであるかを判断する。ノード10がマルチキャスト受信ノードであれば、処理は図10のブロック415に移動する。ノード10がマルチキャストセッションのFN90であれば、ブロック415(図8)で、FN90はマルチキャストパケットがMPキャッシュテーブル(例えば、図11、500a)内にあるか判断する。
【0062】
マルチキャストパケットがMPキャッシュテーブル500a内のいずれのパケットとも一致しない場合は、ブロック420で、FN90は受信したマルチキャストパケットをMPキャッシュテーブル500aに追加する。この実施形態では、マルチキャストパケットに関連する情報とパケットの両方がMPキャッシュテーブル500aに追加される。
【0063】
FN90は、マルチキャストグループID、シーケンス番号、送信元識別子、Time−to−Live(TTL)値、およびデータを抽出し、この情報をMPキャッシュテーブル500aに付加する。さらに、FN90は再送カウンタをゼロに初期化する。再送カウンタ(s_mp_c)は、マルチキャストパケットが再送されうる回数を表す。ある実施形態では、マルチキャストメッセージが再送される回数はあらかじめ定められた最大値に制限される。あらかじめ定められた最大値は全ノード10に対して同じであっても良い。別の実施形態では、あらかじめ定められた最大値はGHや送信元ノード700のような特定のノードに対して変更可能としても良い。
【0064】
MPキャッシュテーブルはFN90とマルチキャスト受信ノードとで異なる。FN90用には、MPキャッシュテーブル500は、マルチキャストパケットについてのマルチキャストセッションID、送信元識別子、シーケンス番号、マルチキャストパケットデータ
、ACK状態、再送タイマ値、再送カウンタ、およびTTL値を含む。ACK状態は「未確認」または「確認済み」のいずれかであり得る。再送タイマ値はオンかオフのいずれかであり得る。タイマがオンであれば、再送タイマ値は初期設定タイマ値といつ再送タイマ値が満了したかの指示も含む。マルチキャスト受信ノード20用には、MPキャッシュテーブル500は、マルチキャストセッションID、送信元識別子、およびシーケンス番号だけを含む。
【0065】
ブロック805で、FN90はACK状態を「未確認」に初期化する。FN90はどのマルチキャストパケットが受信確認され受信されたかを追跡できる。さらに、FN90は再送タイマ値をオンに初期化し、タイマを再送時間に設定する。再送時間は、データパケットに含まれるデータの種類、FN90の移動速度、およびその他のユーザ定義の基準に応じて変更可能である。例えば、12msの再送時間を利用することができる。メッセージに含まれるデータが高い優先度のメッセージであれば、再送時間を短くしても良い。あるいは、メッセージが低い優先度のメッセージであれば、再送時間を長くしても良い。回復遅延は再送時間の値に依存する。再送時間が小さいほど、遅延は短くなる。しかしながら、小さくしすぎると多くの再送信が発生し、不必要な再送信が生じる。
【0066】
ブロック810で、再送カウンタが1増分する。すなわちs_mp_c+1にする。再送カウンタが増分された後、ブロック605で、FN90はマルチキャストパケットを一度転送する。FN90は、転送の前にマルチキャストパケットのTTL値から1減算する。したがって、次ホップFNによって受信されるマルチキャストパケットは、最小のTTL値を持つ。ブロック440で、FN90はアイドルになる。
【0067】
マルチキャストパケットがMPキャッシュテーブル500a内のいずれかのパケットと同一であれば、本方法はブロック815へ進む。
【0068】
FN90は入力マルチキャストパケットのTTL値を判断する。上記したようにTTL値は特定のマルチキャストパケットのホップ数を制御するために用いられる。さらにこの実施形態では、TTL値は送信ノード10および受信ノード10の相対的な位置を決定するためにも用いられる。具体的には、マルチキャストパケットが転送されるたびに、ノード10はTTL値から1減算する(すなわち、TTL−1)。特定のFN90から下流にあるノード10から受信されたマルチキャストパケットのTTL値は、FN90から転送された同一のマルチキャストパケットのTTL値よりも小さい。特定のFN90から上流にあるノード10から受信されたマルチキャストパケットのTTL値は、FN90から転送された同一のマルチキャストパケットのTTL値よりも大きい。特定のFN90と同じホップ数のノード10から受信されたマルチキャストパケットは、同一のTTL値を持つ。
【0069】
FN90は、FN90による最初のマルチキャストパケットの転送を補うために、判定されたTTL値にオフセット値の1を加える。これによりオフセットTTL値が生成される。
【0070】
ブロック815で、FN90は、入力パケットのオフセットTTL値(In_MP_TTL+1)と同一のマルチキャストパケットのTTL値とを比較する。同一のマルチキャストパケットのTTL値は、MPキャッシュテーブル500aから取り出される。MPキャッシュテーブル500aから取り出されたTTL値がオフセット値よりも大きくない場合は、ブロック430で、入力マルチキャストパケットは無視されて破棄される。このマルチキャストパケットは上流ノードから発生したものである。マルチキャストパケットの転送は受信確認されない。ブロック440で、FN90はアイドルになる。
【0071】
ブロック815においてMPキャッシュテーブルから取り出されたTTL値がオフセット値よりも大きい場合は、ブロック820で、FN90はこのマルチキャストパケットがすでに受信確認されたか判断する。
【0072】
FN90はMPキャッシュテーブル500aから同一のマルチキャストパケットについてのACK状態を取り出す。同一のマルチキャストパケットがすでに受信確認されていれば、ブロック430で、入力マルチキャストパケットは無視されて破棄される。ブロック440で、FN90はアイドルになる。MPキャッシュテーブル500aに変更はない。ブロック820において同一のマルチキャストパケットが受信確認されていなければ、本方法はブロック825へ進む。
【0073】
ブロック825で、FN90は再送タイマを停止する。さらに、FN90は、キャッシュテーブル500a内の再送タイマ値を「オフ」に変え、ACK状態を「確認済み」に変える。その後、ブロック430で入力マルチキャストパケットは破棄される。ブロック440で、FN90はアイドルになる。マルチキャストパケット転送の受信が確認される。
【0074】
図9は、マルチキャストパケットの転送が受信確認される前に再送タイマが満了する場合の機能ブロック図を示す。図9に示される機能ブロック図はFN90によってのみ実行される。
【0075】
ブロック900で、再送タイマが満了する。FN90は、再送カウンタが最大閾値に達したか判断する。FNは、再送タイマが満了したパケットに対応するマルチキャストパケットの再送カウンタをMPキャッシュテーブル500aから抽出する。再送カウンタは、最大閾値と比較される。再送カウンタが最大閾値以上であれば、FN90はブロック440でアイドルになる。
【0076】
再送カウンタが最大閾値より小さければ、ブロック805で、FN90はマルチキャストパケットの送信タイマをリセットし、マルチキャストパケットのACK状態を「未確認」に初期化する(図9において「Not ACKed」と示される)。
【0077】
ブロック810で、再送カウンタが1増分する。すなわちs_mp_c+1にする。再送カウンタが増分された後、ブロック605で、FN90はマルチキャストパケットを一度転送する。FN90は、転送の前にマルチキャストパケットのTTL値から1減算する。したがって、次ホップFNはマルチキャストパケットを送っているFN90よりも小さいTTLを持つマルチキャストパケットを受信する。ブロック440で、FN90はアイドルになる。
【0078】
図10は、本発明の第3の実施形態に係るマルチキャスト受信ノード20の機能ブロックを示す。図8に示すように、ブロック800においてノード10がFN90でなければ、処理は図10のブロック415に進む。ブロック415で、マルチキャスト受信ノード20は、入力マルチキャストパケットがMPキャッシュテーブル500にリストされているか判断する。マルチキャストパケットがすでにリストされていれば、ブロック430で、パケットは無視されて破棄される。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0079】
マルチキャストパケットがMPキャッシュテーブル500内のいずれのパケットとも一致しない場合は、マルチキャスト受信ノード20は、ブロック420で、入力マルチキャストパケットについての情報をMPキャッシュテーブル500に追加する。具体的には、マルチキャスト受信ノード20は、マルチキャストパケットのマルチキャストセッションID、送信元識別子、およびシーケンス番号をMPキャッシュテーブル500に追加する
。その後、ブロック430で、マルチキャストパケットは破棄される。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0080】
図11は、本発明の第3の実施形態に係るFN用のMPキャッシュテーブル500aの例を示す。図示されるように、MPキャッシュテーブル500aは、2つの異なるマルチキャストパケット(MP1とMP2)を含む。各マルチキャストパケットに対して、MPキャッシュテーブル500aは、マルチキャストセッションID(GroupAdd)、マルチキャストパケットの送信元識別子、マルチキャストパケットのシーケンス番号(SeqNum)、マルチキャストパケットデータ(MPキャッシュ)、受信確認状態(ACK状態)、再送タイマ(Retran_Timer)、再送カウンタ(s_mp_c)、およびマルチキャストパケットのTTL値(C_MP_TTL)を含む。図11に示されるように、マルチキャストパケットの1つは受信確認されており、したがって再送タイマ状態は「オフ」である。
【0081】
図12〜図14(AおよびB)は、本発明の第4の実施形態に係るルーティング方法を示す。この実施形態によれば、マルチキャスト受信ノード20は受信し損ねたマルチキャストパケットを局所的に回復することができる。マルチキャスト受信ノード20は否定的確認(negative acknowledgement)を用いて、他のノード10にマルチキャストパケットを受信していないことを通知する。受信し損ねたマルチキャストパケットは、受信パケットにおける欠落しているシーケンス番号に基づいて検出される。この検出は受信したマルチキャストパケットの間でのシーケンス番号の比較に基づく。
【0082】
ブロック400で、マルチキャストパケットがノード10に到着する。マルチキャストパケットはマルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを含む。TTL値は、マルチキャストパケットが中継されるホップ数である。各ホップで、FN90はTTL値を減少させる。TTL値は、同一のマルチキャストデータパケットが転送させる回数を制限する機能を果たす。
【0083】
ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック800で、ノード10はFN90かマルチキャスト受信ノードであるかを判断する。ノード10がマルチキャスト受信ノード20であれば、処理は図13のブロック415に移動する。
【0084】
ブロック415で、マルチキャスト受信ノード20は、MPキャッシュテーブル(例えば、図15B、500c)内に入力マルチキャストパケットがリストされているか判断する。
【0085】
マルチキャストパケットがMPキャッシュテーブル500c内のいずれのパケットとも一致しない場合は、マルチキャスト受信ノード20は、受信したマルチキャストパケットについての情報をMPキャッシュテーブル500cに追加し、ブロック1300でマルチキャストパケットが不足していないか判断する。マルチキャスト受信ノード20は、マルチキャストセッションID、送信元識別子、シーケンス番号、およびマルチキャストパケットデータをMPキャッシュテーブル500cに追加する。マルチキャスト受信ノード500cのMPキャッシュテーブル500cは、ネガティブACK再送タイマ(NACK再送タイマ:NACK_Retran_Timer)も含む。NACK再送タイマは、近くのFN90やマルチキャスト受信ノード20から同一のマルチキャストパケットが複数回再送信される回数を抑制または制限するために用いられる。
【0086】
NACK再送タイマの時間は、ノード数、データパケットに含まれるデータの種類、ノード10の移動速度、およびその他のユーザ定義の基準に応じて変更可能である。例えば、12msの再送時間を利用することができる。メッセージに含まれるデータが高い優先度のメッセージであれば、再送時間を短くしても良い。あるいは、メッセージが低い優先度のメッセージであれば、再送時間を長くしても良い。回復遅延は再送時間の値に依存する。再送時間が小さいほど、遅延は短くなる。しかしながら、小さくしすぎると多くの再送信が発生し、不必要な再送信が生じる。
【0087】
マルチキャスト受信ノード20は、受信した全てのマルチキャストパケットについてシーケンス番号を調べることで、受信し損ねたマルチキャストパケットを検出する。検出はブロック1305で行われる。例えば、マルチキャスト受信ノード20がシーケンス番号10、11、13のマルチキャストパケットを受信した場合、シーケンス番号12のマルチキャストパケットが抜けている。
【0088】
ブロック1305においてマルチキャストパケットが抜けている場合、マルチキャスト受信ノード20は、ブロック1310で、ネガティブACK(NACK)をマルチキャストする。
【0089】
NACKは、抜けているマルチキャストパケットのマルチキャストセッションID、送信元識別子、およびシーケンス番号を含む。その後、ブロック430で、入力マルチキャストパケットは破棄される。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0090】
ブロック1305でマルチキャストパケットが抜けている場合、ブロック430で、マルチキャスト受信ノード20は入力マルチキャストパケットを棄てる。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0091】
ブロック415においてマルチキャストパケットがMPキャッシュテーブル500c内のいずれかのパケットと同一であれば、ブロック1200で、マルチキャスト受信ノード20はマルチキャストパケットのNACK再送タイマが「オン」であり満了していないか判断する。この判断はMPキャッシュテーブル500cからの情報に基づく。(ブロック1200において)NACK再送タイマがオンであれば(図12に示す機能ブロックと同じ)、ブロック1205でNACK再送タイマは停止される(図12に示す機能ブロックと同じ)。マルチキャスト受信ノード20は、NACK再送タイマの状態を「オフ」に変更する。これは、同一のマルチキャストが不必要に再送信されるのを抑制するために行われる。そしてブロック430で、マルチキャスト受信ノード20入力マルチキャストパケットを棄てる。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0092】
NACK再送タイマが(ブロック1200において)「オフ」であれば、ブロック430で、マルチキャスト受信ノード20は入力マルチキャストパケットを棄てる。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0093】
図12に戻って、ブロック800においてノード10がFN90であれば、処理はブロック415(図12)へ進む。
【0094】
マルチキャストパケットがMPキャッシュテーブル(図15A、500b)内のいずれのパケットとも一致しない場合は、ブロック420で、FN90は受信したマルチキャストパケットをMPキャッシュテーブル500bに追加する。
【0095】
FN90は、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを抽出し、この情報をMPキャッシュテーブル500bに追加する。さらに、FN90は再送カウンタをゼロに初期化する。再送カウンタ(s_mp_c)は、マルチキャストパケットが再送されうる回数を表す。ある実施形態では、マルチキャストメッセージが再送される回数はあらかじめ定められた最大値に制限される。あらかじめ定められた最大値は全ノード10に対して同じであっても良い。別の実施形態では、あらかじめ定められた最大値はGHや送信元ノード700のような特定のノードに対して変更可能としても良い。
【0096】
MPキャッシュテーブルはFN90とマルチキャスト受信ノード20とで異なる。FN90用には、MPキャッシュテーブル500bは、マルチキャストパケットについてのマルチキャストセッションID、送信元識別子、シーケンス番号、マルチキャストパケットデータ、ACK状態、再送タイマ値、再送カウンタ、TTL値、およびネガティブACK再送タイマ(NACK再送タイマ)を含む。ACK状態は「未確認」または「確認済み」のいずれかであり得る。再送タイマ値はオンかオフのいずれかであり得る。タイマがオンであれば、再送タイマ値は初期設定タイマ値といつ再送タイマ値が満了したかの指示も含む。マルチキャスト受信ノード20用には、MPキャッシュテーブル500cは、マルチキャストセッションID、送信元識別子、およびシーケンス番号だけを含む。
【0097】
ブロック805で、FN90はACK状態を「未確認」に初期化する。FN90はどのマルチキャストパケットが受信確認され受信されたかを追跡できる。さらに、FN90は再送タイマ値をオンに初期化し、タイマを再送時間に設定する。再送時間は、データパケットに含まれるデータの種類、FN90の移動速度、およびその他のユーザ定義の基準に応じて変更可能である。
【0098】
ブロック810で、再送カウンタを1増分する。すなわちs_mp_c+1にする。再送カウンタが増分された後、ブロック605で、FN90はマルチキャストパケットを一度転送する。FN90は、転送の前にマルチキャストパケットのTTL値から1減算する。したがって、次ホップFNはマルチキャストパケットを送っているFN90よりも小さいTTL値を含むマルチキャストパケットを受信する。ブロック440で、FN90はアイドルになる。
【0099】
ブロック415においてマルチキャストパケットがMPキャッシュテーブル500c内のいずれかのパケットと同一であれば、ブロック1200で、マルチキャスト受信ノード20はNACK再送タイマが「オン」であり満了していないか判断する。この判断はMPキャッシュテーブル500cからの情報に基づく。(ブロック1200において)NACK再送タイマがオンであれば、ブロック1205でNACK再送タイマは停止される。マルチキャスト受信ノード20は、NACK再送タイマの状態を「オフ」に変更する。これは、同一のマルチキャストが不必要に再送信されるのを抑制するために行われる。
【0100】
NACK再送タイマが(ブロック1200において)「オフ」であれば、処理はブロック815へ進む。
【0101】
ブロック815で、FN90は同一のマルチキャストパケットのオフセットTTL値(In_MP_TTL+1)とTTL値とを比較する。同一のマルチキャストパケットのTTL値はMPキャッシュテーブル500bから取り出される。MPキャッシュテーブル500bから取り出されたTTL値がオフセット値よりも大きくない場合は、ブロック430で、入力マルチキャストパケットは無視されて破棄される。このマルチキャストパケットは上流ノードから発生したものである。マルチキャストパケットの転送は受信確認されない。ブロック440で、FN90はアイドルになる。
【0102】
ブロック815においてMPキャッシュテーブル500bから取り出されたTTL値がオフセット値よりも大きい場合は、ブロック820で、FN90はこのマルチキャストパケットがすでに受信確認されたか判断する。
【0103】
FN90はMPキャッシュテーブル500bから同一のマルチキャストパケットについてのACK状態を取り出す。同一のマルチキャストパケットがすでに受信確認されていれば、ブロック430で、入力マルチキャストパケットは無視されて破棄される。ブロック440で、FN90はアイドルになる。MPキャッシュテーブル500bに変更はない。ブロック820において同一のマルチキャストパケットが受信確認されていなければ、本方法はブロック825へ進む。
【0104】
ブロック825で、FN90は再送タイマを停止する。さらに、FN90は、キャッシュテーブル500b内の再送タイマ値を「オフ」に変え、ACK状態を「確認済み」に変える。その後、ブロック430で入力マルチキャストパケットは破棄される。ブロック440で、FN90はアイドルになる。マルチキャストパケット転送の受信が確認される。
【0105】
図14Aは、NACKを処理する機能ブロックを示す。NACK処理の動作プロセスは、FN90とマルチキャスト受信ノードとで同じである。
【0106】
ブロック1400で、ノード10はNACKパケットを受信する。ノード10は、受信パケットに含まれる情報に基づいてそのパケットがNACKパケットであるか判断する。次にブロック405で、ノード10は、マルチキャストの参加者、すなわちFN90またはマルチキャスト受信ノード20であるか判断する。
【0107】
ブロック405で、ノード10は受信したNACKパケットからマルチキャストグループIDを抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにそのパケットのNACKは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック415で、ノード10はマルチキャストパケットがMPキャッシュテーブル(500bまたは500c)にあるか判断する。例えば、マルチキャストパケットの情報エントリがMPキャッシュテーブル(500bまたは500c)にリストされているか確認する。
【0108】
ブロック415においてマルチキャストパケットがMPキャッシュテーブル内のいずれかのパケットと同一であれば、ブロック1200で、ノード10はNACK再送タイマが「オン」であるか判断する。この判断はMPキャッシュテーブル(500bまたは500c)からの情報に基づく。NACK再送タイマが(ブロック1200で)オンであれば、ブロック440で、ノード10はアイドルになる。反対に、NACK再送タイマが(ブロック1200で)「オフ」であれば、ブロック1405で、ノード10はNACK再送タイマを所定値に設定する。言い換えると、ノード10はNACK再送タイマの状態を「オン」に変える。NACK再送タイマはNACK期間の計時を開始する。
【0109】
図14Bは、NACK再送タイマが満了した際のマルチキャストパケットの再送の機能ブロックを示す。ブロック1410で、NACK再送タイマが満了する。ノード10はNACK再送タイマの状態を「オフ」に変える。ブロック605で、ノード10はマルチキャストパケットを再送または転送する。ブロック440で、ノード10はアイドルになる。
【0110】
図15Aは、本発明の第4の実施形態に係るFN90のMPキャッシュテーブル500bの例を示す。図示されるように、MPキャッシュテーブル500bは、2つの異なるマルチキャストパケット(MP1とMP2)を含む。各マルチキャストパケットに対して、MPキャッシュテーブル500bは、マルチキャストセッションID(GroupAdd)、送信元識別子、マルチキャストパケットのシーケンス番号(SeqNum)、マルチキャストパケットデータ(MPキャッシュ)、受信確認状態(ACK状態)、再送タイマ(Retran_Timer)、再送カウンタ(s_mp_c)、マルチキャストパケットのTTL値(C_MP_TTL)、およびネガティブACK再送タイマ(NACK再送タイマ)を含む。図15Aに示されるように、NACK再送タイマはマルチキャストパケットの一方についてオンである。
【0111】
図15Bは、本発明の第4の実施形態に係るマルチキャスト受信ノードのMPキャッシュテーブル500Cの例を示す。図示されるように、MPキャッシュテーブル500bは、2つの異なるマルチキャストパケット(MP1とMP2)を含む。各マルチキャストパケットに対して、MPキャッシュテーブル500cは、マルチキャストセッションID(GroupAdd)、送信元識別子、マルチキャストパケットのシーケンス番号(SeqNum)、およびネガティブACK再送タイマ(NACK再送タイマ)を含む。
【0112】
図16は、本発明の第5の実施形態に係るルーティング方法を示す。本発明の第5の実施形態は、マルチキャストパケットが複数回中継される点を除いて、第3の実施形態と同様である。
【0113】
ブロック400で、マルチキャストパケットがノード10に到着する。マルチキャストパケットは、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを含む。TTL値は、マルチキャストパケットが中継されるホップ数である。
【0114】
ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック800で、ノード10はFN90かマルチキャスト受信ノードであるかを判断する。ノード10がマルチキャスト受信ノード20であれば、処理は図10の機能ブロック415へ進む。ノード10がマルチキャストセッションのFN90であれば、ブロック415(図16)で、FN90はマルチキャストパケットがMPキャッシュテーブル(例えば、500a)内にあるか判断する。
【0115】
マルチキャストパケットがMPキャッシュテーブル500a内のいずれのパケットとも一致しない場合は、ブロック420で、FN90は受信したマルチキャストパケットをキャッシュテーブル500aへ追加する。
【0116】
FN90は、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを抽出し、この情報をMPキャッシュテーブル500aに追加する。さらに、FN90は再送カウンタをゼロに初期化する。再送カウンタ(s_mp_c)は、マルチキャストパケットが再送されうる回数を表す。第3の実施形態と同様に、MPキャッシュテーブルはFN90とマルチキャスト受信ノードとで異なる。MPキャッシュテーブル(例えば、500aおよび500)は、第3の実施形態と同一の情報を含む。
【0117】
ブロック805で、FN90はACK状態を「未確認」に初期化する。FN90はどのマルチキャストパケットが受信確認され受信されたかを追跡できる。さらに、FN90は再送タイマ値をオンに初期化し、タイマを再送時間に設定する。再送時間は、データパケットに含まれるデータの種類、FN90の移動速度、およびその他のユーザ定義の基準に応じて変更可能である。
【0118】
ブロック810で、再送カウンタが1増分する。すなわちs_mp_c+1にする。再送カウンタが増分された後、ブロック605で、FN90はマルチキャストパケットをN回転送する。ある実施形態では、FN90はマルチキャストパケットをN回連続して転送する。パケットが転送される数字「N」回は予め定められていて変更可能である。到達率の増加とデータオーバヘッドの増加にはトレードオフがある。数字「N」が増えるにしたがって、データオーバヘッドが著しく増加するが、到達率もまた増加する。別の実施形態では、FN90はパケットをN回同時に転送する。
【0119】
FN90は、転送の前にマルチキャストパケットのTTL値から1減算する。したがって、次ホップFNはマルチキャストパケットを送っているFN90よりも小さいTTL値を含むマルチキャストパケットを受信する。ブロック440で、FN90はアイドルになる。
【0120】
マルチキャストパケットがMPキャッシュテーブル500a内のいずれかのパケットと同一であれば、本方法はブロック815へ進む。
【0121】
FN90は入力マルチキャストパケットのTTL値を判断する。上記したようにTTL値は特定のマルチキャストパケットのホップ数を制御するために用いられる。さらにこの実施形態では、TTL値は送信ノード10および受信ノード10の相対的な位置を決定するためにも用いられる。具体的には、マルチキャストパケットが転送されるたびに、ノード10はTTL値から1減算する(すなわち、TTL−1)。特定のFN90から下流にあるノード10から受信されたマルチキャストパケットのTTL値は、FN90から転送された同一のマルチキャストパケットのTTL値よりも小さい。特定のFN90から上流にあるノード10から受信されたマルチキャストパケットのTTL値は、FN90から転送された同一のマルチキャストパケットのTTL値よりも大きい。特定のFN90と同じホップ数のノード10から受信されたマルチキャストパケットは、同一のTTL値を持つ。
【0122】
FN90は、FN90による最初のマルチキャストパケットの転送を補うために、判定されたTTL値にオフセット値の1を加える。これによりオフセットTTL値が生成される。
【0123】
ブロック815で、FN90は、オフセットTTL値(In_MP_TTL+1)と同一のマルチキャストパケットのTTL値とを比較する。同一のマルチキャストパケットのTTL値は、MPキャッシュテーブルから取り出される。MPキャッシュテーブルから取り出されたTTL値がオフセット値よりも大きくない場合は、ブロック430で、入力マルチキャストパケットは無視されて破棄される。このマルチキャストパケットは上流ノードから発生したものである。マルチキャストパケットの転送は受信確認されない。ブロック440で、FN90はアイドルになる。
【0124】
ブロック815においてMPキャッシュテーブル500aから取り出されたTTL値がオフセット値よりも大きい場合は、ブロック820で、FN90はこのマルチキャストパケットがすでに受信確認されたか判断する。
【0125】
FN90はMPキャッシュテーブル500aから同一のマルチキャストパケットについてのACK状態を取り出す。同一のマルチキャストパケットがすでに受信確認されていれば、ブロック430で、入力マルチキャストパケットは無視されて破棄される。ブロック440で、FN90はアイドルになる。MPキャッシュテーブル500aに変更はない。ブロック820において同一のマルチキャストパケットが受信確認されていなければ、本方法はブロック825へ進む。
【0126】
ブロック825で、FN90は再送タイマを停止する。さらに、FN90は、キャッシュテーブル500a内の再送タイマ値を「オフ」に変え、ACK状態を「確認済み」に変える。その後、ブロック430で入力マルチキャストパケットは破棄される。ブロック440で、FN90はアイドルになる。マルチキャストパケット転送の受信が確認される。
【0127】
残りの機能ブロックは図9および図10で示された機能ブロックと一致しているので、詳しくは説明しない。
【0128】
図17は、本発明の第6の実施形態に係るマルチキャスト受信ノード20の機能ブロックを示す。本発明の第6の実施形態は、本発明の第2および第3の実施形態の機能ブロックを組み合わせたものである。FN90の機能ブロックは図8および図9で示された機能ブロックと一致しているので、詳しくは説明しない。
【0129】
ブロック415で、マルチキャスト受信ノード20は、マルチキャストパケットがMPキャッシュテーブル(例えば、500a)内にあるか判断する。マルチキャストパケットがMPキャッシュテーブル500aないにあれば、ブロック430で、マルチキャストパケットは破棄される。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0130】
マルチキャストパケットがMPキャッシュテーブル500内に無い、すなわち、同一ではない場合は、マルチキャストパケットに含まれる情報がMPキャッシュテーブル500aに追加される。ブロック600で、マルチキャスト受信ノード20は、マルチキャストパケットに割り当てられたランダムな確率と、確率閾値とを比較する。マルチキャストパケットに割り当てられたランダムな確率が確率閾値よりも小さければ、ブロック605で、マルチキャスト受信ノード20は受信したマルチキャストパケットを転送する。そして、ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0131】
マルチキャストパケットに割り当てられたランダムな確率が確率閾値以上であれば、ブロック430で、マルチキャスト受信ノード20は受信したマルチキャストパケットを破棄する。そして、ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0132】
図18は、本発明の第7の実施形態に係るルーティング方法を示す。第7の実施形態によれば、、マルチキャストパケットの送信はあらかじめ定められた基準に基づいて抑制される。
【0133】
図18に示すように、マルチキャストパケットがノード10に到着する。マルチキャストパケットは、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを含む。TTL値は、マルチキャストパケットが中継されるホップ数である。
【0134】
ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメ
ンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック800で、ノード10はFN90かマルチキャスト受信ノードであるかを判断する。ノード10がマルチキャスト受信ノードであれば、処理はブロック415(受信者用)に移動する。ノード10がマルチキャストセッションのFN90であれば、ブロック415(FN90用)で、FN90はマルチキャストパケットがMPキャッシュテーブル(例えば、500d)内にあるか判断する。
【0135】
マルチキャストパケットがMPキャッシュテーブル500d内のいずれのパケットとも一致しない場合は、ブロック420で、FN90またはマルチキャスト受信ノード20は受信したマルチキャストパケットをMPキャッシュテーブル500dに付加する。
【0136】
FN90は、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを抽出し、この情報をMPキャッシュテーブル500dに付加する。さらに、FN90は再送カウンタをゼロに初期化する。再送カウンタ(s_mp_c)は、マルチキャストパケットが再送されうる回数を表す。この実施形態では、s_mp_cの値は「0」か「1」である。FN90のMPキャッシュテーブル500dはランダム転送タイマも含む。
【0137】
MPキャッシュテーブルはFN90とマルチキャスト受信ノード20とで異なる。マルチキャスト受信ノード20のMPキャッシュテーブル500dは、マルチキャストセッションID、送信元識別子、およびマルチキャストパケットのシーケンス番号を含む。したがって、ブロック420で、マルチキャスト受信ノード20は、マルチキャストセッションID、送信元識別子、およびシーケンス番号をMPキャッシュテーブル500に付加する。
【0138】
ブロック425で、ノード10はマルチキャストセッションのFN90であるか判断する。この判断は転送テーブルおよびMPキャッシュテーブル(例えば、500)内の情報に基づく。ノード10がマルチキャストパケットのFN90でなければ、ブロック419で、入力マルチキャストパケットは破棄される。ノードがFN90であれば、ブロック1800で、FNは転送タイマをランダム値に設定する。このランダム値によりマルチキャストパケットの転送が妨げられる。FN90は、ランダム値が満了、すなわちランダム転送タイマが満了したときのみマルチキャストパケットを転送する。
【0139】
ブロック415において、マルチキャストパケットがMPキャッシュテーブル500d内にすでに存在する場合は、ブロック1802で、FN90はこのパケットをすでに転送したか、すなわちs_mp_c=1であるか判断する。カウンタ(s_mp_c)が1に等しければ、パケットはすでに転送されている。カウンタ(s_mp_c)が0に等しければ、パケットはまだ転送されていない。FNはMPキャッシュテーブル500dからカウンタ値を取り出す。ブロック1802においてカウンタ(s_mp_c)が1に等しければ、ステップ430で、マルチキャストパケットは転送されることなく破棄される。ブロック1802で、カウンタ(s_mp_c)が0に等しければ、FN90は入力マルチキャストパケットのTTL値を判断する(ブロック815)。上記したように、TTL値は特定のマルチキャストパケットのホップ数を制御するために用いられる。さらに、この実施形態では、TTL値は送信ノード10および受信ノード10の相対的な位置を決定するためにも用いられる。FN90は、FN90による最初のマルチキャストパケットの転送を補うために、判定されたTTL値にオフセット値の1を加える。これによりオフセットTTL値が生成される。
【0140】
ブロック815で、FN90は、オフセットTTL値(In_MP_TTL+1)と同
一のマルチキャストパケットのTTL値とを比較する。同一のマルチキャストパケットのTTL値は、MPキャッシュテーブル500dから取り出される。MPキャッシュテーブル500dから取り出されたTTL値がオフセット値よりも大きくない場合は、(ブロック430で)入力マルチキャストパケットは破棄され、FN90はアイドルになる。このマルチキャストパケットは上流ノードまたはピアノードから発生したものである。ブロック815においてMPキャッシュテーブル500dから取り出されたTTL値がオフセット値よりも大きい場合は、入力マルチキャストパケットは例えば下流FN90から発生したものであり、FN90はマルチキャストパケットを転送する必要が無い。
【0141】
ブロック1805で、FNはマルチキャストパケットのランダム転送タイマを停止する。言い換えると、FNはランダム転送タイマの状態を「オン」から「オフ」に変更する。その後、ブロック430でマルチキャストパケットは破棄される。ブロック440で、FN90はアイドルになる。
【0142】
ランダム転送タイマが満了したら、FN90はマルチキャストパケットを転送する。ブロック1810で、ランダム転送タイマが満了し、FN90がランダム転送タイマの状態を「オン」から「オフ」に変更する。その後、ブロック605で、FN90はマルチキャストパケットを転送する。FN90はTTL値を1だけ減らす。マルチキャストパケット内のTTL値を1だけ減少させた後、FN90マルチキャストパケットを転送する。さらに、マルチキャストパケットの転送の後、ブロック1812でFNは再送カウンタ(s_mp_c)を1に設定する。ブロック440で、FN90はアイドルになる。第7の実施形態によれば、FN90によるマルチキャストパケットの転送は軽く抑制される。
【0143】
図19は、本発明の第8の実施形態に係るルーティング方法を示す。第8の実施形態によれば、マルチキャストパケットの転送は厳しく制限される。図19に示される機能ブロックの多くは図18と同じであり、したがって、詳しくは説明しない。第7と第8の実施形態の違いは、ブロック1900における(ブロック815と対照的な)TTL値の比較である。ブロック1900で、入力マルチキャストパケットのTTL値がMPキャッシュテーブル(例えば、500d)に格納されたTTL値と比較される。
【0144】
入力マルチキャストパケットのTTL値にはオフセット値が加えられない。
【0145】
MPキャッシュテーブル(例えば、500d)から取り出されたTTL値が入力TTL値より大きくなければ、入力マルチキャストパケットは(ブロック430で)破棄され、ブロック440でFN90はアイドルになる。このマルチキャストパケットは上流ノードから発生したものである。ブロック1900においてMPキャッシュテーブル500dから取り出されたTTL値が入力TTL値より大きければ、入力マルチキャストパケットは例えばピアや下流ノードから発生したものである。FN90は、マルチキャストパケットの転送をやめて、マルチキャストパケットのランダム転送タイマを停止する。
【0146】
図20は、本発明の第9の実施形態に係るルーティング方法を示す。本発明の第9の実施形態は2段階の抑制方法を用いる。図20は、2つの機能ブロックが追加されている以外は、図18と同様である。同一の機能ブロックについては繰り返しては説明しない。
【0147】
上述したように、ブロック815で、FN90は、オフセットTTL値(IN_MP_TTL+1)を同一のマルチキャストパケットのTTL値と比較する。同一のマルチキャストパケットのTTL値はMPキャッシュテーブル(例えば、500d)から取り出される。MPキャッシュテーブル500dから取り出されたTTL値がオフセット値よりも大きくなければ、入力マルチキャストパケットは(ブロック430で)破棄され、ブロック440でFN90はアイドルになる。しかしながら、第9の実施形態では、MPキャッシ
ュテーブル500dから取り出されたTTL値がオフセット値よりも大きくなければ、ブロック2000で、FNはMPキャッシュテーブルから取り出されたTTL値がオフセット値と等しいか判断する。MPキャッシュテーブル500dから取り出されたTTL値がオフセット値と等しくなければ、入力マルチキャストパケットは破棄され、ブロック440でFN90はアイドルになる。しかしながら、MPキャッシュテーブル500dから取り出されたTTL値がオフセット値と等しい、すなわち、マルチキャストパケットが周囲のピアから受信されたものであれば、ブロック2005で、マルチキャストパケットのランダム転送タイマが停止されて、別のランダム値に再設定される。マルチキャストパケットのランダム転送タイマ延長される。この時間延長により、同一のマルチキャストパケットのTTL値よりも小さいオフセットTTL値を有する入力マルチキャストパケットを、ランダム転送タイマが満了する前に受信する機会が増える。したがって、不必要な転送が抑制され、重複するパケットが生成することが少ない。
【0148】
図21は、第7〜第9の実施形態に係るFN90のMPキャッシュテーブル500dの例を示す。図示されるように、MPキャッシュテーブル500dは、2つの異なるマルチキャストパケット(MP1およびMP2)を含む。各マルチキャストパケットに対して、MPキャッシュテーブル500bは、マルチキャストセッションID(Group Add)、送信元識別子、マルチキャストパケットのシーケンス番号(SeqNum)、マルチキャストパケットデータ(MPキャッシュ)、再送カウンタ(s_mp_c)、マルチキャストパケットのTTL値(C_MP_TTL)、およびランダム転送タイマ(Random_Forward_Timer)を含む。図21に示されるように、マルチキャストパケットの一方についてオンである。
【0149】
本発明の第9の実施形態は、マルチキャストパケットと同様にブロードキャストパケットにも適用できる。しかしながら、ブロードキャスト通信を行うためには、すべてのノードがFN90になる。
【0150】
本発明はここまで特定の例示的な実施形態を参照して説明されている。本発明の範囲から逸脱することなくいくらかの代替や変更は当業者にとって明らかであろう。例示的な実施形態は説明を意図したものであり、添付の特許請求の範囲によって定義される本発明の範囲を限定するものではない。
【技術分野】
【0001】
[関連出願の相互参照]
本発明は、共同所有され同時に係属中である、アドホック無線ネットワークにおけるユニキャストおよびマルチキャストメッセージをルーティングするための方法および通信装置と題する、2006年10月23日出願の出願番号第11/585,047の米国特許出願(「’047出願」)に関連する。
【0002】
[技術分野]
この発明は、移動環境における通信ネットワークに関連する。より具体的には、本発明は、複数の移動装置間のマルチホップ・マルチキャストメッセージをルーティングするための方法に関連する。
【背景技術】
【0003】
無線ホームネットワークや、無線オフィスネットワークや、ローカルカフェ、ファーストフードチェーン又はホテルにおけるいわゆる「ホットスポット」ネットワークや、さらには都市全体でのWiFi技術の実現であれ、無線技術は今日の生活のあらゆる面において一般的なものとなっている。社会においてこのように無線を推し進める目的は、情報へのアクセスを提供し、社会全体がコンピュータネットワーク、特にインターネットを広く受け入れるとともに利用することで享受してきた生産性をさらに向上させるためである。
【0004】
無線通信社会になるという願望は、移動車両のような移動装置にまで広がっている。この種の無線通信ネットワークは、限定はしないが、緊急路上障害物警告、交差点での協調、隠れた車道に関する警告、車線変更または合流の支援などを含む、車両安全アプリケーションの多くの態様において現れる。
【0005】
車両安全通信(「VSC」)は大きく分類して、車車間通信とインフラ協調車両通信とに分けることができる。車車間通信では、固定インフラストラクチャからの支援なしに車両同士がお互いに通信する。車両同士が同じ無線通信範囲内に位置する場合や、他の車両を介したマルチホップ通信が可能な場合に、車両同士がお互いに通信する。インフラ協調車両通信では、路側無線アクセスポイントなどのインフラストラクチャの支援を受けて、車両同士がお互いに通信する。この場合、車両はインフラストラクチャのみと通信することもできる。
【0006】
衝突回避のような種々のVSCアプリケーションを支援するために、重要なVSC性能要件には、遅延時間が短いこと(100ミリ秒のオーダー)と、スループット(近くの車両が警告メッセージを受信に成功する確率と同等)を維持することが含まれる。
【0007】
’047出願には、1台の移動車両をグループヘッダとして選択し、このグループヘッダを利用してローカル・ピア・グループを維持し、ローカルルーティング情報を生成することで、移動車両のグループをローカル・ピア・グループに組織化することが記述されている。移動車両はユニキャストおよびマルチキャストのルーティングに適合される。しかしながら依然として、スループットをさらに向上し遅延が少ないマルチキャストのルーティング方法に対する要求がある。
【発明の概要】
【0008】
したがって、マルチキャストメッセージのルーティング方法が開示される。この方法は
、少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、前記メッセージが以前に受信したものであるか判断するステップと、前記メッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、前記マルチキャストメッセージを受信したノードが転送ノードであるか判断するステップと、前記マルチキャストメッセージを転送するための待機時間をランダムに設定するステップと、前記待機時間が満了したときに、前記マルチキャストメッセージを転送するステップと、を含む。
【0009】
前記メッセージが以前に受信したものである場合に、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを前記ランダムに設定された待機時間内に下流ノードから受信したときは、前記待機時間を停止する。待機時間が停止された場合は、マルチキャストメッセージは転送されない。
【0010】
第2のマルチキャストメッセージが下流ノードから受信されたかの判断は、第2のマルチキャストメッセージからTime−to−Live値を抽出する工程と、前記Time−to−Live値にプリセット値を加えてオフセットTime−to−Live値を生成する工程と前記マルチキャスト転送テーブルから同一のメッセージを含むマルチキャストメッセージのTime−to−Live値を取り出す工程と、前記オフセットTime−to−Live値と前記取り出されたTime−to−Live値とを比較する工程とを含み、前記取り出されたTime−to−Live値が前記オフセットTime−to−Live値よりも大きい場合に、前記待機時間が停止される。
【0011】
前記取り出されたTime−to−Live値が前記オフセットTime−to−Live値と等しい場合は、前記待機時間はランダム値にリセットされる。
【0012】
本方法は、転送後にACKフラグを未確認に設定するステップと、再送時間を所定時間に設定するステップと、をさらに含む。前記メッセージが以前に受信されたものである場合に、本方法は、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを下流ノードから受信したときは、前記再送時間を停止するステップをさらに含む。前記再送時間を停止した後に、ACKフラグを確認済みに設定される。
【0013】
本方法は、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、再送後に前記送信時間を所定時間に設定するステップと、をさらに含む。
【0014】
本方法は、再送の上限に達したか判断するステップと、前記判断に基づいて、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、再送カウンタを増加させるステップと、再送後に前記再送時間を所定時間に設定するステップと、をさらに含む。再送の上限に達した場合には、再送時間が停止される。
【0015】
前記マルチキャスト転送テーブルは、前記グループ宛先と前記送信元識別子と前記シーケンス番号と前記メッセージと前記ACKフラグと前記再送時間値と前記再送カウンタと前記Time−to−Live値とを含む。
【0016】
マルチキャストメッセージをルーティングするための別の方法も開示される。本方法は、少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと
、前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、前記メッセージが以前に受信したものであるか判断するステップと、前記マルチキャストメッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、前記マルチキャストメッセージを受信したノードがマルチキャスト受信ノードであるか判断するステップと、マルチキャスト受信ノードに確率値をランダムに割り当てるステップと、前記ランダムに割り当てられた確率値とプリセット確率閾値とを比較するステップと、前記比較に基づいて前記マルチキャストメッセージを転送するステップと、を含む。
【0017】
本方法は、前記プリセット確率閾値を設定するステップをさらに含む。
【0018】
前記マルチキャスト転送テーブルは、前記グループ宛先と前記送信元識別子と前記シーケンス番号とを含む。
【0019】
本方法は、転送後にACKフラグを未確認に設定するステップと、再送時間を所定時間に設定するステップと、をさらに含む。
【0020】
本方法は、再送カウンタを増加させるステップをさらに含む。
【0021】
前記メッセージが以前に受信されたものである場合に、本方法は、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを下流ノードから受信したときに、前記再送時間を停止する工程をさらに含む。
【0022】
前記再送時間を停止した後に、ACKフラグを確認済みに設定される。
【0023】
本方法は、再送カウンタの値に基づいて、再送の上限に達したか判断するステップと、前記判断に基づいて、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、再送カウンタを増加させるステップと、再送後に前記再送時間を所定時間に設定するステップと、をさらに含む。再送の上限に達した場合には、再送時間が停止される。
【0024】
マルチキャストメッセージをルーティングするための別の方法も開示される。本方法は、少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、前記メッセージが以前に受信したものであるか判断するステップと、を含み、前記メッセージが以前に受信されたものである場合に、前記Time−to−Live値にプリセット値を加えてオフセットTime−to−Live値を生成する工程と、前記オフセットTime−to−Live値と前記マルチキャスト転送テーブル内のTime−to−Live値を比較する工程と、前記オフセットTime−to−Live値が前記マルチキャスト転送テーブル内のTime−to−Live値以上である場合に、前記マルチキャストメッセージを破棄する工程と、を含む。
【0025】
前記マルチキャストメッセージが以前に受信したものではない場合に、本方法は、ACKフラグを未確認に設定する工程と、再送カウンタを増加させる工程と、再送時間を所定値に設定する工程と、マルチキャストメッセージを転送する工程と、を含む。
【0026】
前記オフセットTime−to−Live値が前記マルチキャスト転送テーブル内のTime−to−Live値よりも小さい場合に、本方法は、ACKフラグを確認済みに設
定する工程と、前記再送時間を停止する工程と、をさらに含む。
【0027】
本発明のこれらおよび他の特徴、利益や利点は、以下の図面を参照することによって明らかになる。なお、図面を通して、類似の参照符号は類似の構造を指している。
【図面の簡単な説明】
【0028】
【図1】図1は、マルチキャストメッセージ用に設定されたローカル・ピア・グループの例を説明する。
【図2】図2は、ハートビートメッセージの例を説明する。
【図3】図3は、メンバシップレポートメッセージの例を説明する。
【図4】図4は、本発明の第1の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図5】図5は、本発明の第1の実施形態に係る、転送ノードおよびマルチキャスト受信ノードのためのMPキャッシュテーブルの例を説明する。
【図6】図6は、本発明の第2の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図7】図7は、本発明の第2の実施形態に係るルーティング方法の例を説明する。
【図8】図8は、本発明の第3の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図9】図9は、本発明の第3の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図10】図10は、本発明の第3の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図11】図11は、本発明の第3の実施形態に係る、転送ノードのためのMPキャッシュテーブルの例を説明する。
【図12】図12は、本発明の第4の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図13】図13は、本発明の第4の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図14A】図14Aは、本発明の第4の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図14B】図14Bは、本発明の第4の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図15A】図15Aは、本発明の第4の実施形態に係る、転送ノードのためのMPキャッシュテーブルの例を説明する。
【図15B】図15Bは、本発明の第4の実施形態に係る、マルチキャスト受信ノードのためのMPキャッシュテーブルの例を説明する。
【図16】図16は、本発明の第5の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図17】図17は、本発明の第6の実施形態に係る、マルチキャスト受信ノードによるマルチキャストパケットのルーティング方法を説明する。
【図18】図18は、本発明の第7の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図19】図19は、本発明の第8の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図20】図20は、本発明の第9の実施形態に係るマルチキャストパケットのルーティング方法を説明する。
【図21】図21は、本発明の第7〜第9の実施形態の係る、転送ノードのためのMPキャッシュテーブルの例を説明する。
【発明を実施するための形態】
【0029】
[定義]
「ノード」は、チャネルの決定・選択処理や以下の説明で記載される方法を実行するルータである。例えば、通信装置を備える移動車両はノードである。この出願では、ノードと移動車両は同じ意味で使われている。
【0030】
「マルチキャストメッセージ」は1つまたはそれ以上の宛先を持つメッセージである。詳細な説明では、マルチキャストメッセージはマルチキャストパケット(MP)と称される。「ホップ」はメッセージを中継するノードである。2ノード間、すなわち送信元と宛先の間の「ホップカウント」は、中継ノードの数に1を足したものに等しい。
【0031】
本発明によれば、ローカル・ピア・グループ(LPG)に組織化されたノードまたは移動車両は、マルチキャストルーティングテーブルを生成するために相対位置、一意の識別子、LPGに関する情報を交換する。後述するハートビートメッセージやメンバシップレポートメッセージのような制御パケット内の情報に基づいて、ルーティングテーブルが生成される。マルチキャストは、1つのマルチキャストセッションについて複数の送信元ノード700とマルチキャスト受信ノード20に対応する。
【0032】
LPG1は、近くの複数のノード10から動的に形成される。具体的には、第1のノードが無線信号をブロードキャストし、第1のノードの範囲内の他のノード10は、この無線信号を受信する能力がある。LPG1は無線通信範囲に基づいて形成されるので、LPG1内のノードは、固定インフラストラクチャを必要とせずに、1ホップまたはマルチホップで互いに通信できる。ハートビートメッセージおよびメンバシップレポートの送信に基づいて、LPG1は形成および維持される。
【0033】
図1は、マルチキャストメッセージ用に設定されたモードを持つLPG1を示す。マルチキャストを行うために、ノード10は、マルチキャスト受信ノードと転送ノード90の2つのグループに分けられる。マルチキャスト受信ノード20はマルチキャストメッセージの受信が意図されるノードである。転送ノード90はメッセージを転送する。LPG1内の全てのノード10は、転送ノードにもマルチキャスト受信ノード20にもなりうる。さらに、LPG1内の1つのノードがグループヘッダ(GH)として選択される。GHは、他のノードやインフラストラクチャからの命令なしにLPG1を維持および制御することを指定されたLPG1内の移動装置またはノード10である。ノード10は、メンバシップレポートをGHへ中継するために用いられるときに、FN90になる。LPG1の形成、維持、GHの選択、制御は’047出願に記載されており、その内容は参照により本明細書に含まれる。
【0034】
図2は、本発明に係るハートビートメッセージ200の例を示す。GHは、ハートビートメッセージ200を定期的に送出して、LPG1を識別(identify)するとともにLPG1に関する情報を提供する。この周期は固定間隔(T)である。この間隔(T)の値は、設計や運用の要求に基づいて選択可能である。GHは、LPG1に含まれる全ノードのリストの維持も行う。このリストには、ノードがLPG1に参加した時のタイムスタンプ、あるいは、GHがノードからステータス更新を受信した時のタイムスタンプが含まれる。このリストは、LPG1に対する種々の維持・管理機能のために用いられる。例えば、このリストは、グループサイズを追跡したり、マルチキャストルーティングテーブルを作成・更新したり、ヘッダ解決のために用いることができる。さらに、このリストは、LPG1内の他の全てのノードに周期的にブロードキャストされる。ハートビートメッセージ200がLPG1内の全ノード10にブロードキャストされる。
【0035】
ハートビートメッセージ200は、LPG1の識別子、GH ID、シーケンス番号、
ハートビートメッセージの種類(例えば、完全なグループリスト付きのハートビートか、増分(incremental)グループリスト付きのハートビートか、グループリストなしのハートビートか)を含む。ある実施形態では、ハートビートメッセージは全てのパケットにおいて完全なグループリストを含む。完全なグループリストを使うことが、ルーティング制御と正しいグループメンバのリストを維持するための最も正確な方法であるが、完全なグループ付きのハートビートのためには相当量の帯域幅が必要となる。別の実施形態では、ハートビートメッセージ200は、n回おきに完全なグループリストを含む。例えば、3回おきにハートビートが完全なグループリストを含むようにする。ToHbは、ハートビートメッセージの種類を意味する。ハートビートメッセージの種類は、LPG1のトポロジー変化の早さとハートビートのブロードキャスト頻度の影響を受ける。LPG1のトポロジー変化速度が速くなると、全てのハートビートメッセージ200に完全なグループリストを含める必要性が高まる。
【0036】
ハートビートメッセージ200は、GHからのホップカウント(HC)も含む。最初は、HCは所定値、たとえば1に設定される。ハートビートメッセージ200がノードによって中継されるたびに、中継ノードがHC値を1増加させる。すなわち、HC=HC+1とする。HC値は、LPGのサイズを限定したり、ハートビートメッセージ200内の情報の古さを示したり、オーバヘッドを減らすための制御パケットのルーティングを制御したりするために用いることができる。各LPG1に対して、ルーティングの最大ホップカウント(例えば10)がある。HCが最大ホップカウントに達すると、その制御パケットはそれ以上中継されない。
【0037】
最大ホップカウント、HCおよびシーケンス番号を用いることで、LPG1内で制御パケットが無限に複製されることを防止できる。ホップカウントは中継戦略のためにも利用される。ノードがハートビートメッセージを転送するときにメッセージにID情報を含めるので、次ホップのノードは、このハートビートメッセージ200を誰が中継するのかを知ることができる。
【0038】
上述したように、ハートビートメッセージ200はグループリストも含むことができる。グループリストは、LPG1のメンバに関する情報を含むことができる。たとえば、LPG1内のメンバ数、各メンバのIPアドレス、GHからのホップカウントや分類などである。
【0039】
分類は、たとえばアップリンク、ダウンリンク、ピアのような、GHからの相対的な方向を示すコードであり得る。ピア分類は、ノードがGHと同じ無線通信範囲内であることを示す。すなわち、全てのピアノードは、GHから同じホップカウントを有する。上流ノードはハートビートから決定される。下流ノードは、後述するメンバシップレポート(MR)300に基づいて決定される。上流送信はGH25に向かう方向の通信を意味し、下流送信はGH25からの離れる方向の通信を意味する。分類は相対的な用語である。各ノードはその近隣ノードを異なる3つの種類に分けることができる。他のノードのメンバシップレポートのホップカウント(HC)が自ノードのHCよりも1少なければ、自ノードは上流ノードである。そのHCが自身のHCと同じであれば、自ノードはピアである。そのHCが自身のHCよりも1大きければ、自ノードは下流ノードである。
【0040】
図3はメンバシップレポート(MR)300の例を示す。MR300はGH以外のノードからブロードキャストされる制御パケットであり、その受取人はGH25である。MR300は、ハートビートメッセージ200に対する応答として生成される。MR300は、メンバシップリスト、下流ノードID、下流ノードに対する次ホップのような収集可能なルーティング情報を含む。MR300は、GIDやグループヘッダIDのような、ハートビートメッセージ200と同じ情報のいくつかを含む。MR300は、MRシーケンス
番号も含む。MRシーケンス番号は、ハートビートメッセージ200のシーケンス番号と同様のものであり、MRの順序を維持するために用いられる。MRシーケンス番号はある特定のノードに対するMRの順序である。典型的には、MRシーケンス番号は、MR300のきっかけとなったハートビートメッセージ200のシーケンス番号と同じ値を有する。
【0041】
MR300には、発信元ノード、すなわち、MR300を生成したノードのノードIDも含まれる
【0042】
MR300は次ホップ中継IDも含む。次ホップ中継IDは、GHへ向かうMR300に対する中継の指示である。次ホップの情報は、受信したハートビートメッセージ200から直接決定される。ノード10が新しいすなわち新規のハートビートメッセージ200を受信すると、何らかのパケット処理を行う前にIP層およびMAC層から直前の中継ノードのIDを取り戻す。直前の中継ノードのIDはメモリに格納され、MR300の次ホップ中継IDとして用いられる。ノード10がハートビートメッセージ200を転送するときは、ノード10は自身のIDをパケットに含める。これを受信する次ホップノードは、新しいすなわち新規のハードビートメッセージ200を受信すると、このIDをGH25に達するための次ホップ中継IDとして格納する。新しいすなわち最新のハートビートメッセージ200は、最も小さいHCと新しいシーケンス番号を有する。
【0043】
MR300は「MR標識の種類」ToMRも含む。MR300には、単一メンバレポートおよび複数集約メンバレポート(aggregated multiple member report)の2つの種類がある。単一メンバMRは発信元ノードからのMR300のみを含む。複数集約メンバレポートは2つ以上のノードのMR300を含む。1つのMR300が複数のMRを含んで送られる。
【0044】
さらに、MR300はGHからのホップカウント(HCGH)を含んでも良い。(HCGH)は、GHから発信ノードまでのMR300のHC値である。MR300は、報告ノードが利用可能なチャネルのリストを含む。さらに、MRは、MR300をGHに向かって中継した全ノードについての利用可能なチャネルのリストを含んでも良い。さらに、MR300は、その状態またはマルチキャストメッセージを中継可能であるか、すなわち転送ノードステータスを含む。
【0045】
マルチキャストルーティングテーブルは、マルチキャストセッションが開始された後に、ハートビートメッセージ200およびMR300から作成される。マルチキャストルーティングテーブルは木構造またはメッシュとして視覚化するのが最も適切といえる。木構造またはメッシュは、任意の送信元ノード700からFNを介してマルチキャスト受信ノード20に至る経路またはリンクを提供する。マルチキャストセッションを確立するために、マルチキャストセッションに参加したいノード10はマルチキャストセッションに対応したマルチキャストアプリケーションプログラムを起動する。このアプリケーションプログラムはメモリに格納される。そして、ノードはFNかマルチキャスト受信ノードになり、セッション参加の要求を示す信号(MR300)を発する。これらの信号によって、マルチキャストセッションに対するマルチキャストツリーの生成が開始される。
【0046】
ノードがMR300をGHに向かって中継すると、そのノードはマルチキャストグループのFN90になる。FN90は、ここで説明される1つまたはそれ以上の方法によって、マルチキャストセッションに関連づけられたマルチキャストパケットを受け付けて転送することができる。木構造またはメッシュ、すなわちマルチキャストルーティングテーブルは、ここに参照によって明示的に組み入れられる’047出願において説明されるいずれかの方法を用いて作成される。マルチキャストルーティングテーブルは、ハートビート
期間ごとに更新される。マルチキャストパケットはマルチキャストルーティングテーブルを用いて経路が定められる。
【0047】
図4は、本発明の第1の実施形態に係るマルチキャストルーティング方法を示す。本ルーティング方法を、その機能ブロックを用いて説明する。異なる実施形態における同一の機能ブロックは、同一の番号を用いて参照される。
【0048】
ブロック400で、マルチキャストパケットがノードに到着する。ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10は、FN90かマルチキャスト受信ノード20のいずれかであれば、マルチキャストセッションのメンバである。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック415で、ノード10は、MPキャッシュテーブル(例えば図5、500)内に、受信したマルチキャストパケットと一致するものがあるか探す。本発明の第1の実施形態では、MPキャッシュテーブル500はFN90とマルチキャスト受信ノード20の両方に対して同一である。MPキャッシュテーブル500は、グループ識別子、送信元識別子、つまりマルチキャストパケットの元々の送信元ノード700、およびシーケンス番号を含む。パケットのシーケンス番号と送信元識別子の両方が同じであれば、マルチキャストパケットは受信パケットと同一である。マルチキャストパケットが同一であれば、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。
【0049】
マルチキャストパケットがMPキャッシュテーブル500内のいずれのパケットとも一致しない場合は、ブロック420で、ノード10は、グループ識別子、送信元識別子、マルチキャストパケットの順番のようなマルチキャストに関連する情報をMPキャッシュテーブル500に追加する。マルチキャストパケットがMPキャッシュテーブル500に加えられると、ブロック425で、ノード10はマルチキャストセッションのFN90であるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのFN90でなければ、ブロック430で、マルチキャストパケットは破棄される。その後、ブロック440でノード10はアイドルになる。
【0050】
ノード10がマルチキャストセッションのFN90であれば、ブロック435で、ノードはマルチキャストパケットをN回再マルチキャストすなわち転送する。ある実施形態では、FN90はマルチキャストパケットをN回連続して転送する。パケットが転送される数字「N」回は予め定められていて変更可能である。到達率の増加とデータオーバヘッドの増加にはトレードオフがある。数字「N」が増えるにしたがって、データオーバヘッドが著しく増加するが、到達率もまた増加する。別の実施形態では、FN90はパケットをN回同時に転送する。
【0051】
マルチキャストパケットを転送した後、ブロック440で、FN90はアイドルになる。
【0052】
図5は、本発明の第1の実施形態におけるMPキャッシュテーブル500の例を示す。図5に示すように、MPキャッシュテーブル500は、IPアドレスのようなセッションやグループの識別子である追加グループ(GroupAdd)、マルチキャストパケットの送信元ノード700の識別子である送信元識別子、およびパケットのシーケンス番号(SeqNum)を含む。
【0053】
図6は、本発明の第2の実施形態に係るマルチキャストルーティング方法を示す。ブロ
ック400で、マルチキャストパケットがノード10に到着する。ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10は、FN90かマルチキャスト受信ノード20のいずれかであれば、マルチキャストセッションのメンバである。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック415で、ノード10は、MPキャッシュテーブル内に、受信したマルチキャストパケットと一致するものがあるか探す。本発明の第2の実施形態では、MPキャッシュテーブル500はFN90と受信ノードの両方に対して同一である。MPキャッシュテーブル500は、グループ識別子、送信元識別子、およびシーケンス番号を含む。パケットのシーケンス番号と送信元識別子の両方が同じであれば、マルチキャストパケットは受信パケットと同一である。マルチキャストパケットが同一であれば、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。
【0054】
マルチキャストパケットがMPキャッシュテーブル500内のいずれのパケットとも一致しない場合は、ノード10は、ブロック420で、受信したマルチキャストパケットについての情報をMPキャッシュテーブル500に追加する。マルチキャストパケットに関連する情報がMPキャッシュテーブル500に加えられると、ブロック425で、ノード10はマルチキャストセッションのFN90であるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がFN90であれば、ブロック605で、ノード10はマルチキャストパケットを一度転送する。ブロック440で、ノード10はアイドルになる。
【0055】
ノード10がFN90でなければ、ノード10はマルチキャスト受信ノード20である。本実施形態によれば、FN90による通常の転送に加えて、いくつかのマルチキャスト受信ノード20がマルチキャストパケットの転送のために選択される。この追加的な転送によって、マルチキャストセッションのメンバがパケットを受信し損ねる可能性が抑えられる。受け取ったマルチキャストデータパケットごとに割り当てられる確率に基づいて、いくつかのマルチキャスト受信ノード20が選択される。各マルチキャスト受信ノード20は確率閾値とともにプログラムされる。確率閾値は0と1の間の値である。確率閾値は、複数のマルチキャスト受信ノード20について同じではない。ある実施形態では、確率閾値はランダムにプログラムされる。別の実施形態では、確率閾値は、LPG1内のノード10の数またはマルチキャストセッション内のノード数に基づいて割り当てられる。言い換えると、確率閾値は周期的に変化しても良い。ある実施形態では、マルチキャストセッションの送信元ノード700が確率閾値を割り当てても良い。代替として、GHが確率閾値を割り当てても良い。
【0056】
ブロック600で、マルチキャスト受信ノード20であるノード10は、マルチキャストパケットに割り当てられたランダムな確率と、確率閾値とを比較する。マルチキャストパケットに割り当てられたランダムな確率が確率閾値よりも小さければ、ブロック605で、マルチキャスト受信ノードは受信したマルチキャストパケットを転送する。そして、ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0057】
マルチキャストパケットに割り当てられたランダムな確率が確率閾値以上であれば、ブロック430で、マルチキャスト受信ノード20は受信したマルチキャストパケットを破棄する。そして、ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0058】
図7は、本発明の第2の実施形態に係る方法を実行するマルチキャストセッションの例を示す。送信元ノード700がマルチキャストセッションを開始し、マルチキャストパケ
ットをマルチキャストする。FN1 901、FN2 902、およびFN3 903は、マルチキャストパケットを受信した後に、ブロック605で、マルチキャストパケットを転送する。マルチキャスト受信ノード201、202、203はマルチキャストデータパケットを転送せずにマルチキャストパケットを破棄する(ブロック430)。しかしながら、マルチキャスト受信ノード204、205、206は、マルチキャストパケットを転送する(ブロック605)。MPキャッシュテーブルは本発明の第1の実施形態と同様である(例えば、500)。MPキャッシュテーブル500は、FN90とマルチキャスト受信ノード20の両方に対して同一である。
【0059】
図8〜図10は、本発明の第3の実施形態に係るルーティング方法を示す。本発明の第3の実施形態によれば、次ホップノードは転送されたマルチキャストパケットの受信通知を行う。この受信通知(acknowledgement)はパッシブ受信通知方式をとる。FN90によって転送されたマルチキャストパケットは、その次ホップFNによって転送されたマルチキャストパケットによって受信通知が行われる。次ホップFNから転送されたマルチキャストパケットは、傍受(overheard)される。
【0060】
ブロック400で、マルチキャストパケットがノード10に到着する。マルチキャストパケットは、マルチキャストグループID、シーケンス番号、Time−to−Live(TTL)値、およびデータを含む。TTL値は、マルチキャストパケットが中継されるホップ数である。各ホップで、FN90はTTL値を減少させる。TTL値は、同一のマルチキャストデータパケットが転送させる回数を制限する機能を果たす。
【0061】
ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック800で、ノード10はFN90かマルチキャスト受信ノードであるかを判断する。ノード10がマルチキャスト受信ノードであれば、処理は図10のブロック415に移動する。ノード10がマルチキャストセッションのFN90であれば、ブロック415(図8)で、FN90はマルチキャストパケットがMPキャッシュテーブル(例えば、図11、500a)内にあるか判断する。
【0062】
マルチキャストパケットがMPキャッシュテーブル500a内のいずれのパケットとも一致しない場合は、ブロック420で、FN90は受信したマルチキャストパケットをMPキャッシュテーブル500aに追加する。この実施形態では、マルチキャストパケットに関連する情報とパケットの両方がMPキャッシュテーブル500aに追加される。
【0063】
FN90は、マルチキャストグループID、シーケンス番号、送信元識別子、Time−to−Live(TTL)値、およびデータを抽出し、この情報をMPキャッシュテーブル500aに付加する。さらに、FN90は再送カウンタをゼロに初期化する。再送カウンタ(s_mp_c)は、マルチキャストパケットが再送されうる回数を表す。ある実施形態では、マルチキャストメッセージが再送される回数はあらかじめ定められた最大値に制限される。あらかじめ定められた最大値は全ノード10に対して同じであっても良い。別の実施形態では、あらかじめ定められた最大値はGHや送信元ノード700のような特定のノードに対して変更可能としても良い。
【0064】
MPキャッシュテーブルはFN90とマルチキャスト受信ノードとで異なる。FN90用には、MPキャッシュテーブル500は、マルチキャストパケットについてのマルチキャストセッションID、送信元識別子、シーケンス番号、マルチキャストパケットデータ
、ACK状態、再送タイマ値、再送カウンタ、およびTTL値を含む。ACK状態は「未確認」または「確認済み」のいずれかであり得る。再送タイマ値はオンかオフのいずれかであり得る。タイマがオンであれば、再送タイマ値は初期設定タイマ値といつ再送タイマ値が満了したかの指示も含む。マルチキャスト受信ノード20用には、MPキャッシュテーブル500は、マルチキャストセッションID、送信元識別子、およびシーケンス番号だけを含む。
【0065】
ブロック805で、FN90はACK状態を「未確認」に初期化する。FN90はどのマルチキャストパケットが受信確認され受信されたかを追跡できる。さらに、FN90は再送タイマ値をオンに初期化し、タイマを再送時間に設定する。再送時間は、データパケットに含まれるデータの種類、FN90の移動速度、およびその他のユーザ定義の基準に応じて変更可能である。例えば、12msの再送時間を利用することができる。メッセージに含まれるデータが高い優先度のメッセージであれば、再送時間を短くしても良い。あるいは、メッセージが低い優先度のメッセージであれば、再送時間を長くしても良い。回復遅延は再送時間の値に依存する。再送時間が小さいほど、遅延は短くなる。しかしながら、小さくしすぎると多くの再送信が発生し、不必要な再送信が生じる。
【0066】
ブロック810で、再送カウンタが1増分する。すなわちs_mp_c+1にする。再送カウンタが増分された後、ブロック605で、FN90はマルチキャストパケットを一度転送する。FN90は、転送の前にマルチキャストパケットのTTL値から1減算する。したがって、次ホップFNによって受信されるマルチキャストパケットは、最小のTTL値を持つ。ブロック440で、FN90はアイドルになる。
【0067】
マルチキャストパケットがMPキャッシュテーブル500a内のいずれかのパケットと同一であれば、本方法はブロック815へ進む。
【0068】
FN90は入力マルチキャストパケットのTTL値を判断する。上記したようにTTL値は特定のマルチキャストパケットのホップ数を制御するために用いられる。さらにこの実施形態では、TTL値は送信ノード10および受信ノード10の相対的な位置を決定するためにも用いられる。具体的には、マルチキャストパケットが転送されるたびに、ノード10はTTL値から1減算する(すなわち、TTL−1)。特定のFN90から下流にあるノード10から受信されたマルチキャストパケットのTTL値は、FN90から転送された同一のマルチキャストパケットのTTL値よりも小さい。特定のFN90から上流にあるノード10から受信されたマルチキャストパケットのTTL値は、FN90から転送された同一のマルチキャストパケットのTTL値よりも大きい。特定のFN90と同じホップ数のノード10から受信されたマルチキャストパケットは、同一のTTL値を持つ。
【0069】
FN90は、FN90による最初のマルチキャストパケットの転送を補うために、判定されたTTL値にオフセット値の1を加える。これによりオフセットTTL値が生成される。
【0070】
ブロック815で、FN90は、入力パケットのオフセットTTL値(In_MP_TTL+1)と同一のマルチキャストパケットのTTL値とを比較する。同一のマルチキャストパケットのTTL値は、MPキャッシュテーブル500aから取り出される。MPキャッシュテーブル500aから取り出されたTTL値がオフセット値よりも大きくない場合は、ブロック430で、入力マルチキャストパケットは無視されて破棄される。このマルチキャストパケットは上流ノードから発生したものである。マルチキャストパケットの転送は受信確認されない。ブロック440で、FN90はアイドルになる。
【0071】
ブロック815においてMPキャッシュテーブルから取り出されたTTL値がオフセット値よりも大きい場合は、ブロック820で、FN90はこのマルチキャストパケットがすでに受信確認されたか判断する。
【0072】
FN90はMPキャッシュテーブル500aから同一のマルチキャストパケットについてのACK状態を取り出す。同一のマルチキャストパケットがすでに受信確認されていれば、ブロック430で、入力マルチキャストパケットは無視されて破棄される。ブロック440で、FN90はアイドルになる。MPキャッシュテーブル500aに変更はない。ブロック820において同一のマルチキャストパケットが受信確認されていなければ、本方法はブロック825へ進む。
【0073】
ブロック825で、FN90は再送タイマを停止する。さらに、FN90は、キャッシュテーブル500a内の再送タイマ値を「オフ」に変え、ACK状態を「確認済み」に変える。その後、ブロック430で入力マルチキャストパケットは破棄される。ブロック440で、FN90はアイドルになる。マルチキャストパケット転送の受信が確認される。
【0074】
図9は、マルチキャストパケットの転送が受信確認される前に再送タイマが満了する場合の機能ブロック図を示す。図9に示される機能ブロック図はFN90によってのみ実行される。
【0075】
ブロック900で、再送タイマが満了する。FN90は、再送カウンタが最大閾値に達したか判断する。FNは、再送タイマが満了したパケットに対応するマルチキャストパケットの再送カウンタをMPキャッシュテーブル500aから抽出する。再送カウンタは、最大閾値と比較される。再送カウンタが最大閾値以上であれば、FN90はブロック440でアイドルになる。
【0076】
再送カウンタが最大閾値より小さければ、ブロック805で、FN90はマルチキャストパケットの送信タイマをリセットし、マルチキャストパケットのACK状態を「未確認」に初期化する(図9において「Not ACKed」と示される)。
【0077】
ブロック810で、再送カウンタが1増分する。すなわちs_mp_c+1にする。再送カウンタが増分された後、ブロック605で、FN90はマルチキャストパケットを一度転送する。FN90は、転送の前にマルチキャストパケットのTTL値から1減算する。したがって、次ホップFNはマルチキャストパケットを送っているFN90よりも小さいTTLを持つマルチキャストパケットを受信する。ブロック440で、FN90はアイドルになる。
【0078】
図10は、本発明の第3の実施形態に係るマルチキャスト受信ノード20の機能ブロックを示す。図8に示すように、ブロック800においてノード10がFN90でなければ、処理は図10のブロック415に進む。ブロック415で、マルチキャスト受信ノード20は、入力マルチキャストパケットがMPキャッシュテーブル500にリストされているか判断する。マルチキャストパケットがすでにリストされていれば、ブロック430で、パケットは無視されて破棄される。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0079】
マルチキャストパケットがMPキャッシュテーブル500内のいずれのパケットとも一致しない場合は、マルチキャスト受信ノード20は、ブロック420で、入力マルチキャストパケットについての情報をMPキャッシュテーブル500に追加する。具体的には、マルチキャスト受信ノード20は、マルチキャストパケットのマルチキャストセッションID、送信元識別子、およびシーケンス番号をMPキャッシュテーブル500に追加する
。その後、ブロック430で、マルチキャストパケットは破棄される。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0080】
図11は、本発明の第3の実施形態に係るFN用のMPキャッシュテーブル500aの例を示す。図示されるように、MPキャッシュテーブル500aは、2つの異なるマルチキャストパケット(MP1とMP2)を含む。各マルチキャストパケットに対して、MPキャッシュテーブル500aは、マルチキャストセッションID(GroupAdd)、マルチキャストパケットの送信元識別子、マルチキャストパケットのシーケンス番号(SeqNum)、マルチキャストパケットデータ(MPキャッシュ)、受信確認状態(ACK状態)、再送タイマ(Retran_Timer)、再送カウンタ(s_mp_c)、およびマルチキャストパケットのTTL値(C_MP_TTL)を含む。図11に示されるように、マルチキャストパケットの1つは受信確認されており、したがって再送タイマ状態は「オフ」である。
【0081】
図12〜図14(AおよびB)は、本発明の第4の実施形態に係るルーティング方法を示す。この実施形態によれば、マルチキャスト受信ノード20は受信し損ねたマルチキャストパケットを局所的に回復することができる。マルチキャスト受信ノード20は否定的確認(negative acknowledgement)を用いて、他のノード10にマルチキャストパケットを受信していないことを通知する。受信し損ねたマルチキャストパケットは、受信パケットにおける欠落しているシーケンス番号に基づいて検出される。この検出は受信したマルチキャストパケットの間でのシーケンス番号の比較に基づく。
【0082】
ブロック400で、マルチキャストパケットがノード10に到着する。マルチキャストパケットはマルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを含む。TTL値は、マルチキャストパケットが中継されるホップ数である。各ホップで、FN90はTTL値を減少させる。TTL値は、同一のマルチキャストデータパケットが転送させる回数を制限する機能を果たす。
【0083】
ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック800で、ノード10はFN90かマルチキャスト受信ノードであるかを判断する。ノード10がマルチキャスト受信ノード20であれば、処理は図13のブロック415に移動する。
【0084】
ブロック415で、マルチキャスト受信ノード20は、MPキャッシュテーブル(例えば、図15B、500c)内に入力マルチキャストパケットがリストされているか判断する。
【0085】
マルチキャストパケットがMPキャッシュテーブル500c内のいずれのパケットとも一致しない場合は、マルチキャスト受信ノード20は、受信したマルチキャストパケットについての情報をMPキャッシュテーブル500cに追加し、ブロック1300でマルチキャストパケットが不足していないか判断する。マルチキャスト受信ノード20は、マルチキャストセッションID、送信元識別子、シーケンス番号、およびマルチキャストパケットデータをMPキャッシュテーブル500cに追加する。マルチキャスト受信ノード500cのMPキャッシュテーブル500cは、ネガティブACK再送タイマ(NACK再送タイマ:NACK_Retran_Timer)も含む。NACK再送タイマは、近くのFN90やマルチキャスト受信ノード20から同一のマルチキャストパケットが複数回再送信される回数を抑制または制限するために用いられる。
【0086】
NACK再送タイマの時間は、ノード数、データパケットに含まれるデータの種類、ノード10の移動速度、およびその他のユーザ定義の基準に応じて変更可能である。例えば、12msの再送時間を利用することができる。メッセージに含まれるデータが高い優先度のメッセージであれば、再送時間を短くしても良い。あるいは、メッセージが低い優先度のメッセージであれば、再送時間を長くしても良い。回復遅延は再送時間の値に依存する。再送時間が小さいほど、遅延は短くなる。しかしながら、小さくしすぎると多くの再送信が発生し、不必要な再送信が生じる。
【0087】
マルチキャスト受信ノード20は、受信した全てのマルチキャストパケットについてシーケンス番号を調べることで、受信し損ねたマルチキャストパケットを検出する。検出はブロック1305で行われる。例えば、マルチキャスト受信ノード20がシーケンス番号10、11、13のマルチキャストパケットを受信した場合、シーケンス番号12のマルチキャストパケットが抜けている。
【0088】
ブロック1305においてマルチキャストパケットが抜けている場合、マルチキャスト受信ノード20は、ブロック1310で、ネガティブACK(NACK)をマルチキャストする。
【0089】
NACKは、抜けているマルチキャストパケットのマルチキャストセッションID、送信元識別子、およびシーケンス番号を含む。その後、ブロック430で、入力マルチキャストパケットは破棄される。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0090】
ブロック1305でマルチキャストパケットが抜けている場合、ブロック430で、マルチキャスト受信ノード20は入力マルチキャストパケットを棄てる。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0091】
ブロック415においてマルチキャストパケットがMPキャッシュテーブル500c内のいずれかのパケットと同一であれば、ブロック1200で、マルチキャスト受信ノード20はマルチキャストパケットのNACK再送タイマが「オン」であり満了していないか判断する。この判断はMPキャッシュテーブル500cからの情報に基づく。(ブロック1200において)NACK再送タイマがオンであれば(図12に示す機能ブロックと同じ)、ブロック1205でNACK再送タイマは停止される(図12に示す機能ブロックと同じ)。マルチキャスト受信ノード20は、NACK再送タイマの状態を「オフ」に変更する。これは、同一のマルチキャストが不必要に再送信されるのを抑制するために行われる。そしてブロック430で、マルチキャスト受信ノード20入力マルチキャストパケットを棄てる。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0092】
NACK再送タイマが(ブロック1200において)「オフ」であれば、ブロック430で、マルチキャスト受信ノード20は入力マルチキャストパケットを棄てる。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0093】
図12に戻って、ブロック800においてノード10がFN90であれば、処理はブロック415(図12)へ進む。
【0094】
マルチキャストパケットがMPキャッシュテーブル(図15A、500b)内のいずれのパケットとも一致しない場合は、ブロック420で、FN90は受信したマルチキャストパケットをMPキャッシュテーブル500bに追加する。
【0095】
FN90は、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを抽出し、この情報をMPキャッシュテーブル500bに追加する。さらに、FN90は再送カウンタをゼロに初期化する。再送カウンタ(s_mp_c)は、マルチキャストパケットが再送されうる回数を表す。ある実施形態では、マルチキャストメッセージが再送される回数はあらかじめ定められた最大値に制限される。あらかじめ定められた最大値は全ノード10に対して同じであっても良い。別の実施形態では、あらかじめ定められた最大値はGHや送信元ノード700のような特定のノードに対して変更可能としても良い。
【0096】
MPキャッシュテーブルはFN90とマルチキャスト受信ノード20とで異なる。FN90用には、MPキャッシュテーブル500bは、マルチキャストパケットについてのマルチキャストセッションID、送信元識別子、シーケンス番号、マルチキャストパケットデータ、ACK状態、再送タイマ値、再送カウンタ、TTL値、およびネガティブACK再送タイマ(NACK再送タイマ)を含む。ACK状態は「未確認」または「確認済み」のいずれかであり得る。再送タイマ値はオンかオフのいずれかであり得る。タイマがオンであれば、再送タイマ値は初期設定タイマ値といつ再送タイマ値が満了したかの指示も含む。マルチキャスト受信ノード20用には、MPキャッシュテーブル500cは、マルチキャストセッションID、送信元識別子、およびシーケンス番号だけを含む。
【0097】
ブロック805で、FN90はACK状態を「未確認」に初期化する。FN90はどのマルチキャストパケットが受信確認され受信されたかを追跡できる。さらに、FN90は再送タイマ値をオンに初期化し、タイマを再送時間に設定する。再送時間は、データパケットに含まれるデータの種類、FN90の移動速度、およびその他のユーザ定義の基準に応じて変更可能である。
【0098】
ブロック810で、再送カウンタを1増分する。すなわちs_mp_c+1にする。再送カウンタが増分された後、ブロック605で、FN90はマルチキャストパケットを一度転送する。FN90は、転送の前にマルチキャストパケットのTTL値から1減算する。したがって、次ホップFNはマルチキャストパケットを送っているFN90よりも小さいTTL値を含むマルチキャストパケットを受信する。ブロック440で、FN90はアイドルになる。
【0099】
ブロック415においてマルチキャストパケットがMPキャッシュテーブル500c内のいずれかのパケットと同一であれば、ブロック1200で、マルチキャスト受信ノード20はNACK再送タイマが「オン」であり満了していないか判断する。この判断はMPキャッシュテーブル500cからの情報に基づく。(ブロック1200において)NACK再送タイマがオンであれば、ブロック1205でNACK再送タイマは停止される。マルチキャスト受信ノード20は、NACK再送タイマの状態を「オフ」に変更する。これは、同一のマルチキャストが不必要に再送信されるのを抑制するために行われる。
【0100】
NACK再送タイマが(ブロック1200において)「オフ」であれば、処理はブロック815へ進む。
【0101】
ブロック815で、FN90は同一のマルチキャストパケットのオフセットTTL値(In_MP_TTL+1)とTTL値とを比較する。同一のマルチキャストパケットのTTL値はMPキャッシュテーブル500bから取り出される。MPキャッシュテーブル500bから取り出されたTTL値がオフセット値よりも大きくない場合は、ブロック430で、入力マルチキャストパケットは無視されて破棄される。このマルチキャストパケットは上流ノードから発生したものである。マルチキャストパケットの転送は受信確認されない。ブロック440で、FN90はアイドルになる。
【0102】
ブロック815においてMPキャッシュテーブル500bから取り出されたTTL値がオフセット値よりも大きい場合は、ブロック820で、FN90はこのマルチキャストパケットがすでに受信確認されたか判断する。
【0103】
FN90はMPキャッシュテーブル500bから同一のマルチキャストパケットについてのACK状態を取り出す。同一のマルチキャストパケットがすでに受信確認されていれば、ブロック430で、入力マルチキャストパケットは無視されて破棄される。ブロック440で、FN90はアイドルになる。MPキャッシュテーブル500bに変更はない。ブロック820において同一のマルチキャストパケットが受信確認されていなければ、本方法はブロック825へ進む。
【0104】
ブロック825で、FN90は再送タイマを停止する。さらに、FN90は、キャッシュテーブル500b内の再送タイマ値を「オフ」に変え、ACK状態を「確認済み」に変える。その後、ブロック430で入力マルチキャストパケットは破棄される。ブロック440で、FN90はアイドルになる。マルチキャストパケット転送の受信が確認される。
【0105】
図14Aは、NACKを処理する機能ブロックを示す。NACK処理の動作プロセスは、FN90とマルチキャスト受信ノードとで同じである。
【0106】
ブロック1400で、ノード10はNACKパケットを受信する。ノード10は、受信パケットに含まれる情報に基づいてそのパケットがNACKパケットであるか判断する。次にブロック405で、ノード10は、マルチキャストの参加者、すなわちFN90またはマルチキャスト受信ノード20であるか判断する。
【0107】
ブロック405で、ノード10は受信したNACKパケットからマルチキャストグループIDを抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにそのパケットのNACKは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック415で、ノード10はマルチキャストパケットがMPキャッシュテーブル(500bまたは500c)にあるか判断する。例えば、マルチキャストパケットの情報エントリがMPキャッシュテーブル(500bまたは500c)にリストされているか確認する。
【0108】
ブロック415においてマルチキャストパケットがMPキャッシュテーブル内のいずれかのパケットと同一であれば、ブロック1200で、ノード10はNACK再送タイマが「オン」であるか判断する。この判断はMPキャッシュテーブル(500bまたは500c)からの情報に基づく。NACK再送タイマが(ブロック1200で)オンであれば、ブロック440で、ノード10はアイドルになる。反対に、NACK再送タイマが(ブロック1200で)「オフ」であれば、ブロック1405で、ノード10はNACK再送タイマを所定値に設定する。言い換えると、ノード10はNACK再送タイマの状態を「オン」に変える。NACK再送タイマはNACK期間の計時を開始する。
【0109】
図14Bは、NACK再送タイマが満了した際のマルチキャストパケットの再送の機能ブロックを示す。ブロック1410で、NACK再送タイマが満了する。ノード10はNACK再送タイマの状態を「オフ」に変える。ブロック605で、ノード10はマルチキャストパケットを再送または転送する。ブロック440で、ノード10はアイドルになる。
【0110】
図15Aは、本発明の第4の実施形態に係るFN90のMPキャッシュテーブル500bの例を示す。図示されるように、MPキャッシュテーブル500bは、2つの異なるマルチキャストパケット(MP1とMP2)を含む。各マルチキャストパケットに対して、MPキャッシュテーブル500bは、マルチキャストセッションID(GroupAdd)、送信元識別子、マルチキャストパケットのシーケンス番号(SeqNum)、マルチキャストパケットデータ(MPキャッシュ)、受信確認状態(ACK状態)、再送タイマ(Retran_Timer)、再送カウンタ(s_mp_c)、マルチキャストパケットのTTL値(C_MP_TTL)、およびネガティブACK再送タイマ(NACK再送タイマ)を含む。図15Aに示されるように、NACK再送タイマはマルチキャストパケットの一方についてオンである。
【0111】
図15Bは、本発明の第4の実施形態に係るマルチキャスト受信ノードのMPキャッシュテーブル500Cの例を示す。図示されるように、MPキャッシュテーブル500bは、2つの異なるマルチキャストパケット(MP1とMP2)を含む。各マルチキャストパケットに対して、MPキャッシュテーブル500cは、マルチキャストセッションID(GroupAdd)、送信元識別子、マルチキャストパケットのシーケンス番号(SeqNum)、およびネガティブACK再送タイマ(NACK再送タイマ)を含む。
【0112】
図16は、本発明の第5の実施形態に係るルーティング方法を示す。本発明の第5の実施形態は、マルチキャストパケットが複数回中継される点を除いて、第3の実施形態と同様である。
【0113】
ブロック400で、マルチキャストパケットがノード10に到着する。マルチキャストパケットは、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを含む。TTL値は、マルチキャストパケットが中継されるホップ数である。
【0114】
ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック800で、ノード10はFN90かマルチキャスト受信ノードであるかを判断する。ノード10がマルチキャスト受信ノード20であれば、処理は図10の機能ブロック415へ進む。ノード10がマルチキャストセッションのFN90であれば、ブロック415(図16)で、FN90はマルチキャストパケットがMPキャッシュテーブル(例えば、500a)内にあるか判断する。
【0115】
マルチキャストパケットがMPキャッシュテーブル500a内のいずれのパケットとも一致しない場合は、ブロック420で、FN90は受信したマルチキャストパケットをキャッシュテーブル500aへ追加する。
【0116】
FN90は、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを抽出し、この情報をMPキャッシュテーブル500aに追加する。さらに、FN90は再送カウンタをゼロに初期化する。再送カウンタ(s_mp_c)は、マルチキャストパケットが再送されうる回数を表す。第3の実施形態と同様に、MPキャッシュテーブルはFN90とマルチキャスト受信ノードとで異なる。MPキャッシュテーブル(例えば、500aおよび500)は、第3の実施形態と同一の情報を含む。
【0117】
ブロック805で、FN90はACK状態を「未確認」に初期化する。FN90はどのマルチキャストパケットが受信確認され受信されたかを追跡できる。さらに、FN90は再送タイマ値をオンに初期化し、タイマを再送時間に設定する。再送時間は、データパケットに含まれるデータの種類、FN90の移動速度、およびその他のユーザ定義の基準に応じて変更可能である。
【0118】
ブロック810で、再送カウンタが1増分する。すなわちs_mp_c+1にする。再送カウンタが増分された後、ブロック605で、FN90はマルチキャストパケットをN回転送する。ある実施形態では、FN90はマルチキャストパケットをN回連続して転送する。パケットが転送される数字「N」回は予め定められていて変更可能である。到達率の増加とデータオーバヘッドの増加にはトレードオフがある。数字「N」が増えるにしたがって、データオーバヘッドが著しく増加するが、到達率もまた増加する。別の実施形態では、FN90はパケットをN回同時に転送する。
【0119】
FN90は、転送の前にマルチキャストパケットのTTL値から1減算する。したがって、次ホップFNはマルチキャストパケットを送っているFN90よりも小さいTTL値を含むマルチキャストパケットを受信する。ブロック440で、FN90はアイドルになる。
【0120】
マルチキャストパケットがMPキャッシュテーブル500a内のいずれかのパケットと同一であれば、本方法はブロック815へ進む。
【0121】
FN90は入力マルチキャストパケットのTTL値を判断する。上記したようにTTL値は特定のマルチキャストパケットのホップ数を制御するために用いられる。さらにこの実施形態では、TTL値は送信ノード10および受信ノード10の相対的な位置を決定するためにも用いられる。具体的には、マルチキャストパケットが転送されるたびに、ノード10はTTL値から1減算する(すなわち、TTL−1)。特定のFN90から下流にあるノード10から受信されたマルチキャストパケットのTTL値は、FN90から転送された同一のマルチキャストパケットのTTL値よりも小さい。特定のFN90から上流にあるノード10から受信されたマルチキャストパケットのTTL値は、FN90から転送された同一のマルチキャストパケットのTTL値よりも大きい。特定のFN90と同じホップ数のノード10から受信されたマルチキャストパケットは、同一のTTL値を持つ。
【0122】
FN90は、FN90による最初のマルチキャストパケットの転送を補うために、判定されたTTL値にオフセット値の1を加える。これによりオフセットTTL値が生成される。
【0123】
ブロック815で、FN90は、オフセットTTL値(In_MP_TTL+1)と同一のマルチキャストパケットのTTL値とを比較する。同一のマルチキャストパケットのTTL値は、MPキャッシュテーブルから取り出される。MPキャッシュテーブルから取り出されたTTL値がオフセット値よりも大きくない場合は、ブロック430で、入力マルチキャストパケットは無視されて破棄される。このマルチキャストパケットは上流ノードから発生したものである。マルチキャストパケットの転送は受信確認されない。ブロック440で、FN90はアイドルになる。
【0124】
ブロック815においてMPキャッシュテーブル500aから取り出されたTTL値がオフセット値よりも大きい場合は、ブロック820で、FN90はこのマルチキャストパケットがすでに受信確認されたか判断する。
【0125】
FN90はMPキャッシュテーブル500aから同一のマルチキャストパケットについてのACK状態を取り出す。同一のマルチキャストパケットがすでに受信確認されていれば、ブロック430で、入力マルチキャストパケットは無視されて破棄される。ブロック440で、FN90はアイドルになる。MPキャッシュテーブル500aに変更はない。ブロック820において同一のマルチキャストパケットが受信確認されていなければ、本方法はブロック825へ進む。
【0126】
ブロック825で、FN90は再送タイマを停止する。さらに、FN90は、キャッシュテーブル500a内の再送タイマ値を「オフ」に変え、ACK状態を「確認済み」に変える。その後、ブロック430で入力マルチキャストパケットは破棄される。ブロック440で、FN90はアイドルになる。マルチキャストパケット転送の受信が確認される。
【0127】
残りの機能ブロックは図9および図10で示された機能ブロックと一致しているので、詳しくは説明しない。
【0128】
図17は、本発明の第6の実施形態に係るマルチキャスト受信ノード20の機能ブロックを示す。本発明の第6の実施形態は、本発明の第2および第3の実施形態の機能ブロックを組み合わせたものである。FN90の機能ブロックは図8および図9で示された機能ブロックと一致しているので、詳しくは説明しない。
【0129】
ブロック415で、マルチキャスト受信ノード20は、マルチキャストパケットがMPキャッシュテーブル(例えば、500a)内にあるか判断する。マルチキャストパケットがMPキャッシュテーブル500aないにあれば、ブロック430で、マルチキャストパケットは破棄される。ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0130】
マルチキャストパケットがMPキャッシュテーブル500内に無い、すなわち、同一ではない場合は、マルチキャストパケットに含まれる情報がMPキャッシュテーブル500aに追加される。ブロック600で、マルチキャスト受信ノード20は、マルチキャストパケットに割り当てられたランダムな確率と、確率閾値とを比較する。マルチキャストパケットに割り当てられたランダムな確率が確率閾値よりも小さければ、ブロック605で、マルチキャスト受信ノード20は受信したマルチキャストパケットを転送する。そして、ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0131】
マルチキャストパケットに割り当てられたランダムな確率が確率閾値以上であれば、ブロック430で、マルチキャスト受信ノード20は受信したマルチキャストパケットを破棄する。そして、ブロック440で、マルチキャスト受信ノード20はアイドルになる。
【0132】
図18は、本発明の第7の実施形態に係るルーティング方法を示す。第7の実施形態によれば、、マルチキャストパケットの送信はあらかじめ定められた基準に基づいて抑制される。
【0133】
図18に示すように、マルチキャストパケットがノード10に到着する。マルチキャストパケットは、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを含む。TTL値は、マルチキャストパケットが中継されるホップ数である。
【0134】
ブロック405で、ノード10はパケットからマルチキャストグループ識別子を抽出して、ノード10がマルチキャストセッションのメンバであるか判断する。この判断はマルチキャストルーティングテーブルに基づく。ノード10がマルチキャストセッションのメ
ンバでなければ、ブロック410で、それ以上の処理をせずにマルチキャストパケットは破棄される。ノード10がマルチキャストセッションのメンバであれば、ブロック800で、ノード10はFN90かマルチキャスト受信ノードであるかを判断する。ノード10がマルチキャスト受信ノードであれば、処理はブロック415(受信者用)に移動する。ノード10がマルチキャストセッションのFN90であれば、ブロック415(FN90用)で、FN90はマルチキャストパケットがMPキャッシュテーブル(例えば、500d)内にあるか判断する。
【0135】
マルチキャストパケットがMPキャッシュテーブル500d内のいずれのパケットとも一致しない場合は、ブロック420で、FN90またはマルチキャスト受信ノード20は受信したマルチキャストパケットをMPキャッシュテーブル500dに付加する。
【0136】
FN90は、マルチキャストグループID、送信元識別子、シーケンス番号、Time−to−Live(TTL)値、およびデータを抽出し、この情報をMPキャッシュテーブル500dに付加する。さらに、FN90は再送カウンタをゼロに初期化する。再送カウンタ(s_mp_c)は、マルチキャストパケットが再送されうる回数を表す。この実施形態では、s_mp_cの値は「0」か「1」である。FN90のMPキャッシュテーブル500dはランダム転送タイマも含む。
【0137】
MPキャッシュテーブルはFN90とマルチキャスト受信ノード20とで異なる。マルチキャスト受信ノード20のMPキャッシュテーブル500dは、マルチキャストセッションID、送信元識別子、およびマルチキャストパケットのシーケンス番号を含む。したがって、ブロック420で、マルチキャスト受信ノード20は、マルチキャストセッションID、送信元識別子、およびシーケンス番号をMPキャッシュテーブル500に付加する。
【0138】
ブロック425で、ノード10はマルチキャストセッションのFN90であるか判断する。この判断は転送テーブルおよびMPキャッシュテーブル(例えば、500)内の情報に基づく。ノード10がマルチキャストパケットのFN90でなければ、ブロック419で、入力マルチキャストパケットは破棄される。ノードがFN90であれば、ブロック1800で、FNは転送タイマをランダム値に設定する。このランダム値によりマルチキャストパケットの転送が妨げられる。FN90は、ランダム値が満了、すなわちランダム転送タイマが満了したときのみマルチキャストパケットを転送する。
【0139】
ブロック415において、マルチキャストパケットがMPキャッシュテーブル500d内にすでに存在する場合は、ブロック1802で、FN90はこのパケットをすでに転送したか、すなわちs_mp_c=1であるか判断する。カウンタ(s_mp_c)が1に等しければ、パケットはすでに転送されている。カウンタ(s_mp_c)が0に等しければ、パケットはまだ転送されていない。FNはMPキャッシュテーブル500dからカウンタ値を取り出す。ブロック1802においてカウンタ(s_mp_c)が1に等しければ、ステップ430で、マルチキャストパケットは転送されることなく破棄される。ブロック1802で、カウンタ(s_mp_c)が0に等しければ、FN90は入力マルチキャストパケットのTTL値を判断する(ブロック815)。上記したように、TTL値は特定のマルチキャストパケットのホップ数を制御するために用いられる。さらに、この実施形態では、TTL値は送信ノード10および受信ノード10の相対的な位置を決定するためにも用いられる。FN90は、FN90による最初のマルチキャストパケットの転送を補うために、判定されたTTL値にオフセット値の1を加える。これによりオフセットTTL値が生成される。
【0140】
ブロック815で、FN90は、オフセットTTL値(In_MP_TTL+1)と同
一のマルチキャストパケットのTTL値とを比較する。同一のマルチキャストパケットのTTL値は、MPキャッシュテーブル500dから取り出される。MPキャッシュテーブル500dから取り出されたTTL値がオフセット値よりも大きくない場合は、(ブロック430で)入力マルチキャストパケットは破棄され、FN90はアイドルになる。このマルチキャストパケットは上流ノードまたはピアノードから発生したものである。ブロック815においてMPキャッシュテーブル500dから取り出されたTTL値がオフセット値よりも大きい場合は、入力マルチキャストパケットは例えば下流FN90から発生したものであり、FN90はマルチキャストパケットを転送する必要が無い。
【0141】
ブロック1805で、FNはマルチキャストパケットのランダム転送タイマを停止する。言い換えると、FNはランダム転送タイマの状態を「オン」から「オフ」に変更する。その後、ブロック430でマルチキャストパケットは破棄される。ブロック440で、FN90はアイドルになる。
【0142】
ランダム転送タイマが満了したら、FN90はマルチキャストパケットを転送する。ブロック1810で、ランダム転送タイマが満了し、FN90がランダム転送タイマの状態を「オン」から「オフ」に変更する。その後、ブロック605で、FN90はマルチキャストパケットを転送する。FN90はTTL値を1だけ減らす。マルチキャストパケット内のTTL値を1だけ減少させた後、FN90マルチキャストパケットを転送する。さらに、マルチキャストパケットの転送の後、ブロック1812でFNは再送カウンタ(s_mp_c)を1に設定する。ブロック440で、FN90はアイドルになる。第7の実施形態によれば、FN90によるマルチキャストパケットの転送は軽く抑制される。
【0143】
図19は、本発明の第8の実施形態に係るルーティング方法を示す。第8の実施形態によれば、マルチキャストパケットの転送は厳しく制限される。図19に示される機能ブロックの多くは図18と同じであり、したがって、詳しくは説明しない。第7と第8の実施形態の違いは、ブロック1900における(ブロック815と対照的な)TTL値の比較である。ブロック1900で、入力マルチキャストパケットのTTL値がMPキャッシュテーブル(例えば、500d)に格納されたTTL値と比較される。
【0144】
入力マルチキャストパケットのTTL値にはオフセット値が加えられない。
【0145】
MPキャッシュテーブル(例えば、500d)から取り出されたTTL値が入力TTL値より大きくなければ、入力マルチキャストパケットは(ブロック430で)破棄され、ブロック440でFN90はアイドルになる。このマルチキャストパケットは上流ノードから発生したものである。ブロック1900においてMPキャッシュテーブル500dから取り出されたTTL値が入力TTL値より大きければ、入力マルチキャストパケットは例えばピアや下流ノードから発生したものである。FN90は、マルチキャストパケットの転送をやめて、マルチキャストパケットのランダム転送タイマを停止する。
【0146】
図20は、本発明の第9の実施形態に係るルーティング方法を示す。本発明の第9の実施形態は2段階の抑制方法を用いる。図20は、2つの機能ブロックが追加されている以外は、図18と同様である。同一の機能ブロックについては繰り返しては説明しない。
【0147】
上述したように、ブロック815で、FN90は、オフセットTTL値(IN_MP_TTL+1)を同一のマルチキャストパケットのTTL値と比較する。同一のマルチキャストパケットのTTL値はMPキャッシュテーブル(例えば、500d)から取り出される。MPキャッシュテーブル500dから取り出されたTTL値がオフセット値よりも大きくなければ、入力マルチキャストパケットは(ブロック430で)破棄され、ブロック440でFN90はアイドルになる。しかしながら、第9の実施形態では、MPキャッシ
ュテーブル500dから取り出されたTTL値がオフセット値よりも大きくなければ、ブロック2000で、FNはMPキャッシュテーブルから取り出されたTTL値がオフセット値と等しいか判断する。MPキャッシュテーブル500dから取り出されたTTL値がオフセット値と等しくなければ、入力マルチキャストパケットは破棄され、ブロック440でFN90はアイドルになる。しかしながら、MPキャッシュテーブル500dから取り出されたTTL値がオフセット値と等しい、すなわち、マルチキャストパケットが周囲のピアから受信されたものであれば、ブロック2005で、マルチキャストパケットのランダム転送タイマが停止されて、別のランダム値に再設定される。マルチキャストパケットのランダム転送タイマ延長される。この時間延長により、同一のマルチキャストパケットのTTL値よりも小さいオフセットTTL値を有する入力マルチキャストパケットを、ランダム転送タイマが満了する前に受信する機会が増える。したがって、不必要な転送が抑制され、重複するパケットが生成することが少ない。
【0148】
図21は、第7〜第9の実施形態に係るFN90のMPキャッシュテーブル500dの例を示す。図示されるように、MPキャッシュテーブル500dは、2つの異なるマルチキャストパケット(MP1およびMP2)を含む。各マルチキャストパケットに対して、MPキャッシュテーブル500bは、マルチキャストセッションID(Group Add)、送信元識別子、マルチキャストパケットのシーケンス番号(SeqNum)、マルチキャストパケットデータ(MPキャッシュ)、再送カウンタ(s_mp_c)、マルチキャストパケットのTTL値(C_MP_TTL)、およびランダム転送タイマ(Random_Forward_Timer)を含む。図21に示されるように、マルチキャストパケットの一方についてオンである。
【0149】
本発明の第9の実施形態は、マルチキャストパケットと同様にブロードキャストパケットにも適用できる。しかしながら、ブロードキャスト通信を行うためには、すべてのノードがFN90になる。
【0150】
本発明はここまで特定の例示的な実施形態を参照して説明されている。本発明の範囲から逸脱することなくいくらかの代替や変更は当業者にとって明らかであろう。例示的な実施形態は説明を意図したものであり、添付の特許請求の範囲によって定義される本発明の範囲を限定するものではない。
【特許請求の範囲】
【請求項1】
少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、
前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、
前記メッセージが以前に受信したものであるか判断するステップと、
前記メッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、
前記マルチキャストメッセージを受信したノードが転送ノードであるか判断するステップと、
前記マルチキャストメッセージを転送するための待機時間をランダムに設定するステップと、
前記待機時間が満了したときに、前記マルチキャストメッセージを転送するステップと、
を含む、マルチキャストメッセージのルーティング方法。
【請求項2】
前記メッセージが以前に受信したものである場合に、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを前記ランダムに設定された待機時間内に下流ノードから受信したときは、前記ランダムに設定された待機時間を停止するステップをさらに含む、
請求項1に記載のマルチキャストメッセージのルーティング方法。
【請求項3】
前記待機時間が停止された場合は、前記マルチキャストメッセージは転送されない、
請求項2に記載のマルチキャストメッセージのルーティング方法。
【請求項4】
第2のマルチキャストメッセージが下流ノードから受信されたかの判断は、
第2のマルチキャストメッセージからTime−to−Live値を抽出する工程と、
前記Time−to−Live値にプリセット値を加えてオフセットTime−to−Live値を生成する工程と;
前記マルチキャスト転送テーブルから同一のメッセージを含むマルチキャストメッセージのTime−to−Live値を取り出す工程と、
前記オフセットTime−to−Live値と前記取り出されたTime−to−Live値とを比較する工程と、
を含み、
前記取り出されたTime−to−Live値が前記オフセットTime−to−Live値よりも大きい場合に、前記待機時間が停止される、
請求項2に記載のマルチキャストメッセージのルーティング方法。
【請求項5】
前記取り出されたTime−to−Live値が前記オフセットTime−to−Live値と等しい場合に、前記待機時間はランダム値にリセットされる、
請求項4に記載のマルチキャストメッセージのルーティング方法。
【請求項6】
転送後にACKフラグを未確認に設定するステップと、
再送時間を所定時間に設定するステップと、
をさらに含む、請求項1に記載のマルチキャストメッセージのルーティング方法。
【請求項7】
前記メッセージが以前に受信されたものである場合に、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャ
ストメッセージを下流ノードから受信したときは、前記再送時間を停止するステップをさらに含む、
請求項6に記載のマルチキャストメッセージのルーティング方法。
【請求項8】
前記再送時間を停止した後に、ACKフラグを確認済みに設定するステップをさらに含む、
請求項7に記載のマルチキャストメッセージのルーティング方法。
【請求項9】
前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、
再送後に前記送信時間を所定時間に設定するステップと、
をさらに含む、請求項7に記載のマルチキャストメッセージのルーティング方法。
【請求項10】
再送の上限に達したか判断するステップと、
前記判断に基づいて、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、
再送カウンタを増加させるステップと、
再送後に前記再送時間を所定時間に設定するステップと、
をさらに含み、
再送の上限に達した場合には、再送時間が停止される、
請求項7に記載のマルチキャストメッセージのルーティング方法。
【請求項11】
少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、
前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、
前記メッセージが以前に受信したものであるか判断するステップと、
前記メッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、
前記マルチキャストメッセージを受信したノードがマルチキャスト受信ノードであるか判断するステップと、
マルチキャスト受信ノードに確率値をランダムに割り当てるステップと、
前記ランダムに割り当てられた確率値とプリセット確率閾値とを比較するステップと、
前記比較に基づいて前記マルチキャストメッセージを転送するステップと、
を含む、マルチキャストメッセージのルーティング方法。
【請求項12】
前記プリセット確率閾値を設定するステップをさらに含む
請求項11に記載のマルチキャストメッセージのルーティング方法するステップ。
【請求項13】
前記マルチキャスト転送テーブルは、前記グループ宛先と前記送信元識別子と前記シーケンス番号とを含む、
請求項11に記載のマルチキャストメッセージのルーティング方法。
【請求項14】
前記マルチキャスト転送テーブルは、前記グループ宛先と前記送信元識別子と前記シーケンス番号と前記メッセージと前記ACKフラグと前記再送時間値と前記再送カウンタと前記Time−to−Live値とを含む、
請求項10に記載のマルチキャストメッセージのルーティング方法。
【請求項15】
転送後にACKフラグを未確認に設定するステップと、
再送時間を所定時間に設定するステップと、
をさらに含む、請求項11に記載のマルチキャストメッセージのルーティング方法
【請求項16】
再送カウンタを増加させるステップをさらに含む、
請求項11に記載のマルチキャストメッセージのルーティング方法。
【請求項17】
前記メッセージが以前に受信されたものである場合に、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを下流ノードから受信したときに、前記再送時間を停止するステップをさらに含む、
請求項15に記載のマルチキャストメッセージのルーティング方法。
【請求項18】
前記再送時間を停止した後に、ACKフラグを確認済みに設定するステップをさらに含む、
請求項15に記載のマルチキャストメッセージのルーティング方法。
【請求項19】
再送カウンタの値に基づいて、再送の上限に達したか判断するステップと、
前記判断に基づいて、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、
再送カウンタを増加させるステップと、
再送後に前記再送時間を所定時間に設定するステップと、
をさらに含み、
再送の上限に達した場合には、再送時間が停止される、
請求項15に記載のマルチキャストメッセージのルーティング方法。
【請求項20】
少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、
前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、
前記メッセージが以前に受信したものであるか判断するステップと、
を含み、
前記メッセージが以前に受信されたものである場合に、
前記Time−to−Live値にプリセット値を加えてオフセットTime−to−Live値を生成する工程と、
前記オフセットTime−to−Live値と前記マルチキャスト転送テーブル内のTime−to−Live値を比較する工程と、
前記オフセットTime−to−Live値が前記マルチキャスト転送テーブル内のTime−to−Live値以上である場合に、前記マルチキャストメッセージを転送することなく破棄する工程と、
を含む、マルチキャストメッセージのルーティング方法。
【請求項21】
前記マルチキャストメッセージが以前に受信したものではない場合に、
ACKフラグを未確認に設定する工程と、
再送カウンタを増加させる工程と、
再送時間を所定値に設定する工程と、
マルチキャストメッセージを転送する工程と、
をさらに含む、請求項20に記載のマルチキャストメッセージのルーティング方法。
【請求項22】
前記オフセットTime−to−Live値が前記マルチキャスト転送テーブル内のT
ime−to−Live値よりも小さい場合に、
ACKフラグを確認済みに設定する工程と、
前記再送時間を停止する工程と、
をさらに含む、請求項20に記載のマルチキャストメッセージのルーティング方法。
【請求項1】
少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、
前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、
前記メッセージが以前に受信したものであるか判断するステップと、
前記メッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、
前記マルチキャストメッセージを受信したノードが転送ノードであるか判断するステップと、
前記マルチキャストメッセージを転送するための待機時間をランダムに設定するステップと、
前記待機時間が満了したときに、前記マルチキャストメッセージを転送するステップと、
を含む、マルチキャストメッセージのルーティング方法。
【請求項2】
前記メッセージが以前に受信したものである場合に、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを前記ランダムに設定された待機時間内に下流ノードから受信したときは、前記ランダムに設定された待機時間を停止するステップをさらに含む、
請求項1に記載のマルチキャストメッセージのルーティング方法。
【請求項3】
前記待機時間が停止された場合は、前記マルチキャストメッセージは転送されない、
請求項2に記載のマルチキャストメッセージのルーティング方法。
【請求項4】
第2のマルチキャストメッセージが下流ノードから受信されたかの判断は、
第2のマルチキャストメッセージからTime−to−Live値を抽出する工程と、
前記Time−to−Live値にプリセット値を加えてオフセットTime−to−Live値を生成する工程と;
前記マルチキャスト転送テーブルから同一のメッセージを含むマルチキャストメッセージのTime−to−Live値を取り出す工程と、
前記オフセットTime−to−Live値と前記取り出されたTime−to−Live値とを比較する工程と、
を含み、
前記取り出されたTime−to−Live値が前記オフセットTime−to−Live値よりも大きい場合に、前記待機時間が停止される、
請求項2に記載のマルチキャストメッセージのルーティング方法。
【請求項5】
前記取り出されたTime−to−Live値が前記オフセットTime−to−Live値と等しい場合に、前記待機時間はランダム値にリセットされる、
請求項4に記載のマルチキャストメッセージのルーティング方法。
【請求項6】
転送後にACKフラグを未確認に設定するステップと、
再送時間を所定時間に設定するステップと、
をさらに含む、請求項1に記載のマルチキャストメッセージのルーティング方法。
【請求項7】
前記メッセージが以前に受信されたものである場合に、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャ
ストメッセージを下流ノードから受信したときは、前記再送時間を停止するステップをさらに含む、
請求項6に記載のマルチキャストメッセージのルーティング方法。
【請求項8】
前記再送時間を停止した後に、ACKフラグを確認済みに設定するステップをさらに含む、
請求項7に記載のマルチキャストメッセージのルーティング方法。
【請求項9】
前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、
再送後に前記送信時間を所定時間に設定するステップと、
をさらに含む、請求項7に記載のマルチキャストメッセージのルーティング方法。
【請求項10】
再送の上限に達したか判断するステップと、
前記判断に基づいて、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、
再送カウンタを増加させるステップと、
再送後に前記再送時間を所定時間に設定するステップと、
をさらに含み、
再送の上限に達した場合には、再送時間が停止される、
請求項7に記載のマルチキャストメッセージのルーティング方法。
【請求項11】
少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、
前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、
前記メッセージが以前に受信したものであるか判断するステップと、
前記メッセージが以前に受信したものではないと判断された場合に、前記マルチキャストメッセージを前記マルチキャスト転送テーブルに追加するステップと、
前記マルチキャストメッセージを受信したノードがマルチキャスト受信ノードであるか判断するステップと、
マルチキャスト受信ノードに確率値をランダムに割り当てるステップと、
前記ランダムに割り当てられた確率値とプリセット確率閾値とを比較するステップと、
前記比較に基づいて前記マルチキャストメッセージを転送するステップと、
を含む、マルチキャストメッセージのルーティング方法。
【請求項12】
前記プリセット確率閾値を設定するステップをさらに含む
請求項11に記載のマルチキャストメッセージのルーティング方法するステップ。
【請求項13】
前記マルチキャスト転送テーブルは、前記グループ宛先と前記送信元識別子と前記シーケンス番号とを含む、
請求項11に記載のマルチキャストメッセージのルーティング方法。
【請求項14】
前記マルチキャスト転送テーブルは、前記グループ宛先と前記送信元識別子と前記シーケンス番号と前記メッセージと前記ACKフラグと前記再送時間値と前記再送カウンタと前記Time−to−Live値とを含む、
請求項10に記載のマルチキャストメッセージのルーティング方法。
【請求項15】
転送後にACKフラグを未確認に設定するステップと、
再送時間を所定時間に設定するステップと、
をさらに含む、請求項11に記載のマルチキャストメッセージのルーティング方法
【請求項16】
再送カウンタを増加させるステップをさらに含む、
請求項11に記載のマルチキャストメッセージのルーティング方法。
【請求項17】
前記メッセージが以前に受信されたものである場合に、少なくとも同一のメッセージと送信元識別子とシーケンス番号とマルチキャストグループ宛先とを含む第2のマルチキャストメッセージを下流ノードから受信したときに、前記再送時間を停止するステップをさらに含む、
請求項15に記載のマルチキャストメッセージのルーティング方法。
【請求項18】
前記再送時間を停止した後に、ACKフラグを確認済みに設定するステップをさらに含む、
請求項15に記載のマルチキャストメッセージのルーティング方法。
【請求項19】
再送カウンタの値に基づいて、再送の上限に達したか判断するステップと、
前記判断に基づいて、前記再送時間が満了したときに、前記マルチキャストメッセージを再送するステップと、
再送カウンタを増加させるステップと、
再送後に前記再送時間を所定時間に設定するステップと、
をさらに含み、
再送の上限に達した場合には、再送時間が停止される、
請求項15に記載のマルチキャストメッセージのルーティング方法。
【請求項20】
少なくともメッセージと送信元識別子とシーケンス番号とTime−to−Live値とマルチキャストグループ宛先とを含むマルチキャストメッセージを受信するステップと、
前記マルチキャストグループ宛先がマルチキャスト転送テーブル内に存在するか判断するステップと、
前記メッセージが以前に受信したものであるか判断するステップと、
を含み、
前記メッセージが以前に受信されたものである場合に、
前記Time−to−Live値にプリセット値を加えてオフセットTime−to−Live値を生成する工程と、
前記オフセットTime−to−Live値と前記マルチキャスト転送テーブル内のTime−to−Live値を比較する工程と、
前記オフセットTime−to−Live値が前記マルチキャスト転送テーブル内のTime−to−Live値以上である場合に、前記マルチキャストメッセージを転送することなく破棄する工程と、
を含む、マルチキャストメッセージのルーティング方法。
【請求項21】
前記マルチキャストメッセージが以前に受信したものではない場合に、
ACKフラグを未確認に設定する工程と、
再送カウンタを増加させる工程と、
再送時間を所定値に設定する工程と、
マルチキャストメッセージを転送する工程と、
をさらに含む、請求項20に記載のマルチキャストメッセージのルーティング方法。
【請求項22】
前記オフセットTime−to−Live値が前記マルチキャスト転送テーブル内のT
ime−to−Live値よりも小さい場合に、
ACKフラグを確認済みに設定する工程と、
前記再送時間を停止する工程と、
をさらに含む、請求項20に記載のマルチキャストメッセージのルーティング方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14A】
【図14B】
【図15A】
【図15B】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14A】
【図14B】
【図15A】
【図15B】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【公表番号】特表2011−515037(P2011−515037A)
【公表日】平成23年5月12日(2011.5.12)
【国際特許分類】
【出願番号】特願2010−546885(P2010−546885)
【出願日】平成21年2月12日(2009.2.12)
【国際出願番号】PCT/US2009/033879
【国際公開番号】WO2009/102841
【国際公開日】平成21年8月20日(2009.8.20)
【出願人】(399047921)テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】(507302900)トヨタ インフォテクノロジー センター,ユー.エス.エー.,インコーポレイテッド (10)
【Fターム(参考)】
【公表日】平成23年5月12日(2011.5.12)
【国際特許分類】
【出願日】平成21年2月12日(2009.2.12)
【国際出願番号】PCT/US2009/033879
【国際公開番号】WO2009/102841
【国際公開日】平成21年8月20日(2009.8.20)
【出願人】(399047921)テルコーディア テクノロジーズ インコーポレイテッド (61)
【出願人】(507302900)トヨタ インフォテクノロジー センター,ユー.エス.エー.,インコーポレイテッド (10)
【Fターム(参考)】
[ Back to top ]