Computer Networks Laboratory

Úvod: Čo keby sme na vytvorenie siete nepotrebovali žiadne sieťové prvky ako sú routre, switche alebo access-pointy ? Čo keby v nej neexistovalo ani jedno rizikové miesto (single point of failure) a bola by vytváraná kompletne dynamicky bez akéhokoľvek orgánu, ktorý by ju spravoval. Sieť ktorá by bola tvorená iba koncovými zariadeniami, ktoré by si boli rovnocenné, mohli by sa pohybovať, kedykoľvek sa pripájať a odpájať, zároveň by bol každý bod tejto siete v ktoromkoľvek momente za akýchkoľvek podmienok dostupný z ľubovoľného iného bodu. Sieť robustná a pritom jednoduchá, hovorí sa jej MANET, mobilná ad-hoc sieť.

S pojmom Ad-Hoc sa mnohí z Vás už určite stretli, takéto siete sa zvyknú využívať na priame prepojenie dvoch zariadení, napr. dvoch PC bezdrôtovo bez potreby access-pointu. Možnosti siete Ad-Hoc však zďaleka nekončia iba pri prepojovaní dvoch zariadení. Za bežných okolností a s bežne dostupným softvérovým vybavením to tak je, našťastie sa vždy nájde niekto, komu súčasné možnosti nestačia a chce posunúť hranice možného. MANET-y sú nutným, logickým evolučným krokom vpred, sú postavené na overenej jednoduchosti Ad-hoc sieti a pridávajú k nej možnosť vytvárať väčšie siete použitím smerovacieho protokolu. Výhody takýchto sietí sú jednoznačné, preto sa nemožno čudovať, že sa o ne zaujímajú výskumníci z celého sveta, a to nie len s akademickej oblasti. Veľký kus práce zohrala aj americká armáda, vyvinula napr. vlastnú implementáciu smerovacieho protokol optimalizovaného pre siete MANET – OLSR /optimized link state routing protocol/. Napriek všetkým snahám ostávajú siete MANET naďalej len víziou, doposiaľ fungujú len v prísne kontrolovaných laboratórnych podmienkach.

Keď som sa pred pár týždnami dozvedel o súťaži MANIAC /Mobile Ad-Hoc Network Interoperability and Cooperation/ Challenge organizovanej Virginia Polytechnic Institute and State Univesrity s podporou The National Science Foundation, USA, nevedel som toho veľa o problematike MANET-ov a už vôbec som s nimi nemal žiadne praktické skúsenosti. Bol som však nadchnutý ich možnosťami a tým, že mám príležitosť sa priamo podieľať na jedinečnom experimente. MANIAC Challenge si zobral za cieľ simulovať sieť MANET za reálnych podmienok, organizátori priamo vyzývali zapojené tímy k tomu, aby sa správali sebecky, aby sa snažili doručovať v prvom rade svoje dáta a minimalizovať dáta ostatných tímov. Efektívnosť jednotlivých riešení sa posudzovala podľa jednoduchého vzorca : 10 bodov za každý doručený vlastný packet a mínus 1 bod za každý odoslaný packet. Takéto hodnotenie malo motivovať k invenčným riešeniam zameraním na šetrenie energie, pretože každý odoslaný packet spôsobí straty energie. Organizátori dodali hotové API /application programming interface/, takže tímy sa mohli sústrediť priamo na rozhodovaciu logiku a nemuseli riešiť systémové otázky. Ako smerovací protokol bol použitý už spomenutý OLSR vyvinutý US Naval Research Laboratory. Vzhľadom na to, že jednotlivé tímy nemali žiadne informácie o postupe iných tímov, muselo byť ich riešenie generické a vedieť sa prispôsobiť rôznym situáciám.

Celý vývoj prebiehal veľmi dynamicky, neexistovala nijaká podrobná špecifikácia alebo návody ako postupovať. V prvom rade bolo nutné vytvoriť si vývojové a testovacie prostredie. Ale ako jednoducho simulovať sieť zloženú s niekoľkých autonómnych strojov, kde len niektoré stroje majú vzájomnú konektivitu? Pokiaľ by sme položili na stôl niekoľko notebookov, každý z nich by mal konektivitu so všetkými ostatnými. Nemohli by sme teda nasimulovať reálnu topológiu, kde napr. jeden stroj má v dosahu len jeden ďalší a ten zase ďalší atď. Preto som sa rozhodol použiť virtuálne stroje, ktorým sa na druhej vrstve OSI modelu nadefinovalo, ktoré ďalšie stroje vidia a ktoré nie. Týmto krokom sa na jedinom notebooku mohol simulovať menší MANET, na dvoch notebookoch to však už stačilo na simulovanie MANET-u zloženého s deviatich strojov, a teda celkom peknej siete, na ktorej sme mohli vyskúšať prakticky akúkoľvek situáciu. Ako som sa neskôr dozvedel boli sme jediný ktorí zvolili takýto postup. Nakoľko to výrazne zjednodušuje a zrýchľuje celkový vývoj rozhodli sme sa spolu s organizátormi že pre ďalší ročník súťaže bude zverejnený obraz virtuálneho stroja na oficiálnych stránkach a budú ho môcť použiť aj ostatné tímy.

Obr.1.: Vývojárske prostredie z 9-tich virtuálnych strojov

Organizátori nemali presne stanovené očakávania, skôr ich zaujímalo, s akými nápadmi prídu súťažiace tímy. Naše riešenie sa celé odvíjalo od jedinej vety: „Ži a nechaj žiť“. Možno sa pýtate, prečo práve táto veta. Odpoveď je jednoduchá, žiaden celok nemôže fungovať, pokiaľ nie je cieľom jeho jednotlivých komponentov spolupráca. Celok je v tomto konkrétnom prípade sieť, komponenty jednotlivé body siete a funkcia je optimálne vzájomné prepojenie všetkých bodov siete. Ale ako minimalizovať spotrebu energie jednotlivých bodov siete a pri tom zachovať sieť ako celok funkčný? Na túto otázku hľadali odpoveď všetci súťažiaci. Všetci šli svojou vlastnou cestou, či už zložitými matematickými modelmi, hrubým zásahom do správania sa smerovacieho protokolu alebo… Hlavná myšlienka nášho riešenia spočíva v minimalizácii priamych spojení so susedmi. V prvom kroku sme si našli najlepšieho suseda pre odosielanie pre nás zaujímavých dát, t.j. s najmenšou metrikou k cieľu našich dát. Potom sme doslovne odrezali všetkých ostatných susedov, počkali, kým sa zmeny v topológii prejavia a následne overili, či sú všetci, ktorých sme odrezali, ešte stále dostupní. Keby naši priamy topologickí susedia mali ešte nejaké ďalšie pripojenie do siete ako nás, dozvedeli by sme sa o nich cez suseda, ktorého sme si vybrali ako ideálneho pre posielanie našich dát. Ak sa o niekom so susedov nedozvieme, znamená to, že nemá inú cestu do siete ako cez nás. V tom prípade ho povolíme a poskytneme mu pripojenie do siete cez nás. Ak sa detekujú akékoľvek topologické zmeny, ktoré by mohli mať dopad na objektívnosť nami vytvorenej minimálnej topológie susedov, prerátame ju. Takéto „odrezávanie“ má aj ďalšiu výhodu a to je zvyšovanie metriky pre nezaujímavé body siete a teda zmenšovanie atraktivity posielania nezaujímavých dát cez nás. A to je ideálny prípad, keď zvyšok siete ani len nebude chcieť poslať svoje dáta cez nás.

Obr.2.: Príklad „odrezania“ susedov ktorý majú inú možnosť pripojenia do siete ako cez nás = NODE 1

Samozrejme sme nemohli vedieť čo si na nás pripravia ostatné tímy a preto sme predpokladali že sa taktiež budú držať nejakého konštruktívneho prístupu udržiavania siete funkčnej ako celok. Ďalej sme si mohli byť viac ako istí, že budú nejakým spôsobom obmedzovať dáta iných tímov. Aby sme zabezpečili čo najrýchlejšie dátové prenosy, rozhodli sme sa implementovať istý druh load-balancingu. Pokiaľ existuje viac ako jedna cesta k cieľu, a všetky cesty majú rovnaké alebo porovnateľné parametre, použijeme ich všetky na prenos dát systémom per packet switching.

Obr.3.: Príklad load-balancingu po viacerých cestách s rovnakou váhou

Teória vyzerá fajn, ale ako by sa to správalo v reálnom živote? Pozrime sa na nejaký veľmi jednoduchý príklad.

Obr.4.: Príklad zo skutočného života

Predpokladajme, že máme v domácnosti 2 notebooky, PC 1 a PC 2 a 3 mobilné telefóny, NODE 1 až 3, pričom PC 2 má ako jediný priamy prístup do internetu. PC 1 a PC 2 bežia napájané zo siete, telefóny na batérie. Ďalej predpokladajme, že na všetkých strojoch beží rovnaký smerovací protokol, napríklad OLSR. Na telefónoch okrem toho beží naša rozhodovacia logika – MANIAC. NODE 1 má v dosahu iba PC 1 a NODE 2, MANIAC zabezbečí, že sa pripojí iba na PC 1, teda nezaťažuje svojimi dátami NODE 2 a šetrí mu energiu. NODE 3 má však v dosahu iba NODE 2, nemá žiadnu inú možnosť pripojenia do siete ako cez neho, preto mu NODE 2 poskytne prístup do siete cez PC 2. V konečnom počte krokov sa vytvorí optimálna topológia.

V ďalšom príklade sa pozrieme na ďalšiu možnú topológiu a spomenieme si základne triky, s ktorými takúto topológiu generujeme. Nebudeme sa však do hĺbky zaoberať technickou realizáciu, pretože by to bolo nad rámec tohto článku.

Obr.5.: Príklad použitia unicastovania multicastovych OLSR hello / TC sprav a ARP hidingu

MANIAC Challenge bol organizovaný ako sprievodná akcia ku konferencii IEEE Globecom 2007, ktorá ma tohto roku svoje 50. výročie. Jedná sa o jednu z najväčších telekomunikačných konferencii vôbec. Celá akcia prebiehala v priestoroch hotela Hilton Washington vo Washnigtone D.C. USA. Nešetrilo sa naozaj na ničom a pri cenách v danom hoteli sme boli naozaj radi, že sme dostali od organizátorov štedrý grant. V nasledujúcich fotkách by som chcel priblížiť nezabudnuteľnú atmosféru tejto akcie.

Obr.6.: Výhľad z hotelovej izby na Washington DC, v pozadí washingtonský monument

Obr.7.: Zdravá americká strava – večera po príchode do US

Obr.8.: Text úvodnej reči k našej prezentácii

Obr.9.: Sála, v ktorej prebiehali prezentácie

Obr.10.: Naša prezentácia

Obr.11.: Prezentácia

Obr.12.: Aktuálny stav topológie bol neustále zobrazovaný na projektoroch, všimnite si dva body, ktoré nie sú súčasťou full-meshu, to je náš tím. Jeden z organizátorov vyslovil pamätnú vetu keď to uvidel: “Chlapi, naozaj neviem ako to robíte, ale bojím sa toho”

Obr.13.: Spoločná foto, zľava: Vladimír Sidimák, Vivek Srivastava, Ivan Klimek

Obr.14.: Po bankete sme si s Vladom povedali, že ideme pozriet mesto. Keďze washingtonsky monument bolo vidno priamo z hotelovej izby, predpokladali sme že to nebude príliš ďaleko … bolo, vyše hodiny cesty pešo. Ale oplatilo sa, na fotke biely dom.

Obr.15.: Washingtonsky monument je naozaj veľký

Obr.16.: Áno, tam sedí sám veľký Lincoln

Obr.17.: Nedostatok spánku

Obr.18.: Chvíľka prekvapenia

Obr.19.: Testovacie kolo

Obr.20.: Národy celého sveta … našli by ste tam indov, japoncov, čínanov, arabov …

Obr.21.: Ázijský kútik

Obr.22.: Taktická porada, zprava Ivan Klimek, Jawwad Nasar a Amr

Obr.23.: Všade vládla úžasná nálada

Obr.24.: Porada organizátorov

Obr.25.: *Nezabudlo sa ani na frekvenčnú analýzu … *

Obr.26.: … alebo sledovanie šumu

Počas celého priebehu súťaže si žiaden tím nemohol byť istý svojim umiestnením. Boli udeľované dve ceny, prvá zameraná na výkon podľa pomeru vlastných doručených packetov a celkového počtu poslaných packetov a cena za design, celkovú invenčnosť stratégie. Každý tím mal vlastnú myšlienku, jedinečnú stratégiu. Konkurencia každého tímu a chuť vyhrať bola cítíť vo vzduchu. Nebudem klamať keď poviem že som pri prezentáciách iných tímov niekedy nemal celkom jasno, o čom to vlastne hovoria, rôzne matematické modely riešené pomocou MATLAB-u atd. “The performance award” nakoniec získal tím University of North Carolina at Charlotte, “The strategy award” – putoval k nám. Áno, ani my sami sme tomu nechceli veriť, o to väčšia bola naša radosť. Je to naozaj tak, naše riešenie ako jediné prezentované bolo priamo nasaditeľné, pokrývalo všetko otázky a efektívne /možno aj efektne :) / riešilo všetky problémy sieti MANET. Je to naozaj veľký úspech nie len pre CNL, nie len pre katedru alebo Technickú Univerzitu, ale pre celý slovenský výzkum ako taký. Dúfam, že tento úspech bude slúžiť ako motivácia pre ďaľších, pretože keď dvaja slovenský študenti mohli vyhrať na sútaži takéhoto významu, prekročiť všetky hranice, všetky očakávania, tak potom už vážne nič nie je nemožné …

Obr.27.: Víťazi idú domov, síce fyzicky úplne na dne ale s pocitom hrdosti a dobre vykonanej práce. Aj vďaka nám budú siete MANET už skoro bežne používané