雙環連結網路的最小直徑

Abstract

雙環聯結網路是一種廣泛被研究的區域網路架構。N表示網路中節點的個數，d(N) 表示在一N個節點的雙環網路中有可能最短的直徑。Wong and Coppersmith 證明了$d(N) \ge \left\lceil \sqrt{3N}\right\rceil -2$ □ 。這是一個廣為大家所知d(N)的下界，表示作lb(N)。給定N，如果可找出一個雙環連結網路的直徑剛好等於lb(N)，那就可以清楚的知道這有N個節點的雙環聯結網路的直徑是最小的。之前有許多人用此方法找出了一些可達到最小直徑的不同型態的N，但是在d(N) > lb(N)的情形下，只有少數的結果被知道。在這篇論文中，我們找出了兩種型態有d(N) = lb(N) + 1性質的N。

Double-loop networks have been widely studied as an architecture for local area networks. Let N denote the number of stations in a double-loop network and let d(N) be the best possible diameter of a double-loop network with N vertices. Wong and Coppersmith showed that $d(N) \ge \left\lceil \sqrt{3N}\right\rceil -2$. This is a well-known lower bound for d(N) and is usually denoted as lb(N). Given an N, if one can find a double-loop network with its diameter being equal to lb(N), then clearly this network is a minimum diameter double-loop network with N stations; this is the way that many authors found minimum diameter double-loop networks for some classes of values of N. When d(N) > lb(N), only a few results about minimum diameter double-loop networks are known. In this paper, we find minimum diameter double-loop networks for two classes of values of N when d(N) = lb(N) + 1.