To maintain load balancing in a distributed system, it is necessary to obtain workload information from all the nodes in the network. This processing requires O(v2) communication complexity, where v is the number of nodes. The authors present a new synchronous dynamic distributed load balancing algorithm on a (v, k+1, 1)-configured network applying a symmetric balanced incomplete block design, where v=k2+k+1. The algorithm needs only O (v√v) communication complexity and each node receives workload information from all the nodes without redundancy. Therefore, load balancing is maintained since every link has the same amount of traffic for transferring workload information.
References
-
-
1)
-
C.L. Liu
.
(1968)
Block designs in introduction to combinatorial mathematics.
-
2)
-
S. Das ,
D. Harvey ,
R. Biswas
.
Parallel processing of adaptive meshes with load balancing.
IEEE Trans. Parallel Distrib. Syst.
,
12
-
3)
-
M. Wu
.
On runtime parallel scheduling for processor load balancing.
IEEE Trans. Parallel Distrib. Syst.
,
2 ,
173 -
185
-
4)
-
I. Chung ,
W. Choi ,
Y. Kim ,
M. Lee
.
The design of conference key distribution system employing a symmetric balanced incomplete block design.
Inf. Process. Lett.
,
6 ,
313 -
318
-
5)
-
M. Willebeek-Lemair ,
A.P. Reeves
.
Strategies for dynamic load-balancing on highly parallel computers.
IEEE Trans. Parallel Distrib. Syst.
,
9 ,
979 -
993
-
6)
-
K. Nam ,
J. Seo ,
S. Lee ,
J. Kim
.
Synchronous load balancing in hypercube multicomputers with faulty nodes.
J. Parallel Distrib. Comput.
,
26 -
43
-
7)
-
S. Das ,
D. Harvey ,
R. Biswas
.
Adaptive load-balancing algorithms using symmetric broadcast networks.
J. Parallel Distrib. Comput.
,
6 ,
1042 -
1068
-
8)
-
B.A. Shirazi
.
(1995)
Scheduling and load balancing in parallel and distributed systems.
-
9)
-
C. Hui ,
S. Chanson
.
Hydrodynamic load balancing.
IEEE Trans. Parallel Distrib. Syst.
,
11 ,
1118 -
1137
-
10)
-
L.R. Ford ,
D.R. Fulkerson
.
(1962)
Flow in networks.
-
11)
-
H. Rim ,
J. Jang ,
S. Kim
.
Method for maximal utilization of idle links for fast load balancing.
J. KISS, Comput. Syst. Theory
,
12 ,
632 -
641
-
12)
-
Padlipsky, M.: `A perspective on the ARPANET reference model', Proc. IEEE INFOCOM, 1983.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-com_20040704
Related content
content/journals/10.1049/ip-com_20040704
pub_keyword,iet_inspecKeyword,pub_concept
6
6