Cc. Han et al., On load balancing in multicomputer/distributed systems equipped with circuit or cut-through switching capability, IEEE COMPUT, 49(9), 2000, pp. 947-957
For multicomputer or distributed systems that use circuit switching, wormho
le routing. or virtual cut-through (the last two are collectively called th
e cut-through switching), the communication overhead and the message delive
ry time depend largely upon link contention rather than upon the distance b
etween the source and the destination. That is, a larger communication over
head or a longer delivery delay occurs to a message when it traverses a rou
te with heavier traffic than the one with a longer distance and lesser traf
fic. This characteristic greatly affects the selection of routes for interp
rocessor communication and/or load balancing. We consider the load-balancin
g problem in these types of systems. Our objective is to find the maximum l
oad imbalance that can be eliminated without violating the (traffic) capaci
ty constraint and the route to eliminate the imbalance while keeping the ma
ximum link traffic as low as possible. We investigate the load-balancing pr
oblem under various conditions. First, we consider the case in which the ex
cess load on each overloaded node is divisible. We devise a network flow al
gorithm to solve this type of load balancing problem optimally in polynomia
l time. Next, we impose the realistic assumption that the system uses a spe
cific 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 s
ystem graph to another graph to which the same network flow algorithm can b
e applied to solve the load balancing problem optimally. Finally, we consid
er 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 heuri
stic algorithm as a solution.