標誌環上最佳化之 k 容錯網路設計

Abstract

多處理機的容錯設計已經被廣泛的應用在線上交易處理, 以及可靠度較 低的大型平行處 理系統. 多處理機系統的容錯設計主要有兩方面, 一是 處理機的容錯設計,一是連接線的容錯設計. 在不同網路架構上, 前人的 研究大都只考慮到處理機的容錯設計, 或只考慮到連接線的容錯設計方 面. 在本篇論文中, 我們則討論在 token rings 上, 處理機與連接線可 同時發生錯誤的容錯設計. 其中 "k faults" 表示處理機與連接線共有 k 個錯誤發生. 在 token ring 中設計一個最佳化的 k 容錯網路, 就等於 建造一個 k-hamiltonian圖形, 其中 k 是一個正整數, 對應著錯誤發生 的個數. 一個圖形 G 是 k-hamiltonian 圖形, 若 G-V'-E' 是一個 hamiltonian 圖形, 其中 V' 屬於 V , E' 屬於 E 且 V'+ E' <= k. 一 個有 n 個頂點的 k-hamiltonian 圖形是最佳的, 若這個 k-hamiltonian 圖形含有最少邊. 在本篇論文中, 我們建造出當 k=2,3 的時候, 最佳化 的 k-hamiltonian 圖形; 那也就是在 token rings 上的最佳化的 k 容 錯網路. Fault-tolerant multiprocessors are widely used in on-line transactionprocessing. Fault tolerance is also desirable in massive parallel systemsthat have a relatively high failure probability. Two types of failures in amultiprocessor system are of interest, processor failures and link failures.Most of previous research in designing optimal fault-tolerant topologies wascincentrated on the cases that only processor failures were allowed, or the cases that only link failures were allowed. In this paper, we discuss the caseof a combination of processor failures and link failures for token rings. By"k faults" we mean k-component faults in any combination of processor faultsand link faults. Designing an optimal k-fault-tolerant network for token rings is equivalent to constructuring an optimal k- hamiltonian graph, where k is a postive integer and corresponds to the number of faults. A graph G is k-hamiltonian if G-V'-E' is hamiltonian for any sets V' in V and E' in E withV'+E'<= k. An n-node k-hamiltonian graph is optimal if it contains the leastnumber of edges among all n-node k-hamiltonian graphs. In this paper, we are going to construct optimal k-hamiltonian graphs with k=2 and 3, which are optimal k-fault-tolerant networks with respect to token rings.