Performance analysis of information dissemination by flooding

Performance properties are established for the dissemination by flooding of a database that is initially distributed among the nodes of a communications network. An example of this general process is the dissemination of network status information as a component of the adaptive routing mechanism in a network like Arpanet. Bounds are given on the progress of the dissemination process at a sequence of times before the completion of the process, whereas earlier results only bounded the time until completion. The present bounds further extended earlier analysis by treating the diameter explicitly as a parameter. Specialized versions of the bounds are given for k-connected networks. The bounds yield a recognition property whereby a node can recognize that it has received the entire database without having a priori knowledge of the size of the database. An earlier assumption about a fixed time for correct message transmission over any edge is relaxed to assume only an upper bound on these transmission times     

A k shortest path algorithm for adaptive routing incommunications networks

An efficient and flexible algorithm is presented for finding a k shortest loopless path with distinct initial links from one node to each other node. Low-order polynomial bounds are established for the worst-case time complexity of the algorithm, showing it to offer a substantial improvement over applying known algorithms to the problem. The algorithm can incorporate various extensions, including the ability to handle an algebraic objective, which enhance its applicability to diverse network models. In addition, the k shortest path formulation and algorithm are proposed as a basis for network survivability measures where path length bounds exist