A SURVEY OF HIERARCHICAL ROUTING ALGORITHMS AND A NEW HIERARCHICAL HYBRID ADAPTIVE ROUTING ALGORITHM FOR LARGE SCALE COMPUTER COMMUNICATION NETWORKS

摘要

This paper is concerned with a survey of present hierarchical routing algorithms for Large Scale Computer Communication Networks (LSCCN), with emphasis on a new proposed scheme,Hierarchical Hybrid Adaptive Routing Algorithm (HHARA).Routing schemes of some currently implemented computer communication networks are reviewed and a short comparative survey for newly proposed hierarchical routing algorithms are given.Reliability. communication overheads, computation overheads are the major performance measures.HHARA is proposed to reduce the size of routing database by dynamically organizing nodes into hierarchically structered clusters such that only partial information is stored and maintained in each site. Also, the responsibility of routing is shared by the routing hierarchy such that the algorithm can maintain the global routing optimality and the local adaptivity at the same time. In this way, the storage, maintenance, communication, and computation overheads can be reduced while the response time to local status changes is kept small. HHARA can be used with either datagram routing or virtual circuit routing. Due to its ability to adapt to the network changes, it is specially useful for dynamic networks such as large military computer communication networks.This study leads to a conclusion that the hierarchical hybrid adaptive routing algorithm applied to a clustered network could be a convincing algorithm.