CS118 Week 5 Lecture Slides!Chapter 3 outline!! 3.1 Transport-layer services!! 3.2 Multiplexing and demultiplexing!! 3.3 Connectionless transport: UDP!! 3.4 Principles of reliable data transfer!! 3.5 Connection-oriented transport: TCP!" segment structure!" reliable data transfer!" flow control!" connection management!! 3.6 Principles of congestion control!! 3.7 TCP congestion control!CS118!2!Network Congestion!Congestion: “too many sources sending too much data too fast for network to handle”!CS118! 3!Scenario 1!# 2 senders, 2 receivers!# one router w/ infinite buffer!# no retransmission!When congested:!# long delays!# maximum achievable throughput!unlimited shared output link buffers Host A !in : original data Host B !out Congestion: scenario 2 !Ideal case:!! Each sender takes turns and sends only when router buffer available!CS118!4!one router, finite buffer!senders retransmit when timeout!R/2 R/2 !in !out !"in !"out =Congestion: scenario 2 !CS118!5!one router, finite buffer!senders retransmit when timeout!R/2 R/2 !in !out ! Packets may get dropped at router due to buffer full!! Known loss case: sender only retransmits if packet known to be lost!! Duplicates: sender times out prematurely and retransmits, both packets are delivered!R/2 R/2 !in !out Congestion scenario 3!CS118!6!• Long delays!• superfluous retransmissions!• when a packet is dropped, any “upstream transmission capacity” used for that packet was wasted!!Host A Host B finite shared output link buffers !'in : original data, plus retransmitted data !in : original data !out Q: what happens as and increase? ! "'in! "inCost of congestion!! unneeded retransmissions: bottleneck link transmitted multiple copies of the same packet, reduce effective throughput!! when a packet dropped further down the road, any “upstream” transmission capacity used for that packet was wasted!!CS118!7!Congestion control: options!Two broad approaches towards congestion control:!Network-assisted congestion control: routers provide feedback to end hosts, such as !! Single bit congestion indication, or!! Explicit rate that sender should send at!End-end congestion control: no explicit feedback from network!! Hosts infer congestion from observed loss or delay!" approach taken by TCP!CS118!8!TCP Congestion Control!! Add a “congestion control window” congwin on top of flow-control window!! Sender limits: LastByteSent-LastByteAcked ! CongWin!!! CongWin initialized to 1 packet, increases until congestion!" How sender infers congestion: packet loss (timeout, or 3 dup. ACKs)!! Upon loss: decrease congwin, then begin increasing again!" Two phases: (1)slow start, (2)congestion avoidance!" threshold defines the boundary between the two !CS118!9!Congwin recvwin Basic idea: learn from observations!! (mss: maximum segment size)!! when congwin < threshold, increase congwin exponentially!! when congwin " threshold, increase congwin linearly!! if packet lost, have gone too far!" threshold = congwin / 2!" If 3 dup. ACKs: network capable of delivering some packets, cut congwin to half of its current value!" If timeout: slow-start again (congwin = 1 mss)!! Additive Increase, Multiplicative Decrease (AIMD)!CS118!10!TCP SlowStart & Congestion Avoidance!CS118!11!initialize: Congwin = 1 mss threshold = RcvWindow if (CongWin < threshold) { for every segment ACKed Congwin++ } until (loss event) /* slowstart is over */ { for every w segments ACKed: Congwin++ } Until (loss event) /* loss detected */ threshold = Congwin/2 If (3 dup. ACKs) Congwin = threshold Else Congwin = 1 mss one segment RTT two segments four segments TCP sender congestion control!CS118!12!State Event TCP Sender Action Commentary Slow Start (SS) Received ACK for previously unacked data CongWin = CongWin + MSS If (CongWin > Threshold) set state to “Congestion Avoidance” Resulting in a doubling of CongWin every RTT Congestion Avoidance (CA) Received ACK for previously unacked data CongWin = CongWin+MSS * (MSS/CongWin) Additive increase, resulting in increase of CongWin by 1 MSS every RTT SS or CA Loss event detected by 3 duplicate ACK Threshold = CongWin/2, CongWin = Threshold, Set state to “Congestion Avoidance” Fast recovery, implementing multiplicative decrease. CongWin will not drop below 1 MSS. SS or CA Timeout Threshold = CongWin/2, CongWin = 1 MSS, Set state to “Slow Start” Enter slow start SS or CA Duplicate ACK Increment duplicate ACK count for segment being acked CongWin and Threshold not changedTCP throughput!! What’s TCP throughout as a function of window size and RTT?!! Ignore slow start: let W = window-size when loss occurs!" When window is W, throughput = W/RTT!" Just after loss, window $ W/2, throughput to W/2RTT !" Average throughout: 0.75 W/RTT!CS118!13!Is TCP fair?!Fairness: if N TCP sessions share same bottleneck link, each should get 1/N of link capacity!Example: 2 competing connections, same RTT!! Additive increase gives slope of 1!! multiplicative decrease decreases throughput proportionally !CS118!14!capacity R R equal bandwidth share Connection 1 throughput Connection 2 throughput congestion avoidance: additive increase loss: decrease window by factor of 2 congestion avoidance: additive increase loss: decrease window by factor of 2 TCP connection 1 bottleneck router TCP conn 2 Fairness (more)!Fairness and UDP!! Multimedia apps often do not use TCP!" do not want rate throttled by congestion control!! Instead use UDP:!" pump audio/video at constant rate, tolerate packet loss!! Research area: TCP friendly!Fairness and parallel TCP connections!! nothing prevents app. from opening parallel TCP connections between 2 hosts!! Web browsers do this !! Example: a link of rate R, supporting 9 connections; !" A new app. asks for 1 TCP, gets rate R/10!" A new app. asks for 11 TCPs, gets R/2 !!CS118!15!Chapter 3: Summary!! principles behind transport layer services:!" multiplexing, demultiplexing!" reliable data transfer!" flow control!" congestion control!! Internet transport protocols: UDP, TCP!Next:!! leaving the network “edge” (application, transport layers)!! into the network
View Full Document
Unlocking...