5 - Fault-Tolerant Routing Schemes and Analysis

Summary

Lee and Jackson were now separated,

and only victory would reunite them.

—Winston Churchill

Fast, fault-tolerant communication schemes using constant size buffers on the hypercube and the de Bruijn networks are presented. All our schemes run with probability of successful routing 1 – N^−Θ(logN) where N denotes the number of processors. A summary of this chapter's results can be found in Section 4.4.

Parallel Communication Scheme

The notion of symmetric parallel communication scheme (SPCS) captures the essence, and facilitates the analysis, of our parallel routing algorithms.

Definition 5.1In anepoched communication scheme (ECS), packets are sent inepochs, numbered from 0. In any epoch, packets that demand transmission to neighboring nodes in that epoch, as determined by the routing algorithm, are sent along the links as requested. A symmetric parallel communication scheme (SPCS) is an ECS that satisfies the following conditions.

1. Each node initially has h packets.

2. All packets are routed independently by the routing algorithm; that is, in any epoch, a packet crosses an out-going link independently with equal probability.

3. The expected number of packets at each node is h at the end of each epoch.

Such a scheme is called an h-SPCS.

Comment 5.2 Condition 3 implies that no packets can be lost. In all our schemes, however, pieces (that is, packets in the definition of ECS) can be lost due to buffer overflow. This is not a serious problem since we can analyze a scheme as if pieces over the capacity of the buffer were not lost.