Hello world!

Welcome to your new Blog.nus site. This is your first post. Edit or delete it, then start blogging!

Please remember to the Terms of Service:
1. Please use the blog for academic, educational, research and administrative purposes only.
2. Please adhere to Singapore laws and the NUS Acceptable Use Policy for IT Resources: http://www.nus.edu.sg/comcen/security/aup/
3. The Centre for Instructional Technology and National University of Singapore are not liable for any legal or financial issues which may arise as a result of your use of Blog.nus.

Also, a few disclaimers:
1. Content on Blog.nus and all blogs hosted on Blog.nus contain opinions which may not represent the official views of the National University of Singapore.
2. The Centre for Instructional Technology and the National University of Singapore are not responsible for the content of external internet sites.

We hope you enjoy your new blog.

Assignment 3: Grades and Comments

Here are your grades for Assignment 3. You may pick up the assignment from me from my office.

More than half of the class got a grade in the A range (A– to A+). These are students that provide detailed analysis of the traces (e.g., values of b, maximum window sizes, careful sampling of RTT, etc.) and its relation to the TCP equation (e.g., realizing the difference between goodput vs. throughput, packet loss rate vs. loss event rate, sender’s perceived losses vs. actual losses, behaviour of TCP vs. “textbook” Reno, etc.).

If you have questions about your grades, please contact me before end of Monday, 7 December 2009.
Continue reading

Clarifications for Lecture 9 and Lecture 10

Some questions from a discussion in my office this morning.

1. Can you give an example of redundant retransmissions caused by coarse feedback?

During class I explained what coarse feedback means but never gave a real example on how this could lead to redundant retransmissions. Vern Paxson gave a real example in his thesis (Page 317-318, ftp://ftp.ee.lbl.gov/papers/vp-thesis/dis.pdf). I could not explain any better than Vern Paxson so let me just refer you to the thesis for the example.

2. To pessimistically estimate the loss rate on an alternative path consists of default paths with loss rate of p1, p2, .. pk, can we really sum up the loss rate (Slide 64, Lecture 10)??

I stand corrected. We assume that loss rate on the paths are independent. Thus, the loss rate on the alternative path, i.e., probability that a packet is lost on one of these default paths, should be 1 – (1-p1)(1-p2)..(1-pk).

Thanks to Luochen for pointing out the error.

Lecture 11: DNS

In this lecture, we are going to first look at how DNS works in details through a measurement study, and then see how we can exploit DNS to help us measure latency between any pair of end hosts on the Internet.


  • J. Jung, E. Sit, H. Balakrishnan, R. Morris “DNS Performance and the Effectiveness of Caching,” IEEE/ACM Transactions on Networking, 2002, 10(5), [ Google Scholar]
  • KP Gummadi, S. Saroiu, S. Gribble, “King: Estimating latency between arbitrary Internet end hosts“, ACM IMC 2002 [Google Scholar]

    This paper uses DNS in an unintended and clever way to measure latency between any pair of hosts on the Internet.


Download slides as PDF.

Discussion 10: Internet Routing


In the measurement studies by Stefan Savage et. al., a graph is constructed to represent a set of hosts and links between them. They then run shortest path algorithm on the graph to determine the best alternate path between any two hosts.

Should the graph be a undirected or directed graph? Explain.


Vern Paxson found that route fluttering does occur in the Internet. What undesirable effect(s), if any, do route fluttering have on TFRC-based transport protocol such as DCCP?


Vern Paxson also found that routes on the Internet are often asymmetric. What effects(s), if any, do route asymmetry have on the TCP’s adherence to the principle of packet conservation?

Lecture 10: Internet Routing

In this lecture, we are going to look at two measurement-based papers on Internet routing. We will see if Internet routes are stable, symmetric, and optimal.


  • V. Paxson “End-to-end Routing Behaviour in the Internet,” SIGCOMM 1996 [ Google Scholar]

    This paper won the SIGCOMM test-of-time award. See here for a retrospective review of the paper after winning the award. Much more details about this work can be found in Paxson’s thesis.

  • S. Savage, A. Collins, E. Hoffman, J. Snell, T. Anderson, “The End-to-End Effects of Internet Path Selection“, SIGCOMM 1999 [Google Scholar]

    This paper gives some surprising results that inspire a whole new research direction (in overlay networks).

Supplemental Readings

    Vern Paxson, “Measurements and analysis of end-to-end Internet dynamic”, Ph.D. Thesis, UC Berkeley, 1997. PDF from LBL

    This is Vern Paxson’s thesis, which documents his measurement work in greater details than the paper. You may also find these other talks by Vern Paxson interesting.


Download slides as PDF.
Continue reading

Assignment 3: Clarifications

1. Can we do this over LAN?

Yes, this can be one of the scenario if you really want to. But I doubt you will get anything interesting from the traces. It would be more fun to collect traces of TCP flows over WAN.

2. It takes 2 hours to transfer a 200MB file. Is 200MB really necessary?

I have reduced the minimum file size requirement to 50MB.

Discussion 9: Internet Packet Dynamics


Vern Paxson uses PBM (“packet bunch modes”) to estimate the bottleneck bandwidth. PBM uses a range of packet-bunch sizes to form receiver-side estimates, and is designed to overcome several limitations of packet pair techniques, including bottleneck bandwidth changes.

Is using more than two packets strictly necessary to detect a change in bottleneck bandwidth? Justify your answer.


Vern Paxson suggests that a TCP receiver should wait for time W before sending a duplicate ACK upon detecting a gap in the sequence number to reduce the number of bad retransmission. A good choice of W depends on the network characteristics and behavior. What are the factors that affect a good choice of W? How do these factors affect the effectiveness of a particular choice of W?


In the paper “End-to-End Internet Packet Dynamics”, Vern Paxson says the following after presenting his findings on packet losses on the Internet.

` .. the patterns of loss bursts we observe might be greatly shaped by use of “drop tail” queueing. In particular, deployment of random early drop (RED) could significantly affect these patterns …”

How would deployment of RED affect Vern Paxson’s findings in terms of (i) the distribution of outage duration, (ii) unconditional loss probability P_l^u, and conditional loss probability P_l^c ?

(Recall that P_l^c is conditioned on the loss of previous packet)