Agronegocios

Algoritmos de Enrutamiento: Distancia Vector

Ing. Marco A. Sotelo Monge

Algoritmos de ruteo
Estrechamente relacionados con el protocolo de ruteo Características deseables  Correctos  Simples  Robusto  Óptimos (criterios: demora, throughput de la red, costo, hops, etc.) Objetivo: Lograr la convergencia en las redes de datos. Es decir, hacer posible la comunicación desde cualquierorigen hacia cualquier destino de red. Recursos que utilizan  Memoria  Tiempo de CPU

 Ancho de banda (intercambio de información entre routers)
 Tiempo de administración (si requieren configuración manual)

Algoritmos de ruteo: clasificación
Según dónde se toman las decisiones  centralizados  distribuidos  Aislados Según la estrategia de ruteo  no adaptativos

 Adaptativos
Según elorigen de la información  Local  Nodos adyacentes

 Todos los nodos

Algoritmos de ruteo: Ruteo estático (por tablas)
Tablas de ruteo en cada nodo, ingresadas por el operador Sólo está presente la función de reenvío (no hay intercambio de información de ruteo entre nodos) Vulnerable a cambios en la carga y/o topología

Utilizado sólo en redes de tamaño manejable
I Destino Red AProx.Router D-1 D-1 B-1 Local F-2 Red A A-1 Red B A-2 B-1 B-2 C-1 D-1 Red C Red D C-2 E-1 Red E E-2 D-2 Router X F-1 Red F F-2

Tabla router X

Red B Red C Red D Red E

Red F
Otras redes

Local
B-1

Algoritmos de ruteo: Ruteo centralizado
Se designa un equipo como controlador central de rutas Los nodos envían información periódicamente CCR El CCR realiza desiciones de ruteo óptimas ybasadas en un conocimiento de la totalidad de la red


Es vulnerable a fallas en el CCR Información desactualizada a medida que los nodos se alejan del CCR Saturación de líneas en las adyacencias del CCR





Algoritmos de ruteo: Flooding
Ruteo estático, aislado Cada paquete es enviado por todos los vínculos excepto por el que llegó Muy resistente a fallas Llega por el camino más cortoGenera gran overhead en la red Mejoras  No reenviar un paquete más de una vez  Contador de nodos y eliminación de paquete  Flooding selectivo
5 1 1 5 3 2 4 4 3 3

2

4

Algoritmos de ruteo: Backward learning
Ruteo dinámico, aislado El router aprende rutas en función de los paquetes que pasan por él, provenientes de otros nodos Tablas con entradas que son eliminadas por tiempo Brodcast uotro método si un destino no tiene entrada Puede incorporarse información acerca de costos (p. ej. nodos)
H1 envia a H4: Red A, alcanzable por B-1 H2 envia a H3, Red C, alcanzable por F-2

I

H1 Red A A-1 H2

H3

A-2 B-1 B-2 Red B C-1 D-1 Red C Red D C-2 D-2 Router X H4 E-1 F-1 Red E E-2 Red F F-2

Algoritmos de ruteo: Distance vector
Ruteo dinámico, distribuido
Utilizado en laInternet, RIPv1(Dominio público), RIPv2(DP), IGRP (Cisco), EIGRP (Cisco) Está siendo reemplazado por ruteo link state (OSPF) Simple de instalar y administrar Puede soportar una métrica (pura o combinada) Limitado en cuanto al diámetro máximo de la red Cada nodo conoce el costo de cada uno de sus vínculos (distancia, demora, etc.) Un nodo intercambia periódicamente sus tablas de ruteo con sus nodosadyacentes El cálculo del camino más corto se realiza distribuido entre los nodos

Algoritmos de ruteo: Distancia vector-Ejemplo
Ejemplo Nodos A, B, C, D, E; vínculos 1, 2, 3, 4, 5. Se asume como métrica distancia (todos los vínculos
A 3 D 6 1 B 4 5 E 2 C

tienen costo 1)

1. Estado de las tablas en el arranque (aún no se intercambió información)
Nodo A Nodo B Nodo C
Link local Costo 0Nodo D
Link local Costo 0
A Nodo D Link local Costo 0

Nodo E
A Nodo E Link local Costo 0

A Nodo A

Link local

Costo 0

A Nodo B

A Nodo C

2. Primer intercambio, cada nodo envía su tabla a los adyacentes (p.ej. A envía: A=0 a B y a D)
Nodo A A Nodo A B D Nodo B

Link local 1 3

Costo 0 1 1

A Nodo B A C E

Link local 1 2 4

Costo 0 1 1 1

Nodo C A Nodo C B E...