| In parallel computing, an interconnection network is needed to connect the process array. The time needed to disseminate the information among the processors in a network often determines running time of some parallel algorithms. Along with this transmission latency concern, reliability of the interconnection network is also widely researched in both academics and industry. Because of instability of computing model needs to cope with occasional failures while still remain a reasonable processing power.; The first part of this thesis focuses on the worst-case latency in face of node failures in interconnection networks. The paper defines ‘Diameter Vulnerability’ property of a graph by its diameter changes in face of node failures. Diameter vulnerability is measured by the lengths of vertex disjoint paths between any pair of nodes in a network. The paper proposes a general approach to prove the diameter vulnerability of several classes of interconnection models, including Kautz, De Bruijn, General Cycle graphs. It also solves a difficulty, which has been ignored by a number of researchers.; The second part of this thesis focuses on the availability of interconnection networks in case of link failures. Super line-connectivity is used as a major measurement. A graph is said to have super line-connectivity n if and only if it has line-connectivity of n and all its line cuts are natural. The paper proposes a general proof of super line-connectivity of several classes of interconnection models. Therefore, it proves those graphs are optimal in case of link failures.; The third part of this thesis focuses on the real time Ethernet design. It proposes a novel probabilistic approach to bound the worst case latency in the standard Ethernet protocol. It also provides a set of simulation results to verify its feasibility. |
