next up previous
Next: 1 Introduction

On-line Algorithms for Path Selection in a Nonblocking Network

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


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 tex2html_wrap_inline1229 bounded-degree nodes, and an algorithm that can satisfy any request for a connection or disconnection between an input and an output in tex2html_wrap_inline1231 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 tex2html_wrap_inline1235 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 tex2html_wrap_inline1237 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 tex2html_wrap_inline1239 bit steps, no matter what other connections have been made previously or are being made simultaneously.



Bruce Maggs
Mon Jul 22 21:19:59 EDT 1996
anonymous logging image