Paralelizace datových přenosů přes rozlehlé vysokorychlostní sítě

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE Fakulta elektrotechnická

Diplomová práce

Paralelizace datových přenosů přes rozlehlé vysokorychlostní sítě

Martin Čížek

Poděkování Rád bych poděkoval Ing. Antonínu Královi za vedení diplomové práce, množství užitečných rad a poznámek, Dr. Ing. Svenu Ubikovi za konzultace výzkumného záměru, sdružení Cesnet, z.s.p.o. za poskytnutí prostoru a prostředků k řešení projektu a Pavlu Vodrážkovi za pomoc s kreslením obrázků.

Prohlášení Prohlašuji, že jsem svou diplomovou práci vypracoval samostatně a použil jsem pouze literaturu a podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

Praha, 27. 1. 2005

Podpis / Signature

Anotace Paralelizace datových přenosů přes rozlehlé vysokorychlostní sítě Práce se zabývá paralelizací datových přenosů v počítačových sítích, zejména přístupem, kdy je paralelní přenos explicitně řízen koncovými stanicemi. Diskutovány jsou možnosti paralelizace na různých komunikačních vrstvách a je navržen systém provádějící paralelizaci nad transportní vrstvou. Systém také slouží jako framework pro implementaci různých paralelizačních přístupů. Dále je rozebírána realizace navržené architektury paralelizačního subsystému, jeho způsobu použití a měření vlastností. Klíčová slova: Paralelní přenosy, rozlehlé vysokorychlostní sítě

Abstract Parallelization of data transfers over wide-area high-speed networks This paper is concerned with the parallelization of data transfers in computer networks, especially with the approach where the parallelization is explicitly controlled by end stations. Parallelization alternatives on different communication layers are discussed. A system that allows parallalelization upon the transport layer and provides a framework for implementation and testing of various parallelization approaches is then designed. Successive sections analyze the implementation of the proposed parallelization subsystem architecture, its usage and measurements of characteristics. Keywords: Parallel transfers, wide-area high-speed networks

Obsah 1 Paralelizace datových přenosů 1.1

1.2

1.3

9

Motivace k paralelizaci přenosů . . . . . . . . . . . . . . . . . . . . . . . .

9

1.1.1

Terminologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.1.2

Neřízený paralelizmus

9

1.1.3

Paralelní přenos – explicitní řízení paralelizmu . . . . . . . . . . . . 10

1.1.4

Přenosy přes rozlehlé vysokorychlostní sítě . . . . . . . . . . . . . . 10

1.1.5

Shrnutí

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Možnosti paralelizace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1

Paralelizace na síťové vrstvě . . . . . . . . . . . . . . . . . . . . . . 11

1.2.2

Paralelizace na transportní vrstvě . . . . . . . . . . . . . . . . . . . 12

1.2.3

Paralelizace na aplikační vrstvě . . . . . . . . . . . . . . . . . . . . 13

Vrstva podpory paralelních přenosů . . . . . . . . . . . . . . . . . . . . . . 15 1.3.1

Požadavky kladené na paralelizační vrstvu . . . . . . . . . . . . . . 15

2 Návrh systému 2.1

2.2

2.3

17

Způsob dělení dat do dílčích přenosů . . . . . . . . . . . . . . . . . . . . . 17 2.1.1

Deterministické dělení . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1.2

Nedeterministické dělení . . . . . . . . . . . . . . . . . . . . . . . . 18

Kontext provádění protokolu . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1

Provádění protokolu v kontextu aplikačního programu . . . . . . . . 19

2.2.2

Asynchronní provádění protokolu . . . . . . . . . . . . . . . . . . . 19

Architektura systému . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.1

Komunikace s vláknem protokolu . . . . . . . . . . . . . . . . . . . 20

2.3.2

Sdílení soketů dílčích přenosů . . . . . . . . . . . . . . . . . . . . . 21

2.3.3

Rozvrh paralelního přenosu . . . . . . . . . . . . . . . . . . . . . . 22

2.4

Řídicí komunikace s protistranou . . . . . . . . . . . . . . . . . . . . . . . 23

2.5

Životní cyklus paralelního spojení . . . . . . . . . . . . . . . . . . . . . . . 24

5

2.5.1

Stavy paralelního spojení . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Implementace

30

3.1

Pojmy a struktury . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2

Vlákno protokolu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.3

3.2.1

Události . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2.2

Reakce na událost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.2.3

Ovladač paralelního přenosu . . . . . . . . . . . . . . . . . . . . . . 35

Library Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Vlastnosti paralelních přenosů 4.1

4.2

39

Paralelní přenosy po jedné fyzické trase . . . . . . . . . . . . . . . . . . . . 39 4.1.1

Přenos beze ztrát . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.1.2

Přenos se ztrátami . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Paralelní přenosy po více fyzických trasách . . . . . . . . . . . . . . . . . . 44

5 Závěr 5.1

46

Další výzkum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

A Příklady

48

A.1 Příklad aplikačního paralelizmu . . . . . . . . . . . . . . . . . . . . . . . . 48 B Programátorské rozhraní

49

B.1 Knihovna psock-mt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 B.2 Testovací nástroj psock-testperf . . . . . . . . . . . . . . . . . . . . . . . . 52 C Obsah CD-ROM

53

6

Seznam obrázků 2.1

Architektura systému psock . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2

Přechodový diagram paralelního soketu (zjednodušeno) . . . . . . . . . . . 27

2.3

Navazování paralelního spojení . . . . . . . . . . . . . . . . . . . . . . . . 28

2.4

Ukončování paralelního spojení . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1

Vztahy struktur v Protocol Space . . . . . . . . . . . . . . . . . . . . . . . 32

3.2

Princip algoritmu pollall . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.3

Vztahy struktur v Library Space

4.1

Propustnost v závislosti na počtu dílčích přenosů při různých hodnotách okénka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.2

Propustnost v závislosti na sumárním okénku . . . . . . . . . . . . . . . . 42

4.3

Nárůst okénka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.4

Propustnost v závislosti na počtu dílčích přenosů při ztrátovosti 0,01% . . 44

4.5

Propustnost dvou tras v závislosti na rozdělení kapacity . . . . . . . . . . . 45

. . . . . . . . . . . . . . . . . . . . . . . 38

7

Seznam tabulek 2.1

Příklad rozvrhu paralelního přenosu . . . . . . . . . . . . . . . . . . . . . . 22

4.1

Konfigurace měření paralelních přenosů po jedné fyzické trase . . . . . . . 40

4.2

Konfigurace měření paralelních přenosů po ztrátové trase . . . . . . . . . . 44

8

Kapitola 1 Paralelizace datových přenosů 1.1

Motivace k paralelizaci přenosů

Paralelizmus datových přenosů v sítích představuje jejich přirozenou vlastnost. Je dán jednak vlastní redundancí přenosových linek, jednak sdílením přenosového média, zejména pomocí časového a frekvenčního multiplexu. V dalších úvahách se zaměříme na paketové „Best-Effortÿ sítě a TCP/IP jako nejrozšířenějšího představitele.

1.1.1

Terminologie

Následující seznam uvádí základní použitou terminologii ve vztahu k paralelním přenosům obecně. Logický přenos poskytuje spolehlivý přenos dat „rourouÿ. Jedná se buď o klasický přenos nebo o paralelní přenos. Paralelní přenos je logický přenos, který ke své funkci používá několik přenosů dílčích. Dílčí přenos je komponentou paralelního přenosu. Jaká data po něm putují, jejich formát atd., určuje konkrétní implementace paralelního přenosu. Klasický přenos je logický přenos reprezentovaný TCP spojením.

1.1.2

Neřízený paralelizmus

Předpokládejme, že • provoz na síti se skládá z řady méně náročných, nezávislých logických přenosů, • intenzita zpráv λ [zpráv/sec] na trasách mezi dvojicemi uzlů má náhodný charakter a její střední hodnota v čase příliš nekolísá. 9

1.1 Motivace k paralelizaci přenosů

10

Tyto podmínky jsou ideální pro klasické využití síťového paralelizmu. Rozložení toků v síti je v hrubém měřítku dáno z vnějšku; určuje jej statická a dynamická1 konfigurace sítě. Pomocí vhodného uspořádání lze dosáhnout příznivé sumární propustnosti, malého středního zpoždění, nižšího zatížení jednotlivých tras a vyšší spolehlivosti.

1.1.3

Paralelní přenos – explicitní řízení paralelizmu

V případech, kdy • pro logický přenos je požadována velká kapacita sítě nebo • požadavky na náročnější přenosy vznikají mezi různými uzly a nárazově, kýžené vlastnosti paralelizmu pro náročný přenos klasickým způsobem nezískáme. K jejich dosažení je potřeba zabývat se cíleným využitím síťového paralelizmu pro logický přenos. Kromě zlepšení vlastností samotných přenosů pak též lze dosáhnout rovnoměrnějších nároků na síťovou infrastrukturu, nebo naopak maximálního vytížení kapacity části sítě. V komunikačních systémech, kde existuje více využitelných fyzických tras, znamená paralelizace datových přenosů jedinou možnost, jak v rámci logického přenosu překonat limity jednotlivých tras.

1.1.4

Přenosy přes rozlehlé vysokorychlostní sítě

Další požadavky na paralelizaci pramení z vlastností používané síťové infrastruktury. Nejrozšířenější transportní protokol TCP vykazuje v oblasti přenosů přes rozlehlé vysokorychlostní sítě některé nepříjemné vlastnosti: • Při použití přenosových bufferů s kapacitou menší než je kapacita trasy2 nedostáváme plný výkon. • Při použití přenosových bufferů s kapacitou větší než je kapacita trasy též obvykle dostaneme suboptimální výkon, neboť řízení zahlcení (congestion control) způsobuje oscilace velikosti okénka (congestion window) [1]. • Přestože existuje mnoho úprav TCP pro zlepšení jeho vlastností, ne vždy je možné je aplikovat.3 Paralelizace tyto nedostatky pochopitelně nevyřeší, nicméně může značnou měrou snížit jejich projevy. 1

Na síťové úrovni jsou to směrovací protokoly a policy routing. U aplikačního modelu klient-server stojí za zmínku škálování pomocí časově a geograficky proměnných DNS překladů. Předním dodavatelem tohoto řešení je společnost Akamai, používá je např. vyhledávač Google. 2 Součin bandwidth.delay, viz část 4.1.1. 3 Aplikaci úprav je potřeba provést u obou koncových stanic.

1.2 Možnosti paralelizace

1.1.5

11

Shrnutí

Ačkoliv je paralelizmus na různých úrovních již nasazen, má smysl jej nadále zkoumat. Jednak kvůli prudkému rozvoji síťových technologií, jednak pro možnosti, jež získáme jeho explicitním řízením.

1.2

Možnosti paralelizace

Paralelizaci datových přenosů lze provádět mnoha způsoby; zde rozebereme několik možností opírajících se o architekturu klasických sítí TCP/IP.

1.2.1

Paralelizace na síťové vrstvě

Podpora redundance tras ve směrovačích a operačních systémech je dnes samozřejmostí. Modernější systémy podporují rozkládání zátěže (load balancing), tedy explicitní využití síťového paralelizmu. Paralelizaci na síťové vrstvě lze řídit právě pomocí pravidel pro load balancing. Pravidla rozkládání zátěže by měla zachovávat příslušnost datagramů každého přenosu k jedné zvolené trase; jinými slovy, jsou-li X a Y dva datagramy náležící témuž přenosu, pro oba by měl být použit stejný záznam směrovací tabulky. V opačném případě se síť pro transportní protokol jeví nestabilně, selhává např. predikce RTT a neuplatní se různé heuristiky vycházející z předpokladu „slušnéhoÿ chování sítě (FIFO). Důsledkem je pochopitelně nepříznivý vliv na výkon transportního protokolu [6]. Jestliže ale má být zachována příslušnost daného přenosu k určité trase, není možné jej paralelizovat. Řešení je tedy potřeba hledat na vyšších vrstvách síťového modelu. Dostupné implementace • Jádro OS Linux – síťový subsystém iproute2 implementuje policy routing; výběr směrovacích tabulek lze kromě běžných pravidel (zdrojová IP adresa) provádět pomocí hodnoty fwmark4 , • PF: The OpenBSD Packet Filter, • směrovače, např. Cisco IOS Server Load Balancing (SLB). 4

Číselná značka, kterou paket udržuje po dobu svého života v jádře. Lze ji libovolně nastavovat v subsystému netfilter (filtrování paketů v Linuxu).


1.2.2

12

Paralelizace na transportní vrstvě

Poznámka 1.1 Striktně vzato, až na této úrovni lze hovořit o paralelních přenosech, neboť na nižších vrstvách nejsou přenosy definovány. Na transportní vrstvě se lze rozdílným parametrům jednotlivých přenosových tras přizpůsobit, navíc sledováním těchto parametrů lze paralelní přenos inteligentně optimalizovat. Využití existujícího transportního protokolu Pro jednotlivé konkurentní přenosy, resp. trasy lze použít existující transportní protokol. Podpora paralelních přenosů pak bude tvořit komunikační mezivrstvu, která bude používat existující transportní vrstvu podobně jako klasické aplikace, nicméně pro skutečnou aplikaci bude poskytovat funkcionalitu transportní vrstvy. Jako transportní protokol dílčích přenosů se nabízí TCP. Jeho uplatněním lze získat jisté výhody: • využití prověřené a všeobecně přijaté metody přenosu, • implementované řízení toku pro jednotlivé dílčí přenosy, • lepší koexistence s ostatním provozem na síti (spravedlnost, stabilita), • průchodnost síťovou infrastrukturou (přes různé stavové firewally, NAT N:1 apod.). Z použití TCP zároveň plynou možné nevýhody: • Všeobecně přijatá metoda přenosu může mít své nedostatky (viz sekce 1.1.4 na str. 10). Ačkoliv projevy některých nedostatků lze paralelizací odbourat5 , vlastní slabiny samozřejmě přetrvají. • Řízení toku jednotlivých přenosů nemusí být pro logický přenos jako celek optimální. • Případné retransmise se provádí vždy po stejném (a potenciálně problémovém) spojení, na němž se paket ztratil. • Potvrzení paketů odcházejících určitou trasou se vždy vracejí toutéž. Bez tohoto omezení by bylo možné získat určitý prostor pro zefektivnění paralelního přenosu. • Uspořádání přijatých paketů se nejprve provádí na jednotlivých TCP spojeních. Pokud paket nebo skupina paketů na spojení „předběhneÿ, TCP musí počkat na všechny nepřijaté pakety s nižším sekvenčním číslem; pak teprve předá data nadřazené vrstvě. Nicméně nadřazenou vrstvou je právě diskutovaná vrstva paralelizační, která by eventuálně uměla naplánovat i takto „předběhléÿ pakety dříve. 5

A také je to naším cílem.


13

Dostupné implementace • PSockets – C++ knihovna pracující nad TCP sokety, implementuje dělení dat do bloků konstantní délky metodou round-robin.6 Klade si za cíl dosáhnout výkonu, jaký by síť měla s optimálně vyladěnými parametry (zejména velikost bufferů pro TCP okénka), bez nutnosti vlastní změny parametrů. Vytyčený cíl knihovna plní; nicméně způsob, kterým jej dosahuje, je v podstatě jen změna parametrů sítě (zvětšení sumárního okénka a úprava koeficientů výpočtu Window a Threshold). Použitý algoritmus je vhodný pro přenosy po jedné společné trase. Průměrná celková propustnost paralelního přenosu je dána n-násobkem propustnosti nejpomalejšího dílčího přenosu, kde n je počet dílčích přenosů. To pochopitelně představuje omezení, pokud mají dílčí přenosy různé podmínky (různé fyzické trasy, stochastická frontová disciplína na trase, . . . ). V případě identických podmínek pro dílčí přenosy může tento přístup být výhodný díky stabilitě jejich zatížení.

1.2.3

Paralelizace na aplikační vrstvě

Zatímco transportní vrstva může paralelně přenášet jen data v rámci přenosových bufferů, aplikační vrstva může využít skutečného paralelizmu daného podstatou problému, který řeší.7 Vždy se ale jedná o vlastnost specifickou pro konkrétní aplikaci, a proto její využití zůstává na programátorech. Poznámka 1.2 S ohledem na použitou terminologii nepředstavují paralelně využívaná aplikační spojení „paralelní přenosÿ, ale jsou chápána jako nezávislé klasické přenosy. Uplatnění aplikačního paralelizmu Přestože aplikace s vlastním paralelizmem má potenciál výhodně využít paralelizmu síťového, narážíme na praktická omezení. Aby aplikace mohla efektivně využít přenosového paralelizmu, je potřeba vyřešit zejména tyto otázky: • Bude umět namapovat své potřeby na konkrétní infrastrukturu? • Bude nezávislost dat procházejících různými přenosy skutečně velká? Ukázku aplikace, kde tomu tak není, uvádí příklad A.1 na str. 48. 6

V terminologii autorů PSockets je přístup nazýván „network strippingÿ. Nemusí se nutně jednat o komplikované paralelní algoritmy. Rozhodující je dostupnost vzájemně nezávislých zdrojů/konzumentů dat, a to na obou stranách. Může jít i o obyčejný soubor – stačí jej vícenásobně otevřít, pozice jednotlivých otevřených souborů vhodně nastavit voláním lseek() a dále číst z různých pozic, resp. zapisovat do různých částí souboru najednou. 7


14

• Lze optimálně využít všech přenosů? Pokud aplikace bude využívat některá spojení na maximum, zatímco jiná zanedbatelně, neplní náš záměr. • Bude umět přemapovat data na různé přenosy? Jako příklad, kdy je přemapování žádoucí, může posloužit přenos souboru dvěma spojeními po dvou fyzických trasách. Předpokládejme, že soubor je přenášen po polovinách a že první trasa je 2x rychlejší než druhá. Lze snadno nahlédnout, že bez přemapování bude přenos trvat až o polovinu déle. • Nebude suplovat funkčnost paralelizace na transportní vrstvě? Výše uvedené problémy lze samozřejmě vyřešit. Obnáší to ale psaní nepříjemného kódu, který nakonec plní funkce paralelizace na transportní vrstvě. Stojí proto za zvážení, zda tyto starosti raději nepřenechat dedikovanému subsystému. Podpora nezávislých aplikačních přenosů Potřebuje-li aplikace přenášet více toků naráz, může vytvořit příslušný počet soketů a otevřít potřebná spojení. Navazovat nová spojení je ale bohužel drahé, nepříjemné a v dnešní době firewallů a NATů často problematické.8 Na to mysleli autoři protokolu SCTP [8]. SCTP umožňuje přenos více nezávislých toků v rámci jedné asociace. Dostupné implementace Příkladů existuje řada, zde je několik vybraných: • GridFTP [11], bbFTP [10] – přenosy souborů s podporou paralelních datových toků, • pscp [5] – rozšíření scp o podporu paralelních přenosů, • HTTP 1.0 a vyšší – v požadavku lze uvést hlavičku „Rangeÿ a vyžádat tak určitou část objektu. Pokud server vyhoví, odpoví kódem 206 (Partial Content) a v hlavičkách upřesní, jaký rozsah posílá. Ačkoliv tato vlastnost není primárně určena k paralelním přenosům, mnoho tzv. „download managerůÿ ji k tomu využívá. 8

Z těchto důvodů se často od nezávislých přenosů upouští a nezávislá data se přenášejí sekvenčně jedním spojením. Později posílané zprávy se tak stávají zcela závislé na přenosu a doručení dřívějších zpráv.

1.3 Vrstva podpory paralelních přenosů

1.3

15

Vrstva podpory paralelních přenosů

Snahou je poskytnout aplikacím možnost využívat paralelní přenosy bez podstatnějších změn jejich struktury. Vrstvu podpory paralelních přenosů je tedy potřeba začlenit pod aplikační vrstvu9 . Paralelizace na síťové vrstvě (sekce 1.2.1) též není pro naše účely vhodná, zvoleno tedy bylo řešení na, resp. nad transportní vrstvou (sekce 1.2.2). Pro dílčí přenosy je použito TCP, zejména pro dostupnost, rozšířenost a snadnou implementovatelnost. Nevýhody použití TCP zmíněné v 1.2.2 lze v současné fázi vývoje zanedbat. Uplatnění TCP též dovoluje zkoumat chování paralelních přenosů ve vztahu ke klasickým TCP přenosům.

1.3.1

Požadavky kladené na paralelizační vrstvu

Řešení by mělo vyhovovat následujícím nárokům: • flexibilita paralelního přenosu, možnost nastavovat parametry voláním API, • jednoduchost pro uživatele – použití vycházející ze standardního rozhraní BSD soketů. Ani specifická volání API by většinou neměla být nutná – v případě testů existujících aplikací se systémem by implicitní parametry mělo být možné nastavit pomocí konfiguračního souboru knihovny, • možnost použití alternativních algoritmů a strategií dělení dat mezi přenosy a jejich rekonstrukce. Možnosti na této úrovni jsou rozmanité, proto by knihovna měla zároveň sloužit jako framework pro implementaci dalších algoritmů/strategií, • schopnost automatického vyjednání parametrů (počet dílčích přenosů, algoritmus) při spojování, • možnost relativně snadného vývoje – alespoň v počátečních fázích, • malá zátěž CPU a sběrnic, • maximálně konkurentní běh všech komponent. Tzn. instance protokolu paralelních přenosů nesmí omezovat (blokovat) aplikaci ani sebe navzájem. Naopak činnost/nečinnost aplikace nesmí blokovat protokol. Framework pro alternativní algoritmy paralelního přenosu musí umožňovat vzájemné neblokování jednotlivých přenosů (ačkoliv konkrétní algoritmus může definovat závislosti), • zobecnitelnost; struktura systému by měla posloužit dalšímu výzkumu, měla by se hodit i pro případnou implementaci v jádře OS. 9

Zde máme na mysli funkční význam vrstvy; technicky může implementace pracovat právě na aplikační vrstvě.

1.3 Vrstva podpory paralelních přenosů

16

Základy architektury by mělo být možné použít pro tato na sebe navazující zobecnění: 1. oddělení kontextu řízení paralelizačního protokolu a uživatele paralelního soketu na různé výpočetní uzly, 2. uživatelem paralelního soketu se stane více uzlů; jinými slovy data bude generovat/zpracovávat více uzlů, ale protokol se bude provádět centrálně, 3. plná distribuce provádění protokolu (tzn. i protokol se bude provádět na více uzlech).

Kapitola 2 Návrh systému Tato kapitola se zabývá koncepcemi realizace paralelizačního systému postaveného nad transportní vrstvou (viz sekce 1.3 na str. 15). Diskutovány jsou klíčové funkce systému, možnosti, jak je uskutečnit, a zvolená řešení. Deklarace záměru. Cílem je vytvořit knihovnu podpory paralelních přenosů pro uživatelské aplikace splňující požadavky ze sekce 1.3.1. Dílčí přenosy budou uskutečněny protokolem TCP s využitím standardních BSD soketů. Hlavním výstupem bude sdílená knihovna a příslušné hlavičkové soubory. Implementační platforma. Projekt je implementován v jazyce C a používá POSIX vlákna. Hlavní vývojovou a testovací platformou pro koncové stanice je OS Linux. Plánovány jsou také testy na jiných systémech.

2.1

Způsob dělení dat do dílčích přenosů

Jedním z požadavků na systém je podpora více algoritmů paralelního přenosu. Mezi nejdůležitější charakteristiky algoritmu patří strategie dělení dat do dílčích přenosů. Aby systém mohl pokrýt různé přenosové algoritmy, je vhodné způsoby dělení dat do přenosů zmapovat.

2.1.1

Deterministické dělení

V případě deterministického dělení vysílač v každém okamžiku ví, kterým dílčím přenosem bude odesílat následující blok dat. Přijímač zase vždy zná dílčí přenos, z něhož získá očekávaná data. Mezi algoritmy s deterministickým dělením patří round-robin a jeho modifikace. i-tý blok se pošle i mod n -tým dílčím přenosem. Bloky mohou mít konstantní nebo variabilní

17

2.2 Kontext provádění protokolu

18

velikost. Variabilní velikost bloku umožňuje paralelní přenos přizpůsobovat požadavkům aplikace a stavu sítě (na základě statistických údajů). Na druhou stranu bloky o variabilní délce je potřeba doplnit o údaj s jejich délkou. Další informace o algoritmu round-robin se nachází v sekci 3.2.3 na str. 35.

2.1.2

Nedeterministické dělení

V tomto případě přijímač a/nebo vysílač nemusí vždy znát dílčí přenos použitý pro následující transfer. Typickým příkladem nedeterministického dělení je řešení, kdy je použitý přenos určován oznámením nižší vrstvy o připravenosti k odeslání/příjmu (tento přístup tvoří základ algoritmu pollall – sekce 3.2.3 na str. 35). Nedeterministické dělení je flexibilnější než deterministické, umožňuje algoritmu okamžitou reakci na změny v síti a jiné události, usnadňuje případnou rekonfiguraci paralelního přenosu. Naproti tomu vyžaduje, aby s jednotlivými bloky byla přenášena i synchronizační informace (např. v podobě číslování bloků), což také klade vyšší nároky na výpočetní výkon koncových stanic. Ověření funkce. Účinnost přenosu pomocí paralelních TCP spojení a metody roundrobin ukazuje [13]. Pro ověření základních vlastností paralelního přenosu s nedeterministickým dělením přenášených dat byla vytvořena zjednodušená verze paralelizačního systému. Implementován byl algoritmus, který odesílá bloky dle připravenosti soketů, a byla provedena základní měření [3]. Nároky na systém. Je zřejmé, že různé přístupy distribuce dat v rámci paralelního přenosu kladou různé nároky na činnost systému. Zatímco deterministické je méně náročné a většina operací pro jeho zajištění navazuje na aplikační volání systému, u nedeterministického dělení je obvykle potřebné řadu úkonů provádět nezávisle na běhu aplikace. Dělení a rekonstrukce přenášených dat představují klíčové úkoly protokolu paralelizačního systému, a jsou proto zohledněny i v následující sekci, věnované způsobu implementace protokolu.

2.2

Kontext provádění protokolu

Běh systému tohoto druhu vyžaduje uchovávat mnoho stavových informací a reagovat na různé události jako připravenost dílčího přenosu či zprávu protistrany. Obecně tuto činnost budeme nazývat „provádění protokoluÿ.

2.2 Kontext provádění protokolu

2.2.1

19

Provádění protokolu v kontextu aplikačního programu

Tento způsob lze též označit jako synchronní provádění, neboť místa přechodů mezi aplikačním programem a kódem realizujícím protokol jsou jasně dána. Při provádění netriviálního protokolu v rámci volání sdílené knihovny hrozí, že jeho funkce utrpí dlouhými intervaly mezi knihovními voláními a že v okamžicích volání naopak vzniknou zbytečné prostoje.1 Mezi možnosti, jak tyto potíže zmírnit, patří: • Kooperace ze strany aplikace v podobě konvencí používání speciálních knihovních volání (hooků). Na unixových systémech jsou obzvlášť výhodné funkce (wrappery, obálky) obalující volání poll(), select(), sleep() apod. Knihovna pak může čekat na časové události („timeoutyÿ) spolu s událostmi na svých a uživatelových souborových deskriptorech najednou. Tato metoda je implementována např. v knihovně sctplib [9]. • Programování řízené událostmi. Uživatel knihovně oznámí události, které jej zajímají, a obslužné funkce (handlery, callbacky), které je budou obsluhovat. Poté předá knihovně řízení. Při výskytu daných událostí knihovna volá obslužné funkce oznámené aplikací. V podstatě se ale jedná o původní problém obrácený naruby. V předchozím případě mohl uživatel zablokovat protokol nevoláním knihovních funkcí. Tentýž efekt nastává i v tomto případě, pokud aplikační obsluha trvá neúměrně dlouho. Metoda je vhodná tam, kde je běh programu zcela podřízen síťovým událostem. Využívá ji opět sctplib [9] nebo např. LIBPCAP [12].

2.2.2

Asynchronní provádění protokolu

V tomto případě je kód protokolu aktivován nezávisle na běhu aplikace, ta se tedy nemusí o nic starat. Vzhledem k požadavkům ze sekce 1.3.1 a nárokům různých přístupů dělení dat bylo zvoleno právě toto řešení. Asynchronní provádění protokolu lze technicky zajistit dvěma způsoby. Prvním z nich je přímá aktivace kódu protokolu, zejména pomocí přerušení. Tato metoda se používá v jádře operačního systému; v omezené míře ji lze použít i v uživatelském prostoru při vhodném nastavení generování a obsluh signálů.2 Druhým způsobem je provádění protokolu v samostatném vlákně, kdy se o přepínání kontextu stará operační systém. 1

Např. při každém čtení algoritmem s nedeterministickým dělením dat by bylo potřeba vyzvednout události na dílčích přenosech, přečíst hlavičky přijatých bloků, naplánovat jejich příjem a obsloužit případné zprávy od protistrany. Teprve pak by mohla operace pokračovat. 2 Sledování událostí na souborových deskriptorech lze zajistit nastavením F SETSIG pomocí fcntl(), časové události lze plánovat voláním alarm().

2.3 Architektura systému

20

Poněvadž první zmíněný přístup je pro implementaci v uživatelském prostoru poměrně problematický3 , byl zvolen způsob, kdy se protokol provádí v samostatném vlákně. Aby byly výhody asynchronního přístupu maximálně využity, budeme navíc klást na kód projektu tyto požadavky: • Kód provádějící protokol smí uskutečňovat jen taková blokující volání, která čekají na všechny události relevantní pro daný stav instance protokolu. • Kód sdílené knihovny musí být časově i paměťově nenáročný. Blokovat smí ve dvou případech. Jednak záměrně, pokud to vyžaduje sémantika prováděné operace, např. paccept() při čekání na spojení. Jednak při potřebě komunikace typu požadavek/odpověď s vláknem, v němž je prováděn protokol – předchozí nárok na kód provádějící protokol zaručuje rychlou odezvu.

2.3

Architektura systému

Základní koncepci navrženého systému psock zachycuje obr. 2.1. Klíčovou roli hrají dvě komponenty: Vlákno protokolu (Protocol Thread, Protocol Space) je program realizující chod protokolu. Zejména reaguje na události na deskriptorech dílčích přenosů, požadavky uživatele, požadavky z Library Space, zprávy protistrany a časové události. Library Space je kód využívající služeb vlákna protokolu; zahrnuje jednak uživatelský program, jednak implementaci sdílené knihovny nazvané psock-mt 4 . Knihovnu volá uživatel prostřednictvím jejího API, ta provádí potřebné úkony včetně vlastní komunikace s vláknem protokolu. Knihovna plní i další úlohu – snaží se vytvořit obálky (wrappery) některých systémových funkcí tak, aby bylo možné existující síťové programy upravit pro využití psock s co nejmenšími zásahy. Pod pojmem Library Space se bude nadále rozumět především implementace sdílené knihovny psock-mt.

2.3.1

Komunikace s vláknem protokolu

Vlákno protokolu a aplikační program spolu musí komunikovat. Pro vzájemnou komunikaci Library Space a Protocol Space definujeme komunikační rozhraní, dále označované 3

Jedním z důvodů je nemožnost koexistence s obsluhami signálů, které definuje uživatel nebo které používají některá knihovní volání, např. sleep(). 4 psock multithreaded.


21 Library Space

User API

Association Association Distribution Distribution Protocol Thread

Dispatching Dispatching Scheduling Scheduling

(9) (6) (10)

(7)

(8)

Control Control Engine Engine

(1)

(5) (4)

Dispatching Dispatching Execution Execution

(2)

Operating System Operating System (allocated (allocated control sockets) control sockets)

(3)

Operating Operating System System (allocated (allocated data sockets) data sockets)

Obrázek 2.1: Architektura systému psock PSCIF 5 . Toto rozhraní je pro větší flexibilitu návrhu definováno obecně, bez předepsané implementace. Ve verzi psock běžící v rámci jedné stanice může být realizováno jako sdílená paměť, unixový soket, fronta zpráv; v případné pozdější distribuované verzi psock může jít o UDP nebo TCP soket či volání knihovny MPI6 .

2.3.2

Sdílení soketů dílčích přenosů

Pro minimalizaci komunikační režie lze využít faktu, že kontexty vlákna protokolu a Library Space sdílí souborové deskriptory. Bude-li korektně vyřešena synchronizace a bude-li kód Library Space vědět, kdy a jakým způsobem, z kterých dílčích přenosů a v jakém pořadí má přijímat data, může vyřizovat uživatelské požadavky na příjem dat a tato umisťovat přímo do bufferu poskytnutého uživatelem. Analogicky, bude-li Library Space 5 6

Parallel Socket Controller Interface. Message Passing Interface, http://www-unix.mcs.anl.gov/mpi/.


22

vědět, které dílčí přenosy použít k odesílání a jak, může přímo odesílat uživatelská data bez nutnosti použití pomocného bufferu. Úloha vlákna protokolu pak bude spočívat ve sledování událostí na soketech, zpracování řídicích informací a předávání instrukcí Library Space. Stejný přístup lze aplikovat i v případě, že je možné použít duplikované deskriptory – tedy takové, které reprezentují tentýž soket. Toho lze využít pro zajištění dědění paralelního soketu při volání fork(). Princip oddělení datového a řídícího přístupu k dílčím přenosům lze dále uplatnit i při pozdějším rozšíření psock na distribuovanou verzi.

2.3.3

Rozvrh paralelního přenosu

Sdílení soketů dílčích přenosů umožňuje eliminovat kopírování dat mezi Library Space a vláknem protokolu. Aby byl Library Space schopen samostatně provádět příjem a odesílání dat, udržuje pro každý logický přenos datovou strukturu rozvrh, obsahující instrukce, jak má tyto činnosti provádět (které dílčí přenosy použít, kolik dat po nich poslat atd.). Tabulka 2.1 zachycuje ukázku, jak může vypadat rozvrh pro tři dílčí přenosy. Rozvrh obsahuje nezávislé pozice pro čtení a pro zápis. Každá pozice obsahuje identifikátor dílčího přenosu („kanonický indexÿ) a délku bloku k přenosu.7 Dále si knihovna pamatuje pozice v rozvrhu pro čtení i pro zápis. Má-li provést operaci, pro niž není aktuální pozice v rozvrhu vyplněna, musí počkat, až ji obdrží od vlákna protokolu.8 Pozice obou rozvrhů jsou využívány cyklicky. Pozice v rozvrhu Kanonický index dílčího přenosu; délka bloku – čtení Kanonický index dílčího přenosu; délka bloku – zápis Pozice v rozvrhu pro čtení Pozice v rozvrhu pro zápis

0

1

2

2; 1448 –

– 0; 1448

0; 1448 1; 1448

0 1

Tabulka 2.1: Příklad rozvrhu paralelního přenosu Protocol Space potřebuje k tvorbě záznamů (instrukcí) přijímacího a vysílacího rozvrhu zejména následující podklady: • události na soketech dílčích přenosů, • hlavičky datových bloků z dílčích přenosů, • notifikace o provedeném příjmu/odeslání bloku a jeho výsledku. 7 8

Ve skutečné implementaci obsahuje i další informace. V případě neblokujících volání vrátí chybu.

2.4 Řídicí komunikace s protistranou

23

Dostupnost prvních dvou uvedených je zajištěna sdílením souborových deskriptorů, třetí podklad zajišťuje rozhraní PSCIF. Protocol Space má tedy všechny informace potřebné pro tvorbu rozvrhu a do Libary Space je předává opět pomocí PSCIF.

2.4

Řídicí komunikace s protistranou

Kromě přenosu datových bloků dílčími přenosy je také potřeba určitá výměna metainformací, zejména při navazování a ukončování spojení. Pro tento účel je dedikováno tzv. řídící spojení (Control Stream). Kromě přenosu řídících zpráv též slouží k reprezentaci celého paralelního soketu – adresa paralelního soketu je ve skutečnosti adresou jeho řídícího soketu. Koncové stanice si vyměňují následující řídící zprávy. HELLO – iniciační zpráva, zasílaná ihned po spojení řídícího streamu. Obsahuje: • identifikátor protokolu zabraňující špatné interpretaci náhodného spojení s jiným protokolem, • verzi psock, která se skládá ze trojice: major a minor verze, patchlevel. Aby stanice mohly komunikovat, musí se major a minor verze shodovat. • doporučený nrcmd a maximální nmax počet dílčích přenosů, • identifikátor ovladače paralelního přenosu (viz sekce 3.2.3 na str. 35), • prioritu požadovaného ovladače paralelního přenosu. Na zprávu HELLO stanice neodpovídají, neboť obě strany jsou schopny určit potřebné parametry – počet dílčích přenosů a ovladač – ihned po jejím přijetí. Počet dílčích přenosů n se vypočte jako n = min(max(nrcmd,1 , nrcmd,2 ), nmax,1 , nmax,2 ).

(2.1)

Ovladač se vybírá na základě oznámených priorit; jsou-li stejné, upřednostní se navazující strana. STREAM ANNOUNCE – touto zprávou se druhé straně oznamují informace o dostupných datových soketech: • dostupný mód soketu (aktivní, pasivní, oba), • adresa, na níž bude datový soket naslouchat, resp. z které se bude připojovat, • identifikátor tzv. svazku přenosů – rezervován pro pozdější využití; bude sloužit k ovlivnění způsobu, jakým se mají dílčí přenosy sdružovat, • identifikátor trasy – rezervován pro pozdější využití.

2.5 Životní cyklus paralelního spojení

24

Po přijetí zprávy se vypočte párování soketů. Není-li dosažen potřebný počet dvojic, lze seznam nabízených soketů upravit a poslat zprávu znovu. Poznámka 2.1 Zprávy HELLO a STREAM ANNOUNCE nepoužívají systém dotaz/odpověď, jak je zvykem v modelu klient/server. Využívá se plného duplexu a zprávy jsou posílány „proti soběÿ (viz též obr. 2.3). Odpověď se posílá pouze v případě chyby. Postup má za cíl zkrátit dobu navazování spojení. SHUTDOWN – oznámení o finalizaci paralelního přenosu. Formálně se vyskytuje ve dvou variantách – žádost a odpověď. Obsah zprávy je určen ovladačem paralelního přenosu, typicky je to číslo posledního odeslaného bloku. Ukončování přenosu zpravidla probíhá tak, že jej jedna strana iniciuje žádostí SHUTDOWN a druhá zareaguje odpovědí SHUTDOWN. Stanice ale musí počítat i se situací, kdy dojde k současnému vyslání žádostí SHUTDOWN. Přesný formát zpráv se nachází v souboru src/include/net/psock/psockmsg.h v implementaci projektu.

2.5

Životní cyklus paralelního spojení

Dosud byla diskutována především činnost při přenosu dat. Nicméně než je možné přenos zahájit, musí paralelní soket projít několika iniciačními fázemi. Stejně tak po uzavření je potřeba provést finalizaci. Vývoj paralelního spojení s vybranou částí přechodů měnících stav je zachycen na obr. 2.2. Stav paralelního spojení a další data podstatná pro paralelní přenos je udržován v datové struktuře PCB – Parallel Stream Transmission Control Block, přesnou definici uvádí sekce 3.1 na str. 31. Vysvětlení významu znázorněných stavů přináší následující část.

2.5.1

Stavy paralelního spojení

CLOSED je iniciální a finální stav paralelního soketu. Z hlediska komunikačního protokolu jde o fiktivní stav (podobně jako v definici TCP [14]). LISTEN je stav vznikající při pasivním otevřením soketu. Řídící soket je též ve stavu LISTEN a čeká na příchozí spojení. Po jeho příchodu se vytvoří nový PCB a od PCB naslouchajícího paralelního soketu zdědí většinu vlastností. Pomocí spojeného řídícího soketu je protistraně zaslána zpráva HELLO a nový PCB přechází do stavu HELLO WAIT.


25

CONNECTING – vzniká aktivním otevřením paralelního soketu, s přechodem do tohoto stavu se iniciuje navazování řídícího spojení s protistranou. Po navázání je zaslána zpráva HELLO a PCB přechází do stavu HELLO WAIT. HELLO WAIT je stav, v němž se čeká na přijetí zprávy HELLO od protistrany. Po přijetí HELLO je určen počet spojení pro dílčí přenosy dle vztahu (2.1) a je vybrán ovladač paralelního spojení. Poté obě strany vyhradí potřebný počet adres koncových bodů9 a oznámí je protistraně pomocí zprávy STREAM ANNOUNCE. S odesláním této zprávy paralelní soket přechází do stavu STREAM ANNOUNCE WAIT. STREAM ANNOUNCE WAIT – soket čeká na zprávu STREAM ANNOUNCE, viz též sekce 2.4. Po úspěšném výpočtu párování soketů se přechází do stavu ESTABLISHING. ESTABLISHING – v této fázi se navazují spojení mezi sokety dílčích přenosů. Navazující strana se připojuje na adresy oznámené naslouchající stranou zprávou STREAM ANNOUNCE; naslouchající strana dovolí spojení pouze z adres, které byly oznámeny ve zprávě STREAM ANNOUNCE její protistrany. S navázáním posledního dílčího spojení paralelní soket přechází do stavu ESTABLISHED. ESTABLISHED je stav, v němž je paralelní soket většinu času své existence. Paralelní soket tuto fázi opouští buď na žádost protistrany a po jejím potvrzení přechází do SHUTDOWN RECEIVED, nebo na žádost uživatele, kdy po zaslání zprávy SHUTDOWN protistraně přechází do SHUTDOWN SENT. V obou případech stanice zahájí vyprazdňování zbylých dat v bufferech. Zpracování těchto dat určuje ovladač paralelního přenosu. SHUTDOWN SENT je stav, kdy finalizace paralelního spojení byla zahájena uživatelem, ale ještě nebyla potvrzena protistranou, a přenos dat nebyl ukončen. SHUTDOWN RECEIVED je stav, kdy finalizace paralelního spojení byla oznámena protistranou, ale ne uživatelem, a přenos dat nebyl ukončen. SHUTDOWN APPROVED je stav, kdy finalizace paralelního spojení byla oznámena uživatelem i protistranou, nicméně přenos dat nebyl zcela ukončen. SHUTDOWN WAIT je stav, kdy se s uvolněním prostředků paralelního přenosu čeká pouze na oznámení od uživatele. SHUTDOWN ACK WAIT je stav, kdy se s uvolněním prostředků paralelního přenosu čeká pouze na oznámení od protistrany. 9

Tedy dvojic IP adresa, port.


26

Poznámka 2.2 Tzv. half open spojení, známá z TCP, nejsou v současné verzi návrhu zahrnuta. Nicméně bude-li tato funkcionalita v budoucnosti potřebná, změny si vyžádají jen malé úpravy. Lepší pohled na časovou souvztažnost událostí vývoje paralelního soketu přináší obrázky 2.3 a 2.4. Zprávy protokolu psock jsou na obrázcích zobrazeny tlustou čarou, významné pakety protokolu TCP jsou značeny tence. Zprávy protokolu psock se předávají spolehlivým kanálem (proto nejsou vyznačena potvrzení protokolu nižší vrstvy). V obrázku 2.3 stojí za zmínku určení počtu dílčích přenosů ze zpráv HELLO(nrcmd , nmax ) dle vztahu (2.1). K obrázku 2.4 poznamenejme, že přesný průběh ukončování spojení závisí na vzájemném pořadí následujících tří událostí: ukončení spojení na požadavek uživatele, ukončení na požadavek protistrany a dokončení komunikace na dílčích přenosech – to ostatně plyne z diagramu na obr. 2.2. Obrázek zachycuje jednu z možností (datové pakety dílčích přenosů jsou pro přehlednost vynechány).


27

CONNECTING

LISTEN

passive open active open / connect control stream

control stream connected

CLOSED

/ send hello

HELLO_WAIT accept on control stream

/ duplicate pcb, send hello

recv hello / send stream announce

STREAM_ANNOUNCE_WAIT

recv stream announce

ESTABLISHING

establishment of a pstream

establishment of the last pstream

recv shutdown / send ack

ESTABLISHED

shutdown / send shutdown

recv shutdown ack

SHUTDOWN_SENT

recv shutdown / (ptransfer driver specific) flush_end

SHUTDOWN_RECEIVED

shutdown

flush_end

SHUTDOWN_WAIT

SHUTDOWN_APPROVED

flush_end

recv shutdown ack

shutdown

SHUTDOWN_ACK_WAIT

recv shutdown / (ptransfer driver specific) CLOSED

Obrázek 2.2: Přechodový diagram paralelního soketu (zjednodušeno)


28

CLOSED Control stream − SYN

LISTEN

Control stream − SYN+ACK

CONNECTING

Control stream − ACK HELLO(2,4)

HELLO(3,5)

HELLO WAIT

HELLO WAIT STREAM ANNOUNCE STREAM ANNOUNCE

STREAM ANNOUNCE WAIT

STREAM ANNOUNCE WAIT pstream 1 − SYN

pstream 2 − SYN

pstream 3 − SYN

ESTABLISHING

pstream 1 − SYN+ACK


pstream 1 − ACK


ESTABLISHING

pstream 2 − ACK

pstream 3 − ACK

ESTABLISHED ESTABLISHED

Obrázek 2.3: Navazování paralelního spojení


29

ESTABLISHED Shutdown by user

ESTABLISHED

Flushing pstream 3

Flushing pstream 2

Flushing pstream 1

SHUTDOWN APPROVED

pstream 2 − FIN

pstream 3 − FIN

SHUTDOWN RECIEVED

Flushing pstream 3

pstream 1 − FIN

Flushing pstream 2

SHUTDOWN REPLY

Flushing pstream 1

SHUTDOWN SEND

SHUTDOWN REQUEST

pstream 1 − FIN

pstream 2 − FIN

pstream 3 − FIN

Control stream − FIN

CLOSED

SHUTDOWN WAIT Shutdown by user

CLOSED

Obrázek 2.4: Ukončování paralelního spojení

Kapitola 3 Implementace Paralelizační systém je implementován v uživatelském prostoru jako sdílená knihovna, která si pro svoji činnost vytváří pomocná výpočetní vlákna. Programátorské rozhraní (viz příloha B.1) se velmi podobá standardním voláním specifikací BSD a POSIX, aby bylo možné snadno zavést možnost používání paralelních přenosů do existujících aplikací.

3.1

Pojmy a struktury

Tato sekce popisuje klíčové pojmy, vztahy a datové struktury použité v implementaci psock a jejím dále uvedeném popisu. Výčty uvádí jen nejdůležitější položky, podrobnější informace lze dohledat ve vygenerované dokumentaci zdrojových kódů. Protocol Space, Library Space – viz sekce 2.3. pstream je dílčí přenos představovaný TCP spojením. Řídící přenos je TCP spojení určené k přenosu řídících zpráv pro paralelní přenos. Instance protokolu je představována běžícím stavovým automatem; odpovídá jí běžící vlákno protokolu. Zatímco u síťových technologií implementovaných v jádru monolitických operačních systémů je obvyklá jedna instance protokolu v rámci stanice, v současné implementaci v uživatelském prostoru připadá jedna instance protokolu na jeden paralelní přenos. Důvodem je zejména lepší spravovatelnost. Ovladač paralelního přenosu – ptransfer driver je sada metod realizujících konkrétní algoritmus rozdělování dat do dílčích přenosů a jejich zpětné rekonstrukce (dispatching). Ovladač má dvě komplementární části: Ovladač paralelního přenosu ve vlákně protokolu – ptransfer pdrv je na obrázku 2.1 reprezentován komponentou „Dispatching Schedulingÿ. Jeho vstupem jsou zejména zprávy s výsledky provedení instrukcí z Library Space (5) a události na dílčích přenosech (2). 30

3.1 Pojmy a struktury

31

Ovladač paralelního přenosu v Library Space – ptransfer cdrv se používá při obsluze uživatelských požadavků. Provádí přenosové instrukce (viz část 2.3.3) a reaguje na výsledek jejich provedení. PCB (Parallel Stream Transmission Control Block) je datová struktura v Protocol Space sdružující informace o paralelním přenosu. Nese s sebou zejména tyto informace: • referenci na instanci protokolu, do níž PCB patří, • komunikační rozhraní PSCIF, umožňující obousměrnou komunikaci s Library Space, • souborový deskriptor řídícího přenosu, • datové struktury pro zpracování zpráv na řídícím přenosu, • stav paralelního přenosu, • hodnoty soketových nastavení (přístupné voláním setpsockopt() v úrovni SOL PSOCK), • hodnoty platné jen pro PCB ve stavu LISTEN: – backlog – maximální počet příchozích spojení čekajících na převzetí uživatelem, – seznam čekajících spojení, • hodnoty platné pro PCB ve stavu CONNECTING a pozdějších: – datové struktury odpovídající jednotlivým dílčím přenosům. Obsahují vždy deskriptor příslušného soketu, zbytek definuje použitý ovladač paralelního přenosu, – vlastní ovladač paralelního přenosu, – data algoritmu paralelního přenosu (význam dán použitým ovladačem paralelního přenosu), – řadu dalších pomocných atributů. struct psock je datová struktura v Library Space obsahující informace, jež je potřeba uchovávat mezi jednotlivými uživatelskými voláními knihovny. Obsahuje zejména tato data: • komunikační rozhraní PSCIF umožňující obousměrnou komunikaci s vláknem protokolu, • odkaz na ovladač paralelního přenosu v Library Space, • hodnoty platné jen pro stav LISTEN: – seznam struktur psock odpovídajících příchozím spojením; při volání funkce paccept() je vytvořen deskriptor příchozího spojení a je předán uživateli,

3.2 Vlákno protokolu

32

• struktury platné pro spojený paralelní soket: – rozvrh instrukcí pro odesílání dat, – rozvrh instrukcí pro příjem dat.

3.2

Vlákno protokolu

Vztahy objektů v Protocol Space jsou znázorněny na obr. 3.1. Library Space (cut)

Protocol Thread(s) PSCIF communication driver 2 PSCIF communication driver 1

psock’s PSCIF interface

ptransfer driver B (Protocol space part)

Protocol instance, running state machine PCB’s PSCIF interface

Control stream and control block pstream 1

PCB

pstream 2 pstream n

Protocol instance, running state machine


PCB’s PSCIF interface

Control stream and control block pstream 1

PCB

pstream 2 pstream n

ptransfer driver A (Protocol space part)

Obrázek 3.1: Vztahy struktur v Protocol Space V hlavní smyčce vlákna protokolu se sledují obsluhované souborové deskriptory a časové události pomocí volání poll(). Obsluhovanými sokety jsou: řídící přenos, dílčí datové přenosy a rozhraní PSCIF pro komunikaci s Library Space, které je v současné verzi implementováno jako unixový soket. Po návratu z volání poll() jsou na základě jeho výsledků generovány příslušné události; ty jsou pak předány ke zpracování stavovému automatu.

3.2.1

Události

Událost je identifikována dvěma čísly – typem a podtypem. Události s sebou mohou nést datový argument.


33

Typy a podtypy událostí jsou: PSKEV T STREAM – událost týkající se přenosů, patří sem: PSKEV DATA STREAMS POLL – výskyt události na datových přenosech. Ve stavu ESTABLISHED a při zavírání spojení předáváno ke zpracování ovladači ptransfer pdrv. PSKEV CTL STREAM POLL – vyskytla se událost na řídícím spojení. Využívá se při navazování spojení a pro obsluhu řídících zpráv. PSKEV DATA STREAMS ESTABLISHMENT – událost generovaná ve stavu ESTABLISHING při spojení všech dílčích přenosů. PSKEV DATA STREAM HANGUP – generováno při chybě na datovém přenosu. PSKEV CTL STREAM HANGUP – generováno při chybě na řídícím přenosu. PSKEV DATA STREAMS FLUSH END – generováno v závěrečné fázi života paralelního soketu při dokončení přenosu zbývajících dat. PSKEV T LIB2PROTO – zprávy posílané vláknu protokolu z Library Space. Číslo (kód) zprávy se používá přímo jako podtyp události. Argumentem události je reference na přijatou zprávu. Definovány jsou tyto zprávy: PSKEV LIB2PROTO RECV INSTR RES – oznámení výsledku provedení instrukce příjmu z pstreamu, PSKEV LIB2PROTO SEND INSTR RES – oznámení výsledku provedení instrukce odeslání na pstream, PSKEV LIB2PROTO TRANSFER – požadavek na datový přenos mezi knihovnou a protokolem, využívá se zřídka,1 PSKEV LIB2PROTO PSOCKCTL zahrnuje různé požadavky na vlákno protokolu, mezi tyto požadavky patří mj. nastavení a dotazy na vlastnosti soketu nebo protokolu v rámci volání setpsockopt() a getpsockopt(), PSKEV LIB2PROTO BIND – pojmenování soketu, aplikuje se na řídící stream, PSKEV LIB2PROTO PASSIVE OPEN – příkaz k přechodu PCB do režimu LISTEN, PSKEV LIB2PROTO ACTIVE OPEN – příkaz ke spojení se vzdáleným systémem, 1

V současné verzi se tyto přenosy nepoužívají. Význam budou mít zejména při rekonfiguraci dílčích přenosů.


34

PSKEV LIB2PROTO SHUTDOWN – příkaz ke korektnímu ukončení protokolu, PSKEV LIB2PROTO ABORT – násilné zrušení paralelního soketu. PSKEV T CTLMSG – řídící zprávy od vzdáleného systému. Podtyp události je odvozen z kódu zprávy jako 2(msg code − 1) + (is reply ? 1 : 0). Argumentem události je reference na přijatou zprávu.

3.2.2

Reakce na událost

Na základě stavu PCB, typu a podtypu události se určí obslužná funkce.2 Popis činnosti obslužných funkcí přesahuje rámec tohoto dokumentu; v případě zájmu lze informace dohledat ve zdrojových kódech, startovním místem je soubor src/net/psock/ sm funcs.inc.h. Po provedení obslužné funkce a případném obsloužení výjimečných stavů se pokračuje další iterací hlavní smyčky. Zprávy zasílané do Library Space Zprávy zasílané vláknem protokolu do Library Space představují buď reakce na přímý požadavek Library Space, nebo asynchronní oznámení, která jsou generována na základě jiných událostí. Počítá se s tím, že Library Space asynchronní zprávy zpracuje až v momentě uživatelského volání knihovny – neočekává se okamžité zpracování a počet asynchronních zpráv je omezený. Asynchronních zpráv je jen několik druhů, přičemž většina je tvořena instrukcemi pro rozvrh paralelního přenosu. Jelikož rozvrh má danou velikost, je právě ta omezením počtu asynchronně zaslaných instrukcí. Předávání instrukcí pro paralelní rozvrh probíhá následujícím způsobem: jakmile vlákno protokolu zjistí, že je možné naplánovat příjem, resp. vyslání nějakého bloku z/do některého dílčího přenosu, odešle do Library Space instrukci PSKEV PROTO2LIB RECV INSTR, resp. PSKEV PROTO2LIB SEND INSTR a přestane se zajímat o připravenost daného dílčího přenosu pro čtení, resp. zápis. Až Library Space instrukci vyzvedne, zařadí ji na příslušné místo svého rozvrhu. Teprve po jejím provedení zasílá zprávu PSKEV LIB2PROTO RECV INSTR RES, resp. PSKEV LIB2PROTO SEND INSTR RES spolu s výsledkem. Poté může vlákno protokolu obnovit sledování připravenosti daného dílčího přenosu pro čtení, resp. zápis. Poznamenejme, že plánování rozvrhu paralelního přenosu nemusí nutně probíhat uvedeným způsobem. V případě jednoduchého algoritmu přenosu, jako je round-robin, by byl výše uvedený postup zbytečně těžkopádný. Proto instrukce mohou být generovány 2

Kompletní tabulka přechodů je v souborech doc/statetable.* ve stromu projektu. Optimalizovaná tabulka obslužných funkcí v jazyce C je generována programem scripts/gen state table.


35

přímo ovladačem v Library Space. Ostatně toto je také jeden z důvodů, proč byla zavedena i Library Space část ovladače paralelního přenosu.

3.2.3

Ovladač paralelního přenosu

Příslušným metodám ovladače paralelního přenosu jsou ve stavech ESTABLISHED a následných předávány události DATA STREAMS POLL, PSKEV LIB2PROTO RECV INSTR RES a PSKEV LIB2PROTO SEND INSTR RES. Ovladač také obsahuje několik dalších metod, které ovšem nejsou pro popis koncepce tak podstatné. Plnou specifikaci lze nalézt v dokumentaci zdrojových kódů – struct ptransfer pdrv a struct ptransfer cdrv. Algoritmus round-robin Dílčí přenosy jsou využívány pro odesílání bloků cyklicky v pevném pořadí. Požádá-li aplikace o odeslání určitého množství dat, jsou tato rozdělena na bloky dané délky, které jsou po řadě odesílány jednotlivými dílčími přenosy. Příjem dat z jednotlivých dílčích přenosů se provádí opět cyklicky ve stejném pořadí, v jakém byly odeslány protější stanicí. Nevýhoda tohoto algoritmu spočívá ve faktu, že zablokování libovolného dílčího přenosu zablokuje celý přenos paralelní. Maximální dosažitelná rychlost je c = n min ci ,

(3.1)

i

kde ci je propustnost i-tého dílčího přenosu a n počet dílčích přenosů. Podmínkou dosažení této rychlosti je dostatečná velikost soketového bufferu, aby okénka pokryla kapacitu trasy – viz kapitola 4. Algoritmus pollall Algoritmus je pojmenován podle způsobu jeho implementace, v níž je systémové volání poll() prováděno nad všemi dílčími přenosy. Základní myšlenku tohoto algoritmu zachycuje obrázek 3.2.

Input flow

pstream 1

pstream 1

pstream 2

pstream 2

Internet pstream n

Output flow

pstream n

Obrázek 3.2: Princip algoritmu pollall Data jsou do dílčích přenosů distribuována podle jejich připravenosti pro zápis. Pokud aplikace generuje data rychleji, než je propustnost tras, začnou se odchozí soketové


36

buffery plnit. Je-li některá trasa méně propustná, příslušný odchozí soketový buffer bude dříve zaplněn a soket následně přestane hlásit připravenost pro zápis. Zátěž se tak rozkládá větší měrou mezi ostatní sokety a dochází tak k využití přenosové kapacity i v případě jejího nerovnoměrného rozdělení. Jelikož relativní pořadí bloků rozeslaných na různé dílčí přenosy nezůstává zachováno, je na začátek každého bloku přidána hlavička s číslem bloku. Je-li na datovém soketu zjištěna příchozí událost, přijme se hlavička bloku a je z ní určeno pořadí bloku v rozvrhu pro příjem. Bohužel toto pořadí může předbíhat aktuální pozici v rozvrhu o více, než jaká je jeho velikost (počet dílčích přenosů). Plyne to z následující úvahy: Předpokládejme, že počet dílčích přenosů je n a následující blok k předání aplikaci na přijímající straně má číslo k. Dále předpokládejme, že vysílači se podaří na nějakou podmnožinu přenosů A ⊂ S odeslat m ≥ n bloků, mezi nimi i blok číslo k, a poté odešle blok k + m po přenosu z množiny S \ A. Za takové situace může přijímač přijmout právě blok k + m jako první, a jelikož m ≥ n, je blok mimo rozsah příjmového rozvrhu. Naštěstí takto předběhlých bloků může být maximálně n − 1. Instrukce odpovídající předběhlým blokům ovladač uchovává v seznamových položkách farsched list a ke každé položce rozvrhu v Library Space existuje ve vlákně protokolu seznam předběhlých instrukcí. V podstatě se tedy jedná o hashovací tabulku o n položkách, v níž je indexem číslo bloku modulo počet dílčích přenosů (pozice v rozvrhu). Amortizovaná složitost všech operací je konstantní. Podmínka plného využití sumární kapacity tras. Klíčovou komponentu, nad kterou probíhá rozkládání a paralelizace datového přenosu, tvoří soketové buffery. Nutnou podmínkou využití plné kapacity tras je, aby velikosti soketových bufferů vysílače i přijímače pokrývaly kapacitu příslušné trasy (kap. 4). Avšak aby zátěž mohla být rozložena do tras s různými vlastnostmi, musíme splnit další požadavky na velikost soketových bufferů – v opačném případě začne docházet k synchronizaci „přes příjemceÿ (podobně jako v příkladu A.1) a rychlost propustnějších tras se bude přizpůsobovat méně propustným trasám. Předpokládejme dva dílčí přenosy a, b. Označme wa , wb kapacity soketových bufferů pro odchozí data (na obr. 3.2 vlevo), ra , rb kapacity soketových bufferů pro příchozí data (na obr. 3.2 vpravo), ca , cb rychlosti přenosových tras a td,a , td,b dopravní zpoždění tras. Dále předpokládejme, že v určitém okamžiku se uvolní místo v odchozích bufferech přenosu a i b a vysílač do nich umístí dva po sobě jdoucí bloky A, B (první do a, druhý do b). Doba, za kterou bloky dorazí k přijímači, je ta =

wa + td,a ca

tb =

wb + td,b cb

(3.2)

Bez újmy na obecnosti připusťme, že ta > tb , tzn. že blok vyslaný dílčím přenosem b dorazí dříve než sousední blok vyslaný dílčím přenosem a. Aby bylo zachováno pořadí bloků, přijímač musí před předáním bloku B aplikaci počkat i na blok A. Mezitím se

3.3 Library Space

37

však příchozí buffer přenosu b dále plní příchozími daty. Chceme-li se vyhnout omezení rychlosti dílčího přenosu b, musí buffer tato data pojmout. K tomu je potřeba dodatečná kapacita wa wb + td,a − + td,b . (3.3) ∆rb = cb ∆t = cb ca cb Po úpravě dostáváme wa + td,a − td,b − wb . (3.4) ∆rb = cb ca Jelikož velikost rb musí navíc pokrývat velikost okénka oznamovanou vysílači, jeho velikost za předpokladu optimální volby odchozího soketového bufferu (4.2) bude

rb = c b

wa + td,a − td,b . ca

(3.5)

Tento závěr lze zobecnit na libovolný počet dílčích přenosů; pro velikost příjmového soketového bufferu i-tého přenosu dostáváme !

ri = ci max

j∈h1,ni

3.3

wj + tj − ti . cj

(3.6)

Library Space

Vztahy objektů v Library Space jsou znázorněny na obr. 3.3 (jde o komplement obrázku 3.1). Aplikace referencuje paralelní sokety a ostatní I/O prostředky spravované knihovnou pomocí celočíselných nezáporných deskriptorů – analogicky jako při volání OS. Každý existující deskriptor odkazuje na nějakou instanci struct psock file3 . Ta udržuje referenci na I/O prostředek a sadu metod pro práci s ním. Tento přístup umožňuje použít systém v transparentním režimu, kdy po nahrazení standardních volání voláními psock je přístup ke všem prostředkům unifikovaný. Při vstupu z aplikace do kódu knihovny se obslouží zprávy na rozhraní PSCIF.4 Poté následuje vykonání činnosti vyžádané uživatelem – např. příjem dat z dílčích přenosů do předaného bufferu. Řešení implementace jednotlivých operací lze nalézt v src/net/psock/ psock.c.

3

Analogie struct file v jádru unixových systémů. Jedná se většinou instrukce pro paralelní přenos – jiné asynchronní zprávy zasílá Protocol Space jen zřídka. 4

3.3 Library Space

38

Library Space psock file and socket descriptors

struct psock_file

Standard file and socket operations

ptransfer driver B (Library space part)

psock operations

ptransfer driver A (Library space part)

psock object

psock’s

0 1 2 3 4

psock object

. . .

Protocol Thread(s) (cut) PSCIF communication driver 2 PSCIF communication driver 1


PSCIF interface


System file and socket references (via fd)

Obrázek 3.3: Vztahy struktur v Library Space


Kapitola 4 Vlastnosti paralelních přenosů 4.1

Paralelní přenosy po jedné fyzické trase

Rozlehlé vysokorychlostní sítě se vyznačují jednak velkou šířkou pásma, jednak velkým transportním zpožděním. S touto kombinací ale původní návrh přenosového protokolu TCP nepočítá, proto bylo navrženy různé změny a techniky, které výkonnost přenosového protokolu zlepšují. Patří mezi ně selektivní potvrzení, časová razítka, úpravy parametrů AIMD nebo právě paralelní přenosy.

4.1.1

Přenos beze ztrát

Maximální dosažitelná propustnost je kromě propustnosti vlastního přenosového kanálu (BW ) dána maximální velikostí okénka – congestion window Wmax a hodnotou Round Time Trip (RT T ): Wmax T CPBW = min BW, (4.1) RT T Wmax představuje maximální množství nepotvrzených dat odeslaných vysílačem. Vztah (4.1) plyne z faktu, že potvrzení libovolného odeslaného segmentu se k vysílači dostane za dobu RT T . Z (4.1) lze snadno určit optimální velikost okénka Wopt : Wopt = BW.RT T.

(4.2)

Pravá strana (4.2) se nazývá kapacita trasy nebo též bandwidth × delay product. Poměr W velikosti okénka a kapacity trasy BW.RT udává využití šířky pásma. T Ačkoliv paralelní přenosy po jedné bezeztrátové fyzické trase nepřináší z teoretického hlediska zlepšení propustnosti, mohou v praxi pomoci překonat problém, kdy není možné měnit nastavení soketových bufferů koncových stanic.

39

4.1 Paralelní přenosy po jedné fyzické trase

40

Měření Poznámka 4.1 Toto i dále uvedená měření byla provedena za pomoci testovacího nástroje psock-testperf – viz sekce B.2. K emulaci síťových parametrů byl využit emulátor NISTNet [21]. Konfiguraci měření zachycuje tabulka 4.1. Hodnota wmem je velikost soketového bufferu pro odchozí data, která určuje maximální velikost okénka. Hodnota rmem je velikost soketového bufferu pro příchozí data, oproti wmem je o 13 naddimenzovaná (nutné z důvodu vnitřní aritmetiky při používání bufferu pro okénko v OS Linux). Buffery byly nastaveny pomocí implicitní (default) hodnoty pro koncovou stanici1 : # sysctl -w net.ipv4.tcp_rmem=’min default max’ # sysctl -w net.ipv4.tcp_wmem=’min default max’ Šířka pásma RT T [ms] Kapacita trasy [B] Testovací data [B] W BW.RT T

0,2 0,8 1,0 1,5

[–]

100 Mb/s = 12,5 MB/s 40 500 000 100 M

wmem/soket [B] 100 400 500 750

000 000 000 000

rmem/soket [B] 133 333 533 333 666 667 1 000 000

Tabulka 4.1: Konfigurace měření paralelních přenosů po jedné fyzické trase Obrázek 4.1 ukazuje, jak roste propustnost s počtem dílčích přenosů při různých velikostech okénka. Jelikož je maximální velikost okénka dána velikostí soketového bufferu, roste sumární okénko s počtem použitých soketů. Je celkem zřejmé, že propustnost přenosu se odvíjí zejména od sumární velikosti okénka. Tento fakt dokládá graf na obrázku 4.2. V grafu na obr. 4.1 je patrný mírný nárůst propustnosti s počtem dílčích přenosů i při velikostech okének, které pokrývají kapacitu trasy už pro jeden dílčí přenos. Tento jev je způsoben větší rychlostí otevírání spojení (slow start), kdy při použití více dílčích přenosů roste strmost nárůstu velikosti sumárního okénka. Tento fakt dokládá graf na obr. 4.3. 1

Názvy sysctl proměnných platí pro OS Linux.


41

100 90

Throughput [Mb/s]

80 70 60 50 40 30 20 CWND=0.2 CWND=0.8 CWND=1.0 CWND=1.5

10 0

1

2

3

4

5 6 Flows [-]

7

BW.RTT BW.RTT BW.RTT BW.RTT 8

9

10

Obrázek 4.1: Propustnost v závislosti na počtu dílčích přenosů při různých hodnotách okénka

4.1.2

Přenos se ztrátami

Existuje několik studií, které odvozují teoretické výrazy pro propustnost TCP toku jako funkci ztrátovosti paketů, RT T , maximální velikosti segmentu (M SS) a různých dalších parametrů. Model považovaný za nejpřesnější je popsán v [17]. Propustnost lze aproximovat rovnicí2 :  

T CPBW (p) = min  BW,

  1 Wmax  M SS, , q q RT T RT T 2bp + T min 1, 3 3bp p (1 + 32p2 )  0 3 8

(4.3) kde T CPBW (p) reprezentuje počet bytů přenesených za sekundu, M SS je maximální velikost segmentu, Wmax je maximální velikost okénka, b je počet odeslaných paketů potvrzovaných jedním potvrzením (ACK), T0 je hodnota časového limitu a p je ztrátovost paketů – poměr retransmisí a celkového počtu přenesených paketů. Pro ztrátovosti menší než Mathisovu rovnici [18]:

1 100

lze bez újmy na přesnosti použít podstatně jednodušší

T CPBW (p) ≤

M SS C √ , RT T p

(4.4)

kde C je konstanta. Předpokládejme, že parametry M SS, RT T a p nejsou závislé na zatížení sítě. Pak 2

Měřítko původní rovnice změněno, aby odpovídala vztahu (4.4).


42

100

Throughput [Mb/s]

80

60

40

20

0

CWND=0.2 CWND=0.8 CWND=1.0 CWND=1.5 0

2

4

6 8 10 CWND sum / BW.RTT [-]

12

BW.RTT BW.RTT BW.RTT BW.RTT 14

16

Obrázek 4.2: Propustnost v závislosti na sumárním okénku můžeme pro propustnost n přenosů psát #

"

T CPagg BW

M SS2 M SSn M SS1 . ≤C √ + √ + ... + √ RT T1 p1 RT T2 p2 RT Tn pn

(4.5)

Předpoklad nezávislosti parametrů je ale potřeba důkladněji prověřit. Parametr M SS je nejméně proměnný, obvykle je dán maximální velikostí rámce fyzické vrstvy. Hodnota parametru RT T je více dynamická. Její spodní mez je dána zpožděním šíření signálu v médiích; s rostoucím počtem hopů přibývá zpoždění dané průchodem směrovači a linkovými protokoly, nicméně toto přidané zpoždění lze považovat za konstantní. Teprve při vysokém relativním vytížení tras narůstá RT T vlivem zpoždění v plnících se frontách síťových uzlů. Při použití více paralelních přenosů můžeme předpokládat stejnou hodnotu M SS a RT T u každého přenosu a dostáváme "

T CPagg BW

#

M SS 1 1 1 ≤C . √ + √ + ... + √ RT T p1 p2 pn

(4.6)

Nejdynamičtějším parametrem z trojice M SS, RT T a p je právě ztrátovost paketů. Algoritmus zamezení zahlcení (congestion avoidance) interpretuje ztrátu paketu jako indikaci, že síť je zahlcena a vysílač by měl snížit rychlost přenosu. Nicméně zdroje ztrátovosti paketů v internetu lze rozdělit do dvou kategorií – jednak ztráty způsobené zahlcením, jednak ztráty nezávislé na intenzitě provozu. Právě pro druhou skupinu lze předpokládat, že ztrátovost paketů jednoho přenosu nebude ovlivněna ostatními přenosy. Jsou-li navíc


43

700

Outstanding data [KiB]

600

500

400

300

200

100

0

1 flow 10 flows 0

100

200

300 400 Time [ms]

500

600

700

Obrázek 4.3: Nárůst okénka ztráty rovnoměrně distribuovány mezi jednotlivé přenosy3 , lze vztah (4.6) vyjádřit jako T CPagg BW ≤ C

nM SS √ . RT T p

(4.7)

Odtud plyne zajímavý závěr – agregátní přenos n paralelními TCP spojeními je dle použitého modelu ekvivalentní jednomu přenosu s n-násobným M SS. Další závěr z uvedeného teoretického rozboru se týká spravedlnosti rozdělení šířky pásma mezi datové toky. Obecně platí, že algoritmus zamezení zahlcení konverguje k ustálenému stavu, kdy soupeřící TCP přenosy dostanou ekvivalentní šířku pásma. Je tedy zřejmé, že datové toky přenášené paralelními přenosy si za stejných podmínek „ukrajujíÿ větší část přenosové kapacity než toky přenášené jedním spojením. Má-li ale soupeřit přenos přes rozlehlou síť s přenosem na kratší vzdálenost, dostává se do nevýhody díky mnohem pomalejšímu nárůstu okénka po ztrátě paketu. Rychlost tohoto nárůstu lze zvýšit zvětšením (virtuální) M SS, čehož lze dle předchozího závěru dosáhnout právě pomocí paralelních přenosů. Paradoxně tak paralelní přenosy mohou sloužit k dosažení spravedlivého rozdělení kapacity páteřních tras.

Měření Graf na obrázku 4.4 ukazuje závislost propustnosti paralelního přenosu na počtu dílčích přenosů. Levá část grafu ukazuje lineární nárůst v souladu se vztahem (4.7). Dále je patrné 3

Existuje několik výjimek, kdy ztrátovost není spravedlivě rozkládána, např. při vzniku fázového efektu [19]. Dosáhnout lepšího chování je možné při použití vhodných plánovacích strategií, např. Random Early Detection (RED).

4.2 Paralelní přenosy po více fyzických trasách

44

„kolenoÿ, v němž se začíná projevovat zahlcení sítě a (4.7) přestává platit. Šířka pásma RT T [ms] Ztrátovost [–] Kapacita trasy [B] Testovací data [B]

100 Mb/s = 12,5 MB/s 40 1 10 000

500 000 200 M

Tabulka 4.2: Konfigurace měření paralelních přenosů po ztrátové trase

100

Throughput [Mb/s]

80

60

40

20

0

Throughput 1

2

3

4

5 6 Flows [-]

7

8

9

10

Obrázek 4.4: Propustnost v závislosti na počtu dílčích přenosů při ztrátovosti 0,01%

4.2

Paralelní přenosy po více fyzických trasách

Jak již bylo zmíněno v části 1.2.1, dělení přenosu mezi více fyzických tras na síťové vrstvě má nepříznivý vliv na efektivitu protokolu TCP, neboť ten počítá s FIFO chováním sítě, a proto jsou pro jednotlivé trasy používána samostatná TCP spojení. Chování paralelního přenosu pak značnou měrou závisí na způsobu, jakým se data dělí mezi dílčí přenosy.

Měření V provedených měřeních byly emulovány dvě oddělené přenosové trasy se sumární propustností 100 Mb/s. Cílem bylo zjistit vliv poměru rozdělení přenosové kapacity na celko-

4.2 Paralelní přenosy po více fyzických trasách

45

vou dosaženou propustnost jednoho logického přenosu. Testovány byly algoritmy roundrobin a rozdělování dat podle připravenosti soketů pro zápis (pollall ). Potvrdil se předpoklad, že propustnost při použití round-robin bude dvojnásobkem (pro n přenosů obecně n-násobkem) rychlosti nejpomalejšího dílčího přenosu. Algoritmus pollall dosáhl dle očekávání plného využití sumární přenosové kapacity. Výsledky ilustruje graf na obr. 4.5; pro srovnání je zachycena i propustnost při použití jednoho přenosu výhodnější trasou. 100 90

Throughput [Mb/s]

80 70 60 50 40 30 20 single stream round robin dispatching pollall dispatching

10 0

0

0.2 0.4 0.6 0.8 Bandwidth of the 1st path / bandwidth sum [-]

1

Obrázek 4.5: Propustnost dvou tras v závislosti na rozdělení kapacity

Kapitola 5 Závěr V práci byly analyzovány možnosti, jak realizovat paralelní přenosy a jak je aplikovat pro efektivnější využití datových sítí. Důraz byl kladen na uplatnění existujících hardwarových i softwarových prostředků. Byl navržen paralelizační systém vhodný ke zkoumání paralelních přenosů a zlepšování jejich vlastností. Programátorské rozhraní systému používá obdobu klasických síťových volání dle specifikací BSD a POSIX; z tohoto důvodu modifikace existujících síťových aplikací pro paralelní přenos nevyžaduje příliš mnoho úsilí. V případě, že síťová aplikace využívá přímo POSIX a BSD volání, je možné i transparentní použití na úrovni zdrojových kódů. Do budoucna je též plánováno vytvoření transparentní verze pro dynamicky sestavované aplikace. Klíčové vlastnosti paralelních přenosů byly teoreticky zdůvodněny a ověřeny laboratorními měřeními. Hlavních cílů práce, tedy zlepšení charakteristik TCP přenosů a využití sumární kapacity více tras pro logický přenos, byly dosaženy.

5.1

Další výzkum

Pokračování práce je plánováno v rámci výzkumného záměru „End-to-end performanceÿ [4] sdružení Cesnet, z.s.p.o.

Knihovna a framework psock S využitím vytvořené paralelizační platformy budou zkoumány další možnosti zvýšení aktivního uplatnění paralelních přenosů. Plánována je implementace schopnosti automatické volby přenosových tras a testování modifikací algoritmů paralelního přenosu. Dále bude zváženo rozšíření psock na paralelní systémy (clustery) s cílem poskytnout podporu paralelního přenosu tam, kde jsou data generována, resp. zpracovávána více výpočetními uzly. Toto navazuje na poslední bod požadavků ze sekce 1.3.1.

46

5.1 Další výzkum

47

Jiné možnosti paralelizace Studovány budou i možnosti paralelizace pomocí jiných přenosových protokolů, zejména SCTP (RFC 2960), které podporuje multihoming, ale využívá jej jen pro účely redundance (zvýšení spolehlivosti). Testována budou též již navržená řešení jako pTCP [20]. Uvedené aktivity lze shrnout do následujícíh rámcových témat dalšího výzkumu: • zlepšování charakteristik rozlehlých vysokorychlostních sítí pomocí paralelních přenosů, • využití efektů paralelních přenosů pro modifikace transportních protokolů, • uplatnění redundance přenosových tras v transportních protokolech, • aplikačně transparentní podpora paralelních přenosů, • paralelizace datových přenosů mezi distribuovanými výpočetními uzly.

Příloha A Příklady A.1

Příklad aplikačního paralelizmu

Příklad A.1 (Aplikace se dvěma souběžnými přenosy a závislostí dat) Zkusme navrhnout program netpaste – síťovou variaci unixového paste (man paste) – s následující funkcí. Na stanici S spustíme netpaste (bez parametrů – jako server). Na stanici C pak zadáme netpaste SERVER-ADDRESS FILE1 FILE2. Úkolem serveru bude vypsat na standardní výstup po řádcích spojené soubory FILE1 a FILE2 ze stanice C. Řešení: Klient umí číst a následně odesílat každý soubor nezávisle. Server může přijímat data prvního souboru pomocí jednoho přenosu a data druhého souboru pomocí přenosu druhého. Má tedy smysl využít dvě spojení. Tím jsme navrhli jsme aplikaci využívající paralelní spojení. Zamysleme se ale nad funkcí serveru. Nejprve čeká na data prvního přenosu, při jejich příjmu je vypisuje na výstup, dokud nenarazí na znak nového řádku. Poté provádí totéž s druhým přenosem. Následně vypíše znak nového řádku a celý postup se opakuje. Server tedy zpracovává data přenosů metodou round-robin, což po naplnění odchozích bufferů na straně klienta vede k tomu, že tento je metodou round-robin také odesílá. Takovou práci ale může bez problémů zastat paralelizace na transportní vrstvě. Příklad slouží jako ukázka, kdy i ručně vytvořené aplikační paralelní přenosy nepřináší výhodu proti paralelizačnímu systému na transportní vrstvě.

48

Příloha B Programátorské rozhraní B.1

Knihovna psock-mt

Následující výčet podává základní přehled funkcí poskytovaných uživateli knihovny psockmt. Většina představuje obálky standardních volání a používá se analogickým způsobem. Jak typy parametrů, tak návratové hodnoty a hodnoty errno jsou se standardními voláními kompatibilní a další informace lze hledat např. v druhé sekci unixových manuálových stránek.

int psocket(int domain, int type, int protocol); Obálkou volání socket(). Parametr domain specifikuje jmenný prostor, ve kterém se bude komunikace odehrávat, type určuje typ soketu a protocol stanoví, který konkrétní protokol bude použit. Je-li funkce volána s parametry PF INET, SOCK STREAM, IPPROTO PSOCK, vytvoří se paralelní soket; v ostatních případech je použito standardní volání socket(). IPPROTO PSOCK je konstanta určující číslo protokolu paralelních přenosů a je volena tak, aby nekolidovala s čísly existujících protokolů nad IP dle organizace IANA. V případě úspěchu volání vrací celočíselný deskriptor soketu1 .

int psclose(int s); Obálka volání close(), zavírá knihovní souborový deskriptor s.

int pbind(int s, struct sockaddr *addr, socklen t addrlen); Obálka volání bind(), pojmenuje soket s. U paralelních soketů se aplikuje na soket řídícího přenosu (ostatní přenosy se dají pojmenovat pomocí setpsockopt()). Paralelní 1

Deskriptory soketů používaných knihovnou ze zřejmých důvodů neodpovídají systémovým deskriptorům. Z tohoto důvodu u plně transparentní verze v uživatelském prostoru bude potřeba vytvořit obálky všech volání, které nějakým způsobem pracují se souborovými deskriptory.

49

B.1 Knihovna psock-mt

50

sokety v současné verzi podporují pouze jmenný prostor AF INET.

int plisten(int s, int backlog); Obálka volání listen(), uvede soket do naslouchajícího módu, kdy čeká na příchozí spojení. Požadavky na spojení lze poté vyzvednout funkcí paccept(). Parametr backlog určuje maximální počet nevyzvednutých příchozích spojení. Spojení nad tento limit jsou odmítána.

int paccept(int s, struct sockaddr *addr, socklen t *addrlen); Obálka volání accept(), přijme spojení na soketu s. Jsou-li parametry addr a addrlen nenulové, je na předané adresy zapsána adresa protistrany a její délka (v případě paralelních spojení je adresa reprezentována adresou řídícího spojení). Funkce vrací deskriptor přijatého spojení.

int pconnect(int s, struct sockaddr *addr, socklen t addrlen); Obálka volání connect(), inicializuje spojení soketu s protistranou. Jedná-li se o paralelní soket, je protistrana určena adresou řídícího přenosu.

ssize t psend(int s, const void *buf, size t len, int flags); Obálka volání send(), pošle do soketu zprávu na adrese buf o délce len. Pokud není vyžádán neblokující mód (příznak MSG DONTWAIT), je poslána vždy celá zpráva.

ssize t precv(int s, void *buf, size t len, int flags); Obálka volání send(), přijme ze soketu data o délce nejvýše len a zapíše je na adresu buf.

int getpsockopt(int s, int level, int optname, void *optval, socklen t *optlen); int setpsockopt(int s, int level, int optname, const void *optval, socklen t optlen); Obálky volání getsockopt() a setsockopt(), zjišťují a nastavují vlastnosti soketů. Parametr level specifikuje úroveň, na níž je se soketem manipulováno. Pro paralelní sokety je vyhrazena úroveň SOL PSOCK. Parametr optname určuje vlastnost soketu na dané úrovni, zbylé parametry slouží předání hodnoty vlastnosti. Vlastnosti definované v úrovni SOL PSOCK jsou uvedeny dále. Až na poslední tři jsou všechny předávány ukazatelem na typ int.

B.1 Knihovna psock-mt

51

PSOCK PSTREAM BLOCK SIZE – maximální velikost bloku posílaného jedním dílčím přenosem, PSOCK RCMD STREAM CNT – doporučený počet dílčích přenosů oznamovaný při spojování (musí být voláno nad nespojeným soketem), PSOCK MAX STREAM CNT – maximální počet dílčích přenosů oznamovaný při spojování (musí být voláno nad nespojeným soketem), PSOCK PTRANSFER DRV – požadovaný ovladač oznamovaný při spojování (musí být voláno nad nespojeným soketem), PSOCK PTRANSFER DRV PRIO – priorita požadovaného ovladače oznamovaná při spojování (musí být voláno nad nespojeným soketem), minimální hodnota je 0, maximální 255 PSOCK ADD LOCAL ADDR – přidá datovému soketu adresu, která bude použita pro dílčí přenosy při spojování paralelního soketu, musí být voláno nad nespojeným soketem, PSOCK SNDBUF – nastaví velikost odchozího soketového bufferu (SO SNDBUF) pro daný dílčí přenos, k nastavení se používá ukazatel na hodnotu typu struct pstream int (viz dále), PSOCK RCVBUF – nastaví velikost příjmového soketového bufferu (SO RCVBUF) pro daný dílčí přenos, k nastavení se používá ukazatel na hodnotu typu struct pstream int (viz dále). Pro předávání hodnot typu int konkrétním dílčím přenosům slouží datový typ struct pstream int: struct pstream_int { int index; int value; };

/* pstream index */ /* option value */

int psock getopt(int optname, void *optval, socklen t *optlen); int psock setopt(int optname, const void *optval, socklen t optlen); Tato volání nastavují implicitní hodnoty knihovny psock-mt v rámci aplikace. Jako hodnotu optname lze použít možnosti PSOCK PSTREAM BLOCK SIZE, PSOCK RCMD STREAM CNT, PSOCK MAX STREAM CNT, PSOCK PTRANSFER DRV a PSOCK PTRANSFER DRV PRIO. Význam těchto nastavení je stejný jako u funkcí getpsockopt() a setpsockopt().

B.2 Testovací nástroj psock-testperf

B.2

52

Testovací nástroj psock-testperf

Program je implementován nad knihovnou psock a zahrnut do projektu. Při spuštění s parametrem --help vypíše způsob použití. psock-testperf { --xmit | --recv } [ VOLBY ] \ { --connect host[:port] | --listen [host[:port]] } VOLBY jsou: --help vypíše způsob použití --rcmd N doporučený počet dílčích přenosů --max N maximální počet dílčích přenosů --pstream-bs N velikost bloku posílaného dílčím přenosem --drv ID ovladač paralelního přenosu --drv-prio N priorita ovladače paralelního přenosu --add-addr ADDR zavolá PSOCK_ADD_LOCAL_ADDR setpsockopt() --psock-sndbuf I,BUF nastaví odchozí soketový buffer I-tého dílčího přenosu na hodnotu BUF --len N maximální délka přijatých/odeslaných dat --bs N velikost bufferu pro volání psend()/precv() --in mem|file metoda generování datového vstupu při --xmit --out mem|file metoda zpracování dat při --recv --file FILE jméno souboru pro zdroj/cíl dat, ’-’ představuje standardní vstup/výstup (jen pro metody generování/zpracování ’file’) --wait počkej na potvrzení zahájení přenosu uživatelem Parametry pro spojení: --connect host[:port] připoj se na adresu a port (implicitně 2323) --listen [host[:port]] poslouchej na dané adrese a portu (implicitně všechny adresy, port 2323)

Příloha C Obsah CD-ROM Struktura dat na přiloženém CD-ROM a nejdůležitější soubory jsou: doc/ statetable.* – přechodová tabulka stavového automatu ve formátech html, sxc, plain text a pdf, html/ – vygenerovaná dokumentace API, index.html – startovní stránka vygenerované dokumentace, psock.pdf – tato práce, scripts/ – skripty pro zpracování zdrojových kódů, src/ – kořenový adresář zdrojových kódů, include/net/psock/ – hlavičkové soubory, include/net/psock/ptransfer drv/ – hlavičkové soubory ovladačů paralelního přenosu, net/psock/ – implementace systému, net/psock/ptransfer drv/ – implementace ovladačů paralelního přenosu, tests/ – testovací nástroj psock-testperf, tests/ – testy některých komponent systému, COPYING – licence GPL, README – instrukce k instalaci a použití systému.

53

Literatura [1] Dr. Ing. Sven Ubik: Přenosy velkých objemů dat v rozlehlých Gigabitových sítích http://staff.cesnet.cz/~ubik/publications/2003/olomouc.doc [2] Martin Čížek: Paralelizace datových přenosů Technická zpráva v rámci projektu End-to-end performance sdružení Cesnet, z. s. p. o, 2004. [3] Stránky projektu psock http://perfmon.cesnet.cz/cizek/psock/ [4] Projekt End-to-end performance http://www.ces.net/project/qosip/ [5] Parallel Secure Remote Copy http://perfmon.cesnet.cz/pscp/ [6] RFC 3449: TCP Performance Implications of Network Path Asymmetry http://www.faqs.org/rfcs/rfc3449.html [7] Linux Advanced Routing & Traffic Control Howto http://www.lartc.org/ [8] RFC 2960: Stream Control Transmission Protocol http://www.faqs.org/rfcs/rfc2960.html [9] The SCTP library (sctplib) http://www.sctp.de/sctp-download.html [10] bbFTP: Large files transfer protocol http://doc.in2p3.fr/bbftp/ [11] The GridFTP Protocol and Software http://www.globus.org/datagrid/gridftp.html [12] TCPDUMP/LIBPCAP http://www.tcpdump.org/

54

LITERATURA

55

[13] H. Sivakumar, S. Bailey, R. L. Grossman: Psockets: the case for applicationlevel network stripping for data intensive applications using high speed wide area networks http://www.sc2000.org/techpapr/papers/pap.pap240.pdf [14] RFC 793: Transmission Control Protocol http://www.faqs.org/rfcs/rfc793.html [15] Daniel P. Bovet, Marco Cesati: Understanding the Linux kernel O’Reilly, 2003 [16] T. Hacker, B. Athey, B. Noble: The end-to-end performance effects of parallel TCP sockets on a lossy wide-area network Proceedings of IPDPS, April 2002. [17] J. Padhye, V. Firoiu, D. Towsley, J. Kurose: Modeling TCP throughput: a simple model and its empirical validation ACMSIGCOMM, September 1998. [18] M. Mathis, J. Semke, J. Mahdavi, T. Ott: The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm Computer Communication Review, volume 27, number 3, July 1997. [19] S. Floyd, V. Jacobson: On traffic phase effects in packet-switched gateways Internetworking: Research and Experience 3: 115-156 [20] Hung-Yun Hsieh, Raghupathy Sivakumar: pTCP: an end-to-end transport layer protocol for striped connections Proceedings of International Conference on Network Protocols, 2002 [21] NIST Net network emulator http://www-x.antd.nist.gov/nistnet/

Paralelizace datových přenosů přes rozlehlé vysokorychlostní sítě

Recommend Documents