All-To-All Routing With Bounded Loads

All-to-all routing is the most important routing primitive.
Optical networks are going to be the dominant future standard.
For grid-like and other product topologies, i show how to
perform all-to-all routing under the tough conditions of an
optical network. This offers new possibilities, and may have
great practical impact.

The talk will have an elementary character and should be
understandable to all. It is split over two sessions, the
second will be friday or next week.

FOR THE FEW EXPERTS:

Two hardware models are considered. The first reflects the features
of networks in which a permutation can be efficiently routed when no
connection has to transfer more than $L$ packets. The second reflects
the feautures of networks in which a permutation can be routed
efficiently if each packet can be colored with one of $L$ colors, so
that no connection has to transfer two packets with the same color.
For these models we study how to decompose all-to-all routing
patterns into permutations and how many permutations are required in
order to respect the bound $L$ on the connection loads.

We focus on product networks, more specifically on meshes and tori.
For these networks, based on optimal schedules for linear and
circular arrays, we obtain novel optimal schedules. That is, we show
that for an $n \times n$ mesh and given $L$ there is a decomposition
into $M(L) = (n + \go{1}) \cdot n^2 / (4 \cdot L)$ permutations.
For tori $M(L)$ is only half as large. Most importantly, these bounds
also hold for the model with colored packets, which gives the first
efficient algorithm for all-to-all routing on grid-like optical
networks with finite wavelength multiplexing.

All results are generalized for higher dimensional meshes and tori.
Furthermore, among all possible decompositions into permutations, we
are particularly interested in those that are composed of exchanges,
which may be routed faster than permutations composed of longer
cycles. We show that such decompositions require only few extra
permutations to achieve the same $L$.