cs398 Lecture Notes Spring 2000 Week 12, Thursday For today you should have finished Chapter 6 and written answers to questions 1, 6, 12, and 25. For next time, read Chapter 9. Section 6.3 ----------- TCP congestion control send packets, react to events events = timeouts and obstinate ACKs congestion collapse 1) blast the network 2) everything gets dropped and times out 3) go to 1 self-clocking means the protocol is dynamic and usually has no initial information about flows or network Additive increase/multiplicative decrease ----------------------------------------- AdvertisedWindow protects receiver provided by receiver CongestionWindow protects network continuously estimated Fundamental assumption: if a packet it dropped, it is probably due to congestion. (how do we know when a packet is dropped?) Another fundamental assumption: things are constantly changing, but they are not changing TOO fast (information about recent history is still relevant) After every successful transfer, increment the CW. After every dropped packet, halve the CW. This turns out to be a necessary condition for stability. Intuition: Being too high is much worse than being too low. Need to get out fast! Slow start ---------- Increase exponentially, rather than linearly. (What exactly is this slower than?) This happens at the beginning of a connection. It also happens when a timeout occurs: 1) threshhold = target window = 1/2 current window 2) current window = 1 3) increase current window exponentially until we get back to target 4) increase linearly thereafter (why are so many packets lost during startup) (tradeoff between agressive start and linear start) Is there a better way to get an initial estimate of the available bandwidth? Maybe -- packet-pair. Fast retransmit --------------- How do we usually detect a lost packet. What's the alternative. 1) sender sends a packet after every arrival, but only ACKs things in order 2) out-of-order arrivals yield obstinate ACKs 3) obstinate ACKs probably indicate loss 4) and we can tell what's missing (How long does it take to get an obstinate ACK?) (Is that really shorter than the timeout value?) Fast recovery ------------- After a timeout, just set current window = 1/2 current window. Section 6.4 ----------- Congestion avoidance DECbit: changes both routers and hosts RED: changes just the routers Vegas: just the hosts Which can we implement? Which can Cisco implement? Which can no on implement? DECbit ------ (what does DEC stand for?) packet headers have a bit, initially zero. (they call it a congestion bit, it should be a contention bit) If the packet goes through a busy router, the bit gets set. Bit gets copied into the ACK. Hosts can keep track of how many of their recent packets went through busy routers (on the outgoing path?) How busy is busy? 1) smoothed average of queue length 2) arbitrary threshhold (based on very careful analysis of unreasable workload and meaningless performance metric) How do hosts react? If the %age of marked packets is small, increase the window, and vice versa. Again, there are free parameters that have to be tuned. RED --- Random early detection. Routers monitor their utilization. Send implicit messages to hosts. (What's an implicit message?) Again, we have a smoothed queue length. If small, never drop. If large (but not full) always drop. In between, there is some probability of dropping. See figure on page 479. Even with RED, we might wind up in tail drop mode. (How?) Again, there are free parameters that have to be tuned. Hard to do without a good network simulation, and that depends on a good workload model. Current work at Cisco focuses on setting RED parameters dynamically. Small optimization: on ATM, if you are going to drop one cell of an AAL PDU, then you might as well drop them all. Vegas ----- Entirely source-based: try to detect the incipient stages of congestion. 1) observe an increase in RTT: queue delays are increasing! 2) observe a leveling off in actual throughput, even as congestion window increases. How can we estimate actual throughput? 1) Divide the number of bytes outstanding in the network by RTT 2) Choose a reference packet. Record the time when it starts to transmit and when it gets ACKed. Measure the number of bits that are sent during that RTT. For a given congestion window, what throughput do we expect in the absence of contention: ExpectedRate = CongestionWindow / BaseRTT Where BaseRTT is the shortest (possible/observed) RTT. Diff = ExpectedRate - ActualRate This is positive by definition. If it's too big, we are spinning our wheels. If it's too small, we dont have enough data in the network, which makes it harder to respond to transient increases in capacity (so I've heard). No clues about how to choose the threshholds. Evaluation ---------- All hosts need not run the same congestion avoidance algorithm. Some are probably more polite than others. Why not run "TCP Vogon"? It's ok, my brother drives like this.