The generalized packet routing problem

DOI10.1016/0304-3975(87)90069-7MaRDI QIDQ580964zbMATH OpenOpenAlexFDO

Authors David Peleg, Eli Upfal

Publication date 1987

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(87)90069-7

zbMATH Keywords

communication networksexpander graphsefficient packet routingload balancing problem in distributed systemsparallel and distributed computationpermutation packet routingtoken distribution problem

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Recommendations

• An approximation algorithm for the general routing problem
• On the general routing polytope
• The generalized arc routing problem
• Routing optimization in packet switching communication networks
• Generalized network improvement and packing problems
• Packet Routing: Complexity and Algorithms
• scientific article; zbMATH DE number 4059093
• A capacitated general routing problem on mixed networks
• The general routing polyhedron: A unifying framework
• scientific article; zbMATH DE number 432994

Cites work

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Efficient Schemes for Parallel Communication
• Sorting in \(c \log n\) parallel steps

Cited in

(19)

• Packet Routing: Complexity and Algorithms
• Efficient offline algorithmic techniques for several packet routing problems in distributed systems
• scientific article; zbMATH DE number 1559579 (Why is no real title available?)
• scientific article; zbMATH DE number 7561459 (Why is no real title available?)
• scientific article; zbMATH DE number 4059093 (Why is no real title available?)
• TOKEN DISTRIBUTION AND LOAD BALANCING ON RECONFIGURABLEd-DIMENSIONAL MESHES
• Rapid convergence of a local load balancing algorithm for asynchronous rings
• A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria
• Constraint satisfaction, packet routing, and the lovasz local lemma
• An extended dimension order token distribution algorithm on \(k\)-ary \(d\)-cubes and its complexity
• Strongly adaptive token distribution
• A note on the token distribution problem
• scientific article; zbMATH DE number 1760014 (Why is no real title available?)
• Dimension-exchange token distribution on the mesh and the torus
• The general routing polyhedron: A unifying framework
• Algorithms for generalized round robin routing
• Near-perfect token distribution
• Representing shared data on distributed-memory parallel computers
• Optimal dimension-exchange token distribution on complete binary trees

This page was built for publication: The generalized packet routing problem

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