Linear network coding: Difference between revisions

Revision as of 20:58, 26 March 2022

Revision as of 15:45, 7 April 2022

Line 1:

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

In [[computer networking]], '''linear network coding''' is a schemeprogram 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'''.

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, theThe [[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]].

It has been mathematically proven that, theoretically, [[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 earlierpast received packets by multiplying them by [[coefficient]]s chosen from a [[Galois field|finite field]], typically of size <math>GF(2^s)</math>.

More 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 formula:

:<math>X_k = \sum_{i=1}^S g_k^i\cdot M_i</math>

whereWhere the values <math>g_k^i</math> are the coefficients selected from <math>GF(2^s)</math>. Note that, sinceSince 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

Line 21:

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

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 1978, Celebiler and Stette proposed a scheme for improving the throughput of a two-way communication through a satellite.<ref name="Celebiler&S1978">{{cite journal |last=Celebiler |first=M. |author2=G. Stette |year=1978 |title=On Increasing the Down-Link Capacity of a Regenerative Satellite Repeater in Point-to-Point Communications |journal=Proceedings of the IEEE |volume=66 |issue=1 |pages=98–100 |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.

In 2000, Rudolf and Cai gave the butterfly network example, 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 ==

Line 37 ⟶ 30:

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 butterflyButterfly network exampleNetwork ==

[[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 simultanouslysimultaneously. Meanwhile, it takes four time slots in total for both destination nodes to know A and B.

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.

Line 58 ⟶ 51:

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 |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 |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}}</ref>

== Applications ==

Line 78 ⟶ 71:

There are new methods{{Which|date=March 2022}} emerging to use network coding in multiaccess systems to develop Software Defined Wire Area Networks that can offer lower delay, jitter and high robustness.<ref>{{Cite journal |last=Rachuri |first=Sri Pramodh |last2=Ansari |first2=Ahtisham Ali |last3=Tandur |first3=Deepaknath |last4=Kherani |first4=Arzad A. |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>{{Cite journal |last=Ansari |first=Ahtisham Ali |last2=Rachuri |first2=Sri Pramodh |last3=Kherani |first3=Arzad A. |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 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 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>

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">{{Cite 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 |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}}</ref>

== See also ==