Problema 3. (Problema 5.16 de [Klei76])

Considere una red de comunicaciones ideal con N=4 nodos para la cual es aplicable el modelo M/M/1. Si suponemos que µ = 1 y las siguientes matrices de tráfico ( ) y de enrutamiento (rij) donde rij = número del siguiente nodo a
visitar si el mensaje está en el nodo j y tiene como destino final el nodo i.
 

 1. Calcular la longitud media del camino, .

2. Si la capacidad global es C = C_i = 34, encontrar la asignación de capacidades {C_i} que minimiza el retardo de tránsito, T.

3. Dibujar la red y etiquetar cada enlace con una flecha y el par (, C_i).

4. Evaluar T.

5. Si se define la longitud de un canal como:
 

a) Encontrar la longitud de todos los caminos entre el nodo 1 y el nodo 3 e identificar cual es el más corto.

b) ¿Se usa ese camino par cursar el tráfico ? ¿Sería la misma su respuesta si trabajase con redes óptimas?

6. Suponga que cambia la matriz de enrutamiento por la siguiente:
 

Si tenemos la misma matriz , µ y C, y hacemos una asignación óptima de capacidades. ¿Cuál sería el nuevo valor de T?
 
 

Solución Problema 3
 
Apartado 1:

En primer lugar obtenemos los árboles de encaminamiento, para obtener de forma sencilla el número de saltos que hay en un camino:
 
 

 
Para hacer estos árboles, partimos del nodo 1, y voy desde él a los otros nodos, miraré los elementos de la matriz de enrutamiento de la forma ri1, además de algunos otros elementos intermedios, en este caso r32, ya que r31 vale 2, es decir, para ir al nodo 3 desde el 1 pasaré por el 2, y de ahí al 3 voy directamente. De esta forma confeccionamos los árboles y les asignamos nombre a los enlaces, de los que luego calcularemos más parámetros.

Sabemos que:

 
dando valores obtenemos:

 = 16
 

donde n_jk  es la longitud de un camino, el número de canales que atraviesan los mensajes que lo siguen. También se le denomina número de saltos. Lo hemos obtenido de los árboles de encaminamiento.
   

Apartado 2:

Suponiendo una función de costes en la red constante conocemos la expresión de las capacidades de cada enlace (meter enlace a 2.3.4 de los apuntes de teoría):
    donde los M posibles enlaces son: a, b, c, d, e, f.

De esta fórmula conocemos los siguientes datos:

  = 1
 C = 34
= 16 / 34

, donde i es un canal incluido en el camino .

Aplicando esto la fórmula se nos reduce a:

Haciendo esto con todos los enlaces, obtenemos finalmente:

C_a=6, C_b=6, C_c=6, C_d=12, C_e=2 y C_f=2 , verificándose: C_T=34
 

Apartado 3:

Con los datos de los anteriores apartados podemos dibujar:
   

Apartado 4:

Para evaluar el retardo tenemos la expresión siguiente, de la que conocemos todos los datos, obtenemos:

Siendo las unidades del retardo segundos, dadas las unidades de los otros parámetros.
 

Apartado 5:

a) Tenemos que la distancia se mide de la siguiente forma:

                                                    l_i=

Confeccionamos un grafo de la red en el que esten todos los posibles caminos del nodo 1 al nodo 3: Tenemos tres caminos posibles,
 

Calculamos la longitud de los enlaces: Obteniendo unos caminos con longitud:

Camino A = la + lc = 6/32 = 3/16 Camino B = lb + lf = 3/32 + 4/32 = 7/32 Camino C = lb + le + lc = 3/32 + 4/32 + 3/32 = 10/32 = 5/16

Por lo tanto el camino más corto entre los nodos 1 y 3 es el Camino A: Camino A

b) No necesariamente, ya que el algoritmo de encaminamiento no está definido, por lo tanto puede ser cursado por ese camino o puede que no. Si trabajásemos con redes óptimas, sí se cursaría el tráfico  por ese camino, ya que sería el que minimiza el uso de recursos de la red.
 

Apartado 6:

De la nueva matriz de enrutamiento podemos obtener el grafo de la red:

De este grafo podemos concluir que el número medio de saltos en la nueva red será un único salto, ya que todos los nodos están conectados con el resto en ambos sentidos. Con esto, la expresión de los tráficos internos en cada canal i
() sólo depende de la tasa de llegada de mensajes externos (), siendo ese j y ese k los nodos origen y destino del enlace, el tráfico interno sólo depende de ese único término. Mirando la matriz de tráfico tendremos ocho enlaces con tráfico interno 1, dos enlaces con tráfico interno 2, un enlace con tráfico interno 4 y un enlace con tráfico interno 0 (los elementos de la diagonal principal de la matriz no los considero porque no son enlaces). Con esto podemos calcular:
   
 

Calculamos ahora las capacidades de los enlaces clasificándolos según su tráfico interno:

Y aplicando la expresión del retardo: