89-850 Exercises and Solutions

89-850 Exercises - Network Calculus, DiffServ, IntServ and 802.11 Comment: I hope to provide solutions to most (but not these from [BT])
1. All problems from chapter 4 of [KMK]
2. Problems 8.4-8.12 of [KMK]
3. Exercises from [Boudec and Thiran]: 1.1-1.5, 1.12, 1.14, 1.17-19,
1.22,1.25,1.27, 1.30, 1.34, 1.36, 2.4
4. [wireless, 802.11, simple optimization] Help design a new wireless
network using the 802.11 MAC protocol. The hardware supports
transmission rate of 5Mbit/sec and maximal distance of 1KM from sender
to recipient. Assume independent bit errors: each bit flips with
probability 10-6.
a. Ignoring collisions and size of headers and ACK, compute optimal
packet length. Note: check and indicate if the use of RTS/CTS is
desirable or not.
b. Explain the expected impact of possible collisions on the
optimal packet length (no need to compute it analytically).
c. Assume that the time to process an in coming packet is 5 micro
seconds. What is a good choice of DIFS? Justify.
5. [wireless, 802.11] Write pseudo-code for 802.11 MAC sender and
receiver. The code should cover all the aspects we studied, including
RTS/CTS, except PCF.
6. [QoS, Tspec, simple analysis] Let a token bucket Tspec be defined by
bucket size of B bytes, token arrival rate of R bytes/second, and
maximum (peak) output rate of p bytes/second.
a. Derive a formula for the length S of the maximum-rate burst,
i.e. the longest sequence of bytes sent using the maximum (peak)
rate p.
b. Consider a router receiving packets from three inputs flows, all
conforming to the same Tspec with parameters as above, and all
going to the same destination. Assume that S is the maximal
packet length. and minimal packet length of 64 bytes. Compute
the token-bucket Tspec parameters for the output of the router,
for FIFO, GPS, and WFQ queuing?
7. [DiffServ] The AF PHB utilizes four classes and three drop precedence
levels, or a total of 12 differential services code points (DSCP's).
The EF PHB uses a single DSCP, 101110. Motivate this difference.
a. Explain why a single DSCP is sufficient for EF. Namely, show
that every EF-compliant scheduling mechanism using multiple
DSCP, can be replaced by using a single DSCP with same results.
Notice: you may (and should) make a reasonable assumption,
regarding the packet arrival process.
b. Demonstrate that a single DSCP does not suffice for AF.
8. [ECN/RED] Suggest how routers supporting RED should be extended to
support ECN and Diff Serv. Specifically:
a. The two last bits of the DS field are for ECN, specifically: an
`ECN capable` bit, which is `on` iff the sender supports ECN;
and an `ECN (congestion experienced)` bit, turned on (in `ECN
capable` packet) by ECN-capable routers, to warn of congestion.
What, if any, changes in the RED algorithm are desirable, to
support ECN? Explain.
b. The first 6 bits of the DS field are the DS codepoint,
identifying the PHB to be applied to the packet. What changes
are required, if we want to support EF PHB and `best effort`
PHB? (Ignore any other PHBs, e.g. AF PHB).
c. Extend the pseudo-code for RED presented in the lecture as you
explained in the previous parts of this question (to support ECN
and EF PHB). Present your extension by a marking your changes on
the code presented in class.
9. Consider the simple network in the figure below. Sources A,B,C may
need high-quality video flow to destination D, with maximal delay of
100msec, for video messages of (compressed) length up to 10Kbit, sent
once every 20msec (or more). Assume such messages can fit within a
single packet. All packets pass thru local routers RA, RB and RC,
which can enforce QoS policy, in particular block or mark packets (DS
field) as necessary. Then, these routers pass the packets to the
`outgoing router` R, which sends them to the destination router RD.
Ignore delays between sources A,B, C, respective routers RA , RB and
RC and router R, and between destination D and router RD. However, do
not ignore the inter-router link R-RD whose length is 2500km and
transmission rate is 1Mb/sec (each way, full duplex). Ignore the
overhead (headers etc.). Assume strict priorities: A > B > C. The
sources (A, B, C) do not communicate all the time, so we should
provide best possible service to the lower priority sources when
possible. Assume propagation speed of 250,000Km/sec.
a. The goal is to provide the best possible service to the lower
priority sources (B,C), as long as the service to higher
priority sources (A, B) are kept within the allowed parameters.
Router RA , RB and RC are allowed to regulate the traffic and
discard or mark packets. Show why WFQ cannot satisfy these
requirements.
b. Present a simple non-preemptive queuing algorithm for R,
satisfying the same requirements.
c. What is the (minimal) size of buffer required at router R and at
the destination, to satisfy the above goal and ensure continuous
play, using the algorithm you presented in (b)?
d. Can you satisfy EF PHB for any or all of the sources (which?)?
If so, what is the best per-packet error EP (for each source)?
e. Assume all three routers RA, RB and RC, enforce token-bucket on
the inputs, with the same Tspec parameters. Show that, with
appropriate [pic]
10. Consider a router using RED, which carries (only) TCP traffic. Assume
that the average number of bytes in the queue of the router converges
to N, the average output rate converges to ? (bytes/sec), and the
average delay converges to T.
a. Explain why you cannot simply apply Little's theorem (as stated
in class).
b. Prove or disprove: N= ? T [or: N( ? T, N? ? T].
11. Consider the enclosed state-transition diagram for a (simple, discrete-
value) Discrete-Time Markov Chain.
a. Present transition probabilities Pij s.t. the chain is periodic
(prove).
b. Present transition probabilities Pij s.t. the chain is a-
periodic (prove).
c. Express the stationary probability ?j=(i ?iPij as a function of
P10. In particular compute for P10={0,0.5,1}.
12. Consider the two leaky-bucket shapers in tandem, with parameters (?1 ,
?1) and (?1 , ?1).
a. Obtain the overall envelope.
b. Suppose A(t) has envelope E(t). What is the envelope of D2(t)?
13. Consider a router with one output port, rate C, that handles two
flows: one `best-effort` flow and one Expedited Forwarding PHB flow
with traffic spec (? , ?), i.e. arrivals enveloped by ?+?t. Can you
bound the (best) competitive ration for the et departures process (for
both flows), denoted D(t) ?
1.
-----------------------
0 2 1