Bounds on evacuation time for deflection routing

DOI10.1007/BF02311228zbMATH Open0723.68015MaRDI QIDQ757016FDOQ757016

Authors: Bruce Hajek 

Publication date: 1991

Published in: Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

adaptive routingdeflection routinghypercube networkhot potato routingmisrouting

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)