Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2005-02-26
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
This paper establishes the state of the art in both deterministic and randomized online permutation routing in the POPS network. Indeed, we show that any permutation can be routed online on a POPS network either with $O(\frac{d}{g}\log g)$ deterministic slots, or, with high probability, with $5c\lceil d/g\rceil+o(d/g)+O(\log\log g)$ randomized slots, where constant $c=\exp (1+e^{-1})\approx 3.927$. When $d=\Theta(g)$, that we claim to be the "interesting" case, the randomized algorithm is exponentially faster than any other algorithm in the literature, both deterministic and randomized ones. This is true in practice as well. Indeed, experiments show that it outperforms its rivals even starting from as small a network as a POPS(2,2), and the gap grows exponentially with the size of the network. We can also show that, under proper hypothesis, no deterministic algorithm can asymptotically match its performance.
Mei Alessandro
Rizzi Romeo
No associations
LandOfFree
Online Permutation Routing in Partitioned Optical Passive Star Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Permutation Routing in Partitioned Optical Passive Star Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Permutation Routing in Partitioned Optical Passive Star Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-33192