Advanced Computer Networks: Lecture 37 - 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 (586.48 KB, 31 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
1
Lecture No. 37
2
Congestion Control
• Basics: problem, terminology,
approaches, metrics
• Solutions
– Routerbased: queuing disciplines
– Hostbased: TCP congestion control
• Routerbased congestion avoidance
– DECbit
– RED gateways
• Quality of service
3
Routerbased
Congestion Avoidance
DECbit: Destination Experiencing
Congestion bit
• Developed for Digital Network Architecture
• Basic idea
– One bit allocated in packet header
– Any router experiencing congestion sets bit
– Destination returns bit to source
– Source adjusts rate based on bits
• Note that responsibility is shared
– Routers identify congestion
– Hosts act to avoid congestion
5
DECbit (continued)
• Routers
– Calculate average queue length
– Averaging interval spans last busy+idle cycles
• busy: queue is nonempty
• idle: queue is empty
– Set DECbit when:
average queue length >= 1
• Why 1?
– Maximizes power function
– Smaller values result in more idle time
– Larger values result in more queuing delay
6
DECbit – Average Queue Length
7
DECbit (continued)
• Hosts
– Count number of marked packets in last congestion
window of packets
– Increase congestion window by 1 if less than 50% of
packets marked
– Decrease congestion window by factor of 7/8
if greater than or equal to 50% of packets marked
• Why 50%?
– Maximizes power function
• Resurfaced as Explicit Congestion Notification (ECN)
in last few years, proposed TCP extension
8
Congestion Control
• Basics: problem, terminology,
approaches, metrics
• Solutions
– Routerbased: queuing disciplines
– Hostbased: TCP congestion control
• Routerbased congestion avoidance
– DECbit
– RED gateways
• Quality of service
9
Random Early Detection
(RED) Gateways
• Developed for use with TCP
• Basic idea
– Implicit rather than explicit notification
– When a router is “almost” congested
– Drop packets randomly
• Responsibility is again shared
– Router identifies, host acts
– Relies on TCP’s response to dropped packets
10
Weighted Running Average Queue
length
11
Random Early Detection (RED)
Gateways
• Hosts
– Implement TCP congestion control
– Back off when a packet is dropped
• Routers calculate average queue length (as
exponential moving average)
length = (A) measurement + (1 – A) length
• Routers act based on average queue length
– Below minimum length, keep new packets
– Above maximum length, drop new packets
– Between the two, drop randomly
12
RED Thresholds on a FIFO Queue
13
Drop Probability Function for RED
14
Random Early Detection (RED)
Gateways
• Router drop probability depends on
two factors
– Relation of average queue length to
bounds
– Number of packets (count) since
• Last drop, or
• Length outside random drop range
15
RandomEarlyDetection(RED)
Gateways
ã Routercalculates
Baseprobabilityfordrop:
baseProb=MaxPì(lengthminThresh)/
(maxThreshminThresh)
Actualprobabilityfordrop
prob=baseProb/(1baseProbìcount)
16
Random Early Detection (RED)
Gateways
• Parameter values
– MaxP is typically 0.02 (drops roughly 1 in 50
packets at midpoint)
– min (threshold) is typically max/2
• Choosing parameters
– Carefully tuned to maximize power function
– Confirmed through simulation
– But answer depends on accuracy of traffic model
– May create oscillating behavior in the Internet
17
TuningtheREDGateways
ã Dropsroughlyinproportiontoflowbandwidths
ã Queuesizechanges
Duetodifferenceininput/outputrates
Notrelatedabsolutemagnitudeofthoserates
ã minmustallowreasonablelinkutilization
ã Differencebetweenminandmaxthresholds
Largeenoughtoabsorbburstiness
Inpractice,canusemax=2ìmin
ã Usepenaltyboxforoffenders!
18
Hostbased Congestion Avoidance
TCP Vegas – Basic Idea
• Watch for signs of queue growth
• In particular, difference between
– Increasing congestion window
– Stable throughput (presumably at maximum
capacity)
• Keep just enough “extra data” in the network
– Time to react if bandwidth decreases
– Data available if bandwidth increases
20
Trace of TCP Vegas Congestion
Avoidance Mechanism
21
TCP Vegas Implementation
• Estimate uncongested RTT, baseRTT, as
minimum measured RTT
• Calculate expected throughput as congestion
window / baseRTT
• Measure throughput each RTT
– Mark time of sending distinguished packet
– Calculate data sent between send time and
receipt of ACK
22
TCP Vegas Implementation
• Act to keep the difference between estimated and
actual throughput in a specified range
– Below min threshold, increase congestion
window
– Above max threshold, decrease congestion
window
• Additive decrease used only to avoid congestion
• Want between 1 and 3 packets of extra data (used
to pick min/max thresholds)
23
Congestion Control & Resource
Allocation
• Basics: problem, terminology,
approaches, metrics
• Solutions
– Routerbased: queuing disciplines
– Hostbased: TCP congestion control
• Routerbased congestion avoidance
– DECbit
– RED gateways
• Quality of service
24
Quality of Service
Outline
– Realtime Applications
– Integrated Services
– Differentiated Services
25
