TY - GEN

T1 - In-domain neighborhood approach to heterogeneous dynamic load balancing in real world network

AU - Daraghmi, Eman Yasser

AU - Yuan, Shyan-Ming

PY - 2014/9/18

Y1 - 2014/9/18

N2 - In this paper, we present a novel in-domain neighborhood approach to clarify the dynamic load balancing problem on a heterogeneous network and to solve many practical problems. The distributed system consists of a network of workstations with different domains, speeds and capacities. Since the number of workstations and the diameter of the network affect the convergences rate, our approach introduces the in-domain relation that classifies the entire network into sub-networks called domains. The algorithm runs in each workstation in order to reach the fairness state in-domain and in entire network rapidly. In this paper, our approach is applied to a cafeteria system as a case study, each workstation is viewed as a cafeteria where the maximum number of orders that can be submitted to one cafeteria corresponds to the capacity of that cafeteria workstation, the communication channels are modeled between the in-domain cafeterias, and the workload is represented as orders. An algorithm is presented to simulate the migration of the orders between in-domain cafeterias and to distribute a proportion of the excessive workload of heavily loaded node to lightly loaded node by considering the capacity of each node such that when the algorithm terminates, the effective-load in all cafeterias is the same. Therefore, each workstation receives an amount of workload proportional to its total capacity. This framework is analyzed mathematically, and it is proved that the proposed algorithm converges and achieves the fairness state.

AB - In this paper, we present a novel in-domain neighborhood approach to clarify the dynamic load balancing problem on a heterogeneous network and to solve many practical problems. The distributed system consists of a network of workstations with different domains, speeds and capacities. Since the number of workstations and the diameter of the network affect the convergences rate, our approach introduces the in-domain relation that classifies the entire network into sub-networks called domains. The algorithm runs in each workstation in order to reach the fairness state in-domain and in entire network rapidly. In this paper, our approach is applied to a cafeteria system as a case study, each workstation is viewed as a cafeteria where the maximum number of orders that can be submitted to one cafeteria corresponds to the capacity of that cafeteria workstation, the communication channels are modeled between the in-domain cafeterias, and the workload is represented as orders. An algorithm is presented to simulate the migration of the orders between in-domain cafeterias and to distribute a proportion of the excessive workload of heavily loaded node to lightly loaded node by considering the capacity of each node such that when the algorithm terminates, the effective-load in all cafeterias is the same. Therefore, each workstation receives an amount of workload proportional to its total capacity. This framework is analyzed mathematically, and it is proved that the proposed algorithm converges and achieves the fairness state.

KW - convergence

KW - Dynamic load balancing

KW - fairness state

KW - heterogeneous

KW - in-domain neighborhood

UR - http://www.scopus.com/inward/record.url?scp=84907978493&partnerID=8YFLogxK

U2 - 10.1109/PDCAT.2013.17

DO - 10.1109/PDCAT.2013.17

M3 - Conference contribution

AN - SCOPUS:84907978493

SN - 2379-5352

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 63

EP - 70

BT - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

A2 - Horng, Shi-Jinn

PB - IEEE Computer Society

Y2 - 16 December 2013 through 18 December 2013

ER -