Continuing the enterprise of research in re-architecting the future
Internet, I have started to delve into the world of “network coding”, a recent field of study (Ahlswede, 2000) that aims at solving an “information flow problem”
by leveraging forwarding nodes in a network with “content mixing” capabilities of data flows (packets) in addition to simply forwarding operations.
Even though the practical usage of network coding has yet to be proven in many real networking scenarios, network coding is being considered by major research industry players as part of the next wave of networking.
The promise of network coding? Gains in terms of network throughput, resilience, security, simplicity… an alternative path to the current practices of boosting network performance, which is basically limited on new networking hardware versions with increased chip rate and memory sizes.
In my opinion, network coding applied to future inter-networking architectures is an example of research by questioning paradigms and has the potential to introduce another shift in internetworking with an impact comparable to the information theory work of Shannon 60 years ago.
In this post, I will not introduce gratuitous maths and non-rigorous explanation on network coding (please refer to the wast
literature, specially a book for theoreticians and and another one for practitioners). The point I want to make is some key observations that make me believe that network coding is an area worth of exploring for any future networking research project:
- Big computer industry players (e.g., Microsoft, HP, Intel) are investing in network-coding applied research. There may be something ($$$) beyond pure academic research.
- Pioneering research institutions around the world (e.g., Berkeley, MIT) are increasingly publishing the practical results of ongoing research projects.
- Network coding is meeting legacy network settings, e.g., the TCP protocol (Sundajaran et al, INFOCOM ‘09). We may see further “transparent” integration of network coding in real systems.
So far, so good. But, network coding is a tricky area. Even though it’s basic concept and the canonical example over a butterfly type of network is pretty simple, the actual field where network coding can be apply and the implementation options is very broad, spanning over all the layers of the traditional network stack:
- Application: Content distribution and P2P systems. The best example is Avalanche by Microsoft Research – related work ). The version applied in real life is called Secure Content Distribution (MSCD) and was trialed recently by to download a new release of Microsoft Visual Studio 2008. R2:Live Peer-to-Peer Streaming.
- Transport: Network coding meets TCP: A new interpretation of ACKs (revealing newly degrees of freedom). Although, in the paper, coding seems to be E2E, the term NC is used as the coding could be at the end-host or inside the network.
- Network: Practical Network Coding (Chou, 2003)
- Link: XORs in the air, Network Coding forWireless Mesh Networks: A Case Study, MORE:Trading Structure for Randomness in Wireless Opportunistic Routing
- Physical: Network Coding-based Protection Strategies Against a Single Link Failure in Optical Networks, Symbol-level Network Coding for Wireless Mesh Networks, Efficient, Fault-Tolerant All-Optical Multicast Networks via Network Coding, Network Coding in a Multicast Switch
I admit a taxonomy based on layers is blury below the network level, where “practical network coding” by Chou et al introduced the notion of mixing packets within generations.
Skepticism is also there (How Practical is Network Coding?). Or should I say good sense (“Mixing Packets: Pros and Cons of Network Coding”). We may assist to some phase of delusion surrounding network coding, if a typical Gartner’s hype cycle can be applied to the field of research.
Question to the community? In which phase would you say is network coding (if research were a technology product)?
- “Technology Trigger”
- “Peak of Inflated Expectations”
- “Trough of Disillusionment”
I have my own list of questions when thinking about the practicality (implementability) of network coding:
- How to decide which information to mix when operating over multiple flows?
- How to carry effciently the coding operations to the final data consumers?
- How to achieve butterfly type of network paths in the information-oriented network under sonsideration?
- Differences and similitudes of network coding over wireless networks compared to wired deployments?
- Feedback channel and applicability in two-way communications (real and non-real time)?
- Security advantages and implications of network coding?
- Interactions with active caching functionalities at multiple levels (packets, pages, documents)?
I will start thinking small, listing the requirements (e.g., multi-paths, identifier space, meaningfulness of packet generation, packet
headers) to perform a strawman approach for network coding in the context of information-oriented networking (e.g., the PSIRP project). Then, we can evaluate the costs and the practical benefits by extensive ns-3 simulations and may be some NetFPGA test implementations.
Whether network coders will eventually supplant routers in large, shared infrastructures like the Internet is very questionable, may be
in the long term as an additional network service… However, I think that we will se more and more real life (niche?) solutions implementing some flavour of network coding. Let it be an IPTV multicast deployment, or Instant Messaging dissemination protocols, error correction algorithms, switch designs or new variants of P2Pcontent distribution schemes like Microsoft’s Avalanche…
I am curious if Rudolf Ahlswede of the University of Bielefeld, Germany could imagine the impact of his research back in
2000. In this post, I have raised more questions than answers. Hopefully, I can turn this over during this promising 2009.
To end with, an optimistic quote of network coding experts:
“By changing how networks function, network coding may influence society in ways we cannot yet imagine.”
say FFROS, KOETTER and MÉDARD.
-Ch.
P.D: I found another optimistic (press-type) reference related to the information-oriented research area: PcMag includes the Van Jacobsen’s content-centric networking (CCN) as one of the “five ideas that will reinvent modern computing“, although I dislike very much the term “Extreme Peer-to-Peer” used by the PcMAg redactors.
P.D2: I could not resist not to google what the blogsphere has also commented on this topic:
- Back to Research: Network Coding and a Small Riddle for You
- Network Coding for Mobile Phones
- Do you know more?
Selected publications on network coding:
- Network Information Flow. R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung in IEEE Transactions on Information Theory, Vol. 46, No. 4, pages 1204-1216; July 2000.
- T. Ho and D. S. Lun. “Network Coding: An Introduction. Cambridge University Press, Cambridge, U.K., April 2008.
- Fragouli, C. and Soljanin, E. 2007. Network coding applications. Found. Trends Netw. 2, 2 (Jan. 2007), 135-269. DOI= http://dx.doi.org/10.1561/1300000013
- Information Theory and Network Coding by Raymond W. Yeung, The Chinese University of Hong Kong, Springer, August 2008
- Linear Network Coding. S.-Y. R. Li, R. W. Yeung and N. Cai in IEEE Transactions on Information Theory, Vol. 49, No. 2, pages 371-381; February 2003.
- An Algebraic Approach to Network Coding. R. Koetter and M. M?dard in IEEE/ACM Transactions on Networking, Vol. 11, No. 5, pages 782-795; October 2003.
- Polynomial Time Algorithms for Multicast Network Code Construction. S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain and L.M.G.M. Tolhuizen in IEEE Transactions on Information Theory, Vol. 51, No. 6, pages 1973-1982; June 2005.
- T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi and B. Leong. A Random Linear Network Coding Approach to Multicast. In IEEE Transactions on Information Theory, Vol. 52, No. 10, pages 4413-4430; October 2006.
- Jay Kumar Sundararajan and Devavrat Shah and Muriel Medard and Michael Mitzenmacher and João Barros. Network coding meets TCP. CoRR, (abs/0809.5022) 2008. [BibSonomy: dblp] URL
- P. Chou, Y. Wu, and K. Jain, “Practical network coding,” 2003. [Online]. Available: http://citeseer.ist.psu.edu/chou03practical.html
- Barros, J.; “Mixing Packets: Pros and Cons of Network Coding”, Proc Wireless Personal Multimedia Communications Symp. – WPMC, Lapland, Finland, September, 2008.
-Ch.
