Post on 28-Jan-2016
SWITCHING, ENCOLAMIENTOSWITCHING, ENCOLAMIENTOY SCHEDULING Y SCHEDULING
Seminario de Redes de Alta VelocidadSeminario de Redes de Alta VelocidadMayo 2006
Tomás Urra B.
Índice Presentación
1. Introducción
2. Objetivos Switch ATM
3. Arquitectura Switch ATM
4. Switching Fabric
5. Resolución de Contenciones
6. Buffering
7. Encolamiento
8. Scheduling
Introducción
ATM es un sistema orientado a la conexión, maneja celdas (paquetes).
Sistemas no orientado a la conexión manejan datagramas.
En un SVC (Switched Virtual Circuit), ATM requiere de protocolo de señalización antes de enviar cualquier dato.
Se necesitan dispositivos a nivel de capa de red ( Capa 3).
Introducción
Recordando la forma de los enlaces en ATM: Virtual Path (VP) Virtual Channel (VC) Transporte Unidireccional de Celdas ATM a través de un mismo
Camino / Canal.
Introducción
ATM utiliza switches (conmutadores) para encaminar celdas del sistemas origen al sistema destino.
Host A quiere enviar datos a host B.
Interfaz Interfaz entradaentrada
VCI VCI EntradaEntrada
Interfaz Interfaz SalidaSalida
VCI VCI SalidaSalida
22 55 11 1111
Interfaz Interfaz entradaentrada
VCI VCI EntradaEntrada
Interfaz Interfaz SalidaSalida
VCI VCI SalidaSalida
00 77 33 44
Interfaz Interfaz entradaentrada
VCI VCI EntradaEntrada
Interfaz Interfaz SalidaSalida
VCI VCI SalidaSalida
33 1111 00 77
Tabla: Switch 2Tabla: Switch 2
Tabla: Switch 3Tabla: Switch 3
Tabla: Switch Tabla: Switch 11
Introducción
Switch ATM : Conjunto de links de entradas y salidas.
Switching Fabric: Parte que realiza efectivamente la función de conmutación.
Switch Elements: son los elementos básicos de un Switching Fabric.
Realiza 2 funciones básicas : Traslado VPI / VCI. Transporte de Celdas desde la entrada hasta su salida.
Introducción
Criterios de diseño :
Retardo en los nodos debe ser mínimo.
Perdida de paquetes debe ser mínima.
Para prevenir perdida excesiva de celdas en el caso de colisiones internas, se debe disponer de buffers dentro de los switch elements.
Objetivos Switch ATM
Flexibilidad: para soportar una amplia variedad de servicios.
Escalabilidad: para permitir un gran aumento en la cantidad de conexiones.
Eficiencia: para maximizar la utilización de los enlaces.
QoS garantizada: para otorgar tráfico en tiempo real con bajo jitter y permitir funciones de CAC simples.
Aislamiento: para reducir interferencias entre las distintas clases de servicios y conexiones.
Equitatividad: para permitir una buena distribución del ancho de banda disponible
Arquitectura Switch ATM
Multiplexores Demultiplexores
Puerto de entrada
Puerto de salida
1
L
1 1
N N
SwitchFabric
Unidad de Control
Switching Fabric
Implementar el Switching Fabric es complejo.
Se pueden clasificar en las siguientes categorías:
Memoria Compartida
Medio Compartido Bus TDM
División Espacial Single Path Multi Path
Auto-Ruteo
Switching Fabric Switching Fabric
1. Memoria Compartida1. Memoria Compartida Basado en una memoria rápida y de gran capacidad, que es accesada por los puertos lógicos de entrada y salida.
La memoria se organiza en filas lógicas.
Existen mas de 6 métodos distintos de cómo implementar las filas en la memoria:
Complete Partitioning (CP); Complete sharing (CS); Complete sharing subject to maximum
(CSMX); Complete sharing subject to allocated
minimums; etc……
Tipo Memoria compartida
Switching FabricSwitching Fabric
2. Bus TDM2. Bus TDM
La red de interconexión puede ser implementada a través de multiplexacion por tiempo (TDM).
La velocidad del bus debe ser mayor/igual que la suma de las velocidades de los puertos de entrada.
Ejemplos son los switch NEC ATOM, IBM PARIS.
Tipo BUS TDM
Switching FabricSwitching Fabric
3. Single Path3. Single Path
Todas la entradas y todas las salidas operan a la misma velocidad.
Existe solo un camino desde la entrada hasta la salida.
En esta configuración no existe bloqueo de celdas interno
Knockout Switch
Entradas
Entradas
Salidas
Switching FabricSwitching Fabric
4. Auto- Ruteo4. Auto- Ruteo Las celdas son enrutadas a través de la información contenida en el header.
Puede manejar un alto nivel de paralelismo.
Se componen por elementos conmutadores básicos en cascada.
También conocidas como redes Banyan.
Tipo auto-ruteo
Resolución de ContencionesResolución de Contenciones
Cuando celdas de 2 entradas distintas requieren salir por el mismo puerto de salida (compiten por el mismo recurso), se producen contenciones.
Existen varias técnicas para resolver las contenciones
• Dependiendo de la arquitectura del switch fabric es posible ocupar una u otra técnica de contención.
Resolución de ContencionesResolución de Contenciones
Estrategias
En una estrategia de Buffering cuando dos celdas están competiendo por un mismo recurso una gana y la otra pierde. La celda que pierde se guarda en un buffer para una transmisión posterior.
En una estrategia de Backpressure para evitar problemas de contención se envían señales a los módulos posteriores indicando que buffer de salida se encuentran disponibles.
Con una estrategia de Deflection la celda que pierde la contención se encamina a través de otro camino mas largo al mismo puerto de salida.
Con la estrategia de Descarte simplemente se descarta la celda que pierde la contención.
BufferingBuffering
INPUT BUFFERINGINPUT BUFFERING
OUTPUT BUFFERINGOUTPUT BUFFERING
VIRTUAL OUTPUT BUFFERINGVIRTUAL OUTPUT BUFFERING
INPUT OUTPUT BUFFERINGINPUT OUTPUT BUFFERING
CENTRAL BUFFERINGCENTRAL BUFFERING
BufferingBuffering INPUT BUFFERING
1 1
m m
1 1
m m
BufferingBuffering
INPUT BUFFERING
Se genera un nuevo problema llamado “Bloqueo de cabecera de línea” (HOL).
BufferingBuffering
INPUT BUFFERING
HOL blocking, puede ser mejorada con una disciplina no-FIFO de selección de ventana.
Buffering
OUTPUT BUFFERING
No existe HOL blocking en este caso, pero puede haber pérdida de celdas por congestión.
1 1
m m
Buffering
OUTPUT BUFFERING
Para evitar pérdida de celdas antes de arribar a una salida, el medio de transferencia interno (switch fabric) debe ser N veces más rápido que la tasa de entrada.
1
N
Buffering
VIRTUAL OUTPUT BUFFERING
Se resuelve el problema de HOL dividiendo lógicamente cada buffer de entrada en N buffer virtuales.
1 1
m
m
out1
outm
out1
outm
Buffering
INPUT & OUTPUT BUFFERING
Se usa cuando el número de celdas entrantes es superior al que puede aceptar una salida.
1 1
m m
Buffering
CENTRAL BUFFERING
Cada salida rescata sus celdas desde el buffer central.
Se requiere un complejo sistema de administración de memoria.
1 1
m m
S/P
S/P
S/P
P/S
P/S
P/S
Buffer Buffer ManagerManager
High Speed Parallel Bus
Central Buffer
Encolamiento
Estructuras de Encolamiento
Estas estructuras se pueden organizar de la siguiente forma:
• Encolamiento por grupo
Grupo por categoría de servicio Grupo por clase de servicio Grupo por definición de conformación
• Encolamiento por VC/VP
Encolamiento
Encolamiento por Grupo
Categoría de Servicio
Aislamiento por servicio Se divide la capacidad de enlace, garantizar QoS por cada servicio. Idealmente #colas = #categorías de servicio.
Arbitrador
CBR
VBR
UBR
Capacidad del enlace
Encolamiento
Encolamiento por Grupo
Clase de Servicio Dentro de cada categoría de servicio podemos definir clases de servicio
definiendo valores umbrales para cada parámetro.
Arbitrador
Capacidad del enlace
CBR
CBR/rt-VBR
nrt-VBR
nrt-VBR
ABR
UBR
CTD=250ms
CTD=2500ms
CLR=10e-7
CLR=10e-4
Encolamiento
Encolamiento por Grupo
Definición de Conformación Ejemplo: servicios VBR pueden ser clasificados en VBR.1, VBR.2, VBR.3,
basados en la definición de los descriptores de trafico y el significado del bit CLP.
Arbitrador
Capacidad del enlace
CBR.1
VBR.1
VBR.2/VBR.3
UBR.1
UBR.2
Encolamiento
Encolamiento por VC/VP
Las celdas de cada VC o VP son encoladas separadamente Encolamiento por VC es mas complicado y costoso.
Arbitrador
VC1
VC2
VC3
VCn
Todas estas estructuras de encolamiento necesitan de mecanismos de Scheduling para manejar adecuadamente los Buffers
Scheduling
Definición:
Un mecanismo de scheduling o planificación es aquél que se debe implementar en cada fila o encolamiento existente en un nodo de manera que exista un orden en la atención de las mismas que permitan lograr los objetivos de QoS.
Scheduling
Mecanismos primitivos: FIFO Es el más comúnmente utilizado en redes. Muy fácil de implementar. Trabaja en forma correcta si no hay congestión. No es demasiado eficiente ni es justo con los distintos usuarios.
Scheduling
Mecanismos primitivos: ROUND ROBIN (RR)
Los paquetes se clasifican y se envían a ‘n’ colas.Las colas se sirven en el orden 0,1,...,n-1.
Ventajas:•Fácil implementación.•Repartición justa de BW para paquetes iguales.
Desventajas:•No garantiza BW ni retardo (delay).•No proporciona ninguna protección frente a usuarios que hagan un uso indebido de la red.
Scheduling
...ambos métodos no son empleados por si solos.
A pesar de que ambos son fáciles de implementar, ninguno de ellos asegura calidad de servicio (pej, retardo medio) con cargas elevadas.
Como no se basan en un sistema de prioridades o pesos, no es posible diferenciar paquetes de distintas categorías de servicios (CBR, VBR, UBR).
De este modo, un usuario cualquiera puede congestionar la red.
En la práctica:
Scheduling
Mecanismos de Scheduling
Se tiene una serie de colas por atender. Un “arbitro” encarga de la asignación de BW para las colas. El algoritmo implementado por el “árbitro” debe ser robusto. De a cuerdo a la organización de estos “árbitros”, se derivan dos grupos.
S1
S1
S2
S3
S1
S1
Flat o “un nivel” Scheduling Hierarchical Scheduling
Scheduling
Mecanismos de Scheduling Flat Scheduling
se emplea un planificador para atender la totalidad de las filas. Con ello divide el BW disponible entre ellas.
Hierarchical Scheduling existe un planificador distinto para cada conjunto de filas, así como
planificadores entre los distintos niveles de planificación. Cada planificador puede emplear un algoritmo de schedule diferente. Facilita la división (simétrica o asimétrica) del BW entre distintos tipos
de tráfico.
Scheduling
Clasificación:
Los algoritmos de scheduling pueden ser clasificados en 3 categorías:
1. Priority-based scheduling
2. Fair-share scheduling Work-conserving fair-share scheduling Non-Work-conserving fair-share scheduling
3. Traffic Shaping
Scheduling
1. Priority-based scheduling
A cada fila le es asignada una cierta prioridad de acuerdo a algún criterio. Una fila de baja prioridad sólo será atendida cuando no existan paquetes en filas de mayor prioridad.
CBR y rt-VBR tienen requerimientos de retardo muy estrictos.
UBR no tiene requerimientos de retardo. Es simple y eficiente operando con un
reducido número de filas.
CBR, rt-VBR
Nrt-VBR
ABR, GFR
UBRp
rio
rid
ad
Scheduling
1. Priority-based scheduling
Scheduling 1.1 Shortest Job Next (SJN)
•Escoge los paquetes en función de la longitud para un instante dado.•Los paquetes de menor longitud salen con anterioridad.
Ventajas: Minimiza el tiempo de espera en la cola. Paquetes pequeños no tienen que
esperar. Desventajas:
Es muy difícil predecir la longitud de los diferentes paquetes que entran al sistema.
Si todos los paquetes tienen la misma longitud, se comporta como FIFO.
Scheduling
1.2 Static Priority Scheduling(SPS)
Los paquetes se envían a ‘n’ colas, asignadas con una prioridad 0,...(n-1). Los paquetes en las colas de mayor prioridad obtienen servicio primero, mientras que los paquetes de la cola ‘m’ sólo reciben servicio si las colas 0,...(m-1) están vacías.
Ventajas: Las filas de alta prioridad obtienen alto
rendimiento, bajo retardo y elevado BW. Desventajas:
Las filas de baja prioridad se encuentran a merced de las de alta prioridad.
Las filas de baja prioridad no obtienen servicio si las colas de alta prioridad saturan la salida.
Scheduling
2. Fair-share scheduling
•Este tipo de algoritmo asigna a cada fila un “peso” o ponderación en vez de un prioridad. De este modo, se garantiza que cada fila será atendida con un BW proporcional al peso de ésta.
•El objetivo es dividir la totalidad del BW disponible de manera justa entre todas las filas, esto es, se garantiza la atención de la totalidad de las filas en un ciclo, pero no necesariamente con el mismo BW.
•¿Qué sucede si un canal envía paquetes a una tasa mayor a la asignada, pero esta mayor tasa no afectara a los demás usuarios?
Scheduling
2. Fair-share scheduling
Existen para ello 2 criterios:
•Rate allocation service discipline :permite una tasa de tx mayor a la asignada mientras no se afecte el desempeño del resto de las filas.
•Rate controlled service disciplines : no permite la tx a una tasa mayor a la asignada bajo ninguna circunstancia.
Work conserving fair-sharescheduling algorithm
Rate allocation
Non-Work conserving fair-sharescheduling algorithm
Rate controlled
Scheduling
2.1 Work conserving Fair-share scheduling
En esta disciplina el servidor nunca se encuentra ocioso mientras exista un paquete a transmitir en alguna fila.
Existen varios algoritmos que implementan este método:
1. Fair Queuing (FQ)2. Virtual Clock (VC) 3. Pulse Scheduling (PS)
4. Weighted Round Robin (WRR) 5. Deficit Round Robin (DRR)6. Rotating Priority Queues (RPQ)7. Delay Earliest-Due-Date (Delay-EDD)8. Packet-Based Generalize Processor Sharing (PGPS)9. Self-Clock Fair Queuing (SCFQ)10. Worst Case Fair-Weighted Fair Queuing (WF2Q)11. Leap Forward Virtual Clock (LFVC)12. Frame-Based Fair Queuing (FFQ)13. Variation Fluctuation Smoothing (VFS)
Scheduling
2.1.1 Fair Queuing (FQ)
Asume encolamiento por VC/VP
Si N filas comparten un enlace de salida, cada uno debiera tener 1/N del BW. Si un canal ocupa menos, el resto se reparte equitativamente entre los canales restantes.Lo anterior se logra mediante un servicio bit-by-bit Round Robin (RB).
Fair Queuing emula RB. Cada paquete posee un número que indica
cuando éste debiera recibir servicio, de acuerdo a RB. Se atienden los paquetes en orden creciente de este número.
Scheduling
2.1.2 Virtual Clock (VC)
Esta disciplina emula Time Division Multiplexing (TDM).
A diferencia de TDM slots no son fijos.
A cada paquete es asignado un virtual transmission time, que corresponde al tiempo en el cual el paquete debiera ser transmitido, usando TDM.
Por ejemplo, si un cliente contrata una tasa de 5 [paq/s], los paquetes provenientes de dicho cliente estarán separados entre sí por un virtual transmission time de 0.2[s].
Scheduling
2.1.3 Delay Earliest-Due-Date
En el algoritmo clásico EDD (Earliest-Due-Date), a cada paquete le es asignado un deadline time(tiempo límite), y éstos son atendidos en orden creciente de deadlines times. Delay-EDD es una extensión de lo anterior, donde el servidor negocia un contrato de servicio con cada fuente: ‘si la fuente obedece a una tasa peak y promedio, el servidor le garantiza un retardo máximo para esos paquetes’.
Reservando un BW equivalente al peak-rate, Delay-EDD asegura para cada canal un límite en el retardo. Usado en servicios tiempo real.
Por ejemplo, si un cliente asegura que enviará paquetes cada 0.2[s] y el retardo máximo otorgado por el servidor es 1[s], el k-ésimo paquete tendrá un deadline time de 0.2k+1[s].
Scheduling
2.2 Non Work conserving Fair-share scheduling
En esta disciplina a cada paquete se le asigna un tiempo de elegibilidad. Si el servidor se encuentra ocioso, y ningún paquete es elegible, no se transmitirá ninguno de ellos.
Algunos algoritmos que emplean este método son:
1. Stop and Go (S&G)
2. Hierarchical Round Robin (HRR)
3. Jitter Earliest Due Date (Jitter EDD)
Scheduling
2.2.1 Stop and Go (S&G)
Se divide el tiempo en tramas o frames.
En cada trama de salida, sólo se envían paquetes que arribaron al servidor en la trama anterior.
Con este mecanismo, se garantiza que cada paquete transmitido posea un delay mínimo y máximo.
El retardo es proporcional a el largo de la trama, S&G propone diversos largos de frames.
Scheduling
2.2.2 Hierarchical Round Robin (HRR)
HRR posee varios niveles de servicio, el los cuales se aplica la disciplina RR en cada uno de ellos.
Si una fila ‘C’ no posee paquetes a transmitir, el servidor permanece ocioso durante el intervalo de tiempo destinado a la atención de esa fila.
Cierta fracción del BW se asigna a niveles más bajos.
bi
C C CC L LC CC L
C CC C
fi
Nivel 1
Nivel 2
Nivel 3
Scheduling
2.2.3 Jitter Earliest-Due-Date
La disciplina jitter EDD es una extensión de delay EDD que provee de límites para el jitter.
Una vez que un paquete es atendido por un switch, se le asigna un valor que corresponde a la diferencia entre el instante en que el paquete fue servido y el instante en el cual supuestamente debió haber sido atendido:
Un regulador en la entrada del siguiente switch mantiene el paquete en espera por este periodo de tiempo antes que éste sea elegible en la siguiente planificación.
correction term deadline time actual finish time
Scheduling
2.2.3 Jitter Earliest-Due-Date
deadline time
actual finish timeInicio atención
paquete en switch K
Switch K
Switch K+1
correction time
Inicio atenciónpaquete en switch K+1
tiempo
Scheduling
3. Traffic Shaping
El Traffic Shaping consiste adecuar o manipular el tráfico para cumplir con ciertas características preestablecidas. Usualmente, la especificación viene dada por el peor caso (por ejemplo, una aplicación que genere 100[Mbps] de datos por una ráfaga máxima de 2[s] de duración y un promedio no superior a 50[Mbps] sobre un intervalo cualquiera de 10[s]).
Algunos parámetros que permiten caracterizar el tráfico son mean bitrate, peak bitrate, variance of bitrate, burst length, burst frequency, cell-loss rate, cell-loss priority, etc.
Scheduling
3. Traffic Shaping
El objetivo del Traffic Shaping es regular el flujo de datos de modo tal de cumplir con las especificaciones de QoS establecidas al comienzo de la conexión por cada uno de los clientes, logrando así un uso más eficiente de la red.
El diseño y operación eficiente de la red ATM se logra gracias a la cooperación entre un conjunto de procesos (ruteamiento, policiamiento, etc), los cuales operan en un lugar y fase determinados de la red, encargándose cada uno de ellos de problemáticas específicas.
Scheduling
3. Traffic Shaping
Si la función de policiamiento la lleva a cabo un policía y la función de Control de Admisión (CAC) un juez, el Traffic Shaping lo realiza un abogado que acata las órdenes del juez y está bajo la supervisión del policía.
Scheduling
3. Traffic Shaping
El control de tráfico puede ser realizado con técnicas de buffering, las cuales logran un tráfico más constante sobre la red. Si bien se logra reducir la tasa de pérdida de celdas, esto podría introducir un retardo considerable.
Debido a lo anterior, es recomendable emplear en forma simultánea técnicas de buffering y mecanismos de scheduling para garantizar QoS (cell loss rate, cell delay y variations of jitter) bajo cualquier caso (burst input traffic).
Scheduling
3.1 Rate-Controlled Static-Priority
Este modelo (RCSP) emplea traffic shapers para cada conexión seguido de una estructura basada en prioridades estáticas.
Shaper 1
Shaper 2
Shaper N
Real Time traffic
Prioridad Nivel 1
Prioridad Nivel M
Non Real Time traffic
Link
Output
Scheduling
3.2 Dynamically Weighted Priority Scheduling Algorithm
Esta disciplina considera un “índice de prioridad instantáneo” Pj(t) para cada clase de servicio o fila j en un tiempo t dado por:
donde:
uj corresponde a una prioridad fija asociada a la fila j-ésima. Wj (t) corresponde al tiempo que ha debido esperar la celda más antigua
en la fila j-ésima.
j
j
j
uP t
w t
Scheduling
3.2 Dynamically Weighted Priority Scheduling Algorithm
El índice de prioridad para cada fila (Pj(t) ) es recalculado en cada slot time.
La fila con el menor valor de Pj(t) es atendida en primer lugar.
El valor de prioridad fijo uj puede ser escogido arbitrariamente, donde a una fila de mayor prioridad le es asignado un número menor. Por ejemplo, clases CBR y VBR pueden tener uj 1 y 2, respectivamente.
Scheduling
3.2 Dynamically Weighted Priority Scheduling Algorithm
Note que para =0, el algoritmo tiende a comportarse como una disciplina de prioridad fija, donde Pj(t)=uj.
En cambio, para grandes valores de , Pj(t) queda fuertemente dominado por el valor de wj, tendiendo a comportarse como una disciplina FIFO.
Simulaciones han demostrado que la elección de un valor óptimo del parámetro depende de las características del tráfico y de las clases de servicio que se deseen atender.
Scheduling
RESUMEN SCHEDULING:
Criterios de QoS: Cotas de retardo. Variación de retardo (jitter). Grado de pérdida de paquetes. Caudal (Throughput).
Necesidades en el diseño de una disciplina: Repartir de manera equitativa los recursos entre todas las conexiones
de una misma categoría. Optimizar el grado de aprovechamiento de los recursos. Flexibilidad. Sencillez de implementación. El comportamiento anómalo de un usuario no debe afectar al resto.
Referencias
[1]: Ivan Dimov, Pablo Roncagliolo, Switching y Encolamiento ATM, Presentación, 2003.
[2]: Paolo González, Hernán Soto, Scheduling, Presentación 2003, 1999 [3]: Natalie Giroux, Sudhacar Ganti, Quality of Service on ATM Networks,
Prentice Hall, 1999. [4]: Todd Lizambri, Fernando Duran and Shukri Wakid, Priority Scheduling
and Buffer Management for ATM Traffic Shaping, National Institute of Standards and Technology.
[5]: Hui Zhang and Srinivasan Keshabv, Comparision of Rate - Based Service Disciplines, Proceedings of ACM SIGCOMM, 1991.
[6]: Josep Bada y Ferran Casadevall, Algoritmos del Scheduling para el Sistema GRPS
[7]: Enrique Hernández Orallo, Reserva Eficiente de Recursos en Redes para Transmisión en Tiempo Real, Tesis doctoral Universidad Politécnica de Valencia, 2001.
[8]: Presentaciones y apuntes RAV-2002: Álvaro Arenas: Mecanismos de Scheduling, Mario Cáceres: Mecanismos de Scheduling , Felipe Figueroa: Switches y Encolamiento.