交錯立方體

Abstract

一個平行分散式系統的效能深受其網路拓樸的影響，n維的超立方體Qn便是一個很有名的連結網路拓樸，它具有許多好的特性，但仍然沒有完全善用其硬體資源，因此，有許多它的變形被提出，譬如：雙扭立方體，雙扭立方體改善了超立方體的直徑，使得減少為大約一半。 在論文的第一部份，我們研究n維雙扭立方體TQn的邊壅塞度，對一個圖的某個路由而言，邊壅塞度代表的是所有邊中最高的訊息流量，因此，一個圖的邊壅塞度即可定義為所有路由中最小的邊壅塞度，相反地，如果一個路由的邊壅塞度即是某個圖的邊壅塞度，我們稱此路由為最佳的。在這個研究裡，我們發現TQn原始路由的邊壅塞度大於2n，這也就是為什麼在之前的研究中顯示TQn的動態效能反而比Qn差的原因，因此，我們提出一個新的路由演算法，並且證明了該路由的邊壅塞度是2n，這剛好與我們所算得的下限相等，因而證明了此路由是最佳的，而TQn的邊壅塞度就是2n，這是和Qn相同的。另一方面，我們同時也證明了TQn的切半寬度為2n-1。 在論文的第二部份，我們試著模仿雙扭立方體的架構去建構一個新的變形，這個新的變形稱作交錯立方體，這個嘗試是起自於對於是否存在一個更低直徑變形的懷疑。一個交錯立方體SQn，與Qn一樣具有2n個點，而每個點連結n條邊，更重要的是，我們證明了，它的直徑是 ，這大約是TQn的直徑的一半。這個結果比之前所有超立體變形的直徑都要好。 在論文的第三部份，我們探討SQn的一些特性。首先，我們證明了SQn的連通度為n，這表示當有壞點或壞線但不超過n-1個時，SQn還會是連通的。其次，我們證明了SQn寬直徑的上限為 ，寬直徑所顯示的是一個網路拓樸在多路徑路由下的效能，這個結果說明了在SQn中任兩點間，存在n條不相交路徑，其最大的長度不超過 ，同時這個結果也保證了在壞點或壞線不超過n-1個時，SQn的直徑不會超過 。第三，我們證明了SQn是具有漢米爾頓環路的，這表示在SQn裡，是可以在膨脹度1、壅塞度1、負載1的條件下嵌入號誌環。第四，我們證明了SQn是(n-2)-漢米爾頓及(n-3)-漢米爾頓連通的，前項的結果保證在壞點或壞線不超過n-2個時，SQn仍具有漢米爾頓環路，後一項的結果則保證在壞點或壞線不超過n-3個時，SQn中的任兩點之間仍存在漢米爾頓路徑，這兩個結果都是最佳的，因為，SQn是n正則的。最後，我們證明了SQn的邊壅塞度大於2n，這是SQn的一個缺點，我們希望在未來，我們可以建構出一個具有較小邊壅塞度的變形。 在論文的最後一個部份，我們將交錯立方體的架構加以一般化：給定一個正整數常數g，我們發展出一套方法來建構一個n維的一般化交錯立方體，它的直徑會是 ，其中C也是一個正整數常數。這是一個重要的結果，因為它說明了我們可以儘可能地降低直徑，只要n夠大的話。

The performance of a distributed system is significantly determined by its network topology. The $n$-dimensional hypercube, denoted by $Q_n$, is one of the most famous interconnection network topologies. It possesses many good properties, but it does not make the best use of its hardware. As a result, there are many variations of $Q_n$ being proposed, for example, the $n$-dimensional twisted cubes $TQ_n$. The diameter of $TQ_n$ is about half of that of $Q_n$, which is an improvement. In the first part of the dissertation, we study the edge congestion of $TQ_n$. For a routing algorithm of a graph, the edge congestion is the maximum traffic among all edges. Then the edge congestion of a graph is the minimum edge congestion among all routings of the graph. We say that a routing of a graph is optimal if the edge congestion of the routing is minimum. In the study, we find the edge congestion of the original routing of $TQ_n$ is greater than $2^n$. This is the reason why the dynamic performance of $TQ_n$ is worse than that of $Q_n$ in the previous studies. Thus, we propose a new routing algorithm and show that the edge congestion of the routing is $2^n$, which matches the lower bound we have obtained. So the routing is optimal with respect to the edge congestion, and the edge congestion of $TQ_n$ is $2^n$, which is equal to that of $Q_n$. And we simultaneously show that the bisection width of $TQ_n$ is $2^{n-1}$. In the second part of the dissertation, we try to construct a new variation based on the structure of the twisted cube, called the shuffle cube. The attempt arises from the doubt of whether the diameter of the variations of $Q_n$ can be reduced more. The $n$-dimensional shuffle cubes, denoted by $SQ_n$, also has $2^n$ nodes, and each node in $SQ_n$ connects to $n$ edges, which is the same as $Q_n$. Most importantly, we show that the diameter of $SQ_n$ is $\lceil \frac{n}4 \rceil +3$, which is about half of that of $TQ_n$. This result is better than the various diameters of all the previous variations of the hypercubes. In the third part of the dissertation, we investigate some properties of $SQ_n$. First, we show that the connectivity of $SQ_n$ is $n$, which means that $SQ_n$ is connected when the number of faults is less than $(n-1)$. This result is optimal since $SQ_n$ is $n$-regular. Second, we show that the wide diameter of $SQ_n$ is bounded by $\lceil \frac{n}4 \rceil +7$. The wide diameter is one of the indicators measuring the performance of multi-path routing of the given network topology. This result shows that between any pair of nodes in $SQ_n$, there are $n$ internally disjoint paths of length at most $\lceil \frac{n}4 \rceil +7$. It also guarantees that when there are at most $(n-1)$ faults in $SQ_n$, the diameter of $SQ_n$ is bounded by $\lceil \frac{n}4 \rceil +7$. Third, we show that $SQ_n$ is hamiltonian, which means that the token ring can be embedded into $SQ_n$ with dilation 1, congestion 1, and load 1. Fourth, we show that $SQ_n$ is $(n-2)$-hamiltonian and $(n-3)$-hamiltonian connected. The former guarantees that $SQ_n$ is still hamiltonian when there are at most $(n-2)$ faults in it. And the latter guarantees that for any pair of nodes $x$ and $y$ in $SQ_n$, there still exists a hamiltonian path between $x$ and $y$ when there are at most $(n-3)$ faults in $SQ_n$. The result is optimal since $SQ_n$ is $n$-regular. Finally, we show that the edge congestion of $SQ_n$ is greater than $2^n$. This is a drawback of $SQ_n$. We hope that we will construct a new variation with lower edge congestion in the future. In the final part of the dissertation, we generalize the model of the shuffle cube. Given a positive integer constant $g$, we develop a strategy to construct an $n$-dimensional generalized shuffle cube with diameter $\lceil \frac{n}g \rceil +C$, where $C$ is also a positive integer constant. This is an important result since it shows that we can reduce the diameter as we wish if $n$ is large enough.