Routing Table Optimization Using T-Spanner Technique

Abstract

Dynamically changing graphs are used in various applications of graph algorithms. The scope of these graphs is in graphics, in communication networks and VLSI design where graphs are subjected to change, such as addition and deletion of links and nodes. There is a rich body of the algorithms and data structures used for dynamic graphs. The thesis contains techniques and data structures used in various dynamic algorithms. There are many applications in distributed systems and communication networks where spanner appears as the underlying graph structures. For instance in dynamically changing graphs where the edge weights are changing can be visualized as a communication network where the load on the links is changing. In this thesis, a new clustering technique is introduced that is based on two parameters; radius and degree of node. This thesis work proposes an algorithm of constructing sparse t-spanners for arbitrary undirected weighted graphs. This thesis also explains fully dynamic algorithm for maintaining t-spanner of undirected weighted graphs under a sequence of update operations like insertion and deletion of links. This algorithm is applied on communication networks to optimize routing table space and also for good routing scheme by taking weight as congestion load of network link among two routers. All the algorithms are suggested in this thesis are practically implemented and tested for undirected weighted graph by varying number of nodes and number of link of graph.