Transport Protocols
Reliability
• Based on acknowledgments (to determine if segments have been correctly received)
Copyright By PowCoder代写 加微信 powcoder
• If a segment is lost (or not acknowledged), it will be re- transmitted
• Can have it be re-transmitted multiple times until successfully receive an acknowledgement
Acknowledgment types
1. Go-Back-N
• Send all N unACKed packets when a loss is signaled
• Inefficient to implement
Acknowledgment types
2. Selective repeat
• Only send specifically unACKed packets
• A bit trickier to implement
What does TCP do?
• A bit of both — Go-back-n and Selective repeat
• Acknowledgment numbers in TCP are called cumulative acks (they are cumulative over contiguous bytes successfully received)
• An acknowledgment will acknowledge all bytes that have been contiguously received until this point, but not any non- contiguous bytes
A Sliding Window Mechanism
• TCP’s variant of the sliding window algorithm, which serves several purposes:
– (1) it guarantees the reliable delivery of data,
– (2) it ensures that data is delivered in order, and
– (3) it enforces flow control between the sender and the receiver.
Pipelining via Sliding Window
• A “window” of un-ACKed frames
• Allow multiple outstanding (un-ACKed) frames
• Upper bound on un-ACKed frames
Sender Receiver
Buffering on Sender and Receiver
• Sender needs to buffer data so that if data is lost, it can be resent
• Receiver needs to buffer data so that if data is received out of order, it can be held until all packets are received
– Flowcontrol
• How can we prevent sender overflowing receiver’s buffer?
– Receiver tells sender its buffer size during connection setup
• How can we insure reliability in pipelined transmissions?
– Go-Back-N
• Send all N unACKed packets when a loss is signaled • Inefficient
– Selectiverepeat
• Only send specifically unACKed packets
• A bit trickier to implement
Sliding Window Revisited
Sending application
TCP LastByteWritten
LastByteAcked LastByteSent
Sending side
LastByteAcked < = LastByteSent
LastByteSent < = LastByteWritten
buffer bytes between LastByteAcked and LastByteWritten
Receiving application
TCP LastByteRead
NextByteExpected LastByteRcvd
Receiving side
– LastByteRead <
NextByteExpected
– NextByteExpected < = LastByteRcvd +1
– buffer bytes between NextByteRead and LastByteRcvd
CSE 123 – Lecture 10: Transport Layer
An Example
T=3 Stall due to T=4
flow control here T=5
Receiver has buffer size 4
Receiver has
and application
buffer of size 4
does not read
and application doesn’t read
ACK=2; WIN=3 ACK=3; WIN=2
ACK=4; WIN=1 ACK=5; WIN=0
SEQ=1 SEQ=2
SEQ=3 SEQ=4
An Example
=acked =sent
=advertised
CSE 123 – Lecture 10: Transport Layer
Flow Control in TCP
• Send buffer size: MaxSendBuffer
• Receive buffer size: MaxRcvBuffer
• Receiving side
– LastByteRcvd - LastByteRead < = MaxRcvBuffer
– AdvertisedWindow = MaxRcvBuffer - ((NextByteExpected - 1) - LastByteRead)
• Sending side
– LastByteSent - LastByteAcked < = AdvertisedWindow
– EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked)
– LastByteWritten - LastByteAcked < = MaxSendBuffer
– block sender if (LastByteWritten - LastByteAcked) + y >
MaxSenderBuffer
• Always send ACK in response to arriving data segment
• Persist sending one byte seg. when AdvertisedWindow = 0
– Keep soliciting ACKs, eventually window opens up CS 640 12
Triggering Transmission
• How does TCP decide to transmit a segment? – TCPsupportsabytestreamabstraction
– Application programs write bytes into streams
– It is up to TCP to decide that it has enough bytes to send a segment
• TCP uses “self clocking”
– Use ACKs as an implicit timer
• ACK info tells if there is enough space
Silly Window Syndrome
• When should we send a segment (packet)? • Small packets (tinygrams) are inefficient
• We could use a clock-based timer, for example. one that fires every 100 ms
• Nagle introduced an elegant self-clocking solution
• Key Idea
– As long as TCP has any data in flight, the sender will eventually receive an ACK
– This ACK can be treated like a timer firing, triggering the transmission of more data
Nagle’s Algorithm
When the application produces data to send
if both the available data and the window ≥ MSS
send a full segment else
if there is unACKed data in flight
buffer the new data until an ACK arrives
send all the new data now
Delayed ACKs
• Should we send an ack for each segment received?
• ACKs are small packets (40 bytes – TCP+IP header)
• Since ACKs are cumulative, why not wait a bit to see if we can ack more data
• Wait upto X milliseconds (with the hope that we can send one ACK for multiple segments
• Intracts poorly with Nagle’s algo
Delayed ACKs
Adaptive Retransmission
• When should we initiate a retransmission of a segment?
• Inparticular,whendowedeclareasegmentislost • Needatimeout
• OriginalAlgorithm
– Measure SampleRTT for each segment/ ACK pair
– Compute weighted average of RTT
• EstRTT= a xEstRTT+ (1 – a )xSampleRTT – a between 0.8 and 0.9
n Set timeout based on EstRTT n TimeOut=2xEstRTT
Original Algorithm
– ACK does not really acknowledge a specific transmission • It actually acknowledges the receipt of data
– When a segment is retransmitted and then an ACK arrives at the sender
• It is impossible to decide if this ACK should be associated with the first or the second transmission for calculating RTTs
Karn/ for RTO
Sender Receiver Sender Receiver
• Two degenerate cases with timeouts and RTT measurements – Solution: Do not sample RTT when retransmitting
• After each retransmission, set next RTO to be double the value of the last
– Exponential backoff is well known control theory method
– Loss is most likely caused by congestion so be careful
Original transmission
Original transmission
SampleR TT
SampleR TT
• Karn-Partridge algorithm was an improvement over the original approach, but it does not eliminate congestion
• We need to understand how timeout is related to congestion
– If you timeout too soon, you may unnecessarily retransmit a segment which adds load to the network
• Main problem with the original computation is that it does not take variance of Sample RTTs into consideration.
• If the variance among Sample RTTs is small
– Then the Estimated RTT can be better trusted
– There is no need to multiply this by 2 to compute the timeout
• On the other hand, a large variance in the samples suggest that timeout value should not be tightly coupled to the Estimated RTT
• Jacobson/Karels proposed a new scheme for TCP retransmission
Jacobson/ Karels Algorithm
• In late ’80s, Internet was suffering from congestion collapse
• for average RTT – Jacobson ’88
• Variance is not considered when setting timeout value
– If variance is small, we could set RTO = EstRTT
– If variance is large, we may need to set RTO > 2 x EstRTT
• New algorithm calculates both variance and mean for RTT • Diff = sampleRTT – EstRTT •EstRTT=EstRTT+(d x Diff)
• Dev = Dev + d ( |Diff| – Dev)
– Initially settings for EstRTT and Dev will be given to you – where d is a factor between 0 and 1
– typicalvalueis0.125
Jacobson/ Karels contd.
• TimeOut= μ xEstRTT+ f xDev – where μ = 1 and f = 4
• When variance is small, TimeOut is close to EstRTT
• When variance is large Dev dominates the calculation
• Another benefit of this mechanism is that it is very efficient to implement in code (does not require floating point)
– algorithm only as good as granularity of clock (500ms on Unix)
– accurate timeout mechanism important to congestion control (later)
• These issues have been studied and dealt with in new RFC’s for RTO calculation.
• TCP RENO uses Jacobson/Karels
Jacobson/ Karels in code
SampleRTT – = (EstimatedRTT >> 3); EstimatedRTT += SampleRTT;
if (SampleRTT < 0)
SampleRTT = -SampleRTT;
SampleRTT -= (Deviation >> 3);
Deviation += SampleRTT;
TimeOut = (EstimatedRTT >> 3) + (Deviation >> 1);
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com