Intro to Telecom Networks  Test 2

ECSE 416 – Intro to Telecom Networks 
Test 2
 Please scan your answers and submit the scanned
pages as a single pdf file. Alternatively, you can prepare answers in electronic
format and submit a single pdf.
3 questions, 60 marks
There are 3 questions. Marks allocated to each part are indicated in square brackets.
This exam is open book. You are permitted to consult any resources — textbook, web, notes.
But do not discuss the questions and solutions with your classmates. Do not ask anyone else to
help you solve the problems.
Question 1 [20 marks]
P4
P13
P12
P19
P23
P30
Figure 1: Distributed hash table for question 1. Solid circles represent peers, labelled by their
location. The table uses a 5-bit key space, so peers have addresses from 0 to 31.
The figure above illustrates the peers involved in a P2P network that is using the Chord distributed hash table for routing and key searches. The table uses a 5-bit key space. As a result all
distances are computed modulo 32 (we focused on 128 in lectures, but here there are at most 32
peers, numbered from 0 to 31).
Assume that there is no key copying currently implemented. This means that in its current
deployment keys are stored at only one peer, i.e., the peer responsible for each key is computed
using Chord’s mechanism for assigning keys to peers.
1
The labels next to the peers indicate their addresses in the key space, i.e. P4 has address 4.
Peer P12 departs from the network.
a) Which keys are irrevocably lost when peer P12 departs? [2 marks]
b) Write down all finger tables for all nodes prior to the departure of P12. [4 marks]
c) After the departure of P12, all peers remove the routing table (finger table) entries referencing
peer 12. Assume that no new routing table entries are added. A search fails if it does not
reach the correct peer corresponding to the searched key. Give an example of a search that
starts at peer 19 and fails. List all visited peers in order. [4 marks]
d) We say that an overlay network is routable if we can successfully search for all key addresses
from all peers in the network. Is the overlay network routable after the departure of P12?
Expain why or why not. [2 marks]
e) If it is not routable, what is the smallest number of changes that you need to make to the
routing tables at the peers to make the overlay network to make it routable? Specify the
change(s). [2 marks]
f) Suppose that peer P19 discovers that its successor link is no longer consistent, because peer
P23 has updated its predecessor link. What must have happened in order for this to occur?
[1 marks]
g) Before peer P12 has departed, what is the expected number of hops required for a query to
be resolved, if the query starts uniformly at random from one of the six peers and targets a
key that is selected uniformly at random from the range [0,31]? [5 marks]
2
Question 2 [20 marks]
D
A B
Flow 1 C
3
Flow 3
Flow 4
2.5
4.5
E
F
1.5
1
Flow 2
Flow 5
Figure 2: Network for question 2. Each link is labelled with its capacity in Mb/s.
a) For the network and flows in Figure 2 calculate the max-min fair flow allocations. Show all
steps in the procedure you use to calculate them. [5 marks]
b) For this network, is it possible to identify any allocation that has higher aggregate rate than
the max-min fair allocation. (The aggregate rate is the sum of all rates allocated to all flows).
Explain why or why not. [3 marks]
c) What is a proportionally fair flow allocation? [2 marks]
d) Is the allocation (1, 2, 1.75, 0.75, 1.5) proportionally fair? Show why or why not. [4 marks]
e) The fairness conditions and algorithms we have studied have assumed that each user (flow)
has infinite demand. Suppose that there is a finite demand vector d such that user r requests
a rate of dr. This means that the user should not be allocated a rate higher than dr. The
definition of max-min fairness is now similar, but it focuses only on users whose demand has
not been satisfied. A flow allocation x is max-min fair for a demand d if it is feasible and for
any other feasible flow allocation y, if there exists yr xr for xr < dr then there exists ys
such that ys < xs ≤ xr.
Specify an algorithm that will identify a max-min fair allocation when there is a demand
vector d. [4 marks]
f) If the demand vector d is [1, 3, 3, 0.9, 2], identify the max-min fair flow rate allocation for the
network and flows in Figure 2. [2 marks]
3
Question 3 [20 marks]
For a weight vector w = (wr, r ∈ R), where R is the set of user flows, with A the linkroute incidence matrix and c the corresponding vector of link capacities, the NETWORK(A, c, w)
problem is defined as:
maximize X
r∈R
wr log xr
subject to Ax ≤ c
over x ≥ 0
In the lectures, we proposed the following dynamic algorithm for setting rates
d
dtxr(t) = κr

wr − xr(t)
X
j∈J (r)
µj (t)

 , r ∈ R, (1)
µj (t) = pj


X
s:j∈J (s)
xs(t)

 , j ∈ J . (2)
Here J is the set of links in the network and J (r) are the links traversed by route r. The function
pj (·) is positive, continuous and increasing and κr is a scalar constant.
a) Why is the solution to the NETWORK problem unique? [2 marks]
b) Explain how the proposed dynamic algorithm works in performing congestion control and
rate allocation. [5 marks]
c) Explain how I can choose price functions so that the dynamic algorithm always converges
(to within an arbitrarily close approximation) to the solution of the NETWORK(A, c, w)
problem. [4 marks]
d) Explain why this choice is not a practical solution when we consider networks with time delay.
Provide a detailed explanation. [4 marks]
e) You have implemented a version of the dynamic algorithm above, but modified it so that it
takes into account the time delays in the network. You are now faced with the choice of the
gain κr for each route r. What aspects will affect your decision for this value? What is the
trade-off between choosing a large value and choosing a small value? [5 marks]
4