DOC PREVIEW
MIT 6 033 - Sharing in network systems

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:

L13: Sharing in network systemsPowerPoint PresentationThis LectureSliding WindowSlide 5Slide 6Slide 7Slide 8Slide 9What is the right window size?Flow ControlSlide 12Sharing the networkCongestionDanger: Congestion Collapse Increase in input traffic leads to decrease in useful workExample: old TCP implementationsWhat can be done in general?How do senders learn of congestion?Slide 19TCP Increase/decrease algorithmAdditive IncreaseTCP AIMDTCP “Slow Start”Slow Start + AIMDFairness?SummaryL13: Sharing in network systems6.033 Spring 2007http://web.mit.edu/6.033Slides from many folksWhere is sharing happening?stubstubNetwork LayerLink Layerpresentation LayerEnd-to-end layerRPC RPCHDHDHDHD HDHDHeaderData HeaderDataclient serverThis Lecture•Problems:•Sharing server•Sharing network•Solution: •Set the window size carefully•Sharing server: flow control•Sharing the network: congestin controlSliding Window•The window advances/slides upon the arrival of an ack•The sender sends only packets in the window•Receiver usually sends cumulative acks•i.e., receiver acks the next expected in-order packet Window SizeOutstandingUn-ack’d pktsPackets OK to sendPackets not OK to send yetPackets ACK’dSrcRcvrwindow = 1-512345p1xSrcRcvrwindow = 2-612345p1a2x6Srcwindow = 2-612345p1a2x6a2p3RcvrSrcwindow = 2-612345p1a2x6a2p3a2p4a2p6a2p5Timeout2a7p2RcvrSrcwindow = 7-1112345p1a2x6a2p3a2p4a2p6a2p5Timeout2a7p27891011RcvrIn this example, the receiver sent cumulative acks, but the same behavior happens if the receiver acks the received sequence numberWhat is the right window size?•The window limits how fast the sender sends•Two mechanisms control the window:•Flow control •Congestion controlFlow Control•The receiver may be slow in processing the packets  receiver is a bottleneck•To prevent the sender form overwhelming the receiver, the receiver tells the sender the maximum number of packets it can buffer fwnd•Sender sets W ≤ fwndHow to set fwnd?App AppB1 B2TCP Multiple applications run on the same machine but use different portsP1D P2DP2DHP1DHnetwork•Fwnd = B x RTT•Size of queue substitute for B•Adapts to•RTT changes•B changes•“self-pacing”Sharing the networkHow do you manage the resources in a huge system like the Internet, where users with different interests share the same resources?Difficult because of:•Size•Millions of users, links, routers•Heterogeneity•bandwidth: 9.6Kb/s (then modem, now cellular), 10 Tb/s •latency: 50us (LAN), 133ms (wired), 1s (satellite), 260s (Mars)CongestionS1S2R1D10Mb/s2Mb/s100Mb/sS1S2Sources share links, and buffer spaceWhy 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)Long delays may lead to retransmissions, which lead to more packets….Danger: Congestion CollapseIncrease in input traffic leads to decrease in useful workInput trafficThroughputcliffCongestion CollapsekneeLatencyCauses of Congestion CollapseRetransmissions introduce duplicate packetsDuplicate packets consume resources wasting link capacityExample: old TCP implementationsFwnd 2Fwnd 1Long haul network (i.e., large RTT)Router drops some of TCP 2’s fwnd packetsEach discard packet will result in timeoutAt timeout TCP 2 resends complete windowCumulative ACK, timeouts fire off at “same” timeBlizzard of retransmissions can result in congestion collapseInsufficiently adaptive timeout algorithm made things worseWhat can be done in general?•Avoid congestion:•Increase network resources•But demands will increase too!•Admission Control & Scheduling•Used in telephone networks•Hard in the Internet because can’t model traffic well•Perhaps combined with Pricing•senders pay more in times of congestion•Congestion control: •Ask the sources to slow down; But how?•How do the sources learn of congestion?•What is the correct window?•How to adapt the window as the level of congestion changes?How do senders learn of congestion?Potential options:•Router sends a Source Quench to the sender •Router flags the packets indicating congestion•Router drops packets when congestion occurs•Sender learns about the drop because it notices the lack of ack•Sender adjusts window•Define a congestion control window cwnd•Sender’s window is set to W = min (fwnd, cwnd) •Simple heuristic to find cwnd:•Sender increases its cwnd slowly until it sees a drop•Upon a drop, sender decreases its cwnd quickly to react to congestion•Sender increases again slowly •No changes to protocol necessary!Case study: current TCPTCP Increase/decrease algorithm •AIMD: •Additive Increase Multiplicative Decrease •Every RTT: No drop: cwnd = cwnd + 1 drop: cwnd = cwnd /2Additive IncreaseDASrcRcvrcwnd = 1cwnd += 1cwnd = 2D D A Acwnd = 3D D A AD Acwnd = 4TCP AIMDTimeCwndGrab capacity again Halve CwndTimeout because of a packet lossdesired cwndNeed the queue to absorb these saw-tooth oscillationsTCP “Slow Start”DAD D A A D DA ADASrcRcvrDA1248A A A AHow to set the initial cwnd?At the beginning of a connection, increase exponentiallyEvery RTT, double cwndSlow Start + AIMDTimeCwndSlow startAdditive increaseMultiplicative decrease TimeoutFairness?•No!•Applications don’t have to use TCP•Use multiple TCP connectionsSummary•Controlling complexity in network systems•Layering•Interesting division of labors based on E2E principle•Case study: Internet•Interesting problems and techniques•Packets•Protocols•…•Client-server implementation•Next: Application-level reliability and


View Full Document

MIT 6 033 - Sharing in network systems

Documents in this Course
TRIPLET

TRIPLET

12 pages

End Layer

End Layer

11 pages

Quiz 1

Quiz 1

4 pages

Threads

Threads

18 pages

Quiz I

Quiz I

15 pages

Atomicity

Atomicity

10 pages

QUIZ I

QUIZ I

7 pages

Load more
Download Sharing in network systems
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 Sharing in network systems 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 Sharing in network systems 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?