■ 第5回 DSR（Dynamic Source Routing）プロトコル ■

●2月の主なニュース

　2月にINTERNET Watchで掲載された、P2Pやワイヤレスに関するニュースを、ジャンルごとにざっと眺めてみよう。かなり私見も含まれるが、気になったことについてコメントを少々付け加えている。

　まずはファイル交換関係では、「P2Pで音楽をコピーせずに“貸す”ソフト」が気になった。聞きたいファイルを持っているユーザーのマシンから直接ストリーミングで音楽を聞くという仕組みらしい。このソフトが既存のファイル交換ソフトと異なるのは、音楽データが実際に置かれている「場所」なのであって、聞きたい曲がお金を払わずに自由に聞けてしまうという事実には変わりがないから、このソフトは結局は既存のファイル（音楽データ）交換ソフトと同じ運命をたどることになると思っている。

　なぜなら、ブロードバンド化が進み、どこでも無線でネットにつながるようになったら、公開された他人のコンピュータは、実質自分のコンピュータの一部と変わらなくなるからだ。逆に、そうなることを今のうちに見越しておくことが、新しい面白いサービスを考えるためのヒントになるかもしれない。

　では、ホットスポット関係について見てみよう。最も気になったのは「ホットスポットのポジティブな利用意向は81％」という記事だ。気になったのは81％という数字ではなく、ホットスポットの利用目的である。「メールチェック」、「ニュース・天気予報等」、「位置検索等」と並んでいる。ほとんど帯域を必要としないものばかりだ。この結果から分かることは、ユーザーにとって、「つながる」ということが重要なのであって、「ブロードバンド」はそれに比べるとあまり必要とされていないのかもしれない、ということだ。

　その他、「ITの閉塞感を打ち破るのは『無線ICタグ』」というニュースがあった。「無線ICタグ」がITのブレークスルーをもたらす技術として、2位の「無線LAN」や「IP電話」を大きく引き離してトップに選ばれたという記事だ。無線ICタグが身の回りのアイテムに付加されることで、さまざまなサービスが展開されることは間違いない。

　例えば、食料品に無線ICタグが付けられれば、いちいちレジに並ばずとも会計が行なわれるようになるし、冷蔵庫に何を入れたかをユーザーが入力しなくても、冷蔵庫自身が勝手に中身を管理してくれるようになる。また、書き換えが不可能なチップであれば、本物か偽物かを判定するのに役立てることもできる。いろいろな面白いアイデアが次から次へと浮かんでくる、そんな技術なのである。ただし、いろいろなものにタグがつき、自由に読み取ることができるようになってしまうと、プライバシーが守れないのではないかという心配があることも確かだ。

●DSRプロトコルの基礎

　さて、ここからはDSRプロトコルについて解説していこう。DSR（Dynamic Source Routing）プロトコルは、IETF MANET WGで提案されているルーティングプロトコルの1つであり、ネットワークインフラそのものや管理が不要で、自律的な無線ネットワークの構築が可能となるものだ。

　2003年2月現在、Internet Draftとして公開されているDSRプロトコルは、2002年2月に公開された「draft-ietf-manet-dsr-07.txt」が最新である。今回の解説もこの内容を参考にして書いている。Internet Draftは有効期間が最大6カ月なので、Draft自体はすでに無効となっているのだが、興味のある方はIETF MANET WGのページ（ http://www.ietf.org/html.charters/manet-charter.html ）からダウンロードして読んでみていただきたい。かなりの量があり読み応えがあるが、読みやすく章立てしてあるので、かいつまんで読んでいってもある程度理解できるだろう。

　DSRプロトコルが初めて世に姿を現わしたのは、1994年12月にカリフォルニアで開かれたワークショップ「WMCSA1994」である。Rice UniversityのDavid B. Johnsonが「Routing in Ad Hoc Networks of Mobile Hosts」と題した論文を発表した。それから、コンピューター上でのシミュレーションやFreeBSDへのプロトコルの実装、実環境下での実験などを経て現在に至る、MANET WGの中でもかなり歴史のあるプロトコルだ。現在このプロトコルは、LinuxやWindows CEなどでも実装されている。

　DSRプロトコルは、Reactive型のルーティングプロトコルであり、通信の要求が発生してから経路を探索し、実際の通信を行なう。Proactive型のようにネットワーク状況の変化に追従しようとして、通信が行なわれなくてもパケットを定期的に送受信することはない。パケットの転送は、経路表に従って行なうのではなく、ソースルーティングという、パケットの発信元があらかじめ全体の経路を指定する方式を用いている。

　このような方式だと通信を要求してから、通信が始まるまでに時間がかかるように思えるかもしれない。実際には、通信を行なったり、周りから経路情報を受け取ったりするたびに、各ノードはそれを「Route Cache」として蓄えているので、それを参照することで、頻繁に使うノードに対して速やかに通信が行なえるようになっている。なお、通信を行なうノード間のホップ数は、せいぜい数ホップの範囲を想定しており、数十ホップという長い経路は考えていない。

●DSRヘッダー

　それでは、DSRプロトコルの全体像を、イラストとともに簡単に説明していこう。まず最初に、電波に乗って飛び交うパケットの中身を見てみよう。DSRプロトコルでは、通常のIPパケットに「DSRヘッダー」を追加する。追加される位置は、IPヘッダーとそれに続くTCPやUDP等のトランスポート層のヘッダーの間である。

図1DSRプロトコルのパケットフォーマット

　DSRヘッダーにはオプション領域があり、そこには主に以下に挙げる種類のオプションが追加される。

1. Route Request
2. Route Reply
3. Route Error
4. Acknowledgement Request
5. Acknowledgement
6. DSR Source Route

　DSRプロトコルでは、経路探索や経路の維持などのために、いろいろな種類のパケットが飛び交うが、それらの種類はこれらのオプションで区別されている。

●経路の探索（Route Discovery）

　次に、DSRプロトコルが実際にどのように動作するのかを見ていこう。DSRプロトコルは、通信の要求があると現在利用可能な経路を探索する。これを「Route Discovery」と呼ぶ。分かりやすいように単純な例を図で示す。

図2-1 ノードSによるRoute Discoveryの開始

　図2-1には6つのノードがある。ここでノードSは、ノードEとデータの送受信をしようと思っている。すなわち、ノードSによってRoute Discoveryが開始されるわけだ。まずノードSは、「Route Requestパケット」（Route RequestオプションのついたDSRパケット）を周りのノードに向けて送信する。このとき、自分のノードをパケットに経路情報として追加して送信する（図2-1ではこれを「S」と表している）。

図2-2 ノードB,C,DによるRoute Requestの転送

　すると、Route Requestパケットは周囲のノード（B、C、D）で受信される。それらのノードは、このパケットに書かれている送信先ノードが自分自身ではないことを知り、自分のノードIDをパケットの経路情報に追加して周りのノードへ送信する。例えば、ノードCは「S→C」という経路情報をパケットに書き込む（図2-2）。なお、同時にノードSもパケットを受信することになるが、「パケットに記述されている経路情報に自分が含まれていたら破棄する」というルールによって無視される。

図2-3 ノードEによるRoute Replyの返送

　今度はノードAとノードEが受信したパケットを処理する。ノードAは経路情報を追加して送信するが、ノードEはこのパケットが自分に向けて送られてきたことを知り、「Route Replyパケット」を送信元ノードSに向けて返信する（図2-3）。このパケットには、目的のノードEとSの間の経路情報が書かれているので、ノードSはこれを使ってノードEへデータを送信することができるようになる。

　なお、各ノードはRoute Requestパケットを送信する前に、自分自身の「Route Cache」（以下「キャッシュ」という）に送信先ノードEへの経路情報があるかを見ている。各ノードは、今までに送受信した経路情報をすべてキャッシュに蓄えているので、その中に目的のノードまでの経路を発見したら、それを使うことによって時間と電力の浪費が防ぐのだ。

●経路の維持（Route Maintenance）

　DSRプロトコルは、大きく「Route Discovery（経路発見）」と、これから説明する「Route Maintenance（経路維持）」の2つの機能で成り立っている。Route Maintenanceは、通信中に経路がなんらかの原因で切断されてしまった場合に、そこを回避して通信を続けるための仕組みだ。図3を使って説明する。

図3 Route Maintenanceの仕組み

　DSRプロトコルでは、ノードはパケットを他のノードに送信する時、本当にそのリンクが使えるのかどうかを確認することになっている。しかし、常時確認するわけではなく、確認を行なうのはデータを送信する時だけだ。例えば、図3のノードSからノードAへ向かうリンクは、ノードSによって利用できるのかどうかが、パケット送信時に確認される。リンクが利用できるかできないかを調べるには、

1.無線LAN等で実装されている、リンク層Acknowledgementを用いる方法
2.次のノードがさらに次のノードへ送信したパケットを盗み聞きする方法
3.Acknowledgement Requestオプションを用いる方法

の3つの方法がある。通常は1番目の方法を用いる。無線LAN等にはあらかじめデータが届いたかどうかを確認する機能がついているので、DSRプロトコルはその機能をそのまま使えばよいことになる。そのような機能が無線デバイスにない場合は、2番目の方法を使う。これはパッシブ確認と呼ばれ、次のノードがさらに次のノードへパケットを送るときに発信した電波を盗み聞きし、それが受信できたことでパケットが届いたとみなす確認方法である。しかしこれはそのノード間のリンクが双方向でつながっていることが条件となる。最後の3番目の方法は、DSR専用の確認プロトコルを用いる方法である。

　ともかく各ノードはいずれかの方法で次のノードへパケットが届いたかを確認するわけだが、もしパケットの到達が確認ではない場合は（何度か確認するなどした後に）、そのリンクは使えないものと判断してキャッシュから対応する経路情報を削除する。また、確認が取れなくなったリンクを使おうと希望してきたすべての送信元へ向けて、Route Errorパケットを返す。

　例えば、図3のネットワークで、ノードSからノードDへ向けて、黒矢印の経路で通信していたとする。ここで何らかの理由でノードBからノードCへ通信ができなくなったとする。するとノードBはノードCへデータが届いたことが確認できなくなり、このリンクはもう使えないものと判断する。それゆえキャッシュからこのリンクを使う経路情報を削除し、この経路に対して通信を行なっていたノードSに対して、「ノードBからノードCへのリンクは使えませんよ」と書かれたRoute Errorパケットを返す（図3の赤矢印）。

　ノードSは、もはやこの経路は使えないことを知り、自身のキャッシュから対応する経路情報を削除する。このままでは通信が途切れてしまうことになるのだが、キャッシュにノードDへの他の経路が記録されている可能性もある。図3の例では、青矢印の経路がキャッシュ内に記録されていれば、それを利用して通信を続行できる。一方、経路が見つからなかった場合は、改めてRoute Discoveryを行なって新しい経路を探索する。これらの処理の間に失われるパケットがあるかもしれないが、それはTCPなどの上位層プロトコルによって再送処理が行なわれるようになっている（プロトコルによっては再送しないものもある）。

●その他の機能

　以上のように、DSRプロトコルは「Route Discovery」と「Route Maintenance」の2つの機能をうまく使いながら、勝手に動き回るノードをまとめて、ネットワークを自律的に構成しているのだ。ただし、ここに書いたことがDSRプロトコルのすべてではない。他に細かい様々な機能がある。

　「Packet Salvage（パケット救助）」機能は、経路の切断が頻繁に起こるマルチホップ無線ネットワークでは積極的に利用すべき機能だ。これは、利用しようとしていた経路が使えない時、すぐに送信元へRoute Errorパケットを送り返すのではなく、そのノード自身のキャッシュに代替経路が見つかったら、パケットの経路情報を書き換えて送信するという機能である。

　また、ホップ数を制限する機能も重要である。これはIPヘッダのTTL（Time-to-Live）フィールドを使って実装される。原理上はどんなに遠くのノードであっても通信ができるのだが、実際のところ、数十ホップ先に存在するノードと通信するのは現実的ではない。ホップするノード数が多いほど通信は不安定になるし、そもそもルートを見つけるためのRoute Requestパケットが無制限に拡散してしまっては、処理しなければならないパケット数が多くなりすぎて、ネットワークに深刻な影響をもたらしてしまうのである。それゆえ、意図的にRoute Requestパケットをホップさせない「non-propagating Route Request」や、徐々に遠くのノードを検索していく「expanding ring search」などが用意されている。

　さらに、冗長な経路を自動的に短縮する機能や、大量のRoute Replyパケットが返ってきてしまう「Route Reply Storm」を防ぐ機能、双方向通信できないリンクを「ブラックリスト」で管理する方法など、さまざまな機能がある。

　これ以外にも、他の研究者の手によってDSRが機能拡張されたプロトコルが存在している。例えば、Route Discovery機能は、実質上Route Replyパケットのブロードキャストであるので、あまり効率が良いとはいえない。そこで効果的にパケットを転送し、目的のノードを探索するアルゴリズムが考え出されている。また、周辺のノードとの電池残量を比較して、できるだけ電池残量の多い余裕のあるノードがパケットの転送を行なう方法なども考案された。相当な数のプロトコルが提案されているところを見ると、まだまだ考えなければならないことはたくさんあるようだ。

　

■筆者紹介■ 小出俊夫 http://homepage1.nifty.com/toshio-k/ 　常に他人と違うことをすることに喜びを覚える知的好奇心旺盛な人間。他に雑誌連載を1つ手がけ、プログラミングの解説書は5冊。実は博士課程の大学院生で、メーカーの研究所に入りたがっている。求むオファー。

(2003/3/5)

[Reported by 小出俊夫]