Optimal Routing of Tight Optimal Bidirectional Double-Loop Networks

摘要

Double-loop networks are widely used in computer networks for its simplicity, symmetry and scalability. In this paper, we focus on optimal routing of Bidirectional Double-loop Network (BDLN) using coordinates embedding and transforming. First, we get the lower bound both of diameter and average distance of BDLN by embedding BDLN into Cartesian coordinates. Then, we find nodes distribution regularity on the embedding graph of tight optimal BDLNs that achieve the lower bound both in diameter and average distance. On the basis of nodes distribution regularity in tight optimal BDLNs, we present on demand optimal message routing algorithms which do not require routing tables and are highly efficient requiring very little computation.