Algoritmos de encaminamiento

Algoritmos de encaminamiento

Rodrigo Carlos Garnica Acuña

1) Introducción

Algoritmos de enrutamiento

Un algoritmo de enrutamiento decide qué salida vincular un paquete entrante debe ser transmitido en Cada host está conectado a un enrutadorSi el host de destino no está directamente conectado, el paquete se transfiere a este enrutador predeterminado (primer salto)

Algoritmos de enrutamiento

Enrutamiento de la ruta más cortaPara un par de hosts que se comunican, hay es un camino más corto entre ellos. La brevedad puede definirse por:+Número de saltos de enrutador / conmutador+Distancia geográfica+ Retraso de enlace+ Costo

Algoritmos de enrutamiento

Dos tipos de algoritmos de enrutamiento:+Algoritmos de enrutamiento global+La información de estado completa se utiliza en las decisiones de enrutamiento.+ Algoritmos de enrutamiento descentralizados+Estado local / vecino+El enrutamiento jerárquico se utiliza para hacer que estos algoritmosescalar a grandes redes

Algoritmos de enrutamiento

Los algoritmos de enrutamiento estático no se basan sus decisiones de enrutamiento en la corriente estado de la red:+Enrutamiento dinámico+La ruta de la ruta cambia a medida que cambia el costo del enlace

Enrutamiento de estado de enlace

Protocolos

Cada enrutador mide la distancia (en retraso, saltorecuento, etc.) entre él y sus enrutadores adyacentes El enrutador crea un paquete que contiene todos estosdistancias. El paquete también contiene una secuencianúmero y un campo de edad.Cada enrutador distribuye estos paquetes usando flooding Para controlar las inundaciones, se utilizan los números de secuenciapor enrutadores para descartar los paquetes de inundación que ya hanvisto desde un enrutador dadoUna vez que un enrutador recibe todos los paquetes de estado dela red, puede reconstruir la topología completay calcular una ruta más corta entre él y cualquierotro nodo utilizando el algoritmo de Dijsktra.

Enrutamiento jerárquico

Todos los algoritmos de enrutamiento tienen dificultades comola red se vuelve grande Para redes grandes, las tablas de enrutamientocrecen muy rápidamente, y también lo hace el número de paquetes de inundaciónSegmentar la red en regionesLos enrutadores de una sola región conocen todos los detallessobre otros enrutadores en esa región, pero ninguno delos detalles sobre enrutadores en otras regionesAnalogía: códigos de área telefónicos

OSPF

Abra primero el camino más cortoAlgoritmo de enrutamiento ahora utilizado en InternetOSPF usa el algoritmo Link State Routing conmodificaciones para soportar: Múltiples métricas de distancia (distancia geográfica,retraso, rendimiento)Soporte para tráfico en tiempo realEnrutamiento jerárquicoSeguridad OSPF divide la red en varios jerarquías:􀂄 Sistemas autónomos (AS)- grupos de subredes􀂄 Áreas- Grupos de enrutadores dentro de un AS􀂄 Áreas troncales- Grupos de enrutadores que conectan otras áreas juntas

OSPF

Los enrutadores se distinguen por las funcionesellos realizan􀂄 Enrutadores internos- Solo enruta paquetes dentro de un área􀂄 Enrutadores de borde de área- Conectarse a áreas juntos􀂄 Enrutadores troncales- Residir solo en el área de la columna vertebral􀂄 AS enrutadores de límite- Enrutadores que se conectan a un enrutador fuera del AS

OSPF: Enrutamiento de estado de enlace modificado

􀁺 Recordar:􀂄 En el enrutamiento de estado de enlace, los enrutadores inundan su información de enrutamientotodos los demás enrutadores de la red􀁺 En OSPF, los enrutadores solo envían su información a "adyacentesenrutadores ”, no a todos los enrutadores.􀁺 Adyacente NO significa vecino más cercano en OSPF􀁺 Un enrutador en cada área está marcado como el "enrutador designado"􀁺 Los enrutadores designados se consideran adyacentes a todos los demás enrutadores enla zona􀁺 OSPF combina el enrutamiento de estado de enlace con adaptativo centralizadoenrutamiento

Algoritmos de enrutamiento distribuido

􀁺 Cada enrutador intercambia periódicamente el enrutamientoinformación (por ejemplo, retraso de tiempo estimado, colalongitud, etc.) con sus vecinos􀁺 Ejemplos:􀂄 Enrutamiento por vector de distancia􀂄 RIP

Vectores de distancia

Cada enrutador mantiene listas de las distancias más conocidastodos los demás enrutadores conocidos. Estas listas se llaman"Vectores".Se supone que cada enrutador conoce la distancia exacta (enretraso, recuento de saltos, etc.) a otros enrutadores directamenteconectado a él.Periódicamente, los vectores se intercambian entreenrutadores, y cada enrutador actualiza sus vectores. Problema: cuenta hasta el infinitoCon el enrutamiento por vector de distancia, buenas noticiasviaja rápido, pero las malas noticias viajan lentamente Cuando un enrutador deja de funcionar, puedetomar mucho tiempo antes de que todos losotros enrutadores se dan cuenta de ello

Mejoras

􀁺 Horizonte dividido􀂄 No le cuente al vecino sobre las rutas obtenidas de él􀂄 O nunca anuncie una ruta fuera de la interfaz que la aprendió􀁺 Veneno inverso􀂄 Anunciar la red inalcanzable a través de la misma interfazlo aprendiste􀂄 anunciar todos los ID de red, pero esos ID de red aprendidos en un determinadodirección se anuncian con una métrica de 16, lo que indica que lala red no está disponible.􀁺 Actualizaciones activadas en lugar de actualizaciones periódicas􀁺 Vectores de ruta, vectores de almacenamiento o ruta completa en lugar de solosiguiente salto

ROTURA RIP

􀁺 Protocolo de información de ruta􀁺 Uno de los algoritmos de enrutamiento utilizados porLa Internet􀁺 Basado en enrutamiento por vector de distancia􀁺 No escaló bien, y sufrió laproblema de conteo hasta el infinito􀁺 RIP se está eliminando gradualmente

Desarrollos recientes: IPv6

IPv4 (el protocolo IP estándar) tiene limitacionesespacio de dirección Lo más importante es que la IP se está quedando sindirecciones. 32 bits no son suficientes.El tráfico en tiempo real y los usuarios móviles tambiénvolviéndose más comúnIP versión 6(También llamado IPng o IP de próxima generación) IPv6: los cambiosGran espacio de direcciones:Direcciones de 128 bits (16 bytes)Permite hasta340,282,366,920,938,463,463,374,607,431,768,211,456decciones únicasEncabezados de longitud fija (40 bytes) Mejora la velocidad de procesamiento de paquetes en enrutadores 􀁻 Se le asigna el nombre ‘localhost’

RE

Encabezado IPv6

Etiqueta de flujo: se puede usar para etiquetar todos los paquetescon cierta propiedad para un manejo especialDS / ECN para indicar el tipo de servicioIPv6: los cambios (continuación) Soporte para "flujos"Los flujos ayudan a respaldar el servicio en tiempo real en Internetn "flujo" es un número en el encabezado de IPv6 que se puedeutilizado por los enrutadores para ver qué paquetes pertenecen almisma corriente