Simple Algorithms for Routing on Butterfly Networks with Bounded Queues

DOI10.1137/S0097539796311818MaRDI QIDQ4229419zbMATH OpenOpenAlexFDO

Authors Bruce M. Maggs, Ramesh K. Sitaraman

Publication date 22 February 1999

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539796311818

zbMATH Keywords

circuit-switchingcommunication protocolsinterconnection networksparallel computersperformance analysisrouting algorithms

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• Sharper analysis of packet routing on a butterfly
• Concurrent threads and optimal parallel minimum spanning trees algorithm
• A theory of wormhole routing in parallel computers
• Randomized Routing and Sorting on Fixed-Connection Networks

Cited in

(9)

• Improved routing and sorting on multibutterflies
• The domination number of wrapped butterfly digraphs
• The forwarding indices of wrapped butterfly networks
• Increasing the Size of a Network by a Constant Factor can Increase Performance by More Than a Constant Factor
• Sharper analysis of packet routing on a butterfly
• scientific article; zbMATH DE number 1559567 (Why is no real title available?)
• Stochastic comparisons for rooted butterfly networks and tree networks, with random environments
• On the benefit of supporting virtual channels in wormhole routers
• Deterministic routing with bounded buffers: turning offline into online protocols

This page was built for publication: Simple Algorithms for Routing on Butterfly Networks with Bounded Queues

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