Úvod Motivace Dosahování maximální propustnosti Aplikace Koncept Network Coding a jeho aplikace 8. prosince 2013 1 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Obsah prezentace Sítě, prospustnost (toky), multicast Co je to Network Coding? Jak ho můžeme využít? 2 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Propustnost Pro naše účely definujeme síť jako orientovaný acyklický graf G = (V , E) s hranovým ohodnocením (kapacity linek). Propustnost sítě kolik dat „protlačíme sítí za určitý čas závisí na kapacitě linek a na konkrétní topologii Řez v grafu je rozdělení množiny vrcholů na dvě neprázdné podmnožiny T a T . Kapacita řezu je součet kapacit hran vedoucích „mezi množinami T a T . 3 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Propustnost – definice 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 4 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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. 5 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Multicast Pro multicast pořád platí věta MaxFlow-MinCut. Problémem ale je, že neexistuje efektivní algoritmus pro hledání maximální propustnosti. ⇒ neumíme prakticky realizovat maximální tok (kromě brute-force způsobu). 6 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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 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 T1 obdrží dvakrát a (tok velikosti 1), a uzel T2 obdrží a i b (tok 2). 7 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Kódování Situace se ale změní, povolíme-li uzlu W , 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 T1 obdrží a a taky a + b. Z toho jednoduše určí b jako b = (a + b) − a. Obdobně pro uzel T2 8 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Kódovací schema Kódovací schema určuje pro každý uzel, jak má být vstupní informace kódována. Existují efektivní algoritmy pro návrh kódovacího schematu v obecnejších grafech. Jednotlivým uzlům přirazujeme lokální kódovací funkci Globální kódovací funkce vyjádřují, jak je informace transformována při přechodu sítí, t.j., jak má přijemce 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řijemce musí řešit systém lineárních rovnic, kde neznámými jsou původní informace. 9 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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) 10 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Algoritmy II - praktické nevýhody kódovací schema musí být vytvořeno před přenosem pracují centralizovaně a na statických topologiích dojde-li ke změne topologie, musí se schema 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é . . . 11 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Dynamické sítě Pro reálné sítě je vhodnejší použít jiný přístup ⇒ 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á. 12 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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ěšne 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 13 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace Kontrolní otázka Jaký počet lineárních kombinací je dostatečný? 14 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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). 15 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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 . 16 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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 . . . Peer-to-peer sítě Poskytování obsahu velkému počtu uživatelů – systé Avalanche Live Streaming 17 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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í . . . 18 / 19 Úvod Motivace Dosahování maximální propustnosti Aplikace 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. 19 / 19