Experience-based Efficient Scheduling algorithm (EXES) for serving requests in cloud using SDN controller

Abstract

Efficient servicing of requests in cloud environment has become need of the hour. Cloud services work based on zones in various locations and multiple service requests may be simultaneously considered as a batch and allocated to various zones. Experience-based Efficient Scheduling or EXES focuses on achieving minimum possible waiting time for a batch of requests, under the constraint that overall allocation cost should be less than or equal to a budget limit. Migration of tasks is also possible to balance loads if budget permits and we gain in energy. For each task in a batch and all available zones, a priority value is computed based on previous interaction experience of the zone and the site that generated this task. The zone that produces highest priority for a task, is allocated the task. An SDN controller is in charge of the entire process of priority computation and assigning tasks to zones. Priority is given to requests generating from sites that consumed lesser execution time compared to other sites that have generated requests in request queue of the zone. To the best of authors’ knowledge, no existing scheduling scheme in cloud has considered batch processing based on service process experience of zones.

Keywords

Allocation budget cloud load minimum waiting time priority software-defined-networks

1 Introduction

1.1 Utility of SDN in scheduling in cloud

Allocating a batch of requests to zone offering average minimum waiting time, is extremely important from the perspective of energy-efficient scheduling in a cloud environment. It directly affects the application and service availability for cloud clients [1, 2, 5, 8, 10–21]. Load balancing is a mention-worthy part of it. Intention behind building a good scheduler is to utilize resources to the fullest so that [3–7] overall cost could be restrained within a predefined budget limit. It is a general practice to deploy [5–7] data centers with dedicated hardware to distribute a batch of tasks on requests to multiple zones so that risk of overloading a single server gets reduced. But these hardware systems normally used in clouds, are difficult and expensive to procure; can be technically challenging to be deployed and may require human intervention to work in a continuous consistent mode. In order to eliminate this not-so-smart human intervention, software defined network (SDN) [8–10] has been introduced. SDN provides a convenient and flexible flow control method with nominal investments that enhances benefit-cost ratio for a large number of cloud clients.

1.2 Contribution of EXES

In the proposed experience-based efficient scheduling EXES, [1–17] a centralized SDN controller is deployed to communicate with zones whenever a batch of requests flows into it. The controller keeps track of number and length of service requests generated by various sites to a zone. It will instruct a zone Z to assign low priority to a task T generated by a site st if st produced earlier a huge number of tasks to the 1 above same zone Z. In this way, EXES discourages sites from overloading the system too much. Also, sites feel an urge to try a variety of zones to get priority, instead of sending requests to one particular zone. This helps in balancing load without specific migration of tasks from one zone to another. Explicit migration of tasks is also allowed if budget permits and gain in energy is expected.

Computation of process priority with respect to various zones is also unique in EXES. If most of the processes from a site st suffered huge waiting time in zone Z, then in future, processes generated by the same site are expected to enjoy higher priority in Z. If st has already utilized a lot of processing capacity of zone Z, then priority of its forthcoming processes will decrease. If length of a task is huge, then its priority is expected to be low. This is in line with SJF or shortest path algorithm. This contributes to minimize waiting time, as much as possible, for a batch of processes.

2 Related work

Traditional:: Among traditional scheduling algorithms in cloud networks, round-robin [9] is the most primitive. A circular order of zones is pre-defined. The first request is allocated to a zone picked randomly, say, the i-th zone. Then the second request has to be serviced by (i + 1)-th zone, the third one by (i + 2)-th and so on. Throttled load balancing algorithm (TLBA) [10, 11] maintains a list of busy and free zones. A request is allocated to a totally free zone if available, otherwise, any of the busy zone is allocated. Priority algorithm [13] assigns the least busy zone to highest priority job. In Load Balanced Scheduling Algorithm (LBSA) [33],a new request is allocated to a zone having least number of entries in the Request Allocation Table (RAT). Simplicity or ease of implementation is the only merit of traditional scheme. Demerit - these schemes do not consider waiting time of service requests. Priority algorithm does not compare workload on busy zones. Any one of them is selected randomly if no completely free zone is available.

Ant and bee colony: J. Yao and J.H [15] proposed an artificial Bee Colony algorithm based on characteristics and requirements of cloud computing environment. Hundreds of requests with the same type are queued to the same server. A. Chala and N.S. Ghumman [19] scheduled the tasks based on cost. A zone is allocated to a request that will require minimum allocation cost. Demerit – This scheme emphasizes on minimizing the allocation cost and completely ignores the issue of optimizing average waiting time which is an important drawback. Also it does not talk about balancing loads.

Power-aware load balancing method is proposed in [21] where each active zone computes its percentage of utilization. Newly arrived request is allocated to the zone with least utilization percentage. Demerit – This saves energy in zones but ignores performance optimization.

K. Li et al. [21] proposed a task schedule policy based on ant colony optimization. It balances load along with minimizing make span for a set of requests. Demerit – Please note that priority computation of resources in this scheme does not depend upon energy consumption in zones by various competing sites. A site that has largely utilized service of a zone in the past, should not enjoy high priority in the same zone in future. Moreover, there has to be a budget to which every task allocation and migration should conform.

Particle swarm optimization based:: A particle swarm optimization (PSO) based method appears in [26] that instructs certain tasks to migrate from heavily loaded zones to a comparatively less busy zone. Demerit – Although this reduces the time required for preparing a load balanced schedule, it does not minimize waiting time for a batch of tasks.

Cluster based:: One cluster based scheduling approach is also proposed in literature of cloud network [27]. It divides the network into multiple single hop clusters. Each cluster has a cluster head (termed as master) and a set of ordinary cluster members called slaves. The slaves periodically inform their master regarding processing load, storage and band width. Master maintains a table of load information of all of its slaves. Whenever a new request arrives at the master, it allocates that to the slave with minimum load. Demerit – However, minimum load does not necessarily guarantee optimum waiting time.

Game theoretic:: Certain scheduling algorithm are game theoretic. K.G. Srinivasa et al. [28] proposed one such algorithm that employs a utility maximization approach to solve resource partitioning and allocations problem. Utility value is computed taking into account the factors like weight for money, cost per second, length and capacity of each request. In different rounds of the game, local and global maxima of utility values are computed. First resource is allocated to the request with maximum utility or the global maxima. Non-cooperative game resource allocation algorithm appears in [29] which solves Nash equilibrium to obtain reasonable resource allocation strategy. It focuses on collective benefits of job or task requests than individual requests. The algorithm presented by X. Xu and H. Yu [30] considers fairness among users and resource utilization both. FUGA (Fairness-utilization Trade off Game Algorithm) is implemented on an 8-node server cluster. Fairness of this scheme is compared with the same of Hadoop Scheduler, and it showed improvements in favour of FUGA. Demerit – These algorithms do not consider the history of allocating service requests to zones. If a site generates request at a huge rate compared to others, then its jobs should be punished by assigning low priority, which is done in EXES. The task of migrating tasks from one physical zone to another should be considered.

Processing capacity based::Minimum execution time (MET) [31] is a heuristic that chooses the zone where execution time of a request will be smallest. It does not balance load too. In Dual Weighted Least Connection approach (DWLC) [32], each zone is assigned an weight based on it’s processing capacity. The zone with a higher weight value, receives a larger percentage of active connections at any point of time. Default weight value is one. In DWLC, new request is assigned to a zone having least ratio of (number of requests already assigned / processing capacity). The zone with better processing capacity will require smaller execution time for a job. Demerit – These schemes typically consider only processing capacity of zones. Existing loads in them are ignored. Also the possibility of task migration is not there.

3 Overview of EXES

3.1 Utility of batch processing

With the help of Figs. 1–8, the example below demonstrates the fact that considering Average Minimum Waiting Time for a batch of tasks is always better than considering Minimum Waiting time for an individual task. The tasks in the batch are stored in job or task queue and processed in FIFO order. Although in implementation of EXES, tasks are placed in task queue according to some priority assigned to generation sites of those tasks. Priority is computed by zones depending upon experience of those zones in serving requests generated from that site. This priority is applicable to all competing scheduling algorithm in simulation section. Consider a batch of jobs J1, J2, J3 of lengths 3, 15 and 16 respectively, as shown in Fig. 1. Two zones are available – zone 1 and zone 2. Task queues of these zones are shown in Fig. 2. Task queue of zone 1 is containing 4 tasks of lengths 6, 1, 3 and 1 while the same of zone 2 is containing 5 tasks of length 8, 2, 3, 1 and 7 respectively. Number of empty locations in zone 1 and 2 are 1 and 2 respectively, i.e. zone 1 ‘s task queue can accept only one more job at this point of time while the same of zone 2 can accept 2.

Fig.1

Batch of jobs.

Fig.2

Task queues of zones 1 and 2.

Allocation of J1:

J1 has length 3. It can be placed both in zones 1 and 2. Waiting times offered by zone 1 and zone 2 are 11 and 21, in that order. So, J1 will be placed in zone 1. Zone 1 now looks like Fig. 3. It’s task queue is completely filled, waiting time suffered by J1 = 11.

Fig.3

Task queue of zone 1.

Allocation of J2:

J2 has to be allocated in zone 2. At this moment, task queue of zone 2 will look like Fig. 4. Here waiting time of J2 = 21.

Fig.4

Task queue of zone 2.

Allocation of J3:

J3 too has to be allocated in zone 2 because there is no other option. Now, task queue of zone 2 is as per Fig. 5. Waiting time of J3 = 36.

Fig.5

Task queue of zone 2.

Average waiting time for the batch in minimum individual waiting time approach = (11 + 21 + 36)/3 = 68/3 = 22.667. Here we assume that the entire batch is available to us and we serve jobs in the batch in any order we desire.

J3 is placed in zone 1. Task queue of zone 1 will look like Fig. 6. Therefore, waiting time of J3 = 11. Now zone 1 can not accept any more job.

Fig.6

Task queue of zone 1.

J1 is allocated to zone 2. Task queue of zone 2 looks like Fig. 7. Waiting time of J1 = 21

Fig.7

Task queue of zone 2.

J2 has to be allocated to zone 2. Task queue of zone 2 looks like Fig. 8. Waiting time of J2 = 24.

Fig.8

Task queue of zone 2.

Therefore, average waiting time for the batch in average minimum batch waiting time approach = (11 + 21 + 24)/3 = 56/3 =56/3 =18.667 < 22.667. Hence, average waiting time improves.

3.2 Main aspects of EXES

Whenever a batch of requests enter into the system, the SDN controller computes initial priority of a process P generated by site st with respect to a zone Z as per the following factors:

If average waiting time suffered by earlier processes of site st at zone Z is large, then priority of P at Z will be high.

If earlier processes generated by st have utilized a huge processing time of Z, then it will reduce priority of P in Z.

If length of current task is high, then its priority will be low.

If rate of producing service request by st on Z has been really high in the past, then it will negatively influence the priority of P in zone Z.

These criteria are purely novel and rationally control rate of packet generation as well as propagation. Initial priority of a process P in all available zones Z is computed based on a weighted function of estimated waiting time of P in Z and the associated allocation cost. Then this priority is modified in different passes by increasing weight of waiting time and decreasing wait of cost. The underlying intention is to assign maximum possible weight to the waiting time criterion while conforming to the budget constraints.

4 System modeling

4.1 Task allocation

Zone based task allocation is considered in EXES based on practical examples. A mason is a cloud service provider that extends services line infrastructure, platform and software on the basis of pay per use. It has multiple zones in various geographical locations like US, EUROPE, ASIA etc. At any point of time it may happen that use of cloud resources at some zone is much more than others. In that case, intelligent allocation of task is need of the hour. Let a batch of n task on requests are to be assigned to m number of zones. Each zone Z has a timed allocation cost with respect to a resource request R_i. The cost depends upon geographical distance between origin of request and the zone on which it is to be allocated. In EXES, the goal of allocating a batch of requests to a set of zones, is to minimize average waiting time while keeping the overall cost within budget limit M. A solution to the scheduling problem is a matrix a of n rows, one for each requests and m columns, one for each zone. a_ij = -1 if request R_i is not allocated to Z_j. Otherwise, a_ij is a triplet such that a_ij = (x_ij, y_ij, z_ij) where x_ij is estimated waiting time of request R_i in zone Z_j; y_ij is associated allocation cost and τ_ij denotes the time stamp at which R_i is supposed to be given to Z_j. Average waiting time considering the entire batch, is given by (1), while the corresponding cost-budget relationship is expressed in (2). $\begin{matrix} awt = {\sum extr (a_{ij}, 1) | a_{ij} / = - 1} / n \\ 1 \leq i \leq n, 1 \leq j \leq m \end{matrix}$ (1) $\begin{matrix} {\sum extr (a_{ij}, 2) | a_{ij} / = - 1} \leq M \\ 1 \leq i \leq n, 1 \leq j \leq m \end{matrix}$ (2)

∀1 ≤ p ≤ 3 extr (a_ij, p) is a function that returns p-th field of a_ij. If p = 1, extr (a_ij, p) will return x_ij. Similarly y_ij and z_ij will be returned corresponding to the values 2 and 3 of p.

4.2 Task migration for load balancing

Task migration is performed by the SDN controller under the following situations. i) Estimated energy consumption of queues in certain zones is much higher than the average energy consumption in the collection of zones. ii) through migration system must not loose in terms of energy as well as waiting time. iii) cost of migration after allocation of requests, should be within budget. Assume that zone Z_i needs enr_i amount of energy to finish a unit length task: Z_i can migrate a task R_k of length 1_k to anoter zone Z_j provided conditions (3) and (4) hold good. $(l_{k} \times {enr}_{i}) \geq (l_{k} \times {enr}_{j}) + {migr}_{ij} (k)$ (3) ${wtime}_{i} (k) \geq {wtime}_{j} (k) + migr - {time}_{ij} (k)$ (4)

Here, migr_ij (k) is energy cost involved in migration of R_k from Z_i to Z_j and the corresponding time required is migr - time_ij(k). These are formulated in (5–7). ${migr}_{ij} (k) = (ψ 1 + {dis}_{ij} + l_{k})$ (5) $migr - {time}_{ij} (k) = {migr}_{ij} (k) / ψ 2$ (6) $migr - {time}_{ij} (k) = {migr}_{ij} (k) / ψ 2 + 1$ (7)

l_k is length of R_k and dist_ij is cartesian distance between Z_i and Z_j. ψ1 and ψ2 are constants.

4.3 The EXES architecture

The EXES architecture appears in Fig. (9) where multiple geographically close users are under monitoring of one particular site. Multiple such sites are there in the network. Resource requests from individual users arrive at these sites. Sites blindly forward them to the SDN controller. The SDN controller decides which zone to allocate one particular request. The SDN controller stores information about zones and sites into the tables named Zone-cost-table, site-reputationtable, site-table and Zone-start-table.

Fig.9

The EXES architecture.

Zone-cost-table consists of i) zone– id ii) site– id iii) cost.

zone– id and site– id denote unique identification number of the zone and site, which cost specifies the cost of allocating a request generated at site– id to the zone specified by zone – id.

Component of site– table are i) site-id ii) (bl – locx, bl – locy) iii) (tr – locx, tr – locy)

bl – locx and bl – locy denote bottom left x and y coordinates of the site having identifier site – id, while tr – locx and tr – locy denote top – right x and y coordinate positions of the same site.

Site– reputation– table consists of i) zone– id ii) site– id. iii) no-of-job iv) Wait– suffered, site– id, zone-id v) additional– wait – introduced vi) tot-time-consumed vii) handshake– timestamp

tot– time-consumed is the total time of zone– id consumed in serving a request of site– id. no-of– job indicates the total number of jobs the site numbered site– id has issued so far to the zone numbered zone– id. wait– suffered denotes the total waiting time that has been suffered by a task generated by zone– id at side site– id from handshake – timestamp. additional– wait– introduced is the additional waiting time caused by a job generated at site – id to other jobs in the site.

Attributes of zone– stat– table are i) zone– id ii) unit– task– eng iii) pointer to job– list

unit-task-eng is the amount of energy consumed by zone zone-id to perform a unit length task. Pointer to job list points to the jobs that has been carried out by zone zone-id.

job-list comprises of the followings;- i) request– id ii) site– id iii) start– timestamp iv) end– timestamp.

4.4 Allocating requests to zones

4.4.1 Priority computation

Priority assigned to task R_i by zone Z_j, is denoted as PR_ij and mathematically modelled in (8). ${PR}_{ij} = \frac{(\sum_{s \in S} θ_{org (i), j} (s) + 1) (t - τ m_{org (i), j} + 1)}{(\sum_{s \in S} θ_{org (i), j}^{'} (s) + 1) (| S | + 1) 1_{i} θ_{org (i), j}^{'} (s^{'})}$ (8)

Fig.10

Values of α and β in different rounds.

Fig.11

Flowchart of EXES.

org(i) is the site at which R_i originated. S is the set of past communication sessions when a task originating from org(i) was given to Z_j for service. θ_org(i),j (s) is the waiting time a job of site org(i) suffered in queue of Z_j in sessions.

θ′org (i) , j (s) is the processing time of Z_j utilized by a request from org(i) in session s. Let the current timestamp be denoted as t. τmorg (i) , j is the timestamp when the first request of org(i) arrived at zone Z_j. 1_i is length of the request R_i. s ^′ denotes the current session. Formulation of PR_ij is based on the fact that request from a site will get high priority if earlier requests from the same site suffered high waiting times in queue of Z_j and those requests did not entrust huge processing load on the zone. Moreover, rate of assigning requests on one particular zone by a site should be small to gain high priority. Shorter jobs are placed high on priority list to incorporate flavour of shortest-job-first (SJF) algorithm. This will reduce waiting time in any schedule. Comparing value of P R_ij with priorities of other requests residing in queue of Z_j, Z_j decides a suitable place for R_i in it’s task queue. Zones always order requests in increasing order of priority. According to position of a request R_i, it’s waiting time in Z_j can be computed. Let position (w + 1) has been decided for R_i in Z_j. Also assume that start_j (k) and end_j (k) denote start time and end time, respectively, of R_k in queue of Z_j. Then waiting time wtime_j (i) of R_i in queue of Z_j is formulated in (9). ${wtime}_{j} (i) = ({start}_{j} (w) - {start}_{j} (1))$ (9)

Let, cost of allocating a unit-length request from org (i) in Z_j is given by cost_j (org (i)). Then, overall cost of allocating R_i to Z_j is denoted as C_j (i) and mathematically expressed in (10). $C_{j} (i) = {1_{i} \times {cost}_{j} (org (i))}$ (10)

Similarly, for all other zones, wtime and c are computed. These two criteria are combined into the final criterion F_j (i) as in (11). $F_{j} (i) = {{wtime}_{j} (i)}^{α} {C_{j} (i)}^{β}$ (11)

where α, β ≥ 0.

R_i is allocated to a zone Z_v s.t. 1 ≤ v ≤ m and F_v (i) ≤ m

∀F_j (i)

j = 1

4.1.2 Rounds of binary search for the optimum

In first round of search, α = 1 and β = 0, i.e. only wtime is considered for all requests. If summation of associated cost of all sites is less then solution is obtained in the first round, otherwise subsequent rounds become essential. For example, assume that at any point of time, five requests R1, R2, R3, R4 and R5 have arrived in a batch. Three zones are there Z1, Z2 and Z3 values of F have been computed putting α = 1 and β = 0.

Consider that the following conditions are true:-

F2(1)≤ {F1 (1) , F3 (1)}

F3(2)≤ {F1 (2) , F2 (2)}

F1(3)≤ {F2 (3) , F3 (3)}

F3(4)≤ {F1 (4) , F2 (4)}

F1(5)≤ {F2 (5) , F3 (5)}

Therefore, minimum waiting time is offered to the requests R1, R2, R3, R4 and R5 by zones 2, 3, 1, 3 and 1 respectively. Overall cost CT of the system is formulated in (12) $C T = C 2 (1) + C 3 (2) + C 1 (3) + C 3 (4) + C 1 (5)$ (12)

If CT ≤ M, then the solution is acceptable. When α = 1 and β = 0, cost has no contribution in determining best zone. Similarly when α = 0 and β = 1 only cost is considered as a criterion to allocate a zone to a request. If this minimum overall cost is also higher than budget, then SDN controller understands that allocating the current batch of requests to zones is not possible abiding by the budget limit. In that case, budget is completely ignored and we accept the solution where α = 1 and β = 0. Figure 5 demonstrates various different values of α and β corresponding to the situations cost ≤ M and cost > M. Whenever we see that cost ≤ M, we go on increasing impact of average waiting time, unless the output converges. Similarly hen cost > M, increase impact of cost. The binary tree shown in Fig. 12 is termed as α = 1, β = 0, param-impact tree.

Values of α and β are modified in different rounds as per the following rules:-

when α = α1, β = β1 and cost ≤ M, new values of α and beta will be like α = α1 and β = β1/2

when α = α1, β = β1 and cost > M, new values of α and β will be like α = α1 and β = (β1 + max f (α1, β1))/2

For any (α1, β1) pair, maxf(α1, β1) is second component of the closest predecessor of the node (α = α1, β = β1) in left subtree in which the node (α = α1, β = β1) resides. A flowchart of the overall system is drawn in Fig. 12.

Fig.12

Average waiting time vs size of batch.

LEMMA 1. Maximum value of β in left subtree of the node (α = α1, β = β1) in a param-impact tree, is less than β.

PROOF. Maximum value of β in left subtree of the node (α = α1, β = β1) must appear in right most node of the left subtree of param – impact tree generated at (α = α1, β = β1). Values of β in right most node of that param – impact tree, at different levels, is shown below:-

level-1: β = β1/2 in left child of (α = α1, β = β1)

level-2: β = (β1 + β2/)/2

level-3: β = {β1 + (β1 + β1/2)/2}/2

level-4: β = [β1 + {β1 + (β1 + β1/2)/2}/ 2]/2

Assuming that at level n the solution converges, value of β at n – th level in left subtree of param – impact tree generated at (α = α1, β = β1) shown in (13).

Level h: $β = β 1 / 2 + β 1 / 2^{2} + β 1 / 2^{3} + \dots \dots + β 1 / 2^{n}$ (13) $i . e ., β = β 1 / 2 [1 + 1 / 2 + 1 / 2^{2} + \dots + 1 / 2^{n - 1}]$ (14) $\begin{matrix} i . e ., β = β 1 / 2 [(1 - 1 / 2^{n}) / (1 - 1 / 2)] \\ i . e ., β = β 1 / 2 [1 - 1 / 2^{n}] < β 1 \end{matrix}$ (15)

LEMMA 2. No loops can appear in param – impact tree.

PROOF. As per lemma 1, β1 cannot appear in left sub tree of the param – impact tree generated at node (α = α1, β = β1). Any arbitrary node in right sub tree generated at (α = α1, β = β1) can be expressed in general as, η (p + β1)/2ⁿ where n ≥ 1 and p and η are both old numbers. Let us assume that for some valid p and η,(α = α1, β = β1) reappears in the param – impact tree of Fig. 14. $Therefore, η / 2^{n} (p + β 1) = β 1$ (16)

$So, η p + η β 1 = 2^{n} β 1$ $or, β 1 (2^{n} - η) = η p β 1$ $or, β 1 = η p / (2^{n} - η) β 1$

Please note that, 2ⁿ - η = 2k for some 0 < k < η. So, η = 2ⁿ - 2^k.

Both, η and k are >0 hence, η can not be odd, which is a basic requirement for any node (α = α1, β = β1). So, we can conclude that (α = α1, β = β1) can not appear in right sub-tree of (α = α1, β = β1), as well.

5 Simulation

5.1 Simulation environment

In order to evaluate effectiveness of the proposed scheme, the tools open stack and Haprony are used. Open stack is a renowned open source cloud management platform that uses virtualization system KVM to create, manage and destroy virtual machines through APIS. The virtual machines are approximate identical with the configuration of 2.4 GHZ CPU, 8G RAM and Ubuntu 12.04 OS. Haprony is an open source traditional load balancing procedure which has been changed to EXES load balancer. Number of zones in our experiment is 10. Each has it’s own capacity of storing resource requests in queues. Minimum and maximum queue sizes are 10 and 30. Numbers of jobs on requests take the values 100, 300, 500, 700 and 1000. Queue size in the SDN controller is 100. This means maximum size of a batch can be 100. Scheduling decision made by EXES, is compared with load balance Scheduling Algorithm (LBSA), Dual weighted least connection (DWLC) and minimum execution time (MET) algorithm. Metrics considered are average waiting time, cost, effect of bandwidth over average job completion time and percentage of success after balancing.

5.2 Simulation results

Average Waiting Time:

This is the criterion that is considered most important in EXES. LBSA and DWLC consider only number of requests, not the approximate waiting time of requests in zones. MET depends upon only execution time, not the waiting time. on the other hand, EXES takes care of not only the waiting time but also tries to minimize average waiting time for a batch of processes. Therefore, performance improvement is very prominent in favour of EXES, as seen in Figs. 12 and 13 in two different simulation runs.

Fig.13

Average waiting time vs size of batch.

Cost:

Cost has two components in our perspective – one for placing jobs in various zones (this depends on band width as well as the geographical distance between originating site of a job and the zone where it will be allocated) and cost of migrating jobs from one zone to another (again this depends on available band width and distance between zones). When multiple zone options are available to place one particular job, EXES goes for the one that optimizes two criteria – waiting time and cost. Staying within budget limit, EXES tries to gain as much as possible in terms of overall waiting time. as for as job migration is concerned, EXES does not get involved into that very often until and unless it explicitly yield good advantage. Therefore, overall cost in EXES is lesser than others, as seen in Fig. 14.

Fig.14

Cost vs size of batch.

Job Completion Time:

Band width plays a vital role in scheduling decisions. Task migration always consumes band width, along with causing additional significant delay since transferring executable and data of a job requires time. a lower band width often results in higher cost as well as job completion time, affecting overall performance of the distributed system. EXES migrates task only when a huge advantage is achieved in terms of average waiting time and associated transfer cost added to overall execution cost lies within budget. EXES, by it’s own nature always schedules job based on average waiting time for an entire batch. Therefore, compared to other algorithm, job migration is performed in EXES much lesser number of times and whenever that is performed, we gain substantially in terms of waiting time and entropy. This completion time gain for individual jobs along with batch waiting time improvement, lead to significant reduction in completion time of jobs. This is expressed in Figs. 15–19 corresponding to number of requests 100, 300, 500, 700 and 1000, where job completion time is plotted vs band width. It is clearly seen from there that whatever be the number of jobs, overall job completion time in EXES is much smaller than it’s state-of-the-art competitions.