L12: end to end layerSlide 2Network layer provides best effort serviceThis lecture: some E2E propertiesAt Least OnceDuplicate ACK problemSolution: nonceEngineering a nonceRTT Measurements (collected by Caida)Adaptive 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 connectionSlide 25L12: end to end layerDina Katabi6.033 Spring 2007http://web.mit.edu/6.033Some 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 Retransmission an RTT client serverDataDataACKACKclient serverDataDataDataDataXDuplicate ACK problem•Problem: Request 2 is not delivered•violates at-least once delivery timeout Client ServerReq 1Req 1Req 1Req 1ACKACKReq 2Req 2Req 3Req 3ACKACKSolution: nonce•Label request and ack with unique identifier that is never re-used timeout Client ServerReq N1Req N1Req N1Req N1ACK N1ACK N1Req N2Req N2Req N2Req N2ACK N1ACK N1N1N2Engineering a nonce•Use sequence numbers•Challenges: •Wrap around?•Failures?Client ServerReq 1Req 1Req 1Req 1ACK 1ACK 1Req 2Req 2Req 2Req 2ACK 1ACK 112 timeout•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 valueRTT Measurements(collected by Caida)Adaptive 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 serverReq 1Req 1req 1req 1OkACK 1OkACK 1ACK 1ACK 1•Server shouldn’t process req 1•Server should send result preferably12Process request 1Process request 1Idea: remember sequence numberclient serverReq 1Req 1req 1req 1OkACK 1OkACK 1•Server remembers also last few responses112OkACK 1OkACK 1OkACK 1OkACK 1Resend ACK 1Process request 1Problem: failuresclient serverReq 1Req 1req 1req 1OkACK 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 slow Host 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 BD1D2D3D1D3XD2D4Nack-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 BSyn xData x+1, ack y+1ack x+1, syn yy, x+1x,?x+1, y+1•Connection-oriented•Delivers bytes at-most-once•Bidirectional•ACKs are piggybackedTCP headerClosing a TCP connectionHost A Host Bfn xack x+1y, xx,yfn yack y+1closedtimed
View Full Document