FAKULTA INFORMATIKY Masarykova univerzita PB165 - Grafy a sítě Toky v síti 5.12.2019 PB165 - Grafy a sítě • 5.12.2019 1/51 FAKULTA INFORMATIKY I Masarykova univerzita Obsah přednášky Řezy v grafu Toky v síti Algoritmy pro maximální tok Další problémy Network Coding . PB165 - Grafy a sítě • 5.12.2019 2/51 Řezy v grafu FAKULTA INFORMATIKY Masarykova univerzita Řez v grafu 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ývame 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 druhy nikoliv. Jelikož se jedná o rozklad, platí: PnP = 0,PuP= V PB165 - Grafy a sítě • 5.12.2019 3/51 Řezy v grafu FAKULTA INFORMATIKY Masarykova univerzita Řezy v grafu V každém grafu existuje 2^l_1 - 1 řezů. Obrázek: Příklady řezů v grafu jsou vyznačeny čárkovaně. PB165 - Grafy a sítě • 5.12.2019 4/51 Řezy v grafu FAKULTA INFORMATIKY Masarykova univerzita Hrany křižující řezy Definice Necht řez C dělí vrcholy na množiny P, P. 0 hranách (u, v), jejichž jeden vrchol lezív P a druhy nikoliv, říkáme ze kňzujířez C. Obrázek: Hrany křižující řezy d, Cj jsou vyznačeny modře. PB165 - Grafy a sítě • 5.12.2019 5/51 Řezy v grafu FAKULTA INFORMATIKY I Masarykova univerzita Bipartitní grafy Definice Bipartitinľgrafje takový graf G, jehož množina vrcholu je disjunktním sjednocením dvou množin S a T a platí E (G) = Wq(S). Množiny S a T nazývame stranami bipartitniho grafu. Každá hrana grafu G má jeden vrchol v S a druhý v T. Definice Uplny bipartitní graf je takový bipartitní graf jehož každá dvojice vrcholu (s, ŕ), s g S a t g T je spojena pravé jednou hranou. PB165 - Grafy a sítě • 5.12.2019 6/51 Řezy v grafu FAKULTA INFORMATIKY Masarykova univerzita Váha řezu 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 Cj v ohodnoceném grafu je rovna 17. . PB165 - Grafy a sítě • 5.12.2019 7/51 Řezy v grafu FAKULTA INFORMATIKY Masarykova univerzita Minimální a maximální řez Definice Minimálním rozumíme takový řez v grafu, jehož vdha 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ě. PB165 - Grafy a sítě • 5.12.2019 8/51 Toky v síti FAKULTA INFORMATIKY Masarykova univerzita Síť a tok Definice Sítí nazývame orientovaný, hranově ohodnoceny graf G = (V, £). Definice Tokem vsítí nazývame takové ohodnocení hran reálnymi čísly f : f (G) —>► IR, které pro každý vrchol v splňuje Kirchhoffuv zákon E fW = E eeE+(v) 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 preuděrjpfproti směru hrany. 9/51 Toky v síti FAKULTA INFORMATIKY Masarykova univerzita 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ýlevko, 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. PB165 - Grafy a sítě • 5.12.2019 10/51 Toky v síti FAKULTA INFORMATIKY I Masarykova univerzita Přípustný tok Zpravidla omezujeme tok na hraně shora i zdoLa,tj. platí f{e) g (/(e), c{e)). ČísLo c(e) nazýváme kapacitou hrany, případně v horním omezením toku v hraně. CísLo /(e) nazýváme dolním omezením toku v hraně. Tok, který splňuje l{e) l{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 Lz&tak- m^&jf&iýmmstě změnit. 22 / 51 Algoritmy pro maximální tok FAKULTA INFORMATIKY Masarykova univerzita Ford-Fulkersonův algoritmus ■ Využívá ekvivalence mezi maximaLitou toku a neexistencí cesty ze zdroje ke spotřebiči v reziduálni síti. ■ H Leda 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(é) bere tok, který hranou protéká ve směru její orientace - tedy/(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. . PB165 - Grafy a sítě • 5.12.2019 23 / 51 Algoritmy pro maximální tok FAKULTA INFORMATIKY I Masarykova univerzita Hledání zlepšující cesty Můžeme použít značkovací proceduru {Py(e) je počáteční a Kv(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 Kv(e) nemá a současně platí /(e) < c(e), pak označkuj Kv(e). Vzad Existuje-Li hrana e taková, že Kv(e) má značku a Py{e) nemá a současně l{e) 0 eeW+(P) eeW-(P) PB165 - Grafy a sítě • 5.12.2019 34/51 Další problémy FAKULTA INFORMATIKY I Masarykova univerzita Algortimus pro přípustnou cirkulaci Vstupem je síť G s omezeními toku í,ca Libovolná (i nulová) cirkulace /.Výstupem je budí přípustná cirkulace/7 nebo řez se zápornou kapacitou. 1. Najdeme hranu h s nepřípustným tokem. Pokud taková hrana neexistuje, výpočet končí a dosavadní tok/7 je přípustný. 2. Je-Li f{h) < /(/?), pak z := Kv(h), s •= Py(h), v opačném případě (f{h)>c{h))z:=Pv{h),s:=Kv{h). 3. 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. 4. 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 . PB16Z pětffFSíkro5kil 2019 35/51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita Network Coding 5.12.2019 Network Coding • 5.12.2019 36/51 Network Coding FAKULTA INFORMATIKY I Masarykova univerzita 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, že zdroj dat je v T a přijímající v V. Definice platí pro: ■ unicast ■ broadcast ■ multicast Network Coding • 5.12.2019 37/51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita 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. 38/51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita Multicast Pro multicast pořád platí věta MaxFLow-MinCut. Problémem aLe je, že neexistuje efektivní algoritmus pro hledání maximální propustnosti. =4> neumíme prakticky realizovat maximální tok (kromě brute-force způsobu). Network Coding • 5.12.2019 39/51 Network Coding FAKULTA INFORMATIKY I Masarykova univerzita Multicast 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 budí a nebo b. ■ V obou případech bude přicházející tok v jednom z koncových uzLů pouze 1. . NlwŕrňBL&Pi.'é.-zyiyzeL W symbol a, uzeL Tt obdrží dvakrát a (tok 4C Network Coding FAKULTA INFORMATIKY Masarykova univerzita 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 W může tuto správu poslat v jednom kroku. ■ UzeL 7i obdrží a a taky a + b. Z toho jednoduše určí b jako b = (a + b) - a. . N*wQibs|<0»to n š • f? r*s> i@ z e l T2 41 /51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita Kódovací schéma 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. . Network Coding • 5.12.2019 42/51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita 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) Network Coding • 5.12.2019 43/51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita 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é Network Coding • 5.12.2019 44/51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita Dynamické sítě 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í propustnosti pomocí kódování potřebná. Network Coding • 5.12.2019 45/51 Network Coding FAKULTA INFORMATIKY I Masarykova univerzita 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) ■ 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 Network Coding • 5.12.2019 46/51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita Kontrolní otázka Jaký počet Lineárních kombinací je dostatečný? Network Coding • 5.12.2019 47/51 Network Coding FAKULTA INFORMATIKY I Masarykova univerzita Kontrolní otázka 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). Network Coding • 5.12.2019 47/51 Network Coding FAKULTA INFORMATIKY Masarykova univerzita 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ří bud aX + bY nebo cX + dY. Network Coding • 5.12.2019 Network Coding FAKULTA INFORMATIKY Masarykova univerzita 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 Network Coding • 5.12.2019 49/51 Network Coding FAKULTA INFORMATIKY I Masarykova univerzita 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í Network Coding • 5.12.2019 Network Coding FAKULTA INFORMATIKY I Masarykova univerzita Literatura [1] R. AhLswede, S.-YR. Li, and R.W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4)1204-1216, July 2000. [2] 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. [3] S.-Y.R.Li and R.W. Yeung. Linear network coding. IEEE Transactions on Information Theory, 49(2):371-381, February 2003. Network Coding • 5.12.2019 51/51