Optimal design and routing of distributed loop networks

The ring network is a popular network topology for implementation in local area networks and other configurations. However, it has the disadvantage of high diameter and hence large communication delay. So loop networks were introduced with fixed-jump links added to the ring. The authors characterize the values of N (number of vertices in the network) for which the lower bound on the diameter of the network is achieved. These classes cover almost all values of N. The authors focus attention on the problem of routing. They give an algorithm for finding a shortest path between any two vertices of a general loop network. They also propose a scheme to find a near optimal path (not more than one over the optimal) in case of a single vertex or link failure