A combinatorial problem related to distributed loop networks
Ding‐Zhu Du, D. Frank Hsu, Qiao Li, Jun‐Ming Xu · Networks · 1990
Abstract The problem under consideration arises from studies on local networks and multimodule memory organizations. The ring network has been one of the popular network topologies used in the design and implementation of local area networks and other configurations. We consider here a generalization of the ring network by adding two fixed‐step links to each node. The resulting networks have low diameter, easy routing, and switching structure and therefore are suitable for implementation in the design of reliable networks. Let N denote the number of nodes in the network. For a given N, we are concerned with the problem of determining the best topologies to minimize the diameter (and, hence, the transmission delay) of the network. We obtain new classes of values of N for which topologies can be found that achieve the lower bound lb = [(√2N ‐ 1 ‐ 1)/2] for the minimum diameter. We also show that for some infinite classes of N this lower bound lb is not achievable.