1. No category

Pablo Serrano, José Alberto Hernández
Una introducción amable a la teoría de colas:
Problemas propuestos
Departamento de Ingeniería Telemática - Universidad Carlos III de Madrid
Control de versiones - Curso 14/15
Copyright © 2015 Pablo Serrano, José Alberto Hernández
Este obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-CompartirIgual
4.0 Internacional. Para más información, visite la página web: http://creativecommons.org/licenses/
by-nc-sa/4.0/.
Contenido
Repaso de probabilidad
5
Variable aleatoria exponencial
7
Procesos de llegada de Poisson
9
Cadenas de Markov de tiempo discreto
11
Cadenas de Markov de tiempo continuo
Teoría de colas: sistemas básicos
Teoría de colas: sistemas avanzados
Batiburrillo
31
Formulario
39
15
21
25
Repaso de probabilidad
Problema 1.1 Resuelva el problema original de De Méré: “¿Qué
es más probable, sacar al menos un seis en cuatro tiradas de un
dado, o sacar al menos un doble seis en veinticuatro tiradas de dos
dados?”
Problema 1.2 Suponga que el tráfico en una red se distribuye
según se muestra en la tabla, donde la primera columna indica la
aplicación, la segunda la distribución que siguen sus tramas, y la
tercera la proporción relativa de dichas tramas. Obtenga:
1. La longitud media de las tramas en la red.
2. La longitud media del tráfico que no sea P2P.
Solución.
1. 1085 B; 2. 912.5 B.
Problema 1.3 Una red compuesta por 10 ordenadores y 5 servidores se conecta a Internet a través de un switch Ethernet. Los
ordenadores transmiten asentimientos TCP con una probabilidad
del 60 %, y tramas de datos con una probabilidad del 40 %. Para el
caso de los servidores, estas probabilidades son del 90 % y 10 %,
respectivamente.
1. Calcule la probabilidad de que una trama sea un asentimiento.
2. ¿Cuál es la probabilidad de que un servidor haya generado dicha
trama?
Solución.
1. 7/10; 2. 3/7
Problema 1.4 Sea X una variable aleatoria continua con función
de densidad
3
f ( x ) = (1 − x2 ) , − 1 ≤ x ≤ 1.
4
Obtenga la esperanza de X.
Problema 1.5 La función de densidad de X viene dada por
f ( x ) = a + bx2 ,
0 ≤ x ≤ 1,
Aplicación
Skype
P2P
Web
email
Longitud (B)
U(50,150)
U(1000,1500)
exp(1/1000)
N(800,100)
%
5
60
25
10
6
una introducción amable a la teoría de colas: problemas propuestos
mientras que su esperanza es E[ X ] = 3/5. Deduzca a y b.
Problema 1.6 Un grupo de exploradores se ha perdido en una
mina. Llegan a una sala con tres puertas: una de ellas conduce a la
salida tras 10 horas de camino, mientras que las otras dos vuelven a
llevar a la misma sala tras 5 y 15 horas de camino, respectivamente.
Suponga que el grupo elige una puerta al azar pero antes de emprender el camino la marca de alguna forma, para así no volver a
ir por la misma. Calcule la esperanza del tiempo hasta que logran
salir de la mina.
Problema 1.7 Dos estaciones, una de alta y otra de baja prioridad,
utilizan una variante de Aloha ranurado para acceder al medio. La
estación de alta prioridad transmite con el doble de probabilidad
que la estación de baja prioridad.
1. Calcule la probabilidad de transmisión de ambos tipos de estaciones que maximiza la eficiencia en el uso del canal.
2. Indique si la máxima eficiencia del protocolo con diferenciación
es superior a la del Aloha sin diferenciación.
Solución.
1. p1 = 3/8, p2 = 3/4; 2. Es mayor.
Problema 1.8 Una estación WiFi usa dos modulaciones, 1 Mbps y
11 Mbps. A 11 Mbps, la probabilidad de pérdida es 20 %, mientras
que a 1 Mbps esta probabilidad es 3 %. Se ha observado en un canal
que la probabilidad media de pérdida es del 12.35 %. Calcule:
1. La proporción de tramas que fueron enviadas a 1 Mbps.
2. De las tramas recibidas correctamente, ¿cuántas fueron enviadas
a 11 Mbps?
Solución.
1. 0.45; 2. 0.502
Problema 1.9 Sea X una variable aleatoria uniformemente distribuida entre 0 y 1, esto es, X ∼ U[0, 1]. Si a y b son dos valores dados, deduzca la media y varianza de la variable aleatoria
Z = a + (b − a) X.
Variable aleatoria exponencial
Problema 2.1 Pruebe que una variable aleatoria distribuida uniformemente en [0, a] no es “sin memoria”.
Problema 2.2 Suponga que la variable aleatoria X1 se distribuye
uniformemente [0, a], y que la variable X2 se distribuye exponencialmente con media 1/λ. Calcule Pr( X1 < X2 ).
Solución.
1
−λa )
λa (1 − e
Problema 2.3 Suponga que la variable aleatoria X1 se distribuye
uniformemente [0, a], y que la variable X2 se distribuye uniformemente en [0, b], con a < b. Calcule Pr( X1 < X2 ).
Solución.
1−
a
2b
Problema 2.4 (Ross 2.10a) Suponga que el tiempo entre autobuses se puede modelar según una variable aleatoria exponencial, de
media 1/λ. Una vez en el autobús, el tiempo de recorrido hasta el
destino es R. Andando desde la parada, el tiempo es W. Suponga
que la regla que se sigue para decidir si tomar o no el autobús es
la siguiente: se espera como mucho un tiempo S, pasado el cual se
decide ir andando. Se pide:
1. Obtenga el tiempo medio desde que llega a la parada de autobús
hasta el destino.
2. Discuta, en función del cociente W/( R + λ−1 ), el valor óptimo
de S.
Solución.
1. R + λ−1 + e−λS (W − R − λ−1 ).
Problema 2.5 (Ext. 10/11) Suponga que el tiempo que tarda un
cajero en atender a un cliente es exponencial. En un banco hay dos
cajeros, que tardan en media 3 y 6 minutos en atender a un cliente,
respectivamente. Suponga que un cliente llega al banco y los dos
cajeros están ocupados, y no hay nadie más esperando. Se pide:
1. Probabilidad de estar más de 2 minutos esperando a ser atendido.
2. Tiempo medio de estancia total en el banco.
8
una introducción amable a la teoría de colas: problemas propuestos
Solución.
1. e−1 ; 2. 6 minutos.
Problema 2.6 (Ord. 10/11) Suponga que el tiempo que se necesita para averiguar una contraseña se distribuye según una variable
aleatoria exponencial de media 10 días.
1. Si un usuario establece su contraseña el 1 de enero, obtenga la
probabilidad de que su contraseña no sea descubierta durante el
año (no bisiesto).
2. Un usuario cambia su contraseña el día 1 de cada mes. Calcule
de nuevo la probabilidad anterior, y comente el resultado.
Solución.
e−36,5 .
Problema 2.7 (Ord. 10/11) Sea un acuerdo de nivel de servicio
en el que el retardo de los paquetes debe ser inferior a 0.5 s. Todo
paquete con un retardo superior a dicho umbral conlleva una penalización de 0.01 e/s a partir de dicho umbral (p.ej., un paquete con
un retardo total de 1.8 s conllevaría una penalización de 0.013 e).
Suponga que el retardo de los paquetes sigue una variable aleatoria
exponencial de media 1 segundo. Se pide: (suponga que e−0,5 ≈ 0,6)
1. Coste medio por paquete.
2. Coste medio de los paquetes que suponen un coste.
Problema 2.8 (Ord. 11/12) Sea un servicio DNS compuesto por
tres servidores. El tiempo en servir una petición se puede modelar
según una variable aleatoria exponencial. Cada servidor proporciona un tiempo medio de servicio diferente: 1/2, 1, y 2 milisegundos.
Suponga que los tres servidores se encuentran ocupados y justo
llega una petición al sistema.
1. Calcule el tiempo medio de espera de la petición antes de empezar a ser atendida.
2. Calcule el tiempo medio total que tarda dicha petición en ser
servida.
Solución.
1. 2/7 ms; 2. 8/7 ms.
Procesos de llegada de Poisson
Problema 3.1 Se define una ráfaga de tráfico como una sucesión
de tramas espaciadas menos de 1 ms. Suponga que acaba de llegar
la primera trama. Calcule la probabilidad de que se forme una
ráfaga de 10 tramas (y sólo 10), si llegan siguiendo un proceso de
Poisson de parámetro λ tramas/ms.
Solución.
e − λ (1 − e − λ )9 .
Problema 3.2 Sea un switch al que llegan tramas según un proceso de Poisson de tasa λ = 2 tramas/s. Calcule la duración de la
ventana de tiempo T en la que la probabilidad de que llegue una
única trama sea máxima.
Solución.
1/2 s.
Problema 3.3 Los goles que un equipo de fútbol mete en un partido es una variable aleatoria que se puede modelar con un proceso
de Poisson. Suponga que el equipo de fútbol RM tiene una media
de cuatro goles por partido, el equipo ATM una media de dos goles
por partido, y se juega el partido RM-ATM. Dispone de 10 e que va
a gastar en una de las siguientes opciones:
2-1 al descanso (6 e/ e apostado).
2-2 al descanso (10 e/ e apostado).
¿Qué opción elegiría?
Problema 3.4 (Ej. 10/11) Un switch Ethernet tiene 64 puertos de
entrada y dos puertos de salida. Los paquetes llegan a cada puerto
de entrada con un tiempo entre paquete que se distribuye según
una distribución uniforme U(2,12) segundos. El 90 % del tráfico de
63 puertos de entrada va a un puerto de salida. El 10 % restante, y
el tráfico del puerto 64 de entrada, va al segundo puerto de salida.
1. Discuta si se puede considerar el proceso de llegada al primer
puerto como un proceso de Poisson. De ser así, calcule su tasa.
2. Si el tráfico de todos los puertos de entrada es de Poisson con
tasa 5 paquetes/segundo, describa el proceso en el segundo
puerto y calcule su tasa.
10
una introducción amable a la teoría de colas: problemas propuestos
Solución.
1. 8.1 paquetes/segundo; 2. 36.5 paquetes/segundo.
Problema 3.5 (Ord. 09/10) Un códec de voz sobre IP (VoIP) genera paquetes de 80 bytes de longitud fija cada 20 +/- 1 ms (esto es,
el tiempo hasta el siguiente paquete se distribuye uniformemente
entre 19 y 21 ms). Suponga que el agregado de 100 teléfonos VoIP
se sirve con un concentrador que transmite a 10 Mbps. Dicho concentrador se bloquea si tiene que procesar 2 o más tramas a la vez.
Calcule la probabilidad de que, mientras está transmitiendo una
trama, se bloquee.
Solución.
1 − e−0,32
Problema 3.6 (Ej. 11/12) A un servidor con una única CPU y
una cola de espera infinita llegan peticiones según un proceso de
Poisson de tasa λ peticiones/segundo. Una vez que la CPU comienza a atender una petición, el tiempo que tarda en completarla se
puede modelar con una variable aleatoria exponencial de media
µ−1 segundos. Se pretende analizar el servicio recibido por la segunda petición que llega al sistema. En concreto, se desea conocer
para la segunda petición:
1. Probabilidad de que tenga que esperar.
2. Tiempo medio de espera hasta que empieza a ser atendida.
3. Tiempo medio total que pasa la petición en el servidor.
Solución.
1. λ/(λ + µ); 2. (λ/µ)/(λ + µ); 3. µ−1 (1 + λ/(λ + µ).
Cadenas de Markov de tiempo discreto
Problema 4.1 Una moneda 1 cuando es lanzada al aire tiene una
probabilidad de 0.6 de que salga cara, mientras que una moneda 2
lo hace con probabilidad 0.5. Una moneda es lanzada al aire continuamente hasta que sale cruz, en ese momento la moneda se retira
y se coge la otra.
1. Si se empieza moneda 1, calcule la probabilidad de que la moneda 2 sea usada en el tercer lantamiento.
2. Calcule la proporción de lanzamientos que se realizan con la
moneda 2.
3. Indique la proporción de caras que son debidas a la moneda 2.
Solución.
1. 0.44; 2. 4/9; 3. 2/5.
Problema 4.2 Tres de cada cuatro camiones en una carretera son
seguidos por un coche, mientras que uno de cada cinco coches es
seguido por un camión. Calcule la fracción de vehiculos que son
camiones.
Solución.
4/19.
Problema 4.3 Suponga que la probabilidad de que un día llueva
(o no) depende de si ha llovido (o no) en los tres días anteriores.
Muestre la forma en que podría modelar el sistema usando una
cadena de Markov. Deduzca el número de estados necesarios.
Solución.
8.
Problema 4.4 Siguiendo con el ejemplo anterior del clima, suponga ahora que si ha llovido en los tres días anteriores, la probabilidad de que llueva hoy es de 0.8; si no llovió en ninguno de los
tres días anteriores, la probabilidad de que llueva hoy es de 0.2; y
en cualquiera de los otros casos, hay una probabilidad de 0.6 que
el tiempo hoy sea como el de ayer. Determine P para la cadena de
Markov propuesta.
Problema 4.5 (Ej. 10/11) Suponga que en una red inalámbrica
basada en el estándar IEEE 802.11 (WiFi) las estaciones pueden usar
12
una introducción amable a la teoría de colas: problemas propuestos
los siguientes esquemas de modulación: C=1, 2, 4, 8 Mbps. Una
mayor tasa permite transmitir más datos en menos tiempo, pero
a cambio resultan más vulnerables a los errores en el canal. Las
estaciones utilizan el siguiente algoritmo de ajuste de tasa: si una
transmisión tuvo éxito, se aumenta la tasa a la siguiente más alta; si
una transmisión tuvo error, se reduce la tasa a la siguiente más baja
(p. ej.: transmitir con éxito a 2 Mbps implica que el siguiente intento
de transmisión se realiza a 4 Mbps; de fracasar, se reducirá la tasa
a 1 Mbps). Suponga que todas las transmisiones a 1 Mbps tienen
éxito; que las transmisiones a 2 y 4 Mbps tienen una probabilidad
de error de trama de 1/4; y que las transmisiones hechas a 8 Mbps
fallan con probabilidad 1/2.
1. Si una trama se transmite con éxito, calcule la probabilidad de
que haya sido enviada a 8 Mbps.
2. Si una trama se transmitió a 4 Mbps, ¿con qué probabilidad la
anterior trama se transmitió a 2 Mbps?
3. ¿Cuál es la tasa de transmisión media?
Solución.
1. 9/22; 2. 1/4.;
Problema 4.6 (Ord. 10/11) Un determinado jugador es muy
aficionado a los batidos. Tiene tres marcas favoritas, A, B y C, de
precio 760, 380 y 190 e, respectivamente. Su proceso para elegir
qué tomar antes de cada partido es el siguiente: si tras acabar un
partido no tiene molestias, al siguiente partido tomará la siguiente
marca más barata (si la hubiera). Si al acabar el partido sí que tiene
molestias, para el siguiente partido tomará la siguiente marca más
cara (si la hubiese). La marca A nunca le ocasiona molestias, la
marca B le ocasiona molestias el 20 % de las veces que la usa, y la
marca C le causa molestias el 60 % de las veces que la usa.
1. Si en el primer partido usa la marca A, ¿qué marca usará en el
cuarto partido?
2. Calcule en media cuánto se gasta por partido.
Solución.
1. B (68 %), C (32 %); 2. 310 e.
Problema 4.7 (Ext. 10/11) Sea un determinado proceso que se
puede modelar con una cadena de Markov discreta. Se barajan las
siguientes opciones:
1/3
2/3
8 Aa
1/2
!
2/3
Be
1/2
1/3
8 Aa
!
B
1
Una observación del proceso consiste en la siguiente secuencia
. . . A A A B A . . .. A la vista de la observación, razone qué cadena
es más adecuada para modelar el proceso.
cadenas de markov de tiempo discreto
Solución.
13
Ambas son igual de plausibles.
Problema 4.8 (Ord. 09/10) Dos estaciones comparten el medio usando una variante de Aloha ranurado, donde las pérdidas
sólo se producen por colisión, es decir, cuando las dos estaciones
transmiten a la vez. Las estaciones emplean el siguiente mecanismo
para acceder al medio: si una ranura queda vacía (ninguna estación
transmitió), en la siguiente ranura transmitirán con probabilidad
p; si la ranura no queda vacía, transmitirán con probabilidad p/2.
Calcule la probabilidad de que una ranura contenga un éxito para
p = 1/2.
Solución.
3/7.
Problema 4.9 (Ord. 11/12) Un determinado servidor es poco
fiable: tiene días buenos, regulares y malos. La probabilidad de que
una petición falle depende de cada día, y se tiene que las probabilidades de fallo son p B = 0, p R = 1/2, y p M = 5/8, para cada el
caso de un día bueno, regular y malo, respectivamente. Tras un día
bueno, existe una probabilidad del 50 % de tener un día regular, y
del 50 % de tener un día malo. Después de un día regular siempre
hay un día malo, mientras que después de un día malo el 25 % de
las veces viene un día bueno, y el 75 % otro día malo.
1. Calcule la probabilidad media de fallo de una petición.
2. Si hoy es un día malo, ¿qué probabilidad hay de que ayer fuese
un día bueno?
Solución.
1. 1/2; 2. 1/8.
Problema 4.10 (Ext. 11/12) En una determinada organización sólo permiten navegar por tres páginas web: A.com, B.com
y C.com. Suponga un robot (crawler) cuya función es visitar constantemente dichas páginas, según el siguiente algoritmo: estando en
una página, escoge al azar la siguiente página a visitar entre todos
los enlaces que encuentra en dicha página. Suponga que cada página tiene la distribución de enlaces de la tabla. Se puede ver, por
ejemplo, que la página A tiene 750 enlaces internos y no enlaza a C;
la página B no tiene enlaces internos, y la página C no enlaza a B.
Calcule la proporción de visitas que realizará el robot a cada una de
las tres páginas.
Solución.
4/9, 1/9, 4/9.
Problema 4.11 (*) (El problema del gato y el ratón). Hay cinco
cajas en fila, con un gato en la primera y un ratón en la última. Tras
un intervalo de tiempo T, cada animal salta a una caja colindante, completamente al azar. Modele el sistema con una cadena de
Markov discreta.
Página / Enlaces
A
B
C
A
750
100
1000
B
250
C
100
7000
Cadenas de Markov de tiempo continuo
Problema 5.1 Sea una universidad con dos ascensores, cada uno
con un tiempo de vida que se puede modelar con una variable aleatoria exponencial de media 1/λ. Hay tres políticas de reparación:
Sólo se avisa a mantenimiento cuando los dos ascensores están
estropeados, siendo el tiempo de reparación de los dos ascensores (a la vez) una variable aleatoria exponencial de media 1µ.
Se avisa a mantenimiento en cuanto un ascensor se estropea,
pero sólo hay un técnico disponible. El tiempo de reparación por
ascensor es una variable aleatoria exponencial de media 1/µ.
Igual que en el caso anterior, pero hay dos ténicos disponibles.
Calcule la proporción de tiempo que la universidad tiene los dos
ascensores funcionando y ningún ascensor funcionando, en los
siguientes casos
1. 1/λ = 1 semana, 1/µ = 2 semanas.
2. 1/λ = 1/2 semana, 1/µ = 1 semana.
Problema 5.2 Sea una estación de servicio con un único surtidor. Los clientes llegan según un proceso de Poisson de tasa 20
coches/hora, y sólo hay hueco para dos coches (incluyendo el que
estuviese repostando). Suponga que el tiempo necesario para repostar un vehículo es exponencial de media 5 minutos.
1. Calcule la proporción de tiempo que el surtidor está ocupado.
2. Calcule la proporción de clientes que se pierden.
Solución.
1. 40/49; 2. 25/49.
Problema 5.3 Una barbería, con un único barbero, tiene sitio para
hasta dos clientes. Los clientes llegan según un proceso de Poisson
de 3 clientes/hora, y el tiempo que tarda el barbero en despachar a
un cliente es exponencial de media 15 minutos. Calcule
1. La proporción de clientes que entran a la barbería.
2. El número medio de clientes en la barbería.
3. Si el barbero trabajase al doble de la velocidad, repita el apartado
1.
16
una introducción amable a la teoría de colas: problemas propuestos
Solución.
1. 28/37; 2. 30/37; 3. 88/97.
Problema 5.4 Una tienda se compone de tres máquinas y dos
reparadores. El tiempo en activo (sin estropearse) de una máquina
es exponencial de media 10 minutos. El tiempo para reparar una
máquina es exponencial de media 8 minutos. Se pide:
1. Calcule la proporción de tiempo que los dos operarios están
ocupados a la vez.
2. Calcule el número medio de máquinas que no se usan.
Solución.
1. 336/761; 2. 1068/761.
Problema 5.5 Una empresa tiene dos ordenadores que se usan a
la vez. El tiempo que pasa hasta que un ordenador se estropea es
exponencial de media 1/λ. Cuando esto pasa, un técnico se pone
a repararlo de forma inmediata, y tarda un tiempo exponencial
de media 1/µ. Los fallos son independientes entre ordenadores,
y tras la reparación el PC queda como nuevo y se reincorpora al
servicio de forma inmediata. Obtenga el diagrama de transiciones
del proceso y calcule, para λ = 5 y µ = 10:
1. La proporción de tiempo que la empresa no tiene ningún PC
disponible
2. La proporción de tiempo que la empresa no dispone de algún
PC.
Solución.
1. 1/5; 2. 3/5.
Problema 5.6 Sean 3 bombillas que siempre están encendidas.
Las bombillas tienen un tiempo de vida exponencial, de media
1/λ. Solo se cambia las bombillas cuando se han fundido todas,
y en esto se tarda un tiempo exponencial de media 1/µ. Obtenga
el diagrama de transiciones del proceso y calcule, para λ = 5 y
µ = 10:
1. La probabilidad de que solo haya una bombilla fundida.
2. La probabilidad de que las tres bombillas estén funcionando.
Solución.
1. 3/14; 2. 1/7.
Problema 5.7 Una centralita, con dos líneas de salida, da servicio
a cuatro usuarios que solo realizan llamadas externas. Cada usuario
llama según un proceso de Poisson de tasa λ llamadas/minuto. La
duración de una llamada es exponencial, de media 1/µ minutos.
Si un usuario no puede llamar porque no hay línea de salida, no
lo vuelve a intentar y la llamada se pierde. Obtenga el diagrama
de transiciones del proceso y calcule el número medio de líneas
ocupadas para λ = 1/2 y µ = 2.
cadenas de markov de tiempo continuo
Solución.
14/19.
Problema 5.8 Una línea de montaje se compone de dos estaciones
en serie. Cada estación admite un único item en cada momento.
Cuando un item termina en la primera estación, pasa a la segunda solo si ésta está vacía, de lo contrario se queda esperando. Los
items llegan a la primera estación según un proceso de Poisson de
tasa λ, pero solo se admiten si la estación está vacía –de lo contrario, son descartados. El tiempo que tarda un item en la estación
i es exponencial de media 1/µi . Defina la cadena de Markov que
modela este proceso. Calcule, para λ = 10, µ1 = 20 y µ2 = 50:
1. La probabilidad que no haya ningún item en la línea de montaje.
2. La probabilidad que de haya un item esperando en la primera
estación.
Solución.
1. 175/317; 2/317.
Problema 5.9 (Ext. 09/10) Suponga que el tiempo que funciona
su conexión ADSL es exponencial de media 30 semanas. Cuando se
estropea, la compañía consigue repararlo en un tiempo exponencial
de media 3 semanas, enviándole un operario a casa.
1. Calcule el porcentaje de tiempo que no tiene acceso a Internet.
Suponga ahora que contrata un ADSL adicional con otro proveedor
diferente, independiente, pero con las mismas prestaciones de
servicio y reparación. En cuanto detecta que un acceso deja de
funcionar, avisa a la compañía correspondiente.
2. Calcule el porcentaje de tiempo que no tiene acceso a Internet.
Además de estos accesos ADSL, contrata otros dos ADSL independientes, con otros proveedores independientes, pero las mismas
prestaciones.
3. Calcule el nuevo porcentaje de tiempo sin acceso a Internet.
El hecho de tener a tanto operario por su casa resulta molesto. En
su vivienda le imponen la siguiente política: solo cuando todos los
ADSL dejen de funcionar se avisará a un reparador independiente,
capaz de arreglar los cuatro ADSL en un tiempo exponencial de
media 6 semanas (suponga que los repara todos a la vez).
4. Calcule el porcentaje de tiempo sin acceso a Internet.
Solución.
1. 1/11; 2. 1/121; 3. 1/14641; 4. 12/137.
Problema 5.10 (Ord. 10/11) Un sistema se compone de una cola
de tamaño unidad y dos servidores, uno de baja velocidad y otro
de alta. Los servidores procesan las peticiones según una variable
aleatoria exponencial, de media 1/2 y 1/4 segundos, respectivamente. El servidor lento se usa siempre que sea posible, esto es, el
17
18
una introducción amable a la teoría de colas: problemas propuestos
servidor rápido solo atiende una petición si el servidor el lento está
ocupado. Las peticiones llegan según un proceso de Poisson de tasa
6 peticiones/segundo. Modele el sistema como una cadena de Markov, indicando claramente los estados y las transiciones entre ellos
y resuelva::
1. Calcule la probabilidad de que, al llegar, una petición no quepa
en el sistema.
2. Calcule el número medio de peticiones en el sistema.
Solución.
1. 5/17; 2. 30/17.
Problema 5.11 (Ext. 10/11) Cuando accede a Internet usando
la red WiFi obtiene una velocidad de descarga de 5 Mbps. Sin embargo, la red no es 100 % fiable, sino que cuando está siendo usada
se puede “caer”, quedando fuera de servicio un tiempo exponencial de media 30 minutos. Suponga que el tiempo que pasa desde
que vuelve a estar disponible hasta que se cae de nuevo también es
exponencial, de media 2 horas.
1. Calcule el ancho de banda medio disponible.
Suponga ahora que su ordenador dispone de un módem 3G que,
en cuanto detecta que la red WiFi no funciona, se activa y le permite navegar a 1 Mbps. Dicha conexión 3G también falla cuando
está siendo usada: tiene un tiempo de vida exponencial, de media
1 hora, y tarda en recuperarse 15 minutos. Tenga en cuenta que
su ordenador siempre se conectará a la WiFi si ésta se encuentra
disponible.
2. Calcule la probabilidad de no tener conexión, y el ancho de
banda medio disponible.
Solución.
1. 4 Mbps; 2. 9/305, 1272/305 (≈ 4.2 Mbps).
Problema 5.12 (Ord. 11/12) Sea un conmutador con dos puertos
de entrada diferenciados y un único puerto de salida. El tráfico del
puerto de baja prioridad llega según un proceso de Poisson de tasa
λ B = 1 tramas/segundo; si el puerto de salida está ocupado, es
descartado. El tráfico del puerto de alta prioridad llega según un
proceso de Poisson de tasa λ A =2 tramas/segundo, y en caso de
que el puerto de salida esté ocupado se dispone de espacio para
almacenar una única trama. El tiempo de servicio de cada trama se
puede modelar según una variable aleatoria exponencial de media
0.25 segundos. Se pide:
1. Calcule la probabilidad de pérdida para cada tipo de tráfico.
2. Calcule el retardo total de cada tipo de tráfico.
cadenas de markov de tiempo continuo
Solución.
1. 3/17, 9/17; 2. 5/14, 1/4.
Problema 5.13 (Ext. 11/12) Sea una cafetería, pequeña, que
ofrece WiFi gratis a los clientes. De hecho, los clientes no van por
precisamente por el café, sino para descargarse una cantidad de
datos que se puede modelar según una variable aleatoria exponencial, de media 480 Mbytes (acabada la descarga abandonan el local).
La velocidad efectiva de la WiFi es de 32 Mbps, que se distribuye
equitativamente entre los usuarios de la cafetería (por ejemplo: con
dos clientes, la velocidad de descarga por cliente es la mitad que en
el caso de un cliente solo). Si como mucho caben 4 clientes, y llegan según un proceso de Poisson de tasa 15 clientes/hora, ¿cuánto
tiempo pasan en media los clientes en la cafetería (en minutos)?
Solución.
52/15.
19
Teoría de colas: sistemas básicos
Problema 6.1 Se desea comparar un sistema M/M/1 con un
sistema M/M/2 donde la capacidad de cada recurso es la mitad
que para el sistema M/M/1. Suponga λ = 1, µ1 = 2 y µ2 = µ1 /2.
Realice la comparación en términos de tiempo medio total en el
sistema y tiempo medio de espera en cola.
Solución.
M/M/1: T=1, W=1/2; M/M/2: T=4/3, W=1/3.
Problema 6.2 (*) Compare las prestaciones (en términos de tiempo medio de estancia en el sistema) de tres colas, cada una con tasa
de entrada λi y de salida µi
Un sistema M/M/1, con (λ1 , µ1 )
Un sistema M/M/2, con (λ1 , µ1 /2).
Dos sistemas M/M/1, con (λ1 /2, µ1 /2)
Pista.
Calcule Ni , expresado en función de ρi .
Problema 6.3 Sea un sistema M/M/1, cuyo coste por unidad de
tiempo viene dado por la suma de dos componentes: una es proporcional a la la velocidad de servicio µ contratada (con constante
Cu ), mientras que la otra es proporcional al tiempo total de estancia
en el sistema T (con constante Ct ). Obtenga la µ que minimiza el
coste.
Solución.
µ=
q
Ct
Cu
+λ
Problema 6.4 Sean dos centrales unidas por 4 circuitos. La primera recibe llamadas hacia la segunda a una tasa λ = 3 llamadas/minuto. La segunda recibe llamadas hacia la primera a una
tasa tres veces inferior (también de Poisson). La duración de las llamadas es exponencial, de media 30 segundos. Si llega una llamada
y están todos los circuitos ocupados ésta se pierde. Se pide
1. Llamadas atendidas por unidad de tiempo.
2. Número medio de circuitos ocupados.
22
una introducción amable a la teoría de colas: problemas propuestos
Solución.
1. 76/21; 2. 38/21.
Problema 6.5 Se tiene un concentrador que recibe paquetes de
un conjunto de diez ordenadores y que debe enviar a un nodo
de red. Los paquetes tienen una longitud que se puede modelar
mediante una distribución exponencial de media 960 bits. Cada
ordenador genera paquetes según una Poisson de media λ = 2,5
paquetes/segundo. Suponga dos opciones:
1. Unir el concentrador y el nodo de red por un enlace de 64 Kbps
de capacidad.
2. Unir el concentrador y el nodo de red por dos enlaces de 32
Kbps de capacidad.
Se pide, para cada una de las dos opciones: a) tiempo medio empleado hasta que el concentrador ha transmitido un paquete recibido; b) probabilidad de que un paquete no tenga que esperar; c)
tiempo medio de espera de los paquetes que esperan.
Solución.
31 ms.
1. a) 24 ms; b) 5/8; c) 24 ms; a) ≈ 35 ms; b) 5/11; c)
Problema 6.6 Analice si es mejor tener una línea de capacidad
C, o k líneas de capacidad C/k (cada una) sirviendo cada línea a
la k-ésima parte del tráfico. Haga las suposiciones necesarias para
resolver el problema, pero intente que sean las menos posibles.
Problema 6.7 (Ej. 10/11) Un servidor emplea dos máquinas idénticas para servir páginas web, con una única cola de espera de
tamaño infinito desde la que se dirige cada petición a la primera
máquina que quede disponible. Suponga que las peticiones llegan
según un proceso de Poisson de tasa 40 peticiones por minuto, y
que cada petición demanda un tiempo exponencial de media 2
segundos.
1. Calcule en segundos el tiempo total (en media) que pasa una
petición en el sistema.
Suponga ahora que se emplea una única máquina, más rápida,
para atender las peticiones.
2. Si el tiempo demandado sigue siendo exponencial, ¿cómo de
rápido debe ser dicha máquina (en comparación con una de
las dos máquinas del apartado anterior) para obtener el mismo
tiempo medio?
Solución.
1. 18/5 s; 2. 17/9 más rápida.
Problema 6.8 (Ej. 11/12) Un servidor emplea tres máquinas idénticas para servir peticiones web, con una única cola de espera. Dicha cola tiene tamaño infinito, y las peticiones se dirigen a la primera máquina que quede disponible. Las peticiones llegan según un
teoría de colas: sistemas básicos
proceso de Poisson de tasa 4 peticiones/segundo, y el tiempo que
tarda en ser servida una petición se distribuye según una variable
aleatoria exponencial de media 500 ms.
1. Calcule, en segundos, el tiempo medio total que se tarda en
atender una petición.
Suponga ahora que en vez de tres máquinas se emplea una única
máquina, pero tres veces más rápida.
2. ¿Cuál sería en estas condiciones el valor del tiempo medio total?
3. Compare los resultados anteriores.
Solución.
1. 13/18; 2. 1/2.
Problema 6.9 (*) Demuestre las siguientes propiedades de la
Erlang-B.
B(n, I ) =
I · B(n − 1, I )
n + I · B(n − 1, I )
B(n1 + n2 , I1 + I2 ) < B(n1 , I1 ) + B(n2 , I2 ),
23
Teoría de colas: sistemas avanzados
Problema 7.1 (*) Se quiere calcular el tiempo medio que pasa desde que un usuario llega a un sistema M/M/1 hasta que el recurso
queda libre por primera vez y que, por tanto, otro usuario pase a
emplearlo (esto es, el tiempo residual de servicio). Sean dos formas de
calcular este tiempo
El tiempo medio de espera en cola (que se tiene por análisis
del M/M/1) es igual al tiempo requerido por los usuarios por
delante de dicho usuario más el tiempo restante del usuario que
ya estuviese sido atendido, siendo este último tiempo el tiempo
que se quiere calcular.
Dicho tiempo medio residual, por otra parte, es sencillo de calcular sabiendo que el tiempo de servicio es exponencial (esto es, sin
memoria).
Compare los resultados.
Problema 7.2 (*) Sea el sistema en tándem de la figura, donde los
tiempos de servicio son variables aleatorias exponenciales independientes, de tasa µ1 y µ2 , y el proceso de llegadas al primer sistema
es exponencial de tasa λ.
Modele el sistema como una cadena de Markov, donde el estado
(n, m) represente el número de usuarios en cada sistema, y compruebe que las ecuaciones de balance de dicho sistema se cumplen
si
n m λ
λ
λ
λ
Pn,m =
1−
1−
µ1
µ1
µ2
µ2
Solución. La ecuación se cumple para los cuatro tipo de estados:
(i) (0, 0), (ii) (n, 0), n > 0, (iii) (0, m), m > 0, y (iv) (n, m), n, m > 0.
Problema 7.3 Sea una comunicación TCP entre dos nodos, donde
el primero manda datos al segundo. La aplicación genera segmentos de 1460 B según un proceso de Poisson. Discuta si se podría
modelar las tramas generadas por el primero nodo como un proceso de Poisson.
Solución.
No.
Figura 7.1: Sistemas M/M/1 en
tándem.
26
una introducción amable a la teoría de colas: problemas propuestos
Problema 7.4 En una red de datos se transmiten dos tipos de
paquetes. Un tipo son paquetes de control, todos de 48 bits de
longitud. El otro son paquetes de datos de usuarios que tienen una
longitud que se puede modelar con una distribución exponencial
de media 960 bits. Los enlaces de transmisión tienen una capacidad
de 9600 bits/seg. El 20 % de los paquetes que forman el tráfico
total son paquetes de control. La utilización global en un enlace es
de ρ = 0,5. Calcule el tiempo medio de espera antes de que los
paquetes empiecen a ser transmitidos si la disciplina de la cola es
FCFS sin prioridades.
Solución.
16005/162 ≈ 100 ms.
Problema 7.5 Analice si es mejor tener una línea de capacidad
C, o k líneas de capacidad C/k (cada una) sirviendo cada línea a
la k-ésima parte del tráfico. Haga las suposiciones necesarias para
resolver el problema, pero intente que sean las menos posibles.
Problema 7.6 Sea la red de colas abierta de la figura, donde la
llegada de usuarios sigue un proceso de Poisson, todas las colas
disponen de un único servidor, todos los tiempos de servicio son
exponenciales y las tasas se miden en eventos / hora. Calcule T y
N.
Figura 7.2: Red de colas
Solución.
N = 213/35; T = 71/210.
Problema 7.7 Sea la red de la figura, donde el terminal conectado al nodo 1 genera tráfico según una distribución de Poisson de
media λ = 3 paquetes/segundo. Todos los paquetes van destinado
al nodo 4. La longitud de los paquetes se puede modelar mediante una distribución exponencial de media 2048 bits, mientras que
todos los enlaces tienen una capacidad de 12288 bits/s. Calcule el
tiempo medio que tardan los paquetes de ir del nodo 1 al 4 en los
siguientes casos:
1. Las tablas de encaminamiento dirigen todo el tráfico del nodo 1
al 4, por el camino 1-2-4.
2. Las tablas de encaminamiento dirigen todo el tráfico del nodo 1
al 4, por el camino 1-2-3-4.
teoría de colas: sistemas avanzados
3. Se emplean unas tablas de encamientamiento aleatorias: en el
nodo 1, la probabilidad de dirigir el tráfico hacia el nodo 3 (q13 )
es de 1/3; q23 = 3/4, y q34 = 1.
Indique las suposiciones que necesita hacer para resolver el problema, y su validez.
Figura 7.3: Red de colas
Solución.
1. 2/3 s; 2. 1 s; 3. 4247/6930 s.
Problema 7.8 (Ord. 09/10) Sea un switch (switch A) con 20 puertos de entrada y un puerto de salida. A cada puerto de entrada
llega un tráfico de tasa 100 paquetes por segundo, y la capacidad
de procesado del switch es de 50 paquetes por milisegundo (ms).
Tras pasar por este switch, el 70 % del tráfico se dirige a un segundo
switch (switch B) con una capacidad de 30 paquetes/ms, mientras
que el 30 % se dirige a otro switch (switch C) con una capacidad
de 10 paquetes/ms. Suponga que el tráfico de entrada es de Poisson, y que los tiempos de procesado de A y B son exponenciales,
mientras que el tiempo de procesado del switch C se distribuye uniformemente entre 0 y una constante. Obtenga el tiempo medio de
estancia en todo el sistema.
Solución.
1/48 + 0.7 · 1/28.6 + 0.3 · 9.8/94 ms.
Problema 7.9 (Ext. 09/10) A una cola de longitud infinita con un
único recurso llegan los usuarios según un proceso de Poisson. Sea
TM el tiempo medio de estancia total en el sistema si el tiempo de
servicio es exponencial de media µ−1 , y TD el tiempo medio de
estancia total si el tiempo de servicio es determinista de media µ−1 .
Calcule TD /TM .
Solución.
1 − ρ/2.
Problema 7.10 (Ord. 10/11) Sea la red de colas de la figura, donde los sistemas 1 y 2 se pueden modelar como colas M/M/1 con
tasas de servicio µ1 = 18 y µ2 = 20 paquetes/segundo, respectivamente, y donde la tasa de entrada a la red es λ = 8 paquetes/segundo. Calcule el número medio de usuarios en el sistema, y
el tiempo medio de estancia total en el sistema.
27
28
una introducción amable a la teoría de colas: problemas propuestos
Figura 7.4: Red de colas
Solución.
1. 2; 2. 1/4 s.
Problema 7.11 (Ext. 10/11) A un nodo llegan tramas TCP según
un proceso de Poisson de tasa 15 tramas por milisegundo. Una
proporción p de dichas tramas la constituye segmentos de datos
TCP, de longitud constante e igual a 960 bytes, mientras que el resto
son asentimientos, de tamaño fijo 40 bytes. El enlace de salida es de
80 Mbps.
1. Si p = 2/3, calcule la ocupación media del enlace.
2. Si la ocupación media es del 75 % (o sea, 3/4), calcule p.
3. Suponga ahora que hay tantos segmentos como asentimientos (o
sea, p = 1/2). Calcule el tiempo medio de espera en cola.
Solución.
1. 98 %; 2. 1/2; 3. 138.48 µs.
Problema 7.12 (Ord. 11/12) Sea la red de colas representada en la
figura, donde en cada sistema hay un único recurso, el proceso de
llegadas es de Poisson y los tiempos de servicio son exponenciales.
Figura 7.5: Red de colas
Se tiene que:
p1 = 1/5, p2 = 1/2, p3 = 1/2
λ = 4 tramas/s, µ1 = 8 tramas/s, µ2 = 4 tramas/s, µ3 = 2
tramas/s
Se pide:
1. Calcule el tiempo medio para atravesar cada sistema.
2. Calcule el tiempo medio total en atravesar la red.
teoría de colas: sistemas avanzados
Solución.
1. 1/4 s, 1 s, 1 s; 2. 5/4 s.
Problema 7.13 (Ext. 11/12) Sea el sistema de la figura. Los dos
flujos de llegada siguen un proceso de Poisson, si bien con distinta tasa. Además, las tramas del primer flujo tienen una longitud
constante de 1500 octetos, mientras que la longitud de los paquetes
del segundo flujo se puede modelar según una variable aleatoria
exponencial, de media 1250 octetos. Calcule el retardo medio total
(en microsegundos) que sufre cada flujo al atravesar el sistema.
Solución.
Figura 7.6: Red de colas.
21 µs, 19 µs.
29
Batiburrillo
Problema 8.1 (Ord. 12/13) Sea un equipo de fútbol con dos entrenadores. Después de cada partido puede salir un entrenador (K)
u otro (M) a dar la rueda de prensa. El entrenador K nunca da más
de tres ruedas de prensa de forma consecutiva, mientras que el entrenador M nunca da dos (ni más) ruedas de prensa seguidas. En
los demás casos, es tan probable que dé la rueda de prensa tanto
uno como otro. Si las ruedas de prensa siguen una variable aleatoria exponencial, de media 22 minutos para M y 11 minutos para K,
calcule la duración media de las ruedas de prensa de dicho equipo.
Solución.
15 minutos.
Problema 8.2 (Ord. 12/13) Sea una red donde los paquetes tienen
que atravesar dos enlaces en serie, de 10 y 20 Mbps, respectivamente. Al primer enlace llegan tramas con un tamaño fijo de 1250 Bytes,
siendo el tiempo entre tramas una variable aleatoria exponencial de
media 2 ms. Calcule, si fuese posible, el retardo total en atravesar el
sistema completo.
Solución. No es posible. El primer enlace introduce un retardo de
1.5 milisegundos.
Problema 8.3 (Ord. 12/13) Sea una empresa con 5 trabajadores
y 1 jefe, que comparten una impresora en red con una capacidad
máxima de 4 trabajos de impresión (es decir: mientras un trabajo
se está imprimiendo, pueden esperar hasta 3 trabajos). El tiempo
para imprimir se puede modelar con una variable aleatoria exponencial de media 24 segundos. La tasa de generación de trabajos de
impresión del jefe se puede modelar con un proceso de Poisson de
media 150 trabajos por hora. El tiempo entre peticiones de impresión de cada empleado se puede modelar con una variable aleatoria
exponencial de media 2 minutos.
1. Calcule la probabilidad de que un trabajo del jefe no se imprima.
2. Si, cansado de quejarse, el jefe se compra una impresora idéntica
para su despacho, calcule el tiempo medio de impresión en cada
impresora (en minutos).
32
una introducción amable a la teoría de colas: problemas propuestos
Solución.
1. 16/31; 2. 1 minuto.
Problema 8.4 (Ord. 12/13) Sea una red WiFi con dos puntos de
acceso, cada uno con una capacidad máxima de 2 usuarios. Los
usuarios llegan al sistema según un proceso de Poisson de tasa 1
usuario cada 6 segundos, y siempre se asocian (y reasocian, cuando
algún usuario abandona el sistema) al punto de acceso con menos
usuarios. El tiempo de (re)asociación es despreciable. Cada usuario permanece en el sistema hasta descargar una cantidad de datos
que se puede modelar según una variable aleatoria exponencial de
media 7.5 MBytes. La velocidad de descarga es de 10 Mbps independientemente del número de usuarios en los puntos de acceso. Si
un punto de acceso consume 13 W si tiene algún usuario asociado y
0 en caso contrario, calcule la potencia media consumida.
Solución.
58/5 W.
Problema 8.5 (Ord. 12/13) El retardo en una red se distribuye
según una variable aleatoria exponencial de media 10 ms. Calcule el
retardo medio de los paquetes con un retardo mayor de 50 ms.
Solución.
60 milisegundos.
Problema 8.6 (Ext. 12/13) Suponga que, en un móvil, el tiempo
de vida de cada componente se puede modelar según una variable
aleatoria exponencial. La pantalla dura, en media, 4 meses; el botón
del menú, 2 meses, y el módulo de WiFi, 8 meses. Reparar la pantalla cuesta 140 e, el botón 35 e y el WiFi 70 e. ¿Cuánto se gasta en
media por reparación?
Solución.
70 e.
Problema 8.7 (Ext. 12/13) El juego de piedra, papel o tijera se
realiza entre dos jugadores. Cada uno elige uno de los elementos
de forma independiente, y se tiene que la piedra vence a la tijera,
la tijera vence al papel, y el papel vence a la piedra (si los elementos coinciden, hay empate). Suponga que un amigo siempre decide
piedra, mientras que el otro amigo actúa de una forma más elaborada: en caso de empate nunca repite elemento, cuando gana repite
elemento el 50 % de las veces, y todas las demás alternativas se distribuyen de forma equiprobable. Calcule la proporción de partidas
en las que la jugada es (piedra, papel).
Solución.
4/9.
Problema 8.8 (Ext. 12/13) El tiempo que se tarda en atender a un
cliente en una hamburguesería se puede modelar con una variable
aleatoria exponencial de media 3 minutos. Los clientes llegan según
un proceso de Poisson de tasa 30 clientes/hora y forman una única
batiburrillo
fila hasta ser atendidos. El encargado tiene que decidir si poner
dos, tres o cuatro empleados atendiendo en paralelo, queriendo
minimizar el coste bajo la condición de que el tiempo medio total
que tarda un cliente desde que llega hasta que ha sido atendido sea
menor de 6 minutos. Qué recomendaría?
Solución.
Dos empleados.
Problema 8.9 (Ext. 12/13) Un cliente en una red WiFi recibe las
tramas en modo “rx” si van destinadas a su dirección MAC, y
en modo “idle” si van destinadas a otra dirección. En el primer
caso, una vez recibida la trama pasa a modo “idle”, mientras que
en el segundo caso tras acabar la trama pasa al modo “sleep”. El
tiempo entre que acaba una trama y llega la siguiente se puede
modelar como una variable aleatoria exponencial de media 10 ms,
y la duración de las tramas es otra variable aleatoria exponencial
de media 5 ms. Las tramas destinadas al móvil constituyen el 80 %
del tráfico del total. El terminal en modo “sleep” consume 0.5 W; en
modo “idle” consume 1 W y en modo “rx” consume 10 W. Calcule
el consumo medio del terminal.
Solución.
10/3 W.
Problema 8.10 (Ext. 12/13) Sea X una variable aleatoria exponencial de media 1/λ1 . Sea Y otra variable aleatoria, que se obtiene
como una variable aleatoria exponencial de media 1/λ2 a la que se
le suma una constante C (por lo tanto, el valor mínimo de Y es C).
Calcule Pr( X < Y ).
Solución.
1−
λ2
− λ1 C
λ1 + λ2 e
Problema 8.11 (Ord. 09/10) Una granja de servidores se compone
de 3 máquinas y 2 administradores. El tiempo que un servidor
se encuentra operativo se puede modelar según una exponencial
de media 5 minutos, mientras que el tiempo necesario para ser
reparado también es exponencial, de media 4 minutos. Se desea
conocer:
1. Número medio de servidores que no están operativos.
2. Proporción de tiempo que los dos administradores están ocupados a la vez.
3. Si cada administrador factura 100 e/hora, el coste estimado de
la factura anual por mantener los servidores.
4. El tiempo medio que un servidor deja de estar operativo
Problema 8.12 (Ej. 11/12) Sea una red 802.11 donde la tasa de
transmisión es de 4 Mbps. Una estación 802.11 debe primero autenticarse y luego asociarse (en este orden) antes de poder enviar
33
34
una introducción amable a la teoría de colas: problemas propuestos
datos. Suponga que autenticarse requiere un tiempo exponencial de
media 1 ms y asociarse supone otro tiempo exponencial de media 1
ms, pero este último proceso falla un 25 % de las veces, lo que conlleva además la pérdida de la autenticación. Una vez completada
la asociación, la estación transmite durante un tiempo exponencial
de media 8 ms, pasado el cual vuelve al estado inicial (esto es, sin
autenticar ni asociar). Calcule la tasa máxima de transmisión que se
podría obtener.
Solución.
3 Mbps.
Problema 8.13 (Ej. 09/10) Hay dos peluquerías cerca de su casa.
En una, pequeña, hay un único peluquero. En la otra hay dos peluqueros, pero los clientes llegan a un ritmo doble. Suponga que
(i) en ninguna peluquería hay sitio para esperar a ser atendido,
(ii) los clientes llegan según un proceso de Poisson, y (iii) el tiempo
necesario para atender un cliente se distribuye según una variable
aleatoria exponencial. Suponga que, en media, llega un cliente cada
hora a la peluquería pequeña y que, para ambas, el tiempo medio
necesario para un corte de pelo es de media hora. Compare las
probabilidades de que un cliente, al llegar, no sea atendido.
Solución.
1/3 vs. 1/5.
Problema 8.14 (Ord. 10/11) Se dispone de un sistema con un único recurso y cola infinita al que las peticiones llegan según un proceso de Poisson. Compare el retardo total en el sistema si el tiempo
que pasa una petición en el recurso es (a) un tiempo determinista
o (b) un tiempo aleatorio con la misma media que el anterior, pero
uniformemente distribuido entre 0 y un determinado valor. Para
realizar la comparación, obtenga el cociente de los retardos medios
Solución.
(1 − ρ/2)/(1 − ρ/3)
Problema 8.15 Sea un sistema con dos servidores y un único buffer. No se trata de un M/M/2/3 convencional, ya que cada servidor
opera a una velocidad diferente. El tiempo medio de servicio del
servidor lento es 1/µ, mientras que para el servidor rápido es la
mitad. Cuando los dos servidores están desocupados y llega un
nuevo trabajo, siempre se usa el servidor lento. Si llega un trabajo
cuando el servidor lento está ocupado, se espera hasta que bien
a) el servidor lento quede libre, pasando entonces a ser ocupado, o
b) llega un nuevo trabajo, por lo que el que estaba esperando pasa
al servidor rápido. Se pide:
1. El diagrama de transición para este sistema.
2. Indique cómo obtendría el tiempo medio de espera en el sistema.
Problema 8.16 (Ej. 11/12) Sea una red Ethernet donde 2/3 de las
tramas son segmentos de datos, y 1/3 de las tramas son segmentos
batiburrillo
de asentimiento. Tras un segmento de datos, la mitad de las veces
aparece otro segmento de datos, y la otra mitad un segmento de
asentimiento. Calcule la probabilidad de observar dos segmentos de
asentimiento consecutivos.
Solución.
0.
Problema 8.17 (*) A un router llegan tramas según un proceso de
Poisson de tasa λ. Si pasa un tiempo T sin que se reciba ninguna
trama, el router inicia tareas de mantenimiento, que se interrumpen
inmediatamente en cuanto llega una trama. Calcule el tiempo medio que pasa desde que se interrumpe una tarea de mantenimiento
hasta que se inicia la siguiente.
Solución.
λ−1 eλT − 1 .
Problema 8.18 (Ej. 10/11) Sea una barbería con un único barbero, en un local en el que solo caben tres clientes (incluyendo al que
esté siendo afeitado), y donde el tiempo que se tarda en atender
a un cliente es exponencial de media 1/µ segundos. Se tiene que
los clientes no llegan de forma individual, sino a pares (esto es, de
dos en dos), y que el tiempo entre llegadas de estas “parejas” de
clientes es exponencial de media 1/λ segundos. De esta forma, por
ejemplo, si el sistema está vacío, el siguiente evento (que ocurre
tras dicho tiempo exponencial) llevará el sistema a un estado con
dos clientes en la barbería. Si una pareja llega cuando solo cabe un
cliente, solo entra uno de ellos, mientras que el otro decide afeitarse
en otro sitio. Modele el sistema con una cadena de Markov, identificando adecuadamente los estados y las correspondientes tasas de
transición entre estados y resuelva:
1. Suponga que hay un cliente en la barbería. Calcule el tiempo
medio que el sistema permanece en dicho estado.
2. Calcule la probabilidad que, habiendo un cliente en la barbería,
el siguiente evento sea tener la barbería llena.
3. Obtenga, en función del cociente ρ = λ/µ, la probabilidad de
que la barbería esté vacía.
Solución.
1. (λ + µ)−1 ; 2. λ/ (λ + µ); 3. 1 + 2ρ + 3ρ2 + ρ3
−1
Problema 8.19 En una estación de autobuses hay dos cabinas
de teléfono. Los viajeros son gente curiosa: cuando nadie está hablando, acuden a llamar según un proceso de Poisson de media 6
usuarios/hora, pero si alguien se encuentra ocupando una cabina,
el ritmo de llegadas se duplica. Además, nunca hay alguien esperando para hablar: los usuarios prefieren buscar otra cabina en otro
lugar. Sabiendo que la duración de una llamada se puede modelar mediante una distribución exponencial de media un minuto,
35
36
una introducción amable a la teoría de colas: problemas propuestos
compruebe que se cumple el teorema de Little, calculando el número medio de usuarios en el sistema, la tasa media de llegadas y el
tiempo medio de estancia en el sistema.
Solución.
12/111 = 720/111 · 1/60.
Problema 8.20 (Ej. 09/10) En un determinado equipo de fútbol
hay dos jugadores encargados de tirar los penalties, Cristiano y
Xabi. Para evitar conflictos han llegado al siguiente acuerdo: si uno
lanza y convierte la pena máxima, tiene derecho a tirar el siguiente
penalti; si falla el penalti, el siguiente lanzamiento le corresponde al
otro lanzador. Suponga que Cristiano falla 1 de cada 32 penalties,
mientras que Xabi acierta el 1 de cada 2 lanzamientos que intenta.
Se pide:
1. Si Cristiano tira el primer penalti de la temporada, calcule la
probabilidad de que tire el tercer penalti de la temporada.
2. Calcule qué proporción de penalties tira cada uno (a largo plazo).
3. Calcule cuál es la probabilidad media de que el equipo falle un
penalti.
Solución.
1. 977/1024; 2. 16/17 y 1/17; 3. 1/17.
Problema 8.21 (Ej. 13/14) El 50 % de las tramas de un flujo de video tienen un tamaño de 1500 B, el 45 % de 500 B, y el 5 % restante
de 100 B. Se puede suponer que el tamaño de una trama es independiente de las anteriores o de las que le siguen. El tiempo entre
tramas se puede modelar según una variable aleatoria uniformemente distribuida entre 10 y 30 ms. Si a un router llega el agregado
de 40 flujos de video independientes, se pide
Probabilidad de que pasen más de 10 ms sin recibir una trama
de 100 B.
Probabilidad de recibir tres o más tramas de 1500 B en 5 ms.
Solución.
1. 1/e, 2. 1 − 18,5e−5
Problema 8.22 (Ej. 13/14) Un grupo de amigos veranea en tres
destinos: Tarifa, Santander y Gandía. Cuando van a Tarifa, nunca
repiten al año siguiente, y eligen uno de los otros dos destinos al
azar; cuando van a Santander, suelen repetir la mitad de las veces,
y la otra mitad deciden ir a Tarifa. Cuando van a Gandía, siempre
repiten un año, y al siguiente lo eligen al azar entre los tres destinos
(si vuelve a tocar Gandía, ya no repiten necesariamente). Calcule la
proporción de veces que veranean en Gandía.
batiburrillo
Solución.
1/3.
Problema 8.23 (Ej. 13/14) Suponga que el tiempo que tarda un
jugador en recuperarse de una lesión se puede modelar con una
variable aleatoria exponencial de media 12 semanas, y supone un
coste para el equipo de 5.000 e/ semana. Existe un tratamiento
muy eficaz basado en batidos que permite una recuperación instantánea, pero tiene coste de 50.000 e. La política que se sigue en
el club es esperar cuatro semanas y, si no se produce recuperación,
proceder al tratamiento. Calcule el coste medio por lesión.
Solución.
52834 e.
37
Formulario
Little
E[ N ] = λ × E[ T ]
Procesos de nacimiento y muerte
n
pn =
∏
i =1
∞
p0 =
1+
λ i −1
p0
µi
n
∑∏
n =1 i =1
λ i −1
µi
! −1
M/M/1
ρ=
λ
, p n = (1 − ρ ) × ρ n , n ≥ 0
µ
ρ
E[ N ] =
1−ρ
FCFS:
FW (t) = 1 − ρe−(1−ρ)µt , t ≥ 0
FT (t) = 1 − e−(1−ρ)µt , t ≥ 0
M/M/m
I=
"
p0 =
I
λ
, ρ=
µ
m
m −1 n
I
∑
n =0
Im
1
+
×
n!
m! 1 − ρ
 n
 I ×p ,
0
pn =
n!
 n−m
ρ
× pm ,
E[ Q] =
∀n ∈ [1, m]
∀n > m
Imρ
m!(1 − ρ)2
FCFS:
FW (t) = 1 −
# −1
p0
pm −mµ(1−ρ)t
e
1−ρ
40
una introducción amable a la teoría de colas: problemas propuestos
M/M/m/k
I=
λ
λ
, ρ = (1 − p k )
µ
mµ
 n
I


× p0 ,
0≤n≤m
n!
pn =
n

I

× p0 ,
m≤n≤k
n
−
m m m!
"
# −1
m
In
I m k−m I n
p0 = ∑
+
×
n!
m! n∑
n =0
=1 m
"
k − m +1 k−m #
I m mI p0
I
I
I
E[ Q] =
− 1−
( k − m + 1)
2 × 1 −
m
m
m
m! 1 − mI
M/M/1/k
 n
λ

1 − λµ

µ



k +1 ,

1 − λµ
pn =





 1 ,
k+1
λ 6= µ
λ=µ
I
( k + 1 ) I k +1
−
,
1−I
1 − I k +1
N=


 k,
2




M/M/m/m
"
p0 =
m
∑
n =0
pn =
In
n!
# −1
In
p0 , 0 ≤ n ≤ m
n!
M/G/1
E [W ] =
λE[t2s ]
2(1 − ρ )
λ 6= µ
λ=µ