On-line Algorithms for Path Selection in a Nonblocking Network

Sanjeev Arora - F. Thomson Leighton - Bruce M. Maggs

Abstract:

This paper presents the first optimal-time algorithms for path selection in an optimal-size nonblocking network. In particular, we describe an N-input, N-output, nonblocking network with bounded-degree nodes, and an algorithm that can satisfy any request for a connection or disconnection between an input and an output in 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 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 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 bit steps, no matter what other connections have been made previously or are being made simultaneously.

• 1 Introduction
  • 1.1 Definitions
  • 1.2 Previous work
  • 1.3 Models and conventions
  • 1.4 Our results
  • 1.5 Our approach
• 2 The multi-Benes and multibutterfly networks
• 3 A proof that the multi-Benes network is nonblocking
• 4 Establishing many paths at once
  • 4.1 Unshared neighbors
  • 4.2 A level-by-level algorithm
  • 4.3 A faster algorithm
  • 4.4 Routing many paths in a nonblocking fashion on a multi-Benes network
    • 4.4.1 The subnetwork of working nodes
    • 4.4.2 Routing new paths
  • 4.5 Processing incoming calls
• 5 Extensions
  • 5.1 Multiparty calls
  • 5.2 Multiple calls to the same output
  • 5.3 Removing the distinction between terminals and non-terminals
    • 5.3.1 The network
    • 5.3.2 Constructing node-disjoint paths
    • 5.3.3 Establishing edge-disjoint paths
• 6 Acknowledgments
• References
• About this document ...