PŘENOS SIGNALIZACE PRO INTERNETOVOU TELEVIZI

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

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

PŘENOS SIGNALIZACE PRO INTERNETOVOU TELEVIZI SIGNALLING TRANSMISSION FOR INTERNET TELEVISION

DIZERTAČNÍ PRÁCE DOCTORAL THESIS

AUTOR PRÁCE

Ing. RADIM BURGET

AUTHOR

VEDOUCÍ PRÁCE SUPERVISOR

BRNO 2010

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

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

Dizertační práce doktorský studijní obor Teleinformatika Student: Ročník:

Ing. Radim Burget 1

ID: 22433 Akademický rok: 2009/2010

NÁZEV TÉMATU:

Přenos signalizace pro internetovou televizi POKYNY PRO VYPRACOVÁNÍ:

DOPORUČENÁ LITERATURA:

Termín zadání: Vedoucí práce:

Termín odevzdání:

30.8.2010

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

prof. RNDr. Vladimír Aubrecht, CSc. Předseda oborové rady

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

ABSTRAKT Signalizace v sítích pracujících s internetovým protokolem (IP) je používána pro monitorování a řízení činnosti sítě. Tato práce se zabývá přenosem signalizace skrze IP sítě pro velké skupiny komunikujících prvků a navrhuje škálovatelné řešení, jak pro malá, tak pro velká vysílání internetových televize (IPTV). Hlavní přínos práce spočívá v návrhu algoritmů pro ustavení optimálního hierarchického stromu na základě dostupných zdrojů a s ohledem na geografickou a virtuální polohu jednotlivých stanic. Pro účely optimalizace byly použity jak simulace s parametry globální experimentální sítě Planetlab, tak byly navržené algoritmy a protokoly nasazeny do reálného provozu v této síti.

KLÍČOVÁ SLOVA IPTV, signalizace, RTCP, RTP, Hierarchická agregace, síťové souřadnicové systémy

ABSTRACT A signalization in an Internet protocol environment is commonly used for monitoring quality of service and other parameters of a network. This thesis is involved in transmission of signalization through internet protocol networks and proposes scalable solution for small and even for large-scale internet television broadcasting. The main contribution of this thesis lies in design and validation of optimal hierarchical tree on the basis of resources assigned. This is done in respect to geographical distance, network distance of each particular member of the hierarchical structure. For the design of algorithms simulations and global experimental network were used.

KEYWORDS IPTV, signalling, RTCP, RTP, hierarchical aggregation, network coordinating systems

Bibliografická citace: BURGET R. PŘENOS SIGNALIZACE PRO INTERNETOVOU TELEVIZI. Brno: Vysoké učení technické v Brně, Fakulta elektrotechniky a komunikačních technologií, 2010. Počet stran s. 107. Vedoucí dizertační práce doc. Ing. Dan Komosný, Ph.D.

PROHLÁŠENÍ Prohlašuji, že svou dizertační práci na téma „PŘENOS SIGNALIZACE PRO INTERNETOVOU TELEVIZIÿ jsem vypracoval samostatně pod vedením vedoucího dizertační práce a s použitím odborné literatury a dalších informačních zdrojů, které jsou všechny citovány v práci a uvedeny v seznamu literatury na konci práce. Jako autor uvedené dizertační práce dále prohlašuji, že v souvislosti s vytvořením této dizertační práce jsem neporušil autorská práva třetích osob, zejména jsem nezasáhl nedovoleným způsobem do cizích autorských práv osobnostních a jsem si plně vědom následků porušení ustanovení § 11 a následujících autorského zákona č. 121/2000 Sb., včetně možných trestněprávních důsledků vyplývajících z ustanovení § 152 trestního zákona č. 140/1961 Sb.

V Brně dne

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

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

Děkuji vedoucímu disertační práce Doc. Ing. Danu Komosnému, Ph.D. a Prof. Ing. Zdeňkovi Smékalovi, CSc. za užitečné rady a pomoc při vypracování disertační práce.

SEZNAM SYMBOLŮ, VELIČIN A ZKRATEK R

přijímač

S

vysílač

FT

cíl zpětné vazby

RFT kořenový FT FTM správce FT stanic LM

poziční bod (z anglického landmark)

RR

zpráva přijímače (ang. Receiver Report) posílaná od R směrem k FT

SR

zpráva vysílače (z ang. Sender Report)

RSI zpráva FT (ang. Receiver Summary Information) informující o stavu v podsíti Is Alive zpráva posílaná periodicky za účelem monitorování funkčnosti stanice FTD zpráva Feedback Target Definition sloužící pro definici role v hierarchickém stromu FTR zpráva Feedback Target Registration sloužící pro registraci stanic v hierarchickém stromu FTI zpráva Feedback Target Information sloužící pro informování stanice FTM od ostatních stanic FT FTS zpráva Feedback Target Specification sloužící pro popis podoby hierarchického stromu nR

počet přijímačů

nFT

počet všech cílů zpětné vazby

nFT (h) počet cílů zpětné vazby v h-té vrstvě hierarchického stromu, počítáno od kořene stromu h = 0 TRR perioda vysílání RR zpráv přijímačem TSR

Perioda vysílání SR zpráv vysílačem

TRSI perioda vysílání RSI zpráv od FT

B

šířka pásma vyhrazená pro vysílání RTP i RTCP (audio či video)

BRTCP šířka pásma vyhrazená pro kanál RTCP BRR šířka pásma vyhrazená pro posílání RR zpráv BRSI šířka pásma vyhrazená pro posílání RSI zpráv BTTP šířka pásma vyhrazená pro protokol TTP RTP Real-Time Transport Protocol [73] RTCP Real-Time Control Protocol [73] F

množina všech FT

FA

množina všech aktivních FT

FP

množina všech pasivních FT

FAl

množina všech aktivních FT v l-té vrstvě hierarchického stromu

LRR délka paketu RR LRSI délka paketu RSI TTP Tree Transmission Protocol LAN Z anglického Local Area Network, představuje síť lokálního charakteru WAN Z anglického Wide Area Network, představuje rozsáhlejší sítě spojující několik LAN TALIVE Perioda pro hlášení funkčnosti stanice FT TREQ Perioda pro dotazování stanic FT o změření RTT vůči jiným FT PRTT Míra naplnění tabulky vzdáleností RTT mezi jednotlivými FT RTT Z anglického round-trip time. Představuje dobu přenosu paketu na vydálené místo v síti a zpět CFT Míra změny ve skupině FT od posledního stanovení pozic NI

Počet FT při poslední inicializaci souřadnicového systému

NCH Počet změn ve skupině FT stanic od poslední inicializace souřadnicového systému

N

Celkový počet pozičních bodů v souřadnicovém systému

D

Počet dimenzí v souřadnicovém prostoru

ε(x, y) Odchylka mezi hodnotami x a y L

Množina pozičních bodů

Li

Poziční bod

dLi ,Hj Vzdálenost mezi pozičním bodem a stanicí H v síti dLi ,Lj Vzdálenost mezi pozičními body v síti dSLi ,Lj Vzdálenost mezi pozičními body v souřadnicovém prostoru Z

množina celých čísel

min(x, y) Funkce vracející menší z hodnot argumentu x či y max(x, y) Funkce vracející větší z hodnot argumentu x či y wait(x) Funkce pozastaví provádění programu na x milisekund. random(x, y) Funkce vracející (pseudo)náhodné číslo v intervalu x a y s rovnoměrným rozložením pravděpodobnosti. VoD Video na vyžádání z anglického Video on Demand on-line Termín online je termín vztažaný k telekomunikacím, s tím, že online představuje status připojení k síti set-top-box zařízení sloužící k dekódování videa na straně uživatele služby IPTV STB viz set-top box IP

Internet protokol

PIM Protocol Independent Multicast ASM Any-source Multicast, typ multicastu, umožňující libovolný počet vysílačů ve skupině SSM Source-secific Multicast, typ multicastu, umožňující jediného vysílače ve skupině IGMP Internet Group Management Protocol

IP

Internet Protocol

UDP User Datagram Protocol TCP Transport Control Protocol MPLS Multiprotocol Label Switching, a mechanismus používaný ve vysokorychlostních sítích IPTV Televizní vysílání vysílané přes IP protokol P2P architektura peer-to-peer, neboli klient-klient VoD Video on Demand, internetová služba video na vyžádání MLD Multicast Listener Discovery BPON Broadband Passive Optical Network GPON Gigabit Passive Optical Network DSLAM Digital Subscriber Line Access Multiplexer, zařízení (nejčastěji umístěné u telefonního operátora) pro připojení mnoha zákazníků modem zařízení pro převod mezi analogovým a digitálním signálem kodek zařízení nebo počítačový program, pro kompresi a dekompresi datového proudu nebo signálu terestriální pozemní analogové anebo digitální televizní vysílání MPEG je zkratkou Motion Picture Experts Group, v dnešní době se jedná o zažitou zkratku ohledně rodiny audio a video kodeků PES Packetized Elementary Stream IOS IOS je název pro operační systém v síťových produktech společnosti CISCO ATM zkratkou Asynchronous Transfer Mode, protokol založený na přepínaných okruzích b

bit, základní a současně nejmenší jednotka informace používaná v informatice

B

byte, jednotka množství dat v informatice, zpravidla označuje osm bitů

Mbs−1 jednotka přenosové rychlosti, megabit za sekundu

OBSAH Seznam symbolů, veličin a zkratek

7

1 Úvod 1.1 Používané protokoly pro přenos videa v internetovém televizním vysílání 1.2 Signalizace prostřednictvím zpětného kanálu . . . . . . . . . . . . . . 1.3 Přehled členění textu disertační práce . . . . . . . . . . . . . . . . . .

14 15 17 19

2 Přenos multimédií v sítích internetového protokolu 21 2.1 Využití signalizace RTCP . . . . . . . . . . . . . . . . . . . . . . . . 24 3 Hierarchická agregace 3.1 Prvky sítě hierarchické agregace 3.1.1 Vysílač . . . . . . . . . . 3.1.2 Přijímač . . . . . . . . . 3.1.3 Cíl zpětné vazby . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

4 Odhad vzájemné polohy stanic na základě latence 4.1 Odhad pozice v síti . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Odhad pozice pomocí IP adresy a reverzních záznamů . . . . . . 4.3 Měření vzdálenosti pomocí latence . . . . . . . . . . . . . . . . . 4.4 Souřadnicové systémy pro odhad vzdáleností mezi stanicemi . . 4.4.1 Síťový souřadnicový systém Global Network Positioning 4.4.2 Síťový souřadnicový systém Vivaldi . . . . . . . . . . . . 4.4.3 Síťový souřadnicový systém Netvigator . . . . . . . . . . 4.4.4 Síťový souřadnicový systém Myth . . . . . . . . . . . . . 4.4.5 Síťový souřadnicový systém Pharos . . . . . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

26 27 27 29 29

. . . . . . . . .

30 30 32 33 34 34 37 38 39 40

5 Limity hierarchické agregace

43

6 Simulace souřadnicových systémů 6.1 Ideální podmínky . . . . . . . . . . . . . . . 6.1.1 Souřadnicový systém GNP . . . . . . 6.1.2 Mapování z imaginárního prostoru do 6.1.3 Souřadnicový systém Vivaldi . . . . . 6.2 Šíťové podmínky . . . . . . . . . . . . . . .

44 44 44 49 50 51

. . . . 2D . . . .

. . . . . . . . . . . . prostoru . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

7 Sběr signalizace přijímačů 7.1 Návrh algoritmu pro rozložení stanic FT . . . 7.2 Optimalizace algoritmu TTA . . . . . . . . . . 7.3 Zhodnocení algoritmu TTA . . . . . . . . . . 7.4 Ustavení stromu při nedostatečném počtu FT

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

8 Integrace hierarchické agregace se souřadnicovým systémem 8.1 Registrace nově příchozcích FT stanic . . . . . . . . . . . . . . . 8.2 Odhlášení FT stanice . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Přidělení hierarchického stromu vysílači . . . . . . . . . . . . . . 8.4 Zajištění spolehlivosti FT . . . . . . . . . . . . . . . . . . . . . 8.5 Inicializace pozice přijímače . . . . . . . . . . . . . . . . . . . . 9 Návrh protokolu pro hierarchickou agregaci 9.1 Obecná hlavička přijímače . . . . . . . . . . 9.2 Obecný popis fungování protokolu TTP . . . 9.3 Přijímač . . . . . . . . . . . . . . . . . . . . 9.4 Cíl zpětné vazby (FT) . . . . . . . . . . . . 9.5 FT Manažer (FTM) . . . . . . . . . . . . . 9.6 Vysílač (S) . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . .

. . . . .

. . . . . .

. . . .

. . . . .

. . . . . .

. . . .

54 54 57 57 59

. . . . .

63 63 65 65 67 67

. . . . . .

69 69 70 72 74 74 76

10 Vybrané navazující práce a validace navrženého řešení 78 10.1 Globální experimentální síť PlanetLab . . . . . . . . . . . . . . . . . 81 10.2 Sběr informací a vizualizace celého stromu ze sítě PlanetLab . . . . . 83 11 Závěr

86

Literatura

89

Vybraná literatura autora

98

Seznam algoritmů a příloh

104

A Přílohy A.1 Obsah přiloženého CD . . . . . . . . . . . . . . . . . . . . . . A.1.1 Implementace protokolu TTP . . . . . . . . . . . . . . A.1.2 Knihovna pro podporu Source-specific Multicast pro formu JAVA . . . . . . . . . . . . . . . . . . . . . . . . A.1.3 Simulační knihovna JSimlib 3 . . . . . . . . . . . . . . A.2 Graf závislosti doby přenosu a počtu zařízení . . . . . . . . . .

105 . . . . 105 . . . . 105 plat. . . . 105 . . . . 105 . . . . 105

Rejstřík

107

1

ÚVOD

Na základě mnoha prognóz [35], [68], [53], které byly v posledních letech provedeny na téma vývoje trhu internetových televizí (IPTV), vše nasvědčuje tomu, že v následujících letech budeme svědky globálního rozmachu nasazení této technologie po celém světě. Oblasti, kterých se tento rozmach dotkne nejvíce, budou zřejmě Evropa, Asie a Severní Amerika. Na základě minulého rozvoje a předpokládaných výdajů by trh s IPTV měl do konce roku 2013 přesáhnout 80 milionů domácností, kde se předpokládá, že celkový obrat překročí 36 miliard dolarů ročně. Za zmínku také stojí skutečnost, že i přes současnou ekonomickou recesi si růst trhu IPTV udržel silnou pozici a některé prognózy z minulých let současná situace dokonce předčila. Z tohoto pohledu skýtá trh IPTV velký potenciál s příslibem růstu až několik desítek procent ročně v letech 2010 – 2013 [53]. Tímto se technologie IPTV stává perspektivní investicí pro mnoho subjektů a i malý podíl na tomto trhu může představovat zajímavé ekonomické výsledky v letech následujících. Služba IPTV přináší nižší náklady pro distributory televizního signálu, nižší náklady pro koncové zákazníky a má potenciál přinést divákovi nové služby s přidanou hodnotou. S pomocí IPTV je možné provozovat on-line videopůjčovny, poskytovat mnohonásobně větší škálu televizních programů, mnohem snadněji, a tedy i efektivněji, cílit reklamu a regionálně přizpůsobovat jejich podobu, získávat podrobnější statistiky o sledovanosti a chování diváků, zajistit interakci s diváky a mnohem dalších služeb. Jedna z nejběžnějších podob struktury sítě z pohledu distribuce IPTV je znázorněna na obr. 1.1. Struktura je rozdělena podle role, kterou v síti zastává, na oblast hlavního odbavovacího pracoviště, páteřní síť, regionální odbavovací pracoviště, přístupovou síť a domácnosti. Činností hlavního odbavovacího pracoviště je sběr a kódování multimediálního obsahu do podoby, která je vhodná pro přenos po síti. Multimediální obsah může být poskytován na základě aktuálního obsahu obdrženého terestriálního vysílání, z satelitního vysílání, z obsahu kamery či také na základě obsahu uloženého v databázi. Takový obsah je v případě filmů často označován za video na vyžádání (VoD, z anglického Video on Demand). Vysílač má pak za úkol poskytnout datový tok do sítě. Takto zpracovaná data jsou následně přenášeny skrze páteřní síť až na místo regionálního odbavovacího pracoviště. Páteřní síť má zpravidla vysokou propustnost a dobré parametry sítě z pohledu kolísání zpoždění přenosu. Nicméně i přesto mohou vznikat chyby. Nejčastější chyby jsou způsobeny ztrátou paketu, poškozením paketu, duplikací paketu či zpožděním paketu. Regionální odbavovací pracoviště přijímá data zpravidla z mnoha zdrojů (např. satelit, terestriální vysílání, IPTV) a poskytuje tuto službu zákazníkům, kterým je

14

Database

VoD

Database

VoD PC

Vysílač Média kodéry Vysílač Média kodéry

IP / MPLS páteřní síť

OLT

BPON/ GPON

Set-top-box TV

ADSL2

Přepínač

PC

IP DSLAM Hlavní odbavovací pracoviště

Páteřní síť

Regionální odbavovací pracoviště

Přístupová síť

Modem Set-top-box TV Domácnosti

Obrázek 1.1: Obecná struktura sítě pro potřeby internetového televizního vysílání.

zpravidla poskytována datová konektivita. Poslední vrstvou sítě je síť přístupová. Skrze ni jsou pak připojovány domácnosti či další odběratelé datových či hlasových služeb. Toto regionální odbavovací pracoviště může signál odebírat z hlavního regionálního pracoviště, či může čerpat z jiných zdrojů a tato data posílat do sítě. Jeden z důvodů, proč je koncovému zákazníkovi zprostředkováno vysílání skrze regionální pracoviště, je skutečnost, že audio a video data jsou náchylná na poruchy, které v síti mohou vznikat, a současně je obtížné měřit kvalitu příjmu pro velký počet diváků. Této problematice se bude věnovat blíže následující text.

1.1

Používané protokoly pro přenos videa v internetovém televizním vysílání

Aby mohl přenos videa skrze paketové sítě správně probíhat, je nezbytné nejprve transformovat datový tok do podoby, kterou podporují jednotlivé technologie vrstvy sítě. Nejčastěji používané technologie jsou naznačeny na obr. 1.2. Vstupní signál může být jak v digitální podobě, tak v podobě analogové. V druhém případě je signál nejprve digitalizován a následně zkomprimován pomocí některé komprimační technologie (nejčastěji MPEG-2 [3], MPEG-4, H.264 [84] anebo WM9 (VC-1) [79]). Komprimovaný obraz a zvuk je členěn do menších tzv. Packetized Elementary Stream (PES) paketů, které jsou již vhodnější pro přenos po síti. Tyto PES pakety potom tvoří základ přenosového datového toku MPEG-TS. Tento datový tok je následně vložen do záhlaví Real-Time Transport protokolu (RTP). Následuje zasazení datového toku do zbylých čtyř vrstev - transportní, síťové, spojové a fyzické. To obnáší opatřit data záhlavím a zápatím nejprve Uniform Datagram Protokolu

15

Aplikační vrstva

Video/Audio+služby

Prezentační vrstva

PES

Relační vrstva

MPEG-TS

Transportní vrstva

UDP,RTP, RTCP

Síťová vrstva

IP

Spojová vrstva

Ethernet

Fyzická vrstva

Fyzická vrstva

Obrázek 1.2: Model ISO/OSI a protokoly potřebné pro IPTV vysílání.1 (UDP), následně Internet Protokolu (IP) a nakonec jsou zasazeny do podoby ethernetového rámce 1 . Protokoly se podle použité technologie mohou i lišit, nicméně popsaná sada je dnes jednou z nejčastěji používaných v rámci vysílání IPTV. V této podobě jsou data připravena k transportu skrze síťové prvky a jsou doručena až k settop-boxu na straně příjemce vysílání. Set-top-box je nejčastěji hardwarové zařízení, kterým musí být vybaven každý z koncových uživatelů služby. V tomto zařízení dojde postupně k odstranění hlaviček a zápatí jednotlivých protokolů a nakonec k dekomprimaci dat a transformaci do podoby, která je čitelná televizním přístrojem. Samotná distribuce dat může být realizována pomocí spojení typu unicast či multicast. Pro komunikaci typu multicast je definována protokolová sada Protocol Independent Multicast (PIM), kde každá část je optimalizována pro různá prostředí. Existují dva hlavní režimy PIM: řídký (PIM-SM) [24], [25], [26] a hustý (PIM-DM) [77]. Třetí případ obousměrného PIM (BIDIR-PIM) [30] není tolik rozšířen. Řídký režim předpokládá, že členové multicastové skupiny jsou v síti a podsítích rozmístěni spíše řídce, zatímco hustý režim předpokládá, že téměř všichni (či alespoň většina) podsítí bude mít o distribuovaná data zájem. V případě spojení typu unicast existuje spojení pro každého diváka zvlášť, a pokud je např. 100 diváků současně sledující jeden pořad, je nutné posílat data pro každého diváka samostatně. Pro datový tok o velikosti 2 Mb/s by tedy bylo zapotřebí linky o kapacitě 2000 Mb/s. Je zřejmé, že takový typ vysílání je nepříliš efektivní 1

Protokolová sada RTP/RTCP je z pohledu modelu ISO/OSI obtížněji zařaditelná a lze v ní najít prvky transportní, relační i prezentační vrstvy. V tomto textu byla protokolová sada RTP/RTCP v souladu s převládající většinou odborné literatury také zařazena do vrstvy transportní.

16

a současně neumožňuje sledování kanálu příliš mnoha uživatelům. Další a mnohem efektivnějším způsobem datového přenosu je spojení typu multicast. Multicast je na v současnosti dostupných zařízeních k dispozici ve dvou základních módech: AnySource Multicast (ASM) a Source-Specific Multicast [2]. Historicky starší varianta ASM má velkou výhodu v tom ohledu, že vysílat data do multicastové skupiny může kdokoli z připojených uživatelů. To umožňuje komunikaci typu každý s každým. Nevýhodou je složitost konfigurace a také skutečnost, že tento typ není obecně v prostředí Internetu podporován a je spíše záležitostí menších soukromých sítí či experimentálních prostředí v rámci univerzit. Druhá varianta SSM je novější a přináší omezení, že pouze jediný uzel z celé skupiny může být vysílačem. Výhodou je, že jeho nasazení je výrazně jednodušší. V prostředí IPv4, která je současnosti stále převládající oblastí internetu, je nezbytné, aby poslední směrovač u příjemce podporoval protokol Internet Group Management protokol (IGMP) ve verzi 3 [12]. Zřejmě celosvětově nevýznamnějším dodavatelem prvků síťového zařízení je společnost CISCO. Tento výrobce do svých směrovačů integruje podporu protokolu IGMPv3 již řadu let. Konkrétně je to od verze IOS2 12.23 . Podpora IPv6 je samozřejmě také k dispozici. Pro jeho podporu je nezbytný Multicast Listener Discovery (MLD)[31], který je také od verze IOS 12.2 k dispozici. V případech, kdy je žádoucí, aby do vysílací skupiny posílal data pouze jediný zdroj (tj. např. IPTV, rádio, atp.), je SSM rozhodně vhodnější variantou. Kromě dopředného kanálu pro distribuci audio a video dat existuje také kanál zpětný. Jeho nejčastější využití je sledování kvality příjmu na straně přijímacího zařízení. Na jejich základě lze identifikovat případné problémy sítě a provést taková opatření, která povedou k minimalizaci dopadů vnímaných ze strany diváka. V případě, že měření kvality služby je interaktivní, může poskytovatel provádět změny v reálném čase a adaptovat tak vysílaný tok aktuálnímu stavu v síti. Tím lze minimalizovat potenciální problémy z pohledu koncového uživatele. Monitorování kvality příjmu a vlastností přenosu je realizováno prostřednictvím Real-Time Control protokolu (RTCP).

1.2

Signalizace prostřednictvím zpětného kanálu

Zatímco dopředný kanál je již v současné době dobře zvládnut a příslušná protokolová sada pro multicast je již několik let nabízena v základní verzi většiny směrovačů přinejmenším předních výrobců síťových zařízení, distribuce zpětného 2

IOS je zkratkou Internetwork Operating Systém, což představuje operační systém používaných na směrovačích a přepínačích firmy Cisco Systems. 3 http://www.ciscosystems.com/en/US/docs/ios/12_2sx/12_2sxh/feature/guide/ exaclsxh.html

17

kanálu doposud vyřešena není. V případě nasazení multicastu typu ASM problém není. V takovém případě může být každý prvek současně přijímač i vysílač a protokolová sada automaticky zajistí distribuci přes multicastovou skupinu. Jeho nevýhodou je značná složitost a také, že nemůže být nasazena pro velké vysílací skupiny (max. v řádu stovek účastníků). Mutlticast typu SSM je z tohoto pohledu připraven na výrazně větší vysílací skupiny. Díky omezení na jeden zdroj dat tu ale vzniká komplikace s distribucí zpráv od zbytku vysílací skupiny. Tato práce navazuje na společné výsledky pracoviště Univerzity v Cambridge a AT&T Labs-Research, dále společnosti Intel [63], [37] a University of Prince Edward Island [23], [21], [22], [20], které se zbývají výzkumem přenosu signalizace skrze zpětný kanál pro velké skupiny uživatelů. Ke konci řešení této práce v únoru roku 2010 byly některé z jejich výsledků shrnuty do výsledného dokumentu RFC [63]. Přínos této práce spočívá v rozšíření struktury pro přenos signalizace od přijímačů zpět k přijímači a optimalizaci využití zdrojů. V práci jsou navrženy autonomní algoritmy, které samy určují strukturu zpětného kanálu a automaticky se přizpůsobují aktuálnímu stavu v síti. Struktura zpětného kanálu před a po optimalizaci je znázorněn v obr. 1.3. Použité algoritmy jsou navrženy tak, aby pracovaly efektivně jak pro malé regionální poskytovatele, tak pro rozsáhlé vysílací skupiny, které pokrývají rozsáhlá geografická území. Oproti původnímu předpokladu [37], kde autoři předpokládají neomezené hardwarové zdroje poskytovatele, tato práce vychází z praktických požadavků poskytovatelů IPTV vysílání a je schopna se přizpůsobit libovolným hardwarovým zdrojům. Je tak schopna růst od malých vysílání až po rozsáhlé skupiny, pokrývající např. celé kontinenty. Veškeré navržené algoritmy byly nasazeny a ověřeny z pohledu jejich funkčnosti v experimentální síti Planetlab4 . Jedná se o celosvětově rozlehlou počítačovou síť určenou pro experimentální účely a potřeby. Celá práce se snaží v maximální míře využít stávající používané protokoly, zejména protokolovou sadu RTP/RTCP. Je třeba také zdůraznit, že práce si v žádném případě neklade za cíl pomocí popisovaných technologií kompletně nahradit zavedenou strukturu, kde vystupuje hlavní odbavovací pracoviště a regionální odbavovací pracoviště (viz obr. 1.1). Co popisovaná technologie přináší, je relativně rychlé a škálovatelné sledování kvality služby na straně přijímačů. Pokud se poskytovatel IPTV služby rozhodne poskytovat službu IPTV nejen v rámci sítě LAN5 , ale i v rámci sítí WAN6 . Pokud se nalezne část IPTV trhu, kde uživatelé upřednostní nižší cenu či větší velikost nabídky programů 4

www.planet-lab.org LAN vychází z anglického Local Area Network a je v dnešní době zavedená zkratka značící síť lokálního rozsahu 6 WAN je zkratkou z anglického Wide Area Network a představuje rozsáhlou síť zahrnující v sobě mnoho sítí LAN 5

18

(a) Neoptimalizované rozložení

(b) Optimalizované rozložení

Obrázek 1.3: Optimalizované a neoptimalizované rozložení struktury pro sběr signalizace. a služeb nad vysokou kvalitou, může to znamenat z hlediska poskytovatelů výrazně větší cílovou skupinu. Společně s tím je možné skrze zpětný kanál přenášet další data a tak poskytnout služby s přidanou hodnotou v podobě např. interaktivních služeb. Jelikož se tato práce zajímá přednostně o signalizaci skrze veřejné sítě, bude ve zbytku práce používána zjednodušená topologie, kde nebudou brány v úvahu detaily, ale jen vztah vysílač vs. přijímač popřípadě další prvky, které jsou v této práci zavedeny.

1.3

Přehled členění textu disertační práce

První část této práce se detailněji zabývá protokolem RTP/RTCP s tím, že klade důraz na matematické vztahy, kterými se celý protokol řídí. Současně s tím je v kapitole zdůrazněna závislost doby šíření signalizace na počtu přijímačů ve skupině a nastíněn problém z toho plynoucí. Tato protokolová sada je v současné době jedna z nejčastěji používaných pro přenos audia a videa. Další kapitola je věnována teoretickému modelu hierarchické agregace. Kapitola opět objasňuje závislost doby přenosu signalizace na počtu přijímačů ve skupině a zdůrazňuje její výhody oproti RTP/RTCP. Kapitola třetí se potom zabývá problematikou lokalizace síťových stanic s použitím latence. Čtvrtá kapitola zdůrazňuje nedostatky hierarchické agregace a ukazuje prostor pro její zdokonalení. Pátá kapitola popisuje experimenty a simulace, které byly provedeny s umělými síťovými souřadnicovými systémy. Simulace byly prováděny, jak v umělém prostoru, tak i v prostoru získaném z měření parametrů skutečné sítě. Šestá kapitola se zabývá návrhem a popisem algoritmů pro ustavení hierarchické stromové struktury pro přenos signalizace přijímačů a

19

zhodnocuje kolik z celkové cesty v síti lze tímto algoritmem v rámci celé struktury ušetřit. Stav před a po aplikaci tohoto algoritmu je znázorněn na obr. 1.3. Sedmá kapitola popisuje principy protokolu, s pomocí kterého lze integrovat virtuální souřadnicový systém společně s hierarchickou stromovou strukturou pro přenos signalizace. Protokol je navržen tak, aby jej bylo možné provozovat v rámci vlastní sítě, ale také jako službu pro jiné operátory IPTV vysílání. Její nasazení nemusí být vázáno na konkrétního operátora, ale pro jakýkoli druh služeb, kde je vyžadován rychlý přenos signalizace od velkého počtu přijímačů. Osmá kapitola potom uvádí detaily ohledně podoby zpráv používaných v rámci protokolu a detailně objasňuje roli jednotlivých prvků v síti. V poslední kapitole jsou popsány některé z podpůrných nástrojů, které v rámci této práce vznikly. Je také popsán webový portál, který slouží ke kontrole a celkové validaci funkčnosti celého zpětného kanálu. Na konci je celá práce zhodnocena a jsou naznačeny další možné cesty vývoje.

20

2

PŘENOS MULTIMÉDIÍ V SÍTÍCH INTERNETOVÉHO PROTOKOLU

Pro distribuci časově citlivých multimediálních dat se protokoly RTP a RTCP [73] se staly převládajjícím řešením. Dvojice protokolů je přesně definována v RFC 1 Protokol RTP slouží k distribuci časově citlivých dat, jako je například audio či video. Často bývají tímto způsobem šířena i další data, jako jsou titulky, klíče pro autentifikaci atp. Vysílání RTP je možné prostřednictvím unicastového spojení, avšak při větším počtu přijímačů dochází ke značně neefektivní komunikaci a velice brzy také k vyčerpání kapacity použitého datového kanálu. Jako řešení pro větší počty spojení se nabízejí multicastová spojení Any-Source Multicast (ASM), popřípadě také novější Source-Specific Multicast (SSM) [2]. Rozdíl mezi těmito ASM a SSM je ten, že v případě ASM může být každý přihlášený ve skupině vysílačem, což však vede k velké složitosti ve směrování a směrovacích tabulkách. SSM přišel z tohoto pohledu s optimalizací, nicméně podporuje pouze jeden zdroj dat. Na druhou stranu se jedná o zjednodušení ASM multicastu a je možné jej nasadit i pro velké skupiny přijímačů. Na obr. 2.1a jsou znázorněna schéma IPTV vysílání. U varinaty SSM (viz obr. 2.1b) dochází mírně ke komplikaci v tom smyslu, že signalizace od přijímačů nemůže být odesílána. Řešení je však jednoduché - signalizace je poslána unicastovým kanálem vysílači a ten pak tyto zprávy “zrcadlí” do multicastového kanálu. Multicast je technologie, kterou pravděpodbně v budoucnu čeká velký rozmach. V současnosti roste výrazně počet domácností, které disponují širokopásmovým připojením do sítě Internet a díky tomu je také možné provozovat i služby, které by nepřipadaly v úvahu. Co se týče problematiky multicastu je to ovšem poněkud ošidné. V jakékoli literatuře se o nich dočteme jako běžně známou a používanou věc, nicméně pokud příjdeme do reality dnešního internetu, až na výjimky jako jsou především experimentální a akademické laboratoře, téměř nikde na něj nenarazíme. Tento stav je zapříčiněn tím, že tento druh služeb je poměrně nový a ze stran uživatelů je po nich malá poptávka. V tomto směru mají výhodu operátoři velkých sítí, jako je France Telecom, Deutche Telecom kteří současně poskytují službu IPTV a současně vlastní infrastrukturu sítě. Mohou tedy směrovače v síti optimalizovat pro své potřeby. Bohužel, většina struktury sítě internet je na americkém, evropském i asijském trhu poměrně značně segmentována na malé vlastníky lokálních sítí, které jsou vzájemně připojeni. Ukáže zřejmě až čas, zdali se vytvoří dostatečně silná 1

RFC je zkratkou anglického “Request For Comments” a je vydávána organizací Internet Engineering Task Force (IETF). Organizace se zabývá popisem metod, chováním, výzkumem a inovacemi pro Internet a internetové aplikace.

21

poptávka po tomto druhu aplikací. RTCP realizuje přenos signalizace směrem od přijímačů. Tato signalizace má širokou škálu využití - od monitorování kvality služby přijímačů, přes informování o lokalitě posluchačů, až po služby jako je interaktivní hlasování, online nakupování a další. RTP/RTCP jsou navrženy tak, aby byly zcela nazávislé na nižších protokolech. Není tedy žádný problém použít technologii jak v prostředí Transmission Control Protocol (TCP) [36] tak v prostředí UDP [70] popřípadě dalších. Zjednodušeně by se dal princip RTCP protokolu shrnout nějak takto: vysílač posílá tzv. Sender Report (SR) zprávy všem přijímačům, kde je mimo jiné informace i o tom, kolik dat bylo vysláno. Na druhé straně jsou přijímače, které SR zprávy přijímají, analyzují a odpovídají tzv. Receiver Report (RR) zprávami. Ty obsahují mimo jiné informaci o kvalitě příjmu (ztrátovost paketů, jitter 2 , RTT3 ) [73]. Tyto zprávy jsou periodicky posílány po dobu celého spojení. Aby nedošlo k zahlcení kanálu i v případě, že je počet přijímačů velký, je perioda vysílání SR i RR zpráv přesně stanovena podle následujících rovnic: TRR =

nR · PRR [s], 0, 75 · BRTCP

(2.1)

TSR =

PSR [s], 0, 25 · BRTCP

(2.2)

BRTCP = 0, 05 · B [bit · s−1 ].

(2.3)

Kde 0,25 zastupuje 25 % podíl pásma vyhrazený pro dopředný kanál, 0,75 představuje 75 % vyhrazeného pro zpětný kanál, 0,05 představuje 5% kanálu vyhrazeného pro RTCP, PRR představuje délku zprávy RR v bitech, PSR délku zprávy SR, B je celková šířka pásma vyhrazená službě, BRTCP představuje šířku pásma vyhrazenou pro RTCP protokol [73], nR představuje počet přijímačů. Během trvání RTP/RTCP vysílání jsou BRTCP a B neměnné, a jelikož je v síti právě jeden přijímač, je délka zpráv RR (PRR ) také konstantní. Co především ovlivňuje periodu vysílání je tedy počet přijímačů ve skupině nR . Pokud je počet přijímačů nR opravdu velký, znamená to, že perioda posílání zpráv roste třeba až na půl hodiny, což je například pro potřeby interaktivního hlasování diváků nedostačující. Aby nenastal případ, kdy by zprávy přijímače byly posílány příliš často, byla zavedena spodní hranice 5 s. Pro všechny hodnoty periody nižší než je tato konstanta jsou hodnoty upraveny na právě tuto délku periody, viz rovnice 2.4. Další 2

Kolísání velikosti zpoždění paketů při průchodu sítí (vzniká např. na směrovačích (routerech) jako důsledek změn routování, chování interních front routeru atd.) 3 Z anglického Round-Trip Time, představuje latenci cestování paketu na vzdálenou stanici a zpět.

22

parametr modifikující výpočet periody je tzv. kompenzační faktor a náhodné číslo k (viz rovnice 2.6, 2.5). Kompepnzační faktor byl stanoven na základě empirických zkušeností v síti, parametr k představuje náhodné číslo v intervalu k ∈< 0, 5; 1, 5 >, které zajišťuje vzájemné vysílání RR zpráv přijímači rovnoměrně v čase. V případě standardu RFC je náhodné číslo aplikováno jak na přijímač, tak na vysílač. Nicméně, jelikož vysílač může být v případě IPTV pouze jeden, pozbývá svého významu a je spíše na škodu nežli ku prospěchu. Není-li řečeno jinak, jsou v následujícím textu veškeré vztahy, týkající se délky periody z důvodu jednoduchosti, popisovány bez nich: ′

(2.4)

TXX = max(5 s, TXX ) [s], ′

′′

TRR

TXX , k ∈< 0.5; 1, 5 > [s], =k· e − 1, 5

(2.5)

′

′′

TSR =

TXX [s]. e − 1, 5

(2.6)

RR-RTCP IPTV vysílač

RR-RTCP RTP (audio, video)

RR-RTCP RTP (audio, video)

SR-RTCP + zrcadlené RR-RTCP

SR-RTCP

RR-RTCP

IPTV vysílač

Multicastová skupina (S,G)

Multicastová skupina

RR-RTCP

RR-RTCP RR-RTCP

Přijímač

RR-RTCP Přijímač

RR-RTCP

Přijímač

Přijímač

Přijímač Přijímač

Přijímač Multicast RR/SR (RTCP)

Přijímač

Unicast RR (RTCP)

Multicast Audio/ Video(RTP)

Multicast SR (RTCP)

(a) Any-Source Multicast (ASM)

Multicast Audio/ Video(RTP)

(b) Source-specific Multicast (SSM)

Obrázek 2.1: Zjednodušená topologie architektury IPTV vysílání využívající druh multicastu SSM a ASM.

23

SDTV MPEG-2 2-4 Mbs−1 MPEG-4 1,6 - 2,1 Mbs−1 H.264 1,5 - 2 Mbs−1 WM9 (VC-1) 1,5 - 2 Mbs−1

16 6 6 6

HDTV - 19 Mbs−1 - 9 Mbs−1 - 8 Mbs−1 - 8 Mbs−1

Tabulka 2.1: Kompresní poměr kodeků používaných pro IPTV vysílání. Jak je z rovnice 2.1 patrné, délku periody pro vysílání RR zpráv ovlivňují parametry jako jsou šířka pásma B, počet přijímačů nR a délka zprávy PSR . Zde šířka pásma a délka zprávy zůstávají většinou po dobu vysílání konstantní. Co tedy ′′ především ovlivňuje délku periody TRR je počet přijímačů. Uvážíme-li, že nejčastěji používané kodeky pro IPTV vysílání jsou kodeky MPEG-2, MPEG-4 H.264 (MPEG4-AVC) či WM9 (VC-1) a šířka potřebného pásma je následující jak je uvedeno v tabulce 2.1, může perioda RR zpráv narůstat do opravdu velkých hodnot. Ty se pak mohou stát pro některé případy, jako je například interaktivní hlasování, nepoužitelné. Na obr. 2.2 je potom znázorněna závislost délky periody TRR na použitém kodeku a počtu přijímačů ve skupině. Například pro kvalitu videa SDTV4 v kombinaci s 105 přijímačů je délka periody hlášení zpráv RR u kodeku H.264 12 minut. Uvážíme-li, že televize Nova ve svých rekordech sledovanosti obsahuje dokonce počtů diváků 2,6 milionu. byly by pro některý druh použití tento kanál natolik pomalý, že získaná data by již byla irelevantní. Nemluvě zde o počtech sledovanosti v zemích s větším počtem obyvatel, nežli žije v České republice. V brzké budoucnosti se počítá také s rozmachem mobilních multimediálních služeb. Vzhledem k jejich potenciálnímu počtu a značné nestabilitě vůči době připojení se bude zřejmě jednat o výzvu pro současné technologie.

2.1

Využití signalizace RTCP

Jak již bylo nastíněno, zpětný kanál má velkou škálu využití a s rozmachem této služby se předpokládá ještě širší využití. Signalizace internetového vysílání je nejčastěji používána pro přenos parametrů sítě. Jsou jimi kolísání (jitter), RTT a ztrátovost paketů. Pokud má být služba považována za vysoce kvalitní, neměla by ztrátovost paketů překračovat hodnotu 10−6 , RTT být v řádech stovek milisekund a kolísání v řádech desítek milisekund. Jestliže poskytovatel garantuje nějakou úroveň služby, měl by mít možnost průběžně monitorovat aktuákní stav. Další scénář 4

Zkratka anglického standard-definition television, odpovídá rozlišení 704 pixelům na 480 řádcích.

24

Obrázek 2.2: Závislost délky periody TRR na použitém kodeku, kvalitě videa a počtu přijímačů.

pro poměrně bohaté využití je interaktivní komunikace spolu s diváky na základě aktuálně vysílaného programu. Přínosem této práce je právě skutečnost, že s její pomocí je možné výrazně urychlit přenos této signalizace i pro velké počty přijímačů. Další schopností jsou přesné statistiky o počtu přijímačů. V současnosti operátoři používají speciální zařízení, která komunikují přes GSM kanál a posílají statistiky o aktuálně sledovaném programu. V tomto případě jeden pozorovaný přijímač zastupuje přibližně 8000 diváků. Výsledky proto mohou být výrazně zpřesněny. Navíc je možné přenášet také informaci o přibližné poloze přijímače a interaktivně zobrazovat oblasti sledovanosti. Dnes nepříliš tradiční, ale do budoucna možná slibnou metodou, může být také adaptivní přizpůsobování kvality vysílání aktuálnímu stavu v síti. Například, pokud server dostává informaci, že se plošně zhoršila kvalita příjmu, může na to reagovat vyšší kompresí, tím redukovat datový tok a zamezit tak problémům sítě. Popřípadě by přijímače s nižší kvalitou příjmu byly přesměrovány na jiný kanál, kde je vysílání s menším požadavkem na dostupnou šířku pásma.

25

3

HIERARCHICKÁ AGREGACE

Pro RTCP protokol bylo navrženo několik vylepšení, jako jsou filtrace, zaměření, zdůraznění až po sumarizaci a hierarchickou agregaci [4], [55], [44], které dokázaly tuto závislost snížit. Nejslibnější z těchto metod se ukázala být hierarchická agregace [61], [48], [37], [63]. Hierarchická agregace do sítě přivádí nový prvek – takzvaný cíl signalizace, či anglicky feedback target“ (FT). Těchto stanic typu FT je v síti ” několik. Zaveďme formální popis sítě jako množinu přijímačů R = {r1 , . . . , rm }, jichž je v síti m. Množina F = {f1 , . . . , fn } představuje množinu n FT uzlů a S označuje vysílač. Množina F se dále dělí na dvě disjunktní množiny: množinu aktivních FT: FA a množinu pasivných FT: FP kde FA ∩ FP = ∅. Pasivní FT neprovádějí žádnou činnost a pouze čekají, až dostanou pokyn k aktivaci. Aktivní FT tvoří stromovou strukturu, kde v kořenu stromu je tzv. root feedback target (RFT), neboli kořenový cíl signalizace. Zaveďme konvenci, že F i představuje množinu uzlů v i-té vrstvě stromové struktury a fji představuje FT fj , který se nachází v i-té vrstvě. Aktivní FT v nejnižší vrstvě stromu přijímají RR zprávy od přijímačů, agregují je do tzv. Receiver Summary Information (RSI) paketu a přeposílají nejbližšímu FT z vyšší vrstvy. Na obr. 3.2 jsou znázorněny architektury klasická a rozšířená o hierarchickou agregaci s výškou stromu 1. Zatímco v klasické architektuře jsou

IPTV RR-RTCP RTP vysílač RR-RTCP (audio, video)

SR-RTCP + RSI-RTCP RR-RTCP RR-RTCP

Multicastová skupina (S,G)

Přijímač Přijímač

Přijímač

Hierarchická agregace

RTP/RTCP standard

RSI-RTCP

RSI-RTCP

SR-RTCP IPTV + RTP vysílač RSI-RTCP (audio, video) + Hlavní cíl zpětné vazby

RR-RTCP

Multicastová skupina (S,G)

Cíl zpětné vazby RR-RTCP

Cíl zpětné vazby

RR-RTCP

RR-RTCP Přijímač Přijímač

Přijímač

Přijímač Unicast RR (RTCP)

Multicast Audio/ Video(RTP)

Multicast SR (RTCP)

Unicast RR (RTCP)

Unicast RSI (RTCP)

Multicast SR (RTCP)

Multicast Audio/ Video (RTP)

Přijímač

Obrázek 3.1: Srovnání struktury klasické architektury RTP/RTCP vůči spojení typu SSM multicast [73] (vlevo) a architektury hierarchické agregace (vpravo).

26

RR zprávy posílány přímo vysílači, v případě hierarchické agregace jsou RR zprávy přeposlány nejbližším FT z nejnižší vrstvy stromu, zpráva je potom agregována a šířena až k RFT. S touto architekturou se potom vztahy pro výpočet periody chovají dle následujících rovnic: TSR =

PSR [s], 0, 25 · BRTCP

(3.1)

TRR =

PRR · LH FT (n) [s], 0, 75 · BRTCP

(3.2)

l TRSI =

PRSI · Ll−1 FT (n) [s], 0, 75 · BRTCP

(3.3)

kde konstanta 0,25 zastupuje 25 % vyhrazené pro dopředný kanál, 0,75 zastupuje 75 % kanálu vyhrazeného pro zpětný kanál, n představuje počet přijímačů ve skupině a funkce LH FT (n) vypočte potřebný počet FT, aby nedošlo k překročení hodnoty 5 s. l−1 l TRSI představuje periodu vysílání RSI zpráv FT ve vrstvě l, LRSI představuje počet FT stanic ve vrstvě hierarchického stromu. Ostatní parametry jsou identické jako v případě standardního RTP/RTCP [73]. Na obr. 3.2 je znázorněná závislost výsledného času šíření signalizace. Hodnota B byla zvolena 1 Mbs−1 , délka paketu RR byla zvolena 60 B (konstantní délka bez použití Source Description RTCP paketu). V druhém řádku grafu je vyznačena závislost potřebných aktivních FT v závislosti na počtu přijímačů.

3.1

Prvky sítě hierarchické agregace

V hierarchické agregaci jsou nezbytné čtyři druhy stanic. Obdobně jako v případě standardního RTP/RTCP protokolu to jsou vysílač a přijímač. Dále potom ještě nový prvek: tzv. cíl zpětné vazby (FT).

3.1.1

Vysílač

Úkolem vysílače je odesílat multimediální data do sítě internet prostřednictvím protokolu RTP. Aby bylo možné monitorovat kvalitu příjmu jednotlivých stanic, jsou v pravidelných intervalech TSR 3.1 posílány zprávy SR. Na jejich základě mohou přijímače vyhodnotit množství ztracených paketů a další vlastnosti o kvalitě příjmu. V reálném nasazení bude vysílač zřejmě vypadat jako aplikace nasazená na samostatném serveru. Těchto vysílání může být v jednom okamžiku více, nizméně všechny by měly posílat v různých vysílacích skupinách. V případě SSM multicastu je počet multicastových adres dostatečný, protže je každá skupina identifikována adresou zdroje + multicastovou skupinou. 27

14

0 0

2

4

6

8

10

12

C]

2000

3000

4000 5000 6000 Počet of přijímačů number receivers

7000

8000

9000 10000

1000

2000

3000

4000 5000 6000 početofpřijímačů number active FTs

7000

8000

Změněna výška stromu 9000 10000

D]

0

20

40

60

80

100

120

140

0

1000

0

2

3

4

5

6

7

8

9

10

1

0

Výsledný čas kolísá vždy když je přidán nový FT (výsledný čas není omezen žádnou spodní hranicí).

B]

1

2

3

4

5

6

7

8

9

10

A]

doba šíření signalizace seconds stromem [s]

Number of FTs in session počet FT ve skupině

seconds stromem [s] doba šíření signalizace

početofFT ve inskupině Number FTs session

28

0

1

0

1

}

}

Obrázek 3.2: Závislost celkové doby přenosu signalizace směrem od přijímačů ke kořenovému FT na počtu přijímačů. Levý sloupec 0 − 104 , pravý sloupec 0 − 105 . Spodní řádek reprezentuje počet potřebných aktivních FT (B = 1Mbs−1 , LRR = 60B). …

3

2

3

x123

4 5 6 Počet of přijímačů number receivers

4 5 6 počet přijímačů number of active FTs

Přibývají FT ve druhé vrstvě

2

105 přijímačů

…

7

7

x1 hlavní cíl zpětné vazby

8

8

9

9

4

10

x 10

4

10

x 10

3.1.2

Přijímač

Úkolem přijímače je přijímat aduiovizuální data, zobrazovat je a přehrávat je. Mimo to je dobrý zvyk signalizovat vysílači kavlitu příjmu, které jsou posílány ve formě RR paketů. Oproti standardnímu RTP/RTCP protokolu [73] jsou tyto zprávy směrovány nikoli přímo vysílači, ale některému z cílů zpětné vazby. Dojde tak k rozprostření zátěže mezi několik síťových stanic a zamezí se tím zahlcení vysílače či velmi dlouhým periodám TRR pro vysílání RR zpráv. V odeslaných RR zprávách je mimo jiné obsažena informace o kvalitě příjmu, která je vypočtena podle standardu protokolu RTP/RTCP. Přijímač bude zpravidla zákazníkovi doručen jako samostatná aplikace instalovatelná jako klasický software, či v podobě set-top boxu, který bude dekomprimovat audio/video data a převádět do formátu kompatibilním s rozhraním, které podporují televizní přijímače dnes dodávané na trhu.

3.1.3

Cíl zpětné vazby

Cíl zpětné vazby (FT) je prvek, který ve standardním protokolu RTP/RTCP není definován. V sísti je jich několik a jejich role je taková, aby sbíraly zprávy přijímačů RR o kvalitě příjmu, odstranily redundantní a irelevantní část informace a v podobě zprávy RSI doručily vysílači statistiky o kvalitě příjmu. Tyto FT stanice tvoří ve skutečnosti jakousi hierarchickou stromovou strukturu, kde FT nejnižší vrstvy stromu sbírá zprávy přijímačů. Ostatní FT potom opět provádí agregaci informace z předešlých FT a předávají ji dále do vyšší vrstvy hierarchického stromu až se informace dostane ke kořenovému FT, který získá informaci o celé síti. Aby bylo možné realizovat nad jedinou množinou více hierarchických stromů, každý FT bude udržovat tabulku s indexací cíle zpětné vazby pro každý uzel. FT bude v reálném síťovém prostředí vypadat jako samostatný dedikovaný server. V tomto případě by bylo nerozumné na jedné stanici spouštět více instancí této aplikace, jelikož bychom vytížení nikterak neulehčily. Navíc v krajním případě se bude jednat o stanici vytíženou sběrem RR či RSI zpráv a jejich agregací do nové RSI zprávy.

29

4

ODHAD VZÁJEMNÉ POLOHY STANIC NA ZÁKLADĚ LATENCE

Výkonnost většiny distribuovaných aplikací, jakou nepochybně je i hierarchická agregace, úzce závisí na latenci komunikace mezi účastníky spojení (např. [19], [80]). Pro tyto účely bylo navrženo mnoho metod, od tzv. měření proxy [29], [78], přes uchovávání pozičních značek [72], až po metody decentralizovaného síťového zakotvení [27], [59], [66], [76], [82], [34]. Jako nejzajímavější metodou se ukázaly být metody decentralizovaného síťového zakotvení, kde měření vzdáleností mezi stanicemi je transformováno do nízkodimenzionálních prostorů. Každý uzel potom udržuje informaci o svých síťových souřadnicích v umělém prostoru. Na jejich základě je potom možné odhadnout vzdálenost i k těm stanicím, mezi kterými nebylo provedeno měření. Výsledkem je výrazná úspora šířky pásma, zvlátě z toho důvodu, že je možné provádět jen malé množství měření. Druhou příčinou úspory je, že sdělovat informaci o poloze v prostoru zabírá výrazně méně bytů, právě díky tomu, že je nyní reprezentován pouze v nízkodimenzionálním umělém prostoru. Na adresu souřadnicových systémů se také objevila kritika, že jsou vysoké požadavky na jejich provoz a mají menší přesnost nežli přímé metody měření. Někteří odpůrci dokonce tvrdí, že se jedná o nespolehlivou a neprověřenou myšlenku. Kritika se zpravidla opírá o oprávněné tvrzení, že všechny tyto metody mají hlavním předpokladem, že v síti se nesmí (nemělo by) objevovat porušení pravidla trojúhelníkové nerovnosti [87]. To je bohužel nemožné a často se vyskytuje. Na druhou stranu obhájci souřadnicových systémů argumentují faktem, že chybovost je v průměru 11% (od 8% do 15%). To je uspokojivý výsledek, uvážíme-li, že prostor sítí není homogenní s euklidovskými prostory, a že samotné měření není vždy přesné ani v klasické podobě. Měření samotné latence může být, a často i bývá, postiženo chybou vlivem dočasných problémů v síti atp. Pozitivní vlastnosti a stabilitu potvrzují dlouhotrvající měření (několik měsíců) experimentální síti PlanetLab [51], [67], [51] a dokonce byly provedeny měření, jak uvádějí sami autoři publikace, “v divočině” [50], které opět dávají uspokojivé výsledky. Autoři tím mají na mysli prostředí běžných uživatelů a nikoli prostředí experimentální sítě.

4.1

Odhad pozice v síti

Pro rozsáhlé distribuované aplikace, jako jsou například peer-to-peer (P2P) sdílení dokumentů, tzv. overlay multicast aplikace či rozprostřené ukládání dat, dokáže správná organizace koncových uzlů v sezení výrazně ovlivnit celkovou spotřebovanou šířku pásma. K tomu, aby stanice znaly vzdálenosti vůči ostatním aplikacím, existuje

30

monžství přenesených dat [GB]

jednoduchá cesta - prostým změřením latence ke kandidátním uzlům. V prostředí sítě, kde by existovalo N stanic, by to tedy znamenalo N ∗ (N − 1) měření. Uvážímeli velikost jednoho ICMP paketu 8 bytů, znamená to pro nás přenos dat jaký je znázorněn v obrázku 4.1, kde je patrné, že se jedná o nezanedbatelný datový tok.

počet komunikujících stanic [-]

Obrázek 4.1: Množství přenesených dat při měření vzdáleností mezi stanicemi způsobem každý s každým. Velikost ICMP paketu je 8 bytů.

S tímto problémem se snaží vypořádat tzv. souřadnicové systémy. Jednou z metod pro určení pozice v síti je tzv. trojúhelníková heuristika. Pro ni se ukázalo jako nejspolehlivější a nejpřesnější zjišťování vzdálenosti mezi stanicemi podle spodní meze vzdálenosti [59], jak je popsáno rovnicí 4.1: U = mini∈{1,2,...,N } (|dH1 Li + dH2 Li |) [−],

(4.1)

kde H1 , H2 představuje stanice, mezi kterými je vzdálenost měřena, Li kde i = 1, 2, . . . , N představuje poziční body. Mezi metody pro určování vzdáleností patří metody jako IDMaps [27], trojúhelníková heuristika [59], Global Network Positioning [59], Vivaldi [18], Hilbertovy křivky [1] a další. Problémem většiny metod, zde zmíněných, je skutečnost, že vychází z předokladu, že směrování je prováděno ideálně. To bohužel v praxi není pravda. Například pro všechny tojúhelníkově uzavřené okruhy, které jsou tvořeny cestami (a, b), (b, c) (a,c) a (c, a), které byly změřeny, celých 7% poměrů (a,b)+(b,c) bylo větších než jedna [28].

31

4.2

Odhad pozice pomocí IP adresy a reverzních záznamů

Jednou z možností, jak předpovídat polohu stanice v síti Internet, je s využitím IP adresy a reverzních záznamů. Co je v kontextu této kapitoly nutno zmínit je fakt, že prostý odhad na základě hodnoty IP adresy možný není. Přidělování IP adres není na polohu strojů nikterak vázáno a dvě velice podobné adresy mohou být vzájemně topologicky velice vzdálené. Naštěstí existují prostředky, pomocí kterých lze stanice podle její IP adresy alespoň odhadnout. I tak, jak bude demonstrováno později, není přesnost této metody příliš vysoká. Odhad pozice stanic pracující s hodnotami IP adres využívají databáze organizací. Celosvětovou zodpovědnost za přidělování adres náleží organizaci Internet Assigned Numbers Authority (IANA)1 . Do konce poloviny řídila přidělování adrres IPv4. V současné době, hlavně z důvodu docházejícího prostoru adres IPv4, se zabývá zejména přidělováním adres IPv6 a komunikaci typu multicast. Zodpovědnost za přidělování adres IPv4 byla delegována na organizace s regionální působností. Organizace s regionální působností jsou AfriNIC2 pro oblast Afriky, APNIC pro oblast Asie a Pacifiku, LACNIC3 pro oblast Latinské Ameriky a Karibiku, ARIN4 pro severní Ameriku a Résaux IP Européens Network Coordination Centre (RIPE NCC)5 pro Evropu, Střední východ a centrální Asii. Organizace RIPE NCC mimo jiné spravuje databázi RIPE. Tato databáze zahrnuje IP adresy, autonomní systémy, údaje o organizacích a uživatelích svázaných s IP adresami, popř. s autonomními systémy. U všech eviduje kontaktní údaje (tzv. Point sof Contact (POC)). Na základě těchto údajů pak lze následně odhadovat fyzickou polohu zařízení, vázanému ke konkrétní IP adrese. Veškeré údaje o IP adresách z databáze RIPE jsou volně k dispozici na adrese www.ripe.net a lze je také dotazovat s pomocí nástroje whois. Další alternativou, jak zjišťovat polohu stanice podle IP adresy, je s využitím Domain Name System (DNS) záznamů. Tento systém slouží k překladu doménového jména na základě její IP adresy. Lze však použít i reverzní překlad, kde k IP adrese získáme doménový záznam. Lze tak získat například i informaci o přesném umístění stroje v rámci jedné organizace. Nevýhodou DNS záznmů je, že tato položka je nepovinná, a tudíž mnoho IP adres touto informací ani nedisponuje. 1

Informace Informace 3 Informace 4 Informace 5 Informace 2

o o o o o

této této této této této

organizaci organizaci organizaci organizaci organizaci

jsou jsou jsou jsou jsou

dostupné dostupné dostupné dostupné dostupné

na na na na na

adrese adrese adrese adrese adrese

32

http://www.iana.net. http://www.afrinic.net. http://lacnic.net. https://www.arin.net. https://www.ripe.net.

4.3

Měření vzdálenosti pomocí latence

Aby bylo možné odhadovat strukturu sítě podle latence, je nutné vzít v úvahu její topologii. Členění dnešní sítě z pohledu její struktury lze na lokální (LAN)6 a rozsáhlé (WAN)7 . Charakter těchto sítí se podstatně liší jak z pohledu struktury sítě, používaných hardwarových prvků, tak z pohledu využívaných protokolů. Sítě LAN jsou převážně doménou přepínačů, které již v dnešní době téměř nahradily opakovače (huby). Přepínače jsou prvky, které zpravidla pracují na druhé vrstvě modelu ISO/OSI a tedy pracují nanejvýše na úrovni MAC adres. Díky rostoucím nárokům na hardware v sítích LAN se objevila také technologie virtuální sítě LAN (VLAN), která bez ohledu na fyzickou podobu sítě dokáže logicky oddělit komunikaci v rámci jediné fyzické LAN na několik logických podsítí. Stále častěji se také objevují tzv. L3 přepínače, což značí, že pracují na úrovni třetí vrstvy modelu ISO/OSI (tj. nejčastěji na úrovni IP protokolu) a dokážou tak částečně nahradit úkol směrovače pro směrování v rámci jednotlivých VLAN. Protokoly, které mohou mít vliv na parametry sítě LAN, jsou zpravidla relativně jednoduché. Nejčastěji používaný protokol na úrovni spojové vrstvy je technologie ethernet. V rámci sítí LAN bývá obecně dosahováno jak vysokých přenosových rychlostí, tak vysoké kvality parametrů sítě. Fyzické připojení je zpravidla v podobě topologie hvězda, ale logické fungování je v podobě topologie sběrnice díky funkci přepínačů typu 1:1. Sítě WAN slouží k propojení sítí LAN. V rámci sítí WAN jsou naopak uplatňovány směrovače, které zpravidla pracují na L3 vrstvě modelu ISO/OSI, tj. nejčastěji na úrovni protokolu IP. V rámci sítí WAN je možné využít tři základní typy konektivity: pronajatou linkou, přepínané okruhy a přepínané pakety. První varianta bývá zpravidla nejkvalitnější z pohledu parametrů síťového připojení (zejména latence a kolísání latence). Mezi protokoly, které realizují paketově přepínané okruhy, patří např. X.25, Frame Relay či Asynchronous Transfer Mode (ATM). V síti Internet převládá technologie Frame Relay, a tím má také největší vliv na charakteristiky parametrů sítí. Struktura této sítě je zpravidla mřížka a to v ideálním případě plně propojená, v praxi se jedná o částečně propojenou mřížku či topologii hierarchického stromu. V síťovém prostředí je prakticky nemožné zjišťovat přesnou polohu každé stanice. Jako poměrně stabilní a spolehlivá metoda se z pohledu relativních vzdáleností v síti ukázalo měření tzv. RTT pomocí protokolu ICMP a paketu typu ECHO REQUEST. Jedná se o nízkoůrovňový protokol. Jakmile některá stanice obdrží tento druh paketu, okamžitě posílá odpověď ve formě tzv. ECHO REPLY paketu a doba, 6 7

Z anglického Local Area Network Z anglického Wide Area Network

33

která uplyne mezi vysláním a obdržením odezvy se nazývá RTT. Co je při pohledu na strukturu sítí (viz obrázek 4.2) zřejmé na první pohled, je, že topologie sítí nemůže společně s Euklidovským prostorem korespondovat zcela přesně a nejsou to ani homogenní prostory. I přes tuto skutečnost je vcelku překvapivé zjištění, že doba RTT příliš nezávisí na topologii sítě a naopak geografická vzdálenost mezi stanicemi má podstatný vliv [59], [76]. Experimentálně bylo ověřeno, že pro 3D prostor a speciální prostor 2D+výška (výška je měřena Manhattonskou metrikou) [57] dávají dobré výsledky. Svojí přesností předčí i než vícenásobné prostory. Na základě měření v celosvětové experimentální síti Planetlab a i na základě hlubšího zkoumání jiných výzkumných týmů se ukázalo, že střední odchylka se právě díky nehomogenně prostorů liší v průměru 11%. Uvážíme-li fakt, že měření bývá postiženo zpožděními či dokonce výpadky sítě, jedná se i tak o poměrně spolehlivou a přesnou metodu.

Obrázek 4.2: Přibližná struktura hierarchické podoby sítě.

4.4

Souřadnicové systémy pro odhad vzdáleností mezi stanicemi

4.4.1

Síťový souřadnicový systém Global Network Positioning

Metoda Global Network Positioning (GNP) na základě několika publikací prokázala velice dobré výsledky [59], [66] a jeví se jako jedna z nejpřesnějších metod. Výpočet u ní probíhá ve dvou samostatných krocích: nejdříve je provedeno založení množiny pozičních značek a až následně je prováděna predikce pozice jednotlivých stanic.

34

Poziční značky jsou stanice v síti, které mají specifickou roli. Jejich pozice v síti musí být známa a vytváří jakousi kostru, o kterou se predikce stanic v síti opírá. S využitím těchto pozičních značek jsou tak ostatní stanice schopny odhadnout svou pozici a současně není generován vysoký provoz na síti. Rovnice, která ustavuje pozici pozičních bodů v síti je záležitostí hledání minima následující funkce: f (cS1 , . . . cSN )

=

N X

ε(dLi Lj , dSLi Lj ) [−],

(4.2)

Li ,Lj ∈{L1 ···LN }|i<j

(4.3)

N = n · D [−].

Proměnná n představuje počet pozičních bodů, D představuje dimenzi, kterou je popsána pozice stanice v síti, dLi Lj představuje změřenou vzdálenost mezi pozičními body Li a Lj , dSLi Lj představuje vypočtenou vzdálenost mezi poziční body Li a Lj , ε představuje druhou mocninu chyby a funkce f (cS1 , · · · , cSN představuje celkovou sumu chyb ε. Proměnnými této rovnice jsou naměřené vzdálenosti RTT a je hledáno takové rozložení pozičních bodů, pro které je hodnota funkce f minimální. [72], [59] Měření vzdáleností je realizováno prostřednictvím protokolu ICMP, který je používán například nástrojem ping. Měřená vzdálenost odpovídá časovému zpoždění RTT mezi požadavkem na stanici a její odpovědí. Přestože se rovnice na první pohled může zdát složitá, je postavena na jednoduché myšlence. Známé proměnné této rovnice jsou naměřené vzdálenosti mezi jednotlivými pozičními body a neznámou jsou takové souřadnice pozičních bodů, pro které dává rovnice nejmenší výslednou chybu. Jedná se tedy o hledání minima této funkce, která má N (viz rovnice (4.2)) vstupních proměnných, kde tyto vstupní proměnné představují celkovou chybu. Pro ilustraci nepřesného rozložení uzlů obr. s velkou chybou a naopak přesného rozložení obr. s chybou rovné nule. Podmínka nejmenší odchylky je splněna tehdy, odpovídá-li pozice pozičními body skutečné pozici. Rovnice tedy porovnává všechny změřené vzdálenosti v síti mezi všemi naměřenými vzdálenostmi v umělém prostoru mezi všemi pozičními body, porovnává tyto vzdálenosti a vypočte sumu chyb. Nalezení optimálního rozložení souřadnic je potom záležitostí hledání minima této funkce. S využitím tohoto algoritmu jsme dokonce schopni vytvořit množinu pozičních bodů z obyčejných stanic, jejichž skutečnou polohu neznáme, ovšem bez jakékoli relevance k nějakému skutečnému souřadnému systému, například pozici na mapě. Druhá část algoritmu určuje pozici regulérních stanic. Je obdobná předchozí variantě s tím rozdílem, že hledáme pozici pouze jedné stanice. Známé proměnné veličiny této rovnice jsou vzdálenosti naměřené prostřednictvím ICMP protokolu mezi stanicí a jednotlivými pozičními body. Další známé proměnné této rovnice jsou

35

2

3

výsledná odchylka funkce GNP

1 3

4

2 vst up

ní p fun aram kce et ry

4

1

y metr

ra ní pa vstup unkce f

výsledná odchylka funkce GNP

Obrázek 4.3: Příklad výsledné hodnoty funkce GNP pro souřadnice, které neodpovídají skutečnosti. GNP dává velkou výslednou odchylku. Problém je pro názornost zobrazen ve 3D funkci, přestože se ve skutečnosti jedná o 9D prostor.

33

11

vs tu

22 pn íp fun aram kc e etry

y metr para í n p vstu unkce f

44

Obrázek 4.4: Příklad výsledné hodnoty funkce GNP pro souřadnice, které odpovídají skutečnosti. GNP dává velkou výslednou odchylku rovnu 0. Problém je pro názornost zobrazen ve 3D funkci, přestože se ve skutečnosti jedná o 9D prostor.

36

vzdálenosti mezi stanicí a jednotlivými pozičními body, které může stanice změřit. Potom je určení pozice stanice dán pomocí hledání minima následující funkce: f (cSH ) =

X

ε(dLHi , dSLH ) [−].

(4.4)

i

Li ∈{L1 ···LN }

V případě rovnice 4.4 se jedná o D-dimensionální funkci a počítá se celková chyba mezi naměřenými a vypočtenými hodnotami mezi stanicí H a pozičními body Li ∈ {L1 · · · LN }.

4.4.2

Síťový souřadnicový systém Vivaldi

Síťový souřadnicový systém Vivaldi [18], [56] je další metodou pro předpověď pozice stanic v síti. Její obrovskou výhodou oproti GNP je skutečnost, že metoda Vivaldi je zcela decentralizovaná a netřeba počítat polohu všech stanic na jednom jediném místě, jak tomu bylo u GNP. Autor algoritmu se inspiroval fyzikálním modelem pružin, kde pozice jednotlivých stanic jsou inicializovány náhodně, a pak dle Hookeova zákona pozice konvergují k rozložení, kde souhrnná potenciální energie systému je minimální. Každý uzel v síti si náhodně zvolí jistou množinu nejbližších sousedů, následně k nim provádí dotazy a zpřesňuje svou pozici tak, aby RTT odpovídala vzdálenosti v umělých souřadnicích.

Lokální 1

2

Dotazované stanice

X Nedotazované stanice X 3

Obrázek 4.5: Schéma principu fungování metody typu Vivaldi. Nejprve se zvolí náhodný uzel, následuje změření RTT vzdálenosti (4.2)+(4.3) a zjištění jeho pozice v umělém souřadnicovém systému (4.3). Následuje přizpůsobení polohy (4.4), který má za cíl minimalizovat výslednou chybu.

Podobně jako metoda GNP, také metoda typu Vivaldi využívá umělé souřadnicové systémy pro určení pozice stanic v Internetu. Principem této metody je najít takové souřadnice stanic, které minimalizují chybu predikované hodnoty RTT mezi 37

těmito stanicemi. Definujme dLi ,Lj jako hodnotu RTT mezi stanicemi Li a Lj . Dále pomocí xi a xj označme souřadnice stanic Li a Lj ve zvoleném souřadnicovém systému. Možným způsobem jak vyjádřit celkovou chybu souřadnicového systému E lze potom pomocí vzorce 4.5: XX E= (dSLi ,Lj − dLi ,Lj )2 [−], (4.5) i

j

kde dSLi ,Lj představuje vzdálenost v souřadnicovém systému a dLi ,Lj představuje skutečnou vzdálnost naměřenou například pomocí metriky RTT. Způsob, jakým celá skupina prvků konverguje k řešení je založeno na tzv. aktualizaci pozice. Ta periodicky aktualizuje polohu tak, aby se výsledná chyba systému zmenšovala. Aktualizace pro každý uzel j potom mezi lokálním uzlem i probíhá, jak je popsáno v aktualizačním algoritmu 1. dLi ,Lj představuje vzdálenost mezi uzly Li , Lj v umělém − souřadnicovém prostoru, δ představuje časový krok, vektor → xi představuje polohu → − v souřadnicovém systému uzlu Li , funkce u( xi ) určuje vektor směru aktualizace polohy uzlu i. Dále konstanty α, ce , cc jsou ad-hoc zvolené hodnoty, ovlivňující rychlost konvergence a tuhost pružin. Algoritmus 1: Metoda Vivaldi Vstup : RTT ke vzdálené stanici, − Výstup: aktualizovaná pozice → xi 1

ws =

2

ε=

3 4 5 6

εi . . . váha ; εi +εj − → − → |kxi −xj k−li,j | . . . relativní li,j

chyba ;

α = ce × w s ; εi+1 = (α × ε) + ((1 − α) × εi ) . . . aktualizace chyby ; δ = cc × ws . . . časový krok ; → − − − − − − xi = → xi + δ × (k→ xi − → xj k − li,j ) × u(→ xi − → xj ) . . . aktualizace pozice v umělém prostoru ;

4.4.3

Síťový souřadnicový systém Netvigator

Metoda Netvigator [75] (neboli také anglicky network navigator, což odpovídá českému názvu síťový navigátor) je další velice zajímavou metodou, jak předpovídat pozici v síti s pomocí poyičních bodů. Tato metoda předpovídá svoji pozici nejen dle latence, ale také podle samotné struktury sítě. Způsob jakým je struktura sítě zjišťována je obdobný jaký používá relativně dobře známý nástroj traceroute v Unixovém prostředí, popřípadě tracert v prostředí operačních systémů Windows. Dále je zobrazen výstup z tohoto nástroje, kde měření bylo provedeno ze stanice umístěné v rámci fakulty elektrotechniky VUT v Brně vůči serveru www.seznam.cz: 38

t r a c e r t www . seznam . cz T r a c i n g route to www . seznam . o v e r a m a x i m u m o f 30 h o p s : 1 <1 m s <1 m s <1 2 <1 m s <1 m s <1 3 <1 m s <1 m s <1 4 <1 m s <1 m s <1 5 <1 m s <1 m s <1 6 <1 m s <1 m s <1 7 1 ms <1 m s <1 8 3 ms 3 ms 3 9 4 ms 4 ms 4 10 4 ms 4 ms 4 11 4 ms 4 ms 4 12 4 ms 4 ms 5 13 4 ms 4 ms 4 14 4 ms 4 ms 4 Trace complete .

cz ms ms ms ms ms ms ms ms ms ms ms ms ms ms

[77.75.76.3] s w−m e o . f e e c . v u t b r . c z [ 1 4 7 . 2 2 9 . 1 4 6 . 1 ] s u m m i t −m e o . n e t . v u t b r . c z [ 1 4 7 . 2 2 9 . 2 5 3 . 2 5 3 ] h p−t e c h . n e t . v u t b r . c z [ 1 4 7 . 2 2 9 . 2 5 4 . 2 2 5 ] h p−a n t . n e t . v u t b r . c z [ 1 4 7 . 2 2 9 . 2 5 4 . 1 4 1 ] f w−a n t . n e t . v u t b r . c z [ 1 4 7 . 2 2 9 . 2 5 4 . 2 3 0 ] h p−a n t 2 . n e t . v u t b r . c z [ 1 4 7 . 2 2 9 . 2 5 3 . 2 3 3 ] r 9 8 −b m . c e s n e t . c z [ 1 4 7 . 2 2 9 . 2 5 2 . 1 7 ] r 8 4 −r 1 0 5 . c e s n e t . c z [ 1 9 5 . 1 1 3 . 1 5 6 . 1 6 5 ] nix2 . d i a l t e l e c o m . cz [ 1 9 4 . 5 0 . 1 0 0 . 9 9 ] c z−p r g −c r 1 −t t c −10 g e 1 −2. d i a l t e l e c o m . c z [ 8 2 . 1 1 9 . 2 4 5 . 1 4 1 ] 212.80.65.161 s e z n a m 1 . d i a l t e l e c o m . cz [ 8 9 . 2 3 5 . 0 . 3 0 ] 77.75.72.253 www . seznam . cz [ 7 7 . 7 5 . 7 6 . 3 ]

Tabulka 4.1: Ukázka výpisu cesty v síti prostřednictvím nástroje tracert.

4.4.4

Síťový souřadnicový systém Myth

Dochází-li v systému často k připojování a odpojování uzlů, je tím do systému zanášena chyba, která v krajních případech může rozkmitat celý systém a vychýlit jej z přesných hodnot nebo alespoň zabránit systému ke konvergenci k přesným hodnotám [15], [49]. Jako opatření oproti tomuto problému byl navržen souřadnicový systém Myth[15]. Tento souřadnicový systém, při připojení nového uzlu zaměřuje jeho počáteční pozici v systému. Redukuje tak chybu, která je do systému zanášena a pro konvergenci k přesným hodnotám je zapotřebí již výrazně méně kroků. Jakmile se chce nový uzel A připojit do systému Myth, musí nejprve navázat spojení se sousedními uzly. Jedná se zpravidla ty uzly, které již nějakou dobu v systému existují a mají tak dostatek času zkonvergovat k přesným pozicím v rámci celého systému. Jakmile se nově připojující se uzel dozví o dostatečném počtu stanic od ostatních stanic, zahájí uzel A měření RTT vzdáleností k L sousedním uzlům. Hodnota L zpravidla nabývá větších hodnot, než je dimenze souřadnicového prostoru. S využitím těchto vzdáleností je možné vypočítat inicializační souřadnici ICA , která minimalizuje celkovou chybu mezi naměřenými a spočtenými vzdálenostmi od uzlu A k sousedním L uzlům. Algoritmus 2 je přepisem popsaného process připojení nového uzlu v podobě pseudokódu. Myšlenku inicializačních souřadnic je možné považovat za kombinaci distribuovaného systému Vivaldi spolu s algoritmem GNP, či jiného systému, založeném na pozičních bodech. Výpočetní zátěž pro prvotní inicializaci je minimální, protože čas potřebný k výpočtu je řádově kratší, nežli interval mezi jednotlivými aktualizacemi v každém kroku.

39

Algoritmus 2: Myth

13

Connect to Rendezvous Point(rp); Get Neighbor Candidates List(rp); Join Overlay(); Make Connection to Neighbors(); foreach i in Neighbors do d (i ) = Measure Distance to i ; end xi = Initial Coordinates Prediction(d(.),N Cs(.)); Wait(Update Interval); while forever do j = random(neighbors of i ); xi = vivaldi(rtt, xj , ej ); Wait(Update Interval);

14

end

1 2 3 4 5 6 7 8 9 10 11 12

4.4.5

Síťový souřadnicový systém Pharos

Systém Pharos [14], [49] je modifikací distribuovaného přístupu k předpovědi vzdáleností. Vychází z poznatku, že největší chyba v souřadnicovém systému vyniká v případě kombinace vzdálených a blízkých stanic. Pro každý uzel v síti používá vícenásobné souřadnice. Jedna souřadnice je pro lokální měřítko a druhá souřadnice je pro globální rozsah. Pro jednoduchost metoda Pharos operuje se dvěma množinami souřadnic [14] a máme tak dva druhy spojení. Je to základní vrstvové spojení, které je vytvořené náhodně mezi stanicemi, které splňují podmínku vzdálenosti jisté konstanty či poměru oproti ostatní vzdálenostem [14]. Druhým typem je lokální spojení množiny uzel, které je vytvořené náhodně mezi uzly stejné vrstvy. Pro korektní funkčnost algoritmu se uzly musí spojit mezi jednotlivými vrstvami jak v rámci lokáních vzdáleností, tak i v rámci globálních vzdáleností. Pro připojení nové základní vrstvy se vytvoří k náhodných spojení k sousedním vrstvám. Pro vytvoření lokální množiny se vybírají stanice, které napomáhají k seskupování uzlů. Takové stanice se nazývají kotvy. Každý stabilní uzel, který je schopný odpovídat na ICMP zprávy typu REQUEST8 , může zastávat funkci kotvy stejně tak jako některý z internetových serverů. Uzly jsou potom řízené těmito kotevními body a seskupované do různých množin. Pro každý nový uzel je měřena vzdálenost mezi kotvami a je vybrána ta nejbližší, 8

Protokol ICMP je definován v RFC 792, http://www.ietf.org/rfc/rfc792.txt

40

od které je také přebírána množina náležitostí. Na základě zvolené kotvy je vybrána nejbližší skupina k stanic. Hierarchická struktura modelu Pharos je naznačena na obr. 4.6.

Kotva 2

Kotva 1

Kotva 3

Obrázek 4.6: Vzájemné propojení uzlů v systému Pharos.

Algoritmus Vivaldi je použit mezi vzdálenými uzly a současně i v rámci lokálních množin. Souřadnice v rámci lokální množin jsou nazývány lokální síťové souřadnice a naopak souřadnice v rámci jednotlivých množin uzlů jsou nazývány globální souřadnice. Následující algoritmus popisuje postup, jak se nový uzel připojuje do systému Pharos. Nově příchozí stanice nejprve kontaktuje tzv. Randezvous stanici systému. Tento postup je velice podobný způsobu, jak se stanice připojují do peer-to-peer (P2P) skupiny. Jakmile se nově připojená stanice dozví o množině kotevních uzlů, zahájí měření vzdáleností k nim. Připojení pak proběhne k nebližší skupině a to jak na lokální tak globální úrovni. Princip tohoto algoritmu je znázorněný s pomocí algoritmu 3. Po získání globálních a lokálních souřadnic již uzel je schopen určovat vzdálenost mezi libovolnými dvěma uzly. Jsou-li dva uzly ze stejné množiny, tak se jejich vzdálenost počítá pomocí lokálních souřadnic, v opačném případě z globálních souřadnic. Tento hierarchický přístup zlepšuje přesnost předpokládaných vzdáleností, které můžeme definovat následovně:  kx A,local − xB,local k skupinaA = skupinaB , d= (4.6) kxA,local − xB,local k skupinaA 6= skupinaB . Metoda Pharos výrazně zpřesňuje vzdálenosti v rámci krátkých vzdáleností a současně ponechává vzdálenosti v rámci velkých vzdáleností [14].

41

Algoritmus 3: Pharos 1 2 3 4 5 6 7 8 9

Connect to Rendezvous Point(rp); Get Anchors List(rp); Nearest Anchor Distance = ∞; foreach i in Anchors do d (i ) = Measure Distance to i ; if Nearest Anchor Distance > d (i) then Nearest Anchor Distance = d (i ); Nearest Anchor = i ; end

17

end Join Cluster(Nearest Anchor); while forever do j = random(local neighbors of i ); xi.local = vivaldi(rtt, xj .local , ej .local ); j = random(global neighbors of i ); xi.global = vivaldi(rtt, xj .global , ej .global ); Wait(Update Interval);

18

end

10 11 12 13 14 15 16

42

5

LIMITY HIERARCHICKÉ AGREGACE

Hierarchická agregace, jak se vyskytuje v současném stavu návrhu, je robustní metoda, jak lze shromáždit signalizaci od obrovského počtu příjemců a to ve velice rychlém čase [6], [7], [33], [5], [45], [43]. Přesto všechno existují slabší místa, kde se je nejprve pokusíme označit a až na jejich základě budeme navrhovat řešení [47]. Jsou to: 1. Rozložení FT pro agregaci signalizace je náhodné, a tudíž může být neoptimální. 2. Komunikace správce správce FT stanic (FTM)1 spolu s FT stanicemi je centralizovaná [61] a může být úzké hrdlo pro škálovatelnost rozsáhlých systémů. 3. Předpověď polohy stanic s využitím vektorů [61] kompromisem mezi přesností a velkým přenosem dat. Hlavní motivací při dosavadní práci bylo, vypořádat se všemi těmito problémy a navrhnout schůdné řešení, které by v maximální míře poskytlo zefektivnění a umožnilo škálovatelnost do obrovských počtů příjemců. Na základě analýzy řady materiálů se ukázalo být poměrně slibné integrovat hierarchickou agregaci se souřadnicovými systémy. S jejich pomocí lze s relativně malými náklady na režijní komunikaci dostatečně škálovat celý systém i pro velké počtz přijímačů ve skupině. Postup pro řešení tohoto problému je následující. V první fázi budou realizovány simulační metody, které umožní získat reálné výsledky jednotlivých simulačních nástrojů a zvolit nejvhodnější z nich. V druhé fázi budou navrženy algoritmy a matematické vztahy, které umožní navrhnout optimální strukturu hierarchického stromu za každé situace. Dále bude nezbytné navržené matematické a algoritmy vztahy zasadit do prostředí distribuovaného síťového systému a navrhnout konkrétní protokol, který celou komunikaci zajistí. Nakonec je nezbytné ověřit celý protokol v prostředí reálné sítě a ověřit její funkčnost.

1

Bližší význam a funkce stanice FTM bude objasněna v následujích kapitolách.

43

6

SIMULACE SOUŘADNICOVÝCH SYSTÉMŮ

Kapitola 4 popisuje současný stav vývoje a poznání souřadnicových systémů a zmiňuje jejich hlavní varianty, výhody a nevýhody. Tato kapitola je věnována bližšímu vyšetření jejich vlastností. K tomu byly zvoleny dva přístupy – v prostředí simulace (kde mohou být nějaké aspekty zanedbány) a reálných síťových podmínkách. Oba přístupy mají své výhody i nevýhody. V případě simulačního prostředí lze pohlížet na celý protokol z nadhledu a lze snáze identifikovat případné plýtvání či nepřesnosti, kterým se dá předejít. Simulačním podmínkám se kapitola věnuje v její první části. Na druhou stranu, simulační podmínky nenahrazují prostředí sítě a nemohou zastoupit experimenty v reálné síti. Druhá část kapitoly se věnuje experimentům ve skutečné síti.

6.1

Ideální podmínky

Simulace souřadnicových systémů v ideálních podmínkách byla vytvořena za účelem vyšetření zejména vlastností optimalizačních funkcí a dále pak vlivu rozložení pozičních bodů na výslednou přesnost predikce pozice. Pro jednoduchost a snadnost graficky znázornit výsledky simulace byl použit 2D souřadnicový prostor. Další zidealizování podmínek bylo, že vzdálenost mezi stanicemi je určována na základě Euklidovských vzdáleností dvou stanic v tomto 2D prostoru. To bohužel neodpovídá skutečným vlastnostem sítě, jelikož skutečná topologie sítě internet je komplexní a zřídka kdy lze některou podmnožinu uzlů zcela přesně promítat do 2D prostoru bez nutnosti zanedbání některých jejích aspektů.

6.1.1

Souřadnicový systém GNP

Hlavní motivaci pro realizaci simulačního nástroje byla snaha identifikovat konkrétní příčiny nepřesností při lokalizaci polohy stanice. To je v síťovém prostředí minimálně velice obtížné. Naopak simulační prostředí umožní pohlížet na systém z globálního pohledu a sledovat takové vlastnosti protokolu, které by bylo možné sledovat jen velice obtížně. Předpokladem je, že hlavní píčinou nepřesností jsou měření RTT vzdáleností či je to vinou lokalizačního algoritmu a procesu mapování struktury sítě do prostoru 2D, 3D či 2,5D. Druhá část do jisté míry závisí i na samotném rozložení stanic v síti. Za tímto účelem byl implementován simulační nástroj [71], [56], který umí vizualizovat předpověděné polohy a rozptyl odchylky naměřených

44

hodnot. Vstupní data při tom mohou být parametry, naměřené ve skutečné síti či data zašuměná na základě průměrné odchylky pozorované v síti. Princip výpočtu je znázorněn na obr. 6.1. Neznámé parametry, které chceme určit, jsou pozice jednotlivých stanic v prostoru souřadnicového systému. Naopak známy jsou vzdálenosti mezi jednotlivými stanicemi, které lze měřit s pomocí parametru RTT. V případě, že poloha jednotlivých stanic je taková, že si vzdálenosti RTT odpovídají nejlépe (tj. střední kvadratická chyba je co nejmenší), jedná se o nejpřesnější možné mapování struktury reálné sítě do prostoru virtuálního souřadnicového systému. Úplná matice vzdáleností:

1 2 3 4 1 2 3 4

[?, ?]

[?, ?]

1

[?, ?]

[x1, y1]

3

3

1 2 4

[?, ?]

Souřadnice jsou neznámé

Rekonstrukce pozice stanic pomocí algoritmu GNP.

[x4, y4]

[x3, y3]

4

2 [x , y ] 2 2

Souřadnice jsou vypočtené a známé

Obrázek 6.1: Rekonstrukce skutečné polohy pozičních bodů z matice vzdáleností na základě algoritmu GNP. Matice vzdáleností obsahuje RTT.

Vyšetřované prostory souřadnicového systému byly tři: 2D; 2,5D a 3D. Výhodou 2D prostoru je, že při sdělování polohy souřadnic posílají jen dva parametry nutné k popisu aktuální polohy. Později v této práci bude popsáno, že je potřeba přenášet informace až o několika stovkách stanic. Z toho důvodu nebyly varianty s vyšším počtem dimenzí, nežli jsou 3, ani uvažovány. Na druhou stranu, 3D prostor je průměrně schopen přesněji mapovat strukturu nežli 2D. Na základě měření v prostředí sítě Planetlab se pravděpodobnost předpovědi nejbližší stanic (která nás ve zbytku textu bude zajímat nejvíce) jedná v rozsahu měření RTT s relativní chybou mezi 0 – 1,5 jedná o odchylku přesnosti 3,21 – 9,41 %. V simulačním nástroji lze konfigurovat několik parametrů. Tyto volby mohou být měněny a ovlivňují běh simulace a i její výstupy. Zjednodušená verze je k dispozici také online1 (viz obrázek 6.2). Důvodem, proč se popisem nástroje práce zabývá podrobněji, je skutečnost, že v přesnost předpovědi je silně závislá na konkrétní podobě sítě. S pomocí tohoto nástroje lze odhadnout chování protokolu v dané síti. Jediné co je zapotřebí, je naměření vzdáleností RTT a stanovení průměrné odchylku při tomto měření. 1

Dostupné online ze stránek autora této práce http://www.dinesgroup.org

45

Ovlivnitelnými parametry jsou: počet použitých pozičních bodů, poměr šumu při měření RTT vzdáleností a poloha každého pozičního bodu. Simulovat lze od tří do jednoho sta pozičních uzlů. Tři poziční body jsou pro 2D prostor minimální použitelná hodnota pro odhad pozice. Pro 2,5D a 3D systémy jsou minimem alespoň 4 poziční uzly. Polohu pozičních bodů lze v simulaci snadno měnit s pomocí uživatelského rozhraní. Každý z pozičních uzlů může být označen, jako tzv. fixní či dynamický. Pojem fixní uzel znamená, že jejich poloha je stanovena pevně a netřeba ji stanovovat výpočtem. V simulaci jsou značeny žlutými tučnými okraji (poziční body číslo 1, 2, 3) a neznámé jsou značeny tenkými černými okraji (poziční body č. 4, 5, 6) (viz obrázek 6.2). Pozice dynamických pozičních bodů je odhadována v prvé fázi algoritmu pomocí rovnice (1). Abychom zahrnuli nepřesnosti do našich výpočtů, je k dispozici parametr “poměr šumu”, který by měl být stanoven na základě charakteristiky sítě a průměrné odchylky při měření vzdáleností RTT. Parametr je možné měnit z hodnoty 0 %, která představuje pro naprosto přesné měření, až po 100%. Hodnota 100% naopak představuje, že virtuálně změřená RTT vzdálenost bude zašuměna v rozmezí 0% až 200% její originální hodnoty. Na obrázku 6.3 je znázorněno přidání šumu do simulačního stanovení vzdálenosti RTT. Jak bylo vysvětleno v kapitole 4, existuje nekonečně mnoho rozložení stanic ve virtuálním prostoru, při kterém je podmínka relativních vzdáleností mezi pozičními body optimální. Na základě matice vzdáleností RTT mezi stanicemi a algoritmu GNP jsme schopni dosáhnout nekonečně mnoha identických řešení – výsledná vypočtená pozice může být oproti skutečné otočená, zrcadlená, posunutá anebo i změněná měřítkem. Pokud chceme takové síťové souřadnicové systémy využít i k dalším účelům, například statistickému vyhodnocení lokality diváků v případě IPTV služby, je nutné některým transformacím zamezit a naopak u jiných přidat možnost změny měřítka. Ve skutečné síti může být množina všech pozičních bodů LA = {L1 , L2 , ..., LN } rozdělena na dvě podskupiny: poziční body, jejichž pozici neznáme (značené LU ) a množinu pozičních bodů, jejichž pozici známe LK . Jak je zřejmé, pro poziční body, jejichž pozici známe, nemusíme, počítat jejich souřadnice. Pokud vezmeme tuto skutečnost v úvahu, rovnice 4.2, 4.3 a 4.4 mohou být modifikovány do tvarů rovnic 6.1, 6.2, 6.3, 6.4 a 6.5 [10]. fobj (cSLU1 , · · · , cSLUN ) = εCD + εCD , kde LU 1 , · · · LUN ∈ LU [−], εCD =

X

[ε(S · dLi ,Lj , dSLi ,Lj )]2 [−],

(6.1) (6.2)

Li ∈LK ,Lj ∈LU

εDD =

X

ε(S · dLi ,Lj , dSLi ,Lj ) [−],

Li ,Lj ∈LU

46

(6.3)

0

1

3

4

2

poziční body se známou polohou poziční body s neznámou & odhadovanou polohou skutečná pozice

Obrázek 6.2: Simulační nástroj pro zkoumání vlastností GNP algoritmu.

X

fobj (cSH ) =

ε(S · dH,Li , dSH,Li ) [−],

(6.4)

L∈{L1 ,L1 ,··· ,LN }

S=

P

dS L

,L

i j 2· Li ,Lj ∈LK ( dLi ,Lj ) !N
=

2

P

dS L

,L

i j Li ,Lj ∈LK ( dL ,L ) i

N2 − N

j

[−].

(6.5)

Mnoho symbolů bylo převzato ze specifikace GNP algoritmu. Pro více informací viz kapitola 3 či také [59] anebo [60]. Symbol εCD představuje celkovou kvadratickou chybu mezi naměřenými a vypočtenými vzdálenostmi ve virtuálním souřadnicovém prostoru. Tyto vzdálenosti jsou měřeny mezi pozičními body z množiny známých uzlů a z množiny neznámých uzlů, či jinými slovy přes relaci LK × LU . Symbol εDD představuje celkovou kvadratickou chybu mezi naměřenými a vypočtenými pozičními body z množiny neznámých uzlů (relace LU × LU ) (viz obrázek 6.4. Pro bližší přiblížení, proč je nezbytné, aby bylo alespoň D+1 pozičních bodů pevně zaměřeno (D představuje dimenzi prostoru, se kterým GNP počítá). 47

přidaný šum -20% +20% 3

skutečná vzdálenost

4

zašuměná vzdálenost

Obrázek 6.3: Princip fungování zašumění měřených vzdáleností v simulační aplikaci.

posun

změna měřítka

zrcadlení

3

otočení

3

1

1

3

1

1

3

1

1

3

1

3 3

1

2

4

4

2 4

4

2

2 4

4

2

4

2

3

2

2

4

Obrázek 6.4: Transformace zapříčiňující možnost vícenásobné reprezentace jednoho modelu.

Algoritmus při předpovědi skutečné polohy vychází z předpokladu pouze vzájemných vzdáleností uzlů. Pokud tedy například neuvedeme žádný uzel jako fixní (jehož poloha je pevně stanovena), může být poloha vypočtena tak, že celková chyba bude velice malá, nicméně prostor bude imaginární a nebude příliš relevantní např. k pozici v mapě. Poloha může být v tomto případě posunuta, otočena, zrcadlena a měřítko může být také jiné (odpovídající jednotkám milisekund měřeného RTT). Není ani vyloučeno, a je to dokonce vysoce pravděpodobné, že bude kombinací několika z nich, popřípadě všech tří. Pokud operujeme ve 2D prostoru a přidáme jeden fixní bod, vyloučíme možnost posunutí, nicméně otočení, zrcadlení i změna měřítka stále hrozí. Při přidání dvou fixních bodů již zbývá pouze zrcadlení. U tří fixních se již vyvarujeme všech možných transformací . Pokud tedy je žádoucí mapovat imaginární prostor do nějakého jiného souřadnicového systému, je nutné dodržet následující vztah 6.6: (6.6)

N ≥ D + 1 [−],

kde N představuje počet fixních pozičních bodů, D dimenzi imaginárního prostoru, ve kterém počítáme. Co je v tomto textu představeno nově je měřítkový faktor S a funkce fobj (cSH ), která počítá celkovou chybu přes známé a neznámé poziční body. Měřítkový faktor S je střední hodnotou hodnot RTT vzdáleností mezi pozičními body z množiny známých pozičních bodů LK . Rovnice počítá průměrné měřítko mezi změřenými vzdálenostmi se skutečnými vzdálenostmi, například na mapě. Díky němu jsou 48

pozice v imaginárním a skutečném prostoru vzájemně porovnatelné. Naneštěstí pozice na mapě a struktura sítě nejsou homogenní struktury. Z toho důvodu může být měřítkový faktor S postižen jistou mírou chyby, což i potvrzují měření, která byla prováděna několik stovek hodin v nadnárodní experimentální síti Planetlab (viz později v této kapitole). V každém případě by ale hodnota RTT měla s pozicí například na mapě do jisté míry korelovat. Pro větší názornost viz obrázek 6.5, kde známé poziční body jsou značeny jako K a neznámé jsou značeny jako U. Navíc, díky měřítkovému faktoru S nejsou používány jednotky RTT, ale nějaké více prakticky použitelné.

K

K

U U K Vzdálenosti mezi známými pozičními body Vzdálenosti mezi známými vs. neznámými p.b. Vzdálenosti mezi neznámými pozičními body

Obrázek 6.5: Relace mezi množinou známých poziční body (K) a množinou neznámých poziční body (U).

6.1.2

Mapování z imaginárního prostoru do 2D prostoru

Předpokládejme případ, kdy máme k dispozici pouze omezený počet pozičních bodů (např. 3) a jsou rozmístěny, jako je znázorněno na obrázku A – první v Rumunsku, druhý v Polsku a třetí ve Francii. Pro tento případ jsou výstupy simulace pro stanici umístěnou v Německu poměrně nepřesné. Získané hodnoty pro 500 předpovědí jsou rozprostřeny od středu Německa, přes Švýcarsko a Rakousko až po Itálii. Jak je vidět ve výsledcích simulace na obr 6.5 A), algoritmus pro takovou konfiguraci nedává příliš dobré výsledky. Zejména pokud se blížíme pozičnímu bodu ve Francii, mohlo docházet k velkému odchýlení od skutečné hodnoty. Je zřejmé, že je zapotřebí ještě alespoň jednoho pozičního bodu, který by byl umístěn někde poblíž této pozice. Jestliže známe dostatek pozičních bodů a tedy i takový, který splňuje současný požadavek, je přidání triviální. Ovšem v případě, kdy se struktura 49

sítě dynamicky mění a různé poziční body musejí operativně vznikat na různých místech, nemusí to být vždy jednoduché. A)

B)

0

1

2

poziční body se známou pozicí

3

4

5

dynamicky přidané poziční body skutečná pozice stanice předpověděná pozice stanice

Obrázek 6.6: Optimalizace určení pozice s využitím početně přidaných pozičních bodů. Varianta A) před přidáním poyičních bodů, B) s početně přidanými pozičními body.

Zajímavé zjištění z této části práce je skutečnost, že přestože se v drtivé většině odborných článků [59], [75], [28] dává nepřesnost za vinu nemožnosti mapovat vysoce dimenzionální prostor, jako je síť internet, do některého nízkodimenzionálního prostoru, značný podíl chyby ve většině případů může mít i samotná volba optimalizační funkce. Zde se ukázalo, že optimalizační algoritmy založené na genetických algoritmech dávají vyšší míru přesnosti v porovnání s metodou simplex downhil.

6.1.3

Souřadnicový systém Vivaldi

Kromě simulačního nástroje pro lokalizaci prvků s pomocí GNP byl vytvořen také nástroj s podobnými vlastnostmi ale simulující algoritmus Vivaldi. S pomocí tohoto nástroje lze opět namodelovat přibližnou podobu sítě a a sledovat chování algoritmu (viz obrázek 6.7). Tento algoritmus nakonec nebyl v této práci využit, nicméně byl jednou ze zvažovaných alternativ. Důvodem proč byla tato varianta zamítnuta je skutečnost, že doba konvergence k přesným hodnotám je výrazně delší než v případě GNP. Současně je topologie hieararchické agregace bližší topologii fungování GNP.

50

Výsledky simulace ukazují, že z pohledu doby konvergence je čas delší a pouze aproximuje přesný stav, kolem kterého neustále osciluje. Není tedy schopna dosáhnout tak přesných hodnot jako algoritmus GNP .

30 sec

Skutečná poloha stanice Předpověděná poloha stanice 0

1

2

Stanice se pevně určenou pozicí

Obrázek 6.7: Simulační nástroj pro zkoumání vlastností GNP algoritmu.

6.2

Šíťové podmínky

Podmínky, které jsou ve skutečné síti, bohužel nelze nahradit simulačním prostředím. Užití simulačního prostředí je vysoce přínosné tím, že se lze dívat na celou topologii širším kontextu a lze lépe identifikovat případné nedostatky. Na druhou stranu nicméně neberou v úvahu veškeré skutečnosti a některé důležité aspekty mohou zanedbat. Zejména, že reálná síť není topologicky shodná s prostorem, založeném na Euklidovském měření vzdáleností, ale blíží se spíše stromové hierarchii. Při použití RTT vzdáleností ze skutečné sítě je bohužel přesnost výrazně poznamenána a to směrem k horším hodnotám. Užití ideálních podmínek je vysoce přínosné tím, že dokážou identifikovat chyby vzniklé nedokonalostí optimalizačních technik. To také drtivá většina článků zabývající se problematikou souřadnicových systémů, zanedbává a dává vše za vinu nemožnosti transformovat mnohorozměrný prostor sítě do několika málo dimenzí a zejména, že reálná síť není topologicky shodná s prostorem, založeném na Euklidovském měření vzdáleností, ale blíží se spíše stromové hierarchii. S tím je také spojena občasná kritika souřadnicových systémů za jejich nepřesnost. I přes tuto kritiku dnes již mnohaleté používání především v oblasti peer-to-peer (P2P) sítí přináší neocenitelnou službu a výraznou úsporu šířky pásma.

51

čas RTT [ms]

geografická vzdálenost stanic (km)

Obrázek 6.8: Závislost doby RTT (ms) v závislosti na geografické vzdálenosti (km). Hodnoty naměřeny v experimentální síti Planetlab 2008-05-21.

Za účelem zkoumání vlastností a struktury skutečné sítě byl použita experimentální síť Planetlab [40], [32], [64], [65], kterou se navíc podařilo spojit i s interní sítí počítačových stanic společnosti GTS Novera. Cílem měření bylo, zdali a do jaké míry koreluje geografická vzdálenost spolu se zpožděním RTT mezi stanicemi. Pro objektivnost bylo měření opakováno v různých denních hodinách a v různých dnech v týdnu. Celkové měření trvalo několik stovek hodin. Aby se minimalizovala dočasná chyba sítě, byla každá hodnota RTT měřena 3x s tím, že se použila vždy nejnižší změřená hodnota. Na obrázku 6.8 je potom tato závislost vyznačena. Jak je patrné, závislost není lineární, ale přesto přes 80 % všech měření spadá do velmi úzkého intervalu a pokud nevyžadujeme naprosto přesnou polohu stanice, lze parametr RTT považovat za závislý na RTT vzdálenosti a využít tuto informaci k optimalizace struktury sítě. Dalším zajímavým zjištěním je, že RTT vzdálenost téměř nezávisí na počtu směrovačů mezi nimi (viz obrázek 6.9). Sledování struktury sítě tedy nebude mít výrazný dopad na zpřesění jednotlivých metod.

52

počet směrovačů mezi stanicemi [ms]

geografická vzdálenost mezi stanicemi [km]

Obrázek 6.9: Závislost počtu směrovačů, tzv. “hopů”, v závislosti na geografické vzdálenosti (km). Hodnoty naměřeny v experimentální síti Planetlab 2008-05-21.

Z těchto zjištění a dat naměřených v rámci této části práce se vycházelo i ve zbytku celé práce. Na základě těchto měření byla vytvořena databáze parametrů čítající několik stovek hodin měření parametrů sítě [38]. Ověření fungování lokalizace ve skutečné síti bylo provedeno v práci P. Pospíšil “OPTIMALIZACE PREDIKCE POZICE V SÍTI” [69], kde autor této práce byl vedoucím práce. Práce potvrdila schopnost lokalizovat stanici s dostatečnou přesností s využitím hierarchického modelu, který nakonec byl integrován do zde popisované práce.

53

7

SBĚR SIGNALIZACE PŘIJÍMAČŮ

Jak je patrné z předchozí kapitoly, pro čím více přijímačů má HA signalizaci přenášet, tím více FT stanic je zapotřebí. Pokud je ovšem volba jednotlivých prvků v rámci HA stromu náhodná, je jen malá pravděpodobnost, že její uspořádání bude efektivní. Čím více těchto FT v rámci stromu existuje, tím větší dopad na plýtvání síťovými zdroji bude mít. Tato kapitola se zabývá návrhem a popisem matematických vztahů, které optimálně navrhnou strukturu HA stromu. Při jejich návrhu byl také reflektován častý požadavek zejména menších poskytovatelů - a to navrhnout optimální strukturu i s využitím omezených hardwarových zdrojů. Na záklaě této kapitoly lze určit výšku stromu, počet FT stanic v jednotlivých vrstvách stromu a celkový počet potřebných FT stanic. Tím dává základní informace o podobě stromu.

7.1

Návrh algoritmu pro rozložení stanic FT

Aby bylo možné rovnoměrně rozmístit FT stanice v oblasti vysílání, byl navržen algoritmus Tree Transmission Algorithm (TTA), který je schopen nalézt množinu aktivních FT stanic tak, že rovnoměrně pokrývá množinu přijímačů a určuje výšku jednotlivých FT stanic ve stromové struktuře [54]. Algoritmus nejprve určí výšku stromu HFT (n), kde argumentem funkce je počet přijímačů n a počet FT stanic nezbytných pro jednotlivé úrovně LFT (n), kde argumentem funkce je v tomto případě nižší vrstva stromu, než pro kterou chceme zjistit počet přijímačů. N5 je počet stanic připojených k jedné FT stanici, aby výsledná perioda TRR byla rovna 5 s1 . Tato hodnota je zpravidla neměnná během trvání vysílání a je zejména ovlivněna šířkou pásma. Na obrázku 7.1 je znázorněn průběh výpočtu algoritmu TTA. Na obrázku 7.1a, je znázorněno počáteční rozložení FT stanic. Nutno poznamenat, že před ustavením stromu, je nutné znát všechny parametry stromu, tj. počet vrstev stromu a kolik má být v jednotlivých vrstvách zapotřebí FT. Sanovením těchto parametrů se bude věnovat tato kapitola později. Samotnému výpočtu se tato sekce nevěnuje a všude budeme předpokládat, že na základě předpokládaného počtu přijímačů, je požadován HA strom výšky 2 s jedním kořenovým FT, a pěti FT ve druhé vrstvě stromu. Poskytovatel má k dispozici 10 FT a ty jsou rovnoměrně rozmístěny po 1

Konstanta 5 s vychází z RFC 3550 [73], která byla odvozena na základě empirických zkušeností s protokolem RTCP. Jedná se o racionální poměr mezi frekvencí posílání zpráv a využitím šířky pásma. Současně konstanta 5 s využitá v hierarchické agregaci také vyhovuje většině současným aplikacím na sběr signalizace. Z toho důvodu je tato konstanta ponechána.

54

(a) Počáteční stav sítě

(b) Výběr kořenového FT

(c) Aktivace FT ve druhé vrstvě HA stromu

(d) Připojení přijímačů ve stromu

Obrázek 7.1: Příklad aplikace algoritmu TTA na síť poskytovatele. 55

Algoritmus 4: Tree Transmission Algorithm Vstup : Množina všech přijímačů R a cílů zpětné vazby F + jejich pozice v souřadnicovém systému Výstup: Množina aktivních FT: FA 1 2 3 4 5 6 7 8 9 10

nastav všechny FT z množiny F jako pasivní: FA = ∅, FP = F ; foreach vrstvu HA stromu l := 0 to HFT (n) − 1 do rozděl množinu FPl+1 z nižší vrstvy l + 1 do nlFT shluků Sj ; foreach s ∈ Sj do vypočti střed clusteru s (tzv. cluster c); z množiny FP vyber nejbližší FT fNEAREST vůči centroidu c; aktivuj fNEAREST : FA = FA ∪ fNEAREST , FP = FP \ fNEAREST ; end přiděl fNEAREST aktuální výšku v hierarchické struktuře l ; end

Evropě v místech stanic, které odpovídajím polohám stanic experiemntální sítě Planetlab. Algoritmus TTA zahajuje svoji činnost výběrem kořenového FT. Nejprve na množinu všech FT (popřípadě těch FT, kde se předpokládá sledovanost daného pořadu) aplikuje algoritmus k-means [52], popřípadě k-median [83]. Z nich se určí tzv. centroid, který představuje ideální střed nad množinou stanic FT (v obrázku je znázorněn fialovou oblastí). Jedná se o ideální střed, kde by měla hledaná FT stanice měla být umístěna. V ideálním případě by měl být na tomto místě spuštěna FT stanice. Jelikož je v praxi nerealizovatelné vždy na požadované místo nalézt vlastní server, je zvolen opačný přístup – poskytovatel z pevně rozmístěných FT stanic vybere tu, která je nejblíže k vypočtenému centroidu. Tato stanice je potom pověřena zastávat funkci kořenové FT (viz obrázek 7.1b). Algoritmus nyní pokračuje výběrem aktivací dalších FT stanic ve druhé vrstvě stromu. Jedná se o poslední vrstvu stromu a tyto FT tedy budou obsluhovat přímo signalizaci přijímačů. Zde je cílem, aby tyto stanice optimálně pokrývaly oblast přijímačů a v ideálním případě, aby každý FT obsluhoval stejný počet přijímačů. Na množinu potenciálních FT je opět aplikována metoda k-means či popřípadě kmedian, kde je nyní hledáno 5 centroidů. Následuje aktivace nejbližších FT stanic (viz obrázek 7.2b). V posledním kroce se připojují přijímače (viz obrázek 7.1d). Máme-li opticky srovnat strukturalizaci sítě, jedná se bezesporu o významné zefektivnění celé komunikace v síti. Na obrázku 7.2 je srovnáno náhodné rozložení bez použití optimalizací společně se architekturou sestavenou pomocí TTP algoritmu.

56

(a) Náhodná volba FT

(b) Výběr FT pomocí algoritmu TTF

Obrázek 7.2: Srovnání náhodné a optimalizované metody pro konstrukci hierarchického stromu. Poloha stanic FT je v obou případech shodná. Komunikace byla zefektivněna o 21,6 %.

7.2

Optimalizace algoritmu TTA

Algoritmus, jak byl navržen v předchozím případě, předpokládá, že uzel, který ustavuje hierarchický strom, zná i souřadnice přijímačů. Uvážíme-li, že přijímačů ve skupině bude pravděpodobně velice mnoho a současně se tyto přijímače budou chovat dynamicky – tj. v náhodných intervalech budou opouštět vysílání a v náhodných intervalech se budou do vysílání přihlašovat, datový tok s tímto spojený by byl značný. Znamenalo by to značné požadavky na internetové připojení této stanice a při jejím výpadku by nebylo možné provádět sběr hierarchické agregace. K tomu, abychom omezili takto závislost na jediném centrálním síťovém uzlu, byl navržen optimalizovaný algoritmus TTA [54]. Algoritmus oproti předchozí variantě požaduje na svém vstupu pouze polohu jednotlivých FT a nikoli přijímačů. Nicméně, jak je z obrázku patrné - centroidy se nepočítají z polohy přijímačů, ale z polohy FT stanic. Vypočtené polohy centroidů je tedy nezbytné přenést směrem k okrajům tak, aby odpovídaly poloze určené pomocí originálního algoritmu TTA. To právě optimalizovaný algoritmus TTA dělá. Vychází z předchozí varianty jen některé kroky modifikuje.

7.3

Zhodnocení algoritmu TTA

K tomu, aby mohl být algoritmus TTA objektivně posouzen, byla vytvořena simulace, která v rozsahu stanic umístěných v rámci Evropy náhodně rozložila 50, 80, 120, 200 a 500 uzlů zpětné vazby. Celá simulace se opírá o parametry

57

Algoritmus 5: Optimalizovaný Tree Transmission Algorithm Vstup : Množina cílů zpětn vazby F + jejich pozice v souřadnicovém systému Výstup: Množina aktivních FT: FA 1 2 3

4 5 6 7

řádky (0) až (4) algoritmu TTA; if aktuální výška stromu l odpovídá kořenovému uzlu (l = 0) then F zjisti maximální vzdálenost δmax mezi kořenovým fRF T a k ostaním FT: F δmax = max(δfRF T ,f |∀f ∈ F ) else Sj zjisti maximální vzdálenost δmax od centroidu cj vůči FT v množině Sj : Sj δmax = max(δcj ,f |∀f ∈ Sj ) ; spočti jednotkoý vektor od centroidu C vůči kořenovému FT fRF T : ψ(c )−ψ(f ) ; v = kψ(cjj )−ψ(fRFT RF T k

8

spočti relativní vzdálenost k polohy centroidu cj vůči kořenovému fRF T :

9

k=K·

10 11 12 13

δcj ,fRFT F δmax

;

end aktualizuj pozici centroidu: ψ(cj ) = ψ(cj ) + k · v; Přiřaď všechny přijímače nejbližšímu centroidu; řádky (5) až (9) algoritmu TTA;

změřených na skutečných stanicích. Hierarchický strom, který měl být ustaven, se skládá z jednoho kořenového FT a pěti FT v druhé vrstvě. Nad těmito strukturami bylo realizováno 500 náhodných výběrů FT stanic, tento výběr byl následně optimalizován prostřednictvím algoritmu TTA a míra zefektivnění komunikace (tj. výsledná délka cest pro hierarchický strom) byl vynesen do grafu včetně relativní odchylky (viz obrázek 7.3). Jak je z grafu patrné, míra zefektivnění je se pro dané parametry pohybují mezi 10-30%. Co se možná může zdát na první pohled překvapující, že míra zefektivnění v závislosti na počtu přijímačů roste. To je způsobeno tím, že přijímače stále vyhledávají nejbližší FT a při velkém počtu přijímačů převládá komunikace přijímač vs. FT nad komunikací FT vs. kořenový RFT. Jelikož na první typ má algoritmus TTA jen miinimální vliv, jeho relativní efektivita klesá s rostoucím počtem přijímačů. Na základě simulací bylo potvrzeno, že vlastnosti jednoduchého a optimalizovaného algoritmu TTA jsou srovnatelné. V čem spočívá jeho zlepšení je, že nevyžaduje, aby byly k dispozici souřadnice přijímačů, ale jen stanic FT, což znamená významné úspory režijního datového toku.

58

nFT = 500

Míra zefektivnění komunikace v síti saved network path length (%)(%)

25

nFT = 200

20

nFT = 120 15

nFT = 80 10

Náhodný výběr

x 5

TTF výběr

x x

x

x

x

x 0

nFT = 50

x x x

0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 6 6.5 7 7.5 8 8.5 9 9.5 10 4 number of receivers Počet přijímačů x 10

Obrázek 7.3: Míra zefektivnění komunikace při náhodném výběru a při použití algoritmu TTA.

7.4

Ustavení stromu při nedostatečném počtu FT

V předchozí kapitole byl předpokládán neomezený počet stanic FT. To ovšem v praxi často není možné zajistit a v takovém případě by strom na základě předešlých vztahů nebylo možné ustavit. Tato kapitola přináší vztahy, pomocí kterých lze ustavit optimální hierarchický strom i s omozenými hardwarovými prostředky. K tomuto účelu je zde představena metoda Best Effort – Tree Transmission Algorithm (BETTA). BE-TTA je z postaven na dříve popsaných vztazích s tím rozdílem, že počet FT není určován na základě počtu přijímačů, ale na základě dostupných zdrojů. Otázkou tedy zůstává, jak vysoký strom použít a kolik FT by v jednotlivých vrstvách mělo být FT stannic. Cílem je, aby celkový čas přenosu signalizace hierarchickým stromem byl minimální. Rovnice 7.2 je obecný vztah pro vyjádření celkového času, než se signalizace dostane od přijímačů až ke kořenovému FT. Neznámé rovnice jsou (0) (1) (h) výška potřebného stromu h a počet FT v jednotlivých vrstvách (nF T , nF T , · · · , nF T )

59

s tím, že jejich suma musí odpovídat počtu dostupných FT (nFT ): Ph

(i)

i=0

(7.1)

nF T = nFT [−]. (0)

Jelikož se jedná stromovou strukturu je zřejmé, že hodnota nFT , kde se nachází kořenová FT stanice, je rovna 1 (viz rovnice 7.3). Použité symboly jsou: počet přijímačů (nR ), počet všech cílů zpětné vazby (nFT ), počet cílů zpětné vazby v h-té vrstvě hierarchického stromu, počítáno od kořene stromu h = 0 (nFT (h) ), šířka pásma vyhrazená pro posílání RR zpráv (BRR ), šířka pásma vyhrazená pro posílání RSI zpráv (BRSI ), délka paketu RR (LRR ), délka paketu RSI (LRSI ): (h)

T (nFT

(h−1)

, nFT

(h−2)

, · · · , nFT

(1)

X nFT (i−1) · LRR nR · LRR + [s]. (7.2) )= nFT (h) · BRR i=1 nFT (i) · BRR

Rovnice 7.2 představuje sumu všech period pro vysílání zpráv RR v případě přijímačů či RSI v případě stanic FT. Pro jednoduchost se předpokládá, že hierarchický strom, který stanice FT tvoří, je ideálně vyvážený, a je tedy pro jednu vrstvu vždy stejná využitá šířka pásma: nFT (0) = 1 [−].

(7.3)

Počet poslední vrstvy lze pak také vyjádřit jako rozdíl počtu všech FT od všech ostatních vrstev (viz rovnice 7.4). Tímto způsobem jsme se zbavili závislosti na dvou proměnných: nFT

(h)

= nFT −

h−1 X

nFT (i) [−].

(7.4)

i=0

Počet poslední vrstvy lze pak také vyjádřit jako rozdíl počtu všech FT od všech ostatních vrstev (viz rovnice 7.4). Substitucí rovnice 7.4 a rovnice 7.3 do rovnice 7.2 se zabvujeme závislosti na dvou proměnných a získáváme rovnici 7.5 a 7.6, které odpovídají výšce stromu 2 resp. 3: nFT (2) · LRSI nFT (1) · LRSI nR · LRR + + nFT (2) · BRR nFT (1) · BWRSI nFT (0) · BRSI (nFT − nFT (1) ) · LRSI nR · LRR + = (nFT − nFT (1) ) · BRR nFT (1) · BRSI nFT (1) · LRSI + [s], 1 · BRSI

T (nFT (1) ) =

60

(7.5)

nFT (3) · LRSI nR · LRR + nFT (3) · BRR nFT (2) · BRSI nFT (2) · LRSI nFT (1) · LRSI + + nFT (1) · BRSI nFT (0) · BRSI nR · LRR = (nFT − nFT (2) − nFT (1) ) · BRR (nFT − nFT (2) − nFT (1) ) · PLRSI + nFT (2) · BRSI nFT (1) · LRSI nFT (2) · LRSI + [s]. + nFT (1) · BRSI BRSI

T (nFT (2) , nFT (1) ) =

(7.6)

Jestliže známe tyto rovnice, popisující varianty výšky stromu, hledání minima funkce je nyní záležitostí hledání kořenů derivace rovnic. ∂T (nFT (1) ) = 0, ∂nFT (1)

(7.7)

∂T (nFT (2) , nFT (1) ) = 0. ∂nFT (1) ∂nFT (2)

(7.8)

(a) Při vyšším počtu FT lze křivku rozdělit na dva(b) Při malém množství FT je trend křivky monotónní polointervaly. rostoucí.

Obrázek 7.4: Závislost výsledné doby na počtu FT v druhé vrstvě stromu. Ačkoli řešení těchto rovnic existuje a lze je analyticky vyjádřit, derivací získáváme polynom čtvrtého řádu, který lze řešit jen relativně obtížně. Rovnice čtvrtého řádu je nejvyšším řádem, který vůbec ještě analyticky řešit lze. V tomto případě se nejedná o žádný ze speciálních případů, a tedy ani neexistuje snadné řešení (tj. ani degenerativní případ, kořeny nejsou na první pohled zřejmé, nejedná se o bikvadratickou rovnici ani kvazisymetrickou rovnici). Pomocí nástroje Matlab lze 61

syms NR PLRR PLRSI BWRR BWRSI N _ FT x ; T2 = . . . ( NR * PLRR ) / (( N _ FT − x ) * BWRR ) + . . . (( N _ FT − x ) * PLRSI ) / ( x * BWRSI ) + . . . ( x * P L R S I ) / (1 * B W R S I ) T2 = s i m p l i f y ( T2 ) d T 2 = d i f f ( T2 , x ) ; dT2 = simplify ( dT2 ) r = s o l v e ( dT2 , x ) ;

Tabulka 7.1: Analytický výpočet extrému funkce pomocí nástroje Matlab. Řešení všech čtyř kořenů rovnice je uloženo na přiloženém CD. tuto rovnici řešit (viz kód v tabulce 7.1) a řešení rovnice je umístěno na přiloženém CD. Výsledný analytický vztah je značně komplikovaný a prakticky nepoužitelný. Z tohoto důvodu byla analytická cesta zavržena a vyhodnocena jako slepá cesta při řešení tohoto problému. Oproti tomu byla upřednostněna cesta optimalizační s využitím multidimenzionální optimalizace prostřednictvím algoritmu SimplexDownHill [58]. Oproti jiným metodám, jako je metoda Hill climbing, genetické algoritmy, či optimalizace pomocí hejn, dávala stabilně velice dobré výsledky a současně byl výpočet otázkou ms na běžném PC. Jak je z 7.4 [8] patrné, trend výsledného času je v závislosti na počtu FT ve druhé vrstvě stromu spojitý a dá se rozdělit na dva monotónní polointervaly. Obdobně tomu je v případě 3-vrstvého stromu u rovnice 7.6. Tím je výpočet relativně rychlý a přesný. Je to dáno také tím, že při výpočtu nás nejen že nezajímají komplexní řešení rovnic, zajímá nás jen řešení v oboru celých čísel Z. Je zřejmé, že např. ve druhé vrstvě nemůže být 2,2 FT stanice ale pouze dvě či tři. Hodnoty optimalizace byly následně ověřeny jak empiricky, tak na základě kontrolních výpočtů z uvedených vztahů. Pro všech 60 náhodných konfigurací (náhodná volba stanic v prostředí sítě Planetlab) byl schopen algoritmus nalézt optimální rozložení hierarchického stromu, tj. 100 % účinnost.

62

8

INTEGRACE

HIERARCHICKÉ

AGRE-

GACE SE SOUŘADNICOVÝM SYSTÉMEM Předchozí kapitola popisuje matematické vztahy a algoritmy, které jsou schopny určit podobu optimálního hierarchického stromu, tj. jeho výšku, počet FT stanic v jednotlivých vrstvách a výběr FT, které mají být v jednotlivých vrstvách aktivovány. Veškeré tyto výpočty probíhají centrálně na jedné stanici, která bude mít na starost správu celého skupiny. Tato stanice se nazývá FT manager (FTM). Cílem této kapitoly je popsat principy výměny dat mezi vysílačem, FTM, FT a přijímači. Cílem je, aby veškeré prvky obdržely potřebné informace, aby mohly správně pracovat. To obnáší aby, 1) stanice typu FTM obdržela matici RTT vzdáleností mezi stanicemi ve skupině, 2) stanice typu FT obdržela informaci o vrstvě, ve které má pracovat, a kam má posílat signalizaci dále a 3) se přijímač R dozvěděl, které stanici typu FT má posílat svoji signalizaci. Tato kapitola se nevěnuje detailnímu popisu protokolu a popisu podoby zpráv, pouze obecným principům principům. Podrobnostem protokolu se věnuje až následující kapitola 9.

8.1

Registrace nově příchozcích FT stanic

Před zahájením činnosti hierarchického stromu je nezbytné inicializovat pozici jednotlivých FT v síti a to hned ze dvou důvodů. Prvně je to nezbytné pro algoritmus TTF, který byl představen v kapitole 7 a který určuje strukturu hierarchického stromu. Dalším důvodem je, aby FT stanice a přijímače mohly vybrat nejbližší hierarchicky nadřazenou stanici a současně to neznamenalo vysokou zátěž při měření RTT vzdáleností. Tento krok lze v případě, kdy je počet FT nízký i vynechat. Jednoduše se RTT vzdálenost změří způsobem “každý s každým”. Nejnižší hodnota potom představuje nejbližší stanici. Schéma, které představuje ustavení polohy RTT je znázorněno na obrázku 8.1. Každý FT, který je nově spuštěn nejprve provede registraci u FTM (krok 1) [10]. Při zaregistrování FT vytvoří FTM záznam v tabulce RTT vzdáleností. S tím je také spojena aktualizace procentuálního naplnění RTT tabulky v procentech (viz rovnice 8.1) na straně FTM. NR představuje počet záznamů v RTT tabulce, kde pro jednu stanici FT může existovat nejvýše 1 záznam RTT. NFT zastupuje počet FT stanic, které jsou registrovány u FTM stanice.

PRTT =

2 · NR · 100% [%]. − NFT )

2 (NFT

63

(8.1)

Množina FT

1

REGISTRACE 2

POŽADAVEK 3

ODPOVĚĎ

FTM

4

RTT tabulka

DEFINICE

Obrázek 8.1: Schéma počátečního ustavení pozice FT stanic.

O tabulku RTT se stará FTM stanice. Jestliže FTM považuje počet RTT záznamů za nízký, požádá některý z nezaměřených FT prvků o zaměření se vůči vybraným jiným FT stanicím (krok 2)[10]. Hodnotu tohoto parametru je vhodné stanovit individuálně, jelikož závisí na rozložení stanic FT v síti (viz kapitola 6). V síti Planetlab bylo empiricky ověřeno, že 80% naplnění pro většinu případů postačuje. Konkrétní chování pro daný případ lze namodelovat s využitím těchto simulačních modelů. Po zjištění požadovaných hodnot FT posílá zpět naměřené hodnoty (krok 3)[10]. Požadavky o zaměření je vhodné opakovat periodicky v daných intervalech. Tuto periodu (viz rovnice 8.3) je doporučeno nastavit na dvaceti násobek délky minimální periody (TREQ MIN ). Délka minimální periody je doporučena 10 s. Současně ve fázi, kdy je RTT tabulka prázdná či téměř prázdná, je žádoucí, aby zaměřování bylo častější. Pro výpopočet délky periody na požadavky o zaměření, jsou k dispozici rovnice 8.2 a 8.3:

TREQ = max(20 · TREQ MIN · PRTT , TREQ MIN ) [s],

(8.2)

TREQ MIN = 10 [s].

(8.3)

Jakmile je na straně FTM stanice dostatek hodnot RTT vzdáleností (doporučuje se PRTT větší či rovno 80 % ), zahájí se mapování stanic do některého umělého souřadnicového síťového prostoru. Variant souřadnicových systémů je mnoho od klasických 2D, 3D, · · · 12D, až po některé speciální jako je 2,5D prostor. 2,5D tu představuje takový prostor, kde poslední rozměr se vypočítává dle Manhattonovské vzdálenosti a nikoli klasické Euklidovské vzdálenosti a právě tento prostor byl použit. Této problematice se blíže věnuje kapitola 4. Po určení polohy všech stanic informuje FTM stanice veškeré FT o jejich polohách (krok 4). Po provedení kroku 4 jsou FT stanice připraveny vykonávat svoji činnost agregačního uzlu.

64

Aby bylo možné reflektovat i změny struktury v síti, k přepočítání souřadnicového systému může docházet i v případě, že dojde k významným změnám ve struktuře skupiny FT. Míru změny v tomto stromě lze vyjádřit rovnicí 8.4: CFT =

NCH · 100% [%], NI

(8.4)

kde NCH představuje součet počtu nově přihlášených a odhlášených FT stanic. NI představuje počet FT při předchozí inicializaci. Pokud ještě k inicializaci nedošlo je tato hodnota inicializována na hodnotu 1. Je samozřejmě nežádoucí, aby k přepočítávání polohy docházel příliš často, protože to spolu ponese značnou režii v podobě potřeby sdělit vypočtené hodnoty všem FT. Jak již bylo zmíněno, je nežádoucí, aby se poloha FT často měnila. Z toho důvodu při výpočtu poloh FT po měla být použita počáteční poloha FT stanic z předchozích hodnot. Pokud se jedná o první výpočet, měla by poloha odpovídat nule. Navíc je možné pomocí speciální zprávy požádat o opětovnou aktualizaci polohy v síti a opětovné nalezení nejbližší stanice.

8.2

Odhlášení FT stanice

Pokud dojde k regulérnímu ukončení činnosti FT stanice (nikoli vlivem poruchy v síti či stanice), FT stanice posílá zprávu, kterou se odhlásí od FTM. Tím FTM ví, že se stanicí nadále nemá počítat a aktivním stromům přidělí náhradníka. Pro případ chyby způsobené poruchou v síti či stanice, existuje princip periodického hlášení FT stanic. Pokud FTM neobdrží 3 za sebou jdoucí zprávy “IS ALIVE” (viz rovnice 8.5), považuje stanice typu FTM stanici FT ve stavu mimo provoz a stanice typu FTM buď najde adekvátní náhradu anebo uzpůsobí strukturu HA stromu nové situaci. Jeho činnost je obnovena ihned, jakmile je stanice typu FT opět k dispozici: TALIVE = r · min(

B , 30s) [s], 64 · NFT

(8.5)

kde funkce min(a, b) vrací menší z hodnot a a b. Pokud FT množství odhlášených či nově přihlášeno dosáhne určitého prahu, dojde k přepočítání polohy ze strany FTM a přepočítání jejich poloh (viz rovnice 8.4).

8.3

Přidělení hierarchického stromu vysílači

Celý hierarchický strom je pojat jako služba, která je schopna na základě požadavku vysílače zajistit patřičné služby vysílači. Jakmile se má zahájit IPTV vysílání, 65

požádá vysílač stanici typu FTM o přidělení hierarchického stromu. S tímto požadavkem je posílána i informace, pro jak velkou hierarchickou skupinu má být vysílání používáno. Na základě toho FTM určí ideální výšku stromu, vypočte počet nutných FT stanic a podle algoritmu TTA a souřadnicového prostoru zvolí potřebné FT stanice (viz kapitola 7) z množiny registrovaných FT stanic. Jakmile je tato informace známa, je vysílači sděleno unikátní identifikační číslo stromu (těchto stromů může existovat paralelně několik a je možné souběžně pracovat pro více vysílačů) a FT stanice z nejnižší vrstvy hierarchického stromu. Na tuto množinu stanic budou přijímače následně posílat svoji signalizaci a vysílač v rámci kanálu RTCP bude sdělovat informaci o jejich poloze v souřadnicovém prostoru a IP adresách v síti, zpravidla prostřednictvím multicastu. Komunikace je naznačena na obrázku 8.2. O zbylých FT stanicích bude FTM informovat prostřednictvím další multicastové skupiny všechny registrované FT stanice (viz obrázek 8.3). Jakmile vysílač ukončí svoji činnost a nepotřebuje nadále sběr signalizace, informuje o tom FTM stanici, která zruší rezervovanou adresu stromu. Množina FT

1

POŽADAVEK 2

ID STROMU FTM

Vysílač

Množina FT

Obrázek 8.2: Poždadavek o ustavení hierarchického stromu

MULTICAST FTM

Obrázek 8.3: FTM prostřednictvím multicastového kanálu periodicky informuje FT o aktuální roli každého uzlu.

66

8.4

Zajištění spolehlivosti FT

Bohužel, v případě většího množství stanic v rámci protokolu také roste riziko selhání. Aby byla zajištěna kontrola případného selhání je kontrola zajištěna pomocí tzv. “IS ALIVE” zprávy. Pomocí těchto zpráv je stanici FTM periodicky, že stanice je funkční a nedošlo např. k výpadku proudu či nenastaly neočekávané potíže v síti. Tyto zprávy jsou vysílány pomocí UDP protokolu a jim je vyhrazena konstantní šířka pásma po celou dobu provozu stanice. Periodu pro vysílání těchto zpráv pak spočte každý FT uzel pomocí rovnice 8.5. BTTP představuje šířku pásma vyhrazenou pro tento kanál zpráv. NFT představuje počet registrovaných FT stanic. r je náhodné číslo s rovnoměrnou distribuční funkcí v intervalu 0,5 až 1,5. Funkce min vrací menší hodnotu ze dvou argumentů, které má na vstupu. Minimální interval pro hlášení se je potom 30 s. Pokud FTM stanice nedostane 3 intervaly žádnou zprávu (tj. 1 min 30 s), považuje danou stanici ve stavu mimo provoz. Hodnota proměnných NCH inkrementována při každém přihlášení či odhlášení nové FT stanice. V případě přepočtení souřadnicového systému ze stranz FTM se vždy nastavuje na nulu. Pokud FT množství odhlášených či nově přihlášeno dosáhne určité hodnoty, dojde k přepočítání polohy ze strany FTM a přepočítání jejich poloh (viz rovnice 8.4). Zajištěním spolehlivosti a stabilitou hierarchické agregace se také zabýval pod vedením autora této práce P. Olivka v rámci diplomové práce s názvem “Stabilita hierarchické agregace pro internetové televizní vysílání” [62].

8.5

Inicializace pozice přijímače

Jak je definováno ve standardu RFC 3550, ihned po připojení začíná každý z přijímačů v přesně daných intervalech (viz rovnice 3.2) posílat zprávy RR. V této zprávě je implicitně obsažena informace o kvalitě příjmu popsaných několika parametry (RTT, kolísání sítě, počet ztracených paketů atd.). Navíc zde mohou být obsaženy dodatečné informace, jako například odpovědní hlas na soutěžní otázku, informace o poloze přijímače či další. Tyto zprávy se souhrnně nazývají signalizace. U standardního RTCP protokolu je RR zpráva odeslána vždy na adresu vysílače. Tato adresa pochopitelně musí být známa, jinak by přijímač nevěděl, ze které adresy má být audio a video obsah přijímán. U protokolu TTP je to z tohoto pohledu mírně komplikovanější. Zpětná vazba není posílána přímo vysílači, ale jednomu z FT, které jsou pro vysílání registrovány. Zbývá tedy popsat, jak zjistit množinu kandidátních FT, kam by signalizace nově příchozích přijímačů měla být vysílána, a který z této množiny je nejblíže a co nejméně vytížen.

67

K tomuto účelu je žádoucí, aby při prvním připojení k dané adrese, bylo poskytnuto minimálně několik náhodně zvolených FT stanic a udána jejich poloha v souřadnicovém systému. Tyto adresy by navíc měly být voleny náhodně a tato volba by měla být rozložena rovnoměrně mezi všechny přidělené FT, aby se předešlo zahlcení některého z nich. Současně sdělovat větší počet těchto adres není vhodné, jelikož by to představovalo výrazný datový objem, který by bylo v rámci režijní komunikace nutné přenášet. Zbytek informací je poté periodicky posílán kanálem vysílače vyhrazeným pro RTCP data. Tyto data jsou posílána periodicky a využívají tak konstantní šířku pásma. Díky tomu, že je přijímač ihned inicializován s jistou množinou FT, je možné odeslat signalizaci i tehdy, není-li přijímač ještě dostatečně zaměřen. V takovém případě se volí náhodná FT stanice. Zaměření přijímače totiž může trvat jistou dobu a není vždy zaručeno, že tato doba bude kratší než interval pro první odeslání signalizace. Jakmile je přijímač spuštěn, ihned se zahájí proces zaměřování, který probíhá ve dvou fázích. Nejprve s využitím vzdálenějších bodů. S jejich pomocí se přijímač zhruba lokalizuje do přibližné oblasti. V druhé fázi přijímač zvolí FT stanice v bližším okolí z předchozí lokalizace a na jejich základě dojde k přesnému zaměření. Princip fungování zaměření pozice stanice byl ověřen v experimentální sítě Planetlab [40], [32], [64], [65] v rámci diplomové práce “Optimalizace predikce pozice v síti” [69] a byla ověřena jeho funkčnost dokonce i v globálním měřítku.

68

9

NÁVRH

PROTOKOLU

PRO

HIERAR-

CHICKOU AGREGACI V předchozí sekci 8 byly popsány principy, které jsou nutné pro zajištění fungování celé hierarchické struktury. Následující sekce bude toto téma dále rozvíjet a bude se věnovat detailům, které popisují konkrétní podobu protokolu. Pro tyto účely je v tomto textu představen protokol Tree Transmission Protocol (TTP) [46], [17], [39],[11], [41]. Protokol vychází z existence protokolu RTP/RTCP a je navržen tak, aby nebyl závislý na ostatních použitých technologiích a bylo snadné jej integrovat s existujícími IPTV systémy. Díky tomu je možné zde popsané technologie integrovat nejen s IPTV systémy, ale i velice snadno s každou jinou technologií, která vyžaduje efektivní přenos signalizace od velkého počtu zařízení. Zbytek kapitoly je organizován následovně. V první části jsou popsány principy výměny dat s použitím konkrétních zpráv a jsou obecně popsány typy použitých zpráv. Následuje popis obecné hlavičky pro protokol TTP a detailní fungování přijímače, cíle zpětné vazby, FT manažera a vysílače a detailní popis podoby jednotlivých zpráv.

9.1

Obecná hlavička přijímače

Obecná podoba hlavičky protokolu TTP je uvedena na obrázku 9.1. Jedná se o hlavičku, která je použita v rámci všech zpráv protokolu TTP, a která zajišťuje rozlišení mezi těmito zprávami. 0

1

Ver

2

3

4

5

Type

6

7

8

9

1 0

1

2

3

4

5

6

7

Tree ID

8

9

2 0

1

2

3

4

5

6

7

8

9

3 0

1

Length

Specific content

Obrázek 9.1: Hlavička TTP paketů

První položka “Ver” uvádí verzi zprávy. “Type” určuje typ zprávy, “Tree ID” je identifikátor stromu. FTM jich může souběžně provozovat několik paralelně a s pomocí něj lze rozlišit, o jaký strom se jedná. Celkem je tedy k dispozici 1024 stromů. “Length” představuje celkovou délku zprávy v bytech zarovnanou na 32 bitů. V části Specific conntent“ je obsažen obsah odpovídající konkrétnímu typu. ” V protokolu existují celkem čtyři typy zpráv: Feedback Target Definition (FTD), Feedback Target Registration (FTR), Feedback Target Information (FTI) a Feedback Target deScription (FTS). Součástí zprávy FTS pak může být součástí

69

několik zpráv Feedback Target deScription LandMark (FTS-LM) anebo Feedback Target deScription cíle zpětné vazby (FTS-FT). Součástí definice zpráv protokolu TTP je i aplikační zpráva určená pro protokol RTCP. Jedná se o zprávu plně kompatibilní se stávající definicí protokolu RTCP. Detailní podoba jednotlivých zpráv bude představena později v této kapitole.

9.2

Obecný popis fungování protokolu TTP

Jak jsou jednotlivé typy zpráv protokolu TTP používány je znázorněno na obr. 9.12. Zpráva FTD je posílána vysílačem jako požadavek o vytvoření hierarchického stromu, dále také FTM pro aktivaci konkrétního FT. Zpráva FTI slouží FTM pro potvrzení a přijetí požadavku o vytvoření nového stromu vysílači. Zprávy FTI jsou také posílány FT k FTM. FT tak informují FTM o tom, že jsou funkční a nedošlo k jejich poruše. S Vysílač

FTD FTIACK FTS

FTM Cíl zpětné vazby

FTI

FTI FTI

FTD1

FTD1

FTD1

FTD1 FTDROOT

FTI

FTD1 FTD1

FTI

FT

FT FT

FTI FTI

FT

FT FT RFT

Obrázek 9.2: Schéma výměny zpráv mezi jednotlivými typy stanic v rámci protokolu TTP.

Postup při vytváření nového stromu je znázorněn v diagramu sekvencí na obr. 9.3. Pokud u vysílače vznikne potřeba pro sběr signalizace, požádá vysílač FTM pomocí zprávy FTD o přidělení nového stromu. FTM tento strom vytvoří z množiny registrovaných FT. FTM nejprve zvolí definovaný počet FT a ty se pak pokusí aktivovat zprávou FTD. Každý FT zjistí, zda může dané žádosti vyhovět a odešle zpět zprávu FTI (potvrzení nebo zamítnutí). Jakmile FTM aktivuje potřebný počet, začne prostřednictvím zpráv FTS informovat o podobě vytvořeného stromu. Paket

70

FTS je vysílán periodicky po celou dobu vysílání skrze multicastový kanál. Důvod periodicity je, že nově se připojující členové se musí dozvědět podobu stromu i po dobu ustavení stromu. Každý člen relace tedy přijímá multicastem FTS paket z kterého je schopný získat IP adresu a pozici nejbližšího uzlu FT.

Vysílač (Multicast)

FTM

RFT

FT

FT manažer

Kořenový FT

Cíl zpětné vazby

Definice RFT

FTD

FTD

FTD

FTD FTS

FTI(odsouhlasení) FTI(odsouhlasení) Definice FTACTIV a LM (unicast)

FTS

FTS

Informace o TTP stromu

FTI(změna) FTD FTI(změna) FTS

FTS

FTS

Obrázek 9.3: Diagram sekvencí pro požadavek vysílače o přidělení nového hierarchického stromu.

Na obr. 9.4 je potom znázorněna výměna zpráv pro realizaci samotného šíření signalizace skrze hierarchický strom. Každý přijímač ihned po připojení začne vysílat signalizaci obsahující informace některému z FT v z nejnižší vrstvy HA stromu. Aby přijímač věděl jaké jsou kandidátní FT a kdo z nich mu je nejbližší, musí poslouchat FTS zprávy z multicastového kanálu. Klienti si z FTS zprávy zjistí počet všech členů, kteří posílají stejnému FT a přizpůsobí tak dle pravidel protokolu RTP/RTCP periodu posílání zpráv. Signalizace je následně na úrovni FT stanice tzv. sumarizována a poslána v podobě zprávy RSI výše dalšímu FT, popřípadě již přímo kořenovému FT (v závislosti na výšce HA stromu). Na úrovni kořenového FT je potom výsledná sumarizace celé signlizace posílána vysílači, který je informován o případných problémem v síti.

71

Na obr. 9.4 je také ve spodní části grafu znázorněna situace, kdy libovolný FT zjistí problém ve svém clusteru. Obecně se jedná třeba o situaci, kdy se v clusteru vyskytne více uživatelů, než kolik by jich tu podle FTM mělo být. Proto FT pošle FTI paket, aby o tomto stavu FTM informoval a FTM provede náležité změny. (S) Vysílač

RSI

LM RFT

RSI

RSI

ICMP

FT RR RR

FT

RR

RR RR

FTS

RR

R

RR

RR

LM

RR

R

R

R

R R

R

R

R

ICMP

ICPM

LM

Obrázek 9.4: Schéma přenosu signalizace v rámci hierarchického stromu. S zastupuje vysílač, RFT kořenovou FT stanici, R přijímač a LM poziční bod. RR, RSI a FTS pak představují jednotlivé typy zpráv.

9.3

Přijímač

Přijímač je zařízení, které má samozřejmě (stejně jako v původní definici protokolu RTP/RTCP [73]) za úkol připravit přijatá data pro zobrazovací zařízení. Podoba takového prvku je nejčastěji ve formě zařízení typu viz set-top box (STB), ale může to být i aplikace instalovatelná na klasické PC, PDA či mobilní telefon. Z pohledu zaměření této práce nás ale více zajímá vyhodnocování kvality příjmu a posílání těchto parametrů signalizací zpět k vysílači. Jak již bylo zmíněno dříve, na rozdíl od RTP/RTCP standardu se v hierarchické agregaci již zpětná vazba neposílá přímo k vysílači, ale k jednomu cíl zpětné vazby (FT) z nejnižší vrstvy hierarchického stromu. Informaci o této množině kandidátních FT obdrží přijímač jako součást SR, která je posílána v rámci RTCP kanálu. K tomu, 72

aby FT mohlo přesně určit ke kterému hierarchickému stromu zpráva náleží, byl navržen speciální typ bloku (viz obr. 9.5). Tento blok je možné posílat v rámci RR zprávy a je zcela kompatibilní se zprávami používanými v protokolu RTP/RTCP. Tento blok v sobě obsahuje identifikační číslo stromu. To mimo jiné také umožňuje, aby množina FT stanic poskytovala více než pouze jediný strom a sloužila tak pro několik vysílačů a sběr signalizace přijímačů. 1 0

1 Ver

2

3

4

P

5

6

PODTYP

7

8

9

0

2 1

2

3

4

5

6

7

8

9

0

PT=APP=204

3 1

2

3

4

5

6

7

8

9

0

1

Délka

SSRC/CSRC T'

R'

E'

E'

ID stromu

Obrázek 9.5: Podoba aplikačního paketu, který je součástí RR zprávy. Paket sloužící pro identifikaci hierarchického stromu, do kterého přijímač R posílá signalizaci. O množině kandidátních FT stanic se přijímač dozvídá periodicky přímo z multicastového kanálu pomocí zprávy typu FTS, kde jsou například mimo jiné posílány i zprávy vysílače (SR). Protokol je navržen tak, aby byla vysoká pravděpodobnost, že do prvního vyslání RR zprávy již přijímač tuto zprávu obdrží a má ji k dispozici. Pokud by nastal případ, že zprávu neobdrží, musí přijímač čekat do prvního obdržení této zprávy a následně okamžitě RR zprávu vyslat. Volba FT probíhá na základě vzdálenosti k jednotlivým FT stanicím. K tomu musí proběhnout změření RTT hodnot vůči několika FT stanicím. Pokud je počet FT stanic nízký (< 4), lze změřit hodnotu ke každé z nich a vybrat nejbližší z nich. Pokud je toto číslo větší, je již výhodnější zvolit náhodně minimálně tři, lépe však čtyři či pět FT stanic, změřit RTT hodnotu k nim a na základě GNP algoritmu a optimalizace Simplex Downhill odhadnout pozici v umělém souřadnicovém prostoru. Periodicky vysílaná zpráva FTS obsahuje jak IP adresu FT stanice, tak její pozici v umělém souřadnicovém sprostoru, lze proto jednoduše odhadnout vzdálenost k takovým FT stanicím, ke kterým měření RTT nebylo vůbec provedeno. Bohužel měření RTT vzdálenosti ke čtyřem až pěti stanicím může přijímač stát nějakou dobu. Pokud se přijímač nestihl ještě zaměřit, použije hodnotu z paměti o předchozí poloze FT stanic. Pokud ta není k dispozici, popřípadě neobsahuje ifnormaci o žádná FT stanici z množiny kandidátních FT stanic, zvolí se libovolná FT stanice a zpráva RR se musí poslat bez prodlevy.

73

9.4

Cíl zpětné vazby (FT)

Prvek FT byl již představen dříve v kapitole věnující se popisu metody hierarchické agregace. Ve zkratce se jedná o aktivní prvek, který má na starosti shromažďování signalizace od přijímačů (zprávy RR) popřípadě od ostatních FT stanic z přímých nižších vrstev hierarchického stromu (zprávy RSI). Stanice FT je současně schopna pracovat s několika hierarchickými stromy. Množina FT díky tomu může být sdílena několika vysílači a stanice FT. Stanice typu FT současně může zastávat úlohu pozičního bodu. Samotné rozlišení jednotlivých zpráv je provedeno pomocí identifikačního čísla stromu. To přiděluje stanice typu FTM a je vždy jedinečné v celém systému. Při spuštění prvku FT dojde nejprve k zaregistrování u stanice typu FTM (viz FTR paket na obr. 9.6). Na základě toho se stanice typu FTM dozví, že je k dispozici. Hodnota položky “akce” je v tomto případě rovna nule. Při korektním ukončení činnosti FT prvku je zapotřebí, aby o tom byla informována FTM stanice. To je realizováno opět pomocí FTR paketu. Hodnota položky “akce” je v tomto případě rovna jedné. 1 0

1 Ver

2

3 P

4

5

6

TYP=4

7

8

9

0

2 1

2

3

4

5

AKCE

6

7

8

9

0

3 1

Rezervováno

2

3

4

5

6

7

8

9

0

1

Délka

Obrázek 9.6: Registrační a deregistrační zpráva FTR.

9.5

FT Manažer (FTM)

Stanice FT manažer (FTM) je další síťový prvek, který je v této práci představen. Jedná se o jakýsi pomyslný mozek celé hierarchické agregace a jeho úkolem je ustavit a zorganizovat FT stanice tak, aby tvořily stromovou strukturu a současně aby nedocházelo ke zbytečnému plýtvání s prostředky sítě. Díky tomu se také jedná o nejsložitější prvek v celé HA. V reálném nasazení bude FTM aplikace spuštěná na samostatném dedikovaném serveru, popřípadě bude spuštěn na stanici kde jsou spuštěny vysílače. Jakmile je stanice FTM spuštěna, aktivně začne čekání na registrace od stanic typu FT. To je realizováno pomocí registračního paketu typu FTR. Jakmile je stanice FT registrována, stanice FTM ji může požádat o změření RTT hodnot vůči ostatním stanicím typu FT. 74

0

1

2

3

4

Ver

5

6

7

8

9

1 0

1

Type

2

3

4

5

6

7

8

9

2 0

1

2

3

Tree ID

4

5

6

7

8

9

3 0

1

Length

FTM port Group Size

Status

Level

Reserved Reserved

Obrázek 9.7: Definiční paket FTD sloužící pro definici role v hierarchickém stromu.

Zpráva typu FTD je zpráva, která je generována stanicí typu FTM a slouží k definování vlastností stanic typu FT. Tato zpráva je posílána výhradně unicastem přímo na adresu dané stanice typu FT. Je odesílán přes TCP spojení na IP adresu definované stanice FT. Stanice typu FT potřebuje po příjmu aktivační zprávy FTD určitou reakční dobu k tomu, aby ověřil požadované parametry definovaného právě ve zprávě FTD. Potvrzení či odmítnutí stavu odešle zpět stanici FTM. Je zde definováno několik již pevně určených parametrů a ponecháno místo na další rozšíření. Nejdůležitejší je pole “Výška”, kde stanice FTM odesílá stanici FT informaci o tom v jaké vrstvě zpětného kanálu bude pracovat a pole “Vlastnost”, kde definuje, zda daná stanice typu FT bude aktivním členem zpětného kanálu nebo bude poskytovat službu pozičního bodu. Dalším zajímavým blokem je pole “Velikost přiřazení skupiny”, kde je FT stanice informována o tom, pro jaký počet příjemců je v aktuálním stromu postaven. Pokud by došlo k překročení tohoto limitu, stanice FT informuje o tomto stavu stanici FTM pomocí zprávy FTI. Je poté ponecháno na FTM, jak bude vzniklý problém řešen. Tato zpráva FTI (Feedback Target Information) je posílána především stanicím FT, ale může být poslána i stanici FTM jako informace o zrušení definovaného uzlu ze stromu. Využití má při potvrzení o přechodu do stavu, který stanice FTM požadovala, anebo při situaci, kdy FT překračuje meze určitého parametru definovaného stanicí FTM, například počet uživatelů ve skupině. Další možností je pak informace o nedostupnosti aktivované stanice FT, což zjistí stanice FT jí nadřayená v hierarchickém stromu, pokud přestanou od problematického FT docházet RSI zprávy, popřípadě později i stanice FTM na základě nedoručených zpráv “IS ALIVE”. Obecná struktura paketu je naznačena na obr. 9.8. 0

1

Ver

2

3

4

5

6

7

8

Type

9

1 0

1

2

3

4

5

6

7

8

9

2 0

1

2

Tree ID

3

4

5

6

7

8

9

3 0

1

Length

FT port

Information status

Parameters

Obrázek 9.8: Informativní paket FTI sloužící pro informování stanice FTM od ostatních stanic FT

FTS zpráva je generována stanicí FTM a je odesílána všem členům relace 75

(stanicím FT a všem přijímačům) přes multicastový kanál. Tato zpráva obsahuje informace o všech FT, tj. jejich adresu a polohu v souřadnicovém systému. Poté co si přijímače tuto zprávu přečtou, jsou schopni najít k nim nejbližší sumarizační bod a tak i začít k němu vysílat svoji signalizaci. Velikost zprávy FTS tedy závisí na počtu stanic FT ve stromě. Počet stanic FT může být i velmi vysoké číslo a přitom musí být zajištěno neustálé periodické odesílání táto zprávy: Je to dáno tím, že noví členové se mohou do relace přihlásit v libovolný čas. Tuto metodu odeslání můžeme srovnat s teletextem znám z analogové televize. Všechna data by měla být odeslána alespoň každých 5 sekund (viz obr. 9.9). 0

1

2

3

4

5

Ver

6

7

8

1 0

9

1

2

Type

3

4

5

6

7

8

9

2 0

1

2

3

4

Tree ID

5

6

7

8

9

3 0

1

Length

FTS sequence number Session size Group 1

SFTST

Length

… …

…

Group 2

SFTST

Length

… …

…

Obrázek 9.9: Paket FTS sloužící pro popis podoby hierarchického stromu.

Zpráva FTS se dále dělí na podbloky, které nesou specifickou informaci podle typu služby, kterou stanice FT provozuje. Zatím máme dva takové typy. První typ definuje vlastnosti stanice FT (viz obr. 9.10) a druhý typ definuje vlastnosti pozičního serveru (viz obr. 9.11). 0

1

2

3

4

5

6

7

8

9

1 0

SFTST

1

2

3

4

5

6

7

8

9

2 0

Length

1

2

3

4

5

6

7

8

9

3 0

1

FT Port Feedback target IPv4 address

Group size

P

Priority

Level

Vector Format

…

LM ID vector

Obrázek 9.10: Podblok paketu FTS - definice cíle zpětné vazby (FT).

9.6

Vysílač (S)

Vysílač je prvek, který se oproti standardní protokolové sadě RTP/RTCP liší opravdu jen minimálně, proto se mu tato kapitola věnuje jen poměrně stručně. Pokud chce vysílač interpretovat signalizaci přijímačů a číst aktuální stav příjmu 76

0

1

2

3

4

5

6

7

SFTST

8

9

1 0

1

2

3

4

5

6

7

8

9

2 0

1

Length

2

3

4

5

6

7

8

3 0

9

1

FT Port Feedback target IPv4 address

Vector Format

Reserved

…

LM ID vector

Obrázek 9.11: Podblok paketu FTS - definice cíle zpětné vazby (FT) v omezeném režimu pozičního bodu.

všech přijímačů, musí vysílač samozřejmě znát protokol TTP. Dále musí být schopen požádat stanici FTM o přidělení HA stromu resp. uvolnění přostředků když už nejsou zapotřebí. Ostatní fungování tohoto prvku je identický s tím, jak je definováno v RFC 3550 [73]. Vysílač (Multicast)

FTS

FTM

RFT

FT

R

FT manažer

Kořenový FT

Cíl zpětné vazby

Přijímač

FTS

FTS

FTS

...

ICMP Nalezení nejbližšího FT

ICMP RR1 RR2 RR3 RR4

timer

Interval TRR

……….

DefinitionFT of ACTIV FTACTIV a LM (multicast) Definice a LM (multicast)

…………

RSI RSI RSI Posílání do vyšší vrstvy FT stromu

sumarizace timer

RSI RSI RSI …….

timer sumarizace

RSI

Obrázek 9.12: Diagram sekvencí pro vytváření nového stromu.

77

Posílání RR zpráv

TRSI interval sumarizace

10

VYBRANÉ NAVAZUJÍCÍ PRÁCE A VALIDACE NAVRŽENÉHO ŘEŠENÍ

Tato kapitola pojednává o vybraných souvisejících pracích, kterých se autor této práce přímo účastnil při jejich vývoji - buďto výhradně anebo značnou měrou. Většina z nich byla provedena pod záštitou výzkumné skupiny DINES1 . Autor této práce je jejím členem, školitel této práce je vedoucí této skupiny (Doc. Ing. Dan Komosný, PhD.), stejně tak další spolupracovníci, zejména asistenti a doktorandi z Ústavu telekomunikací, Vysokého učení technické v Brně jsou taktéž čelny této skupiny. Na některých pracích se také svou měrou podíleli studenti ve svývh bakalářských a diplomových pracech. Cílem této části práce bylo zejména ověřit funkčnost navržených algoritmů a protokolu TTP. Vzhledem k rozsahu systému a nemožnosti ověření funkčnosti v laboratorních podmínkách VUT v Brně, kontaktoval výzkumný tým Dr. Li Tanga (Tsinghua University network, Networks Security lab, Peking), který poskytl informace o celosvětové experimentální síti PlanetLab. Bylo zjištěno, že sdružení CESNET, které poskytuje konektivitu i VUT v Brně, již v této síti participuje s pomocí uzlů s DNS názvy “planetlab1.fit.vutbr.cz”, “planetlab2.fit.vutbr.cz” a “planetlab1.cesnet.cz”. Přístup do experimentální sítě byl vyjednán pod názvem “cesnet vutbr1” Jedním z prvních problémů, které autor práce musel řešit je podpora protokolu ICMP v prostředí jazyka JAVA. Jazyk JAVA je relativně vysokoúrovňovým jazykem a jako takový neobsahuje implicitní podporu pro manipulaci s pakety tohoto typu. Tato překážka byla vyřešena rozšíření platformy o nativní knihovny pro platformy Windows, Linux a Unix. Další problém, který nastal, byla chybějící podpora přenosu dat typu SSM multicast. S tímto cílem byl založen projekt JSSM2 . Projekt je v současnosti uvolněn pod veřejnou licencí Apache v 2.03 , která umožňuje využití výstupu nejen pro neziskové projekty, ale také pro komerční využití. Na základě tohoto projektu se jsme byli kontaktováni Alanem Batemanem a požádáni o konyultace. Alan Bateman byl v tu dobu vedoucí specifikace JSR-203 a druhé fáze nových I/O API pro Java SE platformu v. 7 ve společnosti Sun Microsystems, USA. Další z větších nezbytných záležitostí řešených v rámci této práce je projekt pro simulaci síťových služeb. Přestože validace v prostředí skutečné sítě je díky své komplexnosti nenahraditelná, analyzovat některé chování je v prostředí internetu téměř nerealizovatelné. Tento nástroj je zcela jedinečný ve své oblasti. Knihovna umožňuje analýzu a simulaci kompletních aplikací, které lze spouštět i jako klasickou samostatnou simulaci. Lze tak simulovat i aplikace, ke kterým nedisponujeme 1

http://www.dinesgroup.org http://jssm.dev.java.net 3 http://www.apache.org/licenses/LICENSE-2.0 2

78

zdrojovými kódy. Do simulace je možné vkládat více aplikací a je také možné každé přiřadit vlastní IP adresu. Knihovna podporuje simulaci vláken a procesů, simulaci síťové komunikace TCP i UDP, veškeré pozastavení činnosti v průběhu běhu aplikace nemají vliv a simulace probíhá tak rychle, jak jí jen výpočetní výkon dovolí. Umožňuje analýzu všech běžně známých protokolů a exportuje data do prostředí Octave4 , Matlabu5 , Scilab6 i R7 . Současně umožňuje vizulaizaci do grafické podoby. Knihovna je v současnosti používána studenty při řešení jejich bakalářských a diplomových prací a výhledově zvažujeme jejich uvolnění pod veřejnou licencí GPL či LGPL. Jako výchozí práce, ze které projekt a celá práce prvotně vychází, je realizace protokolové sady RTP/RTCP. Spolu s ním bylo vytvořeno grafické uživatelské prostředí, které je schopno analyzovat aktuální stav vysílání a monitorovat parametry QoS. Implementace této protokolové sady byla následně využita k rozšířením a validaci funkčnosti v navazujících pracech. Výsledek je vyobrazen na obr. 10.1.

Obrázek 10.1: Aplikace vytvořeného IPTV vysílače (vlevo) a přijímače (vpravo).

Přesnost lokalizace stanic v síti závisí mimo jiné i na poloze jednotlivých sumarizačních stanic v síti a nevhodné rozmístění může dokonce algoritmus poškodit natolik, že jeho přesnost je srovnatelná s náhodným výběrem. Z důvodu, aby bylo možné přibližně odhadnout vhodné rozložení stanic v síti, byly extrahovány 4

http://www.gnu.org/software/octave http://www.mathworks.com 6 http://www.scilab.org 7 http://www.r-project.org 5

79

algoritmy z protokolu TTP a s jejich pomocí vytvořeny nástroje dostupné online ze stránek autora této práce 8 , které zobrazují výsledky těchto výpočtů a zobrazí přibližnou funkčnost. Náhled takovéto aplikace je na obr. 10.2. Je zde znázorněno dohromady 5 sumarizačních uzlů, ke kterým se pokouší lokalizovat stanice, jejíž poloha je na pozici kurzoru myši. Červeně je poté zvýrazněna oblast s nejvyšší pravděpodobností lokalizace v síti. Parametry sítě jsou ve výchozím nastavení konfigurovány tak, aby odpovídaly skutečnému chování v síti. V případě algoritmu TTP byl nakonec zvolen algoritmus GNP pro jeho nesporné výhody zejména z hlediska rychlosti a také z toho důvodu, že se svojí topologií hodí pro integraci do tohoto protokolu [10].

Obrázek 10.2: Simulační nástroj pro správné rozmístění stanic v síti a dopad na přesnost lokalizace. K dispozici ke spuštění online ze stránek autora této práce www.dinesgroup.org.

Kromě lokalizačních algoritmů byl také extrahován algoritmus pro sestavení hierarchického stromu a s jeho pomocí je možné vizualizovat nejpravděpodobnější podobu hierarchického stromu, který pro daný počet agregačních stanic FT bude v rámci sítě sestaven. Aplikace je opět dostupná ze stránek autora této práce online 8

http://www.dinesgroup.org

80

na stránkách Dines-group a je ji možné spustit přímo z webového prohlížeče. Náhled tohoto nástroje je na obr. 10.3.

Obrázek 10.3: Simulační nástroj pro orientační správné rozmístění stanic v síti a strukturu hierarchického stromu. K dispozici ke spuštění online ze stránek autora této práce www.dinesgroup.org.

10.1

Globální experimentální síť PlanetLab

Pro potřeby testování jsou laboratorní podmínky jednoho pracoviště zcela nedostačující. V rámci omezených výpočetních zdrojů a malých vzdáleností mezi stanicemi bylo testování funkčnosti protokolu nebylo příliš průkazné. Pro potřeby ověření celého protokolu posloužila experimentální síť Planetlab9 [40], [65], [64], [32]. Planetlab je unikátní projekt, kterého se účastní i nadnárodní společnosti jako Hewlet-Packard, Google, Intel a další. Důvod proč tento projekt vznikl, byla právě 9

http://www.planet-lab.org/

81

nemožnost ověřovat nové protokoly v globálním rozsahu. V současnosti projekt obsahuje 1090 stanic na 503 různých místech světa (čísla jsou aktuální ke 2. 4. 2010, 9:15).10 Většina zemí je situována v oblastech vyspělých zemí Evropy, USA a Číny. Tato struktura je pro naše potřeby poměrně vhodná jelikož do značné míry reflektuje i předpokládané nároky na síť z pohledu služby IPTV.[35], [68], [53]

Obrázek 10.4: Rozložení stanic v experimentální síti Planetlab (převzato z http://www.planet-lab.org/).

Samotný projekt Planetlab byl zahájen v roce 2002. Projekt iniciovaly University of California at Berkeley, Princeton University a University of Washington. Sdružení CESNET, přes které nám bylo umožněno připojení se do sítě Planetlab, se do projektu zapojilo v roce 2006 a v současnosti již poskytuje 4 různá přístupová místa, čímž také aktivně přispívá vlastními stroji do této sítě. Účel vzniku byl rozvoj nových síťových služeb a jejich validace a experimentální ověření v celosvětovém měřítku. Oblast experimentálního ověřování se pohybuje zejména v oblasti výzkumu síťových a distribuovaných systémů, kde je možné poskytnout ověření v reálných síťových podmínkách. Přístup do experimentální sítě je nám umožněno prostřednictvím účtu cesnet vutbr2 na adrese http://www.planet-lab.org/. Na jednotlivé stanice se lze přihlašovat klasicky pomocí nástroje SSH (Secure SHell). Komunikace tímto způsobem je ovšem značně nepraktická, jelikož správa většího počtu stanic v síti obnáší opakovat konfiguraci pro každou stanici zvlášť. Aby bylo možné komunikovat 10

Ze zkušeností s používáním této sítě je ale bohužel průměrně mezi 10 - 20 % stanic mimo provoz.

82

i s větším počtem stanic současně, je k tomu poskytnuto několik nástrojů. Jedním z nich je např. PlMan (PlanetLab Experiment Manager)11 či také nástroj Plush12 . S pomocí těchto nástrojů lze snadno distribuovat příkazy a programy a lze je také relativně snadno spouštět. K těmto nástrojům existují i grafické nástavby jako je například Nebula13 , pomocí kterého si lze velice snadno udělat přehled o geografickém rozložení jednotlivých stanic (viz obr. 10.5).

Obrázek 10.5: Podoba aplikace Nebula pro správu sítě Planetlab v grafickém uživatelském prostředí (převzato z http://plush.cs.williams.edu/).

10.2

Sběr informací a vizualizace celého stromu ze sítě PlanetLab

Při testování jsme se potýkali s problémem, jak dlouhodobě monitorovat chování celé aplikace tak, aby bylo možné sledovat podobu fungování protokolu v reálném čase. Simulace má dozajista bezpočet výhod. V síťovém prostředí lze jen s řádově vyšším úsilím provádět kontrolu skrze celou síť, identifikovat případné chybné chování stanice a lze libovolně urychlit čas a dobu simulace, lze srovnávat chování v naprosto 11

http://www.cs.washington.edu/research/networking/cplane/ http://plush.cs.williams.edu/ 13 http://plush.cs.williams.edu/nebula/ 12

83

stejných situacích a zjišťovat, zdali v takovém případě je problém potlačen anebo nikoli. Co ovšem simulace nemůže vzít v úvahu je bezpočet vlivů a situací, které v reálné síti běžně nastávají, ale v simulaci se pro jednoduchost zanedbávají. Typickým příkladem jsou výpadky stanic a neočekávané poruchy. Problém výpadků a poruchovosti byl sice po dobu řešení nepříjemný, na druhou stranu umožnil pozorovat chování protokolu i v situacích, které nebyly zprvu plánovány, a se kterými se vůbec nepočítalo, že mohou nastat. Za účelem monitorování stanice ve skutečném prostředí byla skupinou Dines Group vytvořena monitorovací aplikace (viz obr. 10.6), která shromažďuje informace o aktuální stavu jednotlivých stanic a vizualizuje podobu hierarchického stromu [16]. Monitorovány jsou průběžně veškeré aktivní i pasivní stanice, které jsou zapojeny do práce s hierarchickým stromem. Veličiny, které jsou monitorovány, jsou zejména perioda zasílání signalizace, čas aktivace stanice, ztrátovost paketů audia/videa, zpoždění paketů audia/videa a kolísání zpoždění při přenosu dat a délka signalizační zprávy. Toto jsou nejdůležitější charakteristiky sítě, které ovlivňují kvalitu z pohledu koncového uživatele. Kromě těchto charakteristik jsou o jednotlivých stanicích ukládány informace o pozici stanice v hierarchickém stromu, identifikační číslo stromu, jehož je členem, velikost signalizační skupiny apod. Celá aplikace byla vytvořena jako J2EE14 webová služba běžící ve webovém kontejneru Apache Tomcat15 . Celá aplikace byla navržena jako třívrstvý model s rozdělením na vrstvu datovou, aplikační a prezenční. V rámci persistentní vrstvy je aplikace napojena na databázový server, kam jsou veškeré informace ukládány. Je proto možné monitorovat nejen současný stav, ale i zpětně prohlížet historii a události, ke kterým došlo. K aplikační vrstvě je možné přistupovat jako k webové službě pomocí protokolu SOAP. Vrstva prezenční používá technologii webového rozhraní pomocí standardu XHTML, Scalable Vector Graphics (SVG) a JavaScript a některé další. V síti Planetlab dochází k výpadkům častěji, nežli se předpokládá v prostředí skutečné sítě. V rámci pozorování byly i ručně vyvolány nějaké poruchy a pozorovány dopady na celý přenos. Ukázalo se, že protokol dokáže podle předpokladu konvergovat k jinému stavu a s případnou poruchou se vyrovnat. Doba této konvergence také odpovídala době předpokladům a byla lineárně závislá na periodě stanic v síti.

14

JAVA 2 Enterprise Edition je platforma pro programování serverových aplikací Apache Software Foundation, Tomcat je opens-source řešení pro serverové aplikace na platformě JAVA http://tomcat.apache.org/ 15

84

(a) Grafické uživatelské rozhraní aplikace

(b) Statistiky strátovosti paketů uzlu

Obrázek 10.6: Vzhled aplikace pro monitoring hierarchického stromu v síti Plnetlab. Dostupné online ze stránek autora této práce http://www. dinesgroup.org:8080/TreeVisualization

85

11

ZÁVĚR

Tato práce se zabývá výzkumem přenosu signalizace pomocí IP protokolu. Obecně je typickým uplatněním signalizace monitoring kvality datového spojení. V současnosti nejpoužívanější protokol pro monitoring kvality datového přenosu je protokol RTCP. Tento protokol se nejčastěji používá s protokolem RTP a společně slouží pro přenos a monitoring přenosu dat citlivých na zpoždění, kolísání tohoto zpoždění v čase (jitter) a několik dalších parametrů, které charakterizují vlastnosti sítě a kvalitu datového spojení v rámci lokálních (LAN) a rozlehlých (WAN) sítí. Typickými představiteli dat citlivých na zpoždění a kolísání zpoždění přenosu je audio či video, nicméně protokol RTP/RTCP nachází uplatnění i v jiných oblastech. Aby při větším počtu uživatelů nedošlo k zahlcení signalizací, protokol RTCP s rostoucím počtem účastníků frekvenci signalizace snižuje a využitá šířka vyhrazeného kanálu je potom téměř konstantní 1 . To ale pro větší počty účastníků v síti znamená periodu hlášení chybovostí natolik velkou, že může přesáhnout i dobu vysílaného programu. Například, vysílání, kde je přítomno 100 000 diváků představuje periodu hlášení až 1 hod a 30 minut (více informací viz kapitola I.). Pro řešení tohoto problému se objevilo mnoho řešení jako je např. biasing, filtrování a další. Jedním z řešení tohoto problému je i vypnutí monitorování kvality služby (tato volba je dostupná na IPTV serverech společnosti CISCO). V době zahájení této práce se také objevila myšlenka tzv. hierarchické agregace a její matematický popis. Tato práce vychází z protokolové sady RTP/RTCP a současných nejčastěji používaných standardů pro přenos signalizace a integruje metodu hierarchické agregace do tohoto prostředí. Cílem této práce je zanechat maximum ze stávajících standardů a tak ponechat relativně nízké náklady nezbytné k přechodu k tomuto řešení. Hlavní přínos celé práce spočívá v návrhu protokolu pro přenos signalizace velkého množství stanic. V práci je popsána integrace hierarchické agregace s protokolem RTCP a algoritmus pro návrh stromové struktury s využitím znalosti topologie sítě. Navržený protokol je schopen přenést v signalizaci v krátkém čase a je schopen přizpůsobit se požadavkům a možnostem operátora. Navržené řešení může být proto nasazeno jak pro malé operátory, tak pro velké organizace s tím, že struktura je schopna flexibilně růst dle aktuálních požadavků a rovnoměrně vytížit přidělené zdroje. Byly vytvořeny simulační nástroje, které bez nutnosti nasazení v síti dokážou odhadnout chování protokolu a způsob navržení sítě. Tyto nástroje jsou dostupné online a ze stránek autora této práce. Navržený protokol byl implementován a ověřen v prostředí celosvětové sítě Planetlab. Za předpokladu 1

Podrobnosti o maximálním přesahu využití kanálu pro signalizaci je popsána v [73]

86

dostatečných hardwarových zdrojů je metoda schopna přenést signalizaci od 100 000 přijímačů v čase 14 sekund, což je oproti 1 hod. a 30 min téměř 400x rychlejší oproti protokolu RTCP. Obdobnou problematikou se ve světě aktuálně zabývají např. pracoviště ATT Labs-Research a University of Cambridge, které obě aktivně přispívají v řadě konferencí a několika časopisech zaměřených na síťové technologie. Nově byly výsledky jejich činnosti také navrženy k standardizaci v rámci RFC 5760 [63]. V rámci České republiky se problematikou zabývá výzkumná skupina Dines group2 . Autor této práce je aktivním členem této skupiny a podílel se na řešení výzkumných projektů “Systém přenosu signalizace pro multicast se specifickým zdrojem dat”, GA102/07/1012 financovaný Grantovou agenturou České republiky a Optimalizace metod pro multicast v IP sítích” AVČR 1ET301710508, financovaný ” Akademií věd České republiky. Hlavní oblasti uplatnění této technologie se předpokládají jako interaktivní internetová televize, garance úrovně kvality služby zákazníkům či přizpůsobení kvality vysílání dle aktuálního stavu sítě. Interakce s diváky je v současné době realizována skrze jiné kanály, než bývá distribuována internetová televize. Nejčastěji to bývá síť mobilních operátorů skrze SMS zprávy. Díky efektivnímu využití kanálu mohou vznikat nové typy pořadů, kde mohou diváci interaktivně komunikovat s poskytovatelem služby, a tím i například ovlivňovat průběh a dění v pořadu. Na jeho základě mohou vznikat služby s přidanou hodnotou, kde náklady jak diváků, tak poskytovatelů budou velice nízké v porovnání se stávajícími technologiemi. V případě garance kvality služby je technologie schopna zajistit souvislé monitorování kvality příjmu jednotlivých přijímačů i prostřednictvím veřejné sítě. Operátoři si proto mohou dovolit garantovat vyšší kvalitu služeb odpovídající aktuálnímu stavu a současně s tím je zátěž generovaná touto signalizací relativně nízká. S tím může souviset i adaptivní přizpůsobení obsahu. V současné době existuje řada obrazových a zvukových protokolů [85], [74], [13], [86], [81] kde lze přizpůsobovat poměr mezi kvalitou a odolností proti chybám sítě. S využitím rychlé zpětné signalizace lze tento poměr měnit adaptivně a v různých podmínkách v síti lze nastavit takový poměr, který z pohledu diváka umožní nejvyšší kvalitu služby. Práce je členěna na čtyři základní části. První část se věnuje popisu stávajících standardů, protokolů a algoritmů, které jsou poté v práci využity či rozšířeny. Text je formulován tak, aby zdůraznil nedostatky současné technologie, a poskytuje k tomu i potřebné matematické vztahy a závislosti. V následující části jsou konkrétně pojmenovány nedostatky současných technologií a vytyčeny cíle této práce. Třetí část popisuje vlastní řešení a prezentuje dosažené výsledky. V poslední části jsou 2

Původní název skupiny byl IPTV Multicast Research Group, http://www.dinesgroup.org/

87

popsány nástroje a aplikace, které byly vytvořeny jako součást řešení této práce a je popsáno prostředí celosvětové sítě Planetlab, ve kterém byly výsledky validovány. Průběh a výsledky řešení této práce byly prezentovány na mezinárodních konferencích a v časopisech. Práce byla odbornou komunitou přijata, o čemž mohou svědčit v současné době jedno přijetí článku do impaktového časopisu Journal of Network and Computer Applications, Elsevier3 [56], dvě ocenění “Best Paper Award”. Jedna na International Conference on Networking za příspěvek “Integration of Host Position Prediction into Hierarchical Aggregation” [10] a druhá na Personal Wireless Communications za příspěvek “Multicast Feedback Control Protocol for Hierarchical Aggregation in Fixed and Mobile Networks” [42]. V roce 2009 byl písemně vyžádán článek profesorem Sarwan Sharma, Department of Electronic and Computer Science do časopisu “International Journal on Advances in Internet technology” [9]. O poskytnutí vyvinutého softwaru jsme byli požádáni od Dr. K.M. Guilda z Future Networks Group, Department of Computer and Electronic Systems (CES), UK. Jednalo se o řešitele evropského projektu v rámci Framework Program 74 . Jako vedlejší produkt této práce vzniklo rozšíření platformy JAVA o podporu technologie Source-Specific Multicast. Na jejím základě jsme byli kontaktováni Alanem Batemanem (Specification Lead, JSR-203, SUN Microsystems), který byl vedoucím specifikace pro novou verzi platformy jazyka JAVA a požádáni o konzultace. Oblast pro pokračování v této práci může být v celku široká. Tento protokol byl sice navrhnut zejména pro službu IPTV a monitoring kvality přijímačů, nicméně jedná se o obecný algoritmus, který může být uplatněn pro mnoho různých oblastí. Do budoucna se jedna z těchto oblastí uplatnění rýsují senzorové sítě. V senzorových sítích jsou vysoké nároky na energetickou závislost a s tím také souvisí i efektivní komunikace. Pro komunikaci typu mnoho ku jednomu se algoritmy popsané v této práci mohou uplatnit.

3

V roce 2010 dosáhl časopis Journal of Network and Computer Applications, Elsevier hodnoty impakt faktoru 1,111. 4 http://cordis.europa.eu/fp7/

88

LITERATURA [1] Asano, T.; Ranjan, D.; Roos, T.; aj.: Space-filling curves and their use in the design of geometric data structures. Theoretical Computer Science, ročník 181, č. 1, 1997: s. 3–15. URL citeseer.ist.psu.edu/44852.html [2] Bhattacharrya, S.: An Overview of Source-Specific Multicast (SSM). IETF Request For Comments (RFC) 3569. In RFC 3569, July 2003. [3] Bonatti, P. A.; Lutz, C.; Murano, A.; aj.: 3 ISOIEC 13818-2 MPEG-2. Information technology - generic coding of moving pictures and associated audio information: video. In ICALP 2006. LNCS, Springer, 2006, s. 540–551. [4] Burget, R.; Komosný, D.: Real-time control protocol and its improvements for Internet Protocol Television. International Transaction on Computer Science and Engineering, 2006, ISSN 1738-6438. [5] Burget, R.; Komosný, D.; Šimek, M.: RTP/RTCP for Single Source Topologies. In International Conference on Computer Science and Information Technologies, 2007, s. 223-224. [6] Burget, R.; Komosný, D.; Šimek, M.: Simulation of Large-Scale IPTV Systems for Fixed and Mobile Networks. Springer Verlag, 2007: s. 445—454, ISSN 15715736. [7] Burget, R.; Komosný, D.; Šimek, M.: Transmitting Hierarchical Aggregation Information Using RTCP Protocol. International Journal of Computer Science and Network Security, 2007, ISSN 1738-7906, vol. 7 No. 11 pp. 44-48. [8] Burget, R.; Komosný, D.; Müller, J.: Best Effort Hierarchical Aggregation Tree for IPTV Signaling. 2008, international Journal of Computer Science and Network Security, 2008, roč. 2008, č. 8, s. 1-5. ISSN: 1738-7906. [9] Burget, R.; Komosný, D.; Muller, J.: Interactive Internet Television for Mobile Devices and Large-scale Areas. In International Journal on Advances in Internet Technology, 2009, ISSN 1942-2652. [10] Burget, R.; Komosný, D.; Novotny, V.: Integration of Host Position Prediction into Hierarchical Aggregation. In ICN, 2008, s. 740–745. [11] Burget, R.; Müller, J.: Accuracy Improvements for Network Position Estimation. 2008, in Telecommunication and Signal Processing 2008. 2008. s. 65-68. ISBN: 978-963-06-5487-6. 89

[12] Cain, B.; Deering, S.; Kouvelas, I.; aj.: Internet Group Management Protocol, Version 3. 2002. [13] Chan, S.-H. G.; Zheng, X.; Zhang, Q.; aj.: Video loss recovery with FEC and stream replication. IEEE Transactions on Multimedia, ročník 8, č. 2, 2006: s. 370–381. [14] Chen, Y.; Xiong, Y.; Shi, X.; aj.: Pharos: A Decentralized and Hierarchical Network Coordinate System for Internet Distance Prediction. In GLOBECOM, 2007, s. 421–426. [15] Chen, Y.; Zhao, G.; Li, A.; aj.: Myth: An Accurate and Scalable Network Coordinate System under High Node Churn Rate. In Networks, 2007. ICON 2007. 15th IEEE International Conference on, Listopad 2007, s. 143–148, doi: 10.1109/ICON.2007.4444076. [16] Cimbálek, P.: Grafické zobrazení relací mezi stanicemi v internetu, Brno: Vysoké učení technické v Brně, Fakulta elektrotechniky a komunikačních technologií, 2008. 63 s. Vedoucí diplomové práce Doc. Dan Komosný, PhD. 2008. [17] Cimbálek, P.; Komosný, D.; Müller, J.; aj.: Visual Model of Feedback Transmission in IPTV. 2008, in Proceedings of the Second IASTED Africa Conference on Modelling and Simulation. Gaborone, Botswana: 2008. s. 1-7. ISBN: 978-0-88986-764-2. [18] Dabek, F.; Cox, R.; Kaashoek, F.; aj.: Vivaldi: a decentralized network coordinate system. SIGCOMM Comput. Commun. Rev., ročník 34, č. 4, October 2004: s. 15–26, ISSN 0146-4833, doi:10.1145/1030194.1015471. URL http://portal.acm.org/citation.cfm?id=1030194.1015471 [19] Dilley, J.; Maggs, B.; Parikh, J.; aj.: Globally Distributed Content Delivery. IEEE Internet Computing, ročník 6, č. 5, 2002: s. 50–58, ISSN 1089-7801, doi: http://dx.doi.org/10.1109/MIC.2002.1036038. [20] El-Marakby, R.: Design and Performance of a Scalable Real Time Control Protocol: Simulations and Evaluations. In ISCC ’00: Proceedings of the Fifth IEEE Symposium on Computers and Communications (ISCC 2000), Washington, DC, USA: IEEE Computer Society, 2000, ISBN 0-7695-0722-0, str. 119. [21] El-Marakby, R.; El-marakby, A.; Hutchison, D.: Scalability Improvement of the Real-time Control Protocol (RTCP) Leading to Management Facilities in the 90

Internet. In the Proceedings of the third IEEE Symposium on Computers and Communications (ISCC’98, 1998. [22] El-marakby, R.; Hutchison, D.: A Scalability Scheme for the Real-time Control Protocol. In In Proceedings of 8th International Conference on High Performance Networking (HPN, 1998. [23] Elramly, N. A.; Habib, A. S.; Essa, O. S.; aj.: Analysis, Design, and Performance Evaluation of MS-RTCP: More Scalable Scheme for the Real-Time Control Protocol. Journal of Universal Computer Science, ročník 11, č. 6, 2005: s. 874– 897. [24] Estrin, D.; Farinacci, D.; Helmy, A.; aj.: Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification. RFC 2117 (Experimental), June 1997, obsoleted by RFC 2362. URL http://www.ietf.org/rfc/rfc2117.txt [25] Estrin, D.; Farinacci, D.; Helmy, A.; aj.: Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification. 1998. [26] Fenner, B.; Handley, M.; Holbrook, H.; aj.: Protocol Independent Multicast Sparse Mode (PIM-SM): Protocol Specification (Revised). 2006. [27] Francis, P.; Jamin, S.; Jin, C.; aj.: IDMaps: A Global Internet Host Distance Estimation Service. 2000. URL http://citeseer.ist.psu.edu/francis01idmaps.html [28] Francis, P.; Jamin, S.; Paxson, V.; aj.: An Architecture for a Global Internet Host Distance Estimation Service. In IEEE INFOCOM 1999, New York, NY: IEEE, March 1999, s. 210–217. URL citeseer.ist.psu.edu/francis99architecture.html [29] Gummadi, K. P.; Saroiu, S.; Gribble, S. D.: King: Estimating Latency between Arbitrary Internet End Hosts. In SIGCOMM Internet Measurement Workshop 2002, 2002. [30] Handley, M.; Kouvelas, I.; Speakman, T.; aj.: Bidirectional Protocol Independent Multicast (BIDIR-PIM). RFC 5015 (Proposed Standard), October 2007. URL http://www.ietf.org/rfc/rfc5015.txt [31] Holbrook, H.; Cain, B.; Haberman, B.: Using IGMPv3 and MLDv2 for SourceSpecific Multicast. RFC 4604, IETF, August 2006.

91

[32] Huang, M.: VNET: PlanetLab Virtualized Network Access. Technická Zpráva PDN–05–029, PlanetLab Consortium, June 2005. [33] Šimek, M.; Komosný, D.; Burget, R.: One Source Multicast Model Using RTP in NS2. International Journal of Computer Science and Network Security, 2007, ISSN 1738-7906, vol. 7 No. 11 pp. 252-257. [34] Šimek, M.; Komosný, D.; Burget, R.; aj.: Centralized Boundary Discovery Algorithms for Anchor- Free Localization in Wireless Sensor Networks. 2009, in In Proceeding of ICUMT 2009, St. Petersburg. 2009. s. 220-226. ISBN: 9781-4244-3941- 6. [35] IMS; Research: IPTV: A Global Market Analysis [online]. c2006, [cit. 2008-0314], URL: http://www.imsresearch.com/. [36] Institute, I. S.: RFC 793. 1981, edited by Jon Postel. Available at http://rfc.sunsite.dk/rfc/rfc793.html. URL http://rfc.sunsite.dk/rfc/rfc793.html [37] J. Chesterfield, E. M. S.: An Extensible RTCP Control Framework for Large Multimedia Distributions. ICN07 - The Sixth International Conference on Networking, 2007. [38] Jarošová, L.: Měření vzdáleností stanic prostřednictvím ICMP protokolu v IP sítích. 2008, vysoké učení technickév Brně, Fakulta elektrotechniky a komunikačních technologií, 2008. Počet stran 63. Vedoucí bakalářské práce Ing. Radim Burget. garantem byl prof. Ing. Kamil Vrba, CSc. [39] Jelínek, M.; Komosný, D.; Burget, R.: Hierarchical Feedback Aggregation in IPTV. 2008, in Proceedings of the 12th WSEAS International Conference on Computers. Heraklion, Greece: WSEAS, 2008. s. 852-856. ISBN: 978-960-676685-5. [40] Klingaman, A.; Huang, M.; Muir, S.; aj.: PlanetLab Core Specification 4.0. Technická Zpráva PDN–06–032, PlanetLab Consortium, June 2006. [41] Komosný, D.: Hierarchický přenos signalizace pro multicast v IP sítích, Brno: Vysoké učení technické v Brně, Fakulta elektrotechniky a komunikačních technologií, 2008. 63 s. Habilitační práce. 2008. [42] Komosný, D.; Burget, R.: Multicast Feedback Control Protocol for Hierarchical Aggregation in Fixed and Mobile Networks. In PWC, IFIP, ročník 245, editace R. Bestak; B. Simák; E. Kozlowska, Springer, 2007, ISBN 978-0-387-74158-1, s. 456–467. 92

[43] Komosný, D.; Burget, R.; Müller, J.: Změny ve světě IPTV. 2009, elektrorevue - Internetový časopis (http://www.elektrorevue.cz), 2009, roč. 2009, č. 55, s. 1-11. ISSN: 1213- 1539. [44] Komosný, D.; Burget, R.; Morávek, P.; aj.: Feedback Transmission in LargeScale IPTV Sessions. 2009, in Proceeding of the 9th International Symposium on Communication and Information Technology 2009. Korea: IEEE, 2009. s. 1-6. ISBN: 978-1-4244-4522- 6. [45] Komosný, D.; Burget, R.; Novotný, V.: Simulation of Source-Specific Multicast used in Large-Scale IPTV Broadcasting. In Proceedings of the IASTED Asian Conference on Modelling and Simulation, 2007, beijing, China: IASTED, 2007. s. 163-167. [46] Komosný, D.; Burget, R.; Novotný, V.: Tree Transmission Protocol for Feedback Distribution in IPTV Systems. 2008, in Proceedings of the Seventh IASTED International Conference on Communication Systems and Networks. Palma de Mallorca, Spain: International Association of Science and Technology for Development, 2008. s. 1-7. ISBN: 978-0-88986-758-1. [47] Komosný, D.; KATHIRAVELU, G.; Jelínek, M.; aj.: Scalability Issues with the Hierarchical Feedback Aggregation for Large-Scale IPTV Systems. 2008, in Proceedings of the Seventh International Network Conference. Plymouth: Centre for Information Security and Network Research, University of Plymouth, UK, 2008. s. 15-26. ISBN: 978-1-84102-188-1. [48] Komosný, D.; Novotný, V.: Tree Structure for Source-Specific Multicast with feedback Aggregation. ICN07 - The Sixth International Conference on Networking, 2007. [49] Krajčíř, M.: Internetové souřadnicové systémy, Brno: Vysoké učení technické v Brně, Fakulta elektrotechniky a komunikačních technologií, 2008. 63 s. Vedoucí diplomové práce Ing. Radim Burget. 2008. [50] Ledlie, J.; Gardner, P.; Seltzer, M.: Network coordinates in the wild. In In: Proc. Symposium on Networked Systems Design and Implementation (NSDI, 2007. [51] Ledlie, J.; Pietzuch, P.; Seltzer, M.: Stable and Accurate Network Coordinates. icdcs, ročník 00, 2006: str. 74, ISSN 1063-6927, doi:http://doi. ieeecomputersociety.org/10.1109/ICDCS.2006.79.

93

[52] MacQueen, J. B.: Some Methods for Classification and Analysis of MultiVariate Observations. In Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability, ročník 1, editace L. M. L. Cam; J. Neyman, University of California Press, 1967, s. 281–297. [53] MGR, I.: IPTV Global Forecast – 2009 to 2013: Semiannual IPTV Global Forecast Report - Edition 1. May 2009. URL http://www.strategyanalytics.com/ [54] Müller, J.; Komosný, D.; Burget, R.: Optimizing Feedback Path in Hierarchical Aggregation. 2008, optimizing Feedback Path in Hierarchical Aggregation. Electronics, 2008, roč. 2008, č. 2, s. 3-8. ISSN: 1313-1842. [55] Müller, J.; Komosný, D.; Burget, R.; aj.: Advantage of Hierarchical Aggregation. 2008, international Journal of Computer Science and Network Security, 2008, roč. 2008, č. 8, s. 1-7. ISSN: 1738-7906. [56] Morávek, P.; Komosný, D.; Burget, R.: Study and Performance of Localization Methods in IP Based Networks: Vivaldi Algorithm. Journal of Network and Computer Applications, ročník 6, č. 5, 2010, ISSN 1084-8045. [57] Morávek, P.; Komosný, D.; Burget, R.; aj.: Lokalizační metody v IP sítích - Vivaldiho algoritmu s výškou. 2010, elektrorevue - Internetový časopis (http://www.elektrorevue.cz), 2010, roč. 2010, č. 4, s. 1-15. ISSN: 1213- 1539. [58] Nelder, J. A.; Mead, R.: A Simplex Method for Function Minimization. The Computer Journal, ročník 7, č. 4, January 1965: s. 308–313, doi:10.1093/comjnl/ 7.4.308. URL http://dx.doi.org/10.1093/comjnl/7.4.308 [59] Ng, E.; Zhang, H.: Predicting Internet network distance with coordiantes-based approaches. 2001. URL citeseer.ist.psu.edu/ng01predicting.html [60] Ng, E. T. S.; Zhang, H.: Towards global network positioning. In IMW ’01: Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, New York, NY, USA: ACM Press, 2001, ISBN 1581134355, s. 25–29, doi:http: //dx.doi.org/10.1145/505202.505206. URL http://dx.doi.org/10.1145/505202.505206 [61] Novotný, V.; Komosný, D.: Optimization of Large-Scale RTCP Feedback Reporting in Fixed and Mobile Networks. In ICWMC ’07: Proceedings of the Third International Conference on Wireless and Mobile Communications, 94

Washington, DC, USA: IEEE Computer Society, 2007, ISBN 0-7695-2796-5, str. 85, doi:http://dx.doi.org/10.1109/ICWMC.2007.63. [62] Olivka, P.: Stabilita hierarchické agregace pro internetové televizní vysílání. 2008, vysoké učení technickév Brně, Fakulta elektrotechniky a komunikačních technologií, 2010. Počet stran 63. Vedoucí bakalářské práce Ing. Radim Burget. garantem byl prof. Ing. Kamil Vrba, CSc. [63] Ott, J.; Chesterfield, J.; Schooler, E.: RTP Control Protocol (RTCP) Extensions for Single-Source Multicast Sessions with Unicast Feedback. Technická zpráva, Internet Engineering Task Force, Únor 2010. URL http://64.170.98.42/html/rfc5760 [64] Peterson, L.; Bavier, A.; Fiuczynski, M.; aj.: Towards a Comprehensive PlanetLab Architecture. Technická Zpráva PDN–05–030, PlanetLab Consortium, June 2005. [65] Peterson, L.; Muir, S.; Roscoe, T.; aj.: PlanetLab Architecture: An Overview. Technická Zpráva PDN–06–031, PlanetLab Consortium, May 2006. [66] Pias, M.; Crowcroft, J.; Wilbur, S.; aj.: Lighthouses for Scalable Distributed Location. In Proc. 2nd International Workshop on Peer-to-Peer Systems (IPTPS ’03), Berkeley, CA, USA, 20-21 February 2003. [67] Pietzuch, P.; Ledlie, J.; Mitzenmacher, M.; aj.: Network-Aware Overlays with Network Coordinates. icdcsw, ročník 0, 2006: str. 12, ISSN 1545-0678, doi:http: //doi.ieeecomputersociety.org/10.1109/ICDCSW.2006.76. [68] Piper, B.: US IPTV Market Sizing: 15.5 Million Subscribers by 2013. November 2009. URL http://www.strategyanalytics.com/ [69] Pospíšil, P.: Optimalizace predikce pozice v síti. 2008, fakulta elektrotechniky a komunikačních technologií. Ústav telekomunikací, 2008. Počet stran 82, Počet stran příloh 2. Diplomová práce. Vedoucí práce byl Ing. Radim Burget. garantem byl prof. Ing. Kamil Vrba, CSc. [70] Postel, J.: RFC 768: User Datagram Protocol. Srpen 1980, status: STANDARD. URL ftp://ftp.internic.net/rfc/rfc768.txt [71] Relovský, J.; Komosný, D.; Burget, R.: A Laboratory Solution for a Node Position Estimation in Internet. 2008, in New Information and Multimedia Technologies - NIMT 2008. Brno: VUT v Brně, 2008. s. 63-66. ISBN: 987-80214-3708-1. 95

[72] S. Ratnasamy, M. H. B. K., P. Francis; Shenker, S.: Topology-Aware Overlay Construction and Server Selection. June 2002, iNFOCOM’02. [73] Schulzrinne, H.; Casner, S.; Frederick, R.; aj.: RFC 3550: RTP: A Transport Protocol for Real-Time Applications. Technická zpráva, IETF, 2003. URL www.ietf.org/rfc/rfc3550.txt [74] Shan, Y.; Bajic, I. V.; Woods, J. W.; aj.: Scalable video streaming with finegrain adaptive forward error correction. IEEE Trans. Cir. and Sys. for Video Technol., ročník 19, č. 9, 2009: s. 1302–1314, ISSN 1051-8215, doi:http://dx. doi.org/10.1109/TCSVT.2009.2022788. [75] Sharma, P.; Xu, Z.; Banerjee, S.; aj.: Estimating network proximity and latency. SIGCOMM Comput. Commun. Rev., ročník 36, č. 3, 2006: s. 39–50, ISSN 01464833, doi:http://doi.acm.org/10.1145/1140086.1140092. [76] Shavitt, Y.; Tankel, T.: Big-bang simulation for embedding network distances in Euclidean space. In In Proceedings of IEEE INFOCOM, 2003. [77] Siadak, W.: Protocol Independent Multicast- Dense Mode (PIM-DM): Protocol Specification (Revised). [78] Spring, N.; Wetherall, D.; Anderson, T.: Scriptroute: A Public Internet Measurement Facility. 2002. URL citeseer.ist.psu.edu/spring02scriptroute.html [79] Srinivasan, S.; Hsu, P.; Holcomb, T.; aj.: Windows Media Video 9: Overview and Applications. ročník 19, č. 9, October 2004: s. 851–875. [80] Stoica, I.; Morris, R.; Karger, D.; aj.: Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. 2001, s. 149–160. [81] Tan, Y.; Peng, Y.; Li, S.; aj.: AFEC: An Advanced FEC Algorithm for Video Transmission Control over the Grid. In GCC Workshops, 2004, s. 753–760. [82] Tang, L.; Crovella, M.: Virtual landmarks for the internet. In IMC ’03: Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, New York, NY, USA: ACM, 2003, ISBN 1-58113-773-7, s. 143–152, doi:http: //doi.acm.org/10.1145/948205.948223. [83] de Vries, S.; Posner, M.; Vohra, R.: Polyhedral Properties of the K -median Problem on a Tree. Discussion Papers 1367, Northwestern University, Center for Mathematical Studies in Economics and Management Science, Duben 2003. URL http://ideas.repec.org/p/nwu/cmsems/1367.html 96

[84] Wiegand, T.; Sullivan, G. J.; Bjntegaard, G.; aj.: Overview of the H.264/AVC video coding standard. IEEE Trans. Circuits Syst. Video Techn., ročník 13, č. 7, 2003: s. 560–576. [85] Yin, H.; Cheng, F.; Zhang, D.: Advanced FEC Algorithm of Video Transmission Control over the Internet. In ICICTA ’09: Proceedings of the 2009 Second International Conference on Intelligent Computation Technology and Automation, Washington, DC, USA: IEEE Computer Society, 2009, ISBN 978-0-7695-38044-4, s. 33–36, doi:http://dx.doi.org/10.1109/ICICTA.2009.724. [86] Zhang, Q.; Guo, Q.; Ni, Q.; aj.: Sender-Adaptive and Receiver-Driven Layered Multicast for Scalable Video Over the Internet. ročník 15, č. 4, April 2005: s. 482–495. [87] Zheng, H.; Lua, E. K.; Pias, M.; aj.: Internet routing policies and round-triptimes. In In PAM, 2005.

97

VYBRANÁ LITERATURA AUTORA [56] Morávek, P., Komosný, D., and Burget, R., Study and Performance of Localization Methods in IP Based Networks: Vivaldi Algorithm. Elsevier, Journal of Network and Computer Applications, ISSN: 1084-8045, 2010. (Podíl autora: 10 %, impakt faktor: 1,111.) [9] Burget, R.; Komosný, D., Müller, J., Interactive Internet Television for Mobile Devices and Large-scale Areas. International Journal on Advances in Internet Technology, 2009, ISSN 1942-2652. (Podíl autora: 60 %, vyžádaná publikace.) [42] Komosný, D., Burget, R.: Multicast Feedback Control Protocol for Hierarchical Aggregation in Fixed and Mobile Networks. In PWC, IFIP, ročník 245, editace R. Bestak; B. Simák; E. Kozlowska, Springer, 2007, ISBN 978-0-387-74158-1, s. 456-467. (Podíl autora: 10 %, ocenění “Best Paper Award”.) [14] Burget, R., Komosný, D., Novotný, V., Integration of Host Position Prediction into Hierarchical Aggregation. International Conference of Networking, 2008, s. 740-745 (Podíl autora: 60 %, ocenění “Best Paper Award”.) [4] Burget, R.; Komosný, D. Real-time control protocol and its improvements for Internet Protocol Television. International Transaction on Computer Science and Engineering, 2006, ISSN 1738-6438 (Podíl autora: 60 %.) [5] Burget, R.; Komosný, D., Šimek, M., RTP/RTCP for Single Source Topologies. International Conference on Computer Science and Information Technologies, 2007, s. 223-224. (Podíl autora: 60 %.) [6] Burget, R.; Komosný, D., Šimek, M., Simulation of Large-Scale IPTV Systems for Fixed and Mobile Networks. International Conference on Computer Science and Information Technologies, Springer Verlag, 2007: s. 445—454, ISSN 15715736 (Podíl autora: 45 %.) [7] Burget, R.; Komosný, D., Šimek, M., Transmitting Hierarchical Aggregation Information Using RTCP Protocol. International Journal of Computer Science and Network Security, 2007, ISSN 1738-7906, vol. 7 No. 11 pp. 44-48 (Podíl autora: 10 %.)

98

[8] Burget, R.; Komosný, D., Müller, J., Best Effort Hierarchical Aggregation Tree for IPTV Signaling. International Journal of Computer Science and Network Security, 2008, roč. 2008, č. 8, s. 1-5. ISSN: 1738-7906. (Podíl autora: 60 %.) [11] Burget, R. and Müller, J. Accuracy Improvements for Network Position Estimation. Telecommunication and Signal Processing 2008. s. 65-68. ISBN: 978-963-06-5487-6, 2008. (Podíl autora: 90 %.) [33] Šimek, M., Komosný, D., Burget, R. One Source Multicast Model Using RTP in NS2. International Journal of Computer Science and Network Security, 2007, ISSN 1738-7906, vol. 7 No. 11 pp. 252-257. (Podíl autora: 10 %.) [34] Šimek, M., Komosný, D., Burget, R. aj.: Centralized Boundary Discovery Algorithms for Anchor- Free Localization in Wireless Sensor Networks. in In Proceeding of ICUMT 2009, St. Petersburg. 2009. s. 220-226. ISBN: 978-1-42443941- 6. (Podíl autora: 10 %.) [39] Jelínek, M., Komosný, D., Burget.: Hierarchical Feedback Aggregation in IPTV. Proceedings of the 12th WSEAS International Conference on Computers. Heraklion, Greece: WSEAS, 2008. s. 852-856. ISBN: 978-960-6766-85-5. (Podíl autora: 10 %.) [43] Komosný, D., Burget, R., Müller, J.,: Změny ve světě IPTV. Elektrorevue Internetový časopis (http://www.elektrorevue.cz), 2009, roč. 2009, č. 55, s. 111. ISSN: 1213- 1539. (Podíl autora: 10 %.) [44] Komosný, D., Burget, R., Morávek, P., aj.: Feedback Transmission in LargeScale IPTV Sessions. Proceeding of the 9th International Symposium on Communication and Information Technology 2009. Korea: IEEE, 2009. s. 16. ISBN: 978-1-4244-4522- 6. (Podíl autora: 10 %.) [45] Komosný, D., Burget, R., Novotný, V.: Simulation of Source-Specific Multicast used in Large-Scale IPTV Broadcasting. Proceedings of the IASTED Asian Conference on Modelling and Simulation, 2007, Beijing, China: IASTED, 2007. s. 163-167. (Podíl autora: 10 %.) [46] Komosný, D., Burget, R., Novotný, V.: Tree Transmission Protocol for Feedback Distribution in IPTV Systems. Proceedings of the Seventh IASTED International Conference on Communication Systems and Networks. Palma de Mallorca, Spain: International Association of Science and Technology for Development, 2008. s. 1-7. ISBN: 978-0-88986-758-1. (Podíl autora: 10 %.)

99

[54] Müller, J., Komosný, D., Burget, R.: Optimizing Feedback Path in Hierarchical Aggregation. Proceedings of the Seventh IASTED International Conference on Communication Electronics, 2008, roč. 2008, č. 2, s. 3-8. ISSN: 1313-1842. (Podíl autora: 10 %.) [55] Müller, J., Komosný, D., Burget, R.: Advantage of Hierarchical Aggregation. , international Journal of Computer Science and Network Security, 2008, roč. 2008, č. 8, s. 1-7. ISSN: 1738-7906. (Podíl autora: 10 %.) [57] Morávek, P., Komosný, D., Burget, R., aj.: Lokalizační metody v IP sítích - Vivaldiho algoritmu s výškou. International Journal of Internetový časopis (http://www.elektrorevue.cz), 2010, roč. 2010, č. 4, s. 1-15. ISSN: 1213- 1539. (Podíl autora: 10 %.) [71] Relovský, J., Komosný, D., Burget, R.: A Laboratory Solution for a Node Position Estimation in Internet. International Journal of New Information and Multimedia Technologies - NIMT 2008. Brno: VUT v Brně, 2008. s. 63-66. ISBN: 987-0-214-3708-1. (Podíl autora: 10 %.)

100

SEZNAM OBRÁZKŮ 1.1 1.2 1.3 2.1 2.2 3.1 3.2 4.1 4.2 4.3 4.4 4.5 4.6 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 7.1 7.2 7.3 7.4 8.1 8.2 8.3 9.1 9.2 9.3 9.4

Struktura sítě IPTV . . . . . . . . . . . . . . . . . . . . . . . . . . Model ISO/OSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Topologie stromu pro sběr signalizace . . . . . . . . . . . . . . . . . Zjednodušená topologie architektury IPTV . . . . . . . . . . . . . . délky periody TRR pro posílání signalizace . . . . . . . . . . . . . . Topologie IPTV s vzužitím SSM multicastu . . . . . . . . . . . . . Doba přenosu signalizace hierarchickým stromem . . . . . . . . . . Generovaný datový tok při měření vzdáleností mezi stanicemi . . . Přibližná struktura hierarchické podoby sítě. . . . . . . . . . . . . . Mapování rozložení stanic do fitness funkce - neoptimální . . . . . . Mapování rozložení stanic do fitness funkce - optimální . . . . . . . Princip algoritmu Vivaldi . . . . . . . . . . . . . . . . . . . . . . . Schéma systému Pharos . . . . . . . . . . . . . . . . . . . . . . . . Rekonstrukce polohy stanic . . . . . . . . . . . . . . . . . . . . . . Simulační nástroj pro zkoumání vlastností GNP algoritmu. . . . . . Princip generování šumu . . . . . . . . . . . . . . . . . . . . . . . . Transformace viruálního prostoru . . . . . . . . . . . . . . . . . . . Fixní a dznamické poziční uzly . . . . . . . . . . . . . . . . . . . . . Předpověď polohy stanic . . . . . . . . . . . . . . . . . . . . . . . . Simulační nástroj pro zkoumání vlastností GNP algoritmu. . . . . . Závislost doby RTT (ms) v závislosti na geografické vzdálenosti . . Závislost počtu směrovačů v závislosti vůči geografické vzdálenosti . Příklad aplikace algoritmu TTA na síť poskytovatele. . . . . . . . . Srovnání náhodné a optimalizované metody ustavení stromu . . . . Graf zefektivnění komunikace . . . . . . . . . . . . . . . . . . . . . Závislost výsledné doby na počtu FT v druhé vrstvě stromu. . . . . Schéma počátečního ustavení pozice FT stanic. . . . . . . . . . . . Poždadavek o ustavení hierarchického stromu . . . . . . . . . . . . . Schéma funkce FTM . . . . . . . . . . . . . . . . . . . . . . . . . . Hlavička TTP paketů . . . . . . . . . . . . . . . . . . . . . . . . . . Schéma výměny zpráv mezi jednotlivými typy stanic v rámci protokolu TTP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Diagram sekvencí pro požadavek vysílače o přidělení nového hierarchického stromu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schéma přenosu signalizace v rámci hierarchického stromu. S zastupuje vysílač, RFT kořenovou FT stanici, R přijímač a LM poziční bod. RR, RSI a FTS pak představují jednotlivé typy zpráv. . . . . .

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

15 16 19 23 25 26 28 31 34 36 36 37 41 45 47 48 48 49 50 51 52 53 55 57 59 61 64 66 66 69

. 70 . 71

. 72

9.5 9.6 9.7 9.8 9.9 9.10 9.11 9.12 10.1 10.2 10.3 10.4 10.5 10.6

Podoba aplikačního paketu RR zprávy . . . . . . . . . . . . . . . . . Registrační a deregistrační zpráva FTR. . . . . . . . . . . . . . . . . Definiční paket FTD sloužící pro definici role v hierarchickém stromu. Informativní paket FTI sloužící pro informování stanice FTM od ostatních stanic FT . . . . . . . . . . . . . . . . . . . . . . . . . . . . Paket FTS sloužící pro popis podoby hierarchického stromu. . . . . . Podblok paketu FTS - definice cíle zpětné vazby (FT). . . . . . . . . Podblok paketu FTS - definice cíle zpětné vazby (FT) v omezeném režimu pozičního bodu. . . . . . . . . . . . . . . . . . . . . . . . . . . Diagram sekvencí pro vytváření nového stromu. . . . . . . . . . . . . Aplikace vytvořeného IPTV vysílače (vlevo) a přijímače (vpravo). . . Simulační nástroj algoritmu GNP . . . . . . . . . . . . . . . . . . . . Simulační nástroj algoritmu TTP . . . . . . . . . . . . . . . . . . . . Struktura sítě Planetlab . . . . . . . . . . . . . . . . . . . . . . . . . Podoba aplikace nebula pro správu sítě Planetlab . . . . . . . . . . . Statistiky využití uzlu . . . . . . . . . . . . . . . . . . . . . . . . . .

73 74 75 75 76 76 77 77 79 80 81 82 83 85

SEZNAM TABULEK 2.1 4.1 7.1

Kompresní poměr kodeků používaných pro IPTV vysílání. . Ukázka výpisu cesty v síti prostřednictvím nástroje tracert. . Analytický výpočet extrému funkce pomocí nástroje Matlab. všech čtyř kořenů rovnice je uloženo na přiloženém CD. . . .

. . . . . 24 . . . . . 39 Řešení . . . . . 62

SEZNAM ALGORITMŮ A PŘÍLOH 1 2 3 4 5

Algoritmus Algoritmus Algoritmus Algoritmus Algoritmus

1: 2: 3: 4: 5:

Metoda Vivaldi . . . . . . . . . . . . . . . . . Myth . . . . . . . . . . . . . . . . . . . . . . Pharos . . . . . . . . . . . . . . . . . . . . . Tree Transmission Algorithm . . . . . . . . . Optimalizovaný Tree Transmission Algorithm

. . . . .

. . . . .

A Přílohy A.1 Obsah přiloženého CD . . . . . . . . . . . . . . . . . . . . . . A.1.1 Implementace protokolu TTP . . . . . . . . . . . . . . A.1.2 Knihovna pro podporu Source-specific Multicast pro formu JAVA . . . . . . . . . . . . . . . . . . . . . . . . A.1.3 Simulační knihovna JSimlib 3 . . . . . . . . . . . . . . A.2 Graf závislosti doby přenosu a počtu zařízení . . . . . . . . . .

104

. . . . .

. . . . .

. . . . .

. . . . .

38 40 42 56 58

105 . . . . 105 . . . . 105 plat. . . . 105 . . . . 105 . . . . 105

A

PŘÍLOHY

A.1 A.1.1

Obsah přiloženého CD Implementace protokolu TTP

Na přiloženém CD je kompletní implementace protokolu TTP pro ustavení a signalizaci stanic, která byla simulována a testována v síti Planetlab. Jedná se o implementaci přijímače (R), vysílače (S), agregační stanice (FT), kořenové agregační stanice (RFT) a manažera FT stanic (FTM). Veškerý zdrojový kód je licencován autorovi této práce pod open-source všeobecnou veřejnou licencí GNU GPLv31 a smí být použita k jak k nekomerčním tak komerčním účelům.

A.1.2

Knihovna pro podporu Source-specific Multicast pro platformu JAVA

V souvislosti s touto prací vznikla knihovna pro rozšíření platformy stávající verze platformy JAVA o podporu Source-specific Multicast. Na jejím základě jsme byli kontaktováni vedením specifikace vývoje nové verze platformy JAVA a požádáni o konzultace.

A.1.3

Simulační knihovna JSimlib 3

Jako součást této práce byla implementována simulační knihovna JSimlib v3, s jejíž pomocí lze používat identický kód jak pro simulaci, tak pro ostré nasazení v síťovém provozu.

A.2

Graf závislosti doby přenosu a počtu zařízení

Následující strana vyobrazuje závislost na počtu přijímačů, počtu FT stanic a vyznačuje oblast 15 sekund, která je jako racionální kompromis mezi dobou přenosu skrze hierarchický strom a požadavek na počet nutných FT stanic. (viz následující strana)

1

GNU General Public License, http://www.gnugpl.cz/

105

zvětšenofigure a) b) 1x FT, 100x zoomed a)

a) 1x FT

64

perioda přijímačů (TRR) [minuty]

perioda přijímačů (TRR) [minuty]

doba přenosu je pod 15 vteřin

0 1

šířka pásma (BWRTCP) (kbps) [kb/s]

25

60 00 32

doba přenosu je pod 15 vteřin

0

20 25

60

šířka pásma (BWRTCP) (kbps) [kb/s]

32

00

d) 30x FT

počet přijímačů (104) doba přenosu je pod 15 vteřin

0

64

12

0 92

80 20

6 25

19

0

šířka pásma (BW RTCP) (kbps) [kb/s]

00

32

počet přijímačů (miliony) doba přenosu je pod 15 vteřin

25

šířka pásma (BWRTCP) (kbps) [kb/s]

60 32

00

počet přijímačů (miliony) doba přenosu je pod 15 vteřin

f) 100x FT

perioda přijímačů (TRR) [minuty]

e) 50x FT

perioda přijímačů (TRR) [minuty]

80 19

0 28 1

64

64

0 12

12

19 60

25

32

00

počet přijímačů (miliony) doba přenosu je pod 15 vteřin

0

25

19

2

šířka pásma (BWRTCP) (kbps) [kb/s]

0

0 32

počet přijímačů (miliony)

00

počet přijímačů (miliony) doba přenosu je pod 15 vteřin

80 19

0 56

32

0 12

20

60

h) 500x FT

64 80

20

šířka pásma (BWRTCP) [kb/s] (kbps)

perioda přijímačů (TRR) [minuty]

g) 200x FT

12

80

20

šířka pásma (BWRTCP) [kb/s] (kbps)

64

0

80 19

perioda přijímačů (TRR) [minuty]

OM 100x ZO počet přijímačů (miliony)

perioda přijímačů (TRR) [minuty]

perioda přijímačů (TRR) [minuty]

c) 10x FT

1

0 12

20 19

64

64

0 28

20

šířka pásma (BWRTCP) (kbps) [kb/s]

60

25

00

32

počet přijímačů (miliony)

Rejstřík hierarchická agregace, 27 cíl zpětné vazby, 29, 74 FT manažer, 74 přijímač, 29 vysílač, 27, 72, 76 výpočet periody, 27 IPTV, 14, 21, 23, 24, 65, 69 RTCP, 17, 21, 22, 24, 66–68, 72 výpočet periody, 22 souřadnicové systémy Global Network Positioning, 31, 34, 37, 39, 44, 51, 73, 80 Myth, 39 Netvigator, 38 Pharos, 40 Vivaldi, 31, 37, 50

107