Optimized Link State Routing Protocol

最適化されたリンクステートルーティングプロトコル (OLSR) について

最適化されたリンクステートルーティングプロトコル（OLSR）は、主にモバイルアドホックネットワーク（MANET）用に設計されたIPルーティングプロトコルですが、他のワイヤレスアドホックネットワークでも利用できます。OLSRはプロアクティブなリンクステートルーティングプロトコルであり、ネットワーク内の各ノードが、Helloメッセージとトポロジー制御（TC）メッセージを使用して、ネットワーク全体のリンク状態情報を検出し、共有します。

OLSRの基本動作

各ノードは、受信したトポロジ情報を用いて、ネットワーク内の全ノードへの最短ホップパスを計算します。これにより、効率的なパケット転送が可能になります。

OLSRの独自性

従来のリンクステートルーティングプロトコル（例：OSPF、IS-IS）では、指定されたルーターが全てのリンクでトポロジ情報をフラッディングしますが、無線アドホックネットワークではリンクの概念が異なるため、別の手法が必要です。OLSRでは、Helloメッセージを使用して各ノードが2ホップ先のネイバー情報を検出し、マルチポイントリレー（MPR）と呼ばれるノード群を分散的に選択します。ノードは、自身の2ホップネイバーへのパスが必ず存在するよう、MPRを選択します。選択されたMPRノードは、MPRセレクターを含むTCメッセージを送信し、転送します。

このMPRメカニズムにより、OLSRは他のリンクステートルーティングプロトコルとは異なる特徴を持ちます。TCメッセージの転送経路は送信元によって異なり、全てのノード間で共有されません。また、リンク状態情報を送信するのは一部のノードのみで、全てのノードではありません。さらに、アドバタイズされるリンクは、MPR選択を表すものに限られます。

信頼性に関する考慮

OSPFやIS-ISのようなリンクステートルーティングプロトコルでは、信頼性の高いアルゴリズムを用いてトポロジー情報を同期しますが、アドホックワイヤレスネットワークでの実装は困難です。そのため、OLSRでは信頼性よりも、データベースが長時間非同期にならない程度に十分な頻度でトポロジデータをフラッディングすることに重点を置いています。

マルチポイントリレー (MPR)

MPRは、ノード間でのメッセージ中継を担い、送信元から宛先への適切なルートをルーティング・選択する上で重要な役割を果たします。MPRは、定期的に自身のリンクステート情報を制御メッセージでアドバタイズします。また、ルート計算において、特定のノードから任意の宛先へのルートを形成するためにも使用されます。各ノードは、リンクセンシング、ネイバー検出、MPR選択のため、Helloメッセージを定期的にブロードキャストします。

OLSRの利点

• - プロアクティブなルーティング: ネットワーク内の全宛先へのルートが事前に認識され、維持されるため、ルート発見遅延がありません。これにより、一部のシステムやネットワークアプリケーションで有効です。
• - 安定したルーティングオーバーヘッド: 生成されるルーティングオーバーヘッドは、リアクティブプロトコルよりも大きくなる傾向がありますが、作成されるルート数には依存しません。
• - HNAメッセージのサポート: HNAメッセージにより、デフォルトルートやネットワークルートをシステムに挿入でき、OLSR MANETクラウドからインターネットや他のネットワークへの接続が可能です。
• - 柔軟なタイマー設定: タイムアウト値や有効性情報がメッセージに含まれるため、ノードごとに異なるタイマー値を使用できます。

OLSRへの批判点

• - リンク品質の検知の欠如: OLSRの初期定義では、リンク品質の検知に関する規定がありません。リンクはバイモーダル（正常か失敗か）であると想定していますが、ワイヤレスネットワークでは中間的なパケット損失が発生することがあります。ただし、オープンソースのOLSRdなどの実装では、リンク品質検出機能が追加されています。
• - リソース消費: プロアクティブなプロトコルであるため、未使用の可能性があるルートに関するデータを伝播するために電力とネットワークリソースを消費します。これは有線アクセスポイントなどでは問題になりませんが、センサーネットワークには適していません。
• - 帯域幅とCPUパワーの消費: リンクステートプロトコルであるため、最適なパスを計算するために比較的多くの帯域幅とCPUパワーが必要です。ただし、一般的なネットワーク規模では問題になりません。
• - フラッディングの冗長性の欠如: MPRのみを使用することで、フラッディングプロセスの冗長性が低減されます。これは、中程度から大きなパケット損失率のネットワークで問題になる可能性があります。ただし、MPRメカニズムには自己プルーニング機能があります。

OLSRのメッセージ

OLSRは主に以下のメッセージを使用します。

• - Helloメッセージ: 1ホップおよび2ホップネイバーの発見に使用されます。送信者は、最適なルートを提供する1ホップノードに基づいてMPRを選択します。
• - トポロジー制御 (TC) メッセージ: ネットワーク全体にネイバー情報を配信するために使用されます。
• - ホストおよびネットワークアソシエーション (HNA) メッセージ: ネットワークルート広告を配布するために使用されます。

その他のアプローチ

アドホックワイヤレスネットワークでのルーティング問題は活発に研究されており、OLSRは多くのソリューションの一つです。帯域幅や電力に制約のある環境では、ルーティングするトラフィックがない時にネットワークを静かに保つことが重要です。リアクティブルーティングプロトコルはルートを保持せず、必要な時に構築します。一方で、リンクステートプロトコルはデータベースの同期が必要なため、距離ベクトルアプローチや動的ソースルーティングのような、最適とは限らないパスを構築するアプローチが採用されます。

OLSRバージョン2

OLSRv2は、IETFにより2014年4月に公開されました。OLSRv2は、MPRの選択や普及など、オリジナルの主要な機能を維持しつつ、柔軟性とモジュール性のある設計となっています。主な違いとして、パケット形式packetbb、近隣探索プロトコルNHDPのような共有コンポーネントを採用しており、複数のアドレスやインターフェイスを持つノードの処理方法も異なります。

実装

OLSRは以下のプロジェクトで実装されています。

• - OLSR.org: Linux, Windows, Mac OS X, FreeBSD, NetBSD, OpenBSDで利用可能。
• - NRL-OLSR: Windows, MacOS, Linux, Arm/Zaurus, Pocket PCなどの組み込みPDAシステム、およびシミュレーション環境ns2, OPNETで利用可能。
• - SOURCEFORGE.NET-OLSR: C#で記述されており、WM 6, Win XPなどのプラットフォームで利用可能。ネットフレームワークとコンパクトを使って他のプラットフォームにも適合可能。

関連技術

• - BATMAN (Better Approach To Mobile Adhoc Networking)
• - IEEE 802.1aq
• - TRILL (Transparent Interconnection of Lots of Links)

参考文献

• - IETF (Internet Engineering Task Force)
• - olsr.funkfeuer.at
• - 最適化されたリンクステートルーティングに関するFlashデモ
• - Pyramid Linux
• - NRLのネットワークおよび通信システムブランチ

もう一度検索