Fundamentos de Colas y Optimización en Redes Telemáticas
Cola Simple
Dibujo
- λ: Tasa de llegada de usuarios (u. llegados/tpo)
- μ: Tasa de servicio de usuarios (u. serv/tpo)
Interpretación de Usuarios
- Paquetes que llegan al nodo (conmutación de paquetes)
- Llamadas que esperan ser atendidas (conmutación de circuitos)
Interpretación del Servidor
- Capacidad de transmisión por enlace (conmutación de paquetes)
- Número de llamadas servidas por tiempo (conmutación de circuitos)
Tasa de servicio: C/(l+l’), siendo C la capacidad del canal (bps), y (l+l’) la longitud media del paquete (bits/paq)
Estado de la cola: ρ = λ/μ: Intensidad del tráfico
Cuando ρ -> 1:
- Aumentan los tiempos de espera, siendo muy altos.
- Aumenta el número de paquetes en la cola rápidamente.
Estado de la cola: Número de usuarios en la cola (incluyendo los que están siendo servidos).
Para determinar la probabilidad del estado, se necesita: λ, μ, disciplina de servicio, número de servidores, tamaño de la cola.
Longitud Óptima de Trama
La influencia de la tasa de error en el tamaño óptimo de la trama no es crítica, existiendo un rango de valores. Depende de las características de los errores en los enlaces y la longitud del campo de control usado.
Errores en Enlaces Satélite
pb: Probabilidad de error de bit
p: Probabilidad de error de trama, p = 1 – (1 – pb)^(l+l’). Si pb < 1, p ≈ (l+l’) * pb
Errores en Enlaces Terrestres
pb independiente, no se puede aplicar directamente. Errores en ráfagas.
p proporcional a l+l’. Si pb < 1, p ≈ (l+l’) * k, donde k = pb (enlaces satélite) o k = cte (enlaces terrestres)
Cálculo de la Longitud Óptima
Hipótesis: a = 1 (SW) o (a-1)*p << 1
D/C = l/(l+l’) * (1-p) / (1 + (a-1)*p) ≈ l/(l+l’) * (1-p)
Caso General Satélite
lópt = l’/2 * (√(1 – 4/(l’*ln(pb))) – 1), suponiendo pb < 1
Caso Terrestre/Satélite Simplificado
p = pb(l+l’), lópt ≈ √(l’/pb) – l’
Nacimiento y Muerte
Colas dependientes del estado: Las tasas de llegadas (λ) y de servicio (μ) dependen del estado del sistema.
- λ = λ(n) = λn → Procesos de nacimiento (tasas de llegada en función del estado, procesos sin memoria)
- μ = μ(n) = μn → Procesos de muerte (tasa de salida en función del estado, procesos sin memoria)
pn = ((∏(0 a n-1) λn) * p0) / (Π(1 a n) μn)
Ejemplos: Colas de servidores múltiples: M/M/m y M/M/m/N
Throughput
Throughput: Número de usuarios servidos por unidad de tiempo.
- λ: Tasa de llegadas
- pb: Probabilidad de bloqueo
- λ * (1-pb): Tasa neta de llegadas
γ = λ * (1-pb) (en equilibrio)
- μ: Tasa de servicio
- (1-po): Probabilidad de uso de la cola = Utilización
γ = μ * (1-po) (en equilibrio)
Throughput normalizado: γ/μ
Ventana Deslizante en Circuitos Virtuales No Homogéneos
Se considera un circuito virtual no homogéneo cuando no todas las colas M/M/1 son iguales y/o hay alguna rama en paralelo.
Cálculo recursivo: Hacer una tabla. Cálculos necesarios:
- ti(N) = 1/μi + ni*(N-1)/μi
- Conexión serie: tt(N) = Σti(N), Conexión paralela: tt = Σqi*ti(N)
- γ(N) = N/tt(N)
- Serie: γi(N) = γ(N), Paralelo: γi = qi*γ(N)
- ni(N) = γi(N)*ti(N)
Hay que calcularlo para cada N hasta N = tamaño de la ventana.
Distribución de Poisson
Distribución discreta. Eventos sin memoria.
La probabilidad de K llegadas en un intervalo Δt: p(k) = e^(-λΔt) * ((λ*Δt)^k) / k! para todo k = 0, 1…
E(k) = λ * ∆t → λ = E(t)/Δt = Número medio de llegadas en Δt / Intervalo Δt.
Control de Flujo y Congestión
En principio, las redes están diseñadas con recursos suficientes para soportar el tráfico nominal, pero se puede producir congestión.
Aparecen procesos de control de flujo (evitar la congestión, repartir equitativamente los recursos del sistema, adoptar velocidades entre usuarios). Queremos maximizar γ y reducir el retardo.
Redes de Colas
Modelo de redes de colas. Dos tipos:
- Redes abiertas: El tráfico entra y sale de la red. λin = λout
- Redes cerradas: El tráfico permanece dentro de la red.
Redes Jacksonianas
Estadísticas de llegada de Poisson y soluciones del modelo en forma de producto.
- Tiempos de servicio exponenciales y distribuidos independientemente entre nodos.
- Ruta de forma aleatoria, probabilidades de enrutamiento fijas asignadas por q.
- Solución en forma de producto: Las llegadas externas dependen del número de paquetes en la red, el tiempo de servicio depende del estado de la cola correspondiente.
Protocolo Go Back N
Objetivo: Mejorar el throughput → λmaxGBN > λmaxSW
No se espera confirmación para enviar la siguiente trama. Si llega un NACK o vence el temporizador, se reenvía la trama errónea y las posteriores.
tack, tout = x*ti, si no se cumple: desalojo o sin desalojo → tack’ = (ent(tack/ti) + 1)ti
Suposiciones
- Número de secuencia indefinidos.
- Retransmisión por NACK o timeout se estudian igual.
- Transmisión en régimen de saturación de A a B.
- Longitud de trama ti fija.
- Tiempo de timeout es fijo y múltiplo de ti.
Tiempo medio de transmisión correcta de una trama:
tv = ti * (1 + (a-1)*p) / (1-p), siendo a = tt/ti
Throughput máximo: λmax = 1/tv = (1-p) / (ti * (1 + (a-1)*p)) → p = 0 → λmax = (1-p)/ti
λmaxGBN = a * λmaxSW
Protocolo HDLC
- Flags: Secuencias de bits que delimitan la trama.
- A: Direcciones.
- C: Control.
- CRC: Control de errores.
SS: 4 Tipos de Tramas de Supervisión
- RR (Ready to Receive)
- RNR (Not Ready to Receive): Confirma tramas hasta N(R)-1, establece control de flujo con condición de bloqueo.
- REJ (Reject): Confirma tramas hasta N(R)-1, retransmite desde la trama N(R).
- SREJ (Selective Reject): Pide retransmisión de la trama N(R), no confirma las anteriores.
Análisis
- Numeración de secuencia finita.
- Procedimiento de control de errores específicos (vía REJ, por temporizador, envío de tramas P/F).
Hipótesis para el Análisis
- Solo transmite A hacia B.
- Régimen de saturación.
- B responde con RR y REJ.
Datos para el Análisis
- Módulo M: Número de tramas diferentes numeración enviables.
- Ventana W: Número máximo de tramas en circulación sin confirmación. W < M.
- Longitud de tramas: info (ti = (l+l’)/C), superv (ts = l’/C)
Throughput en HDLC
Cuando hay error se recupera, primero REJ, los demás TIMEOUT.
Thmax = 1/tv, tv = ti + E(t1)*p + T2*p^2/(1-p)