兩種連接網路：三環式網路及 Log2(N, m, p) 交換網路之研究

Abstract

本篇論文主要討論二種類型的網路：一是電腦網路(computer networks)；另一是應用在通訊上的交換網路(switching networks)。對於前者，我們主要針對三環式網路做研究；對於後者，我們則針對Log2(N, m, p)網路做研究。首先，我們先介紹三環式網路： 一個記為ML(N; s1, …, sl)的多環式網路，若以一具N個點(0, 1, …, N − 1)，lN條邊的有向圖來表示，其有向邊的連接方式為：i → i + s1, i → i + s2, …, i → i + sl, (mod N), i = 0,1, …, N −1。其中s1, …, sl這l個整數被稱做是多環式網路的“步”。當l的值確定時，我們也可稱此多環式網路為l-環式網路。尤其當l = 2時，此多環式網路又被稱為雙環式網路，記為DL(N; s1, s2)；當l = 3時，此多環式網路則又被稱為三環式網路，記為TL(N; s1, s2, s3)。 近期，雖然有許多的三環式網路已被提出，並且它們的效能也被研究，但是真實存在的此類網路，就數量來說仍是非常的稀少，因此，在此篇論文中，我們將會把已有的三環式網路推廣以增加其類型的數量，同時，我們也會提出一個啟發式(heuristic)的方式來最佳化我們所提出的三環式網路所需的參數，以增進其效能。 在本篇論文中，我們將研究三個特定三環式網路的3-直徑(3-diameter)，其中，我們用建構的方式來做此研究，亦即，我們在任意二點間建立三條點互斥(node-disjoint)，且長度不超過直徑加2的最短路徑。 接下來，我們將介紹Logd(N, m, p)網路： Lea 和 Shyy [32] 首先提出含有N = 2n條進線(inputs)和出線(outputs)的Log2(N, m, p)網路，其建構方式為將p個BY-1(n, m) 的複製網路垂直堆疊在某一進線層(input stage)和出線層(output stage)中，其中0 □ m □ n□1，並且每一進(出)線層含有N個1 □ p (或 p □ 1)的閂(crossbar)。之後，Hwang [24]將Log2(N, m, p)網路中，每個2 □ 2的閂由d □ d的閂取代，於是把它推廣為Logd(N, m, p)網路。 一個網路若目前送來的訊息，必須在所有的訊息皆依某一給定的演算法連接傳送，才可以保證被連接傳送時，這種不阻塞的程度稱為wide-sense nonblocking。網路的交流量被分類為點對點(point-to-point)，例如傳統電話連接；另一為廣播式(broadcast)，亦即點對所有(one to all)。假如每一訊息的最多接收者有所限制，那麼廣播式亦稱為多重傳播(multicast)，亦即點對多(one to many)；如果接收者被限制為f，則稱為f-cast。 Tscha和Lee [44] 對於多重傳播(multicast) Log2(N, 0, p)網路提出了fixed-size window演算法，並表明期望可以將此演算法推廣至Log2(N, m, p)網路。之後，Kabacinski和Danilewicz [29] 將fixed-size window演算法推廣至variable size window演算法。在這篇論文中，我們更進一步地把variable size window演算法的結果，由Log2(N, 0, p)網路推廣至Log2(N, m, p)網路。

This thesis is divided into two types of networks: computer networks and switching networks used in communication. In particular, we will study a class of computer networks called the triple-loop network, and a class of switching networks called Log2(N, m, p). We first introduce the former. A multi-loop network, denoted by ML(N; s1, …, sl), can be represented by a digraph on N nodes, 0, 1, …, N − 1 and lN links of l types: i → i + s1, i → i + s2, …, i → i + sl, (mod N), i = 0,1, …, N −1. The integers s1, …, sl are called the steps of the multi-loop network. When l is specified, we can also call it an l-loop network. In particular, when l = 2, the multi-loop network is usually called the double-loop network and is denoted by DL(N; s1, s2). When l = 3, the multi-loop network is usually called the triple-loop network and is denoted by TL(N; s1, s2, s3). Several triple-loop networks have been recently proposed and their efficiency studied. However, the number of cases for which one of these networks exist is sparse. In this thesis, we extend these networks to larger classes to enhance their realizability. We also give a heuristic method to optimize the network parameters to increase their efficiency. In this thesis, we study the k-diameters of three specific triple-loop networks. In particular, we construct three node-disjoint shortest paths no longer than the diameter plus 2 for any pair of nodes. Next we introduce the Log2(N, m, p) network. Lea and Shyy [32] first proposed the Log2(N, m, p) network with N = 2n inputs (outputs), which consists of a vertical stacking of p copies of BY-1(n, m), 0 □ m □ n□1, sandwiched between and connected to an input stage and an output stage, each with N 1 □ p (or p □ 1) crossbars. Later, Hwang [24] extended the Log2(N, m, p) network to Logd(N, m, p) network by replacing the 2 □ 2 crossbars with d □ d crossbars. A network is wide-sense nonblocking (WSNB) if the connection of the current request is assured only when all connections are routed according to a given algorithm. Traffic can be classified as point-to-point, like 2-party phone calls, or broadcast, which is one to all. If there is a restriction on the maximum number of receivers per request, then broadcast is called multicast (one to many), or f-cast, if that number is specified to be f. Tscha and Lee [44] proposed a fixed-size window algorithm for the multicast Log2(N, 0, p) network and expressed a desire to see its extension to the Log2(N, m, p) network. Later, Kabacinski and Danilewicz [29] generalized the fixed-size window to variable size to improve the results. In this thesis, we further extend the variable-size results from the Log2(N, 0, p) network to Log2(N, m, p).