Linear network coding: Difference between revisions

Revision as of 17:26, 24 March 2022

Revision as of 20:38, 26 March 2022

Line 1:

{{Copy edit|date=February 2022}}{{Confusing|date=March 2022}}

In [[computer networking]], '''linear network coding''' is a scheme in which intermediate nodes transmit data from source nodes to sink nodes by means of [[linear combinations]] of the source nodes' data over a [[Galois field|finite field]], which are them solved by sink nodes to yield the source data. It is a technique used in the broader field of '''network coding'''.

Network coding is a field of research that originally emerged in a series of papers from the late 1990s to the early 2000s. The concept of '''linear network coding''', however, predates this. In a 1978 paper,<ref> name="</ref> a scheme for improving the throughput of a two-way communication through a satellite was proposed. In this scheme, two communicating users would transmit their data streams to a satellite, combining the two streams by summing them modulo 2 and then broadcasting 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), illustrating how linear network coding can outperform routing. This example is equivalent to the scheme for satellite communication described above. The same paper gives an optimal coding scheme for a network with one source node and three destination nodes. This represents 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 reducing 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 process may be used to attain the maximum possible [[information]] [[flow network|flow]] in a [[Network theory|network]].

Line 10 ⟶ 8:

== 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, by multiplying them by [[coefficient]]s chosen from a [[Galois field|finite field]], typically of size <math>GF(2^s)</math>.

EachMore formally, 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 relationformula:

:<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>.

Line 26 ⟶ 24:

== A brief history ==

Network coding is a field of research that originally emerged in a series of papers from the late 1990s to the early 2000s. The concept of linear network coding, however, predates this.

NetworkIn coding1978, isCelebiler aand fieldStette ofproposed researcha thatscheme originallyfor emergedimproving inthe a seriesthroughput of papersa fromtwo-way thecommunication latethrough 1990sa tosatellite.<ref thename="Celebiler&S1978">{{cite earlyjournal 2000s|last=Celebiler |first=M. The|author2=G. conceptStette of|year=1978 '''linear|title=On networkIncreasing coding''',the however,Down-Link predatesCapacity this. Inof a 1978Regenerative paper,<ref>Satellite name="</ref>Repeater ain schemePoint-to-Point forCommunications improving the throughput|journal=Proceedings of athe two-wayIEEE communication|volume=66 through|issue=1 a|pages=98–100 satellite was proposed|doi=10.1109/PROC.1978.10848}}</ref> In this scheme, two communicating users would transmit their data streams to a satellite, combining the two streams by summing them modulo 2 and then broadcasting 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.

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

== Background ==

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"{{Which|date=March 2022}} 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). Each destination node wants 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. Supposing 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 to both destinations simultanously. Meanwhile, it takes four time slots in total for both destination nodes to know A and B.

Line 40 ⟶ 45:

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 two relay nodes – encoding A and B using the formula "A+B". The left destination receives A and A + B, and can calculate B by subtracting the two values. Similarly, the right destination will receive B and A + B, and will also be able to determine both A and B. Therefore, with network coding, it takes only three time slots and improves the throughput.

== Random Linearlinear Networknetwork Codingcoding ==

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 issuesIssues ===

Linear network coding is still a relatively new subject. Based on previous studies{{Which|date=March 2022}}, 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 Networknetwork Codingcoding ==

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

== Applications ==

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

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 it to real world applications{{How|date=March 2022}}.<ref>{{cite journal|title=How Practical is Network Coding? by Mea Wang, Baochun Li|citeseerx = 10.1.1.77.6402}}</ref> It is envisaged that network coding may be useful in the following areas:

Since linear network coding is a relatively new subject, its adoption in industries

* Owing to multi-source, multicast content-delivery nature of [[Informationinformation-centric networking]] in general and [[Named Data Networking]]; in particular, the linear coding can improve over all network efficiency{{How|date=March 2022}}{{Weasel inline|date=March 2022}}.<ref name="Bilal, Muhammad 2019 1376–1385">{{cite journal|author=Bilal, Muhammad|display-authors=etal|title=Network-Coding Approach for Information-Centric Networking|journal=IEEE Systems Journal |volume=13|issue=2|pages=1376–1385|arxiv=1808.00348|doi=10.1109/JSYST.2018.2862913|bibcode=2019ISysJ..13.1376B|year=2019}}</ref>

is still pending. Unlike other coding, linear network coding is not entirely applicable

* Alternative to [[forward error correction]] and [[Automatic repeat request|ARQautomatic repeat requests]] in traditional and wireless networks with packet loss., e.g.:such as [[Coded TCP]],<ref>{{Cite arXiv |eprint = 1212.2291|last1 = Kim|first1 = Minji|title = Network Coded TCP (CTCP)|class = cs.NI|year = 2012}}</ref> and [[Multi-user ARQ]]<ref>{{citeCite journal web|urllast=http://wwwLarsson |first=P.ericsson |last2=Johansson |first2=N.com/technology/research_papers/wireless_access/doc/Multi-User%20ARQ.pdf |titledate=ArchivedMay copy2006 |accessdatetitle=2007Multi-06-16User |url-status=deadARQ |archiveurlurl=https://webieeexplore.archiveieee.org/webabstract/20071108173654document/http://www.ericsson.com/technology/research_papers/wireless_access/doc/Multi-User%20ARQ.pdf1683207 |archivedatejournal=2007-11-082006 IEEE 63rd Vehicular Technology Conference |volume=4 |pages=2052–2057 |doi=10.1109/VETECS.2006.1683207}}</ref>

in a system due to its narrow specific usage scenario. Theorists are trying to connect

* Robust and resilient{{Weasel inline|date=March 2022}} to network attacks like snooping, eavesdropping, replay, or data corruption attacks.<ref>{{Cite web |title=Welcome to Network Coding Security - Secure Network Coding |url=http://securenetworkcoding.wikidot.com/ | titleurl-status=Welcome to Network Coding Securitylive |access-date=26 SecureMarch Network2022 Coding|website=securenetworkcoding.wikidot.com}}</ref><ref>http://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf{{dead link|date=December 2017 |bot=InternetArchiveBot |fix-attempted=yes }}<nowiki/>{{Dead link|date={{subst:CURRENTMONTHNAME}} {{subst:CURRENTYEAR}}}}</ref>

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>

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

It is envisaged that network coding is useful in the following areas:

* Distributed storage.<ref name="Bilal, Muhammad 2019 1376–1385"/><ref>{{Cite web |urllast=http://netcod.org/papers/11AcedanskiDMK-final.pdfAcedański |titlefirst=ArchivedSzymon copy|last2=Deb |access-datefirst2=2013-04-18Supratim |last3=Médard |first3=Muriel |last4=Koetter |first4=Ralf |title=How Good is Random Linear Coding Based Distributed Networked Storage? |archive-url=httpshttp://web.archivemit.orgedu/web~medard/20130919032950www/http:page2/mpapers/netcod.org/papers/11AcedanskiDMK-finalnetcod2005_accek.pdf |archiveurl-datestatus=2013-09-19live |urlaccess-statusdate=dead26 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>

* Owing to multi-source, multicast content-delivery nature of [[Information-centric networking]] in general and [[Named Data Networking]] in particular, the linear coding can improve over all network efficiency.<ref name="Bilal, Muhammad 2019 1376–1385">{{cite journal|author=Bilal, Muhammad|display-authors=etal|title=Network-Coding Approach for Information-Centric Networking|journal=IEEE Systems Journal |volume=13|issue=2|pages=1376–1385|arxiv=1808.00348|doi=10.1109/JSYST.2018.2862913|bibcode=2019ISysJ..13.1376B|year=2019}}</ref>

* Throughput increase in wireless mesh networks., e.g.: [[COPE (network coding)|COPE]],<ref>http://people.csail.mit.edu/rahul/papers/cope-ton2008.pdf {{Bare URL PDF|datename=March":0" 2022}}</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>{{Full citation needed|date=March 2022}}<ref>http{{Cite journal |last=Sengupta |first=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://www.csieeexplore.wiscieee.eduorg/~shravanabstract/infocomdocument/4215706 |journal=IEEE INFOCOM 2007 -07-2.pdf {{Bare26th IEEE International Conference on Computer URLCommunications PDF|datepages=March1028–1036 2022|doi=10.1109/INFCOM.2007.124}}</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 |url-status=live |archive-url=https://web.archive.org/web/20210512133041/https://www.open-mesh.org/projects/batman-adv/wiki/NetworkCoding |accessdatearchive-date=12 May 2021 |website=www.open-mesh.org |accessdate=2015-10-28}}</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 = Kim|first1 = Minji|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>

* Buffer and delay reduction in spatial sensor networks: [[Spatial buffer multiplexing]]<ref>{{Cite journal |last=Bhadra |first=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}}</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>

* 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>

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

* Distributed file sharing<ref>{{Cite journal |last=Firooz |first=Mohammad Hamed |last2=Roy |first2=Sumit |date=24 March 2012 |title=Data Dissemination in Wireless Networks with Network Coding |url=http://arxiv.org/abs/1203.5395 |journal=IEEE Communications Letters |volume=17 |issue=5 |pages=944–947 |doi=10.1109/LCOMM.2013.031313.121994 |issn=1089-7798}}</ref>

* Distributed storage.<ref name="Bilal, Muhammad 2019 1376–1385"/><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 = Dimakis|first1 = Alexandros|title = Network Coding for Distributed Storage Systems|year = 2007}}</ref>

* Low-complexity video streaming to mobile device<ref>{{Cite journal |last=Fiandrotti |first=Attilio |last2=Bioglio |first2=Valerio |last3=Grangetto |first3=Marco |last4=Gaeta |first4=Rossano |last5=Magli |first5=Enrico |date=11 October 2013 |title=Band Codes for Energy-Efficient Network Coding With Application to P2P Mobile Streaming |url=https://ieeexplore.ieee.org/document/6630050/?tp=&arnumber=6630050 |journal=IEEE Transactions on Multimedia |volume=16 |issue=2 |pages=521–532 |doi=10.1109/TMM.2013.2285518 |issn=1941-0077}}</ref>

* Throughput increase in wireless mesh networks. e.g.: [[COPE (network coding)|COPE]],<ref>http://people.csail.mit.edu/rahul/papers/cope-ton2008.pdf {{Bare URL PDF|date=March 2022}}</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 {{Bare URL PDF|date=March 2022}}</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>

* [[Device-to-device]] extensions<ref>{{Cite journal |last=Wu |first=Yue |last2=Liu |first2=Wuling |last3=Wang |first3=Siyi |last4=Guo |first4=Weisi |last5=Chu |first5=Xiaoli |date=June 2015 |title=Network coding in device-to-device (D2D) communications underlaying cellular networks |url=https://ieeexplore.ieee.org/abstract/document/7248631 |journal=2015 IEEE International Conference on Communications (ICC) |pages=2072–2077 |doi=10.1109/ICC.2015.7248631}}</ref><ref>{{Cite journal |last=Zhao |first=Yulei |last2=Li |first2=Yong |last3=Ge |first3=Ning |date=December 2015 |title=Physical Layer Network Coding Aided Two-Way Device-to-Device Communication Underlaying Cellular Networks |url=https://ieeexplore.ieee.org/abstract/document/7417590 |journal=2015 IEEE Global Communications Conference (GLOBECOM) |pages=1–6 |doi=10.1109/GLOCOM.2015.7417590}}</ref><ref>{{Cite journal |last=Abrardo |first=Andrea |last2=Fodor |first2=Gábor |last3=Tola |first3=Besmir |date=2015 |title=Network coding schemes for Device-to-Device communications based relaying for cellular coverage extension |url=http://www.diva-portal.org/smash/get/diva2:795210/FULLTEXT01.pdf |journal=2015 IEEE 16th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) |pages=670–674 |doi=10.1109/SPAWC.2015.7227122}}</ref><ref>{{Cite journal |last=Gao |first=Chuhan |last2=Li |first2=Yong |last3=Zhao |first3=Yulei |last4=Chen |first4=Sheng |date=October 2017 |title=A Two-Level Game Theory Approach for Joint Relay Selection and Resource Allocation in Network Coding Assisted D2D Communications |url=https://eprints.soton.ac.uk/414039/1/NC_D2D.pdf |journal=IEEE Transactions on Mobile Computing |volume=16 |issue=10 |pages=2697–2711 |doi=10.1109/TMC.2016.2642190 |issn=1558-0660}}</ref><ref>{{Cite journal |last=Zhou |first=Ting |last2=Xu |first2=Bin |last3=Xu |first3=Tianheng |last4=Hu |first4=Honglin |last5=Xiong |first5=Lei |date=1 February 2015 |title=User‐specific link adaptation scheme for device‐to‐device network coding multicast |url=https://ietresearch.onlinelibrary.wiley.com/doi/full/10.1049/iet-com.2014.0323 |journal=IET Communications |volume=9 |issue=3 |pages=367–374 |doi=10.1049/iet-com.2014.0323 |issn=1751-8636}}</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/abs/1203.5395 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>

There are new methods{{Which|date=March 2022}} emerging to use Networknetwork Codingcoding in multiaccess systems to develop Software Defined Wire Area Networks (SD-WANs) that can offer lower delay, jitter and high robustness.<ref>[https://www.researchgate{{Cite journal |last=Rachuri |first=Sri Pramodh |last2=Ansari |first2=Ahtisham Ali |last3=Tandur |first3=Deepaknath |last4=Kherani |first4=Arzad A.net/publication/339973461_Network-Coded_SD-WAN_in_Multi-Access_Systems_for_Delay_Control |last5=Chouksey |first5=Sameer |date=December 2019 |title=Network-Coded SD-WAN in Multi-Access Systems for Delay Control] |url=https://ieeexplore.ieee.org/document/9055565 |journal=2019 International Conference on contemporary Computing and Informatics (IC3I) |pages=32–37 |doi=10.1109/IC3I46837.2019.9055565}}</ref> The proposal mentions that the method is agnostic to underlying technologies like LTE, Ethernet, 5G.<ref>[https://www{{Cite journal |last=Ansari |first=Ahtisham Ali |last2=Rachuri |first2=Sri Pramodh |last3=Kherani |first3=Arzad A.researchgate.net/publication/339973738_An_SD-WAN_Controller_for_Delay_Jitter_Minimization_in_Coded_Multi-access_Systems |last4=Tandur |first4=Deepaknath |date=December 2019 |title=An SD-WAN Controller for Delay Jitter Minimization in Coded Multi-access Systems] |url=https://ieeexplore.ieee.org/abstract/document/9117981 |journal=2019 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS) |pages=1–6 |doi=10.1109/ANTS47819.2019.9117981}}</ref>

== Maturity &and Issuesissues ==

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 likely that this scheme will not prevail, but rather only be an interesting mathematical exercise.<ref>{{Cite journal |last=Wang |first=Mea |last2=Li |first2=Baochun |date=June 2006 |title=How Practical is Network Coding? |url=https://www.eecg.utoronto.ca/~bli/papers/mwang-iwqos06.pdf |journal=2006 14th IEEE International Workshop on Quality of Service |pages=274–278 |doi=10.1109/IWQOS.2006.250480}}</ref>

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 likely that this

subject will not prevail, and cease as a good mathematical exercise.<ref>{{cite journal|title=How Practical is Network Coding?|citeseerx = 10.1.1.77.6402}}</ref>

Researchers{{Who|date=March 2022}} 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 the TCP protocol. If not, network coding may not offer any advantages and can increase computation complexity and memory requirements.<ref name=":0">{{citeCite journal |last=Katti |first=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 web|url=http://nms.csail.mit.edu/~sachin/papers/copesc.pdf |titlejournal=XORsProceedings inof Thethe Air2006 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}}</ref>

== See also ==

Line 94 ⟶ 92:

{{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.

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 ==

{{External links|date=March 2022}}

* [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]