-----------------------
Compute Nash Equilibria: gameExample.txt
-----------------------
S vs S
-----------
Machine 1 : 1 1 4 6
Machine 2 : 1 2 5 10
-----------
S vs L
-----------
Machine 1 : 1 11 2 4 5
Machine 2 : 10 6
-----------
L vs S
-----------
Machine 1 : 10 6
Machine 2 : 1 11 2 4 5
-----------
L vs L
-----------
Machine 1 : 10 4 1
Machine 2 : 6 5 2 1 1
-----------
(S) (L)
(S) (12,18) (14,16)
(L) (16,14) (15,15)
---------------------------
Pure Nash Equilibria = { (L,L) }
%%%%%%%%%%%%%% INPUT FROM TEXT FILE TO MATLAB %%%%%%%%%%%%%%%%
Assume you have a filed named requestStream.txt located on your working directory.
Where the requestStream.txt contents are: 10 6 4 3 3 2 1
From the MATLAB command window:
>>someVarArray = textread('requestStream.txt')
someVarArray =
10 6 4 3 3 2 1
%%%%%%%%%%%%%% INPUT FROM TEXT FILE TO MATLAB %%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% OUTPUT TO TEXT %%%%%%%%%%%%%%%%
fileID = fopen('outputExample.txt','w');
fori = 1:length(someVarArray)
fprintf(fileID,'%i\n', someVarArray(i));
end
fclose(fileID);
end
%%%%%%%%%%%%%% OUTPUT TO TEXT %%%%%%%%%%%%%%%%
Wayne State University, BE1500 Fall 2014
Introduction to Programming and
Computation for Engineers
Project One (P1): Balancing Machine Resource Economies in Competitive Cloud Environments.
1 Objectives
(a) Simulate a competitive cloud computing environment in MATLAB©.
(b) Understand the elementary pure Nash Equilibrium model.
(c) Take your coding up a notch!
1
2 Project One (P1): Due November 8th 2014
2.1 Introduction
Cloud computing service markets are highly competitive. Service Providers such as Amazon Web Services, Microsoft Azure, and Google Cloud all compete against each other to provide services to the general public such as storage, accessing, computing, streaming, etc. Each of these Providers have an arsenal of machines ready to compute processes for Clients who request services, e.g., requesting access to a saved document, storing a database, downloading an MP3 �le, executing Microsoft Word 360, �nding the best Indian food in town or seeing who is at the Fillmore tonight through a mobile device. At any interval of time, there are thousands of Clients online that want to perform a process and a Provider has to accommodate them. Let's look at a simple sequence of execution simulating how this works for a single Provider, e.g., Amazon Web Services.
Balancing Economic Machines in Cloud Competitive Environments
Cloud computing service markets are highly competitive. Service providers such as Amazon
Web Services, Microsoft Azure, and Google Cloud all compete against each other to provide services to
the general public such as storage, computing, streaming, etc. Each of these providers have an army of
machines ready to accept work from Clients who request services i.e., requesting access to a saved
document, downloading an mp3 file, executing Microsoft Word 360, finding the best Indian food in town,
see who is at the Fillmore tonight, etc. At any interval of time, there are thousands of Clients online that
want “something” and a Provider has to accommodate them. Let’s look at a simple sequence of how this
works for a single Provider i.e., Amazon Web Services.
STEP 1: The interacting agents are Amazon, the Clients, and the Amazon machines.
STEP 2: Clients submit requests to an Amazon centralized system.
STEP 3: Amazon’s centralized system distributes the requests to machines in its arsenal.
Figure 2.1: Amazon Web Service Provider, Clients and Amazon Web Service machines.
Balancing Economic Machines in Cloud Competitive Environments
Cloud computing service markets are highly competitive. Service providers such as Amazon
Web Services, Microsoft Azure, and Google Cloud all compete against each other to provide services to
the general public such as storage, computing, streaming, etc. Each of these providers have an army of
machines ready to accept work from Clients who request services i.e., requesting access to a saved
document, downloading an mp3 file, executing Microsoft Word 360, finding the best Indian food in town,
see who is at the Fillmore tonight, etc. At any interval of time, there are thousands of Clients online that
want “something” and a Provider has to accommodate them. Let’s look at a simple sequence of how this
works for a single Provider i.e., Amazon Web Services.
STEP 1: The interacting agents are Amazon, the Clients, and the Amazon machines.
STEP 2: Clients submit requests to an Amazon centralized system.
STEP 3: Amazon’s centralized system distributes the requests to machines in its arsenal.
Figure 2.2: Clients submit tasks to the Amazon Web Service Provider.
2
Balancing Economic Machines in Cloud Competitive Environments
Cloud computing service markets are highly competitive. Service providers such as Amazon
Web Services, Microsoft Azure, and Google Cloud all compete against each other to provide services to
the general public such as storage, computing, streaming, etc. Each of these providers have an army of
machines ready to accept work from Clients who request services i.e., requesting access to a saved
document, downloading an mp3 file, executing Microsoft Word 360, finding the best Indian food in town,
see who is at the Fillmore tonight, etc. At any interval of time, there are thousands of Clients online that
want “something” and a Provider has to accommodate them. Let’s look at a simple sequence of how this
works for a single Provider i.e., Amazon Web Services.
STEP 1: The interacting agents are Amazon, the Clients, and the Amazon machines.
STEP 2: Clients submit requests to an Amazon centralized system.
STEP 3: Amazon’s centralized system distributes the requests to machines in its arsenal.
Figure 2.3: Amazon Web Service distributes the tasks to it's arsenal of machines.
In Figure 2.3, Amazon Web Services must determine the best distribution of tasks to each of it's machines. Each machine will determine it's own strategy for accepting tasks but since they are cooperating; they have to choose the strategy that is a best response to the choices of all the other machines. For our project, the best distribution provides Amazon Web Services the ability to minimize the processing time for all requested tasks where each machine attempts to maximize it's revenue since payment for services is dependent on processing time, i.e., more processing, more revenue. Moreover, we will equate unit pro�t to unit processing time. In the real world, the streams of task processing requests are in real-time and arrive to the Provider near continuously. In our model, we will create only a single, �nite stream of task processing requests called the Request Stream. Below is a Request Stream with 8 tasks where the values of each task represents it's processing time in milliseconds.
Task Processing Time (ms) T1 1 T2 1 T3 1 T4 2 T5 4 T6 5 T7 6 T8 10
The strategic choices Amazon Web Service machines make are to encode themselves with a policy to process tasks from the Request Stream. Examples of very simple poli- cies we are going to use are identi�ed by S (shortest job �rst) & L (largest job �rst). If a machine has policy S encoded onto it, then that machine will be responsible to process the next available task of minimum time. On the other hand, if a machine has policy L encoded onto it, then that machine will be responsible to process the next available task of maximum time. Therefore, all machines are encoded with policies us- ing pseudo-intelligent decision making by playing a game with each other to minimize overall processing time and simultaneously attempt to maximize machine level revenues.
3
For our model, let's assume Amazon Web Services has two identical machines (meaning they have the same disk space, processing power, etc.), where each machine can encode itself a single policy. Let's name our machines M1 & M2, respectively. The objective is to balance the distribution of tasks from the Request Stream so that each machine keeps accepting tasks until that machine's load is equal to or greater than the other machine's load. Note the selection process is not a turn-by-turn process where each machine is given every other task to process. Rather, M1 accepts one task determined by its policy. Then, M2 accepts one task with regard to its policy. If the load on M2 is less than M1, then M2 accepts the next task in accordance to it's policy. Else, the load on M2 is greater than or equal to M1, then M1 accepts the next task in accordance to it's policy. This process continues until all tasks in the Request Stream have been processed; where, upon completion, they are sent back to the Client in-sync.
If the policies chosen by Amazon Web Service machines can be represented as a 2-tuple, (M1's policy, M2's policy), then every possible machine processing time combination can be computed for the given Request Stream. We will go through the process of distributing the tasks to machines for all possible 2-tuple policy combinations with the Request Stream visually.
Evolutionary Stability - Example
G[2,8](M,J,Π)
Job Stream: 1 1 1 2 4 5 6 10
SS: 1 1 1 2 4 5 6 10 SL: 1 1 1 2 4 5 6 10 LS: 1 1 1 2 4 5 6 10 LL: 1 1 1 2 4 5 6 10
20 / 39
Figure 2.4: Initialization
4
Evolutionary Stability - Example
G[2,8](M,J,Π)
Job Stream: 1 1 1 2 4 5 6 10
SS: 1 1 2 4 5 6 10 SL: 1 1 2 4 5 6 10 LS: 1 1 1 2 4 5 6 LL: 1 1 1 2 4 5 6
21 / 39
Figure 2.5: Iteration 1
5
Evolutionary Stability - Example
G[2,8](M,J,Π)
Job Stream: 1 1 1 2 4 5 6 10
SS: 1 2 4 5 6 10 SL: 1 1 2 4 5 6 LS: 1 1 2 4 5 6 LL: 1 1 1 2 4 5
22 / 39
Figure 2.6: Iteration 2
6
Evolutionary Stability - Example
G[2,8](M,J,Π)
Job Stream: 1 1 1 2 4 5 6 10
SS: 2 4 5 6 10 SL: 1 2 4 5 6 LS: 1 2 4 5 6 LL: 1 1 1 2 4
23 / 39
Figure 2.7: Iteration 3
7
Evolutionary Stability - Example
G[2,8](M,J,Π)
Job Stream: 1 1 1 2 4 5 6 10
SS: 4 5 6 10 SL: 2 4 5 6 LS: 2 4 5 6 LL: 1 1 1 2
24 / 39Figure 2.8: Iteration 4
8
Evolutionary Stability - Example
G[2,8](M,J,Π)
Job Stream: 1 1 1 2 4 5 6 10
SS: 5 6 10 SL: 4 5 6 LS: 4 5 6 LL: 1 1 1
25 / 39Figure 2.9: Iteration 5
9
Evolutionary Stability - Example
G[2,8](M,J,Π)
Job Stream: 1 1 1 2 4 5 6 10
SS: 6 10 SL: 5 6 LS: 5 6 LL: 1 1
26 / 39Figure 2.10: Iteration 6
10
Figure 2.11: Iteration 7
11
Evolutionary Stability - Solution
(L,L)∈ ∆NE in G[2,8](M,J,Π)
L∈ ∆ESS in G[2,8](M,J,Π)
28 / 39Figure 2.12: Final Iteration
For each of the 2-tuple policy combinations, the sum total of the tasks per machine represents the amount of time it spends processing. The less time spent on all the machines in total, the more satis�ed the Clients are with Amazon Web Services. The total processing times for this Request Stream are as follows:
M2 S L
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− S | (S, S) (L, S)
| −−−−−−−−−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−−−−−−− | M1 chooses policy S: 12 M1 chooses policy L: 14 | M2 chooses policy S: 18 M2 chooses policy S: 16 | −−−−−−−−−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−−−−−−−
M1 | |
L | (S, L) (L, L) | −−−−−−−−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−−−−−−− | M1 chooses policy S: 16 M1 chooses policy L: 15 | M2 chooses policy L: 14 M2 chooses policy L: 15 | −−−−−−−−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−−−−−−−
By reducing the details, the game takes the following form:
12
M2 S L
−−−−−−−−−−−−−−−−−−−−−−−−−−− S | (12, 18) (14, 16)
M1 | L | (16, 14) (15, 15)
Recall machine level policy selection is not strictly dependent on the choice of the ma- chine but takes in consideration the policy choices of the other machine's best responses. Therefore, a decision making sequence must ensue.
The decision sequence for choosing the best policy for M1 considering M2:
1. Processing time for M1 choosing S, when M2 chooses S, (S, S): 12
2. Processing time for M1 choosing L, when M2 chooses S, (L, S): 16
3. Processing time for M1 choosing S, when M2 chooses L, (S, L): 14
4. Processing time for M1 choosing L, when M2 chooses L, (L, L): 15
If M2 chooses policy S, M1 should choose policy L to maximize machine level process- ing. If M2 chooses policy L, M1 should choose policy L to maximize machine level processing. In either case, M1 will choose policy L. Let's see what M2 would do de- pendent on M1:
The decision sequence for choosing the best policy for M2 considering M1:
1. Processing time for M2 choosing S, when M1 chooses S, (S, S): 18
2. Processing time for M2 choosing L, when M1 chooses S, (L, S): 16
3. Processing time for M2 choosing S, when M1 chooses L, (S, L): 14
4. Processing time for M2 choosing L, when M1 chooses L, (L, L): 15
If M1 chooses policy S, M2 should choose policy S to maximize machine level process- ing. If M1 chooses policy L, M2 should choose policy L to maximize machine level processing. Since M1 will choose policy L, this constrains M2 to choose L for machine level maximum processing (revenue) but minimum request stream processing (time).
This exercise is an example of a very simple game-theoretic model to compute pure Nash Equilibrium. The pure Nash Equilibrium, e.g., (L, L), from the example is the so- lution which represents the best combination of policy choices given both machines have the same objective on this unique Request Stream, i.e., minimize the request stream pro- cessing time for the Clients and maximize machine-level revenue for the Provider. When the Request Stream is small, within a �nite interval of time, the number of machines used are few, and there is only one Provider the problem is easy to solve. When the problem gets large in all dimensions, then a more complex model needs to be developed to compute Nash Equilibrium using this framework. Let's increase the complexity a touch by working with a larger Request Stream. . .
13
2.2 What's Requested of You. . .
Find the pure Nash Equilibria for the described model with the following parameters:
1. Only assume one Provider.
2. The Provider has two machines.
3. Each machine encodes itself with either an S or an L policy as described in this document.
4. The machines accept a Request Stream exactly like M1 & M2 as described in this document.
On Blackboard, in the Project 1 folder, there is a link (Request Streams) to three di�erent Request Streams. Compute the pure Nash Equilibrium for each of those request streams. My suggestion is to try to replicate the process with the Request Stream in this document before attempting the larger Request Streams. When constructing your function, start with the following framework:
function computeNashEquilibria(gameX)
Then, the execution could mimic:
>> gameX = 'stringRequestStreamGameX.txt'; >> computeNashEquilibria(gameX)
Your code should output the distribution of tasks per machine per policy combination, output the totals, and intelligently chooses which combination of policies will be the pure Nash Equilibrium. Develop a method for making the comparisons and modeling the decision making process described in this document. On Blackboard, in the Project 1 folder, there is a link (Solution Output Example) for an example for how the output should look. Follow the presentation therein or make it better. Use MATLAB©'s input and output protocols to upload a Request Stream and output the contents of your results to a text �le. Your solution should be in the form of a package with the usual naming convention and the following contents:
1. A README.txt �le describing the contents of your solution package.
2. A copy of this document.
3. The MATLAB© .m �les used for computing the Nash Equilibria.
4. All three Request Streams stored as separate text �les.
5. Solution output for each of the Request Streams as a text �le; name your solution output �le accordingly.
6. A Final_Report (.pdf) with a cover page and all Execution, Output and Code inserted to complete this project.
14
- Objectives
- Project One (P1): Due November 8th 2014
- Introduction
- What's Requested of You…