Routing Algorithm for a Clustered Network

Authors: Hemanth KumarA.R, Sudhakara G., Satyanarayana B.S.

Abstract:

The Cluster Dimension of a network is defined as, which is the minimum cardinality of a subset S of the set of nodes having the property that for any two distinct nodes x and y, there exist the node Si, s2 (need not be distinct) in S such that ld(x,s1) — d(y, s1)1 > 1 and d(x,s2) < d(x,$) for all s E S — {s2}. In this paper, strictly non overlap¬ping clusters are constructed. The concept of LandMarks for Unique Addressing and Clustering (LMUAC) routing scheme is developed. With the help of LMUAC routing scheme, It is shown that path length (upper bound)PLN,d < PLD, Maximum memory space requirement for the networkMSLmuAc(Az) < MSEmuAc < MSH3L < MSric and Maximum Link utilization factor MLLMUAC(i=3) < MLLMUAC(z03) < M Lc

Keywords: Metric dimension, Cluster dimension, Cluster.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329653

References:

[1] E. Gafni,D.P. Bertsekas, Distributed Algorithms for generating loop-free Routes With frequently changing Topology, IEEE Trans. On Com-munications, Vol. Com-29, no. 1, pp. 11-18, January, 1981.
[2] J. J. Garcia-Luna-Aceves, A Unified Approach to Loop-Free Routing Algorithm Using Distance Vectors or Link States, Proc.ACM Sigcomm Symposium on Communication,Architectures and Protocols, pp. 212¬223, September, 1989.
[3] J. M. Jane,F. M. Moss, A Responsive Routing Algorithm for Computer Networks, IEEE Trans. On Communications, pp. 1758-1762, July, 1982.
[4] J. Mcquillan, Adaptive Routing Algorithm for Distributed Computer Networks, BBN Report 2331, BBN, Cambridge,MA, 1974.
[5] 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.
[6] J. M. Mcquillan, D. C. Walden, The Arpanet work design decisions,Computer Computer networks, vol.1,No.5, pp. 243-289, August, 1977.
[7] M. Schwartz, T. E. Stern, Routing Techniques used in Communication Networks, IEEE Trans. On Communications, pp. 539-552, April, 1980.
[8] C. Perkins, P. Bhagwat, Highly Dynamic Destination Sequenced Dis¬tance Vector Routing (dsdv) for Mobile Computers, Proc. Acm Sigcomm Symposium on Communication , Architectures and Protocols, pp. 234-244, September, 1994.