Effects of Link Communication Time on Optimal Load Balancing in Tree Hierarchy Network Configurations

Jie LI  Hisao KAMEDA  Kentaro SHIMIZU  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.2   pp.199-209
Publication Date: 1993/02/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
Keyword: 
optimal load balancing,  tree hierarchy network,  parametric analysis,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper, optimal static load balancing in a tree hierarchy network that consists of a set of heterogeneous host computers is considered. It is formulated as a nonlinear optimization problem. We study the effects of the link communication time on the optimal link flow rate (i.e., the rate at which a node forwards jobs to other nodes for remote processing), the optimal node load (i.e., the rate at which jobs are processed at a node), and the optimal mean response time, by parametric analysis. We show that the entire network can be divided into several independent sub-tree networks with respect to the link flow rates and node loads. We find that the communication time of a link has the effects only on the link flow rates and the loads on nodes that are in the same sub-tree network. The increase in the communication time of a link causes the decrease in the link flow rates of its descendant nodes, its ancestor nodes and itself, but causes the increase in the link flow rates of other nodes in the same sub-tree network. It also causes the increase in the loads of its descendant nodes and itself, but causes the decrease in the loads of other nodes in the same sub-tree network. In general, it causes the increase in the mean response time.