Self -Routing Superconcentrators
โ Scribed by Nicholas Pippenger
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 293 KB
- Volume
- 52
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
โฆ Synopsis
Superconcentrators are switching systems that solve the generic problem of interconnecting clients and servers during sessions, in situations where either the clients or the servers are interchangeable (so that it does not matter which client is connected to which server). Previous constructions of superconcentrators have required an external agent to find the interconnections appropriate in each instance. We remedy this shortcoming by constructing superconcentrators that are selfrouting,'' in the sense that they compute for themselves the required interconnections. Specifically, we show how to construct, for each n, a system S n with the following properties: (1) The system S n has n inputs, n outputs, and O(n) components, each of which is one of a fixed finite number of finite automata and is connected to a fixed finite number of other components through cables, each of which carries signals from a fixed finite alphabet. (2) When some of the inputs, and an equal number of outputs, are marked'' (by the presentation of a certain signal), then after O(log n) steps (a time proportional to the ``diameter'' of the network) the system will establish a set of disjoint paths from the marked inputs to the marked outputs. The size O(n) is of course optimal for superconcentrators, as is the diameter O(log n) for superconcentrators of bounded degree.
๐ SIMILAR VOLUMES
A self-stabilizing system is a distributed system which can tolerate any number and any type of faults in the history. After the last fault occurs the system converges to a legitimate behavior. The self-stabilization property is very useful for systems in which processors may malfunction for a while
A fault-tolerant high-performance SElf-Routing 2 x 2 Optical ATM Switch (SEROS) is proposed. The switch is designed using all-optical components which allows the exploitation of spatial parallelism. SEROS can be used with any multistage interconnection network such as Omega, Banyan, Shuffle or Bene
Self-healing communication networks that allow re-routing of demands through switching processes at designated nodes are studied. It is shown how network utilization, demand throughput and reliability of such networks can be studied simultaneously to achieve an optimal design for all three. This is