1 SWITCHING, ENCOLAMIENTO Y SCHEDULINGSeminario de Redes de Alta Velocidad Mayo 2006 Tomás Urra B.

2 Índice Presentación Introducción Objetivos Switch ATMArquitectura Switch ATM Switching Fabric Resolución de Contenciones Buffering Encolamiento Scheduling

3 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).

4 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.

5 Introducción ATM utiliza switches (conmutadores) para encaminar celdas del sistemas origen al sistema destino. Host A quiere enviar datos a host B. Tabla: Switch 1 Interfaz entrada VCI Entrada Interfaz Salida VCI Salida 2 5 1 11 Tabla: Switch 2 Interfaz entrada VCI Entrada Interfaz Salida VCI Salida 3 11 7 Tabla: Switch 3 Interfaz entrada VCI Entrada Interfaz Salida VCI Salida 7 3 4

6 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.

7 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.

8 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

9 Arquitectura Switch ATMUnidad de Control

10 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

11 Tipo Memoria compartidaSwitching Fabric 1. 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

12 Switching Fabric 2. Bus TDMLa 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

13 Switching Fabric 3. Single PathTodas 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 Entradas Knockout Switch Entradas Salidas

14 Switching Fabric 4. Auto- RuteoLas 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

15 Resolución de ContencionesCuando 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.

16 Resolución de ContencionesEstrategias 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.

17 Buffering INPUT BUFFERING OUTPUT BUFFERING VIRTUAL OUTPUT BUFFERINGINPUT OUTPUT BUFFERING CENTRAL BUFFERING

18 Buffering INPUT BUFFERING 1 1 1 1 m m m m

19 Buffering INPUT BUFFERINGSe genera un nuevo problema llamado “Bloqueo de cabecera de línea” (HOL).

20 Buffering INPUT BUFFERINGHOL blocking, puede ser mejorada con una disciplina no-FIFO de selección de ventana.

21 Buffering OUTPUT BUFFERINGNo existe HOL blocking en este caso, pero puede haber pérdida de celdas por congestión. 1 1 m m

22 Buffering OUTPUT BUFFERINGPara 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

23 Buffering VIRTUAL OUTPUT BUFFERINGSe resuelve el problema de HOL dividiendo lógicamente cada buffer de entrada en N buffer virtuales. out1 1 1 outm out1 m outm m

24 Buffering INPUT & OUTPUT BUFFERINGSe usa cuando el número de celdas entrantes es superior al que puede aceptar una salida. 1 1 m m

25 Buffering CENTRAL BUFFERINGCada salida rescata sus celdas desde el buffer central. Se requiere un complejo sistema de administración de memoria. 1 m S/P P/S Buffer Manager High Speed Parallel Bus Central Buffer

26 Encolamiento Estructuras de EncolamientoEstas 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

27 Encolamiento Encolamiento por Grupo Categoría de ServicioAislamiento por servicio Se divide la capacidad de enlace, garantizar QoS por cada servicio. Idealmente #colas = #categorías de servicio. CBR VBR Capacidad del enlace Arbitrador UBR

28 Encolamiento Encolamiento por Grupo Clase de ServicioDentro de cada categoría de servicio podemos definir clases de servicio definiendo valores umbrales para cada parámetro. CBR CTD=250ms CBR/rt-VBR CTD=2500ms nrt-VBR CLR=10e-7 Capacidad del enlace nrt-VBR Arbitrador CLR=10e-4 ABR UBR

29 Encolamiento Encolamiento por Grupo Definición de ConformaciónEjemplo: 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. CBR.1 VBR.1 VBR.2/VBR.3 Capacidad del enlace Arbitrador UBR.1 UBR.2

30 Encolamiento Encolamiento por VC/VPLas celdas de cada VC o VP son encoladas separadamente Encolamiento por VC es mas complicado y costoso. VC1 VC2 VC3 Arbitrador Todas estas estructuras de encolamiento necesitan de mecanismos de Scheduling para manejar adecuadamente los Buffers VCn

31 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.

32 Scheduling Mecanismos primitivos: FIFOEs 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.

33 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.

34 Scheduling En la práctica:...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.

35 Scheduling Mecanismos de Scheduling Flat o “un nivel” SchedulingSe 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 S2 S3 S1 Flat o “un nivel” Scheduling Hierarchical Scheduling

36 Scheduling Mecanismos de Scheduling Flat Schedulingse 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.

37 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

38 Scheduling 1. Priority-based schedulingA 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, rt-VBR Nrt-VBR ABR, GFR UBR 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. prioridad

39 Scheduling 1. Priority-based scheduling

40 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.

41 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.

42 Scheduling 2. Fair-share schedulingEste 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?

43 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. Rate allocation Rate controlled Work conserving fair-share scheduling algorithm Non-Work conserving fair-share scheduling algorithm

44 Scheduling 2.1 Work conserving Fair-share schedulingEn 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)

45 Scheduling 2.1.1 Fair Queuing (FQ) Asume encolamiento por VC/VPSi 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.

46 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].

47 Scheduling 2.1.3 Delay Earliest-Due-DateEn 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].

48 Scheduling 2.2 Non Work conserving Fair-share schedulingEn 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)

49 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.

50 Scheduling C L 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 L fi Nivel 1 Nivel 2 Nivel 3

51 Scheduling 2.2.3 Jitter Earliest-Due-DateLa 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.

52 Scheduling 2.2.3 Jitter Earliest-Due-Date deadline timeactual finish time Inicio atención paquete en switch K Switch K Switch K+1 correction time paquete en switch K+1 tiempo

53 Scheduling 3. Traffic ShapingEl 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.

54 Scheduling 3. Traffic ShapingEl 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.

55 Scheduling 3. Traffic ShapingSi 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.

56 Scheduling 3. Traffic ShapingEl 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).

57 Scheduling 3.1 Rate-Controlled Static-PriorityEste 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

58 Scheduling 3.2 Dynamically Weighted Priority Scheduling AlgorithmEsta 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.

59 Scheduling 3.2 Dynamically Weighted Priority Scheduling AlgorithmEl í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.

60 Scheduling 3.2 Dynamically Weighted Priority Scheduling AlgorithmNote 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.

61 Scheduling Criterios de QoS: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.

62 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, [8]: Presentaciones y apuntes RAV-2002: Álvaro Arenas: Mecanismos de Scheduling, Mario Cáceres: Mecanismos de Scheduling , Felipe Figueroa: Switches y Encolamiento.