View source for Linear network coding

Network coding is a field of research founded in a series of papers from the late 1990s to the early 2000s. However, the concept of network coding, in particular '''linear network coding''', appeared much earlier. In a 1978 paper,<ref name="Celebiler&S1978">{{cite journal| first=M.| last= Celebiler|author2=G. Stette | title=On Increasing the Down-Link Capacity of a Regenerative Satellite Repeater in Point-to-Point Communications| journal=Proceedings of the IEEE| year= 1978| volume=66| issue=1| pages= 98–100| doi= 10.1109/PROC.1978.10848}}</ref> a scheme for improving the throughput of a two-way communication through a satellite was proposed. In this scheme, two users trying to communicate with each other transmit their data streams to a satellite, which combines the two streams by summing them modulo 2 and then broadcasts the combined stream. Each of the two users, upon receiving the broadcast stream, can decode the other stream by using the information of their own stream.

The 2000 paper <ref name="Ahlswede2000" /> gave the butterfly network example (discussed below) that illustrates how linear network coding can outperform routing. This example is equivalent to the scheme for satellite communication described above. The same paper gave an optimal coding scheme for a network with one source node and three destination nodes. This is the first example illustrating the optimality of convolutional network coding (a more general form of linear network coding) over a cyclic network.

Linear network coding may be used to improve a network's throughput, efficiency and [[scalability]], as well as resilience to attacks and eavesdropping. Instead of simply relaying the [[Packet (information technology)|packets]] of information they receive, the [[Node (networking)|nodes]] of a network take ''several'' packets and combine them together for transmission. This may be used to attain the maximum possible [[information]] [[flow network|flow]] in a [[Network theory|network]].

It has been mathematically proven in theory that [[linear code|linear coding]] is enough to achieve the upper bound in multicast problems with one source.<ref>S. Li, R. Yeung, and N. Cai, "Linear Network Coding"([http://pdos.lcs.mit.edu/decouto/papers/li03.pdf PDF]), in IEEE Transactions on Information Theory, Vol 49, No. 2, pp. 371–381, 2003</ref> However linear coding is not sufficient in general (e.g. multisource, multisink with arbitrary demands), even for more general versions of linearity such as [[convolutional coding]] and [[filter-bank coding]].<ref>R. Dougherty, [[Chris Freiling|C. Freiling]], and K. Zeger, "Insufficiency of Linear Coding in Network Information Flow" ([http://code.ucsd.edu/~zeger/publications/journals/DoFrZe05-IT-Insufficiency/DoFrZe05-IT-Insufficiency.pdf PDF]), in IEEE Transactions on Information Theory,  Vol. 51, No. 8, pp. 2745-2759, August 2005 ( [http://code.ucsd.edu/~zeger/publications/journals/DoFrZe05-IT-Insufficiency/DoFrZe05-IT-Insufficiency-erratum.pdf erratum])</ref> Finding optimal coding solutions for general network problems with arbitrary demands remains an open problem.

== Encoding and decoding ==
In a linear network coding problem, a group of nodes <math>P</math> are involved in moving the data from <math>S</math> source nodes to <math>K</math> sink nodes. Each node generates new packets which are linear combinations of earlier received packets, multiplying them by [[coefficient]]s chosen from a [[Galois field|finite field]], typically of size <math>GF(2^s)</math>.

Each node, <math>p_k</math> with [[Indegree#Indegree and outdegree|indegree]], <math>InDeg(p_k) = S</math>, generates a message <math>X_k</math> from the linear combination of received messages <math>\{M_i\}_{i = 1}^S</math> by the relation:
:<math>X_k = \sum_{i=1}^S g_k^i\cdot M_i</math>
where the values <math>g_k^i</math> are the coefficients selected from <math>GF(2^s)</math>. Note that, since operations are computed in a finite field, the generated message is of the same length as the original messages. Each node forwards the computed value <math>X_k</math> along with the coefficients, <math>g_k^i</math>, used in the <math>k^\text{th}</math> level, <math>g_k^i</math>.

Sink nodes receive these network coded messages, and collect them in a matrix. The original messages can be recovered by performing [[Gaussian elimination]] on the matrix.<ref>{{citation
 | last1 = Chou | first1 = Philip A.
 | last2 = Wu | first2 = Yunnan
 | last3 = Jain | first3 = Kamal
 | contribution = Practical network coding
 | date = October 2003
 | quote = Any receiver can then recover the source vectors using Gaussian elimination on the vectors in its ''h'' (or more) received packets
 | title = Allerton Conference on Communication, Control, and Computing}}.</ref> In reduced row echelon form, decoded packets correspond to the rows of the form <math>e_i=[0 ... 0 1 0 ... 0]</math>.

== A brief history ==
A network is represented by a [[directed graph]] <math>\mathcal{G}=(V, E, C)</math>. <math>V</math> is the set of nodes or vertices, <math>E</math> is the set of directed links (or edges), and <math>C</math> gives the capacity of each link of <math>E</math>. Let <math>T(s, t)</math> be the maximum possible throughput from node <math>s</math> to node <math>t</math>. By the [[max-flow min-cut theorem]], <math>T(s, t)</math> is upper bounded by the minimum capacity of all [[Cut (graph theory)|cuts]], which is the sum of the capacities of the edges on a cut, between these two nodes.

[[Karl Menger]] proved that there is always a set of edge-disjoint paths achieving the upper bound in a [[unicast]] scenario, known as the [[max-flow min-cut theorem]]. Later, the [[Ford–Fulkerson algorithm]] was proposed to find such paths in polynomial time. Then, Edmonds proved in the paper "Edge-Disjoint Branchings" the upper bound in the broadcast scenario is also achievable, and proposed a polynomial time algorithm.

However, the situation in the [[multicast]] scenario is more complicated, and in fact, such an upper bound can't be reached using traditional [[routing]] ideas. Ahlswede, et al. proved that it can be achieved if additional computing tasks (incoming packets are combined into one or several outgoing packets) can be done in the intermediate nodes.<ref name="Ahlswede2000">{{cite journal| first=Rudolf| last= Ahlswede| author-link= Rudolf Ahlswede|author2=N. Cai |author3=S.-Y. R. Li |author4=R. W. Yeung | title=Network Information Flow| journal=IEEE Transactions on Information Theory| pages= 1204–1216| year= 2000| doi=10.1109/18.850663| volume=46| issue=4| citeseerx= 10.1.1.722.1409}}</ref>

== The butterfly network example ==
[[Image:Butterfly network.svg|thumb|Butterfly Network.]]
The butterfly network <ref name="Ahlswede2000"/> is often used to illustrate how linear network coding can outperform [[routing]]. Two source nodes (at the top of the picture) have information A and B that must be transmitted to the two destination nodes (at the bottom), which each want to know both A and B. Each edge can carry only a single value (we can think of an edge transmitting a bit in each time slot).

If only routing were allowed, then the central link would be only able to carry A or B, but not both. Suppose we send A through the center; then the left destination would receive A twice and not know B at all. Sending B poses a similar problem for the right destination. We say that routing is insufficient because no routing scheme can transmit both A and B simultaneously to both destinations.

Using a simple code, as shown, A and B can be transmitted to both destinations simultaneously by sending the sum of the symbols through the center&nbsp;– in other words, we encode A and B using the formula "A+B". The left destination receives A and A&nbsp;+&nbsp;B, and can calculate B by subtracting the two values. Similarly, the right destination will receive B and A&nbsp;+&nbsp;B, and will also be able to determine both A and B.

== Random Linear Network Coding ==

Random linear network coding <ref name="Ho2003">T. Ho, R. Koetter, [[Muriel Médard|M. Médard]], D. R. Karger and M. Effros, [http://www.its.caltech.edu/~tho/i1.pdf "The Benefits of Coding over Routing in a Randomized Setting"] {{Webarchive|url=https://web.archive.org/web/20171031184306/http://www.its.caltech.edu/~tho/i1.pdf |date=2017-10-31 }} in 2003 IEEE International Symposium on Information Theory. {{DOI|10.1109/ISIT.2003.1228459}}</ref> is a simple yet powerful encoding scheme, which in broadcast transmission schemes allows close to optimal throughput using a decentralized algorithm. Nodes transmit random linear combinations of the packets they receive, with coefficients chosen from a Galois field. If the field size is sufficiently large, the probability that the receiver(s) will obtain linearly independent combinations (and therefore obtain innovative information) approaches 1. It should however be noted that, although random linear network coding has excellent throughput performance, if a receiver obtains an insufficient number of packets, it is extremely unlikely that they can recover any of the original packets. This can be addressed by sending additional random linear combinations until the receiver obtains the appropriate number of packets.

=== Open issues ===
Linear network coding is still a relatively new subject. Based on previous studies, there are three important open issues in RLNC:
# High decoding computational complexity due to using the Gauss-Jordan elimination method
# High transmission overhead due to attaching large coefficients vectors to encoded blocks
# Linear dependency among coefficients vectors which can reduce the number of innovative encoded blocks

== 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/pdf/1210.1326.pdf 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>[http://nms.csail.mit.edu/~sachin/papers/copesc.pdf XORs in The Air: Practical Wireless Network Coding]</ref>

== Applications ==

[[File:NC D2D.png|thumb|500px|A short illustration of the network coding applied to Device-to-Device communication. D1 and D2 denote the devices, BS is the base station and M1, M2 and M3 are the certain messages.]]

Since linear network coding is a relatively new subject, its adoption in industries 
is still pending. Unlike other coding, linear network coding is not entirely applicable
in a system due to its narrow specific usage scenario. Theorists are trying to connect
to real world applications.<ref>{{cite journal|title=How Practical is Network Coding? by Mea Wang, Baochun Li|citeseerx = 10.1.1.77.6402}}</ref> In fact, it was found that BitTorrent approach is far superior than network coding.{{vague|date=April 2019}}{{citation needed|date=April 2019}}

It is envisaged that network coding is useful in the following areas:
* Owing to multi-source, multicast content-delivery nature of [[Information-centric networking]], the linear coding can improve over all network efficiency. <ref>{{cite journal|author=Bilal, Muhammad|displayauthors=etal|title=Network-Coding Approach for Information-Centric Networking|journal=IEEE Systems Journal |pages=1–10|arxiv=1808.00348|doi=10.1109/JSYST.2018.2862913|year=2018}}</ref>
* Alternative to [[forward error correction]] and [[Automatic repeat request|ARQ]] in traditional and wireless networks with packet loss. e.g.: [[Coded TCP]],<ref>{{Cite arXiv |eprint = 1212.2291|last1 = Bilal|first1 = Muhammad|title = Network Coded TCP (CTCP)|class = cs.NI|year = 2012}}</ref> [[Multi-user ARQ]]<ref>{{cite web|url=http://www.ericsson.com/technology/research_papers/wireless_access/doc/Multi-User%20ARQ.pdf |title=Archived copy |accessdate=2007-06-16 |url-status=dead |archiveurl=https://web.archive.org/web/20071108173654/http://www.ericsson.com/technology/research_papers/wireless_access/doc/Multi-User%20ARQ.pdf |archivedate=2007-11-08 }}</ref>
* Robust and resilient to network attacks like snooping, eavesdropping, replay or data corruption attacks.<ref>{{Cite web | url=http://securenetworkcoding.wikidot.com/ | title=Welcome to Network Coding Security - Secure Network Coding}}</ref><ref>http://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf{{dead link|date=December 2017 |bot=InternetArchiveBot |fix-attempted=yes }}</ref>
* Digital file distribution and P2P file sharing. e.g.: [[Avalanche filesystem|Avalanche]] from Microsoft
* Distributed storage.<ref>{{Cite web |url=http://netcod.org/papers/11AcedanskiDMK-final.pdf |title=Archived copy |access-date=2013-04-18 |archive-url=https://web.archive.org/web/20130919032950/http://netcod.org/papers/11AcedanskiDMK-final.pdf |archive-date=2013-09-19 |url-status=dead }}</ref><ref>{{Cite arXiv |eprint = cs/0702015|last1 = Bilal|first1 = Muhammad|title = Network Coding for Distributed Storage Systems|year = 2007}}</ref>
* Throughput increase in wireless mesh networks. e.g. : [[COPE (network coding)|COPE]],<ref>http://people.csail.mit.edu/rahul/papers/cope-ton2008.pdf</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 }}</ref> [[Coding-aware routing]],<ref>{{cite web |url=http://arena.cse.sc.edu/papers/rocx.secon06.pdf |title=Archived copy |accessdate=2007-05-10 |url-status=dead |archiveurl=https://web.archive.org/web/20081011124616/http://arena.cse.sc.edu/papers/rocx.secon06.pdf |archivedate=2008-10-11 }}</ref><ref>http://www.cs.wisc.edu/~shravan/infocom-07-2.pdf</ref> [[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|website = www.open-mesh.org|accessdate = 2015-10-28}}</ref>
* Buffer and Delay reduction in spatial sensor networks: [[Spatial buffer multiplexing]] <ref>[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4146919 Welcome to IEEE Xplore 2.0: Looking at Large Networks: Coding vs. Queueing<!-- Bot generated title -->]</ref>
* Reduce the number of packet retransmission for a single-hop wireless multicast transmission, and hence improve network bandwidth.<ref>{{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}}</ref>
* Distributed file sharing <ref>[https://arxiv.org/pdf/1203.5395.pdf Data dissemination in wireless networks with network coding]</ref>
* Low-complexity video streaming to mobile devices <ref>[https://ieeexplore.ieee.org/document/6630050/?tp=&arnumber=6630050 Band Codes for Energy-Efficient Network Coding With Application to P2P Mobile Streaming]</ref>
* [[Device-to-device | Device-to-Device (D2D)]] extensions<ref>Wu, Y., Liu, W., Wang, S., Guo, W., & Chu, X. (2015, June). [https://www.researchgate.net/profile/Yue_Wu77/publication/270645302_Network_Coding_in_Device-to-device_D2D_Communications_Underlaying_Cellular_Networks/links/57977bd508aec89db7b9a65d/Network-Coding-in-Device-to-device-D2D-Communications-Underlaying-Cellular-Networks.pdf Network coding in device-to-device (D2D) communications underlaying cellular networks]. In 2015 IEEE International Conference on Communications (ICC) (pp. 2072-2077). IEEE.</ref><ref>Zhao, Y., Li, Y., & Ge, N. (2015, December). [http://or.nsfc.gov.cn/bitstream/00001903-5/421291/1/1000014259648.pdf Physical layer network coding aided two-way device-to-device communication underlaying cellular networks]. In 2015 IEEE Global Communications Conference (GLOBECOM) (pp. 1-6). IEEE.</ref><ref>Abrardo, A., Fodor, G., & Tola, B. (2015, June). [http://www.diva-portal.org/smash/get/diva2:795210/FULLTEXT01.pdf Network coding schemes for device-to-device communications based relaying for cellular coverage extension]. In 2015 IEEE 16th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) (pp. 670-674). IEEE.</ref><ref>Gao, C., Li, Y., Zhao, Y., & Chen, S. (2017). [https://eprints.soton.ac.uk/414039/1/NC_D2D.pdf A two-level game theory approach for joint relay selection and resource allocation in network coding assisted D2D communications]. IEEE Transactions on Mobile Computing, 16(10), 2697-2711.</ref><ref>Zhou, T., Xu, B., Xu, T., Hu, H., & Xiong, L. (2015). User-specific link adaptation scheme for device-to-device network coding multicast. IET Communications, 9(3), 367-374.</ref>

== Maturity & Issues ==
Since this area is relatively new and the mathematical treatment of this subject is
currently limited to a handful of people, network coding has yet found its way to
commercialization in products and services. It is unclear at this stage if this 
subject will prevail, or cease as a good mathematical exercise.<ref>{{cite journal|title=How Practical is Network Coding?|citeseerx = 10.1.1.77.6402}}</ref>

Researchers have clearly pointed out that special care is needed to explore how network coding can co-exist with existing routing, media access, congestion, flow control algorithms and TCP protocol. If not, network coding may not offer much advantages and can increase computation complexity and memory requirements.<ref>{{cite web|url=http://nms.csail.mit.edu/~sachin/papers/copesc.pdf |title=XORs in The Air}}</ref>

== See also ==
* [[Secret sharing protocol]]
* [[Homomorphic signatures for network coding]]
* [[Triangular network coding]]

== References ==
{{Reflist}}
* 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.

== External links ==
* [https://web.archive.org/web/20070524100030/http://www.ifp.uiuc.edu/~koetter/NWC/index.html Network Coding Homepage]
* [https://web.archive.org/web/20110719100201/https://wiki.lnt.ei.tum.de/doku.php?id=network_coding:bibliography_for_network_coding 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.
* 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: [http://web.mit.edu/professional/short-programs/courses/network_coding.html Introduction to Network Coding]
* [https://web.archive.org/web/20090331225831/http://www.networkworld.com/news/2007/121007-network-coding.html Network coding: Networking's next revolution?]
* Coding-aware protocol design for wireless networks: http://scholarcommons.sc.edu/etd/230/

{{DEFAULTSORT:Network Coding}}
[[Category:Coding theory]]
[[Category:Information theory]]
[[Category:Finite fields]]
[[Category:Network performance]]
[[Category:Wireless sensor network]]