CSE 123bCSE 123bCommunications SoftwareCommunications SoftwareSpring 2004Spring 2004Lecture 3: Reliable CommunicationsLecture 3: Reliable CommunicationsStefan SavageStefan SavageSome images courtesy David Wetherall and Van JacobsenApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 2AdministrativaAdministrativaz Home page is up and working◆ http://www-cse.ucsd.edu/classes/sp04/cse123B/◆ Also linked off dept page and my home page◆ Class notes includedz First homework will be assigned next Tuesdayz This week my office hours are changed to Th3-4pmApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 3Last TimeLast Timez We talked about the network layer (IP) and internetworking.z We assume: the network provides best-effort (i.e. unreliable) delivery of packets from one host to another◆ How that is done, routing, is left for a future classApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 4Today’s classToday’s classz We begin on the transport layer◆ Builds on the services of the Network layer◆ Communication between processes running on hostsz Principle focus◆ How do we ensure that a message is reliablycommunicated from one host to another?z Topics◆ ARQ◆ Sliding windows◆ Retransmission timersApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 5Thought experimentThought experimentz You want to send a long letter to your friend z All you have (and all your friend has) is postcardsz Postcards get lost in the mail, delayed, damaged, reorderedz How do you send the letter?April 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 6Reliable TransmissionReliable Transmissionz How do we reliably send a message when packets can be lost in the network?z Some options◆ Detect a loss and retransmit (Cerf&Kahn74, and others)◆ Send redundantly (Byers et al.98, and others)April 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 7Automatic Repeat Request Automatic Repeat Request (ARQ)(ARQ)z Packets can be corrupted or lost. How do we add reliability?z Acknowledgments (ACKs) and retransmissions after a timeoutz ARQ is generic name for protocols based on this strategySender ReceiverDataACKTimeoutTimeSender ReceiverDataTimeoutData (rexmit)ACKTimeoutApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 8The Need for Sequence The Need for Sequence NumbersNumbersz In the case of ACK loss (or short timeout) the receiver can’t distinguish this message from the next◆ Need to understand how many packets can be outstanding and number the packets; here, a single bit will doSender ReceiverDataACKTimeoutData (rexmit)ACKTimeoutSender ReceiverDataACKTimeoutData (rexmit)ACKTimeoutApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 9StopStop--andand--WaitWaitz Only one outstanding packet at a timez Also called alternating bit protocol0101SenderReceiver0110April 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 10How does receiver recognize How does receiver recognize a duplicate?a duplicate?z Sequence # in packet is finitez How many bits do we need?◆ One bit for stop and wait◆ Won’t send seq #1 until receive ACK for seq #0◆ Only allows one packet in flightPkt0ACK 0Pkt0ACK 1Pkt1ACK 0T imeoutApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 11What if packets are delayed?What if packets are delayed?z Never reuse a seq #? Finite…z Require in order delivery?z Prevent very late delivery?◆ TTL: Decrement hop count per packet, discard if exceeded◆ Seq #s not reused within delay boundz Trust issues?001100Accept!Reject!April 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 12What happens if a machine What happens if a machine crashes?crashes?z How do we distinguish packets sent before and after reboot? Which seq# to use?z Solutions◆ Restart sequence # at 0?◆ Assume boot takes max packet delay?◆ Choose seq # at random and hope?◆ Use stable storage and increment high order bits of seq # on every bootz Reality: People don’t worry about this◆ Slow reboots, explicit connection management, tolerant usersApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 13Limitations of StopLimitations of Stop--andand--WaitWaitz Lousy performance if wire time << prop. delay◆ How bad? z Want to utilize all available bandwidth◆ Need to keep more data “in flight”◆ How much? Remember the bandwidth-delay product?z Also limited by quality of timeout (how long?)April 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 14Pipelined transmissionPipelined transmissionz Send multiple packets without waiting for the first to be ACKedz Reliable, unordered delivery:◆ Send new packet after each ACK◆ Sender keeps list of unACK’ed packets and resends after timeout◆ Receiver same as stop & waitz Prob: What if packet #2 keeps being lost?◆ Receiver must buffer all packets after 2◆ Potential buffer overflowApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 15Sliding Window Sliding Window ––SenderSenderz Window bounds outstanding data◆ Implies need for buffering at senderz “Last” ACK applies to in-order dataz What to do on a timeout?◆ Go-Back-N: one timer, send all unacknowledged data on timeout◆ Selective Repeat: timer per packet, resend as needed≤Window Size“Last” ACK Last Sent……Sender:April 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 16Sliding Window Sliding Window ––ReceiverReceiverz Receiver buffers too:◆ data may arrive out-of-order◆ or faster than can be consumed (flow control)z Receiver ACK choices:◆ Individual, Cumulative (TCP), Selective (newer TCP), Negative≤Receive Window“Last” Received Largest Accepted……Receiver:April 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 17Sliding Window Sliding Window ––TimelineTimelineSender ReceiverTime……April 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 18Sliding Window FunctionsSliding Window Functionsz Sliding window is a mechanismz It supports multiple functions:z Reliable deliveryz In-order deliveryz Flow controlApril 6, 2004 CSE 123b -- Lecture 3 – Reliable Transmission 19Deciding When to RetransmitDeciding When to Retransmitz How do you know when a packet has been lost?◆ Ultimately sender uses timers to decide when to retransmitz But how long should the timer be?◆ Too long: inefficient (large delays, poor use of bandwidth)◆ Too short: may retransmit unnecessarily (causing extra traffic)z Right timer is based on the round trip time (RTT)◆