For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Reliable and Efficient Fixed Rountings on Digraphs
Yoshifumi MANABE Makoto IMASE Terunao SONEOKA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1988/12/25
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on CAS Karuizawa Workshop)
Full Text: PDF(666.4KB)>>
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.