LOKALIZACE STANIC V INTERNETU POMOCÍ SYSTÉMU LIGHTHOUSES

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY

FAKULTA ELEKTROTECHNIKY A KOMUNIKAČNÍCH TECHNOLOGIÍ ÚSTAV TELEKOMUNIKACÍ FACULTY OF ELECTRICAL ENGINEERING AND COMMUNICATION DEPARTMENT OF TELECOMMUNICATIONS

LOKALIZACE STANIC V INTERNETU POMOCÍ SYSTÉMU LIGHTHOUSES LOCALIZATION OF NODES IN INTERNET USING LIGHTHOUSES SYSTEM

BAKALÁŘSKÁ PRÁCE BACHELOR'S THESIS

AUTOR PRÁCE

LUKÁŠ SMRČKA

AUTHOR

VEDOUCÍ PRÁCE SUPERVISOR

BRNO 2011

doc. Ing. DAN KOMOSNÝ, Ph.D.

VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ Fakulta elektrotechniky a komunikačních technologií Ústav telekomunikací

Bakalářská práce bakalářský studijní obor Teleinformatika Lukáš Smrčka 3

Student: Ročník:

ID: 74577 Akademický rok: 2010/2011

NÁZEV TÉMATU:

Lokalizace stanic v Internetu pomocí systému Lighthouses POKYNY PRO VYPRACOVÁNÍ: Seznamte se s principy vyhodnocování logické polohy stanic v síti Internet. Prostudujte lokalizační algoritmus s názvem Lighthouses a následně proveďte jeho realizaci v operačním systému GNU/Linux distribuce CentOS. Seznamte se s experimentální sítí PlanetLab http://www.planet-lab.org/. Na zvolené stanice této sítě přeneste vytvořenou aplikaci a ověřte její činnost na reálných serverech rozmístěných na různých místech zeměkoule. Zhodnoťte dosahovanou přesnost a rychlost odhadu vzdáleností mezi stanicemi v síti PlanetLab. DOPORUČENÁ LITERATURA: [1] PIAS, M. et al. Lighthouses for scalable distributed location [online]. Lecture Notes in Computer Science. Springer Berlin/Heidelberg, 2003. URL: [cit. 13. 10 2009]. [2] EUGENE, T. S., ZHANG, H. Predicting Internet Network Distance with Coordinates-Based Approaches. Proceedings of 21st Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2002. [3] PlanetLab Consortium. PlanetLab: An open platform for developing, deploying, and accessing planetary-scale services. URL: [cit. 13. 10. 2009]. Termín zadání:

7.2.2011

Vedoucí práce:

doc. Ing. Dan Komosný, Ph.D.

UPOZORNĚNÍ:

Termín odevzdání:

2.6.2011

prof. Ing. Kamil Vrba, CSc. Předseda oborové rady

Autor bakalářské práce nesmí při vytváření bakalářské práce porušit autorská práva třetích osob, zejména nesmí zasahovat nedovoleným způsobem do cizích autorských práv osobnostních a musí si být plně vědom následků porušení ustanovení § 11 a následujících autorského zákona č. 121/2000 Sb., včetně možných trestněprávních důsledků vyplývajících z ustanovení části druhé, hlavy VI. díl 4 Trestního zákoníku č.40/2009 Sb.

ABSTRAKT Tato práce se zabývá problematikou lokalizace stanic v Internetu pomocí umČlých souĜadnicových systémĤ. Tyto systémy slouží k odhadu hodnoty zpoždČní RTT mezi jednotlivými stanicemi. Odhadovaná hodnota zpoždČní mĤže stanici sloužit napĜ. k efektivnímu výbČru druhé stanice pro komunikaci mezi dvČma stanicemi, bez nutnosti mČĜení tČchto hodnot, což snižuje zatížení sítČ. V první þásti této práce je vysvČtlena problematika systémĤ pro predikci zpoždČní, kde jsou teoreticky vysvČtleny metody Vivaldi, King, GNP a Lighthouses. Po vysvČtlení uvedené problematiky jsou v další þásti této práce nastínČny základní informace o prostĜedí, ve kterém má být vybraná metoda realizována. V poslední þásti práce je pak popsána metoda Lighthouses a program navržený pro použití v experimentální síti PlanetLab s následným zhodnocením dosahované pĜesnosti odhadu.

KLÍýOVÁ SLOVA Predikce

zpoždČní,

umČlé

souĜadnicové

systémy,

Vivaldi,

King,

GNP,

Lighthouses, PlanetLab.

ABSTRACT The thesis is focused on the localization of stations in the Internet with the help of artificial coordinate systems. These systems can be used to estimate the delay value of RTT between individual stations. The estimated delay value can e.g. help the station to choose an optimal second station for communication between two stations without the necessity to measure these values, which reduces the load of the net. The first part of the thesis describes systems that predict the delay and explains how the methods Vivaldi, Kings, GNP and Lighthouses work. The next part of the work gives basic information about environment where the chosen method shall be implemented. The final part defines both the Lighthouses method and a program designed to be used in the experimental PlanetLab network and it also evaluates achieved accuracy of the estimation.

KEYWORDS Prediction delays, virtual coordinate based location systems, Vivaldi, King, GNP, Lighthoueses, PlanetLab.

SMRýKA, L. Lokalizace stanic v Internetu pomocí systému Lighthouses. Brno: Vysoké uþení technické v BrnČ, Fakulta elektrotechniky a komunikaþních technologií. Ústav telekomunikací, 2011. 39 s.. BakaláĜská práce. Vedoucí práce: doc. Ing. Dan Komosný, Ph.D.

PROHLÁŠENÍ Prohlašuji, že svou bakaláĜskou práci na téma Lokalizace stanic v Internetu pomocí systému Lighthouses jsem vypracoval samostatnČ pod vedením vedoucího bakaláĜské práce a s použitím odborné literatury a dalších informaþních zdrojĤ, které jsou všechny citovány v práci a uvedeny v seznamu literatury na konci práce. Jako autor uvedené bakaláĜské práce dále prohlašuji, že v souvislosti s vytvoĜením této bakaláĜské práce jsem neporušil autorská práva tĜetích osob, zejména jsem nezasáhl nedovoleným zpĤsobem do cizích autorských práv osobnostních a/nebo majetkových a~jsem si plnČ vČdom následkĤ porušení ustanovení § 11 a následujících zákona þ. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o zmČnČ nČkterých zákonĤ (autorský zákon), ve znČní pozdČjších pĜedpisĤ, vþetnČ možných trestnČprávních dĤsledkĤ vyplývajících z ustanovení þásti druhé, hlavy VI. díl 4 Trestního zákoníku þ. 40/2009 Sb. V BrnČ dne ..............................

.................................... (podpis autora)

PODċKOVÁNÍ DČkuji vedoucímu bakaláĜské práce doc. Ing. Danu Komosnému, Ph. D. za úþinnou metodickou, pedagogickou a odbornou pomoc a další cenné rady pĜi zpracování mé bakaláĜské práce.

V BrnČ dne ..............................

.................................... (podpis autora)

OBSAH Seznam obrázkĤ

ix

Úvod

1

1

Lokalizace stanic v Internetu

3

2

Systémy pro predikci zpoždČní

5

2.1

Metoda Vivaldi ........................................................................................ 5

2.2

Metoda King ............................................................................................ 6

2.3

Metoda Global Network Positioning (GNP)........................................ 7

2.4

Metoda Lighthouses .............................................................................. 8

2.4.1 Hledání majákĤ................................................................................... 9 2.4.2 SouĜadnice lokální báze L ................................................................ 9 2.4.3 SouĜadnice stanice .......................................................................... 10 2.4.4 PĜechodová matice P ...................................................................... 11 3

OS Linux distribuce CentOS

12

4

Experimentální síĢ PlanetLab

13

4.1

Pojmy sítČ PlanetLab........................................................................... 13

4.1.1 Pojem Nod......................................................................................... 14 4.1.2 Pojem Slice ....................................................................................... 14 4.1.3 Pojem Sliver ...................................................................................... 14 4.1.4 Pojem Site ......................................................................................... 14 5

Popis metody Lighthouses realizované v navrženém programu

15

6

Popis navrženého programu

17

6.1

Struktura programu .............................................................................. 17

6.2

PĜíklad chodu programu...................................................................... 22

7

Zhodnocení pĜesnosti metody

24

8

ZávČr

26

Literatura

27

vii

Seznam symbolĤ, veliþin a zkratek

28

Seznam pĜíloh

29

viii

SEZNAM OBRÁZKģ Obr. 1: Logická a fyzická poloha uzlĤ A a B ................................................................... 4 Obr. 2 : Princip þinnosti algorimu Lighthouses ................................................................ 8 Obr. 3 : RozprostĜení uzlĤ PlanetLab ve svČtČ (pĜevzato z [3]) ..................................... 13 Obr. 4 : Kumulativní distribuþní funkce metody Lighthouses 4D ................................. 25

ix

ÚVOD Trendem doby, ve které dnes žijeme je prudký rozmach moderních technologií, mezi nČž patĜí také výpoþetní technika a Internet. Doba ukázala, že samostatná oddČlená pracovištČ, zpracovávající a analyzující mnohdy složité výrobní postupy a procesy, pĜípadnČ pracovištČ jinak pracující s daty která je nutno uchovávat a efektivnČ šíĜit, potĜebují k této þinnosti médium, prostĜednictvím kterého by se šíĜení a sdílení dat stalo efektivním. Ukázalo se, že tímto médiem by mohly být poþítaþové sítČ, zejména pak Internet. Aplikace využívající Internet pro pĜenos dat pak na toto médium kladou vysoké nároky z hlediska šíĜky pásma a urþité hodnoty zpoždČní. Toto zpoždČní mnohdy vypovídá o kvalitČ spojení mezi dvČma komunikujícími body. ObecnČ platí, že þím nižší hodnota zpoždČní tím vyšší je kvalita spoje. Aby tedy bylo šíĜení a sdílení dat mezi komunikujícími body co nejefektivnČjší, mČl by být vybrán spoj, který bude pro pĜenos dat nejvhodnČjší a nejefektivnČjší, to znamená, který má co nejmenší zpoždČní. ZpĤsoby, jak zjistit vhodnost výbČru daného spoje, jsou dva. Prvním zpĤsobem je mČĜení zpoždČní mezi dvČma body, pĜiþemž by první bod provedl mČĜení mezi všemi možnými kandidáty na komunikaci (druhý bod) a na základČ výsledku by provedl výbČr. Toto Ĝešení však pĜináší další zatížení sítČ, které by pĜi velkém poþtu komunikujících zpĤsobovalo zhoršení kvality spoje (nárĤst zpoždČní). Druhý zpĤsob pak hodnotu zpoždČní vypoþítává, napĜ. pomocí umČlých souĜadnicových systémĤ. U tČchto metod je provedeno nejzákladnČjší mČĜení a zbytek je vypoþítáván. Na základČ výsledku je pak vybírán spoj. Tyto metody tedy tolik nezatČžují sítČ a proto jsou efektivnČjší. Tato bakaláĜská práce se proto zabývá principy vyhodnocování logické polohy stanic v síti Internet se zamČĜením zejména na algoritmus Lighthouses. Cílem této práce je funkþní algoritmus Lighthouses, navržený pro operaþní systém Linux distribuce CentOS a jeho otestování v experimentální sítí PlanetLab. V první þásti práce bude proveden teoretický úvod do problematiky s uvedením základních metod pro predikci zpoždČní. V této þásti je nejvíce popsána metoda

1

Lighthouses, která je pro tuto práci hlavní metodou. Po teoretickém rozboru vybraných metod následuje þást, která struþnČ popisuje prostĜedí, v nČmž má být vybraná metoda realizována. V následující þásti je pak popsána vlastní realizace metody vþetnČ popisu navrženého programu a zhodnocení pĜesnosti metody.

2

1

LOKALIZACE STANIC V INTERNETU Problematikou urþování polohy stanic v Internetu se dnes již zabývá mnoho

autorĤ a metod. Je to zejména z dĤvodu dosažení respektive obsazení urþité, zatím ještČ poĜád shora limitované, šíĜky pásma a s tím spojené snahy o jeho, alespoĖ þásteþné, uvolnČní, které je spíše chápáno jako úspora pĜi pĜidČlování a využívání tohoto pásma. Základní myšlenkou tedy je efektivnost využití sítČ. Je zĜejmé, že velkou roli pĜi hledání vhodných algoritmĤ pro zvýšení efektivnosti využití sítČ hraje zejména vzájemná poloha stanic, pĜípadnČ serverĤ þi uzlĤ, hodlajících mezi sebou komunikovat. Pro zjednodušení je v této práci dále místo termínu stanice þi server použit poslední jmenovaný termín – uzel. Vzájemná poloha dvou nebo více uzlĤ mĤže být chápána jak geograficky, tzn. geografické údaje o fyzickém umístnČní daného uzlu, tak logicky, kde je umístnČní chápáno jako relativní pozice v rámci topologie sítČ, v níž se daný uzel nachází. Pro jasnČjší odlišení významu obou druhĤ poloh si pro pĜíklad uvećme dva uzly A a B. Geografický, respektive fyzický spoj z uzlu A do uzlu B mĤže obsahovat i nČkolik dalších mezi-uzlĤ, kdežto logický spoj, je veden jako spoj mezi uzly A a B jako by se jednalo o dva uzly propojené vzájemnČ kabelem „na pĜímo“. Logické spoje tak nad fyzickou topologií vytváĜí tzv. pĜekryvnou síĢ. Uvedený pĜíklad je zobrazen na Obr. 1. Jak je tedy zĜejmé, logická cesta nemusí být vzhledem k fyzické ta nejkratší, pĜesto nČkteré aplikace využívají pĜekryvné sítČ, a s tím tedy výbČr logické cesty, z dĤvodu adresace dat pĜíjemci jiným zpĤsobem, než pomocí IP adres. Mezi nejznámČjší patĜí napĜ. protokol aplikace BitTorrent 1. Pro zefektivnČní výbČru nejvhodnČjší cesty v pĜekryvných sítích bylo tedy nutné vyvinout vhodné algoritmy (respektive metody) a pĜiblížit logický spoj

1

www.bittorrent.com

3

fyzickému. Toto pĜiblížení bylo realizováno parametrem IP sítČ, konkrétnČ mČĜením zpoždČní (RTT) mezi stanicemi. MČĜení je realizováno protokolem ICMP, který je souþástí sady protokolu TCP/IP. PĜi mČĜení zpoždČní RTT by mČlo být nasbíráno co nejvČtší množství vzorkĤ, aby byla dosažena požadovaná pĜesnost. MČĜení vČtšího množství vzorkĤ, však s sebou pĜináší další zatížení sítČ, které se vzrĤstajícím poþtem stanic kvadraticky roste. Aby se tomuto pĜedešlo, byly vyvinuty systémy, umožĖující predikci zpoždČní bez provádČní vlastního mČĜení. MČĜení je zde provádČno jen k nČkolika referenþním uzlĤm, pĜípadnČ není provádČno vĤbec a je využito jiných systémĤ.

Obr. 1: Logická a fyzická poloha uzlĤ A a B

4

2

SYSTÉMY PRO PREDIKCI ZPOŽDċNÍ Systémy pro predikci zpoždČní by se daly rozdČlit do dvou skupin. Jsou to

systémy pro predikci zpoždČní pomocí pĜímého mČĜení a systémy pro predikci zpoždČní za použití umČlých souĜadnicových systémĤ. V této práci se budeme dále zabývat zejména systémy, respektive metody, provádČjící predikci zpoždČní za pomoci umČlých souĜadnicových systémĤ. KonkrétnČ si v této práci uvedeme metody GNP (Global Network Positioning), Vivaldi, King a Lighthouses.

2.1 Metoda Vivaldi Jedná se o algoritmus, o kterém by se z hlediska principu je fungování dalo také Ĝíci, že pracuje s pružinami.[7] Jde o to, že si stanice v Internetu samy spoþítají vlastní souĜadnice v daném prostoru tak, aby vzdálenost mezi nimi pĜesnČ odpovídala namČĜenému RTT mezi nimi. Stanice pak na sebe vzájemnČ pĤsobí témČĜ jako hmotné body uchycené na koncích pružiny. Vzájemným pĤsobením jsou pak po ustálení pružin nalezeny takové souĜadnice, aby odchylka systému byla co nejmenší. Síla pĤsobící na tyto body je dána rozdílem délek pružiny v klidovém a nataženém stavu. Posuv z klidového do nataženého stavu udává mimo jiné. druhou odmocninu potenciální energie pružiny, tedy potenciální energie je rovna druhé mocninČ tohoto posuvu. Pro upĜesnČní lze Ĝíci, že klidový stav pružiny je roven namČĜené hodnotČ RTT a délka pružiny v nataženém stavu udává nalezenou (vypoþtenou) vzdálenost mezi jednotlivými body. Je-li potenciální energie dána druhou mocninou posuvu pružiny, pak chybová funkce E je dána souþtem kvadratických odchylek potenciální energie pružiny [7]

(

E = ¦¦ ε RTTij − si − s j

2

),

(1)

5

RTTij zde pĜedstavuje zmČĜenou vzdálenost mezi stanicemi o souĜadnicích si a sj. [7] Celková síla pĤsobící na stanici je dána vektorovým souþtem Fij, [7]

Fj = ¦ Fij ,

(2)

kde Fij je rovno

(

)

Fij = RTTij − s i − s j × u (s i − s j ) ,

(

výraz RTTij − s i − s j

(3)

) udává posuv pružiny a je tedy roven síle potĜebné

k posuvu. Druhý výraz v rovnici udává smČr posuvu. Algoritmus metody Vivaldi pracuje v malých þasových krocích, jejichž hodnota se pĜi každé iteraci pĜiþte k souĜadnicím stanice, což vede k novým souĜadnicím stanice. Postup se opakuje tak dlouho, dokud není hodnota E v odpovídajících mezích. Vlivem porušování trojúhelníkové rovnosti [7] nelze provést pĜesné mapování souĜadnic.

2.2

Metoda King Metoda King [4] je metodou, nebo chcete-li systémem, který nevyužívá

umČlých souĜadnicových systémĤ. Je to systém využívající existující služby DNS (Domain Name System). Tato služba je vlastnČ zodpovČdná za fungování adresace Internetových webĤ, tak jak je dnes známe. Provádí totiž pĜeklad mezi doménovým jménem (napĜ. www.seznam.cz) na ip adresu stroje (uzlu) na kterém je uvedená (pĜekládaná) doména provozována. Metoda poþítá s existencí serveru DNS, majícího nízkou hodnotu RTT vĤþi stanici v Internetu, u každé stanice v Internetu. Za tohoto pĜedpokladu lze urþovat hodnotu RTT mezi dvČma stanicemi s celkem velkou pĜesností mČĜením mezi DNS servery jednotlivých stanic. Celý princip spoþívá v odeslání dotazu z první stanice na fiktivní stanici z domény druhé stanice. Tím je zajištČno to, že první DNS server nezná na tento dotaz odpovČć a proto je dotaz pĜedán na druhý DNS server. Ten samozĜejmČ

6

fiktivní stanici nezná a vrací odpovČć o neznámem hostu zpČt až k první stanici. Takto je získána hodnota RTT mezi první stanicí a druhým DNS serverem. ObdobnČ zašle první stanice dotaz na první DNS server a získá hodnotu RTT mezi první stanicí a prvním DNS serverem. Rozdílem obou získaných hodnot je hodnota (velikost) RTT mezi obČma DNS servery, tj. mezi první a druhým DNS serverem. Hodnota RTT mezi stanicí a nejbližším DNS serverem se bČžnČ pohybuje kolem 10ms a tak lze bez vČtších problémĤ predikovat hodnotu RTT mezi první a druhou stanicí.

2.3 Metoda Global Network Positioning (GNP) Jedná se o metodu realizující predikci zpoždČní. Metoda je založena na existenci orientaþních bodĤ a mapuje reálnou síĢovou topologii do N – rozmČrného euklidovského prostoru.[7] Z dĤvodu jednoznaþného výpoþtu souĜadnic stanice je zapotĜebí dostatek orientaþních bodĤ, jinak Ĝeþeno referenþních serverĤ.

Minimální poþet je stanoven dimenzí vektorového

prostoru, kde dimenze je p a minimální poþet vybíraných referenþních serverĤ je p+1. Prvním krokem po výbČru referenþních serverĤ je promČĜení zpoždČní RTT mezi všemi orientaþními body. Pomocí tČchto souĜadnic je vytvoĜena matice o velikosti N x N, která udává vzájemné zpoždČní mezi jednotlivými servery. Z takto vzniklé matice jsou pak vypoþteny souĜadnice, které jsou následnČ pĜepoþítány pomocí funkce pro minimalizaci chyby a každému orientaþnímu je pĜidČlen bod ci v euklidovském prostoru.

(

E = ¦¦ ε RTTij si s j

)

(4)

kde ε je chybová funkce a RTTij pĜedstavuje prvky matice zmČĜených vzdáleností. PĜiĜazení souĜadnic jednotlivým bodĤm je základem algoritmu GNP. PĜistupující stanice pak matici souĜadnic považuje za globální bázi a provede zmČĜení zpoždČní k nČkolika orientaþním bodĤm. NáslednČ pomocí vhodné optimalizaþní funkce, napĜ. Simplex Downhill, provede výpoþet vlastních souĜadnic sj v urþeném souĜadnicovém prostoru bez potĜeby mČĜení dalších zpoždČní.

7

2.4 Metoda Lighthouses Metoda Lighthouses [1] je velice podobná metodČ GNP, avšak kompenzuje jeho slabá místa. TČmi mĤže být množina pevnČ daných orientaþních bodĤ, kdy u nich není zcela jasné co by mČl algoritmus GNP udČlat v pĜípadČ nedostupnosti þásti tČchto bodĤ. PĜi návrhu metody Lighthouses byl proto tento nedostatek zohlednČn a pro pĜipojující se stanici mĤže být skupinou serverĤ libovolná skupina serverĤ v systému a pro každou stanici mĤže být tato skupina zcela odlišná. Technika náhodného výbČru orientaþních serverĤ se dle teze [1] nazývá pivotování a každý takto zvolený orientaþní bod zveme pivot. VýbČrem odlišných serverĤ u každé nové stanice se vytváĜejí tzv. mnohonásobné lokální báze.

Metoda

Lighthouses pracuje na principu existence mnohonásobné lokální báze spoleþnČ s tzv. pĜechodovou maticí P ve vektorovém prostoru, kterou musí udržovat aktuální každý server v systému. Každá stanice si pak sama dokáže vypoþítat, pomocí lokální báze a základních matematických operací, její vlastní souĜadnice v systému, které jsou relativní ke skupinČ zvolených orientaþních serverĤ, tzv. majákĤ (z anglického slova lighthouses). Pro možnost predikce zpoždČní RTT mezi servery jiných lokálních bází, je zapotĜebí pĜepoþítat takto získané souĜadnice pomocí pĜechodové matice P. Ta tvoĜí vazbu mezi lokálními bázemi a spoleþnou globální bází souĜadnicového systému a tedy udržování aktuálnosti této matice je dĤležitou þástí systému Lighthouses. Princip metody je zobrazen na Obr. 2.

Obr. 2 : Princip þinnosti algorimu Lighthouses

8

2.4.1 Hledání majákĤ U metody Lighthouses si novČ pĜipojované stanice do pĜekryvné sítČ musí nejprve vytvoĜit seznam referenþních serverĤ, majákĤ, které budou potĜeba pĜi výpoþtu souĜadnic lokální báze. Pro získání seznamu tČchto serverĤ kontaktuje novČ pĜistupující stanice Si jakýkoli server Sj ze souĜadnicového modelu sítČ [6]. Existuje nČkolik zpĤsobĤ, jak tento seznam získat. Pro menší pĜekryvné sítČ, kde se poþet pĜipojených stanic nepohybuje v Ĝádech stovek až tisícĤ by mohl existovat pravidelnČ aktualizovaný seznam, který by si novČ pĜipojující se stanice stáhla a nČjakým zpĤsobem vybrala server, který by kontaktovala, napĜ. první v poĜadí. Pro rozsáhlejší pĜekryvné sítČ by mohla existovat služba, která by tento seznam udržovala a nabízela jeho aktuální verzi. Po zvolení serveru Sj žádá stanice Si tento server o zaslání seznamu referenþních serverĤ, ze kterého si stanice vybere potĜebný poþet majákĤ. Tento poþet je dán dimenzí p vektorového prostoru tvoĜícího model pĜekryvné sítČ následující výrazem p + 1, stejnČ jako u systému GNP. V poþátcích budování vektorového prostoru se mĤže stanice dostat do situace, kdy není k dispozici potĜebný poþet majákĤ, tzn. je-li stanice m-tou stanicí v systému, je m menší nebo rovno p+1, a pĜistupující stanice se pak chová jako „první stanice“ což znamená, že si tato stanice souĜadnice lokální báze musí vypoþítat pomocí serverĤ, které jsou již v systému zapojeny. V okamžiku, kdy má stanice Si vytvoĜen jedním z výše uvedených zpĤsobĤ seznam vlastních majákĤ, mĤže zaþít mČĜit zpoždČní RTT mezi ní a jednotlivými majáky (jak je uvedeno v [1]). Toto mČĜení je stejnČ jako u metody GNP realizováno protokolem ICMP, konkrétnČ pakety ICMP ECHO. Pro pĜesné mČĜení je opČt zapotĜebí nabrat urþité množství vzorkĤ, ze kterých je vypoþtena statistická hodnota mediánu. Takto získá stanice matici zpoždČní o rozmČru p x p, kterou stanice vyžije pĜi výpoþtu souĜadnic lokální báze L.

2.4.2 SouĜadnice lokální báze L Pro výpoþet souĜadnic stanice je nutné nejprve vypoþítat souĜadnice lokální báze L. Lokální bázi o stejné dimenzi p vektorového prostoru tvoĜí množina vektorĤ l1, l2, ….lp; takto

9

L = {l1 , l2 ,..., l p },

(5)

kde každý vektor l je tvoĜen dvojicí majákĤ stanice Si. Tyto dvojice jsou tvoĜeny poþáteþním poziþním serverem a nČkterým dalším poziþním serverem (majákem) a vektor l je z nich vytvoĜen jako rozdíl vektorĤ dvou bodĤ v témže prostoru. Z takto získaných vektorĤ jsou souĜadnice vypoþítávány pomocí GramSchmidtova algoritmu. S aplikací Gram-Schmidtova algoritmu jsou souĜadnice lokální báze vypoþítávány následovnČ: [1] l1 = projw0 l1 + proj ⊥ l2 w0

l2 = projw1 l 2 + proj ⊥ l1 w1

(6)

... = ............. + ............. l p = projw p −1 l p + proj ⊥ l p−1 w p −1

kde proj w p −1 l p je ortogonální promítnutí vektoru lp na podprostor wp-1 a proj ⊥ l p −1 je složka vektoru proj w p −1 l p ortogonální na podprostor wp-1. w p −1

2.4.3 SouĜadnice stanice Jakmile stanice získá souĜadnice své lokální báze mĤže zaþít poþítat vlastní souĜadnice. Z dĤvodu volnosti pĜi výbČru majáku však musíme zajistit, aby vypoþítané vektory l lokální báze byly

lineárnČ nezávislé. Aby byl

algoritmus schopen dále pokraþovat i v pĜípadČ, kdy vektory vypoþítané báze nejsou vzájemnČ ortogonální, jsou souĜadnice stanice Si vypoþítány jako lineární kombinace vektorĤ lokální báze L, Si = c1l1 + c2l2 + ... + c pl p ,

(7)

kde þísla ci jsou Ĝešením následující soustavy lineárních rovnic, uvedených v publikaci [1],

c1 l1 + ... + c pl p cos(l1 , l p ) = si cos(si , l1 ) ... + ... + ... + ... + ... + ... + ... = ............... , c1 l1 cos(l1 , l p ) + ... + c pl p = si cos(si , l p )

10

(8)

výrazy uvedené v této soustavČ rovnic v kulatých závorkách jsou skalárními souþiny vektorĤ, definovaných uvnitĜ závorky. Vektory lx jsou vektory lokální báze pĜed aplikací Gram- Schmidtova algoritmu. ||si|| udává velikost RTT mezi pĜistupující stanicí a poþáteþním poziþním serverem Sj . SouĜadnice Si udává umístnČní právČ poþítané stanice.

2.4.4 PĜechodová matice P Pokud bychom potĜebovali predikovat zpoždČní mezi stanicemi, bylo by to v tomto okamžiku nemožné, protože vypoþtené relativní souĜadnice jsou vztaženy k lokální bázi dané stanice a proto tyto souĜadnice musíme nČjakým zpĤsobem pĜepoþítat na souĜadnice vztažené ke globální bázi. K tomu abychom získali souĜadnice vztažené ke globální bázi bez nČjakého dalšího mČĜení, používá algoritmus Lighthouses pĜechodovou matici P mezi lokální bází L a globální bází G. Tuto matici stanice buć vypoþítá nebo ji obdrží od poziþního referenþního serveru Sj. Pro výpoþet matice je však stanice potĜebuje znát kromČ souĜadnic vlastní lokální báze L ještČ souĜadnice globální báze G. Globální báze G je ve skuteþnosti tvoĜena globálními souĜadnicemi majákĤ vybraných pĜi prvním kroku algoritmu. Pro výpoþet souĜadnic vztažených ke globální bázi pak použijeme vztah uvedený v publikaci [1],

[v]B' = P −1 [v]B

(9)

11

3

OS LINUX DISTRIBUCE CENTOS DĤvodem uvedení této distribuce Linuxu v této práci je použití tČchto

distribucí Linuxu na uzlech v síti PlanetLab. Jedná se o distribuci Linuxu, opírající se o Red Hat Enterprise Linux. Zkratka názvu distribuce CentOS [8] vychází ze spojení þtyĜ anglických slov Community

Enterprise

Operating

System.

Tento

operaþní

systém

je

podporován vlastní komunitou, která zahrnuje systémové administrátory, správce sítí a pokroþilé uživatele Linuxu z celého svČta. Distribuce CentOS je 100% binárnČ kompatibilní s distribucí Red Hat Enterprise Linux, pĜiþemž hlavním rozdílem je odstranČní kreseb, ochranných známek a placených služeb firmy Red Hat. Toto odstranČní bylo provedeno zejména z dĤvodu kolize výše uvedeného s licenþní politikou (Red Hat nepovoluje opakovanou distribuci). Aktuální verze tohoto systému je 5.5. PĜednosti této distribuce, pĜedurþující ji pro použití jak v podnicích, tak ve školách a výzkumu, jsou zejména dány licenþní politikou distribuce a výhodami systému Linux. Konkrétní výhodou Linuxu a tudíž i této distribuce je to, že se jedná o víceúlohový a víceuživatelský operaþní systém. To znamená, že na Linuxu mĤže být pĜihlášeno i nČkolik uživatelĤ najednou a mĤže zde bČžet mnoho aplikací od rĤzných uživatelĤ najednou.

12

4

EXPERIMENTÁLNÍ SÍġ PLANETLAB Jak již napovídá název kapitoly, jedná se o poþítaþovou síĢ vytvoĜenou pro

úþely testování síĢových aplikací a distribuovaných systémĤ.[3] Díky této síti lze tedy testovat vyvíjené aplikace a jejich chování v reálné síti, na stanicích, tzv. uzlech (uzly – z anglického slova node). Tuto síĢ je tedy možné chápat jako soubor uzlĤ, které jsou rozprostĜeny po celém svČtČ, ke kterým je možné, podle jejich dostupnosti, se pĜipojit. Po pĜipojení se k uzlu je pak možné testovat a zkoumat chování námi vyvíjené aplikace v této reálné síti. Názorné rozmístČní uzlĤ ve svČtČ je zobrazeno na Obr. 3.

Obr. 3 : RozprostĜení uzlĤ PlanetLab ve svČtČ (pĜevzato z [3])

Dlužno Ĝíci, že je tato síĢ pĜístupná pouze registrovaným uživatelĤm. Ti jsou vČtšinou þleny organizací a subjektĤ, které se na projektu PlanetLab podílí. V rámci Ĝešení této bakaláĜské práce je tato síĢ využita k testování vyvinutého algoritmĤ a následné promČĜení vlastností predikce metody Lighthouses.

4.1 Pojmy sítČ PlanetLab Pro jednoznaþnou orientaci v prostĜedí PlanetLab následují alespoĖ

13

základní pojmy používané pĜi práci v této experimentální sít.

4.1.1 Pojem Nod Nod, použije-li se pĜeklad z anglického jazyka, uzel. Je to pojem, pod kterým je v síti PlanetLab myšlena jedna konkrétní stanice s urþitou adresou. Na tČchto uzlech jsou pak vytváĜeny virtuální servery, na kterých je možno testovat vyvíjené aplikace.

4.1.2 Pojem Slice Veškerý pĜístup ke zdrojĤm PlanetLabu je Ĝešen pomocí slice (pĜeklad tohoto slova je slovo krajíc). [3] Slice je souborem zdrojĤ, poskytovaných jednotlivými uzly PlanetLabu. PĜi pĜidání uzlu do slice je na tomto uzlu vytvoĜen virtuální server, který je spuštČn po celou dobu existence daného uzlu ve slice. Jakmile je tento uzel ze slice odebrán, zaniká také virtuální server, který byl vytvoĜen pĜi pĜidání uzlu do slice.

4.1.3 Pojem Sliver Sliver je slice, bČžící na vybraném uzlu. Pro pĜihlášení k tomuto sliveru mĤžeme použít libovolného klienta SSH. 4.1.4 Pojem Site Tímto termínem je myšlen subjekt v síti PlanetLab, který je zapojen do projektu PlanetLab. ZároveĖ tento subjekt mĤže mít nČkolik uzlĤ. Jedná se také o fyzickou lokaci uzlĤ sítČ PlanetLab.

14

5

POPIS METODY LIGHTHOUSES REALIZOVANÉ V NAVRŽENÉM PROGRAMU PĜi prozkoumání algoritmu lighthouses dle teze [1][7] je zĜejmé, že

pĜistupující stanice Si ve fázi hledání majákĤ promČĜí hodnotu RTT mezi ní a referenþním poziþním serverem Sj, který byl kontaktován jako první. Dále referenþní poziþní server Sj provede promČĜení hodnot RTT mezi sebou a dalšími poziþními servery (majáky). Poþet majákĤ je dán velikostí dimenze, pro kterou má být algoritmus realizován. Tento poþet je dán vztahem p+1, tak jak je to rozebráno v kapitole 2.4.1. Pro výpoþet souĜadnic lokální báze L je nutné znát souĜadnice jednotlivých poziþních serverĤ, které byly v pĜedchozím kroku algoritmu promČĜeny. PĜi pĜedpokladu volnosti pĜi výbČru majákĤ a vlastností tohoto algoritmu, kterou zmiĖuje teze [5] „existuje mnohem více volnosti než omezení“, lze tyto souĜadnice vygenerovat. Pro správný výpoþet lokální báze, takové, která by odpovídala zmČĜenému prostoru je nutné, aby velikost výsledného vektoru lx odpovídala velikosti zmČĜeného RTT. Vektor lx je pĜitom získán jako rozdíl dvou vektorĤ, tvoĜených souĜadnicemi referenþního poziþního serveru Sj a nČkterého dalšího poziþního serveru Sp. S pĜihlédnutím k výše uvedenému a ke skuteþnosti, že skupinou majákĤ mĤže být libovolná skupina majákĤ, je v navrženém programu referenþní poziþní server vždy ten první a následují ho ostatní poziþní servery. To znaþnČ zjednodušuje zpĤsob mČĜení, protože pak lze Ĝíci, že referenþní poziþní server bude mít vždy souĜadnice Sj{0,0,..0} a tudíž mohou být všechna potĜebná mČĜení, k ostatním poziþním serverĤm a pĜistupujícím stanicím, provedena právČ z tohoto serveru. Po vzniku lokální báze L tak jak jej popisuje pĜedchozí odstavec, je na takovouto bázi aplikován algoritmus Gram-Schmidt pro získání ortogonální báze. Tuto bázi pak již použijeme pĜi výpoþtu konstant cx, které jsou Ĝešením soustavy lineárních rovnic rov.(8). Pro názornost nyní následuje pĜíklad soustavy tČchto rovnic pro dimenzi o rozmČru 4:

15

c1 l1 + c2l2 cos(l2 , l1 ) + c3l3 cos(l3 , l1 ) + c4l4 cos(l4 , l1 ) = si cos(si , l1 ) c1 l1 cos(l1 , l2 ) + c2l2 + c3l3 cos(l3 , l2 ) + c4l4 cos(l4 , l2 ) = si cos(si , l2 ) c1 l1 cos(l1 , l3 ) + c2l2 cos(l2 , l3 ) + c3l3 + c4l4 cos(l4 , l3 ) = si cos(si , l3 ) c1 l1 cos(l1 , l4 ) + c2l2 cos(l2 , l4 ) + c3l3 cos(l3 , l4 ) + c4l4 = si cos(si , l4 )

(9)

kde cos(lx,ly) je vypoþítán jako úhel svíraný dvČma vektory následovnČ:

cos ϕ =

l x1 ⋅ l y1 + l x 2 ⋅ l y 2 2

§¨ l 2 + l 2 ·¸ + §¨ l 2 + l 2 ·¸ x2 y2 © x1 ¹ © y1 ¹

2

(10)

V rovnici (9) je jako konstanta ||si|| chápáno zpoždČní RTT mezi pĜistupující stanicí Si a referenþním poziþním serverem Sj. SouĜadnicí si jsou pak myšleny souĜadnice pĜistupující stanice. Je zĜejmé, že aby bylo možné soustavu lineárních rovnic vyĜešit a vhledem k faktu, že pro každou stanici budou konstanty cx odlišné, je tĜeba vygenerovat pĜedpokládané souĜadnice si tak, aby odpovídaly zpoždČní ||si|| a pĜíslušné velikosti Ĝešené dimenze. Po výpoþtu souĜadnic cx již je možné pĜistoupit k výpoþtu souĜadnic dle rovnice (7) a po jejich získání vypoþteme velikost tohoto vektoru. Díky tomu, že všechny pĜistupující stanice využívají souĜadnicový systém globální báze G, není nutné pĜepoþítávat souĜadnice pomocí pĜechodové matice P. Výsledná velikost vypoþteného vektoru je tedy rovna velikosti hledaného zpoždČní RTT.

16

6

POPIS NAVRŽENÉHO PROGRAMU PĜi návrhu algoritmu bylo vycházeno ze skuteþnosti, že algoritmus má být

použit na uzlech s instalovaným OS Linux CentOS. Pro zajištČní pĜedpokladu kompatibility s ostatními distribucemi Linuxu a z toho dĤvodu, aby pĜi zmČnČ konfiguraþních parametrĤ nebylo nutné provádČt kompilaci programu, byl zvolen jako skriptovací jazyk BASH. Je souþástí snad každé distribuce Linuxu a proto myšlenka pĜenositelnosti mezi jednotlivými uzly v experimentální síti PlanetLab je reálnou skuteþností. Ne všechno však lze snadno a efektivnČ vyĜešit pouze s použitím tohoto skriptovacího jazyka a proto je souþástí navrženého programu také þást napsaná v programovacím jazyku C.

6.1 Struktura programu Navržený program je logicky rozdČlen do þtyĜ hlavních þástí, které jsou pĜedstavovány jednotlivými soubory programu. Jsou to tyto soubory: main.sh, calculate.sh, config a soubor matice.c, který je již dopĜedu zkompilován pro potĜeby programu pro jednotlivé dimenze. Jak je již z názvu patrné, soubor main.sh je z hlediska bČhu a jeho spouštČní hlavním souborem programu. Je to jeden ze dvou souborĤ psaných ve skriptovacím jazyce BASH. Jeho hlavním úkolem je vyþištČním resp. výmaz souborĤ vygenerovaných pĜi pĜedchozím spuštČní programu, promČĜení parametrĤ testované sítČ a generace pĜedpokládaných souĜadnic uzlĤ. SpuštČním souboru jsou generovány tĜi výstupní soubory, které poté slouží jako vstupní data souboru calculate.sh. TĜemi zmiĖovanými výstupními soubory jsou: merene_servery.txt – kde jsou chronologicky uloženy adresy serverĤ tak jak jsou postupnČ mČĜeny pĜi promČĜování parametrĤ sítČ, merene_RTT.txt – zde jsou uloženy hodnoty reálné vzdálenosti mezi jednotlivými uzly, které jsou reprezentovány hodnotou zpoždČní RTT, hc.txt – kam jsou ukládány generované souĜadnice uzlĤ.

17

SbČr hodnot RTT je provádČn v cyklu pro tolik uzlĤ, kolik je nastaveno v konfiguraþním souboru config. SouþasnČ je v jednom kroku cyklu provedeno uložení hodnoty RTT do souboru merene_RTT.txt a název, pĜípadnČ IP adresa uzlu, který odpovídá hodnotČ RTT do souboru merene_servery.txt. Cyklus pro mČĜení hodnot RTT: while [ "$x" -lt "$dimenze" ]; do ip=$(head -n $rs config | tail -n 1); echo $ip >> merene_servery.txt; echo probiha mereni zpozdeni k $ip; ping -c10 $ip | tail -n1 | awk -F"/" merene_RTT.txt; rs=$(expr $rs + 1); x=$(expr $x + 1); sleep 0 done

'{print

$5}'

>>

Cyklus pro generaci souĜadnic majákĤ / stanic: while [ "$radek" -le "$pocet_mereni" ]; do majak1=0; rtt=$(head -n $radek merene_RTT.txt | tail -n 1); echo rtt je$rtt; majak1=$(echo "scale=3; $rtt*$rtt" | bc -l); echo majak1 je $majak1; y=1; while [ "$y" -lt "$dimenze" ]; do pomprom=$(echo "scale=6; $majak1*0.694" | bc -l); echo pomocna $pomprom; pomprom_odm=$(echo "scale=6; sqrt($pomprom)" | bc -l); majak1=$(echo "scale=3; $majak1-$pomprom" | bc -l); echo $pomprom_odm >> hc.txt; echo majak1 po odectu $majak1; y=$(expr $y + 1); done majaklasthc=$(echo "scale=6; sqrt($majak1)" | bc -l); echo $majaklasthc >> hc.txt echo radek=$(expr $radek + 1); done

Dalším souborem programu je soubor calculate.sh. Je také napsán ve skriptovacím jazace BASH a je zejména urþen pro vČtšinu poþetních operací metody. Cílem této práce je mimo jiné otestovat metodu Lighthouses, resp. její pĜesnost v závislosti na velikosti zvolené dimenze. V dĤsledku rozdílnosti nČkterých výpoþtĤ a v dĤsledku faktu, že tento skriptovací jazyk neumí pracovat s vícerozmČrnými poli, je v tomto souboru použit pro rozhodnutí chodu programu v závislosti na zvolené dimenzi pĜíkaz case. Po rozhodnutí toho o

18

kterou dimenzi se jedná, je provedeno naþtení souĜadnic majákĤ a následnČ vypoþteny souĜadnice jednotlivých vektorĤ l lokální báze L. Na takto vzniklou lokální bázi je aplikován Gram-SchmidtĤv algoritmus k získání ortogonální báze a jsou vypoþteny jednotlivé parametry pro sestavení sestaveny soustavy lineárních rovnic. Tyto parametry jsou pĜedány pomocí souboru gaus.txt jako vstupní data souboru matice*d (* pĜedstavuje þíslo dimenze, napĜ. pro 2D je název souboru matice2d). Výstupem souboru matice*d je matice soustavy lineárních rovnic po GaussovČ eliminaci, kde zpČtnou substitucí jsou získány koeficienty cx, které jsou následnČ použity pĜi výpoþtu souĜadnic stanice. PĜíklad cyklu pro naþtení vektoru l2, jeho následný výpis na obrazovku a výpoþet vektoru lb2: #nacteni vektoru l2 x=1; while [ "$x" -le "$dimenze" ]; do r=0; r=$(head -n $radek hc.txt | tail -n 1); l2[$x]=$r; radek=$(expr $radek + 1); x=$(expr $x + 1); sleep 0; done; echo "l2:" ${l2[*]}; #výpoþet vektoru lb2 x=1; while [ "$x" -le "$dimenze" ]; do lb2[$x]=$(echo "scale=6; ${MAJAK2[$x]}-${MAJAK0[$x]}" | bc -l); x=$(expr $x + 1); sleep 0; done; echo "lb2:" ${lb2[*]};

PĜíklad aplikace algoritmu Gram-Schmidt na vektor l2: #gram-schmidt na nactene vektory #l1gs=l1 #l2gs x=1; a=0; while [ "$x" -le "$dimenze" ]; do citatel=$(echo "scale=6; ${lb2[$x]}*${lb1[$x]}" | bc -l); soucet[$x]=$citatel c=${soucet[$x]} b=$(echo "scale=6; $a+$c" | bc -l); a=$b;

19

x=$(expr $x + 1); done x=1; d=0; while [ "$x" -le "$dimenze" ]; do jmen=$(echo "scale=6; ${lb1[$x]}*${lb1[$x]}" | bc -l); soucet[$x]=$jmen; c=${soucet[$x]}; b=$(echo "scale=6; $d+$c" | bc -l); d=$b; x=$(expr $x + 1); done jmenovatel=$(echo "scale=6; sqrt($d)" | bc -l); zlomek=$(echo "scale=6; $a/$jmenovatel" | bc -l); x=1; d=0; while [ "$x" -le "$dimenze" ]; do zlomek_lb1=$(echo "scale=6; $zlomek*${lb1[$x]}" | bc -l); soucet[$x]=$zlomek_lb1; c=${soucet[$x]}; b=$(echo "scale=6; $d+$c" | bc -l); d=$b; x=$(expr $x + 1); done echo zlomeklb1------------------------------ ${soucet[*]}; x=1; d=0; while [ "$x" -le "$dimenze" ]; do c=${lb2[$x]}; f=${soucet[$x]}; jmen=$(echo "scale=6; $c-$f" | bc -l); echo jmen $jmen; l2gs[$x]=$jmen; x=$(expr $x + 1); done echo l2gs------------------------------ ${l2gs[*]};

Posledním souborem, když neuvažujeme soubor config, je soubor matice.c. Ten je napsán v programovacím jazyku C a proto je po jakékoli jeho zmČnČ nutná následná kompilace, aby mohl být použit. Jak je již uvedeno výše, je tento soubor urþen pouze pro Gaussovu eliminaci matice, která vznikne sestavením soustavy lineárních rovnic. Soubor obsahuje mimo hlavní funkci main() ještČ 5 dalších funkcí, které jsou volány funkcí main(). Je to funkce pro naþtení matice þísel soustavy lineárních rovnic nacteni_matice(), naþtená matice je poté zpracována funkcemi gauss(), gaussline(), vymenarad(), které Ĝeší vlastní algoritmus Gaussovy eliminace, a funkce

20

tiskmatice(), která slouží pro tisk upravené matice na obrazovku a jednotlivých hodnot do souboru. Naþtení hodnot ze souboru je provedeno funkcí fscanf() a zápis hodnot do souboru je provádČn za pomocí funkce fputs(), kde je každá jednotlivá hodnota uložena do souboru gaused.txt, vždy na nový Ĝádek. Pro názornost je funkce tiskmatice() vypsána v následujícím zdrojovém kódu. void tiskmatice(double *matice, int x, int y) { int i, j; FILE *print_c; double znak; char string_number[20]; if ((print_c = fopen(OUTPUT,"w"))==NULL) { printf("Chyba pri otevreni souboru \n"); return; } for (i = 0; i < x; ++i) { for (j = 0; j < y; ++j){ printf("%7.2f ", matice[i * y + j]); znak = matice[i * y + j]; sprintf(string_number, "%f\n", znak); fputs(string_number, print_c); } printf("\n"); } printf("\n"); if(fclose(print_c)==EOF){printf("\nChyba pri uzavreni souboru"); return;} }

Pro konfiguraci je použit soubor config. Slouží pro nastavení parametrĤ jako je velikost dimenze, poþet provedených mČĜení a seznam serverĤ, které chceme pĜidat do virtuálního souĜadnicového systému. Nutno dodat, že v seznamu serverĤ jsou jednotlivé servery pĜidávány postupnČ, to znamená, že pokud máme dimenzi o velikosti 2, první dva servery budou použity jako referenþní poziþní servery a následující, tĜetí, je chápán jako první pĜistupující stanice, která splĖuje podmínku m > p+1, protože poþáteþní poziþní server je vlastnČ ten, na kterém je tento program spuštČn a ze kterého probíhají mČĜení.

21

6.2 PĜíklad chodu programu V této podkapitole je, jak již název napovídá, uveden postup algoritmu programu pro prostor 2D. Na server, který bude sloužit jako referenþní poziþní server je nutno nakopírovat obsah adresáĜe /src, který se nachází na pĜiloženém CD. PĜed spuštČním programu nastavíme v souboru config velikost dimenze 2 a poþet mČĜení 3. Tímto nastavením je nastaven 2D prostor a provedou se 3 mČĜení zpoždČní RTT. DvČ tyto mČĜení jsou mezi referenþním poziþním serverem Sj a dvČma prvními servery ze seznamu serverĤ, obsaženém v souboru config. TĜetí mČĜení je mezi provedeno mezi pĜistupující stanicí Si a referenþním poziþním serverem Sj. SpuštČní programu je uskuteþnČno po zadání do pĜíkazové Ĝádky ./main.sh. Po spuštČní programu probČhnou výše uvedená tĜi mČĜení a následná generace souĜadnic obou poziþních serverĤ a zároveĖ pĜistupující stanice.

Pro

názorný

pĜíklad

je

program

nakopírován

na

server

planetlab2.cesnet.cz, který bude tedy jako referenþní poziþní server. Do souboru config jsou pĜidány následující 3 servery: planetlab1.cesnet.cz, planet0.jaist.ac.jp, planetlab2.iis.sinica.edu.tw. ZmČĜené zpoždČní RTT mezi jednotlivými serery je: 0,177ms; 289,479ms; 323,801ms. K jednotlivým serverĤ jsou vygenerovány následující souĜadnice: Sj

planetlab2.cesnet.cz

{0,0; 0,0}

Sp1

planetlab1.cesnet.cz

{0,146676; 0,097396}

Sp2

planet0.jaist.ac.jp

{241,155292; 160,131870}

Si

planetlab2.iis.sinica.edu.tw

{268,747805; 179,117862}

V tomto okamžiku soubor main.sh spouští skript pro zahájení výpoþtĤ pomocí ./calculate.sh. Jsou vypoþteny souĜadnice lokální báze a z tČch je pomocí Gram-Schmidtova algoritmu (7) vypoþtena ortogonální báze. Poté je sestavena soustava lineárních rovnic dle rovnice (9). SouĜadnice lokální báze: l1 = {0,146676; 0,097396},

l2 = {241,155292; 160,131870}.

22

Aplikace Gram-Schmidtova algoritmu:

l1 = l1 , l2 = l2 −

(11)

(l1 ⋅ l2 ) 2 1

l +l

2 2

2

(12)

⋅ l1

Lokální báze po aplikaci Gram-Schmidtova algoritmu:

l1 = {0,146676; 0,097396},

l2 = {198,694301; 131,936864}.

Nyní je podle rovnice (9) sestavena soustava lineárních rovnic:

c1 0,176062 + c2 238,509455 cos 41,993807 = 323,801cos 57,010892 c1 0,176062 cos 41,993807 + c2 238,509455 = 323,801cos 77229,600358

(13)

Po vytvoĜení soustavy lineárních rovnic je spuštČn program matice2d, která provede Gaussovu eliminaci dané soustavy a takto upravenou matici vrátí zpČt skriptu calculate.sh, který dopoþítá konstanty cx a podle rovnice (7) dopoþítá predikované souĜadnice stanice. Vezme-li se v úvahu, že souĜadnice stanice jsou vlastnČ vektor, je již snadné provést dopoþítání hledaného RTT zjištČním velikosti vektoru. Vypoþtené hodnoty konstant cx: c1 = 918,430609,

c2 = 0,679535.

Výpoþet souĜadnic stanice s využitím rovnice (7): S i = 918,430609(0,146676; 0,097396 ) + 0,679535(198,694301; 131,936864 ) (14) S i = (269,731459;179,107183)

(15)

S i = 323,781474

(16)

Tím byl ukonþen výpoþet souĜadnic a predikovaného zpoždČní pro jednu stanici.

23

7

ZHODNOCENÍ PěESNOSTI METODY S pĜihlédnutím na možnost porovnání pĜesnosti predikce jednotlivých

systémĤ pro predikci zpoždČní, jeví se jako nejvýhodnČjší zhodnotit dosahovanou pĜesnost metody Lighthouses pomocí grafu. V grafu bude tedy provedeno zobrazení absolutní relativní chyby pomocí kumulativní distribuþní funkce. Absolutní relativní chyba je vypoþtena pomocí vzorce (17):

η=

S im − S ip S im

,

(17)

kde Sim je hodnota mČĜeného zpoždČní a Sip je hodnota pĜedikovaného zpoždČní. Kumulativní distribuþní funkce je mimo jiné použita pro urþení rozložení vícerozmČrných

náhodných

veliþin.

ěešení

výpoþtu

této

funkce

není

pĜedmČtem této práce a proto bude pro její výpoþet použita integrovaná funkce tabulkového kalkulátoru Excel, a sice funkce NORMDIST(). Vstupními hodnotami této funkce jsou: hodnota pro kterou chceme zjistit hodnotu rozložení, aritmetická stĜední hodnota rozložení, smČrodatná odchylka rozložení a logická hodnota, kterou urþíme zda chceme souþtovou distribuþní, funkce nebo hromadnou pravdČpodobnostní funkci. Pro potĜeby této práce bude tedy použita logická hodnota udávající distribuþní funkci. Z teoretických pĜedpokladĤ lze usuzovat, že pĜi vzrĤstající dimenzi se pĜesnost pĜedikovaného zpoždČní zvyšuje. Praktické zjištČní, získané pomocí aplikace navrženého algoritmu v experimentální síti PlanetLab je zobrazeno na Obr. 4. V grafu osa y zobrazuje hodnoty kumulativní distribuþní funkce (CDF) a osa x zobrazuje jednotlivé iterace metody Lighthouses, kde v jedné iteraci je provedeno jeden odhad hodnoty zpoždČní.

24

1 0,9 0,8 0,7 CDF

0,6 0,5 0,4 0,3

Lighthouses 4D

0,2 0,1 0 1

3

5

7

9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 iterace

Obr. 4 : Kumulativní distribuþní funkce metody Lighthouses 4D

Hodnocení objemu pĜenesených dat vychází ze skuteþnosti, že každá pĜistupující stanice Si si zmČĜí hodnotu RTT mezi sebou a referenþním poziþním serverem Sj. To znamená, že poþet mČĜení se rovná poþtu stanic pĜistupujících do systému + poþet mČĜení mezi poziþními servery (dáno velikostí dimenze). PĜi každém mČĜení je pak pĜeneseno r paketĤ, kde jeden paket má velikost 64 bytĤ. Aby byla hodnota zmČĜeného zpoždČní co nepĜesnČjší, opakuje se 10x (nastaveno v programu) a z tČchto mČĜení se poté bere aritmetický prĤmČr. Pro 107 pĜistupujících stanic je pĜeneseno 69 760 bytĤ. Toto mČĜení je však pro daný server provádČno v rámci stejné dimenze pouze jednou, ve stejné dimenzi již není potĜeba toto mČĜení opakovat a tedy pĜi následné predikci se pro dané servery nepĜenášejí žádná data. Rychlost predikce je nejvíce urþována parametrem velikosti dimenze, kde platí pravidlo, že þím vČtší je velikost dimenze, tím více þasu zaberou výpoþty a zároveĖ jsou i pĜesnČjší. Urþitý kompromis mezi rychlostí výpoþtu a pĜesností by podle provedených mČĜení mČla být metoda Lighthouses ve þtvrté dimenzi.

25

8

ZÁVċR V této práci byly v její první þásti rozebrány metody resp. systémy pro

predikci zpoždČní, kde byly rozepsány tĜi vybrané metody a þtvrtá metoda, která je pro tuto práci stČžejní, byla probrána nejpodrobnČji. Další þást práce byla zamČĜena na pĜiblížení prostĜedí, ve kterém byla stČžejní metoda realizována. PĜedposlední þást práce popisuje navržený program aplikovaný do již zmiĖovaného prostĜedí a poslední þást se zamČĜuje na zhodnocení pĜesnosti predikce tohoto navrženého programu. Algoritmus realizované metody je ze þtyĜ metod, uvedených v první þásti práce, nejvíce podobný metodČ GNP, kde jeho nejvČtší výhodou oproti metodČ GNP je naprostá volnost pĜi výbČru majákĤ (poziþních serverĤ) a s tím spojená jeho pružnost na aktuální podmínky sítČ, ve které je implementován.

26

LITERATURA [1] PIAS, M. et al. Lighthouses for scalable distributed location [online]. Lecture Notes in Computer Science. Springer Berlin/Heidelberg, 2003. URL: [2] EUGENE, T. S., ZHANG, H. Predicting Internet Network Distance with CoordinatesBased Approaches. Proceedings of 21st Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2002. [3] PlanetLab Consortium. PlanetLab: An open platform for developing, deploying, and accessing planetary-scale services. URL: [4] KOPEýEK, T. Nalezení fyzické pozice stanice v síti Internet. Brno: Vysoké uþení technické v BrnČ, Fakulta elektrotechniky a komunikaþních technologií, 2010. [5] SPENCE, DAVID R. An Implementation of coordinate based systém. Cambridge: University of Cambridge. Computer laboratory, 2003. URL: [6] ŠIMÁK J. MČĜení vzdáleností mezi stanicemi v IP sítích. Brno: Vysoké uþení technické v BrnČ. Fakulta elektrotechniky a komunikaþních technologií. Ústav telekomunikací, 2010 [7] ŠVÉDA, J. Nalezení pozice stanic v Internetu pomocí umČle vytvoĜených souĜadnicových systémĤ. Brno: Vysoké uþení technické v BrnČ. Fakulta elektrotechniky a komunikaþních technologií. Ústav telekomunikací, 2009. [8] The Community ENTerprise Operating System. URL:

27

SEZNAM SYMBOLģ, VELIýIN A ZKRATEK cx

konstanty soustavy lineárních rovnic

İ

chybová funkce

Fij

síla pĤsobící na stanici

lx

vektor vytvoĜený rozdílem souĜadnic dvou stanic

p

dimenze

Si

pĜistupující stanice

Sj

referenþní poziþní server

Sp

poziþní server

DNS

Domain Name Server

GNP

Global Networ Positioning

ICMP

Internet control message protocol

IP

Internet protocol

RTT

Round trip dely time

TCP/IP

Transmission kontrol protocol / Internet protocol

28

SEZNAM PěÍLOH Obsah pĜiloženého cd

30

29

OBSAH PěILOŽENÉHO CD AdresáĜ

Obsah adresáĜe

Popis

src

main.sh

hlavní soubor programu

src

calculate.sh

soubor realizující výpoþty

src

config

konfiguraþní soubor

src

matice.c

zdrojový soubor v C

src

matice2d – matice5d

zkompilovaný soubor matice.c

pdf

BP_2011_smrcka.pdf

elektronický text SP

30