Literature Survey

The literature survey should've been done thoroughly way back in PhD... oh well...

only after all these years, I seem to have a better understanding of the problem itself... 

and as every year it gets delayed, every DC meeting is like... have you read the recent papers?

Looks like I've collected many papers every year to properly write a survey.

Index 

AB : Agent Based

AD : Adaptive scheduling

SS : Scheduling papers from long time ago. (1970-2000)

SC : Scientific Computing in Cloud

SP : Survey papers on cloud computing - used to gauge the trend.

Type of Workload 

BTS : Bag-of-Tasks Scheduling
WFS : Workflow Scheduling

CSS : Cloud Service Scheduling

DCU : Datacenter Utilization / VM Allocation

EAS : Energy aware Datacenter resource allocation

QSS : QoS/SLA aware resource allocation

Type of Scheduling
TS : Task Scheduling
HBS : Hybrid cloud scheduling
DCS : Dynamic Cloud Scheduling
SCS : Static Cloud Scheduling

Year Wise

2005
WFS008

2008
DCS001  - grid computing, computing on heterogeneous resources.

2010

AD002

SP002

DCU002
EAS002
HBS003(CSS, QSS)
TS005(BTS)

2011

AB002

SC001
WFS001 (HBS)
WFS004(TS, DCU)
WFS007

2012

AB001

EAS001

HBS001
AD003(WFS, HBS)
HBS002(EAS)
DCU002
WFS002(HBS, SC)
HBS004(DCU, TS, QSS, SC)
WFS002(TS,QSS)
WFS003(TS, QSS, DCS)

EAS003(DCU)
SCS001(DCU)
AD002
AD004(DCU, CSS, QSS)

2013

SC001

DCU001

2015
SP003
TS007(BTS,EAS)
TS010(QSS)

2016
SP006 - cloud resource provisioning
AB003

2017
TS006(BTS,WFS, DCS)


2018
TS008(EAS, DCU)
TS009(QSS

2019
SC002  - this paper talks about adapting grid for cloud, might be useful for supporting the LHC case
TS001 - API for user defined scheduling algorithms
TS002 - Metaheuristic moth scheduling algorithm
HBS005 - bring up resource utilization of private cloud to optimum, reduces cost of bursting to the public cloud
SP005  - good paper to justify research direction in scheduling
HBS006 - Multi heuristic - GA based PSO (go figure!)
TS003 - PSO for scheduling in cloud computing.
WFS005 - (SC)
WFS006 - H2O cloud, uses reinforcement learning for clustering... not sure.
CSS001 - data streaming hybrid cloud CDN
TS004 - Hybrid PSO based.

Supporting

SS001, SS002, SS003, SS004 (also SP), SS005, SS006, SP004, SP001


Energy Efficiency Factors : Energy cost, carbon Emission rate, Workload, CPU Power Efficiency

HBS002 : reduce cost achieve established desired execution.(WF001)
HBS003 : reduce execution time, running costs (QoS parameters)
HBS004 : execution Time, public cloud cost, #VM leased
SS005  - compares 11 static heuristics, (1) Opportunistic Load Balancing  (2) MET Minimum Execution Time  (3) MCT ( Minimum Completion Time) (4) Min-Min (5) Max-Min (6) Duplex (7)GA (8) GSA (9) SA (10) Tabu (11) A*

DCU002 Resource Allocation (VM resource allocation : immediate, best effort, advanced reservation, deadline sensitive)

WFS002  : scheduling length(%), Ratio of successful execution(%), QoS factor (trust)
WFS003 :optimize makespan, reliability
WFS004(DCU) : utilization(CPU, Memory)

Now its dragged on to 2020 so need to collect even more papers :(

The discussion

https://libguides.usc.edu/writingguide/discussion

Now that I'm at the end of the road, this thing about discussing the results come up... I've no idea how to do that as I've not been able to reproduce complicated algorithms from other papers to compare an discuss it with... so i'm drawing blank here...

So "The discussion"- demonstrates your ability to think critically on an issue-develop creative solutions to problems based on a logical synthesis of the problem- formulate a deeper more profound understanding of the research problem under consideration

(Okay so, basically, I'm reinstating the problem statement in terms of the findings...)

Present the underlying meaning of your research, note possible implications in other areas of study, and explore possible improvements that can be made in order to further develop the concerns of your research.

(Okay, so i can write about that... there are tonnes of future work that needs to be done 'nywayz.

Highlight the importance of your study and how it may be able to contribute to and/or help fill existing gaps in the field. If appropriate, the discussion section is also where you state how the findings from your study revealed and helped fill gaps in the literature that had not been previously exposed or adequately described, and

Engage the reader in thinking critically about issues based upon an evidence-based interpretation of findings; it is not governed strictly by objective reporting of information.

(that might be a little tricky!)   The rest of the article is pretty informative too... give a lot of pointers!!)

Just had a thought... it's difficult to be highly critical of your own work, so I'm just gonna take all those critical reviewer comments and put them in my paper 😁 best idea I've had so far!!

And they've given me lot's of things to discuss about to... like all those things that are not in the paper... the good bits, etc...

Notes on Pareto optimal Cloud Bursting

Pareto-Optimal Cloud Bursting

 Farahabady, YLee, and  Zomaya

October 2014

focus of cloud bursting is on performance to cost ratio.
BoT applications are chosen- horizontally scalability

degree of performance is not strongly correlated with cost.

2 conflicting objectives:
1. minimizing cost(c)
2.  maximizing performance by minimizing makespan (t)

Schedule -
not possible to achieve best values for both criteria simultaneously.
sigma-bar - is said to be dominated by a schedule sigma if both the cost and time metrics are worser than or equal to the latter.

sigma star - a schedule that is not dominated by other schedule.  It is called pareto-optimal schedule.

Pareto frontier - set of all feasible pareto-optimal points.

Each user possesses a utility function, U (c,t) - represents value of a particular schedule from the user's interest.

**Actual user preferences are difficult to obtain...
** complex utility function makes the scheduling problem intractable.

Main contribution : allows users to recognize the best performance to cost ratio
the framework presented is also capable of effectively dealing with uncertainties in application or resource performance.

Problem formulated as binary integer programming problem.

- k different resource types with speeds (s1,.... sk) and cost(c1,..., ck)
- no. of resources that can be leased by the public cloud - Lk
- no of homogeneous resources that are available in the private cloud is Lv

BoT Application model
 - application B, consists of n tasks all available at scheduling time t=0
   (execution of the task is dependent on the clock spee,hence it is CPU intensive.
- the running time of task j is denoted by Pj

** preemption is not considered

If task j is assigned to run on resource i,
processing time = Pj / si
cost of execution  = (ci X Pj) / si

- |B|R - represents the amount of time taken by a BoT application to complete in a reference machine.

Objective function

 min z = theta Cost + (1 - theta) Time : theta is between 0 and 1

value of theta - helps user make better realization of the optimization goal.

• theta = 1 :  generates a solution that all tasks run in resources of the most cost effective type, i.e. with the highest values of si / ci

eg. speed is 1000 MIPS, cost is $2.00 per hour
1000/2 = 500

speed is 500 MIPS, cost is $1.00 per hour
500/2 = 250

• theta = 0 : leads to a load balance solution among available resources.

                 each resource of type i receives a load proportional to the value of si / sum of the total number of resources X the speed


Let E denote a set of pareto points denoted by the user
Let Tbest and Tworst be the best and worst makespan achievable for the execution of a given BoT application.

Writing pseudocode

I had no idea writing pseudo code will be so difficult.  I'm still not sure whether it's more appropriate to write an algorithm or pseudocode.

https://link.springer.com/content/pdf/bbm%3A978-1-4471-5173-9%2F1.pdf

So there's this link from Springer on how to write a pseudo code, I think that's a good start.  There was a review some few years back that I'm mixing up various conventions when writing a pseudo code.
Then I tried to follow some conventions and it was just too complicated.

Let's see if I'm able to write with this convention.

Also I feel an algorithm is better

Notes on Algorithms and Complexity

From a 1993 handbook on OR and MS

Sequencing and Scheduling.

Definition:optimal allocation of scarce resources to activities over time.

Algorithms and Complexity

Complexity Theory : provides a mathematical framework where mathematical problems can be classified as "easy" or "hard"

NP Complete problem :  hardest problem in NP, meaning in that if it is solvable, then each problem in NP would be solvable.
so P=NP
NP-completeness - strong evidence that a polynomial time algorithm does not exist.

A problem is NP-complete if every problem is NP and it reduces to NP-complete

Optimization problem is NP Hard - if the associated decision problem is NP-complete.

optimization problem is NP Hard - meaning it is impossible to always find an optimal solution quickly.
possible to have some approximation algorithms.

Arbitrary precedence constraints, release dates, deadlines

if release dates are specified, makes the problem strongly NP Hard.

when jobs have to meet deadlines : shown to be NP- Hard by Lawler

Many have developed elimination criteria. i.e., of it meets certain criteria for tasks, then schedule, etc.
if elimination criteria are met then the problem can be approximated to polynomial time.

The rest of the chapter examines each type of scheduling problem ones with uniform processors, heterogeneous processor, job-shop.

There is a reference to Ibarra and Kim from which I'd somewhat understood the scheduling problem.

Calculating Utilization

Yes, I'm still not done with PhD after 6 long years... I guess this year most would be at the stage of submitting thesis and would've had their research work published in some reputed journal, but here I am, still tryin' to unravel the mysteries of CloudSim... :( :(

Anyways,  I wanted to sense the utilization of CPU in MIPS or percentage at a regular interval... I need to do this to decide when the tasks can be burst to the public cloud.

Fairly straightforward, or so I thought...

I found this function attached with VM: getTotalUtilizationofCpu(double time)

VM: getTotalUtilizationOfCpuMips(double time)

I thought if I got this, then I can add up all the utilization in each VM  to calculate overall utilization in a set of VM,

I had initially set my VM's to be timeshared and cloudlets to be spaceshared.

But irrespective of whether my VM is timeshared or spaceshared, the utilization either returns 0 (I'm assuming 0%) or 1 (100%).

I can't possibly work with that !!!!!

The following is the functionality of these two functions... well, that is exactly what I want but...

• getTotalUtilizationOfCpu

  public double getTotalUtilizationOfCpu(double time)

  Get utilization created by all clouddlets running on this VM.

  Parameters:

  time - the time

  Returns:

  total utilization

• getTotalUtilizationOfCpuMips

  public double getTotalUtilizationOfCpuMips(double time)

  Get utilization created by all cloudlets running on this VM in MIPS.

  Parameters:

  time - the time

  Returns:

  total utilization

 the output I get at any interval is...

utilization on 30 :666075.0

utilization on 31 :0.0

utilization on 31 :0.0

Processing cloudletid2464

utilization on 0 :1.0

utilization on 0 :82000.0

utilization on 1 :0.0

_________________________________________________________________________________

I'm trying to reason here but it seems to me if a cloudlet is assigned a VM, then it's utilization is 100% but shouldn't that change if my cloudlet is space shared?

This does not make any sense...

I found this thread from stackoverflow:

https://stackoverflow.com/questions/28436419/cloudsim-monitoring-vm-cpu-utilization-and-bw-utilization-in-constant-intervals 

It says I have to use PowerHostUtilizationHistory... wait what????

'n it gets worse...

I found this example in vm migration... (Now since my work does not deal with migration of VM's or cloudlets or energy conservation, I've overlooked that entire part of cloudsim)

 

/**
	* The percentage of CPU that a cloudlet will use when
	* it starts executing (in scale from 0 to 1, where 1 is 100%).
	* For each cloudlet create, this value is used
	* as a base to define CPU usage.
	* @see #createAndSubmitCloudlets(DatacenterBroker)
	*/
	private static final double CLOUDLET_INITIAL_CPU_PERCENTAGE = 0.8;
	/**
	* Defines the speed (in percentage) that CPU usage of a cloudlet
	* will increase during the simulation execution.
	* (in scale from 0 to 1, where 1 is 100%).
	* @see #createCpuUtilizationModel(double, double)
	*/

Okay, does tat say that I have to define the CPU usage for each cloudet?? So like my entire code... whatever I've done so far is wrong?? I guess not, 'cos I did not see any such thing in the cloudsim examples that came with the package...

Not lemme find createAndSubmitCloudlets(..)

UtilizationModelDynamic um = createCpuUtilizationModel(CLOUDLET_INITIAL_CPU_PERCENTAGE, 1);
	for(Vm vm: vmList){
	cloudlet = createCloudlet(vm, broker, um);
	list.add(cloudlet);
	}
	//Changes the CPU usage of the last cloudlet to start at a lower value and increase dynamically up to 100%
	cloudlet.setUtilizationModelCpu(createCpuUtilizationModel(0.2, 1));
	broker.submitCloudletList(list);

I wonder what utilization Model I'm using...

UtilizationModelFull

 simple model, according to which a Cloudlet always utilize all the available CPU capacity.

Okay, starting to make sense... and the other utilization models available are:

Found this UtilizationModelStochastic

implements a model, according to which a Cloudlet generates random CPU utilization every time frame.

Again, shouldn't CPU utilization of cloudlet be based on the cloudlet length??? I'm not able to grasp these concepts...

Playing along, I'll just change is to Stochastic and find out what kinda output I get.

Ah, interesting, now I get this output:

utilization on 2 :0.9273814162364167

utilization on 2 :24111.916822146835

utilization on 3 :0.0

utilization on 3 :0.0

_________________________________________________________________________

So, let's assume I do write code to tweak the utilization w.r.t. the cloudlet length, does that mean the utilization will increase if two cloudlets are executing in a timeshared basis... it should right??/

Before I get to that, I need to know if the getUtilizationHistory() of the powerHost works... now I've no idea how to call that in the context of my code...

let me just instantiate powerhost and power VM, see if that does the trick in accessing getUtilization History.

kay so I had to change host to PowerHost, there are some power models available, no idea which one to choose so I randomly chose, PowerModelSpecPowerIbmX3550XeonX5675

Next had to change VM to PowerVM, the constructor changes a lot...

looked up some examples on what to set for priority... most examples give 1, so I'm gonna go with that...

.

.

.

A scheduling interval also needs to be set... At this point, I feel, I'm doing something without understanding anything, but no other go...

I tried to get utilizationHistory of vm, but unfortunately that is a protected method.  I can only get Utilization history of host with the powerhostUtilizationHistory...

so I guess creating a power host isn't enough?? I need to create a PowerHostUtilizationHistory??

STOP

I found another code that dosn't completely change the Host and VM to power everything...

https://github.com/manoelcampos/cloudsim-plus/blob/master/cloudsim-plus-examples/src/main/java/org/cloudsimplus/examples/PowerExample.java

will revert to that!

It uses VmSimple, HostSimple...

Okay but this class is in CloudSim Plus... 'n in my installation since it's from ages ago, dosn't work!!

Should I install cloudsim plus now???

I guess... It would make life easier!

But then again... how much of my existing code would I have to rewirte??? :( :(

updateVMs processing

This function is pretty tricky....

I'm using this to find expected completion time of a a particular cloudlet on a machine.

If there is not cloudlet assigned to it... it returns 0...

else it returns .2

huh...

everything traces back to cloudletScheduler... which seems to be an interface with no implementation.

Have to find out what class implements this....

oh... this is an abstract class... so if it is timeshared, then we have to look into that

public double updateVmProcessing(double currentTime,

                        List<Double> mipsShare)

Updates the processing of cloudlets running on this VM.

Parameters:

currentTime - current simulation time

mipsShare - array with MIPS share of each Pe available to the scheduler

Returns:

time predicted completion time of the earliest finishing cloudlet, or 0 if there is no next events

I think I found out why it returns .2...

Why would they code it like that :(

Now I have to write my own implementation for this and override it...

In https://github.com/marcbux/dynamiccloudsim/blob/master/src/org/cloudbus/cloudsim/CloudletSchedulerTimeShared.java

// estimate finish time of cloudlets
 for (ResCloudlet rcl : getCloudletExecList()) {
   double estimatedFinishTime = currentTime
     + (rcl.getRemainingCloudletLength() / (getCapacity(mipsShare) * rcl.getNumberOfPes()));
   if (estimatedFinishTime - currentTime < 0.1) {
    estimatedFinishTime = currentTime + 0.1;
   }


   if (estimatedFinishTime < nextEvent) {
    nextEvent = estimatedFinishTime;
   }