[an error occurred while processing this directive]
IETF MANET Working Group / INTERNET-DRAFT / Expiration: July 2000
Sung-Ju Lee / William Su / Mario Gerla
University of California, Los Angeles / January 2000
On-Demand Multicast Routing Protocol
(ODMRP) for Ad Hoc Networks
Status of this memo
（省略）
Abstract - 概要
On-Demand Multicast Routing Protocol (ODMRP)はアドホックネットワークのモバイルホスト向けのマルチキャストルーティングプロトコルである。ODMRPはtree-basedではなくmesh-basedであり、フォワーディンググループ（転送グループ：限定フラッディングによりマルチキャストパケットを転送するノードの部分集合）の概念を用いている。また、ODMRPは経路生成、マルチキャストグループのメンバ管理を動的に行うオンデマンド型である。帯域幅が限定され、トポロジの変化が激しく、また電源が限られているようなアドホックネットワークにODMRPは適している。
Contents - 目次
（省略）
1. Introduction - 導入
このドキュメントは、Wireless Adaptive Mobility (WAM) Laboratory（University of California, Los Angeles）
[20]にて開発されたOn-Demand Multicast Routing Protocol（ODMRP）
[14][15]について記述している。ODMRPはチャネルのオーバヘッド軽減し、スケーラビリティを改善する、”オンデマンド”なルーティングプロトコルである。ODMRPでは”フォワーディンググループ”
[5]という概念を用いている。フォワーディンググループはマルチチャストデータの転送に責任を持つノードの集合である。またフォワーディングメッシュは各マルチキャストグループごとに生成される。ツリーの代わりにメッシュを用いることによって、マルチキャストツリーの欠点（e.g. 経路が切断されやすい、トラフィックが一部に集中しやすい、頻繁にツリーの再構成が行われる、共有ツリーでは最短経路にならない、など）を回避することができる。マルチキャストメンバの管理はソフトステート型のアプローチをとっている。したがって、メンバがグループを離脱する際には明示的な宣言を行う必要がない。通信/ストレージのオーバヘッドの軽減と緩やかな接続性によって、ODMRPはモバイルワイヤレスネットワークにおいてより魅力的となるであろう。
以下にODMRPの特徴を記す。
○簡潔である
○通信、ストレージのオーバヘッドが少ない
○最新の最短経路を用いる
○信頼性のある経路とフォワーディンググループを選択する
○ホストの移動に対してロバストである
○代替経路を確保する
○ワイヤレス環境におけるブロードキャストを提供する
○ユニキャストルーティングの機能も持つ
2. Terminology - 用語説明
2.1. General Terms - 一般用語
ここではODMRPで用いる用語を定義する。
ノード（node）
IPを割り当てられたデバイス
隣接ノード（neighbor）
通信範囲内に存在するノード
フォワーディンググループ（forwarding group）
マルチキャストパケットの転送を受け持つノードの集合
マルチキャストメッシュ（multicast mesh）
フォワーディンググループのメンバ間に張られたコネクション
join query
マルチキャストメンバの募集と経路の確立・更新を行うために、マルチキャストの送信元によって送られる特別なデータパケット
join reply
マルチキャストメンバの募集と経路の確立・更新を行うために、マルチキャスト受信ノードとフォワーディングノードによってブロードキャストされるテーブル
2.2. Specification Language - キーワード
本稿で用いている次のキーワード ”MUST”、”MUST NOT”、”REQUIRED”、”SHALL”、”SHALL NOT”、”SHOULD”、”SHOULD NOT”、”RECOMMENDED”、”MAY”、”OPTIONAL”については、RFC 2119
[4]にて解説されている。
3. Protocol Overview - プロトコルの概要
3.1. Multicast Route and Mesh Creation - マルチキャストの経路とメッシュの作成
ODMRPでは、マルチキャストメンバとマルチキャスト経路の確立・更新は、マルチキャスト送信元によってオンデマンドに行われる。オンデマンド型のユニキャストルーティングプロトコルと同様に、requestフェーズとreplyフェーズから成っている。マルチキャスト送信元が送るべきパケットを持った際に、マルチキャスト経路とメンバが未知であれば、データのペイロードを上乗せした広告パケットを全メンバにフラッディングする。このパケットを”Join Query”と呼ぶ（パケットのフォーマットは4.1で示す）。Join Queryパケットは定期的にブロードキャストされ、メンバ情報の更新と経路の更新を行う。ノードがJoin Queryパケットを受け取ると、受信ノードは送信元アドレス（source address）とパケットのIDを”メッセージキャッシュ（Message Cache）”に保存する。メッセージキャッシュによりパケットの重複を調べることができる。上流ノードのアドレスは、ソースノードへ向かう際の次ホップのノード（next node）として”ルーティングテーブル（Routing Table）”に格納（更新）する。もし受け取ったJoin Queryパケットが重複しておらずTTL（Time-To-Live）の値が0より大きければ、そのパケットのある特定のフィールドを更新し、再ブロードキャストする（処理の詳細は5.1.2に示す）。
Join Queryパケットがマルチキャスト受信ノードへ届くと、受信ノードは”Join Reply”を生成し隣接ノードへブロードキャストする。ノードがこのJoin Replyパケットを受け取ると、そのノードはエントリの中のnext node addressが自分のアドレスと一致するかどうか調べる。一致すれば、そのノードは自分が送信ノードまでの経路上に位置していることを知り、FG_FLAG（Forwarding Group Flag）をセットしてフォワーディンググループに加わる。そして自身のJoin Replyパケットを生成しブロードキャストする。このパケットのnext node addressフィールドは、自身のルーティングテーブルを検索し埋める。このようにしてJoin Replyパケットはフォワーディンググループを伝達し、選択された経路に沿ってマルチキャスト送信ノードまで届く。このプロセスによって、送信ノードから受信ノードまでの経路が形成（更新）され、メッシュとフォワーディンググループが作成される。
|
■Join Reply of Node R1
| Sender |
Next Node |
| S1 |
l1 |
| S2 |
l2 |
■Join Reply of Node l1
|
上図の例でJoin Replyパケットの送信手順を見てみる。ノードS1とS2はマルチキャスト送信ノードであり、ノードR1とR2はマルチキャスト受信ノードである。ノードR2は、自身のJoin Replyパケットをl1を通してS1とS2に送信し、ノードR1は自身のJoin Replyパケットをl2を通してS2に送信する。受信ノード（R1とR2）がnext hop nodeに対してJoin Replyパケットを送信すると、中間のノードであるl1は、R1から受け取ったJoin Replyパケット中のnext node IDエントリが自分のIDと一致するので、FG_FLAGをセットし、自身のJoin Replyパケットを生成する。ここで注意すべき点は、受け取ったJoin ReplyパケットでのS2に対するnext node addressはl1ではないので、l1の生成するJoin ReplyパケットはS1に対しての1つのエントリしか持たない点である。一方でノードl2はFG_FLAGをセットし、自身のJoin Replyパケットを生成し、隣接ノードに送信する。ここで、l2は2つのJoin Replyパケットを受け取っているにもかかわらず、Join Replyパケットのブロードキャストは1回であることに注意する。これは、2番目に届いたパケットには送信ノードに関する新しい情報は含まれていないためである。このようにすることで、多数のマルチキャスト受信ノードが同一のリンクを共有している場合に、帯域のオーバヘッドを劇的に減少させることができる。
このマルチキャストグループの確立と経路の生成処理が終わると、マルチキャスト送信ノードは選択された経路とフォワーディンググループを通してマルチキャストを行うことができるようになる。送信すべきデータが存在している限り、送信オードはREFRESH_INTERVAL毎にJoin Queryパケットを送信し続ける。このJoin QueryとJoin Replyのやりとりの過程で、フォワーディンググループと経路が更新される。ノードがマルチキャストデータパケットを受け取ると、そのパケットが重複しておらず、かつそのノードのFG_FLAGがセットされていれば、そのノードはデータパケットを転送する。この処理手続きによって、通信のオーバヘッドを最小とし、古くなった経路を使用してしまうことを避けることができる。
3.2. Reliability - 信頼性
Join Replyパケットの信頼性のある伝送は、マルチキャスト経路とフォワーディンググループの確立・更新に重要な役割を担っている。したがって、もしJoin Replyパケットが正確に届かなければ、ODMRPによる効果的なマルチキャストルーティングは期待できない。ワイヤレスネットワークにおける標準であるIEEE 802.11 MAC (Medium Access Control) プロトコル
[8]は、確認応答がない場合において信頼性のある伝送を提供する。しかしながら、パケットがブロードキャストで送信される際には確認応答は行われず、再送も行われない。ODMRPでは、Join Replyパケットの伝送において、複数の送信ノードに対応させるため1つ以上の上流隣接ノードに対してたびたびブロードキャストを行う（e.g. 3.1.の例におけるR1の送信するJoin Replyパケットを見よ）。このような場合には、MACレイヤーによるホップ毎のJoin Replyパケットの送信確認と再送は行われない。このような処理はODMRPによって行う必要がある。信頼性のある伝送を実現するための別の方法としては、Join Replyパケットを各next nodeごとに分割する方法がある。例えば3.1.の例で言うと、ノードR1のJoin Replyパケットをl1宛とl2宛の2つのJoin Replyパケットに分割する。これらのJoin Replyパケットは、IEEE 802.11やMACAW
[3]のような信頼性のあるMACプロトコルを用いて別々にユニキャスト送信する。たいてい隣接ノード数は限られている（一般に、マルチホップネットワークにおける最適な隣接ノード数は6ノードである
[12]）ので、多数の送信ノードが存在する場合に対してもスケーラビリティを確保できる。この方法は、以下に述べるように、パッシブ応答の代替として実際に利用することができる。
[10]で用いられている方法を採用する。ノードがJoin Replyパケットを上流の中間ノードに送信する際に、下流の中間ノードが通信範囲内に存在していれば、この伝送を取得することができる。したがって、このパケットは”パッシブ応答（passive acknowledgment）”として利用することができる。このパッシブ応答をJoin Replyパケットの伝送確認として利用する。ただしマルチキャスト送信ノード自身はnext hopを持たないので、アクティブ応答を前ホップのノードに対して送信する必要がある（ただし送信ノードが別のマルチキャストグループのフォワーディンググループノードでもある場合を除く）。
ここで再度3.1.の例を考えてみる。ノードl1とl2はR1からのJoin Replyパケットを受け取り、自身のJoin Replyパケットを生成し送信するのであった（マルチキャスト送信ノードがS1とS2の場合）。Join Replyパケットの送信の際、ノードl1とl2は互いにオーバーラップする。l1とl2が互いに送信範囲内にいる場合は、CSMA (Carrier Sense Multiple Access)
[13]に代表されるキャリアセンスによってオーバーラップを発見し回復できる。しかし送信範囲外にいる場合は、l1とl2はR1が”隠れ端末（hidden terminal）”、すなわち（オーバーラップした）パッシブ応答を確認することのできない状態になっていることに気づかない。このようにして、ノードは隠れ端末問題により、上流隣接ノードのパッシブ応答を確認することができないかもしれない。また、上流隣接ノードが移動し離脱した場合もパッシブ応答を確認できない。どちらの場合も一定時間内に応答を受信しなかった際には、ノードはメッセージを再送信する。ここで、応答はいくつかの上流隣接ノードから受け取るかもしれないが、全上流隣接ノードから受け取るとは限らないことに注意する。オプションとして、再送は選択した隣接ノードへ分割したテーブルを用いてユニキャストモードで行われるかもしれない。再送を一定の回数行ってもパケットの送信がうまくいかない場合には、その経路は無効であると判断する。ここで、経路間違いが起こる理由としてもっとも起こりやすいのは、経路上のノードが誤っているか通信範囲外に移動してしまうことである。代替経路は”直ちに”発見される。ノードは送信ノードに届かなかったnext hopを指定して、メッセージを隣接ノードにブロードキャストする。このパケットを受け取ると、そのnext hopへの経路を知っていれば、各隣接ノードはそのJoin Replyパケットを生成しユニキャスト送信する。もし経路を知らない場合は、ただ単純にそのパケットをブロードキャストする。どちらの場合でもノードはFG_FLAGをセットする。この冗長な過程によって、次のリフレッシュでより効率の良い経路が確立されるまでの代替経路は充分確保される。各隣接ノードがFG_FLAGをセットすることは極めて冗長であるかもしれないが、これらのフラグのセットのほとんどはすぐに解除される。なぜなら、本当に必要なフォワーディンググループのみが次のJoin Replyの処理で維持されるからである。
3.3. Soft State - ソフトステート
ODMRPでは、グループを離脱する際に明示的な制御パケットを送信する必要がない。マルチキャスト送信元がグループを離脱したい場合は、ただ単にJoin Queryパケットの送信を止めればよい。これはグループに対して送信すべきデータが何もないためである。マルチキャスト受信者があるマルチキャストグループからのメッセージをもはや受信したくないのであれば、そのグループに対してJoin Replyパケットを送信しなければよい。フォワーディンググループのノードがタイムアウトするまでにリフレッシュされなければ（Join Replyパケットを受け取らなければ）、そのノードはフォワーディンググループでなくなる。
3.4. Selection of Timer Values - タイマーの値の選択
ルートリフレッシュの間隔とフォワーディンググループのタイムアウトまでの間隔は、ODMRPのパフォーマンスに大きく影響する。これらのソフトステートタイマーは、ネットワーク環境に応じた値の選択が必要である（e.g. トラフィックの種類、トラフィック経路、端末の移動可能性、移動速度、帯域 etc）。ルートリフレッシュ間隔を小さく取ると、新しい経路情報とメンバ情報は頻繁に手に入るが、その代わり多くのパケットを生成するコストが掛かり、ネットワークの混雑を引き起こす。その一方で、ルートリフレッシュの間隔を大きく取ると、制御パケットのトラフィックは少なくて済むが、各ノードは最新の経路情報とメンバ情報を得ることはできないであろう。このように、移動の頻繁なネットワークにおいてリフレッシュ間隔を大きく取ると、プロトコルのパフォーマンスは低くとどまってしまう。同様にフォワーディンググループのタイムアウト間隔も慎重に選択する必要がある。通信量の多いネットワークでは、不必要なノードがすばやくタイムアウトできるように、また極端な冗長を引き起こさないようにするために、タイムアウト間隔は小さな値を用いるべきである。しかしながら、より多くの代替経路を提供するためにはタイムアウト間隔はきな値を取る必要がある。フォワーディンググループのタイムアウト間隔をルートリフレッシュ間隔よりも大きく（e.g. 3〜5倍）取るように注意することが重要である。
3.5. Unicast Capability - ユニキャストの能力
ODMRPの大きな強みは、ユニキャスト送信の能力である。ODMRPはその他のユニキャストルーティングプロトコルと共存可能なだけでなく、ユニキャストルーティングプロトコルとしても非常に効率的な働きをすることができる。このように、ODMRPを利用するネットワークでは、別の分離したユニキャストルーティングプロトコルを必要としない。AMRoute
[5]、CAMP
[7]、RBM
[6]、LAM
[9]などのその他のマルチキャストルーティングプロトコルはユニキャストルーティングプロトコルが稼動していることが必要である。特にCAMP、RBM、LAMはユニキャストルーティングプロトコルの元でのみ動作する。
3.6. Contents of Tables - テーブルの内容
ODMRPを使用するノードは以下のテーブルを保持する必要がある。これらのテーブルはどんなフォーマットを用いてもよいが、本ドキュメントに挙げる項目は必ず含まなければならない。
3.6.1. Routing Table - ルーティングテーブル
ルーティングテーブルはオンデマンドに生成され、各ノードで管理される。項目は重複していないJoin Queryパケットを受け取ったときに挿入/更新される。ノードは宛先（i.e. Join Queryの送信元ノード）とその宛先へのnext hop（i.e. Join Queryを最後に伝送したノード）を記録する。ルーティングテーブルはJoin Replyを送信する際のnext hopの情報を与える。
3.6.2. Forwarding Group Table - フォワーディンググループテーブル
ノードがマルチキャストグループのフォワーディンググループノードである場合、そのノードはグループの情報をフォワーディンググループテーブルに格納する。マルチキャストグループIDと最後にリフレッシュされた時刻を保持する。
3.6.3. Message Cache - メッセージキャッシュ
メッセージキャッシュは、パケットの重複を検出するために各ノードで保持される。ノードが新しいJoin Queryやデータを受け取ったときに、ノードは送信元アドレスとパケットのUIDを保存する。メッセージキャッシュのレコードは永久に保持される必要がないことに注意する。古いレコードを削除し、メッセージキャッシュのサイズが大きくなるのを防ぐために、メッセージキャッシュにはLRU（Least Recently Used）やFIFO（First In First Out）が用いられる。
3.7. Mobility Prediction - モビリティの予想
3.7.1. Adapting the Refresh Interval via Mobility Prediction
- モビリティを考慮したリフレッシュレートの選択
ODMRPは経路形成と更新のために定期的にJoin Queryをフラッディングすることを要求する。しかしながら、アドホックネットワークでは帯域が制限されているので過度のフラッディングは望ましくない。さらにフラッディングはたびたびネットワークの混雑や衝突を引き起こす。最適なフラッディング間隔を見つけることは。ODMRPのパフォーマンスに大きく影響する。GPS
[11]を利用しているノードによる移動頻度の高いネットワーク（e.g. 軍事用のネットワークを利用する戦車、船、飛行機 etc）では、位置情報や移動情報から導き出した移動パターン・移動速度により、効率的にREFRESH_INTERVALを求めることができる。位置情報や移動情報を利用して、経路が利用可能な状態である存続時間を予想する。経路が断絶する時間を予想することで、Join Queryはセッションが切れる寸前にのみフラッディングされる。ODMRPはこれらのような情報が利用できない場合にも効率的に動作し、これらの情報が利用できる場合にはさらにプロトコルは改良できるということに注意する。
我々の予測方法では、受信する信号の強度は送信者からの距離にのみ依存するfree space propagationモデルを想定している。また、全てのノードはネットワークで同期するクロック（e.g. NTP（Network Time Protocol）
[16]やGPSクロック）を持っていると想定してる。したがって、２つの隣接ノードの動作パラメータ（e.g. 移動速度、移動方向、通信範囲 etc）がわかる場合、その２つのノードが接続を維持できる期間を判断することができる。２つのノード i と j がお互いの通信範囲 r の中に位置しているとする。ノード i の座標を ( x( i ), y( i ) )、ノード j の座標を ( x( j ), y( j ) ) とする。同様に各ノードの移動速度を v( i )、v( j )、移動方向を θ( i )、
θ( j )（ 0 <= θ( i ), θ( j ) < 2 * pi ）とする。そして、２つのノードが接続を維持する期間 D( t ) は以下の式から与えられる：
もしv( i )＝v( j )、θ( i )＝θ( j )であれば、上式に当てはめずともD( t )は無限大になることに注意する。
この予測から得られる情報を利用するためには、Join QueryパケットとJoin Replyパケットに特別なフィールドを追加する必要がある。送信元がJoin Queryを送信するとき、そこに位置情報、移動速度、移動方向を付け加える。送信元ノードには上流ノードは存在しないので、MIN_LET（Minimum Link Expiration Time）フィールドにMAX_LET_VALUEをセットする。次ホップの隣接ノードはJoin Queryを受け取ると、上述の式を用いて自分と上流隣接ノード（previous node）のリンクの維持される時間を予測する。この値とJoin Queryに記されたMIN_LETのうちの小さいほうをパケットに挿入する。これは、経路上の一箇所のリンクが切れた場合、その経路全てが無効になってしまうためである。ノードはまた、上流隣接ノードによって記録された位置情報と移動情報のフィールドを、自身の情報に書き直す。マルチキャストメンバのノードがJoin Queryを受け取ると、経路の末端のリンク維持時間（LET）の予測を計算する。この経路の末端のリンク維持時間とJoin Queryに記されたMIN_LETのうちの小さいほうの値をRET（Route Expiration Time）とする。このRETの値はJoin Replyにセットされブロードキャストされる。フォワーディンググループのノードが異なった値のRETを持つ複数のJoin Replyを受け取ると（i.e. 同一の送信元から複数の受信者への経路が存在する場合）、それらのうちの最小のRETを選択し、自身のJoin Replyにはその選択したRETを入れて送信する。送信元ノードがJoin Replyを受け取ると、全Join Replyの中の最小のRETを選択する。そうして、送信元は最小のRETの時間が経つ前に、Join Queryのフラッディングによって新しい経路を構築することができる。
RETの予測に加えて、リフレッシュ間隔の選択には別の要素を考慮する必要がある。ノードの移動頻度が高くトポロジの変化が頻繁である場合、経路はすぐに、またたびたび切断される。送信元ノードは極端な量のJoin Queryを送信し、その極端な量のフラッディングが制御パケットによるネットワークの衝突と混雑を引き起こす可能性がある。したがって、MIN_REFRESH_INTERVALは制御パケットのオーバーフローを回避するように設定しなければならない。ノードが静止しているかゆっくり動いていて、接続が長時間維持される場合には、経路はずっと維持されたままでJoin Queryが送信されることは滅多にないであろう。この状況ではいくつかの問題が発生する。第一に、ノードが突然移動方向や移動速度を変えた場合、予測したRETの値は古いものとなるが経路はすぐには再構築されない。第二に、メンバーでない遠くのノードがマルチキャストグループに参加しようとした場合、Join Queryを受信するまで新しいメンバであることの通知やデータの受信ができない。したがって、MAX_REFRESH_INTERVALはセットする必要がある。MIN_REFRESH_INTERVALとMAX_REFRESH_INTERVALはネットワーク環境に適したものを選択する必要がある。
3.7.2. Route Selection Criteria - 経路選択の基準
ODMRPでは、マルチキャスト受信者は遅延が最小の経路（i.e. 最初にJoin Queryを受信した経路）を選択する。しかしモビリティの予測を用いる場合、これとは違った方法の経路選択を適用させることができる。この考えはAssociativity-Based Routing（ABR）protocol
[18]、安定した経路を選択するプロトコルから想起される。ODMRPのアルゴリズムでは、最小遅延経路を利用する代わりに最も安定した経路（i.e. 最も長い時間接続を維持できるであろう経路）を選択することが可能である。経路選択に際して、マルチキャスト受信者は、全ての利用可能な経路とその経路の品質について知るために最初のJoin Queryを受信してからしばらくの適正な時間だけ待機する。そして受信者は最も安定した経路を選択し、Join Replyをブロードキャストする。安定した経路を利用することにより、経路切断の発生は少なくなりJoin Queryの伝送量は抑えられるであろう。
3.7.3. Alternative Method of Prediction - 別の予測方法
GPSは特定の環境化では正しく動作しない（e.g. 室内、フェーディングetc）ため、特定のリンクの有効期間をいつでも正しく予想することはできない。しかしながら、リンク維持時間（LET）を予測する別の方法が存在する。この方法はより実際的な伝送モデル元にしており、
[1]や
[17]で提案されている。伝送パワーのサンプルは移動する隣接ノードからパケットを受信する際に定期的に計測される。この情報から、特定の隣接ノードの伝送パワーレベルの変化の割合を計算することができる。このようにして、伝送パワーが受信不可能なレベルまで低下するまでの時間を予測することができる。将来このオプションを提案することを予定している。
4. Packet and Table Formats - パケットとテーブルのフォーマット
4.1. Join Query Packet Header - Join Queryパケットのヘッダ
