Reliability of interconnection networks

Graph is a type of mathematical model to study the relationships among entities. The theory on graphs is called Graph Theory. It started in 1736 and has 283 years of history since the paper was written by Leonhard Euler on the Seven Bridges of Königsberg. In computer science, the term "Interconnection Networks" has been used to refer to a set of interconnected elements. For example, a computer network where computers was connected by wires or Internet of Things (IoT) is connected via wireless connection. There are two types of network: static and dynamic. Static networks are hard-wired and their configurations do not change. The structure, which is also called topology signifies that the nodes are arranged in specific shape and the shape is maintained throughout the networks. In this thesis, we focus on the static networks. In graph theory, graphs are used to model the topology of network, whether it is networks of communication, data organization, computational devices, the flow of computation. For instance, the link structure of a local area network can be represented by an undirected graph, in which the vertices represent computers and edges represent connections between two computers. A similar approach can be applied to problems in social media, travel, biology, computer design, mapping the progression of neuro-degenerative diseases, and many other fields. Graph models could be directed, undirected and weighted, depending on the properties of the network we are studying. Fault-tolerance of networks is an important property. Fault-tolerance is the property that enables a system to continue operating properly in the event of the failure of some (one or more faults) of its components. Fault-tolerance is particularly sought after in high-availability or life-critical systems. We are interested in the fault-tolerance of networks. Considering the corresponding graph model of the networks, connectivity of the graphs measures how resistant a graph can be against the nodes (link) removal. In graph theory, there is a set of fault-tolerance related parameters, such as restricted-connectivity, extra-connectivity etc., which gave refined information about how robust is a network. Performance of the distributed system is significantly determined by the choice of the network topology. Desirable properties of an interconnection network include low degree, low diameter, symmetry, low congestion, high connectivity, and high fault-tolerance. For the past several decades, there has been active research on a class of graphs called Cayley graphs because this type of graph possesses many of the above properties. Many Cayley graphs based on permutation groups has proven to be suitable for designing interconnection networks, such as Star graph [1, 2, 47], Hypercubes [8], Pancake graphs [2, 79], Shuffel- Exchange Permutation Network [50], the Rotation-Exchange Network [110]. These graphs are symmetric, regular, and share the desirable properties described above. In this thesis, we studied the connectivity and diagnosability of some popular network structures. For instance, Cayley graphs generated by transpositions, expanded k-ary n-cube and locally twisted cube.