On Load Balancing in Multicomputer/Distributed Systems Equipped with Circuit or Cut-Through Switching Capability.
AbstractFor multicomputer or distributed systems that use circuit switching, wormhole routing, or virtual cut-through (the last two are collectively called the cut-through switching), the communication overhead and the message delivery time depend largely upon link contention rather than upon the distance between the source and the destination. That is, a larger communication overhead or a longer delivery delay occurs to a message when it traverses a route with heavier traffic than the one with a longer distance and lesser traffic. This characteristic greatly affects the selection of routes for interprocessor communication and/or load balancing. We consider the load-balancing problem in these types of systems. Our objective is to find the maximum load imbalance that can be eliminated without violating the (traffic) capacity constraint and the route to eliminate the imbalance while keeping the maximum link traffic as low as possible. We investigate the load-balancing problem under various conditions. First, we consider the case in which the excess load on each overloaded node is divisible. We devise a network flow algorithm to solve this type of load balancing problem optimally in polynomial time. Next, we impose the realistic assumption that the system uses a specific routing scheme so that the excess load transferred from an overloaded node to an underloaded node must use the route found by the routing scheme. For this case, we use a graph transformation technique to transform the system graph to another graph to which the same network flow algorithm can be applied to solve the load balancing problem optimally. Finally, we consider the case in which the excess load on each overloaded node is indivisible, i.e., the excess load must be transferred as an entity. We show that the load-balancing problem of this type becomes NP-complete and propose a heuristic algorithm as a solution.
Introduction
In multicomputer or distributed systems, dynamic creation/deletion of data and/or files may
temporarily overload some nodes'/sites' storage space while leaving some others' underloaded. Since
storage resources at a node/site are usually limited, uneven data/file distribution may result in
inefficient use of storage space and affect future data/file creation. For example, some nodes/sites
may not have sufficient space to store new data/files even if the overall system has sufficient space
for all the data/files. Load balancing in this respect is thus to transfer the excess (data) load
on overloaded nodes to underloaded nodes to balance the (data) load among all the nodes in the
system.
For multicomputer or distributed systems that use circuit switching, wormhole routing [9], or
virtual cut-through [8], the communication overhead and the message delivery time depend largely
upon the link contention rather than upon the distance between the source and the destination.
That is, a larger communication overhead or a longer delivery delay results when a message traverses
a route with heavier traffic than one with a longer distance and lesser traffic. This characteristic
greatly affects the selection of routes for interprocessor communication (IPC) and/or load balancing.
The objective of selecting a route for IPC or load balancing is thus to minimize the traffic volume on
each link so that the communication overhead/delay due to link contention can be minimized. (Note
that this objective also reduces the probability of blocking future messages.) While transferring load
from overloaded nodes to underloaded ones balances the storage load among all nodes, minimizing
the maximum link contention among all links balances the communication load among all links.
The major difference between IPC and load balancing is that in the former case we must
select a route or routes for each pair of communicating processors, while in the latter case we can
select a route or routes from an overloaded node to one or more underloaded nodes. (Note that the
excess load on an overloaded node can be transferred to any underloaded node or nodes, instead of
a particular one.) Because of this difference, most, if not all, of the variations of the IPC routing
problem are NP-hard, while optimal algorithms of polynomial-time complexity exist for several
variations of the load balancing problem.
Kandlur and Shin [7] studied the route selection problem for interprocessor communication
in multicomputer networks equipped with virtual cut-through switching capability. In this paper,
we study instead the route selection problem for load balancing in multicomputer or distributed
systems that use circuit switching, wormhole routing, or virtual cut-through. Our main concern
is to find the maximum load imbalance that can be eliminated (and the routes to eliminate the
imbalance) without violating the (traffic) capacity constraint 3 on each link, while keeping the
maximum link contention as low as possible.
Our work is a significant extension to Bokhari's work [3]. He solved the load balancing problem
under several restricted assumptions: 1) there is only unit load imbalance on each overloaded or
underloaded node, i.e., each node has either one unit of excess load or one unit of deficit load, or
is neutral, and 2) contention is not allowed on any link, i.e., no more than one unit of excess load
can be transferred via any link. Moreover, his solution approach does not take into account the
contention between the excess load transferred among processors and the other IPC traffic. In this
paper, we relax these assumptions: the load imbalance on each node can be any arbitrary value
instead of one unit only, and more than one unit of excess load can be transferred via a link as long
as the link's (traffic) capacity constraint is not violated. Two cases are studied. First, we consider
the case in which the excess load on each overloaded node is divisible, i.e., can be arbitrarily divided
and transferred to one or more underloaded nodes. Second, we consider the case in which there
may be one or more entities of excess load on each node, and each of them is indivisible and must
be transferred to an underloaded node as an entity. We also take into account the effect of existing
IPC traffic on route selection for transferring excess load. As a result, the load balancing problem
considered in this paper is much more general and practical, and more difficult to solve, than the
one treated in [3].
In [3], Bokhari considered multicomputer systems that use some specific routing schemes.
In particular, he considered mesh and hypercube interconnection networks that use row-column
(column-row) and e-cube routing schemes, respectively. He used a graph transformation technique
and a network flow algorithm to solve the load balancing problem in these systems. The graph
transformation schemes used for meshes and hypercubes are different, and their correctness is not
trivial to prove, especially for the case of hypercube interconnection networks. In contrast, we
propose a simple, unified graph transformation scheme and a network flow algorithm to solve the
load balancing problem in multicomputer/distributed systems with and without specific routing
schemes. The proposed graph transformation scheme, together with the network flow algorithm,
works for a larger class of routing schemes, including both the row-column (column-row) and e-
cube schemes. The proposed scheme also has an intuitive appeal, and its correctness is very easy
to prove.
With the proposed graph transformation scheme and the network flow algorithm, we show
that for the case of divisible excess load, the load balancing problem with or without specific
routing schemes can be solved optimally in polynomial time, i.e., we can find the maximum load
3 to be defined later.
imbalance that can be eliminated without violating the traffic capacity constraint on each link while
minimizing the maximum contention among all links. For the case of indivisible excess load, we
first prove that the load balancing problem is NP-complete, and then propose a heuristic algorithm
for it.
The rest of the paper is organized as follows. In Section 2, we formally define the load
balancing problem considered in this paper and briefly review a network flow problem whose solution
algorithms will be used to solve our load balancing problem. In Section 3, we discuss how to apply
the network flow algorithm described in Section 2 to optimally solve the load balancing problem
under the assumptions that excess load is divisible and there is no specific routing scheme in the
system under consideration. In Section 4, we show how to transform the representing graph of a
system with a specific routing scheme to another graph, so that the technique described in Section 3
can be used to find an optimal solution for the load balancing in the system. In Section 5, we give
an NP-complete proof and a heuristic algorithm for the load balancing problem with indivisible
excess load. The paper concludes with Section 6.
Problem formulation and a network flow algorithm
2.1 Problem formulation
The system under consideration is either a distributed point-to-point network or a multicomputer
with an interconnection structure, such as a mesh or a hypercube. We will use a directed
graph E) to represent the system, where the vertex/node set V represents the set of
nodes/processors in the system, and the edge set E represents the set of communication links.
Also, a traffic capacity (or simply, capacity) function C is defined on the edge set E, i.e., each edge
associated with a (traffic) capacity C(v which is the maximum communication
volume (measured in data units, such as bits, bytes, or packets) that can take place from node v i
to node v j . If there is no such constraint on a link (u; v), C(u; v) is defined to be 1. Note that
the traffic capacity defined in this paper is not the link bandwidth which is the maximum data
transmission rate of a link. We can think of the traffic capacity of a link as the maximum contention
(to be defined later) allowed on the link. Also note that using the notation (v to denote an
edge allows at most one edge from a vertex to another vertex. This, however, does not impose
any unnecessary constraints as multiple edges from a vertex to another vertex can be transformed
into single edges by introducing a new vertex for each of them and properly redefining the capacity
function.
We assume that when the system needs to perform load balancing, each node is either over-
loaded, underloaded, or neutral. The (total) excess load on an overloaded node s
by e i , and the deficit load on an underloaded node t j 2 V is denoted by d j . The excess and deficit
loads can be any arbitrary values, as opposed to only one unit as assumed in [3]. As in [3], we
assume that the global state of the system and the degree of load imbalance on each node are known
to the central load balancing controller. (The determination of the degree of load imbalance on each
node is beyond the scope of this paper.) We require at most e i units of load to be transferred from
an overloaded node s i to other underloaded nodes, and at most d j units of load to be transferred
to an underloaded node t j from other overloaded nodes. We call this requirement the load transfer
constraint. We also assume, without loss of generality, that transferring one unit of load over a link
incurs one unit of communication volume on the link. The link capacity constraint requires that
the total communication volume on a link (v not exceed the the traffic capacity C(v
of the link.
The system may or may not use a specific routing scheme. If a specific routing scheme is
used, a path P from v i to v j is said to be feasible (under the underlying routing scheme) if the
routing scheme will find P as one possible path from v i to v j . We assume that there is at least one
feasible path from a vertex to any other vertex (so jEj - jV j). Note that there may be one or more
feasible paths from a vertex to another vertex. Since we assume there is at most one edge from a
vertex to another vertex, we can use a sequence of vertices
, to denote a path. In
this paper, we consider only the routing schemes that satisfy the following properties:
P1. Each edge in E is a feasible path, i.e., if (v is a feasible path from v i to v j .
P2. Any sub-path of a feasible path is also feasible, i.e., if path v i 1
is feasible then path
is also feasible, for all 1
P3. If the last edge of a feasible path overlaps the first edge of another feasible path, then the path
formed by combining these two feasible paths is also feasible, i.e., if v i 1
and
are two feasible paths, then v i 1
is also feasible, for
Fig. 1).
The routing schemes commonly used in meshes and hypercubes are the row-column (column-
row) and e-cube routing algorithms, respectively. A mesh interconnection network can be considered
as a two dimensional array, in which each processor, denoted by hx; yi, is connected to its four
neighboring processors hx \Sigma 1; yi and hx; y \Sigma 1i (the boundaries of the array may be wrapped
around). On the other hand, an n-dimensional hypercube (n-cube) has 2 n processors labeled from
each processor is labeled by the binary representation/address, hb
feasible feasible

Figure

1: Property P3 of routing schemes considered in this paper.
Two processors are connected to each other if and only if their binary addresses differ in exactly
one bit.
The row-column algorithm on meshes routes a message/packet first horizontally from its
source node to the node that is at the same column as its destination node, and then vertically to
its destination node. For example, a message with source node h3; 4i and destination node h5; 2i will
be routed via the path h3; 4i, h4; 4i, h5; 4i, h5; 3i, h5; 2i. The e-cube algorithm on hypercubes always
routes a message to the node that more closely matches the address of the destination node with the
comparison beginning from the least significant bit of the addresses. For example, a message with
source node h01110i and destination node h10101i will be routed via the path h01110i, h01111i,
h01101i, h00101i, h10101i.
It is easy to check that the row-column (column-row) routing algorithm on meshes satisfies
properties P1-P3, and the e-cube routing algorithm on hypercubes satisfies properties P1-
P2. To check that the e-cube routing algorithm also satisfies P3, let v
and
be two feasible paths in an n-cube under the e-cube routing algorithm, and let the
addresses of v i j
and v i j+1
be hb
respectively (recall that
since
and v i j+1
are two adjacent nodes, their binary addresses differ only in one bit). According
to the e-cube algorithm, the addresses of all the nodes v i j+1
must have the form
it is easy to see that the path v i 1
formed
by combining the two feasible paths is also a feasible path.
We want to find the maximum load imbalance that can be eliminated (and the routes to
eliminate the imbalance) without violating the link capacity and load transfer constraints while
minimizing the maximum link contention.
2.2 The minimax flow algorithm
Our solution approach to the load balancing problem considered in this paper is based on the
flow problem and its solution algorithm described in [6]. 4 This minimax flow algorithm
finds a maximum flow for a network with a 0/1 weight function that also minimizes the maximum
edge cost (the cost of an edge is defined to be the weight times the flow of the edge). Applying this
algorithm to the load balancing problem, one can view the maximum flow as the maximum load
imbalance that can be eliminated, and the edge cost as link contention.
Before describing our solution approach for the load balancing problem, we first give a brief
review on the minimax flow problem/algorithm. Details on the network flow problem and the
flow problem/algorithm can be found in [10] and [6], respectively.
t; C) be a network with vertex/node set V , edge set E, source s, sink t,
and capacity function E) is the underlying directed graph 5
with is the set of positive real numbers. Each edge (u; v) 2 E is
also associated with a nonnegative real-valued weight w(u; v). For ease of discussion, we define
both C and w are defined on V \Theta V ). If
we say that the network has a 0/1 weight function w.
A flow in a network N is a function that satisfies the following
properties:
1. Capacity constraint
2. Conservation condition:
For each edge (u; v) 2 E, f(u; v) is called the flow in (u; v). For each (u; v)
is called the net flow from u to v. The capacity constraint states that the flow in (u; v) is bounded
by the capacity C(u; v), and the conservation condition states that the net flow going into a node,
except the source and the sink, is equal to the net flow going out of the node. The value of a flow
f , denoted as jf j, is the net flow going out of the source, i.e.,
For the load balancing problem with divisible excess load, transferring f(u; v) units of load
from u to v and f(v; u) units of load from v to u (assuming that f(u; v) - f(v; u)) can be replaced
4 It has been brought to our attention that Ahuja [2] has designed a similar algorithm to solve the minimax
transportation problem, and his algorithm can also be adapted to solve the minimax flow problem.
5 Without loss of generality, we assume that G is a simple graph, i.e., it has no loop (an edge from a vertex v to
itself) and no multiple edges (edges from a vertex u to another vertex v). Therefore, each edge can be represented
by the two end vertices of the edge. Note, however, that this assumption can be easily enforced by introducing
"dummy" vertices and properly redefining the capacity and the weight functions if graph G does not originally satisfy
the assumption.
by transferring f(u; v) \Gamma f(v; u) units of net load from u to v without changing the value of the flow
(load) and without increasing the contention (flow) in any edge of the network. Therefore, f is a
flow with f(u; v) - f(v; u) ? 0, the flow in (u; v) can be simply replaced by f(u; v) \Gamma f(v; u) and
the flow in (v; u) by 0 (note that f(u; v) - f(v; u) ? 0 implies that both (u; v) and (v; u) belong to
E). Note, however, that the above replacement operation is not valid if excess load is indivisible
since one indivisible excess load of f(u; v) units transferred from u to v and another indivisible
excess load of f(v; u) units transferred from v to u cannot cancel each other and be replaced by a
single load transferred from one vertex to the other.
If (u; v) 2 E and f(u; we say that flow f saturates edge (u; v) and call (u; v) an
f-saturated edge in N . The (edge) cost (with respect to flow f) of each edge (u; v) 2 E is defined
to be w(u; v) \Delta f(u; v), and the (total) cost of a flow f is defined to be
v). The
flow problem [6] is to find a maximum flow f which minimizes the maximum edge cost,
i.e., minimizes max (u;v)2E w(u; v) \Delta f(u; v). We will show that our load balancing problem can be
transformed to the minimax flow problem with a 0/1 weight function. We henceforth concentrate
on networks with 0/1 weight functions.
Definition. Given a network t; C) with a 0/1 weight function w, define
to be a new network with
for each edge (u; v) 2 E. An edge (u; v) 2 E fi is called a
critical edge if w(u;
Let f   be a maximum flow in N and f fi a maximum flow in N(fi). Since C fi (u; v) - C(u; v)
for all (u; v) 2 E, we have jf
v)g. It is easy to see
that
fi. Therefore, jf
fi. The capacity fi of the critical
edges in N(fi) is the maximum edge cost (note that the weight of a critical edge is 1) allowed for
the network N(fi), and hence, the minimum value of the maximum edge cost for a maximum flow
in N is fi   , where fi   is the minimum value of fi such that jf fi
is a maximum flow in N(fi). 2
We propose in [6] a minimax flow algorithm, MMC01, as a solution to the minimax flow
problem with a 0/1 weight function. MMC01 simply finds fi   and constructs a maximum flow
for the network N(fi   ). For completeness, we list Algorithm MMC01 in Fig. 2 and summarize
it below. However, for the sake of conciseness, we omit the proofs of the correctness and time
complexity of the algorithm. The interested reader is referred to [6] for details.
The idea behind Algorithm MMC01 is that in each iteration, variable fi of the constructed
network N(fi) is set to the maximum edge cost allowed in that iteration. With this maximum edge
Algorithm MMC01
Step 1. Find a maximum flow f   and its value jf   j for the network t; C).
Step 2. Let ' be the number of edges with nonzero weights in N (w.l.o.g. assume ' - 1).
Step 3. Construct network
Find a maximum flow f fi and its value jf fi j for N(fi).
If jf to Step 5.
Step 4. Let \Delta := jf
Let R be the set of f fi -saturated critical edges in N(fi), i.e.,
Go to Step 3.
Step 5. A maximum flow, f fi , that minimizes the maximum edge cost is found, and the maximum
edge cost with respect to flow f fi is fi.

Figure

2: Algorithm for minimax flow problem with a 0/1 weight function.
cost, the capacity of an edge (u; v) with w(u; set to min(C(u; v); fi), i.e., the flow allowed to
go through edge (u; v) is restricted to min(C(u; v); fi), and hence, the cost of edge (u; v) is bounded
by min(C(u; v); fi) \Delta w(u; v) - fi. The algorithm repeatedly constructs maximum flows for networks
N(fi) with increasing values of fi (Steps 3-4). Initially, fi := 0 (Step 2). If jf there is a
maximum flow with zero cost. Otherwise, if jf
fi, the
optimal value of fi (i.e., the minimum value of the maximum edge cost, fi   ) is found.
In Step 3, if jf the optimal value of fi has not been found. For each (u; v)
if w(u; is an f fi -saturated critical edge in N(fi).
Therefore, to get a larger flow, we need to increase the capacities of critical edges. Let \Delta and - be
defined as in the algorithm (Step 4). It has been shown in [6] that fi + \Delta=- fi   . Hence, we set
\Delta=- and repeat the process (Step 4). This assignment guarantees that the value of fi is
always less than or equal to the optimal value fi   , and upon termination jf
. It has also been shown in [6] that Algorithm MMC01 terminates in at most ' iterations,
and hence has a time complexity of O(' \Delta M(n;m)), where ' is the number of edges with nonzero
weight and M(n;m) is the time complexity of the algorithm used in Algorithm MMC01 to find a
maximum flow in a network with jV vertices and edges.
3 Systems without specific routing schemes
In this section, we discuss the load balancing problem for systems without being constrained
by any specific routing scheme, i.e., the excess load to be transferred from an overloaded node s i
to an underloaded node t j can use any route (path) from s i to t j .
We first consider the case in which the excess load on each overloaded node can be arbitrarily
divided and transferred to one or more underloaded nodes. For example, if node v i has excess
load e i , and nodes v j and v k have deficit load d j and d k , respectively, we can transfer e ij and e ik
units of load from v i to v j and v k , respectively, where
of e are real numbers. In the case where excess load is indivisible, i.e., each
overloaded node may have one or more entities of excess load each of which can only be transferred
to an underloaded node as an entity, the load balancing problem becomes more difficult. We defer
the discussion of this case until Section 5.
For the case that excess load is arbitrarily divisible, Algorithm MMC01 described in Section
2.2 can be easily applied to find the maximum amount of load imbalance that can be eliminated
while minimizing the maximum link contention. Given the graph representation E) of a
multicomputer or distributed system, and its capacity function C, let ae V be
the set of overloaded nodes with node s i having excess load e i , and
be the set of underloaded nodes with node t j having deficit load d j , where e i 's and d j 's are
all real numbers (note that Recall that e i is the (maximum) amount of load
on s i to be transferred to other underloaded nodes, and d j is the maximum amount of load
can receive from other overloaded nodes. (As mentioned in Section 1, we assume that e i 's
and d j 's are given and their determination is beyond the scope of this paper.) We construct
a new graph G 0 by adding to G a new source node s, a new sink node t, and
t)g. Define a new capacity function C 0
for (v is the current communication volume on link (v due to the
interprocessor communication traffic, i.e., C 0 (v is the maximum amount of load that can be
transferred on link (edge) (v violating its traffic capacity constraint. Finally, the
weight function w is defined as w(u;
Recall that in the load balancing problem considered in this paper, we want to find the
maximum amount of load imbalance that can be eliminated while minimizing the maximum link
contention. This is equivalent to find a minimax flow in the network with the
0/1 weight function w. Let f(v be the amount of load that will be transferred on link (v
when the load balancing procedure is activated. There are two possible ways to define the link
contention, depending on the type of communication traffic to be minimized on a link: C1) if we
are concerned with minimizing the amount of total communication traffic on link (v
the contention to be F (v if we are concerned with minimizing the amount of
load to be transferred on link (v we define the contention to be f(v
For C2, we simply use Algorithm MMC01 to find a minimax flow f for the network
(with the weight function w). The value jf j and the maximum edge cost of the
flow f found by MMC01 are the maximum load imbalance that can be eliminated and
the maximum edge contention under that flow, respectively. For C1 where the link contention is
defined as F (v the network N(fi) should be redefined as follows.
F be defined as above. Define
to be a new network with
for each edge (u; v) 2 E. An edge (u; v) 2 E fi is called a
critical edge if w(u;
Moreover, the initial value of fi in Step 2 of MMC01 should be changed to max (u;v)2E F (u; v). In
this case, the value of fi in each iteration of MMC01 is the maximum contention, F (u; v)
allowed for that iteration.
Since both cases C1 and C2 can be solved similarly except that the graph representations
need to be appropriately defined, unless otherwise stated, we assume in the following discussion
that the contention of an edge (u; v) is defined to be f(u; v), i.e., the total amount of excess load
that is to be transferred on that edge.
Suppose excess load is not arbitrarily divisible. Without loss of generality, we assume that
the smallest indivisible load entity is one unit. In this case, the flow f and the capacity C should be
redefined as functions from V \Theta V to Z is the set of positive integers. Algorithm
MMC01 can still be applied to find a (integral) minimax flow for the network N , except that the
statement fi := fi + \Delta=- in Step 4 should now be changed to fi := fi
G G'
x
xy
xz
jl
ik

Figure

3: Illustration of graph transformation.
4 Systems with specific routing schemes
In this section, we discuss the load balancing problem for systems with special routing schemes
(that satisfy properties P1-P3). As discussed in Section 2, both the row-column (column-row)
routing scheme for meshes and the e-cube routing scheme for hypercubes satisfy properties P1-P3.
In [3], these two routing schemes were handled differently in solving the load balancing problem.
In fact, using the approach described in [3], different graph transformation methods need to be
designed for different routing schemes. In contrast, we propose a unified graph transformation
scheme which can be applied to different routing schemes as long as they satisfy properties P1-P3.
Given a system graph E) and a specific routing scheme that satisfies properties P1-
P3, we first transform G into another graph G according to the following rules (see
Fig.
R1. For each vertex v x 2 V , there are d(v x
x;d are the in-degree, out-degree, and
total degree, respectively, of vertex v x in G. Each vertex v i
called an
in-vertex/node (of v x ), corresponds to an incoming edge (v and each vertex v
xz ,
called an out-vertex/node (of v x ), corresponds to an outgoing edge (v x
v x in G.
R2. Let v
ik
and v i
xy correspond to the edge (v G. There is a corresponding edge (v
ik
xy
in G 0 with the same capacity as (v and with the weight of 1.
R3. If v is a feasible path from v i to v j in G, add an edge (v i
xz ) in graph G 0 with a capacity
of 1 and a weight of 0, where (v
xy
jl
are the edges in G 0 corresponding
to the edges (v
R4. For each overloaded node v i , add to G 0 a node s i and d
ik

Figure

4: The transformed graph of a 3 \Theta 3 mesh that uses the row-column routing scheme.
each of which has a capacity of e i and a weight of 1, where e i is the (total) excess load on v i .
For each underloaded node v j , add to G 0 a node t j and d i (v j ) edges (v i
jl
each of which has a capacity of d j and a weight of 1, where d j is the deficit load on v j .
R5. Add to G 0 a source s, a sink t, an edge (s; s i ) with a capacity of e i and a weight of 0 for each
overloaded node v i (s i ), and an edge with a capacity of d j and a weight of 0 for each
underloaded node v j (t j ).
After the system graph G is transformed into G 0 , we can treat the system represented by G 0 as one
without any specific routing scheme, and solve the load balancing problem by finding a minimax
flow for the network with the weight function w as described in Section 3,
are the capacity and weight functions defined in rules R1-R5.
The transformed graphs (obtained by applying only rules R1-R3) of a 3 \Theta 3 mesh that uses
the row-column routing scheme and a 3-cube that uses the e-cube routing scheme are shown in
Fig. 4 and Fig. 5, respectively. Note that we assume each link between two adjacent nodes u and v
in a mesh or a hypercube is a bi-directional communication link, and thus, there are two directed
edges (u; v) and (v; u) corresponding to this link in the graph representation of the mesh or the
hypercube. From Fig. 4, it is easy to see that whenever a routing path uses a horizontal edge, it
will no longer be able to use a vertical edge, and hence, each directed path from an out-vertex to an

Figure

5: The transformed graph of a 3-cube that uses the e-cube routing scheme.
in-vertex in the transformed graph corresponds to a feasible path found by the row-column routing
scheme in the mesh and vice versa.
The transformed graph also satisfies the requirement of the e-cube routing scheme for hy-
percubes. For example, consider node h011i in Fig. 5. From the definition of the e-cube routing
scheme, a path going into node h011i from node h010i can go to either node h001i or node h111i, a
path going into node h011i from node h001i can only go to node h111i, and a path going into node
h011i from node h111i can go nowhere.
To formally prove the correctness of the transformation, it suffices for us to prove the following
theorem.
Theorem 1: Suppose the routing scheme used in the system under consideration satisfies properties
P1-P3. Every feasible routing path from a vertex v x to another vertex v y in G corresponds
to a unique directed path from an out-vertex v
xz of v x to an in-vertex v i
yw of v y in the transformed
graph G 0 and vice versa (assume G 0 is derived by applying rules R1-R3 to G).
y is a feasible path from v x to v y in G. From property
P2, we know that each (sub-)path v j l
feasible path in G,
and from transformation rules R1-R3, it is easy to see that there exists a directed path v
yw in G 0 .
On the other hand, suppose
zw is a directed path in G 0 . From the
transformation rules, it is easy to see that each edge must satisfies that either u 0 is
an in-vertex and v 0 is an out-vertex or vice versa. Moreover, if u 0 is an in-vertex and v 0 is an
out-vertex, then u 0 and v 0 correspond to the same vertex in G. Therefore, k must be even and all
are out-vertices, and all v 0
are in-vertices. Moreover, each pair of
vertices
2l
and v 0
correspond to the same vertex, say v
2l
is an in-vertex of v j l
and v 0
is an out-vertex of v j l
, for some i l and . Now, from the
transformation rules R1 and R2, we know that v x
y is a (directed) path from v x to
v y in G. For notational simplicity, let v
and
. We next prove by induction that path
is feasible. Specifically, we will show that all the paths v j 0
are feasible. Since (v
E, from property P1, we have that path v
is feasible in G.
Suppose path v j 0
feasible in G. Since (v 0
) is an
edge in G 0 , from the transformation rule R3 we know that v j
is a feasible path in G.
Then, by property P3, we conclude that path v
5 Systems with indivisible excess load
In this section, we discuss the case in which excess load is indivisible. We assume that there
is no specific routing scheme in the system. For systems that use certain specific routing schemes,
one can first apply the graph transformation rules described in Section 4 to the representing graph
and then treat the transformed graph as a system with no specific routing scheme.
As discussed in Section 3, in a system with indivisible excess load, each overloaded node s i
has one or more entities of excess load e i1
, for some k i - 1, each of which can only be
transferred to an underloaded node as an entity. Without loss of generality, we assume that each
overloaded node s i has exactly one entity of indivisible excess load e i since if s i has
of excess load, we can add a new overloaded node s ij with one entity of indivisible excess load e ij
and a new edge each entity of excess load e ij neutral
node. Note that we use e to refer to either the entity of excess load or its amount.
We first show that the load balancing problem with indivisible excess load is NP-hard in the
strong sense [5] (in fact, we show that the problem of finding the maximum load imbalance that
can be eliminated without considering the link contention is already NP-hard in the strong sense if

Figure

Instance construction in the NP-completeness proof.
the excess load is indivisible). We then propose a heuristic algorithm as a solution to the NP-hard
case of the load balancing problem. The decision version of the load balancing problem of finding
the maximum load imbalance that can be eliminated is to ask, given a number B, whether or not
it is possible to eliminate at least B units of load imbalance (without violating the link capacity
and load transfer constraints).
Theorem 2: The decision version of the load balancing problem of finding the maximum load
imbalance that can be eliminated is NP-complete in the strong sense if the excess load is indivisible.
Proof: It is easy to see that the decision version of the load balancing problem is in NP. To
complete the proof, we reduce to it the multiprocessor scheduling problem [5]: Given a set A
of n tasks, a length l(a i ) for each 1 - i - n, a number p of processors, and a
deadline D, is there a partition of A such that max 1-i-p (
Given an instance of the multiprocessor scheduling problem, we construct an instance of the
load balancing problem (shown in Fig. 6) in which (1) each s i an overloaded node with
indivisible excess load of l(a i ) units, and t is an underloaded node with deficit load of
units; (2) there are p node-disjoint paths from u to v, all the edges on these paths have a capacity
D, all the other edges have an infinite capacity, and
Note that the construction
can be done in polynomial time.
It is easy to see that at least B units of load imbalance can be eliminated without violating the
link capacity and load transfer constraints if and only if there exists a solution for the multiprocessor
scheduling problem. Since the multiprocessor scheduling problem is NP-compete in the strong sense,
the decision version of the load balancing problem with indivisible excess load is also NP-complete
in the strong sense. 2
Since it is unlikely to find a polynomial time optimal algorithm for the load balancing problem
with indivisible excess load, we propose below a heuristic algorithm for the problem. Let E)
be the graph representation of the multicomputer or distributed system under consideration, and
C(u; v) be the capacity (for load transferring purpose) of edge (u; v), for all (u; v) 2 E. Let s i ,
be the overloaded nodes and t i q, be the underloaded nodes. Each overloaded
node s i has indivisible excess load e i which must be routed to an underloaded node as an entity, and
each underloaded node t i has deficit load d i which is the maximum amount of load it can receive
from overloaded nodes. Without loss of generality, we assume that e i 's are sorted in non-increasing
The heuristic algorithm (see Fig. 7) consists of two phases. In Phase I, we treat the excess load
as if it were divisible and use the network flow technique described in Section 3 to find a minimax
flow f . If the excess load was indeed divisible, f would be an optimal solution in which the value jf j
is the maximum load imbalance that can be eliminated with the maximum link contention (cost)
minimized. In Phase II, we use the minimax flow f found in Phase I as a "template" and route
the entities of excess load one by one in such a way that the resulting flow on each link will be as
close to the corresponding minimax flow as possible, i.e., the value f(u; v) found in Phase I serves
as the target flow (load) for edge (u; v) to be achieved in Phase II. Since in general larger amounts
of excess load are more difficult to route than smaller amounts, we will route the excess load in
non-increasing order of load amount.
During the execution of Phase II, f 0 (u; v) is the total load currently routed through edge
v). If the excess load currently being routed is e i , we say that an edge (u; v) is feasible if
a path from s i to t is feasible 6 if all edges on the path are feasible.
We will route excess load e i from the overloaded node s i to an underloaded node t j (actually, to
node t) only via a feasible path, i.e., excess load can only be routed via a path in which each edge
has enough (remaining) capacity. Note that in Phase II, vertex s and edges (s; s i
are, in fact, not used, i.e., the underlying graph is G
qg.
The excess load e i is routed using a greedy type algorithm, called ordered depth-first search
(O-DFS). Note that f(u; v) \Gamma f 0 (u; v) is the difference between the target flow f(u; v) and the total
load f 0 (u; v) currently routed through edge (u; v). A large f(u; implies that the
current load routed through edge (u; v) is still far from the target value (note that f(u;
may be negative). Therefore, at each vertex u, we always choose to traverse next the edge (u; v)
that has the largest f(u; \Delta) \Gamma f 0 (u; \Delta) value among all feasible outgoing edges at u, and hence, reduce
6 Note that we overload the word "feasible" here. The term "feasible path" defined here is different from that
defined in Section 2.1.
Phase I.
Step 1. Construct a network
and
Let w(u;
Step 2. Treat each excess load e i as a divisible load, and use Algorithm MMC01 to find a minimax
flow f for N .
Phase II.
Step 1. Set f 0 (u; v) := 0, for all (u; v)
Step 2. For i / 1 to p do the following:
Step 2.1. Use the ordered depth-first-search (O-DFS) algorithm to find a feasible path from
s i to t, where the ordered DFS algorithm is similar to the DFS graph traversal algorithm
[4], except that when branching out from a vertex we always choose to traverse next the
edge that has the largest f(\Delta; \Delta) \Gamma f 0 (\Delta; \Delta) value among all untraversed feasible edges at
that vertex.
Step 2.2. If there does not exist any feasible path from s i to t, it means that the excess
load e i will not be eliminated when the next round of load balancing is performed. If
there exists a feasible path from s i to t, let P be the (first) path found by the O-DFS
algorithm (P will be used as the route to eliminate the excess load e i when the next
round of load balancing is performed). Reset f 0 (u; v) := f 0 (u; v) each edge (u; v)
on P .

Figure

7: A heuristic algorithm for the case that excess load is indivisible.
the maximum f(u; \Delta) \Gamma f 0 (u; \Delta) value at u.
Note that the heuristic algorithm is not an optimal algorithm. It may not find the maximum
load imbalance that can be eliminated, and in cases in which it does find the maximum load
imbalance, it may not minimize the maximum link contention. We use the following example to
further illustrate the heuristic algorithm.
Example 1: Suppose the constructed network of a system graph E)
and the minimax flow f found at the end of Phase I are shown in Fig. 8(a). The maximum edge
7/7
7/4
9/4
9/3
7/5
s
(a)
9/3
(b)
9/3
(c)
9/3
(d)
9/3 2/2

Figure

8: An example that shows how the heuristic algorithm works.
cost (link contention) shown in the figure is 4 (note that only edges in E are considered).
In Phase II, we initially set f 0 (u; We first route excess load
e 1 . Starting from vertex s 1 , since f(s 1 the
O-DFS algorithm will first visit vertex v 2 . Since (v is the only feasible outgoing edge (i.e.,
the next vertex visited is t 2 . Then, vertex t is visited and a
feasible path from s 1 to t is found for e i , i.e., the path s t. For each edge (u; v) on that path,
we reset f 0 (u; . The current values of C 0 (u;
all are shown in Fig. 8(b).
We next route excess load e 2 . Using the O-DFS algorithm, we find the feasible path s
for e 2 . Note that at vertex s 2 , although f(s
still choose edge 5). For
each edge (u; v) on the path found for e 2 , we reset f 0 (u; . The current values of
are shown in
Fig. 8(c).
The next excess load to be routed is e 3 , and the path found for e 3 is s t. The values of
routed
and f 0 is updated are shown in Fig. 8(d).
Finally, we route excess load e 4 . Starting from s 4 , O-DFS first traverses edge
vertex t 3 , since there is no feasible outgoing edge, O-DFS backtracks to vertex s 4 , and then traverses
edge since t 3 has been visited, O-DFS next traverses (v
both 2, the next
edge traversed is and the path found for e 4 is s t. The values of C 0 (u;
and routed and f 0 is updated
are shown in Fig. 8(e).
The amount of load imbalance that can be eliminated in this example is 7
and the maximum link contention is 7. 2
The time complexity of the heuristic algorithm is shown in the following theorem.
Theorem 3: Phase I of the heuristic algorithm has a worst-case time complexity of O(m \Delta
M(n;m)), where is the time complexity of finding a maximum
flow in a network of O(x) vertices and O(y) edges. Phase II of the heuristic algorithm has a
worst-case time complexity of O(p is the number of excess load entities.
Proof: The complexity of Phase I is discussed in Section 2.2. (note that there are m edges with
nonzero weight in N ).
As mentioned earlier, the underlying graph in finding paths from overloaded nodes to underloaded
nodes in Phase II is G
where q is the number of underloaded nodes. The well-known DFS algorithm can be done in
x is the number of vertices and y is the number of edges of the graph
traversed. For our O-DFS algorithm, each time when we first visit or backtrack to a vertex, we
always traverse an untraversed edge with the maximum f(\Delta; \Delta) \Gamma f 0 (\Delta; \Delta) value. Therefore, traversing
all outgoing edges at a vertex u takes at most O(d is the out-degree
of u and the logarithm is to the base 2. Thus, the total time to route excess load entities is at most
[1, 4]
Since we need to route p excess load entities, e i the worst-case time complexity of Phase
II is O(p m). (Note that since we assume there is
only one entity of indivisible excess load on each overloaded node and there is at least one directed
path from a vertex to any other vertex in G, we have m
6 Conclusion
In this paper, we consider the load balancing problem in multicomputer or distributed systems
that use circuit switching, wormhole routing, or virtual cut-through, with the objective of
finding the maximum load imbalance that can be eliminated without violating the (traffic) capacity
constraint on any link while minimizing the maximum link contention among all links.
We solve the problem under various conditions. We give an O(m \Delta M(n;m)) optimal algorithm
for the load balancing problem with divisible excess load, where n is the number of nodes/processors
and m is the number of links in the system, and M(x; y) is the time complexity of finding a maximum
flow in a network of x vertices and y edges. We propose a graph transformation technique for
systems with specific routing schemes that satisfy properties P1-P3 described in Section 2.1. This
graph transformation technique transforms the representing graph of a system to another graph
with which the load balancing problem can be solved optimally in the same manner and with the
7 It is easy to see that if each overloaded node has more than one entity of indivisible excess load, the time
complexity of Phase II should be changed to O(p since we will add p vertices and p edges to
the system graph (however, we still have m - n ? q).
same time complexity as the load balancing problem for systems without specific routing schemes.
We also consider the load balancing problem for the case in which excess load is indivisible. We
prove that the problem is NP-hard and propose, based on the O(m \Delta M(n;m)) optimal algorithm
for the problem with divisible excess load, an O(m \Delta M(n;m)+ m) heuristic algorithm as
a solution to the problem, where p is the number of excess load entities.
The result obtained in this paper is a significant extension to Bokhari's work reported in [3].
We generalize his work in several directions: 1) we relax the assumption of unit load imbalance; 2)
we relax the assumption of unit link contention; 3) we consider the effect of existing IPC traffic on
the selection of routes for load balancing; 4) our graph transformation technique and network flow
model can be applied to a larger class of routing schemes. Moreover, our solution approach and
algorithms are more intuitive and simpler than those proposed in [3].



--R

The Design and Analysis of Computer Algorithms.
Algorithms for the minimax transportation problem.
A network flow model for load balancing in circuit-switched multicomput- ers
Introduction to Algorithms.
Computers and Intractability: A Guide to the Theory of NP-Completeness
A fast algorithm for the minimax flow problem with 0/1 weights.
Traffic routing for multicomputer networks with virtual cut-through capability
Virtual new computer communication switching technique
A survey of wormhole routing techniques in direct networks.
Data Structures and Network Algorithms.
--TR

--CTR
Michael E. Houle , Antonios Symvonis , David R. Wood, Dimension-exchange algorithms for token distribution on tree-connected architectures, Journal of Parallel and Distributed Computing, v.64 n.5, p.591-605, May 2004
Patrick P. C. Lee , Vishal Misra , Dan Rubenstein, Distributed algorithms for secure multipath routing in attack-resistant networks, IEEE/ACM Transactions on Networking (TON), v.15 n.6, p.1490-1501, December 2007
minimax flow problem;overloaded/underloaded nodes;load balancing;excess/deficit load;link traffic