}w !"#$%&'()+,-./012345
Masarykova univerzita Fakulta informatiky
Vyvažování zátěže přístupových bodů bezdrátové sítě bakalářská práce
Václav Seidler
Brno, jaro 2012
Prohlášení Prohlašuji, že tato bakalářská práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj.
Václav Seidler
Vedoucí práce: doc. Eva Hladká, Ph.D. iii
Poděkování Rád bych poděkoval své vedoucí práce, doc. Evě Hladké, Ph.D. za trpělivost, kterou se mnou při vypracování práce měla a také za cenné rady. Dále děkuji své rodině a přítelkyni, kteří mě neúnavně podporovali a dodávali mi motivaci.
iv
Shrnutí Cílem této bakalářské práce je provést rešerši algoritmů, které vyvažující zátěž na bezdrátových přístupových bodech. Následně je popsat a na základě zvolených kritérií vybrat ten nejvhodnější a implementovat ho. V práci představíme protokol 802.11, pojem zátěže u vyvažování, nástroje pro měření efektivity daných algoritmů, konkrétní algoritmy a přístupy. Nakonec provedeme návrh a implementaci vybraného algoritmu, který vyvažuje zátěž na straně klienta.
v
Klíčová slova research, load balancing algorithms, client-driven load balancing, WiFi, 802.11, access point
vi
Obsah 1
2
Standard 802.11 . . . . . . . . . . . . . . . . . . . . . 1.1 Motivace . . . . . . . . . . . . . . . . . . . . . . 1.2 Vývoj standardu . . . . . . . . . . . . . . . . . . . 1.3 Architektura sítě . . . . . . . . . . . . . . . . . . 1.4 Druhy rámců . . . . . . . . . . . . . . . . . . . . 1.4.1 Datové rámce . . . . . . . . . . . . . . . 1.4.2 Management rámce . . . . . . . . . . . . 1.4.3 Řídící rámce . . . . . . . . . . . . . . . . 1.5 Přístupová metoda . . . . . . . . . . . . . . . . . 1.6 Asociace a roaming . . . . . . . . . . . . . . . . . 1.7 Problém skrytého uzlu . . . . . . . . . . . . . . . Vyvažování zátěže WLAN . . . . . . . . . . . . . . . 2.1 Problém vyvažování zátěže . . . . . . . . . . . . . 2.2 Definice zátěže . . . . . . . . . . . . . . . . . . . 2.2.1 Počet klientských stanic . . . . . . . . . 2.2.2 Využití kanálu . . . . . . . . . . . . . . 2.2.3 Počet přeposlání rámce . . . . . . . . . . 2.2.4 Další způsoby . . . . . . . . . . . . . . . 2.3 Měření efektivity vyvažování zátěže . . . . . . . . 2.3.1 Férovost . . . . . . . . . . . . . . . . . . 2.3.2 Propustnost . . . . . . . . . . . . . . . . 2.3.3 Specializované nástroje . . . . . . . . . 2.4 Existující řešení . . . . . . . . . . . . . . . . . . . 2.4.1 Vyvažování zátěže na straně klienta . . 2.4.2 Algoritmy vyvažování na straně klienta 2.4.3 Vyvažování zátěže na straně sítě . . . . 2.4.4 Cell breathing . . . . . . . . . . . . . . . 2.4.5 Admission control . . . . . . . . . . . . 2.4.6 Plánování frekvencí . . . . . . . . . . . . 2.4.7 Další přístupy . . . . . . . . . . . . . . . 2.5 Vybraný algoritmus . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 2 4 5 6 6 7 7 9 11 13 13 14 14 15 15 16 16 16 17 17 18 18 19 20 20 21 23 23 24
vii
1 Standard 802.11 1.1 Motivace Díky nízké ceně přístupových bodů (Access Point, AP) a bezdrátových síťových karet se technologie Wi-Fi (IEEE 802.11) stala dostupná téměř pro každého po celém světě. Vzniká tak rozsáhlá Wi-Fi džungle, což je stav, kdy v jedné oblasti můžeme zachytit dostatečně silný signál od dvou či více přístupových bodů. K oblíbenosti Wi-Fi také přispěla poměrně vysoká přenosová rychlost (bit rate), nejvíce znatelná s přijetím dodatku 802.11n. Na veřejných prostranstvích vznikají takzvané Hotspot zóny, kde se lze bezplatně připojit k internetu, jako je například knihovna, letiště nebo restaurace. Jako příklad Hotspot zóny můžeme uvést město Tchaj-pej (Taipei), kde byl v roce 2005 uskutečněn projekt Mobile-City. Ten měl za cíl pokrýt většinu města bezdrátovým 802.11 signálem. Pokryto bylo 272 km2 více než 10 000 přístupovými body [1, 2]. Takto pokrytých měst je po světě celá řada a jistě budou přibývat další. Několik studií ukázalo, že se lidé rádi sdružují na stejných místech ve stejný čas, tudíž vytvářejí velkou zátěž pro AP v Hotspot zónách. Když je bezdrátový přístupový bod příliš zatížený, jednoduchým řešením může být přidání nového AP a teoretického rozložení zátěže mezi tyto AP. Jelikož si ale klientské stanice volí AP podle svých kritérií, nemusí se k novému AP připojit a tím tedy pomoci k rozložení zátěže. Pokud je k přístupovému bodu připojeno více stanic, pravděpodobnost výskytu kolizí se zvětšuje, stejně jako počet chyb v přenose a přístupový bod zahazuje pakety, které má v přenosové frontě. Proto se vědci zabývají řešením problému vyvažování zátěže. Hlavní cíl je tedy optimalizovat zátěž na přístupových bodech a tím zvýšit celkovou propustnost sítě. Bylo již navrženo několik metod vyvažování zátěže, každá z nich ale trpí určitými nedostatky, které se při nasazování do provozu musí vzít v potaz. Problém vyvážení zátěže si můžeme rozdělit na dva podproblémy: ∙
jak definovat zátěž AP a následně ji měřit,
∙
jak tuto zátěž vyvažovat. Dále si můžeme rozdělit celý systém podle toho, kdo vykonává 1
1. Standard 802.11 administraci vyvažování a následné vyvážení klientských stanic. Buď jsou tím zatíženy přístupové body, nebo jednotlivé klientské stanice. Dalším kritériem pro nás bude změna standardu 802.11. Pokud budeme provádět určité změny ve standardu, nebudeme moct použít zařízení tak jak ho koupíme, ale budeme muset zařízení (AP nebo klientskou stanici) opatřit novým programovým vybavením.
1.2 Vývoj standardu Standard 802.11 patří do rodiny standardů IEEE 802, které popisují technologie použité pro lokální sítě (LAN, Local Area Network). V rámci ISO/OSI modelu se tento protokol, jako i většina protokolů z celé IEEE rodiny, nachází na první a druhé vrstvě. Tedy fyzické (L1) a spojové (L2) vrstvě. Fyzická vrstva se dělí na dvě podvrstvy, na vyšší PLCP (Physical Layer Convergence Procedure) a nižší PMD (Physical Medium Dependent) [3]. PLCP přidává k rámci z vyšších vrstev hlavičku a funguje jako spojení mezi MAC z L2 a L1 vrstvou. PMD je odpovědná za odeslání bitů, které dostane od PLCP, pomocí antény. Spojová vrstva obsahuje dvě podvrstvy, vyšší LLC (Logical Link Control) a spodní MAC (Medium Access Control). LLC je definováno standardem 802.2 jako běžná spojová vrstva, která může být použita jakoukoliv LAN technologií pracující na nižších vrstvách ISO/OSI modelu [3]. MAC podvrstva definuje několik pravidel, jak přistupovat k médiu a posílat data (viz 1.5. Podvrstva LLC se nepovažuje za část 802.11 standardu [4]. Do konce léta roku 1997 nebyl dosud žádný standard pro lokální bezdrátovou síť (Wireless LAN, WLAN), který by se používal v širším měřítku a byl všemi respektován. Každý výrobce si sám definoval protokol a signalizaci pro své zařízení a tyto proprietární řešení spolu nespolupracovaly [5]. Proto v roce 1990 Institut pro elektrotechnické a elektronické inženýrství (IEEE, Institute of Electrical and Electronics Engineers) vytvořil pracovní skupinu, která nesla název 802.11. Ta měla (a stále má) za úkol standardizovat protokoly a signalizaci pro WLAN. Tak se také během léta 1997 stalo, standard 802.11 byl přijat výborem IEEE a dostal pojmenování 802.11-1997. IEEE je nezisková organizace se sídlem v městě New York, která sdružuje inženýry z celého světa a usiluje o vzestup technologie související s elek2
1. Standard 802.11 trotechnikou. Mezi nejznámější standardy této organizace patří IEEE 802.3 Ethernet a IEEE 802.11 WiFi. Protokol 802.11-1997 používá 2 druhy modulace a to přímého rozprostřeného spektra (DSSS) a přeskakování frekvencí rozprostřeného spektra (FHSS). Pracuje na frekvenci 2.4 Ghz, které se nazývá ISM pásmo (Industrial, Scientific, Medical), a pro vysílání není potřeba vlastnit licenci. Byly zde definovány dvě přenosové rychlosti - 1 a 2 Mb/s. I kvůli ne příliš vysokým rychlostem a špatné implementovatelnosti byly v roce 1999 schváleny dva dodatky. Prvním z nich byl dodatek 802.11b, který rozšířil původní modulaci DSSS o modulaci CCK. Tím dosáhl rychlosti až 11 Mb/s. Tento dodatek prakticky nahradil původní standard 802.11 a docházelo ke značnému rozdílu v počtu implementovaných sítí 802.11b oproti původnímu 802.11. Po vydání tohoto dodatku již byla WLAN značně rozšířená a bylo mnoho dostupných zařízení, které spolu dokázala spolupracovat. Druhým z dodatků byl 802.11a, který pracuje na frekvenci 5 Ghz. Ta se liší fyzikálními vlastnostmi vůči 2.4 Ghz například tím, že signál na vyšší frekvenci je snadněji pohlcován zdí. Byla zde zavedena modulace ortogonálního frekvenčního multiplexu (OFDM), která dosahuje maximální teoretické rychlosti až 54 Mb/s. V červnu 2003 byl ratifikován dodatek 802.11g, který pracuje ve frekvenčním pásmu 2.4 Ghz. Použité jsou modulační techniky DSSS a OFDM. 802.11g může operovat maximální rychlostí 54 Mb/s a je zpětně plně kompatibilní s 802.11b. Tím však přinesl i možné zpomalení sítě, pokud s přístupovým bodem, který pracuje nad protokolem 802.11g, komunikuje zařízení se starším protokolem 802.11b. V roce 2007 byl vydán standard 802.11-2007, který spojil všechny dosud vydané dodatky do jednoho dokumentu. Dalším takovým dokumentem bude standard 802.11-2011, který se plánuje ratifikovat do prosince 2011. Roku 2008 byl přijat dodatek 802.11k, který definuje služby vysílacího měření (radio measurement services). Přidává nové vysílací měření a statistiky pro podporované kanály, žádosti a zprávy rádiového měření přes vysílací rozhraní a rozhraní pro přístup vyšších vrstev k vysílacím měřením skrz objekty MIB nebo jednoduché služby [6]. Přestože byl tento protokol ratifikován již v roce 2008, stále se neobjevily vědecké práce, které by těchto nových mechanismů prakticky 3
1. Standard 802.11 využívaly. Tento dodatek pomohl WLAN, aby se dynamicky adaptovala na své okolí. Další dodatek upravující přenosovou rychlost je z roku 2009 a nese název 802.11n. Je zde použitá modulace OFDM a pomocí více MIMO (Multiple-Input Multiple-Output) proudů lze dosáhnout rychlosti až 650 Mb/s. Pomocí 3 režimů přenosu se docílilo jak zpětné kompatibility se zařízeními pracujícími s dodatky a/b/g, tak i rychlejším rychlostem pro komunikaci zařízení pouze s 802.11n.
1.3 Architektura sítě Každé zařízení, které je vybaveno potřebným technickým a programovým vybavením pro bezdrátovou komunikaci se nazývá bezdrátová stanice (Station, STA). Ty pak můžeme dále rozdělit podle toho, jakou funkci v dané síti vykonávají: ∙
Klientská stanice (Client Station, CS) - zařízení, které se připojuje k přístupovému bodu za cílem používání sítě, většinou Internetu. Každá klientská stanice může být připojena pouze k jednomu přístupovému bodu v daný okamžik.
∙
Přístupový bod (Access Point, AP) - nebo také bázová stanice (Base Station), je zařízení, které umožňuje připojení klientských stanic k síti. Platí, že v jednom okamžiku může být k AP připojena více než jedna CS.
Další rozdělení je založeno na tom, jestli je provoz řízen centrálním prvkem na síť: ∙
Ad hoc - v této síti se nevyskytuje žádný řídící prvek a jedná se tak o decentralizovanou síť, kde klientská stanice komunikuje přímo s jinou klientskou stanicí bez přítomnosti AP. Tento druh sítě většinou vzniká spontánně pro určitou příležitost a je dočasný. Některá ze stanic může být dokonce připojena k jiné síti a sdílet tak své připojení mezi ostatní [5].
∙
Infrastrukturní - nejčastější typ sítě, klientské stanice se rozhodují, ke kterému AP se připojí. Dále CS komunikují pouze s vybraným přístupovým bodem. V této práci se budeme zabývat 4
1. Standard 802.11 infrastrukturní sítí, pokud budeme mít na mysli jiný typ sítě, pak to výslovně uvedeme. Základním stavebním kamenem WLAN je základní obsluhová sestava (Basic Servic Set, BSS), která se skládá z jednoho AP a alespoň jedné klientské stanice. Ty spolu soupeří o přístup ke sdílenému bezdrátovému médiu. Každé AP periodicky vysílá do svého okolí tzv. Beacon rámce, ve kterých informuje okolí o svém stavu a parametrech. CS tyto informace sbírají a na jejich základě se rozhodují, ke kterému AP se připojí. Pokud mluvíme o ad hoc síti, potom se jedná o nezávislou BSS (Independent BSS, IBSS) Protože má každý AP jen omezený dosah vysílání, který je dán typem antény, množstvím vyzářené energie a fyzikálními podmínkami okolí, je často nutné pokrýt rozlehlejší prostory více přístupovými body. Pokud se tyto AP chovají jako jedna ucelená síť, potom mluvíme o rozšířené obsluhové sestavě (Extended Service Set, ESS). Jedná se tedy o skupinu BSS propojenou distribučním systémem, což může být Ethernet či Wi-Fi. Jedním z údajů, které AP vysílají v Beacon rámcích je identifikátor obsluhové sestavy (Service Set Identifier, SSID), což je vlastně název sítě daného AP. K tomu, aby se několik BSS mohlo tvářit jako jeden velký celek, musí všechny AP vysílat stejné SSID. Jednotlivé AP potom můžeme rozlišit podle různých identifikátorů BSS (BSSID), které jsou shodné s hodnotou MAC adresy. K tomu, aby mohla klientská stanice komunikovat s přístupovým bodem a posílat přes něj svá data, musí se vůči AP autentizovat a asociovat. Podle druhu zabezpečení AP se odvíjí počet kroků nutných k autentizaci, kde CS sděluje AP své údaje. V otevřeném (nešifrovaném) režimu zabezpečení stačí výměna 2 Authentication rámců, v šifrovaném spojení už jsou to 4 a více rámců. V asociační fázi se vyjednají parametry připojení, např. podporované rychlosti, a také dostupnost síťových prostředků AP pro obsluhu CS. Teprve když CS projde kladně těmito dvěma fázemi, pak lze s přístupovým bodem plnohodnotně komunikovat.
1.4 Druhy rámců Hlavním cílem WLAN je přenášet data. K tomu, abychom vůbec mohli data přes přístupový bod posílat, tak se s ním musíme nejdříve spo5
1. Standard 802.11 jit, dohodnout a udržovat spojení. Právě k tomu slouží management rámce. Další skupinou jsou řídící rámce, které usnadňují přenos mezi bezdrátovými stanicemi [7]. Uvádíme jen některé velmi časté rámce. Pro vyčerpávající přehled odkazujeme na standard [8]. 1.4.1 Datové rámce V datových rámcích jsou zapouzdřena data vyšších vrstev referenčního ISO/OSI modelu. Většinou některého z protokolů aplikační vrstvy, tedy dat, které chceme reaálně přenést. Datový rámec může například obsahovat poslaný email či SSH komunikaci. 1.4.2 Management rámce ∙
Beacon - přístupový bod tento rámec pravidelně vysílá do okolí, aby sdělil svou přítomnost a další údaje, jako např. SSID, podporované rychlosti nebo časové razítko. To slouží CS k synchronizaci času s AP. CS postupně poslouchají na všech kanálech, aby zachytily tento rámec a zmapovali tak své okolí,
∙
Authentication/Deauthentication - CS v tomto rámci posílá AP své údaje k autentizaci a na jejich základě je buď přijata nebo odmítnuta k asociaci, v případě poslání deautentizačního rámce CS ukončuje autentizační či asociační spojení s AP,
∙
Probe request - klientská stanice tímto rámcem zjišťuje přítomnost přístupových bodů v okolí. CS se může dotazovat jednotlivých AP nebo nastavit hodnotu BSSID na samé jedničky a tím pádem poslat broadcast rámec,
∙
Probe response - slouží k odpovědi AP na Probe request klientské stanice. Obsahuje podobné informace jako v Beacon rámci, ale také některé dodatečné věci vyžádané CS v Probe request,
∙
Association request/response - tyto dva rámce slouží k vyjednání přenosové rychlosti spojení a případné rezervaci paměti, pokud se AP rozhodne CS přijmout,
∙
Reassociation request/response - pokud se klientská stanice rozhodne změnit přístupový bod, zašle novému AP Reassociation 6
1. Standard 802.11 request a ten mu odpoví Reassociation response rámcem s odpovědí a vyjednanými parametry. Pokud se CS nachází v ESS síti a migruje (roam) z jedné BSS buňky do druhé, pak nový AP zažádá původní o nedoručené rámce pro CS, ∙
Disassociation - slouží k zrušení asociace mezi AP a CS.
1.4.3 Řídící rámce Rámce RTS a CTS se používají k řešení problému skrytého uzlu, který je zmíněn v kapitole 1.7 na straně 11. Použití rezervačního RTS/CTS schématu je ve WLAN volitelné. ∙
Request to Send (RTS) - pro rezervaci kanálu na určitou dobu pošle CS přístupovému bodu RTS rámec s celkovým časem potřebným k přenosu datového a Ack rámce,
∙
Clear to Send (CTS) - po přijetí RTS přístupový bod odpovídá broadcastovaným CTS rámcem, ve kterém rezervuje kanál konkrétnímu CS a všem ostatním sděluje, že mají odložit vlastní vysílaní o předepsaný čas,
∙
Acknowledgement (Ack) - jestliže AP přijme v pořádku datový rámec poslaný CS, posílá jí potvrzovací (Ack) rámec, jinak neposílá nic. CS po vyslání čeká, jestli obdrží Ack rámec, pokud ano, je vše v pořádku. Jinak se pokusí znovu poslat datový rámec.
1.5 Přístupová metoda Protokol 802.11 používá podobnou přístupovou metodu jako 802.3 Ethernet, nazvanou CSMA/CA (Carrier Sense Multiple Access/Colision Avoidance). Ta se od Ethernetové metody CSMA/CD (Collision Detection) liší v několika bodech. Obě metody přistupují ke sdílenému médiu, u WLAN je to vzduch, voda a vakuum oproti voděnému a optickému médiu u Ethernetu. Princip CSMA říká, že předtím, než stanice začne vysílat, musí zkontrolovat, jestli je médium volné. V přístupové metodě detekce kolizí (CSMA/CD) začne stanice vysílat hned co zjistí, že je médium volné, jinak čeká určitý krátký čas a proces se 7
1. Standard 802.11 opakuje. V případě kolize se vysílaní přeruší a poté se začne od začátku. U WLAN se ale metoda CD nedá použít ze dvou důvodů. Aby stanice byla schopná detekovat kolizi, musela by v průběhu svého vysílání kontrolovat, jestli nevysílal někdo jiný. Síla přijímaného signálu je oproti vysílanému velmi slabá, a proto by bylo velmi nákladné vyrábět zařízení, které by bylo schopné detekovat kolize na sdíleném médiu. Další důvod je ten, že i kdyby stanice dokázala vysílat a přijímat zároveň, nebyla by schopna detekovat všechny kolize, a to kvůli problému skrytého uzlu a útlumu na médiu [9]. Z těchto důvodů byla zvolena metoda CSMA/CA, která používá přístupovou metodu zvanou distribuovaná koordinační funkce (DCF, Distributed Coordination Function) 1 . Kvůli vysoké míře bitových chyb v přenosu, a tím pádem nutného přeposlání rámce se používá schéma potvrzení/přeposlání (ARQ) na vrstvě datového spoje [9]. To znamená, že kdykoliv stanice přijme korektní rámec, pošle odesílatelovi potvrzení (Ack), že byl přenos úspěšný. Pokud odesílatel nedostane Ack, snaží se odeslat znovu stejný rámec. Protože standard 802.11 nepoužívá detekování kolizí, pokud stanice začne vysílat rámec, musí ho přenést celý. Pro správné fungování potvrzovacího schématu a vůbec celé metody DCF, musely být definovány mezirámcové mezery (IFS, Interframe Space). Ty určují, jak dlouho má stanice čekat před vysláním určitého rámce. Každý dodatek standardu rozděluje časové úseky (time slots) média na různě velké části, např. u 802.11b je Slot time 20 𝜇s a SIFS 10 𝜇s [8]. Z nich se následné odvodí dané IFS, např. 𝐷𝐼𝐹 𝑆 = 𝑆𝐼𝐹 𝑆 + (2 * 𝑆𝑙𝑜𝑡𝑇 𝑖𝑚𝑒). Standard definuje několik IFS, nebudeme však zmiňovat všechny: ∙
SIFS - krátká mezirámcová mezera (Short IFS) se používá pro okamžitou odpověď. Stanice, která musí poslat rámec potvrzení (Ack) nebo Clear to Send (CTS), čeká kratší dobu než DIFS. Tudíž se tyto rámce, které musí být odeslány co nejdříve, s největší pravděpodobností pošlou jako první,
∙
DIFS - mezirámcová mezera DCF (DCF IFS) je druhá nejdelší IFS, která se používá pro Request to Send (RTS), management a
1. Standard definuje i metodu PCF (Point Coordination Function), která funguje na principu vyzývání. V této práci se jí však věnovat nebudeme.
8
1. Standard 802.11 datové rámce, ∙
RIFS - redukovaná IFS (Reduced IFS) je velmi krátká IFS a v některých případech nahrazuje SIFS. Byla definována v dodatku 802.11n.
Přístupová metoda DCF dále definuje jak přistupovat k médiu. Stanice, která má rámec k vyslání, nejprve zkontroluje médium. Pokud je volné, počká danou mezirámcovou mezeru a poté zkusí, jestli je médium opět volné. Jestli ano, pak stanice přenese svůj rámec. Pokud v jednom z případů médium nebylo volné, tak stanice čeká a kontroluje médium, dokud dané vysílání neskončí. Jakmile stanice zjistí, že je médium volné, počká danou IFS a opět zkontroluje, jestli je médium volné. Pokud není, tak se vrací do stavu, kde čeká dokud vysílání neskončí. Když médium bylo volné, pak stanice vyčká náhodný čas (vypočítaný metodou Exponential Backoff) a během něj kontroluje médium. Pokud je médium po celou dobu volné, stanice smí vyslat svůj rámec. Když nebylo volné, zastaví odpočítávání náhodného času a kontroluje médium. Teprve když je volné, může odpočítávání pokračovat. Náhodný čas se vypočítá z proměnné contention window (CW) jako interval 0 až CW [10]. Celý proces znázorňuje obrázek 1.1 z [11].
1.6 Asociace a roaming Každá klientská stanice může být připojena k právě jednomu přístupovému bodu. Který to bude, o tom rozhoduje CS podle jediného parametru, a tím je RSSI (Receive Signal Strength Indicator). Ten vyjadřuje relativní energii, s jakou byl přijat rámec vyslaný daným přístupovým bodem. Každý výrobce bezdrátové síťové karty (WNIC) si definuje, jak dané RSSI vypočítá. Nejprve se vstupní signál, který se na straně CS měří v miliwattech (mW), převede do logaritmické hodnoty decibel (dBm), zde vztaženou k mW. Důvodem je lehčí manipulovatelnost s hodnotami v dBm než mW [12]. Poté se podle algoritmu, který má každý výrobce jiný, převede dBm na RSSI. Tento krok se pro každého výrobce WNIC liší a nemůžeme tedy porovnávat jednotlivé RSSI různých výrobců. 9
1. Standard 802.11
Obrázek 1.1: Přístupová metoda DCF
Pokud CS není asociovaná s žádným AP, tak může buď pasivně poslouchat bezdrátové médium a přijímat Beacon rámce všech přístupových bodů v jejím okolí, nebo může jednat aktivně a dotazovat se jednotlivých přístupových bodů pomocí Probe request rámce. Jakmile má CS informace o svém okolí, může se začít asociovat s AP. Pokud se v okolí nachází více přístupových bodů, které vysílají stejné SSID, klientská stanice si vybere vždy ten bod, který má nejvyšší hodnotu RSSI. Když si CS vybrala AP ke spojení, pošle mu Authentication request rámec. Přístupový bod odpovídá Authentication response rámcem a v případě shody odpoví klientská stanice Association request rámcem. Jestliže CS dostane kladnou odpověď od přístupového bodu v Association response rámci, pak je vytvořeno spojení mezi CS a AP. 10
1. Standard 802.11 Roaming je přechod z jedné BSS buňky do druhé v rámci stejné ESS. Přístupový bod každé BSS má jen omezený vysílací dosah a pokud se uživatel pohybuje v prostoru, může se stát, že se dostane mimo dosah vysílání daného AP. Další důvod může být ten, že se kvalita signálu od daného AP zhorší a vysílání se musí opakovat kvůli přibývajícím chybám v přenosu. Pokud se v daném místě nachází AP, které patří do stejné ESS, může se CS rozhodnout změnit AP. Jestliže je uživatel neustále v pohybu, pak je roaming nezbytný. Cílem roamingu je jako u GSM sítě pro uživatele transparentní přechod mezi jednotlivými BSS celky. WLAN roaming můžeme rozdělit na dva typy, a to roaming na spojové (L2) a síťové vrstvě (L3) ISO/OSI modelu. Roaming spočívá v předání klientské stanice jednoho přístupového bodu druhému, v literatuře se používá pojem handoff. Celé L2 schéma předání se dá rozdělit do tří fází: skenování, autentizace a reasociace. V první fázi CS buď aktivně nebo pasivně sleduje RSSI a kvalitu linky AP. V druhé fázi si CS vyměňuje autentizační zprávy s vybraným AP a v třetí fázi, pokud AP autentizuje CS, se spojení přesouvá ze starého na nový přístupový bod. Celkové zpoždění předání je součet zpoždění skenování (probe delay), autentizace a reasociace. Největším z nich je skenování [13]. Pokud by nové AP, ke kterému se CS chtělo připojit, bylo v jiné podsíti než je původní AP, pak se jedná o L3 roaming na síťové vrstvě. Schéma předání je stejné jako u L2, ale jako poslední krok navíc se použije protokol Mobile IP, který nepřeruší komunikaci internetových aplikací [14].
1.7 Problém skrytého uzlu Problém skrytého uzlu nastává, pokud máme dvě klientské stanice, které jsou připojené ke stejnému přístupovému bodu, ale každá z nich je mimo dosah vysílání opačné stanice (obrázek 1.2). Jestliže stanice A začne vysílat rámec AP, ale stanice B již vysílá, potom nastane kolize. Obě stanice se podle přístupové metody domnívaly, že je bezdrátové médium volné, a tudíž mohou bez problémů vysílat. Rozšíření metody CSMA/CA o volitelný mechanismus RTS/CTS pomáhá tento problém řešit. Myšlenka RTS/CTS je založena na tom, 11
1. Standard 802.11
AP
A
B
Obrázek 1.2: Problém skrytého uzlu že všechny CS v dosahu AP uslyší CTS rámec broadcastovaný přístupovým bodem a následně odloží svoje vysílání. Hlavní nevýhoda mechanismu RTS/CTS je jeho samotná režie, a proto se podle [15] v praxi typicky nepoužívá. Navzdory tomu, že standard 802.11 tuto metodu doporučuje používat jen pro přenos velkých rámců, nespecifikuje žádnou přesnou prahovou hodnotu (threshold). Její stanovení je potom na producentech WNIC či dokonce samotných uživatelích [16]. Kromě problému skrytého uzlu mohou vlastnosti sítě negativně ovlivňovat i další zařízení, například bezdrátové telefony, Bluetooth zařízení nebo mikrovlnné trouby (obzvláště staré) [11]. Tato zařízení mohou využívat ISM pásmo na stejných frekvencích jako naše zařízení, ale nemusí být navzájem kompatibilní. Tím myslíme, že tyto přístroje musí ze zákona splňovat pouze to, aby výkon vysílání nepřesáhl určitou mez [3], ale nikde není specifikován např. přístup k médiu či modulační techniky vysílání. U mikrovlnných trub, kde je prostor pro vysílání řádně oddělen, se nemusíme obávat příliš velkého rušení okolí. Opačný případ může nastat například u bezdrátových telefonů, které svým rušením mohou způsobit dokonce i nefunkčnost 802.11 sítě.
12
2 Vyvažování zátěže WLAN Tato kapitola se bude zabývat popisem algoritmů, které se snaží vyvažovat zátěž na přístupových bodech. Nejdříve se však pokusíme popsat problém vyvažování, definici zátěže a efektivity vyvažování.
2.1 Problém vyvažování zátěže Kvůli stále rostoucí oblíbenosti Wi-Fi sítí se vytvářejí nové metody, jak tyto sítě udělat více efektivní. Pokud je k přístupovému bodu připojeno více klientských stanic, začnou se objevovat problémy jako zahlcení sítě, větší ztrátovost paketů či snížená propustnost sítě. Tím pádem dojde k neefektivnímu používání bezdrátového média a může dojít až ke zhroucení sítě. Proto je potřeba hledat nové způsoby, jaké kritéria mají CS použít pro připojení k AP nebo jak se má přístupový bod vypořádat se zahlcením. Práce [17] definuje optimalizační problém, jehož cílem je minimalizovat rozptyl zátěže přístupových bodů, jako NP úplný. Nelze tedy nalézt optimální řešení, ale použitím různých heuristických metod nalézáme pouze přibližné řešení. U Wi-Fi sítí se jedná o asociační problém, tedy jak co nejlépe asociovat CS s AP tak, aby výsledné přiřazení bylo co nejefektivnější ve smyslu propustnosti, férovosti (fairness) a dalších kritérií. Podle [18] se v algoritmech na vyvažování zátěže musí brát ohled na férovost. Pokud budeme chtít pouze zvýšit celkovou propustnost sítě, může se stát, že některé klientské stanice dále od AP tzv. vyhladoví a přestanou přenášet data. Tím se celková propustnost sítě zvýší, ale férovost se sníží. Dále si popíšeme dvě anomálie Wi-Fi sítě, prostorovou neférovost a plánování frekvencí, které práce [18] popisuje a vysvětluje jimi potřebu férovosti. Jako anomálie prostorové neférovosti se chápe to, že dvě rozdílně vzdálené CS od AP dosahují s tímto bodem různých přenosových rychlostí. Vzdálenější klientská stanice dostává daleko nižší přenosovou rychlost než CS blíže od AP. To je způsobeno rozdílnými RSSI, které tyto stanice získávají. Anomálie plánování frekvencí říká, že použitím stejných frekvencí pro AP, které se překrývají, se dosáhne vyšší propustnosti sítě než při 13
2. Vyvažování zátěže WLAN použití frekvencí, které se navzájem neruší. Tvrzení je podloženo experimentem, ve kterém byly tři klientské stanice asociovány se dvěma AP s tím, že dvě CS byly spojeny s dvěma AP a stanice si navzájem nedetekovaly vysílání. Třetí CS byla spojena s jedním z AP a umístěna v překrývající se části obou AP. Tato CS s nízkou přenosovou rychlostí zanedlouho vyhladověla. Při každém neúspěšném přenosu dat si totiž CS musí nastavit dvojnásobnou hodnotu contention window [18] a čekat při detekci vysílání, čímž se pravděpodobnost vysílání značně sníží. Následně bude kanál použit pouze pro CS s vysokou přenosovou rychlostí. Tato anomálie naznačuje potřebu vzít u metody plánování frekvencí v potaz i férovost, nejen celkovou propustnost sítě. V [19] došli k závěru, že férovost je nezávislá na metodách vyvažování zátěže. Experiment, který provedli ukázal, že i když je síť vyvážená, nemusí být propustnost u všech přístupových bodech stejná. Na vině byla jedna klientská stanice, která měla oproti jiným v experimentu méně RAM paměti (256 MB místo 1 GB u ostatních).
2.2 Definice zátěže Důležitým faktorem u algoritmů, které se snaží vyvažovat zátěž na AP, je hodnota zatížení (load) přístupového bodu. Pod pojmem zatížení si každý představuje různé údaje o síti a zařízeních, které překročily nějakou danou prahovou hodnotu. Některé práce zabývající se vyvažováním zátěže ve svých algoritmech zatížení nijak nedefinují a nechávají tak prostor pro specifické implementace. Existuje řada metod, jak zatížení vypočítat. Uvádíme zde některé často používané postupy. 2.2.1 Počet klientských stanic Velmi používanou hodnotou zatížení je počet stanic, kteří jsou k přístupovému bodu připojeni. Tradičně se používala v přepojovaných buňkových sítích (circuit-switched cellular networks), kde každá stanice představovala stejnou část využití zdrojů [20]. V paketových sítích každá stanice generuje různě velký provoz a nemůžeme tedy určit, jak bude AP zatížen. Počet stanic nám však může něco povědět o po14
2. Vyvažování zátěže WLAN čtu možných kolizí, které vedou k horším vlastnostem sítě. Získat počet stanic připojených k AP není triviální. Probe response a Beacon rámce tuto informaci implicitně neobsahují. Tento počet byl přidán až v dodatku 802.11e v prvku zatížení QBSS (QoS Basic Service Set), což je část Probe response nebo Beacon rámce vysílané přístupovým bodem rozšířeným o QoS (QAP, QoS enhanced Access Point) [19, 21]. Navíc musí být povoleny dva atributy z MIB (Management Information Base) pro AP, aby se QBSS část vůbec poslala. Získat tuto informaci nelze kupodivu ani pomocí SNMP protokolu (Simple Network Management Protocol), protože tento počet nebyl definován v MIB-II, IEEE802dot11-MIB, ani jiné standardizované MIB [19]. Ačkoliv se některé společnosti rozhodly rozšířit MIB o tento prvek, tak je toto rozšíření platné jen pro jejich vlastní zařízení.
2.2.2 Využití kanálu Využití kanálu, tedy zlomek času, kdy je přístupový bod zaneprázdněn přijímáním nebo odesíláním dat během určitého intervalu, je dalším druhem zátěže [19]. Standard 802.11 definuje několik modulací s různými přenosovými rychlostmi (např. 1, 2, 5.5, 11, 55 Mb/s) a proto není možné porovnávat takto získané zátěže jednotlivých přístupových bodů. Pokud by měl například 802.11g AP využití kanálu 4 a 802.11b jen 12 , nutně by to neznamenalo, že 802.11b AP může nově 5 příchozí klientské stanici nabídnout vyšší přenosovou kapacitu. Tuto zátěž používá např. již zmiňovaný dodatek 802.11e s tím rozdílem, že bere do úvahy jen úspěšně přenesené rámce [22].
2.2.3 Počet přeposlání rámce Počet přeposlání rámců je další metoda vypočítání zátěže. Myšlenka je taková, že CS použijí počet, kolikrát se daný rámec musel přeposlat, aby ho cílová stanice přijala bez chyb, jako hodnotu zátěže bezdrátového bodu [19]. Musíme ale znát všechny dvojice skrytých uzlů. Podobná metoda uvažuje odhadnout ztrátovost packetů a tu použít jako hodnotu zátěže. Lze také tyto dvě metody zkombinovat. 15
2. Vyvažování zátěže WLAN 2.2.4 Další způsoby Mnoho prací se zabývá hledáním a definováním efektivních způsobů výpočtu hodnot zátěže či asociace CS k AP. Stručně si zde popíšeme dvě práce. Práce [23] představuje asociační metriku EVA (Estimated aVailable bAndwidth), kterou CS použijí pro připojení k nejvhodnějšímu AP. Klientská stanice poslouchá provoz na médiu a pro každý AP na dostupných kanálech podle algoritmu na výpočet EVA spočte pravděpodobnost kolize a využití kanálu. Poté vybere AP s nejvyšší hodnotou EVA a k němu se připojí. Výhodou algoritmu je použití neinvazivního způsobu skenování, takže nedochází k zbytečné režii. Práce [15] uvádí novou metriku založenou na Probe request rámcích, která se bere do úvahy přímé kolize i nepřímé kolize skrytých uzlů. Autoři se také zaměřili na co nejkratší přepojení CS k nové AP tím, že použijí optimalizovanou backoff metodu pro každou aplikaci. Do úvahy tedy berou maximální přepojovací dobu pro časově kritické aplikace. Metoda prohledává pouze 3 nepřekrývající se kanály (1, 6 a 11). Autoři obou prací nevyužívají žádné speciální rámce, takže se vyhnuli změně standardu.
2.3 Měření efektivity vyvažování zátěže Abychom mohli porovnat efektivitu algoritmů vyvažujících zátěž, musíme k tomu mít nějaké nástroje. Často používané nástroje a metody si zde popíšeme. 2.3.1 Férovost Férovost (fairness) je v sítích důležitá charakteristika a určuje, jestli uživatel dostává férový podíl síťových zdrojů, většinou tedy přenosové rychlosti, v porovnání s ostatními v rámci jedné sítě. V roce 1984 Raj Jain definoval vzorec na výpočet férovosti v celé síti, jehož hodnota se popisuje jako balance index nebo také 𝛽. Vzorec má tvar: ∑︀ ( 𝑘𝑗=1 𝑥𝑗 )2 𝛽= ∑︀ 𝑘 * 𝑘𝑗=1 𝑥2𝑗 16
2. Vyvažování zátěže WLAN Nechť je k počet AP očíslovaných od 1 do k a tyto přístupové body obsluhují stejný počet klientských stanic. Dále 𝑥𝑗 je agregovaná hodnota zátěže na AP j. Potom nám tato rovnice udává, jak férově je rozložena zátěž na všech přístupových bodech. 𝛽 může nabývat hodnot 1 až 𝑘1 s tím, že při 1 je zátěž mezi AP rozložena rovnoměrně, jinak je zátěž nerovnoměrná. Pro tuto rovnici se používá i název JFI (Jain’s Fairness Index). Další metodou, jak férově rozdělit přenosové rychlosti v síti, je metoda max-min spravdlivosti, kterou můžeme najít v [24]. Cílem je maximalizovat minimální férový podíl všech CS. To znamená, že existuje stav, kdy je nemožné zvýšit přenosovou rychlost žádné klientské stanice bez toho, aby se snížily přenosové rychlosti jiným stanicím, které mají přidělené rychlosti menší nebo stejné.
2.3.2 Propustnost Pokud se bavíme o propustnosti (throughput), většinou nás zajímá tzv. agregovaná či systémová propustnost. Ta se vypočítá jako součet efektivních přenosových rychlostí všech zařízení v síti. Do efektivní přenosové rychlosti se nezapočítává režie fyzické vrstvy ISO/OSI modelu. Propustnost většinou měříme v bitech za sekundu. Dále při porovnání metod vyvažování zátěže můžeme využít propustnost jednotlivých klientských stanic.
2.3.3 Specializované nástroje Použít se mohou i komplexní specializované nástroje vyvíjené buď konkrétní firmou jako komerční produkt nebo jako open source projekt podporovaný komunitou. Konkrétně v pracích [25, 26] použili pro simulaci výsledků komerční nástroj OPNET vyvíjený firmou OPNET Technologies, Inc. Open source projekt ns-2 (network simulator) byl použit v dřívějších verzích práce [18], v nejnovější verzi však použit nebyl. Nezachycoval totiž správně anomálii prostorové neférovosti a autoři si proto napsali simulátor nový. Projekt ns je vyvíjen pod licencí GNU GPLv2 a existuje již verze ns-3. 17
2. Vyvažování zátěže WLAN
2.4 Existující řešení V této části popíšeme základní přístupy k vyvažování zátěže, jednotlivé algoritmy a jejich všeobecný popis. 2.4.1 Vyvažování zátěže na straně klienta Tato metoda předpokládá, že se klientské stanice samy rozhodnou kdy a za jakých podmínek provedou reasociaci k jinému přístupovému bodu [19]. Ty jsou v síti pasivní. Pokud CS potřebují s AP komunikovat, tak jim AP posílají potřebné informace. Buď přes Probe response rámce či specializované 802.11k rámce, pokud jsou tak přístupové body nastaveny. Výhodou použití tohoto postupu je to, že většinou lze použít AP bez modifikace programového vybavení nebo jen částečné úpravy. Klientské stanice si většinou volí AP podle toho, jaké kritérium chtějí maximalizovat. Pokud se rozhodly maximalizovat přenosovou rychlost, implementují tzv. least-loaded-first (LLF) heuristiku, která vybere nejméně zatížený přístupový bod a potenciálně tak získají nejrychlejší přenosovou rychlost. Jako kritérium pro LLF se také může vzít počet právě obsluhovaných uživatelů AP. Tuto inforamci AP do okolí rozesílá jako broadcast a CS si vyberou ten s nejmenším počtem. Toto řešení je však proprietární a nabízí ho např. Cisco, protože dodavatel musí změnit síťové ovladače a firmware [27]. Jak jde vidět, vyvažování na straně klienta nebude nikdy plně vyvážené. Klientské zařízení jsou sobecká, protože chtějí jen maximalizovat své kritérium. Dále zde neexisuje entita, která by měla přehled o stavu celé sítě a vyvažování řídila. Algoritmy založené na tomto přístupu tedy nemohou být ideální pro vyvážení celé sítě a mnohdy tak ani nejsou zamýšleny. Asociace CS k AP může být dvojí. Buď statická, kdy se CS připojí k předem danému AP, je k němu připojena stále a nereaguje na změny v síti. Asociace dále může být dynamická. CS potom reaguje na změny v síti a přepojuje se k různým AP podle potřeby. Nevýhodou dynamické asociace je možnost vzniku ping-pong efektu. Tehdy se klientské stanice přepojují z původního AP na AP nové a poté zpět na AP původní atd. Příkladem může být příchod nového přístupového bodu do sítě. Mnoho klientských stanic se přepojí k novému AP, 18
2. Vyvažování zátěže WLAN protože jim nabídne např. lepší přenosovou rychlost. Poté zjistí, že přístupová rychlost je nízká a proto se přepojí k původnímu AP. Proces se může dále takto opakovat. Řešením může být použití backoff algoritmu jako u přístupové metody DCF. 2.4.2 Algoritmy vyvažování na straně klienta Práce [28] představuje algoritmus, kde si přístupové body periodicky počítají svou zátěž a tu pak posílají v Beacon či Probe Response rámcích. Klientské stanice sledují tyto rámce a zátěže v nich uvedené. Pokud ještě CS není asociována s žádným AP, vybere si ten s nejmenší zátěží, jinak vypočte rozdíl zátěže původního a nového AP. Když je rozdíl zátěží větší než dané 𝛿, potom je výhodnější změnit asociaci a přepojit se k novému AP. CS odhadují přenosové rychlosti pro komunikaci s AP podle dostupných RSSI. Nevýhodou algoritmu je nutnost přidání informace o zátěži do posílaných rámců, neboť v původním 802.11 se tyto informace neposílají. CS také periodicky (co 10s) prohledává okolí, což podle autorů trvá až 300ms, což není příznivé např. pro VoIP. Dále není v práci definována zátěž. Autoři v [29] navazují na práci Content Distribution Field, ale na rozdíl od něho používají decentralizované řešení. Práce pro rozhodnutí jestli se přepojit k novému AP nepoužívají jen RSSI, ale definují nový mechanismus QWLAN. Ten bere do úvahy RSSI od AP, indikátor provozu, což je rozdíl mezi vysílanými Beacon rámci a váhu pro indikátor provozu. Dále se zde jako u původního algoritmu přepojení k AP uvažuje hodnota APRH (Acess Point Reselection Hysteresis), která zabraňuje častým reasociacím (ping-pong efektu). Tato práce vyžaduje použití dvou WiFi adaptérů s tím, že jeden z nich neustále monitoruje okolí a druhý je připojen k AP a přenáší data. Práce [26] se zaměřuje na přepojování CS k jiným AP v prostředí s více přenosovými rychlostmi. Algoritmus bere v potaz RSSI, propustnost a přenosové rychlosti. Nejdříve se jako kandidáti pro přepojení přidají AP, od kterých je získané RSSI větší než daná prahová hodnota. Poté CS pošle všem kandidátům Probe Request a z odpovědí Probe Response se vypočte a vybere AP, který je nejvhodnější pro přepojení. V dynamicky se měnícím bezdrátovém prostředí je nutné po určitém čase opakovat daný proces a případně se přepojit k vhodnějšímu AP. 19
2. Vyvažování zátěže WLAN 2.4.3 Vyvažování zátěže na straně sítě Druhý způsob vyvažování zátěže je pomocí centralizované entity, tzv. NOC (Network Operation Center) [18]. Ta je v síti většinou jako dedikovaný server, který provádí sběr informací od přístupových bodů a zná tak celkový pohled na síť. Může pak měnit asociace klientských stanic s AP mnohem efektivněji a dosáhnout tak větší propustnosti sítě a férovosti. V síti však NOC operovat nemusí a AP se mohou domlouvat mezi sebou, např. protokolem IAPP [19]. Vzniká tak větší režie provozu, ale odpadne nutnost provozovat NOC. Většinou jsou přístupové body a NOC propojeny přes Ethernet a díky tomu lze dosáhnout rychlejší a méně chybové komunikace mezi sebou. Oddělíme tak provoz klientských stanic na bezdrátovém médiu a provoz nutný k správnému fungování vyvažovacího algoritmu. Ethernet dosahuje mnohem větších rychlostí než WiFi a nemusíme se tedy obávat zahlcení sítě režií algoritmu [30]. 2.4.4 Cell breathing Cell breathing neboli buněčné dýchání je v tradičních přepojovaných CDMA sítích vedlejší účinek obsluhování více uživatelů, kde buňka zmenší svou velikost [6]. V paketových sítích přístupový bod dynamicky mění velikost své buňky zvyšováním či snižováním vysílacího výkonu. Tím, že se sníží vysílací výkon Beacon rámce, vzdálenější stanice získají menší RSSI a pravděpodobně se přepojí k jinému přístupovému bodu. AP by měly spolupracovat mezi sebou, aby pokryly možné místa, kde by signál Beacon rámce nedosahoval. Méně zatížené AP by měly po domluvě svůj signál zesílit a přilákat tak k sobě stanice připojené k zatíženějším AP. Cell breathing mnohdy znamená jen změnu programového vybavení přístupového bodu. Klientská stanice se modifikovat nemusí, neboť se rozhoduje jen podle změněných Beacon či Probe response rámců. Rozlišujeme dvě hodnoty a to vysílací výkon, což je maximální vysílací výkon AP a velikost buňky, což je kvalita Beacon a Probe response rámců, které získávají klientské stanice. Práce [20] představuje algoritmus DCB (Distributed Cell Breathing), který bere v potaz svou AP a také zátěž souseda. 2 AP jsou sousedi, 20
2. Vyvažování zátěže WLAN pokud mezi nimi existuje alespoň jedna společná klientská stanice. Algoritmus funguje decentralizovaně bez NOC, ale distribuovaně komunikací přístupových bodů mezi sebou. Dále jsou v algoritmu pro každý AP definovány 3 stavy. Fair, kde je zátěž AP podobná jako průměr zátěží ostatních a přístupový bod v tomto stavu nebude provádět žádné akce, dokud se v okolí něco nezmění. Gull, kdy je zátěž větší než v okolí a AP je ochotný zmenšit svou buňku a požádat ostatní o pomoc. Nakonec willing, kdy je zátěž pod průměrem a AP je ochotný zvětšit svou buňku a odpovídat ostatním na žádosti o pomoc. Zátěž se vypočítá jako kapacita volná pro novou CS, která používá nejrychlejší modulaci. AP si počítá zátěž buď periodicky nebo na vyžádání. Nevýhodou práce je jeho složitost a relativní nedokončenost. V práci [31] autoři použili techniku Cognitive radio (CR), které je založené na buněčném dýchání. CR je paradigma, které dokáže autonomně reagovat na situace v rádiovém prostředí, učit se a adaptovat se odpovídajícími akcemi na měnící se podmínky. Algoritmus používá RTS/CTS rámce pro změnu velikosti buňky a funguje následovně. AP podle získaného RSSI od CS vypočte vzdálenost (RSSI je inverzně úměrný vzdálenosti mezi AP a CS) a zjistí, jestli je CS jen ve vysílacím vzdálenosti od AP nebo i v rušivém okolí. Vzdálenost je použita společně se stavem AP pro vstup do řadiče fuzzy logiky. Fuzzy logika je systém pro řešení problémů, kde jsou vstupní informace neúplné a nepřesné. Existují 3 stavy AP: vyvážený, kde se neprovádí žádná změna, přetížený, kde je AP ochotno zmenšit velikost buňky a konečně méně vyvážený, kde je AP ochotno zvětšit velikost buňky. Tyto dva vstupy jsou použity se 4 fuzzy relacemi a vzniká tak 8 pravidel pro chování AP. Nevýhodou práce je poměrně zjednodušený pohled na síť a nejisté vyvážení. 2.4.5 Admission control Admission control přístup jednoduše odmítne nové žádosti o asociaci s daným AP, které je přetížené [19]. Nepřetížený přístupový bod povolí novou asociaci pouze v případě, že predikovaná zátěž nového klienta nepřesáhne určitou prahovou mez. V dalším základním přístupu, association control, se přetížený AP vyrovná s příliš velkou zátěží tak, že některým CS pošle disasoci21
2. Vyvažování zátěže WLAN ační rámec [19]. V tomto rámci může být zadán důvod disasociace ve formě kódu, kde AP říká z jakého důvodu ruší asociaci. Pokud klientská stanice použije jiný algoritmus než implicitní SSF (Strongest Signal First), kde se vybere AP podle nejsilnějšího RSSI, tak se může přepojit k méně vytíženému AP a tím zmenšit zátěž na původním AP. Autoři v [17] definují asociační problém mezi CS a AP jako optimalizační problém s cílem minimalizovat variaci zátěže různých přístupových bodů a vylepšit propustnost a férovost. Představeny jsou 2 hladové (greedy) heuristiky. První z nich, který má za úkol připravit počáteční asociaci pro druhou heuristiku, krok po kroku přepojí CS k AP. Klientské stanice komunikují s NOC a od AP získávají údaje o zatížení, což je počet klientských stanic. Nejdříve se přepojí množina CS s nejmenším počtem AP ve svém okolí, poté množina CS s AP o jedno větší atd. Druhá heuristika má za cíl vyvažovat zátěž minimalizací maximální zátěže AP a vykonává se tak dlouho, dokud již zátěž nejzatíženějšího AP nelze snížit. Na počátku se toto AP vybere a najdou se stanice, které lze přepojit k jiným AP tak, aby zátěž na novém AP nebyla větší než na původním. To se opakuje, dokud lze zátěž snížit. V těchto heuristikách CS často komunikuje s NOC po bezdrátovém médiu a tím snižuje propustnost sítě. Navíc je potřeba použít nové dodatky standardu pro přístup k informacím o počtu klientských stanic nebo modifikovat standard. Další práce [30] je podobná předešlé. Definují se zde 2 algoritmy, první z nich, Fair Bandwidth Allocation Algorithm, pomocí toku v sítích převede asociační problém na maximální tok v grafu. Poté pomoci čtyř kroků, každý krok představuje vyšší stupeň férovosti, alokuje šířku pásma AP do zón. Zóny jsou 2, buď je CS v dosahu pouze jednoho AP, nebo více AP. Druhý algoritmus, Association for maximum throughput, provádí samotnou asociaci CS k AP. Každá CS si vypočte přenosovou rychlost, kterou může získat od dostupných AP a tuto informaci pošle přístupovému bodu, od kterého získává nejsilnější RSSI. Tyto informace si potřebné AP vymění a rozhodnou, jaká CS se má připojit ke kterému AP podle nejvyšší přenosové rychlosti. V tomto algoritmu nefiguruje NOC, ale pouze programové vybavení na AP. Výhodou je zlepšená propustnost, ale za cenu změny fukcionality klientských stanic a přístupových bodů.
22
2. Vyvažování zátěže WLAN 2.4.6 Plánování frekvencí Metodou plánování frekvencí (PF) u WLAN sítí se rozumí rozvržení bezdrátových vysílacích kanálů přístupovým bodům. Implicitním nastavením je algoritmus Least Congested Channel Search [18], který hledá nejméně zarušený kanál. Plánováním frekvencí nelze eliminovat prostorovou neférovost, neboť ta je u WLAN sítí vlastní. Obecný cíl PF je maximalizovat celkovou propustnost sítě snížením rušení mezi buňkami ESS. Mnohdy se však nebere do úvahy férovost a následným vyvažováním zátěže může vzniknout stav, který je kvalitativně horší než původní. Autoři Bejerano, Han a Smith v [18] navrhli algoritmus plánování frekvencí, který zohledňuje mezibuňkové rušení a pro nalezení vhodného rozvržení frekvencí používá koncept sdílených časových úseků. Model kvantitativně zachytává množství rušení mezi vedlejšími buňkami a kombinuje ho se zátěží jednotlivých AP. Zátěž přístupového bodu je čas potřebný pro zpracování (poslání či přijetí) jedné jednotky provozu pro každého svého uživatele. Odráží tedy schopnost uspokojení požadavků svých uživatelů a měla by být inverzně proporční průměrné přenosové rychlosti, kterou uživatelé přijímají. Heuristika v této práci nejprve najde zátěže všech AP pomocí sdílených časových úseků a sdílených zón a poté se iterativně vyberou zatím neobsloužené AP. Pro každý kanál se najdou přípustné rozvržení, aby se minimalizovala určitá jednotka zahlcení. V této práci spolu komunikují AP bez přítomnosti NOC. Výhodou je, že není potřeba spolupráce CS a není potřeba modifikovat standard. Nevýhoda je přílišná komplexnost algoritmu a nezpracované detaily v práci. 2.4.7 Další přístupy V [27] autoři použili dvou genetických algoritmů (GA) k vyvažování zátěže. Důvodem je schopnost rychle nalézt dobré řešení v obtížných situacích s mnoha uživateli. Nejprve AP zjistí, kolik CS je v zóně. Máme 4 zóny podle vzdálenosti CS od AP a podle nich zjistíme maximální dosažitelnou přenosovou rychlost. Ta se rozdělí podle váhy CS a počtu CS v zóně. Váha nám dovolí specifikovat QoS CS. Cílem GA algoritmů je přiřadit CS k AP tak, aby součet všech přenosových rychlostí CS byl maximální. V GA úlohách mapujeme fenotyp, což je 23
2. Vyvažování zátěže WLAN množina spojení CS-AP na genotyp, což je uspořádaná posloupnost CS se spojenými AP. Popsány jsou 2 algoritmy, MicroGA a MacroGA. Liší se jen v poslední fázi, kde je u druhého ještě navíc mutace, která zaručuje diverzitu. Nejdříve se vygenerují jedinci, spojí se s dostupnými AP, vypočítá se fitness přiřazení (přenosová rychlost). Jedinci s nejlepším fitness jsou z aktuální populace zkopírovány do další. Binární soutěž zalidní populaci mating pool (MP) s rodiči. Rekombinační fáze v prvním algoritmu je křížení, kde se 2 jedinci vyberou z MP a operátor křížení prochází genotyp jedinců. Pokud je pravděpodobnost pravdivá, pak se gen na indexu i vymění mezi dvěma jedinci. U mutace se vyberou popořadě jedinci a prochází se geny, které je přiřazují k AP. Pokud je pravděpodobnost mutace pravdivá, pak se gen změní a vybere se náhodně AP z dosahu jedince a nahradí daný gen. Posledním algoritmem, který si představíme je ALBA (An Autonomic Load Balancing Algorithm v [25]. Autoři představují autonomní algoritmus na vyvažování zátěže s využitím tzv. Knowledge Plane (KP). Tento koncept dovoluje síti autonomně reagovat podle instrukcí vyšší úrovně na požadavky uživatelů v síti. Koncept je založen na Situated View, což je pohled uzlu x, který sbírá informace (či znalosti) použité různými algoritmy ze sousedících uzlů vzdálených až n skoků (hopů). Role KP je monitorovat stav zdrojů, dostupné AP, asociované CS a jejich přenosové rychlosti a požadavky. Každý AP si drží informace o seznamu svých sousedních AP ve vzdálenosti menší či stejné než n skoků. Dále má seznam všech viditelných CS, s těmi ale nemusí být asociován. Konečně má uložen seznam CS, se kterými je asociován. Funkcí ALBA je dovolit uživateli spojit se k AP, který splní jeho požadavky, např. na minimální přenosovou rychlost, tím, že změní asociaci jiných CS k AP a vyváží tak zátěž mezi AP na základě znalostí z KP.
2.5 Vybraný algoritmus Algoritmy, které fungují na principu vyvažování zátěže na straně sítě mnohdy potřebují složitou komunikaci mezi přístupovými body či NOC. Musí se tedy modifikovat AP a pokud je potřeba změnit asociaci CS s jiným AP, mnohdy to nejde jinak než modifikovat zařízení 24
2. Vyvažování zátěže WLAN klientské stanice. Tyto algoritmy jsou navíc výpočetně náročné a nedají se často použít pro časově kritické aplikace [27]. Po dohodě s vedoucí práce jsem vybral algoritmus z práce [26], který vyvažuje zátěž na straně klienta, a dále se mu v práci budeme věnovat. Dále navazujeme na bakalářskou práci na téma SNMP [32] a diplomovou práci na téma vyvažování zátěže sítě AP [33]. Tyto dvě závěrečné práce se věnují přístupu, který využívá přístupové body pro komunikaci a vyvažování zátěže na nich. Tato práce rozšiřuje citované práce o algoritmus a jeho implementaci o vyvažování zátěže z pohledu klientské stanice.
25
Literatura [1] C. Yuntsai, “A seamless city: The case study of taipei’s wifi project [online].” http://userpage.fu-berlin.de/jmueller/its/ conf/porto05/papers/Chou.pdf, [cit. 2011-10-05]. [2] J. Lu, “Nortel wins taipei’s mobile city project phase ii contract to deploy wireless mesh network [online].” http://www.nortel.com/corporate/news/newsreleases/ 2005b/06_02_05_qware.html, [cit. 2011-10-05]. [3] M. Gast, 802.11 wireless networks: the definitive guide. Sebastopol: O’Reilly, 2nd ed., 2005. [4] D. Kaur, K. Kaur, and V. Arora, “Qos in wlan using ieee802.11e: Survey of qos in mac layer protocols,” Advanced Computing & Communication Technologies, International Conference on, vol. 0, pp. 468–473, 2012. [5] B. D. Mathews, “Standards based wireless networking with linux [online].” http://www.linux-wlan.com/writings/ std-wlan-linux/stdwlan-whitepaper.html, [cit. 2011-10-10]. [6] E. Garcia Villegas, R. Vidal Ferre, and J. Paradells Aspas, “Load balancing in wlans through ieee 802.11k mechanisms,” in Computers and Communications, 2006. ISCC ’06. Proceedings. 11th IEEE Symposium on, pp. 844 – 850, jun. 2006. [7] J. Geier, “Understanding 802.11 frame types [online].” http: //www.wi-fiplanet.com/tutorials/article.php/1447501, [cit. 2011-10-20]. [8] “Ieee standard for information technology-telecommunications and information exchange between systems-local and metropolitan area networks-specific requirements - part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications,” IEEE Std 802.11-2007 (Revision of IEEE Std 802.11-1999), pp. C1–1184, dec. 2007. 26
2. Vyvažování zátěže WLAN [9] J. F. Kurose and K. Ross, Computer Networking: A Top-Down Approach Featuring the Internet. Boston: Addison-Wesley, 3rd ed., 2005. [10] A. Ksentini, A. Nafaa, A. Gueroui, and M. Naimi, “Determinist contention window algorithm for ieee 802.11,” in Personal, Indoor and Mobile Radio Communications, 2005. PIMRC 2005. IEEE 16th International Symposium on, vol. 4, pp. 2712 –2716 Vol. 4, sept. 2005. [11] W. Stallings, Wireless Communications and Networks. Upper Saddle River: Prentice Hall, 2nd ed., 2002. [12] J. Bardwell, “Converting signal strength percentage to dBm values [online].” http://www.wildpackets.com/elements/ whitepapers/Converting_Signal_Strength.pdf, nov. 2002 [cit. 2012-03-15]. [13] K. Schneider, D. Turgut, and M. Chatterjee, “An experimental study on layer 2 roaming for 802.11 based wlans,” in World of Wireless, Mobile and Multimedia Networks, 2007. WoWMoM 2007. IEEE International Symposium on a, pp. 1 – 6, jun. 2007. [14] Y.-S. Yen, R.-S. Chang, and T.-Y. Wu, “A seamless handoff scheme for ieee 802.11 wireless networks,” in Communications and Networking in China (CHINACOM), 2010 5th International ICST Conference on, pp. 1 – 5, aug. 2010. [15] J. Ryou, B. Lee, C. Yu, M. Kim, S.-J. Hyun, S.-M. Park, and W.T. Kim, “Probe request based load balancing metric with timely handoffs for wlans,” in Information and Communication Technology Convergence (ICTC), 2010 International Conference on, pp. 346 –351, nov. 2010. [16] M. Abusubaih, “A combined approach for detecting hidden nodes in 802.11 wireless lans,” Annals of Telecommunications, pp. 1 – 8. 10.1007/s12243-011-0239-x. [17] Y. Le, L. Ma, H. Yu, X. Cheng, Y. Cui, M. A. Al-Rodhaan, and A. Al-Dhelaan, “Load balancing access point association schemes for ieee 802.11 wireless networks,” in Proceedings of the 6th 27
2. Vyvažování zátěže WLAN international conference on Wireless algorithms, systems, and applications, WASA’11, (Berlin, Heidelberg), pp. 271–279, SpringerVerlag, 2011. [18] Y. Bejerano, S.-J. Han, and M. Smith, “A novel frequency planning algorithm for mitigating unfairness in wireless lans,” Computer Networks, vol. 54, no. 15, pp. 2575 – 2590, 2010. [19] L.-H. Yen, T.-T. Yeh, and K.-H. Chi, “Load balancing in ieee 802.11 networks,” Internet Computing, IEEE, vol. 13, pp. 56 –64, jan.-feb. 2009. [20] E. Garcia, R. Vidal, and J. Paradells, “Cooperative load balancing in ieee 802.11 networks with cell breathing,” in Computers and Communications, 2008. ISCC 2008. IEEE Symposium on, pp. 1133 –1140, jul. 2008. [21] B. Simsek, K. Wolter, and H. Coskun, “Analysis of the qbss load element parameters of 802.11e for a priori estimation of service quality,” International Journal of Simulation: Systems, Science and Technology, Special Issue: Performance Engineering of Computer and Communication Systems, 2006. [22] X. Chen, H. Zhai, X. Tian, and Y. Fang, “Supporting qos in ieee 802.11e wireless lans,” Wireless Communications, IEEE Transactions on, vol. 5, pp. 2217 –2227, aug. 2006. [23] H. Lee, S. Kim, O. Lee, S. Choi, and S.-J. Lee, “Available bandwidth-based association in ieee 802.11 wireless lans,” in Proceedings of the 11th international symposium on Modeling, analysis and simulation of wireless and mobile systems, MSWiM ’08, (New York, NY, USA), pp. 132–139, ACM, 2008. [24] Y. Bejerano, S.-J. Han, and L. Li, “Fairness and load balancing in wireless lans using association control,” Networking, IEEE/ACM Transactions on, vol. 15, pp. 560 –573, jun. 2007. [25] G. Sawma, I. Aib, R. Ben-El-Kezadri, and G. Pujolle, “Alba: An autonomic load balancing algorithm for ieee 802.11 wireless networks,” in Network Operations and Management Symposium, 2008. NOMS 2008. IEEE, pp. 891 –894, apr. 2008. 28
2. Vyvažování zátěže WLAN [26] Z. Liu, Y. Liu, Z. Gong, and L. Chen, “A mutil-rate access point selection policy in ieee 802.11 wlans,” in Multimedia Technology (ICMT), 2011 International Conference on, pp. 63 –67, jul. 2011. [27] T. Scully and K. N. Brown, “Wireless lan load balancing with genetic algorithms,” Know.-Based Syst., vol. 22, pp. 529–534, oct. 2009. [28] S. Venkatesan and M. C., “Fair load balancing in wireless networks,” Global Journal of Computer Science and Technology, vol. 9, no. 5, pp. 41–45, 2010. [29] N. Papaoulakis, C. Patrikakis, C. Stefanoudaki, P. Sipsas, and A. Voulodimos, “Load balancing through terminal based dynamic ap reselection for qos in ieee 802.11 networks,” in Pervasive Computing and Communications Workshops (PERCOM Workshops), 2011 IEEE International Conference on, pp. 600 –605, mar. 2011. [30] S. Dandapat, B. Mitra, N. Ganguly, and R. Choudhury, “Fair bandwidth allocation in wireless mobile environment using maxflow,” in High Performance Computing (HiPC), 2010 International Conference on, pp. 1 –10, dec. 2010. [31] R. Ruslan and T.-C. Wan, “Wi-fi load balancing using cognitive radio techniques,” in Information Technology (ITSim), 2010 International Symposium in, vol. 1, pp. 1 –5, jun. 2010. [32] J. Malík, “Správa přístupových bodů bezdrátové sítě [online].” http://is.muni.cz/th/173411/fi_b/, 2008 [cit. 2012-05-13]. [33] R. Šustek, “Systém pro vyvažování zátěže sítě bezdrátových přístupových bodů [online].” http://is.muni.cz/th/99027/fi_ m/, 2009 [cit. 2012-05-13].
29
