In this section we apply the 
scheduling algorithm to
route N packets on a 
mesh in
steps using constant-size queues. Although
-step routing algorithms for the mesh were known before
[13, 14, 39], they all have
more complicated path selection strategies.
In an 
mesh, each node has a distinct label
, where x is its column and y is its row, and 
. Thus, an 
mesh has 
nodes. For x <
n-1, node 
is connected to 
, and for y < n-1, node
is connected to 
. A 
mesh is illustrated
in Figure 2. Sometimes wraparound edges are
included, so that a node labeled 
is connected to 
and
a node labeled 
is connected to 
.
Proof:
The algorithm consists of four phases. In the first phase only those
packets that need to route up and to the right are sent. The paths of
the packets are selected greedily with each packet first traveling to
the correct row, and then to the correct column. The level of a
node is the sum of its row and column numbers. This simple strategy
guarantees that both the congestion and the number of levels of the
phase are 
. The packets are scheduled using the
-step algorithm from
Section 2. The up-right phase is followed
by up-left, down-right, and down-left phases.
mesh.