Reliable and Efficient Fixed Rountings on Digraphs

Yoshifumi MANABE  Makoto IMASE  Terunao SONEOKA 

Publication
IEICE TRANSACTIONS (1976-1990)  Vol.E71  No.12  pp.1212-1220
Publication Date: 1988/12/20
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on CAS Karuizawa Workshop)
Category: 
Keyword: 


Full Text: PDF(666.4KB)

Summary: 
The problem of constructing a reliable and efficient routing ρ in a communications network G is considered. The forwarding index ξ(G, ρ), which is defined as the maximum number of routes which pass through each node, is a criterion of network efficiency. The diameter of the surviving route graph D(R(G, ρ)/F), which is defined as the maximum number of surviving routes needed for communication between each pair of nodes if node and edge faults F occur, is a criterion of network reliability. Routings which minimize ξ(G, ρ) and D(R(G, ρ)/F) are needed. In this paper the following are shown: (1) A sufficient condition for k-connected digraphs (k2, 4) to have a routing ρ such that D(R(G, ρ)/F)6 for |F|k. (2) A method of constructing a digraph G and routing ρ2 such that ξ(G, ρ2)2logdn for any number of nodes n and maximum degree d. (3) A method of constructing a digraph G and routing such that ξ(G, ρ2)3logdn and D(R(G, )/F)3 for |F|d-1 if nd4 and d3.