Linear network coding: Difference between revisions

Revision as of 12:15, 6 June 2022

Revision as of 12:24, 6 June 2022

Line 64:

[[File:LinDependenciesbinaryvsg.png|thumb|445x445px|The expected number of linearly dependent packets per generation is practically independent of the generation size.]]

'''Overhead due to linear dependencies:''' Since the coding coefficients are chosen randomly in RLNC, there is a chance that some transmitted coded packets are not beneficial to the destination because they are formed using a linearly dependent combination of packets. However, this overhead is negligible in most applications. The linear dependencies depend on the Galois fields' size and are practically independent of the generation size used. We can illustrate this with the following example. Let us assume we are using a Galois field of <math>q</math> elements and a generation size of <math>M</math> packets. If the destination has not received any coded packet, we say it has <math>M</math> degrees of freedom, and then almost any coded packet will be useful and innovative. In fact, only the zero-packet (only zeroes in the coding coefficients) will be non-innovative. The probability of generating the zero-packet is equal to the probability of each of the <math>M</math> coding coefficient to be equal to the zero-element of the Galois field. I.e., the probability of a non-innovative packet is of <math>\frac{1}{q^M}</math>. With each successive innovative transmission, it can be shown that the exponent of the probability of a non innovative packet is reduced by one. When the destination has received <math>M-1</math> innovative packets (i.e., it needs only one more packet to fully decode the data). Then the probability of a non innovative packet is of <math>\frac{1}{q}</math>. We can use this knowledge to calculate the expected number of linearly dependent packets per generation. In the worst-case scenario, when the Galois field used contains only two elements (<math>q=2</math>), the expected number of linearly dependent packets per generation is of 1.6 extra packets. If our generation size if of 32 or 64 packets, this represents an overhead of 5% or 2.5%, respectively. If we use the binary-8 field (<math>q=256</math>), then the expected number of linearly dependent packets per generation is practically zero. Since it is the last packets the major contributor to the overhead due to linear dependencies, there are RLNC-based protocols such as tunable sparse network coding<ref>{{Cite journal |last1=Feizi |first1=Soheil |last2=Lucani |first2=Daniel E. |last3=Sørensen |first3=Chres W. |last4=Makhdoumi |first4=Ali |last5=Médard |first5=Muriel |date=June 2014 |title=Tunable sparse network coding for multicast networks |url=https://ieeexplore.ieee.org/abstract/document/6892129?casa_token=HHkBzpJJy_8AAAAA:i53eO7ijvK0fse-P-g6Yh7uwW08AUhHFvf41zcmppRJRs7FdwpJccGcHFsvb8xyBwxNpchACag |journal=2014 International Symposium on Network Coding (NetCod) |pages=1–6 |doi=10.1109/NETCOD.2014.6892129|isbn=978-1-4799-6217-4 |s2cid=18256950 }}</ref> that exploit this knowledge. These protocols introduce sparsity (zero-elements) in the coding coefficients at the beginning of the transmission to reduce the decoding complexity, and reduce the sparsity at the end of the transmission to reduce the overhead due to linear dependencies.

== Wireless network coding ==

The broadcast nature of wireless (coupled with network topology) determines the nature of [[Interference (communication)|interference]]. Simultaneous transmissions in a wireless network typically result in all of the packets being lost (i.e., collision, see [[Multiple Access with Collision Avoidance for Wireless]]). A wireless network therefore requires a scheduler (as part of the [[Media access control|MAC]] functionality) to minimize such interference. Hence any gains from network coding are strongly impacted by the underlying scheduler and will deviate from the gains seen in wired networks. Further, wireless links are typically half-duplex due to hardware constraints; i.e., a node can not simultaneously transmit and receive due to the lack of sufficient isolation between the two paths.

Although, originally network coding was proposed to be used at Network layer (see [[OSI model]]), in wireless networks, network coding has been widely used in either MAC layer or [[Physical layer|PHY]] layer.<ref name="firooz2013">M.H.Firooz, Z. Chen, S. Roy and H. Liu, ([https://arxiv.org/abs/1210.1326 Wireless Network Coding via Modified 802.11 MAC/PHY: Design and Implementation on SDR]) in IEEE Journal on Selected Areas in Communications, 2013.</ref> It has been shown that network coding when used in wireless mesh networks need attentive design and thoughts to exploit the advantages of packet mixing, else advantages cannot be realized. There are also a variety of factors influencing throughput performance, such as media access layer protocol, congestion control algorithms, etc. It is not evident how network coding can co-exist and not jeopardize what existing congestion and flow control algorithms are doing for our Internet.<ref name=":0">{{Cite journal |last1=Katti |first1=Sachin |last2=Rahul |first2=Hariharan |last3=Hu |first3=Wenjun |last4=Katabi |first4=Dina |last5=Médard |first5=Muriel |last6=Crowcroft |first6=Jon |date=2006-08-11 |title=XORs in the air: practical wireless network coding |url=http://nms.csail.mit.edu/~sachin/papers/copesc.pdf |journal=Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications |series=SIGCOMM '06 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=243–254 |doi=10.1145/1159913.1159942 |isbn=978-1-59593-308-9|s2cid=207160426 }}</ref>

== Applications ==

Line 97 ⟶ 92:

* Digital file distribution and P2P file sharing, e.g. [[Avalanche filesystem]] from Microsoft

* Distributed storage<ref name="Bilal, Muhammad 2019 1376–1385" /><ref>{{Cite web |last1=Acedański |first1=Szymon |last2=Deb |first2=Supratim |last3=Médard |first3=Muriel |last4=Koetter |first4=Ralf |title=How Good is Random Linear Coding Based Distributed Networked Storage? |url=http://web.mit.edu/~medard/www/page2/mpapers/netcod2005_accek.pdf |url-status=live |access-date=26 March 2022 |website=web.mit.edu}}</ref><ref>{{Cite arXiv |eprint = cs/0702015|last1 = Dimakis|first1 = Alexandros|title = Network Coding for Distributed Storage Systems|year = 2007}}</ref>

* Throughput increase in wireless mesh networks, e.g.: [[COPE (network coding)|COPE]],<ref name=":0">{{Cite journal |last1=Katti |first1=Sachin |last2=Rahul |first2=Hariharan |last3=Hu |first3=Wenjun |last4=Katabi |first4=Dina |last5=Médard |first5=Muriel |last6=Crowcroft |first6=Jon |date=2006-08-11 |title=XORs in the air: practical wireless network coding |url=http://nms.csail.mit.edu/~sachin/papers/copesc.pdf |journal=Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications |series=SIGCOMM '06 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=243–254 |doi=10.1145/1159913.1159942 |isbn=978-1-59593-308-9 |s2cid=207160426}}</ref> [[CORE (network coding)|CORE]],<ref>{{cite book | doi = 10.1109/VTCSpring.2013.6692495 | title=CORE: COPE with MORE in Wireless Meshed Networks | journal=2013 IEEE 77th Vehicular Technology Conference (VTC Spring)| pages=1–6 | year=2013 | last1=Krigslund | first1=Jeppe | last2=Hansen | first2=Jonas | last3=Hundeboll | first3=Martin | last4=Lucani | first4=Daniel E. | last5=Fitzek | first5=Frank H. P. | isbn=978-1-4673-6337-2 | s2cid=1319567 }}</ref> [[Coding-aware routing]],<ref>{{Cite journal |last1=Sengupta |first1=S. |last2=Rayanchu |first2=S. |last3=Banerjee |first3=S. |date=May 2007 |title=An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing |url=https://ieeexplore.ieee.org/document/4215706 |journal=IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications |pages=1028–1036 |doi=10.1109/INFCOM.2007.124|isbn=978-1-4244-1047-7 |s2cid=3056111 }}</ref> and [[B.A.T.M.A.N.]]<ref>{{Cite web |title=NetworkCoding - batman-adv - Open Mesh |url=http://www.open-mesh.org/projects/batman-adv/wiki/NetworkCoding |url-status=live |archive-url=https://web.archive.org/web/20210512133041/https://www.open-mesh.org/projects/batman-adv/wiki/NetworkCoding |archive-date=12 May 2021 |website=www.open-mesh.org |accessdate=2015-10-28}}</ref>

* Buffer and delay reduction in spatial sensor networks: [[Spatial buffer multiplexing]]<ref>{{Cite journal |last1=Bhadra |first1=S. |last2=Shakkottai |first2=S. |date=April 2006 |title=Looking at Large Networks: Coding vs. Queueing |url=https://ieeexplore.ieee.org/document/4146919/;jsessionid=Vf_H7NM8pJZkcL5tUwrvGHQd45FXGbWGEGG9OyMg__IVxRlWxF8t!-1723551334 |journal=Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications |pages=1–12 |doi=10.1109/INFOCOM.2006.266|isbn=1-4244-0221-2 |s2cid=730706 }}</ref>

* Wireless broadcast<ref name=":11" />: RLNC can reduce the number of packet transmission for a single-hop wireless multicast network, and hence improve network bandwidth<ref name=":11">{{Cite journal | doi=10.1109/TVT.2008.927729| title=Wireless Broadcast Using Network Coding| journal=IEEE Transactions on Vehicular Technology| volume=58| issue=2| pages=914–925| year=2009| last1=Dong Nguyen| last2=Tuan Tran| last3=Thinh Nguyen| last4=Bose| first4=B.|citeseerx = 10.1.1.321.1962| s2cid=16989586}}</ref>