Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Sibeyn, Jop F.

dblp



Editor(s):





BibTeX cite key*:

F.Sibeyn-IPPS-1999

Title, Booktitle

Title*:

Better Deterministic Routing on Meshes

Booktitle*:

Proceedings of the 13th International Parallel Processing Symposium, and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP-99)

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

St Juan, Puerto Rico

Language:

English

Event Date*
(no longer used):

April, 12-16, 1999

Organization:


Event Start Date:

12 April 1999

Event End Date:

16 April 1999

Publisher

Name*:

IEEE

URL:


Address*:

Los Alamitos, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

May

Pages:

420-425

Year*:

1999

VG Wort Pages:


ISBN/ISSN:

0-7695-0143-5

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Optimal randomized and deterministic algorithms have been given for $k$-$k$
routing on two-dimensional $n \times n$ meshes. The deterministic algorithm
is based on ``column-sort'' and exploits only part of the
features of the mesh. For small $n$ and moderate $k$, the lower-order terms
of this algorithm make it considerably more expensive than the
randomized algorithm. In this paper, we present a novel deterministic
algorithm, which, by exploiting the topology of the mesh, has lower-order
terms that are almost negligible, even smaller than those of the randomized
algorithm. An additional advantage of the new algorithm is that it routes
average-case packet distributions twice as fast as worst-case distributions.
In earlier algorithms this required additional steps for globally probing the
distribution.

Keywords:

Algorithms, Routing, Meshes



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{F.Sibeyn-IPPS-1999,
AUTHOR = {Sibeyn, Jop F.},
TITLE = {Better Deterministic Routing on Meshes},
BOOKTITLE = {Proceedings of the 13th International Parallel Processing Symposium, and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP-99)},
PUBLISHER = {IEEE},
YEAR = {1999},
PAGES = {420--425},
ADDRESS = {St Juan, Puerto Rico},
MONTH = {May},
ISBN = {0-7695-0143-5},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Jop F. Sibeyn
Created
02/19/2000 03:40:29 PM
Revisions
8.
7.
6.
5.
4.
Editor(s)
Christine Kiesel
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Edit Dates
30.05.2005 16:39:21
02/14/2005 08:09:37 PM
04/04/2001 07:46:02 PM
04/04/2000 12:37:48
30.03.2000 12:26:01
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section