Problém skrytých uzlů („hidden nodes“): Porovnání verzí

Z Wiki UnArt Slavičín
Skočit na navigaciSkočit na vyhledávání
 
(Není zobrazeno 6 mezilehlých verzí od 2 dalších uživatelů.)
Řádek 1: Řádek 1:
== Úvod ==
== Úvod (polopatický) ==
Tento problém je způsoben faktem, že návrh fyzických protokolů 802.11a/b/g (WiFi) byl veden hlavním předpokládaným způsobem využití bezdrátovým připojením uživatelů uvnitř budov na vzdálenost maximálně desítek metrů, jako doplněk k metalické síťové kabeláži. Typický příklad je připojení desítek notebooků účastníků konference v sále, kde by připojení pomocí kabelů bylo neekonomické, nepraktické a velmi těžko realizovatelné.
Tento problém je způsoben faktem, že návrh fyzických protokolů 802.11a/b/g (WiFi) byl veden hlavním předpokládaným způsobem využití bezdrátovým připojením uživatelů uvnitř budov na vzdálenost maximálně desítek metrů, jako doplněk k metalické síťové kabeláži. Typický příklad je připojení desítek notebooků účastníků konference v sále, kde by připojení pomocí kabelů bylo neekonomické, nepraktické a velmi těžko realizovatelné.
*Rozdíl mezi konferenčním sálem a WiFi sítí s externími anténami (na střechách) je ten, že wifi karty všech uživatelů v sále vzhledem k malé vzdálenosti a všesměrovým anténám vzájemně slyší své vysílání. Mohou tak reagovat na stav, kdy před vysíláním vlastních dat zjistí, že kanál je momentálně obsazen vysíláním jiného uživatele.  
*Rozdíl mezi konferenčním sálem a WiFi sítí s externími anténami (na střechách) je ten, že wifi karty všech uživatelů v sále vzhledem k malé vzdálenosti a všesměrovým anténám vzájemně slyší své vysílání. Mohou tak reagovat na stav, kdy před vysíláním vlastních dat zjistí, že kanál je momentálně obsazen vysíláním jiného uživatele.  
Řádek 6: Řádek 6:
*Omezení efektu skrytých uzlů je možné pouze dodržování minimálních vzdáleností uživatelů od přístupového bodu (do 100m) a použitím máloziskových antén s větším úhlem vyzařování, které zajistí, že se většina uživatelů bude vzájemně slyšet. Pokud takovouto konfiguraci nelze docílit, je ještě možné nastavit všem uživatelům daného přístupového bodu povinné používání mechanismu RTS/CTS, kdy každé zařízení musí před vysláním regulérního packetu poslat požadavek RTS („Request to send“) a čekat na odpověď přístupového bodu CTS („Clear to send“). Tento mechanismus omezuje kolize (Collision Avoidance, CSMA/CA), bohužel jej ale nelze zapnout centrálně, musí se nastavit u každého uživatele zvlášť parametrem „RTS Threshold“, který určuje velikost packetu, před jehož vysláním se má čekat na CTS. Nevýhody používání mechanismu RTS/CTS jsou následující:
*Omezení efektu skrytých uzlů je možné pouze dodržování minimálních vzdáleností uživatelů od přístupového bodu (do 100m) a použitím máloziskových antén s větším úhlem vyzařování, které zajistí, že se většina uživatelů bude vzájemně slyšet. Pokud takovouto konfiguraci nelze docílit, je ještě možné nastavit všem uživatelům daného přístupového bodu povinné používání mechanismu RTS/CTS, kdy každé zařízení musí před vysláním regulérního packetu poslat požadavek RTS („Request to send“) a čekat na odpověď přístupového bodu CTS („Clear to send“). Tento mechanismus omezuje kolize (Collision Avoidance, CSMA/CA), bohužel jej ale nelze zapnout centrálně, musí se nastavit u každého uživatele zvlášť parametrem „RTS Threshold“, který určuje velikost packetu, před jehož vysláním se má čekat na CTS. Nevýhody používání mechanismu RTS/CTS jsou následující:
** v případě bezdrátových karet vyžaduje znalé a zodpovědné uživatele, kteří jsou schopni nastavení RTS Threshold obnovit i v případě reinstalace operačního systému
** v případě bezdrátových karet vyžaduje znalé a zodpovědné uživatele, kteří jsou schopni nastavení RTS Threshold obnovit i v případě reinstalace operačního systému
** čekání na potvrzení CTS způsobuje nárust režie a tedy pokles propustnosti sítě
** ve srovnání s ideálním stavem - sítí s žádnými skrytými uzly - čekání na potvrzení CTS způsobuje pokles propustnosti sítě
** pokud bude většina uživatelů v síti používat RTS/CTS, pak uživatel, který tento mechanismus nemá nastaven, bude nad ostatními uživateli ve výhodě – bude schopen data přenášet rychleji a častěji
** pokud bude většina uživatelů v síti používat RTS/CTS, pak uživatel, který není skrytým uzlem a mechanismus RTS/CTS nemá nastaven, bude nad ostatními uživateli ve výhodě – bude schopen data přenášet o něco rychleji, protože nebude čekat na CTS. Defaultní nastavení RTS/CTS je totiž takové, že karta pro packety menší než "RTS Threshold" (defaultně 2000 bajtů) sice vyšle RTS, ale sami si ihned odpoví "Clear to send" a začne vysílat data.
** některé přístupové body (Mikrotik!!!!) tento mechanismus nepodporují nebo podporují chybně
** některé přístupové body (Mikrotik!!!!) tento mechanismus nepodporují nebo podporují chybně
== Chování sítě se skrytými uzly==
Skutečné chování sítí 802.11a/b/g, které obsahují skryté uzly, se velmi liší od zažitých představ.
V reálné síti tento problém nemáme možnost jakkoli měřit nebo detekovat, jediná možnost, jak si vyzkoušet chování takových sítí v závisloti na různých podmínkách, je simulace. Za tímto účelem jsem v roce 2006 vypsal diplomovou práci, jejímž cílem bylo vytvoření simulačního modelu sítí 802.11a/b/g a ověření chování těchto sítí v modu "AP s N klienty, z nichž několik jsou skryté uzly".
Tato práce dopadla nad očekávání dobře, technickou zprávu si [http://zamestnanci.fai.utb.cz/~dulik/diplomky/2006-2007/svitak2007.pdf můžete přečíst zde].
Výsledek simulačích experimentů:
#Skryté uzly škodí především samy sobě. Při plně zatížené síti nedokáže skrytý uzel přenést uploadem téměř žádná data
#Nasazení RTS/CTS v celé síti umožní skrytým uzlům přenášet data (byť pomaleji, než normální uzly). RTS/CTS ale sníží propustnost celé sítě, např. u 802.11b s 5ti klienty připojenými rychlostí 11Mbit/s klesne po zapnutí RTS/CTS přenosová rychlost ze 445kbit/s na 325-170kbits. Viz strana 41 uvedené práce.
Tato diplomová práce - vzhledem k časové náročnosti programování simulačního modelu - už ale neřeší závislost chování sítě se zapnutým RTS/CTS na hodnotě RTS Threshold. Na toto téma jsem ale našel následující článek:


== Chování sítě v závislosti na nastavení RTS Threshold ==
== Chování sítě v závislosti na nastavení RTS Threshold ==
Zatím nejlepší článek, popisující chování WiFi APčka v závislosti na provozu, počtu připojených lidí a nastavení RTS Threshold je k dispozici zde: http://www2.tku.edu.tw/~tkjse/6-1/6-1-8.pdf
Zatím jediný článek, popisující chování WiFi APčka v závislosti na nastavení RTS Threshold, na provozu a na počtu připojených lidí je k dispozici zde: http://www2.tku.edu.tw/~tkjse/6-1/6-1-8.pdf


Dovolím si vypůjčit a česky okomentovat několik obrázků z tohoto článku:
Dovolím si vypůjčit a česky okomentovat několik obrázků z tohoto článku:
Řádek 18: Řádek 30:
[[Soubor:Propustnost-vs-RT-Lambda.png]]
[[Soubor:Propustnost-vs-RT-Lambda.png]]


Figure 6: Tady vidíte, jak se chová propustnost AP s 25 klienty, kteří posílají packety o průměrné velikosti 1000 bajtů, v závislosti na RTS Threshold a míře zátěže λ, generované klienty.
Figure 6: Tady vidíte, jak se chová propustnost AP s 25 klienty, kteří posílají packety o průměrné velikosti 1000 bajtů, v závislosti na RTS Threshold a míře zátěže λ, generované klienty. Bohužel v práci není uvedeno, jaká část klientů (či jestli vůbec nějací) jsou skryté uzly.  
* Pro velmi nízkou zátěž λ=0.0001 je propustnost AP = 50% maximální reálné propustnosti, nastavení RTS Threshold nemá vůbec žádný vliv, protože nenastávají kolize
* Pro velmi nízkou zátěž λ=0.0001 je propustnost AP = 50% maximální reálné propustnosti, nastavení RTS Threshold nemá vůbec žádný vliv, protože nenastávají kolize
* Pro větší zátěž λ>=0.0002 ale už má nastavení RTS Thresholdu podstatný vliv na propustnost. Pokud necháte RTS Threshold v defaultní hodnotě (2000 bajtů), je propustnost pouze 48% maximální reálné propustnosti. Pokud nastavíte RTS Threshold na optimální hodnotu (např. 170 bajtů), dostanete propustnost až 75%!!
* Pro větší zátěž λ>=0.0002 ale už má nastavení RTS Thresholdu podstatný vliv na propustnost. Pokud necháte RTS Threshold v defaultní hodnotě (2000 bajtů), je propustnost pouze 48% maximální reálné propustnosti. Pokud nastavíte RTS Threshold na optimální hodnotu (např. 170 bajtů), dostanete propustnost až 75%!!
Řádek 51: Řádek 63:
* Pokud je RTS/CTS vypnut (tj. RT=nekonečno), pak od průměrné velikosti packetů = 1000 bajtů začnou kolize snižovat propustnost
* Pokud je RTS/CTS vypnut (tj. RT=nekonečno), pak od průměrné velikosti packetů = 1000 bajtů začnou kolize snižovat propustnost


==Řešení==
==Řešení skrytých uzlů v síti==
* Jak navrhují autoři těchto grafů (Fun Ye, Shiann-Tsong Sheu, Tobias Chen a Jenhui Chen), nastavení RTS Thresholdu na nízkou hodnotu (např. 175) prudce zlepší chování celé sítě
* Jak navrhují autoři těchto grafů (Fun Ye, Shiann-Tsong Sheu, Tobias Chen a Jenhui Chen), nastavení RTS Thresholdu na nízkou hodnotu (např. 175) prudce zlepší chování sítě
* Bohužel Mikrotik nepodporuje mechanismus RTS/CTS - pokud jej u klienta aktivujete, Mikrotik mu nikdy nepošle CTS, takže takový klient přestane vysílat.
* Bohužel Mikrotik nepodporuje mechanismus RTS/CTS - pokud jej u klienta aktivujete, Mikrotik mu nikdy nepošle CTS, takže takový klient přestane vysílat.
* Na Mikrotiku se tedy musíte smířit s tím, že s rostoucím počtem klientů bude dramaticky klesat propustnost uploadu - minimálně tak, jak to znázorňuje Figure 9. S tímto vědomím [[Probl%C3%A9m_s_velk%C3%BDm_pingem|musíte nastavit i Qosy v Mikrotiku (viz návod)]], aby klientům, kteří jsou skryté uzly, jela síť vůbec nějak.
* Na Mikrotiku se tedy musíte smířit s tím, že s rostoucím počtem klientů bude dramaticky klesat propustnost uploadu - minimálně tak, jak to znázorňuje Figure 9. S tímto vědomím [[Probl%C3%A9m_s_velk%C3%BDm_pingem|musíte nastavit i Qosy v Mikrotiku (viz návod)]], aby klientům, kteří jsou skryté uzly, jela síť vůbec nějak.
* Ideální řešení je místo Mikrotiku nasadit Linux, jehož Madwifi samozřejmě RTS/CTS podporuje. Návod na instalaci [http://wiki.hkfree.org/RouterboardRB500Linux Linuxu na RB532 je zde]
* Ideální řešení je místo Mikrotiku nasadit Linux, jehož Madwifi samozřejmě RTS/CTS podporuje. Návod na instalaci [http://wiki.hkfree.org/RouterboardRB500Linux Linuxu na RB532 je zde]

Aktuální verze z 28. 3. 2008, 00:43

Úvod (polopatický)

Tento problém je způsoben faktem, že návrh fyzických protokolů 802.11a/b/g (WiFi) byl veden hlavním předpokládaným způsobem využití bezdrátovým připojením uživatelů uvnitř budov na vzdálenost maximálně desítek metrů, jako doplněk k metalické síťové kabeláži. Typický příklad je připojení desítek notebooků účastníků konference v sále, kde by připojení pomocí kabelů bylo neekonomické, nepraktické a velmi těžko realizovatelné.

  • Rozdíl mezi konferenčním sálem a WiFi sítí s externími anténami (na střechách) je ten, že wifi karty všech uživatelů v sále vzhledem k malé vzdálenosti a všesměrovým anténám vzájemně slyší své vysílání. Mohou tak reagovat na stav, kdy před vysíláním vlastních dat zjistí, že kanál je momentálně obsazen vysíláním jiného uživatele.
  • Situace je ale naprosto odlišná v případě externích antén: důvodem je jejich větší směrovost a také členitý venkovní terén s mnoha překážkami (stromy, domy, …), kvůli čemuž se část klientů vzájemně neslyší. Uživatelům, jejichž vysílání je před ostatními uživateli skryto díky překážkám nebo díky velké směrovosti jejich antény, se říká „skryté uzly“.
  • V síti se skrytými uzly dochází s růstem počtu aktivních uživatelů k dramatickému nárustu kolizí při vysílání, kdy se v jednu chvíli snaží vysílat dva nebo více uživatelů, takže přístupový bod jejich vzájemnému „překřikování“ nemůže rozumět. Protože standard 802.11 je postaven na využití poloduplexních rádií, která mohou v daném okamžiku buď pouze přijímat, nebo pouze vysílat, není možná detekce kolizí již v průběhu přenosu (systémem CSMA/CD) jako u kabelového ethernetu. Kolize ve WiFi síti jsou proto pouze jedna z mnoha neidentifikovatelných příčin chyb při přenosu. Celkově se tento jev se projevuje ve chvílích velké zátěže sítě masivními ztrátami packetů u všech uživatelů přístupového bodu bez ohledu na kvalitu jejich signálu, přičemž nejvíce jsou postiženy právě skryté uzly. Z podstaty problému je také zasažen především upload.
  • Omezení efektu skrytých uzlů je možné pouze dodržování minimálních vzdáleností uživatelů od přístupového bodu (do 100m) a použitím máloziskových antén s větším úhlem vyzařování, které zajistí, že se většina uživatelů bude vzájemně slyšet. Pokud takovouto konfiguraci nelze docílit, je ještě možné nastavit všem uživatelům daného přístupového bodu povinné používání mechanismu RTS/CTS, kdy každé zařízení musí před vysláním regulérního packetu poslat požadavek RTS („Request to send“) a čekat na odpověď přístupového bodu CTS („Clear to send“). Tento mechanismus omezuje kolize (Collision Avoidance, CSMA/CA), bohužel jej ale nelze zapnout centrálně, musí se nastavit u každého uživatele zvlášť parametrem „RTS Threshold“, který určuje velikost packetu, před jehož vysláním se má čekat na CTS. Nevýhody používání mechanismu RTS/CTS jsou následující:
    • v případě bezdrátových karet vyžaduje znalé a zodpovědné uživatele, kteří jsou schopni nastavení RTS Threshold obnovit i v případě reinstalace operačního systému
    • ve srovnání s ideálním stavem - sítí s žádnými skrytými uzly - čekání na potvrzení CTS způsobuje pokles propustnosti sítě
    • pokud bude většina uživatelů v síti používat RTS/CTS, pak uživatel, který není skrytým uzlem a mechanismus RTS/CTS nemá nastaven, bude nad ostatními uživateli ve výhodě – bude schopen data přenášet o něco rychleji, protože nebude čekat na CTS. Defaultní nastavení RTS/CTS je totiž takové, že karta pro packety menší než "RTS Threshold" (defaultně 2000 bajtů) sice vyšle RTS, ale sami si ihned odpoví "Clear to send" a začne vysílat data.
    • některé přístupové body (Mikrotik!!!!) tento mechanismus nepodporují nebo podporují chybně

Chování sítě se skrytými uzly

Skutečné chování sítí 802.11a/b/g, které obsahují skryté uzly, se velmi liší od zažitých představ. V reálné síti tento problém nemáme možnost jakkoli měřit nebo detekovat, jediná možnost, jak si vyzkoušet chování takových sítí v závisloti na různých podmínkách, je simulace. Za tímto účelem jsem v roce 2006 vypsal diplomovou práci, jejímž cílem bylo vytvoření simulačního modelu sítí 802.11a/b/g a ověření chování těchto sítí v modu "AP s N klienty, z nichž několik jsou skryté uzly".

Tato práce dopadla nad očekávání dobře, technickou zprávu si můžete přečíst zde.

Výsledek simulačích experimentů:

  1. Skryté uzly škodí především samy sobě. Při plně zatížené síti nedokáže skrytý uzel přenést uploadem téměř žádná data
  2. Nasazení RTS/CTS v celé síti umožní skrytým uzlům přenášet data (byť pomaleji, než normální uzly). RTS/CTS ale sníží propustnost celé sítě, např. u 802.11b s 5ti klienty připojenými rychlostí 11Mbit/s klesne po zapnutí RTS/CTS přenosová rychlost ze 445kbit/s na 325-170kbits. Viz strana 41 uvedené práce.

Tato diplomová práce - vzhledem k časové náročnosti programování simulačního modelu - už ale neřeší závislost chování sítě se zapnutým RTS/CTS na hodnotě RTS Threshold. Na toto téma jsem ale našel následující článek:

Chování sítě v závislosti na nastavení RTS Threshold

Zatím jediný článek, popisující chování WiFi APčka v závislosti na nastavení RTS Threshold, na provozu a na počtu připojených lidí je k dispozici zde: http://www2.tku.edu.tw/~tkjse/6-1/6-1-8.pdf

Dovolím si vypůjčit a česky okomentovat několik obrázků z tohoto článku:

Závislost propustnosti na zatížení sítě a hodnotě RTS Threshold pro velké packety

Figure 6: Tady vidíte, jak se chová propustnost AP s 25 klienty, kteří posílají packety o průměrné velikosti 1000 bajtů, v závislosti na RTS Threshold a míře zátěže λ, generované klienty. Bohužel v práci není uvedeno, jaká část klientů (či jestli vůbec nějací) jsou skryté uzly.

  • Pro velmi nízkou zátěž λ=0.0001 je propustnost AP = 50% maximální reálné propustnosti, nastavení RTS Threshold nemá vůbec žádný vliv, protože nenastávají kolize
  • Pro větší zátěž λ>=0.0002 ale už má nastavení RTS Thresholdu podstatný vliv na propustnost. Pokud necháte RTS Threshold v defaultní hodnotě (2000 bajtů), je propustnost pouze 48% maximální reálné propustnosti. Pokud nastavíte RTS Threshold na optimální hodnotu (např. 170 bajtů), dostanete propustnost až 75%!!

Závislost propustnosti na počtu klientů a hodnotě RTS Threshold pro malé packety

Figure 7: Průměrná délka packetů = 150 bajtů, λ=0.001 (vysoké zatížení). Zde se můžete podívat, jak se bude APčko za těchto podmínek chovat pro různý počet klientů (N). Bohužel graf končí u RTS Threshold=1000, tj. abyste viděli, jak se to bude chovat pro defaultní RTS Threshold=2000 (tj. RTS/CTS vypnuto), musíte si graf dokreslit prstem :-)

  • Je vidět, že pokud je RTS Threshold nastaven na malou hodnotu (100-300), chová se AP i pro velký počet klientů (N=50) stále snesitelně - rozdíl propustnosti mezi 50ti a 15ti klienty je pouze 8% !!!
  • Naopak, pokud je RTS nastaveno na větší hodnoty (nebo na defaultní 2000), je degradace propustnosti tím větší, čím víc klientů je na AP připojeno. U 50ti klientů tak klesá až pod 10%...

Závislost propustnosti na počtu klientů a hodnotě RTS Threshold pro velké packety

Figure 8: Průměrná délka packetů = 1000 bajtů, λ=0.001 (vysoké zatížení). Tento obrázek nás bude zajímat víc než ten předchozí, protože za normálních podmínek (pokud zrovna na APčko neútočí nějaké viry) tvoří právě velké packety většinu provozu na APčku

  • opět je vidět, že pokud je RTS Threshold nastaven na malou hodnotu (100-300), chová se AP i pro velký počet klientů (N=50) stále snesitelně - rozdíl propustnosti mezi 50ti a 5ti klienty je pouze 8% !!!
  • Naopak, pokud je RTS nastaveno na velké hodnoty (nebo na defaultní 2000), je degradace propustnosti tím větší, čím víc klientů je na AP připojeno. Bohužel, na grafu opět chybí hodnoty RTS Threshold > 1000, takže výslednou hodnotu - kam to až spadne, pokud RTS Threshold není nastaven - můžeme jen odhadovat

Závislost propustnosti na délce packetů a hodnotě RTS Threshold pro velkou zátěž

Figure 9: Počet klientů N=25, λ=0.001 (vysoké zatížení).

  • Pro malé hodnoty RTS Thresholdu (0-175 bajtů) se závislost propustnosti na délce packetů chová podobně, jako u drátového ethernetu
  • Pokud je RTS/CTS vypnut (tj. RT=nekonečno), nejsme schopni překročit hranici propustnosti 30% při žádné velikosti packetů

Závislost propustnosti na délce packetů a hodnotě RTS Threshold pro velkou zátěž

Figure 10: Počet klientů N=25, λ=0.0001 (malé zatížení).

  • Pro malé hodnoty RTS Thresholdu (0-175 bajtů) se závislost propustnosti na délce packetů chová podobně, jako u drátového ethernetu
  • Pokud je RTS/CTS vypnut (tj. RT=nekonečno), pak od průměrné velikosti packetů = 1000 bajtů začnou kolize snižovat propustnost

Řešení skrytých uzlů v síti

  • Jak navrhují autoři těchto grafů (Fun Ye, Shiann-Tsong Sheu, Tobias Chen a Jenhui Chen), nastavení RTS Thresholdu na nízkou hodnotu (např. 175) prudce zlepší chování sítě
  • Bohužel Mikrotik nepodporuje mechanismus RTS/CTS - pokud jej u klienta aktivujete, Mikrotik mu nikdy nepošle CTS, takže takový klient přestane vysílat.
  • Na Mikrotiku se tedy musíte smířit s tím, že s rostoucím počtem klientů bude dramaticky klesat propustnost uploadu - minimálně tak, jak to znázorňuje Figure 9. S tímto vědomím musíte nastavit i Qosy v Mikrotiku (viz návod), aby klientům, kteří jsou skryté uzly, jela síť vůbec nějak.
  • Ideální řešení je místo Mikrotiku nasadit Linux, jehož Madwifi samozřejmě RTS/CTS podporuje. Návod na instalaci Linuxu na RB532 je zde