Startseite > Publikationen > Publikationen


Meyer auf der Heide, Friedhelm;Schröder, Klaus;Schwarze, Frank:

Routing on networks of optical crossbars.

Theoretical Computer Science 196: S. 181-200, 1998


We describe routing algorithms on networks composed of optical busses. Using networks with short busses and small degree we are able to give very fast routing algorithms. First, we describe a leveled optical network and a routing algorithm for it. Next, we show how to simulate this network on high-dimensional meshes of optical busses (MOBs). We present algorithms for routing, e.g., h-relations with runtime being linear in h, doubly logarithmic in size and polynomial in the dimension of the mesh. Previous results are exponential in the dimension. E.g., routing an h-relation on a d-dimensional MOB of size N requires O(d5 log d log log N+d3h) steps, with high probability.


author = {Meyer auf der Heide, Friedhelm and Schr{\"o}der, Klaus and Schwarze, Frank},
title = {Routing on networks of optical crossbars},
journal = {Theoretical Computer Science},
volume = {196},
pages = {181-200},
year = {1998},

BibTeX in die Zwischenablage kopieren