An optimal time bound for oblivious routing

DOI10.1007/BF01840387MaRDI QIDQ908701zbMATH OpenFDO

Authors Ian Parberry

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01840387

zbMATH Keywords

network of processorsoblivious routingparallel machinesshuffle-exchange

Mathematics Subject Classification ID

Theory of software (68N99) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• Optimal oblivious routing on \(d\)-dimensional meshes
• Tight bounds for oblivious routing in the hypercube
• Oblivious routing with limited buffer capacity
• Optimal oblivious routing in polynomial time
• A Time-Randomness Trade-Off for Oblivious Routing

Cites work

• A universal interconnection pattern for parallel computers
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 4068238 (Why is no real title available?)
• Interconnections Between Processors and Memory Modules Using the Shuffle-Exchange Network
• On recurrent and recursive interconnection patterns
• Parallel permutation and sorting algorithms and a new generalized connection network
• Parallel Processing with the Perfect Shuffle
• Routing, merging, and sorting on parallel models of computation
• Some practical simulations of impractical parallel computers

Cited in

(14)

• Oblivious routing with limited buffer capacity
• Network-oblivious algorithms
• Tight bounds for oblivious routing in the hypercube
• A Time-Randomness Trade-Off for Oblivious Routing
• Survey on oblivious routing strategies
• An O (log N ) deterministic packet-routing scheme
• How much can hardware help routing?
• scientific article; zbMATH DE number 1173684 (Why is no real title available?)
• scientific article; zbMATH DE number 1760011 (Why is no real title available?)
• scientific article; zbMATH DE number 1760014 (Why is no real title available?)
• scientific article; zbMATH DE number 7561477 (Why is no real title available?)
• Optimal oblivious routing in polynomial time
• Optimal oblivious routing in polynomial time
• Communication in parallel systems

This page was built for publication: An optimal time bound for oblivious routing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908701)