Линеарно кодирање мрежа

Линеарно кодирање мрежа је математичка техника која се може користити за побољшање пропусности, ефикасности и скалабилности мреже, као и отпорности на нападе и прислушкивања. Уместо једноставног преноса пакета информација, чворови мреже узимају неколико пакета и комбинују их заједно за пренос. Ово се може користити за постизање максималног могућег протока информација у мрежи. Линеарна кодирање мрежа је изумео професор Роберт Ли, претходно професор на Кинеском Универзитету у Хонг Конгу, а сада угледни професор на Универзитету за електронске науке и технологију Кине.^[1]

Математички је доказано да теорији линеарног кодирања је довољна да се постигне горња граница у проблемима дељења већем броју корисника са једним извором.^[2] Међутим, линеарно кодирање није довољно уопштено, чак и за општије верзије линеарности као што су сверливно кодирање и кодирање филтер-банке.^[3] Проналажење оптималних решења за кодирање општих мрежних проблема са произвољним захтевима остаје отворени проблем.

Кодирање и декодирање

У линеарном проблему кодирања мрежа, група чворова $P$ је укључена у пренос података из изворних чворова $S$ у $K$ низводне чворове. Сваки чвор генерише нове пакете који представљају линеарне комбинације раније примљених пакета, множењем са коефицијентима одабраним из ограниченог поља, обично величине $GF(2^{s})$ .

Сваки чвор, $p_{k}$ са улазним степеном $InDeg(p_{k})$ , генерише поруку $X_{k}$ из линеарне комбинације примљених порука $\{M_{i}\}_{i=1}^{S}$ према релацији:

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

где су вредности $g_{k}^{i}$ коефицијенти изабрани из $GF(2^{s})$ . Треба имати на уму да, пошто се операције израчунавају у коначном пољу, генерисана порука је исте дужине као и оригиналне поруке. Сваки чвор преусмерава израчунату вредност $X_{k}$ заједно са коефицијентима $g_{k}^{i}$ , који се користе у $k$ -том нивоу.

Низводни чворови примају ове кодиране поруке и прикупљају их у матрици. Оригиналне поруке могу се опоравити извођењем Гаусове елиминације на матрици.^[4] У еклон форми редова, декодирани пакети одговарају редовима облика $e_{i}=[0...010...0]$ .

Кратак историјат

Мрежа је представљена као усмерен граф ${\mathcal {G}}=(V,E,C)$ . $V$ је скуп чворова или вертикала, $E$ је скуп усмерених веза (или ивица), а $C$ даје капацитет сваке линије $E$ . Нека $T(s,t)$ буде максимални могући проток из чвора $s$ у чвору $t$ . Према теореми о максималном протоку при минималном броју мостова, $T(s,t)$ је горњу границу минималног капацитета свих мостова, што је збир капацитета ивица на мосту, између ова два чвора.

Карл Менгер је доказао да увек постоји скуп не директно спојених чворова који постижу горње границе у једноредном сценарију протока података, познату као теорема о максималном протоку при минималном броју мостова. Касније је предложен алгоритам Форд-Фулкерсон да пронађе такве стазе у полиномијалном времену. Затим је Едмондс доказао у раду "Не директно спојено гранање"(енгл. Edge-Disjoint Branchings) да је горњу границу емитовања могуће достићи, и предложио је алгоритам полиномске временске сложености.

Међутим, ситуација у истовременом преношењу ка више праваца (енгл. multicast) је компликованија, и заправо, таква горња граница се не може постићи коришћењем традиционалних идеја усмеравања. Алсведе са колегама је доказао да се то може постићи ако се додатни рачунарски задаци (долазни пакети комбинују у један или више одлазних пакета) могу учинити у средњим чворовима.^[5]

Пример мреже лептира

Мрежа лептира^[5] често се користи за илустрацију како линијско кодирање мрежа може да заобиђе рутирање (усмеривање). Два извора чворова (на врху слике) имају информације А и В које се морају пренијети на два одредишна чворова (на дну), од којих свако жели знати А и В. Свака ивица може имати само једну вредност ( можемо размишљати о ивици која се емитује бит у свакој јединици времена).

Ако је дозвољено само усмеравање, онда би централна веза могла да носи само А или В, али не и оба. Претпоставимо да шаљемо А кроз центар; онда би лево одредиште добило А двапут и уопће не зна В. Слање В представља сличан проблем за праву дестинацију. Кажемо да је рутирање недовољно јер ниједна схема рутирања не може истовремено пренети и А и В на обе дестинације.

Коришћењем једноставног кода, као што је приказано, А и В се могу пренијети на обе дестинације истовремено слањем суме симбола кроз центар - другим речима, кодирамо А и В користећи формулу "А + В". Лева одредница добија А и А + В и може израчунати В тако што одузима две вриједности. Слично томе, право одредиште ће примити В и А + В, а такође ће моћи да одреди и А и В.

Произвољно линеарно кодирање мрежа

Произвољно линеарно кодирање мрежа^[6] је једноставна, али снажна шема кодирања, која у програмима преноса емитовања омогућава блиску оптималну пропусност коришћењем децентрализованог алгоритма. Чворови шаљу случајне линеарне комбинације пакета које примају, са коефицијентима изабраним из поља Галоис. Ако је величина поља довољно велика, вероватноћа да ће пријемник (ци) добити линеарно независне комбинације (а самим тим и добити иновативне информације) тежи 1. Треба истаћи да, иако случајно линеарно кодирање мрежа има одличне перформансе протока, у случају да пријемник добија недовољан број пакета, мало је вероватно да могу повратити било који од првобитних пакета. Ово се може решити слањем додатних случајних линијских комбинација све док пријемник не добије одговарајући број пакета.

Проблеми

Кодирање линијског мрежа је и даље релативно нови предмет. На основу претходних студија, постоје три важна отворена питања везана за произвољно линеарно кодирање мрежа:

1. Велика компјутерска комплексност декодирања услед коришћења Гаус-Жордан-ове методе елиминације. 2. Префорсиран пренос због приписивања великих коефицијентних вектора на кодиране блокове 3. Линеарна зависност између вектора коефицијената који може смањити број иновативних кодираних блокова

Бежично кодирање мрежа

Природа емитовања бежичне мреже (у комбинацији са мрежном топологијом) одређује природу ометање сигнала. Истовремени преноси у бежичној мрежи обично даје као резултат губитак готово свих пакета (тј. судара или колизије, погледајте Вишеструки приступ са избегавањем колизије за бежичну мрежу). Због тога бежична мрежа захтева распоређивач (као део контроле приступа медијуму, енгл. MAC) како би се смањиле овакве сметње. Због тога, било који добитак од мрежног кодирања снажно утиче на основни планер и одступаће од предности виђених у жичаним мрежама. Надаље, бежичне везе су типично полудуплексне због хардверских ограничења; тј. чвор не може истовремено пренети и примити због недостатка довољне изолације између стаза, али има могућност да прими и да пренесе.

Иако је изворно мрежно кодирање предложено да се користи на мрежном слоју (погледајте модел отвореног система међуповезаности, енгл OSI model), у бежичним мрежама, мрежно кодирање се широко користи у MAC слоју или физичком слоју (енгл. PHY layer).^[7] Показано је да мрежно кодирање када се користи у мрежама за бежичну мрежу захтева пажљив дизајн и размишљање како би се искористиле предности мешања пакета, у супротном се не могу остварити предности. Постоје и различити фактори који утичу на перформансе пропуштања, као што су протокол за приступ медијима, алгоритми за контролу загушења итд. Није евидентно како мрежно кодирање може истовремено постојати а да не угрожава постојеће алгоритме за загушење и контролу тока за наш Интернет.^[8]

Примена

Пошто је линеарно кодирање мреже релативно нова тема, његово усвајање у индустрији је још увек у току. За разлику од других кодирања, линеарно кодирање није у потпуности применљиво у систему због свог уског специфичног сценарија коришћења. Теоретичари покушавају да се повежу са применама из стварног света.^[9] У ствари, откривено је да је BitTorrent приступ далеко напреднији од мрежног кодирања.

Предвиђено је да мрежно кодирање буде корисно у следећим областима:

Алтернатива за исправку прослеђивања грешака (енгл. forward error correction) и аутоматски захтев за понављање (енгл. ARQ) у традиционалним и бежичним мрежама са губитком пакета. Нпр .: Кодирани TCP (енгл. Coded TCP),^[10] Више кориснички ARQ (енгл. Multi-user ARQ)^[11] Робустан и отпоран на мрежне нападе као што су разне методе прислушкивање, понављање или корупцију података.^[12]^[13] Дистрибуција дигиталних фајлова и дељење датотека P2P. нпр .: Аваленч из мајкрософта Дистрибуирано складиштење.^[14]^[15] Повећање протока у бежичној мрежној мрежи. на пример. : COPE,^[16] CORE,^[17] рутирање свесно кодирања,^[18]^[19] B.A.T.M.A.N.^[20] Смањење баферовања и одлагања у мрежама просторних сензора: просторно мултиплексирање бафера ^[21] Смањивање броја поновног слања пакета за бежична multicast преношење користећи један рутер, а самим тим и побољшати мрежну пропусност.^[22] Дистрибуирано дељење датотека^[23] Приказивање видео клипова са ниском сложеношћу на мобилне уређаје^[24]

Развој и проблеми

Пошто је ово подручје релативно ново и математички третман овог предмета је тренутно ограничен на неколико истраживача, мрежно кодирање још није нашло пут до комерцијализације производа и услуга. У овој фази је нејасно да ли ће ова тема превладати или престати као добра математичка вежба.^[25]

Истраживачи су јасно истакли да је потребна посебна брига како би се истражило како мрежно кодирање може истовремено постојати са постојећим рутирањем, приступом медијима, загушењима, алгоритмима за контролу протока и TCP протоколом. Мада, мрежно кодирање можда не нуди много предности и може повећати сложеност рачунања и захтеве меморије.^[26]

Види још

Референце

^ „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. (август 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.
^ Chou, Philip A.; Wu, Yunnan; Jain, Kamal (октобар 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”
^ ^а ^б 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. стр. 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). Архивирано из оригинала (PDF) 8. 11. 2007. г. Приступљено 16. 6. 2007.
^ http://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf^{[мртва веза]}
^ Welcome to Network Coding Security - Secure Network Coding
^ „Архивирана копија” (PDF). Архивирано из оригинала (PDF) 19. 9. 2013. г. Приступљено 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). стр. 1—6. ISBN 978-1-4673-6337-2. S2CID 1319567. doi:10.1109/VTCSpring.2013.6692495.
^ „Archived copy” (PDF). Архивирано из оригинала (PDF) 11. 10. 2008. г. Приступљено 10. 5. 2007.
^ http://www.cs.wisc.edu/~shravan/infocom-07-2.pdf
^ „NetworkCoding - batman-adv - Open Mesh”. www.open-mesh.org. Приступљено 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).

Литература

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.

Спољашње везе

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 Архивирано на сајту Wayback Machine (16. април 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/^{[мртва веза]}
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. (август 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.

[Allerton-4] Chou, Philip A.; Wu, Yunnan; Jain, Kamal (октобар 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. стр. 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). Архивирано из оригинала (PDF) 8. 11. 2007. г. Приступљено 16. 6. 2007.

[snc-12] ttp://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf^{[мртва веза]}

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

[aceanski-14] „Архивирана копија” (PDF). Архивирано из оригинала (PDF) 19. 9. 2013. г. Приступљено 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). стр. 1—6. ISBN 978-1-4673-6337-2. S2CID 1319567. doi:10.1109/VTCSpring.2013.6692495.

[rocx-18] „Archived copy” (PDF). Архивирано из оригинала (PDF) 11. 10. 2008. г. Приступљено 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. Приступљено 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]