CS514: Intermediate Course in Operating SystemsTCP StreamsTCP is a “stream” protocolStreams conceptTCP sliding windowSlide 6Slide 7Slide 8Slide 9Slide 10Typical implementation issues?Where are the costs?Costs (cont)Slide 14Timed approachVan Jacobson optimizationsDealing with failuresProblems with this approach?Inconsistently broken TCP channelsSlide 20Slide 21Why should this matter?Subtle semantics questionsReliability/Consistency summaryTCP and Router IssuesSlide 26Some options?Slide 28Slide 29Some optionsSlide 31Slide 32Slide 33Random Early DetectionSlide 35Slide 36How Internet Companies think of the NetworkSlide 38TCP is a good citizenTCP issuesStyles of Audio/VideoTCP challengesResearch on better TCPRSVPKeeping RSVP statelessRSVP criticisms?RSVP: A dead standard?How else can we get QoS?Diffsrv ideaRIO: RED with I/O bitsSlide 51Convoy phenomenonSlide 53Readings and homeworkCS514: Intermediate Course in Operating SystemsProfessor Ken BirmanBen Atkin: TALecture 4: Sept. 5TCP Streams•One week ago we very briefly saw how TCP overcomes failures•TCP is the workhorse of the Internet–Under load, many routers drop all non-TCP traffic first!–This is because TCP is a “good citizen”–Every web operation uses its own TCP connection! •Today: look at TCP in more detail•In what sense is the Internet “the bottom half of the TCP protocol”?TCP is a “stream” protocol•Basic concepts•Implementation issues, usual optimizations•Where are the costs?•Van Jacobson optimizations for TCP•Routers: RED, RSVP and RIO•Reliability and consistencyStreams concept•Reliable, point-to-point communication channel•Like a telephone connection:–Information received in order sent, no loss or duplication–Call setup required before communication is possible (in contrast with basic message transport via UDP)–No message structure: abstraction is a stream of bytes•Automatic flow control, error correctionTCP sliding windowinitially emptyinitially emptysender provides datareceiver consumes datawindow has k “segments”TCP sliding windowmistill empty...sender provides datareceiver consumes dataIP packets carry segmentswindow has k “segments”TCP sliding windowmi+1 mi misender provides datareceiver consumes dataIP packets carry segmentswindow has k “segments”receiver replies with acks and nacks. sender resends missing dataTCP sliding windowmi+k mi+k-1 .... mi- - mi+k-2 - mi+k-3 ... misender provides datareceiver consumes dataIP packets carry segmentswindow has k “segments”receiver replies with acks and nacks. sender resends missing dataTCP sliding windowmi+k mi+k-1 .... mi+k+1- - mi+k-2 - mi+k-3 ... misender provides datareceiver consumes dataIP packets carry segmentswindow has k “segments”receiver replies with acks and nacks. sender resends missing dataWhen acknowledgement is received, segment number keeps incrementing but slot number is reused.TCP sliding windowmi+k mi+k-1 .... mi- - mi+k-2 - mi+k-3 ... misender provides datareceiver consumes dataIP packets carry segmentswindow has k “segments”receiver replies with acks and nacks. sender resends missing dataTypical implementation issues?•When to send the ack–Send early: inefficient, channel clogged with acks–Send late: sender side fills window and waits•When to send the nack–Send early: sender will send duplicates of all msgs–Send late: long delay waiting for desired data•How big to make the window•Send messages in “bursts”?Where are the costs?•Excess packets sent/received: very costly–Hence want minimal number of acks, nacks–Also want to avoid excess retransmissions•Notice “tension” between sending acks/nacks too soon, and retransmission too soon, and between doing so too late. –Too soon: consumes bandwidth–Too late: leaves processes idleCosts (cont)•Delays on sender side:–Overheads associated with scheduling (e.g. if window fills up•Avoiding “nervous” scheduling:–Highwater/lowater mark scheme lets sender sit idle until there are several window slots free–Ideally, seek window size at which sender, receiver are rate matched and neither ever waitsCosts (cont)•Delays on receiver side–Want a large enough window so that any error correction is “in the future” for receiver–Don’t want to delay nacks too long (else retransmission delayed too long)•Nervous scheduling less of an issue here–Don’t use hiwater/lowater scheme in receiverTimed approach•Measure round-trip time (e.g. perhaps 1ms)•Track rate of transmission for recent past•Use to calibrate various constants:–Nack if a missing packet is late by 50% of expected time–Calibrate window to be 50-75% full in steady state•Experience: very hard to make it work; variability in network load/latencies too bigVan Jacobson optimizations•Dynamically adjust window size: while no loss detected, repeatedly increase size (linearly)•Detect loss: halve size (“exponential” backoff)•Experience is very positive, many TCP’s use this•Also optimize to supress unchanging header fieldsDealing with failures•Packets lost, duplicated, out of order: easy, just use sequence numbers (TCP calls these “segment” numbers)•Sender or receiver fails, or line breaks:–After excessive retransmissions, or–After excessive wait for missing data, or–After not seeing “keepalives” for too long... break the connection and report “end of file”Problems with this approach?•Channel can break because of a transient condition!•Example: overloaded machine, connection that temporarily fails, router crashes and must reboot itself (all are relatively common conditions)•Systems with many TCP channels: some may break but others stay connected!Inconsistently broken TCP channelsprimarybackupClients initially connected to primary, which keeps backup up to date. (For example, in a database system)Inconsistently broken TCP channelsTransient problem causes some links to break but not all.Backup thinks it is now primary, primary thinks backup is downprimarybackupInconsistently broken TCP channelsSome clients still connected to primary, but one has switchedto backup and one is completely disconnected from bothprimarybackupWhy should this matter?•Suppose that primary and backup are a service used for air traffic control•Service tells controllers which parts of airspace are “available” for routing
View Full Document
Unlocking...