Abstract
We present a loop-free, distributed routing protocol for mobile packet radio networks. The protocol is intended for use in networks where the rate of topological change is not so fast as to make “flooding” the only possible routing method, but not so slow as to make one of the existing protocols for a nearly-static topology applicable. The routing algorithm adapts asynchronously in a distributed fashion to arbitrary changes in topology in the absence of global topological knowledge. The protocol's uniqueness stems from its ability to maintain source-initiated, loop-free multipath routing only to desired destinations with minimal overhead in a randomly varying topology. The protocol's performance, measured in terms of end-to-end packet delay and throughput, is compared with that of pure flooding and an alternative algorithm which is well-suited to the high-rate topological change environment envisioned here. For each protocol, emphasis is placed on examining how these performance measures vary as a function of the rate of topological changes, network topology, and message traffic level. The results indicate the new protocol generally outperforms the alternative protocol at all rates of change for heavy traffic conditions, whereas the opposite is true for light traffic. Both protocols significantly outperform flooding for all rates of change except at ultra-high rates where all algorithms collapse. The network topology, whether dense or sparsely connected, is not seen to be a major factor in the relative performance of the algorithms.
Similar content being viewed by others
References
D. Bertsekas and R. Gallager,Data Networks (Prentice-Hall, 1987).
P. Merlin and A. Segall, A failsafe distributed routing protocol, IEEE Trans. Commun. (September 1979).
J. Jaffe and F. Moss, A responsive distributed routing algorithm for computer networks, IEEE Trans. Commun. (July 1982).
J.J. Garcia-Luna-Aceves, A new minimum-hop routing algorithm,Proc. IEEE INFOCOM '87, San Francisco, CA, 1987.
J.J. Garcia-Luna-Aceves, Distributed routing using internodal coordination,Proc. IEEE INFOCOM '88, New Orleans, LA, 1988.
J.J. Garcia-Luna-Aceves, A distributed, loop-free, shortest-path routing algorithm,Proc. IEEE INFOCOM '88, New Orleans, LA, 1988.
J.J. Garcia-Luna-Aceves, A minium-hop routing algorithm based on distributed information, Comp. Networks ISDN Syst. 16(5) (1989).
B. Rajagopolan and M. Faiman, A new responsive distributed shortest-path routing algorithm, ACM Comp. Commun. Rev. 19(4) (1989).
J.J. Garcia-Luna-Aceves, Loop-free routing using diffusing computations, IEEE Trans. Networking 1(1) (1993).
J. McQuillan, Adaptive routing algorithms for distributed computer networks, BBN Rep. 2831, Bolt Beranek and Newman Inc., Cambridge, MA (1974).
R. Coltun, OSPF; An internet routing protocol, ConneXtions 3(8) (1989) 19–25.
J.J. Garcia-Luna-Aceves, Distributed routing with labeled distances,Proc. IEEE INFOCOM '92, Florence, Italy, 1992.
J.J. Garcia-Luna-Aceves, Steady-state response of shortest-path routing algorithms,11th Annual Int. Phoenix Conf. on Comp. and Commun., Scottsdate, AZ, 1992.
B. Awerbuch, A. Bar-Noy and M. Gopal, Approximate distributed Bellmann-Ford algorithms,Proc. IEEE INFOCOM '91, Bal Harbour, FA, 1991.
B. Awerbuch, Distributed dhortest-paths algorithms,Proc. 21st Annual ACM Symp. on Theory of Computing, Seattle, WA, 1989.
B. Awerbuch, Shortest-paths and loop-free routing in dynamic networks, Comp. Commun. Rev. 20(4) (1990).
E. Dijkstra and C. Scholten, Termination detection for diffusing computations, Inform. Process. Lett. 11(1) (1980).
E. Gafni and D. Bertsekas, Distributed algorithms for generating loop-free routes in networks with frequently changing topology, IEEE Trans. Commun (January 1981).
M. Weber (Bates) and A. Ephremides, A simulated performance study of some distributed routing algorithms for mobile radio networks,Proc. Johns Hopkins Conf., Baltimore, MD, 1983.
M.S. Corson and A. Ephremides, A distributed routing algorithm for mobile radio networks,Proc. 1989 IEEE Military Communications Conf., Boston, MA, 1989.
A. Ephremides, J. Wieselthier and D. Baker, A design concept for reliable mobile radio networks with frequency hopping signaling, Proc. IEEE (January 1987).
B. Awerbuch, B. Patt-Shamir and G. Varghese, Bounding the unbounded,Proc. IEEE INFOCOM '94.
Author information
Authors and Affiliations
Additional information
The work of A. Ephremides was supported in part by the National Science Foundation under grants D-CDR-8803012 and EEC94-02384.
Rights and permissions
About this article
Cite this article
Corson, M.S., Ephremides, A. A distributed routing algorithm for mobile wireless networks. Wireless Netw 1, 61–81 (1995). https://doi.org/10.1007/BF01196259
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01196259