Research And Application Of Network Fault Tolerance And Communication Delay Metric

The diameter of a graph G is the maximum distance between pairs of vertices of G . When a network can be modeled as a graph (if a vertex represents a node of processor (or a station) and an edge between two vertices is a link (or connection) between those two processors), diameter is a measurement for maximum transmission delay . In particular , w-wide diameter on a graph deals with w vertex disjoint paths between a pair of two vertices of G . It arises naturally from the study of routing , reliability , randomized routing , fault tolerance , and other communication protocols in parallel architectures and distributed computer networks , and it is natural generalization of diameter in a graph which pays attention to the practicality .First , we discuss w-wide diameter of Generalized Hypercube which is an important network topology for parallel processing computer system . Here we prove its w-wide diameter in two ways . And at the same time two specific parallel path algorithms are given on the basis of the original search algorithm . (One bases upon the topological properties of Generalized Hypercube , the other bases on the coding of its vertices.) These algorithms are simple , concise and practical .Secondly , we define a new parameter of graph and name it λ-diameter . Its prerequisite is edge disjoint paths . This parameter can not only measure fault-tolerance and transmission delay of network , but also reflect some information about bottle-neck . λ-diameter is really generalization of w-wide diameter in a sense. Furthermore , properties of λ-diameter and an algorithm for it are given in this paper .Finally , in this paper , there is a bottle-neck vertex seach algorithm for various bottle-neck of networks . This algorithm is valuable because to some extent it can emulate and optimize networks at the same time .