IEEE802.11sメッシュのはなし(1)

IEEE802.11s規格はIEEE802.11無線LAN(Wi-Fi)の拡張仕様で、メッシュ通信を実現するものです。今回はこのIEEE802.11sの話です。

IEEE802.11のヘッダとアドレスについて

IEEE802.11sについて語る以前に、まずIEEE802.11無線LANについておさらいしましょう。IEEE802.11にはアドホックモード(※註１)とインフラストラクチャモードがあり、アドホックモードでは無線ノード同士が直接通信します。インフラストラクチャモードではアクセスポイント(AP)とステーション(STA)の役割が分かれます。アドホックモードは原則として「閉じた」ネットワークですが、インフラストラクチャモードではSTAがAPの向こうに接続された有線の機器と通信することもできます。

(※註１) IEEE802.11-1999仕様には"Ad hoc network"という用語の定義がありましたが、2016仕様からは削除されました。仕様上の正式な用語では"IBSS(Independent BSS)"と呼びますが、今でも"Ad hoc mode"と呼ばれることが多いです。

小文字のSTA1eやSTA1wはネットワーク接点のMACアドレスを示しています。STA1は有線と無線に同時に接続しても構いませんが、中継することはできません。

アドホックモードと異なり、AP1を介して有線上のノード(ETH1)とも中継通信することができます。無線ネットワーク内での通信は原則としてAPを介して行う必要があり、STA1とSTA2が直接通信することはできません(※註２)。

(※註２) APから指示を下してSTA同士の直接通信を行うTDLS(Tunneled Direct Link Setup, IEEE802.11z)という拡張オプションも定義はされていますが、現実には殆ど使われていません。

インフラストラクチャモードでは、STAから発信するパケットには「どのAPに向けたパケットなのか」というアドレスと、「どの端末と通信したいのか」という２つの宛先アドレスが必要になります。このためIEEE802.11のデータフレームヘッダは可変長になっており(IEEE802.11-2020 9.3.2)、3ないし4つのアドレスフィールドが入ることになっています(※註3)。

(図) IEEE802.11のMACヘッダ

(※註3) 制御フレームのアドレス個数は1～4になり得ますが、ここでは割愛します

Frame ControlフィールドのB8とB9の「To DS」「From DS」フィールドがアドレスフィールドの個数と役割を定めており、まとめると次のようになります。なお「WDS」については後述します。

	ToDS	FromDS	Addr1	Addr2	Addr3	Addr4
IBSS	0	0	DA	SA	BSSID	n/a
To AP	1	0	BSSID	SA	DA	n/a
From AP	0	1	DA	BSSID	SA	n/a
WDS	1	1	RA	TA	DA	SA

(表) ToDS / FromDSとアドレスフィールドの役割

アドホックモードの場合ToDS=0, FromDS=0を取りフォーマットは3アドレス、Addr1が宛先・Addr2が発信元・Addr3はそのネットワークの識別子(BSSID)になります。アドホックモードのBSSIDは、最初にIBSSを立ち上げたノードが乱数で生成するローカルアドレスです(IEEE802.11-2020 9.2.4.3.4および11.1.4)。アドホックモードでの通信は無線アドレス間に限定されるので、図におけるSTA1のように有線と無線の２つのインターフェースを持っていても、無線側から有線側と通信すること(あるいはその逆)はできません。

インフラストラクチャモードの場合、上り(To AP)と下り(From AP)でフィールドの意味が変わります。上りはToDS=1, FromDS=0で3アドレス、Addr1がAPの識別子(BSSID=APの無線MACアドレス)・Addr2が発信元・Addr3が宛先です。下りはToDS=0, FromDS=1で3アドレス、Addr1が宛先・Addr2がAPの識別子・Addr3が発信元になります。

WDSの場合

WDS(Wireless Distribution System)はインフラストラクチャモードの拡張で、AP同士を無線で接続するものです。なおWDSという用語もIEEE802.11-2016仕様からは削除されており、ToDS=1/FromDS=1のフレームは公式には「メッシュ用」とされています。

この図ではWDS1がAPとしてSTA3,STA4を従えながら、自身はSTAとしてAP1の下にカスケード接続されています。この間のリンク(赤線で表示)は通常のAP-STAの3アドレス接続とは異なり、4アドレスフォーマットのフレームで接続されています。

AP1とWDS1は異なるBSSIDで動作します。SSIDやセキュリティ鍵が異なっても構いません(無線チップ/ドライバがそれを許容するなら)。もっとも無線ネットワークの範囲拡大のためにWDSを使う場合は、ローミングを前提としてマスター/スレーブAP間のSSIDやセキュリティを同じに設定することが普通です。

WDSではマスター/スレーブ間の中継が4アドレスになるので、経路は少々複雑になります。

Addr1～4の対応機能がTo/From DSのビットによって変わるので読みにくいのですが、最終的な発信元(SA)=STA3w・宛先(DA)=STA2wはどのホップでも変わらず、各ホップ間での発信元・宛先がBSSIDやTA/RAというフィールドで表記されていると理解してください。

IEEE802.11メッシュの場合

さてメッシュネットワークです。IEEE802.11sメッシュネットワークではAP-STAのような明確な役割を持たず、全てのノードが発信者でもあり・受信者でもあり・中継者でもあるという形態を取ります。単純な無線メッシュならばメッシュの中だけで閉じていますが、IEEE802.11sのメッシュは有線LANへの中継(Mesh Portal Point:MPP)やインフラストラクチャ無線LANへの中継(Mesh Access Point:MAP)も可能になっています。

(図) IEEE802.11s メッシュトポロジー

「Mesh ID」の青い丸点線でつながれたMPP1,MP1,MAP1,MPP2がメッシュ接続されています。この部分はアドホックネットワークと似ていなくもないですが、BSSIDは無く「Mesh ID」によって識別され(※註4)、すべてのメッシュ参加ノードは同じMesh IDを共用し、それぞれに定期的にビーコンを発信して互いの存在を知らせあっています。

全てのメッシュノード間には直接通信の可能性がありますが(灰色の点線)、実際には何らかの方法で選択された経路(黒の点線)に沿ってパケットが流れます。その「何らかの方法」については後述します。

 

(※註4) Mesh IDはアドホックやインフラストラクチャモードのSSIDに相当しますが、メッシュビーコンのID=0のIE(SSID)にはワイルドカード(長さ0)のSSIDが入り、Mesh IDはID=114のIE(Mesh ID)として格納されます。

 

この複雑な経路制御のためIEEE802.11sではMesh Control Fieldという拡張ヘッダを設けており、その中で１ないし２つの追加アドレスを持てるようになっていますMesh ControlフィールドはMACヘッダ領域ではなくフレームボディに食い込む形で付加され、その存在はQoSフィールドのBit8"Mesh Control Present"によって示されます(IEEE802.11-2020 9.2.4.7.3)。Mesh Flagsフィールドのbit1とbit0がAddress Extension Mode(AE)を意味し、

0:拡張アドレスなし(4アドレス・フレーム)

1:拡張アドレス１つ(5アドレス・フレーム)

2:拡張アドレス２つ(6アドレス・フレーム)

3:予約

として定義されています。

(図) IEEE802.11sのMesh Controlフィールド

Addr1 RA, メッシュ内での発信元アドレス

Addr2 TA, メッシュ内での宛先アドレス

Addr3 M-DA, 中継宛先アドレス

Addr4 M-SA, 中継発信元アドレス

Addr5 DA, 最終宛先アドレス

Addr6 SA, 発信元アドレス

 

IEEE802.11sのトポロジーは複雑になり得るので、アドレス配送も複雑になります。有線からMPPを経てメッシュを通り別のMPPにつながった有線へ届けるパターンと、有線からメッシュを通りAP-STA接続へ届けるパターンの２つを例示します。

Route 1 (ETH1->ETH2)

Hop	ToDS	FromDS	AE	Addr1	Addr2	Addr3	Addr4	Addr5	Addr6
ETH1->MPP2	n/a	n/a	n/a	ETH1(DA)	ETH2(SA)	n/a	n/a	n/a	n/a
MPP2->MP1	1	1	2	MPP1w(RA)	MPP2w(TA)	MP1w(M-DA)	MPP2w(M-SA)	ETH1(DA)	ETH2(SA)
MP1->MPP1	1	1	2	MPP1w(RA)	MPP2w(TA)	MPP1w(M-DA)	MP1w(M-SA)	ETH1(DA)	ETH2(SA)
MPP1->ETH2	n/a	n/a	n/a	ETH1(DA)	ETH2(SA)	n/a	n/a	n/a	n/a

Route 2 (ETH1->STA1)

Hop	ToDS	FromDS	AE	Addr1	Addr2	Addr3	Addr4	Addr5	Addr6
ETH1->MPP2	n/a	n/a	n/a	STA11(DA)	ETH2(SA)	n/a	n/a	n/a	n/a
MPP2->MP1	1	1	2	MAP1w(RA)	MPP2w(TA)	MP1w(M-DA)	MPP2w(M-SA)	STA1(DA)	ETH2(SA)
MP1->MPP1	1	1	2	MAP1w(RA)	MPP2w(TA)	MPP1w(M-DA)	MP1w(M-SA)	STA1(DA)	ETH2(SA)
MPP1->MAP1	1	1	2	MAP1w(RA)	MPP2w(TA)	MAP1w(M-DA)	MPP1w(M-SA)	STA1(DA)	ETH2(SA)
MAP1->STA1	0	1	n/a	STA1w(DA)	MAP1d(BSSID)	ETH2(SA)	n/a	n/a	n/a

(図) メッシュでのパケット配送経路とアドレス

一見すると複雑ですが、アドホックやインフラストラクチャモードと異なりAddr1～Addr6の役割が固定されているので、比較はしやすくなっています。しかし6アドレスのフレーム・フォーマットはメッシュでのパケット配送規則を定めているだけで、誰がどうやって配送経路を選択するのか(ルーティング・アルゴリズム)は別の枠組みになっています。

HWMPについて

HWMPにはReactive ModeとProactive Modeの２つの動作モード(※註5)がありますが、AODVから受け継いだReactive Modeについて解説します。このモードではPREQ(Path Request)とPREP(Path Reply)というアクションフレーム(※註6)を用いて、必要なときに経路探索を行います。「必要なとき」というのは「このMACアドレスへ送信したい」という要求が発生したとき、HWMP層が持っている近隣キャッシュに対応するエントリーが無いときです。

 

(※註5) IEEE802.11-2020仕様の正式な用語では、Reactive Modeを"On-demand path selection mode"、Proactive Modeを"Proactive tree building mode"と呼んでいます。長いので本稿では"Reactive Mode"と"Proactive Mode"と呼びます。

(※註6) アクションフレームはType=0, Subtype=0x0Dの制御フレームです。PREQ/PREPの機能はInformation Elementによって識別しPREQはTag=130(0x82)、PREPはTag=131(0x83)の値を持ちます。

(図) PREQとPREP IEのフォーマット

ここで「でもそれ以前に、IPアドレスに対応するMACアドレスを検索する必要があるよね？」と思うかも知れません。IEEE802.11sには「ブロードキャスト・フラッディング」という、ARP Requestのようなブロードキャスト(あるいはIPv6 Neighbor Solicitationのようなマルチキャスト)フレームは問答無用でネットワーク全域へ拡散する仕組みが備わっています。

フラッディングによってARP Requesetはネットワーク全域に届き、「あっ、それ俺だ」という場合(MPノードアドレスとの一致)あるいは「そのアドレス知ってる(MPPやMAPのブリッジの場合)」はそのノードがARP Replyを返答します。しかしARP Replyはユニキャストで発信され、そしてユニキャストを返すメッシュ経路はまだ確定していません。ここでPREQがブロードキャストで発信され、ARP Requestが来たのとは逆の経路でフラッディング拡散され、ARP Requestを発信したノードにまでたどり着きます。

ノードはユニキャストでPREPを返しますが、PREQの拡散過程で近隣キャッシュが更新されているはずなので、受け取った「お隣さん」にオウム返しに投げれば来た道を辿って発信元に届くはずです。

HWMPの動作

HWMP Reactive Modeの動きをステップバイステップで解説してみます。まず図のようなメッシュネットワークがあるとします。MP1～MP4までの4ノードで構成されており、MP4はやや離れていてMP1から直接の電波は届きません。MP2～MP4の電波は届くけれど距離が離れていて条件は悪いものとします。

MP1がMP4=10.0.0.4と通信を試みるとき、まずARPブロードキャストのフラッディングが発生します。これは電波到達範囲内の全てのノードに受信され、受信したノードはこれをオウム返しに再送信するものです。ただし何も考えずに再送すれば「ピンポン」や「ループ」になって同じパケットの再送信が永遠に繰り返されてしまうので、各パケット(のMesh Controlフィールド)にはTTLカウンタ(※註7)と32bitのシーケンスナンバーが含まれ、「再送信する度にTTLを1減らす」「TTLが0になったパケットは再送信しない」「TTL>1でも過去に再送信したシーケンスナンバーのパケットは再送信しない」ことで無限再送を回避しています。

(※註7) TTL初期値は1～255に設定可能ですが、デフォルト値は31となっています(IEEE802.11-2020 Annex C dot11MeshTTL)。

ARP Requestを受信したMP4はPREQをブロードキャスト送信して「MP1は何処に居るのか？」を調べます。PREQも各ノードによって中継再送されますが、中継するたびにMetric値が更新されてゆきます。Metric値は通信中継(ホップ)に要するコストで、ここではMP2～MP4間が20、その他のノード間は10と仮定しています。

MP1はMP2とMP3の両方からPREQを受信しますが、通ってきた経路が違うのでMetric値も異なっています。MP1はMetricの小さい方を「より有望な経路」と判断して、PREPを名指しのユニキャストでMP3に送信します。MP3は自分の持つMetric情報を加えてパケットをMP4へ中継再送します。こうして各ノードに「近隣ノードとMetric値と、必要ならば最近隣の中継ノード」の一覧リストが作られることになります。

(図) MP1からPREPの返信、路と近隣ノードの一覧更新

PREQ-PREPの往復によって経路ができたので、MP4は持っている近隣表に従ってMP1行きのARP ReplyパケットをMP3に投げます。MP3はこれをMP1へ中継し、こうしてARP Request-Replyの往復が完了します。中継表には揮発時間があり、新たなPREQ/PREPの受信がなければ一定時間で失効します。この揮発時間(dot11MeshHWMPactivePathTimeout)はデフォルトで5000TU(5秒)に設定されています。

HWMP Proactive Modeについて

HWMPのもうひとつのモード「Proactive Mode」については簡単に説明します。これはReactive Modeと異なり、通信の必要の有無に関わらず経路探索と近隣表を更新することを意味します。

Proactive Modeでは、経路探索を仕切る"Root Node"を設定する必要がありますRoot Nodeは一定時間に一度ブロードキャスト送信してフラッディングを誘発し、全ネットワークの接続状態を強制的に更新します。Root Nodeが送信するフレームにはPREQとRoot Announcement(RAAN)の２つのモードがあり、前者は個々のノードがPREPを返すこと・後者は個々のノードがPREQを発信することで近隣表を更新するものですが、詳細については割愛します。いずれにせよ、Root Nodeが強制的にフラッディングを誘発し全ノードの近隣表を更新することでLink State型に近い動作になります。これがHWMPがAODVから拡張された機能であり、"Hybrid"である所以です。

Proactive Modeの利点は、Reactive Modeよりも安定した経路が得られる公算が高いことです。欠点は定期的にフラッディングが起こされるのでネットワーク効率が低いことと、Root Nodeが落ちたり圏外になったりすると経路更新が止まるので冗長性が低いことです。

リンクメトリック

上記の例では、リンクメトリックを「MP2-MP4間が20、その他のノード間は10」と仮定しました。実際には何らかの方法を用いて実測しなければなりません。これもHWMPではAirtime Link Metricと呼ぶ標準アルゴリズムが規定されています。これはパケット送信に伴う電波の占有時間を推定するもので、下記の式が定義されています(IEEE802.11-2020 14.9.2)。

 

ca: 推定電波占有時間(μ秒)

O:パケット送信のオーバーヘッド時間(μ秒)

n:アグリゲーション数(通常は1)

Bt:1パケットのビット数(8192)

r:PHYのデータレート、Mbit/sec

ef:フレームエラー率(% ÷ 100)

 

O,n,Btは定数なので変数はrとefの2つ、Bt/rは1パケットあたりの占有時間、1/(1-ef)は再送回数の推定を意味しています。フレームレートrは大きいほどcaは小さくなり、しかしエラー率efが大きくなるとcaは大きくなる(エラー率50%なら1/(1-0.5)=2倍になる)理屈になります。

 

「へー」と思うかも知れませんが、無線LANのデータレートは通信条件によって変化します。そして、何を条件としてどんな規則でレートを選択するのか・通信発生前のデフォルトレートを何にするのかはドライバの実装によって異なります(※註8)。いずれにせよ、ある程度の通信を交わさないと有効なデータレートは収束しません。更にフレームエラー率も一定量の通信をしなければ収束せず、しかもACKを伴わないブロードキャストのフラッディングでは計測できません。

 

(※註8) Linuxのオープンソースドライバでは、カーネルに組み込まれているMinstrelと呼ばれるデータレート選択アルゴリズムを使います。しかしメーカー純正ドライバではそうとは限らず、しかも最近の無線チップはCPUを内蔵してオンチップ・ファームウェアで通信処理するものが増えており、その場合レート制御アルゴリズムはファームウェアに実装されるのでますますわからなくなっています。

 

つまりメトリック計測にはある程度のデータ量を実際に通信してみる必要がありますが、しかしメッシュ通信では経路選択されないかぎりノードを経由する通信は発生せず、経路選択のためにはメトリック値が計測されなければならないというニワトリタマゴの矛盾が生じます。これはAirtimeに限らず無線メッシュ経路選択には共通する問題なのですが(※註9)、ACKを伴うユニキャストフレームを一定数通信しないと収束しないパケットエラーレートを使うAirtime方式ではより深刻になります。

アプリケーションが全ノードと一定間隔で通信する場合は、その通信をもって計測することもできますが、そうでない場合はProactive Modeを用いて一定間隔での全ノード通信を強制的に誘発したほうが経路が安定するかも知れません。純粋なReactiveモードでは、ユニキャストパケットを殆ど交換していない(ビーコンやフラッディングしか受信していない)近隣ノードとの間で実際の通信品質に対応したメトリック値が算出できないため、適切な経路制御が行えない(※註10)可能性が高くなります。

 

(※註9) 電波状況ならビーコンのRSSIを使えばいいんじゃないの？と思うかも知れませんが、色々な理由があってRSSIは必ずしも実際の通信品質を反映しないのです。前述のMinstrelレート選択アルゴリズムについては論文(https://blog.cerowrt.org/papers/minstrel-sigcomm-final.pdf)が出されており、この中でも"RSSI and SINR are poor guides"とされています
 

(※註10) 具体的には、ぎりぎり電波が届いているくらい遠いノードへの通信が、より電波状況の良い２ホップや３ホップではなく１ホップの直接経路で選ばれてしまったりします。

まとめ

如何でしょうか？メッシュって意外にめんどくさい、と思うかも知れません。ネットワークを埋め尽くすブロードキャスト・フラッディングだとか、通信実績に基づくAirtime Metricの推定なんて不安なメカニズムだと思うかも知れません。

結局、メッシュは柔軟性とネットワーク効率のトレードオフなのです。柔軟性を重視するほど冗長なトラフィックが頻繁に発生して効率を悪化させ、効率を重視するとトポロジーの変化に追従できなくなって柔軟性が下がります。一般的には、トポロジー変化の少ない(固定局的な)メッシュにはLink State型が、変化の多い(モバイル的な)メッシュにはDistance Vector型が向いているとされますが定量的な評価指標があるわけではなく、最適解は設置や運用の条件によって変わります。HWMPがReactiveとProactiveの２モードを持ち、Proactiveモードには経路探索モードが３つあり、近隣キャッシュの有効時間やフラッディング間隔などがいちいち可変パラメータになっているのには、そういう事情があります(※註11)。

さて、次回はLinuxを用いて実際にメッシュを動かしてみることにします。

 

(※註11) 無線メッシュが熱い話題だった2000年～2010年頃には、この問題を機械的に(アルゴリズムで)解決することが試みられて大学や大企業の研究所、あるいはネット上のグループあるいは個人から様々なアルゴリズムが(往々にしてオープンソース・プロジェクトして)提案されましたが、その殆どが袋小路に入ってアップデートが止まり自然消滅してしまいました。アルゴリズムを凝れば凝るほどパラメータが増えてカオス化し収拾が付かなくなる傾向があり、むしろブロードキャスト・フラッディングのように単純な脳筋メカニズムのほうが長生きしています。

製品情報

• メッシュネットワーク：テクノロジー紹介ページへ