You are an expert at summarizing long articles. Proceed to summarize the following text: 
in traditional data centers , applications are tied to specific physical servers that are often over - provisioned to deal with upper - bound workload . such configuration makes data centers expensive to maintain with wasted energy and floor space , low resource utilization and significant management overhead . with virtualization technology , today s cloud data centers become more flexible , secure and provide better support for on - demand allocating . the definition and model defined by this paper are aimed to be general enough to be used by a variety of cloud providers and focus on the infrastructure as a service ( iaas ) . cloud datacenters can be a distributed network in structure , containing many compute nodes ( such as servers ) , storage nodes , and network devices . each node is formed by a series of resources such as cpu , memory , and network bandwidth and so on , which are called multi - dimensional resources ; each has its corresponding properties . under virtualization , cloud data centers should have ability to migrate an application from one set of resources to another in a non - disruptive manner . such ability is essential in modern cloud computing infrastructure that aims to efficiently share and manage extremely large data centers . reactive migration of vms is widely proposed for load balance and traffic consolidation . one key technology playing an important role in cloud data centers is load balance scheduling . there are quite many load balance scheduling algorithms . most of them are for traditional web servers but do not consider vm reservations with lifecycle characteristics . one of the challenging scheduling problems in cloud data centers is to consider allocation and migration of reconfigurable vms and integrated features of hosting pms . the load balance problem for vm reservations considering lifecycle is as follows : given a set of @xmath2 identical machines ( pms ) @xmath3 and a set of @xmath4 requests ( vms ) , each request [ @xmath5 , @xmath6 , @xmath7 , has a start - time ( @xmath5 ) , end - time ( @xmath6 ) constraint and a capacity demand ( @xmath8 ) from a pm , the objective of load balance is to assign each request to one of pms so that the loads placed on all machines are balanced or the maximum load is minimized . this problem is not well studied yet in the open literatures . the major contributions of this paper are :    * providing a modeling approach to vm reservation scheduling with capacity sharing by modifying traditional interval scheduling problem and considering life cycles characteristics of both vms and pms . * designing and implementing load balancing scheduling algorithms , called prepartition for both offline and online scheduling which can prepare migration in advance and set process time bound for each vm on a pm . * deriving computational complexity and quality analysis for both offline and online prepartition . * providing performance evaluation of multiple metrics such as average utilization , imbalance degree , makespan , time costs as well as capacity@xmath1makespan by simulating different algorithms using trace - driven and synthetic data . the remaining parts of this paper are organized as follows : section 2 discusses the related work on load balance algorithms . section 3 introduces problem formulation . section 4 presents prepartition algorithm in details as well as offline and online algorithms are described and compared . performance evaluations of different scheduling algorithms are shown in section 5 . finally in section 6 , a conclusion is given . a large amount of work has been devoted to the schedule algorithms and can be mainly divided into two types : online load balance algorithms and offline ones . the major difference lies in that online schedulers only know current request and status of all pms but offline schedulers know all the requests and status of all pms . andre et al.@xcite discussed the detailed design of a data center . armbrust et al.@xcite summarized the key issues and solutions in cloud computing . foster et al.@xcite provided detailed comparison between cloud computing and grid computing . buyya et al.@xcite introduced a way to model and simulated cloud computing environments . wickremasinghe et al.@xcite introduced three general scheduling algorithms for cloud computing and provided simulation results . wood et al.@xcite introduced techniques for virtual machine migration with spots and proposed a few reactive migration algorithms . zhang@xcite compared major load balance scheduling algorithms for traditional web servers . singh et al.@xcite proposed a novel load balance algorithm called vectordot which deals with hierarchical and multi - dimensional resources constraints by considering both servers and storage in a cloud . arzuaga et al.@xcite proposed a quantifying measure of load imbalance on virtualized enterprise servers considering reactive live vm migrations . galloway et al . in @xcite introduced an online greedy algorithm , in which pms can be dynamic turned on and off but the life cycle of a vm is not considered . gulati et al @xcite presented challenge issues and distributed resource scheduling ( drs ) as a load balance scheduling for cloud - scale resource management in vmware . tian et al.@xcite provided a comparative study of major existing scheduling strategies and algorithms for cloud data centers . sun et al.@xcite presented a novel heuristic algorithm to improve integrated utilization considering multi - dimensional resource . tian et al.@xcite designed a toolkit for modeling and simulating vm allocation , @xcite@xcite introduced a dynamic load balance scheduling algorithm considering only current allocation period and multi - dimensional resource but without considering life - cycles of both vms and pms . li et al.@xcite proposed a cloud task scheduling policy based on ant colony optimization algorithm to balance the entire system and minimize the makespan of a given task set . hu et al.@xcite stated an algorithm named genetic , which can calculate the history data and current states to choose an allocation . most of existing research does not consider fixed interval constraints of vm allocation . knauth et al.@xcite introduced energy - efficient scheduling algorithms applying timed instances that have a priori specified reservation time of fixed length , these assumptions are also adopted in this paper . most of existing research considers reactive vm migrations as a mean for load balance in data centers . to the best of our knowledge , proactive vm migration by pre - partition has not been studied yet in the open literatures . it is one of major objectives in this paper . in this paper we consider vms reservation and model the vm allocations as a modified interval scheduling problem ( misp ) with fixed processing time . more explanation and analysis about traditional interval scheduling problems with fixed processing time can be found in @xcite and references there in . we present a general formulation of modified interval - scheduling problem and evaluate its results compared to well - known existing algorithms . there are following assumptions : + 1 ) all data are deterministic and unless otherwise specified , the time is formatted in slotted windows . we partition the total time period [ 0 , t ] into slots with equal length @xmath9 , the total number of slots is @xmath10=@xmath11 . the start time @xmath5 and finish time @xmath6 are integer numbers of one slot . then the interval of a request can be represented in slot format with ( start - time , finish - time ) . for example , if @xmath12=5 minutes , an interval ( 3 , 10 ) means that it has start time and finish time at the 3rd - slot and 10th - slot respectively . the actual duration of this request is ( 10 - 3)@xmath135=35 minutes . + 2 ) for all vm reservations , there are no precedence constraints other than those implied by the start - time and finish - time . + 3 ) the required capacity of each request is a positive real number between ( 0,1 ] . notice that the capacity of a single physical machine is normalized to be 1 and the required capacity of a vm can be 1/8 , 1/4 or 1/2 or other portions of the total capacity of a pm . this is consistent with widely adopted practice in amazon ec2 @xcite and @xcite . + a few key definitions are explained as follows :    _ definition 1 . traditional interval scheduling problem ( tisp ) with fixed processing time _ : a set of requests @xmath141 , 2,@xmath15 , @xmath16 where the @xmath17-th request corresponds to an interval of time starting at @xmath5 and finishing at @xmath6 , each request needs a capacity of 1 , i.e. occupying the whole capacity of a machine during fixed processing time .    _ definition 2 . interval scheduling with capacity sharing ( iswcs ) _ : the only difference from tisp is that a resource ( to be concrete , a pm ) can be shared by different requests if the total capacity of all requests allocated on the single resource at any time does not surpass the total capacity that the resource can provide .    _ definition 3 . sharing compatible intervals for iswcs _ : a subset of intervals with total required capacity not surpass the total capacity of a pm at any time , therefore they can share the capacity of a pm . in the literature , the makespan is used to measure the load balance , which is simply the maximum total load ( processing time ) on any machine . traditionally , the makespan is the total length of the schedule .    in view of the problem in iswcs for vm scheduling , we redefine the makespan as capacity@xmath1makespan . _ definition 4 . capacity@xmath1makespan of a pm @xmath17 _ : in any allocation of vm requests to pms , let @xmath18 denote the set of vm requests allocated to machine @xmath19 . under this allocation , machine @xmath19 will have total load equal to the sum of product of each required capacity and its duration ( called capacity@xmath1makespan , i.e. , cm for abbreviation in this paper ) , as follows : @xmath20 where @xmath21 is the capacity requests of @xmath22 from a pm and @xmath23 is the span of request @xmath24 ( i.e. , the length of processing time of request @xmath24 ) . therefore , the goal of load balancing is to minimize the maximum load ( capacity@xmath1makespan ) on any pm . some other related metrics such as average utilization and makespan are also considered and will be explained in the following section . assuming there are @xmath2 pms in data centers , the problem of iswcs load balance in it therefore can be formulated as : * @xmath25 * where @xmath21 is the capacity requirement of vm @xmath24 and the total capacity of a pm @xmath17 is normalized to 1 . the condition 1 ) shows the sharing capacity constraint and condition , 2 ) is for the interval constraint of vm reservations .    _ theorem 1 : the offline scheduling problem of finding an allocation of minimizing the makespan in general case is np - complete . _ + the proof can be found in @xcite and is omitted here .      in this section , a few metrics closely related to iswcs load balance problem will be presented . some other metrics can be found in @xcite . + 1 ) pm resource : + @xmath26 , @xmath17 is the index number of pm , @xmath27,@xmath28,@xmath29 are the cpu , memory , storage capacity of that a pm can provide . + 2 ) vm resource : + @xmath30 , @xmath24 is the vm type i d , @xmath31 are the cpu , memory , storage requirements of @xmath22 , @xmath32 are the start time and end time , which are used to represent the life cycle of a vm . + 3 ) time slots : we consider a time span from 0 to @xmath33 be divided into slots with same length . the @xmath4 slots can be defined as @xmath34 $ ] , each time slot @xmath35 means the time span @xmath36 . + 4 ) average cpu utilization of @xmath19 during slot 0 and @xmath37 is defined as : @xmath38 where @xmath39 is the average cpu utilization during slot @xmath35 . average memory utilization ( @xmath40 ) and storage utilization ( @xmath41 ) of both pms can be computed in the same way . similarly , average cpu ( memory and storage ) utilization of a vm can be computed . + 5 ) makespan : the total length of a schedule for a set of vm reservations , i. e. , the difference between the start - time of the first job and the finishing time of the last job . + 6 ) the capacity@xmath1makespan ( cm ) of all pms : can be formulated as : @xmath42 + from these equations , we notice that life cycle and capacity sharing are two major differences from traditional metrics such as makespan which only considers process time ( duration ) . traditionally longest process time first ( lpt ) @xcite is widely used for load balance of offline multi - processor scheduling . reactive ( post ) migration of vms is another popular way of load - balancing . _ however , reactive migration has difficulty to reach predefined load balance objectives , and may cause interruption and instability of service and other associated costs_. by considering both fixed process intervals and capacity sharing properties in cloud data centers , we propose new offline and online algorithms as follows . for a given set of vm reservations , let us consider there are @xmath2 pms in a data center and denote opt as the optimal solution for a given set of @xmath43 vm reservations . firstly define @xmath44 @xmath45 is a lower bound on opt . algorithm 4.1 shows the pseudocodes of prepartition algorithm . the algorithm firstly computes balance value by equation ( 7 ) , defines partition value ( @xmath10 ) and finds the length of each partition ( i.e. @xmath46 , which is the max time length a vm can continously run on a pm ) . for each request , preparition equally partitions it into multiple @xmath46 subintervals if its cm is larger than @xmath46 , and then finds a pm with the lowest average capacity@xmath1makespan and available capacity , and updates the load on each pm . after all requests are allocated , the algorithm computes the capacity@xmath1makespan of each pm and finds total partition ( migration ) numbers . for practice , the scheduler has to record all possible subintervals and their hosting pms of each request so that migrations of vms can be conducted in advance to reduce overheads . initialization : computing the bound @xmath45 value and set the partition value @xmath10 ;    sort all intervals in decreasing order of @xmath47 , break ties arbitrarity ;    let @xmath48 denote the intervals in this order ;    compute cm of each pm and total partitions    _ theorem 2 : the computational complexity of prepartition algorithm is @xmath49 using priority queue data structure where @xmath4 is the number of vm requests after pre - partition and @xmath2 is total number of pms used_. + proof : the priority queue is designed such that each element ( pm ) has a priority value ( average capacity@xmath1makespan ) , and each time the algorithm needs to select an element from it , the algorithm takes the one with the highest priority ( the smaller average capacity@xmath1makespan value is , the higher priority it is ) . sorting @xmath4 numbers in a priority queue takes @xmath50 time and a priority queue performs insertion and the extraction of minima in @xmath51 steps ( detailed proof of the priority queue is shown in @xcite ) . therefore , by using priority queue or related data structure , the algorithm can find a pm with the lowest average capacity@xmath1makespan in @xmath52 time . altogether , for @xmath4 requests , prepartition algorithm has time complexity @xmath49 . _ theorem 3 : the approximation ratio of prepartition algorithm is @xmath53 regarding the capacity_makespan where @xmath54=@xmath55 _ and @xmath10 is the partition value ( a preset constant ) . + proof : this is because that each request has bounded capacity@xmath1makespan by pre - parition based on ideal lower bound @xmath45 . we sketch the proof as follows . each job has start - time @xmath5 , end - time @xmath6 and process time @xmath56=@xmath6-@xmath5 . consider the last job to finish ( after scheduling all other jobs ) and suppose this job starts at time @xmath57 . all the machines must have been fully loaded up to capacity_makespan @xmath58 , which gives @xmath59opt . since , for all jobs , we have @xmath60 opt ( by the settting of prepartition algorithm in equation ( 7 ) ) , this job finishes with load @xmath58+@xmath54opt . hence , the schedule with capacity_makespancan be no more than @xmath58+@xmath54 opt @xmath61 ( 1+@xmath54)opt , this finishes the proof . +      for online vm allocations , scheduling decisions must be made without complete information about the entire job instances because jobs arrive one by one . we extend the offline prepartition algorithm to online scenario as prepartitionon . let us consider there are @xmath2 pms and @xmath62 vms ( including the one just came ) in a data center . firstly define @xmath63 @xmath64 is called dynamic balance value , which is one half of the max capacity@xmath1makespan of all current pms or the ideal load balance value of all current pms in the system , where @xmath62 is the number of vms requests already arrived . notice that the reason to set @xmath64 as one half of the max capacity@xmath1makespan of all current pms is to avoid large requests may cause imbalance in some cases . algorithm 4.2 shows the pseudo codes of prepartitionon algorithm . since in online algorithm , the requests come one by one , the system can only capture the information of arrived requests . when a new request comes into the system , the algorithm computes dynamic balance value by equation ( 8) . to be noticed , @xmath62 represents the number of requests already arrived , and @xmath2 represents the number of pms in use . after the dynamic balanced value ( @xmath64 ) is computed , then the initial request is partitioned into several requests ( segments ) based on the partition value @xmath10 . in these partitioned requests , the first one would be executed instantly , which will be allocated to the pm with the lowest capacity_makespan , while others would be put back into the queue waiting to be executed . then the algorithm picks up the next arrived request to follow the same partition and allocation process . after all requests are allocated , the algorithm computes the capacity@xmath1makespan of each pm and find the total partition numbers for @xmath4 requests . since the number of partitions and segments of each vm request are known at the moment of allocation , the system can prepare vm migration in advance so that process time and instability of migration can be reduced . initialization : set the partition value k , total partition number @xmath65=0 ;    compute @xmath66 of each pm and output total number of partitions @xmath65    _ theorem 4 : the competitive ratio of prepartitionon is @xmath67 _ regarding the capacity_makespan . + proof : without loss of generality , we label pms in order of non - decreasing final loads in prepartitionon . denote @xmath68 and and @xmath69 respectively as the optimal load balance value of corresponding offline scheduling and load balance value of prepartitionon for a given set of jobs @xmath70 , respectively . then the load of @xmath71 defines the capacity@xmath1makespan . the first @xmath72 - 1 ) pms each process a subset of the jobs and then experience a ( possibly none ) idle period . all pms together finish a total capacity@xmath1makespan @xmath73 during their busy periods . consider the allocation of the last job @xmath24to pm@xmath74 . by the scheduling rule of prepartitionon , pm@xmath74 had the lowest load at the time of allocation . hence , any idle period on the first ( @xmath2 - 1 ) pms can not be bigger than the capacity@xmath1makespan of the last job allocated on pm@xmath74 and hence can not exceed the maximum capacity@xmath1makespan divided by @xmath10 ( partition value ) , i.e. , @xmath75 . we have + @xmath76 which is equivalent to @xmath77 which is @xmath78 note that @xmath79 is the lower bound on @xmath80 because the optimum capacity@xmath1makespan can not be smaller than the average capacity@xmath1makespan on all pms . and @xmath81 since the largest job must be processed on a pm . we therefore have @xmath82 . _ theorem 5 : the computational complexity of prepartitionon is @xmath49 using priority queue data structure , where @xmath4 is the number of vm requests after pre - partition and @xmath2 is the total number of pms used_. + proof : the proof is exactly the same as in the proof for theorem 2 , we therefore omit it . .8 types of virtual machines ( vms ) in amazon ec2 [ cols="<,<,<,<",options="header " , ]      +    in this part , we will present the simulation results between prepartition algorithms and other existed algorithms . to achieve this goal , we used a java simulator cloudsched ( see tian et al . @xcite ) . for simulation , to be realistic and reasonable , we adopt data both from normal distribution and lawrence livermore national lab ( llnl ) trace , see @xcite for detailed introduction about the trace .    all simulations are conducted on a computer configured with intel i5 processor at 2.5ghz and 4 gb memory . all vm requests are generated following normal distribution . in offline algorithm comparisons , round - robin ( rr ) algorithm , longest process time ( lpt ) algorithm and post migration algorithm ( pmg ) are implemented . \1 ) round - robin algorithm ( r - r ) : a traditional load balancing scheduling algorithm by allocating the vm requests in turn to each pm that can provide required resource . + 2 ) longest processing time first ( lpt ) : it sorts the vm requests by processing time in decreasing order firstly . then allocating the requests in that order to the pm with the lowest load . in this paper , the lowest load means the lowest capacity@xmath1makespan of all pms . + 3 ) post migration algorithm ( pmg ) : firstly , it processes the requests in the same way as lpt does . then the average capacity@xmath1makespan of all jobs is calculated . the up - threshold and low - threshold of the capacity@xmath1makespan for the post migration are calculated through the average capacity@xmath1makespan multiplied by a factor ( in this paper we set the factor as 0.1 , so the up - threshold is average capacity@xmath1makespan multiplied by 1.1 and the low - threshold is multiplied by 0.9 ) . off course the factor can be set dynamically to meet different requirements ; however , the larger the factor is , the higher imbalance is . a migration list is formed by collecting the vms taken from pms with capacity@xmath1makespan higher than the low - threshold . the vms would be taken from a pm only if the operation would not lead the capacity@xmath1makespan of the pm to be less than the low threshold . after that , the vms in the migration list would be re - allocated to a pm with capacity@xmath1makespan less than the up - threshold . the vms would be allocated to a new pm only if the operation would not lead the capacity@xmath1makespan of the pm to be higher than the up - threshold . there may be still some vms left in the list , finally the algorithm allocates the left vms to the pms with the lowest capacity@xmath1makespan until the list is empty . + in this paper , we adopt the amazon ec2 configuration of vms and pms as shown in table 1 and 2 . note that one compute unit ( cu ) has equivalent cpu capacity of a 1.0 - 1.2 ghz 2007 opteron or 2007 xeon processor @xcite . _ observation 1 . pmg is a best - effort trial heuristic for load balance . it does not guarantee a bounded or predefined load balance objective . this is validated in the following performance evaluation section . _      as for realistic data , we adopt the log data at lawrence livermore national lab ( llnl ) @xcite . the log contains months of records collected by a large linux cluster and has characteristics consistent with our problem model . each line of data in that log file includes 18 elements , while we only need the request - id , start - time , duration and number of processors ( capacity demands ) in our simulation . we convert the units from seconds in llnl log file into minutes , because we set 5 minutes as a time slot length mentioned in previous section . fig.1 and fig.2 show the average utilization , imbalance degree , makespan and capacity@xmath1makespan comparison for different algorithms with llnl data trace . from these figures , we can notice that prepartition algorithm has better performance than other algorithms in average utilization , imbalance degree , makespan , capacity@xmath1makespan . prepartition algorithm has 10@xmath0 - 20@xmath0 higher average utilization than pmg and lpt , and 40@xmath0 - 50@xmath0 higher average utilization than random - robin ( rr ) . prepartition algorithm has 10@xmath0 - 20@xmath0 lower average makespan and capacity@xmath1makespan than pmg and lpt , 5% imbalance degree than lpt and 40@xmath0 - 50@xmath0 lower average makespan and capacity@xmath1makespan than random - robin ( rr ) .    with the partition value @xmath83 , pmg algorithm has a quite similar value in imbalance value , so besides the above evaluations , we also vary the partition number @xmath10 from 4 , 8 to 10 to compare the imbalance degree affects . in figure 3 , we can notice that larger @xmath10 value will induce a lower imbalance degree . similarly , with a larger value , larger average utilization , lower makespan and capacity_makespan can be acquired .    however , increasing the @xmath10 value will bring side - effects . the dominant one is running time , in fig . 4 , we compare the time costs under different partition value @xmath10 , prepartition algorithm with @xmath84 costs about 10% more running time , and with @xmath85 it costs 15% more running time than prepartition algorithm with @xmath83 on the average . it is easy to understand that a larger @xmath10 value will produce a better load balance , which leads to more partitions , and more partitions need more time to proceed . +    _ observation 2 . whatever numbers of migrations to taken , post migration algorithm ( pmg ) just can not achieve the same level of average utilization , makespan and capacity@xmath1makespan as prepartition does_.    this is because that prepartition works in a much more refined and desired scale by prepartition based on reservation data while pmg is just a best - effort trial by migration . we set 5 minutes as a slot , so 12 slots are for an hour , 288 slots are for a day . all requests satisfy the normal distribution , with parameters mean @xmath86 and standard deviation @xmath87 as 864 ( three days ) and 288 ( one day ) respectively . after requests are generated in this way , we start the simulator to simulate the scheduling effects of different algorithms and comparison results are collected . for collecting data , we firstly fix the @xmath10 value of prepartition algorithm as 4 ; different types of vms wit equal probabilities . then we change the vms numbers from @xmath88 , @xmath89 , @xmath90 and @xmath91 to trace the tendency . each set of data is the average values of 10-runs . fig.5 to fig.6 show the average utilization , makespan and capacity@xmath1makespan comparison of different algorithms respectively . from these figures , we can notice that prepartition algorithm has 10@xmath0 - 20@xmath0 higher average utilization than pmg and lpt , and 40@xmath0 - 50@xmath0 higher average utilization than random - robin ( rr ) ; prepartition algorithm has 8@xmath0 - 13@xmath0 lower average makespan and capacity@xmath1makespan than pmg and lpt , and 40@xmath0 - 50@xmath0 lower average makespan and capacity@xmath1makespan than random - robin ( rr ) . we can also notice that the pmg algorithm can improve the performance of lpt algorithm . lpt algorithm is better than r - r algorithm . similar results are observed for the comparison of makespan . the performance improvement of mig algorithm is obtained from the extra migration operations . the vm migration enables a better load balance .      in this part , we will present the simulation results between prepartitionon algorithm and other three existed algorithms . random , round - robin , online resource scheduling algorithm ( olrsa ) @xcite and prepartitionon algorithm are implemented to compare : + 1 ) random algorithm : a scheduling algorithm that randomly allocates the requests to a pm that can provide required resource . + 2 ) round - robin algorithm(r - r ) : a traditional load balancing scheduling algorithm by allocating the vm requests in turn to each pm that can provide required resource . + 3 ) olrsa algorithm : an online scheduling algorithm , it computes the capacity@xmath1makespan of each pm and sort the pm by capacity@xmath1makespan in descending order . this algorithm always allocates the request to the pm with the lowest capacity_makespan and required resource . +      for realistic data , we utilize the log data at lawrence livermore national lab ( llnl)@xcite because the data is suitable for our research problem . fig . 7 to fig . 8 illustrate the comparisons of the average utilization , imbalance degree , makespan , capacity_makespan . from these figures , we can notice that prepartitionon shows the highest average utilization , lowest imbalance degree , and lowest makespan . as for capacity_makespan , olrsa has been proved much better performance compared with random and round - robin algorithms , and prepartitionon still improves 10@xmath0 - 15@xmath0 in average utilization , 20@xmath0 - 30@xmath0 in imbalance degree , and 5@xmath0 to 20@xmath0 in makespan than olrsa . we set 5 minutes as a slot , so 12 slots are for an hour , 288 slots are for a day . all requests satisfy the normal distribution , with parameters mean @xmath86 and standard deviation @xmath87 as 864 ( 3 days ) and 288 ( 1 day ) . we set that different types of vms have equal probabilities , then we change the requests generation approach to produce different size of requests to trace the tendency . from fig . 9 to 10 , we can see that prepartitionon has better performance in average utilization , imbalance degree , makespan and capacity_makespan . comparing to olrsa , prepartitionon still improves about 10@xmath0 in average utilization , 30@xmath0 - 40@xmath0 in imbalance degree , 10@xmath0 - 20@xmath0 in makespan , as well as 10@xmath0 - 20@xmath0 in capacity_makespan . it is apparent that large @xmath10 values may bring side effects since it will need more number of partitions . in fig . 11 , we compare the time costs ( simulated with llnl data and the time unit is mini second ) under different partition value @xmath10 , prepartitionon algorithm with @xmath92 takes about 10% less running time than that with @xmath10=4 , and @xmath93 takes 15% less running time than that with @xmath83 . it is easy to understand that a larger @xmath10 value will produce a better load balance with longer process time . we also observe that larger @xmath10 value will induce a lower capacity_makespan value . similarly , with a larger @xmath10 value , larger average utilization , lower imbalance degree and makespan are obtained . in this paper , to reflect the feature of capacity sharing and fixed interval constraint of vm scheduling in cloud data centers , we propose new offline and online load balancing algorithms . theoretically we prove that offline prepartition is a ( 1+@xmath54)-approximation where @xmath54=@xmath55 and @xmath10 is a positive integer . by increasing @xmath10 it is possible to be very close to optimal solution , i.e. , by setting @xmath10 value , it is also possible to achieve predefined load balance goal as desired because offline prepartition is a ( 1+@xmath55)-approximation and online prepartition ( prepartitionon ) has competitive ratio @xmath67 . both synthetic and trace driven simulations have validated theoretical observations and shown prepartition algorithm has better performance than a few existing algorithms at average utilization , imbalance degree , makespan , and capacity@xmath1makespan both for offline and online algorithms . there are still a few research issues can be considered :    * making suitable choice between total partition numbers and load balance objective . prepartition algorithm can achieve desired load balance objective by setting suitable @xmath10 value . it may need large number of partitions so that the number of migrations can be large depending on the characteristics of vm requests . for example in ec2 @xcite , the duration of vm reservations varies from a few hours to a few months , we can classify different types of vms based on their durations ( capacity@xmath1makespans ) firstly , then applying prepartition will not have large partition number for each type . in practice we need analyzing traffic patterns to make the number of partitions ( premigrations ) reasonable so that the total costs , including running time and migrations , are not very high . * considering heterogeneous configuration of pms and vms . we mainly consider that a vm requires a portion of total capacity from a pm . this is also applied in ec2 and knauth et al . when this is not true , multi - dimensional resources such as cpu , memory and bandwidth etc . have to be considered together or separately in the load balance , see @xcite and @xcite for a detailed discussion about considering multi - dimensional resources . * considering precedence constraints among different vm requests . in reality , some of vm reservations may be more important than others , we should extend current algorithm to consider this case . this research is partially supported by china national science foundation ( cnsf ) with project i d 61450110440 . partial results , especially the offline scheduling algorithm of this paper was presented in the conference of icc 2014 , sydney , australia@xcite . 99 l. andre , et al . , the datacenter as a computer : an introduction to the design of warehouse - scale machines , ebook . 2009 . m. armbrust et al . , above the coulds : a berkeley view of cloud computing , technical report , 2009 . e. arzuaga , d. r. kaeli , quantifying load imbalance on virtualized enterprise servers , in the proceedings of wosp / sipew 10 , january 28 - 30 , 2010 , san jose , california , usa . r.  buyya , r.  ranjan and r.   n.   calheiros , modeling and simulation of scalable cloud computing environments and the cloudsim toolkit : challenges and opportunities , proceedings of the 7th high performance computing and simulation conference ( hpcs 2009 , isbn : 978 - 1 - 4244 - 4907 - 1 , ieee press , new york , usa ) , leipzig , germany , june 21 - 24 , 2009 . e. g. coffman jr . , m. r. garey , and d. s. johnson , bin - packing with divisible item sizes , j. complexity , 406 - 428 , 3(1987 ) . i. foster , y. zhao , i. raicu , s. lu , cloud computing and grid computing 360-degree compared , ieee international workshop on grid computing environments ( gce ) 2008 , co - located with ieee / acm supercomputing 2008 . j. m. galloway , k. l. smith , s. s. vrbsky , power aware load balancing for cloud computing , proceedings of the world congress on engineering and computer science 2011 vol i wcecs 2011 , october 19 - 21 , 2011 . r. l. graham _ bounds on multiprocessing timing anomalies _ , siam journal on applied mathematics , vol.17 , no.2 , pp.416 - 429 , 1969 . a. gulati , g. shanmuganathan , a. holler , i. ahmad , cloud - scale resource management : challenges and techniques , vmware technical journal , 2011 . j. hu ; j.a gu ; g. sun , et al . , a scheduling strategy on load balancing of virtual machine resources in cloud computing environment , parallel architectures , algorithms and programming ( paap ) , 2010 third international symposium on , pp.89 - 96 , 18 - 20 dec . t. knauth , c. fetzer , energy - aware scheduling for infrastructure clouds , in the proceedings of cloudcom 2012 . j. kleinberg , e. tardos , algorithm design , pearson education inc . k. li , g. xu , g. zhao , et al . , cloud task scheduling based on load balancing ant colony optimization , chinagrid , sixth annual chinagrid conference , pp.3 - 9 , 2011 . a. singh , m. korupolu , d. mohapatra , server - storage virtualization : integration and load balancing in data centers , international conference for high performance computing , networking , storage and analysis , 2008 . x. sun , p. xu , k. shuang , et al . , multi - dimensional aware scheduling for co - optimizing utilization in data center , china communications 8(6 ) , pp.19 - 27 , 2011 . w. tian , adaptive dimensioning of cloud data centers : in the proceeding of the 8th ieee international conference on dependable , automatic and secure computing , 2009 . w. tian , y. zhao , m. xu , y. zhong , x. sun , a toolkit for modeling and simulation of real - time virtual machine allocation in a cloud data center . automation science and engineering , ieee transactions on , 2015 , 12(1 ) : 153 - 161 . w. tian , y. zhao , y . zhong , m. xu , c. jing , dynamic and integrated load - balancing scheduling algorithms for cloud datacenters , china communications , , vol . 8 issue ( 6 ) : 117 - 126 , 2011 . w. tian , x. liu , c. jin , y. zhong , lif : a dynamic scheduling algorithm for cloud data centers considering multi - dimensional resources , journal of information @xmath94 computational science , aug . 12 , 2013 . w. tian , m. xu , y. chen , et al . prepartition : a new paradigm for the load balance of virtual machine reservations in data centers[c ] , communications ( icc ) , 2014 ieee international conference on . ieee , 2014 : 4017 - 4022 . b. wickremasinghe et al . , cloudanalyst : a cloudsim - based tool for modelling and analysis of large scale cloud computing environments , proceedings of the 24th ieee international conference on advanced information networking and applications ( aina 2010 ) , perth , australia , april 20 - 23 , 2010 . t. wood , et . black - box and gray - box strategies for virtual machine migration , in the proceedings of symp . on networked systems design and implementation ( nsdi ) , 2007 . w. zhang , research and implementation of elastic network service , phd dissertation , national university of defense technology , china ( in chinese ) 2000 . m. xu , w. tian , an online load balancing algorithm for cloud data centers considering real - time virtual machine allocation with fixed process intervals , journal of information and computational science , vol . 11 , pp . 989 - 1001 , 2014 . h. zheng , l. zhou , j. wu , design and implementation of load balancing in web server cluster system , journal of nanjing university of aeronautics @xmath94 astronautics , vol.38 no . 3 jun . 2006 . hebrew university , experimental systems lab , www.cs.huji.ac.il/labs/parallel/workload , 2013 . amazon , amazon elastic compute cloud , http://aws.amazon.com/ec2/ , 2013 .
it is significant to apply load - balancing strategy to improve the performance and reliability of resource in data centers . 
 one of the challenging scheduling problems in cloud data centers is to take the allocation and migration of reconfigurable virtual machines ( vms ) as well as the integrated features of hosting physical machines ( pms ) into consideration . in the reservation model , 
 the workload of data centers has fixed process interval characteristics . in general , 
 load - balance scheduling is np - hard problem as proved in many open literatures . 
 traditionally , for offline load balance without migration , one of the best approaches is lpt ( longest process time first ) , which is well known to have approximation ratio 4/3 . with virtualization , reactive ( post ) migration of vms after 
 allocation is one popular way for load balance and traffic consolidation . 
 however , reactive migration has difficulty to reach predefined load balance objectives , and may cause interruption and instability of service and other associated costs . in view of this , we propose a new paradigm , called prepartition , it proactively sets process - time bound for each request on each pm and prepares in advance to migrate vms to achieve the predefined balance goal . 
 prepartition can reduce process time by preparing vm migration in advance and therefore reduce instability and achieve better load balance as desired . 
 trace - driven and synthetic simulation results show that prepartition for offline scheduling has 10@xmath0 - 20@xmath0 better performance than the well known load balancing algorithms with regard to average utilization , imbalance degree , makespan as well as capacity@xmath1makespan . 
 we also apply the prepartition to online ( prepartitionon ) load balance and compare it with existing online scheduling algorithms , in which prepartitionon can improve 8%-20% performance with regard to average cpu utilization , imbalance degree , makespan as well as capacity@xmath1makespan . 
 both theoretical and experimental results are provided . 
 cloud computing , physical machines ( pms),virtual machines ( vms),reservation model , load balance scheduling