标题: 混合式弦环网路之距离相关问题
On Distance-related Problems of Mixed Chordal Ring Networks
作者: 蓝国元
Lan, Kuo-Yuan
陈秋媛
Chen, Chiu-Yuan
应用数学系所
关键字: 混合式弦环网路;双环式网路;演算法;直径;最优路由;容错路由;最短距离图;连接网络;平行处理;Mixed chordal ring network;Double-loop network;Algorithm;Diameter;Optimal routing;Fault-tolerant routing;Minimum distance diagram;Interconnection network;Parallel processing
公开日期: 2010
摘要: 本研究涵盖混合式弦环网路中较少被讨论的部份,并试图发掘混合式弦环网路在与距离相关的问题中,是否存在有效率的演算法。这些问题包括最短距离图的建造、直径的计算、以及点与点之间的最优路由连线设计。上述与距离相关之问题在已被广泛研究的双环式网络中,已经找得到有效率的演算法。本研究的重要性在于混合式弦环网路的直径比双环式网络来得小,以及,混合式弦环网路没有点对称性质,因此使得上述与距离相关之问题复杂很多。

我们首先研究混合式弦环网路的最短距离图建造问题。我们发现混合式弦环网路的最短距离图可经由重新组合“虚拟距离图”得到。这样的观察可以让我们研究其它与距离相关之问题。针对直径计算问题,我们提出一个有效率的演算法可以计算出任一给定的混合式弦环网路的直径。关于找出混合式弦网环路中最小直径的最佳化问题,我们改进了前人针对此问题所提出的上下限,并且成功地得到一个无限最优混合式弦环网路族。针对网路路由连线设计问题,我们提出两个可弹性应用的点对点最优路由连线设计演算法:基于最短路径路由演算法及动态路由演算法。此外,我们也提出了一个最优容错路由演算法。此演算法在网路坏掉一个点或一个边时可以执行正确。上述所有路由演算法都不需要路由表格,并且只需要非常小的额外计算花费。
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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079422802
http://hdl.handle.net/11536/40828
显示于类别:Thesis


文件中的档案:

  1. 280201.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.