A cluster-based approach for routing in dynamic networks

ABSTRACT

The design and analysis of routing protocols is an important issue in dynamic networks such as packet radio and ad-hoc wireless networks. Most conventional protocols exhibit their least desirable behavior for highly dynamic interconnection topologies. We propose a new methodology for routing and topology information maintenance in dynamic networks. The basic idea behind the protocol is to divide the graph into a number of overlapping clusters. A change in the network topology corresponds to a change in cluster membership. We present algorithms for creation of clusters, as well as algorithms to maintain them in the presence of various network events. Compared to existing and conventional routing protocols, the proposed cluster-based approach incurs lower overhead during topology updates and also has quicker reconvergence. The effectiveness of this approach also lies in the fact that existing routing protocols can be directly applied to the network --- replacing the nodes by clusters.

REFERENCES

• 1: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 2: I. Castineyra , N. Chiappa , M. Steenstrup, The Nimrod Routing Architecture, RFC Editor, 1996
• 3: M. Scott Corson , Anthony Ephremides, A distributed routing algorithm for mobile wireless networks, Wireless Networks, v.1 n.1, p.61-81, Feb. 1995 [doi>10.1007/BF01196259]
• 4: [4] W. Diepstraten, G. Ennis, P. Bellanger, "DFWMAC - Distributed Foundation Wireless Medium Access Control," IEEE Document P802.11-93/190, Nov., 1993.
• 5: [5] E. Gafni, D. P. Bertsekas, "Distributed Algorithms for Generating Loop-free Routes with Frequently Changing Topology," IEEE Trans. on Communications , Vol. COM-29, No. 1, pp. 11-18, January, 1981.
• 6: [6] J. J. Garcia-Luna-Aceves, "Analysis of Routing Strategies for Packet Radio Networks," Proc. IEEE INFOCOM, pp. 292-302, May, 1985.
• 7: J. J. Garcia-Luna-Aceves, A unified approach to loop-free routing using distance vectors or link states, Symposium proceedings on Communications architectures & protocols, p.212-223, September 25-27, 1989, Austin, Texas, United States
• 8: 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]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 11: [11] Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, Cambridge, Massachusetts, 1985.
• 12: C. L. Hedrick, Routing Information Protocol, RFC Editor, 1988
• 13: [13] K. Ishida, "Space-Time Tradeoff in Hierarchical Routing Schemes," Responsive Computer Systems, edited by H. Kopetze and Y. Kakuda, Springer Verlag, NY, pp. 147-163, 1993.
• 14: [14] J. M. Jaffe, F. M. Moss, "A Responsive Routing Algorithm for Computer Networks," IEEE Trans. on Communications, pp. 1758-1762, July, 1982.
• 15: [15] David B. Johnson, "Routing in Ad Hoc Networks of Mobile Hosts," Proc. of Workshop on Mobile Computing Systems and Applications, pp. December, 1994.
• 16: [16] J. Jubin, J. D. Tornow, "The DARPA Packet Radio Network Protocols," Proceedings of the IEEE, Vol. 75, No. 1, pp. 21-32, January, 1987.
• 17: [17] F. Kamoun, "Design Considerations for Large Computer Communication Networks," UCLAENG-7642, Computer Science Department, School of Engineering and Applied Science, University of California, Los Angeles, March, 1976.
• 18: [18] P. R. Karn, H. E. Price, R. J. Diersing, "Packet Radio in the Amateur Service," IEEE Journal on Selected Areas in Communications, Vol. 3, No. 3, pp. 431-439, May, 1985.
• 19: P. Krishna , Mainak Chatterjee , Nitin H. Vaidya , Dhiraj K. Pradhan, A Cluster-based Approach for Routing in Ad-Hoc Networks, Proceedings of the 2nd Symposium on Mobile and Location-Independent Computing, p.1-10, April 10-11, 1995
• 20: [20] G. Lauer, "Hierarchial Routing Design for SURAN," Proceedings of ICC, pp. 93-101, 1986.
• 21: [21] J. M. McQuillan, D. C. Walden, "The ARPA Network Design Decisions," Computer Networks, Vol. 1, No. 5, pp. 243-289, August, 1977.
• 22: [22] J. McQuillan, "Adaptive Routing Algorithm for Distributed Computer Networks," BBN Report 2331, BBN, Cambridge, MA, 1974.
• 23: [23] J. M. McQuillan, I. Richer, E. C. Rosen, "The New Routing Algorithm for ARPANET," IEEE Trans. on Communications, Vol. 28, No. 5, pp. 711-719, May, 1980.
• 24: Shree Murthy , J. J. Garcia-Luna-Aceves, A routing protocol for packet radio networks, Proceedings of the 1st annual international conference on Mobile computing and networking, p.86-95, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215560]
• 25: 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
• 26: [26] C. V. Ramamoorthy, A. Bhide, J. Srivastava, "Reliable Clustering Techniques for Large, Mobile Packet Radio Networks," Proc. IEEE INFOCOM, pp. 218- 226, May, 1987.
• 27: [27] M. Schwartz, T. E. Stern, "Routing Techniques used in Communication Networks," IEEE Trans. on Communications, pp. 539-552, April, 1980.
• 28: [28] Nachum Shacham, "Organization of Dynamic Radio Network by Overlapping Clusters: Architecture, Considerations, and Optimization," Performance, December, 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Measurement, Performance, Theory, Verification