User:Derianto/cs244 scribe
Jitendra Padhye et. al., Modeling TCP Throughput: A Simple Model and its Empirical Validation, SIGCOMM 1998
(scribed by Derianto Kusuma)
(Disclaimer: This is not an encyclopedia article.)
Back to CS 244 Scribed Notes
Paper Summary
[edit]This paper characterizes the steady state throughput of TCP given its behaviors (TCP Reno) using mathematical analysis, instead of using the more popular approach of simulation and implementation. More specifically, this paper models the throughput () of TCP bulk transfer (i.e. with continuous sending of unlimited amount of data), as a function of average loss rate () and average RTT, given some acceptable assumptions and approximations.
The model captures various TCP behaviors, including congestion avoidance, fast retransmit on triple duplicate ACKs, timeout with limited exponential backoff, including limit on receiver window size. The model differs from other related models by capturing timeout sequence and maximum advertised window size, which are generally neglected by related works at that time.
The model is empirically validated using measurements of real data transfer tests using several hosts with various operating systems and TCP implementations. The measurements are engineered to account for minor differences in the TCP implementations of the hosts, such as double instead of triple duplicate ACK to indicate loss, different timeout exponential backoff limit, etc.
From the tests, this paper also discovers that timeouts constitute the majority of loss indications. Furthermore, ignoring these timeouts on analytical modeling will yield inflated throughput prediction on high loss rate (). On the other hand, ignoring maximum window size by the receiver will inflate throughput prediction on low loss rate. In general, the new model has achieved greater accuracy in predicting TCP throughput in steady state.
Model
[edit]Assumptions:
- Sending all packets in a window takes less than one RTT
- RTT is independent of window size (thus ignoring buffer delay in the network)
- Packet loss in a round is independent of packet loss in other rounds
- If a packet is lost, all remaining packets in that round are also lost (packet losses in a round are correlated)
- Subtleties of fast recovery are ignored
- Slow start is ignored
- Throughput is in packets per time, not bytes per time
- The model measures throughput, not goodput (therefore, retransmissions of the same packet are counted as multiple packets)
Given:
Estimated:
Symbol Definitions
[edit]| Term | Definition |
| Round | The back-to-back sending of packets ( = window size), until ACK of the first sent packet is received |
| TD | Triple duplicate ACKs (indicating loss) |
| TO | Timeout event (indicating loss) |
| TDP | TD period: A period between two TD loss indications, or a period starting after, or ending in, a TO loss indication |
| Average RTT, also called | |
| The number of packets acknowledged by one ACK (typically ) | |
| Probability that packet is lost, given it is the first packet in a round, or the preceding packet in the round is not lost | |
| Throughput (packets per time), usually written as a function of : | |
| Number of packets sent in the -th TDP | |
| Duration of the -th TDP | |
| Window size at the end of the -th TDP | |
| The first packet number lost in the -th TDP | |
| The round in which is located | |
| The waiting time of the first timeout | |
| Duration of a sequence of timeouts | |
| Time interval between two consecutive timeout sequences | |
| Time interval from the start of congestion avoidance phase of the period, through its timeout sequence, until the beginning of the next period () | |
| Number of packets sent during | |
| Number of periods in the inverval | |
| Number of packets sent during timeout sequence | |
| The probability that a loss indication is a TO | |
| Maximum congestion window size (maximum buffer size advertised by receiver) | |
| Number of rounds in which | |
| Number of rounds in which |
Class Discussion Thursday, Jan 29, 2009
[edit]Problems with TCP (Nandita's thesis)
[edit](continued from Tuesday (1/27) lecture)
How to make TCP more fair, particularly to yield the same throughput for flows with long RTT?
- Since , we can increase the window size in the end hosts with long-RTT flow. However, there is no way for routers to affect end host's window size.
- Using ECN (explicit congestion notification)
How to improve the latency of short flows, which usually takes a relatively long time to complete due to TCP slow start?
- Since short flows are short anyway, people may not care. However, people may care on some application, like browsing a page with various components and images on the page. Two common solutions:
- Opening parallel TCP connections
- Using one TCP connection to download multiple resource on the web
How to decrease queue length in the buffers in the network? (The added latency can be pretty large (i.e. 250 ms), large enough to disturb voice over IP and online gaming)
- Make buffer small. Does it work?
- Use ECN to avoid overflowing buffer
- Detect variation in RTT by the end hosts (some implementations of TCP) or by the routers (Fast TCP). In general, improving TCP implementation in the end hosts to be more congestion-aware may not be useful if not done in large scale. High buffer occupancy in the routers are attributed to the complex behaviors of multiple flows, so a single end host backing off may not have any effect on its own throughput (and is more like an altruistic move).
Modeling TCP Throughput (Padhye et al)
[edit]Is it an acceptable assumption that the sender has infinite data to send?
It is valid in a big part. Most utilization of bandwidth today is dominated by BitTorrent + HTTP traffic for downloading big files or streaming.
Is it an acceptable assumption that RTT is independent of window size?
On a typical home internet connection, the queue delay of the modem buffer can vary the latency by 250 ms (100%) or more. However, this paper only tries to estimate throughput, not latency.
Is it an acceptable assumption that it takes less than 1 RTT to send all packets in a typical window size?
Not really. The ACKs will be received by the end host with a certain rate, which depends on how congested the network currently is. It is likely that the ACKs are received rather slowly compared to the amount of data that the host wants to send, thus the host cannot send the data packets too fast.
Are the experimental results convincing?
The error of the new model is 2-10x more accurate than the error of the past model, but the error is still large in general. Furthermore, it only models throughput, and not goodput, latency, or fairness. The model is also inaccurate in some cases.
What are the benefits of analytical model compared to simulation?
We can plug in parameters into analytical model easily to obtain the result. With analytical model, the intermediate results presented by this paper can be used by another paper that tries to build a better model on top of this model.
Fast TCP (Jing Wu et al)
[edit]Why delaying ACKs instead of delaying data packets?
Data packets take much more buffer space than ACKs (1500 bytes to 40 bytes). Delaying ACKs as a substitute of delaying data packets saves a much buffer.
How likely is asymmetric route between the data packets and their ACKs (how likely is it that data packets and their ACKs do not go through the same node)?
It is more likely in backbone network with complex transit / peering arrangement. However, backbone network usually has high capacity and the utilization is fairly low (~3%) except in the border (gateway) routers, thus congestion is usually not a big concern.
How to ensure fairness in delaying ACKs with multiple flows through a router?
We can introduce states per flow to limit the throughput of one flow to not exceed its fair share. It can include keeping track of the number of forward-direction data packets of each flow.
In general, routers do not keep track of flow because there can be numerous number of flows going through a router (in the order of 100,000 or more).
Is the mechanism of delaying ACKs used somewhere else?
Yes. It is pretty common for routers to drop ACKs as a means of traffic shaping. Stanford might be doing it to.
Personal Comments
[edit]- To judge the accuracy of the throughput estimate more accurately, I think the randomness of the experiment data points (loss rate, # packet sent) needs to be taken into account. To leverage this randomness information, we then can try to plot a polynomial approximation function of the data points with the least sum of error squared. This approximation function will be an objective reference function to judge the model presented in the paper, or other models.
- As we all probably realize, the formula that the model present is very complicated, and reading it plainly does not invoke any insight right away. It would be more useful to describe the characteristics of the formula that are easier to comprehend, like linear or sublinear relations between and , what happens to when increases above or decreases below certain thresholds, what are the thresholds for in terms of , what happens when is too small, etc.
- I would like to see analytical models for TCP to estimate latency and goodput, because I think latency and goodput are the performance criteria that matter most to users.
Back to CS 244 Scribed Notes