Algoritmy pro maximální tok Další problémy Network Coding PB165 - Grafy a sítě Toky v síti 30.11.2016 >0 0,0 Ř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 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 (l/, 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 Ci, C2 jsou vyznačeny modře. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Bipartitní grafy 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. 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. 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ě. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Síť a tok 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) —>> IR, které pro každý vrchol v splňuje Kirchhoffův zákon £ f(e)= £ f(e) eeE-(v) 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. □ [fP ► 4 !Š ► 4 > >0 Q,o Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Cirkulace a zdroj a spotřebič 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í 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). Algoritmy pro maximální tok Další problémy Network Coding Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Reziduálni tok 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 Toky v síti - příklad Obrázek : Příklad toku v síti. První číslo v hodnocení hrany je tok, dru 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. F(n= E f(e)- E f(e) e£E+(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. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Velikost toku přes řez 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 F p 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, E ŕ(e) eeW+(P) eew-(P) l/l/+, W~ 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 Shodnost toků přes řezy Necht Cp je libovolný rez, který odděluje zdroj a spotrebič. Potom pro velikost F p toku pres C p platí _Fp(f) = Fjf)_ Přes všechny řezy oddělující zdroj a spotřebič tedy protéká stejný tok. 11/15 Obrázek : Přes všechny vyznačené (i nevyznačené) řezy oddělující sa í protéká tok o velikosti 11. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Shodnost toků přes řezy - důkaz 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 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)= £ c(e)- £ /(e) 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 Ford-Fulkersonův algoritmus • Využívá ekvivalence mezi maximalitou toku a neexistencí cesty ze zdroje ke spotřebiči v reziduálni síti. o 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 Další problémy Network Coding Hledání zlepšující cesty 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í 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) < 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 Další problémy Network Coding Ford-Fulkersonův algoritmus 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 šírky, čí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 Network Coding Ford-Fulkersonův algoritmus - příklad Obrázek : Příklad běhu Ford-Fulkersonova algoritmu, 1. část. Rezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Ford-Fulkersonův algoritmus - příklad 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 Network Coding Ford-Fulkersonův algoritmus - složitost • 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>(| £"|) 9 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(r) iterací. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Edmonds-Karpův algoritmus o Specializace Ford-Fulkersonova algoritmu. o 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é. 9 Průchod do šířky zajistí, že každá nalezená zlepšující cesta je nejméně tak dlouhá, jako předchozí nalezená. 9 Maximální možná délka zlepšující cesty je \ V 9 Složitost algoritmu tak činí 0(VE2). Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Edmonds-Karpův algoritmus - příklad 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 Další problémy Network Coding Omezení toku vrcholem 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 vi, \/2> 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 Další problémy Network Coding Několik zdrojů a spotřebičů 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)= Yl 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 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. Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Network Coding 30.11.2016 Ř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 o 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. 9 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 Algoritmy pro maximální tok Další problémy Network Coding Kódování 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. 9 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 Kódovací schéma určuje pro každý uzel, jak má být vstupní informace kódována. o 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 9 Polynomiální algoritmy pro vytváření kódovacích schém (LIF, LIFE, LIFE-CYCLE, LIFE*) • Procházejí graf od zdroje k příjemci o 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 o 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í 9 využívá hluboké teoretické poznatky z oblasti network coding. 9 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 Náhodnostní kódování - myšlenka • uzly v síti kódují přicházející informace pomocí náhodně vygenerovaných koeficientů (ty se zasílají spolu s daty) 9 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 Další problémy Network Coding Random Linear 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žíva 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 • . .. 9 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í Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding Literatura 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.