An optimal time bound for oblivious routing
type: Item
instance of: scholarly article
title: An optimal time bound for oblivious routing
zbMATH Open document ID: 0693.68028
DOI: 10.1007/BF01840387
author: Ian Parberry
published in: Algorithmica
publication date: 1990-01-01T00:00:00Z
review text: The routing problem is the problem of routing n data packets in a network of n processors. Usually, such a network is assumed to be constant- degree, i.e. each processor is connected to a constant number of other processors. A routing scheme is oblivious if the route taken by each packet depends only on its source and destination. Previous results by Borodin, Hopcroft and Lang show that oblivious routing can be done optimally in \(\theta\) (\(\sqrt{n})\) time. The author considers the case when more than n processors are available; more precisely, he shows that if p processors are available, then oblivious routing can be done in \(\theta\) (n/\(\sqrt{p}+\log n)\) time. Applications of these results are also given.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68N99
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 4135401
zbMATH Keywords: network of processors
zbMATH Keywords: parallel machines
zbMATH Keywords: shuffle-exchange
zbMATH Keywords: oblivious routing
reviewed by: Giora Slutzki
MaRDI profile type: Publication
cites work: Routing, merging, and sorting on parallel models of computation
cites work: A universal interconnection pattern for parallel computers
cites work: Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange Network
cites work: Parallel permutation and sorting algorithms and a new generalized connection network
cites work: On recurrent and recursive interconnection patterns
cites work: Q3801042
cites work: Some practical simulations of impractical parallel computers
cites work: Parallel Processing with the Perfect Shuffle
cites work: Q3326832
description: scientific article; zbMATH DE number 4135401