Overview• User datagram protocol (UDP)• Packet checksums• Reliability: stop and wait, sliding window• TCP connection setup• TCP windows, retransmissions, andacknowledgmentsTransport Protocol Review• Transport protocols sit on top of the network layer(IP)• Provide application-level multiplexing (“ports”)and other servicesUDP – user datagram protocolSrcPort DstPortChecksumLengthData0 16 31• Unreliable and unordered datagram service• Adds multiplexing, checksum on whole packet• No flow control, reliability, or order guarantees• Endpoints identified by ports• Checksum aids in error detectionError detection• Transmission errors definitely happen- Cosmic rays, radio interference, etc.- If error probability is 2−30, that’s 1 error per 128 MB!• Some link-layer protocols provide error detection- But UDP/IP must work over many link layers- Not all links on a path may have error detection• Famous end-to-end argument:- Functions that can only be done right at endpointsshouldn’t be implemented inside the network- Error detection can only be done correctly end-to-end!• Example: Lost Multics source code- Link-layer had error detection, but transport protocol didn’t- Router had bad memory that corrupted bits- Packets didn’t get corrupted on the link, but in the router!Checksums• UDP detects errors with a checksum- Compute small checksum value, like a hash of the packet- If packet corrupted in transit, checksum likely to be wrong- Similar checksum on IP header, but doesn’t cover payload• Good checksum algorithms- Should detect errors that are likely to happen- Should be efficient to compute• IP uses 1s complement sum- Add all 16-bit words- Add any carry bits back in- Flip bits in sum to get checksum(Unless sum is 0xffff, then checksum just 0xffff)- Receiver sums whole packet (incl. sum), should get 0xffffUDP pseudo-headerSource Port Destination Port0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9 0 10 1 2 3Destination IP addressSource IP addressZero Protocol (=17) UDP lengthUDP Payload• Checksum actually includes “pseudo-header”- Not transmitted, just pre-pended to compute checksum- Ensures UDP checksum includes IP addresses• Trick question: Is UDP a layer on top of IP?How good is UDP/IP checksum?+ Very fast to compute in software- Same implementation works on big & little endian CPUs− 16 bits is not very long (misses 1/216errors)+ Checksum does catch any 1-bit error− But not any two-bit error- E.g., increment one word ending 0, decrement one ending 1− Checksum also optional on UDP- All 0s means no checksum calculated- If checksum word gets wiped to 0 as part of error, bad news• Good thing most link layers have stronger checksums• Next problem: If you discard bad packets, how toensure reliable delivery?Acknowledgements and Timeouts• Stop and wait approach- Send packet, wait- Receive packet, send ACK- Receive ACK, send next packet- Don’t receive ACK, timeout and retransmitFinite State Machines• Represent protocols using state machines- Sender and receiver each have a state machine- Start in some initial state- Events cause you to select a state transition• Transition specifies action taken- Specified as events/actions- E.g., software calls send/put packet on network- E.g., packet arrives/send acknowledgmentStop and wait FSMs• Receiver FSM:WaitforPacketsreceive packetsend ACKdeliver packet• Sender FSM:WaitforWaitforDataACKtimeoutre-send packetsend packetsoftware called sendreceived ACKΛProblems with Stop and Wait• Might duplicate packet• Can’t keep pipe full- To get good network utilization, must send at leastbandwidth-delay product unacknowledged bytesSender ReceiverFrameACKTimeoutTimeSender ReceiverFrameACKTimeoutFrameACKTimeoutSender ReceiverFrameACKTimeoutFrameACKTimeoutSender ReceiverFrameTimeoutFrameACKTimeout(a) (c)(b) (d)Duplicates• Solve problem with 1-bit counter- Place in both Frame and ACK- Receiver knows if duplicate of last frame- Sender won’t interpret duplicate oldACK as for new packet• This still requires some simplifyingassumptions- Network itself might duplicates packets- Packet might be heavily delayed andreordered- Assume these don’t happen for now- But usually prefer weaker assumption:Maximum Segment Lifetime (MSL)Sender ReceiverFrame 0ACK 0TimeFrame 1ACK 1 Frame 0ACK 0…Effect of RTT on performance• Stop & wait goodput depends on Round-Trip Time (RTT)- Capped by packet size/RTT regardless of underlying link b/w• Need pipelineing for goodput to approach link throughputSliding window protocol• Addresses problem of keeping the pipe full- Generalize previous protocol with > 1-bit counter- Allow multiple outstanding (unACKed) frames- Upper bound on unACKed frames, called windowSender ReceiverTime… …SW sender• Assign sequence number to each frame (SeqNum)• Maintain three state variables:- Send Window Size (SWS)- Last Acknowledgment Received (LAR)- Last Frame Sent (LFS)≤ SWSLARLFS… …• Maintain invariant: LFS − LAR ≤ SWS• Advance LAR when ACK arrives• Buffer up to SWS framesSW receiver• Maintain three state variables- Receive Window Size (RWS)- Largest Acceptable Frame (LAF)- Last Frame Received (LFR)≤ RWSLFRLAF… …• Maintain invariant: LAF − LFR ≤ RWS• When frame # SeqNum arrives:- if LFR < SeqNum ≤ LFA accept- if SeqNum ≤ LFR or SeqNum > LFA discarded• Send cumulative ACKs- I.e., ACK n means received all packets w. SeqNo ≤ n- E.g., if received packets 1, 2, 3, 5, must ACK 3Sequence number space• How big should RWS be?- At least 1. No bigger than SWS(don’t accept packet the sender shouldn’t have sent).• How many distinct sequence numbers needed?• If RWS=1, need at least SWS+1• If RWS=SWS, need at least 2SWS- Otherwise, bad news if ACKs are lost- Sender may retransmit a window that was already received- Receiver will think retransmissions are from next window• Generally RWS+SWS+1- RWS packets in unknown state (ACK may/may not be lost)- SWS packets in flight must not overflow sequence spaceHigh-level view of TCPApplication processWritebytesTCPSend bufferSegment Segment SegmentTransmit segmentsApplication processReadbytesTCPReceive buffer………• Full duplex, connection-oriented byte stream• Flow control- If one end stops reading, writes at other eventuall block/fail• Congestion control- Keeps sender from overrunning network [more next lecture]TCP segment0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 90 1 2 3 4
View Full Document
Unlocking...