Home Assignments

Reading assignments are for lectures 2,4,6,8,10,12. On these lectures we write short tests, which also include the material of the papers to read.

Home assignments have to be submitted on lectures 5 (sets 1 and 2), 9 (sets 3 and 4),12 (sets 5 and 6). Home assignment are added to this page during course time.

Home assignment solutions

Home assignments solutions are removed.

Set 1 - Traffic models (finalized)

1. You would like to model the traffic in a WLAN, which is used for file transmissions and for voice and video streaming applications as well. The number of users connected to the WLAN changes dynamically, and each user can initiate several voice, video or file transfer sessions. Characterize the WLAN traffic on flow and packet level.

2. Consider a link where ON-OFF traffic sources are multiplexed. The link transmission capacity is C bits/s, there are n sources sharing the link, the average per source bitrate is C/n, the peak rate (the source rate in the ON state) is R. There is no buffer at the link, so if the aggregate rate is higher than C, packets are dropped.

a) Use a two-state markov modulated fluid model to characterize a source.
Give the state transition rates as a function of C, n and R.

b) Define the state of the system by the number of sources in ON state, alternatively by the aggregate bitrate. Give the state transition rates as a function of C, n and R.

3. For the above system give the probability that an arbitrary point of time the aggregate source rate is higher than C. How does this probability depend on the ratio of R and C/n?

4. Compare the Exponential and the Pareto distribution. Consider distributions with the same mean value and plot the tail function for the related Exponential distribution and for Pareto distributions with different shape parameter a. How does the shape parameter affect the tail distribution?

Set 2 - Medium access control (finalized)

1. Consider an FDMA system with M users. The packet size is P, the link rate is R. (Same notation as on the slides). All users generate packets with the same intensity, according to a Poisson process. One of the users, however, should be able to transmit with low delay, and therefore gets a band with twice the bitrate of the others. Give the average delay of the normal users and of the "low delay" user. Evaluate the result.

2. Now consider the same scenario, but now the M users are served with a TDMA scheme. The slot length is equal to the packet transmission time. The "low delay" user can use two timeslots in a frame. For simplicity assume, that M is an odd number and the "low delay" user gets a slot in each half frame time. Again, give the average delay of the normal users and of the "low delay" user and evaluate the result.

3. Express the maximum throughput S(max), and the related offered load G of slotted nonpersistent CDMA as a function of the normalized propagation delay "a". Show the results on a graph with "a" on the x-axes. What happens as "a" increases? Why?

4. Consider slotted, nonpersistent CSMA/CD. Consider: g=1, T=1, tau=0.01 and assume that collision is detected in 2 minislot time. Calculate:
- the average length of the idle period,
- the average number of transmission periods in a busy period,
- the probability that a transmission in a busy period is successful,
- the average length of the busy period
- the average length of useful transmission in a busy period
- the ratio of time when the shared medium is idle
- and finally, the throughput.

Set 3: Congestion, flow and error control (finalized)

1. Consider an additive increase (parameter: "b") multiplicative decrease (parameter: "a") congestion control solution, with "b"=1 and "a"=0.25.
Express the throughput as a function of the loss probability and the round-trip time, following the derivation from the lecture.

2. Considering the congestion control scheme in the previous problem:
a) How does the throughput change as a function of "a"?
b) In a real life system what could happen if "a" is too high?

3. Consider a Leaky bucket (LB) rate control. Show time diagrams of permit arrivals, packet arrivals to the LB and packet departures from the LB for the following cases. Select the time of packet arrivals yourself.
a) Peak rate control, the peak rate is one packet per two time units.
b) Average rate control, the average rate is one packet per three time units.
c) Two LBs are connected, both peak rate and average rate is controlled.

4. Consider go-back-N error control.
a) Derive the probability that a block of N packets have to be retransmitted, as a function of N and the packet loss probability p.
b) Plot the throughput as a function of the packet loss probability for N=5,10,20. Use parameters rtt=1, packet transmission time=timeout=0.02.
Explain the throughput characteristics.

Set 4: Scheduling, mobility - finalized

1. Max-min fairness
a) Explain briefly what is the relationship between fair rate allocation on a link and scheduling.
b) Give the max-min fair rates, if there are 5 backlogged flows, the link capacity is 30Mbit/s, and:
- none of the flows have maximum rate requirement and the wights are equal;
- none of the flows have maximum rate requirement, one of the flows has weight 2, the others weight 1;
- all weights are equal, the maximum rate requirements of the flows are r(1)=4Mbit/s, r(2)=5Mbit/s, r(3)=6Mbit/s, r(4)=r(5)=8Mbit/s.

2. GPS and PGPS
a) In the Parekh-Gallager paper what is Fp, S(tau,t) and Q(tau,t)?
b) Give the packet finishing times under GPS and under PGPS for the following cases. Draw figures that show the remaining traffic to be transmitted as a function of time. Notation: L: packet size, T: time when the packet arrives to the buffer.
- L(1)=2, T(1)=0, L(2)=1, T(2)=0;
- L(1)=2, T(1)=0, L(2)=1, T(2)=1.

3. Based on the Hui Zhang paper, explain the difference between WFQ and WF2Q. What is the problem of WFQ that WF2Q solves?

4. Mobility.
Consider the mobile phones in Stockholm and their mobility patterns. Describe what is micro-, meso- and macroscopic mobility in this case. For each of them give the typical distances and time-scales that matter. Also, explain how mobility on these three levels affects the network performance. You can find Prof. Karlsson's slides among the lecture slides.

Set 5: Fairness - finalized

1. Max-min fairness
Define an arbitrary network and a set of flows (you can consider the one used on the lecture). Show, that the rate of some flows may decrease when one of the flows leaves the network and the rates are re-allocated. Show even the opposite: when a new flow arrives to the network, and the rates are re-allocated, some of the old flows may receive higher rate.

2. Max-min and proportional fairness. Consider the parking-lot (also called as linear network) scenario with 2 links. Derive the max-min and the proportional fair rates. Calculate and compare the network throughput for the two cases. Prove that the proportional fair rates are not max-min fair.

3. Fairness, scheduling and rate control: Explain the connection between fairness, scheduling and rate control. Give examples.

4. Consider an ideal WLAN. The shared transmission capacity is 10Mbit/s, which can be fully utilized (collisions are fully avoided, and all data is transmitted without error). The MAC provides perfect max-min fair capacity allocation for simultaneous transmission requests.
Users would like to transmit files across the WLAN. The file transmission requests arrive according to a Poisson process with 1 request per second in average, file lengths have exponential distribution with a mean of 500kByte. Due to the ideal MAC, the transmission of the files happens simultaneously, and can therefore be modeled with a processor sharing queue. That is, if there are for example 4 files under transmission , each of them receives 2.5Mbit/s transmission rate. If then the transmission of a fifth file is requested, all files is transmitted with 2Mbit/s transmission rate. Give the Markov chain of the system and calculate the mean file transmission time.

Set 6: Multimedia - finalized

Only two problems, since time is very short.

1.
a) Consider a playout buffer that playes out frames with constant frame duration T. Assume that the frame arrival process is Poisson, with intensity lambda. There are n frames in the playout buffer. What is the probability of buffer starvation after the playout of these n frames, that is, the probability that no new frame arrives during the playout of the n frames in the buffer?
b) Cosnider the paper of Laoutaris and Stavrakakis. How does the proposed solution decrease the probability of starvation?

2. Conisder media dependent FEC.
a) Assuming Bernoulli loss model, with parameter p, express the probability that:
- both the original and the copy is lost, considering distances n=1,2,…
- the original and all copies are lost, if the original is repeated k-1 times.
Give the above probabilities for p=0.5.
b) Now consider a Gilbert loss model, with P(01)=P(10)=0.1.
- Calculate the packet loss probability.
- Still considering media dependent FEC with n=1 and k=2, give the probability that both the original packet and the copy gets lost.
- Based on your results, how does the burtiness of the loss process affect the efficiency of media dependent FEC?