L12: end to end layerNetwork layer provides best effort serviceThis lecture: some E2E propertiesAt Least OnceDuplicate ACK problemSolution: nonceEngineering a nonceAdaptive Timeout: Exponential weighted moving averagesAt Most Once ChallengesIdea: remember sequence numberProblem: failuresHow fast should the sender sends?Send a window of packetsSliding WindowThe Right Window Size“Negative” ACKE2E layer in InternetUDPTransmission Control Protocol (TCP)TCP headerClosing a TCP connectionMIT OpenCourseWarehttp://ocw.mit.edu 6.033 Computer System Engineering Spring 2009 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.L12: end to end layerDina KatabiSome slides are from lectures by Nick Mckeown, Ion Stoica, Frans Kaashoek, Hari Balakrishnan, Sam Madden, and Robert MorrisEnd-to-end layerstubstubNetwork LayerLink Layerpresentation LayerEnd-to-end layerRPC RPCHDHDHDHD HDHDHeaderData HeaderDataclient server•Packets may be:• Lossed• Delayed (jitter)•Duplicated • Reordered•…• Problem: Inconvenient service for applications• Solution: Design protocols for E2E modules• Many protocols/modules possible, depending on requirementsNetwork layer providesbest effort serviceThis lecture: some E2E properties•At most once•At least once• Exactly once?• Sliding window•Case study: TCP• Tomorrow: Network File System (NFS)At Least Once• Sender persistently sends until it receives an ack•Challenges:•Duplicate ACKs• What value for timerTimeout and Retransmissionan RTT client serverDataDataACKACKclient serverDataDataDataDataXDuplicate ACK problem• Problem: Request 2 is not delivered• violates at-least once deliverytimeout Client ServerReq1Req1Req1Req1ACKACKReq2Req2Req3Req3ACKACKSolution: nonce• Label request and ack with unique identifier that is never re-usedtimeout Client ServerReqN1ReqN1ReqN1ReqN1ACK N1ACK N1ReqN2ReqN2ReqN2ReqN2ACK N1ACK N1N1N2Engineering a nonce• Use sequence numbers• Challenges: •Wrap around?•Failures?Client ServerReq1Req1Req1Req1ACK 1ACK 1Req2Req2Req2Req2ACK 1ACK 112timeout• Fixed is bad. RTT changes depending on congestion• Pick a value that’s too big, wait too long to retransmit a packet • Pick a value too small, generates a duplicate (retransmitted packet).• Adapt the estimate of RTT Æ adaptive timeoutTimer valueAdaptive Timeout: Exponential weighted moving averages• Samples S1, S2, S3, ..•Algorithm• EstimatedRTT = T0• EstimatedRTT = α S + (1- α) EstimatedRTT•where 0 ≤α≤1• What values should one pick for α and T0?• Adaptive timeout is also hardAt Most Once Challengesclient serverReq1Req1req1req1OkACK 1OkACK 1ACK 1ACK 1• Server shouldn’t process req 1• Server should send result preferably12Process request 1Process request 1Idea: remember sequence numberclient serverReq1Req1req1req1OkACK 1OkACK 1• Server remembers also last few responses112OkACK 1OkACK 1OkACK 1OkACK 1Resend ACK 1Process request 1Problem: failuresclient serverReq1Req1req1req1OkACK 1OkACK 1• Performed request 1 twice!• How to maintain the last nonce per sender (tombstone)?• Write to non-volatile storage?• Move the problem? (e.g., different port number)• Make probability of mistake small?• How about exactly once? (Need transactions)112OkACK 1OkACK 1OkACK 1OkACK 1001OkACK 1OkACK 1How fast should the sender sends?• Waiting for acks is too slow• Throughput is one packet/RTT• Say packet is 500 bytes• RTT 100ms • Æ Throughput = 40Kb/s, Awful!• Overlap pkt transmissionHost A Host BData 1Data 1Data 2Data 2ACKACKSend a window of packets• Assume the receiver is the bottleneck• Maybe because the receiver is a slow machine• Receiver needs to tell the sender when and how much it can send•The window advances once all previous packets are acked Æ too slowHost A Host BSend?OK, 3 pktsIdle2-45-7Sliding Window•Senders advances the window whenever it receives an ack Æsliding window•But what is the right value for the window?Host A Host BSend?OK, 3 pktsIdle2-43-5The Right Window Size• Assume server is bottleneck• Goal: make idle time on server zero• Assume: server rate is B bytes/s• Window size = B x RTT• Danger: sequence number wrap around• What if network is bottleneck?• Many senders?• Sharing?•Next lecture“Negative” ACK• Minimize reliance on timer• Add sequence numbers to packets• Send a Nack when the receiver finds a hole in the sequence numbers• Difficulties•Reordering• Cannot eliminate acks, because we need to ack the last packetHost A Host BD1D2D3XD2D1D3D4Nack-2E2E layer in InternetNetworkLinkTransportThe 4-layer Internet modelApplicationHTTP, RTP, Sun RPC, …IPTCP or UDPEthernet, WiFI, ...End-to-End LayerUDPTransmission Control Protocol (TCP)Host A Host BSynxData x+1, acky+1ackx+1, synyx+1, y+1y, x+1x,?• Connection-oriented• Delivers bytes at-most-once• Bidirectional• ACKs are piggybackedTCP headerClosing a TCP connectionHost A Host Bfin xackx+1y, xx,yfin yack y+1timed waitclosedtimeoutclosedData exchange occurActive closeClosedListenListen(Start)EstablishedClosedClosingFIN WAIT 1Close WAITLast ACKTimeoutACKACKACKFIN/ACKFIN/ACKFIN/ACKSYN+ACK/ACKSYN/SYN+ACK (simultaneous open)Close/FINCloseConnect/SYN (step 1 of the 3 way handshake)(step 3 of the 3 way handshake)CloseACKClose/FINFIN+ACK/ACK(Go back to start)TIMED WAITClose/FINPassive closeFIN WAIT 2SYN Sent SEND/SYNSYNReceivedSYN/SYN+ACK (step 2 of the 3 way handshake)RSTUnusual event Client/reciever path Sender/server pathFigure by MIT
View Full Document
Unlocking...