Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Address-Free All-to-All Routin...

Address-Free All-to-All Routing in Sparse Torus

Risto Honkanen, Ville Leppänen, Martti Penttonen, Address-Free All-to-All Routing in Sparse Torus. In: Proceedings of 9th International Conference on Parallel Computing Technologies, PaCT-2007, Lecture Notes in Computer Science, 200–205, Springer-Verlag Berlin, 2007.

Abstract:

In this work we present a simple network design for all-to-all
routing and study deflection routing on it. We present a time-scheduled
routing algorithm where packets are routed address-free.
We show that a total exchange relation, where every processor has a packet
to route to every other processor, can be routed with routing cost of
1/2 + o(1) time units per packet.

The network consists of an n-sided d-dimensional torus,
where the n^{d-1} processor (or input/output) nodes are sparsely but
regularly situated among n^d - n^{d-1} deflection routing nodes,
having d input and d output links. The finite-state routing nodes
change their states by a fixed, preprogrammed pattern.

BibTeX entry:

@INPROCEEDINGS{inpHoLePe07a,
  title = {Address-Free All-to-All Routing in Sparse Torus},
  booktitle = {Proceedings of 9th International Conference on Parallel Computing Technologies, PaCT-2007},
  author = {Honkanen, Risto and Leppänen, Ville and Penttonen, Martti},
  number = {4671},
  series = {Lecture Notes in Computer Science},
  publisher = {Springer-Verlag Berlin},
  pages = {200–205},
  year = {2007},
  keywords = {network, routing, hot-potato, torus, sparse},
}

Belongs to TUCS Research Unit(s): Algorithmics and Computational Intelligence Group (ACI)

Publication Forum rating of this publication: level 1

Edit publication