混合式弦環網路之距離相關問題

Abstract

本研究涵蓋混合式弦環網路中較少被討論的部份，並試圖發掘混合式弦環網路在與距離相關的問題中，是否存在有效率的演算法。這些問題包括最短距離圖的建造、直徑的計算、以及點與點之間的最優路由連線設計。上述與距離相關之問題在已被廣泛研究的雙環式網絡中，已經找得到有效率的演算法。本研究的重要性在於混合式弦環網路的直徑比雙環式網絡來得小，以及，混合式弦環網路沒有點對稱性質，因此使得上述與距離相關之問題複雜很多。

我們首先研究混合式弦環網路的最短距離圖建造問題。我們發現混合式弦環網路的最短距離圖可經由重新組合「虛擬距離圖」得到。這樣的觀察可以讓我們研究其它與距離相關之問題。針對直徑計算問題，我們提出一個有效率的演算法可以計算出任一給定的混合式弦環網路的直徑。關於找出混合式弦網環路中最小直徑的最佳化問題，我們改進了前人針對此問題所提出的上下限，並且成功地得到一個無限最優混合式弦環網路族。針對網路路由連線設計問題，我們提出兩個可彈性應用的點對點最優路由連線設計演算法：基於最短路徑路由演算法及動態路由演算法。此外，我們也提出了一個最優容錯路由演算法。此演算法在網路壞掉一個點或一個邊時可以執行正確。上述所有路由演算法都不需要路由表格，並且只需要非常小的額外計算花費。

This research covers the less trodden field of mixed chordal ring networks, in the attempt to discover the existence of efficient algorithms on distance-related problems, including the minimum distance diagram construction, the diameter computation, and the node-to-node shortest path routing. The extensively studied double-loop network has proven to hold efficient algorithms on the above specified distance-related problems. The significance of this research lies in mixed chordal ring network's achievement of a better diameter, as well as the in-vertex-transitive feature of it, which makes its exploration on distance-related problems a lot more sophisticated.

We first study and investigate the minimum distance diagram problem. We find that the minimum distance diagram of a mixed chordal ring network can be obtained by reassembling the \textsc{pseudoMDD}. This observation can be used to study other distance-related problems. For the diameter computation problem, we proposed an efficient algorithm to compute the diameter of a given mixed chordal ring network. For the optimization problem of finding optimal networks, we improve previous lower and upper bounds and successfully obtain a class of optimal mixed chordal ring networks. For the routing problem, two node-to-node routing algorithms are presented for flexible applications: the shortest-path-based routing algorithm and the dynamic routing algorithm. In addition, we also present an optimal fault-tolerant routing algorithm for mixed chordal ring networks in the presence of up to one node or link failure. All the routing algorithms presented do not require routing tables and only very little computational overhead is needed.