Exercise 1. The Bellman-Ford algorithm
Run the Bellman-Ford algorithm on the given graph above, indicating the steps in a table similar to the one in the slides (only for the destination node number 6).
Exercise 2. Statistical multiplexing
Consider a link with maximum capacity of C Mbps. Each user of this link is asking for 1 Mbps.
1. If we are not using statistical multiplexing, how many users can use this link before congestion appears? Call that number Nd (we use d for deterministic, meaning that service is ensured with probability 1). We define congestion as the event where the total capacity of the link is exceeded by the demand of the users.
2. We want to use statistical multiplexing to accommodate more users in the link. Users are idle 90% of the time: you can think of it as dividing the time in small periods, and each user asking for 1 Mbps in a slot with probability p = 10%, otherwise 0 Mbps. We set a threshold probability γ = 0.01. We are looking for the maximum number of users Ns in the system such that the probability that any time slot is congested is lower than γ. This γ is a crucial measure: γ = 0 indicates that the system is of perfect quality, but in many cases, users can function with a γ 0. Another way to interpret it is that when congestion occurs, packets are dropped, so γ is the packet loss probability. To model this situation, we use a binomial random variable X~𝐵(Ns, p) to model the number of active users in the system.
1
How should we pick Ns such that (𝑋 𝑁𝑑) < 𝛾 ? You can use different values of C to see how the Ns evolves (e.g., C = 10, 20, 30).
Hint: the binomial distribution has density function
𝑛 𝑘(1 − 𝑝)(𝑛−𝑘). 𝑃(𝑋 = 𝑘) = ( )𝑝
𝑘
So, the cumulative distribution function 𝑔(𝑘) = 𝑃(𝑋 ≤ 𝑘) is
𝑔(𝑘) =∑𝑘𝑖=0P(𝑋 = 𝑖)
What is ∑𝑁𝑖 then? You may need to use a numerical calculation to find Ns.
3. What happens if we double the capacity of the link and double the load, or the number of users (call it system 𝐴)? Compare to the situation where we have two independent links of capacity C, each receiving the original number of users (call it system 𝐵). Which of the two systems can fit the largest amount of users? Why?
Note that this is about resource pooling.
