Algoritmy pro maximální tok Další problémy Network Coding PB165 - Grafy a sítě Toky v síti 26.11.2015 >0 0,0 Řezy v grafu Toky v síti Obsah přednášky Algoritmy pro maximální tok Další problémy Network Coding Rezy v grafu Q Toky v síti Q Algoritmy pro maximální tok O Další problémy Q Network Coding Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Rez v grafu Neformálně: • „Rozříznutí" grafu napříč hranami (nikoliv skrz vrcholy) na dvě poloviny. • Rozdělení vrcholů na dvě části. Řezem v grafu G = (V, E) nazýváme rozklad množiny V na 2 neprázdné podmnožiny P, P. Wq(P) je množina všech hran, jejichž jeden vrchol je v P a druhý nikoliv. Jelikož se jedná o rozklad, platí: PnP = 0,PUP = V Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Rezy v grafu V každém grafu existuje 2^1 1 — 1 řezů. Obrázek : Příklady řezů v grafu jsou vyznačeny čárkovaně. Řezy v grafu Toky v síti Algoritmy pro maximální tok Hrany křižující řezy Další problémy Network Coding Definice Necht řez C dělí vrcholy na množiny P, P. O hranách (u, v), jejichž jeden vrchol leží v P a druhý nikoliv, fikáme že křižují fez C. Obrázek : Hrany křižující řezy Q, C2 jsou vyznačeny modře. Řezy v grafu Toky v síti Bipartitní grafy Algoritmy pro maximální tok Další problémy Network Coding Bipartitiní graf je takový graf G, jehož množina vrcholů je disjunktním sjednocením dvou množin S a T a platí E{G) — Wq(S). Množiny S a T nazýváme stranami bipartitního grafu. Každá hrana grafu G má jeden vrchol v S a druhý v T. Definice Úplný bipartitní graf je takový bipartitní graf, jehož každá dvojice vrcholů (s, ŕ), s G S a t G T je spojena právě jednou hranou. Definice Vahou řezu v hranově neohodnoceném grafu označujeme počet hran, které tento řez křižují. V hranově ohodnoceném grafu se vahou rozumí součet ohodnocení všech hran křižujících tento řez. Obrázek : Váha řezu C\ v neohodnoceném grafu je rovna 4. Váha řezu C2 v ohodnoceném grafu je rovna 17. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Minimální a maximální rez Definice Minimálním rozumíme takový řez v grafu, jehož váha je minimální Maximální řez je naopak ten s maximální vahou. Minimální řez v grafu může být nalezen v čase polynomiálním vůči velikosti grafu. Naopak, problém maximálního řezu je NP-úplný. Obrázek : Minimální řez ve vyobrazeném grafu je vyznačen zeleně, maximální červeně. Sítí nazývame orientovaný, hranově ohodnocený graf G = (\/, E). Definice Tokem v síti nazýváme takové ohodnocení hran reálnými čísly f : E(G) —>> IR, /cteré pro každý vrchol v splňuje Kirchhoffův zákon Takový graf si můžeme představit jako soustavu potrubí, pro níž platí zákon zachování hmoty, tj. kolik do vrcholu přitéká, tolik z něj zase vytéká. Orientace hrany určuje směr proudění, záporný tok představuje proudění proti směru hrany. eeE+(v) eeE-(v) Řezy v grafu Toky v síti Algoritmy pro maximální tok Cirkulace a zdroj a spotřebič Další problémy Network Coding Pokud Kirchhoffův zákon platí pro všechny vrcholy, mluvíme o cirkulaci. Alternativou je tzv. tok od zdroje ke spotřebiči, kde dva vrcholy Kirchhoffův zákon nesplňují. Ve zdroji tok vzniká a ve spotřebiči (stok, výlevka, sink) zaniká. Tok od zdroje ke spotřebiči můžeme vždy převést na cirkulaci přidáním hrany spojující zdroj a spotřebič. Takovou hranu nazýváme návratovou hranou. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Přípustný tok Zpravidla omezujeme tok na hraně shora i zdola, tj. platí f(e) £ (/(e),c(e)}. Číslo c(e) nazýváme kapacitou hrany, případně horním omezením toku v hraně. Číslo /(e) nazýváme dolním omezením toku v hraně. Tok, který splňuje /(e) < r(e) < c(e) pro všechny hrany e nazýváme přípustným tokem. V řadě praktických případů bývá dolní omezení toku zpravidla rovno 0, je-li však nenulové, není a priori jasné, zda existuje přípustný tok v síti. -írnJ^ < >• -E O Q, O Řezy v grafu Toky v síti Příklady sítí Algoritmy pro maximální tok Další problémy Network Coding Výše definované s/íějsou vhodnými reprezentacemi reálných sítí. Klasická teorie grafů se velmi často věnuje problémům toků na železničních, silničních a dalších dopravních sítích. Samostatnou oblastí jsou rozvodné sítě - vodovodní, plynové atd. Obecně mluvíme o transportních sítích. Většina úloh je věnována optimalizaci takovýchto sítí, případně nalezení úzkých míst, maximální kapacity (propustnosti) sítě, garance minimální propustnosti i při výpadku některých linek či vrcholů apod. Pro nás jsou zajímavé toky v počítačových sítích. Na řešení úloh s toky lze převést i řadu plánovacích úloh, např. tzv. přiřazovacíúlohy. V těch máme za úkol přiřadit n úkolů mezi pracovníky tak, abychom minimalizovali náklad (provedení konkrétní úlohy konkrétním pracovníkem má svou cenu). Lze převést na bipartitní graf (pracovníci jsou zdroje a úlohy jsou spotřebiče, hrana představuje cenu práce). Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Reziduálni tok Reziduálni kapacitou hrany e rozumíme číslo c(e) — f{e), tj. rozdíl kapacity hrany a aktuálního toku. ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Reziduálni kapacity hran tvoří reziduálni síť. V mnoha případech potřebujeme zjistit, zda reziduálni síť existuje. Hrany s reziduálni kapacitou nula nejsou v reziduálni síti obsaženy (není možné přes ně vést nenulový tok). Řezy v grafu Toky v síti Algoritmy pro maximální tok Toky v síti - příklad Další problémy Network Coding Obrázek : Příklad toku v síti. První číslo v hodnocení hrany je tok, druhé kapacita hrany Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Velikost toku Velikost toku značíme F(f). Velikost toku od zdroje ke spotřebiči definujeme jako množství toku, které vzniká ve zdroji s. m = E E w eGE+(s) eGE-(s) E+, E~ označují součet toků vstupujících do vrcholu, resp. vystupujících z něj. Obrázek : Velikost vyobrazeného toku (11) je dána množstvím toku opouštějícím zdroj. /(e) pro hranu vzad. Definice říká, že aktuální tok lze zvýšit na hranách vpřed a snížit na hranách vzad o nějakou hodnotu d > 0. Definice Kapacitou zlepšující cesty pak rozumíme maximální hodnotu d, o kterou lze tok na zlepšující cestě změnit. Řezy v grafu Toky v síti Algoritmy pro maximální tok Ford-Fulkersonův algoritmus Další problémy Network Coding • Využívá ekvivalence mezi maximalitou toku a neexistencí cesty ze zdroje ke spotřebiči v reziduálni síti. • Hledá zlepšující cesty mezi zdrojem a spotřebičem, dokud nějaká taková existuje. • Pro hledání cest používá i zpětných hran. • Z hran na cestě se vybere ta, jejíž reziduálni kapacita je minimální. o V případě zpětné hrany (projité proti směru její orientace) se namísto hodnoty c(e) — f(e) bere tok, který hranou protéká ve směru její orientace - tedy f (e) — /(e). Toky se takto mohou vzájemně anulovat. • O tuto minimální kapacitu se zvýší tok po všech dopředných hranách na nalezené cestě. • Naopak, na hranách zpětných se hodnota toku sníží o stejnou hodnotu. Řezy v grafu Toky v síti Algoritmy pro maximální tok Hledání zlepšující cesty Další problémy Network Coding Můžeme použít značkovací proceduru (Py(e) je počáteční a Ky{e) je koncový vrchol hrany e): Inicializace Označkujeme vrchol zdroje, ostatní jsou bez značek. Vpřed Existuje-li hrana e taková, že Py{e) má značku a Ky(e) nemá a současně platí r(e) < c(e), pak označkuj Ky(e). Vzad Existuje-li hrana e taková, že Ky(e) má značku a Py{e) nemá a současně /(e) < r(e), pak označkuj Py(e). Ukončení Je-li označkován spotřebič, nalezli jsme zlepšující cestu. Nelze-li další vrchol označkovat, pak zlepšující cesta neexistuje. Řezy v grafu Toky v síti Algoritmy pro maximální tok Ford-Fulkersonův algoritmus Další problémy Network Coding Pro všechny hrany (u,v) I f(u,v) = 0 Dokud existuje zlepšující cesta p: I Vyber minimální kapacitu d hrany na této cestě. I Pro všechny hrany na cestě p: I | f(u,v) = f(u,v) + d I I f(v,u) = f(v,u) - d Algoritmus neříká, jakým způsobem se má cesta ze zdroje ke spotřebiči hledat. V praxi se používá obvykle průchod do hloubky, nebo průchod do šířky, čímž se z algoritmu stává Edmonds-Karpův (viz dále). Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Ford-Fulkersonův algoritmus - příklad Network Coding Obrázek : Příklad běhu Ford-Fulkersonova algoritmu, 1. část. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Ford-Fulkersonův algoritmus - příklad Network Coding Obrázek : Příklad běhu Ford-Fulkersonova algoritmu, 2. část. Minimální řez je vyznačen na posledním obrázku. Kapacita je 21, což je i maximální tok v tomto grafu. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Ford-Fulkersonův algoritmus - složitost Network Coding • V obecném případě není možné dokázat, že běh algoritmu skončí. • V některých případech nemusí hodnota nalezeného toku ani konvergovat k maximu. V reálných aplikacích jsou kapacity hran obvykle reprezentovány celými čísly. To zaručuje ukončení běhu algoritmu: • Maximální tok má v takovém případě také celočíselnou hodnotu. • Časová složitost nalezení zlepšující cesty je C>(| £"|) • S každou nalezenou zlepšující cestou se hodnota nalezeného toku zvýší minimálně o 1. • Maximálně může tedy proběhnout nejvýše F(f) iterací. Řezy v grafu Toky v síti Algoritmy pro maximální tok Edmonds-Karpův algoritmus Další problémy Network Coding Specializace Ford-Fulkersonova algoritmu. Pro hledání zlepšujících cest je použit průchod do šírky. Pro potřeby průchodu do šířky jsou délky hran považovány za jednotkové. Průchod do šířky zajistí, že každá nalezená zlepšující cesta je nejméně tak dlouhá, jako předchozí nalezená. Maximální možná délka zlepšující cesty je \ V Složitost algoritmu tak činí 0(VE2). Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Edmonds-Karpův algoritmus - příklad Network Coding Ford-Fulkerson Edmonds-Karp Obrázek : V horní části obrázku je znázorněn možný počátek běhu Ford-Fulkersonova algoritmu. Běh může pokračovat stejným způsobem i nadále, a tak potřebovat mnoho iterací. Edmonds-Karpův algoritmus nalezne odpověď během 2 iterací. Řezy v grafu Toky v síti Algoritmy pro maximální tok Omezení toku vrcholem Další problémy Network Coding Reálné aplikace mohou klást i omezení na velikost toku procházejícího vrcholem - např. sběrné místo kanalizací, aktivní prvek v síti, rychlost zpracování dat na příjemci. Pokud jsou toky nezáporné, lze použít následující transformaci grafu: Obrázek : Vrchol je nahrazen dvěma vrcholy a hranou. Vrchol v s omezenou kapacitou nahradíme vrcholy v\, v2, jejichž kapacita nebude omezena. Hrany směřující do v přesměrujeme do vi, hrany z v vycházející budou vycházet z v2. Vrcholy vi, v2 spojíme hranou, jejíž kapacita bude rovna původní kapacitě vrcholu v. Na takový graf je poté možno použít standardní algoritmy pro hledání maximálního toku. Řezy v grafu Toky v síti Algoritmy pro maximální tok Několik zdrojů a spotřebičů Další problémy Network Coding Obdobně lze standardní algoritmy použít i v případě, kdy zadání obsahuje více než 1 zdroj nebo spotřebič: K síti přidáme fiktivní zdroj a spotřebič. Z nově přidaného zdroje povedou hrany (s ,,neomezenou" kapacitou) do všech zdrojů, obdobně přidáme hrany ze všech spotřebičů do nově přidaného. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Nej levnější toky Ke každé hraně je krom její kapacity definována i cena a(e) jednotkového toku. Cena toku hranou e je potom rovna a(e)r(e). Celková cena toku sítí je potom definována jako eeE Úkolem je potom najít maximální tok sítí takový, že jeho cena bude zároveň minimální. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Přípustná cirkulace Pokud se omezíme na cirkulace, je celá řada algoritmů (a odpovídající teorie) jednodušší. A platí, že úlohy týkající se přípustného toku od zdroje ke spotřebiči lze převést na hledání přípustné cirkulace přidáním návratové hrany. Věta V síti s omezeními toku I a c existuje přípustná cirkulace právě tehdy, když každý řez má nezápornou kapacitu c(cP)= Y. c(e)- E eeW+(P) eeW-(P) Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Algortimus pro přípustnou cirkulaci Vstupem je síť G s omezeními toku /, c a libovolná (i nulová) cirkulace f. Výstupem je buď přípustná cirkulace f nebo řez se zápornou kapacitou. O Najdeme hranu h s nepřípustným tokem. Pokud taková hrana neexistuje, výpočet končia dosavadní tok ŕ7 je přípustný. O Je-li f(h) < l(h), pak z := Kv(h),s := Pv(h), v opačném případě (f(h) > c(h)) z := Pv(h),s:= Kv(h). O Nalezneme zlepšující cestu z vrcholu z do vrcholu s. Pokud cesta neexistuje, výpočet končí, přípustná cirkulace neexistuje a množina označkovaných vrcholů P určuje řez Cp, který má zápornou hodnotu. O Pokud cesta existuje, doplníme zlepšující cestu o hranu h, čímž vznikne zlepšující kružnice. Vypočteme její kapacitu, změníme toky na jejích hranách (viz předchozí algoritmy). Pak se vracíme zpět na krok 1. >0 q,o Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Network Coding 26.11.2015 Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Motivace Propustnost sítě je dána větou MaxFlow-MinCut. Ta říká, že maximální propustnost je rovna minimálnímu řezu takovému, zdroj dat je v T a přijímající v T'. Definice platí pro: • unicast • broadcast • multicast Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Unicast Po unicast umíme maximální tok najít pomocí algoritmu Ford-Fulkerson. Neformálně: Algoritmus využíva hledání zlepšujících cest. Začíná s nulovým tokem od zdroje k příjemci a postupně ho zvyšuje, dokud je to možné (nejsou překročeny kapacity linek). Zlepšující cesta od zdroje k příjemci je taková cesta, na které můžeme zvýšit tok, aniž by byla překročena kapacita některé linky na cestě. V každém kroku algoritmu nalezneme nějakou zlepšující cestu a zvýšíme tok. Neexistuje-li zlepšující cesta, algoritmus končí. =>* umíme efektivně realizovat maximální tok v grafech s jedním příjemcem. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Pro multicast pořád platí věta MaxFlow-MinCut. Problémem aleje, že neexistuje efektivní algoritmus pro hledání maximální propustnosti. =4> neumíme prakticky realizovat maximální tok (kromě brute-force způsobu). Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Příklad: Hrany mají jednotkovou kapacitu a navěstí hran určují přenášenou informaci. • Danou hranou umíme přenést jeden symbol za jednotku času. • Uzel W může v daný okamžik přeposílat buď a nebo b. • V obou případech bude přicházející tok v jednom z koncových uzlů pouze 1. • Např. pošle-li uzel W symbol a, uzel 7~i obdrží dvakrát a (tok velikosti 1), a uzel 7~2 obdrží a i b (tok 2^. ^- > < » > , = > = Řezy v grafu Toky v síti Kódování Algoritmy pro maximální tok Další problémy Network Coding Situace se ale změní, povolíme-li uzlu l/l/, aby kódoval přicházející informaci. Zvolme jednoduchou operaci kódování + (konkrétně si za touto operací můžeme představit XOR). • Protože velikost správy a + b je 1, uzel 1/1/ může tuto správu poslat v jednom kroku. • Uzel 7~i obdrží a a taky a + b. Z toho jednoduše určí b jako b = (a + b) - a. • Obdobně pro uzel 7~2 Řezy v grafu Toky v síti Kódovací schema Algoritmy pro maximální tok Další problémy Network Coding Kódovací schéma určuje pro každý uzel, jak má být vstupní informace kódována. • Existují efektivní algoritmy pro návrh kódovacího schématu v obecnejších grafech. • Jednotlivým uzlům přiřazujeme lokální kódovací funkci • Globální kódovací funkce vyjadřují, jak je informace transformována při přechodu sítí, t.j., jak má příjemce zrekonstruovat úvodní informaci. • Bylo dokázáno, že pro dosahovaní maximální propustnosti postačují lineární kódovací funkce (dvě po sobě jdoucí lineární kombinace tvoří opět lineární kombinaci) • Z praktického hlediska to znamená, že každý příjemce musí řešit systém lineárních rovnic, kde neznámými jsou původní informace. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Algoritmy • Polynomiální algoritmy pro vytváření kódovacích schém (LIF, LIFE, LIFE-CYCLE, LIFE*) • Procházejí graf od zdroje k příjemci • Konstruují kódovací funkce (vektory) pro každý uzel tak, aby výslední systém obsahoval dostatečný počet lineárně nezávislých rovnic (jinak by neexistovalo jeho řešení a příjemce by nebyl schopen data zrekonstruovat) Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Algoritmy II - praktické nevýhody • kódovací schéma musí být vytvořeno před přenosem • pracují centralizovane a na statických topologiích • dojde-li ke změně topologie, musí se schéma vypočíst znovu • pracují se zjednodušeným modelem sítě • stejné kapacity linek • všechny datové toky jsou stejně velké • latence na všech linkách je stejná • operace v síti jsou synchronizované Řezy v grafu Toky v síti Dynamické sítě Algoritmy pro maximální tok Další problémy Network Coding Pro reálné sítě je vhodnejší použít jiný přístup =4> Náhodnostní kódování • využívá hluboké teoretické poznatky z oblasti network coding. • ty ukazují, že znalost topologie není k dosahování maximální prospustnosti pomocí kódování potřebná. Řezy v grafu Toky v síti Algoritmy pro maximální tok Náhodnostní kódování - myšlenka Další problémy Network Coding • uzly v síti kódují přicházející informace pomocí náhodně vygenerovaných koeficientů (ty se zasílají spolu s daty) • při průchodu sítí se nám opět „nabalují" lineární kombinace, tentokrát ale náhodné • aby přijímající mohl úspěšné dekódovat informace, potřebuje „nasbírat" dostatečný počet lineárně nezávislých kombinací • kódujeme-li nad algebraickým polem vhodné velikosti, příjemce bude s vysokou pravděpodobností schopen dekódovat informace. • neformálně: ve výsledku to funguje Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Kontrolní otázka Jaký počet lineárních kombinací je dostatečný? Jaký počet lineárních kombinací je dostatečný? Každá lineární kombinace určuje jednu rovnici ve výsledném systému rovnic. Abychom mohli dekódovat, potřebujeme alespoň tolik rovnic, kolik jednotlivých bloků informace jsme obdrželi (obrázek na následujícím slajdu). Řezy v grafu Toky v síti Algoritmy pro maximální tok Random Linear Network Coding Další problémy Network Coding Z = e(aX + bY) + f{cX + dY) = (ea + fc)X + (eb + fd) Y Každý z příjemců řeší systém rovnic. Jedna z rovnic je v obou případech Z, druhou tvoří buď aX + bY nebo cX + dY. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Aplikace I Kromě dosahování maximální propustnosti se network coding využívá i v jiných oblastech, kde je třeba zvyšovat efektivitu šíření informace. • Bezdrátové sítě • Systémy COPE, MORE • Streamování videa s prioritizací vrstev • Sítě pro spolupráci mobilních zařízení • Úprava TCP pro použití na ztrátových linkách • . .. • Peer-to-peer sítě • Poskytování obsahu velkému počtu uživatelů - systé Avalanche • Live Streaming Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Aplikace II Distribuované úložiště • Navrhování robustních schémat • Snižování objemu dat přenášených v systému - Wuala Network Coding a GPU • Snaha o zrychlení kódovacích operací pomocí GPU, resp. spojeného CPU-GPU kódování