Content deleted Content added
plural links |
Citation bot (talk | contribs) Altered page. Add: date, bibcode. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 559/990 |
||
(31 intermediate revisions by 14 users not shown) | |||
Line 1:
{{Short description|Computer Networking Program}}
{{CS1 config|mode=cs1}}
In [[computer networking]], '''linear network coding''' is a program in which intermediate nodes transmit data from source nodes to sink nodes by means of [[linear combination]]s.
Linear network coding may be used to improve a network's throughput, efficiency, and [[scalability]], as well as reducing attacks and eavesdropping. The [[Node (networking)|node]]s of a network take ''several'' packets and combine for transmission. This process may be used to attain the maximum possible [[information]] [[flow network|flow]] in a [[Network theory|network]].
It has been 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; 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
and even [[Undecidable problem|undecidable]].<ref name="li_nc">{{cite journal|last1=Li|first1=C. T.|title=Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication|journal=IEEE Transactions on Information Theory|date=2023|volume=69 |issue=6 |page=3493 |doi=10.1109/TIT.2023.3247570|arxiv=2205.11461 |bibcode=2023ITIT...69.3493L |s2cid=248986512 }}</ref><ref name="kuhne_matroid">{{cite journal|last1=Kühne|first1=L.|title=Representability of Matroids by c-Arrangements is Undecidable|last2=Yashfe|first2=G.|journal=[[Israel Journal of Mathematics]]|date=2022|volume=252 |pages=95–147|doi=10.1007/s11856-022-2345-z|arxiv=1912.06123 |s2cid=209324252 }}</ref>
== Encoding and decoding ==
Line 51 ⟶ 54:
==== Example ====
[[File:CodingProcess.png|thumb|368x368px|Coding and recoding process in linear network coding. Each packet is seen as a set of elements from a Galois field. Therefore, multiplying and adding two packets means multiplying each of its symbols by a coding coefficient chosen from the Galois field and then adding the two packets together, symbol-wise.]]
In the figure, we can see an example of two packets linearly combined into a new coded packet. In the example, we have two packets, namely packet '''<math>f</math>''' and packet '''<math>e</math>'''. The generation size of our example is two. We know this because each packet has two coding
Now, lets assume that the network node wants to produce a new coded packet combining packet <math>f</math> and packet <math>e</math>. In RLNC, it will randomly choose two coding coefficients, '''<math>d_1</math>''' and '''<math>d_2</math>''' in the example. The node will multiply each symbol of packet <math>f</math> by '''<math>d_1</math>''', and each symbol of packet <math>e</math> by '''<math>d_2</math>'''. Then, it will add the results symbol-wise to produce the new coded data. It will perform the same operations of multiplication and addition to the coding coefficients of the coded packets.
Line 58 ⟶ 61:
Linear network coding is still a relatively new subject. However, the topic has been vastly researched over the last twenty years. Nevertheless, there are still some misconceptions that are no longer valid:
'''Decoding computational complexity:''' Network coding decoders have been improved over the years. Nowadays, the algorithms are highly efficient and parallelizable. In 2016,
'''Transmission Overhead:''' It is usually thought that the transmission overhead of network coding is high due to the need to append the coding coefficients to each coded packet. In reality, this overhead is negligible in most applications. The overhead due to coding coefficients can be computed as follows. Each packet has appended <math>M</math> coding coefficients. The size of each coefficient is the number of bits needed to represent one element of the Galois field. In practice, most network coding applications use a generation size of no more than 32 packets per generation and Galois fields of 256 elements (binary-8). With these numbers, each packet needs <math>M * log_2(s) = 32</math> bytes of appended overhead. If each packet is 1500 bytes long (i.e. the Ethernet MTU), then 32 bytes represent an overhead of only 2%.
[[File:LinDependenciesbinary.png|thumb|448x448px|Expected linearly dependent packets at different stages of transmission for a Galois field <math>GF(2)</math> and a generation size of 16 packets. At the beginning of the transmission, the linear dependencies are minimal. It is the last packet of the
[[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
== Applications ==
Line 69 ⟶ 72:
Over the years, multiple researchers and companies have integrated network coding solutions into their applications.<ref>{{Cite web |title=Coding the Network: Next Generation Coding for Flexible Network Operation {{!}} IEEE Communications Society |url=https://www.comsoc.org/publications/ctn/coding-network-next-generation-coding-flexible-network-operation |access-date=2022-06-06 |website=www.comsoc.org}}</ref> We can list some of the applications of network coding in different areas:
* [[Voice over IP|VoIP]]:<ref>{{Cite
* Video<ref name=":2">{{Cite
* Software-defined wide area networks ([[SD-WAN]]):<ref name=":5">{{Cite
* Channel bundling:<ref name=":8">{{Cite
* [[5G]] private networks:<ref name=":9">{{Cite journal |last1=Vukobratovic |first1=Dejan |last2=Tassi |first2=Andrea |last3=Delic |first3=Savo |last4=Khirallah |first4=Chadi |date=April 2018 |title=Random Linear Network Coding for 5G Mobile Video Delivery |journal=Information |language=en |volume=9 |issue=4 |pages=72 |arxiv=1802.04873 |doi=10.3390/info9040072 |issn=2078-2489|doi-access=free }}</ref><ref name=":10">{{Cite
* Remote collaboration.<ref>{{Cite journal |last1=Magli |first1=Enrico |last2=Wang |first2=Mea |last3=Frossard |first3=Pascal |last4=Markopoulou |first4=Athina |date=August 2013 |title=Network Coding Meets Multimedia: A Review
* [[Augmented reality]] remote support and training.<ref>{{Cite journal |last1=Torres Vega |first1=Maria |last2=Liaskos |first2=Christos |last3=Abadal |first3=Sergi |last4=Papapetrou |first4=Evangelos |last5=Jain |first5=Akshay |last6=Mouhouche |first6=Belkacem |last7=Kalem |first7=Gökhan |last8=Ergüt |first8=Salih |last9=Mach |first9=Marian |last10=Sabol |first10=Tomas |last11=Cabellos-Aparicio |first11=Albert |date=October 2020 |title=Immersive Interconnected Virtual and Augmented Reality: A 5G and IoT Perspective |url=https://link.springer.com/10.1007/s10922-020-09545-w |journal=Journal of Network and Systems Management |language=en |volume=28 |issue=4 |pages=796–826 |doi=10.1007/s10922-020-09545-w |hdl=2117/330129 |s2cid=219589307 |issn=1064-7570|hdl-access=free }}</ref>
* Remote vehicle driving applications.<ref>{{Cite
* [[Connected cars]] networks.<ref>{{Cite
* Gaming applications such as low latency streaming and multiplayer connectivity.<ref>{{cite arXiv |last1=Dammak |first1=Marwa |last2=Andriyanova |first2=Iryna |last3=Boujelben |first3=Yassine |last4=Sellami |first4=Noura |date=2018-03-29 |title=Routing and Network Coding over a Cyclic Network for Online Video Gaming |class=cs.IT |eprint=1803.11102 }}</ref><ref>{{Cite
* Healthcare applications.<ref>{{Cite book
* [[Fourth Industrial Revolution|Industry 4.0]].<ref>{{Cite
* Satellite networks.<ref>{{Cite web |title=DLR - Institute of Communications and Navigation - NEXT - Network Coding Satellite Experiment |url=https://www.dlr.de/kn/en/desktopdefault.aspx/tabid-12748/22264_read-26607/ |access-date=2022-06-06 |website=www.dlr.de}}</ref>
* Agricultural sensor fields.<ref>{{Cite
* In-flight
* Major security and firmware updates for mobile product families.<ref>{{Cite
* [[Smart city]] infrastructure.<ref>{{Cite
* [[Information-centric networking]] and [[named data networking]].:<ref name="Bilal, Muhammad 2019 1376–1385">{{cite journal |author=Bilal, Muhammad |display-authors=etal |year=2019 |title=Network-Coding Approach for Information-Centric Networking |journal=IEEE Systems Journal |volume=13 |issue=2 |pages=1376–1385 |arxiv=1808.00348 |bibcode=2019ISysJ..13.1376B |doi=10.1109/JSYST.2018.2862913 |s2cid=51894197}}</ref> Linear network coding can improve the network efficiency of information-centric networking solutions by exploiting the multi-source multi-cast nature of such
* Alternative to [[forward error correction]] and [[automatic repeat request]]s in traditional and wireless networks with packet loss, 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>{{Cite
* Protection against network attacks such as snooping, eavesdropping, replay, or data corruption.<ref>{{Cite web |title=Welcome to Network Coding Security - Secure Network Coding |url=http://securenetworkcoding.wikidot.com/
| | last2 = Wei | first2 = Yawen
| last3 = Ramkumar | first3 = Bhuvaneswari
| last4 = Guan | first4 = Yong
| contribution = An efficient signature-based scheme for securing network coding against pollution attacks
| contribution-url = https://scholar.archive.org/work/keidxnnwaffnrouhg25c5l3ybi
| doi = 10.1109/INFOCOM.2008.199
| pages = 1409–1417
| publisher = IEEE
| title = INFOCOM 2008. 27th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 13–18 April 2008, Phoenix, AZ, USA
| year = 2008| isbn = 978-1-4244-2026-1
}}</ref>
* 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
* Throughput increase in wireless mesh networks, e.g.: [[COPE (network coding)|COPE]],<ref name=":0">{{Cite
* Buffer and delay reduction in spatial sensor networks: [[Spatial buffer multiplexing]]<ref>{{Cite
* 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.| bibcode=2009ITVT...58..914N|citeseerx = 10.1.1.321.1962| s2cid=16989586}}</ref>
* Distributed file sharing<ref>{{Cite journal |last1=Firooz |first1=Mohammad Hamed |last2=Roy |first2=Sumit |date=24 March 2012 |title=Data Dissemination in Wireless Networks with Network Coding |journal=IEEE Communications Letters |volume=17 |issue=5 |pages=944–947 |doi=10.1109/LCOMM.2013.031313.121994 |arxiv=1203.5395 |s2cid=13576 |issn=1089-7798}}</ref>
* Low-complexity video streaming to mobile device<ref>{{Cite journal |last1=Fiandrotti |first1=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
* [[Device-to-device]] extensions<ref>{{Cite
== See also ==
Line 106 ⟶ 121:
{{Reflist}}
* Fragouli, C.; Le Boudec, J. & Widmer, J. "Network coding: An instant primer" in ''Computer Communication Review'', 2006. https://doi.org/10.1145/1111322.1111337
* 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 ==
|