next up previous
Next: 2.2 The algorithm Up: 2 An scheduling algorithm Previous: 2 An scheduling algorithm

2.1 Leveled networks

In a leveled network with depth L, the nodes can be arranged in L+1 levels numbered 0 through L, such that every edge in the network leads from some node on level i to a node on level i+1, for tex2html_wrap_inline2045 . The nodes in the network represent processors and the edges represent unidirectional communication links. The processors are assumed to contain some switching hardware for sending and receiving packets. We will assume that each node has in-degree and out-degree at most tex2html_wrap_inline2047 , where tex2html_wrap_inline2049 is a fixed constant.

There are 3 kinds of queues in the network. Each node has an initial queue in which packets reside before execution begins, and a final queue into which the packets destined for the node must be delivered. At the head of each edge is an edge queue for buffering packets in transit. We place no restriction on the size of the initial and final queues. The edge queues, however, can each hold at most q packets, where q is a fixed constant. In this paper we shall assume that tex2html_wrap_inline2055 . With minor modifications, however, the algorithm and the analysis can be adapted for the case q=1. At the start of the execution, all of the N packets reside in initial queues. A packet can originate on any level and can have its destination on any higher-numbered level.

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996