Fully adaptive circuit switching

an interconnection network for a cluster of workstations/PCs that is
sufficiently fast, sustains high load and is extremely cheap. The proposed
routing algorithms are based on fully adaptive circuit switching.

The project has three components:


1. Theoretical background: Our first goal is to establish a connection as a
response to a connection request as soon as possible even when the network
is rather loaded. At the time of a particular connection request we consider
a subnetwork of only those links (edges) that are free, i.e. not used to
transmit other messages at that time. We try to find a free (short) path from
the message source to its destination, i.e. a path in said subnetwork,
because only such a path enables us to make a connection without waiting
until links that are temporarily occupied would be released.

Assuming the communication in the network is sufficiently random, this point
of view leads to the study of connectivity and path lengths of a random
subgraph of a given graph, obtained by random deletions of edges. Some
classical and new results will be presented. The main teachings are
- if the load grows, the shortest paths in the free-edge subnetwork are
getting longer and therefore they can not be found not only by simple
oblivious routing strategies, but also by minimal adaptive routing
algorithms that are allowed to use arbitrary SHORTEST path
to the destination. This necessitates using fully adaptive routing
- there are two busy-edge density thresholds: if the number of busy edges
is above the threshold, it becomes likely that free subnetwork comprises
some light disconnectivities and makes simple fully adaptive routing
algorithms unstable. Beyond the second threshold the free subnetwork
becomes so disconnected that no efficient wait-free communication is
possible by ANY routing algorithm.
We will present a method to overcome the above mentioned instability
and suggest very simple stable fully adaptive routing algorithms that
work in an efficient way even for loads quite close to the second threshold.

2. Simulation: As the complete analysis of the expected behavior of the above
mentioned stable fully adaptive algorithms seems to be too difficult,
their properties were studied experimentally using computer simulation.
Some results are presented for grids and deBruijn graph. Results
confirm that the considered class of algorithms is very promissing.

3. As the proposed algorithms imply a very simple architecture of a switch node,
we are going to implement them in hardware. At the present time a complete
design of a switch node has been completed. It uses a FPGA chip Xilinx
XC40.. to implement control logic, a crossbar chip I-Cube PSX... for
data switching and Texas Instruments LVDS transmitters and receivers
SN65LVDS31/32 as cable drivers. A switch with 4 input and 4 output 16 bit
chanels could be built using the simplest Xilinx chip XC4003E-PC84C,
I-Cube PSX128 and 4 pairs SN65LVDS31/32 per channel. The present price
of the fastest version of XC, XC4003E-1PC84C, is around US$ 60, PSX has
approximately the same price and a pair of SN..31/32 costs around US$ 10,
which suggest a really very low price of the whole circuit.
At the present moment complete functional simulation of the design has
been done and timing simulation is expected next week. Our estimation is
that even when using above out-of-shelf parts a switching delay per node
of a network would be below 50 nanoseconds.