A bipartite model for load balancing in grid
computing environments

doi:10.1007/s11704-009-0036-0

Front. Comput. Sci.

2009, Vol. 3

Issue (4) : 503-523 https://doi.org/10.1007/s11704-009-0036-0

Research articles

A bipartite model for load balancing in grid computing environments

Wenchao JIANG¹,Matthias BAUMGARTEN²,Yanhong ZHOU³,Hai JIN³,

1.School of Computer Science and Technology, Hubei bioinformatics and molecular imaging key laboratory, Huazhong University of Science and Technology, Wuhan 430074, China；Information Engineering College of Guangdong University of Technology, Guangzhou 510006, China; 2.Faculty of Computing and Engineering, University of Ulster, Shore Road, Newtownabbey BT37 0QB, UK; 3.School of Computer Science and Technology, Hubei bioinformatics and molecular imaging key laboratory, Huazhong University of Science and Technology, Wuhan 430074, China;

Download: PDF(1012 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract In this paper, a bipartite model for load balancing (LB) in grid computing environments, called Transverse viewpoint-based Bi-Tier model (TBT), is proposed. TBT can efficiently eliminate topology mismatching between overlay- and physical-networks during the load transfer process. As an implementation of TBT, a novel LB policy called M²ON (Min-cost and Max-flow Channel based Overlay Network) is presented. In M²ON, the communication capability is denoted as M²C (Min-cost and Max-flow Channel) which is obtained using a Labeled Tree Probing (LTP) method. The computing capacity is denoted as the Idle Factor (IF) which is obtained from the semantic overlay. The higher- and lower-level characteristics are combined into an Integrated Impacting Factor (IIF) using a Double Linear Inserting (DLI) function. Based on IIF, optimal topology matching can be achieved in the LB process. Extensive experiments and simulations have been performed and will be discussed. The results show that M²ON achieves more accurate topology matching with a minimum increment in the overall locating time yet achieving higher system performance as a whole.

Keywords grid computing load balancing (LB) min-cost and max-flow channel (M²C) topology mismatching labeled tree probing (LTP) double linear inserting (DLI)

Issue Date: 05 December 2009

Cite this article:

Wenchao JIANG,Yanhong ZHOU,Matthias BAUMGARTEN, et al. A bipartite model for load balancing in grid computing environments[J]. Front. Comput. Sci., 2009, 3(4): 503-523.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-009-0036-0
https://academic.hep.com.cn/fcs/EN/Y2009/V3/I4/503

	Rao N. Overlaynetworks of in situ instruments for probabilistic guarantees on messagedelays in wide-area networks. IEEE Journalon Selected Areas in Communications, 2004, 22(1): 79―81 doi: 10.1109/JSAC.2003.818797
	Lin H C, Raghavendra C S. A dynamic load balancingpolicy with a central job dispatcher (LBC). IEEE Transactions on Software Engineering, 1992, 18(2): 148―158 doi: 10.1109/32.121756
	Shivaratri N G, Krueger P, Singhal M. Load distributing for locally distributed systems. Computer Communication, 1992, 8: 33―44
	Zeng Z, Veeravalli B. On the design of distributedobject placement and load balancing strategies in large-scale networkedmultimedia storage systems. IEEE TransactionsParallel and Distributed Systems, 2008, 20(3): 369―383
	Dhakal S, Hayat M, Jorge E, et al. Dynamic load balancing in distributed systemsin the presence of delays: a regeneration-theory approach. IEEE Transaction on Parallel and Distributed System, 2007, 18(4): 485―498 doi: 10.1109/TPDS.2007.1009
	Jacques M, Couturier, Dynamic R. Load balancingand efficient load estimators for asynchronous iterative algorithms. IEEE Transactions Parallel and Distributed Systems, 2005, 16(4): 289―300 doi: 10.1109/TPDS.2005.45
	Cao J. Self-OrganizingAgents for grid load balancing. In: Proceedingsof the Fifth IEEE/ACMInternational Workshop on Grid Computing, 2004, 388―395
	Giannacopoulos D. Optimaldiscretization based load balancing for parallel adaptive finite elementelectromagnetic analysis. IEEE Transactionson Magnetics, 2004, 40(2): 977―1001 doi: 10.1109/TMAG.2004.824713
	Kim C, Kameda H. An algorithm for optimalstatic load balancing in distributed computer systems. IEEE Transactions on Computers, 1992, 41: 381―384 doi: 10.1109/12.127455
	Grosu D, Chronopoulos A. A game theoretic model andalgorithm for load balancing in distributed systems. In: Proceedings of 16th International Parallel & Distributed Symposium, April. 2002, 15―19
	Li J, Kameda H. Load balancing problems formulticlass jobs in distributed/parallel computer systems. IEEE Transactions on Computers and Mathematicswith Applications, 1998, 47(3): 322―332
	Tantawi A N, Towsley D. Optimal static load balancingin distributed computer systems. Journalof ACM, 1985, 32(2): 445―465 doi: 10.1145/3149.3156
	Li J, Kameda H. Optimal static load balancingof multi-class jobs in a distributed computer system. In: Proceedings of 10th International Conference on Distributed ComputingSystems, 1990: 562―569
	Zeng Z, Bharadwaj V. Design and analysis of anon-preemptive decentralized load balancing algorithm for multi-classjobs in distributed networks. ComputerCommunication, 2004, 27: 679―694 doi: 10.1016/j.comcom.2004.02.002
	Grosu D, Chronopoulos A T. Algorithmic mechanism designfor load balancing in distributed systems. IEEE Transactions on Systems, Man and Cybernetics-Part B: Cybernetics, 2004, 34(1): 134―143 doi: 10.1109/TSMCB.2002.805812
	Lu K, Subrata R, Zomaya A Y. Towards decentralized load balancing in a computationalgrid environment. In: Proceedings of 1stInternational Conference on Grid and Pervasive Computing (GPC’06), 2006
	Lu K, Subrata R, Zomaya A Y. An efficient load balancing slgorithm for heterogeneousgrid systems considering desirability of grid sites. In: Proceedings of 25th IEEE International Performance Computing andCommunications Conference, Phoenix, Arizona, USA, 2006
	Anand L, Ghose D, Mani V. ELISA: An sstimated load information scheduling algorithmfor distributed computing system. Computersand Mathematics with Applications, 1999, 37: 57―85 doi: 10.1016/S0898-1221(99)00101-7
	Evans D, Butt W. Dynamic Load balancing usingtask-transfer probabilities. Parallel Computing, 1993, 19: 279―301 doi: 10.1016/0167-8191(93)90073-T
	Walshaw C, Berzins M. Dynamic load-blancing forPDE solvers on adaptive unstructured meshes. Concurrency: Practice and Experience, 1995, 7: 17―28 doi: 10.1002/cpe.4330070103
	Watts J, Taylor S. A practical approach to dynamicload balancing. IEEE Transactions on Paralleland Distributed Systems, 1998, 9(3): 235―248 doi: 10.1109/71.674316
	Zhang Y, Kameda H, Shimizu K. Adaptive bidding load balancing algorithms in heterogeneousdistributed systems. In: Proceedings ofIEEE 2nd International Workshop Modeling, Analysis, and Simulationof Computer and Telecomm. Systems, 1994, 250―254
	Fatta G, Berthold M R. Dynamic load balancing forthe distributed mining of molecular structures. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(8): 773―786 doi: 10.1109/TPDS.2006.101
	Zhang Y, Franke H, Moreira J. An integrated approach to parallel scheduling using gangscheduling, backfilling, and migration. IEEE Transactions on Parallel and Distributed Systems, 2003, 14(3): 236―247 doi: 10.1109/TPDS.2003.1189582
	Akay O, Erciyes K. A dynamic load balancingmodel for a distributed system. Mathematicaland Computational Applications, 2003, 8(3): 353―360
	Boeres C, Lima A, Rebello V E F. Hybrid task scheduling: integrating static and dynamicheuristics. In: Proceedings of 15th Symposiumon Computer Architecture and High Performance Computing, SãoPaulo, Brazil, 2003: 199―206
	Avvenuti M, Rizzo L, Vicisano L. A hybrid approach to adaptive load sharing and its performance. Journal of Systems Architecture, 1997, 42: 679―696 doi: 10.1016/S1383-7621(96)00070-7
	Cao J, Spooner D P, Jarvis S A, et al. Agent-based grid load balancing using performance-driventask scheduling. In: Proceedings of theInternational Parallel and Distributed Processing Symposium, 2003, 49.2
	Subrata R, Zomaya A Y, Landfeldt B. Game theoretic approach for load balancing in computationalgrids. IEEE Transactions on Parallel andDistributed Systems, 2007, 18(2): 23―26
	Salehi M A, Deldari H. Grid load balancing usingan echo system of intelligent ants. In: Proceedings of the 24th IASTED International Multi-Conference onParallel and Distributed Computing and Networks, 2006, 14(16): 47―53
	Mello R F D, Senge L G E, Yang L T. A routing load balancing policy for grid computing environments. In: Proceedings of the 20th International Conferenceon Advanced Information Networking and Applications, 2006
	Mello R F D, Filho J A, Senger L J, et al. RouteGA: a grid load balancing algorithm withgenetic support. In: Proceedings of 21stInternational Conference on Advanced Networking and Applications, 2007, 885―892
	Bridgewater J, Boykin P, Roychowdhury V P. Balanced overlay networks (BON): an overlaytechnology for decentralized load balancing. IEEE Transaction on Parallel and Distributed System, 2007, 18(8): 1122―1134 doi: 10.1109/TPDS.2007.1031
	Carra D, Cigno R L, Biersack E. Stochastic Graph processes for performance evaluationof content delivery applications in overlay networks. IEEE Transaction on Parallel and Distributed System, 2007, 19(2): 247―261 doi: 10.1109/TPDS.2007.1114
	Darieby M, Petriu D, Rolia J. Load-balancing data traffic among tnterdomain links. IEEE Journal on Selected Areas in Communications, 2007, 25(5): 67―76
	Liu Y H, Xiao L, Ni L M. Building a scalable bipartite P2P overlay network. IEEE Transaction on Parallel and Distributed System, 2007, 18(9): 1296―1307 doi: 10.1109/TPDS.2007.1059
	David H B, Kaashoek F, Robert M. Resilient overlay networks. In: Proceedings of 18th ACM Symposium on Operating Systems Principles(SOSP) October Banff, Canada., 2001: 131―145
	Savage S, Anderson T, Aggarwal A, et al. Detour: informed internet routing and transport. IEEE Micro, 1999, 19(1): 50―59 doi: 10.1109/40.748796
	Hou Y T, Duan Z, Zhang Z. Service overlay networks: SLA, QoS and bandwidth provisioning. In: Proceedings of International Conference onNetwork Protocols, 2002: 11―17
	Matthews W, Cottrell L. The Ping ER project: activeinternet performance monitoring for the NENP community. IEEE Communication Magazine, May2000: 130―136 doi: 10.1109/35.841837
	Balakrishnan H, Padmanabhan V N, Seshan S, et al. TCP behavior of a busy internet server: analysisand improvements. In: Proceedings of IEEEINFOCOM, 1998,1: 252―262
	Vogel R, Herrtwich R G, Kalfa W, et al. QoS based routing of multimedia streams in computernetworks. IEEE Journal of Selected AreasCommunication, 1996, 14: 1235―1244 doi: 10.1109/49.536365
	Wang Z, Crowcroft J. QoS routing for supportingresource reservation. IEEE Journal of SelectedAreas Communication, 1996, 14: 1228―1234
	Murthy S, Garcia J. Congestion oriented shortestmultipath routing. In: Proceedings of ComputerCommunications, 1996. 3: 1028―1036
	Rao N S V, Batsell S G. QoS routing via multiplepaths using bandwidth reservation. In: Proceedings of Conference. Computer Communications, 1998. 1: 11―18
	Wang H, Poo G S. Load balancing in the provisioningof hose model virtual private networks with multi-path routing. IET Communication, 2007, 4(1): 684―692 doi: 10.1049/iet-com:20060300
	John Z T, Chiasson J, Ghanem J, et al. The effect of time delays on the stability ofload balancing algorithms for parallel computations. IEEE Transactions on Control Systems Technology, 2005, 13(6): 932―943 doi: 10.1109/TCST.2005.854339
	Ruchir Shah B VM. On the design of adaptive and decentralized loadbalancing algorithmswith load estimation for computational grid environments. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(12): 1675―1686 doi: 10.1109/TPDS.2007.1115
	Liu Y H, Liu X, Xiao L, et al. Location-aware topology matching in P2P systems. In: Proceedings of the 23th Annual Joint Conferenceof the IEEE Computer and Communications Societies, 2004, 4: 2220―2230
	Huang Y, Jin B, Cao J. A distributed approach to construction of topology mismatchingaware P2P overlays in wireless ad hoc networks. In: Proceedings of 14th Euromicro International Conference on Parallel,Distributed, and Network Based Processing, 2006: 340―347
	Liu Y H, Zhuang Z, Xiao L, et al. A distributed approach to solving overlay mismatchingproblem. In: Proceedings of 24th InternationalConference on Distributed Computing Systems, 2004: 132―139
	Liu Y H. A Two-hop solution to solving topology mismatch. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(11): 1591―1601 doi: 10.1109/TPDS.2008.24
	Bridgewater J S A, Boykin P O, Roychowdhury V P. Statistical mechanical load balancerfor the web. Physical Reviewer, 2005, E (71): 046133
	Li M, Liu F, Ren F Y. Routing strategy on a two-dimensional smallworld networkmodel. Physical Reviewer, 2007E (75): 066115
	IAkyildiz I F. Wireless sensor networks: a survey, ComputerNetworks, 2002, 38(3): 393―422
	Steele J M. Gibbs_ Measures on combinatorial objects and the central limit theoremfor an exponential family of random trees. Probability in the Engineering and Informational Sciences, 1, 1987: 47―59 doi: 10.1017/S0269964800000279
	Elias P, Feinstein A, Shannon C E. A note on the maximum flow through a network. IRE Transactions on Information Theory, 1956: 117―121 doi: 10.1109/TIT.1956.1056816
	Cheung T Y. Graph traversal techniques and the maximum flow problem in distributedcomputation. IEEE Transactions on SoftwareEngineering, 1983, 9(4): 504―512 doi: 10.1109/TSE.1983.234958
	Ramamoorthy A, Shi J, Wesel R D. On the capacity of network coding for random networks. IEEE Transactions on Information Theory, 2005, 51(8): 2878―2886 doi: 10.1109/TIT.2005.851725
	Dunn D A, Grover W D, MacGregor M H. Comparison of k-shortest paths and maximum flow routingfor network facility restoration. IEEEJournal on Selected Areas in Communications, 1994, 12(1): 88―100 doi: 10.1109/49.265708
	Hu T C. Integer Programming and Network Flows. Addison-Wesley, 1969
	Skienna S. ImplementingDiscrete Mathematics: Combinatorics and Graph Theory with Mathematics. Redwood city. CA: Addison- Wesley, 1990
	Dunn D A, Grover Q D, Macgregor M H. Development and use of a random network synthesis toolwith controlled connectivity statistics. TRLabs, Representative of the University of Alberta. WP-90-10, 1990

[1]	JIN Hai, YI Chuanjiang. CMM: Credential Migration Management system based on trusted computing in CGSP[J]. Front. Comput. Sci., 2007, 1(2): 200-207.

Viewed

Full text

Abstract

Cited

Shared

Discussed