 | |
REDESII | | |
 TEST 2
Problemas. (Enunciados).
Se permiten libros y apuntes.
Problema 1
Se pretende construir una red de conmutación de paquetes con cinco nodos. Se barajan dos posibles topologías:
Se sabe que el tráfico ofrecido entre cada par de nodos es 
=10 mensajes/seg 
0 y que el tamaño medio de los mensajes es de
1/
=100 bits/mensaje. Suponga que el coste de cada canal i es di = 10 pesetas/bps y Ci la capacidad
del canal en bps
(bits/segundo). Suonga que dispone de un presupuesto total D = 1.000.000 pesetas.
Se pide:
1.- Sabiendo que el encaminamiento se hace por menor número de saltos,
calcule para ambas topologías las rutas de
distancia mínima entre el nodo A y el resto de los nodos de la red. No es necesario que aplique los
algoritmos de Dijkstra ni
Bellman_Ford .
2.- Utilizando este encaminamiento, calcule el retardo medio
de tránsito que se obtendría con cada una de las
topologías si se hiciera asignación óptima de capacidades ¿Cuál es mejor ? .
3.- ¿ Qué otra topología propondría usted para interconectar
esos cinco nodos si se deseara mejorar aún mas las
prestaciones ? Diga ventajas e inconvenientes de la topología propuesta por usted frente a las de arriba
.
Soluciones.
Problema 1
1.- Dado que el encaminamiento es por menor número de saltos desde A, por simple inspección tenemos
que:
No existe otra posibilidad que nos dé un menor número de saltos.
2.- Los costes son constantes (d=10 DÓLARES/bps). En este caso, para un reparto óptimo de capacidades,
el retardo medio es:
con : 
Presupuesto: 
Para la topología 1 tenemos, por simetría en la red y en el tráfico:
Para la topología dos tenemos:
En cuanto a retardo la segunda topología es mejor, sin embargo esta topología es mas compleja y requiere
mayor
mantenimiento en los nodos.
3.- Una posible solución sería una topología en estrella:
Con este tipo de topología reducimos el número de canales con respecto a la segunda
topología y el número medio de saltos con respecto a la primera. A cambio tenemos más canales que en
la primera y mayor número medio
de saltos (
)que en la segunda. Ademas, hacemos que el nodo central curse todo el
tráfico. Esto hace que el nodo sea complejo y caro, crítico para el funcionamiento de la red. Un fallo
en el nodo central
supondría la inutiización completa de la red.
Problema 2.
Considere la red de la figura, en la que todos los enlaces son bidireccionales y tienen el mismo coste
en ambos sentidos.
1. Usando el algoritmo de Dijkstra, calcule la ruta de mínimo coste del nodo A al resto de los nodos
.
2. Haga lo mismo empleando el algoritmo de Bellman-Ford. ¿Cuántas iteraciones son necesarias? ().
Solución
Problema 2
1.- Calculamos, usando el algoritmo de Dijkstra, la ruta de coste mínimo del nodo A al resto de los
nodos.
Consideraremos dos conjuntos de etiquetas de nodos: P (distancias permanentes) y T (distancias temporales).
Inicialmente todos los nodos están en
T, menos el nodo origen, en este caso el nodo 1. El objetivo es pasar los nodos de T a P. Esto lo haremos
mediante los siguientes pasos:
0.- Iniciación: P={A} T={B,C,D,E,F}
Djk={0,1,_,_,_,4}
1.-Incluimos en P el nodo "más cercano"n y si las distancias pasando por ese nodos son menores,
se toman como nuevas distancias.
P={A,B} T={C,D,E,F}
Djk={0,1,4,_2,4}
2.-Repetimos el proceso hasta incluir todos los nodos.
2.1.- P={A,B,E} T={C,D,F}
Djk={0,1,4,6,2,3}
2.2.- P={A,B,E,F} T={C,D}
Djk={0,1,4,6,2,3}
2.3.- Incluir C y D, como ocurre en el caso anterior, tampoco cambia nada, por lo que
nos queda definitivamente:
P={A,B,C,D,E,F} T={}Djk={0,1,4,6,2,3}
La complejidad es de orden N2 para un nodo y de orden N3 para todos los
nodos.
2.- Ahora realizamos lo mismo que en apartado anterior pero usando el algoritmo de Bellman-Ford.
Para cada salto calculamos las distancias en cada nodo.
1er salto:
2º salto:
3er salto:
4º salto:
5º salto:
Son necesarias 5 iteraciones (N-1), que son e número máximo de saltos que se pueden dar en una red de
6 nodos sin pasar
dos veces por el mismo nodo. Aunque en este caso no hayan habido cambios en las dos últimas iteraciones,
hasta no haber
completado las 5 iteraciones no podemos asegurar que tenemos las rutas de coste mínimo.
A pesar de ser N-1 iteraciones, este algoritmo encierra mayor complejidad que le de Dijkstra, ya que
para cada iteración tenemos complejidad N2,
es decir, complejidad N3 para cada nodo y N4 para todos los nodos.
| 
