| Improving the Reliability of Computer Communication Networks |
| |
| 引用本文： | Weigeng Shi,Brigitte Servatius. Improving the Reliability of Computer Communication Networks[J]. 计算机科学技术学报, 1991, 6(3): 230-242. DOI: 10.1007/BF02945510 |
| |
| 作者姓名： | Weigeng Shi Brigitte Servatius |
| |
| 作者单位： | [1]DepartmentofMathematicalScience,WorcesterPolytechmicInstitute,Worcester,MA01609,U.S.A. [2]DepartmentofMa,WorcesterPolytechmicInstitute,Worcester,MA01609,U.S.A. |
| |
| 摘 要： | For networks that are directed or can be represented by a directed network,reversing one or more of the uni-directional links may provide the ability to reconnect a network that has been disconnected by link failure.In this paper,a new approach to reconfigure such networks is proposed.We develop a linear time algorithm which,when reachability has been destroyed by the removal of a single link,optimally restores reachability through the reversal of selected links.Multi-link failure reconnectability is discussed and an algorithm with polynomial complexity is given which provides a nearly optimum solution to reconnect the network.We show that the reliability of a network that allows reversals is at least twice more than that in which reversals are not permitted.Unfortunately,the reconnection of some networks cannot be established.Therefore,we discuss the maximization of reachability of such networks so that each node can reach maximum number of the other nodes.
|
| 关 键 词： | 计算机通信网络 可靠性 方向网 |
Improving the reliability of computer communication networks |
| |
| Shi Weigeng,Servatius Brigitte. Improving the reliability of computer communication networks[J]. Journal of Computer Science and Technology, 1991, 6(3): 230-242. DOI: 10.1007/BF02945510 |
| |
| Authors: | Shi Weigeng Servatius Brigitte |
| |
| Affiliation: | Department of Electrical Engineering; Department of Mathematical Science Worcester Polytechnic Institute; Worcester; MA 01609; U.S.A.; |
| |
| Abstract: | For networks that are directed or can be represented by a directed networks, reversing one or more of the uni-directional links may provide the ability to reconnect a network that has been disconnected by link failure. In this paper, a new approach to reconfigure such networks is proposed. We develop a linear time algorithm which, when reachability has been destroyed by the removal of a single link, optimally restores reachability through the reversal of selected links. Multi-link failure reconnectability is discussed and an algorithm with polynomial complexity is given which provides a nearly optimum solution to reconnect the network. We show that the reliability of a network that allows reversals is at least twice more than that in which reversals are not permitted. Unfortunately, the reconnection of some networks cannot be established. Therefore, we discuss the maximization of reachability of such networks so that each node can reach maximum number of the other nodes. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |
