■ 第7回 AODV(Ad hoc On-Demand Distance Vector)プロトコル ■

●AODVルーティングプロトコルの概要

　AODVルーティングプロトコルはReactive型のルーティングプロトコルであり、以前解説したDSRプロトコルと非常によく似たプロトコルである。最新版の仕様は、Internet Draftの「draft-ietf-manet-aodv-13.txt」として公開されている。今回の記事も基本的にはこのドラフトを参考にした（仕様書内で矛盾する記述があるが、それについては正しいと思われるほうの記述に従った）。AODVに関する仕様はすでにExperimental RFCとして投稿がされており、そろそろRFCとして姿を現わす日も近くなってきたようである。

　AODVの主だった特徴を、DSRプロトコルとの違いを意識して列挙するならば、以下のようになるだろう。

• 各ノードはシーケンス番号を管理し、それをルーティングに積極的に利用している
• 各ノードは非常に短い間有効な経路表を持ち、データパケットはそれを用いて転送される
• 各経路表のエントリーにはprecursorリストがあり、リンクに障害があったときに利用される

それぞれの詳しい意味については、後で述べることとして、まずはAODVの概要について簡単にふれていこう。

■経路が見つかるまで

　AODVはReactive型のプロトコルなので、データを送受信しようとしてから初めて経路探索が開始される。ただしProactive型のプロトコルで利用されている「Helloメッセージ」がAODVでも使える仕様になっているので、AODVは、ややReactive型寄りのハイブリッド型ルーティングプロトコルであるといっても過言ではないだろう。

　制御メッセージとして、RREQ（Route Request）、RREP（Route Reply）、RERR（Route Error）、RREP-ACK（Route Reply Acknowledgment）の4種類のメッセージが使われ、各メッセージはUDPの654番ポートへ向けて送信される。Helloメッセージは、RREPメッセージの一種として実現されている。

　AODVは、DSRプロトコルと根本的に異なり、第4回で解説した「経路表」によるパケットの転送が行なわれる。すなわち、DSRプロトコルは送信元ノードのみが経路情報を持っていたが、AODVでは各ノードが次にどこに送ればよいかという情報を持っているのである。従って、パケットには転送されるべき経路が記録されていないことに注意しよう。

　新しい送信先への経路が必要になったとき、その経路を見つけるために、「RREQメッセージ」がネットワークへブロードキャストされる。やがて目的の送信先へRREQメッセージが届くと、送信先ノードは「RREPメッセージ」を送信元へ向けてユニキャストで送り返す。このやり取りによって、中間に位置するノードの経路表上には、送信元と送信先への双方向の経路ができあがっているので、それ以降はその経路表を使ってデータの送受信ができるようになる。

　しかし、これでは経路をまだ知らないノードが通信を始めようとするたびに、ネットワーク中にRREQメッセージがブロードキャストされてしまうことになる。そこで、もし中間ノードが新しい経路を保持していれば、送信先の代わりにRREPメッセージを返すようになっている。この処理によって、無駄なメッセージのブロードキャストができるだけ抑えられるのだ。

■シーケンス番号を積極的に利用する

　「シーケンス番号」はさまざまなプロトコルで用いられている番号だ。一般的にはパケットのヘッダに書き込まれ、送信するたびに毎回値を増やすなどして、新旧を見分けるためによく使われている。AODVにおいてはこの番号がより積極的に利用されており、各ノードは固有のシーケンス番号を管理している。

　通常、経路表の各送信先に対するエントリー（各送信先に対するさまざまな情報の集まり）として、送信先ノードIPアドレス、ホップ数、次ホップ（ネットワークインターフェイス）、有効期間があるぐらいだが、AODVではそれに加えて、送信先シーケンス番号や、そのシーケンス番号の有効性もが含まれている。

　特にマルチホップ無線ネットワークでは、ノードの移動が激しくなると実際のノードの位置関係を追従できなくなり、パケットがぐるぐると周回するという厄介な現象が起こる。これらの情報を駆使することで、そのような現象をできるだけ起こさないようにしている。

■通信経路が切断したとき

　さらに、経路表の各エントリーには「precursorリスト」も含まれている（つまり、リストの中にリストがあるという状態になっている）。このリストは自分の周辺のノードのIPアドレスの一部分から構成されており、ノードの移動や電波的な問題、電源OFFなどで経路が切断されたときに「RERRメッセージ」を送信する時に利用される。どのようにこのリストが作成されるか、またどのように経路が修復されるのかについては後で簡単に述べたい。

　AODVで管理されている経路表の各エントリーは、その経路が頻繁に利用されていると「アクティブ」な状態になっている。しかし利用されなくなって一定時間（3秒が推奨されている）が経過すると「無効状態」となる。これは完全に経路が削除された状態ではなく、後からその経路を探索するときに、再び経路情報が有効に利用される。さらに、無効状態のまま一定時間が経つと（15秒後が推奨されている）、そのエントリーは完全に経路表から削除される。

　以上がAODVの経路探索の基礎中の基礎である。それではAODVプロトコルの各メッセージに重点を置きながら、さらに詳しく見ていこう。

●RREQメッセージ

　AODVにおいて、各ノードはある送信先への経路が要求されたとき、まず自分の経路表をチェックする。その経路に目的のノードへの経路が存在していなかった場合は、新たに経路を探索するためにRREQメッセージをネットワークに向けてフラッディングする。RREQメッセージのヘッダは、図1のようになっている。

図1　RREQメッセージヘッダ

■RREQメッセージを作成する

　「タイプ」には必ず「1」が入り、それによってRREQメッセージであることを識別できるようになる。「ホップ数」は送信元から何回転送されたかを表わすフィールドであり、最初は0に設定される。「RREQ ID」フィールドは、自分が最後に送信したRREQメッセージで利用したRREQ IDに1つ加えた値にする。「送信先IPアドレス」にはその名の通り、送信先のIPアドレスを設定する。「送信先シーケンス番号」は、その送信先について最後に知ったシーケンス番号であり、経路表の中から検索する。もし経路表の中にエントリーが存在せず、シーケンス番号がわからなかったら、「U」 （Unknown sequence number）フラグを立てなければならない。

　「送信元IPアドレス」には自分自身のIPアドレス、「送信元シーケンス番号」には自分自身のシーケンス番号をコピーするのだが、ノードはRREQメッセージを作成する直前に自分自身の送信元シーケンス番号を増加させる。この番号はもし経路が存在すればRREPメッセージに乗っていずれ返ってくることになる番号である。何らかの障害でやむを得ず複数回RREQメッセージを送らなければならなかった場合、後で複数のRREPメッセージを受信する可能性があるが、どのメッセージが最新なのかはこの番号を見ることによって判断することができる。

■徐々にフラッディングの範囲を広げる

　このようにして作成されたRREQメッセージは、ネットワーク中にフラッディングされるが、いきなりネットワーク全体にフラッディングするのは効率的ではない。目的のノードはすぐ近くに存在するかもしれないからだ。そこでAODVでは、「expanding ring serch」という技術を使う。簡単に言うと、最初は再転送するホップ数を制限し、それで見つからなければ徐々にホップ数を大きくし、探索する範囲を広げていくという手法である。最初のホップ数や、増加していく量、RREPメッセージを待つ時間などについては詳しい規定があるが、これについてはドラフトを参照していただきたい。

■RREQメッセージを転送する

　メッセージを受け取ったノードは、すぐにそのメッセージの送信元への経路表のエントリーがあるかどうかを調べ、もしなければ直ちに作成することになっている。そして経路表のエントリーの送信先シーケンス番号は、そのメッセージに含まれている情報から決定される。もしわからない場合は、シーケンス番号が無効であるという情報を記録する。このような処理によって、経路表が徐々に作成されているのである。実はこの処理はRREQメッセージだけではなく、すべてのAODVのメッセージに対して行なわれる処理である。その処理の後には、条件によっていろいろな処理が行なわれるが、全体的に見ると

1. 重複して同じRREQメッセージが送信されないようにする
2. RREQメッセージの送信元への経路表のエントリーをさらに更新する
3. ホップ数が制限以内であれば（TTLが1より大きければ）、ホップ数を増加させるなどのRREQメッセージの更新処理をして、自分の周辺ノードにブロードキャストする

という処理が行なわれ、経路表の作成とメッセージの転送がされる。これが繰り返されることによって、RREQメッセージはネットワーク上に広がっていくのである。以上のイメージを図2に示す。この図のノードsとノードtが、それぞれ送信元と送信先である。

図2　RREQメッセージのフラッディング

●RREPメッセージ

　RREQメッセージが送信先ノードまで届くと、送信先ノードはその返事として、送信元へ向けてRREPメッセージを送信する。RREPメッセージヘッダは図3に示すフォーマットになっている。タイプには「2」が入る。

図3　RREPメッセージヘッダ

■RREPメッセージを作成する

　RREPメッセージを作成する前に、送信先ノードは自分自身のシーケンス番号がRREQメッセージに書かれている送信先シーケンス番号よりも小さい場合に、自分自身のシーケンス番号を送信先シーケンス番号で書き換える。それから、その値をRREPメッセージの送信先シーケンス番号に書き込む。ホップ数は0とする。送信先IPアドレスと送信元IPアドレスには、RREQメッセージに書かれていたものをコピーする。したがって名前だけを見ると逆になるが、このメッセージは送信元IPアドレスへ向かって送られることに注意しよう。

■中間ノードが返答をする場合もある

　RREPメッセージは、送信先ノード（図4のノードt）だけではなく、中間ノード（たとえば図4のノードc）でもあっても作成して送り返すことができる。ただし、そのノードにRREQメッセージに指定されている送信先へのアクティブな経路があり、有効な送信先シーケンス番号がRREQメッセージの送信先シーケンス番号以上であり、かつRREQメッセージのDフラグ（Destination only flag）によって中間ノードによる返答が禁止されていない場合に限る。

　以上の条件を満たすときに限り、中間ノードは送信元ノードに対してRREPメッセージを送信する。そのメッセージのホップ数や送信先シーケンス番号は、そのノードの経路表のエントリーからコピーしてくる。そうすることで、送信先ノードからRREPメッセージが送信されてきたのと同じ状況を作り出すことができる。この処理によって、経路が十分新しい場合には、無駄なメッセージの行き交いを少なくすることが可能となるのだ。

■RREPメッセージを転送する

　RREPメッセージは送信元と送信先の中間に位置するノードらによって送信元へ送り返されるが、このときの経路はRREQメッセージの転送時に作られたものが用いられる。さらにその転送処理を行なうたびに、メッセージの内容に従って送信先への経路表が作成・更新される。この処理によって、双方向の経路が完成するわけだ。このイメージを図で表したのが図4である。

図4　RREPメッセージの返信

さらに、RREPメッセージを送信するノードは、経路表の送信元ノードへのエントリー内のprecursorリストに前ホップのIPアドレスが、送信先ノードへのエントリー内のprecursorリストに次ホップのIPアドレスがそれぞれ追加される。これらのリストのノードは、次に説明するRERRメッセージを送信するために利用される。

●RERRメッセージ

　AODVプロトコルは、リンクに障害が起こったかどうかを、DSRプロトコルとほぼ同様の手法を用いて検知する。リンクが失われたことを検知した場合、その時点で経路表に存在している経路を無効化し（完全に消去するわけではない）、その障害によって影響を受ける送信先をリストアップする。さらに、その影響を受ける可能性がある隣接ノードを決定し、そのような隣接ノードへの適切なRERRメッセージの送信を行なう。RERRメッセージヘッダは、図5の通りである。タイプには「3」が入る。

図5　RERRメッセージヘッダ

　「不達送信先IPアドレス」と「不達送信先シーケンス番号」は1つの組になっている。これは複数組連ねることができ、その個数を「送信先数」フィールドで示すようになっている。

　RRERメッセージはリンク障害を検知した場合だけではなく、アクティブな経路がないノードへのデータパケットを受信した時や、アクティブな経路に関するRERRメッセージを受け取った時にも作成される。リンク障害を検知した場合には、そのリンクを利用する送信先のすべてを不達送信先としてリストアップする。経路がない送信先へのパケットを受信した場合は、単純にその送信先を不達送信先とする。アクティブな経路に対するRERRメッセージを受信した場合は、そのRERRメッセージを送信したノードを次ホップとするようなすべての経路の送信先を不達送信先としてリストアップする。

　それから、そのリストの各不達送信先について経路表を検索し、precursorリストが空でないものをRERRメッセージの不達送信先として登録していく。このようして作られたRERRメッセージは隣接ノードへブロードキャストされるが、もしそのメッセージが1つの隣接ノードでしか必要でないとわかった場合は、ユニキャストで送信される。なお、各不達送信先に対応する経路表のエントリーはすべて無効状態になり、送信先シーケンス番号は増やされるか、または受信したRERRからコピーされる。

　以上の説明は少しわかりにくいかもしれないが（実はドラフトはさらにわかりにくいのだが）、全体的な視点からこの処理を大まかにみると、RERRメッセージは、リンク障害によって影響を受けるような送信元のノードへ向かって広がっていくイメージになる（図6）。するとRERRメッセージを受信した各ノードは対応する経路が無効になるので、次に送信するときには再度経路探索が行なわれるようになるのである。

図6　RERRメッセージの伝播

■効率的に経路を修復する

　もしアクティブな経路上でリンク障害が起こったら、障害を検知したノードは、送信先がある程度近い場合に限り、その経路の修復を自分で行なうことができる。やり方は簡単で、そのノードが送信先のシーケンス番号を増やしたRREQメッセージをフラッディングするだけである。ただしRREQメッセージの広がる範囲は、パケットの送信元まで届かないように計算されて調整される。

　ノードはRREQメッセージの処理と同じようにRREPメッセージを待つのだが、その間、送信元から送られてくるデータパケットは破棄せずに溜め込んでいく。そしてRREPメッセージが届いて経路が再作成されたら、その経路に向かって溜め込んできたパケットを送信する。もちろん、RREPメッセージが決められた期間内に受信できなければ、RERRメッセージを送信して前述のエラー処理を行なわなければならない。

　以上のようにして、リンクに障害が発生した場合でも、経路の修復が自動的に行なわれるのだ。

●まとめ

　AODVプロトコルは、基本的にはRREQメッセージをフラッディングして送信先へ届け、送信先がRREPメッセージで返答をし、中間ノードはそのやり取りの中で経路表を作成していくというものだ。

　AODVには他にもマルチキャストの利用や、サブネットを扱う方法、さらにHelloメッセージによって接続性を保つ方法などがある。また、DSRプロトコル同様にさまざまな研究者によってさまざまな拡張が行なわれているプロトコルでもある。一体どのようなプロトコルが世の中で多く使われるようになってくるのだろうか。今後の動向に注目していきたい。

　

■筆者紹介■ 小出俊夫 http://homepage1.nifty.com/toshio-k/ 　常に他人と違うことをすることに喜びを覚える知的好奇心旺盛な人間。他に雑誌連載も手がけ、プログラミングの解説書は現在6冊。最近はソフトウェアだけではなくハードウェアにも興味を持ち始めたらしい。

(2003/5/22)

[Reported by 小出俊夫]