Time Limit: 20 Days Advisor Name
This quiz contains 5 pages (including this cover page) and 4 problems. Check to see if any pages
are missing. Enter all requested information on the top of this page, and put your initials on the
top of every page, in case the pages become separated.
Try to answer as many problems as you can. The following rules apply:
Write the report with LaTeX and output it as a
PDF le.
Programming with R language (Do NOT accept
other languages)
Submit your report (pdf le) and your program-
ming codes (R le) to the course email address
() before 9:00 am of January
25, 2018. Later homework receives No credit.
You are allowed to discuss with others and use any
references, but if you do so please list your collab-
orators and cite your references in your report.
Problem Points Score
Stochastic Processes Final Projects - Page 2 of 5 Deadline: Jan.25, 2018
1. (30 points) Simulation of M/M/1 queue. Suppose that the arrival rate is = 2jobs=min.
Adjust the service rate as needed to create the the following three kinds of tra c intensity
= = : = 0:4; 0:8; 1. Run your simulation under each scenario for a long time to measure
the mean and variance of the number of jobs in the system
the mean response time of jobs in the system
the mean queueing time of jobs in the system
Then compare your results with theoretic results on the above performance metrics. What is
more, check whether little’s law hold for all three scenarios.
Stochastic Processes Final Projects - Page 3 of 5 Deadline: Jan.25, 2018
2. (30 points) Load Balancing in Cloud Computing. We consider a Google data center
network with n identical servers and a central scheduler (role of load balancing). Each arrival
is a job consisting of many tasks, each of which can be executed in parallel in possibly di erent
servers. Each server can process one task at a time. Each job (batch of tasks) consists of m
tasks and the job arrival process is a Poisson process with rate nm . The scheduler dispatches
the tasks to the servers when a job arrives. The service times of the tasks are exponentially
distributed with mean 1, and are independent across tasks. When a task arrives at a server, it
is processed immediately if the server is idle or waits in a FIFO( rst-in- rst-out) queue if the
server is busy. Run your simulation to compare the following three load-balancing policies:
Random: when a batch of m tasks arrive, the scheduler picks one server uniformly at
random for each task and then dispatch the task to that server.
The-Power-of-d-choices: when a batch of m tasks arrive, the scheduler probes d servers
uniformly at random to acquire their queue lengths for each task. The task is routed to
the least loaded server.
Batch-Sampling: when a batch of m tasks arrive, the scheduler probes dm servers
uniformly at random to acquire their queue lengths. The m tasks are added to the the
least loaded m servers, one for each server.
We consider systems with n = 5000 servers, batch size m = 50. There are di erent probe ratios
d(1 d 5) and three possible values of = 0:4;0:7;0:9. Evaluate the average task response
time and average job response time for the three load-balancing policies.
(a) (10 points) Plot the simulation results using ggplot2 package.
(b) (10 points) Which load balancing policy is optimal? Please give an intuitive explanation.
(c) (5 points) Try your best to show the optimality of some load balancing policy in theory.
(d) (5 points) Please report any other interesting observations and provide corresponding in-
tuitive explanations.
Stochastic Processes Final Projects - Page 4 of 5 Deadline: Jan.25, 2018
3. (50 points) Markov Chain Monte Carlo for Wireless Networks. Given a wireless
network with 24 links and 0 1 interference model, i.e., any two links are either interfere with
each other or not. To describe the interference relationship between wireless links, we
introduce the con ict graph model. In such model, the vertex of the con ict graph represents
the wireless link. An edge between two vertices means corresponding two links interfere with
each other. The following Figure shows the corresponding con ict graph for 24-link wireless
network. You are required to nd the maximum independent set of the con ict graph, i.e.,
the largest set of wireless links that can simultaneously transmit without interferences.
Design the algorithm by MCMC method and evaluate your algorithm.
(a) (20 points) Show your MCMC Design with a discrete Markov chain. Use both theory and
simulation results to justify your algorithms.
(b) (10 points) Try to quantify the convergence time of your algorithm via the theory of
mixing time for the discrete time Markov chain.
(c) (20 points) Show your MCMC Design with a continuous Markov chain. Use both theory
and simulation results to justify your algorithms.
Stochastic Processes Final Projects - Page 5 of 5 Deadline: Jan.25, 2018
4. (50 points) Find the number of all possible graph colorings. G is a graph shown as
follows. We have a set of k colors. A k-coloring of the graph is an assignment of a color to
each node, such that two nodes joined by an edge cant be the same color. Counting the
number of all possible k-colorings via MCMC method.
(a) (20 points) When k = 4, show the best results of your algorithm and compare it to the
theory value 72.
(b) (10 points) When k = 5, show the best results of your algorithm and compare it to the
theory value 240.
(c) (20 points) Provide suggestions to improve the approximation accuracy of MCMC method.