next up previous
Next: 5 Extensions Up: 4 Establishing many paths Previous: 4.4.2 Routing new paths

4.5 Processing incoming calls

Since the working nodes must be identified before new paths can be routed, incoming calls are processed in batches. When a new call originates at an input, it waits until the paths are established for the batch that is currently being processed. When all of the calls in that batch have been established, the working nodes are identified, and then the paths for the new batch are established. Since identifying the working nodes and routing the new paths both take at most tex2html_wrap_inline2357 bit steps, the time to process each batch is tex2html_wrap_inline2359 bit steps, and no call waits for more than tex2html_wrap_inline2361 bit steps before being established, including the time waiting for the previous batch to finish.

Bruce Maggs
Mon Jul 22 21:19:59 EDT 1996