Reliable and Efficient Fixed Rountings on Digraphs

Yoshifumi MANABE; Makoto IMASE; Terunao SONEOKA

Reliable and Efficient Fixed Rountings on Digraphs

Yoshifumi MANABE, Makoto IMASE, Terunao SONEOKA

Full Text Views

0

Cite this

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 ρ₂ such that ξ(G, ρ₂)2log_dn for any number of nodes n and maximum degree d. (3) A method of constructing a digraph G and routing such that ξ(G, ρ₂)3log_dn and D(R(G, )/F)3 for |F|d-1 if nd⁴ and d3.

Publication: IEICE TRANSACTIONS on transactions Vol.E71-E No.12 pp.1212-1220

Publication Date: 1988/12/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on CAS Karuizawa Workshop)

Category

Authors

Yoshifumi MANABE
Makoto IMASE
Terunao SONEOKA

Keyword

Cite this

Copy

Yoshifumi MANABE, Makoto IMASE, Terunao SONEOKA, "Reliable and Efficient Fixed Rountings on Digraphs" in IEICE TRANSACTIONS on transactions, vol. E71-E, no. 12, pp. 1212-1220, December 1988, doi: .
Abstract: 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 ρ₂ such that ξ(G, ρ₂)2log_dn for any number of nodes n and maximum degree d. (3) A method of constructing a digraph G and routing such that ξ(G, ρ₂)3log_dn and D(R(G, )/F)3 for |F|d-1 if nd⁴ and d3.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e71-e_12_1212/_p

Copy

@ARTICLE{e71-e_12_1212,
author={Yoshifumi MANABE, Makoto IMASE, Terunao SONEOKA, },
journal={IEICE TRANSACTIONS on transactions},
title={Reliable and Efficient Fixed Rountings on Digraphs},
year={1988},
volume={E71-E},
number={12},
pages={1212-1220},
abstract={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 ρ₂ such that ξ(G, ρ₂)2log_dn for any number of nodes n and maximum degree d. (3) A method of constructing a digraph G and routing such that ξ(G, ρ₂)3log_dn and D(R(G, )/F)3 for |F|d-1 if nd⁴ and d3.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Reliable and Efficient Fixed Rountings on Digraphs
T2 - IEICE TRANSACTIONS on transactions
SP - 1212
EP - 1220
AU - Yoshifumi MANABE
AU - Makoto IMASE
AU - Terunao SONEOKA
PY - 1988
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E71-E
IS - 12
JA - IEICE TRANSACTIONS on transactions
Y1 - December 1988
AB - 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 ρ₂ such that ξ(G, ρ₂)2log_dn for any number of nodes n and maximum degree d. (3) A method of constructing a digraph G and routing such that ξ(G, ρ₂)3log_dn and D(R(G, )/F)3 for |F|d-1 if nd⁴ and d3.
ER -