Tight Bounds in Message Delays Despite Faults in a Class of Line Digraph Networks

Communication networks must be designed to withstand failures. The robustness of a network needs to account for graceful performance degradation with multiple failures in the network. The traditional delay metric of the diameter of the network is insufficient in this regards to represent the message passing delay in the presence of faults. This paper explores the d-wide diameter of a class of regular extended line digraphs which bound the delays despite faults. By studying the container of the network's underlying graph, a measure of the distance between nodes through multiple node disjoint paths is obtained. This study shows that the class of networks designed by extended line digraphs has very tight upper bounds on the d-wide diameter and is just one more than the normal diameter. Thus despite d-1 node failures the worst case delay is just one more than that of the original network. This tight bound has very powerful uses in areas of enabling load balancing and bounded delays despite multiple network faults.