Bài giảng Mạng máy tính nâng cao - Chương 2: TCP & Congestion control - Lê Ngọc Sơn
TCP & Congestion Control
MẠNG MÁY TÍNH NÂNG CAO
Tháng 09/2015
Introduction to TCP
q Communication abstraction:
§ Reliable
§ Ordered
§ Point-to-point
§ Byte-stream
§ Full duplex
§ Flow and congestion controlled
q Sliding window with cumulative acks
§ Ack field contains last in-order packet received
§ Duplicate acks sent when out-of-order packet received
Evolution of TCP
1984
Nagel’s algorithm
to reduce overhead
of small packets;
predicts congestion
collapse
1975
Three-way handshake
Raymond Tomlinson
In SIGCOMM 75
1987
Karn’s algorithm
to better estimate
round-trip time
1990
4.3BSD Reno
fast retransmit
delayed ACK’s
1983
BSD Unix 4.2
supports TCP/IP
1988
1986
Van Jacobson’s algorithms
congestion avoidance and
congestion control
Congestion collapse
observed
1974
TCP described by
Vint Cerf and Bob Kahn
In IEEE Trans Comm
(most implemented in
4.3BSD Tahoe)
1982
TCP & IP
RFC 793 & 791
1990
1975
1980
1985
TCP Through the 1990s
1994
T/TCP
(Braden)
Transaction
1996
SACK TCP
(Floydet al)
Selective
TCP
Acknowledgement
1996
FACK TCP
(Mathis et al)
extension to SACK
1996
Hoe
Improving TCP
startup
1993
TCP Vegas
(Brakmoet al)
real congestion
avoidance
1994
ECN
(Floyd)
Explicit
Congestion
Notification
1993
1994
1996
Flow Control vs. Congestion Control
qFlow control
§ Keeping one fast sender from overwhelming a slow
receiver
qCongestion control
§ Keep a set of senders from overloading the network
qDifferent concepts, but similar mechanisms
§ TCP flow control: receiver window
§ TCP congestion control: congestion window
§ TCP window: min{congestion window, receiver window}
5
Three Key Features of Internet
qPacket switching
§ A given source may have enough capacity to send data
§ … and yet the packets may encounter an overloaded link
qConnectionless flows
§ No notions of connections inside the network
§ … and no advance reservation of network resources
§ Still, you can view related packets as a group (“flow”)
§ … e.g., the packets in the same TCP transfer
qBest-effort service
§ No guarantees for packet delivery or delay
§ No preferential treatment for certain packets
6
Congestion is Unavoidable
qTwo packets arrive at the same time
§ The node can only transmit one
§ … and either buffer or drop the other
qIf many packets arrive in a short period of time
§ The node cannot keep up with the arriving traffic
§ … and the buffer may eventually overflow
7
Why prevent congestion ?
qCongestion is bad for the overall performance in
the network.
§ Excessive delays can be caused.
§ Retransmissions may result due to dropped packets
• Waste of capacity and resources.
§ Note: Main reason for lost packets in the Internet is due
to congestion -- errors are rare.
The Congestion Window
q In order to deal with congestion, a new state variable called
“CongestionWindow” is maintained by the source.
§ Limits the amount of data that it has in transit at a given
time.
q MaxWindow = Min(Advertised Window, CongestionWindow)
q EffectiveWindow = MaxWindow - (LastByteSent -
LastByteAcked).
q TCP sends no faster than what the slowest component --
the network or the destination host --can accommodate.
Managing the Congestion Window
q Decrease window when TCP perceives high congestion.
q Increase window when TCP knows that there is not much
congestion.
q How ? Since increased congestion is more catastrophic,
reduce it more aggressively.
q Increase is additive, decrease is multiplicative -- called
the Additive Increase/Multiplicative Decrease (AIMD)
behavior of TCP.
AIMD details
q Each time congestion occurs - the congestion
Source
Destination
window is halved.
§ Example, if current window is 16 segments and a
time-out occurs (implies packet loss), reduce the
window to 8.
§ Finally window may be reduced to 1 segment.
q Window is not allowed to fall below 1 segment
(MSS).
q For each congestion window worth of packets
that has been sent out successfully (an ACK is
received), increase the congestion window by
the size of a (one) segment.
TCP Slow Start
q Additive Increase is good when source is
operating at near close to the capacity of the
network.
Source
Destination
§ Too long to ramp up when it starts from scratch.
§ Slow start --> increase congestion window
rapidly at cold start.
q Slow start allows for exponential growth in the
beginning.
E.g. Initially CW =1, if ACK received, CW = 2.
If 2 ACKs are now received, CW = 4. If 4 ACKs are
now received, CW =8 and so on.
q Note that upon experiencing packet loss,
multiplicative decrease takes over.
Where does AIMD come in now ?
q Slow start is used to increase the rate to a “target
window size” prior to AIMD taking over.
q What is this target window size ?
q In addition, we now have to do book keeping for two
windows -- the congestion window and the “target
congestion window” where Slow start ends and AIMD
begins.
The Congestion Threshold
q Initially no target window -- when a packet loss occurs,
divide the current CW by 2 (due to multiplicative
decrease) -- this now becomes the target window.
q Define this to be the “Congestion Threshold”.
q Reduce actual CW to 1.
q Use Slow Start to ramp up to the Congestion Threshold
(or simply threshold). Once this is reached use AIMD.
Summary: TCP Tahoe
q Thus:
§ When CW is below the threshold, CW grows exponentially
§ When it is above the threshold, CW grows linearly.
§ Upon time-out, set “new” threshold to half of current CW and
the CW is reset to 1.
§ This version of TCP is called “TCP Tahoe”.
70
60
50
40
30
20
10
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
Time (seconds)
Fast Retransmit
qWhat are duplicate acks (dupacks)?
§ Repeated acks for the same sequence
qWhen can duplicate acks occur?
§ Loss
§ Packet re-ordering
§ Window update – advertisement of new flow control
window
Duplicate ACKs
q When a duplicate ACK is seen by
the sender, it infers that the other
side must have received a packet
out of order.
Sender
Packet 1
Receiver
Packet 2
Packet 3
Packet 4
ACK 1
ACK 2
§ Delays on different paths could be
different -- thus, the missing packets
may be delivered.
ACK 2
Packet 5
Packet 6
ACK 2
ACK 2
§ So wait for “some” number of
Retransmit
packet 3
duplicate ACKs before resending data.
§ This number is usually 3.
ACK 6
Fast Recovery
qWhen the fast retransmit mechanism signals
congestion, the sender, instead of returning to
Slow Start uses a pure AIMD.
§ Simply reduces the congestion window by half and
resumes additive increase.
qThus, recovery is faster -- this is called Fast
Recovery.
TCP Reno
q The version of TCP wherein fast retransmit and fast
recovery are added in addition to previous
congestion control mechanisms is called TCP Reno.
§ Has other features -- header compression (if ACKs are
being received regularly,omit some fields of TCP header).
§ Delayed ACKs -- ACK only every other segment.
Summary - TCP Congestion Control
LNSon - Bộ môn MMT&VT - Khoa CNTT - ĐH KHTN Tp. HCM
20
Tải về để xem bản đầy đủ
31 trang
9760
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạng máy tính nâng cao - Chương 2: TCP & Congestion control - Lê Ngọc Sơn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_mang_may_tinh_nang_cao_chuong_2_tcp_congestion_con.pdf
