cs398 Lecture Notes Spring 2000 Week 12, Tuesday For today you should have looked over the exam solutions in these notes. Also, you should have skimmed Section 5.3 and read Section 5.4 in detail. Also, you should have started reading Chapter 6. You should be ready to turn in two sets of written homeworks, one of which was due on the day of the exam and the other of which was due last Thursday. For next time you should finish reading Chapter 6 and write answers to questions 1, 6, 12, and 25. Section 5.4 ----------- Latency: when people are talking about the latency of a packet, it is usually synonymous with either round-trip time or one-way delay. (for example, table 5.3 on page 429) When people talk about the latency of a network, the usually mean minimal rtt or one-way delay, for example a packet with zero data bytes. This intrinsic latency is the sum of the propagation time of the physical link and various software overheads, usually dominated by the time to process headers. Throughput: again, don't confuse throughput and bandwidth. Effective throughput is the actual rate at which some chunk of data gets through a network. Bandwidth is the speed of the individual bits. Throughput cannot be greater than the intrinsic bandwidth of the network, but it might be less because of 1) packet header overheads (both processing time and transmission time) 2) queueing delays If all overhead is per-packet overhead, then as packet sizes go to infinity the effective throughput approaches the intrinsic bandwidth. If there are per-bit overheads, then effective throughput may never approach bandwidth (as seems to be the case with the authors' experiment). Could we use the data in Table 5.3 to estimate the intrinsic bandwidth? Section 6.1 ----------- resource allocation: primarily link bandwidth and buffer space on routers contention: one packet delays another congestion: packets are getting dropped because of insufficient buffer (queue) space congestion control: preventing congestion or dealing with it when it happens (why is routing around busy links insufficient to avoid congestion?) (what's a connectionless flow?) (what's the difference between soft state and hard state?) Router-centric vs. host-centric Who is primarily responsible for detecting and acting? Reservation-based vs. feedback-based In virtual circuit networks, hosts reserve resources for each flow ahead of time, so congestion is avoided, at the cost of underutilizing resources. In a connectionless network, it is generally not possible to avoid congestion, can only deal with it. Window-based vs. rate-based Window: you can send x bits now. Await further instructions. Rate: you can send x bits per second until further notice. Evaluation ---------- Measurements of a single flow: Throughput: rate at which bits are getting through (averaged over an interval of time) Delay: time between leaving the source and arriving at host (averaged over a number of packets or bits) Problem 1: the two goals conflict, how to balance them? One (not very good) possibility: maximize throughput/delay Problem 2: measurements pertain to a single flow, how to aggregate? Total throughput over all flows? Average delay? Problem with most kinds of aggregation is that they neglect some notion of fairness. Unfortunately, fairness is not well defined either. Section 6.2 ----------- queue discipline: who gets transmitted next? basic = FIFO drop discipline: if the queue is full, who gets kicked out? basic = last one in Priority queueing: multiple FIFO queues Problems: 1) starvation 2) allocating priority Fair queueing ------------- 1) Separate queue for each flow 2) Round-robin service -- one packet from each queue (why isn't that adequate?) (how, ideally, would we fix it?) (why is the ideal not feasible?) FQ = approximates bitwise round-robin, but maintains packet boundaries. WFQ = each flow gets a weight, which is abstractly the number of bits per rotation. Was bedeutet "separating policy from mechanism?" 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 Fast recovery ------------- After a timeout, just set current window = 1/2 current window. Next time: congestion avoidance.