DOC PREVIEW
CMU CS 15744 - r02-review-transport

This preview shows page 1-2-3-4-30-31-32-33-34-61-62-63-64 out of 64 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 64 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

15-744 Computer NetworkingOutlineTransport ProtocolsFunctionality SplitSlide 5UDP: User Datagram Protocol [RFC 768]UDP, cont.UDP ChecksumHigh-Level TCP CharacteristicsTCP HeaderEvolution of TCPTCP Through the 1990sSlide 13Stop and WaitRecovering from ErrorProblems with Stop and WaitHow to Recognize Resends?How to Keep the Pipe Full?Sliding WindowSender/Receiver StateSequence NumbersWindow Sliding – Common CaseLoss RecoveryGo-Back-N in ActionImportant LessonsGood Ideas So Far…Slide 27More on Sequence NumbersTCP Flow ControlWindow Flow Control: Send SideSlide 31Performance ConsiderationsSlide 33Establishing Connection: Three-Way handshakeSlide 35Reliability ChallengesTCP = Go-Back-N VariantRound-trip Time EstimationOriginal TCP Round-trip EstimatorRTT Sample AmbiguityJacobson’s Retransmission TimeoutTimestamp ExtensionTimer GranularityFast Retransmit -- Avoiding TimeoutsFast RetransmitTCP (Reno variant)SACKSACKPerformance IssuesSlide 50Slide 51Internet Pipes?Slide 53Slide 54Slide 55Plumbers Gone Wild!Plumbers Gone Wild 2!CongestionCongestion CollapseCongestion Control and AvoidanceApproaches Towards Congestion ControlExample: TCP Congestion ControlSlide 63Slide 6415-744 Computer NetworkingReview 2 – Transport Protocols2Outline•Transport introduction•Error recovery & flow control3Transport Protocols•Lowest level end-to-end protocol.•Header generated by sender is interpreted only by the destination•Routers view transport header as part of the payload•Not always true…•Firewalls776655776655TransportTransportIPIPDatalinkDatalinkPhysicalPhysicalTransportTransportIPIPDatalinkDatalinkPhysicalPhysicalIPIProuter222211114Functionality Split•Network provides best-effort delivery•(Hmm, does it anymore? More on this in a few weeks)•End-systems implement many functions•Reliability•In-order delivery•Demultiplexing•Message boundaries•Connection abstraction•Congestion control•…5Transport Protocols•UDP provides just integrity and demux•TCP adds…•Connection-oriented•Reliable•Ordered•Byte-stream•Full duplex•Flow and congestion controlled•DCCP, RTP, SCTP -- not widely used.6UDP: User Datagram Protocol [RFC 768]•“No frills,” “bare bones” Internet transport protocol•“Best effort” service, UDP segments may be:•Lost•Delivered out of order to app•Connectionless:•No handshaking between UDP sender, receiver•Each UDP segment handled independently of othersWhy is there a UDP?•No connection establishment (which can add delay)•Simple: no connection state at sender, receiver•Small header•No congestion control: UDP can blast away as fast as desired7UDP, cont.•Often used for streaming multimedia apps•Loss tolerant•Rate sensitive•Other UDP uses (why?):•DNS•Reliable transfer over UDP•Must be at application layer•Application-specific error recoverySource port # Dest port #32 bitsApplicationdata (message)UDP segment formatLengthChecksumLength, inbytes of UDPsegment,includingheader8UDP ChecksumSender:•Treat segment contents as sequence of 16-bit integers•Checksum: addition (1’s complement sum) of segment contents•Sender puts checksum value into UDP checksum fieldReceiver:•Compute checksum of received segment•Check if computed checksum equals checksum field value:•NO - error detected•YES - no error detectedBut maybe errors nonetheless? Goal: detect “errors” (e.g., flipped bits) in transmitted segment – optional use!9High-Level TCP Characteristics•Protocol implemented entirely at the ends•Fate sharing (on IP)•Protocol has evolved over time and will continue to do so•Nearly impossible to change the header•Use options to add information to the header•Change processing at endpoints•Backward compatibility is what makes it TCP10TCP HeaderSource port Destination portSequence numberAcknowledgementAdvertised windowHdrLenFlags0Checksum Urgent pointerOptions (variable)DataFlags:SYNFINRESETPUSHURGACK11Evolution of TCP1975 1980198519901982TCP & IPRFC 793 & 7911974TCP described byVint Cerf and Bob KahnIn IEEE Trans Comm1983BSD Unix 4.2supports TCP/IP1984Nagel’s algorithmto reduce overheadof small packets;predicts congestion collapse1987Karn’s algorithmto better estimate round-trip time1986Congestion collapseobserved1988Van Jacobson’s algorithmscongestion avoidance and congestion control(most implemented in 4.3BSD Tahoe)19904.3BSD Renofast retransmitdelayed ACK’s1975Three-way handshakeRaymond TomlinsonIn SIGCOMM 7512TCP Through the 1990s1993199419961994ECN(Floyd)Explicit CongestionNotification1993TCP Vegas (Brakmo et al)delay-based congestion avoidance1994T/TCP(Braden)TransactionTCP1996SACK TCP(Floyd et al)Selective Acknowledgement1996HoeNewReno startup and loss recovery1996FACK TCP(Mathis et al)extension to SACK13Outline•Transport introduction•Error recovery & flow control14Stop and WaitTimePacketACKTimeout•ARQ•Receiver sends acknowledgement (ACK) when it receives packet•Sender waits for ACK and timeouts if it does not arrive within some time period•Simplest ARQ protocol•Send a packet, stop and wait until ACK arrives Sender Receiver15Recovering from ErrorPacketACKTimeoutPacketACKTimeoutPacketTimeoutPacketACKTimeoutTimePacketACKTimeoutPacketACKTimeoutACK lost Packet lostEarly timeoutDUPLICATEPACKETS!!!16•How to recognize a duplicate•Performance•Can only send one packet per round tripProblems with Stop and Wait17How to Recognize Resends?•Use sequence numbers•both packets and acks•Sequence # in packet is finite  How big should it be? •For stop and wait?•One bit – won’t send seq #1 until received ACK for seq #0Pkt 0ACK 0Pkt 0ACK 1Pkt 1ACK 018How to Keep the Pipe Full?•Send multiple packets without waiting for first to be acked•Number of pkts in flight = window: Flow control•Reliable, unordered delivery•Several parallel stop & waits•Send new packet after each ack•Sender keeps list of unack’ed packets; resends after timeout•Receiver same as stop & wait•How large a window is needed?•Suppose 10Mbps link, 4ms delay, 500byte pkts•1? 10? 20?•Round trip delay * bandwidth = capacity of pipe19Sliding Window•Reliable, ordered delivery•Receiver has to hold onto a packet until all prior packets have arrived•Why might this be difficult for just parallel stop & wait?•Sender must prevent buffer overflow at receiver•Circular buffer at sender and receiver•Packets in transit  buffer size •Advance when sender and receiver


View Full Document

CMU CS 15744 - r02-review-transport

Documents in this Course
Lecture

Lecture

25 pages

Lecture

Lecture

10 pages

Lecture

Lecture

10 pages

Lecture

Lecture

45 pages

Lecture

Lecture

48 pages

Lecture

Lecture

19 pages

Lecture

Lecture

97 pages

Lecture

Lecture

39 pages

Lecture

Lecture

49 pages

Lecture

Lecture

33 pages

Lecture

Lecture

21 pages

Lecture

Lecture

52 pages

Problem

Problem

9 pages

Lecture

Lecture

6 pages

03-BGP

03-BGP

13 pages

Lecture

Lecture

42 pages

lecture

lecture

54 pages

lecture

lecture

21 pages

Lecture

Lecture

18 pages

Lecture

Lecture

18 pages

Lecture

Lecture

58 pages

lecture

lecture

17 pages

lecture

lecture

46 pages

Lecture

Lecture

72 pages

Lecture

Lecture

44 pages

Lecture

Lecture

13 pages

Lecture

Lecture

22 pages

Lecture

Lecture

48 pages

lecture

lecture

73 pages

17-DNS

17-DNS

52 pages

Lecture

Lecture

10 pages

lecture

lecture

53 pages

lecture

lecture

51 pages

Wireless

Wireless

27 pages

lecture

lecture

14 pages

lecture

lecture

18 pages

Lecture

Lecture

16 pages

Lecture

Lecture

14 pages

lecture

lecture

16 pages

Lecture

Lecture

16 pages

Lecture

Lecture

37 pages

Lecture

Lecture

44 pages

Lecture

Lecture

11 pages

Lecture

Lecture

61 pages

Multicast

Multicast

61 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

81 pages

Lecture

Lecture

9 pages

Lecture

Lecture

6 pages

Lecture

Lecture

63 pages

Lecture

Lecture

13 pages

Lecture

Lecture

63 pages

Lecture

Lecture

50 pages

lecture

lecture

35 pages

Lecture

Lecture

47 pages

Lecture

Lecture

29 pages

Lecture

Lecture

92 pages

Load more
Download r02-review-transport
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view r02-review-transport and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view r02-review-transport 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?