Advanced Computer Networks: Lecture 32 - Dr. Amir Qayyum
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (336.61 KB, 15 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
Lecture No. 32
2
TCP Flow Control Issues
• Problem: app. delivers tiny pieces of data to TCP
– e.g. telnet in character mode
– Each piece sent as segment, returned as ACK
– Very inefficient
• Solutions
– Delay transmission to accumulate more data
– Nagle’s algorithm
• Send first piece
• Accumulate data until first piece ACK’d
• Send accumulated data and restart accumulation
• Not ideal for some traffic, e.g. mouse motion
3
TCPFlowControlIssues
ã Problem:slowapplicationreadsdataintinypieces
Receiveradvertisestinywindow
Senderfillstinywindow
Knownassillywindowsyndrome
ã Solution:duetoClark
AdvertisewindowopeningonlywhenMSSorẵofbufferis
available
SenderdelayssendinguntilwindowisMSSorẵofreceivers
buffer(estimated)
OverriddenbyusingPUSH
4
TCP Flow Control Math
• Send buffer size: MaxSendBuffer
• Receive buffer size: MaxRcvBuffer
• Receiving side
– LastByteRcvd LastByteRead < = MaxRcvBuffer
– AdvertisedWindow = MaxRcvBuffer
(NextByteExpected NextByteRead)
• 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 when AdvertisedWindow = 0
5
TCP Bit Allocation Limitations
• Sequence numbers vs packet lifetime
– Assumed that IP packets live less than 60s
– Can we send 232 (4G) bytes in 60 seconds ?
– Only need a data rate of 573 Mbps!
– Less than an STS12 line... (less than Gigabit
Ethernet)
• Advertised window vs delaybandwidth
– Only 16 bits (64kB) for advertised window
– For crosscountry RTT of 100 milliseconds,
adequate for a mere 5.24 Mbps!
6
Protection Against Wrap Around
• 32bit SequenceNum
Bandwidth
T1 (1.5 Mbps)
Ethernet (10 Mbps)
T3 (45 Mbps)
FDDI (100 Mbps)
STS3 (155 Mbps)
STS12 (622 Mbps)
STS24 (1.2 Gbps)
Time Until Wrap Around
6.4 hours
57 minutes
13 minutes
6 minutes
4 minutes
55 seconds
28 seconds
7
Keeping the Pipe Full
• 16bit AdvertisedWindow
Bandwidth
T1 (1.5 Mbps)
Ethernet (10 Mbps)
T3 (45 Mbps)
FDDI (100 Mbps)
STS3 (155 Mbps)
STS12 (622 Mbps)
STS24 (1.2 Gbps)
Delay x Bandwidth Product
18KB
122KB
549KB
1.2MB
1.8MB
7.4MB
14.8MB
8
AdaptiveRetransmissionAlgorithm
ã OriginalalgorithmusedonlyRTT
estimate
ã Theory:measureRTTforeach
segment+itsACK
EstimateRTT
Timeoutis2ìRTTtoallowfor
variations
9
AdaptiveRetransmissionAlgorithm
ã Practice
Useexponentialmovingaverage( =0.8
to0.9)
Estimate= ìestimate+(1ư )
measurement
Measured
RTT
dependson
time
10
Adaptive Retransmission Algorithm
• Problem: it did not handle variations well
Measured
RTT
time
• Ambiguity for retransmitted packets: was ACK in
response to first, second, etc. transmission ?
transmission
retransmission
RTT ? ? ?
11
AdaptiveRetransmission
(OriginalAlgorithm)
ã MeasureSampleRTTforeachsegment/ACK
pair
ã ComputeweightedaverageofRTT
EstRTT= ìEstRTT+ ìSampleRTT
where + = 1
between0.8and0.9
between0.1and0.2
ã Set timeout based on EstRTT
– TimeOut = 2 × EstRTT
12
Karn/Partridge Algorithm
Receiver
SampleR TT
Orig
in
•
•
•
•
R et r
al t ra
ns m
issio
ans m
issio
Sender
Orig
in
n
SampleR TT
Sender
n
ACK
Receiver
al t ra
ns m
is s io
ACK
R et r
an
smis
n
sion
Do not sample RTT when retransmitting
Double timeout (RTT estimate) after each retransmission
Still did not handle variations well
Did not solve network congestion problems as desired
13
Jacobson/KarelsAlgorithm
ã EstimatevarianceofRTT
CalculatemeaninterpacketRTTdeviationas
anapproximationofvariance
(Diff=RTT_estimatemeasurement)
RTT_estimate=
xRTT_estimate+(1ư
ì
measurement
Usinganotherexponentialmovingaverage
Deviation=
x|RTT_estimateưmeasurement|+(1ư)
deviation
14
=0.25,=0.875inRTT_estimate
Jacobson/KarelsAlgorithm
ã UsevarianceestimateascomponentofRTT
estimate
next_RTT(timeout)=
RTT_estimate+4ìdeviation
ã Protectsagainsthighjitter
ã Algorithmonlyasgoodasclock
granularity(500msonUnix)
ã Accuratetimeoutmechanismimportantto
congestioncontrol
15
