On-line algorithms for path selection in a nonblocking network

Sanjeev Arora, F. T. Leighton, Bruce M. Maggs

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


This paper presents the first optimal-time algorithms for path selection in an optimalsize nonblocking network. In particular, we describe an N-input, N-output, nonblocking network with O(N log N) bounded-degree nodes, and an algorithm that can satisfy any request for a connection or disconnection between an input and an output in O(log N) bit steps, even if many requests are made at once. Viewed in a telephone switching context, the algorithm can put through any set of calls among N parties in O(log N) bit steps, even if many calls are placed simultaneously. Parties can hang up and call again whenever they like; every call is still put through O(log N) bit steps after being placed. Viewed in a distributed memory machine context, our algorithm allows any processor to access any idle block of memory within O(log N) bit steps, no matter what other connections have been made previously or are being made simultaneously.

Original languageEnglish (US)
Pages (from-to)600-625
Number of pages26
JournalSIAM Journal on Computing
Issue number3
StatePublished - Jun 1996

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


  • Multi-beneš
  • Multibutterfly network
  • Network
  • Nonblocking network
  • Routing algorithm


Dive into the research topics of 'On-line algorithms for path selection in a nonblocking network'. Together they form a unique fingerprint.

Cite this