MPI-INF D1 Publications: Proceedings Article: Better Deterministic Routing on Meshes

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

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

Action:

Options:

Goto entry point

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:


(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

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

Attachment Section