Jindřich Skupa. University of West Bohemia in Pilsen Department of Computer Science and Engineering Univerzitni Pilsen Czech Republic

University of West Bohemia in Pilsen Department of Computer Science and Engineering Univerzitni 8 30614 Pilsen Czech Republic

Dynamick´ e smˇ erov´ an´ı v s´ıt´ıch s vyuˇ zit´ım predikce Odborná práce ke státn´ı doktorské zkouˇsce

Jindˇrich Skupa

Technical Report No. DCSE/TR-2016-01 April, 2016 Distribution: public

pˇrekryvn´ ych

Technical Report No. DCSE/TR-2016-01 April 2016

Dynamick´ e smˇ erov´ an´ı v s´ıt´ıch s vyuˇ zit´ım predikce

pˇrekryvn´ ych

Jindˇrich Skupa Abstract This technical report consists of the current state of the art in overlay networks and dynamic routing with traffic prediction. Introduction to the overlay networks is followed by routing specifics in overlay networks. Subsequent chapters describe routing metrics and parameters measured in overlay networks. Following chapter introduces time series prediction algorithms and methods. The last chapter brings a description of the further work and the goals of the Ph.D. thesis followed by summary. The work was supported by the UWB grant SGS-2013-029 Advanced Computer and Information Systems. (Pokroˇcilé v´ ypoˇcetn´ı a informaˇcn´ı systémy).

Copies of this report are available on http://www.kiv.zcu.cz/en/research/publications/technical-reports/ or by surface mail on request sent to the following address: University of West Bohemia in Pilsen Department of Computer Science and Engineering Univerzitni 8 30614 Pilsen Czech Republic c Copyright 2016 University of West Bohemia in Pilsen, Czech Republic

Obsah ´ 1 Uvod

2

2 Pˇ rekryvn´ e s´ıtˇ e

3

2.1

Pˇrekryvné s´ıtˇe v Internetu . . . . . . . . . . . . . . . . . . . . . .

3

2.2

Rozdˇelen´ı pˇrekryvn´ ych s´ıt´ı . . . . . . . . . . . . . . . . . . . . . .

4

2.3

Podle topologie . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.4

Podle vyuˇzit´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2.5

Experimentáln´ı prostˇred´ı . . . . . . . . . . . . . . . . . . . . . . .

9

3 Pˇ rekryvn´ e s´ıtˇ e a smˇ erov´ an´ı dat

10

3.1

Skupinové vys´ılán´ı . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.2

CDN s´ıtˇe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.3

P2P s´ıtˇe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

3.4

Zajiˇstˇen´ı kvality sluˇzeb . . . . . . . . . . . . . . . . . . . . . . . .

14

3.5

Anonymizaˇcn´ı s´ıtˇe . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.6

Shrnut´ı smˇerován´ı v pˇrekryvn´ ych s´ıt´ıch . . . . . . . . . . . . . . .

16

4 Smˇ erovac´ı metriky

16

4.1

Sledován´ı a mˇeˇren´ı parametr˚ u v pˇrekryvn´ ych s´ıt´ıch . . . . . . . .

17

4.2

Dalˇs´ı sledovatelné parametry . . . . . . . . . . . . . . . . . . . . .

17

5 Predikce stavu linek a s´ıtˇ e ˇ 5.1 Casov´ e ˇrady a predikce . . . . . . . . . . . . . . . . . . . . . . . .

19 19

5.2

Predikce pomoc´ı model˚ u ARMA . . . . . . . . . . . . . . . . . . .

20

5.3

Predikce pomoc´ı neuronov´ ych s´ıt´ı . . . . . . . . . . . . . . . . . .

22

5.4

Predikce s vyuˇzit´ım teorie chaosu . . . . . . . . . . . . . . . . . .

24

5.5

Dalˇs´ı metody predikce . . . . . . . . . . . . . . . . . . . . . . . .

26

6 Teze disertaˇ cn´ı pr´ ace

27

7 Z´ avˇ er

28

1

1

´ Uvod

Obsahem této odborné práce ke státn´ı doktorské zkouˇsce je popis aktuáln´ıho stavu v oblasti pˇrekryvn´ ych s´ıt´ı (overaly networks) s d˚ urazem na techniky dynamického smˇerován´ı s r˚ uzn´ ymi metrikami, ˇr´ızen´ım kvality pˇrenosu a predikce stavu pˇrekryvné s´ıtˇe a jej´ıch spoj˚ u. Na základˇe tˇechto poznatk˚ u budou definovány teze disertaˇcn´ı práce a smˇer dalˇs´ıho v´ yzkumu. Vzhledem k rostouc´ım nárok˚ um aplikac´ı na rychlost doruˇcován´ı obsahu, minimalizaci zpoˇzdˇen´ı a maximalizaci spolehlivosti, si pˇrekryvné s´ıtˇe z´ıskaly pozornost odborné veˇrejnosti. Pˇrekryvné s´ıtˇe jsou zkoumány s oˇcekáván´ımi optimalizuj´ıc´ımi pˇrenos tak, aby vyhovˇel nárok˚ um aplikac´ı a uˇzivatel˚ u na kvalitu s´ıt’ov´ ych sluˇzeb. Klasické IP s´ıtˇe nejsou schopny tyto poˇzadavky ˇreˇsit dostateˇcnˇe, zvláˇstˇe v globáln´ım prostˇred´ı, kde panuje velká heterogenita a platnost r˚ uzn´ ych nastaven´ı, metrik nebo funkc´ı s´ıtˇe konˇc´ı s hranicemi autonomn´ıch systém˚ u. Pˇrekryvné s´ıtˇe tak vytváˇr´ı prostˇred´ı pro aplikace, kde pro vˇsechny u ´ˇcastn´ıky plat´ı stejná pravidla, pro která je pˇrekryvná s´ıt’ budována. V prvn´ı ˇca´sti bude ˇctenáˇr seznámen s technikou pˇrekryvn´ ych s´ıt´ı a moˇznostmi vyuˇzit´ı, pˇr´ıkladem mohou b´ yt s´ıtˇe pro doruˇcován´ı obsahu (Content Delivery Network, CDN), virtuáln´ı soukromé s´ıtˇe (Virtual Private Network, VPN), anonymizaˇcn´ı s´ıtˇe (The Onion Routing, TOR), s´ıtˇe pro zajiˇstˇen´ı spolehlivosti a kvality sluˇzeb (Quality of Service, QoS) a zajiˇstˇen´ı efektivity pˇrenosu (skupinové vys´ılán´ı, multicasting). Z v´ yˇctu moˇzn´ ych pouˇzit´ı je patrné, ˇze pˇrekryvné s´ıtˇe nalézaj´ı ˇsiroké uplatnˇen´ı v globáln´ı internetové s´ıti a jejich vyuˇzit´ı je stále aktuáln´ı. Jejich hlavn´ı v´ yhodou je moˇznost pouˇzit´ı r˚ uzn´ ych technik (QoS, smˇerován´ı) a moˇznost provozu samostatn´ ych sluˇzeb (doruˇcován´ı obsahu), které nen´ı moˇzné v bˇeˇzn´ ych s´ıt´ıch ’ zajiˇst ovat dostateˇcnˇe efektivnˇe nebo pro nˇe neexistuje pˇr´ımá globáln´ı podpora. Ve druhé ˇcásti jsou popsány moˇznosti dynamického smˇerován´ı v pˇrekryvn´ ych s´ıt´ıch podle jejich architektury a uˇzit´ı vˇcetnˇe vyuˇz´ıvan´ ych algoritm˚ u. Uvedeny jsou i návrhy moˇzného dalˇs´ıho vyuˇzit´ı dynamického smˇerován´ı. Dynamické smˇerován´ı v pˇrekryvn´ ych s´ıt´ıch prob´ıhá na základˇe mˇeˇren´ ych metrik a jejich následném vyhodnocen´ı a nalezen´ı nejkratˇs´ı vzdálenosti - minimalizace ceny pˇrenosu. Tato ˇca´st dále obsahuje i specifika dynamického smˇerován´ı právˇe v pˇrekryvn´ ych s´ıt´ıch a jejich odliˇsnost od klasick´ ych s´ıt´ı. Následuj´ıc´ı ˇca´st práce se vˇenuje predikci s´ıt’ového provozu, zat´ıˇzen´ı linek a jejich dalˇs´ıch vlastnost´ı v ˇcase. Vlastnosti s´ıt’ového provozu jsou pˇredstaveny jako ˇcasové ˇrady, které je moˇzné predikovat. Pˇredstaveny jsou nejbˇeˇznˇejˇs´ı postupy pro predikci tˇechto ˇrad a dále jsou prezentovány jejich vlastnosti a principy fungován´ı. Posledn´ı ˇcást´ı je shrnut´ı mé ˇcinnosti v pˇredstavené oblasti. Dále jsou pˇredstaveny c´ıle budouc´ı disertaˇcn´ı práce a základn´ı pˇredpoklady pro jej´ı tvorbu.

2

2

Pˇ rekryvn´ e s´ıtˇ e

Pˇrekryvné s´ıtˇe pracuj´ı nad definovanou podkladovou vrstvou, v prostˇred´ı dneˇsn´ıch s´ıt´ı je tou vrstvou protokol IP, pˇr´ıpadnˇe nˇekter´ y z vyˇsˇs´ıch transportn´ıch protokol˚ u TCP nebo UDP. Tento základn´ı pˇredpoklad nemus´ı platit pro vˇsechny s´ıtˇe, pˇrekryvné s´ıtˇe lze vytváˇret i nad protokoly niˇzˇs´ıch vrstev, pˇr´ıkladem je Multiprotocol Label Switching (MPLS)[46]. Pˇrekryvné s´ıtˇe jsou navrhovány a budovány za c´ılem rozˇs´ıˇrit aktuáln´ı funkˇcnost existuj´ıc´ıch s´ıt´ı. T´ım m˚ uˇze b´ yt efektivn´ı vyuˇzit´ı zdroj˚ u podkladové s´ıtˇe, zprostˇredkován´ı pˇremostˇen´ı jednotliv´ ych s´ıt´ı, které nejsou schopny mezi sebou bˇeˇznˇe nˇekterou sluˇzbu podporovat (multicasting). Dále také umoˇzn ˇuj´ı obcházet bezpeˇcnostn´ı a systémová nastaven´ı dan´ ych s´ıt´ı (bezpeˇcnostn´ı politika je natolik restriktivn´ı, ˇze omezuje uˇzivatele v jejich ˇ pˇr´ıstupu k funkc´ım stávaj´ıc´ı s´ıtˇe). Casto jsou pˇrekryvné s´ıtˇe budovány za u ´ˇcelem z´ıskat pro uˇzivatele jistou v´ yhodu, kterou by v klasické IP s´ıti nemˇel, vzhledem k pˇr´ıstupu nejlepˇs´ı snahy“ doruˇcit data, nebo poruˇsen´ı principu s´ıt’ové neutra” lity. Princip fungován´ı pˇrekryvn´ ych s´ıt´ı je oznaˇcován jako sobeck´ y, jejich c´ılem je vyuˇz´ıt maximum dostupn´ ych prostˇredk˚ u podkladové s´ıtˇe pro své uˇzivatele a sluˇzby. Existuj´ı r˚ uzné pˇr´ıstupy k pˇrekryvn´ ym s´ıt´ım. Podle jednoho je pouˇzit´ı dané pˇrekryvné s´ıtˇe pouze doˇcasné, do doby neˇz bude technologie pˇripravená a adaptovaná do podkladové s´ıtˇe, napˇr´ıklad 6BONE zavád´ı IPv6 tunely pˇres existuj´ıc´ı s´ıtˇe IPv4. Druh´ y povaˇzuje pˇrekryvné s´ıtˇe za svébytnou technologii, která má dlouhodobé uplatnˇen´ı a ˇcasto jej´ı funkce ani nen´ı moˇzné uspokojivˇe zakomponovat jako standard do vrstev podkladové s´ıtˇe (P2P, TOR Onion routing, VPN, QoS).

2.1

Pˇ rekryvn´ e s´ıtˇ e v Internetu

Existence a realizace pˇrekryvn´ ych s´ıt´ı v Internetu nen´ı nová a jeho prostˇred´ı funguje celá ˇrada pˇrekryvn´ ych s´ıt´ı r˚ uzného typu a urˇcen´ı. Dneˇsn´ı internet ostatnˇe vznikl jako pˇrekryvná s´ıt’ nad podkladovou telefonn´ı s´ıt´ı, následnˇe se vyvinul do samostatnˇe funguj´ıc´ı infrastruktury a dnes jej telekomunikaˇcn´ı sluˇzby zaˇc´ınaj´ı vyuˇz´ıvat jako podkladovou s´ıt’ pro pˇrenos hlasu a videa. Aktuálnˇe vˇetˇsina pˇrekryvn´ ych s´ıt´ı vyuˇz´ıvá Internet jako podkladovou vrstvu pro realizaci vlastn´ıch sluˇzeb. Struktura a velikost pˇrekryvn´ ych s´ıt´ı také nen´ı nijak omezena a záleˇz´ı na jej´ım návrhu a plánovaném vyuˇzit´ı. Struktura pˇrekryvn´ ych s´ıt´ı ˇcasto záleˇz´ı na jej´ım primárn´ım urˇcen´ı, typick´ ym pˇr´ıpadem jsou P2P s´ıtˇe uspoˇra´dané napˇr´ıklad do struktury stromu, kde je struktura vystavˇena tak, aby bylo nalezen´ı dat na co nejmenˇs´ı poˇcet skok˚ u.

3

2.2

Rozdˇ elen´ı pˇ rekryvn´ ych s´ıt´ı

Pˇrekryvné s´ıtˇe lze klasifikovat podle r˚ uzn´ ych kritéri´ı. Jedn´ım z nich m˚ uˇze b´ yt podle topologie (P2P, centralizované, hierarchické), dalˇs´ı podle vyuˇzit´ı, urˇcen´ı nebo poskytovan´ ych sluˇzeb (pˇrechod od IPv4 k IPv6 - 6BONE, anonymizace TOR, multicasting MBONE, u ´loˇziˇstˇe - CAN, DHT).

2.3

Podle topologie

Základem kaˇzdé pˇrekryvné s´ıtˇe jsou jednotlivé uzly podkladové s´ıtˇe. Jednotlivé kroky cesty mezi uzly A a B jsou pro pˇrekryvnou s´ıt´ı povaˇzovány za jeden spoj. Obecnˇe mohou uzly komunikovat kaˇzd´ y s kaˇzd´ ym - tvoˇr´ı u ´pln´ y orientovan´ y graf, ’ pro dalˇs´ı pouˇzit´ı se pak dle u ´ˇcelu organizuje pˇrekryvná s´ıt do konkrétn´ı topologie. Tato transformace nemus´ı prob´ıhat vˇzdy a pokud prob´ıhá, pak m˚ uˇze m´ıt charakter trval´ y (pevné uspoˇrádán´ı) nebo doˇcasn´ y (dynamické uspoˇra´dán´ı podle aktuáln´ıch potˇreb). Pˇrekryvné s´ıtˇe se nejˇcastˇeji pˇreuspoˇra´dávaj´ı za u ´ˇcelem poskytnut´ı lepˇs´ıch sluˇzeb a vyvaˇzován´ı zátˇeˇze - napˇr´ıklad ˇskálován´ı poskytovan´ ych zdroj˚ u, distribuce a redistribuce poskytovan´ ych sluˇzeb nebo vyhledáván´ı a replikace obsahu. Ke zmˇenˇe struktury s´ıtˇe m˚ uˇze doj´ıt také vlivem vnˇejˇs´ı zmˇeny, napˇr´ıklad zmˇena parametr˚ u propojovac´ıch linek nebo parametr˚ u jednotliv´ ych uzl˚ u nebo také pˇridán´ım nového uzlu. Nˇekteré pˇrekryvné s´ıtˇe mohou m´ıt strukturu pevnou a po dobu jej´ıho fungován´ı nemˇennou. Vzhledem k tomu, ˇze topologie pˇrekryvné s´ıtˇe nen´ı nijak závislá na fyzické topologii nebo jej´ıch moˇznostech, m˚ uˇze se jednat o bˇeˇzné topologie z klasick´ ych s´ıt´ı, peer-to-peer, hvˇezda (centráln´ı uzel, pˇres kter´ y ostatn´ı komunikuj´ı, nebo má centráln´ı databázi uzl˚ u, zdroj˚ u atp.), strom (stromová struktura jednotliv´ ych komunikaˇcn´ıch spoj˚ u, napˇr. multicasting), kruh, kombinace pˇredchoz´ıch, matice nebo n-rozmˇerná kostka (DHT, CAN). Jaké topologie se pouˇz´ıvá pro jaké urˇcen´ı, bude popsáno v následuj´ıc´ıch kapitolách popisuj´ıc´ıch existuj´ıc´ı s´ıtˇe.

2.4

Podle vyuˇ zit´ı

Jak bylo jiˇz uvedeno v pˇredchoz´ıch sekc´ıch, vyuˇzit´ı pˇrekryvn´ ych s´ıt´ı je ˇsiroké. Vytvoˇren´ım pˇrekryvné s´ıtˇe je moˇzné sledovat nebo poskytovat mnoho s´ıt’ov´ ych sluˇzeb. Od klasick´ ych parametr˚ u pˇrenosu jako je doruˇcen´ı dat, rychlost komunikace, spolehlivost, zaruˇcen´ı kvality sluˇzeb, pˇres sluˇzby koncov´ ych uzl˚ u poskytuj´ıc´ı u ´loˇzn´ y prostor nebo v´ ypoˇcetn´ı v´ ykon aˇz po sluˇzby slouˇz´ıc´ı k anonymizaci uˇzivatel˚ u a ˇsifrován´ı komunikace. Pˇrekryvná s´ıt’ m˚ uˇze sledovat v´ıce tˇechto c´ıl˚ u zároveˇ n nebo nˇekteré jsou prostˇredkem pro dosaˇzen´ı jiného, napˇr´ıklad: • komunikaˇcn´ı infrastruktura,

4

• • • • • • • 2.4.1

spolehlivost doruˇcen´ı dat, kvalita spojen´ı (latence, propustnost, stabilita), u ´loˇziˇstˇe nebo poskytován´ı dat, poskytován´ı v´ ypoˇcetn´ıho v´ ykonu, poskytován´ı aplikaˇcn´ıch sluˇzeb, bezpeˇcnost, anonymizace. Komunikaˇ cn´ı infrastruktura - smˇ erov´ an´ı

Pˇrekryvná s´ıt’, jej´ımˇz urˇcen´ım je nab´ızet komunikaˇcn´ı infrastrukturu, m˚ uˇze sledovat nˇekolik r˚ uzn´ ych metrik. Napˇr´ıklad je navrˇzena za u ´ˇcelem zv´ yˇsen´ı spolehlivosti doruˇcen´ı dat, to provád´ı tak, ˇze detekuje a propaguje v´ ypadek rychleji neˇz klasické IP protokoly. Bezodkladnˇe zajiˇst’uje alternativn´ı záloˇzn´ı cestu. Internetov´ y smˇerovac´ı protokol - Border Gateway Protocol (BGP) pro smˇerován´ı mezi autonomn´ımi systémy (AS) má vzhledem k rozlehlosti dneˇsn´ıho internetu relativnˇe dlouhé konvergenˇcn´ı ˇcasy, neˇz je v´ ypadek detekován a náhradn´ı cesty jsou pˇrepoˇc´ıtány v celé s´ıti. C´ılem návrhu BGP byla hlavnˇe stabilita a schopnost smˇerovat rozlehlé s´ıtˇe. Pˇrekryvné s´ıtˇe pracuj´ı obyˇcejnˇe s menˇs´ımi smˇerovac´ımi tabulkami, mohou pˇredpoˇc´ıtávat alternativn´ı cesty a rychleji detekuj´ı v´ ypadky. Doba v´ ypadku je t´ımto postupem minimalizována a koncové uzly jej nemus´ı b´ yt schopny ani detekovat. Pˇrekryvná s´ıt’ zajist´ı transparentn´ı pˇresmˇerován´ı provozu. Kromˇe rychlého pˇrep´ınán´ı s´ıt’ov´ ych cest m˚ uˇze jej´ı konstrukce b´ yt navrˇzena tak, ˇze provád´ı korekci podkladov´ ych protokol˚ u, kde nastaven´ı metrik a pouˇzit´ ych cest nemus´ı b´ yt z hlediska s´ıt’ového provozu optimáln´ı, ale mohou b´ yt ovlivnˇeny ekonomick´ ymi nebo politick´ ymi faktory. Smˇerován´ı provozu v internetu je v´ ysledkem dvoustrann´ ych dohod jednotliv´ ych ’ s´ıt ov´ ych operátor˚ u nebo politikou pˇredávac´ıch (peeringov´ ych) center. Nˇekteré linky tak mohou b´ yt znev´ yhodnˇené napˇr´ıklad kv˚ uli jejich provozn´ı cenˇe. Nˇekteré linky mohou b´ yt také vyuˇz´ıvány pro r˚ uzné specifické u ´ˇcely a jejich parametry ˇ mohou b´ yt vyuˇzity i jinak. Rada linek je také privátn´ıch, pˇrenáˇs´ı napˇr´ıklad data mezi poboˇckami a nepouˇz´ıvá se pro smˇerován´ı veˇrejného datového provozu. Pˇrekryvná s´ıt’ je schopna tento stav efektivnˇe pˇrekr´ yt takov´ ymi cestami, které jsou skuteˇcnˇe pro dan´ y typ provozu a jej´ı konfiguraci v´ yhodné. Pˇrekryvné s´ıtˇe mohou také reagovat na aktuáln´ı stav linek, jejich vyuˇzit´ı a dostupnou propustˇ nost. Casto zajiˇst’uj´ı ˇr´ızen´ı kvality pˇrenosu a rezervaci zdroj˚ u po trase, hojnˇe jsou pak vyuˇz´ıvány pˇri pˇrenosu proudu dat audio-video (VoIP, IPTV). Pˇrekryvné s´ıtˇe mohou také umoˇznit mobilitu zaˇr´ızen´ı. Adresován´ı uzl˚ u v Internetu je realizováno IP adresami, které jsou pˇridˇelované v rámci s´ıt´ı. Aby byl klient pod danou IP adresou dostupn´ y, mus´ı v dané s´ıti fyzicky existovat, nebo tam m´ıt 5

zástupce. Pˇrekryvné s´ıtˇe umoˇzn´ı spojen´ı i s uzlem, kter´ y je aktuálnˇe v jiné s´ıti. V klasické IP s´ıti to lze realizovat bud’ kombinac´ı pˇrekladu adres (NAT) v kombinaci napˇr´ıklad s virtuáln´ı privátn´ı s´ıt´ı - VPN (dle potˇreby). Varianta s NAT bez VPN lze pouˇz´ıt v pˇr´ıpadech, kdy známe nové um´ıstˇen´ı klienta, pˇri pouˇzit´ı VPN se statickou adresou lze tuto konkrétn´ı adresu pˇrekládat nebo smˇerovat do VPN bez ohledu na to, kde mobiln´ı uzel zrovna je. Dalˇs´ım ˇreˇsen´ım je právˇe vyuˇzit´ı pˇrekryvné s´ıtˇe, kdy IP adresa je sluˇzbou pˇrekryvné s´ıtˇe a je skrze n´ı smˇerována k mobiln´ımu uzlu. Oproti pouˇzit´ı klasické VPN lze v pˇrekryvné s´ıti vyuˇz´ıt jej´ıch sluˇzeb vyuˇz´ıvaj´ıc´ı optimalizace datov´ ych tras jak bylo uvedeno v prvn´ı ˇca´sti sekce. 2.4.2

Ukl´ ad´ an´ı a sd´ılen´ı dat

Pˇrekryvné s´ıtˇe navrˇzené pro ukládán´ı dat lze rozdˇelit podle zp˚ usobu uˇzit´ı na klasické P2P s´ıtˇe urˇcené pro sd´ılen´ı velk´ ych soubor˚ u a na content delivery networks, které ukládaj´ı obyˇcejnˇe velké mnoˇzstv´ı menˇs´ıch soubor˚ u. Klasické P2P s´ıtˇe pro sd´ılen´ı soubor˚ u také nekladou vysoké nároky na rychlost pˇrenosu. Proti tomu CDN jsou zˇrizovány právˇe za u ´ˇcelem distribuovat data k uˇzivateli na co nejkratˇs´ı vzdálenosti a co nejrychleji (geografická dostupnost dat, poplatky za tranzitn´ı pˇrenosy, zpoˇzdˇen´ı a rychlost pˇrenosu). Dalˇs´ım rozd´ılem je, ˇze v pˇr´ıpadˇe P2P s´ıt´ı pro sd´ılen´ı soubor˚ u je uˇzivatel této s´ıtˇe jej´ı souˇcást´ı, je ˇclenem s´ıtˇe a také poskytuje svoje zdroje ostatn´ım. V pˇr´ıpadˇe CDN pˇristupuje uˇzivatel ke zdroj˚ um s´ıtˇe zprostˇredkovanˇe, pˇres hraniˇcn´ı uzly CDN s´ıtˇe. Klasické P2P s´ıtˇe, oznaˇcované jako prvn´ı generace, napˇr. Napster, vˇetˇsinou obsahovaly jeden centráln´ı uzel, kter´ y udrˇzoval informace o vˇsech sd´ılen´ ych datech a jejich um´ıstˇen´ı. Tento pˇr´ıstup se ovˇsem ukázal jako nedokonal´ y a naivn´ı, protoˇze centráln´ı uzel, byt’ replikovan´ y, se pro s´ıt’ stává kritick´ ym a v pˇr´ıpadˇe jeho v´ ypadku je ochromen provoz celé s´ıtˇe. Proto byly navrˇzené P2P s´ıtˇe druhé generace, které eliminuj´ı tento centráln´ı prvek a vˇse je plnˇe distribuované, pˇr´ıkladem tˇechto s´ıt´ı jsou s´ıtˇe vyuˇz´ıvaj´ıc´ı distribuovanou hashovac´ı tabulku (DHT), jejichˇz implementac´ı existuje celá ˇrada, CAN (Content Addressable Network), Chord, Kademlia, Pastry, Riak, Tapestry. Nˇekter´ ym bude vˇenován prostor v následuj´ıc´ıch kapitolách. Základn´ı princip fungován´ı DHT je popsán na obrázku 1. Bloku dat je na základˇe hashovac´ı funkce pˇriˇrazen kl´ıˇc, kter´ y zároveˇ n urˇcuje, na kter´ ych uzlech budou data uloˇzena. Uzly maj´ı na základˇe svého unikátn´ıho identifikátoru pˇriˇrazeno um´ıstˇen´ı v prostoru kl´ıˇc˚ u stejnˇe jako data. Kl´ıˇce jak uzl˚ u, tak dat jsou ze stejného prostoru a udávaj´ı jejich polohu. Prostor je podle konkrétn´ı s´ıtˇe reprezentován v 2D prostoru nebo v n-dimenzionáln´ıch u ´tvarech (kostkách). Prostor kl´ıˇc˚ u lze reprezentovat i stromem. Ukládaná data jsou pˇrenesena na nˇekter´ y ze znám´ ych uzl˚ u (soused˚ u), kter´ y je nejbl´ıˇze ke kl´ıˇci dat (dle metriky daného prostoru). Ten pˇrenese data na dalˇs´ıho souseda bl´ıˇze ke kl´ıˇci. V koneˇcném ˇcase jsou data uloˇzena 6

na uzlu, kter´ y je globálnˇe nejbl´ıˇze kl´ıˇci dat. Pˇr´ıstup k dat˚ um se pak dˇeje stejn´ ym zp˚ usobem. Pokud chce uzel z´ıskat daná data, kontaktuje svého souseda nejbl´ıˇze kl´ıˇci, ten vyhledá dalˇs´ıho svého souseda bl´ıˇze kl´ıˇci nebo poskytne data ze svého u ´loˇziˇstˇe. Tento zp˚ usob smˇerován´ı b´ yvá oznaˇcován jako smˇerován´ı kl´ıˇcem (keybased routing). Seznam soused˚ u je obyˇcejnˇe jednoduch´ y slovn´ık obsahuj´ıc´ı pozici znám´ ych uzl˚ u a jejich IP adresy, nesouvis´ı nijak s bl´ızkost´ı uzl˚ u na s´ıt’ové u ´rovni. Pˇrenosové cesty trasované k dat˚ um t´ımto zp˚ usobem ovˇsem nemus´ı b´ yt optimáln´ı z pohledu pˇrenosové rychlosti. Seznam soused˚ u je moˇzné udrˇzovat systematicky tak, aby sousedé byly vyb´ıráni podle vzájemné pˇrenosové rychlosti (pˇrenos dat) nebo za u ´ˇcelem rovnomˇerného pokryt´ı prostoru kl´ıˇc˚ u (rychlost vyhledáván´ı). Po nalezen´ı uzlu, kter´ y má data právˇe k dispozici, lze pouˇz´ıt smˇerován´ı pro pˇrenos dat z pˇredchoz´ı kapitoly, kdy sledujeme dosaˇzen´ı maximáln´ı pˇrenosové rychlosti. Distribuce um´ıstˇen´ı a seznamu soused˚ u m˚ uˇze b´ yt objektem vˇedeckého zkoumán´ı.

Obrázek 1: DHT Oproti P2P s´ıt´ım slouˇz´ı CDN s´ıtˇe k pˇrenosu a replikaci dat co nejbl´ıˇze koncov´ ym uˇzivatel˚ um, na periferii internetové s´ıtˇe. Jedná se pˇredevˇs´ım o geografickou distribuci a replikaci dat, kdy c´ılem je um´ıstit repliky co nejbl´ıˇze koncov´ ym uˇzivatel˚ um na základˇe lokace. Nejˇcastˇeji jsou pouˇz´ıvané v pˇr´ıpadˇe globáln´ıch sluˇzeb, distribuce aktualizac´ı operaˇcn´ıho systému nebo pˇr´ıloh sociáln´ıch s´ıt´ı a dalˇs´ıch sluˇzeb. Z jednoho zdrojového serveru jsou data pˇrenáˇsena do CDN tak, aby k nim mˇeli uˇzivatelé co nejbl´ıˇze, jak z pohledu geografického (kontinent, stát), tak z pohledu s´ıt’ového (minimalizace zpoˇzdˇen´ı, maximalizace rychlosti pˇrenosu). CDN pˇrekryvná s´ıt’ tak b´ yvá obyˇcejnˇe organizována jako strom, jak znázorˇ nuje obrázek 2. Kdy jsou bud’ metodou pull (stahován´ım z centráln´ıho serveru na CDN) nebo push (uploadem z centráln´ıho serveru do CDN) distribuována data. Metoda pull pˇredstavuje, ˇze pokud pˇrijde poˇzadavek na obsah s dan´ ym kl´ıˇcem, tak server vyhledá nadˇrazen´ y server u kterého poˇza´dá o data. Postup se opakuje aˇz k serveru, kter´ y má data v lokáln´ım u ´loˇziˇsti nebo k centráln´ımu serveru. Poprvé 7

staˇzená data se pak uchovaj´ı na hraniˇcn´ım serveru a to bud’ doˇcasnˇe (cache) nebo trvale (replika). Push metoda spoˇc´ıvá v tom, ˇze zdrojov´ y centráln´ı server provede zápis na vˇsechny pˇr´ımo podˇr´ızené servery a ty poskytuj´ı data dále stejn´ ym zp˚ usobem. Zdrojov´ y server pak spravuje i trvalost cache nebo replik. Doruˇcovac´ı strom pro CDN je opˇet tvoˇren logicky, nikoli apriori podle pˇrenosov´ ych kapacit nebo rychlosti. Uˇzivatelé taktéˇz nepracuj´ı pˇr´ımo s pˇrekryvnou s´ıt´ı CDN, ale pˇristupuj´ı pouze k jej´ım koncov´ ym uzl˚ um, které data z´ıskávaj´ı skrze privátn´ı pˇrekryvnou s´ıt’. Optimáln´ı struktura a tvorba stromu m˚ uˇze b´ yt objektem vˇedeckého zájmu.

Obrázek 2: CDN

2.4.3

Bezpeˇ cnost a anonymizace

Dalˇs´ı kategori´ı pˇrekryvn´ ych s´ıt´ı podle pouˇzit´ı mohou b´ yt s´ıtˇe urˇcené k zajiˇstˇen´ı bezpeˇcnosti pˇrenáˇsen´ ych dat nebo anonymizace u ´ˇcastn´ık˚ u spojen´ı. V tomto ohledu lze oznaˇcit i klasické VPN a tunely (IPSec, PPTP, L2TP) za reprezentanty pˇrekryvn´ ych s´ıt´ı, i kdyˇz se vlastnˇe nejedná o nov´ y typ s´ıt´ı z pohledu k pˇr´ıstupu k adresován´ı, smˇerován´ı, ukládán´ı nebo distribuci dat. Tyto s´ıtˇe vytváˇr´ı IP nebo linkové s´ıtˇe nad existuj´ıc´ı infrastrukturou IP s´ıt´ı. V takto vytvoˇren´ ych s´ıt´ıch se pak pouˇz´ıvaj´ı klasické postupy a protokoly jako v bˇeˇzn´ ych s´ıt´ı, pˇrekryvná s´ıt’ slouˇz´ı jen k pˇremostˇen´ı a zabezpeˇcen´ı linek nebo s´ıt´ı s nedostateˇcn´ ymi parametry. Bezpeˇcnost implementuj´ı pomoc´ı pouˇzitého ˇsifrován´ı pˇrenáˇsen´ ych dat a

8

smˇerován´ı vˇcetnˇe pouˇzit´ ych protokol˚ u se nijak neliˇs´ı od protokol˚ u pouˇzit´ ych pro IP s´ıtˇe, lze je i volnˇe propojovat se zbylou IP infrastrukturou. Data = sif raA (hlavicka + sif raB (hlavicka + sif raC (payload)))

(1)

Vhodnˇejˇs´ım reprezentantem pro popis fungován´ı bezpeˇcnostn´ıch pˇrekryvn´ ych s´ıt´ı je The Onion Routing protokol (TOR)[7]. Hlavn´ı u ´lohou TOR je skr´ yt uˇzivatele pˇred okoln´ım svˇetem a zajistit anonymn´ı pˇrenos informac´ı. K tomu se pouˇz´ıvá The Onion Routing protokol, stejnˇe jako plátky cibule jsou datové pakety obalované a ˇsifrované pˇres sebe (rovnice. 1). Kaˇzd´ y server, kter´ y cestou data zpracovává, odebere jednu vrstvu ˇsifrován´ı, pˇreˇcte si hlaviˇcku a podle n´ı poˇsle data dále aˇz na v´ ystupn´ı server, kde jsou rozˇsifrovaná data odeslána na c´ılov´ y server (obr. 3). Cel´ y proces anonymizace prob´ıhá tak, ˇze klient si z adresáˇre server˚ u vyˇza´dá seznam uzl˚ u. Klient následnˇe vybere náhodnou posloupnost uzl˚ uk zam´ yˇslenému c´ıli. Pˇres tuto posloupnost vytvoˇr´ı okruh, kde si s kaˇzd´ ym uzlem vymˇen´ı kl´ıˇce pro ˇsifrován´ı dat. Následnˇe podle postupu, popsaného vzorcem 1, zaˇsifruje sv˚ uj obsah a poˇsle do s´ıtˇe. Kaˇzd´ y z uzl˚ u (Onion router, OR) rozˇsifruje pˇr´ısluˇsnou slupku a podle pˇreˇctené hlaviˇcky pos´ılá zprávy dále. T´ımto postupem ˇ adn´ je zajiˇstˇeno, ˇze ˇzádn´ y z uzl˚ u, kromˇe v´ ystupn´ıho, nezná obsah dat klienta. Z´ y z uzl˚ u také nezná celou cestu v pˇrekryvné s´ıti. Kromˇe posledn´ıho uzlu nen´ı nikomu znám ani c´ıl komunikace. Vytvoˇren´ y okruh je v cibulovém smˇerován´ı bud’ po nˇejakém ˇcase nebo objemu dat pˇreruˇsen a následnˇe se zakládá jin´ y.

Obrázek 3: Smˇerován´ı v s´ıti TOR Tuto základn´ı techniku lze pro zt´ıˇzen´ı vystopován´ı komunikuj´ıc´ıch stran rozˇs´ıˇrit, napˇr´ıklad v rámci jednoho streamu se m˚ uˇze vyuˇz´ıvat v´ıce disjunktn´ıch cest, 9

v´ ystupn´ı server pakety seskládá a poˇsle. Také je moˇzné poˇrad´ı pˇredávan´ ych paket˚ u pˇri pˇrenosu pozmˇenit - zam´ıchat jejich poˇrad´ım, pˇridávat k pˇrepos´ılán´ı náhodné zpoˇzdˇen´ı atp. Dalˇs´ı, dnes aktuáln´ı techniku, pouˇz´ıvá s´ıt’ Vuvuzela [39], která zvyˇsuje zabezpeˇcen´ı proti anal´ yze provozu, odes´ılaná data maskuje náhodn´ ym ˇsumem. Aktuálnˇe je s´ıt’ pouˇzitelná pouze pro jednoduchou textovou komunikace, protoˇze zpoˇzdˇen´ı dosahuje aˇz des´ıtek vteˇrin. Vzhledem k tomu, ˇze primárn´ım c´ılem anonymizaˇcn´ı pˇrekryvné s´ıtˇe je anonymizace, smˇerován´ı prob´ıhá zcela zámˇernˇe náhodnˇe, pak veˇskeré operace pro optimalizaci zpoˇzdˇen´ı nebo pˇrenosové rychlosti jsou na ˇskodu, protoˇze by vnˇejˇs´ımu u ´toˇcn´ıkovi umoˇzn ˇovaly modifikovat smˇerován´ı takov´ ym zp˚ usobem, aby cel´ y okruh byl sestaven pˇres jeho uzly. Modifikace by spoˇc´ıvala v jednoduchém ovlivˇ nován´ı stavu jednotliv´ ych linek, tak aby bylo v´ yhodnˇejˇs´ı poslat data jednou konkrétn´ı cestou. Zpoˇzdˇen´ı a propustnost takov´ ych s´ıt´ı je tedy horˇs´ı neˇz bˇeˇzná pˇr´ımá komunikace. Dalˇs´ım druhem s´ıt´ı v této skupinˇe jsou s´ıtˇe, které podle jejich autor˚ u bojuj´ı proti cenzuˇre, ˇcasto se stávaj´ı u ´toˇciˇstˇem kybernetick´ ych krimináln´ık˚ u“. C´ılem tˇechto ” s´ıt´ı je opˇet anonymizovat obˇe strany komunikace a zajistit necenzurovan´ y pˇr´ıstup k dat˚ um. Tyto s´ıtˇe funguj´ı ˇca´steˇcnˇe jako P2P s´ıtˇe pro sd´ılen´ı soubor˚ u a ˇcásteˇcnˇe také jako cache obsahu. Jedn´ım z rozˇs´ıˇren´ ych zástupc˚ u je Freenet[4].

2.5

Experiment´ aln´ı prostˇ red´ı

Vˇetˇsina vlastnost´ı pˇrekryvn´ ych s´ıt´ıch je patrná a mˇeˇritelná pouze ve vˇetˇs´ım mˇeˇr´ıtku globáln´ıho internetu. Vytvoˇrit si soukromé testovac´ı prostˇred´ı nebo simulaci tak rozsáhl´ ych systém˚ u by nebylo v˚ ubec jednoduché. Proto v roce 2003 vznikl PlanetLab [36][25][24], jehoˇz ˇclenem je i CESNET [2]. PlanetLab je experimentáln´ı s´ıt’ dostupn´ ych uzl˚ u napˇr´ıˇc vˇsemi svˇetad´ıly, tak aby pokr´ yvala vˇetˇsinu Internetu. Je primárnˇe urˇcená pro v´ yzkum, v´ yvoj a testován´ı nov´ ych internetov´ ych protokol˚ u, distribuovan´ ych systém˚ u a s´ıt’ov´ ych sluˇzeb. V rámci PlanetLabu aktuálnˇe prob´ıhá v´ yvoj a testován´ı následuj´ıc´ıch aplikac´ı OceanStore[18], CoralCDN[10], projekt RON[1] (Resilient Overlay Network), projekt DHARMA[22] (Distributed Home Agent for Remote Mobile Access) a dalˇs´ıch.

10

3

Pˇ rekryvn´ e s´ıtˇ e a smˇ erov´ an´ı dat

V této kapitole budou popsány reálné pˇr´ıpady uˇzit´ı pˇrekryvn´ ych s´ıt´ı a podrobnˇe rozebrány zp˚ usoby smˇerován´ı dat v nich. Jak´ ym zp˚ usobem se pˇrekryvná s´ıt’ sestavuje, jakou pouˇz´ıvá topologii, na základˇe jak´ ych metrik a jak funguje smˇerován´ı. Jaké jsou pˇredpoklady a nároky pro smˇerován´ı.

3.1

Skupinov´ e vys´ıl´ an´ı

Z historického hlediska lze ˇr´ıci, ˇze jedny z prvn´ıch pˇrekryvn´ ych s´ıt´ı v internetu byly s´ıtˇe implementuj´ıc´ı multicasting[21][8] nad IP protokolem. Pˇrestoˇze témˇeˇr vˇsechny produkˇcn´ı smˇerovaˇce v internetu podporovaly a podporuj´ı multicasting, tak na vˇetˇsinˇe je jeho podpora vypnuta, proto skupinové vys´ılán´ı v praxi funguje pouze v rámci jednoho autonomn´ıho systému (AS), kde organizace ˇcasto multicasting podporuj´ı a vyuˇz´ıvaj´ı (telekonference, vys´ılán´ı obsahu, IPTV atp.). Pˇr´ınosy pouˇzit´ı skupinového vys´ılán´ı pro optimalizaci pˇrenáˇsen´ ych dat jsou zˇrejmé jak ukazuje obrázek 4, data se v s´ıti dan´ ym smˇerem ˇs´ıˇr´ı pouze jednou, ˇ r´ı se t´ım jak pˇrenos dat, tak ne jako v pˇr´ıpadˇe pouˇzit´ı unicastu v´ıcenásobnˇe. Setˇ pˇrenosové pásmo, ale i zat´ıˇzen´ı vys´ılac´ıch server˚ u, tak smˇerovaˇc˚ u po cestˇe. Pˇri pouˇzit´ı skupinového vys´ılán´ı je tˇreba ˇreˇsit dva problémy. Jedn´ım je udrˇzován´ı skupiny - seznam pˇr´ıjemc˚ u, kter´ ym je vys´ılán´ı adresováno, druh´ ym je obsluha doruˇcen´ı dat do dan´ ych koncov´ ych uzl˚ u. Stejnˇe jako v pˇr´ıpadˇe doruˇcován´ı multicastu v IP s´ıt´ı je tˇreba i v pˇrekryvné s´ıti vytvoˇrit doruˇcovac´ı strom. Strom má koˇren v uzlu, kter´ y poskytuje dan´ y proud/generuje data a postupnˇe je vytváˇrena minimáln´ı kostra grafu vˇsech uzl˚ u skupiny. Implementace multicastu pomoc´ı pˇrekryvné s´ıtˇe dává moˇznost zavést multicast i do s´ıt´ı, kde nen´ı podporován. M´ısto pouˇzit´ı IP smˇerovaˇc˚ u smˇeruje pˇrekryvná ’ s´ıt data pˇres vlastn´ı uzly. Doruˇcovac´ı strom je pak tvoˇr´ı napˇr´ıklad pomoc´ı hladového algoritmu pro hledán´ı minimáln´ı kostry grafu. Pˇrekryvná s´ıt’ je reprezentována u ´pln´ ym grafem (kaˇzd´ y uzel je spojen´ y s kaˇzd´ ym, mimo speciáln´ı pˇr´ıpady a v´ ypadky). Tvorba prob´ıhá tak, ˇze smˇerem od koˇrene pˇridáváme ty hrany, které maj´ı nejmenˇs´ı ohodnocen´ı. Minimáln´ı kostru lze také naj´ıt obrácen´ ym zp˚ usobem a to tak, ˇze z grafu postupnˇe odeb´ıráme hrany s nejvˇetˇs´ım ohodnocen´ım a kontrolujeme souvislost grafu. Doruˇcovac´ı strom je tˇreba pr˚ ubˇeˇznˇe pˇrepoˇc´ıtávat a pˇrestavovat podle aktuáln´ıho stavu s´ıtˇe a podle pˇr´ıchoz´ıch a odchoz´ıch uzl˚ u. Obyˇcejnˇe pouˇz´ıvanou metrikou pˇri vys´ılán´ı proudu dat je propustnost dostupn´ ych linek, v pˇr´ıpadˇe ˇziv´ ych pˇrenos˚ u nebo obousmˇerné komunikace (telekonference, videokonference) je kl´ıˇcov´ ym parametrem zpoˇzdˇen´ı a rozptyl. Strom je tedy tvoˇren jedn´ım nebo kombinac´ı tˇechto parametr˚ u. Kromˇe pˇrizp˚ usobován´ı doruˇcovac´ıho stromu podle aktuáln´ıch parametr˚ u s´ıtˇe je moˇzné provádˇet i rezervaci zdroj˚ u.

11

Obrázek 4: Multicasting komunikace - IPTV Rezervace je ovˇsem v pˇrekryvn´ ych s´ıt´ıch dosti problematická, protoˇze po podkladové s´ıti jsou pˇrenáˇsena data, která pˇrekryvné s´ıti nenáleˇz´ı, pˇrekryvná s´ıt’ nen´ı schopna je ani nijak regulovat a tak nelze rezervace nijak zaruˇcit. Na u ´rovni pˇrekryvné s´ıtˇe lze pracovat vˇzdy pouze s aktuáln´ı pˇrenosovou kapacitou, kterou m˚ uˇze pˇrekryvná s´ıt’ regulovat a ˇr´ıdit. V tomto ohledu lze také vyuˇz´ıt predikci stavu linky na základˇe známého chován´ı pˇrenosu z krátkodobé a dlouhodobé historie.

3.2

CDN s´ıtˇ e

´ celem, za jak´ Uˇ ym jsou CDN s´ıtˇe vytváˇreny, je minimalizovat round-triptime (RTT), time-to-live (TTL) a propustnost linek pˇrenáˇsej´ıc´ıch data mezi uˇzivatelem/klientem a zdrojem obsahu. Tento poˇzadavek je kladen na sluˇzby nab´ızené klient˚ um. Poˇzadavky na s´ıt’ jej´ıho provozovatele jsou minimalizovat pˇrenosy a vyuˇzit´ı linek na základˇe vztah˚ u (ˇcasto smluvn´ıch) mezi jednotliv´ ymi autonomn´ımi systémy, rozkládat zátˇeˇz rovnomˇernˇe mezi dostupné uzly a efektivnˇe replikovat poskytovan´ y obsah. Za pˇrenos mezi AS se ˇcasto u ´ˇctuj´ı poplatky, hlavnˇe na u ´rovni mezinárodn´ıch a tranzitn´ıch s´ıt´ı. C´ılem provozovatele CDN je tedy minimalizovat tyto náklady pomoc´ı vhodného smˇerován´ı v s´ıti. Z pohledu doruˇcován´ı obsahu jsou CDN s´ıtˇe podobné skupinovému vys´ılán´ı. Opˇet je vytvoˇren doruˇcovac´ı strom, kde koˇrenem stromu je p˚ uvodn´ı server (zdroj obsahu) obsahuj´ıc´ı originál dat. Uzly a listy grafu jsou pak jednotlivé uzly CDN. Uzly CDN mohou b´ yt podle funkce dvoj´ıho druhu, jedny (uzly stromu) jsou pouze pro optimalizaci pˇrenosu a druhé (listy stromu) pouze pro komunikaci s koncov´ ymi uˇzivateli. Obˇe tyto funkce lze kombinovat. Jak bylo popsáno v pˇredchoz´ı 12

kapitole s u ´vodem do CDN, existuj´ı dva moˇzné pˇr´ıstupy k distribuci dat uvnitˇr CDN. Jedn´ım je push a druh´ ym pull. Vybran´ y zp˚ usob je vˇetˇsinou dán základn´ı architekturou CDN nebo doruˇcovan´ ym obsahem. Obsah m˚ uˇze b´ yt statick´ y, v ˇcase nemˇenn´ y (obrázky, ˇclánky, videa) nebo dynamick´ y, v ˇcase se ˇcasto mˇen´ıc´ı nebo na ˇcase pˇr´ımo závisl´ y, napˇr. video vys´ılán´ı. O tom co a jak bude do uzl˚ u distribuováno, rozhoduje komponenta CDN oznaˇcovaná jako director. Tato komponenta slouˇz´ı k ˇr´ızen´ı CDN a ˇr´ıká, jak bude obsah distribuován do s´ıtˇe, napˇr´ıklad podle zvolen´ ych sluˇzeb zákazn´ıka. Souˇcást´ı komponenty director je kromˇe ˇr´ızen´ı také sluˇzba evidence zákazn´ık˚ u, u ´ˇctován´ı, katalog obsahu a adresáˇr dostupn´ ych server˚ u a algoritmus pro ˇr´ızen´ı distribuce. V pˇr´ıpadˇe distribuce ˇzivého video vys´ılán´ı se s´ıt’ chová podobnˇe jako multicast, vys´ılán´ı je distribuováno jen do tˇech uzl˚ u, kde na jeho sledován´ı ˇcekaj´ı uˇzivatelé a je tam distribuován pouze v jedné kopii, následnˇe listy doruˇcovac´ıho stromu jiˇz v nˇekolika identick´ ych proudech doruˇcuj´ı obsah pˇr´ımo uˇzivatel˚ um. Vˇetˇsinou je pro to vyuˇzita metoda pull, protoˇze vys´ılán´ı je nutné doruˇcit do daného uzlu jen v pˇr´ıpadˇe, ˇze má konzumenty. Zde se dynamické smˇerován´ı uplatn´ı ˇsirokou mˇerou, protoˇze je tˇreba doruˇcit data bez zbyteˇcného zpoˇzdˇen´ı k uˇzivatel˚ um s co nejvˇetˇs´ı pˇrenosovou rychlost´ı (kvalitou vys´ılán´ı). Strom nebo jeho vˇetev je tˇreba sestavit s ohledem na poˇzadované parametry provozu, aktuáln´ı poˇzadavky a zátˇeˇz systému. V pˇr´ıpadˇe distribuce statického obsahu lze vyuˇz´ıt oba pˇr´ıstupy, jak pull tak push. V pˇr´ıpadˇe pull je vytvoˇrena lokáln´ı replika pˇri prvn´ım pˇr´ıstupu uˇzivatele k obsahu. V tuto chv´ıli je tˇreba vhodnˇe zvolit server, kter´ y bude zdrojem aktuáln´ıch dat. Nejjednoduˇsˇs´ı je zvolit p˚ uvodn´ı server, protoˇze zde je zaruˇceno, ˇze právˇe tam bude aktuáln´ı obsah dostupn´ y. Tento pˇr´ıstup nen´ı vhodn´ y s ohledem na efektivitu a jeden z c´ıl˚ u CDN, kter´ ym je minimalizace zátˇeˇze zdrojov´ ych server˚ u a v pˇr´ıpadˇe nouze i obsluha poˇzadavk˚ u z cache v pˇr´ıpadˇe jeho nedostupnosti. Je tedy vhodnˇejˇs´ı jako zdroj pro lokáln´ı repliku pouˇz´ıt jin´ y server, kter´ y má aktuáln´ı data, server lze naj´ıt pomoc´ı katalogu obsahu. Následnˇe je uplatnˇeno opˇet dynamické smˇerován´ı tak, ˇze je hledána taková cesta pˇres uzly CDN, aby byl obsah dostupn´ y co nejdˇr´ıve. S pouˇzit´ım dynamického smˇerován´ı je moˇzné pouˇz´ıt ty servery, které sice nemaj´ı nejnovˇejˇs´ı repliku dat, ale cesta pˇres nˇe ke zdrojovému serveru je rychlejˇs´ı. Bonusem pak m˚ uˇze b´ yt i to, ˇze pˇri pˇrenosu si mohou své lokáln´ı repliky aktualizovat i pr˚ uchoz´ı uzly. Velkou v´ yzvou pˇri tvorbˇe CDN je také volba um´ıstˇen´ı a mnoˇzstv´ı uzl˚ u v jednotliv´ ych lokalitách (geografická oblast, AS). Tomu vˇetˇsinou pˇredcház´ı mˇeˇren´ı a anal´ yza návˇstˇevn´ık˚ u poskytovatele obsahu. Zde je ˇcasto vyuˇz´ıvána i predikce, protoˇze mnoˇzstv´ı obsahu a uˇzivatel˚ u pr˚ ubˇeˇznˇe roste. Dále pak jednotliv´ı poskytovatelé ˇcasto rozˇsiˇruj´ı svoji p˚ usobnost do nov´ ych region˚ u nebo docház´ı k vyˇsˇs´ımu rozˇs´ıˇren´ı internetu v dˇr´ıve zaostal´ ych regionech.

13

3.3

P2P s´ıtˇ e

Dynamické smˇerován´ı nen´ı prakticky v P2P pˇrekryvné s´ıti pˇr´ıliˇs ˇcasté a ani obsahem aktuáln´ıho v´ yzkumu [47], [11], [13]. Pokud P2P s´ıtˇe vyuˇz´ıvaj´ı pˇri své funkci smˇerován´ı, pak se jedná vˇetˇsinou o hierarchické smˇerován´ı. Primárnˇe se smˇerován´ı vyuˇz´ıvá ve fázi hledán´ı dat. Jak bylo ukázáno na pˇr´ıkladu DHT, obr. 1 data jsou v s´ıti reprezentována v´ ysledkem hashovac´ı funkce. Podle v´ ysledného hashe jsou pak um´ıstˇena na uzly s´ıtˇe nebo je na uzly s´ıtˇe um´ıstˇena reference na tyto data (s´ıt’ slouˇz´ı pro vyhledáván´ı dat). Smˇerován´ı poˇzadavk˚ u je pak vyuˇz´ıvané pˇredevˇs´ım ve fázi vyhledáván´ı dat. V pˇr´ıpadˇe centralizované P2P s´ıtˇe je pˇredán seznam uzl˚ u, které maj´ı daná data k dispozici a následná v´ ymˇena dat jiˇz prob´ıhá pˇr´ım´ ym spojen´ım s tˇemito uzly. Hierarchické P2P s´ıtˇe pak pouˇz´ıvaj´ı smˇerován´ı k nalezen´ı daného uzlu v s´ıti. Bˇehem ˇzivota s´ıtˇe, jak uzly do s´ıtˇe vstupuj´ı a opouˇstˇej´ı ji, jsou zaˇrazovány do struktury s´ıtˇe a na nˇe je mapován obsah podle v´ ysledk˚ u hashovac´ı funkce. Pˇri z´ıskáván´ı dat je pak pouˇzit nejbliˇzˇs´ı znám´ y uzel a dotázán na existenci dat daného kl´ıˇce. Uzel odeˇsle zpˇet vyhledávaná data nebo seznam nejbliˇzˇs´ıch pro nˇej znám´ ych uzl˚ u k danému hashi. Tento proces se pak opakuje, dokud nejsou data nalezena. Smˇerován´ı je realizováno tak, ˇze uzel m´ısto aby vrátil seznam uzl˚ u, které jsou k hledané hodnotˇe bl´ıˇze, provede dalˇs´ı dotaz sám. Tento postup opakuje dalˇs´ı uzel dokud nen´ı konkrétn´ı kl´ıˇc nalezen a data jsou postupnˇe vracena zpˇet, aˇz doputuj´ı k uzlu, kter´ y se dotazoval.

Obrázek 5: Vyhledáván´ı v DHT a) pˇr´ımé dotazován´ı b) smˇerované dotazován´ı Obrázek 5 zobrazuje situace, kdy uzel 000 vyhledává data s kl´ıˇcem 100, nejprve je zde vidˇet dotaz na uzel (nebo skupinu uzl˚ u), kter´ ym náleˇz´ı kl´ıˇc 010. Vyhledáván´ı pokraˇcuje pˇres uzel 011 a v dalˇs´ım kroku konˇc´ı v c´ıli. V pˇr´ıpadˇe a) je dotazován´ı pˇr´ımé, nedocház´ı k ˇzádnému smˇerován´ı, v pˇr´ıpadˇe b) je poˇzadavek smˇerován dále na známé uzly. Z obrázku je patrné, ˇze smˇerován´ı nesleduje ˇza´dné metriky, ale 14

ˇr´ıd´ı se pouze kl´ıˇci DHT. Obrázek 6 znázorˇ nuje dalˇs´ı moˇzné uspoˇrádán´ı uzl˚ u P2P s´ıtˇe do stromu. Smˇerován´ı dat by pak pˇredstavovalo procházen´ı tohoto stromu.

Obrázek 6: Stromová struktura DHT Smˇerován´ı v tˇechto s´ıt´ıch je moˇzné optimalizovat systematickou organizac´ı dané topologie s´ıtˇe. Tato systematizace m˚ uˇze prob´ıhat pˇri zaˇrazen´ı nového uzlu nebo se m˚ uˇze mˇenit v ˇcase podle aktuáln´ıho stavu linek a uzl˚ u. Jednou z otázek poté bude podle jak´ ych metrik volit ohodnocen´ı uzl˚ u nebo skupin uzl˚ u a jejich linek a dále jaké parametry s´ıtˇe optimalizovat. V pˇr´ıpadˇe decentralizované P2P je tˇreba uvaˇzovat, ˇze dané uspoˇrádán´ı bude optimáln´ı z globáln´ıho pohledu, ale nemus´ı b´ yt optimáln´ı z pohledu jednotliv´ ych uzl˚ u a konkrétn´ıch dat, ke kter´ ym pˇristupuj´ı. Dalˇs´ım ˇreˇsen´ ym problémem m˚ uˇze b´ yt znalost aktuáln´ı topologie s´ıtˇe, evidence vˇsech uzl˚ u s´ıtˇe a jejich vzájemn´ ych vztah˚ u pro v´ ypoˇcet optima. Dynamické smˇerován´ı je moˇzné do P2P zavést v pˇr´ıpadˇe, ˇze jednotlivé kl´ıˇce DHT spravuje fyzicky v´ıce uzl˚ u, pak budeme v kaˇzdém kroku vyb´ırat ten uzel, kter´ y splˇ nuje nejlépe definované parametry pro zvolen´ y provoz. Rozhodován´ı o vhodné trase muˇze b´ yt provádˇeno vˇzdy v kaˇzdém uzlu samostatnˇe nebo m˚ uˇze b´ yt ˇr´ızeno hlubˇs´ı znalost´ı topologie a jednotliv´ ych metrik pouˇzit´ ych spoj˚ u. Napˇr´ıklad v kaˇzdém kroku vyhledáván´ı m˚ uˇze b´ yt dotazuj´ıc´ımu uzlu odeslán seznam s nejbliˇzˇs´ımi uzly a parametry dostupn´ ych linek. Dotazuj´ıc´ı pak spoˇc´ıtá optimáln´ı trasu pro pr˚ uchod celou cestou k c´ıli. Inicializace v´ ypoˇctu bude zat´ıˇzena nutnou reˇzi´ı pro z´ıskán´ı tˇechto informac´ı, ale následn´ y pˇrenos dat bude optimáln´ı z hlediska stanoven´ ych metrik.

3.4

Zajiˇ stˇ en´ı kvality sluˇ zeb

Pˇrekryvné s´ıtˇe pro zajiˇstˇen´ı kvality sluˇzeb jsou aktuálnˇe reprezentovány s´ıtˇemi Service Overlay Network (SON)[12] a Resilient Overlay Netwok (RON)[1]. 15

Resilient Overlay Network je navrˇzena s c´ılem minimalizovat dopady náhl´ ych zmˇen na s´ıt´ıch, pˇredevˇs´ım v´ ypadky spoj˚ u (rychlejˇs´ı zmˇena trasy, neˇz ji provede BGP nebo jin´ y internetov´ y smˇerovac´ı protokol), pˇret´ıˇzen´ı nebo zahlcen´ı linek (´ utoky nebo anomálie zp˚ usobená provozem na s´ıti kv˚ uli nˇejaké v´ yznamné události). Uzly RON neustále sleduj´ı stavy jednotliv´ ych linek mezi uzly s´ıtˇe a bez prodlen´ı na nˇe reaguj´ı a provoz pˇresmˇerovávaj´ı. Platforma pro s´ıt’ je vytvoˇrená jako extern´ı knihovna, kterou je moˇzné zakomponovat do existuj´ıc´ıch program˚ u a která následnˇe zajist´ı pˇrenos s´ıt´ı, tak aby byl optimáln´ı podle definovan´ ych potˇreb. Logika v knihovnˇe rozhodne, jestli je vhodnˇejˇs´ı pouˇz´ıt pˇr´ımé spojen´ı pomoc´ı klasick´ ych linek nebo pˇremostit pˇrenos pomoc´ı pˇrekryvné s´ıtˇe. Schéma fungován´ı znázorˇ nuje obrázek 7. RON vyuˇz´ıvá pro rozhodován´ı základn´ı metriky, rychlost, spolehlivost a zpoˇzdˇen´ı. Knihovna je navrˇzena pro spolupráci s aplikacemi, ke kter´ ym je pˇripojena. Je moˇzné specifikovat i vlastn´ı aplikaˇcn´ı metriky. V´ ysledná metrika a politika pouˇzitá pˇri smˇerován´ı je pak zaloˇzena na explicitn´ıch pravidlech, podle zdroje, c´ıle a tˇr´ıdy pˇrenosu. Pˇrenáˇsená data jsou pak oznaˇcena nejen zdrojem a c´ılem, ale také tˇr´ıdou provozu a oznaˇcen´ım pouˇzité politiky. Definice jednotliv´ ych politik m˚ uˇze smˇerován´ı dále ovlivˇ novat, napˇr´ıklad zakázat pˇrenos po vybraném spoji. Kaˇzd´ y uzel s´ıtˇe se skládá z nˇekolika ˇcást´ı, prvn´ı je pˇredavaˇc, kter´ y na základˇe vyhodnocen´ı smˇerován´ı pˇredává data dále, v´ ykonnostn´ı databáze, která obsahuje z´ıskané hodnoty jednotliv´ ych metrik a jsou z n´ı následnˇe odvozeny moˇzné cesty a databáze politik, která dále rozhoduje, která cesta m˚ uˇze b´ yt pro pˇrenos pouˇzita.

Obrázek 7: Koncept fungován´ı RON Hlavn´ım c´ılem RON je minimalizovat problémy v internetu zp˚ usobené pˇredevˇs´ım ’ v´ ypadky linek a n´ızkou pˇrenosovou rychlost´ı zp˚ usobnou, at jiˇz n´ızkou kapacitou linek nebo jej´ım aktuáln´ım zahlcen´ım. Oproti tomu Service Overlay Netwok se snaˇz´ı zcela koncepˇcnˇe zajistit konkrétn´ı parametry komunikace s d˚ urazem pˇredevˇs´ım na kvalitu sluˇzeb (QoS) pro aplikace jako napˇr´ıklad VoIP, video na poˇza´dán´ı a dalˇs´ı online aplikace, kde je tˇreba garantovat definovanou minimáln´ı kvalitu pˇrenosu. 16

QoS jak v pˇrekryvn´ ych tak bˇeˇzn´ ych s´ıt´ı pˇredpokládá prioritizaci nˇekterého pˇrenosu nad ostatn´ımi. Mohou b´ yt definovány tˇr´ıdy pˇrenosu podle jejich poˇzadavk˚ u. Poˇzadavky na pˇrenos pak mohou b´ yt pomoc´ı prioritn´ıch front nebo ˇ pomoc´ı token bucket algoritmu. Casto se také pouˇz´ıvá rezervace pˇrenosového pásma podle nárok˚ u aplikace definovan´ ych pˇri zahájen´ı pˇrenosu. Pouˇzit´ı rezervac´ı je ale v pˇr´ıpadˇe pˇrekryvn´ ych s´ıt´ı nanejv´ yˇse problematické, protoˇze pˇrekryvná s´ıt’ nemá dostatek informac´ı o celkové ˇs´ıˇrce dostupné pro pouˇzité spoje, ale m˚ uˇze je pouze odhadovat na základˇe krátkodob´ ych nebo dlouhodob´ ych mˇeˇren´ı. Pˇrekryvná ’ s´ıt ani nedokáˇze spolehlivˇe poˇzadovanou kapacitu rezervovat, protoˇze linky mohou b´ yt kdykoli zat´ıˇzené pˇrenosem mimo pˇrekryvnou s´ıt’, kter´ y na linkách také prob´ıhá paralelnˇe. Lze tedy pracovat pouze s pravdˇepodobnost´ı schopnosti garantovat dané parametry pˇrenosu. Ke zv´ yˇsen´ı pravdˇepodobnosti mohou pˇrispˇet metody predikce zat´ıˇzen´ı a dostupné kapacity linky, která pˇrenos realizuje. Tomuto tématu, jak predikovat parametry linky v bl´ızké budoucnosti se budou vˇenovat dalˇs´ı kapitoly práce.

3.5

Anonymizaˇ cn´ı s´ıtˇ e

Anonymizaˇcn´ı s´ıtˇe jako jsou TOR[7], ORTA[37] nebo Vuvuzela[39] vyuˇz´ıvaj´ı dynamické smˇerován´ı k anonymizaci u ´ˇcastn´ık˚ u a ochranˇe proti odposlechu neustálou zmˇenou tras. Sledovanou metrikou je pravdˇepodobnostn´ı rozdˇelen´ı generátoru náhodn´ ych cest, aby byla zvolená cesta dostateˇcnˇe náhodná a t´ım i bezpeˇcná proti odposlechu nebo sledován´ı. Cesty mus´ı b´ yt volené tak, aby splˇ novaly poˇzadavek na minimáln´ı poˇcet skok˚ u a aby byly uzly a jejich poˇrad´ı volené s rovnomˇern´ ym rozdˇelen´ım pravdˇepodobnosti. Pokud by docházelo k jakémukoli deterministickému smˇerován´ı na základˇe libovoln´ ych metrik, pak by bylo moˇzné vkládat do s´ıtˇe uzly tak, aby s pravdˇepodobnost´ı p vedla cesta, právˇe pˇres tyto vloˇzené uzly. S moˇznost´ı vloˇzit vˇetˇs´ı poˇcet uzl˚ u by pravdˇepodobnost, ˇze provoz p˚ ujde pˇres vloˇzené uzly, rostla. Vˇsechny s´ıtˇe funguj´ıc´ı na tomto principu mus´ı v návrhu usilovat o to aby pomˇer vlastn´ıch a vloˇzen´ ych uzl˚ u musel b´ yt co nejvˇetˇs´ı, ’ aby nebylo moˇzné kompromitovat s´ıt tak snadno nebo to bylo finanˇcnˇe velice nároˇcné.

3.6

Shrnut´ı smˇ erov´ an´ı v pˇ rekryvn´ ych s´ıt´ıch

V kaˇzdém druhu pˇrekryvn´ ych s´ıt´ı popsan´ ych pˇredchoz´ıch sekc´ıch prob´ıhá smˇerován´ı r˚ uzn´ ymi zp˚ usoby. Nˇekteré s´ıtˇe jsou strukturované, tvoˇr´ı napˇr´ıklad prostor dat ( 2D plocha, n-rozmˇerná kostka atp.) rozdˇelen´ y na menˇs´ı oblasti a smˇerován´ı prob´ıhá mezi tˇemito oblastmi. Jiné strukturované s´ıtˇe tvoˇr´ı napˇr´ıklad doruˇcovac´ı stromy, hvˇezdu, kruh a nebo kombinace. Pokud nen´ı struktura s´ıtˇe pevnˇe dána, pak se tvoˇr´ı zvolené/definované struktury s ohledem na splnˇen´ı de17

finovan´ ych c´ıl˚ u, rychlost, spolehlivost doruˇcen´ı, maximáln´ı logickou vzdálenost a dostupné zdroje. Aby bylo moˇzné strukturu t´ımto zp˚ usobem sestavit, tak je tˇreba znát vlastnosti s´ıtˇe. Vlastnosti dané s´ıtˇe vycház´ı z prostˇredk˚ u, které jsou j´ı ’ dostupné skrze podkladovou s´ıt . Tvorba topologie a jej´ı uspoˇra´dán´ı je tedy dáno vˇsemi poˇzadavky, které jsou na danou s´ıt’ kladeny a aktuáln´ımi a dostupn´ ymi informacemi o stavu s´ıtˇe a parametry linek.

4

Smˇ erovac´ı metriky

Pro smˇerován´ı v pˇrekryvn´ ych s´ıt´ıch se pouˇz´ıvaj´ı dvˇe základn´ı metriky, jednou je dostupná pˇrenosová rychlost, druhou je zpoˇzdˇen´ı. Dalˇs´ı sledované metriky pak mohou b´ yt spolehlivost linky (ztrátovost paket˚ u, chybovost pˇri odes´ılán´ı/pˇr´ıjmu), stabilita (kol´ısán´ı) pˇrenosov´ ych parametr˚ u linky nebo jej´ı opakované pˇreruˇsen´ı spojen´ı. Kaˇzd´ y z tˇechto parametr˚ u je moˇzné mˇeˇrit a následnˇe ho vyuˇz´ıt pˇri smˇerován´ı poˇzadavk˚ u s´ıt´ı. Zásadn´ı komplikac´ı pˇrekryvn´ ych s´ıt´ı je v z´ıskáván´ı tˇechto dat, ˇza´dná nebo pouze malá znalost niˇzˇs´ı vrstvy, kterou pro sv˚ uj provoz vyuˇz´ıvá a také v mnoha pˇr´ıpadech i fakt, ˇze uzly pˇrekryvné s´ıtˇe tvoˇr´ı pˇreváˇznˇe koncové uzly, uˇzivatelské stanice, servery atp. V souˇcasné dobˇe se také rozv´ıj´ı ˇr´ızen´ı pˇrenosu (traffic engineering, TE) nebo dynamické ˇr´ızen´ı pˇrenosu, které m˚ uˇze pˇrekryvn´ ym s´ıt´ım komplikovat situaci, t´ım, ˇze se dynamicky mˇen´ı smˇerován´ı v podkladové s´ıti a t´ım i parametry, které m˚ uˇze pˇrekryvná s´ıt’ sledovat. Na druhou stranu postup˚ um ˇr´ızen´ı provozu na niˇzˇs´ıch vrstvách mohou pˇrekryvné s´ıtˇe také naruˇsovat nebo ovlivˇ novat funkˇcnost. Aktuáln´ı vˇedecké zkoumán´ı se tak zamˇeˇruje jak na aplikaci princip˚ u znám´ ych z pˇrekryvn´ ych s´ıt´ı do ˇr´ızen´ı provozu napˇr. IP s´ıt´ı, tak v rámci softwarovˇe definoˇ van´ ych s´ıt´ı [17][16]. Rada publikac´ı se zab´ yvá interferenc´ı ˇr´ızen´ı s´ıt’ového provozu a pˇrekryvn´ ych s´ıt´ı, jejich moˇznou spoluprac´ı, pˇr´ıpadnˇe ˇr´ızen´ım jedné s´ıtˇe druhou. Publikované práce popisuj´ı, ˇze ˇcisté ˇr´ızen´ı podkladové s´ıtˇe podle poˇzadavk˚ u a pravidel pˇrekryvné s´ıtˇe vede k nestabilitˇe spojen´ı a linek.

4.1

Sledov´ an´ı a mˇ eˇ ren´ı parametr˚ u v pˇ rekryvn´ ych s´ıt´ıch

Problematika sledován´ı a mˇeˇren´ı parametr˚ u pˇrekryvn´ ych s´ıt´ı je oproti podkladov´ ym, základn´ım, s´ıt´ım specifická t´ım, ˇze nejsou dostupné konkrétn´ı informace o dostupn´ ych prostˇredc´ıch, ani konkrétn´ı konfiguraci podkladové s´ıtˇe. Pˇrekryvná s´ıt’ nemá informaci o tom, jaké jsou priority a metriky podkladové s´ıtˇe a jak´ y je pouˇzit´ y smˇerovac´ı protokol. Nen´ı známo jestli podkladová s´ıt’ vyuˇz´ıvá distance 18

vector nebo link state smˇerován´ı. Nemáme ani dostupné informace o tom, jak je s´ıt’ rozlehlá a z jak´ ych technologi´ı se skládá. Mˇeˇrené hodnoty jsou také zat´ıˇzené, resp. ovlivnˇené ostatn´ım okoln´ım provozem, kter´ y s vytvoˇrenou pˇrekryvnou s´ıt´ı interferuje. Mˇeˇren´ı základn´ıch metrik pouˇziteln´ ych pro smˇerován´ı tak m˚ uˇze prob´ıhat dvoj´ım zp˚ usobem, jedn´ım je aktivn´ı mˇeˇren´ı, kdy jsou mezi uzly pˇrekryvné s´ıtˇe pos´ılány zprávy, pomoc´ı kter´ ych je moˇzné dané metriky z´ıskat. V pˇr´ıpadˇe detekce zpoˇzdˇen´ı na lince je moˇzné pos´ılat krátké zprávy a mˇeˇrit ˇcas mezi odeslán´ım a pˇr´ıjmem. Z´ıskan´ y ˇcas je ˇcasem cesty zprávy k c´ıli a odpovˇedi zpˇet, RTT, round trip time. S vyuˇzit´ım znalosti Christianova algoritmu pro synchronizaci ˇcasu m˚ uˇzeme odvodit dobu cesty paketu k c´ıli. Pro z´ıskán´ı dostupné pˇrenosové rychlosti jsou vys´ılány delˇs´ı zprávy, kde se projev´ı dostupná pˇrenosová rychlost v´ıc, neˇz u krátk´ ych, kterou jsou zat´ıˇzené sp´ıˇse zpoˇzdˇen´ım. Pokud bude zpráva dostateˇcnˇe dlouhá, pak bude moˇzné zpoˇzdˇen´ı linky zanedbat. Aktivn´ı mˇeˇren´ı parametr˚ u linky ovˇsem generuje zbyteˇcnou zátˇeˇz s´ıtˇe a m˚ uˇze tak negativnˇe ovlivˇ novat i vlastnosti pˇrekryvné s´ıtˇe. V pˇr´ıpadˇe, kdy je pˇrekryvná s´ıt’ reprezentována jako u ´pln´ y graf na vˇsech uzlech s´ıtˇe, je tˇreba kaˇzdé sledován´ı 2 provést alespoˇ n N . Zas´ılán´ı zpráv je vhodné provádˇet v obou smˇerech dvou komunikuj´ıc´ıch uzl˚ u, protoˇze je tam moˇzné odhalit i asynchronn´ı linky. Existuj´ı algoritmy a postupy, kdy se poˇcet mˇeˇren´ı redukuje na nutná mˇeˇren´ı a dalˇs´ı hodnoty jsou odvozeny pomoc´ı aproximace [44]. Vhodnˇejˇs´ım postupem neˇz aktivn´ım mˇeˇren´ım je pasivn´ı zjiˇst’ován´ı tˇechto vlastnost´ı z procházej´ıc´ıch dat. Základn´ı znalost o latenci m˚ uˇzeme z´ıskat inspekc´ı ´ TCP hlaviˇcek, které obsahuj´ı RTT. Udaj o rychlosti pˇrenosu je moˇzné zjistit z procházej´ıc´ıch dat a doplnˇen´ım provozn´ıch informac´ı do hlaviˇcek pˇrekryvné s´ıtˇe.

4.2

Dalˇ s´ı sledovateln´ e parametry

Dalˇs´ımi sledovateln´ ymi parametry ovlivˇ nuj´ıc´ımi efektivitu pˇrenosu a smˇerován´ı pˇres pˇrekryvné linky mohou b´ yt kromˇe mˇeˇren´ ych hodnot dan´ ych linek i dalˇs´ı vlastnosti komponent pˇrekryvné s´ıtˇe, napˇr´ıklad zat´ıˇzen´ı v´ ypoˇcetn´ıch prostˇredk˚ u jednotliv´ ych uzl˚ u, interference jednotliv´ ych linek mezi sebou, pˇr´ısluˇsnost uzl˚ uk jednotliv´ ym AS. Obrázek 8 znázorˇ nuje pˇrekryvnou s´ıt’, uzly A, B, C, D, E jsou uzly pˇrekryvné s´ıtˇe, uzly 1, 2, 3, 4, 5 jsou uzly, pˇres které komunikace procház´ı, ale nejsou souˇca´st´ı pˇrekryvné s´ıtˇe, napˇr´ıklad smˇerovaˇce. Spojen´ı mezi uzly A a E lze realizovat tˇremi r˚ uzn´ ymi cestami, jedna je oznaˇcena pln´ ymi spoji (A1B2E), druhá pˇreruˇsovanou (A1C2E) a tˇret´ı teˇckovanou ˇca´rou (A3D45E). Z pohledu pˇrekryvné s´ıtˇe jsou ˇc´ısly uzly neviditelné. Pokud zvol´ıme prvn´ı cestu jako primárn´ı a dalˇs´ı dvˇe jako záloˇzn´ı, pak pokud dojde k v´ ypadku nebo zahlcen´ı na spoji A1 nebo 2E, pak to ovlivn´ı 19

jak prvn´ı tak druhou cestu a bude muset b´ yt pouˇzita cesta tˇret´ı. Pˇrekryvná s´ıt’ obecnˇe nemá znalost podkladové topologie, v rámci smˇerován´ı rozliˇsuje pouze vlastn´ı uzly (oznaˇcené p´ısmeny). Pˇrekryvná s´ıt’ chápe cesty A1B a A1C jako dvˇe r˚ uzné cesty AB a AC. V praxi m˚ uˇze pak doj´ıt k tomu, ˇze cesta A1B2E bude nahrazena cestou A1C2E, na které se zjiˇstˇené parametry nebo událost objev´ı také a bude tˇreba pouˇz´ıt aˇz cestu A3D45E. Dalˇs´ı situace, která m˚ uˇze nastat v pˇr´ıpadˇe, kdyby pˇrekryvná s´ıt’ poskytovala agregaci vybran´ ych linek, tak v pˇr´ıpadˇe agregace na linkách A1B2E a A1C2E nemus´ı doj´ıt k ˇza´dnému zisku, protoˇze obˇe cesty vyuˇz´ıvaj´ı spoleˇcn´ ych uzl˚ u a jejich spoj˚ u, konkrétnˇe A1 a 2E kde by rozdˇelená zátˇeˇz znovu sˇc´ıtala.

Obrázek 8: Pˇrekryvná s´ıt’ se spoleˇcn´ ymi linkami ˇ Casto je pˇrekryvná s´ıt’ tvoˇrena jak specializovan´ ymi uzly (smˇerovaˇce, servery urˇcené pro poskytován´ı sluˇzeb pˇrekryvné s´ıtˇe), tak bˇeˇzn´ ymi uˇzivatelsk´ ymi stanicemi (dle nastaven´ı, jak poskytuj´ı sluˇzby, tak je od jin´ ych vyuˇz´ıvaj´ı). Bˇeˇzn´ y uˇzivatelsk´ y pˇr´ıstup je v˚ uˇci sluˇzbám pˇreváˇznˇe konzumn´ı, lze tedy pˇredpokládat, ˇze nastaven´ı tˇechto uzl˚ u bude asymetrické, budou v´ıce ˇcerpat a ménˇe nab´ızet. Kvalitu sluˇzeb nab´ızen´ ych tˇemi uzly dále ovlivn´ı mnohem v´ıce aktuáln´ı zat´ıˇzen´ı jejich systému, dostupné v´ ypoˇcetn´ı prostˇredky (rychlost v´ ypoˇct˚ u, rychlost pˇredáván´ı zpráv, rychlost ˇsifrován´ı atp.), tak dostupné pˇrenosové pásmo, bude tˇreba uspokojit jak poˇzadavky pˇrekryvné s´ıtˇe, tak poˇzadavky lokáln´ıch aplikac´ı. Specializované uzly jsou také ovlivˇ novány dan´ ymi vlastnostmi, ale v mnohem menˇs´ı m´ıˇre. Pˇri efektivn´ım smˇerován´ı dat v pˇrekryvné s´ıti je vhodné brát v u ´vahu i tyto vlastnosti jednotliv´ ych uzl˚ u a zahrnout je napˇr´ıklad jako aditivn´ı sloˇzku pˇri v´ ypoˇctu cest v s´ıti.

20

5

Predikce stavu linek a s´ıtˇ e

Pokud jsme schopni mˇeˇrit a vyhodnocovat vlastnosti, stav a chován´ı linek v pˇrekryvné s´ıti, pak se nab´ız´ı otázka moˇznosti pˇredpov´ıdat zat´ıˇzen´ı s´ıtˇe a t´ım optimalizovat smˇerován´ı. Obyˇcejnˇe je zmˇena smˇerovac´ıch tabulek vyvolána zásadn´ı zmˇenou na s´ıt´ı, v´ ypadkem linky, v´ ypadkem routeru, zásadn´ı zmˇenou parametr˚ u dané linky nebo zásahem administrátora. Tento reaktivn´ı postup m˚ uˇze b´ yt ˇcasovˇe relativnˇe nároˇcn´ y, zvláˇstˇe pak ˇcas konvergence, neˇz se s´ıt’ po této zmˇenˇe opˇet stabilizuje. Pokud bychom k reaktivn´ımu pˇr´ıstupu ˇr´ızen´ı s´ıt´ı pˇripojili i proaktivn´ı zmˇeny smˇerován´ı, pak by bylo moˇzné i pˇres zmˇeny v podkladové s´ıti, kdy napˇr´ıklad dojde k saturaci nebo zahlcen´ı nˇekteré podkladové linky, kterou jsme schopni predikovat, tak pro zachován´ı kvality sluˇzby vˇcas pˇresmˇerovat provoz po jin´ ych linkách, kde je dostateˇcnˇe volná kapacita.

5.1

ˇ Casov´ eˇ rady a predikce

S´ıt’ov´ y provoz pˇredstavuje ˇcasovou ˇradu, která má klasické statistické vlastnosti ˇ jako stˇredn´ı hodnotu, smˇerodatnou odchylku a dalˇs´ı. Casov´ a ˇrada se skládá z jednotliv´ ych hodnot mˇeˇren´ı s konstantn´ım ˇcasov´ ym odstupem jednotliv´ ych mˇeˇren´ı. Pokud nen´ı ˇrada kompletn´ı nebo ˇcasové u ´daje chyb´ı, pak je tˇreba hodnoty interˇ polovat tak, aby byl odstup jednotliv´ ych mˇeˇren´ı konstantn´ı. Casov´ a ˇrada s´ıt’ového provozu m˚ uˇze b´ yt tvoˇrena z r˚ uzn´ ych hodnot, které nám definuj´ı pouˇzitou metriku pˇri smˇerován´ı, napˇr´ıklad aktuáln´ı pˇrenos na lince, zpoˇzdˇen´ı doruˇcen´ı zpráv, obousmˇerné zpoˇzdˇen´ı, spolehlivost, ztrátovost a dalˇs´ı. Z pˇredchoz´ıch namˇeˇren´ ych hodnot je pak moˇzné predikovat pouze jednu následuj´ıc´ı hodnotu nebo skupinu nov´ ych hodnot. ˇ Casov´ e ˇrady je moˇzné zkoumat s ohledem na jejich vlastnosti. Jedn´ım z dˇelen´ı ˇcasov´ ych ˇrad m˚ uˇze b´ yt, jestli je ˇcasová ˇrada stabiln´ı nebo nestabiln´ı. Pokud je ˇcasová ˇrada stabiln´ı, pak jej´ı vlastnosti nezáleˇz´ı na ˇcase, kdy ji sledujeme (má konstantn´ı statistické vlastnosti). Oproti tomu nestabiln´ı ˇcasové ˇrady obsahuj´ı sloˇzky, ˇ které jsou promˇenné v ˇcase, napˇr´ıklad trend nebo periodu. Casov´ a ˇrada je kombinac´ı trendové sloˇzky, sezónn´ı sloˇzky a zbytkové (chybové sloˇzky), vztah vyjadˇruje rovnice 2. V publikac´ıch se uvád´ı jeˇstˇe cyklická sloˇzka. Následuj´ıc´ı obrázky predikce jsou v´ ystupem z jazyka R [30] a dostupn´ ych knihoven pro práci s ˇcasov´ ymi ˇradami. Jazyk R je urˇcen pro zpracován´ı statistick´ ych dat a jejich zobrazen´ı. Yt = Tt + St + et

(2)

ˇ Casov´ a ˇrada s´ıt’ového provozu je klasick´ ym pˇr´ıpadem promˇenlivé ˇcasové ˇrady, protoˇze zcela jistˇe vykazuje periodické chován´ı, které je dáno uˇzivateli, bˇehem 21

ˇ noci je provoz niˇzˇs´ı neˇz bˇehem dne, kdy jsou uˇzivatelé aktivn´ı. Casov´ e ˇrady s´ıt’ového provozu v dlouhodobém mˇeˇr´ıtku vykazuj´ı jasn´ y vzr˚ ustaj´ıc´ı trend, aplikace pˇrenáˇsej´ı vˇetˇs´ı mnoˇzstv´ı dat a poˇcet uˇzivatel˚ u a aplikac´ı postupnˇe roste. Pˇr´ıkladem stabiln´ı ˇcasové ˇrady pak m˚ uˇze b´ yt napˇr´ıklad b´ıl´ y ˇsum, kter´ y neobsahuje ˇza´dnou periodickou ani trendovou sloˇzku a má statisticky konstantn´ı vlastnosti. Nestabilita ˇcasové ˇrady s´ıt’ového provozu je pro predikci pozitivn´ı vlastnost, protoˇze základn´ı predikci lze dˇelat na základˇe periodické a trendové sloˇzky. Z obrázku 9 je patrné rozloˇzen´ı ˇcasové ˇrady na sloˇzky, m˚ uˇzeme vidˇet sloˇzku trendu, sezónn´ı (periodickou) a náhodnou. V praxi se pˇred predikc´ı pouˇz´ıvá jeˇstˇe pˇredzpracován´ı, kdy se ˇcasová ˇrada uprav´ı, napˇr´ıklad se oˇreˇzou extrémy, ˇrada se linearizuje, interpoluj´ı se chybˇej´ıc´ı hodnoty, z´ıskané hodnoty se vyhlad´ı (filtruj´ı), normuj´ı se na rozsah < 0; 1 > nebo < −1; 1 > a dalˇs´ı. Následnˇe jsou data pouˇzita pro samotnou predikci.

Obrázek 9: Dekompozice ˇcasové ˇrady

22

Pro predikci ˇcasov´ ych ˇrad se dnes pouˇz´ıvá nˇekolik základn´ıch technik, metoda jednoduché lineárn´ı regrese, auto-regrese (AR), klouzavého pr˚ umˇeru (MA), kombinace pˇredchoz´ıch (ARMA, ARIMA, FARIMA), metody postavené na dekompozici (STL), fraktálová geometrie a neuronové s´ıtˇe. V následuj´ıc´ıch kapitolách budou vybrané metody popsány a shrnuty jejich vlastnosti. Z vlastnost´ı internetového s´ıt’ového provozu popsaného v ˇclánc´ıch [38][6][19][43] je s´ıt’ov´ y provoz sobˇepodobn´ y (term´ın z oblasti fraktálové geometrie, kdy se jednotlivé ˇca´sti v r˚ uzn´ ych mˇeˇr´ıc´ıch navzájem podobaj´ı) a nelineárn´ı. Této vlastnosti r˚ uzn´ ych jev˚ u je vyuˇz´ıváno i v ˇradˇe dalˇs´ıch vˇedn´ıch obor˚ u, elektronice, ekonomii, fyzice, chemii a dalˇs´ıch, kde je tˇreba predikovat stav jevu tˇechto vlastnost´ı. R˚ uzné vˇedn´ı obory k této problematice pˇristupuj´ı r˚ uznˇe, resp. specializuj´ı se na r˚ uzné metody predikce[15]. V informaˇcn´ıch technologi´ıch pˇrevládá pouˇzit´ı neuronov´ ych s´ıt´ı, v pˇr´ırodn´ıch vˇedách se vyuˇz´ıvá teorie chaosu a fraktálová geometrie nebo jednoduˇsˇs´ı metody z oblasti filtrace a predikce, kde je ovˇsem znaˇcnou nev´ yhodou potˇreba hlubˇs´ı znalosti predikované ˇcasové ˇrady, obecnˇe záleˇz´ı na poˇzadované pˇresnosti a zvoleném aparátu nebo hloubce znalosti predikovan´ ych dat.

5.2

Predikce pomoc´ı model˚ u ARMA

ARMA model je kombinac´ı autoregresn´ıho (AR) modelu a klouzavého pr˚ umˇeru (MA). Auto-regresivn´ı model AR(p) odvozuje predikované hodnoty z hodnot pˇredchoz´ıch jako jejich lineárn´ı kombinaci. V rovnici 3 je yt predikovaná hodnota y v ˇcase t z pˇredchoz´ıch p hodnot pomoc´ı vektoru φ. Hodnota c pˇredstavuje konstantu a et symbolizuje náhodnou sloˇzku, která má nulovou stˇredn´ı hodnotu a normáln´ı distribuci. Tyto modely se hod´ı pˇreváˇznˇe pro stacionárn´ı ˇcasové ˇrady. Nestacionárn´ı ˇcasové ˇrady lze na stacionárn´ı pˇrevést pomoc´ı diference ˇcasové ˇrady (rovnice 7). yt = c + φ1 yt−1 + φ2 yt−2 + ... + φp yt−p + et

(3)

Model klouzavého pr˚ umˇeru M A(q) je pak definován jako lineárn´ı kombinace chyb jednotliv´ ych pˇredpovˇed´ı 4. yt = c + et + Θ1 et−1 + Θ1 et−1 + ... + Θq et−q

(4)

Kombinac´ı auto-regrese a klouzavého pr˚ umˇeru pak z´ıskáváme ARM A(p, q) 5 model, kter´ y lze dále rozˇsiˇrovat na ARIM A(p, d, q) 6 nebo F ARIM A(p, d, q) 6 nebo jejich dalˇs´ı varianty, napˇr´ıklad s uvaˇzován´ım sezónn´ı sloˇzky SARIM A(p, d, q)(P, D, Q).

23

yt = c + et +

p X

φi yt−i +

q X

Θj et−j

(5)

j=0

i=1

Pokud systém v dalˇs´ıch stupn´ıch diference ˇcasové ˇrady (rovnice 7 a 8) vykazuje stacionárn´ı chován´ı, pak na tento stupeˇ n m˚ uˇzeme aplikovat ARM A(p, q) model a vzniká t´ım ARIM A(p, d, q). To je proces, kde je d u ´roveˇ n diference, p je autoregresivn´ı stupeˇ n a q stupeˇ n pohyblivého pr˚ umˇeru, p a q nab´ yvaj´ı nezáporn´ ych celoˇc´ıseln´ ych hodnot. Dále lze odvodit proces F ARIM A(p, d, q), coˇz je proces, kter´ y je zaloˇzen na ARIMA procesu a oba lze vyjádˇrit s pomoc´ı operátoru zpˇetného posunut´ı B následuj´ıc´ım vztahem 6. V pˇr´ıpadˇe ARIM A(p, d, q) jsou vˇsechny parametry celoˇc´ıselné a nezáporné, pro F ARIM A(p, d, q) je parametr d reáln´ y. φp (B)(1 − B)d Yt = Θq Bet

(6)

(1 − B)1 Yt = ∆Yt = Yt − Yt−1

(7)

∆2 Yt = ∆(Yt − Yt−1 ) = ∆Yt − ∆Yt−1 = Yt − Yt−1 − (Yt−1 − Yt−2 ) = Yt − 2Yt−1 + Yt−2

(8)

V rovnic´ıch {Yt : ..., −1, 0, 1, ...} pˇredstavuje ˇcasovou ˇradu, d pˇredstavuje diferenci ˇcasové ˇrady (rovnice 7 a 8), {et : ..., −1, 0, 1, ...} pˇredstavuje b´ıl´ y ˇsum s nulovou stˇredn´ı hodnotou a parametry p a q odpov´ıdaj´ı parametr˚ um AR(p) a M A(q). Pˇr´ıklad jednoduché predikce pomoc´ı modelu ARIM A(p, d, q) s parametry p = 10, d = 0, q = 8 je znázornˇen na obrázku 10.

5.3

Predikce pomoc´ı neuronov´ ych s´ıt´ı

V informatice jsou pro predikci ˇcasov´ ych ˇrad ˇcasto pouˇz´ıvány neuronové s´ıtˇe, neuronov´ ych s´ıt´ı existuje celá ˇrada. Neuronové s´ıtˇe se skládaj´ı z ˇrady v´ ypoˇcetn´ıch jednotek (neuron˚ u), které jsou vzájemnˇe propojeny ohodnocen´ ymi hranami. Neurony jsou organizované do vrstev, základn´ı je vstupn´ı vrstva, která obsahuje vstupn´ı neurony odpov´ıdaj´ıc´ı velikosti vstupu, následuje nˇekolik skryt´ ych vrstev a poté v´ ystupn´ı vrstva opˇet odpov´ıdaj´ıc´ı velikosti v´ ystupu. Jednotlivé druhy

24

Obrázek 10: Predikce pomoc´ı ARIMA(10,0,8)

neuronov´ ych s´ıt´ı se pak liˇs´ı poˇctem organizac´ı tˇechto vrstev (se zpˇetnou propagac´ı obsahuj´ı zpˇetné vazby). Základn´ı organizace neuronov´ ych s´ıt´ı je znázornˇena na obrázku 11. Neuronová s´ıt’ je schopna postupn´ ym uˇcen´ım na trénovac´ım vzorku pˇrizp˚ usobit ohodnocen´ı jednotliv´ ych hran, ˇc´ımˇz se adaptuje na funkci, která je ukryta v datech a která tyto data charakterizuje. V´ yhodou vyuˇzit´ı neuronov´ ych s´ıt´ı je právˇe jej´ı schopnost samo uˇcen´ı z namˇeˇren´ ych dat, kdy nepotˇrebujeme znát pˇresné parametry a charakteristiky provozu. Neuronové s´ıtˇe dokáˇz´ı d´ıky natrénovan´ ym dat˚ um z minulosti predikovat budoucnost na základˇe odhalen´ı“ vnitˇrn´ı funkce ” charakterizuj´ıc´ı vztah mezi aktuáln´ımi hodnotami a jejich projevem v budoucnosti. Správnˇe natrénovaná neuronová s´ıt’ je schopna reagovat i na data mimo cviˇcnou mnoˇzinu, proti tomu ˇspatnˇe natrénovaná s´ıt’ m˚ uˇze b´ yt schopna správnˇe zpracovávat pouze trénovac´ı vzorky. Záleˇz´ı tedy i na kvalitˇe dat pro trénován´ı neuronové s´ıtˇe a následné ovˇeˇren´ı jej´ıch kvalit. Neuronov´ ych s´ıt´ı existuje celá ˇrada, jednotlivé s´ıtˇe se od sebe liˇs´ı svoj´ı topologi´ı, zp˚ usobem uˇcen´ı, zprostˇredkován´ım zpˇetné vazby, doˇcasnou pamˇet´ı a podobnˇe. Ne vˇsechny modely neuronov´ ych s´ıt´ı maj´ı stejnou schopnost ˇreˇsit r˚ uzné problémy. Neuronové s´ıtˇe vyuˇzitelné k rozpoznáván´ı vzor˚ u v obrazech nemaj´ı stejnou schopnost predikce ˇcasov´ ych ˇrad. Kromˇe schopnosti pˇresné predikce jsou neuronové s´ıtˇe hodnoceny dalˇs´ımi parametry jako napˇr´ıklad rychlost uˇcen´ı, schopnost zlepˇsit pre25

Obrázek 11: V´ıcevrstvá neuronová s´ıt’

dikci vhodnou u ´pravou a podobnˇe. Pro predikci sobˇepodobného s´ıt’ového provozu lze pouˇz´ıt nˇekterou z následuj´ıc´ıch neuronov´ ych s´ıt´ı, v´ıcevrstvá perceptronnová ’ ’ ’ s´ıt , Elmanova s´ıt [14][41], NARX s´ıt , LTSM s´ıt’, obecná rekurentn´ı s´ıt’ a dalˇs´ı. Pro pˇr´ıklad pouˇzit´ı neuronov´ ych s´ıt´ı je vybrána Elmanova rekurentn´ı neuronová s´ıt’. Elmanova s´ıt’ obsahuje dvˇe vrstvy s algoritmem uˇcen´ı pomoc´ı zpˇetné propagace. Skrytá vrstva má zpˇetnou vazbu skrz stavovou vrstvu na vstupn´ı vrstvu. V kaˇzdém ˇcasovém okamˇziku je moˇzné v´ ystup ze skryté vrstvy pouˇz´ıt jako vstup do stavové vrstvy a ta je v dalˇs´ım kroku pouˇzita jako souˇcást vstupu do celé s´ıtˇe. Struktura Elmanovi s´ıtˇe je zobrazena na obrázku 12. Mnoˇzstv´ı neuron˚ u ve vnitˇrn´ı i stavové vrstvˇe je shodné, váhy spoj˚ u mezi nimi maj´ı hodnotu 1. V´ yhodou neuronov´ ych s´ıt´ı je jejich schopnost generalizace, odhad sloˇzit´ ych jev˚ u a samo korekce. Urˇcitou nev´ yhodou, zvláˇstˇe s orientac´ı na koncová zaˇr´ızen´ı, jsou relativnˇe vysoké poˇzadavky na v´ ypoˇcetn´ı v´ ykon a pamˇet’ov´ y prostor pˇri trénován´ı s´ıtˇe. Po nastaven´ı vah neuron˚ u v s´ıti je následné vyuˇzit´ı relativnˇe nenároˇcné. S´ıt’ je moˇzné trénovat i pr˚ ubˇeˇznˇe pomoc´ı korekce s nov´ ymi daty. Na obrázku 13 je znázornˇena predikce ˇcasové ˇrady, která je stejná jako na obrázku 10, ovˇsem predikovaná pomoc´ı jednoduché dopˇredné neuronové s´ıtˇe s vyuˇzit´ım funkce nnetar z bal´ıku f orecast jazyka R. Funkce nnetar implementuje jednoduchou dopˇrednou neuronovou s´ıt’ s jednou skrytou vrstvou. Pouˇzitá neuronová s´ıt’ má 4 vstupn´ı neurony, 2 skryté a 1 v´ ystupn´ı, predikuje tedy pouze jednu hodnotu. Predikce dalˇs´ıch hodnot je zaˇr´ızena rekurzivn´ım volán´ım s pouˇzit´ım predikovan´ ych hodnot.

26

Obrázek 12: Elmanova neuronová s´ıt’

Obrázek 13: Predikce pomoc´ı NNAR(3,1,2)

27

5.4

Predikce s vyuˇ zit´ım teorie chaosu

S v´ yvojem teorie chaosu se zkoumaj´ı i moˇznosti predikce pomoc´ı této teorie. Metody teorie chaosu na predikci s´ıt’ového provozu jsou aktuálnˇe zkoumané téma podle publikac´ı [20], [15], [26], [40], [9]. S´ıt’ov´ y provoz lze predikovat pomoc´ı teorie chaosu s vyuˇzit´ım Ljapunovova exponentu. Pomoc´ı teorie chaosu lze obecnˇe predikovat chován´ı nelineárn´ıch systém˚ u, které maj´ı nˇejak´ y skryt´ y ˇrád, avˇsak tento ˇra´d nen´ı na prvn´ı pohled viditeln´ y a jev´ı se jako náhodn´ y systém. Chaotické ˇcasové ˇrady je moˇzné znázornit pomoc´ı D dimenzionáln´ıho abstraktn´ıho prostoru stav˚ u zvaného fázov´ y prostor 9. V nˇem kaˇzdá osa pˇredstavuje jednu dimenzi stav˚ u a ˇcas je zde implicitn´ı, vol´ıme ovˇsem zpoˇzdˇen´ı T jako v pˇredchoz´ıch pˇr´ıpadech, které udává z kolika pˇredchoz´ıch hodnot poˇc´ıtáme pˇredpovˇed’. Po urˇcitém ˇcase vyv´ıjen´ı systému vznikne ve fázovém prostoru kˇrivka, tato kˇrivka po dostateˇcnˇe dlouhé dobˇe zaˇcne zv´ yrazˇ novat strukturu, které se ˇr´ıká atraktor[5]. Atraktor pˇredstavuje koneˇcn´ y stav sledovaného systému, obyˇcejnˇe b´ yvá fraktálem.

Y (I), I ∈ [1[N − (D − 1)T ]] : Y (1) = [x(1), x(1 + T ), ..., x(1 + (D − 1)T )] Y (2) = [x(2), x(2 + T ), ..., x(2 + (D − 1)T )] Y (3) = [x(3), x(3 + T ), ..., x(3 + (D − 1)T )] ... Y (I) = [x(I), x(I + T ), ..., x(I + (D − 1)T )]

(9)

Chaotické atraktory maj´ı velkou citlivost na vstupn´ı podm´ınky. Chaotické systémy charakterizuje Ljapun˚ uv exponent, kter´ y urˇcuje stupeˇ n chaotiˇcnosti daného systému. Ljapun˚ uv exponent vyjadˇruje, zda bl´ızké dráhy konverguj´ı nebo diverguj´ı. Pro kaˇzdou dimenzi systému existuje právˇe jeden Ljapun˚ uv exponent. Pro charakteristiku systému je nejd˚ uleˇzitˇejˇs´ı ten nejvˇetˇs´ı, ovlivˇ nuje dlouhodobé chován´ı systému. Jestliˇze je Ljapun˚ uv exponent záporn´ y, dráhy v ˇcase konverguj´ı, takov´ y dynamick´ y systém nen´ı citliv´ y v˚ uˇci poˇca´teˇcn´ım podm´ınkám. V pˇr´ıpadˇe, ˇze je dan´ y exponent kladn´ y, pak dráhy atraktoru mezi sebou diverguj´ı a dan´ y systém je citliv´ y na poˇca´teˇcn´ı podm´ınky. U chaotického systému se mus´ı alespoˇ n v jednom pˇr´ıpadˇe trajektorie drah atraktoru exponenciálnˇe vzdalovat (mus´ı divergovat), tedy mus´ı m´ıt alespoˇ n jeden Ljapun˚ uv exponent kladn´ y. Jeden zp˚ usob jak hodnotu exponentu z´ıskat, je zvolit si nˇekolik bl´ızk´ ych bod˚ u, které necháme v ˇcase rozv´ıjet a pˇritom sledujeme rychlost r˚ ustu jejich vzájemné vzdálenosti. Tento postup se naz´ yvá Wolf˚ uv algoritmus. 28

Pomoc´ı Ljapunovova exponentu lze urˇcit horizont predikce, tedy maximum budouc´ıch bod˚ u, které je moˇzné predikovat. Tento horizont lze vypoˇc´ıtat pomoc´ı rovnice 10. Tmax =

1 λmax

ln

∆ δ0

(10)

Kde λmax je nejvˇetˇs´ı Ljapun˚ uv exponent, ∆ je poˇzadovaná maximáln´ı chyba a δ0 je neurˇcitost v mˇeˇren´ı poˇca´teˇcn´ıch podm´ınek. Ze vztahu je patrné, ˇze ideáln´ı hodnota λmax je bl´ızká nule, z´ıskáme delˇs´ı horizont predikce. Z prac´ı zkoumaj´ıc´ıch vlastnosti s´ıt’ového provozu ovˇsem plyne, ˇze Ljapun˚ uv exponent je v praxi relativnˇe vysok´ y a tak je moˇzné predikovat pouze bl´ızkou budoucnost. Nev´ yhodou predikce pomoc´ı teorie chaosu s vyuˇzit´ım Ljapunova exponentu m˚ uˇze b´ yt nároˇcn´ y v´ ypoˇcet Ljapunova exponentu a jiˇz zm´ınˇená citlivost na poˇcáteˇcn´ı podm´ınky. Jako pˇr´ıklad lze uvést algoritmus prezentuj´ıc pouˇzit´ı tohoto postupu a Ljapunova exponentu [49]. Nejprve zvol´ıme ˇcasovou ˇradu jako pˇredpis 11 a dvoudimenzionáln´ı stavov´ y prostor.

x(0) = 0.36 x(t + 1) = 4 ∗ x(t) ∗ (1 − x(t))

(11)

Pouˇzitá ˇcasová ˇrada je znázornˇena na obrázku 14 a ve stavovém prostoru pak 15.

ˇ Obrázek 14: Casov´ a ˇrada dle definice 11

29

ˇ Obrázek 15: Casov´ a ˇrada 11 ve 2D prostoru podle 9

Novou predikovanou hodnotu pak hledáme pomoc´ı existuj´ıc´ıch kˇrivek a nejkratˇs´ıch vzdálenost´ı. Známe pozici posledn´ıho bodu fázového prostoru a hledáme nejbliˇzˇs´ı bod na dalˇs´ıch kˇrivkách v okol´ı, z´ıskáme vzdálenost D0 . Následnˇe, na základˇe spoˇc´ıtaného Ljapunova exponentu, odhadneme vzdálenost D1 tˇechto dvou kˇrivek v dalˇs´ım kroku. A v dané vzdálenosti od dalˇs´ıho bodu na nalezené bl´ızké kˇrivce najdeme nov´ y bod ˇcasové ˇrady ve fázovém prostoru. Zpˇetn´ ym pˇrevodem souˇradnice z fázového prostoru z´ıskáme novou hodnotu x(t+1). Postup lze zpˇresˇ novat porovnán´ım v´ ysledk˚ u s vyuˇzit´ım jiného, vyˇsˇs´ıho poˇctu, dimenz´ı.

5.5

Dalˇ s´ı metody predikce

V souˇcasném vˇedeckém zkoumán´ı a publikac´ıch se nejˇcastˇeji objevuj´ı metody predikce zaloˇzené na optimalizaci souˇcasn´ ych a popsan´ ych metod nebo na kombinaci nˇekolika dostupn´ ych metod vedouc´ı k zpˇresnˇen´ı predikce. V publikac´ıch je ˇreˇsena predikce napˇr´ıklad pomoc´ı skryt´ ych Markovsk´ ych model˚ u, které pouˇz´ıvá k predikci napˇr´ıklad práce [32]. Pˇr´ıkladem hybridn´ıch metod m˚ uˇze b´ yt napˇr´ıklad spojen´ı lineárn´ı ortogonáln´ı kovariance a neuronové s´ıtˇe [45]. Pouˇziteln´ y pro potˇreby predikce pro smˇerován´ı v pˇrekryvn´ ych s´ıt´ıch by mohl b´ yt i nˇekter´ y z rozˇs´ıˇren´ ych Kalmanov´ ych filtr˚ u [31], které jsou aplikovatelné i na nelineárn´ı systémy. 30

6

Teze disertaˇ cn´ı pr´ ace

Pˇredmˇetem aktuáln´ıho zkoumán´ı je dynamické smˇerován´ı v pˇrekryvn´ ych s´ıt´ıch s vyuˇzit´ım predikce. V dosavadn´ıch prac´ıch jsem se zamˇeˇroval na dynamické smˇerován´ı v distribuovaném souborovém systému (DFS). Po p˚ uvodn´ım zaveden´ı smˇerován´ı v rámci distribuovaného souborového systému[33] jsem navrhl rozˇs´ıˇren´ y algoritmus smˇerován´ı na základˇe typu zpráv a jejich klasifikaci do skupin podle poˇzadavk˚ u na pˇrenos. Tento algoritmus byl publikován jako teze [34] a následnˇe prakticky ovˇeˇren. Realizovan´ y algoritmus má pozitivn´ı dopad na ˇcas doruˇcen´ı jednotliv´ ych zpráv a také na celkovou odezvou DFS. V´ ysledky byly publikovány na konferenci[35]. Nejen v distribuovaném souborovém systému lze rozliˇsovat nˇekolik skupin zpráv, jejich poˇzadavk˚ u na pˇrenos a dostupn´ ych komunikaˇcn´ıch kanál˚ u. Rozhodl jsem se proto ˇreˇsenou oblast zobecnit a aplikovat na ˇsirˇs´ı skupinu problém˚ u. Pro aplikaci dalˇs´ıho zkoumán´ı jsem zvolil pˇrekryvné s´ıtˇe, kde hledám vhodnou aplikaci znám´ ych princip˚ u v kombinaci s vyuˇzit´ım predikce. Predikce v tomto návrhu umoˇzn ˇuje proaktivnˇe dynamicky mˇenit smˇerován´ı, at’ uˇz na základˇe vlastnost´ı aktuáln´ıch nebo predikovan´ ych parametr˚ u (vlastnosti linek, zat´ıˇzen´ı distribuované aplikace). Oblast´ı, na kterou se aktuálnˇe zamˇeˇruji, je vyuˇzit´ı r˚ uzn´ ych algoritm˚ u a postup˚ u predikce stavu linek a predikce poˇzadavk˚ u na distribuovanou aplikaci pˇri v´ ypoˇctu smˇerovac´ıch tabulek. Algoritmy smˇerován´ı plánuji implementovat a porovnat podle jejich efektivity, vyuˇzit´ı zdroj˚ u a pouˇzitelnosti pˇri efektivn´ım smˇerován´ı v pˇrekryvn´ ych s´ıt´ıch. Dále bude zkoumán vliv pˇresnosti predikce na v´ ysledné smˇerován´ı (faleˇsné zmˇeny ve smˇerován´ı vlivem lokáln´ıch extrém˚ u). Zmˇena smˇeru datového toku nen´ı zcela triviáln´ı a pˇrináˇs´ı nutnou reˇzii pro vytvoˇren´ı a pˇrepnut´ı pˇrenosov´ ych tras, c´ılem tedy bude i nalezen´ı takové kombinace algoritm˚ u a postup˚ u, které budou tuto reˇzii minimalizovat. Aktuáln´ı publikace se pˇreváˇznˇe vˇenuj´ı pˇresnosti predikce, nebo efektivn´ımu smˇerován´ı na základˇe predikce v mobiln´ıch nebo optick´ ych s´ıt´ıch a internetu[29][23][27][42][3][48][28]. Mobiln´ı s´ıtˇe jsou pˇrekryvn´ ym s´ıt´ım podobné, ˇcasto zde vznikaj´ı a zanikaj´ı spojen´ı, uzly se v s´ıti volnˇe stˇehuj´ı, docház´ı k ˇcast´ ym zmˇenám topologie odchodem nebo pˇr´ıchodem uzl˚ u atp. Optické s´ıtˇe jsou oproti tomu relativnˇe stabiln´ı a predikce je vyuˇzita pˇredevˇs´ım pˇri pˇrep´ınán´ı a alokaci pˇrenosov´ ych kanál˚ u (Automatically Switched Optical Networks a Generalized Multiprotocol Label Switching). V disertaˇcn´ı práci budou navrˇzeny takové algoritmy, které budou efektivnˇe vyuˇz´ıvat dostupné v´ ypoˇcetn´ı prostˇredky s ohledem na pˇresnost predikce a následné smˇerován´ı na jej´ım základˇe. Navrˇzené algoritmy budou ovˇeˇreny na vybrané distribuované aplikaci. Pˇredpokládanou aplikac´ı je distribuovan´ y souborov´ y systém, kter´ y byl vyv´ıjen v pˇredchoz´ıch prac´ıch. 31

7

Z´ avˇ er

V odborné práci ke státn´ı doktorské zkouˇsce byly popsány oblasti, kde se aktuálnˇe pˇrekryvné s´ıtˇe nejv´ıce uplatˇ nuj´ı. Tˇemito oblastmi jsou pˇredevˇs´ım P2P s´ıtˇe, s´ıtˇe poskytuj´ıc´ı komunikaˇcn´ı infrastrukturu s´ıtˇe pro zajiˇstˇen´ı anonymn´ı komunikace (TOR), s´ıtˇe poskytuj´ıc´ı efektivn´ı doruˇcován´ı dat (CDN, CAN), s´ıtˇe poskytuj´ıc´ı ˇr´ızen´ı kvality pˇrenosu (VoIP, IPTV), s´ıtˇe pro podporu skupinového vys´ılán´ı (MBone) nebo prostˇredky pro implementaci nov´ ych protokol˚ u a technologi´ı (6BONE). Následnˇe byly popsány motivace a metody smˇerován´ı pouˇzité v r˚ uzn´ ych druz´ıch pˇrekryvn´ ych s´ıt´ı. Kaˇzdá s´ıt’ má pro smˇerován´ı r˚ uznou motivaci. Peer to peer s´ıtˇe vyuˇz´ıvaj´ı smˇerován´ı pˇredevˇs´ım k efektivn´ımu nalezen´ı zdroje v distribuovaném prostˇred´ı s co nejniˇzˇs´ı sloˇzitost´ı vyhledáván´ı, poˇctu skok˚ u v prostoru. Anonymizaˇcn´ı s´ıtˇe sleduj´ı smˇerovac´ımi strategiemi pˇredevˇs´ım zaruˇcen´ı anonymity a zabezpeˇcen´ı pˇrenáˇseného obsahu. S´ıtˇe pro doruˇcován´ı obsahu nebo nab´ızej´ıc´ı sluˇzby garance kvality sluˇzeb, kde se pˇredevˇs´ım jedná o splnˇen´ı nˇekterého z v´ ykonnostn´ıch parametr˚ u, sleduj´ı smˇerovac´ımi strategiemi pˇredevˇs´ım splnˇen´ı tˇechto poˇzadavk˚ u. Vyhledávaj´ı a buduj´ı spojen´ı, která zajist´ı co nejrychlejˇs´ı doruˇcen´ı dat do c´ıle nebo naopak i pˇres niˇzˇs´ı pˇrenosovou kapacitu vyhledávaj´ı spoje podle co nejniˇzˇs´ı zpoˇzdˇen´ı. Dalˇs´ım sledovan´ ym parametrem, kter´ y je pro smˇerován´ı kl´ıˇcov´ y, je napˇr´ıklad stabilita linky a jej´ı spolehlivost nebo pˇredpokládaná zátˇeˇz pˇrekryvné s´ıtˇe. Efektivn´ı a pruˇzná reakce je v dalˇs´ıch kapitolách práce podpoˇrena predikc´ı vlastnost´ı jednotliv´ ych linek a moˇznost´ı proaktivnˇe mˇenit smˇerovac´ı tabulky a nastaven´ı linek, aby byly splnˇeny poˇzadavky na danou pˇrekryvnou s´ıt’. V kapitole, která popisovala aktuáln´ı metody predikce s´ıt’ového provozu, byly popsány nejˇcastˇeji pouˇz´ıvané algoritmy, které se v r˚ uzn´ ych vˇedn´ıch oborech pouˇz´ıvaj´ı pro predikci sobˇepodobn´ ych systém˚ u. Na tuto kapitolu bylo navázáno smˇerem dalˇs´ıho v´ yzkumu a c´ıli disertaˇcn´ı práce, kde popisuji dalˇs´ı moˇznosti v´ yvoje a optimalizace existuj´ıc´ıch postup˚ u. Zv´ yˇsen´ı efektivity v pˇr´ıpadˇe vyuˇzit´ı predikce pro smˇerován´ı v pˇrekryvn´ ych s´ıt´ıch a zajiˇstˇen´ı odpov´ıdaj´ıc´ı kvality sluˇzeb hodlám zkoumat pˇredevˇs´ım s ohledem na vyuˇzit´ı v´ ypoˇcetn´ıch zdroj˚ u a vliv nároˇcnosti u ´lohy a vlivu jej´ı pˇresnosti na v´ ysledné smˇerován´ı.

32

Reference [1] David Andersen, Hari Balakrishnan, Frans Kaashoek, and Robert Morris. Resilient overlay networks. SIGOPS Oper. Syst. Rev., 35(5):131–145, October 2001. [2] Cesnet.cz. Cesnet — prostˇred´ı pro v´ yvoj a testován´ı (planetlab), 2015. [3] J. K. Chiang and Y. H. Lin. A simulation and prediction model for internet traffic and qos based on 1-step markov-chain. In Computer Modelling and Simulation (UKSim), 2014 UKSim-AMSS 16th International Conference on, pages 468–473, March 2014. [4] Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W Hong. Freenet: A distributed anonymous information storage and retrieval system. In Designing Privacy Enhancing Technologies, pages 46–66. Springer, 2001. ˇ [5] Vlastimil Clupek. Nelineárn´ı analýza a predikce s´ıt’ového provozu. PhD thesis, Vysoké uˇcen´ı technické v Brnˇe. Fakulta elektrotechniky a komunikaˇcn´ıch technologi´ı, 2012. [6] M.E. Crovella and A. Bestavros. Self-similarity in world wide web traffic: evidence and possible causes. Networking, IEEE/ACM Transactions on, 5(6):835–846, Dec 1997. [7] Roger Dingledine, Nick Mathewson, and Paul Syverson. Tor: The secondgeneration onion router. Technical report, DTIC Document, 2004. [8] Hans Eriksson. Mbone: The multicast backbone. Commun. ACM, 37(8):54– 60, August 1994. [9] Ashok Erramilli, Matthew Roughan, Darryl Veitch, and Walter Willinger. Self-similar traffic and network dynamics. Proceedings of the IEEE, 90(5):800–819, 2002. [10] Michael J Freedman. Experiences with coralcdn: A five-year operational view. In NSDI, pages 95–110, 2010. [11] Yang Han, K. Koyanagi, T. Tsuchiya, T. Miyosawa, and H. Hirose. A trustbased routing strategy in structured p2p overlay networks. In Information Networking (ICOIN), 2013 International Conference on, pages 77–82, Jan 2013. [12] YT Hou, Z Duan, and Z Zhang. Service overlay networks: Sla, qos and bandwidth provisioning. In Proc. IEEE ICNP, volume 2, 2002.

33

[13] Ma Hui and Yange Chen. Research on p2p routing model based on clustering and position of nodes. In Computer Science and Automation Engineering (CSAE), 2011 IEEE International Conference on, volume 2, pages 307–311, June 2011. [14] Wang Junsong, Wang Jiukun, Zeng Maohua, and Wang Junjie. Prediction of internet traffic based on elman neural network. In Control and Decision Conference, 2009. CCDC ’09. Chinese, pages 1248–1252, June 2009. ´ ˇ [15] Jan KACALEK and Ivan MÍCA. Nelineárn´ı anal´ yza a predikce s´ıt’ového provozu. VUT v Brnˇe, Elektrorevue, 2009. [16] Ryoichi Kawahara, Shigeaki Harada, Noriaki Kamiyama, Tatsuya Mori, Haruhisa Hasegawa, and Akihiro Nakao. Traffic engineering using overlay network. In Communications (ICC), 2011 IEEE International Conference on, pages 1–6. IEEE, 2011. [17] Keith Kirkpatrick. Software-defined networking. Commun. ACM, 56(9):16– 19, September 2013. [18] John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski, Patrick Eaton, Dennis Geels, Ramakrishan Gummadi, Sean Rhea, Hakim Weatherspoon, Westley Weimer, et al. Oceanstore: An architecture for global-scale persistent storage. ACM Sigplan Notices, 35(11):190–201, 2000. [19] Will E. Leland, Murad S. Taqqu, Walter Willinger, and Daniel V. Wilson. On the self-similar nature of ethernet traffic (extended version). IEEE/ACM Trans. Netw., 2(1):1–15, February 1994. [20] Dou Li, Binghui Ji, and Haige Xiang. The on-line prediction of self-similar traffic based on chaos theory. In 2006 International Conference on Wireless Communications, Networking and Mobile Computing, pages 1–4, 2006. [21] Michael R Macedonia and Donald P Brutzman. Mbone provides audio and video across the internet. Computer, 27(4):30–36, 1994. [22] Yun Mao, Björn Knutsson, Honghui Lu, and Jonathan M Smith. Dharma: Distributed home agent for robust mobile access. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 2, pages 1196–1206. IEEE, 2005. [23] P. Millan, C. Molina, E. Medina, D. Vega, R. Meseguer, B. Braem, and C. Blondia. Tracking and predicting link quality in wireless community networks. In 2014 IEEE 10th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), pages 239– 244, Oct 2014. 34

[24] Larry Peterson, Andy Bavier, Marc E. Fiuczynski, and Steve Muir. Experiences building planetlab. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation, OSDI ’06, pages 351–366, Berkeley, CA, USA, 2006. USENIX Association. [25] Larry Peterson and Timothy Roscoe. The design principles of planetlab. ACM SIGOPS operating systems review, 40(1):11–16, 2006. [26] Vitaly Petroff. Self-similar network traffic: From chaos and fractals to forecasting and. [27] L. Pradittasnee. Predicting path quality with cross-layer information in multi-hop wireless networks. In 2015 7th International Conference on Information Technology and Electrical Engineering (ICITEE), pages 464–469, Oct 2015. [28] B. Puype, E. Mar´ın-Tordera, D. Colle, S. Sánchez-López, M. Pickavet, X. Masip-Bruin, and P. Demeester. Prediction-based routing as rwa in multilayer traffic engineering. Photonic Network Communications, 23(2):172–182, 2012. cited By 0. [29] W. Ramirez, X. Masip-Bruin, E. Mar´ın-Tordera, M. Yannuzzi, A. Martinez, S. Sánchez-López, and V. López. An hybrid prediction-based routing approach for reducing routing inaccuracy in optical transport networks. In Networks and Optical Communications - (NOC), 2014 19th European Conference on, pages 147–152, June 2014. [30] Robert Gentleman Ross Ihaka. R: A language for data analysis and graphics. Journal of Computational and Graphical Statistics, 5(3):299–314, 1996. [31] Dominik Sierociuk and Andrzej Dzielinski. Fractional kalman filter algorithm for the states, parameters and order of fractional system estimation. International Journal of Applied Mathematics and Computer Science, 16(1):129, 2006. [32] R Sivakumar, E Ashok Kumar, and G Sivaradje. Prediction of traffic load in wireless network using time series model. In Process Automation, Control and Computing (PACC), 2011 International Conference on, pages 1–6. IEEE, 2011. [33] Jindˇrich Skupa. Kivfs - synchronizace a trasován´ı poˇzadavk˚ u. Master’s thesis, Západoˇceská univerzita v Plzni, Západoˇceská univerzita v Plzni. Fakulta aplikovan´ ych vˇed. Katedra informatiky a v´ ypoˇcetn´ı techniky, 2012. [34] Jindˇrich Skupa. Optimalizace synchronizaˇcn´ı komunikace v dfs. In PAD Sborn´ık pˇr´ıspˇevk˚ u PAD 2014, pages 117–122. TU Liberec, 2014. 35

ˇ r´ık. Dynamic internal message [35] Jindˇrich Skupa, Luboˇs Matˇejka, and Jiˇr´ı Safaˇ routing in distributed file system. In Scientific Conference on Informatics, 2015 IEEE 13th International, pages 236–240, Nov 2015. [36] Neil Spring, Larry Peterson, Andy Bavier, and Vivek Pai. Using planetlab for network research: myths, realities, and best practices. ACM SIGOPS Operating Systems Review, 40(1):17–24, 2006. [37] P. Syverson. Onion routing for resistance to traffic analysis. In DARPA Information Survivability Conference and Exposition, 2003. Proceedings, volume 2, pages 108–110 vol.2, April 2003. [38] G. Terdik and T. Gyires. Does the internet still demonstrate fractal nature? In Networks, 2009. ICN ’09. Eighth International Conference on, pages 30– 34, March 2009. [39] Jelle van den Hooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich. Vuvuzela: Scalable private messaging resistant to traffic analysis. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP ’15, pages 137–152, New York, NY, USA, 2015. ACM. [40] Andras Veres and Miklos Boda. The chaotic nature of tcp congestion control. In INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 3, pages 1715–1723. IEEE, 2000. [41] Xuqi Wang, Chuanlei Zhang, and Shanwen Zhang. Modified elman neural network and its application to network traffic prediction. In Cloud Computing and Intelligent Systems (CCIS), 2012 IEEE 2nd International Conference on, volume 02, pages 629–633, Oct 2012. [42] Y. Wei and J. Wang. A delay/disruption tolerant routing algorithm based on traffic prediction. In The 27th Chinese Control and Decision Conference (2015 CCDC), pages 3253–3258, May 2015. [43] W. Willinger. Self-similarity in wide-area network traffic. In Lasers and Electro-Optics Society Annual Meeting, 1997. LEOS ’97 10th Annual Meeting. Conference Proceedings., IEEE, volume 2, pages 462–463 vol.2, Nov 1997. [44] Shun-an Wu, Qiao Yan, Xue-song Qiu, and Yanjie Ren. A probe prediction approach to overlay network monitoring. In Proceedings of the 7th International Conference on Network and Services Management, pages 465–469. International Federation for Information Processing, 2011.

36

[45] Lin Xiang, Xiao-Hu Ge, Chuang Liu, Lei Shu, and Cheng-Xiang Wang. A new hybrid network traffic prediction method. In Global Telecommunications Conference (GLOBECOM 2010), 2010 IEEE, pages 1–5. IEEE, 2010. [46] Xipeng Xiao, A. Hannan, B. Bailey, and L.M. Ni. Traffic engineering with mpls in the internet. Network, IEEE, 14(2):28–33, Mar 2000. [47] Zhiyong Xu, Rui Min, and Yiming Hu. Hieras: a dht based hierarchical p2p routing algorithm. In Parallel Processing, 2003. Proceedings. 2003 International Conference on, pages 187–194, Oct 2003. [48] Zhi yuan LI, Ru chuan WANG, Zhi jie HAN, Jun lei BI, and Chong HAN. Traffic prediction-based routing algorithm over structured p2p networks. The Journal of China Universities of Posts and Telecommunications, 18, Supplement 1:23 – 27, 2011. [49] Jun Zhang, KC Lam, WJ Yan, Hang Gao, and Yuan Li. Time series prediction using lyapunov exponents in embedding phase space. Computers & Electrical Engineering, 30(1):1–15, 2004.

37

Jindřich Skupa. University of West Bohemia in Pilsen Department of Computer Science and Engineering Univerzitni Pilsen Czech Republic

Recommend Documents