Linearno kodiranje mreža

Linearno kodiranje mreža je matematička tehnika koja se može koristiti za poboljšanje propusnosti, efikasnosti i skalabilnosti mreže, kao i otpornosti na napade i prisluškivanja. Umesto jednostavnog prenosa paketa informacija, čvorovi mreže uzimaju nekoliko paketa i kombinuju ih zajedno za prenos. Ovo se može koristiti za postizanje maksimalnog mogućeg protoka informacija u mreži. Linearna kodiranje mreža je izumeo profesor Robert Li, prethodno profesor na Kineskom Univerzitetu u Hong Kongu, a sada ugledni profesor na Univerzitetu za elektronske nauke i tehnologiju Kine.^[1]

Matematički je dokazano da teoriji linearnog kodiranja je dovoljna da se postigne gornja granica u problemima deljenja većem broju korisnika sa jednim izvorom.^[2] Međutim, linearno kodiranje nije dovoljno uopšteno, čak i za opštije verzije linearnosti kao što su sverlivno kodiranje i kodiranje filter-banke.^[3] Pronalaženje optimalnih rešenja za kodiranje opštih mrežnih problema sa proizvoljnim zahtevima ostaje otvoreni problem.

Kodiranje i dekodiranje

U linearnom problemu kodiranja mreža, grupa čvorova $P$ je uključena u prenos podataka iz izvornih čvorova $S$ u $K$ nizvodne čvorove. Svaki čvor generiše nove pakete koji predstavljaju linearne kombinacije ranije primljenih paketa, množenjem sa koeficijentima odabranim iz ograničenog polja, obično veličine $GF(2^{s})$ .

Svaki čvor, $p_{k}$ sa ulaznim stepenom $InDeg(p_{k})$ , generiše poruku $X_{k}$ iz linearne kombinacije primljenih poruka $\{M_{i}\}_{i=1}^{S}$ prema relaciji:

X_{k}=\sum _{i=1}^{S}g_{k}^{i}\cdot M_{i}

gde su vrednosti $g_{k}^{i}$ koeficijenti izabrani iz $GF(2^{s})$ . Treba imati na umu da, pošto se operacije izračunavaju u konačnom polju, generisana poruka je iste dužine kao i originalne poruke. Svaki čvor preusmerava izračunatu vrednost $X_{k}$ zajedno sa koeficijentima $g_{k}^{i}$ , koji se koriste u $k$ -tom nivou.

Nizvodni čvorovi primaju ove kodirane poruke i prikupljaju ih u matrici. Originalne poruke mogu se oporaviti izvođenjem Gausove eliminacije na matrici.^[4] U eklon formi redova, dekodirani paketi odgovaraju redovima oblika $e_{i}=[0...010...0]$ .

Kratak istorijat

Mreža je predstavljena kao usmeren graf ${\mathcal {G}}=(V,E,C)$ . $V$ je skup čvorova ili vertikala, $E$ je skup usmerenih veza (ili ivica), a $C$ daje kapacitet svake linije $E$ . Neka $T(s,t)$ bude maksimalni mogući protok iz čvora $s$ u čvoru $t$ . Prema teoremi o maksimalnom protoku pri minimalnom broju mostova, $T(s,t)$ je gornju granicu minimalnog kapaciteta svih mostova, što je zbir kapaciteta ivica na mostu, između ova dva čvora.

Karl Menger je dokazao da uvek postoji skup ne direktno spojenih čvorova koji postižu gornje granice u jednorednom scenariju protoka podataka, poznatu kao teorema o maksimalnom protoku pri minimalnom broju mostova. Kasnije je predložen algoritam Ford-Fulkerson da pronađe takve staze u polinomijalnom vremenu. Zatim je Edmonds dokazao u radu "Ne direktno spojeno grananje"(engl. Edge-Disjoint Branchings) da je gornju granicu emitovanja moguće dostići, i predložio je algoritam polinomske vremenske složenosti.

Međutim, situacija u istovremenom prenošenju ka više pravaca (engl. multicast) je komplikovanija, i zapravo, takva gornja granica se ne može postići korišćenjem tradicionalnih ideja usmeravanja. Alsvede sa kolegama je dokazao da se to može postići ako se dodatni računarski zadaci (dolazni paketi kombinuju u jedan ili više odlaznih paketa) mogu učiniti u srednjim čvorovima.^[5]

Primer mreže leptira

Mreža leptira^[5] često se koristi za ilustraciju kako linijsko kodiranje mreža može da zaobiđe rutiranje (usmerivanje). Dva izvora čvorova (na vrhu slike) imaju informacije A i V koje se moraju prenijeti na dva odredišna čvorova (na dnu), od kojih svako želi znati A i V. Svaka ivica može imati samo jednu vrednost ( možemo razmišljati o ivici koja se emituje bit u svakoj jedinici vremena).

Ako je dozvoljeno samo usmeravanje, onda bi centralna veza mogla da nosi samo A ili V, ali ne i oba. Pretpostavimo da šaljemo A kroz centar; onda bi levo odredište dobilo A dvaput i uopće ne zna V. Slanje V predstavlja sličan problem za pravu destinaciju. Kažemo da je rutiranje nedovoljno jer nijedna shema rutiranja ne može istovremeno preneti i A i V na obe destinacije.

Korišćenjem jednostavnog koda, kao što je prikazano, A i V se mogu prenijeti na obe destinacije istovremeno slanjem sume simbola kroz centar - drugim rečima, kodiramo A i V koristeći formulu "A + V". Leva odrednica dobija A i A + V i može izračunati V tako što oduzima dve vrijednosti. Slično tome, pravo odredište će primiti V i A + V, a takođe će moći da odredi i A i V.

Proizvoljno linearno kodiranje mreža

Proizvoljno linearno kodiranje mreža^[6] je jednostavna, ali snažna šema kodiranja, koja u programima prenosa emitovanja omogućava blisku optimalnu propusnost korišćenjem decentralizovanog algoritma. Čvorovi šalju slučajne linearne kombinacije paketa koje primaju, sa koeficijentima izabranim iz polja Galois. Ako je veličina polja dovoljno velika, verovatnoća da će prijemnik (ci) dobiti linearno nezavisne kombinacije (a samim tim i dobiti inovativne informacije) teži 1. Treba istaći da, iako slučajno linearno kodiranje mreža ima odlične performanse protoka, u slučaju da prijemnik dobija nedovoljan broj paketa, malo je verovatno da mogu povratiti bilo koji od prvobitnih paketa. Ovo se može rešiti slanjem dodatnih slučajnih linijskih kombinacija sve dok prijemnik ne dobije odgovarajući broj paketa.

Problemi

Kodiranje linijskog mreža je i dalje relativno novi predmet. Na osnovu prethodnih studija, postoje tri važna otvorena pitanja vezana za proizvoljno linearno kodiranje mreža:

1. Velika kompjuterska kompleksnost dekodiranja usled korišćenja Gaus-Žordan-ove metode eliminacije. 2. Preforsiran prenos zbog pripisivanja velikih koeficijentnih vektora na kodirane blokove 3. Linearna zavisnost između vektora koeficijenata koji može smanjiti broj inovativnih kodiranih blokova

Bežično kodiranje mreža

Priroda emitovanja bežične mreže (u kombinaciji sa mrežnom topologijom) određuje prirodu ometanje signala. Istovremeni prenosi u bežičnoj mreži obično daje kao rezultat gubitak gotovo svih paketa (tj. sudara ili kolizije, pogledajte Višestruki pristup sa izbegavanjem kolizije za bežičnu mrežu). Zbog toga bežična mreža zahteva raspoređivač (kao deo kontrole pristupa medijumu, engl. MAC) kako bi se smanjile ovakve smetnje. Zbog toga, bilo koji dobitak od mrežnog kodiranja snažno utiče na osnovni planer i odstupaće od prednosti viđenih u žičanim mrežama. Nadalje, bežične veze su tipično poludupleksne zbog hardverskih ograničenja; tj. čvor ne može istovremeno preneti i primiti zbog nedostatka dovoljne izolacije između staza, ali ima mogućnost da primi i da prenese.

Iako je izvorno mrežno kodiranje predloženo da se koristi na mrežnom sloju (pogledajte model otvorenog sistema međupovezanosti, engl OSI model), u bežičnim mrežama, mrežno kodiranje se široko koristi u MAC sloju ili fizičkom sloju (engl. PHY layer).^[7] Pokazano je da mrežno kodiranje kada se koristi u mrežama za bežičnu mrežu zahteva pažljiv dizajn i razmišljanje kako bi se iskoristile prednosti mešanja paketa, u suprotnom se ne mogu ostvariti prednosti. Postoje i različiti faktori koji utiču na performanse propuštanja, kao što su protokol za pristup medijima, algoritmi za kontrolu zagušenja itd. Nije evidentno kako mrežno kodiranje može istovremeno postojati a da ne ugrožava postojeće algoritme za zagušenje i kontrolu toka za naš Internet.^[8]

Primena

Pošto je linearno kodiranje mreže relativno nova tema, njegovo usvajanje u industriji je još uvek u toku. Za razliku od drugih kodiranja, linearno kodiranje nije u potpunosti primenljivo u sistemu zbog svog uskog specifičnog scenarija korišćenja. Teoretičari pokušavaju da se povežu sa primenama iz stvarnog sveta.^[9] U stvari, otkriveno je da je BitTorrent pristup daleko napredniji od mrežnog kodiranja.

Predviđeno je da mrežno kodiranje bude korisno u sledećim oblastima:

Alternativa za ispravku prosleđivanja grešaka (engl. forward error correction) i automatski zahtev za ponavljanje (engl. ARQ) u tradicionalnim i bežičnim mrežama sa gubitkom paketa. Npr .: Kodirani TCP (engl. Coded TCP),^[10] Više korisnički ARQ (engl. Multi-user ARQ)^[11] Robustan i otporan na mrežne napade kao što su razne metode prisluškivanje, ponavljanje ili korupciju podataka.^[12]^[13] Distribucija digitalnih fajlova i deljenje datoteka P2P. npr .: Avalenč iz majkrosofta Distribuirano skladištenje.^[14]^[15] Povećanje protoka u bežičnoj mrežnoj mreži. na primer. : COPE,^[16] CORE,^[17] rutiranje svesno kodiranja,^[18]^[19] B.A.T.M.A.N.^[20] Smanjenje baferovanja i odlaganja u mrežama prostornih senzora: prostorno multipleksiranje bafera ^[21] Smanjivanje broja ponovnog slanja paketa za bežična multicast prenošenje koristeći jedan ruter, a samim tim i poboljšati mrežnu propusnost.^[22] Distribuirano deljenje datoteka^[23] Prikazivanje video klipova sa niskom složenošću na mobilne uređaje^[24]

Razvoj i problemi

Pošto je ovo područje relativno novo i matematički tretman ovog predmeta je trenutno ograničen na nekoliko istraživača, mrežno kodiranje još nije našlo put do komercijalizacije proizvoda i usluga. U ovoj fazi je nejasno da li će ova tema prevladati ili prestati kao dobra matematička vežba.^[25]

Istraživači su jasno istakli da je potrebna posebna briga kako bi se istražilo kako mrežno kodiranje može istovremeno postojati sa postojećim rutiranjem, pristupom medijima, zagušenjima, algoritmima za kontrolu protoka i TCP protokolom. Mada, mrežno kodiranje možda ne nudi mnogo prednosti i može povećati složenost računanja i zahteve memorije.^[26]

Vidi još

Reference

^ „Bio of Prof. Robert Li”.
^ Li, S.-Y.R.; Yeung, R.W.; Ning Cai (2003). „Linear network coding”. IEEE Transactions on Information Theory. 49 (2): 371—381. doi:10.1109/TIT.2002.807285.
^ Dougherty, R.; Freiling, C.; Zeger, K. (avgust 2005). „Insufficiency of Linear Coding in Network Information Flow” (PDF). IEEE Transactions on Information Theory. 51 (8): 2745—2759. S2CID 2543400. doi:10.1109/TIT.2005.851744. CS1 održavanje: Format datuma (veza)
^ Chou, Philip A.; Wu, Yunnan; Jain, Kamal (oktobar 2003), „Practical network coding”, Allerton Conference on Communication, Control, and Computing, „Any receiver can then recover the source vectors using Gaussian elimination on the vectors in its h (or more) received packets”
^ ^a ^b Ahlswede, Rudolf; Cai, N.; Shuo-Yen Robert Li; Raymond Wai-Ho Yeung (2000). „Network Information Flow”. IEEE Transactions on Information Theory, IT-46. 46 (4): 1204—1216. doi:10.1109/18.850663.
^ Ho, T.; Koetter, R.; Medard, M.; Karger, D.R.; Effros, M. (2003). „The benefits of coding over routing in a randomized setting”. IEEE International Symposium on Information Theory, 2003. Proceedings. str. 442. ISBN 0-7803-7728-1. S2CID 1903754. doi:10.1109/ISIT.2003.1228459.
^ Firooz, M. H.; Zhiyong Chen, Zhiyong; Roy, S.; Hui Liu, Hui (2013). „Wireless Network Coding via Modified 802.11 MAC/PHY: Design and Implementation on SDR”. IEEE Journal on Selected Areas in Communications. 31 (8): 1618—1628. S2CID 1408561. arXiv:1210.1326 . doi:10.1109/JSAC.2013.130823.
^ XORs in The Air: Practical Wireless Network Coding
^ „How Practical is Network Coding? by Mea Wang, Baochun Li”. CiteSeerX 10.1.1.77.6402 .
^ Kim, MinJi; Cloud, Jason; ParandehGheibi, Ali; Urbina, Leonardo; Fouli, Kerim; Leith, Douglas; Medard, Muriel (2012). „Network Coded TCP (CTCP)”. arXiv:1212.2291 .
^ „Archived copy” (PDF). Arhivirano iz originala (PDF) 8. 11. 2007. g. Pristupljeno 16. 6. 2007.
^ http://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf^{[mrtva veza]}
^ Welcome to Network Coding Security - Secure Network Coding
^ „Arhivirana kopija” (PDF). Arhivirano iz originala (PDF) 19. 9. 2013. g. Pristupljeno 5. 2. 2018.
^ Dimakis, Alexandros G.; Brighten Godfrey, P.; Wainwright, Martin J.; Ramchandran, Kannan (2007). „Network Coding for Distributed Storage Systems”. arXiv:cs/0702015 .
^ http://people.csail.mit.edu/rahul/papers/cope-ton2008.pdf
^ Krigslund, Jeppe; Hansen, Jonas; Hundeboll, Martin; Lucani, Daniel E.; Fitzek, Frank H. P. (2013). „CORE: COPE with MORE in Wireless Meshed Networks”. 2013 IEEE 77th Vehicular Technology Conference (VTC Spring). str. 1—6. ISBN 978-1-4673-6337-2. S2CID 1319567. doi:10.1109/VTCSpring.2013.6692495.
^ „Archived copy” (PDF). Arhivirano iz originala (PDF) 11. 10. 2008. g. Pristupljeno 10. 5. 2007.
^ http://www.cs.wisc.edu/~shravan/infocom-07-2.pdf
^ „NetworkCoding - batman-adv - Open Mesh”. www.open-mesh.org. Pristupljeno 28. 10. 2015.
^ Welcome to IEEE Xplore 2.0: Looking at Large Networks: Coding vs. Queueing
^ Wireless Broadcast Using Network Coding - IEEE Journals & Magazine
^ Firooz, Mohammad Hamed; Roy, Sumit (2013). „Data Dissemination in Wireless Networks with Network Coding”. IEEE Communications Letters. 17 (5): 944—947. S2CID 13576. arXiv:1203.5395 . doi:10.1109/LCOMM.2013.031313.121994.
^ Band Codes for Energy-Efficient Network Coding With Application to P2P Mobile Streaming
^ „How Practical is Network Coding?”. CiteSeerX 10.1.1.77.6402 .
^ „XORs in The Air” (PDF).

Literatura

Fragouli, C.; Le Boudec, J. & Widmer, J. "Network coding: An instant primer" in Computer Communication Review, 2006.
Ali Farzamnia, Sharifah K. Syed-Yusof, Norsheila Fisa "Multicasting Multiple Description Coding Using p-Cycle Network Coding", KSII Transactions on Internet and Information Systems, Vol 7, No 12, 2013.

Spoljašnje veze

Network Coding Homepage
A network coding bibliography
Raymond W. Yeung, Information Theory and Network Coding, Springer 2008, http://iest2.ie.cuhk.edu.hk/~whyeung/book2/
Raymond W. Yeung et al., Network Coding Theory, now Publishers, 2005, http://iest2.ie.cuhk.edu.hk/~whyeung/netcode/monograph.html
Christina Fragouli et al., Network Coding: An Instant Primer, ACM SIGCOMM 2006, http://infoscience.epfl.ch/getfile.py?mode=best&recid=58339 Arhivirano na sajtu Wayback Machine (16. april 2007).
Avalanche Filesystem, http://research.microsoft.com/en-us/projects/avalanche/default.aspx
Random Network Coding, https://web.archive.org/web/20060618083034/http://www.mit.edu/~medard/coding1.htm
Digital Fountain Codes, http://www.icsi.berkeley.edu/~luby/^{[mrtva veza]}
Coding-Aware Routing, https://web.archive.org/web/20081011124616/http://arena.cse.sc.edu/papers/rocx.secon06.pdf
MIT offers a course: Introduction to Network Coding
Network coding: Networking's next revolution?
Coding-aware protocol design for wireless networks: http://scholarcommons.sc.edu/etd/230/

[Li-Bio-1] „Bio of Prof. Robert Li”.

[Li-LNC-2] Li, S.-Y.R.; Yeung, R.W.; Ning Cai (2003). „Linear network coding”. IEEE Transactions on Information Theory. 49 (2): 371—381. doi:10.1109/TIT.2002.807285.

[Dougherty-3] Dougherty, R.; Freiling, C.; Zeger, K. (avgust 2005). „Insufficiency of Linear Coding in Network Information Flow” (PDF). IEEE Transactions on Information Theory. 51 (8): 2745—2759. S2CID 2543400. doi:10.1109/TIT.2005.851744. CS1 održavanje: Format datuma (veza)

[Allerton-4] Chou, Philip A.; Wu, Yunnan; Jain, Kamal (oktobar 2003), „Practical network coding”, Allerton Conference on Communication, Control, and Computing, „Any receiver can then recover the source vectors using Gaussian elimination on the vectors in its h (or more) received packets”

[Ahlswede2000-5] Ahlswede, Rudolf; Cai, N.; Shuo-Yen Robert Li; Raymond Wai-Ho Yeung (2000). „Network Information Flow”. IEEE Transactions on Information Theory, IT-46. 46 (4): 1204—1216. doi:10.1109/18.850663.

[Ho2003-6] Ho, T.; Koetter, R.; Medard, M.; Karger, D.R.; Effros, M. (2003). „The benefits of coding over routing in a randomized setting”. IEEE International Symposium on Information Theory, 2003. Proceedings. str. 442. ISBN 0-7803-7728-1. S2CID 1903754. doi:10.1109/ISIT.2003.1228459.

[firooz2013-7] Firooz, M. H.; Zhiyong Chen, Zhiyong; Roy, S.; Hui Liu, Hui (2013). „Wireless Network Coding via Modified 802.11 MAC/PHY: Design and Implementation on SDR”. IEEE Journal on Selected Areas in Communications. 31 (8): 1618—1628. S2CID 1408561. arXiv:1210.1326 . doi:10.1109/JSAC.2013.130823.

[sachin-8] XORs in The Air: Practical Wireless Network Coding

[wang-9] „How Practical is Network Coding? by Mea Wang, Baochun Li”. CiteSeerX 10.1.1.77.6402 .

[kimcloud-10] Kim, MinJi; Cloud, Jason; ParandehGheibi, Ali; Urbina, Leonardo; Fouli, Kerim; Leith, Douglas; Medard, Muriel (2012). „Network Coded TCP (CTCP)”. arXiv:1212.2291 .

[multi-user-11] „Archived copy” (PDF). Arhivirano iz originala (PDF) 8. 11. 2007. g. Pristupljeno 16. 6. 2007.

[snc-12] ttp://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf^{[mrtva veza]}

[zhenyu-13] Welcome to Network Coding Security - Secure Network Coding

[aceanski-14] „Arhivirana kopija” (PDF). Arhivirano iz originala (PDF) 19. 9. 2013. g. Pristupljeno 5. 2. 2018.

[dimakis-15] Dimakis, Alexandros G.; Brighten Godfrey, P.; Wainwright, Martin J.; Ramchandran, Kannan (2007). „Network Coding for Distributed Storage Systems”. arXiv:cs/0702015 .

[rahul-16] ttp://people.csail.mit.edu/rahul/papers/cope-ton2008.pdf

[cope-17] Krigslund, Jeppe; Hansen, Jonas; Hundeboll, Martin; Lucani, Daniel E.; Fitzek, Frank H. P. (2013). „CORE: COPE with MORE in Wireless Meshed Networks”. 2013 IEEE 77th Vehicular Technology Conference (VTC Spring). str. 1—6. ISBN 978-1-4673-6337-2. S2CID 1319567. doi:10.1109/VTCSpring.2013.6692495.

[rocx-18] „Archived copy” (PDF). Arhivirano iz originala (PDF) 11. 10. 2008. g. Pristupljeno 10. 5. 2007.

[shravan-19] ttp://www.cs.wisc.edu/~shravan/infocom-07-2.pdf

[batman-20] „NetworkCoding - batman-adv - Open Mesh”. www.open-mesh.org. Pristupljeno 28. 10. 2015.

[xplore1-21] Welcome to IEEE Xplore 2.0: Looking at Large Networks: Coding vs. Queueing

[xplore2-22] Wireless Broadcast Using Network Coding - IEEE Journals & Magazine

[datadissemination-23] Firooz, Mohammad Hamed; Roy, Sumit (2013). „Data Dissemination in Wireless Networks with Network Coding”. IEEE Communications Letters. 17 (5): 944—947. S2CID 13576. arXiv:1203.5395 . doi:10.1109/LCOMM.2013.031313.121994.

[p2p-24] Band Codes for Energy-Efficient Network Coding With Application to P2P Mobile Streaming

[practical-25] „How Practical is Network Coding?”. CiteSeerX 10.1.1.77.6402 .

[sachin2-26] „XORs in The Air” (PDF).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]