Using labeled paths for loop-free on-demand routing in ad hoc networks

ABSTRACT

We present the Feasible Label Routing (FLR) protocol for mobilead hoc networks, which uses path information to establish routes to destinations on demand. FLR enables loop-free incremental(hop-by-hop) routing of data packets using only the addresses of their destinations. Like the dynamic source routing (DSR) protocol, FLR avoids the need for any time-stamps or sequence numbers by the use of path vectors exchanged when routes are established or repaired. Instantaneous loop freedom is attained by using path information for a destination as labels with which routers are ordered lexicographically with respect to the destination, i.e., FLR ensures that the labels of routers for a given destination become "smaller" the closer they are to the destination. Simulation experiments in Qualnet show that the performance of FLR is far better than the performance of the ad-hoc on-demand distance vector (AODV) protocol, the dynamic source routing (DSR) protocol, and the optimized link state routing (OLSR) protocol, in terms of the packet delivery ratio and average delivery latencies achieved, as well as the overhead incurred in the network.

REFERENCES

• 1: T. Clausen and P. Jacquet, "Optimized Link State Routing Protocol," Request for Comments 3626, October 2003.
• 2: E. M. Gafni and D. P. Bertsekas, "Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology," IEEE Trans. Comm., COM-29(1):11--18, Jan. 1981.
• 3: J. J. Garcia-Lunes-Aceves, Loop-free routing using diffusing computations, IEEE/ACM Transactions on Networking (TON), v.1 n.1, p.130-141, Feb. 1993 [doi>10.1109/90.222913]
• 4: J. J. Garcia-Luna-Aceves , Marc Mosko , Charles E. Perkins, A new approach to on-demand loop-free routing in ad hoc networks, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.53-62, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872043]
• 5: J. J. Garcia-Luna-Aceves , Marcelo Spohn, Source-Tree Routing in Wireless Networks, Proceedings of the Seventh Annual International Conference on Network Protocols, p.273, October 31-November 03, 1999
• 6: Yih-Chun Hu , David B. Johnson, Implicit source routes for on-demand ad hoc network routing, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501417.501418]
• 7: D. Johnson et al, "The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)," IETF Internet draft, draft-ietf-manet-dsr-09.txt, April 2003.
• 8: R. Ogier et al., "Topology Dissemination Based on Reverse-Path Forwarding (TBRPF)," Request for Comments 3684, February 2004.
• 9: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 10: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 11: C. Perkins et al., "Ad hoc On-Demand Distance Vector (AODV) Routing," Request for Comments 3561, July 2003.
• 12: C. Perkins et al. "Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks," IEEE Personal Communications, 8(1):16 -- 28, Feb 2001.
• 13: J. Raju and J. J. Garcia-Luna-Aceves, "A New Approach to On-Demand Loop-Free Multipath Routing," Proc. IEEE IC3N'99, pp. 522--7, Boston, Massachusetts, Oct. 11--13, 1999.
• 14: S. Roy and J. J. Garcia-Luna-Aceves, " Using Minimal Source Trees for On-Demand Routing in Ad Hoc Networks," Proc. IEEE INFOCOM 2001, Anchorage, Alaska, April 22-26, 2001.
• 15: C. Sengul, "Local Route Recovery in Mobile Ad Hoc Networks," M.S. Thesis, Computer Science, Univ. of Illinois at Urbana-Champaign, 2003.
• 16: Marcelo Spohn , J. J. Garcia-Luna-Aceves, Neighborhood aware source routing, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501417.501419]
• 17: Srinivas Vutukury , J. J. Garcia-Luna-Aceves, A simple approximation to minimum-delay routing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.227-238, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 18: Scalable Network Technologies. Qualnet 3.5.2.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms

Keywords:
ad hoc network, loop-free, path information, routing, routing invariant