Problemas de Arquitectura de Redes, Sistemas y Servicios 3o Ingenier de Telecomunicacin a o Hoja de problemas 7

Figura 1: Red para el problema 7.1 y siguientes

Problema: 7.1 Use el algoritmo de Bellman-Ford para generar la ruta de menor coste a todos los nodos de la gura 1 desde el nodo de origen F. h 0 1 2 3 4 5 6 7 8 Rellene la siguiente tabla con las iteraciones Lh (A) camino(A) Lh (B) camino(B) Lh (C) camino(C) Lh (D) camino(D) Lh (E) camino(E)

b) Suponga que en una red real se usa este algoritmo de enrutamiento y en un instante determinado los nodos de la red se encuentran en la iteracin 3 del algoritmo. Cada nodo establece el siguiente salto para ir al nodo o F como el siguiente nodo en el camino desde l hasta el nodo F que se ha calculado en esa iteracin. e o Cul es el siguiente salto que tiene cada nodo almacenado para ir al nodo F en ese instante? (iteracin 3) a o En A Siguiente salto para paquetes que van al nodo F c) Seg n el apartado anterior, qu camino seguir un paquete que este en el nodo A y tenga como destino u e a el nodo F? Problema 7.2: Use el algoritmo de Dijkstra para generar la ruta de menor coste a todos los nodos de la gura 1 desde el nodo de origen A Rellene esta tabla con las iteraciones No T L(B) camino(B) L(C) 1 {A} 1 A-B 2 3 ... camino(C) L(D) 4 camino(D) A-D L(E) camino(E) L(F) camino(F) En B En C En D En E

Problema 7.3: Use el algoritmo de Bellman-Ford para generar la ruta de menor coste a todos los nodos de la gura 1 desde el nodo de origen A Rellene una tabla como la siguiente con las iteraciones h Lh (B) camino(B) Lh (C) camino(C) Lh (D) 0 1 2 ... camino(D) Lh (E) camino(E) Lh (F ) camino(F)

3 1 D 4 1 A

R1 if0 if1 if2 if3 R2 if0 if1 if2 if3 if4 R3 if0 if1 if2 if3 if4

[Link] [Link] [Link] [Link]

/ / / /

16 30 30 30

[Link] / 16 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 16 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30

R4 if0 if1 if2 if3 O1 if0 if1 if2 O2 if0 if1 if2

[Link] / 16 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 exterior [Link] / 30 [Link] / 30 [Link] / 30 exterior

I1 if0 if1 if2 if3 if4 if5 if6 I2 if0 if1 if2 if3 if4 if5 if6

[Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30 [Link] / 30

Figura 2: Red del problema 7.4

Problema 7.4 Un operador de servicios de internet tiene la red que se ve en la gura 2. Un primer nivel de routers (R1-R4) cerca del usuario dan acceso a diferentes subredes IP. Los routers de este primer nivel estan interconectados con otros routers de primer nivel cercanos. Los routers de primer nivel tienen enlaces a dos routers de interconexin (I1-I2) y estos a dos routers exteriores (O1-O2). Los pesos de los enlaces son como o se ve en la gura 2. Algunos enlaces tienen pesos altos porque no interesa que se usen salvo en caso de rotura de otros enlaces. Los interfaces de los routers se numeran en el sentido de las agujas del reloj y en la gura se indica en cada uno cual es el interfaz if0. En la gura se dan los detalles de los interfaces de cada router En la red se congura un protocolo de enrutamiento tipo link-state de forma que cada nodo recibe toda la informacin de la red y puede calcular los caminos a todas las subredes. o a) Muestre que iteraciones emplea el algoritmo para calcular las mejores rutas desde el nodo R1 a todos los demas nodos y subredes. Trate las redes de acceso como un unico nodo con su correspondiente router y el exterior como un nodo mas

0 2

f .

i 2 0

1 R 0 9 f 1 i 1 I 6 1 / 0 0 f . i 1 0 . R 1 . 0 9 1

ext camino

O1 camino

O2 camino

I1 camino

I2 camino

R2 camino

R3 camino

R4 camino

b) Indique la tabla de rutas que generar el algoritmo de enrutamiento en el nodo R1 para cada una de las a 4 redes y el exterior Subred distancia siguiente salto

c) Que camino seguir un paquete enviado por la direccin 190.1..3.1 a la direccin IP [Link] ? Que camino a o o seguir un paquete enviado por la direccin [Link] a la direccin [Link]? Recorren estos paquetes el a o o arbol de expansion? Razone la respuesta Pregunta 7.5: En la red de la gura tenemos varios nodos cada uno de los cuales est conectado a sus propias a redes. A los enlaces entre nodos se les asigna pesos como se ve en la gura

Suponga que se utiliza un algoritmo de tipo link-state para realizar el enrutamiento. En el nodo B se conoce toda la informacin de enlaces y nodos y se ejecuta el algoritmo de Dijktra para obtener los caminos mas cortos o desde B a cada red destino. a) Muestre las iteraciones del algoritmo de Dijkstra necesarias para obtener los caminos a cada red, indicando en cada iteracin la distancia a la red as como el camino o [Link]/16 [Link]/16 [Link]/16 [Link]/16 [Link]/16 [Link]/16 d camino d camino d camino d camino d camino d camino 0 1 2 3 4 5 6 7 8 9

0 C

. 3

1 6

. A 1

0 /

1 0 . 0 . 2 3 4 . 0 1 B 6 1 / 0 . 0 . 7 . 0 1

b) Qu condicin hace que el algoritmo de Dijkstra se detenga? En cuantas iteraciones se detendr en la e o a pregunta anterior? c) Que tabla de rutas se generar en el nodo B una vez completado el algoritmo? Indique en cada entrada de a la tabla la distancia asociada a dicha entrada Supongamos que una vez que las tablas de rutas estn establecidas se cambia en los nodos el algoritmo de a enrutamiento a uno de tipo distance-vector. Despus de un tiempo de funcionamiento se producen cambios en la e red. En un instante determinado el nodo B tiene la tabla de rutas que ha calculado en la pregunta b. Poco despus e recibe un mensaje de su vecino A indicndole el siguiente vector de distancias a Destino - distancia [Link]/16 0 [Link]/16 3 [Link]/16 3 [Link]/16 2 [Link]/16 4 [Link]/16 7

d) Qu cambios provoca en la tabla de rutas de B la recepcin de este mensaje? e o Problema 7.6: En la red de la gura se pretende utilizar el algoritmo de Bellman-Ford para calcular el enrutamiento

a) Calcule las iteraciones del algoritmo de Bellman-Ford para obtener todos los caminos a todos los nodos desde el nodo B. A B C D E F G H d camino d camino d camino d camino d camino d camino d camino d camino 0 1 2 3 4 5 6 b) En que n mero de Iteracin se conocen por primer vez caminos para llegar a todos los nodos de la red u o aunque no sean m nimos? Cul es el camino de B a E en dicha iteracin? Cul es el camino de B a E al a o a nal del algoritmo? c) Dibuje el rbol de expansin de coste m a o nimo obtenido. Cuantos y cuales enlaces de la red original no estn en el arbol de expansin? a o d) Pueden eliminarse estos enlaces de la red? Contiene el rbol de expansin obtenido toda la informacin a o o de enrutamiento necesaria para la red? Razone la respuesta Problema 7.7: Repita el problema 7.2 y 7.3 con la siguiente red y el nodo de origen A
B 1 A 1 E

B F 1 1 D C 1 5 1 1 A 1 1 H G