■ 第6回 OLSR（Optimized Link State Routing）プロトコル ■

●MANET WGの最近の状況

　IETF MANET WGでは、候補となるプロトコルを広く集め議論を重ねてきたが、最近になってプロトコルをDSR、OLSR、AODV、TBRPFの4つに絞り、Experimental RFCとして投稿することを決めた。また、インターネットドラフトも更新されている。今回の題材であるOLSRプロトコルについても、2003年3月3日に発行された「draft-ietf-manet-olsr-08.txt」を基にして解説を行なう。

　これらのプロトコルが1つに統合されるのか、それともReactive型とProactive型に分けられるのかはまだ分からない。だが、MANETのプロトコルがインターネット標準として姿を現わすのもそろそろ時間の問題となってきたようだ。

●OLSRプロトコルの概要

　OLSRプロトコルはProactive型のルーティングプロトコルだ。したがって、経路は通信を行なう前に確定されており、いつでも直ちに通信を開始することができる。第5回で説明したDSRプロトコルはReactive型なので、その違いを意識しながら読むと理解が深まるだろう。

　OLSRプロトコルの特筆すべき点は、「フラッディング」を効率よく行なうことができるということであり、それがほぼ唯一の特徴でもある。フラッディングとは、同一パケットを1つのノードからすべてのノードへ配信すること、すなわち一斉配信のことだ。OLSRでは、ノードの密集度が高ければ高いほど効率的なフラッディングが行なえる。これに対して、一般的なネットワークでフラッディングを行なう場合は次のようなアルゴリズムが用いられる。

• 送信元ノードは、自分に繋がるすべてのノードにパケットを送信する
• 各ノードは、受け取ったパケットを、自分に繋がるすべてのノードに転送する
• ただし、一度送信したパケットを再び受信した場合はそのパケットを破棄する

多少の最適化方法は存在しても、フラッディングのアルゴリズムの基本は上記の通りである。すなわち、すべてのノードは必ず1回、送信処理を行なうのだ。

　ルーティングプロトコルなどによって生成される制御情報を載せたパケットは、ネットワークに参加している全ノードに対して配信される場合が多い。したがって、いかにフラッディングを効率よく行なえるかが、そのプロトコルの質に関わってくるといっても過言ではない。OLSRプロトコルでは、これをマルチホップ無線ネットワークで効果的に実行するために、「MPR（multipoint relay）集合」というノードの集まりを規定している。これを図1を使って簡単に説明しよう。

図1　MPR集合による再送信ノード数の削減

　 図1の左側は、マルチホップ無線ネットワーク上で、一般的なフラッディングを行なった場合に、パケットが移動する様子を矢印で表わしたものである。パケットの送信元は左上のノードである。このノードからは5本の矢印が出ているが、パケットの送信は電波で行なわれるため、実際には電波の発信は1回で済むことに注意したい。

　パケットを受信したノードはすべて、直ちにそのパケットを再送信する。そのノードを「再送信ノード」と呼ぶことにしよう。図中では、ピンクの太線で囲った5つのノードのことである。この5つのノードが電波を送信すると、残りの7つのノードに電波が届き、それらはそのパケットを受信することになるのだが、ここでかなりの無駄が存在していることに気付くだろうか。効率のよさを考えれば、右側のように再送信ノードは3つで済むのである。

　このように、必要最小限の数の再送信ノードの集まりによってフラッディングを行なうというのがOLSRプロトコルの基本思想であり、そのようなノードの集まりを「MPR集合」と呼んでいる。MPR集合が決まれば、あとはそれらによってルーティングに必要な様々な情報をフラッディングすることになる。OLSRでは、すべてのノードがネットワークのトポロジー（どのノードがどのノードとどのように繋がっているかの情報）を蓄えるが、これもMPR集合によってフラッディングされている。各ノードでは、そのようにして得たトポロジーを基にして経路を計算し、経路表を作成している。実際に行なわれるノード間の通信は、この経路表を基にしている。

　以上がOLSRプロトコルの概要である。このプロトコルの中核は、まさにMPR集合であり、この集合を決定するアルゴリズムが非常に重要となってくる。

●OLSRのパケットフォーマット

　アルゴリズムの解説に入る前に、OLSRでやり取りされるパケットや、その中身について整理しておこう。OLSRプロトコルに関係するすべてのメッセージは、図2に示すフォーマットのパケットで送受信される。

図2　OLSRのパケットフォーマット

　パケットはUDP（User Datagram Protocol）のポート番号698番を使って送受信される。なお図2は、IPやUDPヘッダを取り除いた形になっている。OLSRのパケットは、「パケットヘッダ」と複数の「メッセージヘッダ」から成り立っている。

　パケットヘッダは、「パケット長」と「パケットシーケンス番号」の2つで構成されている。パケット長はパケットのバイト数、パケットシーケンス番号は新しいパケットが生成されるたびに1つずつ増える値で、どのパケットが新しいかを区別するために用いられる。

　メッセージヘッダは、「メッセージタイプ」、「有効時間」、「メッセージサイズ」、「発信元アドレス」、「TTL」、「ホップ数」、「メッセージシーケンス番号」と、メッセージ本体によって構成されている。メッセージタイプは、メッセージ本体に書かれているメッセージの種類を表わし、0から127が予約済みである。有効時間とは、受信後にこのメッセージを管理していなければならない時間であり、仮数部と指数部で構成されている。メッセージサイズでは、メッセージの長さ、発信元アドレスはこのメッセージを生成したノードのアドレスを表わしている。TTLでは、このメッセージが転送される最大ホップ数が指定されており、転送される時に必ず1つ減らされる。このフィールドが1か0の場合は転送されない。ホップ数は、このメッセージの生成元からのホップ数であり、最初は0に設定され、転送される毎に1つずつ増やされる。メッセージシーケンス番号は、各メッセージに割り当てられる識別番号で、メッセージが作成されるたびに、その番号は1つずつ増やされる。重複するメッセージを転送しないためなどに用いられる。

　メッセージには、HELLOメッセージ、TCメッセージ、MIDメッセージ、HNAメッセージの4種類がある。今回は、その中でも重要なメッセージのHELLOメッセージとTCメッセージの2種類について解説する。

●HELLOメッセージ

　HELLOメッセージは、各ノードの持つ情報の配信を目的として、定期的に送信されるメッセージだ。このメッセージを受信することで周辺情報の収集ができることになる。このメッセージを送受信しなければ、自分の周辺にどんなノードがいるのかが把握できないので、最も基礎的なメッセージといえるだろう。

　各ノードでは「ローカルリンク情報」が管理されている。HELLOメッセージとは、このローカルリンク情報の構築や送信を行なうためのメッセージに他ならない。ローカルリンク情報には、

• リンク集合
• 隣接ノード集合
• 2ホップ隣接ノード集合とそれらのノードへのリンク集合
• MPR集合
• MPRセレクタ集合

の5つの集合が含まれている。

　それぞれについて簡単に説明しよう。「リンク集合」は直接的に電波が届くノード（隣接ノード）の集合へのリンクのことであり、各リンクは2ノード間のアドレスの組と有効時間によって表現されている。有効時間は、そのリンクが単方向なのか双方向なのかを表わすためにも利用されている。「隣接ノード集合」は、各隣接ノードのアドレスや、そのノードの再送信への積極度（Willingness）などによって構成されている。その他、隣接ノード集合のさらに先に存在するノード集合、MPRとして選択された隣接ノードの集合、もし自身がMPRとして選択されている場合には自分をMPRとして選択しているノードの集合（MPRセレクタ集合）などの情報が、ローカルリンク情報として各ノードに存在している。

　では、HELLOメッセージによってこのローカルリンク情報が構築される様子を簡単に追って見てみよう。HELLOメッセージは、初期の段階では自分の存在をアピールするために、自分のアドレスの入ったHELLOメッセージを隣接ノードへ向けて送信する。これをすべてのノードが行ない、各ノードは自分の周りにどんなアドレスを持ったノードがいるのかを把握する。こうしてリンク集合と隣接ノード集合が構築されていく。しかしこの時点では、それぞれのリンクが双方向かどうかは不明で、送信元から自分のノードへのリンクがあるということしか分からない。

　構築されたローカルリンク情報のほとんどは、再びHELLOメッセージによって定期的に送り続けられる。これを繰り返すことで、各リンクが双方向であるのか、隣接ノードの先にはどんなノードがあるのかが徐々に明らかになってくる。これらの情報もローカルリンク情報として蓄えられていく。

　さらに、MPRに関する情報もこのHELLOメッセージで定期的に送信され、告知されていく。前述したように、各ノードは自分が送信するパケットの再送信を依頼するノードとして、いくつかのMPRを隣接ノードの中から選択している。この情報はHELLOメッセージによって隣接ノードに送信されるので、これを受け取ったノードは、自分がMPRとして選択されていることを理解することができ、自分をMPRとして選択してきたノードの集合を「MPRセレクタ集合」として管理しておく。こうすることで、どのノードから来たパケットを再送信すればよいのかが一目瞭然となる。

●MPR集合の選択アルゴリズム

　さて、OLSRプロトコルの中核はMPR集合であり、それをいかに選択するかがフラッディングの効率化の鍵である。そのMPR集合の選択アルゴリズムについて概要を解説しよう。

　まず、MPR集合とは何かについて整理したい。MPR集合とは、OLSRプロトコルが動いているネットワーク上でフラッディングを行なう際、パケットの再送信を責任を持って行なうノードの集まりのことである。これはネットワーク上の各ノードによって、隣接ノード集合の中から選ばれている。すなわち、「ノードAのMPR集合」、「ノードBのMPR集合」という言い方をする。ノードAのMPR集合は、ノードAから発せられたパケットを再送信する義務を負う。それ以外のノードは、ノードAからのパケットを受信しても決して再送信は行なわない。

　この仕組みでは、再送信が1回分だけしか行なわれないように感じられる。しかし、ノードAのMPR集合としてノードCとDが選ばれていたとすると、ノードCやノードDもまた自分のMPR集合を持っているので、連鎖的に再送信が行なわれ、結果としてパケットが隅々までフラッディングされることになるのである。

　さらに各ノードは、Willingnessという0～7の範囲の値を持っており、この値が高ければ高いほど、MPRとして選ばれやすくなる。この値はHELLOメッセージによって送信されるので、周辺に存在するノードは、どのノードがどれだけ再送信に対して積極的であるかを把握する。0の場合はMPRとしては選ばれず、7の場合には積極的に選ばれる。通常の値は3である。分かりやすいように、それぞれの値には次表のような名前が付けられている。

　問題は、各ノードがどのようにMPR集合を選べばよいかということだ。理想的なのは

「隣接ノード集合の1ホップ先に存在するすべてのノードにパケットが転送されるように、最小数のノードでMPR集合を構成すること」

だが、そのような最適なMPR集合を見つけるためには「NP完全」クラスの問題を解かなければならない。簡単に言うと、ノード数が増えてしまうとどんな優秀なコンピュータを使っても、実用時間内ではそのような答えは出せないということだ。そこで、現在のOLSRのドラフトではその最適性にはこだわらずに、そこそこいいレベルのMPR集合を見つける高速なアルゴリズムを提案している。

　ではそのアルゴリズムの概略を、図を使って説明していこう。各ノードは、HELLOメッセージを送受信することによって、隣接ノードの先に繋がっているノードまでの状態を把握している。たとえば、図3のようにノードが存在し、通信できる関係が灰色の線のようになっていたとする。このときノードSが知っている範囲はノードkとl以外のすべてのノードであり、それらがアルゴリズムの計算の対象となる。なお、以下で述べるアルゴリズムは、すべてノードSの内部で行なわれている。このため、アルゴリズムの実行により、余分なパケットを送信することはない。また、各ノードのWillingnessは特に指定されていない限りWILL_DEFAULTとする。

図3　初期状態

　まずノードSは、自分が知っているノードから、「N」と「N²」という2つの集合を作り出す。「N」とは双方向のリンクを持った隣接ノード集合のことである。図中では緑色で囲まれたノードに相当する。「N²」は「N」からさらに双方向リンクで繋がっているノードの集合のことであるが、ノードS自身や、「N」に含まれるノードは除外される。したがって、「N」と「N²」双方に所属するようなノードは存在しない。また、Willingnessが「WILL_NEVER」となっているノードにしか繋がっていないノードも除外される。これは図中ではノードnに相当する。このように「N²」には細かい条件がいろいろあるが、図3のような場合は水色で囲まれているノードが「N2」となる。アルゴリズム中では、「N」はMPRとなるノードの候補、「N²」はまだMPRが選択されていないためにパケットが届かないノードという意味で用いられる。

　次に、「N」の中からWILL_ALWAYSであるノードをMPR集合として選ぶ。図中ではノードaである。すると、ノードf・g・hはそのノードからパケットを受け取れるようになるので、「N²」から削除する。こうして図4のような状態になる。

図4　WILL_ALWAYSノードの選択

　その後、Willingnessの最も大きいノードをMPR集合に追加する（ただし「N²」へのリンクがないノードは除く）。もし同じWillingnessであった場合は、「N²」に存在するノードへ対して、より多くパケットを届けられるノードを選ぶ。つまりMPRにした時により多くのノードがカバーできるようなノードを選ぶわけだ。こうしてMPRとして選択されたノードから届くノードを「N²」から削除する。これを図で説明すると、図4ではノードeが他のノードよりもWillingnessが高いので、ノードeがMPRとして選ばれて図5の状態になる。

図5　WILL_HIGHの選択

　このように「N²」からすべてのノードが削除されるまでこれを繰り返す。図の例でいうと、ノードdによって「N²」の残りがカバーされて、結果としてMPR集合はノードa・d・eとなる。

　MPR集合の計算が行なわれると、MPR集合に含まれるノードは、ノードSから発せられるHELLOメッセージによって、自分がノードSのMPRとして選択されたことを知るので、MPRセレクタ集合にノードSを追加する。これ以降ノードSから発せられるパケットは、この3つのノードによって、図3の「N²」のノードすべてに再送信されることになる。「N²」に含まれるノードもそれぞれがMPR集合を決定しているので、さらにその先へと、連鎖的にパケットが再送信されていくことになる。

●TCメッセージと経路表の作成

　以上のようにしてフラッディングのための基盤はでき上がったわけだが、経路表はまだ作成されていない。誌面が限られているので概要までにとどめるが、OLSRでも一般的に用いられているルーティングプロトコルと同じように、最短路に基づく経路表の作成を行なっている。

　OLSRプロトコルでは、HELLOメッセージとは別に、TC（Topology Control）メッセージというメッセージも頻繁に行き交わしている。HELLOメッセージが届く範囲は単純に隣接ノードだけ（すなわち再送信は行なわれない）だが、TCメッセージはネットワーク全体へフラッディングされるメッセージである。もちろんこのフラッディングにはMPRが利用されるので、効率的なメッセージ転送が行なわれる。

　TCメッセージの役割は、ネットワーク全体のトポロジーを各ノードに知らしめることだ。各ノードはそのトポロジー情報を基にして実際の通信経路を計算し、経路表を構築する。トポロジーといっても、実際に存在するすべてのリンクから構成されるトポロジーではなく、基本的には各ノードのMPRセレクタ集合から構築されるトポロジーであるため、管理するリンク数は実際のリンク数よりも非常に少ない。ここでもMPRの思想がうまく生かされているわけである。

　TCメッセージはMPRとして選択されているすべてのノードが定期的に発信する。その中身には、最低でも自分自身とMPRセレクタ集合間のリンクが含まれている。こうしてネットワーク上のすべてのノードはすべてのMPRとそのMPRセレクタ集合を知ることができ、それを基にしてネットワーク全体のトポロジーを知ることができるのだ。各ノードはそのトポロジーを用いて最短路を計算し、それに基づいて経路表を作成する。このようにして、各ノードは全ノードと自由に通信ができる状態になる。

●まとめ

　他にもドラフトでは、単方向のノードがある場合の考慮や、冗長性を持たせてネットワーク信頼性をあげる方法、1つのノードに複数のインタフェースがある場合など、いろいろな場合について規定されている。だがOLSRの本質は、各ノードがMPR集合を隣接ノードから選ぶことによって、効率的なフラッディングが行なえるということだ。ノード密度が高くなればなるほど、その効果は絶大となることは容易に想像がつくだろう。ネットワーク全体のトポロジー情報はその効率的なフラッディング基盤を利用して交換され、各ノードで経路表が計算される。OLSRの基本的な仕組みを簡単にまとめればそのようになるだろう。

　

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

(2003/4/16)

[Reported by 小出俊夫]