[ebook] edicions upc - redes, sistemas y servicios de comunicacion. problemas resueltos - spanish...

AULA POLITÈCNICA 73

Redes, sistemas y servicios de comunicación Problemas resueltos

AULA POLITÈCNICA / ETSETB

EDICIONS UPC

L de la Cruz - J García - J MataJL Melús - E Pallarès - E Sanvicente

Redes, sistemas y servicios de comunicación Problemas resueltos

La presente obra fue galardonada en el séptimo concurso"Ajut a l'elaboració de material docent" convocado por la UPC.

Primera edición: febrer de 2002

Diseño de la cubierta: Manuel Andreu

© Los autores, 2002

© Edicions UPC, 2002Edicions de la Universitat Politècnica de Catalunya, SLJordi Girona Salgado 31, 08034 BarcelonaTel.: 934 016 883 Fax: 934 015 885Edicions Virtuals: www.edicionsupc.esE-mail: [email protected]

Producción: CPET (Centre de Publicacions del Campus Nord)La Cup. Gran Capità s/n, 08034 Barcelona

Depósito legal: B-9299-2002ISBN: 84-8301-531-5

Quedan rigurosamente prohibidas, sin la autorización escrita de los titulares del copyright, bajo las san-ciones establecidas en las leyes, la reproducción total o parcial de esta obra por cualquier medio o pro-cedimiento, comprendidos la reprografía y el tratamiento informático, y la distribución de ejemplares deella mediante alquiler o préstamo públicos.

Índice 9

Índice

1 Conceptos básicos ...............................................................................................................11

2 Técnicas de encaminamiento ...............................................................................................21

3 Mecanismos de control de congestión..................................................................................67

4 Dimensionado y evaluación de dispositivos y redes .............................................................77

5 Evaluación de técnicas de acceso múltiple ........................................................................151

6 Ejercicios de recapitulación ..............................................................................................177

Presentación 7

Presentación

Este libro es una recopilación de problemas resueltos de Redes, Sistemas y Servicios deComunicación, asignatura troncal de segundo ciclo de los estudios de ingeniería de telecomunicaciónen la ETSETB de la UPC.

Muchos de estos problemas han sido propuestos en exámenes de la asignatura, por lo que constituyenuna muestra suficientemente representativa de los temas cuantitativos que en ella se tratan:fundamentalmente, el modelado y la evaluación de redes y conmutadores, así como la caracterizacióndel tráfico y su control.

Más específicamente, después de un capítulo introductorio con ejercicios de carácter básico, seabordan las técnicas de encaminamiento, los mecanismos de control de congestión, el dimensionado yla evaluación de dispositivos y redes, y el análisis de diversos protocolos y técnicas de accesomúltiple. El libro finaliza con una serie de problemas de diferente temática reunidos bajo el epígrafede ejercicios de recapitulación.

Esperamos que la presente obra invite a la reflexión y a la participación activa de los estudiantes, puescreemos que éste es el único medio de aprendizaje.

1 Conceptos básicos 11

1 Conceptos básicos

Problema 1.1

Calcular el tiempo de transferencia entre dos nodos de los paquetes que tienen que esperar.

Datos adicionales:

- λ = 32 paquetes/sg- Capacidad del enlace = 64 Kbps- Longitud de los paquetes = 125 bytes- Distribución exponencial

Solución

Sea T el tiempo de transferencia y ρ la utilización del enlace. Se tiene

Sea Ts el tiempo de transmisión (servicio):

Despejando

Por otra parte

Substituyendo

( ) ( )utilizadoenlaceEutilizadonoenlaceET tt ρρ +−= )1(

( ) ( )utilizadoenlaceETT SS tρρρ

+−=−

11

1

( )ρρ

−−

=12

STutilizadoenlaceE t

5,064000

812532=

⋅⋅==

CLλ

ρ

msg6,1564000

8125 =⋅

==CLTS

Redes, sistemas y servicios de comunicación12

Tiempo de transferencia de los paquetes que esperan = 46,8 msg

( ) msg8,465,015,026,15 =

−−

=utilizadoenlaceE t


Problema 1.2

Una red de datos está compuesta por 11 enlaces dúplex (22 canales de comunicación) de igualcapacidad. Se quiere dar servicio al tráfico generado por 40.000 terminales que, en la hora cargada,generan 12 sesiones/hora con 6 paquetes/sesión. Los paquetes son de 108 bytes y el número medio deenlaces de extremo a extremo, n , es 2. Calcular la capacidad de los canales de comunicación si, paraevitar retrasos, la carga máxima admitida es de 50%.

Solución

El tráfico entrante en la red es,

Por otra parte

Se sabe que

Substituyendo

Despejando C, se obtiene

C = 123 Kbps

paq/seg3600

61240000 ⋅=γ

8108225,05,022

1

22

1 ⋅⋅⋅

=== ∑∑==

CL

C

iiiλλ

γλ

=n

360061240000

8108225,0

2⋅

⋅⋅⋅

=

C


Problema 1.3

En un tránsito de extremo a extremo en una red de comunicación de datos, un paquete debe atravesar 3enlaces.

Paquete saliente��

Paquete entrante

��

Nodo de acceso

Los parámetros de funcionamiento son los siguientes:

- Longitud del paquete = 200 bytes (distribución exponencial)- Capacidad del enlace = 64 Kbps

Calcular el tiempo de tránsito (extremo a extremo) con carga nula, TEE(0), y cuando los enlaces están

cargados al 50%, TEE(0,5).

Si la distribución de las longitudes fuere fija, ¿hasta qué valor de carga, ρ , pueden admitir los enlacespara que el tiempo de tránsito fuere el calculado antes con carga 50%?

Solución

Se tiene queTEE = 3 T

Siendo T el tiempo de transferencia (espera + transmisión) de un enlace. Es decir:

T = Tw + Ts

donde Tw es el tiempo de espera y Ts el de transmisión. Para distribución exponencial Tw está dado por

Carga nulaρ = 0

TW = 0

T = TS

ρρ−

=1SW TT


TEE (0) = 3 TS

TEE (0) = 75 msg

Carga 50%ρ = 0,5

T = 2 TS

TEE(0,5) = 6 TS (el doble)

TEE(0,5) = 150 msg

Distribución constante

Se sabe que

donde CVts es el coeficiente de variación del tiempo de servicio.

En nuestro caso, CVts = 0

Haciendo Tw = Ts, se obtiene

Resumiendo

TEE(0) = 75 msg

TEE(0,5) = 150 msg

ρ = 67 %

6482003)0( ⋅

=EET

SSW TTT =−

=5,01

5,0

ϕϕ−

+=

121 2

Sts

W TCV

T

ρρ−

=12

1SW TT

32=ρ


Problema 1.4

En una red de conmutación de paquetes se ha encontrado que la longitud media de los mensajes (L) esde 30 octetos, y el número medio de nodos (N) atravesados en una ruta es 2. Si el campo de cabecera(H) es de 3 octetos, ¿cuál será la fragmentación óptima de los mensajes en esta red? Supóngase quetodos los enlaces tienen igual capacidad de transmisión, siendo T el tiempo de transmisión de unocteto. Los retardos de propagación, proceso en nodo y espera en colas de retransmisión se considerandespreciables.

Solución

En primer lugar buscaremos una expresión para el tiempo de tránsito de los mensajes en la red.Fragmentando, por ejemplo, los mensajes en 3 paquetes, tendríamos:

Obsérvese que el tiempo total de tránsito es

Ttr = 3 Tp + 2 Tp = 5 Tp (1)

donde Tp es el tiempo de transmisión de un paquete. Dado que el paquete estará formado por unacabecera y una fracción del mensaje

donde hemos llamado n al número de fragmentos o paquetes en que se ha dividido el mensaje.

Volviendo al tiempo de tránsito extremo a extremo de los mensajes (1), observamos que está formado pordos sumandos. El primero de ellos depende del número de nodos atravesados (en este caso N = 2), mientrasque el segundo es función del número de paquetes en que se divide el mensaje (en este caso n = 3). De estemodo, se puede escribir la siguiente expresión genérica

TnLHTp

+=

t=0

ORIGENNODOS INTERMEDIOS

DESTINO

P1

P2

P1

P1

P2

P2

P3

P3

P3

3Tp

2Tp


Ttr = (N + 1) Tp + (n – 1) Tp = (N + n) Tp

Recordando que conocemos el tiempo de transmisión de un paquete, obtenemos

Derivando esta expresión respecto de n e igualando a cero, obtendremos la fragmentación óptima quellevaría al menor tiempo de tránsito de los mensajes en la red

Igualando a cero y despejando

Finalmente substituimos los valores propuestos en el enunciado

Tomando n = 5

( ) THnLnNTtr

++=

Tn

NLHTn

tr

−=

∂∂

2

HNLn =

47,43

230 =⋅=n

( ) TTTtr 63353052 =

++=


Problema 1.5

Llamando tw al tiempo de espera en un nodo, sugerir un método para evaluar p (tw ≤ t) y usar dichaexpresión para calcular el percentil r de tw, Π tw (τ).

Aplicación

Obtener los valores numéricos de Tw y Π tw (90), cuando

- λ = 32 paq/sg- C = 64 Kbps- L = 125 octetos

Solución

p (tw ≤ t) es la función de distribución del tiempo de espera; es, por ello, monótona creciente yasintóticamente vale 1.

Valor en el origen

Así

La función de densidad es

( ) ( ) ρ−===≤= 100)0( wwt tptpFw

ρρ =−=−= aat ,11:0

btt ebttfw

−+−= ρδρ )()1()(

Ftw(t)

t

Se sugiere aproximarlamediante una exponencial

1

1-ρ

( ) btt eatFw

−−= 1


Por lo tanto

Lo que implica que

Finalmente se tiene

El percentil se calcula de la siguiente forma

de donde se deduce que

Aplicación numérica:

Es decir, únicamente un 10% de los paquetes experimenta una espera mayor de 49,9 msg.

∫∞

==0

1)(b

dttftTwtW ρ

SS

W TTTb ρ

ρρρρ −

=

−

==1

1

( )s

w

Tt

t etTρ

ρ−−

−=1

1)(

( )∫∞

Π

− −=

r

bt

wt

dteb100

100 τρ

rT

rbr Wtw −

=−

=100100ln1

100100ln1)( ρ

ρρ

π

5,064000

812532=

⋅⋅==

CLλ

ρ

msg6,1564

8125 =⋅

==CLTs

msg6,151

==−

= SSW TTTρ

ρ

msg9,491050ln

5,06,15)90( ==

wtπ

2 Técnicas de encaminamiento 21

2 Técnicas de encaminamiento

Problema 2.1

Usando el algoritmo de Dijkstra, encontrar el camino de mínimo coste entre A y B, así como el valorde dicho corte.

Solución

Los pasos de la iteración se detallan gráficamente.

E

A

C D

F

G

B

3

3 3

4

1 1

1

1

1 2

2

5 6

E

A

C

3 (3,A)

1 (1,A)


E

A

C D

(3, A)

1

5 (6, C)

(1, A)

(2, C)

E

A

C D

F 4

2

(6, C)

(4, E)

(6, E)

(1, A)

(2, C)

E

A

C D

F

G

B

1

2 6

(6, E) (5, D)

(6, D)

(10, D)

(4, E) (1, A)

(2, C)


Así, el coste mínimo es 9, y el camino óptimo para llegar a B pasa por G, para llegar a G se viene de Dy así sucesivamente, obteniéndose finalmente

A C E D G B

Coste mínimo: 9

Camino óptimo: A C E D G B

E

A

C D

F

G

B

3 (5, D) (6, D)

(10, D)

(4, E) (1, A)

(2, C)

E

A

C D

F

G

B

3

(5, D)

(6, D) (10, D)

(4, E) (1, A)

(2, C) (9, G)


Problema 2.2

Para aumentar la fiabilidad, los nodos A y B de una red de datos están unidos por dos enlaces decapacidades respectivas C1 y C2, con C1 > C2.

A Bλ

Enlace-1

Enlace-2

El nodo A enruta los paquetes, de longitud exponencial de media L bits, por el enlace de mayorcapacidad hasta que λ alcanza cierto umbral u paq/seg. El enlace-2 se empieza a utilizar cuando eltiempo de transferencia (espera + transmisión) por el enlace-1 iguala al tiempo de transmisión de unpaquete por el enlace-2, lo cual determina el valor de u. Cuando λ > u, A distribuye aleatoriamente lospaquetes que sobrepasan el umbral de forma proporcional a la capacidad de los enlaces.

Teniendo en cuenta que

- C1 = 64 Kbps- C2 = 32 Kbps- L = 100 bits

a) Calcule ub) Calcule λ1 y λ2 cuando λ = 2uc) Compare estos resultados con los valores óptimos (mínimo tiempo de transferencia)

Solución

a)

b)

22

11 ,

CLT

LuCLT =−

=

paq/seg320 :Despejando. 21

21=

−==

− LCCu

CL

LuCL

( ) 53332320320

21

11 =+=

+−+=

CCCuu λλ

( ) 106313200

21

22 ==

+−+=

CCCuλλ


c) El umbral óptimo de flujo es

−

1

21 1

CCC , en lugar de

−

1

21 1

CCC . Es decir, 187 paq/seg. El

reparto del exceso se hace proporcionalmente a las raíces cuadradas de las capacidades respectivas, esdecir a

en lugar de proporcionalmentes a 2/3 y 1/3.

Resumiendo

u = 320 paq/seg

λ1 = 533 paq/seg

λ2 = 106 paq/seg

uóptimo = 187 paq/seg

59,0432253

179253253

320006400064000

==+

=+

41,0432179

320006400032000

==+


Problema 2.3

En la figura adjunta se han indicado las probabilidades de que los enlaces de la red estén operativos(no “caigan”).

Los fallos son independientes entre sí. Encontrar, usando el algoritmo de Dijkstra con los costesapropiados, la ruta de máxima fiabilidad entre los nodos A y B.

Solución

Si la ruta R es la concatenación de los enlaces l1, l2, l3, ... se tiene

Tomando ln

⇑debe maximizarse

Equivalentemente

⇑1 – p (fallo en enlace li)

⇑pi

Así, el problema queda en la forma estándar

( ) ( )∏=i

ilpRp enlaceen fallo no rutaen fallo no

( ) ( )∑=i

ilpRp enlaceen fallo noln rutaen fallo noln

( )∑−i

ilpMIN enlace en fallo noln

∑i

icMIN

��

��

E

A

C D

F

G

B

0.97

0.97

0.97

0.96

0.99

0.99

0.99

0.99

0.99 0.98

0.98 0.95 0.94


Donde

Usualmente ,11 ≈− ip con lo que

A este último resultado se puede también llegar escribiendo

y despreciando términos de orden superior

Por ello, la ruta de máxima fiabilidad minimiza la suma

como se dijo.

Los costes quedan así

Tal como se vio en un problema anterior, el algoritmo estándar de Dijkstra proporciona la rutasiguiente

Ruta: A C E D G B

)1(ln ii pc −−=

( ) iii ppc ≅−−= 1ln

( ) ( ) ( ) ( ) =−−−= K321 111 rutaen fallo no pppRp

( ) ( )KK ++++++−= 31213211 ppppppp

( ) ( )K+++−= 3211 rutaen fallo no pppRp

∑i

ip

��

��

E

A

C D

F

G

B

0.03

0.03

0.03

0.04

0.01

0.01

0.01

0.01

0.01 0.02

0.02 0.05 0.06


Problema 2.4

Los nodos A y B están unidos por tres enlaces de capacidades respectivas C1 = 64 Kbps, C2 = 32 Kbpsy C3 = 16 Kbps.

El nodo A encamina los paquetes para minimizar el retrozo medio. Se pide:a) A partir de qué valor del flujo f se bifurca el tráfico por C2.b) Idem para C3.

Solución

a) Como C1 > C’2 = C2 + C3, se pueden usar las fórmulas correspondientes a dos canales.

b) Cuando f > u = 8,6 Kbps, parte del tráfico f’2 < f se bifurca por C’2 = C2 + C3. El nodo A no necesitarecurrir a C3 hasta que

Dado que

Se tiene

Despejandof = 28,86 Kbps

ResumiendoPrimer umbral = 8,6 Kbps

Segundo umbral = 28,86 Kbps

( ) KbpsCCCu 6,816326464'211 =+−=−=

KbpsCCCf 4,9163232322'

2 =−−=−>

−−

+= '

211'21

'2'

2 CCCfCC

Cf

( )( )[ ]16326464163264

16324,9 +−−−

++

+= f

A BC2

C3

C1

ƒbps


Problema 2.5

En la figura se muestra una red de conmutación de paquetes formada por 6 nodos. La capacidad entrela estación origen i y la estación destino j queda determinada por el elemento Cij de la matriz decapacidades.

Asimismo el coste de transmisión de un paquete entre nodos adyacentes vale

Esta red utiliza un algoritmo de encaminamiento múltiple, para lo cual cada nodo i debe calcular laprobabilidad con la que transmitirá un paquete por el enlace que conduce al nodo j. Dicha probabilidades inversamente proporcional al coste de dicho enlace. Los buffers donde se almacenan los paquetesantes de ser transmitidos por el enlace de salida pueden suponerse infinitos.

a) ¿Cuál es el camino de coste mínimo para un paquete procedente del terminal B dirigido al terminalF?b) ¿Cuál es la probabilidad de que un paquete originado en B elija dicho camino?c) Si los terminales A, B, C, D, E generan paquetes destinados a F según un proceso de Poisson conuna tasa de λi = 0,5 paquetes por segundo, ¿cuál es la tasa de dichos paquetes que circula por el enlaceque va desde el nodo 4 hasta el nodo 6?d) Calcule el retardo medio que sufre un paquete en el nodo 5 si la longitud de los paquetes estádistribuida exponencialmente con media L = 75 bytes.

ijij C

d 3600=

bps

12001800900

360036007201200

90018003600

−−−−−−−−−−−

−−−−−−−−

−−−−−−−

=C

3

1

2 4

5

6

A

B

C D E

F


e) ¿Cuál es el número medio de paquetes en cola en el nodo 5 procedentes del nodo C?f) ¿Cuáles de los enlaces de salida de un nodo genérico son utilizados durante la mayor parte deltiempo, los de mayor o los de menor capacidad?

Solución

a) Se calculan los costes para cada enlace

Se busca el camino de coste mínimo con el algoritmo de Dijkstra. Tomando 1 como nodo origen seestudian sus nodos adyacentes.

El mínimo es para el enlace que conduce a 2. Se marca dicho nodo y se estudian sus nodos adyacentesno marcados.

3

1

2 4

5

6

3 2

1

4 1 2

1

4

5

3

��

3

1

2

2

1

4 4

��

��

3

1

2

2

1

4 4

6

4

1+5

1+3


Se marca el nodo 3.

Las rutas que conducen a 4 y no pasan por 3 son más costosas, por lo cual se descartan. Se marca elnodo 5 (también se podría marcar el 4).

Se marca el 4 y se descarta llegar a 6 a través de 5. Como 5 ya está marcado, no lo indicamos comonodo adyacente a 4.

Se descarta llegar a 6 a través de 2.

��

��

��

3

1

2

2

1

4 4

6

4

1+5

1+3

4

5

2+1

2+1

��

��

��

3

1

2

2

1

6 1+5

4

��5

2+1

2+1 6 2+1+3

��

��

��

3

1

2

2

1

6 1+5

��4

��5

2+1

2+1

6 2+1+2


Finalmente se obtiene

La ruta de menor coste desde 1 hasta 6 es

1 → 3 → 4 → 6

Con un coste igual a 2+1+2 = 5.

b) Las probabilidades de encaminamiento para cada enlace son

La probabilidad de que un paquete originado en 1 y destinado a 6 elija el camino más corto es laprobabilidad de que cada nodo (1, 3 y 4) lo haya encaminado por el enlace adecuado. Como lasdecisiones de encaminamiento son independientes,

c) Se calcula la tasa que circula por cada enlace

095,0212

32

21

72

==⋅⋅=p

3

1

2

2

1

4

5

2+1

2+1

6 2+1+2

3

1

2 4

5

6

1 2/7

4/7

1/3 1/2

2/3

1/2

1/7

3/8

5/8


Siendo las tasas de llegada a cada nodo

Obsérvese que la tasa de llegada al nodo 6 es la tasa generada por las estaciones A, B, C, D y E.

La tasa que circula por el enlace que va desde 4 hasta 6 es

d) El teorema de Burke garantiza que a la salida de un sistema M/M/1 se obtiene un proceso dePoisson cuya tasa es igual a la tasa de entrada.

Cada enlace se comporta como un sistema M/M/1.

paq/seg5,01 == iλλ

paq/seg78,07

1174

12 ==+= ii λλλλ

paq/seg64,079

72

13 ==+= ii λλλλ

paq/seg88,05699

21

71

85

3124 ==++= iλλλλλ

paq/seg61,156181

31

212 435 ==++= ii λλλλλ

paq/seg5,2532

83

5426 ==++= iλλλλλ

paq/seg59,02833

32

4 == iλλ

3

1

2 4

5

6

A

B

C D E

F

λi

2/7λ1 1/2λ3

λi λi λi

Sλi

λi 3/8λ1

5/8λ2 4/7λ1

1/7λ1 1/2λ3

λ5

1/3λ4

2/3λ4


Para el nodo 5

e) El tiempo de espera en cola de un paquete genérico

La tasa de llegada al nodo 5 procedente de la estación C vale

Aplicando Little

f) Todos los enlaces de salida son utilizados por igual, ya que todos ellos tienen el mismo factor deutilización. Para un nodo genérico con tasa de entrada λ, la tasa encaminada hacia el enlace i esproporcional a la capacidad de dicho enlace.

El factor de utilización de dicho enlace es el mismo que para el resto de enlaces.

seg6,2556

=−

=LC

LTλ

seg1,256

=−=CLTW

segpaqiiiC /31

32

61

21 ==+= λλλλ

paquetesWN CC 65,0== λ

λλλ iii Ckp ==

LkC

L

i

ii λ

λρ ==

3

4

5

C

1/2λi λi

1/2λi 1/3·1/2λi


Ejercicio 2.6

Considérese la siguiente matriz de costes o distancias:

a) Dibuje la topología de red definida por la matriz C y escriba la matriz de rutas R correspondiente.b) Partiendo de C y R, calcule y escriba las matrices resultantes en cada iteración al aplicar elalgoritmo de Floyd; muéstrense claramente los cambios que se dan en cada una de dichas iteraciones.Justifique la simetría o asimetría de las matrices C y R finales.c) Utilizando las matrices C y R resultantes de aplicar Floyd, desglose y justifique la ruta para ir delnodo 5 al nodo 2 indicando los nodos intermedios y los costes parciales de dicha ruta.d) Aplicando el algoritmo de mínimo coste de Dijkstra, dibuje únicamente el árbol de encaminamientoque se obtiene según la versión hacia adelante (forward) del algoritmo tomando como origen el nodo3.e) ¿Qué rutas y costes deberá almacenar el nodo 3 con respecto al resto de nodos de la topología?Compare y justifique el resultado con lo obtenido al aplicar el algoritmo de Floyd.

Solución

a) Se puede observar que la matriz C no es simétrica, esto es, todos los enlaces que define no sonbidireccionales y del mismo coste.

Topología de red definida

∞∞∞∞∞

∞∞∞

∞∞

=

03201

1035102

320

C

−−−−−−−

−−−−−

−−−

=⇒

∞∞∞∞∞

∞∞∞

∞∞

=

351

41531

32

03201

1035102

320

00 RC

1

2 3

5

4

2 1

5

3

1 2

1 3


b) Primera iteración

Quinta iteración y última

No hay cambios.

Ni C5 ni R5 son simétricas, como ya se observa en C0 la topología inicial no es simétrica por lo que C5no tiene por que serlo. En cuanto a R5, en general la matriz R no tiene por que ser simétrica ya queofrece información de nodo siguiente en una ruta determinada, y los nodos siguientes partiendo delorigen o del destino no tienen por que coincidir.

c) Ruta para ir del nodo 5 al nodo 2, basta recurrir a la información en C5 y R5 e ir desglosando la ruta

−−−−−

−−−−

−−−

=

∞∞∞

∞∞

∞∞

=

351

41531

32

03201

1035102

320

11

111

435 RC

−−−−−

−−−−−

=

∞∞∞

∞∞

=

35111

411531

32

0320431

10535102

320

22 1

2

10

7

RC

−−

−−

−

=

=

333

33

486

24

351111411531232

0320431

10105351027320

33 RC

−−

−−

−

=

=

335111

4331332

04320431

1021024320

44

33

44433

75

34246

RC

−−

−−

−

=

=

33335111444433313332

0437520431310424210264320

55 RC


d)

e)

Este es sólo el resultado parcial de aplicar el algoritmo de Dijkstra hacia adelante, tomando comoorigen el nodo 3 y viendo la ruta a todos los posibles destinos. Sólo se obtiene la fila 3 de C5 y R5comparando con el algoritmo de Floyd.

No obstante, para obtener toda la matriz de costes y de rutas debe terminarse el algoritmo de Dijkstratomando cada uno de los nodos como posible nodo origen.

3 4

1

5

2

72113COSTE =+++=

5 1 3

3 4 2 1 1 2

ORIGEN DESTINO

3 1 2 3 4 54 4 - 4 4

ORIGEN

DESTINOS

RUTAS

3 1 2 3 4 52 4 0 1 3

COSTES


Problema 2.7

Dada la matriz de costes C, que define la topología de interconexión de una red de 5 nodos dispuestoscomo se indica a continuación, y suponiendo que el tráfico dirigido de un nodo i a un nodo j quedaexpresado a través de la matriz [ ijγ ] :

[ ]

−−

−−

−

=

∞∞∞

∞∞∞

=

21112133112213241324

0424405250444401

410

ijC γ

a) Determínese la matriz de encaminamiento de menor coste con menor número de saltos, utilizandopara ello un algoritmo de mínimo coste.b) Calcúlese el número medio de enlaces que atraviesa un paquete en esta red. Justifíquese elresultado.

Solución

Con los datos de la matriz de coste se puede dibujar la topología de red y obtener las matrices C0 y R0para aplicar el algoritmo de Floyd.

(Las etiquetas de los enlaces se pueden tomar como se desee)

Iteración 0

−−−−−

−−−

−−−

=

∞∞∞

∞∞∞

=

432535421531

32

0424405250444401

410

00 RC

3

1 2

4

5

4

2 4

4

5

1

4

2 1

4

3 10

9

6 5 12

11

7

13

14

8

1 2

3 4

5


Aplicando el algoritmo de Floyd resulta

Iteración 5

Con ello, la matriz final de rutas también puede expresarse de la siguiente forma,

Donde D denota el camino directo.

Nota: en caso de utilizar el algoritmo de Dijkstra, se debe elegir el camino de mínimo coste y menornúmero de saltos.

b) Utilizando la matriz de tráfico, la de encaminamiento y usando las etiquetas (i) pertinentes para losenlaces, se obtiene la siguiente tabla

i λi

1, 23, 45, 67, 8

9, 1011, 1213, 14

λ1 = λ2 = γ12 + γ15 = γ21 + γ51 = 4 + 1 = 5 λ3 = λ4 = γ13 + γ14 = 2 + 3 = 5 λ5 = λ6 = γ34 + γ14 = 1 + 3 = 4 λ7 = λ8 = γ35 = 1 λ9 = λ10 = γ32 = 2 λ11 = λ12 = γ45 + γ24 = 2 + 3 = 5 λ13 = λ14 = γ25 + γ15 + γ24 = 1 + 1 + 3 = 5

Nótese que en este caso por simetría se cumple que λi = λi+1 , siendo i un número impar.

Si M es el número de enlaces y γ el tráfico total entrante, el número medio de enlaces que atraviesa unpaquete en esta red se expresa por

−−

−−

−

=

=

43225353542155312332

0424540589250444840159410

55 RC

−−

−−

−

=

DDDDDDDDDDDD

DD

R

253

523

γ

λ∑==

M

ii

n 1


γ = 2 · (10 + 6 + 2 + 2) = 40 paq/seg

35,14054

==n enlaces atravesados en media

Nótese que es inferior a 2 y superior a 1, lo cual es coherente con la tabla de encaminamiento, dondelos caminos más largos pasan por dos enlaces y el resto de rutas son directas.

( )∑=

=⋅=++++++⋅=M

ii

1

paq/seg5427255214552λ


Ejercicio 2.8

La red de la figura está formada por 4 nodos y 5 enlaces unidirecionales. En dicha red, los paquetes seencaminan de manera que realizan el mínimo número de saltos en su ruta. Cada elemento γij de lamatriz indica el tráfico (medido en paquetes/segundo) originado en el nodo i destinado al nodo j.

El coste mensual de un enlace viene dado por la expresión: iiCdte =cos , siendo 8=id pts/bps y Ci lacapacidad de dicho enlace. Además se dispone de un capital mensual para el mantenimiento de la redde 240.000 pts/mes.

Calcular:

a) Tráfico en paquetes por segundo que circula por cada enlace.b) Número medio de enlaces atravesado por un paquete cualquiera de la red.c) Coste mínimo de todos los enlaces de la red si los paquetes están distribuidos exponencialmente enlongitud con un valor medio de 500 bits.d) El incremento de la capacidad (respecto a su valor mínimo) que asignaría a cada enlace paraoptimizar el retardo medio extremo-extremo de toda la red.e) ¿Cuál sería el retardo medio de cada enlace en este caso?f) ¿Y el retardo medio extremo-extremo de toda la red?g) ¿Y el retardo medio máximo para un paquete concreto?h) El incremento de la capacidad (respecto a su valor mínimo) que asignaría a cada enlace si se aplicael criterio minimax.i) ¿Cuál sería el retardo medio de cada enlace en este caso?j) ¿Y el retardo medio extremo-extremo de toda la red?

Solución

Primero miramos cómo se encaminan los paquetes para cada par de nodos

ORIGEN-DESTINO CAMINO (enlaces por los que pasa)1 → 21 → 31 → 42 → 12 → 32 → 43 → 13 → 23 → 44 → 14 → 24 → 3

12

2, 5-3

3, 5-

5, 45-4

4, 3

2

λ1 λ2

λ4

λ3

λ5

1

3

4

−−

−−

=

110230220144

γ


A partir del encaminamiento calculamos el tráfico que circula por cada enlace.

b)

c)

d)

Para minimizar el retardo extermo-extremo de toda la red

Al ser di constante

segpaq /4121 == γλ

segpaq /51414132 =+=+= γγλ

segpaq /51224324233 =++=++= γγγλ

segpaq /51134342324 =++=++= γγγλ

segpaq /82321343224145 =+++=+++= γγγγλ

∑∑≠==

==4

1

4

1

/20

ijj

iji

segpaqγγ

enlaces35,120271 5

1

=== ∑=i

in λγ

∑ ∑= =

=⋅===5

1i

5

1imin,min,0 ptas000.108bps13500ptas/bps8iiii CdDdD

bps4000

bps2500

bps2500

bps2500

bps2000

5min,5

4min,4

3min,3

2min2,

1min,1

==

==

==

==

==

LC

LC

LC

LC

LC

λ

λ

λ

λ

λ

ptas000.132000.108000.2400 =−=−= DDD me

iii CLC ∆+= λ

∑=

=∆ 5

1jjj

ii

i

ei

d

ddDC

λ

λ

i

jj

i

i

ei d

DC λ

λ

λ22,14305

1

==∆

∑=


e)

T1 = 174,79 ms

T2 = T3 = T4 = 156,34 ms

T5 = 123, 6 ms

f)

g) Buscamos el peor caso, para ello miramos los encaminamientos que pasan por dos enlaces.

ORIGEN → DESTINO ENLACES RETARDO1 → 42 → 43 → 24 → 3

2, 53, 55, 44, 3

T2 + T5 = 280 msT3 + T5 = 280 msT5 + T4 = 280 ms

T3 + T4 = 312,68 ms

El peor caso es

Tmax, paquete = 312, 68 ms

h) Con el criterio minimax se tiene el mismo incremento para todos los enlaces.

i) También se obtiene el mismo retardo en todos los enlaces.

j)

bps45,28601 =∆C

bps08,3198432 =∆=∆=∆ CCC

bps29,40455 =∆C

ii C

LT∆

=

∑=

==5

1

ms653,2011

iii TT λ

γ

bps330085

1320005

1

=⋅

====∆

∑=

j

e

j

e

jj

i

i

ei dM

DdM

D

d

ddDC

ms51,151=∆

=i

i CLT

∑∑==

=⋅=⋅===5

1

5

1

ms54,20435,1ms51,15111

iii

iiii nTTTT λγ

λγ


Ejercicio 2.9

En la figura se muestra la topología de una red de conmutación de paquetes y la distancia física de losenlaces expresada en Km.

��

��

��1 2 3

��6 ��

��4

��5

200 200

220

220400

400400

570360 450

570

a) Utilícese el algoritmo de Floyd para encontrar las rutas que proporcionan el camino de menorlongitud entre los nodos.

Supóngase que la población asociada a cada nodo de la red viene dada por la siguiente tabla:

Nodo 1 2 3 4 5 6Población 0.5 1.5 2 2.5 1 1.5

b) Estímese el tráfico (en paquetes/segundo) entre cada par de nodos utilizando una ley proporcional ala población de ambos nodos e inversamente proporcional a la distancia física que deben recorrer lospaquetes. Utilícese un factor de proporcionalidad igual a 1000.c) Utilizando el encaminamiento obtenido en el apartado a) y el tráfico estimado en b) calcúlese eltráfico que circula por cada enlace.d) Calcúlese el número medio de enlaces que atraviesa un paquete genérico de la red.

Solución

a) Matrices iniciales

Inserción nodo 1

:= Ruta

0 2 0 4 5 6

1 0 3 4 0 6

0 2 0 4 5 0

1 2 3 0 5 0

1 0 3 4 0 6

1 2 0 0 5 0

:=Ruta

0 2 0 4 5 6

1 0 3 4 1 6

0 2 0 4 5 0

1 2 3 0 5 1

1 1 3 4 0 6

1 2 0 1 5 0

:=dist

0 200 ∞ 570 400 220

200 0 200 450 600 360

∞ 200 0 400 570 ∞

570 450 400 0 400 790

400 600 570 400 0 220

220 360 ∞ 790 220 0

:=dist

0 200 ∞ 570 400 220

200 0 200 450 ∞ 360

∞ 200 0 400 570 ∞

570 450 400 0 400 ∞

400 ∞ 570 400 0 220

220 360 ∞ ∞ 220 0


Inserción nodo 2

Inserción nodo 3

Inserción nodo 4

Inserción nodo 5

Inserción nodo 6

:=Ruta

0 2 2 4 5 6

1 0 3 4 1 6

2 2 0 4 5 2

1 2 3 0 5 1

1 1 3 4 0 6

1 2 2 1 5 0

:=dist

0 200 400 570 400 220

200 0 200 450 600 360

400 200 0 400 570 560

570 450 400 0 400 790

400 600 570 400 0 220

220 360 560 790 220 0

:= Ruta

0 2 2 4 5 6

1 0 3 4 1 6

2 2 0 4 5 2

1 2 3 0 5 1

1 1 3 4 0 6

1 2 2 1 5 0

:= dist

0 200 400 570 400 220

200 0 200 450 600 360

400 200 0 400 570 560

570 450 400 0 400 790

400 600 570 400 0 220

220 360 560 790 220 0

:= Ruta

0 2 2 4 5 6

1 0 3 4 1 6

2 2 0 4 5 2

1 2 3 0 5 1

1 1 3 4 0 6

1 2 2 1 5 0

:= dist

0 200 400 570 400 220

200 0 200 450 600 360

400 200 0 400 570 560

570 450 400 0 400 790

400 600 570 400 0 220

220 360 560 790 220 0

:=Ruta

0 2 2 4 5 6

1 0 3 4 1 6

2 2 0 4 5 2

1 2 3 0 5 5

1 1 3 4 0 6

1 2 2 5 5 0

:=dist

0 200 400 570 400 220

200 0 200 450 600 360

400 200 0 400 570 560

570 450 400 0 400 620

400 600 570 400 0 220

220 360 560 620 220 0

:=Ruta

0 2 2 4 5 6

1 0 3 4 6 6

2 2 0 4 5 2

1 2 3 0 5 5

1 6 3 4 0 6

1 2 2 5 5 0

:=dist

0 200 400 570 400 220

200 0 200 450 580 360

400 200 0 400 570 560

570 450 400 0 400 620

400 580 570 400 0 220

220 360 560 620 220 0


b) El tráfico entre el nodo i y j se estima como

Siendo Pi y Pj la población asociada al nodo i y j respectivamente la distancia dij se obtiene de lamatriz de distancias del apartado anterior.

El tráfico total que circula por la red vale

Se numeran los enlaces

2 3

6

4 5 10

1

9

11 12

1 2 3 4

17

18 14

15 13

22

19 21

7

20 6

16

5

8

Teniendo en cuenta el encaminamiento obtenido en el apartado a) se observa que en el enlace 1 circulael tráfico que va desde 1 hasta 2 y desde 1 hasta 3 ([1, 2] , [1,3]). En este caso:

Repitiendo el cálculo para el resto de enlaces se obtiene:

enlace i λ i (paq/seg) tráfico del enlace 1 6.250000000 [1, 2], [1, 3] 2 6.250000000 [2, 1], [3, 1] 3 22.85714286 [1, 3], [2, 3], [6, 3] 4 22.85714286 [3, 1], [3, 2], [3, 6] 5 12.50000000 [3, 4]

(paq/seg)1000ij

jiij d

PP=γ

:= γ

0 3.750000000 2.500000000 2.192982456 1.250000000 3.409090910

3.750000000 0 15.00000000 8.333333333 2.586206897 6.250000001

2.500000000 15.00000000 0 12.50000000 3.508771930 5.357142857

2.192982456 8.333333334 12.50000000 0 6.250000000 6.048387098

1.250000000 2.586206897 3.508771930 6.250000000 0 6.818181818

3.409090909 6.250000001 5.357142858 6.048387098 6.818181818 0

egmensajes/s5,1716

1j

6

1i

== ∑∑==

ijγγ

paq/seg25,613121 =+= γγλ


6 12.50000000 [4, 3] 7 12.29838710 [4, 5], [4, 6] 8 12.29838710 [5, 4], [6, 4] 9 15.45277581 [4, 6], [5, 2], [5, 6]10 15.45277581 [2, 5], [6, 4], [6, 5]11 3.409090909 [6, 1]12 3.409090910 [1, 6]13 1.250000000 [1, 5]14 1.250000000 [5, 1]15 2.192982456 [1, 4]16 2.192982456 [4, 1]17 14.19334976 [2, 5], [2, 6], [3, 6]18 14.19334976 [5, 2], [6, 2], [6, 3]19 8.333333333 [2, 4]20 8.333333334 [4, 2]21 3.508771930 [3, 5]22 3.508771930 [5, 3]

d) El número medio de enlaces vale

enlaces192,11 22

1

== ∑=i

in λγ


Problema 2.10

Supóngase que el coste (pesetas/mes) de los enlaces de la red del ejercicio anterior puede expresarsecomo la suma de un coste fijo y otro variable, de la siguiente manera:

COSTE (pts/mes) = 5000 + (α + β li) Ci

con α = 2,5, β = 0,0054 y li en Km.

a) Calcúlese el coste mínimo de los enlaces, si se supone que todos los mensajes tienen una longitudmedia de 300 bits.b) Si se dispone de 763.000 pesetas al mes en concepto de costes de transmisión, ¿cuál será la cantidadde dinero disponible para aumentar la capacidad de los enlaces?c) Distribúyase el dinero calculado en el apartado anterior, minimizando el retardo medio en funciónde la carga (k = 0), el retardo medio mínimo (k = 1) y según el criterio minimax (k = ∞ )d) Calcúlense los retardos por enlace y extremo a extremo para los 3 casos del apartado anteriore) ¿Cuál será el retardo medio máximo para un paquete concreto, según el criterio minimax?

Adoptando el criterio minimax y suponiendo que se permite un retardo medio máximo de 100 ms,calcúlese:

f) Porcentaje en que se puede incrementar el tráfico en la redg) Coste por megabit transmitido

Solución

a) El coste mínimo de los enlaces vale λi L. Para el enlace 1

Como la longitud del enlace es l1 = 200 Km, se obtiene

El coste mínimo del enlace 1 es

Repitiendo el cálculo para el resto de enlaces

enlace i Capacidad mínima longitud di Coste mínimo(bps) (Km) (pts/bps) (pts/mes)

1 1875.000000 200 3.5800 11712.50000 2 1875.000000 200 3.5800 11712.50000 3 6857.142858 200 3.5800 29548.57143 4 6857.142858 200 3.5800 29548.57143 5 3750.000000 400 4.6600 22475.00000 6 3750.000000 400 4.6600 22475.00000 7 3689.516130 400 4.6600 22193.14517 8 3689.516130 400 4.6600 22193.14517 9 4635.832743 220 3.6880 22096.95116

bps187511 == LC min λ

58,32000054,05,21 =⋅+=d

ptas/mes5,1172187558,3500010 =⋅+=D


10 4635.832743 220 3.6880 22096.9511611 1022.727273 220 3.6880 8771.81818312 1022.727273 220 3.6880 8771.81818313 375.0000000 400 4.6600 6747.50000014 375.0000000 400 4.6600 6747.50000015 657.8947368 570 5.5780 8669.73684216 657.8947368 570 5.5780 8669.73684217 4258.004928 360 4.4440 23922.5739018 4258.004928 360 4.4440 23922.5739019 2500.000000 450 4.9300 17325.0000020 2500.000000 450 4.9300 17325.0000021 1052.631579 570 5.5780 10871.5789522 1052.631579 570 5.5780 10871.57895

---------------TOTAL: 368668.7513

Siendo el coste mínimo de toda la red

b) el dinero excedente vale

c)

k = 0 Distribución proporcional al tráfico del enlace

k = 1 Minimizando el retardo medio extremo-extremo

k = ∞ Criterio minimax

Calculando el incremento de capacidad de cada enlace y utilizando cada uno de estos criterios, seobtiene

ptas/mes7513,36866822

100 == ∑

=iiDD

ptas/mes24,3943310 =−= DDD me

∑=

= =∆ M

jj

i

i

eki d

DC

1

0

λ

λ

∑=

= =∆ M

jjj

ii

i

eki

d

ddD

C

1

1

λ

λ

∑=

∞= =∆ M

jj

eki

d

DC

1


enlace i di (pts/bps) λi (paq/seg) ∆Ci(0) (bps) ∆Ci

(1) (bps) ∆Ci(∞)(bps)

1 3.5800 6.250000000 3366.530602 4022.731201 4020.014361 2 3.5800 6.250000000 3366.530602 4022.731201 4020.014361 3 3.5800 22.85714286 12311.88335 7692.933467 4020.014361 4 3.5800 22.85714286 12311.88335 7692.933467 4020.014361 5 4.6600 12.50000000 5172.609250 4986.370753 4020.014361 6 4.6600 12.50000000 5172.609250 4986.370753 4020.014361 7 4.6600 12.29838710 5089.180071 4945.994619 4020.014361 8 4.6600 12.29838710 5089.180071 4945.994619 4020.014361 9 3.6880 15.45277581 8079.810355 6232.041178 4020.01436110 3.6880 15.45277581 8079.810355 6232.041178 4020.01436111 3.6880 3.409090909 1782.515218 2927.159270 4020.01436112 3.6880 3.409090910 1782.515218 2927.159270 4020.01436113 4.6600 1.250000000 517.2609250 1576.828884 4020.01436114 4.6600 1.250000000 517.2609250 1576.828884 4020.01436115 5.5780 2.192982456 758.1274528 1908.977643 4020.01436116 5.5780 2.192982456 758.1274528 1908.977643 4020.01436117 4.4440 14.19334976 6158.804676 5440.990226 4020.01436118 4.4440 14.19334976 6158.804676 5440.990226 4020.01436119 4.9300 8.333333333 3259.548224 3958.297535 4020.01436120 4.9300 8.333333334 3259.548224 3958.297535 4020.01436121 5.5780 3.508771930 1213.003925 2414.686941 4020.01436122 5.5780 3.508771930 1213.003925 2414.686941 4020.014361

d) El retardo del enlace i, cuando se ha incrementado la capacidad para los distintos valores de k, vale

Para todos los enlaces se obtienen los siguientes retardos

enlace i λi (paq/seg) Ti(0) (seg) Ti

(1) (seg) Ti(∞) (seg)

1 6.250000000 .089113 .074576 .0746272 6.250000000 .089113 .074576 .0746273 22.85714286 .024367 .038997 .0746274 22.85714286 .024367 .038997 .0746275 12.50000000 .057998 .060164 .0746276 12.50000000 .057998 .060164 .0746277 12.29838710 .058949 .060655 .0746278 12.29838710 .058949 .060655 .0746279 15.45277581 .037130 .048138 .07462710 15.45277581 .037130 .048138 .07462711 3.409090909 .168302 .102488 .07462712 3.409090910 .168302 .102488 .07462713 1.250000000 .579978 .190255 .07462714 1.250000000 .579978 .190255 .07462715 2.192982456 .395712 .157152 .07462716 2.192982456 .395712 .157152 .07462717 14.19334976 .048711 .055137 .07462718 14.19334976 .048711 .055137 .07462719 8.333333333 .092037 .075790 .074627

)()(

ki

ki C

LT∆

=


20 8.333333334 .092037 .075790 .07462721 3.508771930 .247320 .124240 .07462722 3.508771930 .247320 .124240 .074627

El retardo medio extremo-extremo en toda la red vale

Para los casos k = 0 y k = ∞, se obtiene

y para k = 1

Si representamos el retardo de cada enlace i y el retardo extremo-extremo T en función de k, se obtiene

0.0

0.1

0.2

0.3

0.4

0.5

0.6

0 1 2 3 4 5 6 7 8 9 10 11

k

Retardo (seg)

1,2

3,4

5,6

7,8

9,10

11,12

13,14

15,16

17,18

19,20

21,22

T

e) Con el criterio minimax todos los enlaces tienen el mismo retardo. En estas condiciones el retardomáximo extremo-extremo viene dado por el paquete que recorre la ruta más larga. En la matriz derutas se observa que el camino más largo está formado por dos enlaces. En este caso,

Tpaquete = 2 · 74,62 ms = 149,25 ms

∑=

=22

1

)()( 1

i

kii

k TT λγ

seg08897,022

1

)()0( === ∑=

∞

ii

e

dnDLTT

seg07441,02

22

1

)1( =

= ∑

=iii

e

dD

LT λγ


f) Con el criterio minimax todos los enlaces tienen el mismo retardo. Al permitir que el retardo seamayor (100 ms), la red puede admitir más tráfico. Suponiendo que el tráfico aumentaproporcionalmente en todos los nodos

Este aumento implica un aumento de la capacidad mínima de cada enlace y del coste mínimo de la red

Como el capital disponible es fijo, el capital excedente disminuye

De’ = Dm – D0’

De manera que el incremento de la capacidad se reduce y el retardo es mayor

En este caso

Además

Despejando αα = 1,3868

El tráfico puede aumentar un 38,68%.

g) El nuevo tráfico entrante a red vale

Teniendo en cuenta que en media un paquete tiene 300 bits y que en un mes hay 2592000 segundos

γ’ = 184951,3879 Mbits/mes

Coste mensual por megabit

1;6,,1,' >== αγαγ Kjiijij

22,,1' K== iii λαλ

LC imini λα=

( )∑=

+=+=22

10 7512,2586681100005000'

iii LdD αλα

'''' 22

1

ii

ii

ei C

LTd

DC∆

==∆

∑=

bps3000'

' ==∆i

i TLC

ptas/mes294276''22

1

=⋅∆= ∑=i

iie dCD

7512,258668110000763000'' 0 α−−=−= DDD me

paq/seg85,237' == γαγ

ptas125,4'

MEGABIT POR MENSUAL COSTE ==γ

mD


Problema 2.11

En la red de la figura se especifican las distancias (en Km) de cada uno de los enlaces. Los paquetes seencaminan por el camino de menor distancia física hasta el destino. Todos los enlaces sonunidireccionales. Considere que todos los tráficos son poissonianos y que la longitud de los paquetessigue una distribución exponencial de media L = 300 bits. El tráfico dirigido de un nodo i a un nodo j,en paquetes por segundo, queda expresado a través de la matriz γij.

2 4

3 5

1

1020

2010

10 201

23

4

5

6 ( )

−−

−−

−

=

00050300000020003000

ijγ

a) Obtenga el tráfico soportado por cada enlace (respete la numeración de los enlaces en la figura), y lacapacidad mínima que se deberá asignar a cada uno de ellos.b) Obtenga el número medio de saltos de los paquetes en la red.

Suponga que se dispone de un capital de 200.000 ptas para el mantenimiento mensual de la red, y queel coste mensual de cada uno de los enlaces se obtiene a partir de la expresión:

Di = d0 + diCi = 5000 + (2.5+0.0054 li) Ci con li en Km

c) Obtenga, para los enlaces 5 y 6, la capacidad total a asignar y el retardo medio de transferenciasiguiendo el criterio de minimización del momento k-ésimo del tiempo de tránsito, para los casos k = 0y k = ∞. Razone los resultados.d) Para el caso k = ∞, obtenga:

- Las capacidades totales y los retardos medios de transferencia para todos los enlaces.- El tiempo medio de tránsito extremo a extremo.- Suponiendo que se permite un retardo medio de transferencia por enlace de 45 ms, obtenga la

nueva asignación de capacidades a los enlaces y el factor α por el que se puede escalar eltráfico de entrada.

Solución

Los tráficos entrantes sonγ15 = 3 paq/s

γ25 = 2 paq/s

γ43 = 3 paq/s

γ51 = 5 paq/s

Y la tabla de encaminamiento


1 2 3 4 512345

-3153

2-153

23-53

241-3

2415-

Con ayuda de la tabla anterior, y sabiendo que la longitud media de los paquetes es de 300 bits,construimos la tabla de tráficos y capacidad mínima por enlace.

Enlace i λi (paq/s) Ci mín (bps)123456

γ15 = 3γ15 + γ25 = 5

γ15 + γ25 + γ43 = 8γ43 + γ51 = 8γ51 = 5

0

9001500240024001500

0

b) Para obtener el número medio de saltos tenemos la relación

c) Dm = 200.000 ptas

Di = d0 + di Ci = 5.000 + (2.5 · 0.0054 li) Ci

Sabemos

Particularizamos a los casos solicitados:

k = 0

Para el cálculo del capital excedente necesitamos conocer el capital mínimo

i li di Ci, mín Di, mín123456

102020201010

2,5542,6082,6082,6082,5542,554

9001500240024001500

0

7298,68912

11259,211259,2

88315000

D0 = 52.560 ptas

23,21329

5323588531 6

1

=+++++++

== ∑=i

in λγ

( )( )∑

=

+

+

=∆ 6

1

)1(1

)1(1

j

kkjj

kkii

i

ei

d

ddD

Cλ

λ

∑=

=∆ 6

1jj

i

i

ei d

DC

λ

λ


De = Dm – D0 = 200.000 – 52.560 = 147.440 ptas

Para el enlace 5

Y para el enlace 6

Por tanto, podemos pensar en eliminar el enlace 6 y no pagar el mínimo (d0 = 5.000), que estamospagando por un enlace que no se va a utilizar (le estamos asignando capacidad cero). De esta forma, elcoste mínimo es de 5.000 ptas menos y el capital excedente de 5.000 ptas más. Así, para el enlace 5

k = 1

Primera posibilidad (manteniendo enlace 6)

Enlace 5

088,196

1

=∑=j

jj dλ

C5 = 1500 + 10809 = 12309

bpsC 9953295

554,2147440

5 ==∆

bpsCCC min 11453995315005,55 =+=∆+=

s0301,09953300

150011453300

555 ==

−=

−=

LCLTλ

0290

554,2147440

6 ==∆C

ncia transferede retardo dehablar sentido tienenoy existe no enlace El!!

0300

0

66

6,66

=∆

=

=∆+

CLT

CCC min

bps 10291295

554,2152440

5 ==∆C

bps 117911029115005 =+=C

s 0292,010291300

5 ==T

∑=

=∆ M

jjj

ii

i

ei

d

ddD

C

1

λ

λ

bps10809088,19

574,3554,2

1474405 ==∆C


Enlace 6

C6 = 0 bps

Eliminando el enlace 6

C5 = 1500 + 11176 = 12676 bps

k = ∞

Manteniendo el enlace 6

486,156

1

=∑=j

jd

Enlace 5C5 = 1500 + 9521 = 11021 bps

Enlace 6. En este caso sí se obtienen valores, ya que son iguales para todos los enlaces.

s0278,010809

3005 ==T

bps06

1

66

66 ==∆

∑=j

jj

e

d

ddDC

λ

λ

!!0

300

66 =

∆=

CLT

bps11176088,19

574,3554,2

1524405 ==∆C

s0268,011176

300

55 ==

∆=

CLT

( )enlaces los todospara idéntico9521486,15

1474406

1

6

1

====∆

∑∑== j

j

e

jj

i

i

ei

d

D

d

ddD

C

s0315,09521300

55 ==

∆=

CLT

9521952106,66 =+=∆+= CCC min

seg0315,06

6 =∆

=CLT



d) Manteniendo enlace 6

d.1) Las capacidades se incrementan por igual para todos los enlaces, y los retardos de transferenciason iguales

i Ci Ti

123456

900 + 9521 = 104211500 + 9521 = 110212400 + 9521 = 119212400 + 9521 = 119211500 + 9521 = 11021

0 + 9521 = 9521

31,5 ms31,5 ms31,5 ms31,5 ms31,5 ms31,5 ms

d.2)

d.3)

i α Ci

123456

2,962,962,962,962,962,96

900 + 6665 = 93291500 + 6665 = 111052400 + 6665 = 138692400 + 6665 = 137691500 + 6665 = 11105

0 + 6665 = 6665

bps11788932,12

152440

1

===∆

∑=

M

jj

ei

d

DC

932,125

1

=∑=j

jd

seg0254,011788

3005 ==T

bps132881178815005 =+=C

ms245,70ms5,3123,2 =⋅== iTnT

7,0045,00315,0

'' 1 ===

ie

e

TT

DD

ptas967927,0''0 =−=−= emem DDDDD

bps666595217,07,0' ≈⋅=∆⋅=∆ ii CC

96,22256066792

50006525605000696792'

00

00 ==⋅−⋅−

=−−

=dMDdMD

α



d.1)

i Ci Ti

12345

900 + 11788 = 126881500 + 11788 = 132882400 + 11788 = 141882400 + 11788 = 141881500 + 11788 = 13288

25,4 ms25,4 ms25,4 ms25,4 ms25,4 ms

d.2) ms642,56ms4,2523,21 =⋅== TnT

d.3)

i Ci (bps)12345

3,97 · 900 + 6601 = 101743,97 · 1500 + 6601 = 125563,97 · 2400 + 6601 = 161293,97 · 2400 + 6601 = 161293,97 · 1500 + 6601 = 12556

56,0045,00254,0

''

===i

i

e

e

TT

DD

11463415244056,020000056,0''0 =⋅−=−=−= emem DDDDD

66011178856,056,0 =⋅=∆=∆ ii CC

97,32256089634

500054756050005114634

==⋅−⋅−

=α


Problema 2.12

Según la red de la figura donde se especifican las capacidades (en bits por segundo) de cada uno de losenlaces y considerando que todos los tráficos de la red son poissonianos y la longitud de los paquetessigue una distribución exponencial de media L = 200 bits:

��

��1 2

��3

��4

��5

4800

4800

4800

2400 9600

24001 23

4

5 6

7 9

11

12

10

8

a) Determínese la tabla de encaminamiento (R) utilizando alguno de los algoritmos de mínimadistancia estudiados, considerando como función de coste para cada enlace i, de capacidad Ci, elsiguiente valor:

ii C

f 9600=

b) Suponiendo que el tráfico dirigido de un nodo i a un nodo j queda expresado a través de la matriz

( )γ ij =

−−

−−

−

4 3 2 14 2 3 13 2 2 12 3 2 41 1 1 4

calcúlese el número medio de enlaces que atraviesa un paquete en esta red.

c) Determínese el retardo medio que sufren los paquetes en la red (T).d) Manteniendo el mismo valor del retardo de un paquete en la red (T) y el mismo encaminamiento (R)obtenidos anteriormente, halle los valores de capacidad en los enlaces que dan lugar a un tiempo detransferencia a través de cualquier enlace constante.

Solución

3

1 2

4

5 9600

2400

4800

4800

2400

2 1

4

3

8

6 5 12

11

13

14

7


a) Tabla de encaminamiento R

Función de coste i

i Cf 9600

=

3

1 2

4

5 1

4

2

2

4

2

1

3(4)

2(2)

4(2+1=3)

5(2+4=6)

3(3+2=5)

5(3+2=5)

2 4(1)

5(4)

1(2)

3(2+4=6)

3(1+2=3)

5(1+2=3)

3

4(2)

1(4)

2(2+1=3)

5(2+2=4)

1(3+2=5)


4 3(2)

5(2)

2(1)

1(2+4=6)

1(1+2=3)

5(1+4=5)

5

4(2)

2(4)

2(2+1=3) 1(3+2=5)

3(2+2=4) 1(4+4=8)

−−

−−

−

=

44445322444144412232

R

b) Caminos

{ }{ }{ }{ }{ }{ }{ }{ } 11725

724

6723

221

117115

7114

313

112

,5,4,24,2

,3,4,21,2

,,5,4,2,1,4,2,1

3,12,1

λλλ

λλλ

λλλλλ

λλ

⇒=Π⇒=Π⇒=Π

⇒=Π⇒=Π

⇒=Π⇒=Π⇒=Π

{ }{ }{ }{ }{ }{ }{ }{ } 1145

643

842

2841

11535

534

8532

431

5,43,42,4

,1,2,4,5,4,3

4,3,2,4,3

1,3

λλλ

λλλλ

λλλ

λ

⇒=Π⇒=Π⇒=Π⇒=Π⇒=Π

⇒=Π⇒=Π

⇒=Π

{ }{ }{ }{ } 1254

61253

8252

281251

4,5,3,4,5

,2,4,5,,1,2,4,5

λλλλλ

λλλ

⇒=Π⇒=Π⇒=Π⇒=Π

5254535112

4535251511

10

9

52514241328

25242315147

5343236

3534325

314

133

5141212

1514121

γγγγλγγγγλ

λλ

γγγγγλγγγγγλ

γγγλγγγλ

γλγλ

γγγλγγγλ

+++=+++=

==

++++=++++=

++=++=

==

++=++=

Por simetría


i λi

1, 23, 45, 67, 8

9, 1011, 12

γ12 + γ14 + γ15 = 4 + 2 + 1 = 7γ13 = 3γ32 + γ34 + γ35 = 2 + 2 + 1 = 5γ14 + γ15 + γ23 + γ24 + γ25 = 2 + 1 + 2 + 3 + 1 = 90γ15 + γ25 + γ35 + γ45 = 1 + 1 + 1 + 4 = 7

γ

λ∑= i

i

n

( )∑∑≠==

=⋅=+++⋅==N

jij

ij

N

i 11

46232436102γγ

( ) 6231270953721

=⋅=+++++⋅=∑=

M

iiλ

348,14662

==n

c)

LCLTT

ii

M

i

ii

M

i

i

λγλ

γλ

−⋅=⋅= ∑∑

== 11

i λi Ci ( )msLC

LTii

i λ−=

λi L

1, 23, 45, 67, 89, 10

11, 12

735907

480024004800960024004800

58,82111,1152,6325,64

-58,82

1400600

10001800

01400

[ ]82,58764,25963,52511,111382,58746212

1

⋅+⋅+⋅+⋅+⋅⋅=⋅= ∑=

ii

i TTγλ

[ ] ms77,7172,1650231

=⋅=T

T = 71,77 ms


d)

T = n · T*

T* = retardo medio sufrido en un enlace

Criterio minimax ⇒ T* es constante

ms24,53348,1

77,71* ===

nTT

1*

*

−

=−=∆⇒∀−

=LT

LCCLC

LT iiiiii

λλ

bits42,3756*==∆

TLCi

Finalmente

i λi L ∆ Ci Ci = ∆ Ci + λi L

1, 23, 45, 67, 89, 10

11, 12

1400600

10001800

01400

375637563756375637563756

515643564756555637565156


Problema 2.13

Dada la red de la figura y las matrices de encaminamiento y de tráfico en paquetes por segundo

a) Determine el número medio de enlaces atravesados por un paquete (n)b) El coste mínimo de la red para una longitud media de los paquetes L = 1000 bits y un costeeconómico del enlace que depende de su capacidad (C) de la forma: 2000 + 0,7C unidadesmonetarias/mes con C en bps.c) Calcule el coste de la red Dm cuando se desea obtener un retardo medio en los paquetes de 100 mscon la condición de que todos los enlaces introduzcan el mismo retardo medio en un paquete.d) Para el coste hallado Dm especifique las capacidades asignadas a cada enlace.

Solución

a) Los conjuntos de nodos atravesadeos para ir de un nodo i a un nodo j son:

Π12 = {1, 2}Π13 = {1, 3}Π14 = {1, 3, 4}Π21 = {2, 1}Π23 = {2, 1, 3}Π24 = {2, 1, 3, 4}

Π31 = {3, 1}Π32 = {3, 1, 3}Π34 = {3, 4}Π41 = {4, 3, 1}Π42 = {4, 2}Π43 = {4, 3}

El tráfico soportadopor cada enlace es:

411113111

5416411

01

5113413

242314138

4132317

43416

3424145

4

423

2423212

32121

=+++=+++==++=++=

=+=+==++=++=

===

=++=++==+=+=

γγγγλγγγλ

γγλγγγλ

λγλ

γγγλγγλ

−−

−−

=

323411111332

R

3

1 2

4

3

6

1

7 2

8 5

4

−−

−−

=

411411113113

ijγ


El tráfico entrante en la red en:paq/s22== ∑

≠ jiijγγ

Finalmente, el número medio de enlaces atravesados se obtiene como:

273,122288

1

=== ∑=i

inγλ

3max =n , para Π24

b) Coste de un enlace = 2000 + 0,7 · C (bps)

L = 1000 bits/paq

d0 = 2000

idi ∀= 7,0

∑∑==

+=+=M

iii

M

iii LddMLddMD

10

100 λλ

D0 = 8·2000 + 0,7·1000·28 = 35600 unidades monetarias/mes (33600 unidades monetarias/mes sin el 4)

c) T = 100 ms

Si todos los enlaces tienen igual retardo ⇒ T* (minimax)

ms5,781,273

ms100** ===⇒⋅=

nTTTnT

Dm = D0 + De

∑=

∞==⇒=

M

jj

eie d

DLTTD

1*?

3*1* 105,78

7,071000−

= ⋅⋅⋅

=⋅⋅

== ∑ TdML

dTLD i

M

jje

De = 71337,58 unidades monetarias/mes

De = 62420,38 unidades monetarias/mes (sin el 4)

Dm = 35600 + 71337 = 107000 unidades monetarias/mes

Dm = 33600 + 62420 = 96020 unidades monetarias/mes (sin el 4)


d) Capacidad de los enlaces

*TLLCLC iiii +=∆+= λλ

bits12738*

* ==∆⇒∆

=TLC

CLT

C1 = 12738 + 4000 = 16738

C2 = 12738 + 5000 = 17738

C3 = 12738 + 1000 = 13738

C4 = 0

C5 = 12738 + 6000 = 18738

C6 = 12738 + 5000 = 17738

C7 = 12738 + 3000 = 15738

C8 = 12738 + 4000 = 16738

3 Mecanismos de control de congestión 67

3 Mecanismos de control de congestión

Problema 3.1

Un terminal contrata una tasa de entrada a un nodo de red de λ paq/s. Para contratar la admisión elnodo genera permisos a una tasa de µ = 2λ. Los permisos se almacenan en un buffer de tamaño 3 ycada paquete debe coger un permiso para ser admitido a la red.

Calcular la probabilidad de que, debido al mecanismo de control, un paquete tenga que esperar paraentrar.

Solución

La figura adjunta ilustra lo dicho en el enunciado.

El estado del sistema es (i, j). Observar que i y j no pueden ser distintos de 0 simultáneamente. Eldiagrama de estados y transiciones es

(00)

Se tiene

p (0, 2) = ρ p (0, 3)

p (0, 1) = ρ2 p (0, 3)


p (0, 0) = ρ3 p (0, 3)

p (1, 0) = ρ4 p (0, 3)

p (2, 0) = ρ5 p (0, 3)

...

de lo que se deduce

p (0, 3 ) = 1 - ρ

La probabilidad de tener que esperar para ser admitido esta dado por

()()( )()()()[]1,02,03,010,20100esperaadProbabilidpppppp++−=+++=K

Como

2==µρ

Se tiene

p (0, 3) = 1/2

p (0, 2) = 1/4

p (0, 1) = 1/8

Por lo tanto,

Probabilidad espera = 1/8


Problema 3.2

En una red se implementa el control de congestión limitando el tamaño de los buffers. ¿Cuál es laprobabilidad de pérdida si el tiempo de tránsito máximo de extremo-extremo (para los paquetes que nose pierden) es de 195 ms?

Datos adicionales:

- λ = 50 paq/s para todos los enlaces- C = 64 Kbps para todos los enlaces- Longitud media de los paquetes = 64 octetos- Los paquetes tienen distribución exponencial- Número máximo de enlaces extremo-extremo = 3

Solución

El tiempo de transferencia máximo por enlace es 195/3 = 65 msg. Si el tamaño del buffer se limita a Qpaquetes, el tiempo de espera de un paquete que no se pierde es QTs, donde Ts es el tiempo detransmisión (servicio). Así, el tiempo máximo de transferencia (espera + transmisión) por el enlace es:

(Q + 1) Ts

Por lo tanto

( )1065164000⋅=+Q

DespejandoQ + 1 = 8.125

Es decir,Q = 7

El diagrama de estados y transiciones de un sistema con capacidad para Q paquetes es

2

Asíp (1) = ρ p(0)

p (2) = ρ2 p(0)

...

p (Q+1) = ρQ+1 p(0)

de lo que se deduce


1 = p(0) (1 + ρ + ρ2 + ... + ρQ+1)

es decir

() 210+−=Qpρ

Por otra parte

PL = Probabilidad de pérdida =

21+−=Qpρρ

Como

4,064000===Cρ

substituyendo se tiene

0004,04,01409−=LP

Es decir

La tasa de pérdidas es del 0,4 por mil


Problema 3.3

Comente qué se entiende por control de congestión. Diferencias con el control de flujo.

Considérese un enlace transoceánico que utiliza como medio de transmisión fibra óptica y que une dospuntos A y B separados por 7500 Km de distancia (sin necesidad de nodos intermedios). La velocidadde propagación de una señal electromagnética en el cristal de sílice de la fibra óptica es v = (c/1,5),con c = 3·108 m/s (velocidad de propagación en el vacío).

Por dicho enlace se transfiere información utilizando el Modo de Transferencia Asíncrono (ATM). Esdecir, se transmiten paquetes (celdas) de 53 octetos de longitud. La velocidad de transmisión delenlace es de 150 Mbps.

En estas condiciones,

a) Calcule el retardo de propagación entre A y B.b) ¿Cuál es el tiempo de transmisión de una celda?c) ¿Cuál será el retardo para enviar desde A una celda (supuesta de control) y recibir otra celda derespuesta enviada desde B? Despréciese el tiempo de proceso y la posible espera en cola de los nodosA y B.d) ¿Cuántas celdas están presentes en el enlace entre los extremos A y B suponiendo una utilización uocupación total de dicho enlace?e) En función de los resultados obtenidos y teniendo en cuenta que en ATM se utiliza multiplexaciónestadística, comente y justifique qué técnica, técnicas o combinación de técnicas de control decongestión utilizaría.

Supóngase ahora un control de tráfico denominado leacky o token bucket que se usa para el control delos parámetros de uso/red en las redes basadas en ATM. El esquema es el que se muestra en la figura ysu funcionamiento puede resumirse como sigue:

“Almacén de t e s t i g o s ”Generación de t es t igosB

- Cada vez que llega una celda/paquete, si existe un testigo en el "almacén de testigos" setransmite una celda hacia la red consumiendo un testigo (se decrementa en uno el número detestigos en el "almacén").

- Si cuando llega la celda no hay testigo disponible, ésta es descartada por el sistema (se pierde).- Los testigos se generan a velocidad constante V y se almacenan en el "almacén de testigos"

que posee una capacidad máxima fija de B testigos. Sólo hay incrementos en el "almacén detestigos" con tasa V mientras éste no esté completamente lleno.

Mediante este sistema se desea controlar el flujo de celdas generadas por una fuente de tráfico aráfagas. La velocidad media de la fuente es de 50000 celdas/s, el tiempo de transmisión de una celda


en el canal es de δ = 5 µs e inicialmente el "almacén de testigos" se supone que está totalmente llenocon capacidad máxima B = 4 testigos.

Se pretende controlar la velocidad media de dicha fuente y el tamaño máximo de las ráfagas de celdas(máximo número de celdas que se transmiten una a continuación de otra) que se vierten al canal.

f) Razone a qué tipo de control de tráfico (preventivo o reactivo) responde este sistema.g) ¿Cada cuánto tiempo (T) se deberá generar un testigo?h) Sabiendo que los tiempos de llegada de celdas de la fuente son 0, 5δ, 6δ, 7δ, 8δ, 9δ, 10δ, 11δ, 12δ,18δ, 19δ, 25δ. Obtenga y dibuje la secuencia de tiempos del flujo de celdas de salida del sistema. Paraello marque los tiempos en que se generan testigos, las celdas que "pasan" (cumplen) el sistema, y elnúmero de testigos en cada instante de salida de una celda.

i) ¿Qué número máximo de celdas conforman una ráfaga de salida para esta secuencia de entrada?¿Qué puede decir del valor obtenido?

Solución

Control de congestión: degradación del rendimiento de una red originado por la presencia de unvolumen excesivamente alto de tráfico (se realimenta). Se ha de asegurar que la red sea capaz detransportar el tráfico ofrecido. Es un asunto global a toda la red de transporte.

Control de flujo (adaptación de velocidades): trata de evitar el colapso del receptor (pérdida deinformación) enviándole información más rápidamente de lo que la puede procesar. Es un asuntopunto a punto entre un emisor y un receptor dados.

a)

m / s511038

b)

s/celda8,2b/s101506µ≈=TxT

c)

( )ms752≈+=+TxpropvueltaidaTTT

el tiempo de transición es despreciable.


d)

celdas13392≈=TxTa

e)- Preasignación de buffers. “NO” ⇒ uso ineficiente de los recursos- Control de congestión a través de permisos: SI- Paquetes regulardores: NO- Preasignación de buffers (cierto %, no a la velocidad de pico) + a través de permisos: SI

SE UTILIZARÁN LAS TÉCNICAS QUE NO SEAN REACTIVAS

f) Preventivo, se actúa previamente a la entrada del flujo de celdas en el canal.

g) Para controlar la velocidad media de la fuente de tasa de generación de testigos V debe coincidircon dicha velocidad. Si V = 50000 testigos/s ⇒ T = 1/V =20 µs en generar un testigo (ya que es eltiempo que en media transcurre entre la llegada de dos celdas)

h)

i) Observando el diagrama temporal la máxima ráfaga para esta secuencia de entrada es de 5 celdas(*). Como puede apreciarse cercana al tamaño máximo del almacén de testigos B = 4, que es el queregula dicho valor.


Problema 3.4

En una red de datos se implementa el control de congestión limitando el tamaño de los buffers demodo que el tiempo de tránsito en el primer intento sea como máximo 100 ms. El número máximo deenlaces a atravesar es 4.

Cuando el paquete se pierde, el nodo origen lo retransmite al cabo de 215 ms.

Calcular el tiempo de tránsito teniendo en cuenta que el paquete puede no atravesar la red a la primera.

Datos: (los mismos para todos los enlaces)

λ = 100 paq/sg , C = 128 Kbps , L = 80 octetos

Solución

Sea TEE el tiempo de tránsito, T el de transferencia entre nodos y Q el tamaño del buffer.

Se tiene

5,0128000===Cρmsg25444====EETTT()1+=QCT( )411280001025=⇒+=QQ

La probabilidad de pérdida, PL es

0159,05,01162=−=−=+QLPρ

La probabilidad de pérdida extremo a extremo vale aproximadamente

0636,00159,044=⋅=≈LLPP

El tiempo de tránsito, teniendo en cuenta las retransmisiones, se puede calcular con ayuda de lasiguiente figura (p = PL

(EE))


100 + p(1-p) 215 + p2 (1-p) 2·215 + p2 (1-p) 3 · 215 + ... = 115 msg

4 Dimensionado y evaluación de dispositivos y redes 77

4 Dimensionado y evaluación de dispositivos y redes

Problema 4.1

La tasa de llegadas a la cola del servicio telefónico de información de un ayuntamiento decrece enfunción del número de personas (llamadas) que hay esperando para ser servidas (incluyendo la que sesirve). Suponiendo que dicha tasa evoluciona de la siguiente manera:

λ0 = 5 llamadas por segundo, λ1 = (5/2), λ2 = (5/3), λ3 = (5/4),...

y que en dicho servicio se atienden 2 consultas cada 3 segundos, calcúlese:

a) Número medio de llamadas en el sistemab) Tiempo medio de espera en el sistemaNota. Supóngase una distribución exponencial tanto para el régimen de llegadas como para lostiempos de servicio.

Solución

Se trata de un sistema de colas de llegada con abandono, es decir, las llegadas se “desaniman”conforme más y más clientes están en el sistema.

Para modelar este efecto, las tasas de nacimiento y muerte son de la forma:

En este caso, λ0 = α = 5 llamadas/s. Ello implica que el desánimo o abandono es armónico conrespecto al número de elementos en el sistema.

Diagrama de estados

0

α

µ 1

α/2

µ

2 k+1 k-1

α/k

µ

k

α/(k+1)

µ

01

≥+

= kkkαλ

1≥= kk µµ


Resolviendo, se obtienen las probabilidades de estado

a) Calculando la media de esta distribución de Poisson, el número medio de llamadas en el sistema es

donde α = 5 llamadas/s

Un sólo servicio telefónico → un sólo servidor → una única tasa de servicio.

Del enunciado

b) Aplicando la fórmula de Little, se obtendrá el tiempo medio en el sistema T

Para ello se requiere calcular la λ, pero para colas infinitas de servidor único, el factor de utilización es

Además

!kµαpp

k

k1

0

=

) dergodicida (condición;!

11

1

10 ∞<=

+=

−−

∞

=∑ µ

αµα µ

αe

kp

k

k

Poisson) deón distribuci una deexpresión la a (responde...,2,1,0!

=

=−

kek

p

k

kµ

αµα

µα

=N

llamadas/s32

=µ

llamadas5,7=N

µα

ρ−

−=−= ep 11 0

µλλρ == X·

−==

− µα

µρµλ e1·

s256,1112

=

−

=− µ

αµ

α

eT

TN λ=


Problema 4.2

Al equipo de ingeniería de telecomunicación de la empresa EVALTEL se le ha encargado evaluar tresconfiguraciones distintas para un nodo de una red de conmutación de paquetes.

La primera consiste en suponer que dicho nodo puede modelarse como un sistema M/M/1 con unacola para almacenar paquetes y un servidor muy rápido, y por tanto caro, que se encarga de transmitirlos paquetes por un canal de salida de capacidad 20 Mbps. Los paquetes llegan al sistema con una tasaλ = 10 paquetes/segundo y la longitud media de los mismos es de 1000 bits.

Las dos alternativas de diseño a la primera opción (más cara) constan de 10 dispositivos, cada uno delos cuales puede también modelarse como un sistema M/M/1 con su correspondiente cola y servidor,pero de capacidad 10 veces menor. Las configuraciones son las siguientes:

- 10 sistemas M/M/1 de capacidad 2 Mbps a cada uno de los cuales le llegan paquetes delongitud media 1000 bits a una tasa de λ/10 = 1 paquete/segundo.

- 10 sistemas M/M/1 de capacidad 2 Mbps, pero donde los paquetes que llegan a una tasa λ de10 paquetes/segundo y tienen longitud media de 1000 bits se dividen antes en 10 partesiguales y se envía una parte a cada uno de los 10 dispositivos.

Calcúlese, para cada una de las tres configuraciones anteriores:

a) Tiempo medio de serviciob) Factor de utilizaciónc) Tiempo medio de espera en colad) Número medio de unidades en cola

En función de los resultados anteriores, justifique cada una de las configuraciones y decídase por unade ellas.

Solución

Configuración A

a)

b)

paq/s10=λ paq/s102Mbps20 4⋅==⇒=LCC µ

b/paq1000=L

s5010211

4 µµ

=⋅

==X

4105 −⋅=⋅= Xλρ


c)

d)

Configuración B

2Mbps

2Mbps

λ/10

λ/10

λ

10 subsistemas

a)

b)

c)

d)

Configuración C

2Mbps

2Mbps

λi=λ

λ

10 subsistemasL’

L

L’λi=λ

a)

b)

s105,21

8−⋅=−

=ρ

µρ

W

paq105,2 7−⋅=⋅= WN λ

mayor) veces(10s105 4−⋅=X

410510

−⋅=⋅=⋅= XXiiλλρ

mayor) veces(10 s105,21

7−⋅=−

=i

ii

Wρµ

ρ

paq105,2 7−⋅=⋅= WN ic λ

b/segmento100' =L

s50 µ=X

4105 −⋅=iρ


c)

d)

Se obtienen los mismos valores que en la configuración A, por tanto, ésta es la mejor opción.

Consideraciones

- En los tres casos se trabaja en baja carga, con lo que XT ≈ . Casi no hay espera en cola y

cN es muy pequeño.- En la configuración B el tiempo de espera en cola es mayor, ya que se sirven peticiones de

forma más lenta, mientras que el resto de servidores están desocupados.- En la configuración C se resuelve el problema, ya que se reparte el trabajo (por pequeña que

sea la carga) entre los 10 enlaces obteniéndose los mismos valores que en A.

s105,2 8−⋅=W

paq105,2 7−⋅=N


Problema 4.3

Se desea diseñar una red de área local para una empresa. Se ha decidido ya la topología y el tipo dered. Básicamente constará de un servidor de ficheros y una serie de terminales desde los que losusuarios pueden acceder a la información instalada en el servidor. Uno de los problemas aún porresolver es el de las licencias de uso, es decir, qué número máximo de usuarios simultáneos (N)pueden estar conectados al servidor. Está claro que, cuanto mayor sea el número de licencias de uso,mayor será el coste de la red.

Supóngase que el servicio de los usuarios conectados se hace a través del uso compartido de una solaCPU muy potente, de forma que mientras se sirve un usuario el resto de usuarios conectados al sevidoresperan en una cola.

Las peticiones desde el total de terminales, supuesto infinito, están distribuidas según un proceso dePoisson de tasa λ paq/s, y los tiempos de servicio se asumen exponenciales con tasa µ paq/s.

a) Proponga un modelo markoviano para el sistema descrito; para ello siga el proceso siguiente: definael estado del sistema, determine el número de estados posible, dibuje el diagrama de transición entreestados y dé una posible descripción del sistema mediante la notación de Kendall.

b) Halle la probabilidad pk de dicho sistema en régimen permanente, siendo k el estado del sistema.Discuta la estabilidad del sistema.

c) Para el caso extremo en que el número máximo de usuarios que pueden conectarse al servidor sea 1(N=1), calcúlese el tiempo medio de permanencia en el sistema. Justifique el resultado.

d) Definiendo el parámetro ρ = λ/µ = 0,5 y suponiendo N»1, calcúlese el número mínimo de licenciasnecesarias para garantizar una probabilidad de bloqueo inferior a 10-6.

Solución

Se supone que cada usuario está conectado a través de un terminal y que genera una única petición. Sesigue una disciplina FIFO.

a) Estado: número de usuarios (clientes) en el servidorNúmero de estados: finito N+1Kendall M/M/1/NDiagrama de estados

0

λ

µ 1

λ

µ 2

λ

N-1

λ

µ µ

λ

µ

N 3

λ

µ b)

≥<

=NkNk

k 0λ

λ


Para µλρρ

µλ

=⋅=

=≤ donde00

kk

k pppNk

Para 0=> kpNk

Sumatorio finito, el sistema es siempre ergódico

Finalmente

c) Sólo dos estados k = 0 y k = N = 1

número medio de elementos en el sistema

también

Por tanto

µ1

=T tiempo medio de servicio. Intuitivamente, si N = 1, el sistema es únicamente el servidor, luego

el tiempo medio de permanencia en el sistema coincide con el tiempo medio de servicio.

d) En estas condiciones

Nkk ,,2,1 K== µµ

111

10 1

11−+

−

=

−

−=

+= ∑ ρ

ρρNN

k

kp

Nkp kNk ≤≤⋅

−−

= + 01

11 ρ

ρρ

Nkpk >= 0

ρρ

ρ +=

+=

1;

11

10 pp

ρρ+

=⋅= ∑= 1

1

0kkpkN

CURSADA

NTλ

=

( ) ( )ρ

λλλλ+

=−=−=1

11 1ppBCURSADA

( )ρ

λµλ+

=−=1

1 0pCURSADA

( ) 6101 −<−≈==

NkB Nk

pp ρρ


Despejando N

para pB < 10-6 se obtiene que N > 19, por lo tanto son necesarias como mínimo 20 licencias.

ρρ

ρρ10

10

log1

log

1log

−

=

−

=

B

B

ppN


Problema 4.4

A un nodo de conmutación se conectan 4 terminales. Dicho nodo dispone de 3 enlaces de salida decapacidad 9600 bps cada uno. Cuando un terminal genera un mensaje, éste se transmite por cualquierenlace libre, o se guarda en un buffer a la espera que quede algún enlace libre para transmitirlo. Lalongitud de los mensajes está distribuida exponencialmente con media 960 bits. Entre el nodo y losterminales existe un protocolo, de manera que cuando un terminal genera un mensaje queda inactivo(no genera más mensajes) hasta que el nodo confirma que su mensaje ya ha sido transmitido (dichaconfirmación es inmediata). Los terminales activos generan mensajes según una distribución dePoisson con tasa λ = 2 mensajes/segundo.

a) Dibujar el diagrama de estados e indicar de qué sistema se trata mediante la notación de Kendall.b) Calcular las probabilidades para cada uno de dichos estados.c) Calcular el número medio de mensajes en el nodo.d) Calcular el tiempo medio de permanencia en el nodo.

Solución

a)

λK

µ

M/M/3/∞/4

También sería válido suponer que la cola es de tamaño uno M/M/3/4/4.

0

4λ

µ 1

3λ

2µ

2

2λ

3µ

3

λ

3µ

4

Siendo λ = 2 mensajes/segundo

b)

egundomensajes/s109609600

===LCµ

001 8,04 ppp =⋅=µλ

00

2

2 24,06 ppp =

=

µλ


Resolviendo el sistema

p0 = 0,4821

p1 = 0,385

p2 = 0,1157

p3 = 0,0154

p4 = 1,028 · 10-3

c)

d) Aplicamos Little

Es necesario calcular la tasa cursada

00

3

3 032,04 ppp =

=

µλ

00

4

4 00213,034 ppp =

=

µλ

( ) 100213,0032,024,08,010 =++++p

mensajes 66,03

1612124432

0

4

0

=

+

+

+

== ∑

= µλ

µλ

µλ

µλppkN

kk

c

NTλ

=

3

0

32

0

3

0

143314

+=

+

+

+== ∑

= µλλ

µλ

µλ

µλλλλ ppp

kkkc

egundomensajes/s 664,6=cλ

s1,0==c

NTλ


Problema 4.5

Supóngase que la red interna de una empresa dispone de un servicio de comunicación con el exteriorcontratado a una operadora. Dicho servicio consta de m líneas de transmisión alquiladas iguales. Lapoblación (usuarios de la intranet) a la que éstas dan servicio se supone infinita.

Como medida de ahorro en concepto de comunicaciones con el exterior, cuya factura puede dispararsesin control en una entidad grande, los programas de comunicación que utilizan los usuariosautomáticamente marcan los paquetes de información a transmitir que se generan en importantes y noimportantes (p. e., en función de la URL que se visita). Por motivos de eficiencia y economía de laempresa, la transferencia de un paquete importante es crucial con respecto a la transmisión de unpaquete no importante; no obstante, se permite que estos últimos progresen siempre que existanrecursos de transmisión libres con tal de mantener la utilización de los enlaces en un nivel aceptable.

En conjunto, la generación de paquetes importantes puede modelarse como un proceso de Poisson detasa λI que se ofrece a una cola de capacidad infinita donde dichos paquetes se van acumulandocuando no se encuentran líneas libres. La distribución de paquetes no importantes también se suponepoissoniana de tasa λNI , pero sólo se ofrece a las m líneas que los servirán mientras haya alguna libre;bajo ningún concepto, dichos paquetes tienen la posibilidad de ingresar en cola.

Con las salvedades expuestas anteriormente, las m líneas dan servicio a ambos tipos de paquetes y lostiempos de servicio se suponen distribuidos exponencialmente con media 1/µ.

a) ¿Cuál es la tasa de tráfico total (λT) ofrecido a las m líneas de transmisión contratadas? ¿Por qué?b) Proponga y justifique un modelo markoviano para el sistema descrito; para ello siga el procesosiguiente: defina el estado del sistema, determine el número de estados posible y dibuje el diagrama detransición entre estados. ¿Responde al diagrama de estados de un proceso de nacimiento y muerte?¿Por qué?c) Halle la probabilidad pk de dicho sistema en régimen permanente, siendo k el estado del sistema.Discuta la estabilidad del sistema.d) Obtenga la expresión de la probabilidad de que un paquete no importante encuentre todas las líneasocupadas.e) ¿Cuál es la expresión de la probabilidad de que un paquete importante tenga que esperar?f) Calcule la expresión del número medio de unidades en la cola de paquetes importantes (NQI).g) Calcule la expresión del retardo medio de acceso para un paquete importante, W1 .

Solución

Modelo

λIm líneas

(m servidores)

λTPoblación ∞

λNI


a) Preguntan sobre el tráfico ofrecido (que no cursado) λNI y λI Poisson; el proceso resultante estambién Poisson de tasa, la suma de tasas.

λI = λNI + λI

b) Estado del sistema (k): número de paquetes en el sistema (no se distingue entre importantes y noimportantes).

Número de estados posible: infinitos estados (capacidad de la cola para paquetes importantes esinfinita).

Diagrama de transición entre estados

0

λT

µ

1

λT

2µ

2

λT

m

λT

mµ 3µ

λI

mµ

m+1

λI

mµ

m+2

λI

mµ

Se trata de un proceso de nacimiento y muerte, las transiciones sólo se producen entre estados vecinos.

c) Para su resolución se emplearán las fórmulas de la solución general de equilibrio para un proceso denacimiento y muerte. En este caso las tasas:

Debemos separar la solución en dos partes, para k ≤ m y para k ≥ m. Operando resulta:

- Para k ≤ m

- Para k ≥ m

Con

≥−≤≤

=mk

mk

I

Tk λ

λλ

10

≥≤≤

=mkm

mkkk µ

µµ

1

!1

0 kpp

kT

K

=

µλ

mkIm

mkI

mT

K ppmm

pp −−

=

= ·

!1

0 µλ

µλ

1

1

00

1

1!

1!

1

−

−

=

−

+

= ∑

m

k I

mT

kT

mmk

p

µλµ

λµλ


Condición de estabilidad

d) Denotando a esa probabilidad por PB

A partir de que hay m paquetes en el sistema, un paquete no importante que llega encuentra todas laslíneas ocupadas.

e) Denotando esa probabilidad por PD, se resuelve que PD = PB

Ya que a partir de que hay m paquetes en el sistema, un paquete importante que llega debe esperar encola.

f) En general, el número medio de unidades en un sistema es

En este caso se espera (hay unidades en cola) si ya hay m paquetes en el sistema y llega un paqueteimportante (el m + 1) e ingresa en la cola correpondiente (si fuera un paquete no importante se pierde).Ello indica que se empiece a sumar desde k = m + 1. Por otra parte, se ha de eliminar los m paquetesposibles que se encuentran en el subsistema servidor. Por tanto,

g) Este es uno de los parámetros más importantes que define el grado de servicio del sistema.

Para su cálculo basta aplicar Little, siendo λI la tasa que observa la cola de paquetes importantes.

1<= II

mρ

µλ

Im

mk

mkI

mmk

k pm

ppPBρµ

λ−

=

== ∑∑

∞

=

−∞

= 11·

∑∞

=

=mk

kpkN ·

( ) I

I

I

I

IIm m

PBPBpλµ

λρ

ρρ

ρ−

=−

=−

=1

·1

1· 2

( ) ( )∑∑∞

+=

−∞

+=

=

−=−=

11

··mk

mkI

mmk

kIQ mpmkpmkN

µλ

II

IQI m

PBN

Wλµλ −

==1


Problema 4.6

Un concentrador dispone de dos canales de salida, cada uno de capacidad C, y de una cola dealmacenamiento finita con lugar para dos paquetes. A dicho concentrador llegan paquetes de dos tipos.Los de tipo 1 son paquetes de datos, los cuales si no encuentran un canal libre en el momento de sullegada se almacenan en la cola de espera, perdiéndose en el caso de que ésta esté llena. Los paquetesde tipo 2, por el contrario, son paquetes de audio. Estos paquetes, en el caso de que no encuentren uncanal libre en el momento de su llegada, no son almacenados en la cola, sino que son rechazadosdirectamente.

Tanto los paquetes de tipo 1 como los de tipo 2 son de longitud distribuida exponencialmente conmedia 2400 bits. El régimen de llegadas es exponencial para ambos, con tasas idénticas λ1 = λ2 = 2paq/s.

a) Dibuje el diagrama de transición de estados del sistema.b) Se desea que la probabilidad de que el sistema se encuentre vacío sea igual a la probabilidad de queen el sistema haya una unidad. Obtenga el valor de la capacidad C que proporciona dicha igualdad.

Con el valor de C calculado en el apartado anterior:

c) Obtenga las probabilidades de cada uno de los estados del sistema.d) Obtenga la probabilidad de pérdida de los paquetes tipo1 y de los paquetes tipo 2.e) Obtenga el retardo medio de los paquetes en el sistema.f) Calcule el número medio de paquetes de tipo 1 y de paquetes de tipo 2 en el sistema.g) Con objeto de mejorar las prestaciones ofrecidas a los paquetes de audio, se plantea la posibilidadde dotar de prioridad con expulsión a dichos paquetes. ¿Cuál es la probabilidad de pérdida en este casopara dichos paquetes?

Solución

a) Datos → λ1 paq/s = 2

Audio → λ2 paq/s = 2

Los paquetes de datos se ponen en cola, los de audio no.

0

λ1+λ2

µ 1 2 3

λ1+λ2

2µ

λ1

2µ 4

λ1

2µ

b)

021

1 ppµ

λλ +=

( )02

221

121

2 22ppp

µλλ

µλλ +

=+

=


Aplicando la condición del enunciado

c) Sustituyendo el valor de C:

p1 = p0

p2 = p0/2

p3 = p0/8

p4 = p0/32

y aplicando la condición de normalización de la probabilidad

con lo que

d)

e) Primero encontramos el número medio de unidades en el sistema

y a continuación aplicamos la relación de Little, teniendo en cuenta que la tasa media cursada es

con

( )03

2211

21

3 42ppp

µλλλ

µλ +

==

( )04

221

21

31

4 82ppp

µλλλ

µλ +

==

paq/s42101 =+=⇒= λλµpp

bps96002400·4:y === LC µ

376,0321

81

21111

1

0

4

0

=

++++=⇒=

−

=∑ ppk

k

012,0;047,0;188,0;376,0 4321 ==== pppp

012,041 == pPP

247,04322 =++= pppPP

unidades941,0·4

0

== ∑=k

kpkN

21 CCC λλλ +=

( ) paq/s976,11 111=−= PPC λλ

( ) paq/s506,11 222=−= PPC λλ


Así

con lo que

f)

g) En este caso, los paquetes de audio ven el sistema como si ellos fuesen los únicos. De este modo, elsistema para dichos paquetes se puede representar mediante el siguiente diagrama de estados:

0

λ2

µ 1 2

λ2

2µ

Recuérdese que los paquetes de audio siguen sin ser almacenados en cola cuando no hay un servidordisponible.

paq/s482,3506,1976,1 =+=Cλ

ms270482,3941,0

===C

NTλ

uds534,027,0·976,1·11 === TN Cλ

uds407,027,0·506,1·22 === TN Cλ

2/002

1 ppp ==µλ

8/22 002

22

12

2 pppp ===µ

λµ

λ

615,0182 0

000 =⇒=++ pppp

077,08615,0

80

22 ====ppPP


Problema 4.7

Las peticiones de servicio de un grupo de fuentes son multiplexadas estadísticamente sobre un únicocanal. Las fuentes son de dos tipos, N1 de tipo 1 y N2 de tipo 2, generando paquetes según sendosregímenes de Poisson con tasas λ1 y λ2 respectivamente. La longitud de los paquetes presenta unadistribución exponencial. En ningún caso las fuentes han de esperar la transmisión de sus paquetesantes de generar un paquete nuevo. La capacidad del canal de salida del multiplexor Co es asignadadinámicamente en función del número de elementos Nq en el buffer de espera, el cual puede suponersede longitud infinita, de la siguiente manera:

Zona A: Nq < L1 ⇒ Co = C bps (µo = µ)Zona B: L1 ≤ Nq < L2 ⇒ Co = 2C bps (µo = 2µ)Zona C: L2 ≤ Nq ⇒ Co = 3C bps (µo = 3µ)

a) Especifique cuál es la tasa media de llegadas al sistema λ, y dibuje el diagrama de transición deestados correspondiente al sistema cola + servidor.

b) Definiendo la constante a = λ/µ, y suponiendo a < 1, obtenga las probabilidades de los estadosdefinidos en el diagrama anterior en función de a, L1 y L2. Para ello, obtenga por separado lasprobabilidades de los estados para cada una de las zonas A, B y C en función de la probabilidad de queel sistema esté vacío p0. Finalmente, obtenga la probabilidad p0.

A partir de este momento se supondrá L1 = L2 = L. Es decir, desaparece la zona B (Co = 2C) y quedantan sólo las zonas A y C (Co = C y Co = 3C). Además, se tomarán los valores a = 0,9 y L = 2.

c) Obténganse la probabilidad PA de que el sistema se encuentre en la zona A. Repítase para laprobabilidad PC de que el sitema se encuentre en la zona C.

d) Obtenga el número medio de unidades en el sistema completo cola + servidor.

e) Sabiendo que cuando el sistema está operando en la zona C se sirven 10 paquetes por segundo,obtenga el tiempo medio de permanencia (cola + servidor) de los paquetes.

Solución

a) Diagrama de estados

λ = N1 λ1 + N2 λ2

b) Probabilidades de los estados, pk, k = 0, 1, 2 , ...

Zona A. Nq < L1 ⇒ 0 ≤ k ≤ L1

λ

µ 1

λ

µ 2

λ

µ 0

λ

µ L1

λ

2µ L1+1

λ

2µ L1-1

λ

µ

λ

2µ L2

λ

3µ L2+1

λ

3µ L2-1

λ

2µ


↑

Zona B. L1 ≤ Nq < L2 ⇒ L1 < k ≤ L2

Zona C. Nq ≥ L2 ⇒ K > L2

Finalmente queda encontrar p0

c) L1 = L2 = L

Zona A. 0 ≤ K ≤ L

Zona C. K >L

kkk

i i

ik apppp ·00

1

0 10 =

== ∏

−

= + µλ

µλ

µλ=a

kL

LkL

LkLk

Li

L

i

k

i i

ik

apaappppp

=

=

===

−−−

=

−

=

−

= +∏∏∏ 2

2222

1

1

1

11

1

1

000

11

00

1

0 10 µ

λµλ

µλ

µλ

µλ

k

LL

LLkLLL

k

Li

L

Li

L

i

k

i i

ik

apaaapppp

=

===

−

−−−

=

−

=

−

=

−

= +∏∏∏∏ 32

33232 12

2212

1

2

2

1

1

00

111

00

1

0 10 µ

λµ

λµλ

µλ

1

0 1 1

11

0 110

1 2

1 212

21

323

221

−

= +=

∞

+=−

−−

= +

∞

=

+

+=

+= ∑ ∑ ∑∏∑

L

k

L

Lk Lk

k

LL

LkLk

k

i ik

aaapµ

λ

1111

1

)2(13

23

)2(1222

11

2

12

2

21

11

−+

−

++

+

−

+−

−

+−

−=

a

a

a

aa

aa

L

LL

L

LL

LL

kk

k appp ·00 =

=

µλ

kL

LkL

kappp

=

=

−

33

3 00 µλ

µλ

11

11

110

31

331

13

31

−+

+−

∞

+==

−

+−

−=

++= ∑∑ a

a

aaaap

L

LL

Lk

kL

L

k

k


Tomando valores, L = 2, a = 0,9

Para obtener la probabilidad de C0 = C, hemos de sumar todas las probabilidades de la zona A.

NOTA. También se puede pensar que si el sistema está vacío, el canal no está transmitiendo y portanto habría que restar p0 al valor anterior.

En cuanto a la probabilidad de C0 = 3C,

d) Número medio de unidades

( ) 327,0347,071,27,0

243,01,0

271,03,01

3,039,019,01 1

1132

3

0 =+=

+=

−

+−−

= −−−

p

886,071,2·327,01

1·1

00

0 ==−

−==

+

=∑ a

apappLL

k

kA

∑∞

+=

+

−=≈==−

=

=

1

12

00 1114,0113,0347,0·327,0)3(1

)3(3

33·

LkA

LkL

C pa

apapp

=

+=

+== ∑∑∑∑∑

∞

+=

∂∂

−

=

∂∂

−∞

+==

∞

= 1

3·3

1

00

10

10

00

0 3·

33·

33··

Lk

aa

kL

L

k

aa

k

Lk

kL

L

k

k

kk

k

k

akapakappakpakpkN43421

43421

∑∑∞

+==

=

∂∂

+∂∂

=1

00

0 33

33

Lk

kL

L

k

k aa

apaa

ap

=

−∂∂

+−

−∂∂

=++

31

)3(3

11

11

0 a

a

aaa

aap

LL

L

( ) ( ) ( )( )

( )=

−

++++

−

−+−+−+

+

2

1

2

1

0)31(

31)3()31(

31)3(1

31

111a

aaaL

aaaaLap

LL

LLL

( ) ( )( )

=

−

+

+

−

+

+−

−++++−

++

++

2

11

2

11

0)31(

331

331

331

31

111a

aaLaL

aaaLaLap

LLL

LLLL


Sustituyendo valores:

e) Tiempo medio de espera en cola + servidor

( )( )

=

−

−

+

+−

++−

+

+

2

1

2

1

0)31(

33331

3111

a

aLaL

aaLaLap

LL

LLL

=

+=

−+

+−=

49,0648,0

01,0028,09,0·327,0

7,0

3,0323,0

31,0

9,0·29,0·319,0·327,0 2

32

22

32

N

unidades213,1122,4·9,0·327,0 ==

310103 =⇒= µµ

33

109,09,0 ==⇒== λµλa

ms33,4043213,1

===λNT


Problema 4.8

Los mensajes generados por una población finita de 5 fuentes se envían a un concentrador que disponede dos enlaces de salida y de un buffer con capacidad para dos mensajes. La capacidad de cada uno delos enlaces de salida es normalmente de 1200 bps. Sin embargo, cuando la cola del concentrador estállena, y sólo en éste caso, se renegocia dicha capacidad aumentándose a 3600 bps. El régimen degeneración de mensajes de cada una de las fuentes sigue un proceso de Poisson de tasa λ = 5mensajes/segundo, y la longitud de dichos mensajes sigue una distribución exponencial de media L =240 bits/mensaje.

a) ¿Qué modelo de cola utilizaría para dicho sistema? Expréselo en notación de Kendall y dibuje eldiagrama de transición de estados.b) Calcule las probabilidades de los estados en régimen permanente.c) ¿Cuál es la probabilidad de que un mensaje nuevo que llega al sistema sea rechazado? ¿Y la

probabilidad de que tenga que esperar antes de ser transmitido?d) Obtenga el retardo medio de los mensajes en el sistema.

Se plantea sustituir el sistema anterior por un concentrador sin buffer, conectado a dos enlaces decapacidades permanentes iguales a 1200 y 3600 bps. La población es la misma que en el caso anterior,y siempre que sea posible se empleará el enlace de mayor capacidad.

e) Dibújese el diagrama de transición de estados del nuevos sistema.

NOTA. En todos los casos, las solicitudes de servicio que no pueden ser atendidas lo vuelven aintentar con una demora distribuida exponencialmente y con la misma tasa λ.

Solución

a) En notación de Kendall: M/M/2/4/5

Diagrama de estados:

0

5λ

µ 1

4λ

2µ 2

3λ

3

2λ

2µ’ 2µ 4

Con mens/s5=λ

b) Del diagrama de transición de estados se obtienen las ecuaciones necesarias:

mens/s5240

1200bps1200 ===⇒=LCC µ

mens/s15240

3600''bps3600' ===⇒=LCC µ

0001 55255 pppp ===

µλ


c) Parte de la tasa ofrecida será cursada y el resto será rechazada:

λcλOF

λP

La tasa media ofrecida será:

↑ ↑

Por otra parte, en este sistema la tasa media de llegadas depende del estado en que se encuentre. Estoimplica que hemos de diferenciar entre bloqueo y pérdidas:

pk ≠ rk

↑ Probabilidad del estado k

Probabilidad del estado k cuando hay una llegada

Esto implicaPB ≠ PP↑

Bloqueo: Porcentaje de tiempo que el sistema está lleno

Pérdidas: Relación entre las llamadas perdidas y las ofrecidas

Para este caso concreto

0112 10224 pppp ===

µλ

0223 1523

23 pppp ===

µλ

0334 531

62 pppp ===

µλ

( )36151510511 1

0

4

0

=++++=⇒= −

=∑ ppk

k

432104433221100 2345 ppppppppppOF λλλλλλλλλλλ ++++=++++=

cλ pλ

139,0365

4 ≈== pPB


Calculamos λOF

y

Para la probabilidad de espera hemos de tener en cuenta los estados 2 y 3:

d) Para obtener el retardo medio obtenemos primero el número medio de unidades:

A continuación aplicamos la relación de Little, teniendo en cuenta que la tasa que realmente pasa porel sistema es la tasa media cursada.

Sabemos pcOF λλλ +=

Además

con lo que

e) 5λ

4λ 3µ

00

01

10

11

µ

µ

3µ

4λ

i = enlace a 1200 bpsj = enlace a 3600 bps

[ ] [ ] [ ][ ] 4

44444 // p

tpt

APEPEAPAEPrPP

OFOF

AA λ

λλ

λ =∆

∆====

=++++== ∑ 43210 2345 ppppppOF λλλλλλλ κκ

paq/s5,12365

3630

3630

3620

365

=

++++= λ

0556,0139,05,12

544

4 ==== ppPPOFOF λλ

λλ

325·2·

36155·3·

3610

5,121

33

22

32 =

+=+=+= pprrP

OFOFd λ

λλλ

unidades5,23690

365·4

3615·3

3610·2

365·1·

4

0

==+++== ∑=k

kpkN

cc

NTTNλ

λ =⇒=

mens/s8,1136

8536152

36103

3654

3615 ==+++== ∑ λλλλλλλ kkc p

ms2118,115,2

===c

NTλ

ij


Problema 4.9

Una población infinita genera mensajes distribuidos según un proceso de Poisson de tasa λ = 3mensajes/segundo que son enviados a un nodo de comunicación consistente en dos enlaces de salida yuna cola común con capacidad para permitir la espera de un mensaje. Ambos enlaces poseen la mismacapacidad de 4800 bps. La longitud de los mensajes se considera distribuida exponencialmente conmedia L = 1600 bits/mensaje.

a) ¿Qué modelo de cola define el sistema propuesto? Expréselo según la notación de Kendall,especifique el estado del sistema, indique su número de estados y dibuje el diagrama de transiciónentre estados. ¿Es un proceso de nacimiento y muerte?b) Calcule la tasa de servicio µ por canal y obtenga las probabilidades de los estados en régimenpermanente. ¿Qué puede decir sobre la estabilidad del sistema? Sin hacer ningún cálculo: ¿qué ocurresi λ se hace muy grande con respecto a µ? ¿Cuál sería, en este caso, el número medio de elementos enel sistema?c) Obtenga el retardo medio T que sufren los mensajes en el sistema propuesto inicialmente.d) ¿Cuál es la probabilidad de bloqueo del sistema? ¿Y la probabilidad de que un mensaje tenga queesperar antes de ser transmitido?e) Obtenga el caudal (γ) del sistema inicial tanto desde el punto de vista de la entrada como del de lasalida. Justifique su expresión y observe el resultado.f) Suponga ahora que el mismo sistema dispone de una capacidad de almacenamiento infinita. ¿Cuáles la notación de Kendall del nuevo sistema? Utilizando el proceso visto en el apartado anterior,demuestre que la expresión del factor de utilización para el nuevo sistema tiene que ser ρ = λ/2µ. Paraello calcule y utilice las nuevas probabilidades de estado en régimen estacionario. Interprete laexpresión de dicho factor.g) Utilizando la interpretación del factor de utilización realizada en el apartado anterior, ¿cómodefiniría dicho factor para el sistema inicial y cuál sería su expresión? Si las velocidades detransmisión de los enlaces fueran distintas, ¿cuál sería la nueva expresión para el factor de utilización?Justifique las respuestas.

Solución

a) Entradas Poisson M.Longitud mensajes exponencial, servicio M.Dos enlaces, 2 servidores.Capacidad cola 1, capacidad del sistema 2+1 = 3.Notación Kendall M/M/2/3Estado: número de mensajes en el sistema.Número de estados: 4

λ

µ

µ


Diagrama de transición entre estados:

0

λ

µ 1

λ

2µ 2

λ

2µ 3

Se trata de un proceso de nacimiento y muerte. La transición entre estados sólo se produce entreestados vecinos.

b)

La µ individual de un servidor, en este caso, coincide con el valor de λ.

Aplicando flujo entrante = flujo saliente o bien las ecuaciones generales en régimen permanente de unproceso de nacimiento y muerte, resulta

El sistema es siempre estable ya que

En este caso, la suma es finita y por tanto convergente.

Ello es así incluso si λ se hace muy grande, lo único que implicaría es que la probabilidad de pérdidasería enorme. Si λ → ∞ y sin hacer cálculos, el número medio de mensajes en el sistema sería .3=NEs decir, el sistema estaría siempre lleno, pero no por ello sería inestable.

c) Por Little TN SISTEMA ·λ=

Denotando λSISTEMA la tasa que observa el sistema (cursada que no ofrecida)

En este caso pB = p3 es la probabilidad de bloqueo.

Con ello,

mensaje/s3b/mensaje1600

b/s4800===

LCµ

111;

112;

114;

114

3210 ==== pppp

∏∑−

= +

∞

=

1

0 11

k

i i

i

k µλ

1·3

0

== ∑=k

kpkN

( ) ( ) λλλλλ111011· 3

2

0

=−=−== ∑=

ppp Bk

kkSISTEMA

s63,0)

=T


d) Se cumple la propiedad PASTA (Poisson Arrivals See Time Averages)

pB = p3

Probabilidad de espera: si una nueva llegada encuentra el sistema con dos unidades (ambas enservicio), entonces ésta espera

pD = p2

e) Al ser un sistema con pérdidas, el caudal (la carga que el sistema cursa) puede calcularse desde dospuntos de vista.

Punto de vista de la entrada del sistema:

Punto de vista de la salida del sistema:

Con p0, el sistema está vacío y por tanto no cursa nada.

Con p1, hay un sólo servidor usándose a tasa µ.

Con 1 – p0 – p1 hay dos servidores usándose a tasa 2µ.

Es decir, en cada momento el caudal es la tasa de servicio siempre que haya algo para servir, puedeque sea una unidad o dos unidades y deben contemplarse ambos casos.

Lógicamente, OUTIN γγ =

f) Si la capacidad de almacenamiento es ∞, el sistema viene dado por la siguiente notación de KendallM/M/2. En este caso

Si la cola es infinita, no hay pérdidas pB = 0 y, por tanto, γ IN = λ.

( ) ( ) λλλγ111011Caudal 3 =−=−=≡ ppBIN

( ) λµµγ111012 101 =−−+= pppOUT

0≥= ii λλ

>=

=12

1i

ii µ

µµ

1;2 0 ≥= kpp kk ρ

µλρ

ρρ

2con

11

0 =+−

=p

λ

λ·pB

Sistema


Sin embargo, desde el punto de vista de la salida, sigue siendo válido

Como

y si la cola es ∞, γOUT = λ, resulta

Éste es el factor de utilización para el sistema M/M/2 y puede interpretarse como la relación entre latasa efectiva a la cual llega trabajo al sistema y la tasa máxima a la que el sistema despacha esetrabajo.

g) Usando esta posible interpretación, el factor de utilización para el sistema inicial M/M/2/3 será:

Tasa cursada o efectiva: λ (1 – pB)

Tasa máxima de servicio: 2µ

Si las tasas de servicio de los servidores fueran distintas, µ1 y µ2

( )101 12 pppOUT −−+= µµγ

ρ01 2 pp =

ρρ

+−

=11

0p

µλρ

2=

( )λ

µλ

ρ115

21

=−

= Bp

( )21

1µµ

λρ

+−

= Bp


Problema 4.10

Un conjunto de S terminales, con comportamiento de población finita, se conecta a un nodo deconmutación de paquetes muy rápido, que es capaz de asignar un canal de 9600 bps de capacidad paracada paquete generado por cada uno de los terminales. El tráfico generado por cada terminal es dePoisson, con tasa α = 16 paq./s, y la longitud de los paquetes está distribuida exponencialmente conun valor medio de 300 bits.

a) Calcúlese la tasa de servicio β de un servidor cualquiera del sistema. Propóngase un modelomarkoviano para el sistema descrito; para ello siga el proceso siguiente: defina el estado del sistema,determine el número de estados posible, dibuje el diagrama de transición entre estados y dé unaposible descripción del sistema mediante la notación de Kendall.b) Halle la probabilidad pk de dicho sistema en régimen permanente, donde k se refiere a la definiciónque se ha hecho anteriormente del estado del sistema.c) Obtenga la relación entre el número medio de "paquetes" en el sistema y el número de terminales S.d) Determínese el número máximo de terminales conectados al nodo en cuestión para que la tasamedia de generación de tráfico del conjunto de terminales no supere los 64 paq/s.

Solución

a) El estado del sistema queda fijado por el número k de circuitos ocupados en un instante de tiempo.El número máximo de circuitos ocupados será S, uno por cada terminal, dado el comportamiento depoblación finita. El diagrama de estados será:

0

Sα

β 1

(S-1)α

2β 2 i

(S-(i-1))α

iβ

(S-i)α

(i+1)β

S

α

Sβ

Por tanto, el sistema será un M/M/S//S o M/M/∞//S, donde el valor de paq/s32bits/paq300

bps9600==β

b) Para un proceso general de nacimiento y muerte

paq/s16=α

bits300=L

∏−

= +

=1

00

1

k

j j

jk pp

µλ

9600bps 1

2

S


En este caso

Por lo que

Y entonces

Utilizando la relación ( ) ∑=

=+

S

i

iS xiS

x0

1

Finalmente:

Se observa que k es una variable binomial al reescribir la expresión de la forma

donde se identifica la probabilidad de éxito de la variable binomial βα

α+

=q , por lo que

c) El número medio de canales ocupados será

Recordando que k es una variable aleatoria binomial, el cálculo se simplifica a hallar el producto

( ) 1,,2,1,0con −=−= SjjSj Kαλ

Sjjj ,,2,1con K== βµ

( ) ( )00··3·2·1

11· piS

piiSSSp

ii

i

=

+−−

= β

αβ

αK

K

SS

i

i

SSSS

iS

p

++

+

+

=

+

=

∑=

βα

βα

βα

βα K

2

1

0

211

1

1

1

Sp

+

=

βα1

10

SkkS

p S

k

k ,,1,0con1

K=

+

=

βα

βα

kSk

k kS

p−

+

+

=

βαβ

βαα

( ) SkqqkS

p kSkk ,,1,0con1 K=−

= −

∑=

=ΚS

kkpk

0


La relación SΚ será

d) El valor de S máximo para que la tasa media λ no supere 64 paq/s se obtiene ponderando la tasagenerada en cada estado k por la probabilidad del estado para los S estados.

Para 6·paq/s64 =+

≤⇒=βαβαλλ maxS

Luego 6=maxS

βαα+

= ·· SqS

qS

S

S=

+=

+=

Κβα

αβαα

( ) Κ−=−=−== ∑∑∑∑====

·1····0000

αααααλλ SpkpSpkSpS

kk

S

kk

S

kk

S

kkk

( ) SSSS αβα

ααβα

ααλ

+

−=

+

−=Κ−= 1


Problema 4.11

A un nodo de una red de conmutación de paquetes llegan mensajes que deben ser retransmitidos haciaotro nodo de la misma red, con el cual está conectado a través de dos enlaces de capacidades C1 = C yC2 = 2C bits por segundo. El tráfico destinado al segundo nodo sigue un proceso de Poisson de tasa λpaquetes por segundo y la distribución del tamaño de los paquetes es exponencial de media L bits porpaquete. Por el segundo de los enlaces se enviará una fracción λ del tráfico y el resto por el primero.Cada uno de dichos enlaces está provisto de una cola cuya capacidad puede suponerse infinita.Determínese:

a) Factor de utilización de cada uno de los enlaces de salida.b) Número medio de unidades en el nodo transmisor, incluyendo las que se están sirviendo.c) Tiempo medio de permanencia en el sistema de un paquete, incluyendo el tiempo de transmisión.d) Suponiendo que la capacidad del segundo enlace C2 es igual a λL, determínese la fracción deltráfico total que debe ser encaminada por cada uno de los enlaces para minimizar el tiempo medio deestancia en el sistema de un paquete.e) Evalúense las ventajas que supondría disponer de un único enlace de capacidad C3 = 3C con unacola asociada, cuya longitud puede considerarse igualmente infinita, respecto a la distribución óptimahallada en el apartado anterior, donde C2 es igual a λ L.

Solución

λ

C1

C2

(1-α)λ

αλ

a) Se calcula ρ para cada enlace teniendo en cuenta que cada enlace se modela como una M/M/1.

Como C1 = C y C2 = 2C

b) El número de unidades en el nodo se obtiene como adición de las unidades de los dos subsistemasM/M/1 que lo componen.

Luego,

( )2

21

1 ;·1C

LC

L λαρ

λαρ =

−=

( )C

LC

L2

;121

λαρ

λαρ =

−=

2

2

1

121 11 ρ

ρρ

ρ−

+−

=+= NNN


c) Para hallar el retardo medio sufrido por un paquete en el nodo se aplica la fórmula de Little:

d) Para el caso particular, donde C2 = λ L = 2 C

Para obtener el valor mínimo se deriva la expresión anterior respecto a α y se iguala a 0, resultandoque:

Como resultado, el 70% de los paquetes circularán por el enlace rápido y el resto por el lento. Téngaseen cuenta que el enlace rápido dispondrá de una capacidad C2 y el lento ( )C22 − . Además, eneste caso, N = 3,82.

e) Si se dispone de un único enlace de capacidad 3C, el sistema M/M/1 dispondrá de un CL

3' λρ =

Luego

Por lo tanto, el sistema original es más lento que el planteado en este momento en una relación:

( )( ) LC

LLC

LNλα

λαλα

λα−

+−−

−=

211

( )( ) LC

LLC

LNTλα

αλα

αλ −

+−−

−==

211

( )( )

−

++−−

=−

+−−

−=

αα

αα

αα

αα

22211

2211

CL

CL

CCLT

22=optα

223

23'1

''2

=−

=−

=−

== CLLC

LNλλ

λρ

ρ

291,1282,3

''≈===

λ

λN

N

TT


Problema 4.12

Un centro proveedor de información (CPI) está compuesto de N servidores. Los servidores estánconectados a un enlace de una red Frame Relay mediante un multiplexor. El estudio del tráficogenerado por cada servidor ha revelado que la información entregada a la red alterna entre períodos deactividad e inactividad distribuidos exponencialmente con una duración media de 2 s y 25 srespectivamente. Durante el período de actividad cada servidor genera paquetes de longitud fija a unavelocidad (A) de 10 Kbps.

a) Determínense los valores de α y β del modelo markoviano de generación de un servidor mostradoen la figura:

0 A

ONOFF

α

β

b) Hállese la probabilidad p de que un servidor esté activo.c) Calcúlese la tasa binaria media generada por un servidor.d) Discútase por qué el tráfico conjunto de los N servidores entregado al multiplexor puede sermodelado por un proceso de generación de nacimiento y muerte:

0 A

β

2A

(Ν−1) α

2β

Να

3A

(Ν−2) α

3β

NA

α

Νβ

...

e) Determínense las probabilidades (pk) de encontrar la cadena de nacimiento y muerte en un estado (0≤ k ≤ N) en régimen permanente.f) Calcule la tasa binaria media generada por el conjunto de servidores y la capacidad mínima delenlace para que no se produzcan pérdidas de paquetes en el multiplexor.

Solución

a) Dado que el tiempo medio de actividad de un servidor es TON = 2 s y el de inactividad TOFF = 25 s ylas tasas de transición entre los estados siguen una distribución exponencial, directamente:

0 A

ONOFF

α

β

De esta manera se observa que un servidor no generará ningún bit durante su permanencia en el estadoOFF, que será de valor medio TOFF, y entregará al multiplexor una tasa de A = 10 Kbps cuando esté enel estado ON, donde en media permanecerá un tiempo TON.

2511

==OFFT

α

211

==ONT

β


b) Analizando la cadena de Markov asociada a la generación de un servidor, vemos que laprobabilidad de que un servidor esté activo será

De igual forma la probabilidad de que esté inactivo será

c) La tasa binaria media generada por un servidor λs, se obtiene ponderando las tasas generadas encada estado. Así, en el estado OFF no se generan bits, mientras que en el ON se generan A bits porsegundo. Luego,

d) Cuando se modela el tráfico generado por los N servidores debe observarse que cada servidor actúade forma independiente al resto y que el tráfico generado por el conjunto de servidores se obtiene poragregación de tráfico.

Servidor 1

Servidor 2

Servidor N

Frame Relay

Así, los casos posibles van desde el caso donde ninguno de los N servidores está activo hasta el casodonde todos los servidores están activos. Por lo tanto, las tasas generadas por el conjunto de servidoresson: 0, 1·A, 2·A, 3·A, ..., N·A. Para cada posible tasa generada se define un estado asociado. Por lotanto, la cadena de Markov del tráfico agregado será

0 A

β

2A

(Ν−1) α

2β

Να

3A

(Ν−2) α

3β

NA

α

Νβ

...

Las tasas de transición se obtienen directamente de la agregación de servidores. Por ejemplo, si todoslos servidores están inactivos la tasa generada es 0 bps y la tasa de transición al estado superior será lasuma de tasas de transición de los N servidores. Cuando uno de los N servidores se pone activo, nossituamos en el estado de generación de tasa binaria A. En este estado puede ocurrir que, o bien uno delos N-1 servidores inactivos pase a un estado de actividad, con lo que se produciría una transición alestado de generación 2A, o bien el servidor que está activo pase a inactivo, regresando al estado degeneración 0. En el primer caso la transición hacia el 2A se producirá con tasa de transición (N-1)α, yen el segundo caso la transición hacia el 0 con tasa β .

272

=+

==βα

αONpp

27251 =−=

+= ppOFF βα

β

Kbps2720··· ==+= PAPAPO ONOFFSλ


e) El análisis de esta cadena de Markov ya se hizo en el ejercicio 4.10. El resultado es una distribuciónbinomial de las probabilidades de los N+1 estados:

f) El valor medio de la tasa binaria del conjunto de servidores se obtiene como adición de los valoresmedios de cada servidor, que en este casos son idénticos:

De forma equivalente se obtiene el mismo resultado si se pondera la tasa binaria generada en cadaestado:

El valor mínimo de capacidad del enlace de salida Frame Relay, C, para que no se produzcan pérdidasserá igual a la tasa binaria conjunta generada por los servidores cuando están activos:

C = N · A

( ) NkppkN

P kNkk ,,1,01 K=−

= −

pANN S

N

iSi

···1

=== ∑=

λλλ

( )∑∑=

−

=

−

==

N

k

kNkN

kk Akpp

kN

Akp00

··1···λ


Problema 4.13

Se desea conectar cuatro sucursales de una empresa a su central a través de enlaces de 1200 bits porsegundo de capacidad. La generación de mensajes sigue un proceso de Poisson, con una tasa de 3mensajes por segundo para dos de las sucursales y de 2 mensajes por segundo para las otras dos. Laprobabilidad de la longitud de los mensajes se muestra en la figura.

OFICINA

CENTRAL

Prob

Longitud en

bits50 200 400

0.2

0.7

0.1

2

3

3

2

a) Calcúlese el mínimo número de líneas que deberá instalarse si se desea que el retardo medio de losmensajes en la cola de cada una de las fuentes sea inferior a 200 mseg. Supóngase que:

- Si una sucursal cualquiera necesita varios enlaces con la oficina central, cada uno de ellosdispondrá de su propia cola de transmisión.

- Si varias sucursales pueden compartir un mismo enlace, lo harán a través de un concentradorque debe modelarse como una única cola.

b) Una vez instalada la red anterior, el administrador decide que el tiempo medio de espera en la colapuede incrementarse hasta 400 mseg. ¿Cuántas nuevas sucursales generando mensajes a una tasa de 2por segundo podrían entonces conectarse?

Solución

a) Para una cola M/G/1

Calculemos la tasa total ofrecida.

λ = 3 + 3 + 2 + 2 = 10 mens/seg

Longitud media de los mensajes

Tiempo medio de servicio

Con lo que el tráfico queda,

( ) ( ) [ ]112

1 2

ρρ

−+

= xCxwE

bits190400·1,0200·7,050·2,0 =++=L

ms158mens/s316,61901200

=⇒== xµ

líneas 2 mínimo Como583,110158·10 3 ⇒=== −xλρ


Distribuimos

Y calculamos el factor de utilización de la línea más cargada (en este caso da igual):

Para poder aplicar la fórmula [1] debemos encontrar Cx2:

E (L2) = 0,2 · 502 + 0,7 · 2002 + 0,1 · 4002 = 44.500

Ahora ya podemos aplicar la fórmula

Tendríamos por tanto un tiempo de espera en cada una de las líneas de 365 ms, superior a los 200 msque se desean como cota máxima.

Podemos buscar directamente el factor de utilización máximo que puede soportar cada líneamanteniendo el retardo por debajo de los 200 ms.

Resolviendo 67,0max =ρ

Además x·maxmax λρ =

Con lo que, para cada línea

Por tanto, necesitaremos tres líneas, distribuyendo el tráfico de la siguiente forma:

λ1=3OficinaCentral

L1 λ=2

L2λ2=3

L3

λ3=4λ=2

Podemos comprobar el retardo para la línea que presentará peor comportamiento, L3

=+==+=

mens/s5232mens/s5231

LL

79,010·158·5 31 == −

Lρ

( )( ) ( )

( )23,02

22

2

222 =

−===

LELELE

LECC L

Lxσ

( ) ( ) ms36579,012

23,0179,0·10·158 3 =−

+= −WE

( ) ( )maxmax

3

1223,1·10·158ms200ρ

ρ−

== −WE

mens/s24,410·15867,0

3max

max ===−x

ρλ


b) Buscamos maxρ para este caso

Resolviendo 8,0max =ρ

De donde 06,510·1588,0

3max

max ===−x

ρλ

Con lo que

LÍNEA λ ofrecida Fuentes que se pueden añadir123

3 mens/s3 mens/s4 mens/s

110

TOTAL 2 fuentes

( ) ( )33

3

1223,1··10·158

LLWE

ρρ

−= −

63,010·158·4 333 === −xL λρ

( ) ms200ms165 <=WE

( ) ( )maxmax

3max 12

23,1·10·158ms400ρ

ρ−

== −NE


Problema 4.14

Un nodo de una red de conmutación de paquetes bajo estudio consta de un enlace de salida y unamemoria adicional con capacidad para almacenar 3 paquetes. Una población infinita genera paquetes auna tasa media de λ paq/s. La distribución de la longitud de los paquetes se supone exponencial y demedia L bits. La capacidad de la línea de salida es de C bps mientras el número de unidades en colasea menor o igual a un paquete. Cuando esta condición no se cumple, el nodo renegociainstantáneamente con la red la capacidad del enlace que pasa a ser de 2C bps para intentar drenar conmayor rapidez los paquetes entrantes.

NOTA: En todo el problema se supone que la tasa media de servicio correspondiente a la velocidad detransmisión C bps es igual a la tasa de llegada de paquetes y a su vez, igual a la unidad.

a) Propóngase un modelo markoviano para el sistema descrito, para ello defina el estado del sistema,determine el número de estados posible, dibuje el diagrama de transición entre estados y dé unaposible descripción del sistema mediante la notación de Kendall.b) Halle la probabilidad de los estados en régimen permanente.c) ¿Es estable el sistema? Justifique brevemente la respuesta.d) ¿Cuál es la probabilidad de que el enlace funcione a C bps? ¿Y a 2C bps?e) Se toman como medidas de las prestaciones ofrecidas por el sistema, o figuras de mérito, laprobabilidad de bloqueo y el tiempo medio de permanencia en el sistema. Calcule ambas medidas.¿Cuál es la probabilidad de pérdida de un paquete? Justifique brevemente la respuesta.f) Calcule el factor de utilización para este sistema.

Supóngase ahora que se desea actualizar el nodo de conmutación. Para ello, una de las configuracionesque se está barajando como alternativa es la siguiente: el nodo únicamente dispone de dos enlaces desalida de capacidad C y 4C bps respectivamente. Siempre que sea posible se utilizará el enlace demayor velocidad de transmisión. Con la consideración anterior para la tasa de servicio del enlace decapacidad C, calcúlese:

g) Las probabilidades de los estados en régimen permanente.h) Las figuras de mérito, probabilidad de bloqueo y tiempo medio de permanencia en el sistema.Compárese con las del modelo anterior y coméntese si mejoran con la nueva configuración.i) Calcule el factor de utilización de cada uno de los enlaces, justifique brevemente el resultado.

Solución

a)

Según la nota, λ = µ =1 paq/s (veremos que no plantea ningún problema de estabilidad)Estado: número de paquetes en el sistemaNúmero de estados: 5 (se tiene en cuenta el estado vacío)Posible notación de Kendall M/M/1/4(λ cte, L exp., 1 enlace, capacidad 4)

paq/sLC

=µ

paq/s22' µµ ==LC

λpaq/s


Diagrama de transición entre estados

0

λ

µ 1

λ

µ 2

λ

2µ 3

λ

2µ 4

b) Por simple inspección (flujo entrante = flujo saliente) o recordando que en un proceso denacimiento y muerte

Resulta

c) Se trata de un sistema con capacidad de almacenamiento limitada, el sistema es siempre ergódico ⇒suma finita de términos. Recuérdese que la solución general de un proceso de nacimiento y muerte

↑

La suma converge, el sistema es siempre estable. El problema es que pueden haber muchas pérdidas.

d)

También se acepta

e) 151

4 == ppB ; en este caso pB = pP = p4. Se cumple la propiedad PASTA. Si las llegadas són de

Poisson la probabilidad de que al llegar un paquete se pierda coincide con la probabilidad de que alllegar el sistema esté lleno ⇒ pB = pP

11

−−= kk

kk pp

µλ

151;

152;

154;

154;

154

43210 ===== ppppp

11

0 110

1

0 10 1;

−−

= +

∞

=

−

= +

+== ∏∑∏

k

i i

i

k

k

i i

ik ppp

µλ

µλ

∑=

4

1k

( )54bps 210 =++= pppCp

( )51bps2 43 =+= ppCp

158

21 =+ pp


T en el sistema

λ que ve el sistema = λCURSADA ≠ λOFRECIDA = λ

f) Se puede utilizar la definición m

x·λρ = , donde m = 1 (sólo un servidor); λ = λCURSADA; x es un

problema, ya que el tiempo medio de servicio cambia.

SERVCURSADA

SERV NNx == ρλ

;.

El nº de elementos en el servidor es 0 con probabilidad p0 y 1 con probabilidad 4321 pppp +++

ρ==−== ∑= 15

111 0

4

1. ppN

kkSERV (menor que uno)

tiempo medio de servicio sx1411

=

g)

µ = λ = 1

Diagrama de estados λ

λ

4µ 0

11

12

2

µ

µ

4µ

λ

λNT =

( )15141·

3

0

=−== ∑=

Bk

kkCURSADA pp λλλ

1522·

4

0

== ∑=k

kpkN

sT711

=

µµ 44';4 ==LCC

LCC =µ;

e.1

e.2


Por flujo entrante = flujo saliente

h) Como las llegadas son de Poisson se cumple la propiedad PASTA

Comparando con el modelo anterior, se observa que este último modelo es mejor en cuanto sus figurasde mérito son menores.

i) Interpretándolo como el número medio de elementos en el servidor, el enlace 1 tiene un elementocon probabilidad p11 y p2 análogamente para el enlace 2.

Se observa que 21 ρρ > , ya que se elige el enlace 1 con mayor probabilidad. No obstante, ladiferencia no es muy acusada, debido a que el enlace 2 se ocupa con menor probabilidad, pero durantemás tiempo por ser más lento.

201;

202;

203;

2014

212110 ==== pppp

201

2 == ppB

207·

2

0

== ∑=k

kpkN

( )20191 =−= BCURSADA pλλ

sNTCURSADA 19

7==

λ

51

2111 =+= ppρ

203

2122 =+= ppρ


Problema 4.15

Considérese el caso de dos enlaces conectando dos nodos vecinos en una red de conmutación depaquetes. Los paquetes que llegan al nodo para ser retransmitidos lo hacen según un proceso dePoisson de tasa λ = 3 paq/seg, y el tiempo de transmisión se distribuye exponencialmente conparámetros µ = 3 paq/seg y µ2 = 1 paq/seg para cada enlace. Suponiendo que el nodo dispone de unacola de almacenamiento para un paquete y que, en el caso de que los dos enlaces estén desocupados,cuando un paquete llega al nodo puede se retransmitido equiprobablemente por cualquiera de los dosenlaces:

a) ¿Qué modelo de cola representa este sistema?b) Calcúlense las probabilidades de los estados en régimen permanente.c) ¿Cuál es el número medio de mensajes en el sistema?d) ¿Cuál es la probabilididad de que el enlace 1 esté desocupado?

Solución

a) El nodo puede ser caracterizado por un sistema de almacenamiento y retransmisión que puede tenerdesde 0 elementos hasta 3 elementos. Los casos posibles son:

0 elementos → sistema vacío

1 elemento → servidor 1 o servidor 2 ocupados

2 elementos → ambos servidores ocupados y cola de almacenamiento vacía

3 elementos → servidores y cola ocupados

Puesto que los servidores no son idénticos, se debe distinguir el caso de que el servidor 1 o el 2 esténocupados cuando sólo hay un elemento en el sistema. Para ello definiremos en cada caso el estado delsistema 1a y el 1b respectivamente. Los estados del sistema quedan representados de la siguienteforma:

λ0a

λ1b µ1a

0

1a

1b

2

µ1b

µ2a λ0b

µ2b

λ1a

3

λ2

µ3

paq/s1paq/s3

paq/s3

2

1

==

=

µµλ

λ

µ1

µ2


Las transiciones entre estados quedan definidas por las conexiones definidas directamente por elcomportamiento del sistema de almacenamiento y retransmisión. Las tasas se derivan también delcomportamiento físico.

Estado 0

En este estado la tasa de llegadas al sistema es λ, como en el resto de estados. Cuando se produce unallegada con probabilidad 1/2 se realiza la transición al 1a y con probabilidad 1/2 al 1b. Esto implicaque de forma equiprobable una unidad que llega al sistema, cuando éste está vacío, será servido por unservidor, por lo tanto

Estado 1a

Este estado refleja que el sistema sólo tiene una unidad que está siendo retransmitida por el primerservidor. La tasa de servicio del sistema en este caso será únicamente la de éste servidor. Por tanto

µ1a = µ1

La tasa de llegadas en cualquier estado es λ, y en este caso el incremento de unidades del sistema sólopuede pasar a 2 unidades, por lo que

λ1a = λ

Estado 1b

De forma equivalente al estado 1b, es ahora el caso donde el sistema sólo tiene una unidad en elsegundo servidor, por lo que

µ1b = µ2

λ1b = λ

Estado 2

En este caso los dos servidores están ocupados, por lo que cualquiera puede finalizar su servicio. En elcaso de que finalice el segundo servidor, el sistema quedaría con una sola unidad en el primerservidor. Por tanto, la tasa de finalización del segundo servidor fija la tasa de transición del estado 2 a1a, con lo que:

µ2a = µ2

De forma equivalente, la finalización del servicio del primer servidor define la transición del estado 2al 1b así

µ2b = µ1

Las llegadas en este estado 2 producen una transición al estado 3, por lo que

2λλ =oa

2λλ =ob


λ2 = λ

Estado 3

En este estado el sistema está totalmente ocupado por lo que la única transición posible es hacia elestado 2. Esto ocurre cuando cualquiera de los dos servidores finaliza su servicio. Luego la tasa detransición de 3 a 2 es directamente la adición de las tasas de servicio de ambos servidores:

µ3 = µ1 + µ2

El modelo del sistema lo podríamos expresar como

M / M / 2 (µ1, µ2) / 3

b) Para hallar las probabilidades en régimen permanente planteamos las ecuaciones de balance deprobabilidades en equilibrio sobre la cadena de Markov siguiente:

λ/2

λ µ1

0

1a

1b

2

µ2

µ2 λ/2

µ1

λ

3

λ

µ1+µ2

Sustituyendo los valores numéricos y eliminando la cuarta ecuación por ser combinación lineal de lasotras, llegamos al sistema

Resolviendo se expresan las probabilidades en función de p0

( )

( )

( )( )

=−+=−−−++

=−−+

=−−+

=−−

00

02

02

0

2321

311221

21012

22011

12110

pppppp

ppp

ppp

ppp

ba

b

a

ba

λµµµλλµµλ

µλµλ

µλµλ

µµλ

=−

=−−

=−−

=−−

034

03234

0236

033

23

201

201

110

pp

ppp

ppp

ppp

b

a

ba

03010102 89;

23;

21;

23 pppppppp ba ====


Dado que la suma de probabilidades es 1 se obtiene

c) La suma ponderada de unidades en el sistema nos dará el número medio N

N = 0 · p0 + 1 · p1a + 1 · p1b + 2 · p2 + 3 · p3

N = 1,48

d) El enlace 1 está desocupado en los estados 0 y 1b. Por lo tanto

Prob [enlace 1 desocupado] = p0 + p1b = 0,44

51;

154;

154;

454;

458

32110 ===== ppppp ba


Problema 4.16

Un nodo de una red de conmutación de paquetes debe retransmitir los dos tipos siguientes por unenlace de 1 Mbps:

Tipo 1. Paquetes de control, que representan el 30 % de las llegadas, y que se reparten de la siguienteforma:

- 60 % de paquetes de longitud fija de 64 bytes- 40 % de paquetes de longitud fija de 128 bytes

Tipo 2. Paquetes de datos, que representan el 70% de las llegadas, y que se reparten de la siguienteforma:

- 30 % de paquetes de longitud fija de 1500 bytes- 70 % de paquetes de longitud media igual a 1000 bytes y distribución exponencial

Sabiendo que la capacidad de los enlaces es de 1Mbps y que el factor de utilización es ρ = 0,6, calcule:

a) Tiempo de espera en cola con servicio FIFOb) Número medio de unidades en colac) Número medio de unidades de cada tipod) Dotando de prioridad sin expulsión a los paquetes de control:

- Tiempo medio de espera en cola- Número medio de unidades de cada tipo- Retardo medio de un paquete genérico

Solución

a) Sin prioridades, aplicamos la fórmula general M/G/1

Cálculo de los momentos del tiempo de servicio

( ) ( )( ) ( ) ( )ρ

ρρ

λ−

+=

−=

121

12

22xCxExEwE

ms8,7164,06,0 12111 =+= xxx

ms51210

8·6416

1211 ===

µx

ms102410

8·12816

1212 ===

µx

ms2,97,03,0 22212 =+= xxx

ms1210

8·150016

2121 ===

µx


Para el conjunto completo de paquetes

Cálculo del segundo momento

Para el conjunto total de paquetes

E (x2 ) = 0,3 E (x12) + 0,7 E (x2

2) = 93,13 · 10-6

Para tener el retardo medio en cola nos falta calcular λ

O bien, directamente, paq/s1,9010·66,6

6,03 ===⇒=

−xx ρλλρ

Con esto

b) No hay más que aplicar la fórmula de Little

ms810

8·100016

2222 ===

µx

ms66,67,03,0 21 =+= xxx

( ) ( ) ( ) 9212

211

21 10·71,5764,06,0 −=+= xExExE

( ) 9211

211

211

211 10·14,262 −==+= xxxE σ

( ) 9212

212

212

212 10·58,1048 −==+= xxxE σ

( ) ( ) ( ) 6222

221

22 10·8,1327,03,0 −=+= xExExE

( ) 6221

221

221

221 10·144 −==+= xxxE σ

( ) 6222

222

2

22

222

222

222 10·12821 −==+

=+= xxxxE

µσ

xxx6,0

7,03,06,0

7,03,06,07,03,06,0

21

21

212

2

1

1 =+

=+

=⇒+=+==

µµ

λµ

λµ

λµλ

µλρ

( ) ( )( ) ms5,10

0,810·13,93·1,90

12

62

≈=−

=−

ρλ xEwE

( ) ( ) paq95,010·5,10·1,90 3 === −wENE λ


c)

d) Damos prioridad a los paquetes de control

Prioridad más alta

donde

Prioridad más baja

donde

e) En cuanto al número medio de unidades de cada tipo

f) Si ahora queremos calcular el retardo de un paquete genérico

E (N) = E(N1) + E(N2) = 0,788 paq

( ) ( ) ( ) ( ) paq285,03,03,011 ==== NEwEwENE λλ

( ) ( ) paq665,07,02 === NENE K

( ) ( ) ms196,42

10·13,93·1,902

62

0 ===−xEwE λ

( ) ( )ms28,4

981,010·196,4

1

3

1

01 ==

−=

−

ρwE

wE

019,010·8,716·1,90·3,03,0 6111

1

11 ===== −xx λλ

µλ

ρ

( ) ( )( ) ( ) ms66,10

401,0·981,010·196,4

11

3

211

02 ==

−−−=

−

ρρρwE

wE

58,010·2,9·1,90·7,07,0 32222 ==== −xx λλρ

( ) ( ) paq116,010·28,4·1,90·3,0 3111 ≈== −wENE λ

( ) ( ) paq672,010·66,10·1,90·7,0 3222 ≈== −wENE λ

( ) ( ) ms75,81,90

788,0===

λNEwE


Problema 4.17

Dos usuarios comparten un enlace de 10 Kbps mediante un concentrador cuyo buffer puedeconsiderarse infinito. Cada usuario genera paquetes según la tabla siguiente:

USUARIO A USUARIO BTasa de llegada 2 paq/seg 8 paq/segLongitud media de los paquetes 3700 bits 200 bitsDistribución de la longitud exponencial constante

a) ¿Cuál es el número medio de paquetes en espera si la disciplina de servicio es FIFO?Para disminuir el número de paquetes en espera se asigna prioridad a uno de los dos usuarios.b) ¿A qué usuario asignaría prioridad? En este caso, ¿cuál es el número medio de paquetes en espera?c) ¿Cuál es el número medio de paquetes que adelantarán a un paquete de baja prioridad durante suestancia en el concentrador?d) ¿Cuál es el número medio de paquetes que serán adelantados por un paquete de alta prioridadcuando éste llegue al concentrador?

Debido a una queja presentada por el usuario con menos prioridad, es necesario restablecer ladisciplina FIFO en el concentrador. Para ello se utiliza un enlace más rápido, de manera que no sesupere el número medio de paquetes en espera calculado en el apartado b).

e) ¿Cuál es el valor mínimo de capacidad que debe tener dicho enlace?

Solución

a) Aplicando Little

NQ = λ W

λ = λA + λB = 10 paq/seg

NQ = 10 · 2,754 = 27,54 paquetes

( )( )ρ

λ−

=1

12

2xEW

( ) ( ) 9,002,0·837,0·2 =+=+=+= BBAABA xExE λλρρρ

( ) ( ) ( ) ( ) ( ) =+=+= BB

AA

BBAA xExExEpxEpxE 22222 ·2λ

λλ

λ

( ) ( ) 222 s055,002,010837,02·

102

=+=

( ) s754,29,012

055,0·10=

−=W


b) Al asignar prioridades, los nuevos tiempos de espera valen

- Para el más prioritario

- Para el menos prioritario

El número medio de paquetes en espera es

Para disminuir el número de elementos en espera se deberá cumplir

Hay que asignar prioridad a los paquetes que se sirven más rápidamente, lo cual parece evidente, yaque lo que se pretende disminuir es el número medio de unidades en espera.

Asignamos prioridad al usuario B, ya que E(xB) < E(xA).

Ahora

NQPRI = NQA + N QB = 9,18 paquetes

c) Es el número medio de paquetes de alta prioridad que llegan al concentrador mientras uno de bajaestá en espera.

d) Los que encuentra cuando llega. Como las llegadas son de Poisson, aplicamos la propiedad PASTA

NQA = 6,55 paquetes

( )2

2

2 11

2 ρλ

−=

xEW

( )( ) ( )2

2

1 111

2 ρρλ

−−=

xEW

( )( ) ( ) ( ) =

−

+−−

=+=+=2

2

2

12

2211 111221 ρλ

ρρλλ

λλxEWWNNN QQQPRI

( )( ) QNxE

2

222

2

2

12 ρλλρλλ

ρλ

ρλλρλλ

−−

=−−

−=

( ) ( )212

2 1 xExE >⇒<−−

ρλλρλλ

( )( ) paq62,2

02,0·818·

2055,0·10

12

2

=−

=−

==B

BBBQ

xEWNB ρ

λλλ

( )( ) ( ) ( ) ( ) paq55,6

02,0·819,012

2055,0·10

112

2

=−−

=−−

==B

AAAQ

xEWNA ρρ

λλλ

( )( ) ( ) paq22,26

112

2

=−−

=B

BABxEW

ρρλλλ


e)

Como la longitud de los paquetes no varía

C = 11,58 Kbps

( )( )'12

''22

ρλ

−==

xENN QQPRI

( ) ( ) ( ) ( ) ρρ'

''

'''·CCxE

CCxExECxEC =⇒=⇒=

( ) ( ) ( ) ( )22

22222

'''' xE

CCxExECxEC

=⇒=

( )

−

=ρ

λ

'12

'2

22

CC

xECC

NPRIQ

−

=9,0·

'1012

055,0·'

10·1018,9

2

22

C

C

04,275'62,82'18,9 2 =−− CC


Ejercicio 4.18

Una fuente de tráfico genera mensajes a una tasa λ de 25 mensajes por segundo. El tiempo entregeneraciones puede suponerse distribuido exponencialmente. La longitud de los mensajes, expresadasen bits, repite periódicamente el siguiente patrón:

180.000 - 9.000 - 9.000 - 18.000 - 9.000 - 9.000 - 18.000 - 9.000 - 9.000

Dichos mensajes llegan a un nodo multiplexor que los retransmsite a través de un único enlace de 2Mbps. La fuente no tiene que esperar a que se sirva cada mensaje antes de generar el siguiente.Además, se puede suponer que la longitud del buffer del multiplexor es infinita. Calcule:

a) Tiempo de transferencia de los mensajes en el multiplexor y número medio de mensajes.Con objeto de reducir dicho retardo, se obliga a la fuente a promediar la longitud de los mensajes antesde enviarlos al multiplexor. Con esto, la longitud de los mensajes pasa a ser constante e igual a 30000bits.b) Repita el apartado a) teniendo en cuenta esta última modificación.c) Se desea multiplexar un número M de fuentes como las descritas anteriormente, con la condición deque el tiempo medio en el buffer del multiplexor no supere una cota determinada Tmax. Obtenga unaexpresión general para M en función de la tasa de llegadas individual λ, del tiempo medio de serviciode los mensajes, del coeficiente cuadrático de variación del tiempo de servicio CX

2 y de la cota Tmax.d) Tomando Tmax = 40 ms, obtenga M para los casos descritos en los apartados a) y b).

λ=25 mens/seg 2 MbpsF

180.000 18.000 9.000

Solución

a)

Longitud media de los mensajes

Segundo momento

( )ρρ

−+

+=12

1 2xC

xxT

bits3000090009618000

92180000

91

=++=L

( ) ( ) ( ) =++= 2222 90009618000

92180000

91LE

6668 10·372610·5410·7210·36 =++=

( ) 626222 10·28263000010·3726 =−=−= LLELσ


Tiempo medio de servicio s015,010·2

300006 ===

CLx

Factor de utilización 375,0015,0·25 === xλρ

Sustituyendo

Aplicando la relación de Little

b)

c) M fuentes

Condición

Tasa de llegadas total → Mλ

Factor de utilización → ρ = Mλ x

Por tanto

22

62 14,3

3000010·2826

XL CC ===

( )375,01214,31375,0·015,0015,0

−+

+=T

ms3403363,001863,0015,025,114,4375,0·015,0015,0 ≈=+=+=T

mensajes85,0=⇒= NTN λ

bits30000=L

00 222 ==⇒= xLL CCσ

ms200195,00045,0015,025,11375,0·015,0015,0 ≈=+=+=T

mensajes5,0=⇒= NTN λ

( ) ( ) máxX T

CxwE ≤

−+

=ρ

ρ12

1 2

( ) máx

2

121 T

xMCxMx X ≤

−+

λλ

( ) xTMTCMx X máxmáx22 221 λλ −≤+

( )[ ] máxmáx22 221 TxTCxM X ≤++ λλ


Finalmente

d) Caso a) 14,32 =XC

Caso b) 02 =XC

( ) xTCxTM

X máx22

máx

212

λλ ++≤

151,1053,008,0

03,0023,008,0

015,0·04,0·25·214,4·25·015,004,0·2

2 =→==+

=+

≤ MM

222,2036,008,0

03,025·015,008,0

2 =→==+

≤ MM


Ejercicio 4.19

La longitud de los paquetes retransmitidos por un nodo de una red de conmutación de paquetes estádistribuida uniformemente entre 2400 y 4800 bits. Dichos paquetes provienen de N estaciones, cadauna de las cuales genera en media 1 paquete cada 15 segundos, siguiendo un proceso de Poisson. Elnodo dispone de un buffer que puede suponerse infinito, y retransmite los paquetes por un únicoenlace de salida de 1200 bits por segundo.

a) Obténgase una expresión general para el percentil Π(r) del tiempo de servicio de los paquetes, yaplíquese para el cálculo del percentil 80.b) Se desea que el retardo medio máximo en el buffer del conmutador sea de 3 segundos. ¿Cuál será elnúmero máximo de estaciones, Nmax, que podemos conectar al concentrador?

Solución

a) De la distribución de la longitud de los paquetes obtenemos la distribución del tiempo de servicio

l (bits)

fl(l)

1 2400

2400 4800 x (s)

fx(x)

1 2

2 4 Π(r)

r% C=1200bps

Inmediatamente se obtiene

b) Tenemos llegadas exponenciales, tiempo de servicio distribuido uniformemente y un servidor, porlo que utilizamos la expresión de la cola M/G/1:

Debemos encontrar el coeficiente cuadrático de variación del tiempo de servicio, para lo cualnecesitamos su primer y segundo momento:

( )[ ] ( ) 21002

212

100+=⇒−= ∏∏ rrrr

( ) s6,3210016080 =+=∏

( ) ( ) s312

1 2

≤−

+=

ρρ XCxWE

( ) ( ) 3·4

2== ∫ dxxfxxE X

( ) ( ) 33,94

2

22 == ∫ dxxfxxE X


Tan sólo resta encontrar el factor de utilización

Con lo que podemos sustituir en la expresión general de la cola M/G/1 y despejar

( ) ( )( ) 037,02

222 =

−=

xExExECX

( )515

3 NNxEN === λρ

( ) ( ) s312

1 2

≤−

+=

ρρ XCxWE

( ) s3512

037,015

·3 ≤−

+N

N

329,3 máx =⇒≤ NN


Problema 4.20

Determine sobre un sistema M/M/∞

a) La función generatriz de momentos G(z)b) Empleando G(z), la probabilidad de encontrar k unidades en el sistemac) El número medio de unidades en el sistema

NOTA.

Solución

a)

0

λ

µ 1

λ

2µ 2 k-1

λ

kµ

k

λ

(k+1)µ

k+1

Ecuaciones de equilibrio

Función generatriz

Determinación de G(z)

Calculamos

Luego

( )zGzd

dzxpkk

kk =∑

∞

= 0

KK +++++=!!2!1

12

kxxxe

kx

( ) 0·1 1 ≥+= + kpkp kk µλ

( ) ∑∞

=

=0k

kk zpzG

( )∑∑∞

=+

∞

=

+=0

10

·1k

kk

k

kk zpkzp µλ

( ) ( )∑∞

=++=

011

k

kk zpkzG µλ

( ) { } ====+==+ ∑∑∑∑∞

=

−∞

=

−∞

=

−∞

=+

0

1

1

1

1

1

01 ·11

j

jj

j

jj

j

jj

k

kk zpjzzpjzzpjkjzpk

( ) ( )zGzd

dzGzd

dzz =− ··1


Solución de la ecuación diferencial ordinaria de 1r orden

Solución clásica

Se verifica que

Luego

b) Desarrollando en serie G(z)

Recordando que

Por definición

Identificando los coeficientes del polinomio en z, tenemos

Por tanto

( ) ( )zGzd

dzG µλ =

( ) ( ) 0=− zGzGzd

dµλ

( )z

eCzG

= µλ

( ) ( ) 1111

1

===⇒=

=

µλ

µλ

eCeCGG

z

z

( )( )1

·−

−

==zz

eeezG µλ

µλ

µλ

( )( ) zz

eeezG

−−

== µλ

µλ

µλ

·1

!!2!11

2

kxxxe

kk ++++= K

( )

++

+

+=−

KK!!2!1

1

22

k

zzzezG

kk

µλ

µλ

µλ

µλ

( ) ∑∞

=

=0k

kk zpzG

0!

· ≥

=−

kk

ep

k

kµ

λµ

λ


c) Número medio de unidades en el sistema ( )N

Dos maneras:

i) pk sigue una distribución de Poisson, luego

ii) Aplicando G(z)

=

=−

µλµ

λµ

λ1,,Poisson

!ke

kp

k

k

µλ

λ

µ == 1

1N

( )

11

·

=

−

=

==

z

z

z

eezd

dzdzGdN µ

λµ

λ

µλ

µλ µ

λµ

λ==

=

−

1

··

z

zeeN


Problema 4.21

Un servidor envía una secuencia de vídeo a un ordenador a través de una red de conmutación decircuitos. La transmisión de la secuencia requiere un número variable k de circuitos de capacidadconstante C = 64 Kbps durante la sesión.

Servidor Ordenador

Red de Conmutación de Circuitos

k x 64 Kbps

Considerando que:

1) El número de circuitos k varía gradualmente, de forma que si:Si k = 0, sólo se puede pasar a un valor k = 1.Si k > 0, el valor de k se incrementa en una unidad con probabilidad p y se decrementa en una unidadcon probabilidad 1 - p.2) Los intervalos entre variaciones de k están distribuidos exponencialmente con valor medio Dsegundos.3) El tiempo de establecimiento y liberación de un circuito es despreciable.

Para los valores p = 0,4 y D = 1/12 segundos:

a) Proponga un modelo para el análisis del número de circuitos empleados durante una sesión,suponiendo que se pueden establecer todos los circuitos que se desee.b) Halle la probabilidad de que en una sesión se estén utilizando k circuitos.c) Determine el número medio de circuitos utilizados en una sesión.d) Calcule el número mínimo de circuitos que se utilizan el 98% del tiempo.e) Si el valor máximo de k es 8, ¿cuál será la probabilidad de bloqueo?

Solución

a) Ejemplo de evolución temporal de k

4 3 2 1 0 d1

p

d2 d3 d4 d5 d6

1-p p p 1-p

K


( ) Dt

d eD

tf −=

1 ; función de densidad de probabilidad d

Puesto que el tiempo de permanencia de un valor de k está distribuido exponencialmente, k tomavalores enteros desde 0 y las variaciones de los valores de k son de una unidad entonces el valor de kes modelable por un proceso de nacimiento y muerte de la forma

0

λ0

µ1 1 2 K

λK-1

µK

λK

µK+1

λ1

µ2

λ2

µ3 3

λ3

µ4 4 5

λ4

µ5

Para determinar los valores de λi y µj basta recordar que el tiempo de permanencia en un estado k tienepor valor medio

Dado que todos los intervalos entre variaciones de k están distribuidos por la misma variableexponencial d, cuyo valor medio es D

Luego

Finalizado el tiempo de permanencia en un estado K = 1, 2, ..., la transición a un estado k +1 seproduce con probabilidad p y a un estado k –1 con probabilidad 1 – p.

El valor de p se obtiene como cociente de proporción de tasa de k a k + 1 respecto a todas las tasas. Porlo tanto

De igual forma

De donde se obtienen las tasas de transición para k = 1, 2, ...

∑=

kSk de salida de tasa

1

K,1,0con == kDSk

DS ==0

01λ

K,2,1con1==

+= kDS

kkk µλ

DSp kkkkk

k ·· λλµλ

λ==

+=

DSp kkkkk

k ·1 µµµλ

µ==

+=−

Dp

Dp

kk−

==1; µλ


b) Para el caso particular k = 0, es inmediato que

Con los valores calculados la cadena de Markov queda

0

λ0

(1-p)λ0

1

pλ0

2

pλ0

K

(1-p)λ0 (1-p)λ0 (1-p)λ0 (1-p)λ0

pλ0 pλ0

Aplicando la igualdad en los flujos de probabilidad en las conexiones

Una vez expresadas todas las probabilidades en función de p0, se obtiene

Si p = 0,4 y D = 1/12 s, entonces se hallan las probabilidades en régimen permanente con lasecuaciones en equilibrio.

61

0 =p y K,2,132

125

=

= kp

k

k

c) El valor medio se obtiene

∑ ∑∑∞

=

∞

=

∞

=

=

==

1 10 32··

125

32

125··

i i

ii

ii iipiK

( )

−==

⇒=⇒==0

00

00 1

11λµ

λλλ

λ pp

DDSk

k

( ) 011000 111 p

ppppp

−=⇒−= λλ

( )( ) 02122010 11

1 pp

ppp

pppppp−

=−

=⇒−= λλ

M

( )( )

pp

ppp

pppppp k

k

kkkk−

=−

=⇒−=−

−− 111

1

1010 λλ

M

( )pp

pp

p

kk

k 2221

11

1

1

10 −−

=

−+

=

∑∞

=

−

K,2,1con·1

10 =

−

= kpp

pp

pk

k


Sabiendo que

Entonces

Es decir, el ancho de banda medio de una conexión de vídeo ocupa 2,5 · 64 = 160 Kbps

d) La proporción del tiempo que se emplean k circuitos es igual a la probabilidad pk. Para hallar elnúmero de circuitos mínimo que se utilizan el 98% del tiempo, Π(98), hallaremos el valor acumuladode probabilidad de la forma

e) La probabilidad de bloqueo será en este caso

( )210 11

1··a

aaad

daaad

daaii

i

i

i

−=

−

== ∑∑∞

=

∞

=

( ) 5,225

3213

2·

125

2 ==−

=Κ

( )( ) 1017,99898,0

98

0

==Π⇒≤∑Π

=iiP

38

8 10·62,10162,032

125 −==

== ppB


Problema 4.22

Los equipos terminales de datos (ETD) de una red Frame Relay se conectan a la red a través de undispositivo denominado Multiplexor Inverso (MI). Este dispositivo permite recibir la informacióndirigida desde un servidor al ETD a través de múltiples enlaces de baja capacidad. La inserción del MIse debe a la reducción del coste económico al emplear varios enlaces cuya capacidad conjunta es CTbps respecto a un solo enlace de la misma capacidad.

Servidor

FRAME RELAY

Mux Inv ETD

Para dimensionar el MI, se realizan una serie de medidas del tráfico enviado desde los servidores a losETDs. Este tráfico se puede considerar de Poissson con una tasa de llegadas λ = 2000 paq/s y unadistribución exponencial de los paquetes con longitud media L = 2000 bits. Suponiendo que cadaenlace de baja velocidad tiene una capacidad C = 2Mbps:

1) Considerando que el número de enlaces de baja capacidad es prácticamente infinito:

a) ¿ Qué modelo de cola permite evaluar el comportamiento de MI?b) Halle la probabilidad de encontrar k enlaces ocupados en régimen permanente.c) Determine el número de enlaces mínimo m de forma que cuando llegue un nuevo paquete al MI laprobabilidad de que hallan m enlaces ocupados sea inferior a 1.5 10-2 .d) Calcule el percentil del número de enlaces ocupados al 95%.e) Calcule el número medio de enlaces ocupados en el MI.f) Halle el tiempo medio de tránsito por sistema MI de un paquete.

2) Fijando el número de enlaces de baja capacidad a 6 y no permitiendo el encolamiento de paquetesen el Multiplexor Inverso (MI):

a) ¿ Qué modelo de cola permite evaluar el comportamiento de MI?b) Halle la probabilidad de encontrar k paquetes en el sistema MI en régimen permanente.c) Determine la probabilidad de pérdida de un paquete que llega al sistema MI.d) Calcule el factor de utilización de un enlace de baja capacidad.e) Calcule el número medio de enlaces ocupados en el MI.f) Halle el tiempo medio de tránsito por sistema MI de un paquete.

3) Para un número de enlaces de baja capacidad de 6 y considerando una cola de almacenamiento decapacidad prácticamente infinita:

a) ¿ Qué modelo de cola permite evaluar el comportamiento de MI?b) Halle la probabilidad de encontrar k paquetes en el sistema MI en régimen permanente.c) Determine la probabilidad de cuando llegue un paquete al sistema MI deba esperar en la cola.d) Calcule cuál sería una longitud adecuada para la cola de almacenamiento de forma que laprobabilidad de pérdida de un paquete que llegue al sistema sea inferior a 10-4.


Solución

1) Módulo con ∞ enlaces de baja capacidad

λ∞

a) M/M/∞

b) Para el sistema M/M/∞

c) El número mínimo de enlaces m que verifica con llegadas de Poisson:

Dado que

K

!k

ep

k

k

µλ

µλ −

=

01234567

0,1350,270,270,180,09

0,0360,012*0,0034

d) El percentil ∏ )95( del número de enlaces ocupado al 95% serà el mínimo k que cumple:

e) Al ser una distribución de Poisson (λ, 1/µ):

=−

µλµ

λµ

λ1,Poisson

!e

kp

k

k

( ) 210·5,1llegada−<=

= mpmtNp

2=µλ

610·5,1 2máx =⇒<⇒ − mp

( )

∑∏

=

≥%95

0

95,0k

kp

( )∏ ∑ ≥===

95,0981,0que ya5%955

0kkp


f) En este sistema no existe almacenamiento por lo que:

2) Modelo con número finito de enlaces sin almacenamiento

λm=6

a) M/M/m/m

b) En régimen permanente:

c) Dado que:

Entonces:

Puesto que las llegadas son de Poisson

d) Factor de utilización del sistema con pérdidas:

e) El número medio de enlaces ocupados será:

21· == µλN

ms1== xT

∑=

= m

j

j

k

k

j

kp

0 !1!

1

µλ

µλ

2=µλ

355,7!6

2!5

2!4

2!3

2!2

2!1

2!0

2!

1 65432106

0

=++++++=

∑

=j

j

j µλ

===== − 6,B-Erlang10·2,1

355,7!6

22

6

6 µλppPP mperdB

( )µ

λλρ

mx

mPperd ≈=

−= 329,0·

1·

+++++== ∑

= 72064·6

12032·5

2416·4

68·32·22·1·

35,716

0kkpkN


f) Aplicando la fórmula de Little para el caso con pérdidas:

3) Modelo con capacidad de almacenamiento infinito y número de enlaces finito

6∞

a) M/M/6

b) En régimen permanente el modelo M/M/m tiene por probabilidades:

c) Puesto que las llegadas son de Poisson:

97,1=N

( ) ms9969,01

=−

=perdP

NTλ

( )

≥

=≤=

mkm

mp

mmk

kmp

pmk

k

k

!

!

0

0

ρ

µλρ

ρ

( ) ( )∑−

= −+

= 1

0

0

11

!!

1m

k

mk

mm

km

p

ρρρ

∑∞

=

=

>=

mk

km

enc mmpmNPP

!llegada 0ρ

ρρρ−

== ∑∞

= 1·

!·

!· 00

mm

mk

km

enc mmp

mmpP

( )ρ

ρ−

=1

1!

·0 mmpP

m

enc

52,71

311

1·!6

2!

21

5

0

60 =

−+

=

∑=k

k

k

p


d) Observamos qué valores dan lugar a 410−<perP

kk

m

k mmpP ρ

!0=

91011

4,37 · 10-4

1,459 · 10-4

4,86 · 10-5 < 1 · 10-4 ⇒ Q = 5 unidades

0177,03

111

52,7!6

26

=−

=encP


Problema 4.23

Un multiplexor estadístico conecta un conjunto de terminales con un ordenador a través de un módemque emplea la norma V.23. Esta norma de explotación de la línea de transmisión divide el ancho debanda en dos canales, cuyas velocidades de transmisión son v1 = 1200 bps y v2 = 75 bpsrespectivamente. Cada canal se emplea para transmitir la información en un sentido, aunque no existeuna asignación fija de sentidos y canales. De esta forma, un canal puede ser empleado a veces paratransmitir en un sentido y otras en sentido opuesto durante la comunicación, mientras que el otro seutilizará para la transmisión en sentido opuesto simultáneamente.

Para evaluar el comportamiento de la conexión de los terminales con el ordenador se considera

i) El canal 1 se utiliza con probabilidad σ ∈ [0,1]ii) El canal 2 se utiliza con probabilidad 1 - σ

Suponiendo que el tráfico generado por el conjunto de terminales responde a una distribución dePoisson de tasa λ paq/s, que el multiplexor tiene una capacidad de almacenamiento prácticamenteinfinita y que la distribución del tamaño de los paquetes es exponencial de longitud media L:

a) Determine el tiempo medio de servicio en función de las tasas de servicio µ1 y µ2 asociadas a loscanales 1 y 2 respectivamente.b) Exprese la función de densidad de probabilidad del tiempo de servicio b(t), considerando L = 160bits; λ = 0,375 paq/s; σ = 0,4.c) Halle el coeficiente cuadrático de variación del tiempo de servicio cx

2.d) Caracterizando el sistema como una cola M/G/1

- Calcule el factor de utilización del servidor.- Determine el tiempo medio T necesario para que un paquete atraviese el sistema

cola+servidor.

Solución

a) El tiempo medio será una función de las tasas de servicio posibles en el canal:

b) La función de densidad de probabilidad del tiempo de servicio será:

c) El coeficiente cuadrático de variación del servicio será:

( )21 , µµfx =

( ) 211222

1111 1·

V

Vxxx

Lx

Lxσσ

µ

µ−+=⇒

==→

==→−

−

( )21

111·µ

σµ

σ −+=x

( ) ( ) tt eetb 2121 1·· µµ µσµσ −− −+=


Con 24,0paq/s,375,0 bits,160 === σλL

d)i) El factor de utilización será: 5,0333,1·5,0· === xλρ

ii) El tiempo medio de transferencia será: ( ) ( )5,01208,21

5,0·333,1333,112

1 2

−+

+=−

++=

ρρ xc

xxT

[ ] [ ] 12

2

2

22

2

22 −=

−==

xxE

xxxE

xc x

xσ

[ ] ( )( )∫∞ −− −+=

0

221

2 ·1 21 tdteexE tt µµ µσµσ

[ ] [ ] ( ) [ ] ?1· 22

21

2 =−+= xExExE σσ

[ ] 22

12

12

12

122

1 para mismo lo,21

xxxxxxE x =+=+= σ

s133,01250160

1 ==x

s133,275

1602 ==x

( ) 28,1053,028,113,0·4,01 21 +=+=−+= xxx σσ

s333,1=x

[ ] [ ] ( ) [ ] ( ) 22

21

22

21

2 1221 xxxExExE σσσσ −+=−+=

[ ] 46,501415,0133,2·6,0·2133,0·4,0·2 222 +=+=xE

[ ] 22 s4737,5=xE

[ ] 08,212

22 =−=

xxEcx

s38,3=T


Problema 4. 24

Dos ordenadores se conectan a través de un circuito básico de RDSI de C = 64 Kbps para transmitir unfichero de F = 106 bytes. La transmisión se realiza empleando un protocolo de ventana que utilizapaquetes de longitud fija de L bits y cuyo tamaño de ventana W es 8 paquetes. Teniendo en cuenta quelos paquetes de reconocimiento son de longitud constante R = 800 bits y que la RDSI introduce unretardo extremo a extremo τ.

PC

τ

PC

RDSI

64 kbps

a) Halle la longitud mínima de los paquetes L para que el tiempo de transmisión del fichero sea de 3min cuando el retardo τ = 10 ms.b) Para la longitud mínima hallada, calcule el tiempo necesario para enviar el fichero cuando el retardosea τ = 400 ms.

Solución

a) Para τ = 10 ms

PC

τ=10ms

PC 64 Kbps RDSI

W = 8 paquetes

T = 3 min = 180 s

Para hallar la longitud mínima debemos determinar:

Tiempo de transmisión de un bloque CR

CLWTB ++= τ2

bits10·8bytes10·1 66 ==F

bits800bytes100 ==R

LWFN·

r transmitia bloques de nº ==

τ2++=C

LWRTB


Tiempo de transmisión total

En este caso

b) Aumentando el retardo de propagación a:

Con:

Obtenemos:

Dado queN = 1692

Entonces:T = 1500 s = 25 min

+

+== τ2··

CLWR

LWFTNT B

( )ττ CRFTC

WF

LTC

LWRLW

F 22máx

máx +−

>⇒≤

+

+

bits591≥L

ms375,106=BT

1692=N

ms400=τ

bits591=L

ms375,886=BT

5 Evaluación de técnicas de acceso múltiple 151

5 Evaluación de técnicas de acceso múltiple

Problema 5.1

Los diez terminales dibujados se conectan a un concentrador mediante sondeo centralizado en unescenario de recolección de datos.

Los parámetros del sistema son los siguientes:

- Tasa global de generación de paquetes, λTOT = 9 paq/s- Capacidad del enlace, C = 28800 bps- Velocidad de propagación de señales, v = 200000 Km/s- Longitud de los mensajes de sondeo, LMS = 96 bits- Longitud de los mensajes de respuesta negativa por parte del terminal, LRN = 48 bits- Lontigud de los mensajes de datos del terminal, L = 60 bytes (distribución exponencial)

CONCENTRADOR

Datos

TERM_10

Datos

TERM_1

Control

120 Km

Calcular

a) Tiempo de ciclo sin carga, TC(0)

b) Tiempo de ciclo con carga, TCc) Tiempo de acceso del terminal al concentrador, TA

Solución

a) Sea

TMS = tiempo de transmisión del mensaje de sondeo


TRN = tiempo de transmisión del mensaje de respuesta negativa (nada que transmitir) por parte delterminal

TP = tiempo de propagación entre terminales

Se sabe que

siendo n el número de terminales.

Substituyendo, se tiene

b) Se sabe que

donde

siendo TS el tiempo de transmisión de un paquete (tiempo de servicio).

Substituyendo se tiene

c) El tiempo medio de transferencia (espera + transmisión) sin control y con terminales locales, T, es

T = TW + TS

donde, para longitudes exponenciales, es

Substituyendo se tiene

Como n >> ρTOT el tiempo de acceso se puede aproximar por:

Resumiendo

( ) pRNSC TnnTnTnT 1M)0( +++=

s057,0200000

12111028800

481028800

9610)0( =⋅++=CT

TOT

CC

TT

ρ−=

1

)0(

STOTTOT Tλρ =

ms6715,01

57

288008·6091

57=

−=

−=CT

TOT

TOTSW TT

ρρ−

=1

ms201717,01728800

8·6015,01

15,028800

8·60=+=+

−=T

ms53202

672

=+=+= TTT CA


TC(0) = 57 ms

TC = 67 ms

TA = 53 ms


Problema 5.2

Una red de acceso por sondeo está formada por M = 50 estaciones conectadas a un dispositivo centralmediante enlaces full-dupplex formando una topología en estrella. Cuando el dispositivo centralsondea a la estación, ésta le transmite toda la información que ha almacenado desde la última vez quetransmitió. El dispositivo central retransmite dicha información al resto de estaciones. La estaciónfinaliza la transmisión cuando vacía su buffer complemente añadiendo un sufijo para indicar aldispositivo central que no tiene más información que transmitir. Inicialmente se comprueba elfuncionamiento de la red de manera que ninguna de las estaciones tenga nada que transmitir. En estecaso se observa que cada estación es sondeada cada TC

0 = 3,2 ms. Finalmente se activan los procesosde comunicaciones entre estaciones, de manera que cada una de ellas genera λ1 = 1,5 paquetes porsegundo. Dichos paquetes son de longitud fija e igual a L1 = 1000 bytes. Teniendo en cuenta que elmensaje de sondeo y el sufijo que añaden las estaciones son de 6 y 2 bytes respectivamente, calcule:

a) Tiempo de ciclo del sistemab) Tiempo medio desde que se genera un paquete hasta que es recibido por su destinatarioc) Número medio de paquetes en espera de ser transmitidos en una estación genéricad) Fracción de tiempo durante la cual el sistema está sondeandoe) Número máximo de estaciones que admite el sistema bajo estas condiciones de tráfico

Suponiendo que en cada una de las estaciones, además del tráfico generado anteriormente, se generannuevos paquetes con una tasa λ2 = 2,5 paquetes por segundo, y cuya longitud está distribuidaexponencialmente con media L2 = 250 bytes.

f) Calcule el tiempo medio desde que se genera un paquete de este último tipo hasta que es recibidocompletamente por su destino.

Solución

a)

��

��

��

��

��

��

w

Sufijo i Sondeo i+1

la estación i vacía su buffer

la estación i+1 vacía su buffer

w: tiempo desde que una estación deja de transmitir hasta que empieza la siguiente (walk time)

En un ciclo sin tráfico se cumple

( ) 30 10·2,38·2650 −=+

==C

wMTC

bps106=C


b)

Para paquetes de longitud fija

Tiempo de espera en el buffer de una estación para un paquete genérico

c) Aplicando Little

d) En cada ciclo se sondea durante Mw segundos

Evidente, ya que la estación central siempre está ocupada; cuando no está transmitiendo estásondeando. Como S = 0,6, significa que el 60% del tiempo está transmitiendo de manera que el 40%restante está sondeando.

e) Para no ocupar el sistema más del 100% del tiempo se debe cumplir S < 1.

f)

6,011 ==C

LMS λ

ms86,01

10·2,31

3

=−

=−

=−

SwMTC

ms81 ==CLx

( ) 2622 s10·64 −== xxE

( )( )

( )( ) ms952,912·

12

1 2

=−

+−

−=

xSxES

S

wMMS

W

ms952,1711 =+= WxT

paquetes014928,010·952,9·5,1 31 === −WN λ

4,010·810·2,3

3

3

== −

−

CTwM

1<C

LM iiλ

3,831000·8·5,1

106

==<ii L

CMλ

83=máxM

375,021

11 =

+=

λλλ

p

625,021

22 =

+=

λλλ

p


ms25,422

11 =+=

CL

pCL

px

( ) 85,021 =+= xMS λλ

( ) ( ) ( ) ( ) ( ) 262

221

21

222

211

2 s10·29·2 −=+=+= xEpxEpxEpxEpxE

( )( )

( )( ) ms81,29

·1212

1 2

=−

+−

−=

xSxES

S

wMMS

W

ms818,31222 =+=+= W

CLWxT


Problema 5.3

Un conjunto de 2 terminales accede a una red de transporte a través de un concentrador que les daservicio mediante una técnica de polling centralizado. La línea multipunto que une dichos terminalescon el concentrador es de 4800 bps. El concentrador sondea a cada estación mediante preguntas quesiguen el formato HDLC, al igual que las respuestas de los terminales, en las cuales indican si deseano no desean transmitir. Para dichas preguntas y respuestas, la longitud del campo de datos es n = 10.

F D C DATOS SVT F

bytes 1 1 1 n 2 1

Trama HDLC

En el momento en que el terminal i (i = 1,2) es sondeado:

- con probabilidad pi transmitirá un paquete de longitud fija igual a L bits, empleando para ello untiempo de P segundos.

- con probabilidad (1 - pi) no transmitirá nada.

Los terminales transmiten como máximo un paquete cada vez que son sondeados. Posteriormente sesondeará al siguiente terminal, sin esperar ningún tipo de respuesta por parte de la red ni de ningúnelemento conectado a ella, ya que cuando éstas son necesarias, son transmitidas por un canalindependiente de retorno.a) Calcule el tiempo de ciclo de polling en ausencia de tráfico, TC

(0)

b) Calcule el tiempo medio de ciclo, TC, en función de p1 y p2.c) Calcule el tiempo medio desde que se produce una llegada a una estación hasta que ésta esnuevamente sondeada, en el caso en que L = 480 bits, p1 = 0,4 y p2 = 0,6.d) Repita el cálculo anterior para el caso en que L = 480 bits y que p1 = p2 = 1. Ofrezca, para este caso,una mejora para el sistema de acceso empleado.

Solución

a)

b) El ciclo queda de la siguiente forma

P con prob. p1 0 con prob. (1-p1)

P S/N

preg 1 S/N

preg 2

P

P con prob. p2 0 con prob. (1-p2)

Por tanto, el tiempo medio de ciclo será

( ) ( ) s107,04800

8·6104800

8·610·2)0( =

+++=CT


c) Tenemos que calcular el tiempo residual de un ciclo el cuál viene dado por

Conocemos el tiempo medio de ciclo, TC, pero nos falta calcular el segundo momento de tC para podercalcular CTc

2.

La duración de tc será la siguiente:

tc = TC(0) con probabilidad = (1 - p1) (1 - p2) (es decir, cuando ninguna de las estaciones transmite)

tc = TC(0) + P con probabilidad = p1 (1 – p2) + p2 (1 – p1) (transmite 1 o transmite 2)

tc = TC(0) + 2P con probabilidad = p1 p2 (1 y 2 transmiten)

Podemos comprobar el valor medio:

Aplicando los valores del enunciado

Calculemos el segundo momento

Con esto

( )21)0(

21)0( ·· ppPTpPpPTT CCC ++=++=

CT

espera TC

T c

21 2+

=

( ) ( ) ( ) ( ) ( ) ( )[ ] ( ) =++−+−++−−== 21)0(

1221)0(

21)0( 21111 ppPTppppPTppTTtE CCCCc

( ) +−+−+−++−− 21121)0(

2)0(

21)0(

1)0(

2121)0( 1 ppPpPppTpTppTpTppppT CCCCC

( ) OKppPTpPpPTppPppTppPpP CCC ⇒++=++=++−+ 21)0(

21)0(

2121)0(

212 2

( ) s207,011,0107,0

1,0s

bits4800bits480

6,04,0

s107,0

2

1

)0(

=+=

===

==

=

C

C

T

CLP

ppT

( ) ( ) ( ) ( ) ( ) ( )[ ] ( ) =++−+−++−−= 212)0(

12212)0(

21)0(2 21111

2ppPTppppPTppTtE CCCC

( ) ( ) ( ) =+++++ 6,0·4,0·2,0107,06,0·6,04,0·4,01,0107,04,0·6,0·107,0 222

0476,010·6,2210·3,2210·7,2 333 =++= −−−

( ) ( )( )

112,00428,0

0428,00476,0207,0

207,00476,02

2

2

22

2

22 =

−=

−=

−==

C

CC

C

tt tE

tEtET

C C

C

σ


De donde

d) Si p1 = p2 = 1 (las estaciones transmiten siempre)

Tc = Tc(0) + 2P = 0,107 + 0,2 = 0,307 s

y tc = Tc siempre, ya que el sistema pasa a ser determinista. Por tanto

Evidentemente, se está perdiendo un tiempo innecesario en sondeos y sería mucho más eficaz unsistema TDM determinista.

s115,0207,0·2112,01

espera =+

=T

s154,02307,0

210 espera

2 ===⇒= CT TTCC


Problema 5.4

La figura muestra dos redes de acceso de tipo ALOHA PURO (A y B) interconectadas mediante unalínea dedicada de capacidad C bps. La red de acceso A está formada por 25 terminales iguales(clientes) y un dispositivo que permite la interconexión con la red remota. La red B está formada porotro dispositivo de interconexión y un número suficiente de terminales para que pueda considerarseuna población infinita de servidores. Los clientes de A sólo generan peticiones, las cuales sonrecogidas por el dispositivo de interconexión y retransmitidas hacia la red B. Cuando una peticiónllega a B es atendida por un único servidor, el cual genera una respuesta que es enviada hacia la red A.Tras la puesta en marcha del sistema se observa que cada cliente de A realiza en media 1,5 peticionesexitosas por segundo, las cuales siempre son respondidas por algún servidor en B. Tanto las peticionescomo las respuestas son de longitud fija e igual a 250 bytes y las capacidades de las redes A y B sonCA = 2 Mbps y CB = 1 Mbps respectivamente.

Notas adicionales:

- Los retardos debidos a propagación pueden considerarse nulos.- Para resolver ecuaciones intrascendentes utilice la aproximación e-2x ~ 0,3 (3 – 4x), correspondienteal desarrollo en serie de Taylor de la función e-2x alrededor de x = 0,25.

a) Determine el número medio de intentos de acceso (peticiones nuevas + retransmisiones) porsegundo en la red A y en la red B.b) Calcular el retardo medio desde que se genera una petición en un cliente de A hasta que ésta esrecibida correctamente por el dispositivo de interconexión de A. Repita el cálculo para una respuestagenerada en B y el dispositivo de interconexión en B. El tiempo medio de back-off en ambas redes deacceso es igual a 3 ms.c) Calcular la capacidad mínima necesaria C en la línea dedicada para que el retardo desde que unpaquete llega a un dispositivo de interconexión hasta que es recibido por el otro sea inferior a 20 ms.d) ¿Cuál es el número máximo de terminales (supuestos todos iguales) que pueden conectarse a la redA para que todo el sistema pudiese funcionar?

Solución

a) En la red ALOHA A, se cursa el tráfico generado por las 25 estaciones más el tráfico inyectado porel dispositivo de interconexión provinente de la red B. Como cada petición tiene asociada una únicarespuesta, la tasa total cursada en A será igual al doble de la tasa generada por los 25 terminales.

En condiciones de estabilidad el tráfico ofrecido a la red es igual al cursado (igual al caudal)

paquetes/s755,1·25·2··2 === iA M λλ


La carga ofrecida a la red se obtiene como

La solución estable se obtiene con GA < 0,5

El número total de intentos de acceso por segundo se obtiene a partir de la carga:

Esta solución es aproximada, resolviendo la ecuación intrascendente con métodos iterativos, se obtiene

Utilizando el mismo razonamiento en la red B, se obtiene

Calculando el valor exacto, se obtiene

075,010·2

8·250·756 ====

A

AAAA C

LPS λλ

( ) 22 2,19,0433,0· AAAAG

AA GGGGeGS A −=−≈= −

0075,09,02,1 2 ≈+− AA GG

ESTABLE0955,0≈AG

INESTABLE654,0≈AG

intentos/s5,958·25010·2·095,0 6

=≈==ΛLCG

PG AA

A

AA

AGA eG 2075,0 −=

ESTABLE0897,0=AG

INESTABLE496,1=AG

7,89=ΛA

paq/s75== AB λλ

15,010

8·250·756 ===

B

BB C

LS λ

015,09,02,1 2 ≈+− BB GG

ESTABLE25,0≈BG

INESTABLE5,0≈BG

intentos/s125≈ΛB

2447,0=BG


b) Red A

Red B

Utilizando los valores exactos para GA y GB, se obtiene

TA = 1,78 ms

TB = 5,15 ms

c) Modelamos el dispositivo de interconexión y la línea dedicada con un sistema M/D/1. Se suponeque la capacidad de almacenamiento del dispositivo es suficientemente grande como para considerarlainfinita. La tasa de llegada a cada dispositivo de interconexión es igual a la tasa generada por losterminales de su misma red de acceso. En ambas redes dicha tasa vale

El retardo vale

La condición de estabilidad en este caso es ρ = λ x < 1

d) La condición de estabilidad en las redes de acceso es

intentos/s35,122=Λ B

( ) )(12 BPePT AG

AAA +−+=

ms1==A

A CLP

( )( ) ms84,1ms311ms1 0955,0·2 =+−+= eTA

ms2==B

B CLP

( )( ) ms24,5ms321ms2 25,0·2 =+−+= eTB

paquetes/s5,375,1·25· === iM λλ

( )3

22

10·20752

5,3712

−=−

+=−

+=x

xxx

xxTλ

λ

010·405,35,37 32 =+− −xx

INESTABLE756

=x

ESTABLE751

=x

Kbps15075·8·250 ===xLC


siendo el caudal

La situación más desfavorable es para la red con un tiempo de transmisión de paquete mayor, en estecaso la red B.

Con este número de terminales la tasa de llegada a los dispositivos de interconexión es

Con lo cual todo el sistema puede funcionar.

eS

21

<

PMS iλ'2=

65,304

1' =<Bi Pe

Mλ

terminales30máx =M

paquetes/s455,1·30·máx === iM λλ

17545

<== xλρ


Problema 5.5

Una de las hipótesis simplificadoras en el estudio de las técnicas de acceso múltiple ALOHA yALOHA ranurado es que el número total de paquetes a transmitir por el canal común (incluyendotodas las estaciones de la red, los paquetes generados por primera vez y los que se han de retransmitirpor colisiones previas), responde a una distribución de Poisson. Ello supone, por tanto, una poblaciónde usuarios (M estaciones) infinita.

Considérese ahora una red con M estaciones independientes que utilizan un mecanismo de acceso almedio compartido ALOHA ranurado. Las transmisiones de cada usuario se modelan como unasecuencia de procesos de Bernoulli independientes (cada estación transmite con cierta probabilidadcomprendida entre cero y la unidad). Se supone también que todas las transmisiones se originan segúnel mismo proceso de llegadas y que el modelo no tiene en cuenta los retardos de back off debidos acolisiones.

Sean:

Si = Probabilidad de que la estación i transmita con éxito un paquete en una ranura temporalcualquiera.Gi = Probabilidad de que la estación i intente transmitir en una ranura temporal cualquiera.

Es decir, que Si y Gi son también el caudal y el tráfico ofrecido en régimen permanente para laestación i.

a) Calcule el caudal medio en régimen permanente para una estación j en función del tráfico ofrecido.Justifique la respuesta.b) Considérese ahora que las M estaciones (que son estadísticamente independientes) compartenequitativamente la carga, es decir, Si = S/M y Gi = G/M. Obtenga, según lo visto en el apartadoanterior, la expresión del caudal S.c) Obtenga de nuevo la expresión del caudal cuando el número de estaciones se hace muy grande ytiende a infinito. Justifique la expresión obtenida.d) Calcule la expresión del caudal máximo para los casos b) y c) anteriores.e) ¿Qué valor de M ofrece una buena aproximación al caso de población infinita? (Error relativo paralos caudales máximos inferior al 2,5%.)

Solución

a) Se trata de encontrar Sj en función de Gj

ya que la probabilidad de que la estación j transmita con éxito es debida a que la estación j es la únicade las M que intenta transmitir en una ranura temporal particular (y el resto no intentan transmitir ⇒(1 – Gi)). Además, como los intentos de transmisión son independientes para cada estación, se puedefactorizar.

b) Basta substituir en la expresión anterior

( )∏≠=

−=M

jii

ijj GGS1

1

1

1−

−=

M

MGGS


c) Si M → ∞

S = G · e-G expresión del caudal para la técnica de acceso ALOHA ranurado considerando poblacióninfinita.

d) Basta derivar las exposiciones obtenidas en b) y c) con respecto de G e igualar a cero.

Tomando

Igualando a 0 ⇒ G = 1 (independientemente de M)

Se obtiene Smáx para la carga ofrecida = 1, substituyendo

Operando análogamente cuando S = G · e-G

Igualando a 0 ⇒ G = 1, de donde

Smax = e-1 ≈ 0,368

e)

por tanteo (M ha de ser entero)

El primer valor que cumple es M = 21.

Así e

S 1máx = es buena aproximación al caso de población finita cuando el número de estaciones es

superior a 21.

( ) GM

MMeG

MGlímGSlím −

−

∞→∞→=

−

+= ·1·1

1

1−

−=

M

MGGS

1

máx11

−

−=

M

MS

( )GMG

GdSd M

−

−=

−

112

( )GeGdSd G −= − 1

025,011

111

1

1

<

−

−

−

−

−

M

M

M

eM


Problema 5.6

Una red de comunicaciones compuesta por distintos dispositivos de conexión emplea un mediocompartido de velocidad de transmisión C bps para intercambiar paquetes de información.

λ

C bps

Por conflictos de acceso, el intento de transmisión de un paquete puede ser fallido con unaprobabilidad [ ]1,0∈σ o exitoso con una probabilidad 1-σ. En el caso de fallo se considera que elpaquete debe ser retransmitido nuevamente (como si se tratara de un nuevo paquete a transmitir)transcurrido un tiempo aleatorio distribuido exponencialmente con duración media 1

2µ . Suponiendoque la tasa de llegadas del conjunto de todos los dispositivos de comunicación es λ paq/s y que ladistribución del tamaño de los paquetes es exponencial de longitud media L:

a) Razone por qué, para el análisis del comportamiento de un paquete cualquiera, el sistema dealmacenamiento y transmisión se podría modelar de la siguiente forma:

αγσ

1−σµ1

∞

λΜ/Μ/1

+

β

Μ/Μ/∞µ2µ2

µ2µ2∞

Sistema de Almacenamiento y Transmisión

α= tasa de llegadas al sistema M/M/1β = tasa de llegadas al sistema M/M/∞γ = caudal de salidaµ1 = C/L

b) Aplicando el teorema de Burke, determine la relación entre las tasas:

i) α y γii) α y λiii) β y λ

En el caso de que: λ=15paq/s; µ1=40paq/s; σ=0.25 y 12µ =0.1s

c) Halle el tiempo medio necesario T para que un paquete sea transmitido exitosamente.d) Calcule el caudal de salida γ.e) Razone cuál será la condición de estabilidad.


Solución

a) M / M / 1 Sistema de almacenamiento y transmisión

La cola representa la ocupación de todas las colas de los dispositivos. El servidor en este caso reflejael tiempo necesario para transmitir un paquete cuya distribución es exponencial. La tasa de servicioserá

Al sistema llegan los nuevos paquetes y los fallidos con tasa α, por lo que α = λ + β.

Puesto que λ y β están distribuidos exponencialmente, α también.

M / M / ∞. Sistema de espera para reintento

En este caso, los paquetes esperan un tiempo aleatorio distribuido exponencialmente con tasa µ2.Puesto que consideramos una población infinita, podemos considerar que se está sirviendo, o seaesperando, para reincorporarse en los distintos dispositivos que son ilimitados. De esta maneratenemos hasta ∞ servidores. La tasa de llegada β es exponencial de valor σ · α.

b) El Teorema de Burke demuestra que el proceso de salidas de un sistema M / M / n cuyo proceso dellegadas es de Poisson con tasa exponencial λ es también un proceso de Poisson de la misma tasa. Eneste caso todos los subsistemas son del tipo M / M / n, por lo que se puede operar linealmente con lastasas de llegada y salida. Así

α = λ + β

i) Dado que un proceso de Poisson de tasa α que se divide en dos procesos, de forma que unaunidad pasa a un proceso con probabilidad σ y al otro con probabilidad 1 - σ, da lugar a dosprocesos de Poisson con tasas ( )ασασ −1y respectivamente

ii) Operando linealmente con las tasas de cada subsistema, obtenemos

iii) Por lo tanto β se realaciona con λ como:

Si s1,01y25,0 ; paquetes/s40 ; paquetes/s152

1 ==== µσµλ

c) Considerando el sistema como la composición de dos subsistemas M / M / 1 y M / M / ∞,determinamos el número medio de unidades dentro del sistema

N = NM / M / 1 + NM / M / ∞

LC=1µ

ασβ =

( )ασγ −= 1

σλαασλβλα−

=⇒+=+=1

σλσασβ

−==

1


NM / M / 1 se obtiene a partir del factor de utilización del subsistema 1

1 µαρ = como

NM / M / ∞ es directamente el cociente entre la tasa de llegadas y la tasa de servicio de uno de susservidores

Luego, N = 1,5

Aplicando la fórmula de Little

d) El caudal de salida será directamente

Este resultado es inmediato, dado que el sistema es estable y no tiene pérdidas.

e) El sistema M/M/: siempre es estable mientras que el M/M/1 debe cumplir que:

Para elloα < µ1,

por lo que el sistema global será estable cuando:

es decir,λ < (1 - σ) µ1

En este caso, σ = 0,25 y µ1 = 40 paq/s, se debe cumplir

λ < 30 paq/s

( )

( )1

11

111

1

1

1

1

1

11// =

−−

−=

−=

−=

µσλ

µσλ

µαµ

α

ρρ

MMN

5,0·1 22

// =−

==∞ µλ

σσ

µβ

MMN

ms100==λNT

( ) paq/s151 ==−= λασγ

11 <ρ

11µ

σλα <−

=


Problema 5.7

Un sistema de telemetría está compuesto por una red cableada y una red inalámbrica. Ambas redes deacceso emplean el mecanismo ALOHA para enviar la información hasta un concentrador que estádirectamente conectado al centro de control de información (CCI) a través de una línea dedicada de14400 bps. Suponiendo que el comportamiento del tráfico (paquetes nuevos + retransmisiones) de lasdos redes de acceso es aproximable por un proceso de Poisson y que sus características son:

i) Red de acceso cableada:• Velocidad del medio de transmisión (VA) = 100 Kbps• Longitud de los paquetes (LA) = 16 octetos• Tasa de llegadas (paquetes nuevos + retransmisiones) (λA) = 12 paq/s• Tiempo medio de back-off (BA) = 0,083 s• Retardo máximo de propagación despreciable

ii) Red de acceso inalámbrica:• Velocidad del medio de transmisión (VB) = 48 Kbps• Longitud de los paquetes (LB) = 48 octetos• Tasa de llegadas (paquetes nuevos + retransmisiones) (λB) = 24 paq/s• Tiempo medio de back-off (BB) = 0,0416 s• Retardo máximo de propagación despreciable

CCI

100 Kbps

48 Kbps 14400 bps

a) Determínese el número medio de paquetes por segundo transmitidos exitosamente (γA y γB) en lasdos redes de acceso.b) Hállese el tiempo medio de transmisión exitosa (TA y TB) para cada red de acceso.c) Calcúlese el coeficiente cuadrático de variación (cx

2 ) del tiempo de servicio en el concentrador.d) Estímese el retardo medio sufrido por un paquete en el sistema concentrador (Tc) (encolamiento +retransmisión).e) Determínense los tiempos medios de transmisión de paquetes desde las estaciones al CCI (Te-eA y Te-

eB) cuando se asigna mayor prioridad en el concentrador a los paquetes de la red de acceso inalámbricafrente a los de la red de acceso cableada.

Nota:

Retardo medio en cola M/G/1: )1(2)(

)1(21

)(22

ρλ

ρρ

−=

−+

=xEc

xWE x

Retardo medio en cola para prioridad alta (1) y prioridad baja (2):

ww

10

11=

−( )ρ w

w2

1

1 21=

− −( )ρ ρcon w

E x0

2

2=

λ [ ]


Solución

a)

b) Para cada paquete

# medio de transmisiones SG

=

# medio de retransmisiones 1−=−

=SG

SSG

c)

s/t.paq10·28,110·1008·16 3

3−===

A

AA V

LP

paq/t.paq0,015s/t.paq10·28,1·12· 3 === −AAA PG λ

paq/t.paq0,0149· 2 == − AGAA eGS

paq/s12=⇒≈= AAA

AA P

S γλγ

s/t.paq10·8 3−==B

BB V

LP

paq/t.paq192,0· == BBB PG λ

paq/t.paq13,0· 2 == − BGBB eGS

paq/s35,16==B

BB P

Sγ

GG eSGeGS 22 =⇒= −

( ) ( )12 −++= GeBPPT

s10·84,310·56,210·28,1015,0

s10·28,1

s083,03333 −−−− =+=⇒

==

=

A

A

A

A

TGP

B

s10·2,31468,0·0496,010·8192,010·8

s0416,0333 −−− =+=⇒

==

=

B

B

B

B

TGP

B

[ ]2

22

2

2

2

22

LLLE

Lxc Lx

x−

===σσ


d)

e)

35,2835,1612 =+=+= BA γγγ

oct48oct16 == BA LL

bits71,2758·48·577,08·16·423,0 =+=+= BB

AA LLL

γγ

γγ

[ ] ( ) ( )22222 384·577,0128·423,0 +=+= BB

AA LLLE

γγ

γγ

[ ] 22 bits 54,92012=LE

[ ] 21,012

222 =−==

LLEcc Lx

21,02 =xc

( )ρρ

−+

+=12

1 2x

cc

xxT

106,0bps 14400

bits/paq128·paq/s12· ====t

AAAAA v

LX γγρ

436,0bps 14400

bits/paq384·paq/s35,16· ====t

BBBBB v

LX γγρ

542,0=+= BA ρρρ

s10·146,1914400

712,275 3−===tv

Lx

21,02 =xc

( )542,01221,1·542,0·10·146,1910·146,19 33

−+= −−

cT

s10·855,3210·708,1310·146,19 333 −−− =+=cT

[ ] [ ] s10·3,614400

54,92012·235,28·

2·

23

22

22

0−====

tvLExEw γγ

s10·17,111

30 −=−

=B

Bw

wρ


s10·39,241

3−=−

=ρ

BA

ww

333 10·88,810·39,2410·84,3 −−−− ++=++= AAAAee xwTT

ms12,37=− AeeT

333 10·6,2610·17,1110·2,31 −−−− ++=++= BBBBee xwTT

ms13,69=− BeeT


Problema 5.8

Un conjunto elevado de usuarios accede a una base de datos mediante un sistema de telecomunicación.Las peticiones a la base de datos son paquetes de longitud constante de 960 bits que se envían desde elterminal de los usuarios a través de una red inalámbrica de 100 Kbps que emplea la técnica de accesoALOHA ranurada. La tasa de peticiones generada por los terminales sobre la red es de 25 paq/s, dondese consideran los paquetes nuevos y las retransmisiones. Los terminales emplean un algoritmo deretransmisión (back-off) cuyo retardo es un valor entero equiprobable de tiempos de transmisión depaquete del conjunto {1, 2, 3, 4, 5}. En esta red de acceso se consideran los tiempos de transmisión dereconocimientos (ack) y los retardos de propagación despreciables.

BD33600 bps

100 Kbps

1 Mbps1 Mbps

a) ¿Cuál es el tiempo medio de transmisión con éxito de un paquete de petición en la red de accesoALOHA ranurada (Taloha) ?

Los paquetes de petición transmitidos con éxito son recibidos por un concentrador según unadistribución de llegadas que aproximadamente sigue un proceso de Poisson. El concentrador, concapacidad de almacenamiento prácticamente infinita, retransmite los paquetes de petición sobre unalínea de transmisión de 33600 bps que lo enlaza con la base de datos.

b) ¿Qué tiempo tardan las peticiones almacenadas en el concentrador en ser recibidas por la base dedatos (Tconcentrador-BD)?

Las respuestas de la base de datos son enviadas a un segundo concentrador con capacidad dealmacenamiento prácticamente infinita. El concentrador las retransmite sobre un enlace satélite desubida cuya capacidad es 1 Mbps. Un satélite situado a una distancia de todos los dispositivosterrestres de aproximadamente 12000 Km actúa como repetidor sobre un canal de bajada de capacidadigual al de subida. Se considera que el satélite no introduce ningún tipo de retardo en elalmacenamiento y retransmisión de los bits y que la información únicamente sufre un retardo depropagación a razón de 4 µs/Km.Teniendo en cuenta que para cada paquete de petición que llega a la base de datos se genera unpaquete de respuesta cuya longitud está distribuida exponencialmente con valor medio 10000 bits yque la generación de respuestas por la base de datos sigue un proceso de Poisson:

c) ¿Cuál es el tiempo medio de respuesta a una petición desde la base de datos hasta un terminal de lared de acceso ALOHA ranurada (Trespuesta)?

Solución

a) Estudiamos el acceso al concentradorpaq/s25=λ


(tiempo de sincronismo de ranura)

( –1) colisiones

P 2

llegada

ÉXITO

t

PG S

b) Analizamos la transferencia desde el concentrador a la base de datos

M/G/1

γ

C=33600 bps

γ=19,6657 paq/seg

bits960=L

paq ms/t.6,910·100

9603 ===

vLP

paq trans/t.24,010·6,9·25· 3 === −PG λ

paq paq/t.1888,0· == −GeGS

paq/s6657,19==PSγ

{ }PPB 5 4, 3, 2, 1, de mediovalor ,3=

( ) PBPSGPTaloha ++

−+= 1

2

( )

++

−+= 1311

21·

SGPTaloha

( )

+−+= 141

21· G

aloha ePT

[ ] ms816,24585,2· == PTaloha

bits960=L

02 =Lc

6 Ejercicios de recapitulación 177

i j

6 Ejercicios de recapitulación

Problema 6.1

Un nodo de conmutación dispone de dos enlaces de salida, cada uno de los cuales tiene asociado unbuffer con capacidad para 1 unidad. La utilización de dichos enlaces de salida es de acuerdo con elalgoritmo de la patata caliente, en el cual cada paquete que llega se envía al enlace con menor númerode unidades. Si el número de unidades en ambos enlaces es el mismo, se emplea aleatoriamente uno uotro con probabilidad igual a ½. Supóngase un régimen de llegadas exponencial de tasa λ y serviciosexponenciales de tasa µ1 para el enlace 1 y µ2 para el enlace 2.

a) Dibuje el diagrama de transición de estados del sistema completo.b) Repita dicho diagrama, suponiendo que cuando los enlaces tienen el mismo número de unidades,un nuevo paquete entrante se envía siempre al enlace 1.En el supuesto del caso a), y suprimiendo los buffers de los enlaces:c) Obtenga el nuevo diagrama de transición de estadosd) Calcule las probabilidades en régimen permanente de cada uno de los estados, para los siguientesvalores:

λ = 1 paq/s ; µ1 = 3 paq/s ; µ2 = 2 paq/s

e) Obtenga la probabilidad de que el enlace 1 esté ocupado. Repita para el enlace 2.

Solución

λ

1µ1

1

µ2

a) Denotando

i ≡ unidades en 1

j ≡ unidades en 2

Se obtiene el siguiente diagrama de estados


λ/2

λ

µ1 00

10

01

02

11

20

µ2

µ2 λ/2

µ1

λ/2

λ

µ1

21

12

22 µ2

λ/2 µ1

λ

µ2

λ

λ µ1 µ2

µ2 λ µ1

b) Tan solo hay que cambiar las salidas de los estados 00 y 11

λ

µ1 00

10

01

11

µ2

λ µ1

21

12 µ2

c) Para el caso a) suprimiendo los buffers

λ/2

λ

µ1 00

10

01

11

µ2

µ2 λ/2

µ1

λ

d)

λ = 1; µ1 = 3; µ2 = 2

Utilizamos tres de las ecuaciones que se obtienen del diagrama de transición de estados más lacondición de normalización de la probabilidad.

01210100 ppp µµλ +=

( ) 101112002 ρµλµλ +=+ pp

( ) ( ) 11210110 ppp µµλ +=+

14

1

=∑=k

kp


Resolviendo se obtiene

e)50,0;1,0

61,0;6,0

1110

0100))

))

==

==

PP

PP

{ }{ } 2,0ocupado2

61,0ocupado1

1101

1110)

)

=+=

=+=

PPP

PPP


Ejercicio 6.2

Un nodo de conmutación dispone de dos enlaces de salida de capacidades C1 y C2, cada uno de loscuales tiene asociado un buffer con capacidades L1 y L2. El tráfico entrante al nodo sigue unadistribución de Poisson de tasa λ, y debe ser encaminado hacia estos dos enlaces de salida. Elencaminamiento hacia dichos enlaces es de tipo aislado, en algunas de sus variantes. La longitud delos paquetes entrantes está distribuida exponencialmente, con media L = 1200 bits. Definiendo elestado del sistema conmutador completo de la siguiente forma:

(número de paquetes en enlace+cola 1, número de paquetes en enlace+cola 2)

Dibuje los diagramas de transición de estados en los siguientes casos:

a) Encaminamiento mediante inundación, con L1 = L2 = ∞ y C1 = C2.b) Encaminamiento aleatorio equiprobable, con L1 = L2 = 1 y C1 = C2.c) Encaminamiento proporcional, con C1 = 2C2 y L1 = L2 = 0.- Si los dos enlaces están vacíos, se envía una fracción α del tráfico al enlace 1, y una fracción (1- α)al enlace 2, con α ∈ [0,1].- Si un enlace está ocupado y el otro libre, se envía siempre al enlace libre.d) Para el caso anterior, y tomando λ = 1 y C2 = 1200 bps, obtenga una expresión para la probabilidadde pérdida del nodo en función de α, y represéntela gráficamente para el intervalo α ∈ [0,1].

Solución

El nodo dispone de dos enlaces, cada uno con su propio buffer de espera asociado

λ

L1µ1

L2

µ2

a) Encaminamiento mediante inundación, con L1 = L2 = ∞ y C1 = C2

λ

∞C

C

λ

λ

En este caso cada paquete que llega al nodo se retransmite por los dos canales

LC1

1 =µ

LC2

2 =µ


00

λ

µ

11

λ

µ

22

λ

33

λ

µ µ

b) Encaminamiento aleatorio, con L1 = L2 = 1 y C1 = C2.

Cada uno de los canales disponde de una sala de espera con espacio para un paquete. Cada vez quellega un paquete nuevo, se envía con probabilidad 1/2 al canal 1 y con probabilidad 1/2 al canal 2.

C

C

λ/2

λ/2

λ/2

λ/2

µ 00

01

10

20

11

02

µ

µ λ/2

µ

λ/2

λ/2

µ

12

21

22 µ

λ/2 µ

λ/2

µ

λ/2

λ/2 µ

µ λ/2 λ/2

µ

µ λ/2

c) Una proporción del tráfico se envía a cada enlace. Sin embargo, si un enlace está ocupado y el otroestá libre, se utiliza el enlace libre.

C1 = 2 C2

L1 = L2 = 0

λ

C1

C2

αλ

(1-α)λL

C22 =µ

LC1

1 =µ


(1-α)λ

λ µ2

00

01

10

11

µ1

µ1

αλ µ2

λ

d) λ = 1; C2 = 1200 bps (µ2 = 1; µ1 = 2)

Debemos encontrar la probabilidad de que los dos enlaces estén ocupados, p11, en función de α. Paraello resolveremos el siguiente sistema de ecuaciones

Utilizando además la condición

Se obtiene

La probabilidad buscada, p11, es por tanto

α p11

00,250,5

0,751

0,1360,1310,1250,1180,111

( )[ ] 101012001 ppp µµλαλα +=+−

( ) ( ) 11100012 1 ppp µλαµλ +−=+

( ) 11200101 ppp µλαµλ +=+

( ) ( )10011121 ppp +=+ λµµ

1=∑ ijp

00100011

000100

1031;

103

534;

2115

pppp

ppp

αα

αα

+=

−=

−=

−=

αα

ααα

4223

2115

103;

103

110011 −−

=−

−=

−= ppp


Problema 6.3

El percentil r,π (r) de una variable aleatoria se puede calcular como

Donde m y σ son, respectivamente, la media y la desviación típica de dicha variable.

Calcular k(r) cuando la variable aleatoria es exponencial.

Solución

Sea f(t) la función de densidad de la variable aleatoria exponencial.

El valor π(r) se calcula como se indica en la figura y fórmula adjuntas.

Operando

Y despejando π(r)

Teniendo en cuenta que, para variables aleatorias exponenciales,

Se tiene

Así

Por ejemplo

( ) ( )σπ rkmr +=

( ) 100100 rdte

r

t −=∫

∞ −

π

γγ

( )100

100 re r −=− πγ

( )r

r−

=100

100ln1γ

π

σγ

== m1

( ) σγ

π

−

−+=

−

−+= 1

100100ln1

100100ln11

rm

rr

( ) 1100

100ln −−

=r

rk

( ) 3,190 =k

( ) 295 =k


Problema 6.4

Calcular los percentiles 90 y 95 del tiempo de respuesta en el acceso del terminal T a la base de datosBD de la figura.

NL

t3

NR

t6

DITt2t1

t8 t7

t4

t5

H BD

WAN

T: terminalDI: Dispositivo de interconexiónNL: Nodo localNR: Nodo remotoH: HostBD: Base de datos albergada en el host

Despreciando el tiempo de consulta a la base de datos, el tiempo de respuesta, t, está compuesto porocho sumandos, a saber:

t1 : tiempo de acceso del terminal al dispositivo de interconexiónt2 : tiempo de transferencia (espera + transmisión) desde el dispositivo de interconexión al nodo localt3 : tiempo de tránsito en la red de área extensa (extremo a extremo)t4 : tiempo de transferencia desde el nodo remoto al servidor que alberga la base de datost5 : tiempo de transferencia desde el servidor al nodo remoto (nodo local para el host)t6 : tiempo de tránsito a la red de área extensat7 : tiempo de transferencia desde el nodo local al dispositivo de interconexiónt8 : tiempo de transferencia desde el dispositivo de interconexión al terminal

Suponer que las variables aleatorias anteriores son exponenciales y que sus valores medios son (enmsg)

T1 = 80, T2 = 32, T3 = 125, T4 = 9

T5 = 30, T6 = 125, T7 = 143, T8 = 127

Solución

Det = t1 + t2 + t3 + t4 + t5 + t6 + t7 + t8

deducimos que

T = T1 + T2 + T3 + T4 + T5 + T6 + T7 + T8 =


= 80 + 32 + 125 + 9 + 30 + 125 + 143 + 127 = 671

Para el cálculo de los percentiles, se usará la fórmula obtenida en un problema anterior, a saber

dondem = 671

Para calcular σ, se supondrá que las ocho variables anteriores son incorreladas. Así

= 802 + 322 + 1252 + 92 + 302 + 1252 + 1432 + 1272 = 76233

ya que, para variables aleatorias exponenciales, la media y desviación típica coincidennuméricamente.

Por lo tanto

Finalmente, se tiene

y

Así, aproximadamente

( ) ( )σπ rkmr +=

( ) 3,190 =k

( ) 295 =k

( ) s190 =π

( ) s25,195 =π

( ) ms1223276*267195 =+=π

( ) ms1030276*3,167190 =+=π

27676284 ==tσ

22222222287654321 ttttttttt σσσσσσσσσ +++++++=


Problema 6.5

Los terminales conectados al concentrador de la figura hacen consultas a la base de datos dibujada arazón de 9 paquetes/s. Similarmente, la tasa de generación de paquetes de consulta en los demás nodoses la indicada.

20

Servidor BD

WAN

3 2

1

5

9Concentrador

Term.1Term.10

120 Km

10 Terminales

Calcular el tiempo de respuesta bajo las condiciones que se detallan a continuación.

- Sondeo centralizado y explotación semidíplex del enlace multipunto- Capacidad de enlace multipunto, 28800 bps- Capacidad del enlace de acceso a la red de transporte, (del concentrador al nodo), 19200 bps- Capacidad del enlace entre el nodo de la red de transporte y el servidor, 64000 bps- Tiempo de tránsito (extremo-extremo) en la red de transporte, 125 ms- Longitud de los mensajes de sondeo, 96 bits- Longitud de los mensajes de respuesta negativa por parte del terminal, 48 bits- Velocidad de propagación de las señales, 200000 Km/s- Longitud de los mensajes de pregunta, 60 bytes- Longitud de los mensajes de respuesta, 150 bytes

Las longitudes de los mensajes de pregunta y respuesta están distribuidas exponencialmente.Despreciar el tiempo de consulta de la base de datos.

Solución

Usando la misma notación de un problema anterior,

Tc(0) = n TMS + n TRN + n (n+1) Tp

s057,0200000

1211·1028800

481028800

9610 =++=

ρ21

)0(

−= C

CT

T


donde

ya que a cada pregunta le correponde una respuesta.

Substituyendo

Como se ha indicado en un problema anterior, el tiempo de respuesta incluye 8 componentes. Con lamisma notación de dicho problema, T1 se calcula así:

Cálculo de T8

El cálculo de T2, T4, T5 y T7 se resume en la tabla adjunta.

T2 T4 T5 T7

C 19200 64000 64000 19200L 60 · 8 = 480 bits 480 bits 150 · 8 = 1200 bits 1200 bitsλ 9 20 20 9

CLTS = 0,025 0,0075 0,019 0,0625

STλρ = 0,225 0,15 0,376 0,5625

ρ−=

11

STT32 ms 9 ms 30 ms 143 ms

2RESPPREG ρρ

ρ+

=

2RESPPREG TT λλ +

=

2RESPPREG TT += λ

261,028800

8·15028800

8·60219 =

+=ρ

ms120261,021

57=

⋅−=CT

1785,015,01760

288008·60

288008·6091

288008·609

288008·60

2120

121 ++=+−

+=+−

+= PREGPREG

PREGPREG

C TTT

Tρ

ρ

ms8017360 =++=

ms12728800

8·150

288008·15091

288008·1509

288008·150

2120

128 =+−

+=+−

+= RESPRESP

RESPRESP

C TTT

Tρ

ρ


Finalmente, el tiempo de respuesta a la pregunta formulada al servidor es

T = 80 + 32 + 125 + 9 + 30 + 125 + 143 + 127 = 671 ms

T = 671 ms


Problema 6.6

A un nodo de conmutación llegan paquetes de forma Poissoniana con una tasa λ = 20 paq/s. Lalongitud de dichos paquetes ( l ) está distribuida uniformemente entre 0 y L, siendo L = 55000 bits.Los paquetes se transmiten a través de un enlace de capacidad C = 1 Mbps, el cual dispone de unbuffer que puede considerarse infinito. Para dicha transmisión se utiliza un protocolo el cualfragmenta los paquetes si estos superan la longitud B = 33000 bits, y además les añade una cabecerade H = 500 bits. Así pues:

- A cada paquete de longitud l (siendo l ≤ B) se le añade una cabecera formando una trama delongitud H + l .- Si l es superior a B, los paquetes se fragmentan formando dos tramas de longitudes H + B y H +l -B respectivamente.

Obsérvese que a efectos prácticos, el enlace de salida observa las dos tramas correspondientes a unpaquete fragmentado como una única trama de longitud 2H + l , ya que ambas tramas se generansimultáneamente. Teniendo en cuenta esta observación podemos afirmar que al buffer del enlacellegan dos tipos de tramas:

- Tipo 1: tramas de longitud l 1 = H + l con l ≤ B.- Tipo 2: tramas de longitud l 2 = 2H + l con l > B.

a) Calcular la probabilidad de que un paquete que llega al nodo, sea fragmentado.b) Determine la función de densidad de probabilidad para las variable aleatorias l 1 y para la variablel 2.c) Calcule el primer y segundo momento del tiempo de transmisión para las tramas de tipo 1 y lastramas de tipo 2.d) ¿Cuál es la probabilidad de que el enlace esté ocupado con una trama que contiene un paquete queno ha sido fragmentado?e) Calcule el tiempo medio de espera en el buffer de una trama.f) ¿Cuál es el tiempo medio desde que un paquete de longitud menor que B llega al nodo y esfinalmente transmitido? ¿Y si el paquete es mayor que B?. Supóngase que el tiempo de procesado delos paquetes (encaminamiento, segmentación, entramado del paquete, etc.…) es nulo.

Solución

a) La probabilidad de que un paquete sea fragmentado es la probabilidad de que un paquete que llegaal nodo de conmutación tenga una longitud superior a B.

b) La longitud de los paquetes de tipo 1 está distribuida uniformemente entre H y H + B. La longitudde los paquetes de tipo 2 está distribuida uniformemente entre 2H + B y 2H + L.

c) Teniendo en cuenta que el primer y segundo momento de una variable aleatoria distribuidauniformemente entre a y b valen

( ) ( ) 4,011 =−=≤−=>LBBpBp ll

( ) ( ) ( ) ( )ababxE

ababxE

−−=

−−=

3;

2

332

22


Se obtiene

d) La tasa de llegada de paquetes de tipo 1 es

La probabilidad de que el servidor esté ocupado con paquetes de tipo 1 es

e)

f) Si l ≤ B

Si l > B

( ) ( ) ( ) ms172

221

1 =−+==CB

HBHC

ExE l

( ) ( ) ( ) 242

33

2

212

1 s10·8,33

−=−+

==CB

HBHC

ExE l

( ) ( ) ( ) ( )( ) ms45

222 22

22 =

−+−+

==CBL

BHLHC

ExE

l

( ) ( ) ( ) ( )( )

232

33

2

222

2 s10·065,23

22 −=−

+−+==

CBLBHLH

CExE l

( ) paq/s1220·6,011 ==≤== λλλ Bpp l

( ) 204,010·17·12 3111 === −xEλρ

( )( )ρ

λ−

=12

2xEW

( ) ( ) ( ) 2334222

211

2 s10·054,110·065,2·4,010·8,3·6,0 −−− =+=+= xEpxEpxE

( ) ( ) ( ) s10·2,2810·45·4,010·17·6,0 3332211

−−− =+=+= xEpxEpxE

( ) 564,010·2,28·20 3 === −xEλρ

( ) ms17,24564,012

10·054,1·20 3

=−

=−

W

( ) ms17,41ms17ms17,2411 =+=+= xEWT

( ) ms17,69ms45ms17,2422 =+=+= xEWT


Problema 6.7

Se desea interconectar dos redes de área local (LAN) geográficamente separadas y que utilizandistinto subnivel de acceso al medio compartido, tal como se muestra en la figura. Para ello, seutilizará alguno de los dispositivos de interconexión de redes estudiados, y se supone que dichodispositivo de interconexión ya lleva incorporado el módem o la unidad de servicio de datosnecesarios para la interconexión remota.

Disp. Interconnexión Disp.

Interconnexión

Token-Ring LAN

IEEE 802.5

Ethernet LAN IEEE 802.3

Estación

Estación

Medio de Transmisión

a) Si el medio de transmisión entre los dispositivos de interconexión es una única línea dedicada puntoa punto, ¿qué tipo de dispositivo utilizaría? ¿Y si dicho medio es una red de conmutación depaquetes? Justifique ambas respuestas.

Supóngase que el tráfico dirigido de una LAN a otra es poissoniano, y que el número medio de tramasenviadas es de 21600 durante las 8 horas diarias en que están activas. La longitud media de las tramas,que sigue una distribución exponencial, es de 1200 octetos, y son transportadas por un único enlace decomunicación full-duplex. Se supone también que la capacidad de memoria en los dispositivos esinfinita y que el tráfico es el mismo en ambos sentidos de la comunicación con lo que basta hacer loscálculos en uno de los sentidos. Con estos supuestos responda las siguientes cuestiones:

b1) ¿Qué modelo de colas caracteriza el sistema?b2) Calcule la tasa de llegadas en tramas/segundo.b3) Obténgase la capacidad (C) del enlace para que la probabilidad de que el sistema esté vacio seadel 62,5 %b4) Calcule el número medio de unidades en el sistema y en la cola.b5) Calcule el tiempo medio de permanencia en el sistema y en la cola.b6) ¿Cuál es la probabilidad de tener 8 o más tramas en el sistema del dispositivo de interconexión?

Considérese ahora que el dispositivo de intercoxión posee dos puertos de salida, cada uno de loscuales se conecta a un enlace de capacidad C/2, siendo C la capacidad del enlace calculada en elapartado anterior. La memoria del dispositivo se asume como una única cola de longitud infinita. Eneste nuevo escenario:

c1) ¿Qué modelo de colas caracteriza a este nuevo sistema? Dibuje el diagrama de transición deestados del sistema.c2) Calcule el factor de utilización.c3) Obtenga la expresión de la función generadora de momentos G(z) partiendo de las ecuaciones debalance de flujos del sistema en régimen permanente.c4) Utilizando la función generadora de momentos, obtenga la probabilidad de que no haya ningunatrama almacenada en el sistema y el número medio de unidades en el sistema.c5) Calcule el tiempo medio de permanencia en el sistema.c6) Compare el número medio de tramas y el tiempo medio de permanencia en el sistema con losobtenidos en el esquema de interconexión anterior. Justifique el porqué de dichos resultados.


Nota

( ) ( )[ ]01

01

11 ···· pzGzzpzGzzp

n

nn

n

nn −== −

∞

=+

∞

=− ∑∑

Solución

a) Debe ser un dispositivo que permita la interconexión de redes con tecnologías diferentes (distintosformatos de trama, distintas velocidades, etc). En el caso de utilitzar una línia dedicada punto a puntose puede utilizar un puente (bridge) y realizar la interconexión a nivel de enlace.

Si la interconexión se realiza pasando por una red de área extendida usando conmutación depaquetes, donde intervienen distintos nodos, lo acertado sería utilizar un encaminador (router) a nivelde red ya que el encaminamiento de las tramas será obligatorio. Si hubiera que hacer conversión deprotocolos a nivel de transporte o superiores se necesitaría una pasarela (gateway).

b1) Las entradas siguen una distribución de Poisson (M). octetos1200=L y distribuidaexponencialmente, luego el servicio es exponencial (M). Sólo un enlace, por tanto un único servidor.El sistema puede caracterizarse mediante un modelo M/M/1.

b2)

b3) En este caso la probabilidad de que el sistema esté vacío es p0 = 0,625. En un sistema M/M/1

b4) 6,01

=−

=ρ

ρN tramas en media en el sistema

En el subsistema cola habrá que restar las unidades en el servidor cuyo número medio coincide con elfactor de utilización.

b5) Basta aplicar Little

s8,0==λNT (tiempo medio de permanencia en el sistema)

s3,01=−=−=

µTxTWq (en cola)

tramas/s75,0h

s3600·h8tramas21600 ==λ

LCp ==−= µ

µλρρ ;;10

bps192001 0

=−

=pLC λ

375,0=ρ

tramas225,0=−= ρNNq


b6) En un sistema M/M/1 la probabilidad de que hayan k unidades en él es

y la probabilidad de que el número de unidades sea igual o superior a un determinado valor n es

c1) El modelo que caracteriza ahora al sistema es M/M/2. Cada enlace opera a 9600 bps y la tasamedia de servicio trama/s1'=µ

λ

µ’

µ’

Diagrama de transición entre estados.

0

λ

µ’

1

λ

2µ’

2

λ

k

λ

2µ’ 2µ’

λ

2µ’

c2) Denotando por s el número de servidores

c3) Partiendo de las ecuaciones de balance de flujos en régimen permanente (por inspección deldiagrama de estados), se tiene

Para k = 0

01 'pp

µλ

= (1)

Para k = 1

( ) 02

2 ·'2 pp ρ= (2)

( ) kkp ρρ ·1−=

( ) 1si <==≥ ∑∞

=

ρρ n

nikpnkp

( ) ( ) 48 10·9107,3375,08 −≈=≥kp

L

C2'=µ

375,0'

' ==µλρ

s


Para k ≥ 2

( ) 11 '2'2 +− +=+ kkk ppp µλµλ (3)

La función generadora de momentos es

Recordando las propiedades de dicha función

1-

2-

3-

4-

5-

Teniendo encuenta (1) y (2) y multiplicando cada término de (3) por zk y sumando para k de 2 a ∞ , setiene (aplíquense también las propiedades 4 y 5)

Operando

dividiendo numerador y denominador por ( )11'2 −− zµ y sabiendo que '2

';11

1 µλρ =−=

−−

−z

zz

c4) Aplicando la propiedad 1

( ) ∑∞

=

≅0

·n

nn zpzG

( ) 110

== ∑∞

=nnpG

( ) ( )nEpnzdzGd

nn

z

== ∑∞

== 01

·

( ) ( ) ( )nEnEzd

zGd

z

−==

2

1

2

( )zGzzpn

nn ·

11 =∑

∞

=−

( )[ ]01

01 pzGzzp

n

nn −= −

∞

=+∑

( ) ( )[ ] ( )[ ] ( )( )[ ]zpppzGzzpzGzzppzG ·'2'2 2101

010 −−−+−=−−+ −µλµλ

( ) ( ) ( )( ) ( )1

1

0 1'211'21

−

−

−+−−+−−

=zzzzpzG

µλµλ

( )zzpzG

'1'1

0 ρρ

−+

=

54,0'1'1

0

)=

+−

=ρρp


Aplicando la propiedad 2 se obtendrá el número medio de unidades en el sistema

c5) Por Little

c6) Para M/M/1

Para M/M/2

Resulta mejor el sistema M/M/1 con un enlace a doble velocidad. Intuitivamente es fácil de explicar:hasta situarse en condiciones de baja carga, las pocas tramas a cursar en el sistema M/M/2 se asignana uno de los dos servidores con un tiempo de servicio mayor. Por tanto, se tarda más en realizar latarea y consecuentemente como λ es la misma, se acumulan más tramas en el sistema.

( ) tramas873,0≈= nEN

s164,1==λNT

tramas6,0=N

s8,0=T

tramas873,0=N

s164,1=T


Problema 6.8

Considérense tres redes de área local independientes, con los parámetros que se indican en la siguientetabla:

Red Método deAcceso

Longitud paquetes(cte)

Capacidad Retardo máximo depropagación

1 Aloha 1000 bytes 4 Mbps Despreciable2 Aloha ranurado 1500 bytes 4 Mbps Despreciable3 CSMA 1500 Bytes 10 Mbps 1.2 10-5 s

Cada una de las redes tiene conectado un número que puede suponerse infinito de estaciones,generando paquetes según un régimen de Poisson con media 100 paquetes/segundo. Dicho régimen degeneración incluye tanto los paquetes de nueva generación como las retransmisiones producidas porlas colisiones en el acceso.

a) Obtenga el número de paquetes por segundo transmitidos correctamente en cada una de las redespor separado.Los paquetes transmitidos correctamente por las tres redes se envían a un centro de control a través dedos enlaces de capacidades CA = 1 Mbps y CB = 4 Mbps. Al enlace A se envía una fracción α igual al20 % del total, y el resto al enlace B, como se muestra en la figura. Los buffers de espera asociados alos enlaces pueden considerarse de longitud infinita.b) Obtenga el coeficiente cuadrático de variación del tiempo de servicio de los paquetes en el canal A.c) ¿Cuál es el valor de dicho coeficiente en el canal B?d) Obtenga el número medio de unidades en el sistema formado por los dos canales con sus buffers deespera asociados.e) Obtenga el retardo medio de los paquetes en el buffer asociado al enlace A, E(WA), y en el bufferasociado al enlace B, E(WB).f) Obtenga el retardo medio de los paquetes en el sistema formado por los dos canales con sus buffersde espera asociados.g) Suponiendo un tiempo medio de back-off para la red de acceso 1 igual a 20 ms, calcule, para lospaquetes de dicha red, el tiempo medio desde que llegan a la estación para ser transmitidos hasta queson completamente recibidos por el centro de control.

ALOHA

S-ALOHA

CSMA

CA = 1 Mbps

CB = 4Mbps

CENTRO DECONTROL

α

1−α

Solución

a) Red 1, acceso ALOHA, λ = 100 paq/s


Para pasar a transmisiones correctas por segundo volvemos a dividir por P

Red 2, S-ALOHA, λ = 100 paq/s

Red 3, CSMA, λ = 100 paq/s

1211 · GeGS −=

le)despreciabn propagació de Retardo(s002,010·4

8·100061 ==P

2,0002,0·100· 11 === PG λ

paq/t.paq134,0·2,0·2,0 4,02,0·21 === −− eeS

paq/s67002,0134,0

1

11 ===

PSγ

le)despreciabón (propagacis003,010·4

8·150062 ==P

3,0· 22 == PG λ

222,0·3,0· 3,022

2 === −− eeGS G

paq/s74003,0222,0

2

22 ===

PSγ

( ) 3

3

21·

3

33 Ga

Ga

eaGeGS −

−

++=

01,00012,010·2,1 5

3===

−

Pa τ

0012,010·10

8·150063 ==P

12,00012,0·100· 33 === PG λ

( ) 1069,01212,11199,0

9988,01224,01199,0

01,0·2112,0·12,0

0012,0

0012,0

3 ==+

=++

= −

−

eeS

paq/s890012,01069,0

3 ==γ


γ1 = 67 α

γ2 = 74

γ3 = 89

γT = 230

(1 - α)

CA = 1 Mbps

CB = 4 Mbps

b) El coeficiente cuadrático de variación se puede encontrar directamente sobre la longitud de losmensajes. Al canal A llegarán

De esta forma

y

c) El mismo

d) N = NA + NB

M / G / 1 ( )ρρρ−

++=⇒

121 2

2 XCN

( )321321 2,02,02,02,0230·2,0paq/s γγγγγγγα ++=++==T

( ) ( ) =++=++= 33221133

22

11 1 LLLLLLLE

TTTTA γγγ

γγαγα

γαγα

γαγα

( ) 78261,10834230/249200012000·8912000·748000·672301

==++=

( ) ( ) 2,120695652230/10·277612000·8912000·748000·67230

1 102222 ==++=ALE

22 0281,02,117392514

2,1173925142,120695652XL CC ==

−=

( )A

XAAA

CNρ

ρρ−++=12

1 22

4984,000107,0·230·2,010·1

7826,10834·230·2,0 6 ===⋅= AAA xγρ

4984,0002709,0·230·8,010·4

7826,10834·230·8,0 6 ===⋅= BBB xγρ


Como era de esperar, BA ρρ = ya que al canal 4 veces más lento

= BA CC

41 envíamos una tasa

4 veces menor

= BA γγ

41

Además

e)

f)

g)

Para la retransmisión, tendremos primero una espera en cola de los paquetes de la red 1 mezclados conlos paquetes de las redes 2 y 3.

Por tanto

Para la transmisión, ya sólo tenemos en cuenta paquetes de la red 1

Así

( ) 753,00032,125538,04984,0

4984,0120281,01·4984,04984,0 2 =+=

−+

+=AN

506,1753,0·22 ===⇒= AAB NNNN

( ) s0055,0230·2,0

4984,0753,0=

−=

−=

A

AAA

NWEγ

ρ

( ) s0014,0230·8,0

4984,0753,0=

−=

−=

B

BBB

NWEγ

ρ

s0065,0230506,1

===γNT

IÓNRETRANSMISALOHAredpaq TTT +=1

( )( ) ( )( ) =+−+=+−+= 02,0002,01002,01 4,011

21

1 eBPePT GALOHA

s0128,0022,0·492,0002,0 =+=

( ) ( ) ( ) s00222,00014,0·8,00055,0·2,08,02,0 =+=+= BA WEWEWE

s0032,00016,00016,010·4

8000·8,0108000·2,08,02,0 66111 =+=+=+= BA xxx

s01822,00032,000222,00128,01 =++=redpaqT


Ejercicio 6.9

Un conjunto elevado de usuarios accede a un servidor de WWW mediante un sistema de acceso por laRDSI a 64 Kbps. El acceso al servidor WWW desde la RDSI se realiza mediante un gateway quedispone de 3 accesos básicos de 64 Kbps y un enlace dedicado de 64 kbps que lo conecta directamentecon el servidor de WWW.

PC

PC

PC

RDSI

... GWSERVIDOR

WEB64 Kbps

64 Kbps

64 Kbps

64 Kbps64 Kbps

64 Kbps

64 Kbps

Los intentos de conexión de los usuarios son caracterizables por un proceso de Poisson de tasa α =1/30 min y el tiempo de conexión de un usuario está distribuido exponencialmente con valor medio1/µ = 3 min. Una vez se ha conectado un usuario a través de la RDSI genera peticiones al servidorWWW con una distribución de Poisson de tasa α = 0,1 peticiones/s. Las respuestas del servidor deWWW son paquetes que siguen una distribución de exponencial de longitud media L = 10000 bits.

Teniendo en cuenta que:

- Un usuario conectado al gateway no formulará una nueva petición hasta que no haya llegado larespuesta completa de la petición anterior.- Los paquetes de petición dirigidos al servidor de WWW son de longitud muy reducida de forma quelos tiempos de transmisión en los enlaces son despreciables.- El tiempo de propagación en los enlaces y el tiempo de proceso de los dispositivos se puedeconsiderar despreciables- El gateway actúa simplemente como repetidor cuando retransmite los bits de los paquetes derespuesta hacia el equipo del usuario destinatario sin introducir nigún retardo apreciable- El servidor de WWW atenderá las peticiones con disciplina FIFO. Si el servidor tiene variaspeticiones en espera la respuesta a una petición se iniciará posteriormente a que el paquete derespuesta de la petición anterior haya llegado a su destinatario

Responda a las siguientes cuestiones:

a) Determine la probabilidad de que un usuario no pueda conectarse a través de la RDSI con elgateway

b) Calcule el tiempo de transmisión (1/β) de una respuesta desde el servidor de WWW hasta elusuario destinatario

c) En el caso de que hayan 3 usuarios conectados simultáneamente al gateway utilizando los 3accesos de 64 Kbps y suponiendo que no se producen pérdidas de información, halle el tiempomedio desde que un usuario cualquiera genera una petición hasta que el paquete de respuesta llegacompletamente al usuario

d) Determine el percentil al 99'9% de la longitud en bits de un paquete de respuesta


Solución

a) Modelo M/M/m/mPoblación infinita con tasa -1min30

1=λDuración de la conexión distribuida exponencialmente con tasa

Número de servidores m = 3

Luego

b)

c) Modelamos el sistema de peticiones como un M/M/3//3

0

3α

β 1

2α

β

2

α

β

3

M = 3

Substituyendo

p0 = 0,9538

p1 = 0,0447

-1min31=µ

∑=

== m

0j !1!

1

j

m

mB

j

mpP

µλ

µλ

( )

( )4

3

0j

3

3 10·5,1

101

!1

101

!31

−

=

===

∑j

B

j

pP

bits10000=L

pet/s4,6ms156Kbps6410·101

3

=⇒=== ββ vL

pet/s1,0=α

pet/s4,6=β

( )∑= −

= M

k

k

kMM

p

0

0

!!

1

βα

( )!!

0 kMMpp

k

k −⋅

= βα


p2 = 0,0014

p3 = 2,2 ·10-5

c) El tiempo medio de servicio de una petición lo obtendremos con la fórmula de Little

N = 0 · p0 + 1 · p1 + 2 · p2 + 3 · p3 = 0,04756

Substituyendo

T = 161,1 ms

d) El percentil a 99,9% de la longitud de los paquetes será:

210 23y pppNT ααααα

++==

pet/s295,0=α

( ) l

l LL e

Lf

11 −=

( )999,019,99

0

1

=∫Π −

ll

deL

L

( ) ( )001,0ln9,99 L−=Π

( ) bits690789,99 =Π

[ebook] edicions upc - redes, sistemas y servicios de comunicacion. problemas resueltos - spanish...

Documents