Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

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 JIANG1,Matthias BAUMGARTEN2,Yanhong ZHOU3,Hai JIN3,
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 M2ON (Min-cost and Max-flow Channel based Overlay Network) is presented. In M2ON, the communication capability is denoted as M2C (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 M2ON 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 (M2C)      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