Startseite > Publikationen > Publikationen

Publikationen

Meyer auf der Heide, Friedhelm;Scheideler, Christian:

Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks.

ESA 1995 : S. 341-354, Jul. 1995

Abstract

In this paper we present and analyze on-line routing schemes with contant buffer size and hot-potato routing schemes for vertex-symmetric networks. In particular, we prove that for any vertex-symmetric network with n vertices, degree d, and diameter D = Ω(log n), a randomly chosen function and any permutation can be routed in time
- O(log n * D), with high probability (w.h.p.), if constant size buffers are available for each edge,
- O(log n * D log^(1+ε) D) for any ε > 0, w.h.p., if for each vertex buffers of size 3, independent of the degree of the network, are available. The schedule for the second result can be converted into a hot-potato routing schedule, if a self-loop is added to each vertex. E.g., for any bounded degree vertex-symmetric network with self-loops and diameter O(log n) (among them expanders) we obtain a hot-potato routing protocol that needs time O(log² n(log log n)^(1+ε)) for any ε > 0 to route a randomly chosen function and any permutation, w.h.p.. Our protocols also allow bounds on the space requirements for vertices and packets in the network: we show that O(D(log logD + log d)) space suffices for storing routing information in the vertices and O(log D) space suffices for storing routing information in the packets. This is the first result about space-efficient routing where both the buffer size and the space for storing routing information is strongly bounded. Previous results are only known about routing protocols that either can reduce the buffer size or the space for storing routing information. For space-efficient hot-potato routing no general results are known. In order to prove the results above we introduce a new off-line routing protocol for arbitrary networks which is fast even for vertex buffers of size 1. This bound can not be reached by any other non-trivial off-line routing protocol yet.

Dateien

hni1863.pdf



Bibtex

@article{hniid=1863,
author = {Meyer auf der Heide, Friedhelm and Scheideler, Christian},
title = {Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks},
journal = {ESA 1995},
pages = {341-354},
month = jul,
year = {1995},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/1863