Bounds on evacuation time for deflection routing

DOI10.1007/BF02311228MaRDI QIDQ757016zbMATH OpenFDO

Authors Bruce Hajek

Publication date 1991

Published in Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

adaptive routingdeflection routinghot potato routinghypercube networkmisrouting

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Communication networks in operations research (90B18)

Recommendations

• On the average delay for routing subject to independent deflections
• A versatile model for predicting the performance of deflection-routing networks
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Deflection routing on a torus is monotone
• Greedy hot-potato routing on the two-dimensional mesh

Cites work

• Access and Alignment of Data in an Array Processor
• Routing, merging, and sorting on parallel models of computation

Cited in

(8)

• Many-to-many routing on trees via matchings
• On the average delay for routing subject to independent deflections
• On the theory of interconnection networks for parallel computers
• Towards a better understanding of pure packet routing
• Greedy hot-potato routing on the two-dimensional mesh
• Networks on which hot-potato routing does not livelock
• Hot-potato routing on multi-dimensional tori
• Dynamic tree routing under the “matching with consumption” model

This page was built for publication: Bounds on evacuation time for deflection routing

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