Establishing virtual circuits in large computer networks

Network routing algorithms generally attempt to provide communication between two nodes by sending data messages along the best or shortest path between them. Unfortunately, in large networks it is difficult to maintain knowledge of such path due to the cost in storage, computation, and communication bandwidth. In an attempt to solve this problem the technique of clustering has been proposed. Clustering generally reduces the cost of routing of by sacrificing optimality. Kamoun has shown that this sacrifice is asymptotically negligible under certain strong assumptions. In this paper we propose a new clustering technique which permits us to obtain optimal paths. However, determining these paths requires some effort and thus the methodology is appropriate only if the paths are then used for many messages in virtual circuit fashion. An application to planar networks gives a quantitative demonstration of obtaining optimal paths with reduced path determination cost. © 1986.