Topological Structure and Analysis of Interconnection Networks
==========================================================================
Chapter
4
Fault-Tolerant Analysis of Interconnection
Networks
There are a large number of graph optimization problems which arise in network design and analysis in the literature. Some of them have been
summarized in a survey by Caccetta (1989). Our objective in this chapter is to highlight other new problems which arise in
interconnection networks of large-scale parallel processing real-time systems.
Faults of some components and/or communication lines in a large-scale system are inevitable. However, the presence of faults gives rise to a
large number of problems to have to be handled for some applications. Generally speaking, the solutions of these problems are difficult as
the set of faults is not known in advance. Nevertheless, they have attracted considerable research interest the recent decade, and many
nice results have been obtained.
We in this chapter will introduce some such problems, formalize them as standard concepts of graph theory and present some basic research
results. These issues consist of six research aspects, routing,
Menger-type problems in parallel systems, fault-tolerant diameter, wide diameter,
(l,w)-dominating number and restricted fault tolerance.
|
