11Reliability & Flow ControlSome slides are from lectures by Nick Mckeown, Ion Stoica, FransKaashoek, Hari Balakrishnan, and Sam MaddenProf. Dina KatabiRead 7.E2Previous Lecture How the link layer delivers data over a link How the network layer performs routing andforwarding Hierarchical Routing and Addressing3Hierarchical Routing Internet: collection of domains/networks Inside a domain: Route over a graph of routers Between domains: Route over a graph of domains Address: concatenation of “Domain Id”, “Node Id”domain-1domain-2domain-3Interior router Border router4Hierarchical RoutingAdvantage scalable Smaller tables Smaller messages Delegation Each domain can run its ownrouting protocolDisadvantage Mobility is difficult Address depends on geographic location Sup-optimal paths E.g., in the figure, the shortest path between the two machines shouldtraverse the yellow domain. But hierarchical routing goes directlybetween the green and blue domains, then finds the local destination path traverses more routers.5This Lecture Transport Layer Reliable data transmission Flow Control Multiplexing6Review of the Transport LayerDina NickAthena.MIT.eduLeland.Stanford.eduNetwork LayerLink LayerApplication LayerTransport LayerO.S. O.S.HDHDHDHD HDHDHead e rData Head e rData27LayeringNetworkLinkTransportThe 4-layer Internet modelApplicationHTTP, FTPIPTCPEthernetEnd-to-EndLayer8 Network layer provides best-effort service Loss, delay, jitter, duplicates, reordering, … Not convenient for applications Transport layer builds on the best effort service toprovide applications with a convenient environment Reliability:• at least once• at most once Performance:• flow and congestion control Ordering Data integrity (checksum) Timeliness (remove jitter) Also transport provides multiplexing betweenmultiple applicationsTransport Layer9This Lecture Transport Layer Reliable data transmission Flow Control Multiplexing10At Least Once Sender persistently sends until it receives an ack How long should the timeout be? Fixed is bad. RTT changes depending on congestion• Pick a values that’s too big and it will wait too long to retransmit a packet,• Pick a value too small, and it will unnecessarily retransmit packets. Adapt the estimate of RTT adaptive timeoutTimeout andRetransmission an RTTHost A Host BData 1Data 2ACKHost A Host BData 1Data 1X11RTT Measurements(collected by Caida)12Adaptive Timeout 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 hard313Different Approach: NACK Minimize reliance on timer Add sequence numbers topackets Send a Nack when thereceiver finds a hole in thesequence numbers Difficulties Reordering Cannot eliminate acks, becausewe need to ack the last packetHost A Host BD1D2D3D1D3XD2D4Nack-214At Most Once Suppress duplicates Packets must have ids to allow the receiver todistinguish a duplicate from a new packet Receiver should keep track of which packet idshave been delivered to applications To simplify tracking, senders pick monotonicallyincreasing packet ids, i.e., sequence numbers Receiver delivers packets to application in order.It keeps track of the largest id delivered so far15This Lecture Transport Layer Reliable data transmission Flow Control Multiplexing16How fast should the sender sends? Waiting for acks is too slow Throughput is one packet/RTT Say packet is 500B RTT 100ms Throughput = 40Kb/s, Awful! Overlap pkt transmissionHost A Host BData 1Data 2ACK17Send a window of packets Assume the receiver isthe bottleneck Maybe because thereceiver is a slowmachine Receiver needs to tellthe sender when andhow much it can send The window advancesonce all previouspackets are acked too slowHost A Host BSend?OK, 3 pktsIdle2-45-718Sliding Window Senders advances thewindow whenever itreceives an ack sliding window But what is the rightvalue for the window?Host A Host BSend?OK, 3 pktsIdle2-43-5419The Right Window Size Note that if W/RTT < Bottleneck Capacity under utilization If W/RTT > Bottleneck Capacity Large queues20This Lecture Transport Layer Reliable data transmission Flow Control Multiplexing21Multiplexing by TransportApp AppA1 A2App AppB1 B2TCPTransport Layer Multiple applications run on the same machine but use different portsNetwork LayerP1D P2DP1DHP1D
View Full Document
Unlocking...