Redes de Comunicación

Redes de Sistemas de Colas

Instructor:
Dr.-Ing. K.D. HACKBARTH
Versión 24.08.2012
© Universidad de Cantabria

1
 Contenido

• Redes de conmutación de paquetes

• Redes de sistemas M/M/1
– Teoremas
– Múltiples fuentes/destinos
– Matriz de transición
– Solución estacionaria
– Red de Jackson

2
 Redes de conmutación de paquetes (1/10)

• Primeras experiencias en la comunicación de datos: uso

de modems
• El tráfico de datos es a ráfagas: tiene intervalos de
actividad y (largos) periodos de silencio
• El tráfico de datos suele ser asimétrico
• Requerimientos
– Semánticos: mayor que en la voz
– Temporales: menos restrictivos que en el tráfico de voz

3
 Redes de conmutación de paquetes (2/10)

• Historia de las redes de conmutación de paquetes

– System Network Architecture (SNA): arquitectura de IBM para
comunicar los terminales con un computador central
– La UIT-T desarrolla un protocolo bajo X.25 en 1976
– La ISO desarrolla el modelo de referencia OSI
– La arquitectura X.25 se adapta al modelo OSI
– En paralelo habría que destacar el despliegue y desarrollo de la
Internet

4
 Redes de conmutación de paquetes (3/10)

• Un conmutador de paquetes recibe los paquetes, y dependiendo de su

asignación de una canal virtual de entrada se les asigna un canal virtual de
salida correspondiente.
• El conmutador eliminará los paquetes donde se descubran errores y es
labor de los protocolos correspondientes el recuperarlos.
A D E F
D C D E F
25 -- 17 --
A 20 -- -- 17
11 15 -- -- 8 -- 27 --
23 -- 25 --
Canal físico 3 -- -- 2
7 -- -- 1 19 25 -- --

X
B D E F
B P E 3 5 -- --

17 4 -- --

8 -- 29 --

21 13 -- --

C
5
 Redes de conmutación de paquetes (4/10)

• Circuito virtual
– En un circuito virtual los paquetes siguen siempre el mismo
camino entre el transmisor y el receptor
– La conexión se puede establecer de forma temporal (RTC/RDSI
o GSM) o permanente
• Datagrama
– Cada paquete busca su camino desde el origen hasta su destino
– Las redes IP utilizan la conmutación de paquetes en modo
datagrama
– Actualmente están evolucionando a redes con conexiones
virtuales, mediante protocolos adicionales (e.g MPLS) que se
estudian en más detalle en la asignatura Redes Troncales

6
 Redes de conmutación de paquetes (5/10)

• Comparativa entre la conmutación de paquetes y

circuitos
Establecimiento

Establecimiento
circuito virtual
circuito

Transferencia
Información
Liberación
circuito

Paquete
reconocimiento
(ACK)

Conmutación de paquetes Conmutación de paquetes

Conmutación de circuitos
Datagrama Circuito virtual
7
 Redes de conmutación de paquetes (6/10)

• En conmutación de paquetes se producen retardos

adicionales por la espera y procesado por parte de los
nodos/conmutadores (esto no se produce en
conmutación de circuitos)
• El retardo y la tasa de errores dependen de la longitud
de los paquetes
• Por otro lado, hay que tener en cuenta la sobrecarga
adicional debida a los bytes de cabecera y cola
• El tiempo de procesado de un paquete tp depende de la
velocidad del procesador vp (en bits por segundo) y de
su longitud L (en bytes)…
8

8
 Redes de conmutación de paquetes (7/10)

• Tasas de errores de paquetes para diferentes tipos de redes

1 1
– pB la tasa de errores de bits del enlace
– pp la tasa de errores a nivel de paquetes
– L la longitud de paquetes
– N número de enlaces en la conexión

L = 50 B L = 1000 B
PB
N=1 N=2 N =4 N=1 N=2 N =4
10-4 0.03921 0.07689 0.14786 0.5507 0.7981 0.9592
10-5 0.00399 0.00797 0.01587 0.0769 0.1479 0.2739 Prohibido
10-6 0.00040 0.00080 0.00160 0.0080 0.0159 0.0315 X.25
10-7 0.00004 0.00008 0.00016 0.0008 0.0016 0.0032 FR o IP
10-8 0.00000 0.00001 0.00002 0.0001 0.0002 0.0003 ATM

9
 Redes de conmutación de paquetes (8/10)

Función X.25 en Retransmisión

RDSI (X.31) de tramas
• Frame Relay es una Generación/reconocimiento de indicador
Transparencia




arquitectura bastante usado Generación/reconocimiento FCS  
Reconocimiento de tramas no válidas  
red virtuales privadas al nivel Rechazo de tramas incorrectas  
 
nacional y sobre todo
Traducción de direcciones
Relleno de tiempo de intertrama  

internacional Multiplexación de canales lógicos

Gestión de variable de estado V(S)





• Se basa en el protocolo X.25
Gestión de variable de estado V(R)
Almacenamiento de paquetes en espera de 

con una fuerte reducían de

confirmación
Gestión del temporizador de retransmisiones T1 

funcionalidades Confirmación de I tramas recibidas

Comprobación del N(S) recibido frente al V(R)



• Más detalles se exponen en
Generación de REJ (mensaje de rechazo)
Respuesta al bit P/F (sondeo/final) 

la asignatura redes troncales Almacenamiento del número de retransmisiones

Actuación ante la recepción de REJ


Respuesta a RNR (no preparado para recibir) 
Respuesta al RR (preparado para recibir) 
Gestión del bit D 
Gestión del bit M 
Gestión del bit Q 
Gestión de P(S) 
Gestión de P(R) 
Detección de paquetes fuera de secuencia 
Gestión de RR de la capa de red 
Gestión de RNR de la capa de red  10
 Redes de conmutación de paquetes (9/10)

• ATM: reduce las funcionalidad frente a X.25 y FR aún más y trabaja

con paquetes de tamaño fijo (células) para conseguir:
– velocidades superiores
– Integración de servicios en tiempo real

• Se aplica actualmente en las grandes redes publicas de tipo NGN y

también en redes móviles de tercera generación (UMTS)
• Se esta substituyendo por protocolos MPLS/Ethernet o IP/MPLS
• Más detalles se exponen en la asignatura redes troncales
funciones superiores superiores

ATM ATM ATM ATM ATM

físico físico físico físico físico

IUR Red de transporte IUR

Equipo/red
del usuario
11
 Redes de conmutación de paquetes (10/10)

• Frame Relay (FR)

– Uso notable en el establecimiento de redes privadas virtuales a nivel
nacional e internacional
– Se basa en el protocolo X.25, con un conjunto menor de
funcionalidades
• Asynchronous Transfer Mode (ATM)
– Reduce las funcionalidades de X.25 y Frame Relay
– Emplea tramas (celdas) de tamaño fijo, con lo que se consigue
• Mayores velocidades
• Integración de servicios de tiempo real
– Se aplica actualmente en las grandes redes públicas de tipo NGN y
también en redes móviles de tercera generación (UMTS)
– Se está sustituyendo con arquitecturas MPLS/Ethernet o IP/MPLS
• La asignatura Redes Troncales estudiará con mayor detalle estas
tecnologías

12
 Redes de Sistemas M/M/1
Introducción

• Ya se ha visto que los sistemas M/M/1 y M/M/S

proporcionan un modelo sencillo que ofrece una
aproximación para E(n) y 
• La conexión de varios sistemas M/M/1 (M/M/S) en
cadena se puede analizar igualmente, gracias a la
aplicación de varios teoremas principales: Burke,
Jackson y Reich, con los que estimar…
– El retardo extremo a extremo, “end-to-end delay” (e2e-delay)
entre cualquier par origen/destino
– El retardo de ida y vuelta “round-trip delay”
– El retardo individual entre cada pareja de nodos ij

13
 Redes de Sistemas M/M/1
Teorema de Burke (1/2)

• Un proceso de Poisson, con tasa , a la entrada de un

sistema M/M/1 genera un proceso de salida de Poisson,
con tasa ’ = 
– Este resultado es también válido para sistemas M/M/S, en los
que resulta ’ = /S
• Además, se puede extender a sistemas con múltiples
entradas i (i=1…n) y múltiples salidas j’ (j=1…m)

∈ 0,1 1

14
 Redes de Sistemas M/M/1
Teorema de Burke (2/2)

• Router con cuatro puertos, cada uno de ellos con

direcciones/interfaces de entrada y de salida

in out
# Puerto (Pi)in (Pi)out
(p/s) (p/s)
1 459 475 0.2354 0.2436
2 380 550 0.1949 0.2821
3 621 925 0.3185 0.4744
4 490 0 0.2513 0.0000
Suma 1950 1950 1.0000 1.0000

15
 Redes de Sistemas M/M/1
Teorema de Jackson

• Sea [N1,N2] el proceso que resulta de una cadena de

dos sistemas M/M/1…

• El Teorema de Jackson establece que…

• El resultado se puede extender a una cadena con N

sistemas M/M/1 (o M/M/S)

16
 Redes de Sistemas M/M/1
Teorema de Reich

• Sea [N1,N2] el proceso que resulta de una cadena de

dos sistemas M/M/1, con tasa de llegada  y tasas de
salida diferenciadas i, con i=1,2
• El retardo medio en cada sistema es independiente, y se
calcula por…
1
1,2

• El retardo total se puede obtener con la suma de ambos

• El resultado se puede extender a una cadena con K

sistemas M/M/1 (o M/M/S)

17
 Redes de Sistemas M/M/1
Ejemplo (1/5)

• Una empresa conecta los M terminales de una

delegación remota mediante una red de área local (LAN)
con un servidor que se sitúa en su sede central
• La conexión se realiza mediante conexiones “Frame
Relay” (FR) que proporciona un operador
• La LAN se conecta a un router, que dispone de una
tarjeta FR
• Se asume que el retardo en la LAN es despreciable
frente a los retardos causados en la conexión FR

18
 Redes de Sistemas M/M/1
Ejemplo (2/5)

• Topología de la cadena
User
access
T1 router

LAN LAN
FR-UNI FR-UNI

TM

• Parámetros
Ida Vuelta
L (Bytes) 1024 1024
Velocidad FR (kbps) 64 256
Velocidad procesado (kbps) 1024 1024
# de terminales 100
Tasa por terminal (pkt/m) 1.2 4x1.2
19
 Redes de Sistemas M/M/1
Ejemplo (3/5)

• Se modela la cadena de sistemas de cola

• Se encamina el tráfico sobre el modelo anterior
• Se calculan (utilizando alguna herramienta informática)
– Los valores característicos para cada sistema y el retardo total
para 100 terminales
– El retardo total, incrementando el número de terminales desde
M=100 a M=350

20
 Redes de Sistemas M/M/1
Ejemplo (4/5)

• Solución para M =100

Tasa Vel. ts ttotal

A N p0
(p/s) (kbps) (ms) (ms)
Ida
Router 1 10 1024 8 0.080 0.087 8.696 0.920
FR 2 64 128 0.256 0.344 172.043 0.744
Router 2 10 1024 8 0.080 0.087 8.696 0.920
Vuelta
Router 2 10 1024 8 0.080 0.087 8.696 0.920
FR 8 256 32 0.256 0.344 43.011 0.744
Router 1 10 1024 8 0.080 0.087 8.696 0.920
Total
192 1.036 249.836 0.397

21
 Redes de Sistemas M/M/1
Ejemplo (5/5)

• Retardo para M = 100…350 terminales

22
 Redes de Sistemas M/M/1
Cadena con múltiples fuentes/destinos

• Una cadena con múltiples fuentes y destinos está

compuesta por una concatenación de nodos con
equipos de enrutamiento (OSI capa 3) o de conmutación
(OSI capa 2: FR, ATM, Ethernet)
• Se conectan mediante sistemas de transmisión, como
fibra o cables de cobre (UTP, STP)
• En cada nodo pueden entrar o salir paquetes
• La topología que se conforma es de tipo bus

23
 Cadena con múltiples fuentes/destinos
Ejemplo (1/3)

• Cadena con tres enrutadores a los que se conectan los

terminales (origen y destino de paquetes) mediante LAN
• Se considera que no se pierde ni se añade ningún
paquete adicional a los generados por los terminales
• Entonces resulta…

24
 Cadena con múltiples fuentes/destinos
Ejemplo (2/3)

• A partir de la topología de la red se deduce el grafo

correspondiente, siguiendo los siguientes pasos…
– El grafo tiene ni nodos regulares con i=1…N, además de un
nodo singular n0 que representa, artificialmente, la fuente y el
destino de todos los paquetes
– Los enlaces aij indican las conexiones entre la salida de un nodo
ni y la entrada de otro, nj
– Se establece la probabilidad de que un paquete cualquiera
emplee una salida
– En realidad cada puerto de entrada/salida representa un sistema
de cola, y los servidores se corresponden normalmente con un
procesador, un enrutador, un conmutador o una salida a un
sistema de transmisión

25
 Cadena con múltiples fuentes/destinos
Ejemplo (3/3)

• Grafo correspondiente a la red previa

# Nodo Espera Servidor

1 Router Memoria puerto entrada Procesador
2 Router Memoria puerto entrada Procesador
3 Router Memoria puerto entrada Procesador
4 Transmisión Memoria puerta salida router Transmisión (BW)
5 Transmisión Memoria puerta salida router Transmisión (BW)
6 Transmisión Memoria puerta salida router Transmisión (BW)
7 Transmisión Memoria puerta salida router Transmisión (BW)
26
 Redes de Sistemas M/M/1
Definición

• Una red de sistemas de cola está constituida por un

conjunto de sistemas de cola conectados entre sí
– Cada sistema de cola se corresponde con un nodo de la red
– La conexión entre dos sistemas de cola se corresponde con un
enlace
– El conjunto de nodos y enlaces conforman el grafo de la red
• Se establece una relación entre dos nodos ni, nj a partir
de la probabilidad pij de encaminar una petición por
dicho enlace
• El conjunto de estas probabilidades se describe con una
matriz de dimensión (N+1) x (N+1)

27
 Redes de Sistemas M/M/1
Descripción matemática

• Se define un proceso estocástico en n=1…N

dimensiones

, ,…

• Sea , ,… el vector de una solución

cualquiera del proceso; la pdf correspondiente es…

Pr , ,…

28
 Redes de Sistemas M/M/1
Modelo

• ¿Se puede utilizar un modelo sistemático para llegar a

soluciones genéricas con un algoritmo?
• ¿Existe un criterio para establecer la estacionariedad de
la solución?
• ¿Existen fórmulas para calcular valores de rendimiento
típicos?
– ij para todas las parejas de entrada salida (i,j)
–  global como valor medio en la red
– E(n) global sobre la ocupación media de la red

29
 Redes de Sistemas M/M/1
Modelo

• ¿Se puede utilizar un modelo sistemático para llegar a

soluciones genéricas con un algoritmo?
• ¿Existe un criterio para establecer la estacionariedad de
la solución?
• ¿Existen fórmulas para calcular valores de rendimiento
típicos?
– ij para todas las parejas de entrada salida (i,j)
–  global como valor medio en la red
– E(n) global sobre la ocupación media de la red

30
 Redes de Sistemas M/M/1
Matriz de transición (1/7)

• Metodología sistemática: uso de la matriz de transición

• Se deduce a partir de la demanda de tráfico entre cada
pareja de encaminadores en el grafo de la topología,
considerando el esquema de enrutamiento de la red

Destino
LAN1 LAN2 LAN3 OUT
LAN1 25 41 66

Origen
LAN2 34 18 52
LAN3 21 12 33
IN 55 37 59 151

31
 Redes de Sistemas M/M/1
Matriz de transición (2/7)

• Interpretando el esquema de encaminamiento sobre el grafo se

obtiene una matriz [ij] que proporciona el flujo de cada enlace
• Como se considera que no hay pérdida de paquetes, la suma de los
flujos de entrada debe ser igual a la suma de los flujos de salida en
cada nodo

0 1 2 3 4 5 6 7 OUT
0 66 52 33 151
1 55 66 121
2 37 55 59 151
3 59 33 92
4 66 66
5 55 55
6 59 59
7 33 33
IN 151 121 151 92 66 55 59 33

32
 Redes de Sistemas M/M/1
Matriz de transición (3/7)

• La matriz de transición (T) se define con los siguientes

elementos
– ij establece la probabilidad de que un paquete que llega al
nodo ni se transmita al nodo nj

Θ ∈ 0,1 Θ 1 ∀ 1…

• La matriz de transición se establece a partir de la matriz

de flujo…
Θ

33
 Redes de Sistemas M/M/1
Matriz de transición (4/7)

• Matriz de transición del ejemplo anterior

0 1 2 3 4 5 6 7 Suma
0 0.0000 0.4371 0.3444 0.2185 0.0000 0.0000 0.0000 0.0000 1.00
1 0.4545 0.0000 0.0000 0.0000 0.5455 0.0000 0.0000 0.0000 1.00
2 0.2450 0.0000 0.0000 0.0000 0.0000 0.3642 0.3907 0.0000 1.00
3 0.6413 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.3587 1.00
4 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.00
5 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.00
6 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 1.00
7 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 1.00

34
 Redes de Sistemas M/M/1
Matriz de transición (5/7)

• A partir de los valores de i0 y 0i se distinguen cuatro

tipos de nodos
– Nodo origen de peticiones: i0 = 0 y 0i > 0
– Nodo destino de peticiones: i0 > 0 y 0i = 0
– Nodo origen/destino de peticiones: i0 > 0 y 0i > 0
– Nodo de tránsito: i0 = 0 y 0i = 0

35
 Redes de Sistemas M/M/1
Matriz de transición (6/7)

• De la ecuación anterior

resulta un sistema de ecuaciones lineales:

• Dados T y 0 se puede calcular el vector de flujo, , siendo
i las soluciones del sistema de ecuaciones lineales
correspondientes

Θ Θ

36
 Redes de Sistemas M/M/1
Matriz de transición (7/7)

• A partir de , y 1, se obtiene…

1
1…
1 ∑

• En el ejemplo anterior se obtienen los siguientes

resultados
i 0 1 2 3 4 5 6 7
i 1.0000 0.8013 1.0000 0.6093 0.4371 0.3642 0.3907 0.2185
i 151 121 151 92 66 55 59 33
pi 0.2074 0.1662 0.2074 0.1264 0.0907 0.0755 0.0810 0.0453

37
 Redes de Sistemas M/M/1
Modelo

• ¿Se puede utilizar un modelo sistemático para llegar a

soluciones genéricas con un algoritmo?
• ¿Existe un criterio para establecer la estacionariedad de
la solución?
• ¿Existen fórmulas para calcular valores de rendimiento
típicos?
– ij para todas las parejas de entrada salida (i,j)
–  global como valor medio en la red
– E(n) global sobre la ocupación media de la red

38
 Redes de Sistemas M/M/1
Solución estacionaria (1/3)

• Cada modelo de espera pura debe cumplir que λ < μ

• Extrapolando el requisito a una red de sistemas de cola,
se puede ver que: 1…
• Por tanto…
min
…

• Teniendo en cuenta que…

8
• Resulta finalmente que…
min
… 8
39
 Redes de Sistemas M/M/1
Solución estacionaria (2/3)

• En el ejemplo anterior se asumen los siguientes datos…

– vR=384 kbps, vT= 128kbps y E(L) = 512 Bytes
• Con lo que resulta que 0 < 71.494
• A partir de la matriz de transición, la longitud media de
paquetes y las capacidades de cada enlace , ,
se calcula la carga máxima 0 que puede asumir la red

i 1 2 3 4 5 6 7
vi (kbps) 384 384 384 128 128 128 128
(ts)i (ms) 10.667 10.667 10.667 32.000 32.000 32.000 32.000
i (p/s) 93.750 93.750 93.750 31.250 31.250 31.250 31.250
i/i [p/s] 116.99 93.750 153.872 71.496 85.795 79.979 142.99

40
 Redes de Sistemas M/M/1
Solución estacionaria (3/3)

• Algoritmo para el cálculo del máximo de 0

// maxlambda0 en pkt/s y v[i] en kbps
maxlambda0(T,L,v)
calculate alpha by solving alpha=alpha*T and alpha0 = 1
maxlamda0 = inf
do for i=1 to N
ts[i] = L*8/v[i]
mu[i]=1000/ts[i]
quot = mu[i]/alpha[i]
if quot < maxlambda0
maxlambda0=quot
end if
end do
end

41
 Redes de Sistemas M/M/1
Modelo

• ¿Se puede utilizar un modelo sistemático para llegar a

soluciones genéricas con un algoritmo?
• ¿Existe un criterio para establecer la estacionariedad de
la solución?
• ¿Existen fórmulas para calcular valores de rendimiento
típicos?
– ij para todas las parejas de entrada salida (i,j)
–  global como valor medio en la red
– E(n) global sobre la ocupación media de la red

42
 Redes de Sistemas M/M/1
Red de Jackson abierta (1/2)

• Asumiendo que el proceso de llegadas es de Poisson (tasa 0) y la

longitud de los paquetes L sigue una distribución geométrica, las
ecuaciones lineales , 0, modelan una red de Jackson
abierta
• En una red de Jackson se cumple
– Función densidad de probabilidad (fdp)

– Número medio de paquetes en la red

– Retardo medio de un paquete en la red

43
 Redes de Sistemas M/M/1
Red de Jackson abierta (2/2)

• En el ejemplo anterior resultan, para 0 = 60 p/s y E(L) = 512 bytes, los

siguientes valores
i 0 1 2 3 4 5 6 7 Global
 60.00 48.08 60.00 36.56 26.23 21.85 23.44 13.11
(ts)i 10.67 10.67 10.67 32.00 32.00 32.00 32.00
Ai 0.51 0.64 0.39 0.84 0.70 0.75 0.42
ni 1.05 1.78 0.64 5.22 2.33 3.00 0.72 14.74
i 21.90 29.63 17.48 199.01 106.43 128.10 55.13 245.68

• Para el cálculo de los retardos individuales origen/destino ij se deben

sumar los retardos de los elementos del camino correspondiente
• En el caso de utilizar múltiples rutas se ponderan los retados por ruta con
las probabilidades correspondientes
• En el ejemplo resultan los valores (ij) de la siguiente matriz
1 2 3
1 250.54 396.12
2 157.96 175.22
3 230.58 102.25

44