3.6 Principles of Congestion Control

[Music]

in this section we're gonna take a big

picture view of congestion control

really looking for a principled

understanding of both the causes and the

costs of congestion and we'll identify

two basic approaches for dealing with

congestion in the first place in the

next section we're going to take a look

at TCP and how it actually implements

these principles but for now we're going

to step back and take the big picture

view so you can put your pens and

pencils down and sit back think listen

put your thinking caps on as the saying

goes I think you're going to really

enjoy this and remember congestion

control really is a top five issue in

computer networking so pay attention

well let's start by asking the most

basic question what do we mean by

congestion well in formally congestion

is all about too many sources sending

too many packets too fast for a

congested network link somewhere in the

network to handle now remember remember

that links have a transmission rate and

when the arrival rate of packets exceeds

the transmission rate queues will start

to build up and delays will get larger

and larger and if the links packet

buffers fill up completely arriving

packets will be dropped and lost it's

important to remember that congestion

control is really all about multiple

senders multiple senders sending too

fast and aggregate while flow control

which we studied in the last section is

really about speed matching between a

single sender and a single receiver so

with that is background let's dive into

the causes and the costs of congestion

will do this by starting with a simple

idealized scenario you know idealized

scenarios are something that professors

love to think about and then we'll start

adding increasingly more realistic

assumptions so let's start with the

scenario shown here well look at the

case of a single router where congestion

will occur and first assume that there's

an infinite amount of buffering that's

idealized of course the router has input

and output links of capacity are bits

per second and there are two flows the

read flow and the blue flow shown here

let's take a careful look at the

low rates associated with the red flow

on the sending side there's a lambda in

that's the rate at which data is being

sent from the application layer down to

the transport layer and at the receiving

side there's a lambda out which will

refer to as the throughput that's the

rate at which data is actually delivered

up to the application layer at the

receiver and we'll want to ask the

question what happens to the throughput

as we dial up the arrival rate on the

sending side

assuming that we increase the arrival

rate for the red and the blue flows

similarly well with the case of infinite

buffering no packets are lost every

packet that sent is eventually received

and so the throughput at the receiver

equals the sender's sending rate as

shown in the plot here note though here

that the x-axis ends at R over 2 since

if each sender would it be sending at a

rate faster than R over 2 the throughput

would simply max out at R over 2 per

flow that's because the routers input

and output links can't carry more than R

bits per second of traffic R over 2 for

each of the two flows well this looks

pretty good at least from the throughput

standpoint but remember we learned in

Chapter 1 that when the arrival rate to

a link comes close to the links

transmission rate large queuing delays

can occur as shown here and so we see

already that there are costs in this

case the Leie costs even in this

idealized scenario let's see now what

happens when we drop this unrealistic

assumption about infinite buffering so

let's consider the same scenario except

that now the amount of buffering is

going to be finite recall from our study

of reliable data transfer that we

learned that senders are going to

retransmit in the face of possible

packet loss due to buffer overflows or

corruption so we're going to need to

look a little bit more carefully now at

the sending rate in particular we'll

want to make a distinction between the

rate of original data that's being

passed down from the application we'll

denote that lambda in and the overall

rate at which the transport layer is

sending

data including retransmissions will

denote this as lambda in prime the rate

at which packets arrive to the router is

lambda in prime not lambda in make sure

you've got this and the distinction

between lambda n and lambda n Prime it's

really important and as noted here

lambda N equals lambda out and lambda n

prime is going to be greater than or

equal to lambda n since it's going to

include the retransmissions alright for

this case of finite buffers let's start

with an idealized scenario still and

let's imagine that somehow magically the

sender knows whether or not there will

be free buffer space for transmitted

packet so in this case no packets are

going to be lost the source sends a

packet just buffered at the router

eventually transmitted and received at

the receiver in this case no packets are

lost and the throughput lent out here on

the y-axis equals lambda in no problems

here well except for the queuing delays

as lambda n approaches R over 2 just as

in our first scenario so let's next

relax this assumption that the sender

somehow magically knows when there's

going to be free buffer space and

consider what happens when packets can

be lost at the router when they arrive

and there's no free buffer space here we

see a packet arriving to find the

buffers full it's lost and so a copy of

the packet is retransmitted by the

sender eventually and in this case finds

free buffer space advances into the

buffer and has eventually transmitted by

the router and received at the

destination in this case when

retransmissions occur because of known

loss the plot showing the overall

arrival rate versus throughput looks

something like this at a low arrival

rate buffers will almost always be

available and every originally

transmitted packet is going to make it

through so in the slow arrival region

the arrival rate including

retransmissions which really don't occur

very often essentially equals the

receiver throughput in a unit increase

in the overall arrival rate lambda N

equals a unit increase in the throughput

lambda out that

to say that the slope of this red curve

here is close to one what's much more

interesting is the high rival rate

region here here the arriving packets

increasingly include retransmitted

packets and so the receiver throughput

no longer increases one-for-one with an

increase in the overall arrival rate and

we see that as the overall arrival rate

on the x axis approaches are over two

can't go any higher the maximum

throughput at the receiver is actually

less than R over two this gap here and

this is important to note is because in

retransmitted copies of a packet take up

to n times the transmission capacity of

a single packet but in the end these n

packet transmissions contribute only a

single packet to the throughput well now

let's see what happens if we drop the

unrealistic assumption that all of the

retransmissions are actually needed

that's to say let's assume the sender

may timeout prematurely as shown in the

example here and actually deliver two

copies of a packet to the receiver in

this example the first packets delayed

and so the sender times out eventually

in retransmits and both packets here

eventually make it to the receiver the

receiver of course only delivers one

segments worth of data up to the

application layer even though to

duplicate segments were received with

these unneeded retransmissions this just

means that there are more overall

retransmitted segments in the flow some

needed some duplicates and so the

maximum throughput drops even further

from here to here well we can summarize

what we've learned from the second

scenario by noting that congestion loss

requires retransmission and that n

retransmitted packets take up to n times

the resources that means buffers

transmission capacity as a single packet

but in the end these n packets

contribute only a single packet to the

throughput and so the maximum end-to-end

throughput can actually be significantly

less than the actual transmission

capacity of a congested router in our

third scenario we'll consider four

senders and four receivers with a sender

receiver pair

separated by two routers the red flow

now crosses two hops there again

retransmissions so we'll want to be able

to distinguish between lambda n and

lambda n prime as before and again we'll

be interested in the red flows end and

throughput lambda out now the red flow

shares a link with the blue flow here

and the green flow here and this is

critical now for a red flow packet to be

successfully transmitted from host a to

hosi it must be successfully forwarded

by both routers and this is important

because if a red packet makes it through

the first router but is lost at the

second router it'll have to be

retransmitted again by the red sender

and cross that first router again

another way to look at this example is

that the first packet transmission which

has lost at the second hop will have

essentially wasted the link buffering

and transmission capacity getting

successfully through that first hop only

to be lost at the second hop router so

given this the question we want to ask

ourselves is what happens as lambda in

prime increases for all of the flows so

here's one way to visualize and think

about answering this question as lambda

n prime increases the arrival rate to

the first hop router on the path will

increase increasing the loss rate and

now think about it asymptotically

asymptotically as the sending rate of

the first hop sender say the red sender

here goes higher than R over to this

first hop traffic will crowd out all of

the second hop traffic in this dropping

of second hop traffic will happen at all

routers meaning that the end end to hop

throughput for all flows will go to zero

as we dial up the sending rate ho zero

throughput things really can't get any

worse than zero throughput and so

another lesson we learned is that in the

multi hop scenario all of the upstream

network resources the buffers the

bandwidth used to carry a packet to a

router where it's ultimately dropped are

going to be wasted and since that packet

won't make it to the destination in any

it'll have to be retransmitted again and

attempt to reuse all of the resources

again on the end-to-end path so let's

summarize what we've learned from these

three scenarios we learned from a

throughput point of view that the best

that can happen is that the throughput

equals the rate at which traffic's being

passed down from the sender's

application layers and once a link

reaches its capacity sending more

traffic can't increase the throughput

beyond the link capacity and we saw

again that as the link utilization

approaches 1 the arrival rate of traffic

to the link approaches the links

capacity that delays can become very

large when there is packet loss we saw

that retransmitted segments whether

they're needed or not can reduce the

maximum end and throughput since links

are carrying both original and

retransmitted traffic remember an

retransmitted packets will use up to n

times the transmission capacity and

buffering as a single packet but in the

end only contribute a single packet to

the throughput and finally we saw that

in the multi hop case upstream resources

buffers bandwidth use for packets that

are eventually lost downstream are

really wasted resources and that an

overly congested scenarios this can

cause the end-to-end throughput to

actually go to zero a phenomena that's

been referred to as congestion collapse

well so we've seen that congestion is

definitely a bad thing that's why we

want congestion controls in the first

place so we can avoid those costs that

we just saw the next section we're going

to take a look at how to CP actually

does congestion control but since we're

looking at big principles here let's

step back and let's identify two basic

approaches towards congestion control

and as we'll see TCP implements both of

these well the basic approach to

congestion control is simple when a

sender detects congestion it should

decrease its sending rate that would be

lambda in Prime in our previous examples

in the first approach towards congestion

control the sender in furs congestion by

lost packet indications that might be

timeouts or triple duplicate ACKs

or by the measured RTT

in this case the network layer provides

no explicit help in indicating

congestion it simply drops or delays

packets and it's from these events that

congestion is implicitly inferred at the

sender this is the original approach

towards congestion control taken by the

tcp/ip protocol stack and it remains a

central part of TCPS congestion control

algorithm today in the second approach

towards congestion control the network

layer provides explicit feedback to the

transport layer indicating congestion

and this can happen before there's

actually loss or excessive delay as

we'll see this feedback can be provided

in several different ways

some more recent versions of TCP

implement Network assisted congestion

control together with TCP s original

into n congestion control which is

actually required well I hope you found

this material on the principles of

congestion control to be interesting we

looked at the causes and also the costs

of congestion and we identified two

basic approaches towards dealing with

congestion a network assisted approach

and an end-to-end approach and armed

with these insights I think we're ready

now to dive into the details of how to

CP actually performs congestion control

we'll do that in the next section

[Music]