PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 1/39 Obsah přednášky 1 Transport Doba na nastavení Doba na dopravu 2 Plánování na počítačové síti Úvod k plánování úloh na počítačové síti Paralelní úlohy s komunikací Plánování datových přenosů PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 2/39 Problém obchodního cestujícího Problém obchodního cestujícího obchodní cestující musí projet všechna města tak, aby celková ujetá vzdálenost (resp. doba cesty) byla minimální a každé město projel právě jednou Grafová reprezentace (orientovaný) hranově ohodnocený graf vrchol = město (orientovaná) hrana z A do B = přímá cesta z A do B hrany mohou být orientované, pokud chceme uvažovat různou náročnost v opačných směrech cesty ohodnocení hrany z A do B = doba nutná na cestu z A do B PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 3/39 Nastavovací doba a cena (setup time and cost) Nastavovací doba sijk, sjk: závislá na úlohách udává závislost na posloupnosti provádění úloh sijk čas nutný pro provádění úlohy k po úloze j na stroji i sjk nastavovací doba nezávislá na stroji Problém obchodního cestujícího = 1|sjk|Cmax město reprezentuje úlohu s nulovou dobou provádění sjk : čas na dopravu z města/úlohy k do města/úlohy j příklad: cesta přes města 12341 odpovídá s12 + s23 + s34 + s41 Klasický příklad: plnění limonád do lahví 1|sjk|Cmax dána cena za nastavení stroje při změně plnění typu limonády scola,voda svoda,cola scola,dzus posloupnost plnění: 100 lahví vody, 50 lahví coly, 70 lahví džusu, Nastavovací cena cijk, cjk s přechodem lze spojit i cenu, kterou je nutne zaplatit PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 4/39 Doba na dopravu (transportation time) Multi-operační rozvrhování úloha se skládá z několika operací může/nemusí být určeno pořadí operací operace má zadáno dobu provádění, konkrétní stroj k provádění stroj: na každém stroji maximálně jedna operace doba na dopravu thl mezi stroji h a l: závislá na strojích kapacita cest mezi stroji neomezená délka cesty mezi stroji = součet odpovídajících dob na dopravu cíl: realizovat všechny operace všech úloh při minimalizaci času dokončení všech úloh Grafová reprezentace orientovaný hranově ohodnocený graf vrchol: stroj hrana: pokud lze přejít přímo z jednoho stroje na druhý ohodnocení hrany: doba na dopravu z jednoho stroje na druhý PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 5/39 Úvod k plánování úloh na počítačové síti Stroj: dán počet procesorů Úlohy prováděny na jednom nebo více uzlech počítačové sítě vyžadují několik procesorů Úlohy potřebují k výpočtu data data dané velikosti na jednom nebo více uzlech data je nutné přenést na uzel, kde se úloha bude počítat realita: data jsou často zreplikována na několika uzlech Linka: kapacita linky: velikost přenesených dat za časovou jednotku např. 100Mb/s, 1Gb/s, 10Gb/s latence: doba nutná na přenos dat po lince Cíl: realizovat všechny úlohy tak, jak postupně (dynamicky) přibývají úlohy musí mít dostatek procesorů data musí ležet v době výpočtu na uzlu, kde se počítá úloha je nutné plánovat i přenosy dat tak, aby bylo možné data přenést vzhledem k latenci i kapacitě linek na cestě PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 6/39 Počítačová síť: grafová reprezentace Vrcholově ohodnocený neorientovaný graf Vrchol: stroj nebo linka Ohodnocení vrcholu-stroje: počet procesorů Ohodnocení vrcholu-linky: kapacita linky linka je chápána jako zdroj, který má zadánu kapacitu doba zpracování úlohy na lince (tj. přenosu dat pro úlohu na lince) odpovídá latenci Hrany: pokud jsou stroje A a B přímo spojeny linkou C, pak existují hrany AC a BC PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 7/39 Plánování úlohy na počítačové síti: příklad Úloha naplánována k provádění na uzlu 1 Data na uzlech 2 a 3 Data jsou přenesena přes D,C a A,B Kapacita linek A,B,C,D musí být v daném čase postačující Celková doba přenostu do 1: max(latenceA+latenceB, latenceD+latenceC) Otázky: Je možné takovouto úlohu naplánovat za probíhajícího provozu na síti? Je možné ji naplánovat při modifikaci cest pro přenosy? Obecně: jak naplánovat úlohu(y) za daného provozu na síť? směrování PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 8/39 Paralelní komunikující úlohy Paralelní aplikace n komunikujících úloh m procesorů několik úloh prováděno zároveň na každém procesoru tj. opět plánování pro daný časový okamžik kromě přenosů explicitně uvažována zátěž na uzlech Grafová reprezentace hranově a vrcholově ohodnocený neorientovaný graf ohodnocené vrcholy: úlohy s danou výpočetní náročností ohodnocené hrany: průběžně komunikující úlohy s komunikační náročností Vyvažování zátěže (load balancing): přiřazení úloh na procesory tak, aby byla vyvážená zátěž jednotlivých procesorů byla minimalizována komunikace úloh na různých procesorech PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 9/39 Rozdělení grafu Formulace problému vyvažování zátěže jako problému rozdělení grafu (graph partitioning) Rozdělení grafu G = (V , E) na V = V1 ∪ · · · ∪ Vm tak, že je V1 ∩ · · · ∩ Vm = ∅ G1 = (V1, E1), . . . , Gm = (Vm, Em) Ei tvořeno hranami, jejichž oba vrcholy patří do Vi součet ohodnocení vrcholů v jednotlivých Vi „zhruba stejný” součet ohodnocení hran E\{E1 ∪ · · · Em} spojujících různé Vj a Vk minimalizován PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 10/39 Rozdělení grafu a bisekce grafu Speciální případ: V = V1 ∪ V2 bisekce grafu (graph bisection), tj. z grafu G = (V , E) vytvoříme dva podgrafy (V1, E1) (V2, E2) tak, že V = V1 ∪ V2, V1 ∩ V2 = ∅ Ei tvořeno hranami, jejichž oba vrcholy patří do Vi , tj. E1, E2 ⊂ E, E1 ∩ E2 = ∅, Ei součet ohodnocení vrcholů ve V1 a V2 je „zhruba stejný” součet ohodnocení hran E\{E1 ∪ E2} spojující vrcholy z V1 a V2 je minimalizován Jak nalézt vhodné rozdělení grafu? problém optimálního rozdělení je NP-úplný už pro bisekci: prohledání všech podmnožin množiny vrcholů (podmnožina a její doplněk tvoří V1 a V2) nutné použít dobré heuristiky PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 11/39 Heuristika: opakovaná bisekce grafu Základní používaný princip při rozdělení grafu: rozdělení množiny vrcholů V na 2k částí: rekurzivní bisekce grafu k-krát 58 dělících hran PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 12/39 Dělící hrany (edge separator) vs. dělící vrcholy (vertex separator) Dělící hrany: ES ⊆ E dělí G po odstranění ES z E na dvě stejně velké nesouvisející komponenty V : V1 a V2 Dělící vrcholy: VS ⊆ V dělí G po odstranění VS a všech jejich hran na dvě stejně velké nesouvisející komponenty V : V1 a V2 ES = zelené hrany VS = červené vrcholy PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 13/39 Rozdělení se souřadnicemi vrcholů (partitioning with nodal coordinates) Myšlenka rozdělení pomocí souřadnic vrcholů každý vrchol má souřadnice v prostoru → rozdělení prostoru pomocí dělicí přímky, která dělí vrcholy v prostoru na poloviny PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 14/39 Opakovaná bisekce grafu s dělící přímkou: příklad PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 15/39 Plánování datových přenosů Problém: plánování datových přenosů, kde se velikost přenášených dat blíží kapacitám používaných linek Varianty: plánování přenosů v čase je třeba uvažovat plánování zdrojů v čase plánování současně probíhajících přenosů není uvažován čas, vše se plánuje pro aktuální okamžik není tedy ani uvažováno plánování úloh v čase na uzly pro tento případ uvedeme základní model PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 16/39 Příklady aplikací plánování přenosů Plánování datových přenosů pro speciální zařízení a přístroje umožňuje plánovat přenosy dopředu na danou dobu, kdy budou linky dostupné (bulk přenosy dat) např. RHIC (relativistic heavy ion collider, USA) Umístění aplikací na servry aplikace je nutno naplánovat na servrech, plánování v daném okamžiku ceny: za přenos aplikací na servry, za běh aplikace na daném servru např. aplikace pro italskou mezibankovní síť Plánování přenosů HD videa v rámci kolaborativního prostřední nutná reakce na okamžitý stav počítačové sítě a naplánování na síť za daných aktuálních podmínek např. medicínské aplikace, filmový průmysl, výuka pomocí videa (vzdálená výuka, přístup např. k operačním sálům na medicíně, záznam a zpracování přednášek) systém CoUniverse vyvíjený na FI MU https://www.sitola.cz/CoUniverse PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 17/39 Naplánované spojení pomocí CoUniverse PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 18/39 Grafová reprezentace: uzel Na uzlu v ∈ V se mohou nacházet různé aplikace producent p ∈ P produkuje data konzument c ∈ C přijímá data distributor d ∈ D je schopen rozesílat přijímaná data do několika linek distributor jako náročná aplikace nejvýše jeden na uzlu možné varianty distributora: 1 distributor může data transformovat (transkódovat) přenášená data např. z nekomprimovaného HDTV videa na HDV MPEG2 video 2 data jsou stejného typu, tj. distributor je reflektorem (uvažováno dále) Uzel má několik rozhraní (interfaces), po kterých posílá a přijímá data množina všech rozhraní I kapacita rozhraní capacityI(i) pro i ∈ I linky připojené k rozhraní links(i) pro i ∈ I PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 19/39 Grafová reprezentace (dokončení) Linka l ∈ L má určen počáteční uzel begin(l) koncový uzel end(l) latenci latency(l) kapacitu capacity(l) Linky reprezentují logickou strukturu sítě reálná struktura sítě často neznámá zahlcení linky detekováno monitorováním stavu sítě v případě nutnosti možné přeplánování nutné realizovat v reálném čase tj. vyžaduje rychlou odezvu Orientovaný graf (V , L) vrcholy: množina uzlů v ∈ V hrany: množina orientovaných linek l ∈ L tento graf reprezentuje základní strukturu, se kterou pracujeme PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 20/39 Ukázka sítě při plánování datových přenosů Producent: sender Konzument: receiver Distributor: reflector PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 21/39 Stream Stream s ∈ S je datový tok od producenta ke konzumentům bandwidth(s) udává požadovanou šířku pásma datového toku streamu příjem dat streamu s je požadován množinou zadaných konzumentů consumers(s)⊆ C data streamu s vysílá právě jeden producent p =producer(s)∈ P obecně může existovat více producentů a cílem plánování je pak vybrat producenty zajišťující maximální kvalitu danou typem přenášených dat např. nekomprimované HDTV video, HDV MPEG2 video, HDV MPEG4 video pro zjednodušení můžeme předpokládat, že každý stream má předem jednoznačně určeného producenta vhodného producenta lze vypočítat předem Předpokládáme tedy: pro každý stream přesně určen jeden producent PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 22/39 Problém plánování datových přenosů Problém plánování několika streamu naplánovat všechny streamy z S na dostupné linky tak, aby byla optimalizována zadaná kritéria, např. minimalizace celkové latence při uvažování kvality spojení: maximalizace kvality přenášených dat všechny přenosy probíhají zároveň Konstrukce distribučního stromu pro každého producenta/stream s distribuční strom jako podgraf grafu (V , L) kořen stromu: uzel s producentem producer(s) listy stromu: uzly s konzumenty consumers(s) vnitřní uzly stromu: uzly s distributory PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 23/39 Distribuce dat Distributor vytváří kopie dat Všechny pakety jdou k jednomu konzumentovi po jedné cestě 1/2 1/2 PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 24/39 Modely pro plánování datových přenosů Modely model založený na linkách model založený na cestách model založený na uzlech Model založený na linkách (link-based model) pro každý požadavek (stream) s: proměnná pro každý link l Proměnná xs,l pro každý stream s a každou linku l xs,l = 1 jestliže s prochází po l 0 jinak Cíl: nalézt hodnoty proměnných xs,l optimální vzhledem k zadanému optimalizačnímu kritériu pro tento model si ukážeme vyjádření typických požadavků problému PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 25/39 Další modely pro plánování na přenosů Model založený na cestách (path-based model) pro každý požadavek s: proměnná pro každou možnou cestu p mezi zdrojem (producent) a cílem (konzument) xs,p = 1 jestliže jde požadavek s po cestě p 0 jinak náročné pokud je hodně možných cest Model založený na uzlech (node-based model) pro každý požadavek s: proměnná pro každý uzel v xs,v = 1 jestliže je uzel v použit pro požadavek s 0 jinak PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 26/39 Vztahy pro konzistentní a optimální plánování Konzistentní plánování kapacita linek a rozhraní posílání a přijímání dat vlastnosti konzumenta a producenta vlastnosti distributora eliminace cyklů Optimální plánování optimalizační kritéria PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 27/39 Optimalizační kritéria Celková latence musí být minimalizována minimize s∈S l∈L latency(l) · xs,l Další kritéria: maximalizace kvality přenosu při zajišťování linek s maximální kapacitou pro přenášená data balancování latencí všech linek při video-konferencích k zajištění bezproblémového přerušení a vstupu do probíhající video-konference PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 28/39 Kapacita linky a rozhraní Kapacita linky Požadovaná šířka pásma pro všechny streamy nesmí překročit kapacitu žádného linku ∀l ∈ L s∈S bandwidth(s) · xs,l ≤ capacity(l) Kapacita rozhraní Streamy přenášené jedním rozhraním nesmí překročit jeho kapacitu ∀i ∈ I s∈S l∈links(i) bandwidth(s) · xs,l ≤ capacityI(i) PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 29/39 (NE)posílání a (NE)přijímání dat Kdo může posílat data? Pokud není na počátečním uzlu linky l ani producent streamu s ani distributor ⇒ xs,l = 0 Kdo může přijímat data? Pokud není na koncovém uzlu linky l ani konzument streamu s ani distributor ⇒ xs,l = 0 PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 30/39 Vlastnosti konzumenta a producenta Konzument c přijímá data právě jednou linkou ∀s ∈ S ∀c ∈ consumers(s) l∈L ∧ c∈end(l) xs,l = 1 C Producent posílá data právě jednou linkou ∀s ∈ S l∈L ∧ producer(s)∈begin(l) xs,l = 1 P PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 31/39 Vlastnosti distributora Distributor přijímá data nejvýše jednou ∀d ∈ D s∈S l∈inlinks(d) xs,l ≤ 1 D ? inlinks(d) linky, které vstupují do uzlu distributora outlinks(d) linky, které vystupují z uzlu distributora PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 32/39 Vlastnosti distributora Distributor přeposílá příchozí stream aktivní distributor pro stream s ∀d ∈ D l∈inlinks(d) xs,l ≤ l∈outlinks(d) xs,l D PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 33/39 Vlastnosti distributora Na distributorovi nevznikají žádná data neaktivní distributor pro stream s ∀d ∈ D l∈inlinks(d) xs,l = 0 ⇔ l∈outlinks(d) xs,l = 0 D PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 34/39 Eliminace cyklů C C C D DP D D D C C C D DP D D D Všechny cykly mezi distributory je nutné zakázat Řešení: Nejvýše k − 1 používaných linek mezi každou k-ticí uzlů pro každý stream ve stromu s k uzly je k − 1 hran, přidáním další hrany vznikne cyklus PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 35/39 Metody řešení Uvedený model popisuje základní množinu požadavků pro řešení problémů plánování datových přenosů Při řešení konkrétního problému nutné přidat specifická omezení a také redundantní omezení pro úspěšné/efektivní řešení problému Daný model (a jeho rozšíření na konkrétní aplikaci) lze řešit pomocí grafových algoritmů (toky v síti, hledání cest v grafu) programování s omezujícími podmínkami např. CoUniverse využívá pro plánování Java řešič Choco pro omezující podmínky celočíselné programování nově vyvíjený plánovač pro CoUniverse meta-heuristiky (lokální prohledávání) PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 36/39 Datové přenosy: příklad Pro zadanou počítačovou síť uveďte uveďte seznam proměnných. Navrhněte, jak by mohl být datový přednos realizován a uveďte odpovídající hodnoty proměnných reprezentující řešení optimalizující celkovou latenci. Jaká je celková latence? Ohodnocení linku l latency(l), capacity(l) Stream s1 bandwith(s1) = 5 producer(s1) = P1 consumers(s1) = {C1, C2} Stream s2 bandwith(s2) = 5 producer(s2) = P2 consumers(s2) = {C3} BP1 P2 C1 D1 D4D3D2 C3 C2 1,10 3,10 2,10 1,10 1,10 3,10 1,10 1,1 1,10 2,1 1,10 3,10 PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 37/39 Datové přednosy: výsledný graf Proměnné: pro stream s1: xs1,l1, . . . , xs1,l12 pro stream s2: xs2,l1, . . . , xs2,l12 xs1,l2 = 1 xs1,l4 = 1 xs1,l6 = 1 pro ostatní linky a stream s1 ... 0 B Celková latence 1+1+2 + 1+3 l1 l2 l3 l4 l5 l6 l7 P1 P2 C1 D1 D4D3D2 C3 C2 1,10 3,10 2,10 1,10 1,10 3,10 1,10 1,1 1,10 2,1 1,10 3,10 l8 l9 l10 l11 l12 xs2,l9 = 1 xs2,l12 = 1 pro ostatní linky a stream s2 ... 0 PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 38/39 Datové přenosy: cvičení Pro graf počítačové sítě na obrázku uvažujte datové přenosy pro stream s1 a s2, které jsou zadány následujícím způsobem stream s1: bandwith(s1)=10, producer(s1)=P1, consumer(s1)={C1}; stream s2: bandwith(s2)=10, producer(s2)=P2, consumer(s2)= {C2,C3}. Ohodnocení hran grafu přitom udává jejich latenci a kapacitu. BP1 P2 C1 D1 D4 D3 D2 C3C2 5,1 5,1 15,10 5,10 6,10 4,10 5,10 5,10 7,10 8,10 6,10 Uveďte, jaké proměnné jsou nutné při řešení tohoto problému datových přenosů a navhrněte jejich vhodné hodnoty tak, aby odpovídající řešení minimalizovalo celkovou latenci. Jaká je pak celková latence? PB165 Grafy a sítě: Plánování pro transport, přenosy a komunikace 39/39