|
|
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; |
|
|
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
|
|
|
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|