Introduction
Related work
Problem statement and formulation
Problem statement
Problem formulation
Proposed approach
Notation | Definition |
---|---|
OO | Ordinal Optimization |
U | A set of all possible schedules in search space is termed a Candidate Set. |
N | Total number of available Schedules |
θ | A Schedule that is an element of the Candidate Set U. |
u | The cardinality of Set U, i.e., |U| = u. |
G | A Subset of U that has good enough schedules, is termed an Acceptance Set. |
g | The cardinality of Set G, i.e., |G| = g. |
S | A Subset of U has the most promising Schedule termed a Selection Set. |
s | The cardinality of Set G, i.e., |S| = s. |
M | Time taken to execute all the tasks, termed as Makespan |
k | The cardinality of Set G ∩ S, i.e., | G ∩ S | = k. |
HR | Horse Race condition |
HR_ne | Horse Race condition with no elimination |
HR_e | Horse Race condition with elimination |
OPC | Ordered Performance Curve |
σ | variation in noise |
No. of Datacentres created | 5 |
No. of cloudlets | 250 |
No. of VMs | 25 |
Cloudlet Scheduler | Space Share |
VM Scheduler | Time Share |
M/C configuration (MIPS) | random (250–1000) |
Designing of candidate schedules (U) for applying ordinal optimization
Ordered performance curve
Subset selection rules for OO
Selection of subset G (good enough schedules)
-
❖ Ordered performance curve
-
❖ HR(horse race) with no elimination (HR_ne)
Selection of subset S (acceptance schedule)
Finding GПS
Cloud simulation results and discussions
Experiment conditions
Schedules➔ Load | θ2 | θ3 | θ11 | θ13 | θ16 | θ18 | θ19 | θ24 | θ26 | θ30 |
---|---|---|---|---|---|---|---|---|---|---|
250(L1) | 468 | 410 | 483 | 445 | 483 | 555 | 439 | 449 | 459 | 432 |
300(L2) | 537 | 492 | 580 | 534 | 531 | 666 | 483 | 584 | 550 | 476 |
350(L3) | 702 | 533 | 628 | 579 | 580 | 777 | 527 | 674 | 642 | 519 |
400(L4) | 837 | 574 | 677 | 624 | 628 | 832 | 571 | 808 | 734 | 562 |
Numerical analysis of the proposed approach
X | Y |
---|---|
250 | 462.3 |
300 | 543.3 |
350 | 616.1 |
400 | 684.7 |
Computing the regression line
-
➢ The mean of X is denoted by Mx.
-
➢ The Mean of Y is denoted by My.
-
➢ The standard deviation of X is denoted by Sx.
-
➢ The standard deviation of Y is denoted by Sy.
-
➢ correlation between X and Y is coined by r.s
Mx | My | Sx | Sy | r |
---|---|---|---|---|
325 | 576.6 | 64.54972 | 95.60202 | 0.999284(high correlation) |
Linear regression table | ||||
---|---|---|---|---|
X | Y | Y′ | Y-Y′ | (Y-Y′)2 |
250 | 462.3 | 465.6 | −3.3 | 10.89 |
300 | 543.3 | 539.6 | 3.7 | 13.69 |
350 | 616.1 | 613.6 | 2.5 | 6.25 |
400 | 684.7 | 687.6 | −2.9 | 8.41 |
Makespan According to the best-fitted line | |
---|---|
250(L1) | 465.6 |
300(L2) | 539.6 |
350(L3) | 613.6 |
400(L4) | 687.6 |
Scheduling Method | Strength and Advantages | Disadvantages or Limitations |
---|---|---|
Monte Carlo Simulation Method | High precision to get the best schedule. The Monte Carlo method reduces the memory requirements of the fixed short scheduling period, resulting in high system throughput. | High simulation work with exhaustive searches for optimization. This method does not make the adapt to sudden changes in workload. Longer planning horizons degrade performance. |
Blind Pick Scheduling Method | With moderate overhead, this method applies a reduced search space and can somewhat adapt to rapid workload fluctuations. | It has moderate accuracy because it has less overhead. With a bad selection set, the performance drops in Monte Carlo. |
Ordinal Optimization (Proposed) Method | With very little overhead, OO can adapt to fast workload fluctuations and run suboptimal schedules with high multitasking throughput and reduced memory footprint. | The suboptimal schedule generated at each period may not be as optimal as the schedule generated by the Monte Carlo method. A high noise level can degrade the schedule generated by OO. |