Aaaa

Algoritmos de ruteo
• • Estrechamente relacionados con el protocolo de ruteo Características deseables – Correctos – Simples – Robusto – Estable – Equitativos – Optimos (criterios: demora, throughput de la red, costo, hops, etc)
Recursos que utilizan – Memoria (tablas: RIB, FIB) – Tiempo de CPU – Ancho de banda (intercambio de información entre routers) – Tiempo de administración (si requierenconfiguración manual)

•

1

Algoritmos de ruteo: clasificación
• Según dónde se toman las desiciones – centralizados – distribuidos – aislados
Según la estrategia de ruteo – no adaptativos – adaptativos Según el origen de la información – Local – Nodos adyacentes – Todos los nodos

•

•

2

Algoritmos de ruteo: Ruteo estático (por tablas)
• • Tablas de ruteo (FIB) en cada nodo,ingresadas por el operador Sólo está presente la función de reenvío (no hay intercambio de informacion de ruteo entre nodos)

•
• •

Vulnerable a cambios en la carga y/o topología
Utilizado sólo en redes de tamaño manejable

I
Red A
A-1

Red B
A-2 B-1 C-1 B-2 D-1

Red C
C-2

Red D
D-2

Se utiliza normalmente (tablas) en los hosts en sistemas Unix
Destino Prox.Router D-1 D-1B-1 Local F-2 Local B-1

Router X
E-1 F-1

Red E Red F
E-2 F-2

Tabla router X

Red A Red B Red C Red D Red E Red F Otras redes

3

Algoritmos de ruteo: Ruteo centralizado
•
• •

Se designa un equipo como controlador central de rutas
Los nodos envían información periódicamente El CCR realiza desiciones de ruteo óptimas y basadas en un conocimiento de la totalidad de la red
CCR•
• •

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

4

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 corto 3 Genera gran overhead en la red 4Usos 3 3 – Aplicaciones militares 4 2 – Bases de datos distribuidas
Mejoras – No reenviar un paquete más de una vez – Contador de nodos y eliminación de paquete – Flooding selectivo
5 1 1

2 4

•

5

5

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 conentradas que son eliminadas por tiempo

I

H1

H3

Red A
A-1 H2 A-2 B-1 B-2 Red B D-1 C-1

Red C
C-2 H4

Red D-2 D Router X
F-1

•

E-1

Red E Red F

•
•

Brodcast u otro método (hot potatoe) si un destino no tiene entrada
Puede incorporarse información acerca de costos (p. ej. nodos)

E-2

F-2

H1 envia a H4: Red A, alcanzable por B-1 H2 envia a H3, Red C,alcanzable por F-2

6

Algoritmos de ruteo: Distance vector

• • • • • • • • • •

Ruteo dinámico, distribuido Utilizado en la Internet, 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 Presenta problemas deconvergencia 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 nodos adyacentes El cálculo del camino más corto se realiza distribuido entre los nodos

7

Algoritmos de ruteo: Distance vector-Ejemplo
• • Ejemplo Nodos A, B, C, D, E; vínculos 1, 2, 3, 4, 5. Se asume como métrica distancia (todos losvínculos tienen costo 1)
A

1

B

2 5

C

3
D

4 6
E

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

Nodo 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...