DOC PREVIEW
CMU 15441 Computer Networking - 17-congctl

This preview shows page 1-2-3-20-21-40-41-42 out of 42 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 42 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 42 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 42 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 42 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 42 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 42 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 42 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 42 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 42 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 4415-441 Computer NetworkingLecture 17 – TCP & Congestion Control2Lecture 17: TCP & Congestion ControlGood Ideas So Far…•Flow control•Stop & wait•Parallel stop & wait•Sliding window•Loss recovery•Timeouts•Acknowledgement-driven recovery (selective repeat or cumulative acknowledgement)3Lecture 17: TCP & Congestion ControlOutline•TCP flow control•Congestion sources and collapse•Congestion control basics4Lecture 17: TCP & Congestion ControlSequence Numbers (reminder)•How large do sequence numbers need to be?•Must be able to detect wrap-around•Depends on sender/receiver window size•E.g.•Max seq = 7, send win=recv win=7•If pkts 0..6 are sent succesfully and all acks lost•Receiver expects 7,0..5, sender retransmits old 0..6!!!•Max sequence must be ≥ send window + recv window5Lecture 17: TCP & Congestion ControlSequence Numbers•32 Bits, Unsigned  for bytes not packets!•Circular Comparison•Why So Big?•For sliding window, must have |Sequence Space| > |Sending Window| + |Receiving Window|•No problem•Also, want to guard against stray packets•With IP, packets have maximum lifetime of 120s•Sequence number would wrap around in this time at 286MB/s =~ 2.3Gbit/s (hmm!)0Maxaba < b0Maxbab < a6Lecture 17: TCP & Congestion ControlTCP Flow Control•TCP is a sliding window protocol•For window size n, can send up to n bytes without receiving an acknowledgement •When the data is acknowledged then the window slides forward•Each packet advertises a window size•Indicates number of bytes the receiver has space for•Original TCP always sent entire window•But receiver buffer space != available net. capacity!•Congestion control now limits this•window = min(receiver window, congestion window)7Lecture 17: TCP & Congestion ControlWindow Flow Control: Send SideSent but not acked Not yet sentwindowNext to be sentSent and acked8Lecture 17: TCP & Congestion Controlacknowledged sent to be sent outside windowSource Port Dest. PortSequence NumberAcknowledgmentHL/Flags WindowD. Checksum Urgent PointerOptions…Source Port Dest. PortSequence NumberAcknowledgmentHL/Flags WindowD. Checksum Urgent PointerOptions...Packet SentPacket ReceivedApp writeWindow Flow Control: Send Side9Lecture 17: TCP & Congestion ControlAcked but notdelivered to userNot yetackedReceive bufferwindowWindow Flow Control: Receive SideNewWhat should receiver do?10Lecture 17: TCP & Congestion ControlTCP Persist•What happens if window is 0?•Receiver updates window when application reads data•What if this update is lost?•TCP Persist state•Sender periodically sends 1 byte packets•Receiver responds with ACK even if it can’t store the packet11Lecture 17: TCP & Congestion ControlPerformance Considerations•The window size can be controlled by receiving application•Can change the socket buffer size from a default (e.g. 8-64Kbytes) to some maximum value•Modern TCPs (linux, bsd, os x) may auto-tune•Historical source of performance problems on fast nets•The window size field in the TCP header limits the window that the receiver can advertise•16 bits  64 KBytes•10 msec RTT  51 Mbit/second•100 msec RTT  5 Mbit/second•TCP options to get around 64KB limit  increases above limit12Lecture 17: TCP & Congestion ControlOutline•TCP flow control•Congestion sources and collapse•Congestion control basics13Lecture 17: TCP & Congestion ControlInternet Pipes?•How should you control the faucet?14Lecture 17: TCP & Congestion ControlInternet Pipes?•How should you control the faucet?•Too fast – sink overflows!15Lecture 17: TCP & Congestion ControlInternet Pipes?•How should you control the faucet?•Too fast – sink overflows!•Too slow – what happens?16Lecture 17: TCP & Congestion ControlInternet Pipes?•How should you control the faucet?•Too fast – sink overflows•Too slow – what happens?•Goals•Fill the bucket as quickly as possible•Avoid overflowing the sink•Solution – watch the sink17Lecture 17: TCP & Congestion ControlPlumbers Gone Wild!•How do we prevent water loss?•Know the size of the pipes?18Lecture 17: TCP & Congestion ControlPlumbers Gone Wild 2!•Now what?•Feedback from the bucket or the funnels?19Lecture 17: TCP & Congestion ControlCongestion•Different sources compete for resources inside network•Why is it a problem?•Sources are unaware of current state of resource•Sources are unaware of each other•Manifestations:•Lost packets (buffer overflow at routers)•Long delays (queuing in router buffers)•Can result in throughput less than bottleneck link (1.5Mbps for the above topology)  a.k.a. congestion collapse10 Mbps100 Mbps1.5 Mbps20Lecture 17: TCP & Congestion ControlCauses & Costs of Congestion•Four senders – multihop paths•Timeout/retransmitQ: What happens as rate increases?21Lecture 17: TCP & Congestion ControlCauses & Costs of Congestion•When packet dropped, any “upstream transmission capacity used for that packet was wasted!22Lecture 17: TCP & Congestion ControlCongestion Collapse•Definition: Increase in network load results in decrease of useful work done•Many possible causes•Spurious retransmissions of packets still in flight•Classical congestion collapse•How can this happen with packet conservation? RTT increases!•Solution: better timers and TCP congestion control•Undelivered packets•Packets consume resources and are dropped elsewhere in network•Solution: congestion control for ALL traffic23Lecture 17: TCP & Congestion ControlCongestion Control and Avoidance•A mechanism that:•Uses network resources efficiently•Preserves fair network resource allocation•Prevents or avoids collapse•Congestion collapse is not just a theory•Has been frequently observed in many networks24Lecture 17: TCP & Congestion ControlApproaches Towards Congestion Control•End-end congestion control:•No explicit feedback from network•Congestion inferred from end-system observed loss, delay•Approach taken by TCP•Network-assisted congestion control:•Routers provide feedback to end systems•Single bit indicating congestion (SNA, DECbit, TCP/IP


View Full Document

CMU 15441 Computer Networking - 17-congctl

Documents in this Course
Lecture

Lecture

14 pages

Lecture

Lecture

19 pages

Lecture

Lecture

14 pages

Lecture

Lecture

78 pages

Lecture

Lecture

35 pages

Lecture

Lecture

4 pages

Lecture

Lecture

4 pages

Lecture

Lecture

29 pages

Lecture

Lecture

52 pages

Lecture

Lecture

40 pages

Lecture

Lecture

44 pages

Lecture

Lecture

41 pages

Lecture

Lecture

38 pages

Lecture

Lecture

40 pages

Lecture

Lecture

13 pages

Lecture

Lecture

47 pages

Lecture

Lecture

49 pages

Lecture

Lecture

7 pages

Lecture

Lecture

18 pages

Lecture

Lecture

15 pages

Lecture

Lecture

74 pages

Lecture

Lecture

35 pages

Lecture

Lecture

17 pages

lecture

lecture

13 pages

Lecture

Lecture

21 pages

Lecture

Lecture

14 pages

Lecture

Lecture

53 pages

Lecture

Lecture

52 pages

Lecture

Lecture

40 pages

Lecture

Lecture

11 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Lecture

Lecture

10 pages

Lecture

Lecture

40 pages

Lecture

Lecture

25 pages

lecture

lecture

11 pages

lecture

lecture

7 pages

Lecture

Lecture

10 pages

lecture

lecture

46 pages

lecture

lecture

7 pages

Lecture

Lecture

8 pages

lecture

lecture

55 pages

lecture

lecture

45 pages

lecture

lecture

47 pages

lecture

lecture

39 pages

lecture

lecture

33 pages

lecture

lecture

38 pages

lecture

lecture

9 pages

midterm

midterm

16 pages

Lecture

Lecture

39 pages

Lecture

Lecture

14 pages

Lecture

Lecture

46 pages

Lecture

Lecture

8 pages

Lecture

Lecture

40 pages

Lecture

Lecture

11 pages

Lecture

Lecture

41 pages

Lecture

Lecture

38 pages

Lecture

Lecture

9 pages

Lab

Lab

3 pages

Lecture

Lecture

53 pages

Lecture

Lecture

51 pages

Lecture

Lecture

38 pages

Lecture

Lecture

42 pages

Lecture

Lecture

49 pages

Lecture

Lecture

63 pages

Lecture

Lecture

7 pages

Lecture

Lecture

51 pages

Lecture

Lecture

35 pages

Lecture

Lecture

29 pages

Lecture

Lecture

65 pages

Lecture

Lecture

47 pages

Lecture

Lecture

41 pages

Lecture

Lecture

41 pages

Lecture

Lecture

32 pages

Lecture

Lecture

35 pages

Lecture

Lecture

15 pages

Lecture

Lecture

52 pages

Lecture

Lecture

16 pages

Lecture

Lecture

4 pages

lecture

lecture

27 pages

lecture04

lecture04

46 pages

Lecture

Lecture

46 pages

Lecture

Lecture

13 pages

lecture

lecture

41 pages

lecture

lecture

38 pages

Lecture

Lecture

40 pages

Lecture

Lecture

25 pages

Lecture

Lecture

38 pages

lecture

lecture

11 pages

Lecture

Lecture

42 pages

Lecture

Lecture

12 pages

Lecture

Lecture

36 pages

Lecture

Lecture

46 pages

Lecture

Lecture

35 pages

Lecture

Lecture

34 pages

Lecture

Lecture

9 pages

lecture

lecture

49 pages

class03

class03

39 pages

Lecture

Lecture

8 pages

Lecture 8

Lecture 8

42 pages

Lecture

Lecture

20 pages

lecture

lecture

29 pages

Lecture

Lecture

9 pages

lecture

lecture

46 pages

Lecture

Lecture

12 pages

Lecture

Lecture

24 pages

Lecture

Lecture

41 pages

Lecture

Lecture

37 pages

lecture

lecture

59 pages

Lecture

Lecture

47 pages

Lecture

Lecture

34 pages

Lecture

Lecture

38 pages

Lecture

Lecture

28 pages

Exam

Exam

17 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

9 pages

Project

Project

20 pages

Lecture

Lecture

40 pages

L13b_Exam

L13b_Exam

17 pages

Lecture

Lecture

48 pages

Lecture

Lecture

10 pages

Lecture

Lecture

52 pages

21-p2p

21-p2p

16 pages

lecture

lecture

77 pages

Lecture

Lecture

18 pages

Lecture

Lecture

62 pages

Lecture

Lecture

25 pages

Lecture

Lecture

24 pages

Project

Project

20 pages

Lecture

Lecture

47 pages

Lecture

Lecture

38 pages

Lecture

Lecture

35 pages

Roundup

Roundup

45 pages

Lecture

Lecture

47 pages

Lecture

Lecture

39 pages

Lecture

Lecture

13 pages

Midterm

Midterm

22 pages

Project

Project

26 pages

Lecture

Lecture

11 pages

Project

Project

27 pages

Lecture

Lecture

10 pages

Lecture

Lecture

50 pages

Lab

Lab

9 pages

Lecture

Lecture

30 pages

Lecture

Lecture

6 pages

r05-ruby

r05-ruby

27 pages

Lecture

Lecture

8 pages

Lecture

Lecture

28 pages

Lecture

Lecture

30 pages

Project

Project

13 pages

Lecture

Lecture

11 pages

Lecture

Lecture

12 pages

Lecture

Lecture

48 pages

Lecture

Lecture

55 pages

Lecture

Lecture

36 pages

Lecture

Lecture

17 pages

Load more
Download 17-congctl
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 17-congctl 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 17-congctl 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?