In this section we present a randomized algorithm for sorting packets on an -node butterfly network in
steps using constant-size queues. The algorithm is based on the *
Flashsort* algorithm of Reif and Valiant [32]. The main
difference is that we use the algorithm for scheduling packets on
leveled networks in place of their scheduling algorithm, which
requires queues of size . A similar approach has been
suggested previously by Pippenger [26].

- 8.1 The algorithm
- 8.2 Analysis
- 8.3 Bounding the load
- 8.4 Bounding the congestion at each switch
- 8.5 Bounding the cumulative delay
- 8.6 Putting it all together

Mon Jul 22 22:57:44 EDT 1996