ICMP PROTOKOLU V IP SÍTÍCH

´ UC ˇ ENÍ TECHNICKE ´ V BRNE ˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY

ˇ ÍCH TECHNOLOGIÍ FAKULTA ELEKTROTECHNIKY A KOMUNIKACN ´ USTAV TELEKOMUNIKACÍ FACULTY OF ELECTRICAL ENGINEERING AND COMMUNICATION DEPARTMENT OF TELECOMMUNICATIONS

ˇR ˇ ENÍ VZDA ´ LENOSTÍ STANIC PROSTR ˇ EDNICTVÍM ME ICMP PROTOKOLU V IP SÍTÍCH

´ RSK ˇ A ´ PRACE ´ BAKALA BACHELOR’S THESIS

´ AUTOR PRACE AUTHOR

BRNO 2008

ˇ A ´ LUCIE JAROSOV

´ UC ˇ ENÍ TECHNICKE ´ V BRNE ˇ VYSOKE BRNO UNIVERSITY OF TECHNOLOGY

FAKULTA ELEKTROTECHNIKY ˇ ÍCH TECHNOLOGIÍ A KOMUNIKACN ´ USTAV TELEKOMUNIKACÍ FACULTY OF ELECTRICAL ENGINEERING AND COMMUNICATION DEPARTMENT OF TELECOMMUNICATIONS

ˇR ˇ ENÍ VZDA ´ LENOSTÍ STANIC PROSTR ˇ EDNICTVÍM ME ICMP PROTOKOLU V IP SÍTÍCH HOST DISTANCE MEASUREMENT USING ICMP PROTOCOL IN IP NETWORKS

´ RSK ˇ A ´ PRACE ´ BAKALA BACHELOR’S THESIS

´ AUTOR PRACE

ˇ A ´ LUCIE JAROSOV

AUTHOR

´ VEDOUCÍ PRACE SUPERVISOR

BRNO 2008

ING. RADIM BURGET

´ Í ZADAN

Seznamte se s nástroji pro mˇeˇren´ı vzdálenost´ı v s´ıti. Seznamte se s protokolem ICMP. Proved’te návrh aplikace popiˇste a v jazyce C ˇci C++ implementujte. Vytvoˇrte automatické skripty pro mˇeˇren´ı RTT vzdálenost´ı. Proved’te mˇeˇren´ı vzdálenost´ı mezi mnoˇzinou server˚ u a vytvoˇrte trénovac´ı data. Posud’te závislost parametru RTT na vzdálenosti na mapˇe.

ABSTRAKT Souˇcasný Internet se ˇc´ım dál ˇcastˇeji potýká s problémem správného urˇcen´ı vzdálenost´ı mezi jednotlivými stanicemi. Nejˇs´ırˇs´ı dopad má znalost této veliˇciny v oblastech optimáln´ıho rozloˇzen´ı s´ıtˇe aplikaˇcn´ıho multicastu, správného výbˇeru u´ˇcastn´ıka peer-to-peer s´ıtˇe, nebo pˇri prostém rozhodován´ı koncového uˇzivatele, které z nejbliˇzˇs´ıch zrcadel pouˇz´ıt pro staˇzen´ı nˇejakých dat. Nejbliˇzˇs´ı v tomto smyslu vˇsak nemus´ı nutnˇe znamenat geograficky nejbliˇzˇs´ı - vzdálenosti na Internetu jsou typicky vyjadˇrovány ve veliˇcinách jako je latence nebo ˇs´ıˇrka pásma. Vˇsechny tyto pˇr´ıklady maj´ı spoleˇcnou snahu o u´sporu ˇs´ıˇrky pásma a t´ım pádem ekonomickou u´sporu. Metody odhadu pozice v s´ıti pracuj´ı na základˇe mˇeˇren´ı parametru latence. V této práci budou vytvoˇreny nástroje pro mˇeˇren´ı tohoto parametru a zároveˇn s pomoc´ı tˇechto nástroj˚ u ukázáno, jak moc spolu koresponduj´ı veliˇciny geografická vzdálenost a latence.

ˇ A ´ SLOVA KLÍCOV ICMP protokol, ping, latence, RTT, IDMaps, GNP

ABSTRACT Current internet more and more often faces the problem of the right definition of distance between the single hosts. The knowledge of this quantity influences the areas of the optimal lay-out of overlay multicast networks, the right selection of peer-to-peer network participant, or the simple decision of the end user: which one of the nearest mirrors to use for downloading datas. The nearest one doesn’t have to mean the nearest in geographical point of view - the distance on Internet is usually expressed by quantities as latency or bandwidth. All these examples have got the saving of bandwidth in common and therefore economical saving. The methods of host position prediction in networks work on the basis of measuring latency parameter. The tools for measuring of this parameter will be set up in this thesis and at the same time it will be shown how geographical distance and latency correspond with each other.

KEYWORDS ICMP protocol, ping, latency, RTT, IDMaps, GNP

ˇ A ´ L. Mˇeˇren´ı vzdálenost´ı stanic prostˇrednictv´ım ICMP protokolu v IP s´ıt´ıch. JAROSOV ´ UCEN ˇ Í TECHNICKE ´ V BRNE, ˇ FAKULTA ELEKTROTECHNIKY A Brno: VYSOKE ˇ ÍCH TECHNOLOGIÍ, USTAV ´ KOMUNIKACN TELEKOMUNIKACÍ, Rok vydán´ı: 2008. Poˇcet stran 63. Vedouc´ı bakaláˇrské práce Ing. Radim Burget

ˇ ´ Í PODEKOV AN ´ Dˇekuji vedouc´ımu bakaláˇrské práce Ing. Radimu Burgetovi z Ustavu telekomunikac´ı FEKT VUT v Brnˇe za velmi uˇziteˇcnou metodickou pomoc a cenné rady pˇri zpracován´ı bakaláˇrské práce. Dále dˇekuji svému pˇr´ıteli Pavlovi Fojtovi za neziˇstné komentáˇre a podporu v pr˚ ubˇehu tvorby této práce. V Brnˇe dne . . . . . . . . . . . . . . .

........................... podpis autora

´ SEN ˇ Í PROHLA Prohlaˇsuji, ˇze svou bakaláˇrskou práci na téma Mˇeˇren´ı vzdálenost´ı stanic prostˇrednictv´ım ICMP protokolu v IP s´ıt´ıch jsem vypracoval samostatnˇe pod veden´ım vedouc´ıho bakaláˇrské práce a s pouˇzit´ım odborné literatury a dalˇs´ıch informaˇcn´ıch zdroj˚ u, které jsou vˇsechny citovány v práci a uvedeny v seznamu literatury na konci práce. Jako autor uvedené bakaláˇrské práce dále prohlaˇsuji, ˇze v souvislosti s vytvoˇren´ım této bakaláˇrské práce jsem neporuˇsil autorská práva tˇret´ıch osob, zejména jsem nezasáhl nedovoleným zp˚ usobem do ciz´ıch autorských práv osobnostn´ıch a jsem si plnˇe vˇedom následk˚ u poruˇsen´ı ustanoven´ı § 11 a následuj´ıc´ıch autorského zákona ˇc. 121/2000 Sb., vˇcetnˇe moˇzných trestnˇeprávn´ıch d˚ usledk˚ u vyplývaj´ıc´ıch z ustanoven´ı § 152 trestn´ıho zákona ˇc. 140/1961 Sb.

V Brnˇe dne

...............

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

OBSAH ´ Uvod

11

1 Teoretick´ y z´ aklad pro mˇ eˇ ren´ı vzd´ alenost´ı v s´ıt´ıch 1.1 Zpoˇzdˇen´ı (latency) . . . . . . . . . . . . . . . . . . 1.2 ICMP . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Mˇeˇren´ı RTT . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Aplikace ping . . . . . . . . . . . . . . . . . 1.3.2 Faktory ovlivˇ nuj´ıc´ı mˇeˇren´ı RTT . . . . . . . 1.4 Odhad geografické polohy ze znalosti IP adresy . .

. . . . . .

13 13 14 16 16 17 18

. . . . . . . . . . . .

20 20 20 20 22 22 22 23 24 25 26 26 28

. . . . . . . . . . .

30 30 30 30 31 31 33 33 34 35 35 36

2 Predikce pozice stanice v s´ıti 2.1 Projekty Remos a SPAND . . . . . 2.1.1 Remos . . . . . . . . . . . . 2.1.2 SPAND . . . . . . . . . . . 2.2 IDMaps . . . . . . . . . . . . . . . 2.2.1 Sonar a HOPS . . . . . . . 2.2.2 Metrika . . . . . . . . . . . 2.2.3 Zp˚ usoby mˇeˇren´ı . . . . . . . 2.2.4 Tracery . . . . . . . . . . . 2.2.5 Rozloˇzen´ı tracer˚ u . . . . . . 2.2.6 Virtuáln´ı spojen´ı . . . . . . 2.2.7 V´ ykonnost systému . . . . . 2.3 Global Network Positioning (GNP)

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

3 N´ astroje pro mˇ eˇ ren´ı latence 3.1 Vytvoˇren´ı zdrojov´ ych kód˚ u aplikace ping . . . . . . . . . 3.1.1 Implementace . . . . . . . . . . . . . . . . . . . . 3.1.2 Ovˇeˇren´ı funkˇcnosti . . . . . . . . . . . . . . . . . 3.2 Vytvoˇren´ı skript˚ u pro mˇeˇren´ı RTT a zpracován´ı v´ ysledk˚ u 3.2.1 S´ıt’ PlanetLab . . . . . . . . . . . . . . . . . . . . 3.2.2 Vytvoˇren´ı seznamu stanic . . . . . . . . . . . . . 3.2.3 Skript pro mˇeˇren´ı RTT . . . . . . . . . . . . . . . 3.2.4 Poˇc´ıtán´ı geografické vzdálenosti . . . . . . . . . . 3.2.5 Odstranˇen´ı duplicit . . . . . . . . . . . . . . . . . 3.2.6 Traceroute . . . . . . . . . . . . . . . . . . . . . . 3.3 Databáze namˇeˇren´ ych hodnot . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . . . . . . .

. . . . . .

. . . . . . . . . . . .

. . . . . . . . . . .

4 Zpracov´ an´ı namˇ eˇ ren´ ych hodnot 4.1 Zmˇena závislosti RTT vzhledem k 4.2 Délka mˇeˇren´ı . . . . . . . . . . . 4.3 Anal´ yza referenˇcn´ıho grafu . . . . 4.4 Anal´ yza evropsk´ ych uzl˚ u . . . . . 4.5 Anal´ yza americk´ ych uzl˚ u . . . . . 4.6 Zhodnocen´ı namˇeˇren´ ych v´ ysledk˚ u

denn´ı dobˇe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

37 37 40 43 45 45 45

5 Z´ avˇ er

48

Reference

49

Seznam symbol˚ u, veliˇ cin a zkratek

51

Seznam pˇ r´ıloh

52

A Zdrojov´ y k´ od aplikace PING

53

B Skript ping nodes random

57

C Funkce vzdalenost.bc pro poˇ c´ıt´ an´ı geografick´ e vzd´ alenosti

59

D Skript Count

60

E Skript remove dup

62

F Skript prepare nodes

63

´ ˚ SEZNAM OBRAZK U 1.1 2.1 2.2 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9

ICMP paket - struktura . . . . . . . . . . . . . . . . . . . . . . . . Sd´ılen´ı RTT u ´daj˚ u d´ıky malé vzdálenosti . . . . . . . . . . . . . . . Optimáln´ı rozloˇzen´ı tracer˚ u . . . . . . . . . . . . . . . . . . . . . . Závislot RTT na geografické vzdálenosti - vˇsechny vzorky, 14.5.2008 Závislot RTT na geografické vzdálenosti - detail, 14.5.2008 . . . . . Závislot RTT na geografické vzdálenosti - 20.4.2008 . . . . . . . . . Závislot RTT na geografické vzdálenosti - 22.4.2008 . . . . . . . . . Porovnán´ı závislosti RTT v r˚ uznou dobu - 20.4.2008, 14.5.2008 . . . Závislost RTT na geografické vzdálenosti - barevnˇe oddˇelˇené skupiny, 14.5.2008 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Oblast nejvˇetˇs´ı koncentrace RTT, 14.5.2008 . . . . . . . . . . . . . Závislost RTT na geografické vzdálenosti - Evropa, 14.5.2008 . . . . Závislost RTT na geografické vzdálenosti - Amerika, 14.5.2008 . . .

. . . . . . . .

14 21 27 37 38 38 39 40

. . . .

44 45 46 46

SEZNAM TABULEK 1.1 3.1 4.1 4.2 4.3

Nejˇcastˇejˇs´ı typy ICMP paketu . . . . . . . . . . . . . . . . . . . . Porovnán´ı linuxové a novˇe vytvoˇrené aplikace v milisekundách . . Regresn´ı a korelaˇcn´ı koeficienty . . . . . . . . . . . . . . . . . . . Závislost RTT na poˇctu odeslan´ ych paket˚ u pro r˚ uzné vzdálenosti Závislost RTT na poˇctu odeslan´ ych paket˚ u pro r˚ uzné vzdálenosti -

. . . . . . I . II

15 31 39 41 42

´ UVOD V posledn´ı dobˇe vzr˚ ustá potˇreba rychle a efektivnˇe urˇcovat vzdálenosti mezi jednotliv´ ymi stanicemi v Internetu. D˚ uvodem je obecná snaha poskytovatel˚ u datov´ ych pˇrenos˚ u o co nejvˇetˇs´ı u ´sporu ˇs´ıˇrky pásma a t´ım i u ´sporu náklad˚ u. Typick´ ym pˇr´ıkladem zmenˇsen´ı potˇrebné ˇs´ıˇrky pásma m˚ uˇze b´ yt tzv. multicast. Multicast je metoda rozes´ılán´ı paket˚ u z jednoho zdrojového stroje ke skupinˇe nˇekolika koncov´ ych stanic, pˇriˇcemˇz data vys´ılaná zdrojem se replikuj´ı podle potˇreby v jednotliv´ ych smˇerovaˇc´ıch a pˇrepos´ılaj´ı se dále na ta s´ıt’ová rozhran´ı, za nimiˇz se nacházej´ı registrovan´ı pˇr´ıjemci. Typické vyuˇzit´ı multicastu m˚ uˇze b´ yt napˇr´ıklad pˇri streamován´ı IPTV, kdy zdroj nemus´ı pos´ılat pro 1000 pˇr´ıjemc˚ u 1000 datov´ ych tok˚ u, coˇz obzvláˇst’ u videopˇrenosu m˚ uˇze znamenat v´ yraznou u ´sporu ˇs´ıˇrky pásma jednotliv´ ych linek. Bohuˇzel multicastové protokoly stále nejsou v dneˇsn´ı dobˇe ze strany komerˇcn´ıch poskytovatel˚ u pˇriliˇs podporovány, jeho vyuˇzit´ı z˚ ustává sp´ıˇse na akademické p˚ udˇe (v´ yjimkou z˚ ustáváj´ı poskytovatelé IPTV, avˇsak ani ti nepodporuj´ı mutlicastové vys´ılán´ı vzájemnˇe mezi sv´ ymi s´ıtˇemi; tuto situaci se pokouˇs´ı ˇreˇsit napˇr. Národn´ı centrum videa, které umoˇzn ˇuje jednotliv´ ym poskytovatel˚ um právˇe vzájemné propojen´ı a je potom pouze na nich, zda se rozhodnou tyto multicastové pˇrenosy distribuovat dále ve své s´ıti). Jedn´ım z d˚ uvod˚ u malého rozˇs´ıˇren´ı je fakt, ˇze pro klasické smˇerovaˇce je mnohem jednoduˇsˇs´ı pouze smˇerován´ı paket˚ u nam´ısto dalˇs´ıch rozhodovac´ıch mechanism˚ u a ˇ sen´ım se nab´ız´ı b´ replikace paket˚ u. Reˇ yt tzv. aplikaˇcn´ı (overlay) multicast. Princip spoˇc´ıvá v tom, ˇze pˇr´ıjemce dat se zároveˇ n m˚ uˇze stát jejich vys´ılaˇcem (pˇrepos´ılaˇcem) dalˇs´ım uzl˚ um, ˇc´ımˇz se v podstatˇe simuluje multicast. A právˇe zde se stává d˚ uleˇzitou znalost vzdálenost´ı mezi stanicemi v s´ıti: Pomoc´ı n´ı se totiˇz m˚ uˇze mnohem lépe optimalizovat struktura této pˇrekryvné s´ıtˇe a t´ım pádem zv´ yˇsit jej´ı v´ ykon. Znalost vzdálenost´ı uzl˚ u je také d˚ uleˇzitá pro peer-to-peer s´ıtˇe, ve kter´ ych spolu jednotliv´ı u ´ˇcastn´ıci komunikuj´ı napˇr´ımo a navzájem si poskytuj´ı r˚ uzné sluˇzby. Je tedy nasnadˇe, ˇze dobr´ y odhad vzdálenosti m˚ uˇze v´ yraznˇe usnadnit v´ ybˇer tˇechto jednotliv´ ych poskytovatel˚ u. Aˇckoliv jiˇz bylo provedeno nˇekolik r˚ uzn´ ych v´ yzkum˚ u t´ ykaj´ıc´ıch se této problematiky, zat´ım neexistuje ˇzádn´ y standardizovan´ y protokol pro mˇeˇren´ı vzdálenost´ı mezi jednotliv´ ymi koncov´ ymi body. Existuje nˇekolik r˚ uzn´ ych metod, pomoc´ı kter´ ych se dá odhadnout pozice jednotliv´ ych stanic v s´ıti. Mezi nejznámˇejˇs´ı patˇr´ı Spand, Remos project, IDMaps a GNP (která dává momentálnˇe jedny z nejpˇresnˇejˇs´ıch v´ ysledk˚ u). Je velmi d˚ uleˇzité uvˇedomit si motivaci (d˚ uvod) mˇeˇren´ı vzdálenost´ı, protoˇze r˚ uzné architektury poskytuj´ı r˚ uzné typy informac´ı a ne vˇsechny mohou b´ yt pouˇzitelné pro konkrétn´ı pˇr´ıpady. Aby byly tyto architektury pouˇzitelné, je tˇreba, aby byly dostateˇcnˇe pˇresné, rychlé a snadno rozˇs´ıˇritelné. Drtivá vˇetˇsina tˇechto metod má spoleˇcnou jednu vˇec - zab´ yvaj´ı se odhadem vzájemn´ ych vzdálenost´ı na základˇe

11

mˇeˇren´ı a vyhodnocen´ı parametru latence. Je to ˇcas, kter´ y uplyne od odeslán´ı zprávy zdrojov´ ym uzlem po jej´ı pˇrijet´ı na uzlu c´ılovém. Tato práce si klade za c´ıl vytvoˇrit sadu nástroj˚ u pro mˇeˇren´ı latence. S jejich pomoc´ı se pak na základˇe namˇeˇren´ ych hodnot pokus´ı odpovˇedˇet na otázku, zda mezi veliˇcinami latence a geografické vzdálenosti existuje nˇejaká vzájemná souvslost, tedy zda lze pomoc´ı protokolu ICMP zmˇeˇrit nebo alespoˇ n odhadnout geografickou vzdálenost jednotliv´ ych uzl˚ u v s´ıti. V kapitole 1 jsou shrnuty teoretické poznatky, d˚ uleˇzité pro mˇeˇren´ı vzdálenost´ı v s´ıt´ıch - jsou zde definovány d˚ uleˇzité pojmy metriky. Druhá kapitola pˇredstavuje nejznámˇejˇs´ı dosud vytvoˇrené architektury pro odhad pozice stanice v s´ıti. Kapitola 3 se zab´ yvá vytvoˇren´ım a otestovan´ım aplikace, která je schopna mˇeˇrit latenci a zároveˇ n popisuje skripty, které byly naprogramovány pro mˇeˇren´ı latence ve vˇetˇs´ı m´ıˇre a zároveˇ n namˇeˇrená data zpracovávaj´ı. Pomoc´ı tˇechto skript˚ u jsou dále v kapitole 4 namˇeˇrená data vyhodnocena. V kapitole 5 jsou shrnuty v´ ysledky této práce.

12

1

´ ZAKLAD ´ TEORETICKY ´ Í V SÍTÍCH VZDALENOST

PRO

ˇ REN ˇ Í ME

Mezi kvalitativn´ı parametry s´ıtˇe pouˇzitelné pˇri odhadech vzdálenost´ı patˇr´ı napˇr´ıklad latence, jitter, ztrátovost paket˚ u nebo propustnost. Jejich mˇeˇren´ı je v souˇcasné dobˇe témˇeˇr nezbytné, pouˇz´ıvaj´ı se jako identifikátory stavu s´ıtˇe - m˚ uˇzeme pomoc´ı nich urˇcit, zda je nˇekde problém, ˇceho se t´ yká atd. Jitter pˇredstavuje variabilitu v doruˇcován´ı paket˚ u c´ılovému uzlu (tedy ve zpoˇzdˇen´ı pˇri pˇrenosu). Existuj´ı typy aplikac´ı, kter´ ym rozptyl nezp˚ usobuje ˇza´dné problémy, a naopak takové, které trvaj´ı na konstantn´ım jitteru. Ztrátovost paket˚ u je vyjadˇrována vˇetˇsinou procenty a pˇredstavuje pr˚ umˇernou ztrátu paket˚ u za urˇcité obdob´ı. Dalˇs´ı moˇznost´ı vyuˇzit´ı (konkrétnˇe parametru latence) je moˇznost odhadovat pomoc´ı nˇeho virtuáln´ı vzdálenost jednotliv´ ych stanic v s´ıti.

1.1

Zpoˇ zdˇ en´ı (latency)

Latence je ˇcas, kter´ y uplyne od odeslán´ı zprávy zdrojov´ ym uzlem po jej´ı pˇrijet´ı na uzlu c´ılovém; zahrnuje zpoˇzdˇen´ı v pˇrenosové trase a na zaˇr´ızen´ıch, které jsou jej´ı souˇcást´ı. Je nutné rozliˇsovat zpoˇzdˇen´ı jednosmˇerné (tj. ˇcas mezi odeslán´ım paketu zdrojem a jeho pˇrijet´ı c´ılem) a zpoˇzdˇen´ı obousmˇerné, tzv. round-trip latency, zahrnuj´ıc´ı dva faktory: dobu cesty paketu tam i zpˇet a ˇcas na jeho zpracován´ı (napˇr. zakódován´ı paketu pro jeho pˇrenos). Spodn´ı hranice zpoˇzdˇen´ı je daná vzdálenost´ı, kterou paket mus´ı urazit, a rychlost´ı, kterou se signál ˇs´ıˇr´ı pˇrenosov´ ym médiem (typicky je to hodnota 70-95% rychlosti svˇetla, závis´ı na pouˇzitém pˇrenosovém médiu). Skuteˇcná velikost latence je samozˇrejmˇe mnohem vˇetˇs´ı. Parametr latence je d˚ uleˇzité monitorovat z toho d˚ uvodu, ˇze jeho náhl´ y nár˚ ust obvykle ukazuje na problémy v s´ıti (nejˇcastˇeji na pˇrenosovém médiu). V s´ıt’ové praxi se nejˇcastˇeji vyuˇz´ıvá právˇe parametr round-trip latency nebo také Round Trip Time (RTT), protoˇze jej lze zmˇeˇrit z jedné stanice. Jednoduch´ ym testovac´ım mechanismem pro zkouˇsen´ı dostupnosti uzlu je aplikace ping, která pracuje na základˇe odes´ılán´ı a pˇrij´ımán´ı ICMP zpráv (v´ıce viz kapitola 1.3.1).

13

1.2

ICMP

Sluˇzebn´ı protokol ICMP, definovan´ y specifikac´ı RFC7921 , je vyˇzadovanou souˇcást´ı IP protokolu. Slouˇz´ı k signalizaci neobvykl´ ych situac´ı v s´ıt´ıch, které jsou postaveny na IP protokolu, napˇr. umoˇzn ˇuje zdrojov´ ym smˇerovaˇc˚ um a hostitel˚ um (obecnˇe uzl˚ um) vyuˇz´ıvaj´ıc´ım IP komunikaci ohlaˇsovat chyby a vymˇen ˇovat si omezené ˇr´ıd´ıc´ı a stavové informace. Aˇz na v´ yjimky nen´ı pouˇz´ıván s´ıt’ov´ ymi aplikacemi pˇr´ımo. Stejnˇe jako u protokolu UDP, informace o ztrátˇe nebo zruˇsen´ı ICMP zprávy nej-

Obrázek 1.1: ICMP paket - struktura sou pˇredávány. Z bezpeˇcnostn´ıch d˚ uvod˚ u jsou pomˇernˇe ˇcasto ICMP zprávy zahazovány. Nejˇcastˇeji jsou tyto signalizaˇcn´ı zprávy generovány pˇri chybách v IP datagramech (viz specifikace RFC1122), pˇr´ıpadnˇe pro diagnostické nebo routovac´ı u ´ˇcely. Konkrétn´ım pˇr´ıkladem m˚ uˇze b´ yt situace, kdy: – smˇerovaˇc v tabulce nemá záznam o c´ılové s´ıti – smˇerovaˇc mus´ı zruˇsit paket, pokud dojde k pˇrekroˇcen´ı TTL – poˇzadovaná sluˇzba nebo c´ıl nejsou dostupné, atd. K základn´ım funkc´ım protokolu ICMP tedy patˇr´ı testován´ı dostupnosti a stavu c´ılového uzlu s´ıtˇe, aktualizace smˇerov´ ych tabulek uzl˚ u, ˇr´ızen´ı zahlcen´ı s´ıtˇe a toku paket˚ u a odes´ılán´ı masky pods´ıtˇe. ICMP zprávy se pˇrenáˇs´ı v datové ˇcásti IP datagramu. Aby se ICMP zpráva dostala zpˇet k p˚ uvodn´ımu odes´ılateli, je nutné, aby ji 1

RFC, request for comments. Pouˇz´ıvá se pro oznaˇcen´ı ˇrady standard˚ u a dalˇs´ıch dokument˚ u popisuj´ıc´ıch Internetové protokoly, systémy atd. Vydané RFC se neruˇs´ı, v budoucnu m˚ uˇze upravit vyd´ an´ım novˇejˇs´ıho RFC.

14

Typ

K´ od

Popis

0 3

0

Echo Nedoruˇ citeln´ y IP datagram (destination unreachable)

8 11 13 14

0 1 2 3 5 6 7 0

Nedosaˇzitelná s´ıt’ (Network unreachable) Nedosaˇziteln´ y uzel (Host unreachable) Nedosaˇziteln´ y protokol (Protocol unreachable) Nedosaˇziteln´ y port protokolu UDP (Port unreachable) Selhalo explicitn´ı smˇerován´ı (Source route failed) Adresátova s´ıt’ je neznámá (Destination network unknown) Adresát˚ uv uzel je neznám´ y (Destination host unknown)

0 0

Poˇ zadavek na ˇ casovou synchornizaci (timestamp request)

ˇ adost o echo Z´ ˇ Cas vyprˇ sel (time exceeded) Odpovˇ ed’ na ˇ casovou synchronizaci (timestamp reply)

Tabulka 1.1: Nejˇcastˇejˇs´ı typy ICMP paketu IP vrstva zapouzdˇrila novou IP hlaviˇckou. Záhlav´ı ICMP paketu má vˇzdy velikost 8 byt˚ u. Prvn´ı ˇctyˇri bajty nesou informaci o kódu zprávy, jej´ım typu a dále kontroln´ı CRC souˇcet (16 bit˚ u). Hrubé rozdˇelen´ı paket˚ u se provád´ı typem, konkrétn´ı urˇcen´ı potom specifikuje kód. Nejˇcastˇeji pouˇz´ıvané typy ICMP paketu obsahuje tabulka ˇc.1.1. Zprávy se velmi ˇcasto pouˇz´ıvaj´ı v kombinaci. Spojen´ı zpráv ˇc.0 a 8 se vyuˇz´ıvá v aplikaci ping, která jednoduch´ ym zp˚ usobem testuje dostupnost uzlu (viz kapitola 1.3.1): – Echo request (typ 8) se pouˇz´ıvá ke zjiˇstˇen´ı, zda je dan´ y uzel v s´ıti stále pˇr´ıtomen – Echo reply (typ 0) je odpovˇed´ı na echo request Dalˇs´ı obdobnou aplikac´ı vyuˇz´ıvaj´ıc´ı tyto zprávy je traceroute. Aplikace odes´ılá UDP datagramy se speciálnˇe nastavenou ˇzivotnost´ı v pol´ıˇcku TTL IP hlaviˇcky a oˇcekává ICMP zprávu typu 11 nebo 3. Zprávy ˇc.13 a 14 tvoˇr´ı mechanismus ke zjiˇst’ován´ı charakteristiky zpoˇzdˇen´ı pˇri pr˚ uchodu paketu s´ıt´ı. Zdrojov´ y uzel vkládá do datagramu timestamp (ˇcasovou znaˇcku) a pos´ılá ho jako request. C´ılov´ y uzel vkládá do datagramu timestamp pˇri pˇrijet´ı i odeslán´ı a pos´ılá ho jako reply.

15

1.3

Mˇ eˇ ren´ı RTT

RTT neboli round-trip (delay) time je ˇcas, za kter´ y informace doraz´ı od zdroje k c´ıli a zpˇet. Pomˇernˇe ˇcasto je vyuˇz´ıván routovac´ımi algoritmy pro v´ ypoˇcet optimáln´ı cesty. Pro kaˇzdé mˇeˇren´ı RTT existuje teoretické minimum, které nelze pˇrekonat. Jeho d˚ uvodem je fyzická vzdálenost zdroje a c´ıle (tj. délka pˇrenosového média v cestˇe) a zároveˇ n rychlost ˇs´ıˇren´ı signálu v daném médiu. Bˇeˇznˇe se tento u ´daj pohyˇ ım vˇetˇs´ı je toto zpoˇzdˇen´ı, t´ım h˚ buje v ˇra´dech des´ıtek aˇz stovek milisekund. C´ uˇre se protokol˚ um transportn´ı vrstvy udrˇzuje velká ˇs´ıˇrka pásma (viz RFC2679). V nˇekter´ ych pˇr´ıpadech se také vyuˇz´ıvá pouze tzv. jednosmˇerné mˇeˇren´ı (one-way delay). Jeho v´ yhodou je fakt, ˇze cesta paketu s´ıt´ı nemus´ı b´ yt shodná v obou smˇerech, tj. v tomto pˇr´ıpadˇe by nám klasick´ y RTT dal informaci pouze o pr˚ umˇerné prodlevˇe. V pˇr´ıpadˇe zmˇeˇren´ı tˇechto cest nezávisle je moˇzné z´ıskat lepˇs´ı pˇrehled o v´ ykonnostn´ıch rozd´ılech (kaˇzdá z cest m˚ uˇze procházet pˇres r˚ uzné providery nebo dokonce zcela odliˇsné typy s´ıt´ı - napˇr. ATM versus SONET).

1.3.1

Aplikace ping

Program ping byl napsán r. 1983 Mikem Muussem. PING (neboli Packet InterNet Grouper) slouˇz´ı k detekci ˇcasu odezvy s´ıt’ového zaˇr´ızen´ı v IP s´ıti a patˇr´ı mezi standardn´ı nástroje pro správu s´ıtˇe. Ping pouˇz´ıvá ICMP zprávy Echo request a Echo reply. Pomoc´ı DNS serveru je testovaná URL adresa pˇreloˇzena na IP adresu a na ni je vyslán ICMP datagram s ˇza´dost´ı o odpovˇed’. Ve stanoveném limitu (bˇeˇznˇe cca 3 sekundy, jedná se o nastaviteln´ y parametr) aplikace ˇceká na odpovˇed’ Echo reply. Tuto odpovˇed’ lze identifikovat d´ıky poloˇzce icmp seq v tˇele ICMP zprávy (viz kapitola 1.2). S´ıt’ m˚ uˇzeme testovat pomoc´ı r˚ uznˇe dlouh´ ych paket˚ u, zjist´ıme tak optimáln´ı hodnotu tzv. MTU (maximum transmisson unit). MTU je hodnota udávaj´ıc´ı maximáln´ı velikost pˇrenosové jednotky na u ´rovni vrstvy s´ıt’ového rozhran´ı. Standardem z r.1990 (RFC1191) byla urˇcena maximáln´ı velikost paketu v s´ıt´ıch pouˇz´ıvaj´ıc´ıh standard Ethernet II na 1500 byte. V této hodnotˇe je zahrnuta standartn´ı TCP a IP hlaviˇcka (40 byte). Typická hodnota je tedy 1500 byte, nejmenˇs´ı moˇzná je 576 byte. Za zm´ınku stoj´ı varianta u ´toku typu DoS2 vyuˇz´ıvaj´ıc´ı chyby v TCP/IP protokolu. Mnoho poˇc´ıtaˇcov´ ych systém˚ u neumˇelo zpracovat ping vetˇs´ı neˇz 65535 byt˚ u (coˇz je maximáln´ı velikost paketu v protokolu IP). Takto abnormálnˇe velk´ y paket m˚ uˇze u ´toˇcn´ık poslat do s´ıtˇe, kde zp˚ usob´ı chyby (obvykle tzv. pˇreteˇcen´ı zásobn´ıku) vedouc´ı ˇ sen´ım je k selhán´ı systém˚ u, které nejsou proti takov´ ym chybn´ ym paket˚ um odolné. Reˇ 2

DoS neboli Denial of Service, technika u ´toku na internetové sluˇzby nebo stránky. Docház´ı pˇri n´ı k zahlcen´ı poˇzadavky a p´ adu nebo minimálnˇe nefunkˇcnosti a nedostupnosti pro ostatn´ı uˇzivatele.

16

kontrola opˇetovného spojován´ı IP fragment˚ u. Mus´ı platit, ˇze souˇcet pol´ı Fragment Offset a Total Length v IP hlaviˇcce kaˇzdého fragmentu je menˇs´ı neˇz 65535 byt˚ u. Pokud je souˇcet vˇetˇs´ı, paket je neplatn´ y a IP fragment je ”zahozen”. Pakety ICMP typu echo maj´ı ve smˇerovaˇc´ıch i koncov´ ych uzlech ˇcasto nastavenou niˇzˇs´ı prioritu zpracován´ı v˚ uˇci ostatn´ım druh˚ um komunikace a to se m˚ uˇze projevit na v´ ysledc´ıch mˇeˇren´ı. Nav´ıc ping obvykle pouˇz´ıvá malé pakety, takˇze i zde docház´ı ke znaˇcnému rozd´ılu pˇri jejich pr˚ uchodu s´ıt´ı v˚ uˇci velk´ ym TCP nebo UDP paket˚ um. Datové pakety maj´ı rozd´ılnou velikost, r˚ uzné priority, a r˚ uzné protokoly se v s´ıti chovaj´ı také jinak. Pˇri vyuˇz´ıván´ı programu ping pro mˇeˇren´ı kvalitativn´ıch parametr˚ u s´ıtˇe je tedy nutné vz´ıt v u ´vahu vˇsechny tyto aspekty. V souˇcasné dobˇe jiˇz existuje velké mnoˇzstv´ı nástroj˚ u pro mˇeˇren´ı RTT, nejjednoduˇsˇs´ı (ping implementovan´ y v OS Unix/Win) maj´ı pouze textov´ y v´ ystup, sloˇzitˇejˇs´ı nab´ız´ı grafické rozhran´ı se zobrazován´ım cesty paketu po zemˇekouli. Velmi pˇekn´ y grafick´ y v´ ystup poskytuje napˇr. program VisualRoute, slabinou vˇsak z˚ ustává zp˚ usob zjiˇst’ován´ı pˇresné geografické polohy pingan´ ych host˚ u (viz kapitola 1.4).

1.3.2

Faktory ovlivˇ nuj´ıc´ı mˇ eˇ ren´ı RTT

Pˇri odhadu vzdálenosti pomoc´ı RTT je tˇreba vz´ıt v u ´vahu nˇekolik faktor˚ u, které jednotlivá mˇeˇren´ı ovlivˇ nuj´ı. V´ ysledn´ y RTT je vˇzdy o nˇeco vˇetˇs´ı, neˇz minimáln´ı fyzikáln´ı hodnota, které by teoreticky mohl dosahovat. Ne vˇsechny faktory se vˇsak daj´ı eliminovat, vliv nˇekter´ ych se dá ˇca´steˇcnˇe predikovat. Jsou to zejména: • velikost MTU, • povaha pˇrenosového média - zda se jedná o mˇed’en´ y dvoudrát, optiku nebo tˇreba bezdrátov´ y pˇrenos. R˚ uzná prostˇred´ı znamenaj´ı r˚ uzné rychlosti ˇs´ıˇren´ı signálu, napˇr. po Ethernetu (tedy mˇedˇen´ y drát) se signál ˇs´ıˇr´ı rychlost´ı 0,66 rychlosti svˇetla; • pˇrenosová rychlost, kterou je zdroj pˇripojen do Internetu (tedy ˇs´ıˇrka pásma) • fyzická (geografická) vzdálenost mezi zdrojem a c´ılem • poˇcet uzl˚ u mezi zdrojem a c´ılem (topologie s´ıtˇe) • aktuáln´ı velikost provoz v s´ıti LAN, do které je zapojen koncov´ y uˇzivatel • poˇcet jin´ ych poˇzadavk˚ u, které jsou vyˇrizovány mezilehl´ ymi uzly (souvis´ı s prioritizac´ı paket˚ u) • pˇr´ıtomnost interferenc´ı ve veden´ı Je zˇrejmé, ˇze napˇr´ıklad zmˇenou MTU se dá dosáhnout lepˇs´ıho pr˚ uchodu testovac´ıch paket˚ u s´ıt´ı, naopak typ pˇrenosov´ ych médi´ı obzvláˇst’ u páteˇrn´ıch spoj˚ u nemáme

17

moˇznost jakkoliv ovlivnit (jistá moˇznost existuje u média pouˇzitého na posledn´ı m´ıli). Je vˇsak d˚ uleˇzité uvˇedomit si, ˇze vˇetˇsina faktor˚ u se bude uplatˇ novat jak pˇri mˇeˇren´ı RTT, tak pˇri bˇeˇzném vyuˇzit´ı s´ıtˇe, takˇze zmˇeˇren´ y RTT nám m˚ uˇze poskytnout pomˇernˇe dobr´ y obrázek o stavu s´ıtˇe.

1.4

Odhad geografick´ e polohy ze znalosti IP adresy

Dnes nejpouˇz´ıvanˇejˇs´ı rodina internetov´ ych protokol˚ u TCP/IP je postavená tak, ˇze ˇc´ıselné IP adresy jsou pˇridˇelovány nezávisle na tom, kde se fyzicky nacház´ı (tj. jaká je jejich geografická poloha), a také bez ohledu na to, jak´ ym zp˚ usobem jsou k Internetu pˇripojeny. Vzhledem k omezen´ ym moˇznostem z´ıskáván´ı informac´ı o lokalizaci IP adres je odhad pozice stanice v s´ıti na základˇe této metody velmi nepˇresn´ y. Vˇetˇsina aplikac´ı funguje na základˇe ˇcten´ı u ´daj˚ u z mezinárodn´ıch nebo (a) regionálˇ e n´ıch databáz´ı, jako je ARIN, APNIC nebo LACNIC. Poskytovatelé Internetu v Cesk´ republice vyuˇz´ıvaj´ı databázi RIPE, konkrétnˇe NCC (Network Coordination Centre). Ta obsahuje kontaktn´ı a registraˇcn´ı u ´daje pro tzv. RIPE NCC service region (kam spadá Evropa, Stˇredn´ı v´ ychod a ˇcást Asie). V RIPE databázi je moˇzno nalézt IP adresy, ˇc´ısla autonomn´ıch systém˚ u3 (AS), dále organizace nebo zákazn´ıky spojené s tˇemito AS a kontaktn´ı u ´daje pro tyto s´ıtˇe (Points of Contact, POC). Kaˇzdá organizace, která dle RIPE drˇz´ı IP adresy, je zodpovˇedná za jejich aktuálnost v databázi. Vˇsechny tyto informace jsou bˇeˇznˇe dostupné pˇr´ımo na www stránkách RIPE, viz adresa www.ripe.net. Jak tedy konkrétnˇe funguje odhad geografické pozice v s´ıti? Postup byl testován na IP adrese 62.168.37.105. Na stránce http://www.ripe.net/whois zadáme do formuláˇre IP adresu, kterou chceme lokalizovat. Z v´ ypisu nás nejv´ıce zaj´ımá poloˇzka address, pˇr´ıpadnˇe jeˇstˇe netname. Právˇe z adresy je moˇzno z´ıskat pˇredstavu o lokalizaci IP adresy. Pro náˇs konkrétn´ı pˇr´ıpad jsme z´ıskali záznam addres: Brno a netname: BRNO-NET. Dle tohoto záznamu m˚ uˇzeme odhadnout, ˇze IP adresa je vyuˇz´ıvána v 4 Brnˇe. Dotazem na providera (kter´ y je v´ ypisu v poloˇzce address uveden rovnˇeˇz) bylo zjiˇstˇeno, ˇze odhad koresponduje s realitou a daná IP adresa je opravdu v Brnˇe. Nicménˇe uˇz pˇri testován´ı dalˇs´ı IP adresy, 62.84.132.211, byla zjiˇstˇena nesrovnalost. V´ ypis odkazuje na adresu Praha, opˇetovn´ ym dotazem na poskytovatele vˇsak bylo zjiˇstˇeno, ˇze tato IP adresa je pouˇz´ıvána opˇet v Brnˇe. Poloˇzka address by totiˇz mˇela obsahovat geografickou lokaci prohledávané IP adresy, bohuˇzel velmi 3

Autonomn´ı systém je ˇc´ ast Internetu se spoleˇcnou smˇerovac´ı politikou, typicky ISP + jeho z´ akazn´ıci. 4 poskytovatel pˇripojen´ı k s´ıti Internet, jenˇz má tyto IP adresy pˇridˇeleny

18

ˇcasto v n´ı b´ yvá uvedeno s´ıdlo poskytovatele Internetu, kter´ y vlastn´ı adresn´ı rozsah s touto IP adresou, nebo napˇr. adresa s´ıdla firmy, která IP adresu vyuˇz´ıvá - nikoliv jej´ı poboˇcky, která ji opravdu pouˇz´ıvá fyzicky na nˇekterém zaˇr´ızen´ı. Mezi dalˇs´ı databáze funguj´ıc´ı obdobnˇe jako RIPE patˇr´ı ARIN (pro Severn´ı Ameriku), AFRINIC (Afrika), LACNIC (pro Latinskou Ameriku) a APNIC (Asie a Pacifik). Dalˇs´ı moˇznost´ı, jak zjistit geografickou polohu, m˚ uˇze b´ yt zjiˇstˇen´ı reverzn´ıho záznamu IP adresy (napˇr. pomoc´ı pˇr´ıkazu nslookup pod OS Win, host pod Linuxem). Pro testován´ı byla pouˇzita IP adresa 195.113.160.10 - jej´ı reverz byl zjiˇstˇen opˇet pomoc´ı programu nslookup: na pˇr´ıkazov´ y ˇra´dek (commandline) byl zadán pˇr´ıkaz ˇ ast odpovˇedi s revezn´ım záznamem byla: nslookup 195.113.160.10. C´ N´ azev: gate.fnplzen.cz. Z toho je moˇzno usoudit, ˇze tato IP se pravdˇepodobnˇe nalézá v Plzni. I tato metoda má vˇsak svá u ´skal´ı, vˇetˇs´ı neˇz pomoc´ı z´ıskáván´ı informace z RIPE: reverzn´ı záznam totiˇz nen´ı povinná poloˇzka (tj. mnoho adres ho nemá v˚ ubec) a neexistuje prakticky ˇzádná konvence, jak reverz zavádˇet. Napˇr´ıklad z reverzn´ıho záznamu pro adresu 175.75.89.65 je zˇrejmé, ˇze lokaci nemáme ˇsanci zjistit (nelze naj´ ıt adresu 175.75.89.65: non-existent domain). Posledn´ı moˇznost´ı m˚ uˇze b´ yt vytváˇren´ı vlastn´ı databáze. Tato moˇznost je vˇsak pro bˇeˇzné uˇzivatele sp´ıˇse nereálná a vzhledem k nutnosti neustálé aktuálnosti i velmi systémovˇe nároˇcná. Vˇetˇsina softwaru nebo pˇr´ımo internetov´ ych stránek ovˇeˇruj´ıc´ıch geografickou polohu IP adresy pracuje právˇe na bázi nˇekterého z v´ yˇse uveden´ ych mechanism˚ u. Na stejném principu pracuj´ı také nejr˚ uznˇejˇs´ı grafické programy traceroute, které s kaˇzd´ ym dalˇs´ım skokem vykresluj´ı jeho polohu na mapˇe. Pˇr´ıkladem sluˇzby, která pracuje se svou vlastn´ı databáz´ı, je sluˇzba IP2Location [12]. Tato sluˇzba pro v´ yˇse testované IP adresy nevrac´ı vˇsechny u ´daje totoˇzné jako ve v´ ypisu z RIPE. Grafick´ y program traceroute lze nalézt napˇr. na adrese [13]. Jedin´ ym opravdu spolehliv´ ym zp˚ usobem zjiˇstˇen´ı pˇresné geografické lokace IP adresy tedy z˚ ustává z´ıskán´ı informac´ı od providera, kter´ y má tuto adresu ve svém rozsahu, pˇr´ıpadnˇe samozˇrejmˇe od pˇr´ımého uˇzivatele IP adresy.

19

2

PREDIKCE POZICE STANICE V SÍTI

V souˇcasné dobˇe existuje pomˇernˇe velké mnoˇzstv´ı r˚ uzn´ ych systému, které umoˇzn ˇuj´ı odhad vzájemné vzdálenosti jednotliv´ ych uzl˚ u v s´ıti. Vzdálenost v tomto pˇr´ıpadˇe neznamená pˇr´ımou geografickou vzdálenost, metrikou je parametr latence. Aˇckoliv geografická vzdálenost je jedn´ım z faktor˚ u, které mˇeˇren´ı ovlivˇ nuj´ı, velmi ˇcasto se lze setkat s pˇr´ıpady, kdy geograficky vzdálenˇejˇs´ı uzly maj´ı vzájemnˇe v´ yraznˇe lepˇs´ı dobu odezvy, neˇz nˇekteré bliˇzˇs´ı. Z tohoto d˚ uvodu nelze vzdálenost uzl˚ u mˇeˇrit v geografick´ ych jednotkách a je nutno pouˇz´ıvat ˇcasové odezvy. Systémy se dˇel´ı podle dvou základn´ıch kritéri´ı: zda se jedná o centralizovan´ y (GNP) nebo decentralizovan´ y (Vivaldi) systém, nebo zda vyuˇz´ıvá aktivn´ıch (ID Maps) ˇci pasivn´ıch (SPAND) dat. Kaˇzd´ y z tˇechto systém˚ u má svá specifika, v´ yhody a nev´ yhody, a je nutné definovat si poˇzadavky tak, aby mohl b´ yt proveden správn´ y v´ ybˇer architektury. Vˇetˇsina z tˇechto systém˚ u vyuˇz´ıvá pro mˇeˇren´ı parametr latence RTT (viz kapitola 1.3). Mezi nejznámˇejˇs´ı patˇr´ı Spand, Remos project, IDMaps, Vivaldi nebo GNP (jehoˇz v´ yvoj zat´ım nebyl plnˇe dokonˇcen). Následuj´ıc´ı kapitola se detailnˇeji zab´ yvá dvˇema rozˇs´ıˇren´ ymi systémy s rozd´ılnou architekturou, IDMaps a GNP.

2.1 2.1.1

Projekty Remos a SPAND Remos

Remos (Resource Monitoring System) [17], vyvinut´ y v r.2000, je rozhran´ı nab´ızej´ıc´ı s´ıt’ov´ ym aplikac´ım relevantn´ı informace ohlednˇe jejich okol´ı, pˇr´ıpadnˇe o konkrétn´ıch uzlech v s´ıti nebo komunikaˇcn´ıch linkách. Snaˇz´ı se o dosaˇzen´ı kompromisu mezi pˇresnost´ı (poskytovaná informace je tzv. best-effort) a efektivitou. Sp´ıˇse neˇz na vlastn´ı implementaci je zamˇeˇren na rozhran´ı. Zdrojové informace o metrice z´ıskává z nezávisl´ ych zdroj˚ u - napˇr´ıklad pomoc´ı SNMP protokolu. Z tohoto d˚ uvodu je snaˇzˇs´ı celou aplikaci vytvoˇrit a implementovat (nezab´ yvá se pˇr´ımo mˇeˇren´ım, pouze poskytován´ım z´ıskan´ ych informac´ı dalˇs´ım aplikac´ım). Remos funguje na základˇe logické s´ıt’ové topologie. D˚ uleˇzit´ ym pojmem jsou toky (tzv. flows), coˇz jsou spojen´ı na u ´rovni aplikac´ı mezi dvˇema uzly (napˇr. audio nebo video). Toky jsou vyuˇz´ıvány jako abstrakce fyzick´ ych spojen´ı, d´ıky ˇcemuˇz je Remos pouˇziteln´ y nezávisle na detailech systému.

2.1.2

SPAND

Na rozd´ıl od Remosu, SPAND (Shared PAssive Network Performance Discovery) [6] sám pˇr´ımo provád´ı pasivn´ı sd´ılené mˇeˇren´ı a jeho v´ ysledky uchovává v centralizo-

20

vané databázi. Pasivn´ı technika mˇeˇren´ı závis´ı pouze na datovém provozu, kter´ y je generován aplikacemi pˇri komunikaci s ostatn´ımi uzly v Internetu. Sd´ılené mˇeˇren´ı se op´ırá o tuto myˇslenku: v pˇr´ıpadˇe, ˇze jsou si dva stroje v s´ıti bl´ızké (topologicky), je pravdˇepodobné, ˇze budou sd´ılet stejnou pˇr´ıstupovou linku spojuj´ıc´ı je s nˇekter´ ym vzdálen´ ym hostem. D´ıky tomu budou m´ıt oba dva k dispozici obdobnou ˇs´ıˇrku pásma a informace o latenci nebudou pˇr´ıliˇs rozd´ılné a nen´ı tˇreba provádˇet tolik mˇeˇren´ı, staˇc´ı v´ ysledné u ´daje sd´ılet (viz obrázek ˇc.2.1). Jednoznaˇcná v´ yhoda pasivn´ıho mˇeˇren´ı spoˇc´ıvá v nezahlcován´ı s´ıtˇe dalˇs´ım pake-

Obrázek 2.1: Sd´ılen´ı RTT u ´daj˚ u d´ıky malé vzdálenosti tov´ ym provozem, na druhou stranu má nˇekterá omezen´ı a nev´ yhody: pomoc´ı nˇej lze mˇeˇrit pouze takové oblasti Internetu, ve kter´ ych prob´ıhal v pˇredeˇslé dobˇe provoz. Napˇr´ıklad pokud se má nˇejak´ y klient rozhodnout, které zrcadlo1 si vybrat pro staˇzen´ı dat, mus´ı vyˇzadovat informace o vzdálenosti o vˇsech tˇechto zrcadlech. Systém zaloˇzen´ y na pasivn´ım monitorován´ı vˇsak poskytuje informace pouze o tˇech serverech, ke kter´ ym bylo jiˇz dˇr´ıve pˇristupováno. Dalˇs´ı nev´ yhodou m˚ uˇze b´ yt zmˇena s´ıt’ové topologie, protoˇze v tomto pˇr´ıpadˇe se stávaj´ı data nepouˇzitelná a zaktualizuj´ı se aˇz ve chv´ıli, kdy opˇet danou cestou poteˇce nˇejak´ y provoz. Pasivn´ı mˇeˇren´ı obvykle vyˇzaduje mˇeˇren´ı nebo pˇr´ımo snoopován´ı2 s´ıt’ového provozu, coˇz m˚ uˇze b´ yt povaˇzováno za poruˇsen´ı bezpeˇcnostn´ıch pravidel. 1 2

Zrcadla neboli mirrory jsou servery se stejn´ ym (zrcadl´ıc´ım) obsahem. angl. snoop = ˇspehov´ an´ı, sl´ıdˇen´ı

21

2.2

IDMaps

Jedn´ım ze zp˚ usob˚ u, jak z´ıskat informace o vzdálenosti aktivnˇe (tj. tato informace je mˇeˇrena pˇr´ımo hostem3 , kter´ y ji vyˇzaduje), je napˇr. vyuˇzit´ı aplikac´ı ping nebo traceroute. Tyto aplikace pracuj´ı na základˇe tzv. aktivn´ıho mˇeˇren´ı - pro samotné mˇeˇren´ı jsou pouˇzita data odeslaná pouze za t´ımto u ´ˇcelem. V´ yhodou tˇechto aplikac´ı je jejich jednoduchost, nicménˇe nezanedbateln´ y dopad na celou s´ıt’ m˚ uˇze m´ıt situace, kdy tato aktivn´ı mˇeˇren´ı bude neustále provádˇet vˇetˇs´ı poˇcet stanic - v´ yraznˇe vzroste datov´ y tok. Ideálnˇe by tedy toto mˇeˇren´ı mˇel provádˇet jeden stroj a poskytovat je ostatn´ım.

2.2.1

Sonar a HOPS

Obˇe dvˇe tyto sluˇzby zpracovávaj´ı data z´ıskávaná ze systému IDMaps a pˇredávaj´ı je dál. Server SONAR poskytuje ostatn´ım stanic´ım informace o vzdálenosti mezi n´ım a libovolnou vzdálenou stanic´ı. HOPS distribuuje informace o vzdálenosti mezi jednotliv´ ymi uzly hierarchicky, obdobnˇe jako napˇr. sluˇzba DNS. V´ ybˇer nejbliˇzˇs´ıho uzlu v tomto pˇr´ıpadˇe funguje na základˇe nejmenˇs´ıho poˇctu skok˚ u (tedy do v´ ybˇeru nezahrnuje vlastnosti jednotliv´ ych pˇrenosov´ ych linek). Obˇe dvˇe sluˇzby jsou typu klient/server. Kaˇzd´ y ze server˚ u by mˇel poskytovat odpovˇed’ ve velmi krátkém ˇcase nejlépe ˇcerpat informace z´ıskané pˇri dˇr´ıvˇejˇs´ıch mˇeˇren´ıch, které jsou aktuálnˇe uloˇzeny v lokáln´ıch pamˇet´ıch (nicménˇe nen´ı to podm´ınkou). Je d˚ uleˇzité si uvˇedomit, ˇze IDMaps je architekturou, která poskytuje u ´daje o vzdálenosti a pˇredává je sluˇzbám typu SONAR, které s n´ı potom pracuj´ı dále. Tato separace je nutná z d˚ uvodu rozdˇelen´ı jednotliv´ ych poˇzadavk˚ u na dva systémy. Poˇzadavek na IDMaps je relativnˇe velká pˇresnost mˇeˇren´ı vzdálenosti s co nejmenˇs´ımi náklady, zat´ımco poˇzadavky na sluˇzbu typu klient/server jsou rychlé odezvy na dotazy, velké objemy zpracovan´ ych dotaz˚ u a odpov´ıdaj´ıc´ı velikost u ´loˇziˇstˇe dat.

2.2.2

Metrika

C´ılem IDMaps je tedy poskytovat co nejaktuálnˇejˇs´ı informace o vzdálenosti v mˇeˇr´ıtku latence (napˇr. informace o round-trip zpoˇzdˇen´ı), pˇr´ıpadnˇe ˇs´ıˇrky pásma (tam, kde to lze). Nejv´ıce vyuˇz´ıvan´ y parametr pro odhad vzdálenosti je právˇe latence (viz kapitola 1.1). Lze ji totiˇz jednoduˇse mˇeˇrit - uˇz za pomoci malého mnoˇzstv´ı paket˚ u (ˇra´dovˇe jednotky aˇz des´ıtky) jsme schopni z´ıskat v´ ysledek s dobrou vypov´ıdaj´ıc´ı hodnotou. ˇıˇrka pásma je pro mnoho aplikac´ı rovnˇeˇz d˚ S´ uleˇzit´ ym u ´dajem, mˇeˇr´ı se vˇsak podstatnˇe 3

Host je v tomto smyslu jak´ ykoliv stroj na Internetu, at’ uˇz koncov´ y uˇzivatel, server atd.

22

obt´ıˇznˇeji. Jej´ı mˇeˇren´ı je draˇzˇs´ı, a dále je v´ıce citlivé na pˇresn´ y v´ ybˇer cesty: linka s nejuˇzˇs´ım pásmem v cestˇe paketu urˇcuje ˇs´ıˇrku pásma pro celou tuto cestu (struˇcnˇe ˇreˇceno, nejvyˇsˇs´ı pˇrenosová rychlost je daná nejpomalejˇs´ım u ´sekem cesty). IDMaps se op´ıraj´ı o myˇslenku, ˇze velmi pˇresné odhady vzdálenosti (s odchylkou cca 5% od skuteˇcné vzdálenosti) je pro tak rozˇs´ıˇrenou (a stále se rozˇsiˇruj´ıc´ı) sluˇzbu, jakou Internet bezesporu je, témˇeˇr nemoˇzné provést pˇr´ıliˇs efektivnˇe. Aˇckoliv pro jednotlivá mˇeˇren´ı konkrétn´ıch cest je moˇzno vysoké pˇresnosti dosáhnout, odhad zaloˇzen´ y na triangulaci tˇechto mˇeˇren´ı (viz kapitola 2.2.4) v sobˇe bude kumulovat chyby.

2.2.3

Zp˚ usoby mˇ eˇ ren´ı

Je potˇreba vz´ıt v u ´vahu dva odliˇsné u ´daje o vzdálenosti: za prvé s ohledem na zat´ıˇzen´ı s´ıtˇe, a za druhé tzv. ˇcistou vzdálenost (raw distance - tj. vzdálenost namˇeˇrenou pˇri nulovém zat´ıˇzen´ı s´ıtˇe). Tato ˇcistá vzdálenost m˚ uˇze principielnˇe odpov´ıdat nejmenˇs´ı celkovˇe namˇeˇrené hodnotˇe. V zájmu co nejvˇetˇs´ıho rozˇs´ıˇren´ı sluˇzby tato poˇc´ıtá s aktualizacemi u ´daj˚ u o ˇcisté vzdálenosti v ˇrádu dn˚ u, v pˇr´ıpadˇe potˇreby v ˇra´du hodin. To znamená, ˇze informace o vzdálenosti nebudou pˇresnˇe kop´ırovat pˇrechodné dˇeje v s´ıti, sp´ıˇse budou porovnávat dlouhodobˇejˇs´ı zmˇeny v s´ıt’ové topologii. Informace o okamˇzitém stavu s´ıtˇe (v ˇrádu max. des´ıtek vteˇrin) je témˇeˇr nemoˇzné poskytovat globálnˇe, obzvláˇst’ vezmeme-li v u ´vahu, ˇze se zrychluj´ıc´ım se Internetem se m˚ uˇze stát mnohem v´ yznamnˇejˇs´ı zpoˇzdˇen´ı vzniklé pˇri zpracován´ı informace neˇz jej´ı samotn´ y pˇrenos. V´ yˇse zm´ınˇené projekty Remos a SPAND poskytuj´ı informace o vzdálenosti pouze mezi stanicemi nacházej´ıc´ımi se bl´ızko serveru a vzdálen´ ymi uzly (ˇzadatel mus´ı b´ yt tedy v bl´ızkosti server˚ u). Poskytován´ı takové sluˇzby m˚ uˇze b´ yt jednoduˇsˇs´ı z d˚ uvodu menˇs´ıho mnoˇzstv´ı dat, se kter´ ymi mus´ı servery pracovat, ve srovnán´ı s mnoˇzstv´ım moˇzn´ ych destinac´ı (ˇrádovˇe N ). IDMaps ale poskytuj´ı informace o vzdálenosti mezi jak´ ymikoliv dvˇema platn´ ymi IP adresami, tj. ˇra´dovˇe N 2 . Mnoˇzstv´ı mˇeˇren´ ych dat vˇsak bude pravdˇepodobnˇe mnohem menˇs´ı, a to d´ıky globáln´ımu sd´ılen´ı informac´ı o vzdálenostech a také d´ıky technikám komprese pomoc´ı graf˚ u. Jednou z moˇznost´ı, jak poskytovat informace o vzdálenosti v s´ıti, je sestaven´ı graf˚ u (ideálnˇe stromov´ ych) fyzick´ ych spojen´ı mezi jednotliv´ ymi uzly v s´ıti. Vzdálenost mezi uzly se potom dá odhadnout pomoc´ı jejich vzdálenost´ı v tomto grafu. Tato metoda se naz´ yvá hop-by-hop approach (postup skok za skokem, viz [3]). Postup spoˇc´ıvá v pos´ılán´ı ICMP paket˚ u po tomto grafu. Aby se minimalizovaly momentáln´ı ˇ odchylky v s´ıti, kaˇzd´ yu ´daj se sb´ırá po urˇcitou dobu (napˇr. t´ ydny). Casto jsou vˇsak pokusy o toto mˇeˇren´ı zamˇen ˇovány se SPAMov´ ymi u ´toky, právˇe d´ıky délce mˇeˇren´ı. Nejjednoduˇsˇs´ı a zároveˇ n nejpˇresnˇejˇs´ı formou odhadu vzdálenosti z˚ ustává mˇeˇren´ı mezi vˇsemi koncov´ ymi IP adresami, nicménˇe je prakticky neproveditelné: v pˇr´ıpadˇe

23

N stanic bychom museli drˇzet informaci o velikosti N 2 (je nutné drˇzet informaci o vzájemn´ ych vzdálenostech vˇsech u ´ˇcastn´ık˚ u mˇeˇren´ı). Vzhledem k velikosti Internetu - poˇctu jednotliv´ ych stanic (stovky milion˚ u a stále vzr˚ ustá) - by ˇslo o velmi neefektivn´ı metodu (obdobnˇe jako neustálé vyhledáván´ı novˇe vznikl´ ych stanic). Druhou nejjednoduˇsˇs´ı formou je mˇeˇren´ı mezi jednotliv´ ymi adresov´ ymi prefixy4 (AP). V tomto pˇr´ıpadˇe je odhad vzdálenosti mezi IP adresami trochu komplikovanˇejˇs´ı neˇz prvn´ı zp˚ usob: u kaˇzdé IP adresy je nejprve zjiˇstˇeno, pod kter´ y AP patˇr´ı. Nicménˇe, objem dat v tomto pˇr´ıpadˇe stále z˚ ustává neefektivnˇe velk´ y - celosvˇetov´ y poˇcet AP se m˚ uˇze pohybovat v ˇra´dech statis´ıc˚ u a opˇet stále nar˚ ustá. Je tedy jasné, ˇze potˇrebujeme dalˇs´ı zjednoduˇsen´ı - napˇr. zjiˇstˇen´ı informac´ı vzdálenost´ı mezi jednotliv´ ymi autonomn´ımi systémy (AS) - za pˇredpokladu, ˇze v rámci jednotliv´ ych AS jsou vzdálenosti mezi IP adresami ekvidistatn´ı. I pˇresto, ˇze co se poˇctu mˇeˇren´ ych informac´ı t´ yˇce se situace znaˇcnˇe zjednoduˇsila (v celém Internetu m˚ uˇzou existovat max. desetitis´ıce AS), ani tato varianta nen´ı optimáln´ı: pomˇernˇe ˇcasto se stává, ˇze nˇekteré IP adresy jsou si velmi bl´ızko (at’ uˇz z hlediska latence nebo geografického), ale zároveˇ n patˇr´ı k jin´ ym AS, zat´ımco velmi vzdálené IP adresy mohou patˇrit pod stejné AS.

2.2.4

Tracery

Systém IDMaps vyuˇz´ıvá k mˇeˇren´ı vzdálenosti tzv. tracery, coˇz referenˇcn´ı jsou objekty velikostnˇe spadaj´ıc´ı mezi AS a AP. Tyto jsou rozm´ıstˇené po svˇetˇe tak, ˇze kaˇzd´ y AP je relativnˇe bl´ızko nˇekterému z tracer˚ u. Vzdálenosti tracer˚ u jsou zmˇeˇrené a známé, takˇze se aktualizuj´ı pouze u ´daje o vzdálenosti AP od tracer˚ u. Vzdálenosti jednotliv´ ych stanic se potom urˇc´ı jako suma vzdálenost´ı AP1 −→ tracer1 −→ tracer2 −→ AP2 (pˇriˇcemˇz stanice ˇc.1 náleˇz´ı do AP1 a stanice ˇc.2 do AP2). V´ ysledná pˇresnost závis´ı na poˇctu tracer˚ u a jejich rozm´ıstˇen´ı. Za pˇredpokladu, ˇze máme moˇznost oba tyto faktory ovlivnit, z´ıskáváme takto nástroj na zvyˇsován´ı pˇresnosti z´ıskan´ ych informac´ı. Z v´ yˇse uveden´ ych moˇznost´ı mˇeˇren´ı je právˇe tato nejvhodnˇejˇs´ı z hlediska pˇresnosti odhadu, a proto byla vybrána pro architekturu IDMaps. Ta sestává z tˇr´ı hlavn´ıch ˇcást´ı: tracery, AP a tzv. virtuáln´ı linky neboli ˇcisté vzdálenosti. Pˇredpoklad, ˇze vzdálenost mezi dvˇema body lze odhadnout jakoˇzto sumu vzdálenost´ı mezi jednotliv´ ymi mezilehl´ ymi body, u ´zce souvis´ı s troj´ uheln´ıkovou nerovnost´ı. Ta ˇr´ıká, ˇze máme-li v rovinˇe tˇri r˚ uzné body a, b, a c (vrcholy grafu), pak mus´ı platit: C(a, c) ≤ C(a, b) + C(b, c)

(2.1)

4

Adresn´ı prefix je definovan´ y jako po sobˇe jdouc´ı (následn´ y) rozsah IP adres, pˇriˇcemˇz vzdálenosti vˇsech host˚ u s IP adresami z toho AP jsou v˚ uˇci zbytku internetu ekvidistatn´ı.

24

kde funkce C je vzdálenost´ı v dané metrice. Z rovnice (2.1) vypl´ yvá, ˇze pokud známe C(a, b) a C(b, c), pak C(a, c) leˇz´ı mezi C(a, b) + C(b, c) (omezen´ı shora) a ˇ ım menˇs´ı je rozd´ıl tˇechto dvou v´ |C(a, b) − C(b, c)| (omezen´ı zdola). C´ yraz˚ u, t´ım pˇresnˇejˇs´ı odhad z´ıskáme. Podrobnˇejˇs´ı informace o triangulaci lze z´ıskat z literatury [5]. Do celé záleˇzitosti jeˇstˇe vstupuje routován´ı: to samo o sobˇe se samozˇrejmˇe nesnaˇz´ı nalézt pouze cestu s nejmenˇs´ı latenc´ı (tj. nejkratˇs´ı), v´ ysledná cesta je ovlivnˇená v´ıce faktory (typicky v routovac´ım protokolu OSPF - nejlepˇs´ı cesta je ta s nejniˇzˇs´ı souhrnnou cenou, pˇriˇcemˇz do ceny se zapoˇc´ıtává propustnost spoj˚ u, náklady na spoje atd.). Pˇri vyv´ıjen´ı systému IDMaps bylo provedeno pokusné mˇeˇren´ı, které mˇelo potvrdit ˇci vyvrátit, zda se triangulaˇcn´ı odhady daj´ı k odhadu vzdálenost´ı v Internetu pouˇz´ıt. Spoˇc´ıvalo v trasován´ı (pomoc´ı aplikace traceroute) mezi vybran´ ymi hosty bud’ pˇr´ımo, a nebo pˇres dalˇs´ı hostitele. Na základˇe tohoto mˇeˇren´ı bylo zjiˇstˇeno, ˇze 75-90% (v závislosti na vstupn´ıch podm´ınkách) vzdálenost´ı C(a, b) + C(b, c) bylo maximálnˇe dvakrát vˇetˇs´ı, neˇz je pˇr´ımá vzdálenost C(a, c) - opˇet v metrice latence.

2.2.5

Rozloˇ zen´ı tracer˚ u

Rozloˇzen´ı jednotliv´ ych tracer˚ u v´ yraznˇe ovlivˇ nuje v´ ysledky poskytované systémem IDMaps. Pro optimáln´ı v´ ypoˇcet se vyuˇz´ıvaj´ı dva algoritmy: k-HST a K-center (viz [9]). Na cel´ y problém se dá naz´ırat dvˇema zp˚ usoby: mˇejme s´ıt’ G s N uzly a mez´ı ´ B. Ukolem je naj´ıt co nejmenˇs´ı poˇcet tracer˚ u tak, aby vzdálenost mezi jak´ ymkoliv uzlem a nejbliˇzˇs´ım tracerem byla menˇs´ı nebo rovna B. ´ V druhém pˇr´ıpadˇe mˇejme s´ıt’ G s N uzly a ˇc´ıslo K. Ukolem je nalézt takové rozm´ıstˇen´ı K -tracer˚ u, které minimalizuje maximáln´ı vzdálenost mezi uzlem a jeho nejbliˇzˇs´ım tracerem. Tento problém je znám´ y jako minimum K-centre problem. Oba dva v´ yˇse zm´ınˇené algoritmy mohou b´ yt pouˇzity pro ˇreˇsen´ı tˇechto dvou r˚ uzn´ ych pohled˚ u. Nezanedbateln´ ym faktem ovˇsem je, ˇze Internet se pomˇernˇe rychle dynamicky vyv´ıj´ı a my neznáme jeho pˇresnou topologii. Z tohoto d˚ uvodu nen´ı c´ılem urˇcit nejmenˇs´ı moˇzn´ y poˇcet tracer˚ u potˇrebn´ ych k precizn´ımu odhadu vzdálenosti, ale sp´ıˇse zhodnocen´ı efektivity r˚ uzn´ ych um´ıstˇen´ı r˚ uzného poˇctu tracer˚ u. V´ ysledky mˇeˇren´ı v [2] vˇsak prokázaly, ˇze kvalita odhadu vzdálenosti témˇeˇr nen´ı závislá na s´ıt’ové topologii, kterou oba dva tyto algoritmy vyˇzaduj´ı. Z tohoto d˚ uvodu se jimi nebudeme dále zab´ yvat, pˇr´ıpadné informace lze nalézt v literatuˇre [9]. Dalˇs´ım d˚ uleˇzit´ ym faktorem je typ AS, do kterého budou tracery um´ıstˇeny. V pˇr´ıpadˇe tzv. tranzitn´ıho AS5 vyb´ıráme um´ıstˇen´ı tracer˚ u v rámci AS tak, aby tyto mˇely 5

Tranzitn´ı AS je propojeno s minimálnˇe dvˇema dalˇs´ımi AS a procház´ı pˇres nˇej provoz.

25

pˇr´ıstup k vysokokapacitn´ım linkám. Naopak v pˇr´ıpadˇe tzv. stub - AS6 vyb´ıráme um´ıstˇen´ı se sp´ıˇse n´ızkokapacitn´ımi linkami.

2.2.6

Virtu´ aln´ı spojen´ı

Jakmile jsou tracery v s´ıti rozm´ıstˇeny, zaˇcnou vzájemnˇe sledovat sebe a jednotlivá AP. V´ ysledné informace jsou pr˚ ubˇeˇznˇe oznamována klient˚ um (SONAR a HOPS - viz 2.2.1). Tyto na základˇe v´ ysledk˚ u sestavuj´ı mapy vzdálenost´ı. Za pˇredpokladu, ˇze v s´ıti budeme m´ıt cca 5% tracer˚ u z celkového poˇctu sledovan´ ych stanic, v pˇr´ıpadˇe s´ıtˇe Internet bychom museli kontinuálnˇe sledovat a drˇzet informace o obrovském mnoˇzstv´ı virtuáln´ıch cest mezi tˇemito tracery. Nicménˇe vezmeme-li v u ´vahu jiˇz zm´ınˇenou troj´ uheln´ıkovou nerovnost a efektivn´ı routován´ı, nen´ı nezbytnˇe nutné drˇzet informaci o velikost B 2 (kde B je poˇcet tracer˚ u) k tomu, abychom dosáhli postaˇcuj´ıc´ı pˇresnosti. Pˇripomeˇ nme, ˇze vˇsechny IP adresy v rámci jednoho AP m˚ uˇzeme v˚ uˇci zbytku Internetu povaˇzovat za ekvidistantn´ı. Pokud nen´ı v konfiguraci daného AP pˇr´ımo ˇreˇceno, ke kterému traceru patˇr´ı, mohou ho odhalit (a zmˇeˇrit vzdálenost AP −→ tracer) pouze nejbliˇzˇs´ı tracery. Z toho vypl´ yvá, ˇze prvn´ı tracer, kter´ y AP odhal´ı, pˇredpokládá, ˇze je nejbliˇzˇs´ı a svou vzdálenost od AP zavede do databáze. Ostatn´ı tracery mohou poté zkouˇset, zda náhodou nejsou bl´ıˇze. V pˇr´ıpadˇe, ˇze ano, pˇrep´ıˇs´ı informaci v databázi, a p˚ uvodn´ı tracer pˇrestává vzájemnou vzdálenost mˇeˇrit. Dalˇs´ı otázkou je, zda je v˚ ubec dostaˇcuj´ıc´ı mˇeˇrit vzdálenost AP pouze od jednoho traceru. Pokud je totiˇz AP routováno smˇerem ven do Internetu v´ıce cestami, mˇeˇrená vzdálenost pouze k jedinému traceru m˚ uˇze dávat nepˇresnou informaci (data mohou mezi AP a zbytkem Internetu putovat i jinou cestou, neˇz je ta trasovaná). AP se pot´ ykaj´ı s obdobn´ ym problémem jako AS, nicménˇe v menˇs´ım rozsahu. Jde o to, ˇze jednotliv´ı ISP mohou adresn´ı bloky propagované protokolem BGP dále dˇelit na menˇs´ı podbloky (napˇr. právˇe AP), které jsou ovˇsem v rámci topologie s´ıtˇe od sebe r˚ uznˇe vzdálené. Jedin´ ym zp˚ usobem, jak zjistit adresn´ı rozsahy tˇechto podblok˚ u, je dotazován´ı na routery ISP pomoc´ı SNMP protokolu (viz RFC1157). Optimáln´ı je, pokud sám ISP urˇc´ı polohu traceru v jeho s´ıti - pokud moˇzno vˇetˇs´ıho poˇctu.

2.2.7

V´ ykonnost syst´ emu

V´ ykonnost systému IDMaps m˚ uˇze b´ yt zhodnocena pomoc´ı kritéria uˇziteˇcnosti poskytované informace o vzdálenosti pro jednotlivé dotazuj´ıc´ı se aplikace. Dá se ovˇeˇrit praktick´ ym pˇr´ıkladem: klient má za u ´kol na základˇe informac´ı z IDMaps vybrat jedno z nˇekolika zrcadel (nejbliˇzˇs´ı) v s´ıti. Tento klient by tedy mˇel b´ yt 6

Stub - AS je typ AS, které je pˇripojeno pouze na jedno dalˇs´ı AS - je v podstatˇe hraniˇcn´ı.

26

Obrázek 2.2: Optimáln´ı rozloˇzen´ı tracer˚ u pˇresmˇerován na zrcadlo, které má ve stromovém grafu (zkonstruovaném na základˇe znalosti fyzické topologie) nejkratˇs´ı cestu. V´ ysledky testován´ı systému po jeho dokonˇcen´ı prokázaly nˇekolik v´ yznamn´ ych fakt˚ u: • v´ ybˇer zrcadel pomoc´ı informac´ı z IDMaps byl znatelnˇe lepˇs´ı neˇz ˇcistˇe náhodn´ y v´ ybˇer • s´ıt’ová topologie ˇcásteˇcnˇe m˚ uˇze v´ ysledky ovlivnit • metoda rozm´ıstˇen´ı tracer˚ u, která nezávis´ı na znalosti s´ıt’ové topologie, udává stejnˇe dobré nebo dokonce lepˇs´ı v´ ysledky odhad˚ u neˇz algoritmy apriori znalost topologie vyuˇz´ıvaj´ıc´ı • zvyˇsován´ı poˇctu tracer˚ u (nad 2% poˇctu uzl˚ u v s´ıti) nen´ı co se v´ ysledku t´ yˇce efektivn´ı, uˇz 0,2% - pod´ıl tracer˚ u v s´ıti vrac´ı pˇresné odpovˇedi s velkou pravdˇepodobnost´ı (v´ıce neˇz 80%) pˇri 90% pokus˚ u • poˇcet virtuáln´ıch link˚ u mezi tracery by nemˇel b´ yt v´ yraznˇe vyˇsˇs´ıho ˇrádu, neˇz samotn´ y poˇcet tracer˚ u • se zvyˇsuj´ıc´ım se poˇctem tracer˚ u testuj´ıc´ıch jedno AP se zároveˇ n zvyˇsuje pˇresnost odhadu Systém IDMaps lze tedy velmi dobˇre vyuˇz´ıt pro urˇcován´ı vzdálenost´ı jednotliv´ ych host˚ u v s´ıti a d´ıky tomu zároveˇ n poskytovat efektivn´ı informace pro dalˇs´ı sluˇzby pracuj´ıc´ı s t´ımto druhem informace.

27

2.3

Global Network Positioning (GNP)

Metoda odhadu pozice stanice v s´ıti, jenˇz je v souˇcasné dobˇe pravdˇepodobnˇe nejpˇresnˇejˇs´ı, je GNP (Global Network Positioning). Nejv´ yznamnˇejˇs´ı faktory ovlivˇ nuj´ıc´ı urˇcen´ı pozice pomoc´ı tohoto algoritmu jsou pˇresnost mˇeˇren´ı RTT (mˇeˇren´ı vzdálenost´ı tedy prob´ıhá pomoc´ı ICMP protokolu.), rozm´ıstˇen´ı orientaˇcn´ıch bod˚ u a pˇrevod vzdálenost´ı v s´ıti do prostoru. Systém vyuˇz´ıvá vypoˇc´ıtané vzdálenosti k urˇcen´ı skuteˇcn´ ych vzdálenost´ı. Prvn´ı krok odhadu spoˇc´ıvá v rozm´ıstˇen´ı dostateˇcného poˇctu orientaˇcn´ıch bod˚ u (tzv. landmarks), pˇriˇcemˇz jejich minimáln´ı poˇcet je vˇzdy N + 1, kde N je dimenze (napˇr. N = 2 pro odhad v 2D-prostoru). Tyto orientaˇcn´ı body jsou urˇcité uzly v s´ıti, které tvoˇr´ı kostru celého v´ ypoˇctu. S jejich vyuˇzit´ım mohou vˇsechny stanice pˇredpovˇedˇet svou pozici v s´ıti a to aniˇz by byl generován zbyteˇcnˇe velk´ y tok dat. Obdobnˇe jako u systému IDMaps existuje problém optimáln´ıho rozloˇzen´ı tracer˚ u (viz ), GNP se rovnˇeˇz zab´ yvá rozloˇzen´ım landmark˚ u [8]. Pro optimáln´ı rozloˇzen´ı je tˇreba znát informace o jejich poˇctu, zmˇeˇrenou vzdálenost mezi nimi (pomoc´ı RTT) a vzájemnou vypoˇc´ıtanou vzdálenost, pˇriˇcemˇz je tˇreba hledat minimum funkce celkové sumy chyb. Jakmile jsou orientaˇcn´ı body ustaveny, lze zaˇc´ıt odhad pozice jednotliv´ ych uzl˚ u v s´ıti - postupuje se obdobn´ ym zp˚ usobem, jako pˇri urˇcován´ı souˇradnic samotn´ ych orientaˇcn´ıch bod˚ u. Nejprve jsou zmˇeˇreny vzdálenosti mezi stanic´ı, jej´ıˇz polohu odhadujeme, a znám´ ymi landmarky a na základˇe tˇechto u ´daj˚ u jsou vypoˇc´ıtány jej´ı souˇradnice. V´ yhodou systému GNP oproti IDMaps je architektura typu peer-to-peer. IDMaps funguj´ı jako klient-server, takˇze dotazy vys´ılané jednotliv´ ymi klienty mohou znamenat nav´ yˇsen´ı zpoˇzdˇen´ı, které u peer-to-peer s´ıt´ı nevzniká. U nich naopak docház´ı na vyˇza´dán´ı jedné stanice k odeslán´ı souˇradnic stanice druhé, d´ıky ˇcemuˇz prvn´ı stanice je pak schopná vypoˇc´ıtat parametry spojen´ı k druhé stanici. V ˇclánku [7] je ukázán tzv. scale factor, s jehoˇz pomoc´ı se dá srovnat skuteˇcná vzdálenost (geografická) se vzdálenost´ı zmˇeˇrenou (RTT): 2· S=

P

Li ,Lj ∈Lk

N2

dsL

i ,Lj

dLi ,Lj

(2.2)

−2

V rovnici (2.2) N znamená prostorovou dimenzi, ds oznaˇcuje vypoˇc´ıtanou vzdálenost a d vzdálenost zmˇeˇrenou. Zde tedy pˇricház´ı v u ´vahu mˇeˇren´ı RTT vzdálenost´ı a jejich porovnán´ı se skuteˇcn´ ymi geografick´ ymi. Struˇcnˇe ˇreˇceno, metoda GNP se snaˇz´ı pˇriˇradit jednotliv´ ym uzl˚ um v s´ıti eukleidovské souˇradnice na základˇe mˇeˇren´ı RTT a znalosti korespondence latence a geografické vzdálenosti. Zaj´ımavou myˇslenkou je umist’ován´ı jednotliv´ ych uzl˚ u do v´ıce neˇz 2D prostoru. V pˇr´ıpadˇe 2D je totiˇz potˇreba nˇekteré stanice um´ıstit mnohem dále

28

od ostatn´ıch. V pˇr´ıpadˇe 3D prostoru tyto ”tˇeˇzko umistitelné” uzly m˚ uˇzeme lépe polohovat pomoc´ı tˇret´ıho rozmˇeru. Obdobnˇe kaˇzdá dalˇs´ı dimenze tento problém ˇreˇs´ı lépe. Detailn´ı popis této metody lze nalézt v jiˇz zmiˇ nované literatuˇre [8].

29

3

´ ˇ REN ˇ Í LATENCE NASTROJE PRO ME

3.1 3.1.1

Vytvoˇ ren´ı zdrojov´ ych k´ od˚ u aplikace ping Implementace

Vytvoˇrená aplikace ping je urˇcená pro pouˇzit´ı pod systémem Linux (pˇr´ıpadnˇe Unix). Naprogramován´ı bylo provedeno v jazyce C a pˇreklad za pomoc´ı kompilátoru gccc++-3.3.2, kter´ y je souˇcást´ı distribuce Mandrake 10.0. Nejd˚ uleˇzitˇejˇs´ı souˇca´st´ı kódu je tzv. socket, pomoc´ı kterého se vytváˇr´ı spojen´ı mezi jednotliv´ ymi stroji. Soket je mechanizmus zajiˇst’uj´ıc´ı komunikaci, kter´ y byl poprvé implementován v operaˇcn´ım systému BSD. Jedná se o velice obecn´ y nástroj. Stejné funkce lze vyˇz´ıvat pro komunikaci pomoc´ı r˚ uzn´ ych protokol˚ u, nejˇcastˇeji vˇsak TCP/IP a UDP/IP. Vˇsechny operaˇcn´ı systémy na bázi Unixu maj´ı shodné soketové API (tj. na vˇsech systémech unixového typu by mˇely b´ yt k dispozici stejné funkce se stejn´ ymi parametry). Pˇri pouˇzit´ı soket˚ u na operaˇcn´ıch systémech typu MS Windows (tzv. WinSock) docház´ı k m´ırn´ ym zmˇenám, nˇekteré funkce maj´ı jiné typy parametr˚ u, maj´ı ménˇe (pˇr´ıpadnˇe jiné) moˇznost´ı. Dále je zde nˇekolik speciáln´ıch funkc´ı, které v unixovém soketovém API nejsou k dispozici. Po otestován´ı chybov´ ych stav˚ u dojde v aplikaci k vytvoˇren´ı socketu, naplnˇen´ı ICMP paketu a jeho vyslán´ı. Zároveˇ n je zaznamenán ˇcas. Jakmile pˇrijde odpovˇed’ (jednoznaˇcnˇe identifikovaná v záhlav´ı ICMP paketu), opˇet je zaznamenán ˇcas a vypsána statistika. Kód aplikace se struˇcnou dokumentac´ı viz pˇr´ıloha A. Podrobné informace o socketovém programován´ı a aplikaci ping byly z´ıskány za pomoc´ı literatury [1] a Internetu [16].

3.1.2

Ovˇ eˇ ren´ı funkˇ cnosti

Pro ovˇeˇren´ı správné funkˇcnosti vytvoˇrené aplikace bylo provedeno srovnávac´ı mˇeˇren´ı. Srovnán´ı prob´ıhalo s aplikac´ı ping, která je pˇr´ımo implementovaná v OS Linux, distribuce Mandrake 10.0. Testován´ı bylo provádˇeno na dvou r˚ uzn´ ych IP adresách, ˇ a jedné z USA. Na kaˇzdou IP adresu bylo ’pingáno’ stokrát za sebou jedné z CR zároveˇ n obˇema aplikacemi, ze stejného stroje. V´ ysledky testu jsou zaznamenány v tabulce ˇc.3.1. Zaznamenává minimáln´ı (min), maximáln´ı (max) a pr˚ umˇern´ y (avg) ˇcas zmˇeˇreného RTT (v milisekundách). Ping1 odpov´ıdá aplikaci, která je jiˇz implementovaná v systému Linux, ping2 novˇe vytvoˇrené aplikaci. Z tabulky vypl´ yvá, ˇze ˇ resp. 1,1% (USA). Novˇe pr˚ umˇerné v´ ysledky mˇeˇren´ı RTT se od sebe liˇs´ı o 4,7% (CR)

30

c´ılov´ a IP adresa

aplikace

RTT min

RTT max

RTT avg

212.47.0.4

ping1 ping2 ping1 ping2

7,363 7,315 110,365 110,209

38,680 17,965 311,328 319,954

8,216 7,849 122,326 120,949

4.68.17.135

Tabulka 3.1: Porovnán´ı linuxové a novˇe vytvoˇrené aplikace v milisekundách naprogramovaná aplikace tedy m˚ uˇze b´ yt pro bˇeˇzná mˇeˇren´ı RTT pouˇzita, zdrojové kódy jsou funkˇcn´ı a jejich v´ ystupem jsou relevantn´ı hodnoty.

3.2

Vytvoˇ ren´ı skript˚ u pro mˇ eˇ ren´ı RTT a zpracov´ an´ı v´ ysledk˚ u

Jak jiˇz bylo v pˇredeˇslém textu ˇreˇceno, urˇcen´ı závislosti hodnoty RTT na geografické vzdálenosti m˚ uˇze b´ yt efektivnˇe vyuˇzito jakoˇzto souˇcást algoritm˚ u GNP apod. Abychom byli schopni odpovˇedˇet na otázku, zda je v˚ ubec RTT moˇzno nˇejak´ ym zp˚ usobem mapovat na skuteˇcné vzdálenosti, bylo nutno provést velk´ y poˇcet mˇeˇren´ı po celém svˇetˇe. Zˇrejmˇe nejvˇetˇs´ı problém s pˇresnou lokac´ı zahraniˇcn´ıch IP adres byl vyˇreˇsen pomoc´ı s´ıtˇe PlanetLab, ve které mˇeˇren´ı latence prob´ıhalo.

3.2.1

S´ıt’ PlanetLab

PlanetLab [18] je celosvˇetová poˇc´ıtaˇcová s´ıt’, která slouˇz´ı pro v´ yzkum distribuovan´ ych systém˚ u, s´ıt’ov´ ych aplikac´ı apod. Jednotlivé uzly s´ıtˇe jsou rozloˇzeny po celé planetˇe (nutno podotknout, ˇze nikoliv rovnomˇernˇe - vyspˇelé zalidnˇené oblasti jsou samozˇrejmˇe pokryty hustˇeji), ˇc´ımˇz umoˇzn ˇuj´ı testován´ı v reálném prostˇred´ı celosvˇetového Internetu. Projekt PlanetLab vznikl v r.2002 na nˇekolika americk´ ych uniˇ verzitách a v souˇcastnosti ˇc´ıtá cca 800 uzl˚ u. V CR jsou dva uzly - jeden um´ıstˇen na FIT VUTBR a druh´ y na s´ıti CESNET. Do s´ıtˇe PlanetLabu maj´ı pˇr´ıstup pouze instituce a firmy, které se na nˇem samy aktivnˇe pod´ılej´ı (tj. samy na svém pracoviˇsti vytvoˇr´ı alespoˇ n jeden z uzl˚ u této s´ıtˇe). V souˇcasnosti existuje mnoho projekt˚ u, které tuto s´ıt’ vyuˇz´ıvaj´ı (namátkou jmenujme CoDNS - distribuovan´ y DNS odolnˇejˇs´ı proti u ´tok˚ um; projekt RON zamˇeˇren´ y na tvorbu a optimalizaci routovac´ıch tabulek atd.). Pˇrednost PlanetLabu spoˇc´ıvá pˇredevˇs´ım v moˇznosti vytváˇren´ı nezávisl´ ych aplikac´ı, které mohou bˇeˇzet v s´ıti vedle sebe a vytváˇret tak ucelené virtuáln´ı vrstvy s´ıtˇe. Vrtsvy pouˇz´ıvaj´ı spoleˇcné uzly bez toho, aby se pˇri jejich uˇzit´ı jakkoliv vzájemnˇe ovlivˇ novaly.

31

Postup celého mˇeˇren´ı bylo nutno rozdˇelit do nˇekolika základn´ıch krok˚ u pˇribliˇznˇe takto: – vytvoˇren´ı skriptu, kter´ y bude schopn´ y po distribuci od PlanetLabu pingat na seznam host˚ u – vytvoˇren´ı skriptu odstraˇ nuj´ıc´ıho duplicity mˇeˇren´ı (protoˇze kaˇzd´ y pingá na kaˇzdého, v ideáln´ım pˇr´ıpadˇe tak z´ıskáváme kaˇzd´ y záznam vlastnˇe dvakrát) – vytvoˇren´ı skriptu, kter´ y dokáˇze spoˇc´ıtat skuteˇcnou geografickou vzdálenost dvou m´ıst na zemˇekouli, pˇr´ıˇcemˇz na vstupu jsou souˇradnice. – vlastn´ı mˇeˇren´ı a následné zpracován´ı dat Jednotlivé skripty jsou detailnˇeji popsány v následuj´ıc´ıch kapitolách. V´ ysledná data (vzdálenosti a zmˇeˇrené RTT) je potˇreba k sobˇe správnˇe napárovat, ˇc´ımˇz z´ıskáme soubor dat vhodn´ y pro dalˇs´ı anal´ yzu. Protoˇze na drtivé vˇetˇsinˇe stanic, které jsou souˇca´st´ı s´ıtˇe PlanetLab, je program ping implemetován jiˇz v základu (ovˇeˇreno pomoc´ı návratov´ ych kód˚ u PlanetLabu), nebyl pro mˇeˇren´ı RTT pouˇzit vlastn´ı zdrojov´ y kód, ale pˇr´ımo implementované aplikace. Postup mˇeˇren´ı prob´ıhal následuj´ıc´ım zp˚ usobem: Nejprve byl z´ıskán aktuáln´ı seznam ˇziv´ ych (tj. aktivn´ıch) stanic s´ıtˇe - jejich poˇcet se pohyboval obvykle mezi 180-200. Tento seznam byl spoleˇcnˇe s vytvoˇren´ ymi skripty nahrán do s´ıtˇe PlanetLab na vˇsechny tyto aktivn´ı stroje. Po nastaven´ı pˇr´ısluˇsn´ ych práv bylo provedeno mˇeˇren´ı pingu na vytvoˇren´ y seznam (doba mˇeˇren´ı se pohybovala okolo 20ti minut). Po zkonˇcen´ı mˇeˇren´ı byly v´ ysledky zaznamenány do soubor˚ u a ty následnˇe ze s´ıtˇe PlanetLab staˇzené. V této fázi ˇslo pouze o surová data, která bylo nutno dále zpracovat pomoc´ı skriptu na vyˇrazen´ı duplicit a poˇc´ıtan´ı zemˇepisné vzdálenosti. Tyto v´ ypoˇcty trvaj´ı pˇri uvedeném poˇctu mˇeˇren´ ych host˚ u cca 2 hodiny - pˇri kaˇzdém mˇeˇren´ı (po vyˇrazen´ı duplicit) bylo z´ıskáno pr˚ umˇernˇe 17000 unikátn´ıch záznam˚ u. Nutno poznamenat, ˇze pro u ´ˇcely mˇeˇren´ı byl vybrán vˇzdy jen jeden uzel v dané lokalitˇe (typicky mnoho univerzit disponuje napˇr. tˇremi i v´ıce uzly na stejné zemˇepisné adrese). Pˇri pouˇzit´ı vˇsech aktivn´ıch uzl˚ u by se jejich poˇcet pˇribliˇznˇe zdvojnásobil, coˇz by znaˇcnˇe prodlouˇzilo dobu následn´ ych zpracován´ı mˇeˇren´ ych dat. Metoda mˇeˇren´ı v s´ıti PlanetLab má vˇsak i svá u ´skal´ı. Prvn´ım z nich je fakt, ˇze pˇri odeˇc´ıtán´ı souˇradnic jednotliv´ ych stanic jsme odkázáni na lidsk´ y faktor - souˇradnice jsou do systému zadávány ruˇcnˇe. V nˇekter´ ych pˇr´ıpadech scházely u ´plnˇe a nepodaˇrilo se je urˇcit, v nˇekter´ ych pˇr´ıpadech je bylo moˇzno dohledat pomoc´ı sluˇzby Google Maps. Z d˚ uvodu ˇcasové nároˇcnosti vˇsak nebylo moˇzno ovˇeˇrit, zda vˇsechny jiˇz zadané souˇradnice do s´ıtˇe PlanetLab koresponduj´ı s realitou, namátková kontrola vˇetˇsinovˇe potvrdila, ˇze ano. Druh´ ym problémem je samotnˇe mˇeˇren´ı v s´ıti PlanetLab. Tato s´ıt’ má své koˇreny v

32

univerzitn´ıch s´ıt´ıch a postupnˇe se na n´ı nabalovaly v´ yznamné svˇetové firmy. Sv´ ym zp˚ usobem tento fakt m˚ uˇze ovlivnit topologii s´ıtˇe - mˇeˇren´ı v n´ı zkrátka nemus´ı objektivnˇe reflektovat reálné celosvˇetové podm´ınky s´ıtˇe Internet, mapuje sp´ıˇse jednu jej´ı specifickou ˇca´st. Bohuˇzel se vˇsak v pr˚ ubˇeho mˇeˇren´ı nepodaˇrilo z´ıskat dostateˇcné mnoˇzstv´ı dat z jin´ ych s´ıt´ı. Vˇsechny skripty byly z d˚ uvodu jednoduchosti napsány pˇr´ımo v shellu Bash pod OS Linux, Mandrake 10.0. Pro pˇrehlednost byly rozdˇeleny do nˇekolika ˇca´st´ı:

3.2.2

Vytvoˇ ren´ı seznamu stanic

Nejprve bylo nutné vytvoˇrit vlastn´ı databázi, která obsahuje na kaˇzdém ˇra´dku název uzlu a jeho geografické souˇradnice. Tato databáze je uloˇzena v souboru nodes.axis a vyuˇz´ıvá se pro pˇr´ıpravu kaˇzdého mˇeˇren´ı. Byla vytvoˇrena ruˇcnˇe - informace o zemˇepisn´ ych souˇradnic´ıch jednotliv´ ych uzl˚ u se nacház´ı na www stránkách PlanetLabu. Databáze nen´ı koneˇcná a témˇeˇr pˇri kaˇzdém mˇeˇren´ı je nutno do n´ı pˇridat dalˇs´ı záznamy, podle toho zda je ˇziv´ y nˇejak´ y nov´ y, dosud nepouˇzit´ y uzel. Tato databáze se pak porovnává s aktuáln´ım seznamem stanic (na vstupu), na ystupu které budeme pingat, pomoc´ı skriptu prepare nodes, viz pˇr´ıloha F. Na v´ skriptu je tent´ yˇz seznam obohacen´ y o souˇradnice1 s názvem nodes.txt. Aktuáln´ı seznam stanic PlanetLabu lze z´ıskat na www adrese http://comon.cs.princeton.edu/. Tento seznam je moˇzno r˚ uznˇe filtrovat podle potˇrebn´ ych kritéri´ı: pouze ˇzivé uzly, pouze jeden uzel v kaˇzdé lokalitˇe nebo napˇr. pouze takové uzly, které maj´ı dostateˇcnˇe velk´ y diskov´ y prostor (obzvláˇst’ tato moˇznost se ukázala b´ yt velmi nápomocnou - uzly maj´ıc´ı málo m´ısta na disku totiˇz vykazovaly chyby pˇri zapisován´ı hodnot do promˇenn´ ych, ˇc´ımˇz v´ yraznˇe ovlivˇ novaly v´ ysledky mˇeˇren´ı).

3.2.3

Skript pro mˇ eˇ ren´ı RTT

Tento skript (pojmenovan´ y jako ping nodes random, viz pˇr´ıloha B) má za u ´kol prom´ıchán´ı vstupn´ıho seznamu host˚ u (nodes.txt), na které se bude pingat, poté provést vlastn´ı ping na tento seznam. V´ ysledek je pˇredán na v´ ystup do souboru 2 pojmenovaného jmeno stanice.result . Pˇri poˇctu cca 200 stanic ve vstupn´ım souboru bˇeˇz´ı tento skript pˇribliˇznˇe 20 minut, coˇz je zp˚ usobeno nastaven´ım parametr˚ u (poˇcet ping˚ u na jednotlivé hosty, doba prodlevy pˇri neobdrˇzen´ı paketu; tyto parametry lze ve skriptu mˇenit dle potˇreby). 1

Nˇekteré z´ aznamy vˇsak ve v´ ystupn´ım souboru m˚ uˇzou chybˇet, a to v pˇr´ıpadˇe, ˇze nebyl v souboru nodes.axis poˇzadovan´ y uzel nalezen. V tom pˇr´ıpadˇe je nutné ho doplnit a skript spustit znovu, pˇr´ıpadnˇe pokud jeho souˇradnice neznáme, u ´plnˇe ho vyˇradit ze vstupn´ıho souboru. 2 Jmeno stanice je nahrazeno konkretn´ım hostname daného uzlu, ze kterého se pingá.

33

Prom´ıchán´ı vstupn´ıho souboru bylo provedeno z d˚ uvodu alespoˇ n ˇcásteˇcného odstranˇen´ı vlastn´ıho zat´ıˇzen´ı s´ıtˇe: pokud bychom soubor nodes.txt nahráli na vˇsechny stanice a ty by zároveˇ n zaˇcaly pingat od prvn´ı poloˇzky v seznamu, v´ ysledky mˇeˇren´ı by mohly b´ yt ovlivnˇeny pˇret´ıˇzen´ım (na zaˇcátku by vˇsechny uzly pingaly na prvn´ı poloˇzku, poté na druhou atd., k posuvu by docházelo jen postupnˇe). Kód pro prom´ıchán´ı (random shuffle) byl pˇrevzat z [14]. V´ ysledkem tohoto skriptu je tedy pro kaˇzdou stanici tolik soubor˚ u, kolik je záznam˚ u ve vstupn´ım souboru nodes.txt (m´ınus jeden, kter´ y odpov´ıdá právˇe této stanici). V´ ysledné soubory bylo nutno ze s´ıtˇe PlanetLab stáhnout pro dalˇs´ı zpracován´ı. Záznamy v souborech ve formˇe ˇrádk˚ u maj´ı tento tvar: kupl1.ittc.ku.edu;38.9527;-95.2644;129.670;134.942;138.652;3.829;Tue May 13 09:22:10 UTC 2008 Prvn´ı záznam odpov´ıdá c´ılové stanici, následuje zemˇepisná ˇs´ıˇrka a délka zdrojové stanice (po n´ı je pojmenován cel´ y soubor), dále souˇradnice c´ılového uzlu, hodnota pr˚ umˇerného zmˇeˇreného RTT (v ms) a ˇcas.

3.2.4

Poˇ c´ıt´ an´ı geografick´ e vzd´ alenosti

Prvn´ı zpracován´ı staˇzen´ ych soubor˚ u spoˇc´ıvalo v poˇc´ıtán´ı skuteˇcné geografické vzdálenosti mezi jednotliv´ ymi stanicemi. Pro vlastn´ı v´ ypoˇcet byl pouˇzit skript s názvem vzdalenost.bc, viz pˇr´ıloha C. Jak sama pˇr´ıpona napov´ıdá, jde o posloupnost pˇr´ıkaz˚ u zadávan´ ych v linuxové kalkulaˇcce bc. Nejprve je nutno zadefinovat funkce potˇrebné k v´ ypoˇctu, které kalkulaˇcka standartnˇe nezná (radians, ac, as atd. - podrobnˇeji viz dokumentace pˇr´ımo ve skriptu). Vlastn´ı v´ ypoˇcet je také novˇe definovaná funkce s názvem vzdalenost, na jej´ımˇz vstupu jsou ˇctyˇri parametry (dvakrát zemˇepisná ˇs´ıˇrka a délka, mezi kter´ ymi budeme vzdálenost poˇc´ıtat). Do v´ ysledné promˇenné s názvem os je naˇcten v´ ysledek v´ ypoˇctu vzorce na urˇcen´ı vzdálenosti na kouli pomoc´ı souˇradnic (vzdálenost se mˇeˇr´ı jako nejkratˇs´ı délka ˇca´sti kruˇznice, která dvˇe daná m´ısta na zemˇekouli spojuje). Podrobnˇejˇs´ı teorie v´ ypoˇctu vzdálenosti viz [19], vzorec a definice funkc´ı byly vˇetˇsinovˇe pˇrevzaty z fóra [20]. V´ ystupem toho skriptu je tedy vzdálenost v km (s pˇresnost´ı na tˇri desetinná m´ısta) naˇctená do promˇenné. V´ ysledek lze ovlivnit nastaven´ım velikosti referenˇcn´ı koule (v naˇsem pˇr´ıpadˇe o polomˇeru 6371,1km). Zpracován´ı soubor˚ u s namˇeˇren´ ymi daty prob´ıhalo následuj´ıc´ım zp˚ usobem: Do adresáˇre (pˇredem definovaného ve skriptu count, viz pˇr´ıloha D) byl nahrán soubor nodes.axis a dále vˇsechny v´ ysledné soubory jmeno stanice.result. Nejprve se ovˇeˇr´ı, zda právˇe zpracovávan´ y soubor je uveden v seznamu nodes.axis a pˇriˇrad´ı se mu jeho souˇradnice. V pˇr´ıpadˇe, ˇze nen´ı nalezen, skript se ukonˇc´ı s chybovou hláˇskou. V dalˇs´ım kroku se zpracovává ˇra´dek po ˇra´dku - naˇctou se hodnoty vzdáleného

34

uzlu (název, souˇradnice, RTT) a poˇslou se na vstup v´ yˇse popsaného skriptu vzdalenost.bc pro spoˇc´ıtán´ı vzájemné vzdálenosti. V´ ysledek se je zapsán do v´ ystupn´ıho souboru. T´ımto zp˚ usobem se zpracuj´ı vˇsechny ˇra´dky právˇe otevˇreného souboru a potom se smyˇcka opakuje s dalˇs´ım souborem. Na v´ ystupu skriptu count je soubor result.dup obsahuj´ıc´ı ˇra´dky ve formátu oddˇeleném stˇredn´ıky (stanice1; stanice2; RTT; vzdálenost v km): bob.cc.vt.edu;planet1.ecse.rpi.edu;18.582;839.152 Vzhledem k tomu, ˇze v pr˚ ubˇehu mˇeˇren´ı doˇslo k pingán´ı mezi uzly A −→ B a také B −→ A, po zpracován´ı skriptem count bylo nutno jeˇstˇe odstranit jednu z tˇechto hodnot jako duplicitu.

3.2.5

Odstranˇ en´ı duplicit

Pˇri vyˇrazován´ı duplicitnách záznam˚ u - tj. takov´ ych, ve kter´ ych vystupuj´ı vˇzdy tytéˇz stanice A a B - byl ponechán záznam s menˇs´ı pr˚ umˇernou hodnotou RTT. Na otázku, zda odstranit vyˇsˇs´ı ˇci niˇzˇs´ı hodnotu RTT, bylo nahl´ıˇzeno t´ımto zp˚ usobem: aˇckoliv jednotlivé uzly pingaj´ı na stejn´ y seznam ostatn´ıch (vyjma sebe sam´ ych), kter´ y je náhodnˇe prom´ıchan´ y, i pˇresto se snadno m˚ uˇze stát, ˇze se sejde nˇekolik pingaj´ıc´ıch uzl˚ u na tent´ yˇz stroj, tj. vznikne vˇetˇs´ı neˇz bˇeˇzná zátˇeˇz, která je zp˚ usobena naˇs´ım mˇeˇren´ım. Z tohoto d˚ uvodu bylo pˇristoupeno k ponechán´ı menˇs´ı hodnoty. Skript na odstranˇen´ı duplicit má název remove dup, viz pˇr´ıloha E. Na jeho vstupu je soubor, kter´ y jsme z´ıskali pomoc´ı skriptu count, s názvem result.dup. Tento soubor se dále zpracovává pomoc´ı pˇr´ıkazu awk. Sloupce s u ´daji stanice1 a stanice2 se porovnávaj´ı ve dvou smyˇckách vzájemnˇe (naˇcte se prvn´ı ˇra´dek, jeho hodnoty stanice1 a stanice2 se porovnaj´ı s ostatn´ımi ˇra´dky, pokraˇcujeme druh´ ym ˇra´dkem atd.). V pˇr´ıpadˇe nalezen´ı shody se jeˇstˇe porovnaj´ı hodnoty RTT a na v´ ystup se poˇsle ˇra´dek s niˇzˇs´ı hodnotou. V pˇr´ıpadˇe nenalezen´ı shody se poˇsle na v´ ystup pˇr´ımo porovnávan´ y ˇra´dek. V´ ysledn´ y soubor bez duplicit má název output.txt. Tento skript funguje stejn´ ym zp˚ usobem i v pˇr´ıpadˇe, ˇze na vstupu stoj´ı soubor nav´ıc su ´dajem o poˇctu hop˚ u (viz 3.2.6).

3.2.6

Traceroute

Obdobnˇe jako skripty ping nodes random a count byl vytvoˇreny tytéˇz skripty s názvem ping nodes random trace a count trace. Pracuj´ı velice podobnˇe, rozd´ıl je pouze v tom, ˇze na v´ ystupu máme nav´ıc u ´daj o poˇctu skok˚ u mezi mˇeˇren´ ymi uzly; dále se generuje dalˇs´ı samostatn´ y soubor s kompletn´ım v´ ypisem z traceroute vˇzdy s oznaˇcen´ım failed nebo passed pro konkrétn´ı vzdálenou stanici (failed v pˇr´ıpadˇe, ˇze se v traceroute vyskytuj´ı nezjiˇstˇené skoky oznaˇcené - ”*” (odpov´ıdá situaci, kdy se

35

nevrát´ı ICMP paket). Podrobnˇejˇs´ı komentáˇre spoleˇcnˇe se zdrojov´ ymi kódy jsou pˇriloˇzeny elektronicky.

3.3

Datab´ aze namˇ eˇ ren´ ych hodnot

V´ ystupem v´ yˇse popsan´ ych skript˚ u je soubor s názvem output.txt, kter´ y obsahuje vˇsechna d˚ uleˇzitá data (název zdrojového hostitele, c´ılového hostitele, geografickou vzdálenost mezi nimi a pr˚ umˇernou hodnotu RTT). T´ımto zp˚ usobem jsme tedy z´ıskali pomˇernˇe obsáhlou databázi - pˇri mˇeˇren´ı na cca 200 stanic´ıch jsme po odstranˇen´ı duplicitn´ıch (pˇr´ıpadnˇe nekompletn´ıch) záznam˚ u z´ıskali kolem 18000 unikátn´ıch záznam˚ u. Tento vzorek dat je dostateˇcnˇe velk´ y na následné zpracován´ı. V pˇr´ıloze této práce lze nalézt jak namˇeˇrená nepzracovaná data (adresáˇr mereni a v nˇem podadresáˇre pojmenované podle data mˇeˇren´ı), tak soubory stoj´ıc´ı na v´ ystupu skript˚ u (tedy result.dup a output.txt - v adresáˇri vysledky, podadresáˇre opˇet dle data mˇeˇren´ı).

36

4

´ Í NAME ˇ REN ˇ ´ ZPRACOVAN YCH HODNOT

Namˇeˇrené hodnoty byly zpracovány (tabulkov´ ym procesorem Excell) a pomoc´ı programu GNUPlot z nich sestaveny grafy. Obr.ˇc.4.1 zobrazuje namˇeˇrená data z 14.5.2008 07:45 UTC, s celkov´ ym poˇctem 20422 záznam˚ u. Z grafu jsou i bez

Obrázek 4.1: Závislot RTT na geografické vzdálenosti - vˇsechny vzorky, 14.5.2008 d˚ ukladnˇejˇs´ı anal´ yzy znatelné nˇekteré v´ yraznˇejˇs´ı oblasti a dále urˇcit´ y poˇcet r˚ uznˇe (témˇeˇr náhodnˇe) rozpt´ ylen´ ych hodnot leˇz´ıc´ıch mimo tyto oblasti. Podrobnˇejˇs´ı náhled proto ukazuje graf ˇc.4.2. Na prvn´ı pohled je z nˇej viditeln´ ych nˇekolik podstatn´ ych fakt˚ u: vˇetˇsina hodnot RTT spadá do urˇcitého pásu, kter´ y by mohl m´ıt pˇribliˇznˇe lineárn´ı závislost. Tento pás je na nˇekter´ ych m´ıstech v´ yraznˇe pˇreruˇsen, a naopak v nˇekter´ ych m´ıstech se vytváˇr´ı v´ yznamné shluky i mimo nˇej. Tyto v´ yrazné ˇcásti vˇetˇsinou odpov´ıdaj´ı komunikaci uvnitˇr kontinent˚ u nebo mezikontinentáln´ımu pˇrenosu (viz kapitola 4.3).

4.1

Zmˇ ena z´ avislosti RTT vzhledem k denn´ı dobˇ e

Souˇca´st´ı práce bylo také mj. ovˇeˇren´ı, zda se závislost RTT na geografické vzdálenosti ˇ veˇsker´ mˇen´ı v zavislosti na denn´ı dobˇe, pˇr´ıpadnˇe na dnu v t´ ydnu. Cas ych mˇeˇren´ı je uvádˇen jako UTC. Grafy ˇc. 4.3 a 4.4 zobrazuj´ı obdobné mˇeˇren´ı jako graf ˇc.4.2, pouze v jiné doby (a m´ırnˇe pozmˇenˇen´ y seznam stanic, na kter´ ych se mˇeˇrilo - vzhledem

37

Obrázek 4.2: Závislot RTT na geografické vzdálenosti - detail, 14.5.2008

Obrázek 4.3: Závislot RTT na geografické vzdálenosti - 20.4.2008

38

Obrázek 4.4: Závislot RTT na geografické vzdálenosti - 22.4.2008 datum mˇ eˇ ren´ı

rovnice pˇ r´ımky

spolehlivost R

korelaˇ cn´ı koeficient

20.4.2008 22.4.2008 14.5.2008

y = 0,0277x + 60,768 y = 0,0254x + 38,362 y = 0,0243x + 55,746

0,0522 0,0838 0,0705

0,228512781 0,289478763 0,265582378

Tabulka 4.1: Regresn´ı a korelaˇcn´ı koeficienty k tomu, ˇze nˇekteré se staly aktivn´ımi a nˇekteré naopak nedostupn´ ymi - ve vˇsech pˇr´ıpadech se vˇsak shoduje v´ıce neˇz 75% stanic). Z graf˚ u je na prvn´ı pohled zˇrejmé, ˇze denn´ı doba nemá na mˇeˇren´ı v´ yraznˇejˇs´ı vliv, v´ ysledné grafy jsou prakticky stejné (odliˇsnost m˚ uˇze b´ yt zp˚ usobena právˇe zbylou ˇctvrtinou host˚ u, která se mˇenila). Pro srovnán´ı byla urˇcena lineárn´ı regrese (pomoc´ı aplikace Excell, metodou nejmenˇs´ıch ˇctverc˚ u). Spoleˇcnˇe s korelaˇcn´ım koeficientem pro jednotlivé datumy je vidˇet v tabulce ˇc.4.1. Vzhledem k malé spolehlivosti v´ ypoˇctu (viz koeficient R) jsou tato data uvádˇena sp´ıˇse orientaˇcnˇe. Z namˇeˇren´ ych dat byl vybrán vzorek ze dvou dn˚ u (14.5.2008 a 20.4.2008) v detailu na komunikaci mezi Evropou a Asi´ı. Z tohoto vzorku jeˇstˇe byla odstranˇena ta mˇeˇren´ı, která nebyla obsaˇzena v obou dvou databáz´ıch (tzn. v´ ysledkem je vˇzdy jedna vzdálenost se dvˇemi hodnotami RTT, pro dvˇe r˚ uzná mˇeˇren´ı). V´ ysledek zobrazuje graf ˇc.4.5. Aˇckoliv v celkovém pohledu se grafy mohou zdát podobné (barvy se pˇrekr´ yvaj´ı), jisté odliˇsnosti se daj´ı vysledovat. Napˇr. vyznaˇcená oblast v modré elipse: jedná se stanice, které vykazuj´ı témˇeˇr totoˇzné posunut´ı (korelaˇcn´ı koeficient

39

Obrázek 4.5: Porovnán´ı závislosti RTT v r˚ uznou dobu - 20.4.2008, 14.5.2008 mezi ˇcervenou a ˇcernou mnoˇzinou v elipse vycház´ı cca 0,97). Pravdˇepodobnˇe se tedy jedná o oblast se stejnou topologi´ı, ve které doˇslo k nˇejaké zmˇenˇe (vyˇsˇs´ı/niˇzˇs´ı zat´ıˇzen´ı centráln´ıch router˚ u, u ´prava routován´ı atd.) Korelaˇcn´ı koeficient pro celou oblast Asie - Evropa je vˇsak 0,35, tzn. celá oblast spoleˇcné znaky posunut´ı nevykazuje.

4.2

D´ elka mˇ eˇ ren´ı

Obdobnˇe jako denn´ı doba, ani poˇcet vyslan´ ych (pˇrijat´ ych) paket˚ u v´ yraznˇeji neovlivˇ nuje pr˚ ubˇeh závislosti RTT na vzdálenosti. Pro ovˇeˇren´ı tohoto faktu byl proveden test mˇeˇren´ı RTT v rámci nˇekolika stanic na r˚ uzn´ ych kontinentech (Evropa, Asie, severn´ı a jiˇzn´ı Amerika). Na tyto uzly byl postupnˇe vys´ılán r˚ uzn´ y poˇcet paket˚ u od 3 aˇz po 2000 (odpov´ıdá pˇribliˇznˇe ˇctyˇrhodinovému mˇeˇren´ı). V´ ysledky tohoto testu ukazuje tabulka ˇc.4.2 a 4.3. Namˇeˇrené pr˚ umˇerné hodnoty jednotliv´ ych stanic se od sebe v´ yraznˇe neliˇs´ı - vzájemná korelace jednotliv´ ych sloupeˇck˚ u je ve vˇsech pˇr´ıpadech vˇetˇs´ı neˇz 94%. Z toho vypl´ yvá, ˇze 3 vyslané/pˇrijatˇe ICMP pakety jsou pro mˇeˇren´ı dostateˇcné. Nutno vˇsak podotknout, ˇze mˇeˇren´ı závislosti RTT na geografické vzdálenosti je vhodné po urˇcitém ˇcasovém obdob´ı opakovat, a to z duvodu ovˇeˇren´ı platnosti dat. Topologie s´ıtˇe se neustále vyv´ıj´ı, pˇrib´ yvá vysokorychlostn´ı optick´ ych spoj˚ u apod.

40

vzd´ alenost [km]

3 pakety [ms]

10 paket˚ u [ms]

20 paket˚ u [ms]

569,467 1603,444 1801,51 2220,87 3380,404 3945,239 5090,125 6498,663 6739,522 7335,219 7513,267 7855,952 8114,857 8276,357 8446,365 8806,548 8884,216 9015,553 9297,214 9846,301 10360,23 10632,184 11196,997 11545,679 11816,399 13363,292 14431,346 18949,668

31,797 69,622 64,587 100,408 118,091 145,935 158,133 120,285 111,763 335,143 159,92 147,531 162,11 142,956 222,198 299,458 227,934 235,278 330,848 380,499 261,523 197,609 196,764 326,225 335,965 305,398 490,353

31,402 68,958 64,208 100,249 117,463 139,345 157,053 120,142 111,66 334,986 159,836 147,471 150,966 142,805 374,856 299,25 224,414 386,443 330,266 380,096 260,413 197,508 196,877 311,22 297,292 333,342 283,814 564,314

31,435 69,139 64,236 100,131 118,27 147,707 157,02 120,257 111,621 335,118 162,688 147,413 158,833 142,741 375,808 299,325 224,55 387,813 330,256 380,116 260,999 202,052 196,773 312,651 297,579 333,682 283,634 565,051

Tabulka 4.2: Závislost RTT na poˇctu odeslan´ ych paket˚ u pro r˚ uzné vzdálenosti - I

41

vzd´ alenost [km]

200 paket˚ u [ms]

1000 paket˚ u [ms]

2000 paket˚ u [ms]

569,467 1603,444 1801,51 2220,87 3380,404 3945,239 5090,125 6498,663 6739,522 7335,219 7513,267 7855,952 8114,857 8276,357 8446,365 8806,548 8884,216 9015,553 9297,214 9846,301 10360,23 10632,184 11196,997 11545,679 11816,399 13363,292 14431,346 18949,668

34,06 69,021 64,306 100,321 117,919 144,775 156,924 124,442 111,596 335,237 165,826 147,538 155,988 142,729 376,233 299,323 224,777 388,41 330,436 380,149 261,299 200,21 196,88 312,122 297,05 333,528 283,333 563,54

35,631 69,167 64,509 100,391 118,078 146,379 157,498 124,867 111,717 335,202 167,461 147,676 155,583 143,051 375,841 299,257 225,708 389,891 330,472 380,28 261,759 202,779 196,89 312,52 333,817 283,98 564,189

36,199 69,711 64,323 101,014 118,035 152,096 160,304 124,74 111,679 335,482 172,677 148,212 156,591 142,828 215,727 299,367 316,755 241,278 330,387 380,408 292,079 210,513 196,942 313,236 333,941 305,388 486,246

Tabulka 4.3: Závislost RTT na poˇctu odeslan´ ych paket˚ u pro r˚ uzné vzdálenosti - II

42

4.3

Anal´ yza referenˇ cn´ıho grafu

Graf ˇc.4.6 byl postupnˇe rozdˇelen na jednotlivé ˇcasti, barevnˇe odliˇseny. Vzhledem k tomu, ˇze vˇetˇsina host˚ u v s´ıti PlanetLab je soustˇredˇena v Evropˇe a Americe, dle pˇredpokladu prvn´ı ˇca´st grafu odpov´ıdá vnitrokontinentáln´ı komunikaci v Evropˇe a Americe (samozˇrejmˇe vzhledem k mal´ ym vzdálenostem sem patˇr´ı drtivá vˇetˇsina intrakontinentáln´ıch mˇeˇren´ı). Konkrétnˇe tedy modrá barva odpov´ıdá komunikaci uvnitˇr Evropy, zelená uvnitˇr Ameriky, ˇzlutá komunikaci mezi Amerikou a Evropou, ˇcerná mezi Evropou a jiˇzn´ı Amerikou, ˇsedá Asie - Evropa, fialová Asie - Amerika, atd. (jednotlivé barvy se mohou pˇrekr´ yvat, jsou vrstvené na sebe). Vymezen´ı jednotliv´ ych kontinent˚ u bylo provedeno na základˇe zemˇepisn´ ych souˇradnic. Mezera mezi prvn´ı a druhou ˇca´st´ı odpov´ıdá vzdálenosti, která nen´ı mezi uzly PlanetLabu v´ yraznˇeji zastoupena. V ideáln´ım pˇr´ıpadˇe (pokud bychom neuvaˇzovali vˇsechny faktory ovlivˇ nuj´ıc´ı mˇeˇren´ı RTT, viz kapitola 1.3.2), bychom mohli pˇredpokládat, ˇze závislost RTT na geografické vzdálenosti bude lineárn´ı - signál se ˇs´ıˇr´ı konstantn´ı rychlost´ı. Pro intrakontinentáln´ı mˇeˇren´ı RTT spadá vˇetˇsina záznam˚ u do oblasti vymezené tˇemito pˇr´ımkami: y1 = 0, 017333x a y2 = 0, 017333x + 40

(4.1)

Pˇr´ımky jsou rovnobˇeˇzné a vymezuj´ı interval o ˇs´ıˇrce 40ms (zat´ım se nepodaˇrilo ovˇeˇrit, proˇc je to pˇribliˇznˇe právˇe tato hodnota). Konkrétné pro geografické vzdálenosti do 4673km do tohoto intervalu spadá v´ıce neˇz 75% hodnot (pro mˇeˇren´ı z 14.5.2008 je to 78,8%, tato hodnota byla spoˇc´ıtána pomoc´ı eplikace Excell; viz obr.ˇc.4.7). Lze tedy odhadnout, ˇze pˇr´ımka y1 = 0, 017333x pˇribliˇznˇe tvoˇr´ı hranici, pod kterou se drtivá vˇetˇsina hodnot RTT pro danou vzdálenost nedostane (pro ovˇeˇren´ı, zda se tato pˇr´ımka bliˇz´ı fyzikáln´ı hranici, by bylo zapotˇreb´ı provést mˇeˇren´ı i v jin´ ych s´ıt´ıch). Pro cel´ y graf vˇsak interval rozptylu nen´ı moˇzné v rozumné m´ıˇre urˇcit - bud’ by byl pˇr´ıliˇs ˇsirok´ y a tud´ıˇz nepouˇziteln´ y, a nebo by do nˇej spadalo naopak pˇr´ıliˇs málo hodnot. Lze ho vˇsak urˇcit pro jednotlivé u ´seky grafu, které jsou barevnˇe oddˇeleny, podle toho, která oblast nás zaj´ıma (jedná se o jak´ ysi kompromis: ˇc´ım vˇetˇs´ı bude tento interval rozptylu, t´ım v´ıce hodnot do nˇej bude spadat, ale t´ım ménˇe bude pouˇziteln´ y).

43

44 Obrázek 4.6: Závislost RTT na geografické vzdálenosti - barevnˇe oddˇelˇené skupiny, 14.5.2008

Obrázek 4.7: Oblast nejvˇetˇs´ı koncentrace RTT, 14.5.2008

4.4

Anal´ yza evropsk´ ych uzl˚ u

Graf ˇc.4.8 zobrazuje pohled na komunikaci v rámci Evropy (celkem 2790 mˇeˇren´ı). Korelaˇcn´ı koeficient má v pˇr´ıpadˇe pouze evropsk´ ych uzl˚ u hodnotu c = 0,162088199, pˇr´ımka metodou lineárn´ı regrese pak pˇredpis y = 0,1094x + 11,404 se spolehlivost´ı R = 0,0263.

4.5

Anal´ yza americk´ ych uzl˚ u

Vzhledem k faktu, ˇze vˇetˇs´ı ˇca´st stanic se nacház´ı v Severn´ı Americe ve dvou seskupen´ıch - na v´ ychodn´ım a západn´ım pobˇreˇz´ı, z grafu ˇc.4.9 je vidˇet, ˇze hustota mˇeˇren´ ych hodnot je nejvˇetˇs´ı u mal´ ych geografick´ ych vzdálenost´ı, a dále docház´ı k jej´ımu m´ırnému zhuˇstˇen´ı naopak u vˇetˇs´ıch vzdálenost´ı (coˇz odpov´ıdá mˇeˇren´ı RTT mezi pobˇreˇz´ımi). Pˇri porovnán´ı s grafem Evropy je vidˇet, ˇze tam jsou jednotlivé uzly rozloˇzeny v´ıce rovnomˇernˇe (s nar˚ ustaj´ıc´ı vzdálenost´ı klesá hustota záznam˚ u).

4.6

Zhodnocen´ı namˇ eˇ ren´ ych v´ ysledk˚ u

Pomoc´ı vytvoˇren´ ych nástroj˚ u se podaˇril nashromáˇzdit dostateˇcnˇe velk´ y vzorek dat, aby bylo moˇzno z jejich anal´ yzy udˇelat nˇekteré konkrétn´ı závˇery. Aˇckoliv pro cel´ y

45

Obrázek 4.8: Závislost RTT na geografické vzdálenosti - Evropa, 14.5.2008

Obrázek 4.9: Závislost RTT na geografické vzdálenosti - Amerika, 14.5.2008

46

soubor mˇeˇren´ı nejsou korelaˇcn´ı koeficienty zcela pˇr´ıznivé, lze vymezit nˇekteré oblasti, pro které se závislost RTT na geografické vzdálenosti jev´ı jako bl´ızká lineárn´ı závislosti (interkontinentáln´ı mˇeˇren´ı), naopak nˇekteré oblasti jsou témˇeˇr kruhovˇe symetrické (komunikace mezi Asi´ı a Evropou). Slabinou tohoto mˇeˇren´ı m˚ uˇze b´ yt fakt, ˇze prob´ıhá ve specifické, témˇeˇr v´ yhradnˇe akademické s´ıti PlanetLab. Jednou z moˇznost´ı, jak z´ıskat nezávislá data z jin´ ych s´ıt´ı pro mˇeˇren´ı, je vyuˇzit´ı sluˇzby Test Traffic Measurements (dále jen TTM) organizace RIPE (Reseaux IP Europeens, www.ripe.net). RIPE je nezisková organizace, která mj. ˇr´ıd´ı pˇridˇelován´ı blok˚ u IP adres v Evropˇe, jej´ı zábˇer ˇcinnost´ı je vˇsak ve skuteˇcnosti mnohem ˇsirˇs´ı. Jedn´ım z bˇeˇz´ıc´ıch projekt˚ u je právˇe TTM. Tato sluˇzba dokáˇze mˇeˇrit kl´ıˇcové parametry pˇripojen´ı mezi r˚ uzn´ ymi uzly v Internetu (slouˇz´ı tedy jako kontinuáln´ı monitoring). Pro svá mˇeˇren´ı pouˇz´ıvá zaˇr´ızen´ı vyhrazené pouze na tuto ˇcinnost, které generuje malé mnoˇzstv´ı datového provozu (tzn. zat´ıˇzen´ı s´ıtˇe nezaznamená v´ yraznˇejˇs´ı nár˚ ust). Samotné zˇr´ızen´ı se skládá z poˇc´ıtaˇce pˇripojeného na Internet a dále z GPS modulu, jeho instalace je velmi jednoduchá. Namˇeˇrená data z jednotliv´ ych box˚ u rozm´ıstˇen´ ych po svˇetˇe dle zákazn´ık˚ u jsou k dispozici na www stránkách RIPE, podléhaj´ı vˇsak licenˇcn´ım podm´ınkám a nelze je pouˇz´ıt bez souhlasu autor˚ u. Ten se bohuˇzel bˇehˇem ˇreˇsen´ı této práce nepodaˇrilo zajistit, nicménˇe komunikace byla navázána a v budoucnu by pˇricházela v u ´vahu.

47

5

´ ER ˇ ZAV

Jak bylo naznaˇceno jiˇz v u ´vodu, hlavn´ım c´ılem této práce bylo vytvoˇren´ı nástroj˚ u pro mˇeˇren´ı a zpracován´ı parametru latence v s´ıti a s jejich pomoc´ı provést konkrétn´ı mˇeˇren´ı ovˇeˇruj´ıc´ı fakt, zda hodnota RTT nˇejak´ ym zp˚ usobem závis´ı na skuteˇcné geografické vzdálenosti. Na základˇe podrobnˇejˇs´ıho seznámen´ı se se sluˇzebn´ım protokolem ICMP a nástroji pro vytvoˇren´ı soket˚ u byly vytvoˇreny zdrojové kódy pro mˇeˇren´ı RTT v programovac´ım jazyku C a dále skripty v pˇr´ıkazovém interpretu Bash pro zpracován´ı vˇetˇs´ıho mnoˇzstv´ı namˇeˇren´ ychy dat. Na vzorku mˇeˇren´ı byla ovˇeˇrena jejich plná funkˇcnost. Skripty i zdrojov´ y kód je moˇzno nadále optimalizovat, pˇr´ıpadnˇe doplˇ novat o nové potˇrebné funkce. Interpretace namˇeˇren´ ych hodnot ukázala, ˇze v celkovém pohledu v´ ysledky prakticky nejsou závislé na denn´ı dobˇe, nicménˇe nˇekteré oblasti mohou jevit spoleˇcné charakteristiky a je zapotˇreb´ı d˚ ukladnˇejˇs´ı anal´ yzy. Sp´ıˇse neˇz rozbor celého souboru dat se tedy jev´ı b´ yt vhodnˇejˇs´ı posuzován´ı jednotliv´ ych (geografick´ ych) ˇca´st´ı zvláˇst’ - v závislosti na topologii s´ıtˇe maj´ı konkrétn´ı vlastnosti, které nejsou v celkovém pohledu tolik zˇretelné. Mˇeˇren´ı samotné prokázalo, ˇze závislost RTT na geografické vzdálenosti neni ˇcistˇe nahodilá, a proto má smysl se j´ı nadále zab´ yvat (podrobnˇejˇs´ı anal´ yzou namˇeˇren´ ych hodnot, pˇr´ıpadnˇe nov´ ymi mˇeˇren´ımi). V kaˇzdém pˇr´ıpadˇe by vˇsak bylo vhodné provést vˇetˇs´ı objem mˇeˇren´ı také v jin´ ych s´ıt´ıch, neˇz v dosud provádˇené s´ıti PlanetLab, aby bylo moˇzné vylouˇcit ovlivnˇen´ı v´ ysledk˚ u charakteristick´ ymi vlastnostmi této specifické s´ıtˇe. V´ ysledky této práce mohou b´ yt pouˇzité napˇr. jako podklad pro metody predikce pozice stanic v s´ıt´ı, obzvláˇst’ GNP.

48

REFERENCE [1] Stevens, W.R. UNIX Network Programming Volume 1, Second edition. USA: Prentice Hall PTR, 1998. [2] Francis P., Jamin S., Jin Ch., Jin Y., Raz D., Shavitt Y., Zhang L. IDMaps: A Global Internet Host Distance Estimation Service EEE/ACM Trans. on Networking, Oct. 2001. [3] Govindan R. and Tangmunarunkit H. ”Heuristics for internet map discovery” in Proc. IEEE INFOCOM, vol. 3, 2000, pp.1371-1380. [4] Vazirani, V. Approximation Methods. New York. Springer-Verlag, 1999. [5] Guyton, J.D. and Schwartz, M.F. ”‘Locating nearby copies of replicated internet servers”’. in Proc. ACM SIGCOM, Aug. 1995, pp. 288-298. [6] Srinivasan Seshan, Mark Stemm, and Randy Katz ”Shared passive network performance discovery”’. In Proceedings of the USENIX Symposium on Internet Technologies and Systems, 1997. [7] Radim Burget, Dan Komosny, Vit Novotny ”Integration of Host Position Prediction into Hierarchical Aggregation” icn, pp. 740-745, Seventh International Conference on Networking (icn 2008), 2008 [8] Eugene Ng, T.S. and Hui Zhang ”Towards Global Network Positioning”. Extended Abstract, ACM SIGCOMM Internet Measurement Workshop 2001, San Francisco, CA, November 2001 [9] Hochbaum, Dorit S., Shmoys, David B. ”A best possible heuristic for the kCentre problem”. University of California, Berkley. [10] R. Cox, F. Dabek, F. Kaashoek, J. Li, and R. Morris ”Practical Distributed Network Coordinates”. In Proceedings of the ACM HotNets Workshop, November 2003 [11] Herold, Helmut awk & sed - Pˇr´ıruˇcka pro dávkové zpracován´ı textu. Computer Press, 2004. [12] IP2Location.com Urˇcen´ı zemˇepisné polohy pomoc´ı reverzn´ıho záznamu Dostupné z URL: [13] whatismyipaddress.com Grafický traceroute Dostupné z URL:

49

[14] shadegrowncode.com/ Funkce pro random shuffle, Bash Dostupné z URL: [15] wikibooks.org/ Informace o shellu Bash Dostupné z URL: [16] root.cz Tutoriály programován´ı C++ Dostupné z URL: [17] cmu.edu REMOS Project Dostupné z URL: [18] planet-lab.org S´ıt’ PlanetLab Dostupné z URL: [19] rvp.cz Mˇeˇren´ı vzdálenosti na glóbusu Dostupné z URL: [20] mathforum.com Výpoˇcet vzdálenosti ze zemˇepisných souˇradnic Dostupné z URL: [21] ripe.net Organizace RIPE Dostupné z URL: [22] army.mil Historie pingu Dostupné z URL: [23] cs.wikipedia.org Wikipedia Dostupné z URL:

50

˚ VELICIN ˇ SEZNAM SYMBOLU, A ZKRATEK RTT round-trip (delay) time je ˇcas, za kter´ y informace (obvykle paket) doraz´ı od zdroje k c´ıli a zpˇet ICMP Internet Control Message Protocol - jeho u ´ˇcelem je informován´ı zdrojového uzlu o chybách a nestandartn´ıch situac´ıch pˇri pˇrenosu TTL time to live, znamená dobu ˇzivota IP paketu MTU Maximum transmission unit, jedná se o oznaˇcen´ı maximáln´ı velikosti IP paketu, kter´ y je moˇzné pˇrenést z jednoho s´ıt’ového zaˇr´ızen´ı na druhé; obvyklá hodnota MTU v pˇr´ıpadˇe Ethernetu je 1500 bajt˚ u PING Packet InterNet Grouper slouˇz´ı k detekci ˇcasu odezvy s´ıt’ového zaˇr´ızen´ı v IP s´ıti a patˇr´ı mezi standardn´ı nástroje pro správu s´ıtˇe; vyuˇz´ıvá ICMP TCP/IP transmition control protocol/Internet protocol, sada protokol˚ u pro komunikaci v poˇc´ıtaˇcové s´ıti UDP User Datagram Protocol je nespolehliv´ y nespojov´ y protokol nezaruˇcuje, zda se pˇrenáˇsen´ y datagram neztrat´ı, zda se nezmˇen´ı poˇrad´ı doruˇcen´ ych datagram˚ u nebo zda se nˇekter´ y datagram nedoruˇc´ı v´ıcekrát SNMP Simple Network Management Protocol slouˇz´ı potˇrebám nástroj˚ u správy s´ıt´ı FTP File Transfer Protocol, protokol aplikaˇcn´ı vrstvy z rodiny TCP/IP urˇcen´ y pro pˇrenos soubor˚ u mezi poˇc´ıtaˇci GNP Global Network Positioning, metoda odhadu pozice stanice v s´ıti RIPE Réseaux IP Européens (RIPE), fórum pro zájemce o technick´ y rozvoj Internetu: jeho c´ılem komunity je zajiˇstˇen´ı koordinace správy, u ´drˇzby a rozvoje Internetu AS

Autonomn´ı systém, mnoˇzina IP s´ıt´ı a router˚ u pod spoleˇcnou technickou správou, která reprezentuje v˚ uˇci Internetu spoleˇcnou routovac´ı politiku

AP

Adresn´ı prefix, definovan´ y jako po sobˇe jdouc´ı (následn´ y) rozsah IP adres, pˇriˇcemˇz vzdálenosti vˇsech host˚ u s IP adresami z toho AP jsou v˚ uˇci zbytku internetu ekvidistatn´ı

51

ˇ ÍLOH SEZNAM PR A Zdrojov´ y k´ od aplikace PING

53

B Skript ping nodes random

57

C Funkce vzdalenost.bc pro poˇ c´ıt´ an´ı geografick´ e vzd´ alenosti

59

D Skript Count

60

E Skript remove dup

62

F Skript prepare nodes

63

52

A #include #include #include #include #include #include #include #include #include #include #include #include #include

´ KOD ´ APLIKACE PING ZDROJOVY <sys/socket.h> <sys/types.h> <arpa/inet.h> <stdlib.h> <string.h> <sys/time.h> <signal.h> <stdio.h>

#define BUFSIZE 1024

static int G_break = 0; /* funkce checksum byla opsana z prislucnych RFC dokumentu */ unsigned short checksum(unsigned char *addr, int count) { register long sum = 0; while( count > 1 ) { /* This is the inner loop */ sum += * (unsigned short *) addr; addr+=2; count -= 2; } /* Add left-over byte, if any */ if( count > 0 ) sum += * (unsigned char *) addr; /* Fold 32-bit sum to 16 bits */ while (sum>>16 != 0) sum = (sum & 0xffff) + (sum >> 16); return ~sum; } // signal handler void catchsignal (int sig) { if (sig == SIGINT) { G_break = 1; } } int main(int argc, char *argv[]) { size_t size; hostent *host; icmphdr *icmp, *icmpRecv; iphdr *ip; int sock, length;

53

unsigned int ttl = 255; sockaddr_in sendSockAddr, receiveSockAddr; char buffer[BUFSIZE]; fd_set mySet; timeval tv; char *addrString; unsigned short int pid = getpid(), p; int c = 0; int s = socket(PF_INET, SOCK_RAW, IPPROTO_ICMP); int x; double z = 0;

/* deklarace promennych pro statistiku */ double y = 0; double max = 0; double min = 1000000; double suma = 0; int counter = 0; if (argc != 2) { printf("Syntax:\n\t%s address\n",argv[0]); return -1; } /* zjistime info o vzdalenem pocitaci */ if ((host = gethostbyname(argv[1])) == NULL) { printf("Wrong address\n"); return -1; } /* vytvorime socket*/ if((sock = socket(PF_INET, SOCK_RAW, IPPROTO_ICMP)) == -1) { printf("Can’t create socket\n"); return -1; } /* if (s == -1) { perror("Selhalo vytvoreni socketu."); exit(1); } printf("proslo to, s=%d\n", s);*/ setsockopt(sock, SOL_IP, IP_TTL, (const char *)&ttl, sizeof(ttl)); /* naplneni polozek ICMP hlavicky */ icmp = (icmphdr *)malloc(sizeof(icmphdr)); if (icmp == NULL) { printf("Not enought memory\n"); return -1; } icmp->type = ICMP_ECHO; icmp->code = 0; icmp->un.echo.id = pid; /* pripravime sendto */ sendSockAddr.sin_family = AF_INET; sendSockAddr.sin_port = 0;

54

memcpy(&(sendSockAddr.sin_addr), host->h_addr, host->h_length); // install signal handler for CTRL+C signal(SIGINT, catchsignal); for (p = 1; p <= 20000; p++) { if (G_break == 1) break; struct timeval out, in; icmp->checksum = 0; icmp->un.echo.sequence = p; icmp->checksum = checksum((unsigned char *)icmp, sizeof(icmphdr)); sendto(sock, (char *)icmp, sizeof(icmphdr), 0, (sockaddr *)&sendSockAddr, sizeof(sockaddr)); gettimeofday(&out, NULL); tv.tv_sec = 30; tv.tv_usec = 0; do { FD_ZERO(&mySet); FD_SET(sock, &mySet); if (select(sock + 1, &mySet, NULL, NULL, &tv) < 0) { printf("Select failed\n"); break; } if (FD_ISSET(sock, &mySet)) { size = sizeof(sockaddr_in); if ((length = recvfrom(sock, buffer, BUFSIZE, 0, (sockaddr *)&receiveSockAddr, &size)) == -1) { printf("Receiving data error\n"); } /* prisel blok dat: IP hlavicka + ICMP hlavicka. */ gettimeofday(&in, NULL); ip = (iphdr *) buffer; icmpRecv = (icmphdr *) (buffer + ip->ihl * 4); if ((icmpRecv->un.echo.id == pid) && (icmpRecv->type == ICMP_ECHOREPLY) && (icmpRecv->un.echo.sequence == p)) { addrString = strdup(inet_ntoa(receiveSockAddr.sin_addr)); host = gethostbyaddr(&receiveSockAddr.sin_addr, 4, AF_INET); printf("%d bytes from %s (%s)", length, (host == NULL? "?" : host->h_name), addrString); printf(": icmp_seq=%d ", icmpRecv->un.echo.sequence); y = 1e3*(in.tv_sec - out.tv_sec + 1e-6*(in.tv_usec - out.tv_usec)); z = z + y; max = (y > max)?y:max; min = (y < min)?y:min; suma+=y; printf("ttl=%d, rtt=%.3f ms\n", (int)ip->ttl, 1e3 * (in.tv_sec - out.tv_sec + 1e-6 * (in.tv_usec - out.tv_usec))); c++; free(addrString); } }

55

else { printf("- time exceeded -\n"); break; } } while (!((icmpRecv->un.echo.id == pid) && (icmpRecv->type == ICMP_ECHOREPLY) && (icmpRecv->un.echo.sequence == p))); sleep(1); } x = 100*(p-c-1)/(p-1); close(sock); printf("-- ping statistics for %s --\n", argv[1]); printf("%d packets transmitted, %d received, %d %% packet loss, total time was %f ms.\n", (p-1), c, x, z); printf("Statistics rtt: max/min/avg is %lf/%lf/%lf\n",max,min,suma/c); if (icmp != NULL) { free(icmp); icmp = NULL; } return 0; }

56

B

SKRIPT PING NODES RANDOM

#!/bin/bash # pokud je pri spusteny zadan argument "-show", tak vypise vystup i na obrazovku MY_HOST=‘hostname‘ RESULT=$MY_HOST.result INPUT="nodes.txt" INPUTR="nodes.rnd" TIMEOUT="-W 5" REPLACE1="/" REPLACE2=";" COUNT=1

#nacteni hostname do promenne #definice vystupniho soubboru #definice vstupnich souboru

if [ -f $RESULT ] then rm -f $RESULT fi

#pokud jiz existuje soubor s vysledky, smaze ho

#definice timeoutu pro ping #pomocne promenne #pocitadlo

if [ ! -e $INPUT ] #test zda mame vstupni soubor, pokud ne, tak se ukonci then echo "Input file: $INPUT not found!" exit 1 fi #funkce randomShuffle prevzata z http://www.shadegrowncode.com/ function randomShuffle { typeset -a elements typeset length=0 while read line do elements[$length]=$line length=$(($length + 1)) done typeset firstN=${1:-$length} if [ $firstN -gt $length ] then firstN=$length fi for ((i=0; $i < $firstN; i++)) do randPos=$(($RANDOM % ($length - $i) )) printf "%s\n" "${elements[$randPos]}" elements[$randPos]=${elements[$length - $i - 1]} done } #randomizace vstupniho souboru - vysledek zapsan do pomocneho souboru cat $INPUT | randomShuffle > $INPUTR #test zda byl vytvoren pomocny soubor, pokud ne, tak se ukonci if [ ! -e $INPUTR ] then echo "Input randomized file: $INPUTR not found!" exit 2 fi #hlavni smycka exec < $INPUTR

57

while read REMOTE_HOSTS; do #cteme zaznamy po radcich REMOTE_HOST=${REMOTE_HOSTS%%;*} #zapis do promenne if [ $REMOTE_HOST != $MY_HOST ] #test zda vzdaleny host nejsme my then #ping s nastavenymi parametry; zapis do promenne PING #pouze 4. sloupec (RTT - min/avg/max/mdev hodnoty) PING=‘ping $TIMEOUT -q -c 10 -n $REMOTE_HOST | gawk ’END {print $4}’‘ TIME=‘date -u‘ #uloz aktualni datum a cas UTC do promenne if [ "$PING" ] #test zda promenna obsahuje data then #vystup do souboru - vzdaleny host, RTT - AVRG, datum echo "$REMOTE_HOSTS;${PING//$REPLACE1/$REPLACE2};$TIME" >>$RESULT fi if [ -n "$1" ] #test zda byl zadan argument then if [ $1 == "-show" ] #test zda argument = "-show" then echo "Radek: $COUNT" echo "$REMOTE_HOSTS;${PING//$REPLACE1/$REPLACE2};$TIME" ((COUNT += 1)) fi fi else INSIDE=1 #pokud vzdalena stanice jsme my, tak do promenne zapis 1 fi done echo "$INSIDE" >>$RESULT

#kontrolni zapis na konec souboru zda jsme byli v seznamu

if [ -f $INPUTR ] then rm -f $INPUTR fi

#smaze pomocny soubor

58

C

FUNKCE VZDALENOST.BC PRO ˇ ÍTAN ´ Í GEOGRAFICKE ´ VZDALENOSTI ´ POC #!/usr/bin/bc -l scale=100; define pi(){return(a(1)*4)}

; pi

= pi()

#prepocet stupnu na radiany: define radians(x) { return(x*(pi/180)) } #definice funkce arccos: define ac(x) { return 2*a(1)-as(x) } #definice funkce arcsin: define as(x) { if(abs(x)==1)return(2*a(1)*x)else return( a(x/sqrt(1-x^2)) ) } #definice funkce absolutni hodnoty: define abs(x) { if(x<0)return(-x)else return(x) } #zaokrouhleni na 3 desetinna mista: define int(x) { auto os;os=scale;scale=3;x/=1;scale=os;return(x) } #vlastni vzorec pro vypocet: define vzdalenost(x,y,m,n) { auto os; x=radians(x); y=radians(y); m=radians(m); n=radians(n); os=(ac(c(x)*c(y)*c(m)*c(n) + c(x)*s(y)*c(m)*s(n) + s(x)*s(m)) * 6371.1) return (int(os)) }

59

D

SKRIPT COUNT

#!/bin/bash INPUT_DIR="/home/jarosovl/planetlab/skripty/result/" INPUT_AXIS="/home/jarosovl/planetlab/skripty/nodes.axis" OUTPUT_FILE="$INPUT_DIR/result.dup" VZDALENOST_BC="/home/jarosovl/planetlab/skripty/vzdalenost.bc" #pokud jiz existuje soubor s vysledkem, smaze ho if [ -f $OUTPUT_FILE ] then rm -f $OUTPUT_FILE fi cd $INPUT_DIR #inicializace promennych i=1 FILE_COUNT=0 date #ulozi do promenne aktualni delku behu skriptu merime=$SECONDS #spocita pocet souboru s priponou .result for soubor in *.result; do test -f "$soubor" && ((FILE_COUNT +=1)) done #zacatek hlavni smycky for soubor in *.result; do #opakuj pro vsechny soubory s priponou .result: if [ -f "$soubor" ]; then #test, zda se opravdu jedna o soubor MYHOST=${soubor/%.result/} #do MYHOST nacti nazev souboru pred priponou radku_host=‘wc -l < $INPUT_DIR$soubor‘ #uloz do promenne pocet radku souboru LAT=0 LON=0 eval ‘gawk -F ";" -v mhost=$MYHOST ’{ if ($1 == mhost) print "LAT="$2"\n" "LON="$3"\n" }’ $INPUT_AXIS‘ #pozn.c.1 - viz dole if [ "$LAT" == "0" ] && [ "$LON" == "0" ] #jestlize nenajde souradnice aktualne #zpracovavaneho hosta, ukonci se then echo "!! ERROR - AXIS for HOST: $MYHOST not found !!" exit 1 fi for ((j=1; j <= $radku_host ; j++)) #cteme radek po radku do eval ‘gawk -F ";" -v line=$j ’FNR==line {print "REMOTEHOST="$1"\n" "LATR="$2"\n" "LONR="$3"\n" "AVRG="$5"\n"}’ $INPUT_DIR$soubor‘ #pozn.c.2 if [ $AVRG ] #test, zda se zmeril RTT then vzdalenost=‘echo "vzdalenost($LAT,$LON,$LATR,$LONR)" | $VZDALENOST_BC‘ #pozn.c.3 - viz dole echo "$MYHOST;$REMOTEHOST;$AVRG;$vzdalenost" >>$OUTPUT_FILE #vystup jde do souboru i=$((i + 1)) #spocita zazanmy fi done ((FILE_COUNT -=1)) #odecte hotovy soubor echo "$MYHOST - hotovo zaznamu: $i - zbyva souboru $FILE_COUNT - time:

60

$((SECONDS-merime))" merime=$SECONDS

#vypis na obrazovku #nulovani

fi done date echo "Done - celkem zaznamu: $i" #pozn.c.1 - na vstup prikazu gawk predame promennou MYHOST; ten ji hleda v souboru nodes.axis a pokud ho najde, do promennych LAT a LON vrati hodnoty #pozn.c.2 - na vstup prikazu gawk predame promennou s cislem radku ($j); ten vraci promenne REMOTEHOST, LATR, LONR, AVRG #pozn.c.3 - pomoci echa posilame vzdalenost do externiho skriptu vzdalenost.bc, vysledek se ulozi do promenne $vzdalenost

61

E

SKRIPT REMOVE DUP

#!/bin/bash INPUT_DIR="/home/jarosovl/planetlab/skripty" INPUT_FILE="$INPUT_DIR/result/result.dup" OUTPUT_FILE="$INPUT_DIR/output.txt" #pokud jiz existuje soubor s vysledkem, smaze ho if [ -f $OUTPUT_FILE ] then rm -f $OUTPUT_FILE fi #testovani shodnych zaznamu hostnamu v ruznych radcich; v pripade nalezeni shody #se porovnava RTT (avg) a na vystup je posilan radek s mensi hodnotou. V pripade #nenalezeni shody se radek na vystup posila rovnou awk -F ";" ’{ host1[NR] = $1 ; host2[NR] = $2 ; avrg[NR] = $3 ; radek[NR] = $0} END { if (NR > 1) { for (i=1; i<=NR; i=i+1) { test=0 for (j=NR; i<=j; j=j-1) { if (host1[i] == host2[j] && host1[j] == host2[i]) { if (avrg[i] > avrg[j]) { print radek[j] test=1 radek[j]="" } else { print radek[i] test=1 radek[j]="" } } } if (test < 1 && radek[i]!= "") print radek[i] } } }’ $INPUT_FILE >>$OUTPUT_FILE

62

F

SKRIPT PREPARE NODES

#!/bin/bash INPUT_AXIS="./nodes.axis" INPUT_NODES="./nodes.actual" OUTPUT_NODES="./nodes.txt" OUTPUT_NODES_NOAXIS="./nodes.noaxis" #ulozeni obsahu INPUT_NODES jiz bez duplicit do nodes_act nodes_act=‘sort -u $INPUT_NODES‘ #ulozeni poctu radku radku_nodes=‘echo "$nodes_act" | wc -l‘ #pokud jiz existuje soubor s vysledkem, smaze ho if [ -f $OUTPUT_NODES ] then rm -f $OUTPUT_NODES fi #pokud jiz existuje soubor nodes.noaxis, smaze ho if [ -f $OUTPUT_NODES_NOAXIS ] then rm -f $OUTPUT_NODES_NOAXIS fi #pro vsechny zaznamy v nodes_act delej: for node in $nodes_act do LAT=0 #nulovani LON=0 #nulovani # hledani node v souboru INPUT_AXIS + vraceni jeho prislusnych souradnic eval ‘gawk -F ";" -v mhost=$node ’{ if ($1 == mhost) print "LAT="$2"\n" "LON="$3"\n" }’ $INPUT_AXIS‘ if [ "$LAT" == "0" ] && [ "$LON" == "0" ] then #pokud nebyl nalezen -> souradnice jsou LAT=0 LAN=0 #tak zapis do souboru OUTPUT_NODES_NOAXIS echo "$node" >>$OUTPUT_NODES_NOAXIS else #pokud byl nalezen #zapsat do souboru OUTPUT_NODES echo "$node;$LAT;$LON" >>$OUTPUT_NODES fi #vypisy stavu zpracovani na obrazovku echo "Zbyva zpracovat: $radku_nodes - time: $((SECONDS-merime))" ((radku_nodes -= 1)) merime=$SECONDS done

63

ICMP PROTOKOLU V IP SÍTÍCH

Recommend Documents