02課程講義陳京文英文9e2eprotcol

1、End-to-End ProtocolsInstructor: Jingwen ChenEmail: Web: Dept. Electronics and Information EngineeringOct. 22, 2014Computer NetworksPage 2OutlinelEnd-to-end protocols: basic problemslUser Datagram Protocol (UDP)lTransmission Control Protocol (TCP)lTCP sliding window algorithmlTCP adaptive retransmiss

2、ionComputer NetworksPage 3Transport Layer ProtocolslOffer common services for network applications, e.g., unreliable, reliable, secure data transferlProvide logical communication between application processes running on end hostslsender: breaks application messages into segments, and passes to netwo

3、rk layerlreceiver: reassembles segments into messages, passes to application layerlAlso known as end-to-end protocolsapplicationtransportnetworkdata linkphysicallogical end-end transportapplicationtransportnetworkdata linkphysicalComputer NetworksPage 4Transport Layer Protocols: ChallengeslWhat appl

4、ication-level processes above expectlcoexistence of multiple application processeslreliable message deliverylflow controllvariety of message lengthlWhat the network below may providelunreliable packet delivery: loss, reordering, duplicatelarbitrarily variable delaylfinite size of packetlChallengeslt

5、urn deficient aspects of underlying networks into the high-level service expected by application processesApplicationTransportNetworkReliable Data TransferlReliable data transfer: sliding window algorithm based on acknowledgement, timeout and retransmissionComputer NetworksPage 5Timeout triggerTimeo

6、ut triggerACKSender WindowReceiver WindowSeqNum012End-to-End Reliable Transfer: Issue 1lSliding window algorithm needs state information maintained on both sideslAn end-to-end reliable transfer protocol should support a number of application processeslTherefore, logical connection is necessary to re

7、late an entry of state info with a remote application processComputer NetworksPage 6App. Process1Host 1Host AE2EprotocolApp.App. Process NHost NApp.End-to-End Reliable Transfer: Issue 2lEnd-to-end connections are likely to have widely different RTTs due to distance, and variance of RTTlTherefore, ti

8、meout mechanism in sliding window algorithm that triggers retransmissions must be adaptiveComputer NetworksPage 7TimerTimerSender WindowReceiver WindowEnd-to-End Reliable Transfer: Issue 3lPackets may be reordered while crossing the Internet, and its difficult to anticipate how late a packet can arr

9、ivelTherefore, sliding window algorithm has to keep from being confused by very late arrival of old packetsComputer NetworksPage 8TimerTimerSender WindowReceiver WindowEnd-to-End Reliable Transfer: Issue 4lCurrently available resource (e.g., buffer space) at receiver is highly variable due to differ

10、ent delay x bandwidth products, and resource sharing between multiple connectionslTherefore, a mechanism is needed for sender to learn what amount of resource at receiver is available flow controlComputer NetworksPage 9App. Process1Host 1Host AE2EprotocolApp.App. Process NHost NApp.End-to-End Reliab

11、le Transfer: Issue 5lCurrently available network resource (e.g., bandwidth) is highly variable due to coexisting stochastic flows, cannot be known in advance by senderlTherefore, a mechanism is needed for a sender to learn what amount of resource on the network is available congestion controlCompute

12、r NetworksPage 10App. Host 1bE2EprotocolApp. Host 2bE2EprotocolApp. Host 2aE2EprotocolApp. Host 1aE2EprotocolComputer NetworksPage 11OutlinelEnd-to-end protocols: basic problemslUser Datagram Protocol (UDP)lTransmission Control Protocol (TCP)lTCP flow controllTCP adaptive retransmissionComputer Netw

13、orksPage 12User Datagram Protocol (UDP)lOne of two transport layer protocols in TCP/IP protocol stacklFeatureslupon IP, just adds a level of demultiplexinglmessage-orientedlconnectionlesslno guarantee to reliable message deliverylno flow control Computer NetworksPage 13UDP HeaderlFieldslSrcPort and

14、DstPort: identify application processeslChecksum: optional, computed on the payload and pseudo headerSrcPortDstPortChecksumLengthData01631UDP DemultiplexingApplicationprocessApplicationprocessApplicationprocessUDPPackets arrivePortsQueuesPacketsdemultiplexedComputer NetworksPage 15UDP: Pros and Cons

15、lFine control over what data is sent and whenlAs soon as an application process writes into the socketlUDP will package the data and send the packetlNo delay for connection establishment lUDP just blasts away without any formal preliminariesl which avoids introducing any unnecessary delayslNo connec

16、tion statelNo allocation of buffers, parameters, sequence #s, etc.l making it easier to handle many active clients at oncelSmall packet header overheadlUDP header is only eight-bytes longlNo guarantee to reliable and in-order data deliverylNo adaptation to network statelmay overflow networklmay supp

17、ress adaptive (e.g. TCP) flowsComputer NetworksPage 16Network Applications Using UDPlSimple query protocols, e.g., Domain Name System (DNS)lsingle UDP segment is usually enough for carrying a query messageloverhead of connection establishment is overkillleasier to have the application retransmit if

18、neededlMultimedia streaming, e.g., VoIP, video streamingloccasional loss of packet is acceptablelretransmitting lost/corrupted packets is not worthwhilelby the time the packet is retransmitted, its too lateComputer NetworksPage 17OutlinelEnd-to-end protocols: basic problemslUser Datagram Protocol (U

19、DP)lTransmission Control Protocol (TCP)lTCP sliding window algorithmlTCP adaptive retransmissionComputer NetworksPage 18Transmission Control Protocol (TCP)lOne of two transport layer protocols in TCP/IP protocol stack, and most of applications use TCPlByte streaminglbyte oriented rather than message

20、 oriented (e.g. UDP)lConnection orientedlend hosts need to establish a connection before data exchangelfull-duplex: data can be exchanged along both directionslReliable data transferlguaranteed in-order data deliverylFlow controllkeeps the sender from overloading the receiverlCongestion controllkeep

21、s the sender from overloading the networkByte Streaming by TCPlAlthough transmitting data in the form of segment, TCP does not distinguish boundaries among the messages written by application processesApplication processWritebytesTCPSend bufferSegmentSegmentSegmentTransmit segmentsApplication proces

22、sReadbytesTCPReceive buffer Computer NetworksPage 20TCP SegmentslTCP sends a segment whenlthe amount of data reaches the maximum segment size (MSS)ltriggered by the application, e.g. push operationlperiodic timer expires lChoice of MSSlmakes resulted IP packet not be fragmentedlMSS = MTU IP header s

23、ize TCP header sizeTCP Header FormatOptions (variable)DataChecksumSrcPortDstPortHdrLen0FlagsUrgPtrAdvertisedWindowSequenceNumAcknowledgment04101631lSequenceNum, Acknowledgement, and Advertisedwindow used by sliding-window based flow controllFlagslSYN, FIN establishing/terminating a TCP connectionlAC

24、K set when Acknowledgement field is validlURG urgent data; Urgent Pointer says where non-urgent data startslPUSH dont wait to fill segmentlRESET abort connectionComputer NetworksPage 22TCP PortslSimilar to UDP, TCP uses port numbers to identify the client and server applicationslWell known ports are

25、 used to identify server applicationslexamples: HTTP (80), FTP (21)lwell known port numbers are between 1 and 1023lClient chooses different port number for each application processlthese ports are known ephemeral ports (short lived)lusually between 1024 and 5000Computer NetworksPage 23TCP Ports (con

26、td.)lEach TCP connection is uniquely identified by a 4-tuple lConsider other existing transport protocols (UDP, or raw IP), an end-to-end data flow (not connection) is uniquely identified by the 5-tuple lProtocol means TCP, UDP, lthe finest granularity of service differentiation by a quality of serv

27、ice (QoS) mechanisml implies a socket in Socket API from the senders point of viewComputer NetworksPage 24TCP Connection EstablishmentlDone before data transferlBased on 3-way handshakelexchange three messages between two TCP peerslto agree on the initial sequence numbers of two TCP peers lThe initi

28、al sequence number is randomly generatedlthe Acknowledgment is always one larger than the peer sentComputer NetworksPage 25TCP 3-Way HandshakeActive participant(client)(server)SYN, SequenceNum=xACK, Acknowledgment =y+1Acknowledgment =x+1SYN+ACK, SequenceNum=y,Computer NetworksPage 26TCP Connection T

29、erminationlTwo independent handshakes terminating unidirectional half of the connectionTCP State Transition (State, Event/Action)lStates: CLOSED, ESTABLISHED, lEvents triggering state transitionslsegment arrivalsllocal operationslActionslsending segmentsllocal operationsComputer NetworksPage 27CLOSE

30、DLISTENSYN_RCVDSYN_SENTESTABLISHEDCLOSE_WAITLAST_ACKCLOSINGTIME_WAITFIN_WAIT_2FIN_WAIT_1Passive openCloseSend / SYNSYN/SYN + ACKSYN + ACK/ACKSYN/SYN + ACKACKClose/FINFIN/ACKClose/FINFIN/ACKACK + FIN/ACKTimeout after twosegment lifetimesFIN/ACKACKACKACKClose/FINCloseCLOSEDActive open /SYNComputer Net

31、worksPage 28OutlinelEnd-to-end protocols: basic problemslUser Datagram Protocol (UDP)lTransmission Control Protocol (TCP)lTCP sliding window algorithmlTCP adaptive retransmissionComputer NetworksPage 29TCP Sliding Window AlgorithmlDue to the issues of end-to-end reliable transfer, TCPs variant of sl

32、iding window algorithm is more complex than the one for link layerlreliable in-order data deliverylflow controllcongestion control (see another lecture)lSliding window algorithm with varied receiving window sizelreceiver advertises a receiving window size to sender, which is varied over time rather

33、than fixedlreceiving window size is informed using the AdvertisedWindow field in the TCP headerTCP Sliding Window: SenderComputer NetworksPage 30acknowledgedsentto be sentoutside windowSource PortDest. PortSequence NumberAcknowledgmentHL/FlagsAdvertisedWinD. ChecksumUrgent PointerOptions.Source Port

34、Dest. PortSequence NumberAcknowledgmentHL/FlagsAdvertisedWinD. ChecksumUrgent PointerOptions.Segment sentSegment receivedwritten(by app.)Computer NetworksPage 31TCP Flow ControllFlow control: a sender sends data as much (quickly) as possible but not overloading the receiverlTCP operationslconnection

35、 establishment: the receiver puts its buffer size in the AdvertisedWindow fieldlthe first round: the sender can send no more than min (available data, AdvertisedWindow)lthereafter: the receiver acknowledges received segments, and inform the sender the current available buffer size using AdvertisedWi

36、ndowlthe sender can send no more than min (available data, AdvertisedWindow Amount of unacknowledged data)Computer NetworksPage 32Buffering with Sliding WindowSending applicationLastByteWrittenTCPLastByteSentLastByteAckedReceiving applicationLastByteReadTCPLastByteRcvdNextByteExpected(a)(b)Advertise

37、dWindow = MaxRcvBuffer (NextByteExpected-1) - LastByteRead)SndWindow = AdvertisedWindow (LastByteSent - LastByteAcked)TCP Flow Control: ExamplelOnce receiver advertises a window size of 0, sender will periodically send probe segment to detect receiving window size become non-zero or notComputer Netw

38、orksPage 33Computer NetworksPage 34TCP AcknowledgementlThe acknowledgement contains the sequence number expected nextlThe acknowledgement is piggybacked in a data segment with the ACK flag set in the TCP headerSequence Number and Window Size: Protecting against WraparoundlGeneral rule: sequence numb

39、er space be twice as big as the window sizelTCP sequence number space (232) window size (216)lTo be prepared for very late packet arrival, TCP introduces Maximum Segment Lifetime (MSL), recommended as 120 sec.,l., sequence number doesnt wrap around within MSLComputer NetworksPage 35Sequence Number a

40、nd Window Size: Keeping the Pipe FulllGeneral rule: sending window size (actually determined by AdvertisedWindow) needs to be larger than delay x bandwidth product keeping the pipe fulllTCP AdvertisedWindow: 16 bit 64 KBlDelay x bandwidth product with RTT 100msComputer NetworksPage 36When Does TCP S

41、end a SegmentlTCP sends a segment whenlthe amount of data reaches the maximum segment size (MSS)ltriggered by the application, e.g. push operationla trigger timer expires lConsiderations on the trigger timer designlEfficiency of transmitting data, e.g., sending a large segment rather than a number o

42、f small oneslNo hurt to an interactive application, which often generates small messages, e.g., keystrokeComputer NetworksPage 37Silly Window SyndromelThe strategy of aggressively taking advantage of any available window leads to a situation as silly window syndromelSmall containers cannot coalesce

43、with adjacent ones to create a larger container, which is more efficientlObviously, it seems good to introduce a timer to trigger transmissionlIf waiting for too short, there will be still many small containerslIf waiting for too long, it may introduce large delayComputer NetworksPage 38Nagle Algori

44、thmlBasic idea: self-clocking by ACK las long as TCP has any data in flight, the sender will eventually receive an ACK, and this ACK can be treated like a timer firing, triggering the transmission of more datalAlgorithmlWhen the application produces data to sendlif both the available data and the wi

45、ndow MSSlsend a full segmentlelsel if there is unACKed data in flightl buffer the new data until an ACK arrivesl elsel send all the new data nowlIt takes both into account, i.e., efficiency of sending data and no hurt to interactive applicationsComputer NetworksPage 39Nagle Algorithm: ExampleCompute

46、r NetworksPage 40Computer NetworksPage 41OutlinelEnd-to-end protocols: basic problemslUser Datagram Protocol (UDP)lTransmission Control Protocol (TCP)lTCP sliding window algorithmlTCP adaptive retransmissionComputer NetworksPage 42ACK and TimeoutlThe problem is how to determine the timeout valuelfor

47、 a point-to-point link, its simplelpropagation delay is fixed and known in advancellink bandwidth is knownlthus timeout value can be chosen to be fixedlbut for a TCP connection, its complexComputer NetworksPage 43Determining Timeout for TCPlTimeout mechanism must work anywhere and anytimelTCPs solut

48、ion: to make timeout proportional to RTTlWhat 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 RTTlTCP uses an adaptive mechanism to

49、 determine the timeout valueComputer NetworksPage 44Adaptive RetransmissionlOriginal algorithml1. EstimatedRTT = a x EstimatedRTT + (1- a) x SampleRTTl2. Timeout = 2 x EstimatedRTTl a: 0.8 0.9 recommended in the original TCP speclSampled RTTltime at which the segment is ACKed time at which it is sentRTT Estimation: ExampleComputer NetworksPage 45Computer NetworksPage 46Problem with Original AlgorithmlQ: How to distinguish between the real ACK and the ACK of the retransmitted packet?SenderReceiverOriginal transmissionACKRetransmissionSenderReceiverOriginal transmissionACKRetransmissio