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.