Transcript CS 456: Computer Networks: Congestion Control/QoS

CS 456: Computer Networks:
Congestion Control/QoS
Prof. Varsha Apte
Slides based on William
Stallings+Tanenbaum
What is congestion?
Impact of congestion
Packet queues at links start to grow…
Packets start dropping
Sources start re-transmitting
After a while only re-transmissions occupy the network
Network resources start getting utilized in useless work (packets
in queues that get timed out and re-transmitted)
“Goodput” goes to nearly zero
Max capacity
Congestion
controls try to
avoid getting
into this
situation
Congestion Control
What is congestion control?
How is it done in example networks ?




Bus LAN
Switched LANs
Internet
Telephone network
Congestion control
Is done in some form at all layers


Flow control b/w source and destn.
Network layer congestion control is still
needed. (Why?)
Can be done at various time-scales
Congestion control and QoS
Pre-QoS: Everything “best-effort”

E.g. TCP/IP networks, congestion control is left to
TCP, i.e. TCP is a “well-behaved” source, that
adapts to congestion
Post QoS-Integrated Services: Congestion
control should be different for different
sources


Different for file-transfer/e-mail
Different for real-time-sensitive apps, e.g. voice,
video
 Different based on what type of coding is used for these
apps
Quality of Service
Quality parameters that define the
performance needs of a “flow” (i.e. a
stream of packets belonging to a
particular connection)




Reliability – Probability of delivering
packets correctly
Delay
Jitter – Variation in Packet delay
Bandwidth
QoS Requirements
Jitter Control
(a) High jitter.
(b) Low jitter.
Buffering
Smoothing the output stream by buffering
packets.
General Principles of Congestion
Control
Monitor the system .

detect when and where congestion occurs.
Pass information to where action can
be taken.
Adjust system operation to correct
the problem.
Congestion control time-scales
Long Term: Network Resource Provisioning
(sizing the network correctly)
Connection duration

Connection (call) admission control: In connection
oriented networks, decide whether to admit
connection or not
Round Trip propagation time: Explicit forward
congestion signaling
Packet Insertion Level:

Traffic shaping, policing, selective discarding
Congestion Prevention Policies
Policies that affect congestion.
5-26
Routing around congestion
(a) A congested subnet. (b) A redrawn subnet, eliminates
congestion and a virtual circuit from A to B.
Mechanisms for
Congestion Control
Implicit Congestion Signaling
Transmission delay may increase with
congestion
Packet may be discarded
Source can detect these as implicit indications
of congestion
Useful on connectionless (datagram)
networks

e.g. IP based
 (TCP includes congestion and flow control)
Backpressure
If node becomes congested it can slow down
or halt flow of packets from other nodes
May mean that other nodes have to apply
control on incoming packet rates
Propagates back to source
Can restrict to logical connections generating
most traffic
Used in connection oriented that allow hop by
hop congestion control (e.g. X.25)
Not used in ATM nor frame relay
Only recently developed for IP
Choke Packets
Earlier method takes too much time to send back
congestion message
Instead, router can send “choke” packet back to
source


Once choke packet is send, original packet is marked, so
downstream routers do not generate any more choke
packets
When choke packet comes to receiver, it decreases its traffic
rate
 E.g. by changing window size

Increase traffic rate if choke packets slow down, decrease if
more come.
e.g. ICMP source quench
Hop-by-Hop
Choke Packets
(a) A choke packet that
affects only the source.
(b) A choke packet that
affects each hop it
passes through.
•Not “QoS” aware
•“Reactive”, rather than pro-active
•Generates more packets during
congestion
Congestion Signaling
Network alerts end systems of increasing
congestion
End systems take steps to reduce offered
load
Backwards

Congestion avoidance in opposite direction to
packet required
Forwards

Congestion avoidance in same direction as packet
required
Backward Notification
Mark packets headed in the opposite
direction of the congestion
Tell source that packets transmitted on
this logical connection may encounter
congestion

Source can slow down
Forward notification
Marks packets going in the direction of
congestion
Tells the destination that these packets
experienced congestion
Destination may alert source about
congestion


At network layer
At transport layer
Categories of Explicit Signaling
Binary

A bit set in a packet indicates congestion
Credit based


Indicates how many packets source may send
Common for end to end flow control
Rate based


Supply explicit data rate limit
e.g. ATM
“Load Shedding”
Drop packets when buffers are full
Router can try to drop intelligently


Dropping older packets is better for
multimedia streaming apps
Dropping newer packets is better for data
apps (e.g. file transfer).
 Receiver may discard out-of-order packets
Random Early Detect
Drop packets before buffers are full, so
prevent congestion before it occurs

Sources will react to packet drops and slow
down (e.g. TCP)
Issues to be addressed in broadband
multi-service networks
Sources may not be doing flow control (voice, video)
Feedback is slow, (propagation time much greater
compared to transmission time)
Diverse capacity requirements – may get penalized
unfairly
Traffic patterns very different (not “Poisson”) (CBR,
VBR, very bursty)
Vastly different QoS requirements
Very high speed network  wide fluctuations in
reactive controls
ATM Example
Data rate: 150 Mbps
Cell size (Fixed): 53 bytes
Cell Insertion Time = 2.8 microsecs
Assuming US coast-to-coast, round trip
propagation delay is approx. 48 milliseconds
Suppose a file transfer is initiated, congestion
occurs, and implicit congestion control is used

Time required on the order of propagation delay
Number of cells transmitted in this time =
17000 = 7 Megabits of data
Controlling Sources
Connection admission control

Based on some traffic descriptors, determine
whether this connection can be admitted
Traffic Shaping

Make sure the traffic has certain performance
attribute (shape) e.g. not bursty
Traffic Policing

Make sure traffic sent by user is according to
contract done during connection admission
The Leaky Bucket Algorithm
(a) A leaky bucket with water. (b) a leaky bucket with packets
Leaky bucket
Let one packet out per “clock tick”
If packet arrives, queue it
If “bucket” full, packet is discarded
If packets are the same size, this enforces a
uniform rate
For variable size packets



Initialize counter to n
If packet size < counter, let packet thru and
decrement counter by packet size
If size > counter, wait until clock ticks, and reinitialized
The Leaky
Bucket
Algorithm
(a)
Input to a leaky bucket.
(1 MB burst). Network
speed is 200 Mbps (b)
Output from a leaky
bucket (2MB/sec), 1 MB
bucket size
Output from a token bucket
with capacities of (c) 250
KB, (d) 500 KB, (e) 750
KB, (f) Output from a
500KB token bucket
feeding a 10-MB/sec
leaky bucket.
The Token Bucket Algorithm
5-34
(a) Before.
(b) After.
Token bucket
Leaky bucket enforces rigid shape
Token bucket allows some “bursts”

“Save” unused credit (upto size of bucket)
Does not discard packets (in principle)
Variant can be done for variable size packets


Increment counter every clock tick by k bytes
Decrement counter when packet passes thry
Calculating burst length
Let burst length = S
Token arrival rate = r
Maximum output rate = M
Bucket capacity = C
Burst size = C + Sr
Burst size is also = M S
S = C/(M-r)
Generalized Token bucket in
ATM
Termed “leaky bucket”
Also termed “Generalized Cell Rate Algorithm”,
used to mark cells as conformant or non




Described with two parameters as GCRA (T, )
Bucket size = T + 
Bucket filled with “fluid” at rate 1/unit time (Unit time =
1 cell transmission time)
Let F(t) denote fluid in the bucket at time t.
 If cell arrives at time t, and F(t-) >= T, cell is labeled
“conformant” and F(t+) = F(t-) – T
 If F(t-) < T, cell is labeled “non-conformant” and F(t+) = F(t-)
 If the next cell arrives s time units later, then F(t+s-) = min
{F(t+)+s, T + }
ATM Leaky Bucket
Constant Bit Rate traffic (CBR) should on a
line with rate R describe itself with PCR (peak
cell rate per second) and CDVT, cell delay
variation tolerance
Parameters translate into GCRA as
GCRA(R/PCR, CDVT)
Implies a long term cell rate of PCR, with
CDVT being measure of departure from this
rate
ATM CBR…
Example: R/PCR = 5, CDVT = 1. I.e. PCR is
20 % of line rate.
Suppose initially, “bucket” is full = 6.
Cell arrival times: 0,4,9,14,16,22,24,29
Cell Labels: (C= conformant, NC= non)
 F(0-)= 6, C,F(0+)=1,F(4-)=5, C, F(4+)=0, F(9-)=5, C,
F(9+)=0, F(14-)=5, C, F(14+)=0, F(16-)=2, NC,
F(16+)=2, F(22-)=6, C, F(22+) = 1, F(24-)= 3, NC,
F(24+) = 3, NC, F(29-)=6, C, F(29+)=1
ATM VBR
Variable bit rate: much more bursty,
with idle periods
Described by: PCR, CDVT, BT (burst
tolerance), SCR (sustained cell rate)

Should conform to GCRA(R/PCR, CDVT),
and GCRA(R/SCR, BT+ CDVT)
ATM VBR example
VBR stream with R/PCR=1, R/SCR = 20, BT =
57, CDVT = 0


GCRA (1,0) means ?
GCRA (20, 57):With full bucket, allows four cells
back-to-back (times 0,1,2,3)
Ex. 2: R/PCR=5, R/SCR=10, CDVT=16, BT=20


GCRA(5,16) and GCRA (10, 36)
Bursts of five consecutive cells every 50 cell trans
times
(0,1,2,3,4,50,51,52,53,54,100,101,102,103,104,….)
(Material done on board)
Deriving an algorithm which takes
decides whether a GCRA(T, ) flow will
be admitted.