Jump to content

Linear network coding

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Tortus2123454567789 (talk | contribs) at 15:45, 7 April 2022 (Removes excess wording and vaguely related information that made the article confusing.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

Linear network coding may be used to improve a network's throughput, efficiency, and scalability, as well as reducing attacks and eavesdropping. The nodes of a network take several packets and combine for transmission. This process may be used to attain the maximum possible information flow in a network.

It has been proven that, theoretically, linear coding is enough to achieve the upper bound in multicast problems with one source.[1] However linear coding is not sufficient in general; even for more general versions of linearity such as convolutional coding and filter-bank coding.[2] 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 are involved in moving the data from source nodes to sink nodes. Each node generates new packets which are linear combinations of past received packets by multiplying them by coefficients chosen from a finite field, typically of size .

More formally, each node, with indegree, , generates a message from the linear combination of received messages by the formula:

Where the values are coefficients selected from . 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 along with the coefficients, , used in the level, .

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.[3] In reduced row echelon form, decoded packets correspond to the rows of the form

Background

A network is represented by a directed graph . is the set of nodes or vertices, is the set of directed links (or edges), and gives the capacity of each link of . Let be the maximum possible throughput from node to node . By the max-flow min-cut theorem, is upper bounded by the minimum capacity of all 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?] 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.[4]

The Butterfly Network

Butterfly Network.

The butterfly network[4] 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 simultaneously. 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 Linear Network Coding

Random linear network coding[5] 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.

Issues

Linear network coding is still a relatively new subject. Based on previous studies[which?], there are three important issues in RLNC:

  1. High decoding computational complexity due to using the Gauss-Jordan elimination method
  2. High transmission overhead due to attaching large coefficients vectors to encoded blocks
  3. 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. 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 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 PHY layer.[6] 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.[7]

Applications

A short illustration of network coding as applied to device-to-device communication. D1 and D2 are the devices, BS is the base station and M1, M2 and M3 are the 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?].[8] It is envisaged that network coding may be useful in the following areas:

There are new methods[which?] emerging to use network coding in multiaccess systems to develop Software Defined Wire Area Networks that can offer lower delay, jitter and high robustness.[29] The proposal mentions that the method is agnostic to underlying technologies like LTE, Ethernet, 5G.[30]

See also

References

  1. ^ S. Li, R. Yeung, and N. Cai, "Linear Network Coding"(PDF), in IEEE Transactions on Information Theory, Vol 49, No. 2, pp. 371–381, 2003
  2. ^ R. Dougherty, C. Freiling, and K. Zeger, "Insufficiency of Linear Coding in Network Information Flow" (PDF), in IEEE Transactions on Information Theory, Vol. 51, No. 8, pp. 2745-2759, August 2005 ( erratum)
  3. ^ Chou, Philip A.; Wu, Yunnan; Jain, Kamal (October 2003), "Practical network coding", Allerton Conference on Communication, Control, and Computing, Any receiver can then recover the source vectors using Gaussian elimination on the vectors in its h (or more) received packets.
  4. ^ a b Ahlswede, Rudolf; N. Cai; S.-Y. R. Li; R. W. Yeung (2000). "Network Information Flow". IEEE Transactions on Information Theory. 46 (4): 1204–1216. CiteSeerX 10.1.1.722.1409. doi:10.1109/18.850663.
  5. ^ T. Ho, R. Koetter, M. Médard, D. R. Karger and M. Effros, "The Benefits of Coding over Routing in a Randomized Setting" Archived 2017-10-31 at the Wayback Machine in 2003 IEEE International Symposium on Information Theory. doi:10.1109/ISIT.2003.1228459
  6. ^ M.H.Firooz, Z. Chen, S. Roy and H. Liu, (Wireless Network Coding via Modified 802.11 MAC/PHY: Design and Implementation on SDR) in IEEE Journal on Selected Areas in Communications, 2013.
  7. ^ a b Katti, Sachin; Rahul, Hariharan; Hu, Wenjun; Katabi, Dina; Médard, Muriel; Crowcroft, Jon (2006-08-11). "XORs in the air: practical wireless network coding" (PDF). Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications. SIGCOMM '06. New York, NY, USA: Association for Computing Machinery: 243–254. doi:10.1145/1159913.1159942. ISBN 978-1-59593-308-9.
  8. ^ "How Practical is Network Coding? by Mea Wang, Baochun Li". CiteSeerX 10.1.1.77.6402. {{cite journal}}: Cite journal requires |journal= (help)
  9. ^ a b Bilal, Muhammad; et al. (2019). "Network-Coding Approach for Information-Centric Networking". IEEE Systems Journal. 13 (2): 1376–1385. arXiv:1808.00348. Bibcode:2019ISysJ..13.1376B. doi:10.1109/JSYST.2018.2862913.
  10. ^ Kim, Minji (2012). "Network Coded TCP (CTCP)". arXiv:1212.2291 [cs.NI].
  11. ^ Larsson, P.; Johansson, N. (May 2006). "Multi-User ARQ". 2006 IEEE 63rd Vehicular Technology Conference. 4: 2052–2057. doi:10.1109/VETECS.2006.1683207.
  12. ^ "Welcome to Network Coding Security - Secure Network Coding". securenetworkcoding.wikidot.com. Retrieved 26 March 2022.{{cite web}}: CS1 maint: url-status (link)
  13. ^ http://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf[permanent dead link][dead link]
  14. ^ Acedański, Szymon; Deb, Supratim; Médard, Muriel; Koetter, Ralf. "How Good is Random Linear Coding Based Distributed Networked Storage?" (PDF). web.mit.edu. Retrieved 26 March 2022.{{cite web}}: CS1 maint: url-status (link)
  15. ^ Dimakis, Alexandros (2007). "Network Coding for Distributed Storage Systems". arXiv:cs/0702015.
  16. ^ Krigslund, Jeppe; Hansen, Jonas; Hundeboll, Martin; Lucani, Daniel E.; Fitzek, Frank H. P. (2013). CORE: COPE with MORE in Wireless Meshed Networks. pp. 1–6. doi:10.1109/VTCSpring.2013.6692495. ISBN 978-1-4673-6337-2. {{cite book}}: |journal= ignored (help)
  17. ^ "Archived copy" (PDF). Archived from the original (PDF) on 2008-10-11. Retrieved 2007-05-10.{{cite web}}: CS1 maint: archived copy as title (link)
  18. ^ Sengupta, S.; Rayanchu, S.; Banerjee, S. (May 2007). "An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing". IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications: 1028–1036. doi:10.1109/INFCOM.2007.124.
  19. ^ "NetworkCoding - batman-adv - Open Mesh". www.open-mesh.org. Archived from the original on 12 May 2021. Retrieved 2015-10-28.
  20. ^ Bhadra, S.; Shakkottai, S. (April 2006). "Looking at Large Networks: Coding vs. Queueing". Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications: 1–12. doi:10.1109/INFOCOM.2006.266.
  21. ^ Dong Nguyen; Tuan Tran; Thinh Nguyen; Bose, B. (2009). "Wireless Broadcast Using Network Coding". IEEE Transactions on Vehicular Technology. 58 (2): 914–925. CiteSeerX 10.1.1.321.1962. doi:10.1109/TVT.2008.927729.
  22. ^ Firooz, Mohammad Hamed; Roy, Sumit (24 March 2012). "Data Dissemination in Wireless Networks with Network Coding". IEEE Communications Letters. 17 (5): 944–947. doi:10.1109/LCOMM.2013.031313.121994. ISSN 1089-7798.
  23. ^ Fiandrotti, Attilio; Bioglio, Valerio; Grangetto, Marco; Gaeta, Rossano; Magli, Enrico (11 October 2013). "Band Codes for Energy-Efficient Network Coding With Application to P2P Mobile Streaming". IEEE Transactions on Multimedia. 16 (2): 521–532. doi:10.1109/TMM.2013.2285518. ISSN 1941-0077.
  24. ^ Wu, Yue; Liu, Wuling; Wang, Siyi; Guo, Weisi; Chu, Xiaoli (June 2015). "Network coding in device-to-device (D2D) communications underlaying cellular networks". 2015 IEEE International Conference on Communications (ICC): 2072–2077. doi:10.1109/ICC.2015.7248631.
  25. ^ Zhao, Yulei; Li, Yong; Ge, Ning (December 2015). "Physical Layer Network Coding Aided Two-Way Device-to-Device Communication Underlaying Cellular Networks". 2015 IEEE Global Communications Conference (GLOBECOM): 1–6. doi:10.1109/GLOCOM.2015.7417590.
  26. ^ Abrardo, Andrea; Fodor, Gábor; Tola, Besmir (2015). "Network coding schemes for Device-to-Device communications based relaying for cellular coverage extension" (PDF). 2015 IEEE 16th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC): 670–674. doi:10.1109/SPAWC.2015.7227122.
  27. ^ Gao, Chuhan; Li, Yong; Zhao, Yulei; Chen, Sheng (October 2017). "A Two-Level Game Theory Approach for Joint Relay Selection and Resource Allocation in Network Coding Assisted D2D Communications" (PDF). IEEE Transactions on Mobile Computing. 16 (10): 2697–2711. doi:10.1109/TMC.2016.2642190. ISSN 1558-0660.
  28. ^ Zhou, Ting; Xu, Bin; Xu, Tianheng; Hu, Honglin; Xiong, Lei (1 February 2015). "User‐specific link adaptation scheme for device‐to‐device network coding multicast". IET Communications. 9 (3): 367–374. doi:10.1049/iet-com.2014.0323. ISSN 1751-8636.
  29. ^ Rachuri, Sri Pramodh; Ansari, Ahtisham Ali; Tandur, Deepaknath; Kherani, Arzad A.; Chouksey, Sameer (December 2019). "Network-Coded SD-WAN in Multi-Access Systems for Delay Control". 2019 International Conference on contemporary Computing and Informatics (IC3I): 32–37. doi:10.1109/IC3I46837.2019.9055565.
  30. ^ Ansari, Ahtisham Ali; Rachuri, Sri Pramodh; Kherani, Arzad A.; Tandur, Deepaknath (December 2019). "An SD-WAN Controller for Delay Jitter Minimization in Coded Multi-access Systems". 2019 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS): 1–6. doi:10.1109/ANTS47819.2019.9117981.
  • 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Linear_network_coding&oldid=1081467477"