Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Design for Optimizability: Traffic Management of a Future Internet Kapitel lesen Erstes Kapitel lesen

2010 | OriginalPaper | Buchkapitel

15. Network Coding and Its Applications in Communication Networks

verfasst von : Alex Sprintson

Erschienen in: Algorithms for Next Generation Networks

Verlag: Springer London

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The network coding technique generalizes the traditional routing approach by allowing the intermediate network nodes to create new packets by combining the packets received over their incoming edges. This technique has several important benefits such as an increase in throughput and an improvement in the reliability and robustness of the network. The goal of this chapter is to present a tutorial review of the network coding technique, the practical implementation of network coding, as well as its applications in several areas of networking. We begin by presenting the encoding model and the algebraic framework for network code construction. Next, we discuss efficient deterministic and randomized algorithms for construction of feasible network codes in multicast networks. Next, we present practical implementation schemes and discuss the applications of network coding in content distribution networks, peer-to-peer networks, and wireless networks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Algebraic Approaches for Scalable End-to-End Monitoring and Diagnosis
Nächstes Kapitel Next Generation Search
Fußnoten
1
A Steiner tree is a tree that connects the source node with the terminals and may include any number of other nodes.
 
2
For a definition of finite field see, e.g., [31].
 
3
A cut in a graph G(V,E) is a partition of the nodes of V into two subsets V 1 and V ∖ V 1 . We say that a cut C = (V 1 ,V ∖ V 1 ) separates nodes s and t if s ∈ V 1 and t ∈ V ∖ V 1.
 
4
A matrix T called nilpotent if there exists some positive integer n such that T n is a zero matrix.
 
5
A topological order is a numbering of the vertices of a directed acyclic graph such that every edge e(v, u) ∈ E satisfies v < u.
 
6
Some efficient coding schemes require slightly more than k packets to decode the file.
 
Literatur
1.
R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung. Network Information Flow. IEEE Transactions on Information Theory, 46(4):1204–1216, 2000.MathSciNetMATHCrossRef
2.
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Networks Flows. Prentice-Hall, NJ, USA, 1993.
3.
Z. Bar-Yossef, Y. Birk, T. S. Jayram, and T. Kol. Index Coding with Side Information. In Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science, pages 197–206, 2006.
4.
A. Barbero and O. Ytrehus. Cycle-logical Treatment for “Cyclopathic Networks”. IEEE/ACM Transactions on Networking, 14(SI):2795–2804, 2006.MathSciNet
5.
J. W. Byers, M. Luby, M. Mitzenmacher, and A. Rege. A Digital Fountain Approach to Reliable Distribution of Bulk Data. SIGCOMM Comput. Commun. Rev., 28(4):56–67, 1998.CrossRef
6.
S. Chachulski, M. Jennings, S. Katti, and D. Katabi. MORE: Exploiting Spatial Diversity with Network Coding. In MIT CSAIL Technical Report, 2006.
7.
M. Charikar and A. Agarwal. On the Advantage of Network Coding for Improving Network Throughput. In Proceedings of IEEE Information Theory Workshop, San Antonio, 2004.
8.
M. Chaudhry and A. Sprintson. Efficient Algorithms for Index Coding. Computer Communications Workshops, 2008. INFOCOM. IEEE Conference on, pages 1–4, April 2008.
9.
P. Chou and Y. Wu. Network Coding for the Internet and Wireless Networks. Signal Processing Magazine, IEEE, 24(5):77–85, Sept 2007.CrossRef
10.
P. A. Chou, Y. Wu, and K. Jain. Practical Network Coding. In Proceedings of Allerton Conference on Communication, Control, and Computing, Monticello, IL, October 2003.
11.
R. Dougherty, C. Freiling, and K. Zeger. Insufficiency of Linear Coding in Network Information Flow. IEEE Transactions on Information Theory, 51(8):2745–2759, 2005.MathSciNetCrossRef
12.
E. Erez and M. Feder. Convolutional Network Codes. In IEEE International Symposium on Information Theory, 2004.
13.
C. Fragouli and E. Soljanin. Network Coding Fundamentals. Now Publishers, Inc, 2007.
14.
C. Gkantsidis, J. Miller, and P. Rodriguez. Anatomy of a P2P Content Distribution System with Network Coding. In IPTPS’06, February 2006.
15.
C. Gkantsidis, J. Miller, and P. Rodriguez. Comprehensive View of a Live Network Coding P2P System. In IMC ’06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, pages 177–188, 2006.
16.
C. Gkantsidis and P. Rodriguez. Network Coding for Large Scale Content Distribution. INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 4:2235–2245 vol. 4, March 2005.CrossRef
17.
T. Ho. Networking from a Network Coding Perspective. Dissertation, Massachusetts Institute of Technology, 2004.
18.
T. Ho, R. Koetter, M. Medard, D. Karger, and M. Effros. The Benefits of Coding over Routing in a Randomized Setting. In Proceedings of the IEEE International Symposium on Information Theory, 2003.
19.
T. Ho and D. S. Lun. Network Coding: An Introduction. Cambridge University Press, Cambrige, UK, 2008.CrossRef
20.
S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. Medard, and M. Effros. Resilient Network Coding in the Presence of Byzantine Adversaries. IEEE Transactions on Information Theory, 54(6):2596–2603, June 2008.MathSciNetCrossRef
21.
S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen. Polynomial Time Algorithms for Multicast Network Code Construction. IEEE Transactions on Information Theory, 51(6):1973–1982, June 2005.MathSciNetCrossRef
22.
S. Katti, D. Katabi, W. Hu, H. S. Rahul, and M. Médard. The Importance of Being Opportunistic: Practical Network Coding for Wireless Environments. In 43rd Annual Allerton Conference on Communication, Control, and Computing, Allerton, 2005.
23.
S. Katti, H. Rahul, D. Katabi, W. H. M. Médard, and J. Crowcroft. XORs in the Air: Practical Wireless Network Coding. In ACM SIGCOMM, Pisa, Italy, 2006.
24.
R. Koetter and F. Kschischang. Coding for Errors and Erasures in Random Network Coding. Information Theory, IEEE Transactions on, 54(8):3579–3591, Aug. 2008.MathSciNetCrossRef
25.
R. Koetter and M. Medard. An Algebraic Approach to Network Coding. IEEE/ACM Transactions on Networking, 11(5):782 – 795, 2003.CrossRef
26.
M. Langberg and A. Sprintson. On the Hardness of Approximating the Network Coding Capacity. Information Theory, 2008. ISIT 2008. IEEE International Symposium on, pages 315–319, July 2008.
27.
A. Lehman and E. Lehman. Complexity Classification of Network Information Flow Problems. In Proceedings of SODA, 2004.
28.
S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear Network Coding. IEEE Transactions on Information Theory, 49(2):371 – 381, 2003.MathSciNetMATHCrossRef
29.
Z. Li and B. Li. Network Coding in Undirected Networks. In Proceedings of 38th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, USA, 2004.
30.
Z. Li, B. Li, D. Jiang, and L. C. Lau. On Achieving Optimal Throughput with Network Coding. INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 3:2184–2194 vol. 3, March 2005.
31.
R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 2nd edition, 1997.
32.
E. Lubetzky and U. Stav. Non-linear Index Coding Outperforming the Linear Optimum. In Proceedings of 48th Annual IEEE Symposium on Foundations of Computer Science, pages 161–168, 2007.
33.
M. Médard, M. Effros, T. Ho, and D. Karger. On Coding for Non-multicast Networks. In 41st Annual Allerton Conference on Communication Control and Computing, Oct. 2003.
34.
Y. W. P. A. Chou and K. Jain. Network Coding for the Internet. In IEEE Communication Theory Workshop, Capri, Italy, 2004.
35.
D. Silva, F. Kschischang, and R. Koetter. A Rank-Metric Approach to Error Control in Random Network Coding. Information Theory, IEEE Transactions on, 54(9):3951–3967, Sept. 2008.MathSciNetCrossRef
36.
Y. Wu, P. Chou, and S.-Y. Kung. Minimum-Energy Multicast in Mobile Ad Hoc Networks Using Network Coding. IEEE Transactions on Communications, 53(11):1906–1918, Nov. 2005.CrossRef
37.
R. Yeung. Information Theory and Network Coding. Springer, 2008.
Metadaten
Titel
Network Coding and Its Applications in Communication Networks
verfasst von
Alex Sprintson
Copyright-Jahr
2010
Verlag
Springer London
Buch
Algorithms for Next Generation Networks

Print ISBN: 978-1-84882-764-6

Electronic ISBN: 978-1-84882-765-3

Copyright-Jahr: 2010

DOI
https://doi.org/10.1007/978-1-84882-765-3_15