网络实验计算机网络l14-tcp ii v5

1、lJing Xu (徐晶)lDept. of Electronics and Information Eng.lHuazhong University of Science and TechnologylJune. 2012Problem in Chapter5:Getting Processes to Communicate-2-3-Challenges of TCP Reliable trans.Timeout triggerTimeout triggerACKSender WindowReceiver WindowSeqNum012Background below: IP provide

2、 connection-less, un-reliable services, running across heterogenic networks, connecting diverse hostsTimeout triggerTimeout triggerSeqNum012Challenge3: ReorderingPackets loss and delayChallenge4: Flow controlDiverse delay*bandwidth, bufferChallenges of TCP Reliable trans.-4-Too many TCP connections

3、bringtoo much traffic to the intermediate routerTCP design: Problems and solutions-5-No.Problem and ChallengesSolutionSubsection 1Connection setupSetup: three-way handshakeClose: three-way handshakes5.2.32Timeout problem on various links3Packet arrivals not in sequence4Flow control for various clien

4、ts5Congestion control for networkLecture 14l5.2 Reliable Byte Stream (TCP)l5.2.1 End-to-End Issuesl5.2.2 Segment Formatl5.2.3 Connection Establishment and Terminationl5.2.4 Sliding Window Revisitedl5.2.5 Triggering Transmissionl5.2.6 Adaptive Retransmissionl5.2.7 Record Boundariesl5.2.8 TCP Extensio

5、nsl5.2.9 Alternative Design Choices-6-7-TCP Sliding Window AlgorithmSending applicationLastByteWrittenTCPLastByteSentLastByteAckedReceiving applicationLastByteReadTCPLastByteRcvdNextByteExpected(a)(b)LastByteAckedLastByteSent LastByteSentLastByteWritten LastByteReadNextByteExpected NextByteExpectedL

6、astByteRcvd+1-8-TCP Sliding Window AlgorithmLastByteReadReceivers viewLastByteRcvdNextByteExpectedLastByteRcvd - LastByteRead MaxRcvBufferAdvertisedWindow = MaxRcvBuffer (NextByteExpected-1)-LastByteRead)-9-TCP Sliding Window AlgorithmLastByteSent - LastByteAcked AdvertisedWindowEffectiveWindow = Ad

7、vertiseWindow (LastByteSent LastByteAcked)LastByteWrittenLastByteSentLastByteAckedSenders viewLastByteWritten LastByteAcked MaxSendBuffer -10-TCP Sliding Window AlgorithmTCPs solutionIntroduction of MSL( Maximum Segment Lifetime), e.g. 120secExtension on the space of sequence number (32b) with times

8、tamp (32b)-11-TCP Sliding Window AlgorithmTCPs solutionExtension on the description of AdvertisedWindow size, scaling factorTCP design: Problems and solutions-12-No.Problem and ChallengesSolutionSubsection 1Connection setupSetup: three-way handshakeClose: three-way handshakes5.2.32Timeout problem on

9、 various links3Packet arrivals not in sequenceWindow based buffer management for both sides5.2.44Flow control for various clientsWindow based flow control by AdvertisedWindow notification5.2.45Congestion control for network6Protocol scalability on various linksExtension to the fields of Seq and Adve

10、rtisedWindow in TCP header5.2.4Lecture 14l5.2 Reliable Byte Stream (TCP)l5.2.1 End-to-End Issuesl5.2.2 Segment Formatl5.2.3 Connection Establishment and Terminationl5.2.4 Sliding Window Revisitedl5.2.5 Triggering Transmissionl5.2.6 Adaptive Retransmissionl5.2.7 Record Boundariesl5.2.8 TCP Extensions

11、l5.2.9 Alternative Design Choices-13-14-Triggering Transmission in TCPlTCP has three mechanisms to trigger the transmission of a segmentl(1) When the number of collected bytes reach MSS lMSS (maximum segment size) is usually set to MTU IP_header_sizel(2) When TCP is asked to transmit by the sending

12、processlPush operation: the sending application process invokes this operation to flush the buffer of unsent bytesl(3) When a trigger timer timeoutlthe sender send those bytes currently buffered for transmissionSilly Window SyndromelProblemlThe segments cannot coalesce with adjacent containers to cr

13、eate larger containerslthe strategy of aggressively taking advantage of any available window leads to a situation as the silly window syndromelKey of solution: timer setting lWhen does the TCP sender decide to transmit a segment?lIf wait too short time, there will be many small containers;lIf wait t

14、oo long, there will be a large delay and jitter.-15-Nagle AlgorithmlMotivation: self-clocking by ACK lAs long as TCP has any data in flight, the sender will eventually receive an ACK. lThis ACK can be treated like a timer firing, triggering the transmission of more data -16-Nagle Algorithm-17-TCP de

15、sign: Problems and solutions-18-No.Problem and ChallengesSolutionSubsection 1Connection setupSetup: three-way handshakeClose: three-way handshakes5.2.32Timeout problem on various links3Packet arrivals not in sequenceWindow based buffer management for both sides5.2.44Flow control for various clientsW

16、indow based flow control by AdvertisedWindow notification5.2.45Congestion control for network6Protocol scalability on various linksExtension to the fields of Seq and AdvertisedWindow in TCP header5.2.47Silly Window Syndrome in sender sideNagle Algorithm: self-clocking by ACK 5.2.5Lecture 14l5.2 Reli

17、able Byte Stream (TCP)l5.2.1 End-to-End Issuesl5.2.2 Segment Formatl5.2.3 Connection Establishment and Terminationl5.2.4 Sliding Window Revisitedl5.2.5 Triggering Transmissionl5.2.6 Adaptive Retransmissionl5.2.7 Record Boundariesl5.2.8 TCP Extensionsl5.2.9 Alternative Design Choices-19-Determining T

18、imeout for TCPlWhat makes it difficult to determine RTT for a TCP connectionlwidely variable distance between two end hostslthe propagation delay is not known beforehandltime-variant queuing delay or packet losslmaybe dominant aspect of RTTlTCPs solutionlTCP uses an adaptive mechanism to determine t

19、he timeout value, make timeout proportional to RTT-20-21-Adaptive RetransmissionlOriginal algorithml EstimatedRTT = a x EstimatedRTT + (1- a) x SampleRTTl Timeout = 2 x EstimatedRTTlSmooth factor a: 0.8 0.9 mended in the original TCP speclSampled RTT: time_ACKed time_sentSenderReceiverOriginal trans

20、missionACKRetransmissionSenderReceiverOriginal transmissionACKRetransmission(a)(b)Problem: Cannot distinguish between the current ACK and the ACK of the retransmitted packet22Example RTT Estimation-23-Karn/Partridge AlgorithmlProposed two changesldoes not measure RTT when retransmitting segmentldoub

21、le the timeout after each retransmissionlknown as exponential backofflthe idea: packet loss may be due to congestion, and TCP source should be less aggressiveProblem: no requirement to double small estimated RTT; not enough to double big estimated RTT-24-Jacobson/Karels AlgorithmlThe problem with th

22、e original algorithm is that it didnt take the fluctuation of RTT into accountlProposallDifference = SampleRTT EstimatedRTTlEstimatedRTT = EstimatedRTT + (d x Difference)lDeviation = Deviation + d (|Difference| - Deviation)lTimeout = m x Estimated RTT + f x Deviationlwhere d is between 0 and 1, m is

23、 typically set to 1 and f is set to 4lthe deviation measures how far the estimated RTT may be differed from the true RTT, small deviation means an accurate estimated RTT, and vice versalNotelRe-transmission may based on selective ACK (SACK), which is another extension of TCPTCP design: Problems and

24、solutions-25-No.Problem and ChallengesSolutionSubsection 1Connection setupSetup: three-way handshakeClose: three-way handshakes5.2.32Timeout problem on various linksRTT estimation by Jacobson/ Karels Algorithm5.2.63Packet arrivals not in sequenceWindow based buffer management for both sides5.2.44Flo

25、w control for various clientsWindow based flow control by AdvertisedWindow notification5.2.45Congestion control for networkChapter6 6Protocol scalability on various linksExtension to the fields of Seq and AdvertisedWindow in TCP header5.2.47Silly Window Syndrome in sender sideNagle Algorithm: self-c

26、locking by ACK 5.2.5Lecture 14l5.2 Reliable Byte Stream (TCP)l5.2.1 End-to-End Issuesl5.2.2 Segment Formatl5.2.3 Connection Establishment and Terminationl5.2.4 Sliding Window Revisitedl5.2.5 Triggering Transmissionl5.2.6 Adaptive Retransmissionl5.2.7 Record Boundariesl5.2.8 TCP Extensionsl5.2.9 Alte

27、rnative Design Choices-26-27-Alternative Design ChoiceslStream-oriented protocol vs. Request/reply protocollByte-oriented protocol vs. Message-oriented protocollExplicit setup/teardown vs. Implicit setup/teardown lWindow-based vs. Rate-based-28-Lecture 14lChapter 5 End-to-End ProtocolslProblem: Gett

28、ing Processess to Communicatel5.1 Simple Demultiplexer (UDP)l5.2 Reliable Byte Stream (TCP)l5.6 Summary-29-5.6 SummarylTwo transport layer protocols in TCP/IP protocol stacklUDP: developed in 1980lFirst TCP in 1974, IPv4 in 1981lUDPlUpon IP, just adds a level of demultiplexinglMessage-oriented, conn

29、ectionlesslTCPlUpon IP, reliable communication servicelByte stream servicelModifications on basic sliding window protocolTCP design: Problems and solutions-30-No.Problem and ChallengesSolution1Connection setupSetup: three-way handshakeClose: three-way handshakes2Timeout problem on various linksRTT e

30、stimation by Jacobson/ Karels Algorithm3Packet arrivals not in sequenceWindow based buffer management for both sides4Flow control for various clientsWindow based flow control by AdvertisedWindow notification5Congestion control for network6Protocol scalability on various linksExtension to the fields

31、of Seq and AdvertisedWindow in TCP header7Silly Window Syndrome in sender sideNagle Algorithm: self-clocking by ACK Challengesof unreliable IPChallengesof complex Protocol designChallenges of TCP Reliable trans.-31-Too many TCP connections bringtoo much traffic to the intermediate router-32-Congesti

32、onlCongesting occurs in a network when the traffic load offered to it is persistently higher than the capacitylManifestations of congestion arelsustained packet losslincrease in packet delay-33-Congestion control and Resource AllocationlCongestion control and Resource Allocation are two sides of the

33、 same coin. lFrom the view of userlhost-to-host, end-to-end protocollFrom the view of networklmultiple flow are competing the resourcelresource: the bandwidth of the links and the buffers on the routers or switches lcongestion: too many packets are contending for the same link, the queue overflows a

34、nd packets have to be droppedlhow to effectively and fairly allocate resources among acollection of competing users?-34-Congestion control and Resource AllocationlCongestion control and Resource Allocation are two sides of the same coin. lIf the network takes an active rolelResource AllocationlAlloc

35、ating the network resource in advance, for example,scheduling which virtual circuit gets to use a given physical linklIf the network takes an inactive rolelCogestion controllLet packet sources send as much data as they want, and then recover from congestion should it occurProblem in Chapter6:Allocat

36、ing resources-35-Lecture 14lChapter 6. Congestion Control and Resource AllocationlProblem: Allocating Resourcesl6.1 Issues in Resource Allocation l6.2 Queuing Disciplines l6.3 TCP Congestion Control l6.4 Congestion-Avoidance Mechanisms l6.5 Quality of Service l6.6 Summary -36-Networking ModellPacket

37、-switched networkslConnectionless flowslNo reservation of network resources at the start of a sessionlFlows can be defined at several granularities (process to process, source-destination, etc.)lService modellBest effort: All packets are treated in exactly the same manner37Taxonomy of Resource Alloc

38、ationlRouter-centric vs. host-centriclRouter-centric: Routers decide when to schedule, which packets drop, inform the rate to hostslHost-centric: End-hosts observe the network conditionslRouter-centric and host-centric are not mutually exclusivelReservation-based vs. feedback-basedlReservation-based

39、: Resource reserved in advance, flow is dropped if resources are unavailablelFeedback-based: Source transmits packets without reserving any capacitylFeedback may be explicit or implicitlWindow-based vs. rate-basedlWindow-based: Use the same window employed for reliable transmissionlRate-based: Rate

40、is explicitly controlled by the network or receiver38Network load and Congestion lKnee point after which lthroughput increases very slowldelay increases fastlCliff point after whichlthroughput starts to decrease very fast to zero (congestion collapse)ldelay approaches infinityLoadLoadThroughputDelay

41、kneecliffcongestioncollapsepacketlossCongestion Control and AvoidancelCongestion cannot be removed by increasing router buffer sizelCongestion can be removed bylsources reducing their offered load short time scaleltraffic engineering long time scalelincreasing link capacity long time scaleLoadThroug

42、hputkneecliffcongestioncollapseCongestion control Congestion avoidance-41-Congestion control actionhost-based congestion controlrouter-based congestion controlhost-based congestion controlhost-based congestion controlhost-based congestion control-42-Chapter 6. Congestion Control and Resource Allocat

43、ionPolicyRouterHostSubsectionHost-based congestion controlFIFO queuing TCP congestion control6.2, 6.3 in textbookRouter-based congestion controlActive queue management (AQM)TCP congestion control6.4 in textbookResource allocation and congestion avoidance Resource reservation and QoS provision 6.5 in

44、 textbookLecture 14lChapter 6. Congestion Control and Resource AllocationlProblem: Allocating Resourcesl6.1 Issues in Resource Allocation l6.3 TCP Congestion Control l6.3.1 Additive Increase/Multiplicative Decrease l6.3.2 Slow Start l6.3.3 Fast Retransmit and Fast Recovery l6.6 Summary -43-44-TCP Co

45、ngestion ControllTCP sources at end hosts adjust their sending rates to avoid overloading the networklconsidering the available capacity of the networklTwo basic questionslhow to infer the network congested?lUses timeout as an indication of network congestionlhow to adjust the sending rate?lTCP main

46、tains a CongestionWindow variableTCP Congestion WindowlEach TCP sender maintains a congestion windowlMax number of bytes to have in transit (not yet ACKd)lAdapting the congestion windowlDecrease upon losing a packet: backing offlIncrease upon success: optimistically exploringlAlways struggling to fi

47、nd right transfer ratelTradeofflPro: avoids needing explicit network feedbacklCon: continually under- and over-shoots “right” rate45Receiver Window vs. Congestion WindowlFlow controllKeep a fast sender from overwhelming a slow receiverlCongestion controllKeep a set of senders from overloading the ne

48、tworklDifferent concepts, but similar mechanismslTCP flow control: receiver windowlTCP congestion control: congestion windowlSender TCP window = l min congestion window, receiver window 466.3.1 Additive Increase, Multiplicative Decrease (AIMD)lHow much to adapt?lAdditive increase: On success of last

49、 window of data, increase window by 1 Max Segment Size (MSS)lMultiplicative decrease: On loss of packet, divide congestion window in halflMuch quicker to slow than speed up!lOver-sized windows (causing loss) are much worse than under-sized windows (causing lower thruput)lAIMD: A necessary condition

50、for stability of TCP47Leads to the TCP “Sawtooth”48tWindowhalvedLossHow Should a New Flow Start?49tWindowhalvedLossBut, could take a long time to get started!Start slow (a small CWND) to avoid overloading network-50-6.3.2 Slow StartlProblemladditive increase takes too long to ramp up a connection fr

51、om the beginninglMotivationlto take a faster approachlSolutionlset CongestionWindow to one packet Initiallylincreases rate exponentially until the first lossSlow Start and the TCP Sawtooth51tWindowhalvedLossExponential “slow start” So-called because TCP originally had no congestion control Source wo

52、uld start by sending an entire AdvertisedWindow Led to congestion collapse!-52-Additive Increase vs. Slow StartTwo Kinds of Loss in TCPlTimeoutlPacket n is lost and detected via a timeoutlWhen? n is last packet in window, or all packets in flight lostlAfter timeout, blasting entire CWND would cause

53、another burstlBetter to start over with a low CWNDlTriple duplicate ACKlPacket n is lost, but packets n+1, n+2, etc. arrivelHow detected? Multiple ACKs that receiver waiting for nlWhen? Later packets after n receivedlAfter triple duplicate ACK, sender quickly resends packet nlDo a multiplicative dec

54、rease and keep going53-54-Triple duplicate ACK-55-6.3.3 Fast RetransmitlProblem with original retransmitllong periods of timeoutlinefficiency in cases in which only one packet is lostlMotivationlObservation of Duplicate ACKs lone packet is lostlout-of-order deliverylSolutionlFast retransmit: TCP retransmit without waiting for timeout if the source receives three duplicate ACKs-56-Fast RecoverylPreviously, slow start follows fast retransmitlNow fast recoverylremoves the slow start phase between fast retransmit and additive increaselsets CongestionWindow equal to ha