Issues in routing for large and dynamic networks

Abstract

The routing function is necessary in computer communication networks in order to create the appearance of complete connectivity in an environment of sparse physical links. The purpose of this dissertation is to examine ways of providing the routing function in large networks or networks which are characterized by frequent topological changes or both. The focus is on distributed routing algorithms because of their failsafe property. Two new event driven distributed route table update algorithms, A and B, are introduced and proven correct. Algorithm A requires less buffer space to store route tables than other event driven algorithms. Algorithm B, a variation of algorithm A, allows each node to maintain a source tree, i.e. a tree rooted at the node and containing the shortest path to all possible destinations in the network. The source tree may be used to implement source routing, i.e. the whole path from source to destination is determined at the source. Transient route table looping is also studied for algorithms A, B, as well as other algorithms in the literature. Hierarchical routing has been suggested in the literature as a means to reduce the size of the route tables when networks become very large. Reduction of the table size may also reduce the communication cost incurred during the update of the route tables. A possible effect of the shrinking of the route tables is that the resulting paths are not optimal. A classification of hierarchical routing schemes is introduced. The trade-off between between route table reduction and path length increase is studied in detail for two classes of schemes. Alternate policies for routing in the absence of necessary information are suggested and evaluated. In order to implement hierarchical routing it is necessary to partition the network into clusters. The network partitioning problem is abstracted to a graph partitioning problem which is shown to be NP complete. A new heuristic procedure, V3.2, is developed which is compared to the agglomerative method, a procedure suggested in the literature. V3.2 is shown to perform considerably better computationally as well as in terms of desired properties of the partitions. The comparison is performed by simulation experiments. An algorithm is developed to randomly generate connected networks suitable to be used in the simulations.