Wake up call

hmmmm.... getting a paper rejected...
A wise person once said not to be discouraged if a paper got rejected. I think i'm done wallowing in self-pity... i'm allowed to do it for some time...
Let's see those comments now...
The abstract should preferably be within 150 words.
  mine was around 130 words...

Clearly give five keywords in alphabetical order at the end of the abstract.
  ummm, now... I didn't know keywords had to be given alphy order... will keep that in mind.

 Introduction to the papers may be in two to three paragraphs.
 mine was all crammed in one...

There should be a clear paragraph for motivation of your work.
 ugh... this is not the first time someone's telling me to write motivation properly... that is definitely an obstacle i'm still facing.

Clearly highlight the contributions of your work in a paragraph. This is mandatory. It gives a glimpse of your work to the reviewer.
  okay, i failed to do that... since i'm not doing anything in real world... this part is shady even to me 

 The Literature Survey should be relevant and recent.
  hate the literature survey part... i put literature survey i did initially for my problem statement for my Ph. D 2 years ago... don't judge... lack of time!!!

The Background work of the existing works for comparison should find place in the paper.
   yup... i was under fire for not doing this properly since my Literature survey DC :(

 System Model, Mathematical Model, Proofs, Theorems enhances the quality of your paper.
  I actually wanted some feedback whether the equations i'm writing are correct...  maybe in my next paper rejection i'll get those...

The algorithm should be simple and understandable and neatly put in a box. There are numerous algorithmic styles available on net. You can use any of them.
  I used my own algorithmic style... don't think that was okay with the reviewer... i have to follow a good style... not hard to do... will do that.

Each paragraph should be in 6-7 sentences.
   ummm... okay...

The implementation of the algorithm, comparison with existing state-of-the-Art works is mandatory.
  my paper only had the theoretical part... hadn't started any implementations then... will do that now.
Your work should clearly stand out from other works and you should clearly state the reasons for improvement.
  future enhancements... done!

Conclusions should be to the point, clear and terse.
 J'accepte! My conclusion was all over da place...

The Bibliography gives the type of references you have been following to write your paper. The reviewer will be able to gauge the depth of your research from the Bibliographic references.

Follow the format, style sheet and template given to you meticulously.
  I might have not have been too keen on the m-e-t-i-c-u-l-o-u-s part... will do that next time...

I wanted to send another wishy-washy paper... not prepared to get burnt again... I'll do more code now... 

Cloudsim : MinET and MinCT

MinET(Minimum Execution Time )

As expected in MET all the cloudlets got allotted to VM #0 'cos that's having the minimum execution time with 82000 mips but because we do not consider the load already allocated to it, all the tasks get allotted to it...

Some observations:

• When size ratio is more, in BoT 5, it is 13 (more number of small tasks), MET performs better than {StoL, R}.
• In all other cases the performance is not good.

MinCT (Minimum Completion Time)

Now to determine which machine gives earliest completion time(MCT) and the trick here is we should know when the machine will be ready after completing the task at hand and then allot.

So, I had to do a substantial amount of tinkering around in cloudsim to get this thing to work properly...

What i did initially...
I modified the submitCloudlets() method in myDataCenterBroker class by manually calculated the expected finish time....
but the problem was...
in this method, the cloudlets just get submitted... at maybe 0.1 in cloudsim clock time....
No cloudlets begin execution in vm and hence it is impossible to calculate the expected finishing time for which you need to know the current number of cloudlets in the vm,,,

Solution :
I still sent the cloudlets to randomly assigned VM's...
I extended the Datacenter class to create a myDatacenter class.
So in the processCloudletSubmit method is where the cloudlets are submitted to the cloudlet scheduler.

before that happens, I calculate the vm which will give the minimum expected completion time.

for(Vm vm : getVmList()){
                    
            CloudletScheduler scheduler1 = vm.getCloudletScheduler();
           Log.printLine("No. of Currently running cloudlets in VM #"+vm.getId()+" :"+ scheduler1.runningCloudlets());
             Log.printLine("Estimated finish time in VM #"+vm.getId()+" :"+
                             scheduler1.updateVmProcessing(CloudSim.clock(), scheduler1.getCurrentMipsShare()));
                     
          double eft = scheduler1.updateVmProcessing(CloudSim.clock(), scheduler1.getCurrentMipsShare());
      if(vm.getId()==0)
            mineft = scheduler1.updateVmProcessing(CloudSim.clock(), scheduler1.getCurrentMipsShare());
                     
                     if(eft <mineft){
                         mineft=eft;
                         minVmId = vm.getId();
                     }
                }


Then I reassign the vm id to that particular cloudlet to minVmId....

The output will look something like this, for one of the cloudlets submitted...

No. of Currently running cloudlets in VM #0 :7
Estimated finish time in VM #0 :4295.208414634147
No. of Currently running cloudlets in VM #1 :6
Estimated finish time in VM #1 :4295.20812244898
No. of Currently running cloudlets in VM #2 :4
Estimated finish time in VM #2 :4295.22676923077
No. of Currently running cloudlets in VM #3 :15
Estimated finish time in VM #3 :4295.203269230769
No. of Currently running cloudlets in VM #4 :20
Estimated finish time in VM #4 :4295.20076923077
No. of Currently running cloudlets in VM #5 :33
Estimated finish time in VM #5 :4295.200000000001
No. of Currently running cloudlets in VM #6 :1
Estimated finish time in VM #6 :4295.200000000001
No. of Currently running cloudlets in VM #7 :1
Estimated finish time in VM #7 :4295.200000000001
No. of Currently running cloudlets in VM #8 :1
Estimated finish time in VM #8 :4295.200000000001
No. of Currently running cloudlets in VM #9 :1
Estimated finish time in VM #9 :4295.200000000001
4295.1 @ Minimum EFT is VM #5

What I did later :
I didn't override the submitcloudlets method in myDatacenterBroker 'cos I don't need to assign any VM to it.... I just let it do whatever it does by default.

I did an override on the processCloudletSubmit in myDatacenter directly... seems to work fine...

 Some observations

• For BoT 5 where the size ratio is 13 (where the number of small tasks are more), {LtoS, MinCT} performs much better compared to all other scheduling algorithms.
• The same can be observed in BoT 7 where the size ratio is 7.
• I think I can safely conclude that if there is a system in heterogeneous computing with very high MIPS compared to the rest ordering the tasks LtoS gives good results because... obviously, those tasks get assigned to the most powerful machine first and they get executed first.

Notes from Dynamic Matching and Scheduling of a class of independent tasks on heterogeneous computing systems

Title : Dynamic Matching and Scheduling of a class of independent tasks on heterogeneous computing systems

Authors : Muthucumaru Maheshwaran, Shoukat Ali, Howard Jay Siegel, Debra Hengsen, Richard F. Freund

Year 1999

Journal of Distributed and Parallel Computing

Heterogeneous Systems : schemes are necessary to assign tasks to machines (matching)

then compute order of execution (scheduling)

mapping - the process of matching and scheduling tasks

Dynamic

Static (a priori)

In immediate mode, task is mapped onto machine as soon as it arrives at the mapper.

In batch mode, tasks are collected and examined and then mapped.

Expected execution time of a task a on machine j is the amount of time taken by j to execute t in j given j has no load when t is assigned to it.

It includes time to move the code or data to j.

Expected Completion Time is the wall clock time of task i on machine j after having finished any previously assigned tasks.

Ready time : the earliest time machine is going to be ready after completing the tasks currently assigned to it.

This is based on a combination of actual task execution times (for tasks that have completed) and

estimated expected task execution times (for tasks waiting to execute),

Reading these definitions feel like someone just defogged my windscreen.... clears up a lot of doubts... 

Immediate mode heuristics (only those i need to know)

Minimum completion Time (MCT) : assigns each task to the machine that results in the task's earliest Completion time.

As task arrives, all machines are examined to determine the machine that gives earliest completion time for the task.

so it takes O(m) time to map a given task.

Minimum execution Time (MET) : assigns each task to the machine that performs that task's computation in the least amount of execution time.

This does not consider machine ready times...

can cause severe unbalance in load among machines.

Adv : it gives each task to the machine that performs it in the least amount of execution time and heuristic is very simple.

Heuristic needs O(m) time to complete.

I'm lovin' the paper :D  all my doubts are being answered now :) :)  

kay so now i'm gonna try implementing MCT 'n MET in cloudsim...

I'll do MET first 'cos that's straightforward... 

Scheduling BoT's in cloudsim

From the LCG workload, i've taken 1000 tasks 'n created 10 BoT's with 100 tasks each... 

I've given submission times for the 10 BoT's as follows

Size of BoT	100		82000 MIPS
				Actual Makespan
BoT	Size Ratio	Submission Time	Ideal Makespan	{U,R}	{StoL,R}	{LtoS,R}
1	2	0.1	0.248	1.534	1.7808	1.5124
2	2	417.1	0.248	2.4052	1.60015	1.30361
3	3	952.1	0.2155	2.1625	1.63496	1.34319
4	1	1379.1	0.1576	0.76192	0.797307	0.652461
5	13	2020.1	0.5958	3.02415	2.156	1.3052
6	3	2991.1	0.1711	0.8095	0.8288	0.43392
7	5	3721.1	0.1676	0.7913	0.77075	0.3876
8	3	4034.1	0.0198	0.3212	0.31915	261
9	2	4295.1	0.052	0.4326	0.43328	0.3202
10	2	4899.1	0.2665	1.2816	1.0856	0.54276

These are the results I got... for 

{U,R} , Unordered, random

{StoL,R}, Small to Large, Random

{LtoS,R}, Large to Small, random

For some weird reason, makespan of Bot 8 for {LtoS,R} is 261 for no good reason whatsoever...

****** BoT 8

Submit Time : 4034.0

Number of tasks: 100

Size Ratio of BoT 8 = 3.0

***BOT Ordering 

LARGE TO SMALL

BOT 8

Submit Time: 4034.1

Max Execution Task: 700 & Time : 4295.1

Largest Task: 1631

Ideal Makespan : 0.019890243902439025

Actual Makespan : 261.00000000000045

I mean, the largest task itself is 1631 only.... i'm completely stumped :(

'n another thing... I've tried the same experiment with randomly allocated VM's and a constant mips of 1000... these are the observations I made from that

• Sorting LtoS, StoL is comparable
• the makespan is reduces as compared to {U,R}
• When size Ratio is more (i.e. no. of small task are more...) LtoS performs slightly better than StoL.
• When size Ratio is more, the unordered makespan is much more

Notes : The larger the size Ratio, the more number of smaller tasks there are....

These results were obtained from setting up the private cloud according to the experimental setup in 

Iqbal et al paper which i've slightly adapted and modified to fit into cloudsim spec.

The observations that I can make now are... (with the exception of BoT 8)

• Ordering tasks LtoS actually performs much better than StoL
• Ordering tasks StoL in some cases is produces larger makespan than {U,R}

But, isn't SJF the most optimal algorithm??? it's even proven to be optimal :(  so stumped rite now :( :(

I'll go check if the ordering is done correctly or not now...

So in my code the vm's are allocated in order from 1 to 10... so what is happening is all the largest tasks are getting assigned to VM #0 which has the largest processing capacity at 82,000 MIPS, whereas all the smaller jobs are getting allotted to VM's that are slowest... 26,000 Mips with 1 PE...

oh....... 

But why 261 for only BoT 8?

Something else i found was this... even though the BoT submission time was 4034 for BoT 8, in the cloudsim clock time,  cloudlets in BoT 8 are received only at 4295.1 which is the submit time of BoT 9... now how'd that happen?

4295.1: Broker: Cloudlet 769 received

4295.1: Broker: Cloudlet 779 received

4295.1: Broker: Cloudlet 789 received

4295.1: Broker: Cloudlet 799 received

4295.200230769231: Broker: Cloudlet 830 received

I can't figure out what was wrong... maybe there's something 'bout those tasks in that batch in the log itself... I took the next 100 tasks 'n it'z all good now...

So the results are kinda useless 'cos the mapping policy is not random... the largest/smallest task is getting allocated to the fastest VM... 

Now i'm gonna change this code...

  vmIndex = (vmIndex + 1) % getVmsCreatedList().size();

'n make it random...

 Random rn = new Random();

 int i = rn.nextInt(getVmsCreatedList().size());

vmIndex = i;

Hopefully, it should work now....

hmmmm....

nope... LtoS, R still produces smaller makespan as compared to StoL,R.... maybe the sooner the bigger tasks are in the system... because its in timesharing mode anywayz... maybe the overall makespan gets reduced...

Enough for today... i'll try with more number of BoT's 'n change the size of BoTs also...

Cloudsim: allocating vm's to hosts and running cloudlets with different start times

So I was trying to create my own broker policies....

Bind VM's to particular hosts

First up, i needed to manually allocate VM's to particular hosts so they have different MIPS.

This was done successfully.

I did an override on the allocateHostForVm(Vm vm) method.
Then I wrote some code like
 if(vmid == 0){
        Host host = this.getHostList().get(0);
        vm_allocated = this.allocateHostForVm(vm, host);      
}
if(vmid == 1){
        Host host = this.getHostList().get(1);
         vm_allocated = this.allocateHostForVm(vm, host);      
}
so on 'n so forth.... to allocate all the vm's to my hosts....
I needed to do this because I created VM's with different Mips 'n it was not getting allocated to the host that has that capacity...
<br /> VM #0 has been allocated to the host#0 datacenter #3(Datacenter_0) #<br /> VM #1 has been allocated to the host#1 datacenter #3(Datacenter_0) #<br /> VM #2 has been allocated to the host#2 datacenter #3(Datacenter_0) #<br /> VM #3 has been allocated to the host#3 datacenter #3(Datacenter_0) #<br /> VM #4 has been allocated to the host#3 datacenter #3(Datacenter_0) #<br /> VM #5 has been allocated to the host#4 datacenter #3(Datacenter_0) #<br /> VM #6 has been allocated to the host#4 datacenter #3(Datacenter_0) #<br /> VM #7 has been allocated to the host#5 datacenter #3(Datacenter_0) #<br /> VM #8 has been allocated to the host#5 datacenter #3(Datacenter_0) #<br /> VM #9 has been allocated to the host#6 datacenter #3(Datacenter_0) #<br /> 0.1: Broker: VM #0 has been created in Datacenter #3, Host #0<br /> 0.1: Broker: VM #1 has been created in Datacenter #3, Host #1<br /> 0.1: Broker: VM #2 has been created in Datacenter #3, Host #2<br /> 0.1: Broker: VM #3 has been created in Datacenter #3, Host #3<br /> 0.1: Broker: VM #4 has been created in Datacenter #3, Host #3<br /> 0.1: Broker: VM #5 has been created in Datacenter #3, Host #4<br /> 0.1: Broker: VM #6 has been created in Datacenter #3, Host #4<br /> 0.1: Broker: VM #7 has been created in Datacenter #3, Host #5<br /> 0.1: Broker: VM #8 has been created in Datacenter #3, Host #5<br /> 0.1: Broker: VM #9 has been created in Datacenter #3, Host #6<br />
Then for varying the submit time of the cloudlet I have extended the cloudlet to MyCloudlet and added a different submission time for the cloudlet.

super(cloudletId, cloudletLength, pesNumber, cloudletFileSize,
cloudletOutputSize, utilizationModelCpu, utilizationModelRam,
utilizationModelBw);
// TODO Auto-generated constructor stub
this.startTime = startTime;
                this.setStartTime(startTime);
                this.setSubmissionTime(startTime);
                Log.printLine("Start time cloudlet "+cloudletId+"startTime :"+this.getSubmissionTime());

There seems to be a problem....
For a long time, my cloudlets were getting submitted at the proper time... but now for no sane reason... the submission time of the cloudlets are how I set it... but then all the cloudlets start at time 0 or whenever the vm's get created!

Did some pokin' around, then found this.... After I've set submission time to user defined submission time... when I used getSubmissionTime(), I still get


Start time cloudlet 7startTime :0.0
Start time cloudlet 8startTime :0.0
Start time cloudlet 9startTime :0.0


When I changed this.setStarTime(startTime) to this.setStartTime(this.startTime)... The getStartTime() was giving the correct output... but submission time was still getting set to 0.

wow... so, I had to go back to my own notes to solve this...
I think when i made some other changes in the mydatacenterBroker code... I accidentally changed the submitcloudlets method also...
I'll put up the entire code with all the changes so this does not happen again!!!
Can't believe I was again stuck with this for this long :(

Simulated cloudlets with varying Submission Times

protected void submitCloudlets() {
                int vmIndex = 0;
                List<MyCloudlet> successfullySubmitted = new ArrayList<MyCloudlet>();
                for (Cloudlet cloudlet : getCloudletList()) {
                   
                    // typecast cloudlet to user defined mycloudlet
                    MyCloudlet myCloudlet = (MyCloudlet)cloudlet;
                        Vm vm;
                        // if user didn't bind this cloudlet and it has not been executed yet
                        if (myCloudlet.getVmId() == -1) {
                                vm = getVmsCreatedList().get(vmIndex);
                        } else { // submit to the specific vm
                                vm = VmList.getById(getVmsCreatedList(), myCloudlet.getVmId());
                                if (vm == null) { // vm was not created
                                        Log.printLine(CloudSim.clock() + ": " + getName() + ": Postponing execution of cloudlet "
                                                        + myCloudlet.getCloudletId() + ": bount VM not available");
                                        continue;
                                }
                        }

                        Log.printLine(CloudSim.clock() + ": " + getName() + ": Sending cloudlet "
                                        + myCloudlet.getCloudletId() + " to VM #" + vm.getId());
                        myCloudlet.setVmId(vm.getId());
                        send(getVmsToDatacentersMap().get(vm.getId()),myCloudlet.getStartTime(), CloudSimTags.CLOUDLET_SUBMIT, myCloudlet);
                       
                        //sendNow(getVmsToDatacentersMap().get(vm.getId()), CloudSimTags.CLOUDLET_SUBMIT, cloudlet);
                        cloudletsSubmitted++;
                        vmIndex = (vmIndex + 1) % getVmsCreatedList().size();
                        getCloudletSubmittedList().add(myCloudlet);
                        successfullySubmitted.add(myCloudlet);
                }

                // remove submitted cloudlets from waiting list
                getCloudletList().removeAll(successfullySubmitted);
        }

So basically, change all the cloudlet to mycloudlet which i typecasted from cloudlet...


'n we're back in business now :)

Reinforcement learning Agents

I thought I'll use agents to schedule in the hybrid cloud, since they have good autonomic behaviour and also capable of learning.

Notes from Stuart Russuel, Peter Norvig, "Artificial Intelligence : A modern apporach

Supervised learning

supervised learning methods are appropriate when a teacher is providing correct values or when the function's output represents a prediction about the future that can be checked by looking at the percepts in the next time step

How canagents can learn in much less generous environments, 
where the agent receives no examples,
and starts with no model of the environment and no utility function?

The agent should have some sort of feedback.  It can try some random moves, if it is closer to the solution it receives a reward / reinforcement

end state : terminal state in the state history sequence

The task of reinforcement learning is to use rewards to learn a successful agent function
reward can be provided by a precept
In complex domains, reinforcement learning is the only feasible way to train a
program to perform at high levels.

Basic working of Reinforcement learning

An agent in an environment gets percepts, maps some of them to positive or negative utilities, and  then has to decide what action to take.

• The environment can be accessible or inaccessible. 
• In an accessible environment, states can be identified with percepts
• Inaccessible environment, the agent must maintain some internal state to try to keep track of the environment.
• The agent can begin with knowledge of the environment and the effects of its actions; 
• or it will have to learn this model as well as utility information
• Rewards can be received only in terminal states, or in any state
• Rewards can be components of the actual utility that the agent is trying to maximize, or they can be hints as to the actual  utility.
• The agent can be a passive learner or an active learner.

2 basic designs

• agent learns a utility function on states, uses it to select actions that maximize the expected utility of their outcomes
• The agent learns an action-value function giving the expected utility of taking a given action in a given state. This is called Q-learning.

Utility function

An agent that learns utility functions must also have a model of the environment.  

It must know the basic rules

only then it can apply the utility function to the outcome states.

Action-value function

they do not know where their actions lead, they cannot look ahead.

it can compare their values directly without having to consider their outcomes.

An action-value function assigns an expected utility to taking a given action in a given state

Q(a,i) to denotes the value of doing action a in state i

Q-values are directly related to utility values

U(i) = max Q(a, i)

2 adv:

• they suffice for decision making without the use of a model
• they can be learned directly from reward feedback

Passive learning in a known environment

In passive learning, the environment generates state transitions and the agent perceives them
The object is to use the information about rewards to learn the expected utility U(i) associated with each nonterminal state i.
the utility of a sequence is the sum of the rewards accumulated in the states of the sequence, i.e. it is additive.

Back to cloudsim : BoT's

So this is the sequence:

• UA(user agent) on behalf of the user submits BoT's to BA(Broker Agent)
• BA calls a Sheduler Agent (SA) to schedule.
• SA then calls RA(Resource agent) representing VM's and allocates jobs (cloudlets)
• RA returns output to UA (bcos it's simulation... nothing is returned actually...)

Simulating BoT's (Bag-of-Tasks)

Size : 100 (Initially...)

No. of BoT's : 10

So 1000 cloudlets.... I'm just using the LCG log and i'm taking 1000 cloudlets 'n using break to stop reading more tasks from the log after 1000.

Next I wrote a class called BoT

Parameters

• no. of tasks
• submit time
• size of Instructions [NO_OF_TASKS]
• numPes [NO_OF_TASKS]
• sizeRatio

(there are other parameters such as ordering of tasks and the type of distribution which i've not included as of now...)

Methods

• BoT(int size) // constructor
• setSubmitTime(double s)
• double getSubmitTime()
• addTask(int, long, int)
• double calcSizeRatio()

After simulation, I've calculated the actual makespan of each Bot which is the largest finish time subtracted from the submission time and ideal makespan.

The ideal makespan is based on the concept that in theory, cloud computing has infinite computing resources... So, ideal makespan is the time taken for the largest task in a BoT to execute in the fastest machine available, I've given the formula as

max(sizeof task in BoTi) in million instructions / max (speed of resource j) in MIPS

These are the simulation results for the test run with the default time shared allocation policy in cloudsim:

Size of BoTs:	100		Speed of the Fastest VM :			1000 MIPS
BoT	Size Ratio	Submission Time	Max Finish Time	Ideal Makespan	Actual Makespan
1	2	19.6	76	20	57
2	2	436	496	20	59
3	3	971	1026	17	54
4	1	1398	1416	12	18
5	13	2039	2115	48	76
6	3	3010	3026	14	16
7	5	3740	3759	13	19
8	3	4053	4060	1	7
9	2	4314	4322	4	7
10	2	4918	4950	21	32

So now i've gotta implement my own scheduling algorithm for each BoT...

Software Agents

I thought I'd list down my major book sources, for software agents

Multiagent systems, Michael Wooldridge
http://coltech.vnu.edu.vn/httt/media/courses/AI++/Tai%20lieu/TLTK.pdf

And another book from where I learnt about
learning agents, reinforcement learning, policy algorithm, utility based and goal based agents,
the types of environments
accessible vs. non-accessible
deterministic vs. non-deterministic
static vs. dynamic
discrete vs. continuous
episodic vs. non-episodic

and other good concepts

Artificial Intelligence : A modern approach,
Stuart J. Russel, Peter Norvig
http://repo.hackerzvoice.net/depot_madchat/coding/ai/Artificial%20Intelligence%20-%20A%20Modern%20Approach.pdf

Bag of Tasks

I forgot where I read the characteristics of BoT workload...
so hard to keep track of what I read where...
RR · N
tasks, where N is the number of machines in the Grid (N = 185), and RR is a
numerical coefficient used to change the size of each bag.

The duration of each task is assumed to be a random variable uniformly distributed in the interval
[RT ∗0.5∗BaseTime,RT ∗1.5∗BaseTime] seconds, where BaseTime and RT are
workload parameters (note that the duration of tasks is referred to a machine
with computing power P = 1).

This is the characteristics as given by Sim Moon

I think I found the source of BoT's... my work for today is over...

On the efficacy, efficiency and emergent behavior of task replication in large distributed systems

Cirne et al

http://www.sciencedirect.com/science/article/pii/S016781910700004X