New version page

CMU 15441 Computer Networking - Lecture

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

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
Upgrade to remove ads

This preview shows page 1-2-3 out of 9 pages.

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

Upgrade to remove ads
Unformatted text preview:

115-441 Computer NetworkingLecture 19 – TCP PerformanceOutlineTCP ti id•TCP congestion avoidance• TCP slow start11-01-07Lecture 19: TCP Congestion Control 2• TCP modelingAdditive Increase/Decrease• Both X1and X2increase/ decrease T0T1Fairness LineUser 2’s Allocation x2by the same amount over time• Additive increase improves fairness and additive decrease reduces fairness11-01-07Lecture 19: TCP Congestion Control 3Efficiency LineUser 1’s Allocation x1Muliplicative Increase/Decrease• Both X1and X2increase by theincrease by the same factor over time• Extension from origin – constant fairnessT0T1Fairness LineUser 2’s Allocation x211-01-07Lecture 19: TCP Congestion Control 4Efficiency LineUser 1’s Allocation x12What is the Right Choice?• Constraints limit tAIMDus to AIMD• Improves or keeps fairness constant at each step• AIMD moves x0x1x2Fairness LineUser 2’s Allocation x211-01-07Lecture 19: TCP Congestion Control 5towards optimal pointEfficiency LineUser 1’s Allocation x1TCP Congestion Control• Changes to TCP motivated by ARPANET congestion collapsecongestion collapse• Basic principles• AIMD• Packet conservation•Reaching steady state quickly11-01-07Lecture 19: TCP Congestion Control 6Reaching steady state quickly• ACK clockingAIMD• Distributed, fair and efficient• Packet loss is seen as sign of congestion and results in a ggmultiplicative rate decrease • Factor of 2• TCP periodically probes for available bandwidth by increasing its rate11-01-07Lecture 19: TCP Congestion Control 7TimeRateImplementation Issue• Operating system timers are very coarse – how to pace packets out smoothly?py• Implemented using a congestion window that limits how much data can be in the network.• TCP also keeps track of how much data is in transit• Data can only be sent when the amount of outstanding data is less than the congestion window.•The amount of outstanding data is increased on a“send”and11-01-07Lecture 19: TCP Congestion Control 8The amount of outstanding data is increased on a send and decreased on “ack”• (last sent – last acked) < congestion window• Window limited by both congestion and buffering• Sender’s maximum window = Min (advertised window, cwnd)3Congestion Avoidance• If loss occurs when cwnd = W•Network can handle 0.5W~W segmentsNetwork can handle 0.5W W segments• Set cwnd to 0.5W (multiplicative decrease)• Upon receiving ACK• Increase cwnd by (1 packet)/cwnd• What is 1 packet? Æ 1 MSS worth of bytes• After cwnd packets have passed by Æ approximately increase f1MSS11-01-07Lecture 19: TCP Congestion Control 9of 1 MSS• Implements AIMDCongestion Avoidance Sequence PlotSequence No11-01-07Lecture 19: TCP Congestion Control 10TimePacketsAcksCongestion Avoidance BehaviorCongestionWindow11-01-07Lecture 19: TCP Congestion Control 11TimePacket loss+ retransmitGrabbingback BandwidthCutCongestionWindowand RatePacket Conservation• At equilibrium, inject packet into network only when one is removedwhen one is removed• Sliding window and not rate controlled• But still need to avoid sending burst of packets Æwould overflow links• Need to carefully pace out packets• Helps provide stability Ndli i i i i11-01-07Lecture 19: TCP Congestion Control 12•Need to eliminate spurious retransmissions• Accurate RTO estimation• Better loss recovery techniques (e.g. fast retransmit)4TCP Packet Pacing• Congestion window helps to “pace” the transmission of data packetsp• In steady state, a packet is sent when an ack is received• Data transmission remains smooth, once it is smooth• Self-clocking behaviorPPb11-01-07Lecture 19: TCP Congestion Control 13PrArAbReceiverSenderAsHow to Change Window• When a loss occurs have W packets outstanding•New cwnd = 0 5*cwnd•New cwnd = 0.5 cwnd• How to get to new state without losing ack clocking?11-01-07Lecture 19: TCP Congestion Control 14Fast Recovery• Each duplicate ack notifies sender that single packet has cleared networkp• When < cwnd packets are outstanding• Allow new packets out with each new duplicate acknowledgement• Behavior• Sender is idle for some time – waiting for ½ cwnd worth of dupacks11-01-07Lecture 19: TCP Congestion Control 15of dupacks• Transmits at original rate after wait• Ack clocking rate is same as before lossFast Recovery Sequence NoSent for each dupack afterW/2 dupacks arriveX11-01-07Lecture 19: TCP Congestion Control 16TimePacketsAcks5OutlineTCP ti id•TCP congestion avoidance• TCP slow start11-01-07Lecture 19: TCP Congestion Control 17• TCP modelingCongestion Avoidance BehaviorCongestionWindow11-01-07Lecture 19: TCP Congestion Control 18TimePacket loss+ retransmitGrabbingback BandwidthCutCongestionWindowand RateReaching Steady State• Doing AIMD is fine in steady state but slow…•How does TCP know what is a good initial rate to•How does TCP know what is a good initial rate to start with?• Should work both for a CDPD (10s of Kbps or less) and for supercomputer links (10 Gbps and growing)• Quick initial phase to help get up to speed (slow start)11-01-07Lecture 19: TCP Congestion Control 19start)Slow Start Packet Pacing• How do we get this clocking behavior to start?Iitili d 1•Initialize cwnd = 1• Upon receipt of every ack, cwnd = cwnd + 1• Implications• Window actually increases to W in RTT * log2(W)• Can overshoot window and cause packet loss11-01-07Lecture 19: TCP Congestion Control 20cause packet loss6Slow Start ExampleOne RTT0R1One pkt time21R32R12 311-01-07Lecture 19: TCP Congestion Control 21456783R91011121314154 5 6 7Slow Start Sequence Plot...Sequence No11-01-07Lecture 19: TCP Congestion Control 22TimePacketsAcksReturn to Slow Start• If packet is lost we lose our self clocking as well•Need to implement slow-start and congestion•Need to implement slow-start and congestion avoidance together• When retransmission occurs set ssthresh to 0.5w• If cwnd < ssthresh, use slow start• Else use congestion avoidance11-01-07Lecture 19: TCP Congestion Control 23TCP Saw Tooth BehaviorCongestionWindowTimeoutsmay stillmay stilloccur11-01-07Lecture 19: TCP Congestion Control 24TimeInitialSlowstartFast Retransmitand RecoverySlowstartto pacepackets7OutlineTCP ti id•TCP congestion avoidance• TCP slow start11-01-07Lecture 19: TCP Congestion Control 25• TCP modelingTCP Performance• Can TCP saturate a link?•Congestion control•Congestion control• Increase utilization


View Full Document
Download Lecture
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 Lecture 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 Lecture 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?