Concepto de Flujo en QoS

• Secuencia de datagramas que se produce como resultado de una acción del usuario y requiere la misma QoS.
• Normalmente es simplex (unidireccional).
• Es la entidad más pequeña a la que los routers pueden aplicar una determinada QoS.

Servicio Best Effort (BE)

• Se trata igual a todo el tráfico, sin separación entre flujos ni diferenciación entre paquetes.
• No garantiza ningún SLA.
• Ante congestión:
  • Crecen los retardos sin control.
  • Pérdidas sin control.

IntServ

• IETF.
• Para cada flujo (puede ser agregado) reserva recursos en todo el camino.
• Orientado a conexión.
• Cada router del trayecto ha de tomar nota y efectuar la reserva solicitada (guardan estado).
• Requiere un protocolo de señalización que soporten todos los routers: RSVP.
• IntServ no requiere modificar los protocolos existentes.
• RSVP no hace la reserva, solo la señaliza.
• Poco utilizado salvo en algunos escenarios de videoconferencia.
• Poco escalable.
• Resurgiendo con MPLS.

DiffServ

• IntServ se ha criticado por no escalar bien.
• Clasificar el tráfico en pocas clases.
• Clasifican los ingress routers (complejidad en la frontera) con un codepoint en la cabecera IP.
• DiffServ mapea en cada nodo el codepoint en el paquete a un PHB en concreto.
• PHB = Per Hop Behavior:
  • El tratamiento que se le da al paquete en cuestión de scheduling y gestión de cola en ese nodo.
  • El mapeo codepoint ↔ PHB debe ser configurable.
• No es sensible a los requisitos de un flujo individual.

Clasificación y Marcado: Elementos

• Clasificación / Marcado:
  • Los routers necesitan distinguir el tráfico de diferentes clases y aplicarles diferentes políticas: packet marking (generalmente a la entrada a la red).
  • Identificación/clasificación de flujos.
  • En IPv4 (layer 3) la clasificación se suele hacer por:
    • Dirección IP de origen, dirección IP de destino.
    • Protocolo de transporte utilizado (TCP o UDP).
    • Puede incluir parámetros de nivel de transporte (puertos).
  • Fragmentos IP pierden cabecera nivel 4 y se vuelven best effort.
• Marcado / Coloreado:
  • Marcar al paquete como perteneciente a un flujo o a una clase.
  • En base a la clasificación.
  • Simplifica la clasificación a partir de ese punto.
  • En IPv4 usar los bits de TOS (renombrados para DiffServ).
  • En trama 802.1Q en los bits de prioridad.
• ¿Dónde? = ¿Quién?:
  • Preferiblemente en los extremos (edge) de la red.
  • O en los propios generadores de los paquetes.

Policing and Shaping: Elementos

• Traffic shaping y policing:
  • Marcar, descartar o retrasar el tráfico en exceso.
  • ¿Qué sucede si las aplicaciones no se comportan como deben?
  • Por ejemplo, la aplicación de audio envía más de lo previsto.
  • Necesitamos forzar que las fuentes se comporten como se ha acordado.
  • Forzar que una clase de tráfico se comporte dentro de lo contratado: policing (típicamente a la entrada).

Policing

• Objetivo: Limitar el tráfico a la entrada a la red para que no exceda el declarado.
• Su objetivo es un flujo o un agregado de flujos.
• Los que excedan lo contratado (nonconforming) se descartan o marcan (conditional marker).
• No introduce delay o jitter adicional al tráfico que se acepta.
• Características del tráfico:
  • Tasa media (media a largo plazo).
  • Tasa de pico.
  • Tamaño máximo de ráfaga: máx. nº paquetes a tasa de pico.

Token Bucket

• One-rate token bucket policer:
• Tasa de llegada de tokens R.
• Tamaño máximo del cubo de tokens B.
• Llega un paquete de tamaño b.
• ¿Hay al menos b tokens en el cubo?
  • Sí: paquete “conforme” al contrato. Retirar b del cubo.
  • No: paquete “no conforme” al contrato. Descartar/marcar.
• No retrasa el tráfico, el buffer es para los tokens.

Tráfico de usuario → Cubo de tokens (tamaño B) → Regulator → Generación de tokens (tasa R) → Tokens → Sí/No → Descartar/marcar

srTCM: Single Rate Three Color Marker

• Dos Token Buckets (inicio llenos).
• Parámetros:
  • CIR: Committed Information Rate.
  • CBS: Commited Burst Size.
  • EBS: Excess Burst Size.
• “Rojo” excede el CIR y ráfaga de CBS+EBS, “Amarillo” excede CIR y ráfaga de CBS.

Tráfico de usuario → Cubo de tokens C (tamaño CBS) → Regulator → Generación de tokens (tasa CIR) → Tokens → No (no quita tokens) → No (rojo) → Cubo de tokens E (tamaño EBS) → Regulator → Desbordamiento de tokens → Sí (verde, quita tokens de C)

srTCM: Color-Aware

• Vienen los paquetes ya marcados.
• Si es amarillo entra directamente a la comprobación del regulador de cubo E.

Tráfico de usuario → Cubo de tokens C (tamaño CBS) → Regulator → Generación de tokens (tasa CIR) → Tokens → Sí (verde, quita tokens de C) → No (no quita tokens) → No (rojo) → Cubo de tokens E (tamaño EBS) → Regulator → Desbordamiento de tokens → Generación de tokens (tasa CIR)

trTCM: Two Rate Three Color Marker

• Dos Token Buckets (inicio llenos).
• Parámetros nuevos:
  • PIR: Peak Information Rate.
  • PBS: Peak Burst Size.
• “Rojo” excede el PIR y ráfaga de PBS, “Amarillo” excede el CIR y ráfaga de CBS.

Tráfico de usuario → Cubo de tokens P (tamaño PBS) → Regulator → Generación de tokens (tasa PIR) → Tokens → No (rojo, no quita tokens) → Cubo de tokens C (tamaño CBS) → Regulator → Sí (verde, quita tokens de P y C) → Sí

trTCM: Color-Aware

• Vienen los paquetes ya marcados.
• No se puede “mejorar” de clase.

Tráfico de usuario → Cubo de tokens P (tamaño PBS) → Regulator → Generación de tokens (tasa PIR) → Tokens → No (rojo, no quita tokens) → Sí → Cubo de tokens C (tamaño CBS) → Regulator → Generación de tokens (tasa CIR) → Amarillos no pueden pasar a verde → Sí (verde, quita tokens de P y C)

Shaping

• Los que excedan no se descartan sino que se encolan.
• Introduce delay y jitter.
• Permite adaptar el tráfico ante diferentes velocidades en los extremos de una red.
• Policing es similar a Shaping con buffer nulo.

WAN

Ejemplo: Single Leaky Bucket

• Parámetros:
  • CIR = Commited Information Rate (bytes de paquetes IP por seg.).
  • CBS = Commited Burst Size (bytes).
• A(0,t) = tráfico cursado en intervalo (0,t).
• A(0,t) ≤ rot + sigma.
• “Restricción (sigma, ro)” a la salida (LBAP, Linear Bounded Arrival Process).

Tráfico de usuario → CBS (sigma) → PCR → CIR (ro) → Tokens → Tráfico acumulado → sigma → ro → tiempo

Connection Admission Control (CAC)

• “Call Admission Control”.
• “Capacity Admission Control”.
• Durante el establecimiento de la conexión.
• Acciones para determinar si se permite o no.
• Puede rechazar conexiones aunque haya capacidad suficiente.
• Así asegura dejar BW disponible para otras de mayor prioridad.

Core CAC

• Apropiado para flujos RT en vez de control de congestión.
• ¡Protege al tráfico RT del tráfico RT!
• Sencillo para flujos que requieren QoS CBR.
• Con flujos VBR necesita caracterización estadística del agregado.
• Puede permitir un grado de sobresubscripción para flujos VBR.

Core CAC para IP: Taxonomía

• Endpoint measurement-based CAC:
  • Las decisiones son tomadas por las aplicaciones extremo.
  • Se basan en medidas del tráfico a los destinos.
  • Monitorización activa: se envían paquetes “sonda” (“probe”) para medir las características del camino.
  • Monitorización pasiva: miden las características de flujos ya presentes entre esos extremos.
  • Tiene el problema de que medidas pasadas pueden no ser un buen indicador de prestaciones futuras.
  • No muy extendido.
• On-path network signaled CAC:
  • Los nodos en el camino de los datos son los responsables del CAC.
  • Esto requiere que la señalización emplee el mismo camino que los datos.
• Off-path CAC:
  • La señalización puede llevar camino diferente a los datos.
  • Puede ser mediante “bandwidth managers”.

Scheduling

• Permite compartir recursos.
• Emplea una disciplina de planificación para decidir la siguiente petición a atender.
• Puede tener lugar en diferentes niveles de una pila de protocolos.
• Por ejemplo, en el nivel de aplicación sería necesario para decidir la siguiente petición a un servidor que atender.

Scheduler

• Nos centraremos en compartir la capacidad de un enlace.
• Y en planificadores conservativos en trabajo (work conserving): están inactivos solo si la cola está vacía.

Scheduler: FCFS (FIFO)

• Orden de llegada.
• Es el método más rápido y sencillo de implementar.
• Se suele utilizar por defecto (Best Effort).
• ¿Problemas?

FCFS (FIFO): Problemas

• Limitado por la capacidad del buffer ante congestión (normalmente en número de paquetes).
• No permite diferenciar entre distintos tipos de paquete.
• Se logra asignación proporcional a la demanda.
• Una fuente greedy puede capturar el enlace.

Scheduling: FCFS

The Conservation Law

• La disciplina FCFS no distingue entre diferentes flujos.
• FCFS, por ejemplo, no permite menor retardo a paquetes de un flujo.
• Conservation Law: Nos dice que una disciplina de planificación solo puede mejorar el retardo medio de un flujo frente a FCFS a costa de empeorar el de otro flujo.
• Ejemplo:
  • Sea un conjunto de N flujos en un planificador.
  • Para el flujo i la tasa media de llegadas por unidad de tiempo es λi.
  • El tiempo medio de servicio de los paquetes del flujo i es xi.
  • La utilización media del enlace debido al flujo i es roi = λi xi.
  • El tiempo medio de espera en cola de los paquetes del flujo i es qi.
  • Si el planificador es conservativo en trabajo (work-conserving) entonces:
  • ∑(i=1,N) roi qi = Constante.
  • Es independiente del planificador en concreto.

The Conservation Law: Ejemplo

• Un STM-1.
• Dos PVCs ATM:
  • A. Tasa de llegadas de 10Mbps.
  • B. Tasa de llegadas de 25Mbps.
• Con FCFS ambos sufren un retardo medio en cola de 0.5 ms.
• Con un planificador diferente los paquetes del flujo A sufren un retardo medio en cola de 0.1 ms.
• ¿Cuál es el retardo medio en cola que sufren los paquetes del flujo B?
• Todas las celdas de igual tamaño así que igual al tamaño medio de paquete: roi = λi xi = 10Mbps / (53 x 8bits) x (53 x 8bits) / 155Mbps = 10/155.
• 10 / 155 x 0.5 + 25 / 155 x 0.5 = 10 / 155 x 0.1 + 25 / 155 x RB.
• RB = 0.66 ms.

Es decir: para reducir el retardo medio de una clase debemos aumentar el de otra.

Características de un Planificador

Características Deseables

• Sencillo de implementar.
• Performance bounds (deterministas o estadísticos).
• Que permita implementar un CAC simple.
• Reparto justo y protección.

Sencillez

• Que requiera pocas operaciones para ser rápido.
• Implementable en hardware.
• Que el número de operaciones sea independiente del número de flujos a planificar.

Performance Bounds

• Debería permitir garantizar límites (bounds) a un flujo.
• Bounds extremo a extremo, lo cual implica a todos los schedulers en el camino.
• Más simple si emplean la misma disciplina de planificación.
• Performance bounds:
  • Deterministas: Se cumplen para todos los paquetes del flujo.
  • Estadísticos:
    • Probabilístico:
      • Ejemplo: menos de 10s de retardo con probabilidad 0.99, implica que la probabilidad de que un paquete sufra más de 10s de retardo es menor del 1%.
    • Otra posibilidad es en forma de “uno entre N”:
      • Ejemplo: No más de 1 entre 100 paquetes sufrirán un retardo de más de 10s.
      • Este caso es más fácil de verificar pero más difícil de implementar pues los conmutadores deben seguir el estado de cada flujo.
• Los deterministas suelen requerir más recursos pues son para todos los paquetes.

Performance Parameters: Bandwidth

• Recibir al menos un mínimo, medido en un intervalo.
• Es el más habitual en las implementaciones.

Performance Parameters: Delay

• Determinista o estadístico.
• Caso peor: suponer que el resto de flujos se comportan de la peor manera posible.
• Medio:
  • Debe ser la media para cualquier patrón de llegadas.
  • O sea, imposible de medir.
  • Eso lo hace difícil de garantizar.

Performance Parameters: Delay-Jitter

• Acotar la diferencia entre el mayor y el menor retardo posible.
• Algunos schedulers tienen una dependencia entre BW y delay de forma que para lograr bajo delay hace falta alto BW.

Performance Parameters: Losses

• Fracción de paquetes (del flujo).

CAC Simple

• Dado el conjunto de flujos existentes y sus requisitos y el nuevo flujo y los suyos, decidir si se pueden alcanzar los requisitos del nuevo flujo sin violar los de los anteriores.
• Hacerlo sin infrautilizar la red.

Reparto Justo (Max-Min Fair)

• Flujos con requerimientos estrictos deben tenerlos garantizados independiente de esta “justicia”.
• Reparto justo es importante para flujos best-effort.
• Reparto decimos que es justo si satisface un max-min fair share.
• Scheduling es normalmente una decisión local al nodo de conmutación pero la “justicia” para un flujo es un objetivo global.
• Lograr justicia global con flujos cambiantes no es tan sencillo.
• La protección implica que un flujo que envíe más que su asignación justa no afecte al resto.
• Un planificador que haga un reparto justo ofrece protección.

Reparto Justo (Max-Min Fair): Definición

• Para dividir recursos entre un conjunto de usuarios, todos con iguales “derechos” pero diferentes demandas.
• De forma simple: a los que piden “poco” se les da lo que piden y lo que sobra se reparte entre los que piden “mucho”.
• Formalmente:
  • Asignar recursos en orden creciente de demanda.
  • Ningún cliente recibe más de lo que solicita.
  • Aquellos cuya demanda no se pueda satisfacer se reparten el remanente del recurso.

x1 x2 x3 x4 x5 x6

Reparto Justo (Max-Min Fair): Procedimiento

• Flujos 1,…,n.
• Demandas x1,…,xn.
• Demandas ordenadas x1 ≤ x2 ≤ … ≤ xn.
• Capacidad a repartir C.
• Inicialmente asignar C/n al flujo 1.
• Si esto es más que lo que necesita (C/n > x1) lo que sobra se repartirá entre el resto.
• Al final todos tienen lo que han pedido o si no había suficiente para eso no tienen menos que cualquier otra fuente que ha pedido más.

C/n + (C/n – x1)/(n-1)

Max-Min Fair: Ejemplo

• Recurso: 10.
• Demandas: 2, 2.6, 4 y 5.
• 10/4 = 2.5:
  • Demasiado para el primer cliente.
  • Asignarle 2 y queda 0.5.
• Ese 0.5 repartirlo entre los otros 3:
  • 0.5/3 = 0.16666…
  • Asignaciones [2, 2.66, 2.66, 2.66].
  • Demasiado para el segundo cliente.
  • Asignarle 2.6 y quedan 0.0666….
• Repartir ese 0.0666… entre los otros 2:
  • (2.5+0.5/3-2.6)/2 = 0.03333…
  • Asignaciones [2, 2.6, 2.7, 2.7].

Reparto Justo con Pesos (Max-Min Weighted Fair)

Max-Min Weighted Fair Share

• En ocasiones se desea una asignación preferente a unos flujos frente a otros.
• Se asocia esta preferencia con unos pesos w1, w2, …, wn.
• Extensión:
  • Los recursos se asignan en orden de demanda creciente, normalizada por el peso.
  • Ningún cliente recibe más de lo que solicita.
  • Aquellos cuya demanda no se pueda satisfacer se reparten el remanente del recurso en proporción a sus pesos.

Max-Min WFS: Ejemplo

• Recurso: 20. Demandas: 4, 2, 10 y 8. Pesos: 2.5, 4, 0.5 y 1.
• Normalización de los pesos:
  • Que el menor valga 1.
  • Pesos normalizados: 5, 8, 1 y 2.
• En vez de 4 clientes es como si hubiera 5+8+1+2 = 16.
• C/n = 20/16 = 1.25.
• La asignación a cada uno sería:
  • (5×1.25=) 6.25, (8×1.25=) 10, (1×1.25=) 1.25 y (2×1.25=) 2.5.
  • El cliente 1 obtiene 6.25 pero solicitaba 4 luego sobra 2.25.
  • El cliente 2 obtiene 10 pero solicitaba 2 luego sobra 8.
  • El cliente 3 obtiene 1.25 pero solicita 10 (insuficiente).
  • El cliente 4 obtiene 2.5 pero solicita 8 (insuficiente).
• Ha sobrado 2.25 + 8 = 10.25 a repartir entre los clientes 3 y 4.
  • Sus pesos ya están normalizados (1 y 2). C/n = 10.25 / 3 = 3.417.
  • El cliente 3 obtiene 3.417 adicional, en total 1.25+3.417 = 4.667 (insuficiente).
  • El cliente 4 obtiene 6.834 adicional, en total 2.5+6.834 = 9.334, sobra 1.334.
  • Lo que sobra del cliente 4 se asigna al cliente 3 y así recibe 4.667+1.334.
• Asignación final: 4, 2, 6, 8.

Planificadores: de PQ a WRR

Priority Queueing (PQ)

• Paquetes en cola de mayor prioridad se envían siempre antes que paquetes en colas de menor prioridad.
• En cada cola FCFS.
• Asegura que el tráfico importante reciba un servicio rápido.
• Puede crear inanición (starvation), es decir, dejar fuera de servicio a tráfico menos prioritario.
• Menor retardo en cola medio para un flujo a costa de mayor para otros.
• Multilevel priority with exhaustive service: Los paquetes en una cola de menor prioridad no se envían hasta que todas las colas de mayor prioridad están vacías.
• El número de niveles de prioridad depende del número de clases de retardo a crear.
• Son típicas al menos 3:
  • Prioridad alta: mensajes urgentes, por ejemplo, protocolos de control de red.
  • Prioridad media: servicio garantizado.
  • Prioridad baja: best-effort.
• Otra posibilidad:
  • Prioridad alta: voz.
  • Prioridad media: vídeo.
  • Prioridad baja: resto de datos.
• Es vital un correcto control de admisión y policing para todo lo que no sea la clase más baja.
• El reparto del BW entre las clases no es max-min fair.
• Sencillo de implementar.

Priority Queueing: Ejemplo

• Se conoce el tamaño de la ráfaga más larga que puede llegar de un flujo (bi).
• Para el flujo de prioridad mayor i = 1 el b1 debe ser inferior al retardo de peor caso que se busque.
• Para el flujo de prioridad i = 2 el retardo máximo es b1+b2.
• El flujo de prioridad i = k sufre un retardo de caso peor de ∑(i=1,k) bi.

Processor Sharing (PS)

• Para best-effort querríamos un reparto max-min fair.
• Esto se puede lograr con un scheduler llamado Processor Sharing.
• Es un planificador work-conserving.
• Sirve de forma simultanea todas las colas, repartiendo la capacidad.
• O se puede decir que las sirve por turnos (round robin) pero sirviendo una cantidad infinitesimal de cada una.
• Si una cola está vacía pasa a la siguiente, de forma que su tiempo se está repartiendo entre el resto (y de ahí el max-min).
• Aproximación de tráfico como un fluido.
• Es un planificador ideal e imposible de implementar, aunque se puede aproximar.

Processor Sharing: Ejemplo

tiempo → envío de la clase 3 → envío de la clase 2 → envío de la clase 1 → 1 clase activa a C → 2 clases activas a C/2 → N clases activas a C/N

Generalized Processor Sharing (GPS)

• Se puede asociar un peso a cada cola y entonces la cantidad de servicio es proporcional al mismo.
• Ofrece weighted max-min fairness y lo llamamos Generalized Processor Sharing (GPS).
• En cualquier caso, en la realidad no podemos servir fluidos sino que servimos paquetes así que solo podremos aproximarlo.
• Round Robin es una aproximación a PS.

Round Robin (RR)

• Opera en “turnos” (rounds), conservativo en trabajo • En cada turno visita cada cola (en round-robin) • En cada cola FCFS • Se sirve un número de paquetes o paquetes durante un cierto tiempo fijo (la diferencia es cómo afectan sus tamaños) – Weighted Round Robin (WRR) • Opera por “turnos” • Se normaliza el peso por el tamaño medio de paquete en la clase • Normaliza el resultado para que sean enteros • En cada turno visita cada cola (en RR) y sirve tantos paquetes como su peso normalizado • Ejemplo:-  si n1=6 n2=1 n3=10 n4=4 – Weighted Round Robin (WRR) • Opera por “turnos” • Se normaliza el peso por el tamaño medio de paquete en la clase • Normaliza el resultado para que sean enteros • En cada turno visita cada cola (en RR) y sirve tantos paquetes como su peso normalizado • Ejemplo:– Pesos: 0.03, 0.05, 1 y 0.5- Tamaños medios: 50, 500, 1000 y 1200 bytes- Renormalizados según tamaños medios: 0.0006, 0.0001, 0.001 y 0.0004- Renormalizados a enteros: 6, 1, 10, 4 !(i) si n1=6 n2=1 n3=10 n4=4 – Weighted Round Robin (WRR) Problemas • Necesita saber el tamaño medio de paquete de cada clase • Más sencillo si los paquetes son de tamaño constante • Es justo solo por encima de la escala de la duración del turno • Ejemplo:– Enlace T3 (45Mbps)- 500 PVCs ATM con peso 1 y 500 PVCs con peso 10- Supongamos que todos los PVCs tiene tráfico- Un turno requiere enviar: 500 x 1 + 500 x 10 = 5500 celdas ! 51.82 ms- Por debajo de una escala de 50ms unos PVCs reciben más que otros • El retardo que sufre una clase depende del número de clases que haya • Hay implementaciones que lo combinan con una cola de prioridad – Shaped Round Robin (SRR) • Modo Shaped: limita BW consumido por cada clase • Modo Shared: el tiempo no utilizado por una clase lo usan el resto • A partir de una cierta escala sirven los mismos paquetes de cada cola WRR y SRR • SRR los envía con un orden diferente, más entremezclados de las diferentes clases – Deficit Round Robin (DRR) • Permite hacer un RR con pesos sin conocer tamaños medios de paquetes (veamos primero versión sin pesos) • Cada clase mantiene un contador de déficit inicializado a 0 • En cada turno se añade q (el quantum) al contador de cada clase si tiene paquetes por servir, si no se resetea • El planificador visita cada clase y sirve el primer paquete de la cola si su tamaño es menor que su contador de déficit • y decrementa el contador en el tamaño del paquete • Deficit Round Robin (DRR) • Ejemplo:- q = 1000 bytes- Tres clases A, B y C con paquetes de 1500, 800 y 1200 bytes- Turno 1: Clase A contador a 1000, clase B se sirve paquete y el contador se queda en 200, clase C contador a 1000- Turno 2: Clase A se sirve paquete y contador a 500, clase B se resetea pues no tiene paquetes (para que no acumule), clase C se sirve paquete y contador a 800 – Deficit Round Robin (DRR) • En la versión con pesos el quantum es el peso de cada clase • El quantum debería ser al menos del tamaño máximo de paquete para servir alguno en todos los turnos • Es sencillo de implementar REVISAR EJEMPLOS DE PLANIFICADORES.

TEMA 6 

 Scheduling: WFQ Weighted Fair Queueing -WFQ • Aproximación de GPS (Generalized Processor Sharing) para el caso de paquetes • Equivalente a PGPS (Packet-by-packet Generalized Processor Sharing) • No requiere conocer el tamaño medio de paquete • Emplea un reloj virtual • Calcula el final virtual en que se enviaría cada paquete en el caso ideal GPS • Se envían en orden de tiempo final virtual • Más complejo de implementar • Puede ofrecer worst-case bounds -WFQ • Se simulan “turnos” (rounds) • Supongamos que no hay pesos • Supongamos que GPS no sirve fluido perfecto sino bit-a-bit • En cada turno se envía 1 bit de cada flujo • El número de turno (round number) es el número de turnos bit-a-bit que se han completado en un instante • Así, cuantos más flujos activos simultáneos hay, más despacio se incrementa el turno con el tiempo • Ignoramos el servir bit-a-bit si definimos el round number como un valor que crece inversamente proporcional al número de flujos activos -WFQ • Un paquete k del flujo i que llega en el instante t • Su finish number F(i,k,t) :- Si flujo está inactivo: el round number actual + el tamaño en bits- Si flujo está activo: máx[F(i,k-1,t), round_number] + tamaño en bits • Una vez calculado para un paquete no hay que recalcularlo ante nuevas llegadas • Si llega a una cola llena se descartan paquetes en orden decreciente de finish number hasta que quepa -WFQ • Calcular el round number es complejo • Hay que hacerlo para cada paquete que llega y por cada uno que se envía • En el caso con pesos a la hora de calcular el finish number:- Si flujo inactivo: el round number actual + tamaño / peso- Si flujo activo: máx[F(i,k-1,t), round_number] + tamaño / peso • y el round number se incrementa con el inverso de la suma de los pesos • Existen variantes para simplificar este cálculo:- Self-Clocked Fair Queuing (SCFQ)- Start-Time Fair Queuing -WFQ: Ejemplo -WFQ (Ejemplo) • Enlace a 1 unidad/s • Llegadas de tamaños 1, 2 y 2 unidades en t=0 y de tamaño 2 unidades en t=4 A B C round number 1 2 3 1 2 3 4 5 6 7 8 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ  • Finish numbers:- A1 = 0 + 1 = 1- B1 = 0 + 2 = 2- C1 = 0 + 2 = 2 A B C round number 1 2 3 1 2 3 4 5 6 7 8 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ  • Hay 3 flujos a enviar simultáneamente • El round number se incrementa a C/3 = 1/3 por unidad de tiempo A B C round number 1 2 3 1 2 3 4 5 6 7 8 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ  • En el instante t=3 se han servido 3 bits, eso es uno por flujo y por lo tanto termina el round 1 y termina de enviarse A1 A B C round number 1 2 3 1 2 3 4 5 6 7 8 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ • A partir de ahí se siguen sirviendo B1 y C1 con finish number = 2 • Al haber dos flujos activos crece el round number a 1/2 A B C round number 1 2 3 1 2 3 4 5 6 7 8 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ • B1 y B2 terminarían de enviarse al alcanzar round number = 2 (t = 5) pero llega antes A2 A B C round number 1 2 3 1 2 3 4 5 6 7 8 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ (Ejemplo) • Finish number de A2 es 1.5 + 2 = 3.5 • A partir de t=4 vuelve a haber 3 flujos simultáneos A B C round number 1 2 3 1 2 3 4 5 6 7 8 1.5 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ  • Se alcanza el round number 2 en t = 4 + 0.5/(1/3) = 5.5 • Entonces se completaría el envío GPS de B1 y C1 A B C round number 1 2 3 1 2 3 4 5 6 7 8 1.5 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ  • Queda solo una fuente activa luego ahora se avanza a 1 round por unidad de tiempo A B C round number 1 2 3 1 2 3 4 5 6 7 8 1.5 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño -WFQ  • Queda solo una fuente activa luego ahora se avanza a 1 round por unidad de tiempo • En t = 7 se alcanza el round number 3.5 y termina de enviarse A2 A B C round number 1 2 3 1 2 3 4 5 6 7 8 1.5 3.5 tiempo F(i,k,t): • Inactivo: roundNumber + tamaño • Activo: máx[F(i,k-1,t), roundNumber] + tamaño –WFQ: Cotas -Cotas (bounds) en WFQ • WFQ garantiza reparto weighted max-min fair • Eso quiere decir que cada flujo recibe una asignación proporcional a su peso • Además pone una cota al retardo máximo • ¿Cómo? – ci = C !(i) P!(i) -Cotas (bounds) en WFQ • Supongamos un flujo con una restricción “sigma-ro”  :- En un intervalo t llegan como mucho sigma + rot bits- Es la salida de un token bucket- Linear Bounded Arrival Process (LBAP) • Un flujo i con restricción sigma-ro• El resto del tráfico puede no estar conformado • – Tráfico acumulado sigma ro tiempo -WFQ token rate, ro bucket size, sigma Tráfico Cotas (bounds) en WFQ • Camino con K saltos (todos WFQ) • Se le ha asignado una tasa g(i,k) en cada uno: