Network coding for efficient communication in extreme networks

ABSTRACT

Some forms of ad-hoc networks need to operate in extremely performance-challenged environments where end-to-end connectivity is rare. Such environments can be found for example in very sparse mobile networks where nodes "meet" only occasionally and are able to exchange information, or in wireless sensor networks where nodes sleep most of the time to conserve energy. Forwarding mechanisms in such networks usually resort to some form of intelligent flooding, as for example in probabilistic routing.We propose a communication algorithm that significantly reduces the overhead of probabilistic routing algorithms, making it a suitable building block for a delay-tolerant network architecture. Our forwarding scheme is based on network coding. Nodes do not simply forward packets they overhear but may send out information that is coded over the contents of several packets they received. We show by simulation that this algorithm achieves the reliability and robustness of flooding at a small fraction of the overhead.

REFERENCES

• 1: R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, July 2000.
• 2: P. A. Chou, Y. Wu, and K. Jain. Practical network coding. In Proc. Allerton, Oct. 2003.
• 3: P. T. Eugster, R. Guerraoui, A.-M. Kermarrec, and L. Massoulie. Epidemic information dissemination in distributed systems. IEEE Computer, 37(5):60--6, May 2004.
• 4: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 5: K. Fall. Messaging in difficult environments. Technical Report IRB-TR-04-019, Intel Research Berkeley, Dec. 2004.
• 6: Z. J. Haas, J. Y. Halpern, and L. Li. Gossip-based ad hoc routing. In Proc. IEEE Infocom, June 2002.
• 7: S. M. Hedetniemi, S. T. Hedetniemi, and A. Liestman. A survey of gossiping and broadcasting in communication networks. Networks, 18(129-134), 1988.
• 8: T. Ho, B. Leong, M. Medard, R. Koetter, Y. Chang, and M. Effros. On the utility of network coding in dynamic enviornments. In Proc. International Workshop on Wireless Ad-hoc Networks, June 2004.
• 9: T. Ho, M. Médard, J. Shi, M. Effros, and D. R. Karger. On randomized network coding. In Proc. Allerton, Oct. 2003.
• 10: S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen. Polynomial time algorithms for multicast network code construction. submitted to IEEE Transactions on Information Theory, July 2003.
• 11: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 12: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 13: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 14: S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. IEEE Transactions on Information Theory, Feb. 2003.
• 15: Chae Hoon Lim , Pil Joong Lee, More Flexible Exponentiation with Precomputation, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.95-107, August 21-25, 1994
• 16: A. Lindgren, A. Doria, and O. Schelén. Probabilistic routing in intermittently connected networks. In Proc. SAPIR Workshop, Aug. 2004.
• 17: M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman. Efficient erasure correcting codes. IEEE Transactions on Information Theory, 47(2):569--584, 2001.
• 18: J. Luo, P. T. Eugster, and J.-P. Hubaux. Route driven gossip: Probabilistic reliable multicast in ad hoc networks. In IEEE Infocom, pages 2229--2239, San Francisco, CA, Mar. 2003.
• 19: Peter Sanders , Sebastian Egner , Ludo Tolhuizen, Polynomial time algorithms for network information flow, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777464]
• 20: Y. Sasson, D. Cavin, and A. Schiper. Probabilistic broadcast for flooding in wireless mobile ad hoc networks. In Proc. IEEE WCNC, Mar. 2003.
• 21: James P. G. Sterbenz , Rajesh Krishnan , Regina Rosales Hain , Alden W. Jackson , David Levin , Ram Ramanathan , John Zao, Survivable mobile wireless networks: issues, challenges, and research directions, Proceedings of the 3rd ACM workshop on Wireless security, p.31-40, September 28-28, 2002, Atlanta, GA, USA [doi>10.1145/570681.570685]
• 22: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, Apr. 2000.
• 23: J. Widmer, C. Fragouli, and J.-Y. Le Boudec. Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding. In Proc. Workshop on Network Coding, Theory, and Applications, Apr. 2005.
• 24: Y. Wu, P. A. Chou, and S.-Y. Kung. Minimum-energy multicast in mobile ad hoc networks using network coding. In Proc. IEEE Information Theory Workshop, Oct. 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Performance

Keywords:
delay-tolerant network, network coding