yasutoshi's blog

IEEE802.11e

http://mailman.isi.edu/pipermail/ns-users/2006-September/057314.html

のmlに載っていた情報

11eの実装ウェブページが見つかりました

http://www.telematica.polito.it/casetti/802.11e/

http://www-sop.inria.fr/planete/qni/fhcf/

http://www.tkn.tu-berlin.de/research/802.11e_ns2/

とりあえずこの3つを読み進めてみます．

あとはちゃんとシナリオを固めることだ…

google力磨かないとなぁ

IEEE802.11e for the ns-2 simulator

・An IEEE 802.11e EDCA and CFB Simulation Model for ns-2

http://sourceforge.net/projects/ieee80211e-ns2/

とりあえずバックアップとって置いた

HCCA for ns2

http://info.iet.unipi.it/~cng/ns2hcca/

nsでRTS/CTSをオフにする方法

http://mailman.isi.edu/pipermail/ns-users/2006-September/057278.html

次の行をTclに書き込むだけらしい．

　Mac/802_11 set RTSThreshold_ 3000

シミュレータ

無線LANでよく利用されるシミュレータに

GloMoSim　というものと　NS-2(Network Simulator）がある

どちらのほうが優れているのか，

IEEE802.11eのシミュレーションではどちらをりようすべきか

を調査

http://www.ishilab.net/~ishihara/sim/index.html

ネットワークシミュレータ全般の解説（石原先生のblog）

GloMoSim

本家（http://pcl.cs.ucla.edu/projects/glomosim/）

日本語解説ページ

http://www.cs.hiroshima-u.ac.jp/~gsun0125/index.html

http://www.cs.hiroshima-u.ac.jp/~gsun0125/　より

引用：現在GloMoSimからQualnetに移行しており、プロジェクト自体

は終了しております．

ががーん！そうだったのか！！

ns-2

本家：http://www.isi.edu/nsnam/ns/index.html

ドキュメント（マニュアル）：http://www.isi.edu/nsnam/ns/doc/

マニュアル日本語版：http://www.cool.giti.waseda.ac.jp/~onoder/onoder/ns-project.htm

チュートリアル：http://www.isi.edu/nsnam/ns/tutorial/index.html

（チュートリアルの日本語訳っぽいやつ）http://www.kensuke.org/ns/index.html

サンプル集：http://nile.wpi.edu/NS/

日本語ウェブページ

http://netlab.ce.nihon-u.ac.jp/~sue/

nsの学習ページ：

http://www.lares.dti.ne.jp/~wyama/craft/learning-ns2.html

ns2の使い方（基本的なところ）：http://www.cool.giti.waseda.ac.jp/~onoder/onoder/ns-tutorial.htm

2chｽﾚ

http://science4.2ch.net/test/read.cgi/sim/1039414330/l50

こんな本も出ているみたい（http://www.morikita.co.jp/mokuji/8462.html）

前書きなど：http://www.morikita.co.jp/mokuji/8462.html

とりあえずNS-2をFedoraに入れて動かしてみた．

無事にうごいた．

色々覚えることがあって大変そうだ・・・

無線AV伝送システムにおけるQoS制御技術

というタイトルの技術解説論文を読んでみた．

http://www.sharp.co.jp/corporate/rd/22/pdf/87-08.pdf

概要説明をします．

最初に無線ホームネットワークやら11eの概要説明やら．

AV伝送にはHCCAのほうが適しており，この論文ではHCCAについて記述．

QAPに存在するHC(Hybrid Coordinator)が送信時間の割り当てを一括管理．

QSTAは送信したいデータに要求される情報をTSPEC(Traffic SPECification)

というパラメータを用いて伝える．

QAPはQSTAの送信割り当て要求に対して　TSPECから受付判断（Admission Control）し，必要な送信時間・タイミングを計算*1→CF-Pollによる送信権（TXOP)の付与を行う．CF-Pollに記述された送信許可時間だけQSTAは送信可能．

また，QSTAは次に付与してほしいTXOP時間をQAPにフィードバックできる．

　この際，値をQSTAの送信するデータフレームに埋め込むことが可能

　また，TXOPがあまったらQAPへ返還

QAP→QSTA　の場合CF-Poll無しにデータフレームの送信をする．

QSTA→QSTA　の場合，次に付与してほしいTXOP時間はQoS null（QAP宛）

QAPは以下の要求を満たすように

送信許可時間のタイミングを計算

１　要求を受け入れたSTAにはTSPECに記されたデータに必要な最低限の送信時間を保証する

２　無線パスの変化によりパケットエラー率が増加する場合には１の時間割り当てでは不十分であり，そのSTAにはより多くの送信時間を割り当てる救済措置を取る．

３　この二つを満たした上で，多くのQSTAの要求を受け入れる．

これらの要求を満たすスケジューリングアルゴリズムは無数に存在．

具体的にはIEEE802.11eの仕様では規定されてなく，メーカーの実装依存．

特に２が重要．（仕様書レベルでは具体的に記述されていない）

・スケジューラアルゴリズム

　SHARPのこの論文では

　　ポーリング更新・作成機能を

　　ハードウェア処理　と　ソフトウェア処理　に分ける．

ソフトウェアによるTXOP計算では，ビーコン周期単位でポーリングリストを更新しているため，遅延発生時間が非常に長い．そのため，ポーリングリストが更新されるまではハードウェアによる応急措置を行うという方法．

リンクエラーによりTXOP要求が増えたQSTAに対して，ハードウェア処理でなるべく多くのTXOP間隔を割り当てる．

Beacon Intervalが終わった後，ソフトウェア処理部分でTXOP値が更新される．

*1：※どう計算しているのかについての記述はない

アクセス制御方式（詳細）

CSMA

http://www.katayama.nuee.nagoya-u.ac.jp/~okada/works/packet/node1.html

• 回線交換方式とパケット交換方式


• Pure (Unslotted) ALOHA方式

　送りたい人が勝手に送る

• Slotted ALOHA方式

　それじゃ困るからタイムスロットを割り当ててみた

　ガードインターバルを用いてある程度の遅延に対応

• CSMA方式

　それでも重複するんでキャリアセンスを導入

• 数値例

と，アクセス制御方式についての歴史的流れがわかる．

図と数式を使って説明されている．

http://www.ht.sfc.keio.ac.jp/mcng/arc/CSMA-CA/

• CSMA/CA

non-persistent CSMA方式

　CS→ビジー→CS中止→一定時間待→CSから

p-persistent CSMA方式

　CS→ビジー→CS→idle→フレーム送信

　送信の際,確率pでフレーム送信開始，確率1-pで送信を見送る．

1-persistent CSMA方式

　p-persistent CSMA方式のp=1の場合．

　IEEE 802.3 (CSMA/CD) の基礎となった方式である．

1-persistent CSMA方式 - 低トラフィック時

p-persistent CSMA方式 - 高トラフィック時

non-persistent CSMA方式 - 高トラフィック時

（参考文献：p72-73　無線LANとユビキタスネットワーク）

　予めステーション間に優先順位を設け，ビジー検出時の待ち時間をこの優先順位に応じて決定する．ステーションに番号(優先順位)iを割り当て，各優先順位iに応じた再送間隔時間Di (D1<D2<・・・<D_n)を定義する．ビジー検出時に割り当てられた優先順位Diだけ待ってからフレーム送信を試みる</ppp>

• CSMA/CAでのステーション動作例 (CSMA/CA with Ack)

１：CS→if(DIFSの間，アイドル)→送信

　　 　　　　　　ビジー　　→ 2 へ

２：アイドル→DIFS待ち→ランダムタイム待ち（バックオフタイム）→アイドル→送信

　　　　　　　　　　　　　　　　　　　　　　ビジー　→ 2 へ

３：Point to Point 通信の場合，宛先ステーションが直ちに(SIFS時間後)Ack信号を送信．

４：Point to Point 通信では，一定時間内にAckを受信しなければ，データを再送する．

フレームの種類によってIFSを定義

　SIFS(ACKなどに利用・最優先）

　PIFS（ポーリング用．PCFに利用）

　DIFS（分散制御用フレーム．DCFに利用．最低優先）

　EIFS(ExtendedIFS　チャネル使用状況ビジーかつフレームがエラーの場合に利用）

　　EIFS=SIFS+ACKフレーム長＋DIFS

上から順に時間が長くなる．

以上のような通信はDCF型と呼ばれる

隠れ端末問題の解決にはRTS/CTSが利用されるが，完全な解決はできていない．

• PCF方式

ポーリングによる集中制御

タイムチャートは

無線LANとユビキタスネットワークのp119図2-88

各STAに対して通信時間を割り当てることによる衝突回避．

DCFとPCFの共存

　CSMA/CAによる時間分離により，周期的な運用が可能　図2-89

・問題

周囲に同一チャネルを利用する無線セルが存在する場合，ポーリング信号の衝突が起こる　

CFP先頭のBeacon同士が衝突，CF-Pollも衝突→データが受け取れなくなる

・解決

IEEE802.11ではCFP先頭タイミングの決定アルゴリズムが規定されておらず

各ベンダーが独自に実装している．

アクセス制御方式

Dynamic TDMA

http://biz.ascii24.com/biz/column/trend/article/2001/02/17/print/623080.html

に少し記載されているが2001年の記事。03年に11eの方式がある程度

決められたことからも、やや古い内容。

http://202.23.184.254/dia/monthly/monthly03/20030502/22_ichikawa.pdf

03年5月

次世代無線LAN

～Dynamic TDMA 方式によるIEEE802.11e の新たな展開～

上の記事内容まんま。ｲﾐﾈｰ

http://infonet.cse.kyutech.ac.jp/paper/2002/Kaori-Chigusa-20030228-Bachelor.pdf

前半部分が知識のまとめになっている

http://www.atmarkit.co.jp/fnetwork/trend/20050511/01.html

無線LANスイッチ？？？11eでは結局負荷集中時には問題解決できないんだよなぁ。

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?tp=&arnumber=1321978&isnumber=29278

IEEEにある論文。会員じゃないと読めず

http://www-sop.inria.fr/mistral/personnel/Ahmad.Al_Hanbali/presentations/ns802_11.pdf

ns-2における無線LAN導入方法　from　Inria

ちなみに

Q:QualnetではIEEE802.11eはサポートされていますか？

A:QualNet Developer 3.9で標準ライブラリに含まれるようになります。

　それ以前のバージョンでは、802.11eはサポートしておりません。

とのこと

http://www.ee.kth.se/php/modules/publications/reports/2005/IR-SB-EX-0525.pdf

http://www.bettstetter.com/publications/carlson-2005-ew-dare.pdf

http://www.ee.surrey.ac.uk/Personal/G.Pavlou/Publications/Conference-papers/Siva-04a.pdf

http://www.sweegy.ch/references/qos/2003%2006%20Analysis%20of%20IEEE%20802.11e%20and%20application%20of%20game%20model%20for%20support%20QoS%20in%20coexisting%20wireless%20networks%20(These),%20S.Mangold.pdf　（すげー長い250ページくらい）

http://www.hamilton.ie/Qiang_Ni/papers/JWCMC_Qiang.pdf　（サーベイ論文）

http://team.iict.ch/LGE/IEEE-QoS-Survey.pdf　（サーベイ論文）

11eを扱っている英語論文

一番したのやつが結構参考になりそう

http://www.sanyo.co.jp/giho/no72/pdf/7210.pdf

Qos全般についてまとめた論文

• まとめ

中央集中制御端末や広範囲にわたる同期機能が備わっていないアドホックネットワークでは，TDMAのような割り当て方式が向いているとは思えない．また，モビリティを考慮すると，送信フレームのスケジューリングが上手くいかなくなると思われる．

そのため，分散して制御する必要がある．

ノードが固定である環境を想定すれば，優先制御を用いたチャネルのタイムスロット割り当てが上手くいく可能性がある．

他の端末がしゃべりたくなったときにどう黙らせるか，そして優先的なタイムスロット割り当てをするには何が最適かを考える必要がある．

簡単なミーティングがありました

下記の考えてきた話はいったん白紙．

アプリケーション側で帯域を減らすより，端末間でのパケット送受信タイミングを

あわせたり，他の端末を黙らせたりする方法をやることにした．

そっちのほうが根本的な解決にはなるんだけど…　正直なところ勝算が見えない．

具体的にはL2のアクセス制御で解決．IEEE802.11eで行われているQoS機能と

11eで行われているアクセス制御と通常のCSMA/CA ACKなどがどう違うか調査する必要．

とりあえず来週の水曜日までに調査結果とイケテル点，イケテナイ点をまとめて

どうしたらイケテル解決になるかを出さねば．

IEEE802.11e

「IEEE802.11e」

IEEE(米国電気電子学会)規格の一つ

既に定められている規格であるIEEE 802.11aやIEEE 802.11bをもとに、

ユーザ認証やアクセス制限の手段を提供するセキュリティ機能や、

動画等のマルチメディアデータの流通を意識した

サービス品質制御技術のQoS機能などを付け加えたもの．

物理レイヤーは11aや11gなどを利用

アクセス制御には　Dynamic TDMA*1方式

CSMA/CAはフレーム単位に早い者勝ちルール

　複数端末が同時に通信を始めると通信速度にばらつきが生じる

Dynamic TDMAは優先度に応じた送信権割り当て（TDMAによる）

QoSの実現には二種類の方式

EDCA（enhanced distributed channel access）

　フレーム送信までの待ち時間を調整

　優先度を4段階に分けて待ち時間を順番に短くする

　優先度が高いフレームが先に転送されるようにする．

４つのカテゴリ

　AC_BK（バックグランド・トラフィック用）

　AC_BE（ベスト・エフォート用）

　AC_VI（ビデオ伝送用）

　AC_VO（音声用）

優先制御のために使用されるパラメータ

　AIFS（Arbitration IFS、フレーム送信間隔）

　CW（Contention Window、コンテンション・ウィンドウ）

　TXOP（Transmission Oppotunity、排他的なチャネルの利用）

これらは送信頻度の決定に利用

アクセス・カテゴリごとに異なるパラメータを用いることで統計的な優先制御を実現

　利点　優先度が高いフレームは待ち時間が短くなる

　欠点　優先度が高いフレームが多いと効果は低い

結局CSMA/CAに優先度制御を付け加えただけっていう感じ

1台の端末内における優先度制御．

CSMA/CAでは複数端末間におけるCS後の送信時間に優先度を付けていた．

11eでは端末間の優先制御はDynamic TDMAに任せているようだ

<<参考ページ>>

http://sun.qee.jp/mtech/modules/xfsection/article.php?articleid=74

HCCA（hybrid coordination function controlled channel access）

　従来のIEEE802.11PCFを拡張したもの．

　PCFの問題点として2点あった

　・データ転送を開始するに当たって特別なビーコンを送信する必要がある

　・基地局と端末の間で具体的なパラメータの交渉手段が提供されていない

　これを解決する．

　APがCF(contention free)-Pollingにより優先度の高いフレームを

　送信する端末に対して送信時間を割り当てる．

　割り当てられた時間の間，他の端末に邪魔されずに資源を独占可能

　CSMA/CAを一時的に停止．1台づつ個別に帯域を割り当てる．

　トラフィックが増えても帯域の使用効率が落ちない（なぜ？）

詳細なシーケンスは

http://sun.qee.jp/mtech/modules/xfsection/article.php?articleid=76

3ページ目に詳しいポーリング制御が記載されている

http://www.sharp.co.jp/corporate/rd/22/pdf/87-08.pdf

オプション

http://www.atmarkit.co.jp/fnetwork/rensai/ieee04/02.html

• DLP （Direct Link Protocol）：　アクセスポイントを介さず、局（通信ノード）間で直接通信するための仕組み。DLPを設定した局間ではパワーセーブモードに入ることができない


• Block ACK：　複数のデータに対してACKを一括して返送する仕組み。データ送信側からのBlock ACK Requestパケット（ACK状況を返送してほしい先頭フレームのID情報を含む）に対し、データ受信側はBlock ACKパケットを返送する


• 上位層同期：　上位層が共有している時計の任意の精度での時報情報をマルチキャストフレームとして送受信するための仕組み


• APSD（Automatic Power Save Delivery）：　ビーコン単位より短い周期でパワーセーブを行う仕組み

などのオプション機能が利用可能となっている。

参考ページ

http://itpro.nikkeibp.co.jp/article/COLUMN/20060113/227248/　

http://times.ansl.ntt.co.jp/gijyutu/2005_02/Topic_02/04.html

http://sun.qee.jp/mtech/modules/xfsection/article.php?articleid=55

通常の無線LANアクセス制御方式であるCSMA/CAについて

http://sun.qee.jp/mtech/modules/xfsection/article.php?articleid=79

バックオフタイムのせいで大きな遅延が発生している．

*1：この方式について深く調べます

昨日までの話を整理．

背景

　室内環境でmanetによる監視カメラを構築する

　映像はメッシュネットワーク上で一定のフレームで転送される

問題

　特定の端末に複数フローが集中したときに，

　輻輳のために転送が出来なくなる問題がある．

　また，アプリケーション側では輻輳が起こっていると判断

　出来ないため，輻輳発生前と同じ転送レートで転送をし続けてしまう．

手法

　中継端末は自身の負荷を監視し，送信元に報告する．

　方法としては，一定間隔でHelloパケットに現在の負荷状況を

　埋め込む方法と,一定以上の負荷が集中した際に報告する方法の

　二つがある．前者の場合，一定間隔で全ての端末に対して

　中継端末の負荷状況がわかるため，新規フロー作成時の

　経路作成が容易に可能である．後者の場合は，

　負荷集中が発生する以前に送信元に対して伝えることが出来ないが

　新規フローが頻繁に発生しないような環境では使えるかもしれない．

　　また経路作成時に，既存の転送レートのままでは輻輳が発生する場合，

　新規フロー作成端末は，現在流れているフローの送信元に対して

　転送量削減の指令を出すことで，アプリケーション側での転送容量削減を測る．

見込

　実装はアプリケーション側とルーティング側で行う

　・負荷状況を監視し，helloパケットに埋め込む部分

　・負荷状況を考慮してルーティング経路を決定する部分

　・アプリケーションにデータ容量を下げさせるように命令する部分

　・アプリケーションでレートを下げる部分

状態遷移図

新規フロー作成端末側：処理の流れ

　　　　　　　　　　　　　　　　余裕がある→通常通信へ戻る

　　　　　　　　　　　　　　　　　　↑

　通常通信→（新規フロー発生）→＜負荷計測＞→余裕がない（集中状態）

　　　　　　　　　　　　　　　　　　　　　　　　　↓

　　　　　　　　　　　　　　　　転送量削減←送信元ノードにReply

考慮すべき点

　・負荷の計測

　・送信元ノードへの連絡方法

　・転送容量削減アルゴリズム

・負荷の計測

　本システムでは動画Flowは一定間隔，一定期間で流れ続けるモデルのため

　送信パケットごとに負荷分散を行う必要性は低い．

　通常の負荷計測方法としては，RTTとパケットロス率を用いた

　送信側でのトラフィック推定手法が多い（情報処理学会論文集2006Julyより）

　他の負荷分散手法について調査

　参考文献"マルチホップ無線LANにおける動的なトラヒック制御"

　P36　過去の送信量と現在の送信量を基に使用帯域を推定するTSW（Time Sliding Window)

　アルゴリズムというものがある．

　D.D. Clark and W. Fang : “Explicit Allocation of Best-effort Packet Delivery Service,”

IEEE/ACM Transactions on Networking, vol.6, no.4, August. 1998.(古いナー）

　一般的な負荷分散の話でそんなに役に立たない．

・送信元ノードへの連絡方法

　映像データはUDPで転送されるが，ReplyパケットはTCPが好ましい．

　負荷が集中している場合に迅速にTCPパケットが送信できるのか．

　送信を開始する前なのでReplyパケットの遅延はさほど問題ない？

・転送容量削減アルゴリズム

　アプリケーション側で容量削減（単純に送信データ総量を削減）するが

　どの程度削減するべきか，スループットとの兼ね合いを考慮して

　画像サイズ，フレーム数，転送間隔を何msにするか　などを決定．

流れ

数行でまとめてみる

背景

　室内環境でmanetによる監視カメラを構築する

　映像はメッシュネットワーク上で一定のフレームで転送される

問題

　特定の端末に複数フローが集中したときに，

　輻輳のために転送が出来なくなる問題がある．

　また，アプリケーション側では輻輳が起こっていると判断

　出来ないため，輻輳発生前と同じ転送レートで転送をし続けてしまう．

手法

　中継端末は自身の負荷を監視し，送信元に報告する．

　方法としては，一定間隔でHelloパケットに現在の負荷状況を

　埋め込む方法と,一定以上の負荷が集中した際に報告する方法の

　二つがある．前者の場合，一定間隔で全ての端末に対して

　中継端末の負荷状況がわかるため，新規フロー作成時の

　経路作成が容易に可能である．後者の場合は，

　負荷集中が発生する以前に送信元に対して伝えることが出来ないが

　新規フローが頻繁に発生しないような環境では使えるかもしれない．

　　また経路作成時に，既存の転送レートのままでは輻輳が発生する場合，

　新規フロー作成端末は，現在流れているフローの送信元に対して

　転送量削減の指令を出すことで，アプリケーション側での転送容量削減を測る．

見込

　実装はアプリケーション側とルーティング側で行う

　負荷状況を監視し，helloパケットに埋め込む部分

　負荷状況を考慮してルーティング経路を決定する部分

　アプリケーションにデータ容量を下げさせるよう命令する部分

　アプリケーションでレートを下げる部分

　想定トポロジが完全に固定の場合と

　有る程度フラットな場合で難易度が違う　固定のほうがやりやすい

　固定でまずは考えて，フラットへの拡張という方向で

今日はこの辺で帰ります

ちゃんとタグ付けしないとね．

明日の予定

13:30～M2　3人の中間発表

その後M1一人のミニプロジェクト発表

fixな予定はそんなもん．

とりあえず早起きして最初にやることは

負荷分散の論文を読むこと．

あと明日中にはシナリオ詳細をある程度かたちにして

S田さんに提出できるようにする．

複数インタフェースは本質ではなく，

あくまで補助的なものとしての研究になりそう．