ON DESIRABLE FAULT-TOLERANT TOPOLOGY FOR CLUSTER-BASED NETWORK

Management of control functions in large computer networks is a very d ifficult problem. One of the effective way to overcome the difficulty is to introduce hierarchical control structure (network cluster) in th e management. When a fault occurred in the cluster, routing informatio n at some nodes in the network must be updated in order to react the f ault. However, the number of such nodes can be reduced by introducing ingenious topology into the cluster. This paper presents a fundamental discussion on network topology for a network cluster. First, L-FT is defined to represent a degree of fault-tolerance in a cluster with res pect to link failures. Secondly, the minimum link problem M is defined to find the minimum number of links to make the cluster L-FT. The fol lowing results are obtained. (1) For a network cluster with the fault- tolerant topology 1-FT, at least 2n - 2 links have to exist in the clu ster where n is the number of border nodes in the cluster. (2) As far as connectivity of the whole network is held, for multiple L link fail ures in a L-FT cluster, the update of routing information at each node is localized within only the cluster containing the failed links. (3) Several hierarchical networks with fault-tolerant conditions are pres ented as case studies for a LAN and a MAN.