■ 第8回 TBRPF（Topology Broadcast Based on Reverse-Path Forwarding）プロトコル ■

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

図1:TBRPFの2つのモジュール

　TBRPFルーティングプロトコルは、Proactive型のルーティングプロトコルだ。したがって、第6回で解説したOLSRプロトコルと同様に、経路は通信を行なう前に確定されており、いつでも直ちに通信を開始することができる。

　TBRPFの特徴は、「差分情報」を積極的に用いる点である。経路などの情報をすべて定期的に更新するのではなく、何が追加されたか、何が削除されたかなどの必要最小限の情報を利用するのだ。この仕組みによって、やり取りすべきメッセージのサイズを小さくすることができ、比較的短い期間に周期的にルーティング情報を送受信することができるようになる。それゆえ、ノードの移動などによる急激なトポロジー変化にも比較的強いプロトコルとなるのだ。

　TBRPFを大まかにみると2つのモジュールからなっている。1つは隣接ノード探索モジュール、もう1つはルーティングモジュールである。それぞれのモジュールの関係は図1のように独立に動作しており、それぞれ独自のメッセージを送受信している。

　まずは非常に簡単にそれぞれのモジュールの役割を述べよう。なお執筆段階では、TBRPFに関する最新のドラフトは「draft-ietf-manet-tbrpf-08.txt」である。今回はこのドラフトに基づいて解説を行ないたい。

■隣接ノード探索

　TBRPFプロトコルを利用するノードはすべて定期的に「HELLOメッセージ」を隣接ノードへ向けて送信している。このメッセージによって、自分の隣にはどんなノードがいるのかがわかるようになるわけだ。

　ただし、TBRPFでは単純にそのメッセージを受け取ったからといって、すぐにリンクを確立するわけではない。十分な回数のHELLOメッセージを受け取って、やっと「片方向の」リンクが確立するのだ。それでもまだ、この時点で実際にそのリンクを利用することはできない。なぜならば、TBRPFでは双方向のリンクのみを利用するように設計されているからだ。その後、その片方向のリンクが確立したという情報が含まれたHELLOメッセージがやり取りされ、双方向でパケットのやり取りができるということが確認された上で、初めて双方向のリンクとして確立され、実際に利用できるようになるのである。

　なぜこのような面倒なことをするかというと、一度パケットが届いたからといって、それが長く使えるリンクであるとは限らないことが多いからである。よって、このように何度もメッセージをやり取りして、比較的安定しているリンクのみを利用するのである。ただし、メッセージとして送る情報は最近変更された差分情報のみにすることができるので、パケットのサイズを減らすことができるようになっており、必要以上のトラフィックが発生してしまう可能性は小さい。

■ルーティング

　ルーティングモジュールでは、上記の隣接ノード探索によって得られた情報や、他のノードから送られてきた「トポロジー更新（TOPOLOGY UPDATE）メッセージ」の情報を用いてさまざまな計算を行ない、経路表を作成する。実際のデータパケットは、この経路表に従ってルーティングされる。

　各ノードは自分を送信者とするすべてのノードへの経路を作成し、管理している。この経路をすべて重ね合わせるとまるで木のような形になるので、この経路を「送信者木（source tree）」と呼んでいる。その木の情報はトポロジー更新メッセージに乗せて隣接ノードへ送信される。従って、他のノードはこのメッセージを受け取ることによって、隣接ノードだけではなくその先のネットワークの状況を知ることができるようになるのだ。

　ただし、この送信者木の情報のサイズは大きくなる場合があるので、実際に送信するのはその一部分である。それを「報告部分木（reported subtree）」と呼ぶが、それをいかに小さくするかが腕の見せ所なのだ。そのためTBRPFは、できるだけ他のノードが報告するリンクと重複して報告しないように、独自のアルゴリズムを用いて、報告部分木を決定している。

■パケット形式

　TBRPFのパケットは、他の多くのプロトコルのパケット同様、ヘッダーとメッセージ本体から成り立っている。

図2:TBRPFのヘッダーとメッセージ本体

　ヘッダーの先頭は4ビットのバージョンフィールドで始まり、これにはTBRPFのバージョン番号が入る。現在のドラフトでは4を指定することになっている。それに続いて各1ビットのフラグ、「F」「C」「L」「R」が続く。Fが1のときは、フラグ拡張（8ビット）が付いていることを表わす。Cが1のときは16ビットのチェックサムが、Lが1の時は16ビットのパケット長が、Rが1のときはルータIDがそれぞれヘッダー拡張に付くことを表わしている。

　それに続くメッセージ本体は、4ビットのオプションと「型」で始まる。メッセージは1つのパケットに複数詰め込むことができることに注意しよう。いくつかの種類のメッセージがあるが、それは型のフィールドで識別される。具体的なメッセージについては後述する。

　それでは、ここからはプロトコルの詳細について解説する。なお、厳密さの追求よりも意味的な理解に重きを置いて解説する目的上、本記事ではすべてのノードにインタフェースは1つのみと仮定し、ドラフト上でインタフェースとして触れられている部分はノードとして解説していることをご了解願いたい。

●隣接ノード探索

　TBRPFプロトコルを利用するすべてのノードは「隣接ノード表（neighbor table）」を持っている。これは、自分の周りに存在するノードとのリンク情報を集めたリストである。たとえばノードiからノードjに向かうリンク（以降、これを「（i,j）」と表現する）に関しては、主に次のような情報を管理している。

• 隣接ノードjのID（ルータIDと呼ばれる）
• （i,j）の状態（LOST、1-WAY、2-WAYのいずれか）
• （i,j）の生存時間。この間HELLOメッセージを受け取らなかったら状態はLOSTになる
• jから最後に受け取ったシーケンス番号
• （i,j）のカウンター。jを含んだHELLOメッセージをあと何回送るべきかを表わしている
• jの転送優先度。この優先度が高いほど転送ノードとして選ばれやすくなる。通常は7

（i,j）の状態としては、LOST、1-WAY、2-WAYのいずれかが入るが、それぞれの意味は次の通りである。

LOST:ノードはまだ十分な数のHELLOメッセージを受け取っていない
1-WAY:十分な数のHELLOメッセージは受け取ったが、双方向であることが確認されていない
2-WAY:双方向のリンクであることが確認された（通信可能である）

　これらのリンク情報は、すべてHELLOメッセージの送受信によって構築されていく。ドラフトでは、各ノードはこのメッセージを1秒に少なくとも1回は送信することが推奨されている。HELLOメッセージは図3のような形式になっている。

図3:HELLOメッセージ

　HELLOメッセージには、「NEIGHBOR REQUEST」、「NEIGHBOR REPLY」、「NEIGHBOR LOST」の3つの種類があり、それらは「型」のフィールドに入る数値で区別される。具体的な値はそれぞれ2、3、4である。HELLOメッセージには必ずNEIGHBOR REQUESTが含まれなければならないことになっている。たとえ報告する情報がなかったとしても、必ず空のNEIGHBOR REQUESTを送信しなければならない。これは次に説明する「シーケンス番号」を必ず送信しなければならないからである。

　8ビットの「シーケンス番号」は、送信されるたびに1つずつ増える番号である。HELLOメッセージを受信するノードでは、この番号の履歴を利用することによって、隣接ノードとのリンクを維持するかどうかを決めている。

　4ビットの「優先度」フィールドには、次ホップとしてこのノードを優先的に選ぶのかどうかの度合いを設定する。0にするとそのノードは非転送ノードとなる。通常のノードはここに7を設定する。

　12ビットの「個数」フィールドには、このHELLOメッセージに含める隣接インタフェース数を入れ、その後に32ビットの隣接インタフェースアドレスが、その個数分続く。隣接インタフェースアドレスは、ここでは隣接ノードのIDと考えていただきたい。

■送信処理

　HELLOメッセージの送信処理は、比較的簡単である。基本的にはそのメッセージを送信しようとしているノードに含まれている全リンクに関する情報を送信するだけである。ただし、リンクと言っても（i,j）という形ではなく、jだけを含めることになる。iは自分自身であり、それはIPヘッダーの送信元IPアドレスから割り出せるからである。従って、HELLOメッセージにはリンクではなく「隣接インタフェースアドレス」というフィールドを用いるのである。

　また、リンクの状態によって、送信するメッセージの「型」を適切に指定しなければならない。具体的には、LOST状態のリンクはNEIGHBOR LOSTに、1-WAY状態のリンクはNEIGHBOR REQUESTに、2-WAY状態のリンクはNEIGHBOR REPLYのメッセージにそれぞれ含めて送信する。また、それぞれのリンクのカウンターは送信するときに1つ減らし、カウンターが0になっているリンクについての情報は送信しない。こうすることによって、カウンターに指定された回数だけ、そのリンク情報が周辺ノードに告知されることになるのだ。

■受信処理

　送信処理に対して、受信処理は少し複雑となる。まず受信したパケットのIPヘッダから、送信元IPアドレスを得る。たとえばノードiがノードjから送られたHELLOメッセージを受け取ったとすると、ノードiでは大まかにいうと次のような処理が行なわれる。

1. ノードiの隣接テーブルに（i,j）に関するリンク情報が存在しなかったら、ルータIDをjに、リンク状態をLOSTに、カウンターを0に、そしてシーケンス番号をメッセージ内のシーケンス番号としたリンク情報を、隣接テーブル内に新しく作成する。

2. これ以降は、隣接テーブルのリンク（i,j）の状態によって処理が異なる。

2-1. リンク状態が「LOST」で、かつ十分な数（2回）のHELLOを順調に受信できた場合：

もしiがNEIGHBOR REQUESTにもNEIGHBOR REPLYにも見つからなかった場合、（i,j）のリンク状態を1-WAYにし、カウンターを3に設定する。そうでなければリンク状態を2-WAYにしてカウンターを3に設定して、リンク（i,j）を接続可能にする。

2-2. リンク状態が「1-WAY」の場合：

a. もしメッセージ中のシーケンス番号が、リンク（i,j）のシーケンス番号+3を超えていたら、リンク状態をLOSTにして、カウンターを3とする。
b. そうでないとき、NEIGHBOR REQUESTにiが含まれていたら、リンク状態を2-WAYにして、カウンターを3にする。そして、リンク（i,j）を接続可能にする。
c. NEIGHBOR REPLYにiが含まれていたら、リンク状態を2-WAYにし、カウンターは0に設定する。そして、リンク（i,j）を接続可能にする。

2-3. リンク状態が「2-WAY」の場合：

a. NEIGHBOR LOSTにiが含まれていたら、（i,j）のリンク状態をLOSTにして、カウンターを0にして、リンク（i,j）を切断する。
b. 受け取ったメッセージのシーケンス番号が、リンク（i,j）のシーケンス番号+3を超えていたら、リンクを切断する。
c. もしNEIGHBOR REQUESTメッセージにiが含まれていて、リンクのカウンターが0だったら、カウンターを3に設定する。

3. 最後に、リンク（i,j）の生存時間を延長し、リンクのシーケンス番号と転送度をメッセージに含まれているシーケンス番号と優先度にそれぞれ更新する。

■具体例

　隣接ノード探索モジュールでは以上のような処理が行なわれるわけだが、少しわかりにくかったかもしれない。ここでは非常に単純な例を、図4を使って説明しよう。

図4:隣接ノード探索の例

　ネットワークには図のように2つのノード、aとbのみが存在していたとする。最初は隣接ノード表には何も書き込まれていないので、空のNEIGHBOR REQUESTメッセージがお互いに送受信される。すると、隣接ノード表には、相手とのリンク情報が追加され、状態がLOSTに設定される。これが図中の（1）の状態である。

　次に、ノードaがbよりも少し早くパケットを送信したとしよう。するとそれを受信したノードbは、ノードaから2回連続してメッセージを受け取ったので、自分の隣接ノード表の（b,a）リンクの状態を1-WAYに変更し、カウンターを3に設定する。これが図中の（2）の状態である。

　次にノードbから送信されるNEIGHBOR REQUESTメッセージには、ノードaのアドレスが含まれるようになる。するとそれを受信したノードaは、ノードbにおいて、自分とのリンクが1-WAYであることを知るので、自分はリンク（a,b）の状態を2-WAYにして、初めてここでノードbとの通信ができるようになる。これが図中の（3）の状態である。

　まだノードbは1-WAYのままであるが、次回ノードaから送られるNEIGHBOR REPLYメッセージの中にはノードbのアドレスが含まれる。これを受け取ったノードbは、リンク（b,a）の状態を2-WAYに設定し、ようやくそのリンクが利用できるようになる。これが図中の（4）の状態である。

　以上の要領で隣接ノードが探索され、隣接ノード表が構築されていく。この情報は次に説明するルーティングモジュールで利用され、実際に経路表などが作成されていくことになる。

●ルーティング

　TBRPFプロトコルは経路表を作成し、その経路表に従って、1ホップごとにパケットを転送していく方式を用いている。その経路表は以下で説明するルーティングモジュールで作成される。それでは、感覚的に理解できるようポイントをかいつまんで解説しよう。

　図1にも示したように、各ノードは「トポロジー表（topology table）」と呼ばれる、ネットワーク全体の構造を保持しておくための表を持っている。この表を利用して、経路表を作成していくわけである。図5はノードiのトポロジー表で管理されている情報の例を図的に表したものである。この図を元にしてそれぞれのポイントについてまとめていこう。

図5:トポロジー表の情報のイメージ

　ルーティングモジュールでは、大まかに以下のような処理が定期的に繰り返し実行される。HELLOメッセージの送信周期と同一にすることが多い。

1. 無効リンクの削除
2. 送信者木の更新
3. 経路表の更新
4. 報告部分木の更新
5. トポロジー更新メッセージの作成と送信

　最後に作成されて送信される「トポロジー更新メッセージ」によって、「報告部分木」が周辺のノードに向けて送信される。情報を受信した他のノードは、その情報を元にして自分自身のトポロジー表や経路表を更新する。これを繰り返すことによって、徐々にネットワーク全体のノードの存在や接続関係が各ノードに浸透していくわけである。では、これらの処理について細かく見ていくことにしよう。

■送信者木と経路表の更新

　各ノードは、現在自分が持っているトポロジー表の情報を元にして、送信者木を作成する。たとえば、図5におけるノードiの送信者木は青い太線で描かれたものである。ノードiやその周辺のノードは、この木を元にして経路表を作成するので、ノードiと他のノードが通信するときは結果的にこの青い太線の経路を通ることになる。たとえばノードiとノードjは、ノードaを経由して送受信を行なうことになる。

　送信者木を作成する際は、各リンクに「距離」と呼ばれる値を設定して、その距離の総和が最小となるような経路を計算する。数学の分野では、そのような経路を「最短路」と呼んでおり、あるノードからすべてのノードへの最短路の集まりを「最短路木（shortest path tree）」と呼んでいる。この木を求めるアルゴリズムとして「ダイクストラ法」があるが、TBRPFはそのアルゴリズムを独自に少し変形させたものを利用している。ダイクストラ法については余りにも有名なので、ここでは割愛させていただく。気になる方はWebサイトを検索してどのような手法なのかを確かめていただきたい。

　TBRPFでは、その距離は基本的にはすべて「1」である。従って基本的にはホップ数最短の経路が選ばれるわけだが、前回計算した送信者木の情報を見て、その木に含まれていないリンクについては「ペナルティ」という形で距離を追加している。これにより、木が頻繁に切り替わるのを防ぐことができる。その距離としては、0.01が推奨されている。また、可能ならば次ホップのノードによって報告されているリンクを使って木を作りたいため、報告されていないリンクにもペナルティという形で距離を追加する。その値としては、1.01が推奨されている。さらに、意図的に「メトリック」という形でもっと長い距離を設定して、そのリンクを送信者木に選ばれにくくすることも可能だ。もし等距離になる経路が複数あった場合は、転送優先度や、ノードIDによってどの経路を選ぶかを決定する。

　このように距離を決定して最短路木を求めることで、できるだけ変化が少なく、かつ使える可能性の高いリンクによる送信者木を求めることができるわけである。送信者木ができあがれば、各ノードへの次ホップは送信者木からすぐにわかるので、それに従って経路表は簡単に作成できる。つまり、図5で言えば、できあがった送信者木に従って、「ノードjへのパケットはノードaに送る」等のエントリーをすべて経路表に書き込めばよいことになる。

■報告ノード集合の更新と報告部分木の作成

　このようにして送信者木が作られるわけだが、それをそのまますべて送信するのはあまりよくない。データのサイズが大きくなってしまうし、実は他のノードが送信する情報と重複した情報が多いからである。従って、実際にはその一部分を送信することになる。その送信者木の一部分を、「報告部分木（reported subtree）」と呼んでいる。その作り方をここで簡単に説明すると、次のようになる。

　ノードiから直接通信できるすべてのノードを、ノードiの隣接ノード集合といい、Nと表現する。また、報告ノード集合という特殊なノードの集りを、RNと表現する。自分自身と、そのNに含まれるノードのみのネットワークを考えたとき、最短路が自分自身をホップして行くような経路の終点をRNに含め、かつ送信者木においてそのRNを次ホップとするような送信先ノードもRNに含める。最後に自分自身もRNに含める。こうしてできあがったRNを元にして、送信者木に含まれていて、かつRNを始点とするリンクを報告部分木とする。

　これを図5を使って説明すると、ノードiのNは水色の輪の上にいるノードの集まりであり、それらのノード間の最短路をすべて求めるわけである。たとえば、ノードaから他のすべての最短路が赤い矢印で描いた経路だったとする。するとノードiを通過する最短路は、終点がcとdとeの3つである。したがって、cとdとeはRNに含める。この図ではノードaからの最短路のみを描いているが、もちろん他のノードからの最短路もすべて計算する。そのたびに、ノードiを通過するような最短路の終点をRNに追加していく。

　すべての最短路の計算が終わっても、RNが相変わらずcとdとeだけであったとしよう。すると、それらを次ホップとするようなすべての送信先ノードもすべてRNに含める。つまり図で言うと、kとlである。そして最後にノードi自身もRNに追加する。結果としてRNは図のオレンジ色で囲まれるノードの集りとなり、報告部分木は、（i,c）（i,d）（i,e）（d,k）（e,l）となる。

■トポロジー更新メッセージの作成と送信

　トポロジー更新メッセージは約1秒毎に送信される。5回に1回はすべての情報を送信するが、その他は基本的に差分情報のみである。これによってメッセージのサイズを小さくすることができ、早急な更新が可能となる。このメッセージのフォーマットは以下の通りである。

図6:トポロジー更新メッセージ

　このメッセージで送信されるのは、前述の「報告部分木」の情報である。ただしひとつのメッセージでその全体を送信することはできず、一つ一つのメッセージは、あるひとつのノード（これをuとしよう）と、そこに直接繋がっている隣接ノード（それぞれv1,v2...,vnとしよう）の情報のみを含むことができる。それぞれのルータIDは「uのルータID」、「v1のルータID」というフィールドに入る。したがって、そのようなメッセージをいくつか送信することになる。たとえば、（i,c）（i,d）（i,e）（d,k）（e,l）という5つのリンクを送信したい場合は、3つのメッセージが必要になる。ただしそれは1つのパケットにして送ることができることに注意しよう。

　「型」には、このメッセージには全情報が含まれているのか、それとも追加情報なのか、削除情報なのかが入る。それぞれの具体的な値は、5、6、7である。その他のフィールドについてはドラフトを参照していただきたい。

　このようにして送信されたトポロジー更新メッセージは、周辺のノードで受信され、そのメッセージに入っている情報を元にして、トポロジー表が更新され、同時に送信者木と経路表も更新される。この仕組みによって、すべてのノードはネットワークのトポロジー変化に対応できるようになるのだ。

●まとめ

　今回の解説はとても長く、しかも少々わかりにくかったかもしれない。TBRPFプロトコルはここで説明した以外にも数々のアルゴリズムを駆使して成り立っているプロトコルであり、他に比べて数学的な要素の多いプロトコルである。

　簡単にまとめれば、できるだけメッセージを短い周期で大量に投げあうことによってネットワークの変化に即座に追従できるようにメッセージのサイズを最小限する必要があるので、送信者木の部分木を作成してその差分情報を送信したり、できるだけ長く利用できそうなリンクを使うために、管理するリンク情報に状態やカウンターをつけて、他のプロトコルよりも念入りにそのリンクの確認を行なうということになるだろう。

　以上でMANETで議論されているプロトコルの解説はひとまず締めくくりたい。次回の執筆は、勝手ながら3カ月後を予定している。内容は未定だが、少しプロトコルからは離れて、現実に近い部分の話をすることになるだろう。

　なお、本連載中に間違いを発見されたり、ご意見等ございましたら、編集部アドレス（internet-watch-info@impress.co.jp）までぜひお寄せください。たくさんのご意見をお待ちしてします。

　

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

(2003/6/24)

[Reported by 小出俊夫]