Algoritmy pro maximální tok Další problémy PB165 - Grafy a sítě Toky v síti 11.11.2014 Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Obsah přednášky Q Řezy v grafu Q Toky v síti Q Algoritmy pro maximální tok Q Další problémy Qi Network Coding Neformálně: • „Rozříznutí" grafu napříč hranami (nikoliv skrz vrcholy) na dvě poloviny. • Rozdělení vrcholů na dvě části. Definice Řezem v grafu G = (V, E) nazýváme rozklad množiny V na 2 neprázdné podmnožiny P, P. Wc(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 Rezy v grafu Toky v síti Algoritmy pro max imální tok Další problémy Network Coding Rezy v grafu V každém grafu existuje 2^ 1 - 1 řezů. Obrázek : Příklady řezů v grafu jsou vyznačeny čárkovaně. <□> <9» <1> 3 O^O Řezy v grafu Toky v síti Algoritmy pro maximální tok 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, říkáme že křižují řez C. Obrázek : Hrany křižující řezy Q, C2 jsou vyznačeny modře. Definice 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) = Wc(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, t), s G S a t G T je spojena právě jednou hranou. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding 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 Q 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 Definice Minimálním rozumíme takový řez v grafu, jehož váha je minimální. Maximální fez 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ě. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Definice Sítí nazýváme orientovaný, hranově ohodnocený graf G = (V, E). Definice Tokem v síti nazýváme takové ohodnocení hran reálnými čísly f:E(G) —> M., které pro každý vrchol v splňuje Kirchhoffův zákon £ f(e)= £ f(e) eeE+(v) eeE-(v) Takový g raf 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. 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. Algoritmy pro r Další problémy Network Coding Zpravidla omezujeme tok na hraně shora i zdola, tj. platí ^(e) G (/(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) < f(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. Řezy v grafu Toky v síti 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). Definice Reziduálni kapacitou hrany e rozumíme číslo c(e) — ^(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 Další problémy Network Coding Velikost toku značíme F(f). Velikost toku od zdroje ke spotřebiči definujeme jako množství toku, které vzniká ve zdroji s. F(f)= £ f(e)- E f(e) ee£+(s) eeE-(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. 5 ^«,0 Nechť řez C dělí vrcholy grafu na množiny P,P. Označíme jej Cp. Dále nechť zdroj toku náleží do množiny P a spotřebič do P. Potom má smysl definovat velikost Fp toku přes řez Cp jako rozdíl mezi velikostí toku na hranách vedoucích z množiny P a velikostí toku na hranách vedoucích do této množiny. Říkáme, že řez Cp odděluje zdroj a spotřebič. FP(f)= y, f(e)- E f(e) eeW+(P) eew-(P) 1/1/+, l/l/- značí hrany vycházející z množiny l/l/, resp. do ní vstupující. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Věta Nechť Cp je libovolný řez, který odděluje zdroj a spotřebič. Potom pro velikost Fp toku přes Cp platí _Fpjf) = Fjf)_ Přes všechny řezy oddělující zdroj a spotřebič tedy protéká stejný tok. Obrázek : Přes všechny vyznačené (i nevyznačené) řezy oddělující s a t protéká tok o velikosti 11. Důkaz. Důkaz povedeme indukcí: Základ indukce: Položme P = {s}, kde s je zdroj toku. Tvrzení platí z definice. Indukční krok: Do množiny P přidáme libovolný vrchol grafu, různý od spotřebiče. Jelikož pro tento vrchol musí platit Kirchhoffův zákon, nezmění se nikterak rozdíl mezi velikostmi toků z P vytékajících a do P vtékajících. Platnost tvrzení se tedy nezmění. Jelikož postupným přidáváním vrcholů lze získat libovolný řez, který odděluje zdroj od spotřebiče, platí tvrzení pro všechny řezy zdroj od spotřebiče oddělující. □ Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Kapacita řezu oddělujícího zdroj a spotřebič specifikuje, jaký maximální tok může tímto řezem protéct. Definována je jako součet kapacit všech hran, které tento řez protínají ve směru od zdroje ke spotřebiči zmenšená o součet minimálních kapacit hran opačně orienovaných. c(cP)= y, c(e)- E '(e) eeW+(P) eew-(p) Obrázek : Kapacity řezů Q,..., C4 jsou po řadě 16, 18, 17, 15. Problém maximálního toku je hledání největšího toku v grafu od zdroje ke spotřebiči. Následující podmínky jsou ekvivalentní: O Tok f je maximální (maximalizujeme F(f)). O \f\ je kapacita některého řezu oddělujícího zdroj od spotřebiče. O V reziduálni síti neexistuje cesta ze zdroje ke spotřebiči. Algoritmy pro nalezení maximálního toku vycházejí z těchto ekvivalencí - hledají řez s minimální kapacitou nebo přidávají cesty mezi zdrojem a spotřebičem, dokud nějaké v reziduálni síti existují. • Nejednodušší algoritmus. • Generuje postupně všechny podmnožiny vrcholů, pro každý provede následující kroky: • Najde mezi hranami všechny, které křižují řez definovaný touto množinou vrcholů. • Sečte kapacity hran křižujících tento řez, směřujících od zdroje ke spotřebiči. • Výsledkem je řez s minimální vypočtenou kapacitou. Jelikož všech řezů oddělujících zdroj od spotřebiče je 2lv/l~2 — 1, pro každý je potřeba zkontrolovat všech \E\ hran, celková časová složitost algoritmu hledání maximálního toku brutální silou je 0(2M-2|E|) /(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 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í. • 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) — l(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. Můžeme použít značkovací proceduru (Py(e) je počáteční a Ky(e) je koncový vrchol hrany e): nicializace 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í f(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) < ^(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. Algoritmy pro r 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 | 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). Obrázek : Příklad běhu Ford-Fulkersonova algoritmu, 1. část. < □ ► (e)f(e). eeE Úkolem je potom najít maximální tok sítí takový, že jeho cena bude zároveň minimální. 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 /(e)^° eeW+{P) eeW-{P) Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding 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čí a dosavadní tok f je přípustný. O Je-li f(h) < l(h), pak z := Kv(h),s := Py{h), v opačném případě (f(h) > c{h)) z := Pv(h),s:= Kv{h). Q 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. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Network Coding 11.11.2014 Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Propustnost sítě je dána větou MaxFlow-MinCut. Ta říká, že maximální propustnost je rovna minimálnímu řezu takovému, že zdroj dat je v T a přijímající v T. Definice platí pro: • unicast • broadcast • multicast 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. Source: 0 Sink: 5 14 S ► < -š ► 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). 4Ľ3k4l3*4 = k4 = * -š -O^O Algoritmy pro r 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 1/1/ může v daný okamžik přeposílat bud' 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 1/1/ symbol a, uzel 7~i obdrží dvakrát a (tok velikosti 1), a uzel 7~2 obdrží a i b (tok 2|. ^ 1 -00.0 Řezy v grafu Toky v síti 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 W 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 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 • 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) Algoritmy pro r Další problémy Network Coding • 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é Algoritmy pro r 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 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 4Ľ3k4l3*4 = k4 = * -š -O^O Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding 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). 4Ľ3k4l3*4 = k4 = * -š -O^O Algoritmy pro r Další problémy Network Coding aX+bY X+dY cX+dY 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ří bud' aX + bY nebo cX + dY. 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 Algoritmy pro r Další problémy Network Coding 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í Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding R. Ahlswede, S.-Y.R. Li, and R.W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4): 1204-1216, July 2000. T. Ho, M. Medard, R. Koetter, D.R. Karger, M. Effros, J. Shi, and B. Leong. A Random Linear Network Coding Approach to Multicast. IEEE Transactions on Information Theory, 52(10):4413-4430, October 2006. S.-Y.R. Li and R.W. Yeung. Linear network coding. IEEE Transactions on Information Theory, 49(2):371-381, February 2003.