REDES DE

COMPUTADORAS 2 Clase 9

Agenda

Servicios de la capa transporte

Multiplexing y demultiplexing

Transporte sin conexioacuten UDP

Principios de transferencia confiable de datos

Transporte orientado a la conexioacuten TCP

bull Estructura de un segmento

bull Transferencia confiable de datos

bull Control de flujo

bull Gestioacuten de la conexioacuten

Principios del control de congestioacuten

Control de congestioacuten en TCP

Principios de control de congestioacuten

Congestioacuten

Informalmente ldquodemasiadas fuentes enviando muchos

datos muy raacutepido para que la red lo manejerdquo

Es distinto a control de flujo eacuteste ocurre entre dos

aplicaciones

Manifestaciones

bull Peacuterdidas de paquetes (buffer overflow en routers)

bull Grandes retardos (en las colas en los router)

Uno de los problemas top-10

La capa de red no ofrece garantiacuteas de

entrega de paquetes en orden tasas de

transferencia fija llegada confiable de datos

y retardo acotado desde transmisioacuten hasta

recepcioacuten iquestCuaacuteles de estos requerimientos

son posibles de garantizar viacutea una

programacioacuten adecuada de la capa de

transporte

Entrega de paquetes en orden y llegada confiable

de datos

Causascostos de congestioacuten escenario

1 (buffer infinito sin re-enviacuteo) dos transmisores dos receptores

un router buffer tamantildeo infinito

sin retransmisioacuten

λin datos enviados por la aplicacioacuten (bytessec)

λout datos recibidos por la

aplicacioacuten (bytessec)

grandes retardos en estado congestionado (muchos paquetes esperando en cola)

maacuteximo flujo posible (throughput = C) de datos

unlimited shared

output link buffers

(C = link capacity)

Host A in original data

Host B

out

Causascostos de congestioacuten escenario

2 (buffer no infinito con re-enviacuteo) un router buffer finito

Se pierden paquetes que no tienen espacio en

buffer

transmisor retransmite paquetes perdidos

Buffer enlace de salida

finito compartido

Host A in original

data

Host B

out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 2 (a) caso perfecto sin peacuterdidas ni retransmisiones λin = λrsquoin

(b) retransmisioacuten soacutelo en caso de peacuterdida de segmentos (no por timeout

prematuro) λrsquoin gt λout

(b) retransmisioacuten de paquetes hace que λrsquoin sea maacutes grande (que el caso

perfecto) para el mismo λout (No necesariamente R3 como cota)

(c) retransmisiones innecesarias (timeout prematuros) enlaces enviacutean muacuteltiples

copias del paquete (eg dos re-enviacuteos por paquete)

ldquocostosrdquo de congestioacuten

maacutes trabajo (retransmisioacuten) para lograr el transporte de datos ldquogoodputrdquo

R2

R2 in

out

b

R2

R2 in

out

a

R2

R2 in

out

c

R4

R3

Causascostos de congestioacuten escenario 3

cuatro transmisores

rutas con multihops

timeoutretransmisiones

iquestQueacute pasa cuando λin se incrementa y λrsquoin crece

finite shared output

link buffers

Host A in original data

Host B out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Agenda

Servicios de la capa transporte

Multiplexing y demultiplexing

Transporte sin conexioacuten UDP

Principios de transferencia confiable de datos

Transporte orientado a la conexioacuten TCP

bull Estructura de un segmento

bull Transferencia confiable de datos

bull Control de flujo

bull Gestioacuten de la conexioacuten

Principios del control de congestioacuten

Control de congestioacuten en TCP

Principios de control de congestioacuten

Congestioacuten

Informalmente ldquodemasiadas fuentes enviando muchos

datos muy raacutepido para que la red lo manejerdquo

Es distinto a control de flujo eacuteste ocurre entre dos

aplicaciones

Manifestaciones

bull Peacuterdidas de paquetes (buffer overflow en routers)

bull Grandes retardos (en las colas en los router)

Uno de los problemas top-10

La capa de red no ofrece garantiacuteas de

entrega de paquetes en orden tasas de

transferencia fija llegada confiable de datos

y retardo acotado desde transmisioacuten hasta

recepcioacuten iquestCuaacuteles de estos requerimientos

son posibles de garantizar viacutea una

programacioacuten adecuada de la capa de

transporte

Entrega de paquetes en orden y llegada confiable

de datos

Causascostos de congestioacuten escenario

1 (buffer infinito sin re-enviacuteo) dos transmisores dos receptores

un router buffer tamantildeo infinito

sin retransmisioacuten

λin datos enviados por la aplicacioacuten (bytessec)

λout datos recibidos por la

aplicacioacuten (bytessec)

grandes retardos en estado congestionado (muchos paquetes esperando en cola)

maacuteximo flujo posible (throughput = C) de datos

unlimited shared

output link buffers

(C = link capacity)

Host A in original data

Host B

out

Causascostos de congestioacuten escenario

2 (buffer no infinito con re-enviacuteo) un router buffer finito

Se pierden paquetes que no tienen espacio en

buffer

transmisor retransmite paquetes perdidos

Buffer enlace de salida

finito compartido

Host A in original

data

Host B

out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 2 (a) caso perfecto sin peacuterdidas ni retransmisiones λin = λrsquoin

(b) retransmisioacuten soacutelo en caso de peacuterdida de segmentos (no por timeout

prematuro) λrsquoin gt λout

(b) retransmisioacuten de paquetes hace que λrsquoin sea maacutes grande (que el caso

perfecto) para el mismo λout (No necesariamente R3 como cota)

(c) retransmisiones innecesarias (timeout prematuros) enlaces enviacutean muacuteltiples

copias del paquete (eg dos re-enviacuteos por paquete)

ldquocostosrdquo de congestioacuten

maacutes trabajo (retransmisioacuten) para lograr el transporte de datos ldquogoodputrdquo

R2

R2 in

out

b

R2

R2 in

out

a

R2

R2 in

out

c

R4

R3

Causascostos de congestioacuten escenario 3

cuatro transmisores

rutas con multihops

timeoutretransmisiones

iquestQueacute pasa cuando λin se incrementa y λrsquoin crece

finite shared output

link buffers

Host A in original data

Host B out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Principios de control de congestioacuten

Congestioacuten

Informalmente ldquodemasiadas fuentes enviando muchos

datos muy raacutepido para que la red lo manejerdquo

Es distinto a control de flujo eacuteste ocurre entre dos

aplicaciones

Manifestaciones

bull Peacuterdidas de paquetes (buffer overflow en routers)

bull Grandes retardos (en las colas en los router)

Uno de los problemas top-10

La capa de red no ofrece garantiacuteas de

entrega de paquetes en orden tasas de

transferencia fija llegada confiable de datos

y retardo acotado desde transmisioacuten hasta

recepcioacuten iquestCuaacuteles de estos requerimientos

son posibles de garantizar viacutea una

programacioacuten adecuada de la capa de

transporte

Entrega de paquetes en orden y llegada confiable

de datos

Causascostos de congestioacuten escenario

1 (buffer infinito sin re-enviacuteo) dos transmisores dos receptores

un router buffer tamantildeo infinito

sin retransmisioacuten

λin datos enviados por la aplicacioacuten (bytessec)

λout datos recibidos por la

aplicacioacuten (bytessec)

grandes retardos en estado congestionado (muchos paquetes esperando en cola)

maacuteximo flujo posible (throughput = C) de datos

unlimited shared

output link buffers

(C = link capacity)

Host A in original data

Host B

out

Causascostos de congestioacuten escenario

2 (buffer no infinito con re-enviacuteo) un router buffer finito

Se pierden paquetes que no tienen espacio en

buffer

transmisor retransmite paquetes perdidos

Buffer enlace de salida

finito compartido

Host A in original

data

Host B

out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 2 (a) caso perfecto sin peacuterdidas ni retransmisiones λin = λrsquoin

(b) retransmisioacuten soacutelo en caso de peacuterdida de segmentos (no por timeout

prematuro) λrsquoin gt λout

(b) retransmisioacuten de paquetes hace que λrsquoin sea maacutes grande (que el caso

perfecto) para el mismo λout (No necesariamente R3 como cota)

(c) retransmisiones innecesarias (timeout prematuros) enlaces enviacutean muacuteltiples

copias del paquete (eg dos re-enviacuteos por paquete)

ldquocostosrdquo de congestioacuten

maacutes trabajo (retransmisioacuten) para lograr el transporte de datos ldquogoodputrdquo

R2

R2 in

out

b

R2

R2 in

out

a

R2

R2 in

out

c

R4

R3

Causascostos de congestioacuten escenario 3

cuatro transmisores

rutas con multihops

timeoutretransmisiones

iquestQueacute pasa cuando λin se incrementa y λrsquoin crece

finite shared output

link buffers

Host A in original data

Host B out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

La capa de red no ofrece garantiacuteas de

entrega de paquetes en orden tasas de

transferencia fija llegada confiable de datos

y retardo acotado desde transmisioacuten hasta

recepcioacuten iquestCuaacuteles de estos requerimientos

son posibles de garantizar viacutea una

programacioacuten adecuada de la capa de

transporte

Entrega de paquetes en orden y llegada confiable

de datos

Causascostos de congestioacuten escenario

1 (buffer infinito sin re-enviacuteo) dos transmisores dos receptores

un router buffer tamantildeo infinito

sin retransmisioacuten

λin datos enviados por la aplicacioacuten (bytessec)

λout datos recibidos por la

aplicacioacuten (bytessec)

grandes retardos en estado congestionado (muchos paquetes esperando en cola)

maacuteximo flujo posible (throughput = C) de datos

unlimited shared

output link buffers

(C = link capacity)

Host A in original data

Host B

out

Causascostos de congestioacuten escenario

2 (buffer no infinito con re-enviacuteo) un router buffer finito

Se pierden paquetes que no tienen espacio en

buffer

transmisor retransmite paquetes perdidos

Buffer enlace de salida

finito compartido

Host A in original

data

Host B

out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 2 (a) caso perfecto sin peacuterdidas ni retransmisiones λin = λrsquoin

(b) retransmisioacuten soacutelo en caso de peacuterdida de segmentos (no por timeout

prematuro) λrsquoin gt λout

(b) retransmisioacuten de paquetes hace que λrsquoin sea maacutes grande (que el caso

perfecto) para el mismo λout (No necesariamente R3 como cota)

(c) retransmisiones innecesarias (timeout prematuros) enlaces enviacutean muacuteltiples

copias del paquete (eg dos re-enviacuteos por paquete)

ldquocostosrdquo de congestioacuten

maacutes trabajo (retransmisioacuten) para lograr el transporte de datos ldquogoodputrdquo

R2

R2 in

out

b

R2

R2 in

out

a

R2

R2 in

out

c

R4

R3

Causascostos de congestioacuten escenario 3

cuatro transmisores

rutas con multihops

timeoutretransmisiones

iquestQueacute pasa cuando λin se incrementa y λrsquoin crece

finite shared output

link buffers

Host A in original data

Host B out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Causascostos de congestioacuten escenario

1 (buffer infinito sin re-enviacuteo) dos transmisores dos receptores

un router buffer tamantildeo infinito

sin retransmisioacuten

λin datos enviados por la aplicacioacuten (bytessec)

λout datos recibidos por la

aplicacioacuten (bytessec)

grandes retardos en estado congestionado (muchos paquetes esperando en cola)

maacuteximo flujo posible (throughput = C) de datos

unlimited shared

output link buffers

(C = link capacity)

Host A in original data

Host B

out

Causascostos de congestioacuten escenario

2 (buffer no infinito con re-enviacuteo) un router buffer finito

Se pierden paquetes que no tienen espacio en

buffer

transmisor retransmite paquetes perdidos

Buffer enlace de salida

finito compartido

Host A in original

data

Host B

out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 2 (a) caso perfecto sin peacuterdidas ni retransmisiones λin = λrsquoin

(b) retransmisioacuten soacutelo en caso de peacuterdida de segmentos (no por timeout

prematuro) λrsquoin gt λout

(b) retransmisioacuten de paquetes hace que λrsquoin sea maacutes grande (que el caso

perfecto) para el mismo λout (No necesariamente R3 como cota)

(c) retransmisiones innecesarias (timeout prematuros) enlaces enviacutean muacuteltiples

copias del paquete (eg dos re-enviacuteos por paquete)

ldquocostosrdquo de congestioacuten

maacutes trabajo (retransmisioacuten) para lograr el transporte de datos ldquogoodputrdquo

R2

R2 in

out

b

R2

R2 in

out

a

R2

R2 in

out

c

R4

R3

Causascostos de congestioacuten escenario 3

cuatro transmisores

rutas con multihops

timeoutretransmisiones

iquestQueacute pasa cuando λin se incrementa y λrsquoin crece

finite shared output

link buffers

Host A in original data

Host B out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Causascostos de congestioacuten escenario

2 (buffer no infinito con re-enviacuteo) un router buffer finito

Se pierden paquetes que no tienen espacio en

buffer

transmisor retransmite paquetes perdidos

Buffer enlace de salida

finito compartido

Host A in original

data

Host B

out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 2 (a) caso perfecto sin peacuterdidas ni retransmisiones λin = λrsquoin

(b) retransmisioacuten soacutelo en caso de peacuterdida de segmentos (no por timeout

prematuro) λrsquoin gt λout

(b) retransmisioacuten de paquetes hace que λrsquoin sea maacutes grande (que el caso

perfecto) para el mismo λout (No necesariamente R3 como cota)

(c) retransmisiones innecesarias (timeout prematuros) enlaces enviacutean muacuteltiples

copias del paquete (eg dos re-enviacuteos por paquete)

ldquocostosrdquo de congestioacuten

maacutes trabajo (retransmisioacuten) para lograr el transporte de datos ldquogoodputrdquo

R2

R2 in

out

b

R2

R2 in

out

a

R2

R2 in

out

c

R4

R3

Causascostos de congestioacuten escenario 3

cuatro transmisores

rutas con multihops

timeoutretransmisiones

iquestQueacute pasa cuando λin se incrementa y λrsquoin crece

finite shared output

link buffers

Host A in original data

Host B out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Causascostos de congestioacuten escenario 2 (a) caso perfecto sin peacuterdidas ni retransmisiones λin = λrsquoin

(b) retransmisioacuten soacutelo en caso de peacuterdida de segmentos (no por timeout

prematuro) λrsquoin gt λout

(b) retransmisioacuten de paquetes hace que λrsquoin sea maacutes grande (que el caso

perfecto) para el mismo λout (No necesariamente R3 como cota)

(c) retransmisiones innecesarias (timeout prematuros) enlaces enviacutean muacuteltiples

copias del paquete (eg dos re-enviacuteos por paquete)

ldquocostosrdquo de congestioacuten

maacutes trabajo (retransmisioacuten) para lograr el transporte de datos ldquogoodputrdquo

R2

R2 in

out

b

R2

R2 in

out

a

R2

R2 in

out

c

R4

R3

Causascostos de congestioacuten escenario 3

cuatro transmisores

rutas con multihops

timeoutretransmisiones

iquestQueacute pasa cuando λin se incrementa y λrsquoin crece

finite shared output

link buffers

Host A in original data

Host B out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Causascostos de congestioacuten escenario 3

cuatro transmisores

rutas con multihops

timeoutretransmisiones

iquestQueacute pasa cuando λin se incrementa y λrsquoin crece

finite shared output

link buffers

Host A in original data

Host B out

in original data plus

retransmitted data

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Causascostos de congestioacuten escenario 3

Otro ldquocostordquo de congestioacuten

cuando se descartan paquetes cualquier capacidad (de router) usada anteriormente pasa a ser un recurso desperdiciado

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Estrategias para control de congestioacuten

Control de congestioacuten

extremo a extremo

No hay informacioacuten de

realimentacioacuten expliacutecita de la red

La congestioacuten es inferida desde

las peacuterdidas y retardos

observados por terminales en los

extremos

Es la estrategia usada por TCP

Control de congestioacuten asistido

por la red

routers proveen realimentacioacuten a

sistemas extremos

Un Bit uacutenico indicando

congestioacuten (ej SNA DECbit

TCPIP ECN ATM)

Expliacutecitamente se informa al Tx

la tasa que el router puede

soportar

Los podemos clasificar en dos grupos amplios

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Caso de estudio Control de congestioacuten en ATM

ABR (tecnologiacutea de red capa 3 y menores)

ABR Available Bit Rate

Es un servicio ldquoelaacutesticordquo o flexible

Si camino del Tx tiene poca

carga

bull Tx deberiacutea usar ancho de

banda disponible

Si camino de Tx a Rx estaacute

congestionado

bull Tx reduce a un miacutenimo la

tasa garantizada

Celdas RM (Resource

Management)

Enviadas a intervalos por Tx entre

celdas de datos

bits en celda RM son modificados

por switches

Bit NI no incrementar tasa (=

congestioacuten moderada)

Bit CI Congestion Indication

Celdas RM son retornadas al Tx por

el Rx con bits intactos

ATM Asynchronous Transfer Mode

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Caso de estudio Control de congestioacuten

en ATM ABR

En celda RM hay campo ER (explicit rate) de dos bytes

bull Un Switch congestionado puede bajar valor de ER en la celda

bull Tasa de enviacuteo del Tx se ajusta a la tasa miacutenima soportable en el camino entre fuente y destino (la del switch maacutes criacutetico)

En celda de datos hay Bit EFCI (explicit forward congestion indicator) eacuteste es fijado en 1 por switch congestionado

bull Si celda de datos precedente a celda RM tiene el EFCI marcado el destino marca bit CI en celda RM retornada

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

TCP corriendo sobre IP espera hasta recibir tres

paquetes ACK duplicados para iniciar una

retransmisioacuten raacutepida iquestPor queacute piensa usted que los

disentildeadores de TCP no escogieron iniciar la

retransmisioacuten raacutepida tan pronto llega el primer ACK

duplicado iquestSe justifica la espera por tres ACKs

duplicados en la implementacioacuten de un protocolo

confiable en una red ATM

La retransmisioacuten no se efectuacutea ante la llegada del primer duplicado pues es posible que el primer paquete haya tomado una ruta maacutes larga y llegue con posterioridad al segundo En este caso un cambio de orden de llegada genera acuses de recibo duplicados pero no constituye peacuterdida de paquete No se justifica esperar tres ACKs en ATM pues eacutesta establece una conexioacuten entre fuente y destino luego todos los paquetes deben usar la misma ruta y con ello el orden de salida y llegada se mantiene cuando no hay peacuterdidas

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Control de Congestioacuten en TCP Usa control extremo a extremo (sin

asistencia de la red)

Tx limita su ventana de transmisioacuten

Si Rx tiene espacio se tiene

CongWin es dinaacutemica y funcioacuten de la

congestioacuten percibida de la red

RcvWindow es el nuacutemero de bytes que

el Rx puede recibir en su buffer la suponemos grande y no limita la tasa de enviacuteo

iquestCoacutemo el Tx percibe la

congestioacuten

Evento de peacuterdida = timeout oacute 3

acks duplicados

Tx TCP reduce tasa (CongWin)

despueacutes de un evento de

peacuterdida

Hay tres mecanismos

AIMD (Additive-Increase

Multiplicative-Decrease)

ldquoPartida lentardquo

Conservativo despueacutes de

evento de timeout

tasaAprox

= CongWin

RTT

[Bytessec]

LastByteSentminus LastByteAckedle minCongWin RcvWindow

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

TCP AIMD (Additive-Increase

Multiplicative-Decrease)

Decrecimiento

multiplicativo reducir

CongWin a la mitad luego

de peacuterdida

Aumento aditivo aumenta CongWin en 1 MSS cada RTT en ausencia de peacuterdida En algunas implementaciones CongWin incrementa en MSSx(MSSCongWin) por cada ACK recibido

MSS (Maximum Segment Size) es la maacutexima cantidad de datos que se enviacutea en cada segmento sin fragmentarse

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Indique queacute protocolo usa el tamantildeo de

segmento maacuteximo (MSS Maximum

Segment Size) iquestA queacute corresponde

El MSS es usado por TCP Corresponde al

MTU (Maximum Transmission Unit) maacutes

pequentildeo en la ruta de la fuente al destino

Usando segmentos de tamantildeo MSS TCP

asegura que sus paquetes no seraacuten

fragmentados

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Aumento aditivo La idea es aumentar un MSS luego de un RTT

Podemos aproximarnos aumentando la CongWin cada vez

que se recibe un ACK de manera que al completar 1 RTT

hayamos sumado un MSS

Se enviacutea como maacuteximo CongWin bytes y esperamos por el acuse de recibo

NumSegmentos= NumAkcs=CongWin

MSS

Incr=MSS

NumAkcs=

MSS

CongWin

MSS

=MSSlowast MSS

CongWin

Incr Incremento por cada ACK

RTT

CongWin

Si hay ACK retardados el incremento debe ser

mayor

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Partida lenta en TCP (slow start)

Cuando la conexioacuten comienza CongWin = 1

MSS

bull Ejemplo MSS = 500 bytes

amp RTT = 200 msec

bull Tasa inicial = 20 kbps

Ancho de banda disponible

puede ser gtgt MSSRTT

bull Es deseable aumentar tasa

raacutepidamente hasta una tasa

respetable

Cuando la conexioacuten comienza aumentar tasa exponencialmente raacutepido hasta tener primer evento de peacuterdida

Se le llama Slow Start porque parte desde tasa muy abaja

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Partida lenta en TCP

Cuando la conexioacuten

comienza aumentar tasa

exponencialmente hasta

primera peacuterdida

bull Duplicar CongWin cada RTT

bull Es hecho incrementando CongWin en 1 MSS por cada

ACK recibido

Resumen tasa inicial es lenta

pero se acelera

exponencialmente raacutepido

Host A

RT

T

Host B

time

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Reaccioacuten ante eventos de timeout

iquestCuaacutendo deberiacutea cambiar el aumento de exponencial a lineal

Un buen criterio es Cuando CongWin llega a 12 de su valor antes del timeout

Implementacioacuten Umbral variable (variable threshold)

Ante evento de peacuterdidas el umbral es fijado en 12 de CongWin justo antes de la peacuterdida

Tahoe primera versioacuten de control de congestioacuten en TCP No distinguiacutea entre timeout o ACK duplicados Reno versioacuten siguiente en TCP Siacute distingue timeout de ACK duplicados Es como TCP opera hoy

3 ACKs Duplicados Evento

umbral

Mejor

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Reaccioacuten ante eventos de timeout

Despueacutes de 3 ACKs

duplicados

bull CongWin baja a la mitad

bull Luego la ventana crece

linealmente

Despueacutes de un timeout

bull CongWin es fijada en 1

MSS

bull Luego la ventana crece

exponencialmente hasta un

umbral luego crece

linealmente

3 ACKs duplicados indican

que la red es capaz de

transportar algunos

segmentos (soacutelo llegan

fuera de orden en el Rx)

Se perdioacute uno pero

llegaron los otros y por

eso tenemos ACKs

duplicados

timeout antes de 3

duplicados es ldquomaacutes

alarmanterdquo (no llegaron)

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

En ausencia de errores y cuando el buffer de recepcioacuten es

muy grande la tasa promedio de transferencia de TCP

durante un RTT se puede aproximar por (Tamantildeo de

Ventana de congestioacuten)RTT Muestre un diagrama que

explique la deduccioacuten de esta expresioacuten iquestEs esta expresioacuten

vaacutelida para todo valor de ldquoVentana de Congestioacutenrdquo

Luego de enviar la ventana W el Tx debe esperar la llegada del acuse de recibo maacutes antiguo para retomar la transmisioacuten

No es vaacutelida siempre pues conforme la ventana de congestioacuten aumenta aumenta la utilizacioacuten del canal y cuando eacutesta alcanza 100 no es posible seguir aumentando la tasa pues la tasa de transmisioacuten del enlace pone una cota maacutexima

Tx Rx

RT

T W

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Resumen Control de Congestioacuten en TCP

Cuando CongWin estaacute bajo el Threshold (umbral) Tx estaacute en fase slow-start la ventana de transmisioacuten crece exponencialmente (un MSS por cada ACK)

Cuando CongWin estaacute sobre Threshold Tx estaacute en fase abolicioacuten de congestioacuten la ventana crece linealmente (aprox un MSS por cada RTT)

Al tercer ACK duplicados Threshold pasa a CongWin2 y CongWin pasa a Threshold

Cuando ocurre un timeout Threshold pasa a CongWin2 y CongWin se lleva a 1 MSS

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Control de Congestioacuten del Tx TCP

SS or CA

SS or CA

SS or CA

Congestion

Avoidance (CA)

Slow Start (SS)

State

CongWin y Threshold no

cambian

Increment duplicate ACK count for

segment being acked

Duplicate ACK

Ingresa a Partida Lenta (slow

start)

Threshold = CongWin2

CongWin = 1 MSS

Set state to ldquoSlow Startrdquo

Timeout

Recuperacioacuten raacutepida

implementando reduccioacuten

multiplicativa CongWin no

caeraacute a 1 MSS

Threshold = CongWin2

CongWin = Threshold

Set state to ldquoCongestion Avoidancerdquo

Loss event

detected by

triple duplicate

ACK

Aumento aditivo resulta en

aumento de CongWin en apox

1 MSS cada RTT

CongWin = CongWin+MSS

(MSSCongWin)

ACK receipt for

previously

unacked data

Resulta en una duplicacioacuten de

CongWin cada RTT

CongWin = CongWin + MSS

If (CongWin gt Threshold)

set state to ldquoCongestion

Avoidancerdquo

ACK receipt for

previously

unacked data

Commentary TCP Sender Action Event

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Throughput Simplificado de TCP (tasa de

transferencia de datos lograda) iquestCuaacutel es el throughput promedio de TCP como una funcioacuten del tamantildeo

de ventana CongWin y RTT

bull Ignoremos slow start ya que al ser exponencial es una fase muy

corta

TCP pide ancho de banda adicional al incrementar W en 1 MSS por

cada RTT hasta una peacuterdida

Sea W el tamantildeo de la ventana (en bytes) cuando ocurre una peacuterdida

Cuando la ventana es W el throughput es WRTT

Justo despueacutes de la peacuterdida la ventana cae a W2 y el throughput a

W2RTT

Throughput promedio entre W2RTT y WRTT es 075 WRTT

Esto debido a que el throughput crece linealmente entre ambos

valores

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Futuro de TCP Ejemplo segmentos de 1500 bytes RTT de 100ms queremos

throughput de 10 Gbps

Requiere tamantildeo de ventana CongWin W = 83333 (segmentos

en traacutensito)

Throughput en teacuterminos de tasa de peacuterdida (L) es

L=(bytes perdidos)(Nuacutemero total enviados)

Para el throughput deseado con el algoritmo de control de

congestioacuten actual se toleran probabilidades de peacuterdida de soacutelo L

= 210-10 Wow (1 cada 5 mil millones de segmentos)

Se requieren nuevas versiones de TCP para enlaces de alta

velocidad (interesados ver RFC 3649)

LRTT

MSS=hputAvgThroug

122

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

iquestPor queacute la ventana de congestioacuten de

TCP soacutelo se reduce a la mitad cuando

la peacuterdida es detectada por 3 ACKs

duplicados mientras que se reduce a 1

MSS cuando la peacuterdida es detectada

por timeout

Porque la llegada de 3 ACKs duplicados es una

indicacioacuten que paquetes posteriores al perdido siacute

llegaron luego esta situacioacuten de congestioacuten es

menos criacutetica que cuando hay timeout sin 3 ACKs

duplicados

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Equidad en TCP

Objetivo de la Equidad (fairness) Si K sesiones TCP

comparten un mismo enlace de ancho de banda R cada

una deberiacutea tener una tasa promedio de RK

TCP connection 1

Router cuello de botella de capacidad R

TCP connection 2

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

iquestPor queacute TCP es justo

Supongamos dos sesiones compitiendo

Aumento aditivo da pendiente de 1 como aumento de throughout

Reduccioacuten multiplicativa reduce throughput proporcionalmente

R

R

Recta de Igual tasa capacidad compartida

Throughput Conexioacuten 1

Through

put Cone

xioacuten 2

Peacuterdida decrece tasa en factor de 2

Abolicioacuten de congestioacuten aumento aditivo

Abolicioacuten de congestioacuten aumento aditivo

Peacuterdida decrece tasa en factor de 2

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

Equidad

Equidad y UDP

Aplicaciones Multimedia no

usan TCP

bull No quieren tasa limitada

por control de congestioacuten

En su lugar usan UDP

bull Enviacutean audioviacutedeo a tasa

constante y toleran

peacuterdidas de paquetes

Aacuterea de investigacioacuten

Hacerlas amistosas con

TCP (TCP friendly)

Equidad y conexiones TCP

paralelas

Nada previene a las aplicaciones de

abrir conexiones paralelas entre

dos hosts

Navegadores WEB hacen esto

Ejemplo Sea un enlace de tasa R

soportando 9 conexiones

Una aplicacioacuten nueva pide 1

conexioacuten TCP obtendraacute R10

Si la aplicacioacuten nueva pide 11

conexiones TCP eacutesta obtendraacute

11R20 maacutes de R2

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten

En una subred hay 6 usuarios viendo

viacutedeos de Youtubecom viacutea conexiones

TCP iquestSi eacutestos fueran los uacutenicos

usuarios queacute fraccioacuten de la capacidad

de un enlace congestionado le deberiacutea

corresponder a cada uno

16

Nota Se supone que ese es el uacutenico traacutefico en el

enlace congestionado en otro caso seraacute la misma

fraccioacuten del traacutefico para cada conexioacuten