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 . 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 , where 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 . 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.

Mon Jul 22 22:57:44 EDT 1996