PDF de programación - Temas sobre informática teórica - Problemas de investigación en Internet - Clase 11

Control de congestión

MIT 18.996: Temas sobre informática teórica: problemas de investigación en Internet
Primavera de 2002
Clase 11 – 24 de abril de 2002
Profesor: Rahul Hariharan
Escriba: Ben Leong

11.1

Los efectos de la congestión pueden verse en la Figura 11.1. Tal y como se muestra en la figura, el
rendimiento de una conexión aumenta a medida que la carga asciende hasta un punto en el que las colas
del sistema comienzan saturarse y el aumento del rendimiento se detiene. En el momento en el que la
carga ofrecida es demasiado grande y los búfers se saturan, el sistema comienza a descartar paquetes y el
rendimiento disminuye.



Figura 11.1.

Efectos de la congestión


El efecto de la congestión en el tiempo de respuesta también resulta claro de forma intuitiva. Cuando el
sistema no está congestionado, el tiempo de respuesta es breve. A medida que crece la congestión y los
paquetes se ponen en cola, el tiempo de respuesta aumenta. Finalmente, cuando se empiezan a descartar
paquetes, el tiempo de respuesta vuelve a aumentar de forma pronunciada. Las tres zonas de
funcionamiento descritas se dividen por dos puntos conocidos como codo y cliff, respectivamente. Los
algoritmos que hacen que el sistema funcione en los codos reciben el nombre de algoritmos de evasión de
congestión, mientras que los que consiguen el funcionamiento entre el codo y el cliff se denominan
algoritmos de control de congestión.

11 - 1

MIT 18.966



Clase 11 – 24 de abril de 2002



Primavera de 2002


11.2 Modelo básico

Diseñaremos la red como un sistema simple de colas con n flujos y el flujo i, 1 ≤ i ≤ n, tendrá como
rendimiento xi(t). Xgoal representa la capacidad total de la red.

Con el fin de cuantificar la “benevolencia” de un algoritmo de control de congestión, introduciremos los
siguientes parámetros:

• Eficiencia
• Equidad
• Distribución
• Convergencia

11.2.1 Eficiencia

Para que un algoritmo sea eficiente, el rendimiento total debe aproximarse a la capacidad total de la red,
esto es


11.2.2 Equidad

Son muchas las medidas de equidad que se han propuesto. La idea general se basa en que los flujos que
pertenecen a la misma clase deben constar de partes aproximadamente equivalentes del ancho de banda
disponible. La medida de la equidad que debemos adoptar para nuestras propuestas es



donde resulta evidente que,


11.2.3 Distribución

El criterio de distribución simplemente se basa en la idea de que todos los flujos deben ser capaces de
tomar decisiones de forma independiente, sin tener que obtener permiso de ningún coordinador
centralizado.

11 - 2

MIT 18.966



Clase 11 – 24 de abril de 2002



Primavera de 2002



Figura 11.2.

Convergencia



11.2.4 Convergencia

La convergencia mide el tiempo que tarda el sistema en arrancar desde cualquier punto y converger a un
estado ideal. Tal y como se muestra en la Figura 11.2, podemos medir la capacidad de respuesta y la
suavidad. La primera mide el tiempo que tarda el sistema en alcanzar el estado ideal; la suavidad, por su
parte, mide la magnitud de las oscilaciones del estado ideal incluso cuando el sistema alcanza un
equilibrio dinámico.


11.3

A continuación intentaremos obtener las condiciones necesarias para que un algoritmo logre una salida
equitativa y eficiente[1]. Nos limitaremos a la clase de controles lineales. En nuestro modelo, la red
proporcionará una realimentación binaria, y(t), que los usuarios interpretarán de la siguiente manera:

y(t) = 0 Aumento de carga
1 Disminución de carga

Como respuesta a la realimentación, la carga ofrecida en el tiempo t + 1, xi(t + 1) se calcula como función
de xi(t) e y(t) de la siguiente forma:


Condiciones de convergencia para la eficiencia y la equidad

En un caso sencillo de dos usuarios, la distribución de recursos puede representarse como un punto en un
espacio bidimensional, tal y como se muestra en la Figura 11.3. En dicha figura, el eje horizontal
representa la distribución del usuario 1 y el eje vertical, la distribución del usuario 2. Todas las
distribuciones en las que x1 + x2 = Xgoal son distribuciones eficientes. En el gráfico se muestra con la línea
continua marcada como “línea de eficiencia”. Todas las distribuciones en las que x1 = x2 son
distribuciones equitativas. En el gráfico se muestra con la línea continua marcada como “Equidad = 1”.
Las dos líneas se cortan en el punto



que es el punto óptimo. El objetivo de un esquema de control es conseguir que el sistema alcance este
punto.

11 - 3

MIT 18.966



Clase 11 – 24 de abril de 2002



Primavera de 2002



Figura 11.3.

Representación vectorial para un sistema de dos usuarios



11.3.1 Eficiencia

Para que el sistema pueda cumplir los criterios de eficiencia, deben darse las siguientes condiciones:



11.3.2 Equidad

Para que el sistema tienda a la equidad, deben cumplirse las siguientes condiciones:



Realizando algunos cálculos, podemos reescribir F(t + 1) de la siguiente manera:


donde


Observamos que la equidad mejora si c > 0 y que permanece constante si c = 0. Así, tanto



como



En otras palabras, aI y bI deben tener el mismo signo y aD y bD también deben tener el mismo signo.
Además, como mucho uno de los aI y bI y uno de los aI y aD pueden ser cero.

11 - 4



Clase 11 – 24 de abril de 2002

MIT 18.966


11.3.3 Distribución

Para que el sistema pueda cumplir los criterios de distribución, deben darse las siguientes condiciones:



Primavera de 2002


Esto implica que:



La primera condición implica que a1 > 0 y que b1 ≥ 1, mientras que la segunda condición implica que aD
≤ 0 y que bI < 1. Uniendo los dos resultados de la sección anterior, obtenemos:



Finalmente, observamos que la equidad es una función creciente de

y que

Así, para maximizar cI, hacemos que bI = 1.

11.3.4 Convergencia

Tenemos


A continuación, sumamos todos los nodos para obtener:


de donde podemos obtener


Si bI = 1, entonces la solución es


Esta expresión nos proporciona el límite de la capacidad de respuesta del algoritmo, esto es, el tiempo que
tarda en alcanzar Xgoal.

11.3.5 Conclusiones

Podemos concluir, pues, que los siguientes parámetros son los óptimos:



11 - 5



MIT 18.966

Como resultado se obtienen los siguientes controles lineales:


Clase 11 – 24 de abril de 2002



Primavera de 2002


Esto también recibe el nombre de algoritmo de crecimiento aditivo/decrecimiento multiplicativo
(CADM).

Concluiremos observando que en el modelo anterior no hemos tenido en cuenta varios factores. En
concreto:

• Hemos asumido que todos los emisores están sincronizados
• Hemos obviado la posibilidad de una realimentación desfasada
• Hemos obviado la presencia de otros flujos (> 2) en la red.
• Hemos asumido que la realimentación disponible es simplemente binaria. Quizá deberíamos

preguntarnos si podríamos obtener más datos de haber más información disponible.

Aplicación – Protocolo de control de transmisión (TCP)


11.4

El protocolo de control de transmisión [2, 3, 4, 5] (TCP) es un protocolo de ventana autocronometrado
(esto es, realiza un seguimiento de los paquetes de datos pendientes en el flujo como una ventana) que
proporciona la gestión del tiempo de espera y de las retransmisiones. Existen, asimismo, otros protocolos
basados en la velocidad que, por su parte, controlan la velocidad de transferencia de los datos enviados
por el emisor. El tamaño de la ventana determina el número de bytes de datos que pueden enviarse antes
de que resulte necesaria la aplicación de un aviso de recepción por parte del receptor.

En el modo de evasión de congestión, el TCP utiliza el algoritmo CADM para adaptarse a la congestión.
La transmisión correcta de un paquete se indica mediante un aviso de recepción (ACK) por parte del
receptor, mientras que la pérdida de un paquete es detectada por el tiempo de espera. El TCP intenta
estimar el tiempo de ida y vuelta (RTT) y la varianza del RTT con el fin de calcular un umbral adecuado
de tiempo de espera. Donde w es el tamaño de la ventana, este tamaño aumenta en uno
(aproximadamente) para cada RTT:



si se recibe un ACK; en caso de tiempo de espera de la transmisión

Durante la fase inicial de arranque lento (Slow Start), la ventana se ajusta de forma más brusca para
permitir que el TCP sature la capacidad del enlace cuanto antes. En concreto, el tamaño de la ventana se
duplica cada RTT:



Basándonos en el anterior algoritmo, el comportamiento de la ventana TCP en estado permanente es el
que se indica en la Figura 11.4. En esta figura podemos ver que el rendimiento del TCP viene dado por


Supongamos que asumimos un modelo perfecto en el que tan sólo se pierde un paquete cada vez que la
ventana de congestión se divide por la mitad. En ese caso, la probabilidad de pérdida de paquetes, p,
viene dada por:

11 - 6

MIT 18.966



Clase 11 – 24 de abril de 2002



Primavera de 2002



Esto implica



Figura 11.4.

TCP en estado permanente


y nos permite expresar el rendimiento en términos de la probabilidad de pérdida de paquetes:

Rendimiento =

Aplicación – Protocolo de control eXplícito (XCP)



11.5

El protocolo de control eXplícito[6] (XCP) es un novedoso protocolo fiable que intenta separar la
eficiencia de la realimentación explícita de la equidad para solventar la ineficiencia del ancho de banda
mediante encaminadores que agreguen información adicional a los paquetes encaminados. Basándose en
el ancho de banda disponible, el protocolo pretende reducir la ausencia de equidad provocada por grandes
desfases mediante flujos de compensación para RTT largos. Los encaminadores únicamente se encargan
del flujo adicional de tráfico.

11 - 7