skip to main content
10.1145/872035.872043acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
Article

A new approach to on-demand loop-free routing in ad hoc networks

Published: 13 July 2003 Publication History

Abstract

A new protocol is presented for on-demand loop-free routing in ad hoc networks. The new protocol, called labeled distance routing (LDR) protocol, uses a distance invariant to establish an ordering criterion and per-destination sequence numbers to reset the invariant resulting in loop-freedom at every instant. The distance invariant allows nodes to change their next hops or distances to destinations without creating routing-table loops. The destination sequence number, which only the destination may increment, permits nodes to reset the values of their distance invariants. The performance of LDR is compared against the performance of three other protocols that are representative of the state-of-the art, namely AODV, DSR and OLSR.

References

[1]
L. Bajaj et al. GloMoSim: A scalable network simulation environment. Technical Report 990027, UCLA Computer Science Department, 1999.]]
[2]
T. Clausen et al. Optimized link state routing protocol. IETF Internet draft, draft-ietf-manet-olsr-06.txt, Sep 2001.]]
[3]
E. W. Dijkstra and C. S. Scholten. Termination detection for diffusing computations. Information Processing Letters, 11(1):1--4, Aug. 1980.]]
[4]
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.]]
[5]
J. Garcia-Luna-Aceves and S. Murthy. A path finding algorithm for loop-free routing. IEEE/ACM Trans. Networking, 5(1):148--160, Feb. 1997.]]
[6]
J. J. Garcia-Luna-Aceves and M. Spohn. Source-tree routing in wireless networks. In Proc. IEEE ICNP'99, pp. 273--82, Oct. 1999.]]
[7]
J. J. Garcia-Lunes-Aceves. Loop-free routing using diffusing computations. IEEE/ACM Transactions on Networking, 1(1):130--41, Feb. 1993.]]
[8]
D. Johnson et al. The dynamic source routing protocol for mobile ad hoc networks (DSR). IETF Internet draft, draft-ietf-manet-dsr-07.txt, Feb 2002.]]
[9]
D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, volume 353. Kluwer Academic Publishers, 1996.]]
[10]
R. Ogier et al. Topology broadcast based on reverse-path forwarding (TBRPF). IETF Internet draft, draft-ietf-manet-tbrpf-05.txt, Mar 2001.]]
[11]
V. D. Park and M. S. Corson. A highly adaptive distributed routing algorithm for mobile wireless networks. In IEEE INFOCOM, pp. 1405--13 vol. 3, Apr. 1997.]]
[12]
C. Perkins, E. Belding-Royer, and S. Das. Ad hoc on demand distance vector (AODV) routing. IETF Internet draft, draft-ietf-manet-aodv-10.txt, Mar 2002.]]
[13]
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.]]
[14]
A. Plakoo and A. Laouiti. INRIA OLSR draft 3 linux source code. http://menetou.inria.fr/olsr/#code, ported by Marco Spohn, 2001.]]
[15]
J. Raju and J. J. Garcia-Luna-Aceves. A new approach to on-demand loop-free multipath routing. In IEEE IC3N'99, pp. 522--7, Oct. 1999.]]
[16]
M. Spohn and J. J. Garcia-Luna-Aceves. Neighborhood aware source routing. In ACM MOBIHOC 2001, pp. 11--21, Oct. 2001.]]
[17]
S. Vutukury and J. Garcia-Luna-Aceves. A simple approximation to minimum-delay routing. In Proc. AMC SIGCOMM 1999, pp. 227--238, Sept. 1999.]]

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing
July 2003
380 pages
ISBN:1581137087
DOI:10.1145/872035
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 July 2003

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. ad hoc network
  2. distance invariant
  3. loop-free
  4. routing

Qualifiers

  • Article

Conference

PODC03
Sponsor:

Acceptance Rates

PODC '03 Paper Acceptance Rate 51 of 226 submissions, 23%;
Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)1
Reflects downloads up to 12 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Throwboxes in delay tolerant networksJournal of Network and Computer Applications10.1016/j.jnca.2017.04.00491:C(89-103)Online publication date: 1-Aug-2017
  • (2016)Traces and t-Distribution Based Multi-Copy Routing in Delay Tolerant Networks2016 12th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN)10.1109/MSN.2016.043(222-227)Online publication date: Dec-2016
  • (2013)VAPRIEEE Transactions on Mobile Computing10.1109/TMC.2012.5312:5(895-908)Online publication date: 1-May-2013
  • (2013)Energy Efficient Routing in Wireless Sensor NetworksNext-Generation Wireless Technologies10.1007/978-1-4471-5164-7_8(131-157)Online publication date: 2013
  • (2011)Energy-Aware Routing Protocol for Delay Tolerant NetworksDelay Tolerant Networks10.1201/b11309-4(69-100)Online publication date: 28-Nov-2011
  • (2011)An interest-driven approach for unicast routing in MANETs with labeled paths and proactive path maintenance2011 IEEE Wireless Communications and Networking Conference10.1109/WCNC.2011.5779266(962-967)Online publication date: Mar-2011
  • (2009)Routing Scalability in MANETsHandbook on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless, and Peer-to-Peer Networks10.1201/9780203323687.ch2Online publication date: 9-Nov-2009
  • (2008)Routing Protocols in Intermittently Connected Mobile Ad Hoc Networks and Delay‐Tolerant NetworksAlgorithms and Protocols for Wireless and Mobile Ad Hoc Networks10.1002/9780470396384.ch8(219-250)Online publication date: 26-Mar-2008
  • (2006)Cluster Overlay Broadcast (COB)IEEE Transactions on Mobile Computing10.1109/TMC.2006.735:6(653-667)Online publication date: 1-Jun-2006
  • (2006)Ad Hoc Routing with Distributed Ordered SequencesProceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications10.1109/INFOCOM.2006.200(1-12)Online publication date: Apr-2006
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media