Making link-state routing scale for ad hoc networks

ABSTRACT

In this paper, we introduce a class of approaches that attempt to scale link-state routing by limiting the scope of link state update dissemination in space and over time. We present the first fundamental analysis of this generic class, which we call "Fuzzy Sighted Link State routing". Using a novel perspective on the "overhead"of a protocol that includes not only the overhead due to control messages but also due to route sub-optimality, we formulate an analytical model whose solution automatically leads to the best algorithm in this class. This algorithm is shown to have nearly the best possible asymptotic overhead for any routing algorithm -proactive or reactive. Simulation results are presented that compare the performance or several algorithms in this class

REFERENCES

• 1: Andrew S. Tanenbaum, Computer networks (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 2: B. Bellur, R. Ogier, "A Reliable, Efficient Topology Broadcast Algorithm for Dynamic Networks," Proc. IEEE INFOCOM, 1999.
• 3: P. Jacquet, P. Muhlethaler, and A. Quayyum, "Optimized link state routing protocol", IETF MANET Working Group Internet-Draft, Work in Progress
• 4: 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
• 5: Ram Ramanathan , Martha Steenstrup, Hierarchically-organized, multihop mobile wireless networks for quality-of-service support, Mobile Networks and Applications, v.3 n.1, p.101-119, June 1998 [doi>10.1023/A:1019148009641]
• 6: B. A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, "Scalable Routing Strategies for Ad Hoc Wireless Networks". IEEE Journal of Selected Areas on Communications, vol. 17, no. 8, Aug. 1999.
• 7: Gregory S. Lauer, Packet-radio routing, Routing in communications networks, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1995
• 8: D. B. Johnson and D. Maltz,"Dynamic Source Routing in Ad Hoe Wireless Networks.", In Mobile Computing, edited by Tomasz Imielinski and Hank Korth. Kluwer Academic Publishers, 1995.
• 9: C. Perkins. "Ad-Hoc On-Demand Distance Vector Routing". MILCOM'97 panel on Ad-Hoc Networks, Monterey, CA, November 3, 1997.
• 10: Stefano Basagni , Imrich Chlamtac , Violet R. Syrotiuk , Barry A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.76-84, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288254]
• 11: Zygmunt J. Haas , Marc R. Pearlman, The performance of query control schemes for the zone routing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-177, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 12: P. Jacquet and L. Viennot, 'Overhead in Mobile Ad-hoc Network Protocols", INRIA Research Report 3965, Institut National de Recherche en Informatique et en Automatique (INRIA), France, June 2000.
• 13: R. Guerin, et. al., "Equivalent Capacity and Its Applications to Bandwidth Allocation in High Speed Networks," IEEE Journal of Selected Areas on Communications, vol. 9, no. 7, pp. 968-981, Sept. 1991.
• 14: R. Ramanathan and R. Hain, "Topology Control of Multihop Radio Networks using Transmit Power Adjustment," in Proceedings of IEEE Infoeom'2000, Tel Aviv, Israel, 2000
• 15: A. B. McDonald and T.F. Znati. "A Mobility Based Framework for Adaptive Clustering in Wireless Ad Hoc Networks". IEEE Journal of Selected Areas on Communications, vol. 17, no. 8, Aug. 1999.
• 16: C. Santivanez, "Asymptotic Behavior of Mobile Ad Hoc Routing Protocols with respect to Traffic, Mobility, and Size," Technical Report TR-CDSP-O0-52, CDSP Center, Northeastern University, Boston, MA, October 2000. Available at http: / /www.cdsp.neu.edu/info /students /cesar / analysis.ps.gz
• 17: C. Santivanez, R. Ramanathan, "Hazy Sighted Link State (HSLS) Routing: A Scalable Link State Algorithm", BBN technical memo BBN-TM-I30I, B BN technologies, Cambridge, MA, August 2001. Available at http://www.ir.bbn.com/documents/techmemos/index.html

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Performance