DOC PREVIEW
CMU CS 15744 - Placement of Function in a Best Effort World

This preview shows page 1-2-3-24-25-26 out of 26 pages.

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

Unformatted text preview:

Placement of Function in a Best Effort WorldCourse Logistics UpdateInternet Architecture ReduxThings the Transport FacesSo: TCP?Reliable TransfersTCP Gets OlderTCP VariantsTCP PrinciplesTimersEWMAVarianceUsing more information: Fast RetransmissionWither dup acksCongestion ControlThe basicsFast RecoverySACKOther tricks in TCPALFVideo over TCP?A better wayErgo, ALF and ADUsALF in the real worldBenefits of ALFSummaryPlacement of Function in a Best Effort WorldCourse Logistics Update•45 total in class. Still off target.•Prioritized waitlist now available. See me after class.Internet Architecture Redux•The network is stateless (w.r.t. e2e connection state), for survivability•The network is unreliable–No guarantees; 1%ish drop rate OK; may burst to higher or have temp. outagesEnd-hosts must do reliability/retransmission•The network provides no QoSEnd-hosts must do congestion controlThings the Transport Faces•Loss–Congestion, corruption, routing probs, failures•Congestion? Yup: Stat mux! Finite buffers for store-and-forward. Bursts or excess traffic.–Queue size is tricky: Too large == too much delay, too small == bad statmux. More later•Variable delay•Reordering (how can this happen?)–Bugs, multipath•Duplication–Bugs, lower-layer spurious retransmissionsSo: TCP?•A reliable, congestion-controlled, in-order bytestream–As mentioned last time: Not a perfect fit for everybody. Drawbacks?•Unreliable apps don’t need it•May delay app processing, causing CPU/memory/disk to be more bursty than necessary –Known problem. Nice paper @ SIGCOMM 2006 on DCCP, datagram congestion control: Unreliable, congestion controlled datagrams–Also mentioned ITP, image transport protocol: reliable *out of order* –Rel to end-to-end arguments?Reliable Transfers•Forward Error Correction: (redundancy in-band)•Automatic Repeat reQuest (ARQ): retransmissions. How does it know?–Acknowledgements!–In tcp: cumulative ACKs•How do you detect a loss with ACKs?–Timeout–Or – (diagram) notice that you’re getting dup ACKsTCP Gets Older•V1: “go-back-N” retransmissions based on timeouts with a fixed-size sliding window•V2: Congestion collapse!–Van Jacobsen and Mike Karels congestion avoidance (congestion control), better RTT estimators (why? To set the timeout), and slow start. (Coming up later)•Karn & Partridge: Retransmission Ambiguity–How do you tell if an ACK is for orig or Rx packet? If you can’t tell, your RTT estimator can break–Next step: TCP timestamp optionsTCP Variants•TCP Tahoe: Fast retransmission + Jacobson/Karels (slow start/cong avoid)–First data-driven, not timeout-driven, Rxmit•TCP Reno: Fast recovery: The now-classic sawtooth•TCP NewReno: improves fast recovery to survive multiple data losses in large windows•TCP SACK: Pretty close to the state of the art. Instead of just ACKing last received seq, tell sender about other recv’d packets too (easier to recover from weird loss patterns)•Most machines today are NewReno / SACK (Sally Floyd 2005 study)TCP Principles•Don’t retransmit early; aoid spurious retransmissions–A response to congestion collapse. Part of cong. collapse was Rx of packets that were queued, not lost.•Conserve packets–Don’t blast network with extra traffic during retransmissions.–General technique: Count # dup acks to know how many packets have left the network.Timers•How do you know when packets were lost? If no other ACKs, must timeout.•How long to wait? Well, depends on the RTT.–Easy to measure: segment -> ACK–Problems: Variable delay, variable processing times at receiver–Solution: AveragingEWMA•Exponential Weighted Moving Averages–A low-pass filter by another name–Srtt = alpha * r + (1 – alpha)*srtt•R is the current sample•Srtt is the smoothed average•TCP uses alpha = 1/8. Doesn’t matter too much.–Great! We’re done.–Or not.•EWMA is great to put in your toolboxVariance•If we use srtt, then half of our transmissions are spurious.•TCP early solution: Beta * srtt (beta =~ 2)–But what if the path has high variance?•Real solution:–RTO = srtt + 4 * rttdev–Rttdev = mean linear deviation (>= stddev)•= rttdev = gamma * dev + (1-gamma) * rttdev•Dev = |r – srtt|. TCP uses gamma = ¼•Final note: What to do on timeout?–Exponential backoff (another good toolkit thing)Using more information: Fast Retransmission•Data-driven retransmission•What happens on loss? Duplicate ACKs–Imagine you sent:–1:1000, 1001:1700, 2501:3000, 3001:4000, 4001:4576–And got ACKs 1001 1701 1701 1701 1701–Clear that something’s going wrong!Wither dup acks•Why DUP acks?–Window updates: TCP receivers have limited space in socket buffer, so they can tell the source to “shut up” (flow control)–Segment loss–Or … segment re-ordering•TCP says three dupacks == not re-ordered•Works pretty well, but now forces network design to abide by it because it works pretty well!–Per-packet load balancingCongestion Control•Okay. Great. We know we had a loss because of a timeout or dup ACKs. What do we do?–1: Retransmit–2: Adjust our congestion window•TCP isn’t just doing reliability…The basics•Slow start: Ramp up•Congestion avoidance: Be conservative when you’re near the limitFast Recovery•There’s still more information floating in the net.•If you did fast recovery, you got dup ACKs, and will probably keep getting more.•Retransmit lost packet. Cut cong window in half. Wait until half of the window has been ACKed, and then send _new_ data.•Basic idea in TCP Reno.•TCP NewReno adds more tricks to deal with multiple losses in a window, which kills Reno.SACK•You can get still more information!•1:1000 1001:1700 2501:3000 3001:4000 4577:5062 6000:7019•Send ACKs•1001 1701 1701 [2501-3000] 1701 [2501-4000] 1701 [4577-5062; 2501-4000] etc.•Aimed at Long Fat Networks (LFNs; pronounced “Elephants”). Standardized in RFC2018 after years of debate.•SACK isn’t perfect! If TCP window is very small, not enough Rx to deal with it.Other tricks in TCP•Three way handshake: Establishes the sequence # space with both sender and receiver•Segment size: How big can the network support?–Path MTU discovery–Set IP “Don’t Fragment” bit.•Routers with smaller MTU send back ICMP error message containing their MTU•Low-bandwidth links: TCP Header


View Full Document

CMU CS 15744 - Placement of Function in a Best Effort World

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 Placement of Function in a Best Effort World
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 Placement of Function in a Best Effort World 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 Placement of Function in a Best Effort World 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?