PDF de programación - Tipos de protocolos de enrutamiento

Tipos de protocolos de enrutamiento

Departamento de Automática y Computación

Area de Ingeniería Telemática
Universidad Pública de Navarra

[email protected]

Dr. Daniel Morató

Laboratorio de Programación de Redes

http://www.tlm.unavarra.es/asignaturas/lpr

Contenido

• Estructura de Internet
• Algoritmos de enrutamiento

– Distance vector
– Link State
– Path vector

3 Nov

Tipos de protocolos de enrutamiento

1/10

1

Estructura de Internet

• Tier-1 ISPs

– Completamente mallada
– Default-free zone
– Más de 100K rutas

– ISPs locales de acceso

• Tier-2 ISPs

• Tier-3 ISPs

– ISPs regionales o nacionales

Tier 1 ISP

Default-free zone

Tier 1 ISP

Tier 1 ISP

Tier 1 ISP

Tier 2 ISP

Tier 3 ISP

Tier 2 ISP

Tier 2 ISP

Tier 2 ISP

NAP

Tier 3 ISP

Tier 3 ISP

Tier 3 ISP

Tier 3 ISP

Tier 3 ISP

3 Nov

Tipos de protocolos de enrutamiento

2/10

Contenido
• Algoritmos de enrutamiento

– Distance vector
– Link State
– Path vector

3 Nov

Tipos de protocolos de enrutamiento

3/10

2

Tipos de Algoritmos de Enrutamiento

• Distance Vector (DV)

– Los routers cooperan en un cálculo distribuido de las rutas
– El algoritmo en cada router calcula el mejor camino (mínimo coste) a

todos los destinos

– Cada router informa a sus vecinos de las rutas que ha calculado
– Informan de la dirección (vector) y el coste (la distancia) a cada destino
– Viendo las rutas anunciadas por los vecinos puede que el router encuentre

un mejor camino (menor coste)

– El algoritmo, tras varias iteraciones, converge a los mejores caminos (se

estabilizan las rutas)

– El cálculo es: simple, asíncrono, incremental y distribuido
– Ejemplos: RIP, IPX-RIP, DECnet, IGRP, EIGRP*

3 Nov

Tipos de protocolos de enrutamiento

4/10

Contenido
• Algoritmos de enrutamiento

– Distance vector
– Link State
– Path vector

3 Nov

Tipos de protocolos de enrutamiento

5/10

3

Tipos de Algoritmos de Enrutamiento

– Aproximación de base de datos distribuida replicada en vez de un cálculo

distribuido incremental

– Cada router posee información global sobre la red: nodos y enlaces

• Link State (LS)

existentes
– ¿Cómo?

• Los routers informan de sus enlaces a redes activas y con routers vecinos
• “Inundan” la red con esta información para que llegue a todos los routers
• “Cómo” hacer esta inundación es uno de los principales problemas de estos

protocolos

– Todos los routers tienen una imagen (grafo) de la red (todos la misma) y a

partir de ahí eligen los caminos...

– Menor tiempo de convergencia que DV ante cambios en la red
– Permiten calcular caminos con diferentes requisitos de métrica
– Ejemplos: OSPF, IS-IS, PNNI

3 Nov

Tipos de protocolos de enrutamiento

6/10

Contenido
• Algoritmos de enrutamiento

– Distance vector
– Link State
– Path vector

3 Nov

Tipos de protocolos de enrutamiento

7/10

4

Tipos de Algoritmos de Enrutamiento

• Path Vector

– Ejemplo: BGP

– Similar a Distance Vector
– Cálculo distribuido
– Los routers informan a sus vecinos de las rutas calculadas pero incluyen

todo el camino (path) hasta el destino de cada ruta

3 Nov

Tipos de protocolos de enrutamiento

8/10

Resumen

• La estructura de Internet tiene necesidades variadas
los algoritmos de

las propiedades de

respecto a
enrutamiento

• Esquemas distance-vector y link-state se emplean dentro

de los dominios (ASs)

• DV hace un cálculo distribuido incremental empleando el

algoritmode Bellman-Ford

• LS opta por una aproximación de base de datos distribuida

usando el algoritmo de Dijkstra sobre el grafo resultante

• El estándar de-facto de enrutamiento entre dominios es

BGP

• BGP es un protocolo path-vector y que permite expresar

políticas

3 Nov

Tipos de protocolos de enrutamiento

9/10

5

Próxima clase

Enrutamiento distance-vector. RIP

3 Nov

Tipos de protocolos de enrutamiento

10/10

6