PERALTA DIEGO

ROMÁN CARLOS

CAPA DE REDCAPA DE RED

Algoritmos de control de Congestión1. Principios generales2. Políticas de prevención de congestión3. Formación del tráficoa. Algoritmo leaky bucketb. Algoritmo token bucket4. Especificaciones de flujo5. Control de congestión en subredes de circuitosvirtuales6. Paquetes de obstrucción7. Pérdida de carga8. Control de jitter9. Control de congestión para multicasting

IntroducciónCuando hay demasiados paquetes en la subred, la

eficiencia se degrada – congestión.

Congestión – causada por varios factores. Memoria insuficiente, si aumenta es contraproducente. Procesadores lentos

¿ Cuál es la diferencia entre control de congestión y deflujo? Ejemplo: Computadora y líneas rápidas hacia una computadora

lenta – control de flujo Varias computadoras a varias computadoras – control

decongestión.

Principios GeneralesSe pueden ver algunos problemas de redes desde el

punto de vista de la teoría de control, lo cual lleva a dividir las soluciones en dos grupos:

Ciclo abierto. Se intenta evitar la congestión con un buen diseño. Usa algoritmos para decidir cuándo aceptar más tráfico, cuándo descartar paquetes, etc. Algoritmos no utilizan el estado actual de la red.

Ciclo cerrado. Monitorean el sistema para ubicar la congestión, pasan la información a los lugares donde se puede utilizar y ajustan la operación de los sistemas para corregir el problema.

Políticas de Prevención

Formato del Tráfico

Un método de ciclo abierto es ayudar a manejar la congestión al forzar a que los paquetes se transmitan a una razón más predecible. Esto se llama formación de tráfico.

Regula la tasa promedio de ráfagas de transmisión de datos. Reduce la congestión.

Monitorear el flujo de tráfico – traffic policing.

Algoritmo de cubeta con goteo

• Cada host conectado a la red por una cola interna finita.• Es un sistema de colas en un solo servidor con tiempo de servicio constante.• Paquetes del mismo tamaño – un paquete por tic de reloj.• Paquetes de tamaño variable – un número fijo de bytes por tic.• Algoritmo fácil de implementar.

Ejemplo Algoritmo ACG Imagina que una computadora produce datos a 25 MB/s

(200 Mbps) y la red corre a esa velocidad. Sin embargo los ruteadores solo pueden manejar esta velocidad en intervalos cortos y su rendimiento mejor es de 2 MB/s.

Los datos llegan en ráfagas de 1 MB, una ráfaga de 40 ms cada segundo.

Para reducir la tasa promedio a 2 MB/s, se podría usar este algoritmo con r=2 MB/s y una capacidad de 1 MB.

Esto significa que las ráfagas de hasta 1 MB se pueden manipular sin pérdida de datos, y que tales ráfagas están dispersas cada 500 ms, no importando qué tan rápido lleguen.

Ejemplo Algoritmo ACG

Algoritmo de Cubeta con Tokens Permite variaciones de velocidad en la salida. La “cubeta” contiene tokens en lugar de paquetes. Genera tokens a razón de 1 token/DT s. Para transmitir un paquete destruye un token de la cubeta

(cola). El algoritmo permite ahorrar permisos de envío hasta un

tamaño máximo de la cubeta de n. Eso significa que todas las ráfagas de hasta n paquetes se pueden enviar a la vez.

No se descartan paquetes cuando se llena la “cubeta” (cola), sino tokens.

Variación: Un token representa el derecho a enviar no un paquete, sino k bytes. Un paquete se transmite si cubre k bytes.

Se usan para tráfico leve entre ruteadores así como para regular la salida de un host (al igual que el de cubeta con goteras).

Algoritmo de Cubeta con Tokens

Ejemplo de Algoritmo ACTTenemos un “token bucket” con capacidad de 250 KB. Los

tokens llegan a una razón que permita salidas a 2 MB/s. Asumiendo que el token bucket está lleno cuando una ráfaga de1 MB llega, la cubeta puede vaciarse a su máxima capacidad 25 MB/s en 11 ms. Entonces, regresa a 2 MB/s hasta que se vacía completamente.

Especificaciones de Flujo La especificación del patrón de tráfico se

llama especificación de flujo. Consiste de una estructura de datos que

describe el patrón del tráfico a enviar y la calidad de servicio deseada por las aplicaciones.

Se aplica a paquetes enviados sobre un circuito virtual o a una secuencia de datagramas enviadas entre una fuente y un (o más) destino (s).

Formato de Especificaciones de FlujoAntes de que la conexión se establezca o se inicie el

envío de una secuencia de datagramas, la fuente da las especificaciones a la subred para aprobación. La subred puede aceptar o rechazar o dar una contrapropuesta.

Control de Congestión enSubredes de Circuitos Virtuales

Aproximaciones para controlar la congestión dinámicamente en subredes de circuitos virtuales:

Control de admisión – una vez que se ha identificado un problema de congestión, no se establecen más circuitos virtuales hasta que se haya solucionado.

Alternativa: Permitir nuevos circuitos virtuales pero enrutarlos cuidadosamente alrededor de las áreas congestionadas.

Control de Congestión enSubredes de Circuitos Virtuales

Paquetes de Obstrucción Un método que se usa para subredes de circuitos

virtuales y datagramas.

Cada ruteador puede monitorear la utilización de sus líneas de salida y otros recursos.

U new=A_Uold+(1-a)f

Cuando u sobrepasa un umbral, la línea de salida entra enun estado de precaución. El ruteador envía un “choke packet” al host fuente y el paquete se etiqueta (un bit en el encabezado se “enciende”).

Cuando el host obtiene el paquete de obstrucción, debe reducir x% el tráfico al destino específico.

Colas Justas El problema con usar paquetes de obstrucción es

que la acción tomada por los host es voluntaria.

Cada línea de salida en un ruteador tiene un conjunto de colas, una para cada línea de entrada. El ruteador transmite un paquete por cola en turno. Si un host manda demasiado paquetes, no afecta a otros.

Una modificación del algoritmo es tomar en cuenta los tamaños de los paquetes. Round robin que opera byte-por-byte.

Se permiten prioridades distintas para las colas.

Ejemplo: Colas Justas Weighted fair queueing.- Da prioridades

diferentes a las colas. Se usa ampliamente.

Paquetes de Obstrucción Salto por Salto A altas velocidades y en grandes distancias, un

problema con los paquetes de obstrucción es el tiempo por su propagación.

En este tiempo el host puede mandar muchos paquetes.

Una solución es los paquetes de obstrucción de salto-porsalto.

En esta cada ruteador intermedio tiene que reducir el flujo inmediatamente, que alivia la situación del último ruteador.

Este esquema alivia la congestión antes de que se pueda desarrollar, pero al costo de requerir más buffers.

Descartar la cargaLoad Shedding Ultima opción: Deshacerse de la carga. Se pueden descartar aleatoriamente o:

Tirar paquetes viejos es mejor: transferencia de archivos Tirar paquetes nuevos es mejor: multimedia

Una política para descartar paquetes: indicar en ellos la prioridad para la aplicación. El incentivo: paquetes con menor prioridad tienen un

costo menor de transmisión. Requiere un campo más en el encabezado del paquete

(1 bit) Otra opción: permitir a los host exceder los límites

acordados cuando no haya mucho tráfico, dando oprioridad baja a los paquetes excedidos.

Control de Jitter En ciertas aplicaciones (transmisión de audio o

video) importa que el tiempo de transmisión sea constante.

El jitter se puede limitar calculando el tiempo de entrega esperado para cada salto a lo largo de la ruta.

Cada ruteador verifica si un paquete va adelantado o atrasado. Indica en él el tiempo y lo envía.

Paquetes adelantados se detienen y paquetes atrasados se envían lo antes posible. En ambos casos se reduce la cantidad de jitter.

Control de Congestión para Multicasting RSVP – Resource reSerVation Protocol Permite a múltiples emisores transmitir a

múltiples grupos de receptores, receptores individuales cambian canales libremente, y optimiza el uso de ancho de banda a la vez que elimina congestión.

Trabaja en conjunto con los algoritmos de enrutado.

RSVP – Protocolo deReservación de Recursos En su forma más simple, el protocolo usa

enrutado multicast usando spanning trees.

Se le asigna una dirección al grupo. Para enviar a un grupo, el emisor pone la dirección del grupo en los paquetes.

El algoritmo de enrutado no es parte del RSVP.

RSVP – Protocolo deReservación de Recursos

RSVP – Protocolo deReservación de Recursos