Algotirmos de Enrutamiento

Algoritmos de

Enrutamiento

Ing. Alvaro Hernn Alarcn Lpez

Algoritmos de Encaminamiento

Encaminamiento: Diversas rutas para llegar a un destino.

Termino ms corto

(una combinacin de

muchos factores )

Trayecto ms corto

Ms econmico

Mas rpido

Ms fiables y otros.

Contador de Saltos: - Cada salto o retransmisin tiene igual valor

- Solo se actualiza al no esta disponible enlace

- Mximo 15 saltos.

- Protocolos Novell, Apple Talk, OSI, TCP/IP



Encaminamiento: Diversas rutas para llegar a un destino.

Longitud simblica: - Cada salto puede no tener igual valor

- Otros factores q afectan enlace (carga, calidad

enlace, etc.)

- Velocidad, Trafico, Medio TX

Esttico Dinmico

Paquetes por igual ruta. Nueva ruta para cada

paquete.

No se basa en condicin

o topologa de red.

Se basa en cambios en

condicin o topologa de red

(ruta ms eficiente en un

instante).



Encaminamiento: TTL Tiempo de vida de paquete

Bucle encaminador a encaminador sin llegar a

destino

Al apagar un encaminador de la ruta se devuelve

paquete pensando en ruta mas corta

Tiempo de vida TTL: saltos (cuenta regresiva)

Vector Distancia, Estado del Enlace Ing. Alvaro Hernn Alarcn Lpez


Encaminamiento Basado en vector Distancia

- Router Comparte Conocimiento de toda la red

- Encaminamiento solo a vecinos (enlace directo)

- Comparte informacin a intervalos regulares

Coste se Basa en

Contar Saltos, cada

salto tiene valor de 1

Imagen tomada de BEHROUZ. A. FOROUZAN. 2002. Transmisin de Datos y redes de comunicaciones.

Ed. Mc Graw Hill. Segunda edicin. Ing. Alvaro Hernn Alarcn Lpez



Compartir Informacin

Cada encaminador enva informacin a vecino

Imagen tomada de BEHROUZ. A. FOROUZAN. 2002. Transmisin de Datos y redes de

comunicaciones. Ed. Mc Graw Hill. Segunda edicin.




Tablas de

Enrutamiento

- Cada enrutador sabe a redes esta conectado

- Enrutador acta como estacin en cada red

Destino final Numero saltos Siguiente

encaminador

Identificador de

Red

Coste Siguiente Salto




Creacin de Tablas de Enrutamiento

B enva tabla de enrutamiento de

paquetes por redes 55 y 14.

B es vecino, paquetes pueden

alcanzar a B en un salto.

Aadir un salto a todos los costes

mostrados en la tabla de B

La suma ser el coste de A para

alcanzar a esas otras redes.

Imgenes tomadas de BEHROUZ. A. FOROUZAN. 2002. Transmisin de Datos y redes de

comunicaciones. Ed. Mc Graw Hill. Segunda edicin. Ing. Alvaro Hernn Alarcn Lpez





Imagen tomada de BEHROUZ. A. FOROUZAN. 2002. Transmisin de Datos y redes de comunicaciones. Ed.

Mc Graw Hill. Segunda edicin.




1. Si el destino anunciado no est en la tabla de encaminamiento, el encaminador

debera aadir la informacin del destino a la tabla.

2. Si el destino anunciado est en la tabla de encaminamiento.

a. Si el campo siguiente salto es el mismo, el encaminador debera reemplazar la

entrada de la tabla con la nueva. As el contador de saltos nuevo sea mayor, la

entrada anunciada debera reemplazar a la entrada de la tabla.

b. Si el campo siguiente salto no es el mismo,

i. Si el contador de saltos nuevo es ms pequeo que el de la tabla, el encaminador

debera reemplazar la entrada de la tabla con la nueva.

ii. Si el contador de saltos nuevo no es ms pequeo (es el mismo o mayor), el

encaminador no debera hacer nada.

BEHROUZ. A. FOROUZAN. 2002. Transmisin de Datos y redes de comunicaciones. Ed. Mc Graw Hill. Segunda edicin. Pags. 613 y 614






Imagen tomada de BEHROUZ. A. FOROUZAN. 2002. Transmisin de Datos y redes de comunicaciones. Ed. Mc Graw Hill.

Segunda edicin.


Encaminamiento Basado en Estado de Enlace

- Comparte Conocimiento

sobre sus vecinos.

- A todos los encaminadores

de la red (inundacin).

-Compartir Informacin

cuando hay cambios.

Coste por varios factores

trafico, seguridad, estado

enlace.






Coste del paquete solo dado

por encaminador no por

estaciones.

Solo se plica coste de

encaminador a red; de red a

encaminador cero.

Paquete de estado de enlace LSP

Obtencin de informacin por

medio de paquetes saludo.

Imgenes tomadas de BEHROUZ. A. FOROUZAN. 2002. Transmisin de

Datos y redes de comunicaciones. Ed. Mc Graw Hill. Segunda edicin. Ing. Alvaro Hernn Alarcn Lpez



LSP: Paquete

de estado de

enlace. Emisor

Red Destino Coste

Encaminador

Vecino

Base de datos de estados de enlace Igual para Cada Encaminador

Advertencia Red Coste Vecino

Anunciante Red Coste Vecino

A 14 1 B

A 78 3 F

A 23 2 E

B 14 4 A

B 55 2 C

C 55 5 B

C 66 2 D

D 66 5 C

D 08 3 E

E 23 3 A

E 08 2 D

F 78 2 A

F 92 3





Algoritmo de Dijkstra Camino ms corto por grafos de nodos y arcos

rbol de Camino ms Corto

- Identifica raz y aade nodos vecinos

- Compara arco mas corto y se hace

permanente

- Identifica nodos que se alcanzan desde

nodo elegido (temporales).

- Repite dos ltimos pasos hasta

completar la red.

Encontrar las rutas ms cortas entre un nodo origen dado y todos los dems

nodos, desarrollando los caminos en orden creciente de longitud

Aplicado a Base

de Estados de

Enlaces





Algoritmo de Dijkstra

1. 2. 3.

4. 5.

6. 7.

8. 9.

10. 11.

12. 13.

Imgenes tomadas de BEHROUZ. A. FOROUZAN. 2002. Transmisin de Datos y

redes de comunicaciones. Ed. Mc Graw Hill. Segunda edicin. Ing. Alvaro Hernn Alarcn Lpez

7


Algoritmo de Dijkstra

Tabla de encaminamiento:

Red Coste Siguiente

Encaminador

08 4 E

14 1 ---

23 2 ---

55 3 B

66 5 B

78 3 ---

92 4 B



Algoritmo de Bellam-Ford

- Identifica raz .

- Aade nodos con distancia = 1 enlace.

-Aade nodos con distancia = 2 enlaces

y actualiza tabla.

- Aade nodos con distancia = 3 enlaces

y actualiza tabla.

Encontrar los caminos ms cortos desde un nodo origen dado con la condicin de

que stos contengan a lo sumo un enlace; a continuacin encontrar los caminos

ms cortos con la condicin de que contengan dos enlaces como mximo, y as

sucesivamente.

- Proceso sigue hasta tener mnimo coste de conexin para cada nodo

desde nodo origen.





Algoritmo de Bellman - Ford


comunicaciones. Ed. Mc Graw Hill. Segunda edicin. Ing. Alvaro Hernn Alarcn Lpez


Algoritmo de Bellman - Ford

Tabla de encaminamiento:

Red Coste Siguiente

Encaminador

08 4 E

14 1 ---

23 2 ---

55 3 B

66 5 B

78 3 ---

92 4 B


Documents

Algotirmos de Enrutamiento