King¡¯s College London
UNIVERSITY OF LONDON
This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
MSc EXAMINATION
7CCSMNTH Network Theory
Period 2 (May/June 2015)
TIME ALLOWED: THREE HOURS
ANSWER ALL FOUR QUESTIONS
ANSWER EACH QUESTION IN A SEPARATE ANSWER BOOK
AND WRITE ITS NUMBER ON THE COVER.
CALCULATORS MAY BE USED. THE FOLLOWING MODELS ARE PERMITTED:
Casio fx83
Casio fx85.
DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
TURN OVER WHEN INSTRUCTED 2015 ý King¡¯s College London
7CCSMNTH
1. Question one
a) Figure 1 shows network topology between different departments at
KCL. The capacities of the Ethernet links between pairs of departments are shown in the figure (in Mbps).
i. What is the maximum data rate we can transmit from department S to department T?
ii. How should we route this data from S to T? Explain your calculation in details.
46
6
5
Figure 1. Network topology of question 1.a.
[12 marks]
b) Consider the following generalisation of the max flow problem.
You are given a directed network G = (V, E) with edge capacities {ce}. Instead of a single (s, t) pair, you are given multiple pairs (s1, t1), (s2, t2)… (sk, tk), where the si are sources of G and the ti are destinations of G. You are also given k demands d1, …, dk. The goal is to find k flows f(1), …, f(k) with the following properties:
– f(i) is a valid flow from si to ti
– For each edge e, the total flow fe(1) + fe(2) + … + fe(k) doesn¡¯t exceed
the capacity ce.
– The size of each flow f(i) is at least the demand di.
– The size of the total flow (the sum of the flows) is as large as
possible.
i. Explain whether you can reduce this problem to a simple
max flow problem.
ii. How would you solve this problem?
2
[13 marks]
[Total 25 marks]
2.
a)
b)
c)
Question two
Consider an M/M/1 system with parameters ¦Ë and ¦Ì in which exactly 4 customers arrive at each arrival instant.
i. Draw the state-transition-rate diagram
ii. By inspection, write down the equilibrium equations for
p(k), for k=0, 1, 2 ….
[8 marks]
Suppose that whether or not a web server is in a fully operational mode
at a specific day N depends on previous conditions of the server through the last two days only, i.e., days N-1, and N-2. Show how the performance of this web server can be analysed using a Markov chain. How many states are needed for the Markov chain?
[4 marks] Consider a two-node Markovian queueing network (of the more general
type considered by Jackson) for which N=2, m1 = m2=1 (single server queues), ¦Ìki = ¦Ìi (constant service rate), and which has transition probabilities (rij) as described in the following matrix:
See Next Page
7CCSMNTH
i¡ý j¡ú
0
1
2
3
0
0
1
0
0
1
0
0
1-¦Á
¦Á
2
0
1
0
0
Table 1: transition probabilities (rij )
Where 0 < ¦Á < 1 and node 0 and N+1 are the ¡°source¡± and ¡°¡±sink nodes,
respectively. We also have (for some integer K)
And assume the system initially contains K customers.
i) Since N=2, let us denote p(k1, k2) = p(k1, K-k1) by p(k1). Find the balance equations for p(k1).
ii) Solve these equations for p(k1) explicitly.
[8 marks] [5 marks]
3
3.
a)
[Total 25 marks] See Next Page
7CCSMNTH
Question three
An Internet service provider wants to choose among 10 future
customers (each perhaps a large company). Each of these new customers has a certain bandwidth requirements that are listed in the vector B:
B = [100, 250, 300, 70, 80, 150, 350, 60, 200, 50]
The service provider has the total capacity of 1GB, and the profit, p(k), they receive from selling service to each customer k, per MB of bandwidth is based on the below function:
p(k) = 0.2*B (k) +1/B(k)
Clearly this service provider is looking to maximise their profit.
i. Formulate the service provider¡¯s decision into a knapsack
problem and explain how you will solve it.
[8 marks]
ii. Model the problem with the genetic algorithm, and continue for
five iterations (use binary codes for representing the population). [8 marks]
b)
Consider the function f(x1, x2 ) as:
This function has its optimal solution at x* =(x*1, x*2).
i. Explain how Newton¡¯s algorithm can find the optimal value of f.
ii. Run two iterations (for example the first and second iterates) of the Newton¡¯s algorithm, and compute dk (the descending direction at iteration k).
[9 marks]
[Total 25 marks]
4
.
4.
a)
See Next Page
7CCSMNTH
Question four
Consider the social network in Figure 2, and assume nodes 7 and 10 have decided to follow a different behavior from the rest of their network (e.g. wearing red shoes). Other nodes in the network will adopt this behavior if at least 40% of their connections have already adopted (that is a threshold of q=2/5).
i. Explain how this behavior cascade through the social network. Clearly show all the steps.
[6 marks]
ii. What is the maximum value of q at which this behavior can
b) c)
Draw simple, connected graphs with degree sequences of (5;4;4;3;3;2;1) and (7;6;5;5;4;3;2).
[4 marks]
IntheErdos-RenyirandomgraphofG(n,p),
i. Explain how clustering coefficient of C is calculated.
[6 marks]
ii. What property of network is captured by the clustering
become epidemic in the network.
coefficient?
Figure 2: Social network of question 4.a.
5
[5 marks]
[4 marks]
[Total 25 marks] Final Page