Transcript
Universidad de Costa Rica Facultad de Ingeniería Escuela de Ingeniería Eléctrica IE-0425 Redes de Computadoras I ciclo 2015
Trabajo Final
Protocolo de Enrutamiento RIP
Josué David Vargas Andrés Sánchez Cristopher Rodríguez Iván Brizuela
Grupo 2
Profesor: Eduardo Navas C. 22 de junio de 2015
Introducción En la actualidad la tecnología de la comunicación digital permite la interconexión de distintas redes de computadoras que se encuentran geográficamente dispersas en todo el mundo. Pero para enviar y recibir paquetes de datos entre diferentes localizaciones geográficas existe una gran cantidad de rutas posibles por las que estos pueden viajar para llegar a su destino. Debido a la necesidad de considerar la mejor ruta posible para transmitir los paquetes de datos entonces surge la necesidad de emplear métodos que permitan el tránsito eficiente de información en las redes por ello surge el concepto de algoritmos de enrutamiento. Estos algoritmos deciden porque enrutadores deben pasar para llegar a su destino. Este tipo de algoritmos emplean tablas en donde se encuentra la información de los equipos vecinos y los pesos de las rutas entre ellos para elegir la línea de salida donde se enviarán los paquetes. Además en el enrutamiento se deben actualizar las tablas para así poder manejar los cambios de topología y tráfico de red durante las actividades de la red. Un ejemplo de implementación de uno de los algoritmos antes mencionados es el RIP (Routing Information Protocol), el cual será discutido en el presente trabajo.
Evolución de los protocolos de enrutamiento dinámico Los protocolos de enrutamiento dinámico se han usado en redes desde comienzos de la década de los ochenta. La primera versión de RIP se lanzó en 1982, pero algunos de los algoritmos básicos dentro del protocolo ya se usaban en ARPANETven 1969. Debido a la evolución de las redes y a su complejidad cada vez mayor, han surgido nuevos protocolos de enrutamiento. La figura muestra la clasificación de los protocolos de enrutamiento. Uno de los primeros protocolos de enrutamiento fue el Routing Information Protocol (RIP). RIP ha evolucionado a una nueva versión, el RIPv2. Sin embargo, la versión más nueva de RIP aún no escala a implementaciones de red más extensas. Para abordar las necesidades de redes más amplias, se desarrollaron dos protocolos de enrutamiento avanzados: Open Shortest Path First (OSPF) e Intermediate System-to-Intermediate System (IS-IS). Cisco desarrolló el Interior Gateway Routing Protocol (IGRP) y el Enhanced IGRP (EIGRP), que también escala bien en implementaciones de redes más grandes (Graziani, 2008). Asimismo, surgió la necesidad de interconectar diferentes redes y proveer el enrutamiento entre ellas. El protocolo Border Gateway Routing (BGP) ahora se usa entre ISP y entre ISP y sus clientes privados más grandes para intercambiar información de enrutamiento. Con la llegada de numerosos dispositivos para consumidores que usan IP, el espacio de direccionamiento IPv4 está prácticamente agotado. Por tal motivo, ha surgido el IPv6. A fin de sostener la comunicación basada en IPv6, se han desarrollado versiones más nuevas de los protocolos de enrutamiento IP. Protocolos de enrutamiento por vector de distancia en la actualidad Para los protocolos de enrutamiento por vector de distancia, sólo existen realmente dos opciones: RIP o EIGRP. La decisión acerca de qué protocolo de enrutamiento se utilizará en una situación determinada depende de varios factores, entre los que se incluyen: el tamaño de la red, la compatibilidad entre los modelos de routers y el requisito de conocimientos administrativos. RIP Con el tiempo, el RIP ha pasado de ser un protocolo de enrutamiento con clase (RIPv1) a un protocolo de enrutamiento sin clase (RIPv2). El RIPv2 es un protocolo de enrutamiento estandarizado que funciona en un entorno de enrutador de fabricante mixto. Los enrutadores fabricados por empresas diferentes pueden comunicarse utilizando el RIP. Éste es uno de los protocolos de enrutamiento más
fáciles de configurar, lo que lo convierte en una buena opción para las redes pequeñas. Sin embargo, el RIPv2 todavía tiene limitaciones. Tanto el RIPv1 como el RIPv2 tienen una métrica de ruta que se basa sólo en el conteo de saltos y que se limita a 15 saltos (Graziani, 2008). Características del RIP: Admite el horizonte dividido y el horizonte dividido con envenenamiento en reversa para evitar loops. Es capaz de admitir un balanceo de carga de hasta seis rutas del mismo costo. El valor por defecto es de cuatro rutas del mismo costo. Métricas. Propósito de una métrica En algunos casos, un protocolo de enrutamiento aprende sobre más de una ruta hacia el mismo destino. Para seleccionar la mejor ruta, el protocolo de enrutamiento debe poder evaluar y diferenciar entre las rutas disponibles. Para tal fin, se usa una métrica. Una métrica es un valor utilizado por los protocolos de enrutamiento para asignar costos a fin de alcanzar las redes remotas. La métrica se utiliza para determinar qué ruta es más preferible cuando existen múltiples rutas hacia la misma red remota. Cada protocolo de enrutamiento usa su propia métrica. Por ejemplo, RIP usa el conteo de saltos, EIGRP usa una combinación de ancho de banda y retardo, y la implementación de OSPF usa el ancho de banda. El conteo de saltos es la métrica más sencilla para hacer previsiones. El conteo de saltos se refiere a la cantidad de enrutadores que debe atravesar un paquete para llegar a la red de destino. Para R3 en la figura 1, la red 172.16.3.0 se encuentra a dos saltos o dos enrutadores de distancia (Graziani, 2008).
Figura 1: Saltos en los enrutadores Métricas y protocolos de enrutamiento. Parámetros de las métricas
Diferentes protocolos de enrutamiento usan diferentes métricas. La métrica utilizada por un protocolo de enrutamiento no es comparable con la métrica utilizada por otro protocolo de enrutamiento. Dos protocolos de enrutamiento diferentes pueden elegir diferentes rutas hacia el mismo destino debido al uso de diferentes métricas. El RIP elegirá la ruta con la menor cantidad de saltos, mientras que OSPF elegirá la ruta con el ancho de banda más alto. El campo métrica en la tabla de enrutamiento en distintos protocolos La métrica para cada protocolo de enrutamiento es: RIP: conteo de saltos: la mejor ruta se elige según la ruta con el menor conteo de saltos. IGRP e EIGRP: ancho de banda, retardo, confiabilidad y carga; la mejor ruta se elige según la ruta con el valor de métrica compuesto más bajo calculado a partir de estos múltiples parámetros. Por defecto, sólo se usan el ancho de banda y el retardo. OSPF: costo; la mejor ruta se elige según la ruta con el costo más bajo.
Figura 2: Ejemplo de saltos Los protocolos de enrutamiento determinan la mejor ruta en base a la ruta con la métrica más baja. En el ejemplo de la figura 2 los enrutadores están usando el protocolo de enrutamiento RIP. El valor de métrica es el segundo valor en los corchetes para una entrada de la tabla de enrutamiento. En la figura 2, R2 tiene una ruta hacia la red 192.168.8.0/24 que se encuentra a 2 saltos de distancia. Diferencias básicas de RIP versión 1 y RIP versión 2 Primero mencionaremos las características más relevantes para RIPv1 y RIPv2. RIPv1:
Cada 30 segudos se transmiten las actualizaciones de routing por métrica 255.255.255.255 Un conteo de saltos de 15 ya se considera como infinito, por lo que no se propaga la actualización de routing al siguiente router. Para la selección de rutas se utiliza el conteo de saltos.
RIPv2:
A diferencia del RIPv1, el RIPv2 es un protocolo de routing sin clase, admite VLSM (Variable Length Subnet Mask) y CIDR (Classless Inter-Domain Routing)
Envia actualizaciones a la dirección de multidifusión 224.0.0.9, lo que se traduce en una mayor eficiencia.
Tiene entradas de routing reducidas, con esto admite la sumarización de ruta manual en cualquier interfaz
Cuenta con protección mediante un mecanismo de autentificación para proteger las actualizaciones de la tabla de routing entre vecinos.
Recapitulando tenemos entonces que las diferencias básicas entre RIPv1 y RIPv2 son: Características y funciones Protocolo sin clase Métrica Dirección a la que se envían las actualizaciones Admite VLSM Admite CIDR Admite sumarización Admite autenticación
RIPv1 RIPv2 No Sí Conteo de saltos en ambos casos, teniendo 15 como su cantidad máxima. 255.255.255.255 224.0.0.9 No No No No
Sí Sí Sí Sí
Classfull o classless La diferencia entre un protocolo classfull o classless es que un protocolo classfull no envía información de la máscara de subred en las actualizaciones de enrutamiento. RIPv1 es un protocolo classfull que en su momento asignaba las direcciones de red en función de las clases (A, B o C) y no era necesario que incluyera una máscara de subred ya que esta podía determinarse en función del primer octeto de la dirección de red. Estos protocolos classfull pueden usarse cuando una red se divide en subredes utilizando más de una máscara de subred.
Entre las limitaciones de los protocolos classfull está la imposibilidad de admitir redes no contiguas. En la figura 6 se observa una representación de un enrutamiento classfull:
Figura 6: Enrutamiento con protocolo classful En caso contrario, RIPv2 es un protocolo classless. Este protocolo incluye la máscara de subred con las direcciones de red en las actualizaciones de enrutamiento. Actualmente, las redes no se asignan en función de clases y la máscara de subred no puede determinarse según el valor del primer octeto como pasaba en el caso de los protocolos classfull, esto sucede porque estos protocolos admiten VLSM. La figura 7 muestra la representación de un enrutamiento classless.
Figura 7: Enrutamiento con protocolo classless Comprando las dos últimas figuras, vemos que la red classless está usando máscaras de subred /30 y /27en la misma tipología.
Formato paquete RIP
Los datos en un mensaje RIP se encapsulan en un segmento UDP con 512 de número de puertos de origen/destino. También se tiene el encabezado de enlace de datos, encabezado de segmento y encabezado de segmento UDP. Con esto tenemos que el mensaje RIPv1 tiene la siguiente forma de encapsulado:
Encabezado enlace de datos
Encabezado de paquete IP
Encabezado de segmento UDP
Mensaje de RIP 512 bytes, hasta 25 rutas
Estas secciones se conforman de la siguiente manera:
Enlace de datos: Dirección MAC de origen y destino. Paquete IP: Dirección IP origen y destino, así como el campo protocolo de 17 para UDP. Segmento UDP: Puerto de origen y destino, cada uno de 520. Mensaje RIP: Sí es solicitud o respuesta, versión del RIP (1 o 2), ID de familia de direcciones (2 para IP) y la métrica (para este RIP es conteo de saltos).
En la figura 8 se puede apreciar el formato de RIPv1 (Graziani, 2008).
Figura 8: Formato RIPv1 Descripción del formato de RIPv1:
Comando: Sí es una solicitud es 1 y si es una respuesta es un 2. Versión: Puede ser RIPv1 o RIPv2. Identificador: 2 para IP, ó 0 para solicitud de una tabla competa de enrutamiento. Dirección IP: Dirección de ruta de destino Métrica: Conteo de saltos entre 1 y 16.
Los campos que se indican como “Deben ser cero” son espacio que se deja para futuras implementaciones del protocolo RIP (en RIPv2 ya se utilizan la mayoría de estas previstas). Los últimos 4 elementos del formato son la porción de la entrada de ruta, donde se incluye el identificador de familia de direcciones, dirección IP y métrica.
Cuando de actualiza el RIP se pueden incluir hasta un máximo de 25 de estas porciones de entrada de ruta. Por último, podemos tener un tamaño máximo de datagrama de 512 bytes, esto no incluye los encabezados IP o UDP. Conceptos de protocolos de enrutamiento Distancia administrativa La distancia o métrica es determinada por el número de saltos de enrutador hasta el destino. RIP tiene una distancia administrativa de 120 (la distancia administrativa indica el grado de confiabilidad de un protocolo de enrutamiento), RIP no es capaz de detectar rutas circulares, por lo que necesita limitar el tamaño de la red a 15 saltos. Cuando la métrica de un destino alcanza el valor de 16, se considera como infinito y el destino es eliminado de la tabla. La métrica para un destino se calcula como la métrica comunicada por un vecino más la distancia en alcanzar a ese vecino. Las métricas se actualizan sólo en el caso de que la métrica anunciada más el coste en alcanzar sea estrictamente menor a la almacenada. Sólo se actualizará a una métrica mayor si proviene del enrutador que anunció esa ruta. Las rutas tienen un tiempo de vida de 180 segundos (Huitema, 2000). Si pasado este tiempo, no se han recibido mensajes que confirmen que esa ruta está activa, se borra. Estos 180 segundos, corresponden a 6 intercambios de información. Una ventaja del protocolo RIP sobre el enrutamiento estático es su configuración inicial que es muy simple y la actualización manual de su configuración no es requerida ante cambios en la topología. Sistema autónomo Un sistema autónomo (AS) es un conjunto de redes bajo el control administrativo de una única entidad que presenta una política de enrutamiento común para Internet. En la figura, las empresas A, B, C y D se encuentran todas bajo el control administrativo de un ISP (Proveedores de servicios de Internet) que en la figura 3 aparece como ISP1. Entonces ISP1 presenta una política de enrutamiento común para todas estas empresas cuando publica rutas en ISP2. Los lineamientos para la creación, selección y registro del sistema autónomo se describen en RFC 1930. La Autoridad de Números Asignados de Internet (IANA con sus siglas en inglés) asigna números AS, y es la misma autoridad que asigna el espacio de dirección IP. Por lo general los ISP, los proveedores de “backbone” de Internet y grandes instituciones que se conectan con otras entidades que también cuentan con un número de AS. Estos ISP y las grandes instituciones utilizan el Border Gateway Protocol, o BGP, del protocolo de enrutamiento de “gateway” exterior para propagar información de enrutamiento. La gran mayoría de las empresas e instituciones con redes IP no necesitan un número de AS porque se encuentran bajo el control de una entidad más grande, como un ISP. Estas empresas utilizan protocolos de “gateway” interior como RIP, para realizar el
enrutamiento de paquetes dentro de sus propias redes. Son una de muchas redes independientes dentro del sistema autónomo de ISP. ISP es responsable del enrutamiento de paquetes dentro del sistema autónomo y entre otros sistemas autónomos (Graziani, 2008).
Figura 3: Ejemplo de sistema autónomo Routing Loop o bucle de enrutamiento El “routing loop” (bucle de enrutamiento) es una condición en la que un paquete se transmite continuamente dentro de una serie de enrutadores donde nunca alcanza la red de destino deseada. Un routing loop puede producirse cuando dos o más enrutadores tienen información de enrutamiento que indica erróneamente que existe una ruta válida a un destino inalcanzable (Graziani, 2008). Situaciones en las que se podría dar un routing loop: -Rutas estáticas configuradas incorrectamente. -Redistribución de ruta configurada incorrectamente (la redistribución es un proceso de envío de la información de enrutamiento desde un protocolo de enrutamiento a otro). -Tablas de enrutamiento incongruentes que no se actualizan debido a una convergencia lenta en una red cambiante y rutas de descarte configuradas o instaladas incorrectamente. La convergencia ocurre cuando todas las tablas de enrutamiento de los routers se encuentran en un estado de uniformidad. La red ha convergido cuando todos los routers tienen información completa y precisa sobre la red. El tiempo de convergencia es el tiempo que los routers tardan en compartir información, calcular las mejores rutas y actualizar sus tablas de enrutamiento. Una red no es completamente operativa hasta que la red haya
convergido; por lo tanto, la mayoría de las redes requieren tiempos de convergencia cortos. Consecuencias de los routing loops Todos estos factores pueden hacer que la red se vuelva muy lenta y en algunos casos muy severos completamente inoperante. ● El ancho de banda del enlace se utilizará para el tráfico que va de acá para allá entre los enrutadores formando el un bucle. ● Probablemente la CPU de algún enrutador se sobrecargará con el envío inútil de un paquete que afectará la convergencia de la red. ● Las actualizaciones de enrutamiento podrían perderse o no ser procesadas a tiempo, lo que implicaría eventualmente más bucles de enrutamiento y por lo tanto un deterioro mayor de la red. ● Los paquetes podrían perderse en los llamados “agujeros negros” y jamás llegar a su destino.
Cuenta al infinito La cuenta a infinito es una condición que se produce cuando las actualizaciones de enrutamiento inexactas aumentan el valor de la métrica a "infinito" para una red que ya no se puede alcanzar. Una cuenta a infinito ocurre cuando se rompe el enlace de red y el algoritmo de enrutamiento trata de calcular nuevos caminos más cortos. El problema de cuenta hasta infinito resulta en como los protocolos de enrutamiento en especial los de vector de distancia trabajan: Las buenas noticias llegan rápido, las malas noticias llegan lento (Lindqvist, 2004).
Figura 4: Ejemplo enrutador configurado para evitar cuenta al infinito
Para detener el aumento de la métrica, el “infinito” se define un valor máximo de métrica configurable en el enrutador. Por ejemplo en el protocolo RIP, el infinito (métrica inalcanzable) se define como 16 saltos, así cuando una ruta se cae y se realiza la cuenta a infinito los enrutadores colocan la red a 16 saltos de distancia, es decir marcan la ruta como inalcanzable. En la figura 4 se muestra un ejemplo de cómo se puede configurar un enrutador de modo que alcance el límite superior. Horizonte dividido Horizonte dividido es una técnica empleada en los protocolos de enrutamiento basados en vectores de distancia para evitar bucles de enrutamiento. Esta técnica le prohíbe a un enrutador dar a conocer una ruta a cierto destinatario si la ruta la aprendió por parte de él mismo (Lindqvist, 2004). Entonces esta técnica dice que un enrutador no debe publicar una red a través de la interfaz por la que le llegó la actualización. Se puede ejemplificar cómo funcionaría la técnica de horizonte dividido con la red de la figura 5 de la manera siguiente: R2 publica las redes 172.10.3.0.0 y 172.16.4.0 a R1. R2 publica las redes 172.16.3.0 y 172.16.4.0 a R3. R1 publica la red 172.16.1.0 a R2. R3 publica la red 172.16.4.0 a R2. Por lo tanto R2 no publica 172.16.4.0 a R3 por se0/1 ya que la ruta se originó por esa interfaz (Graziani, 2008).
Figura 5: Ejemplo de horizonte dividido.
Envenenamiento de ruta Es un tipo de horizonte dividido donde no se le prohíbe a A informar a B de la ruta, en su lugar A lo que le informa a B es que es imposible llegar a C mediante A, diciendo que la distancia a C es infinita (16 en RIP). De esta manera B nunca intentará llegar a C mediante A. Se le conoce como envenenamiento porque la información que da A es falsa, y a su vez puede incrementar el tamaño de las tablas de enrutamiento para redes de tamaño significativo, ya que enviar un 16
consume más recursos que no informar, por lo que se dice que se está envenenando la ruta. Sin embargo, aunque el envenenamiento es un método que involucra más datos y es más pesado, está confirmado que incrementa la eficiencia de la red en caso de fallos, por lo que es una práctica que se frecuenta (Lindqvist, 2004). Se utiliza para marcar la ruta como inalcanzable en una actualización de enrutamiento que se envía a otros enrutadores. La condición de inalcanzable para RIP es igual a la de infinito con métrica de 16. De esta manera la ruta envenenada tiene una métrica de 16 (Graziani, 2008). Un ejemplo de envenenamiento de ruta para la red de la figura 5 es el siguiente: 1. La red 172.16.4.0 falla el enlace. 2. R3 envenena la métrica con un valor de 16 (para RIP) y envía una actualización activa indicando que esta red no está disponible. 3. R2 procesa la actualización, como la métrica es de 16, R2 invalida la entrada en su tabla de enrutamiento (pone también 16) y envía una actualización del envenenamiento a R1. 4. R1 procesa la actualización e invalida la entrada de enrutamiento para 172.16.4.0 en su tabla. Algoritmo de enrutamiento Bellman-Ford Concepto grafo dirigido Un grafo dirigido (o dígrafo) D consiste de un conjunto finito no vacío de elementos llamados vértices conectados por un conjunto finito de pares ordenados llamados arcos o aristas, donde éstas solo pueden ir en un solo sentido. En la figura 9 se observa un dígrafo cuyas rutas de ida como de vuelta entre los nodos u y w son distintas.
Figura 9: Ejemplo grafo dirigido
Algoritmo de Bellman-Ford-Moore El algoritmo de Bellman-Ford-Moore es un algoritmo para calcular el camino más corto en un grafo dirigido desde un vértice fuente hacia los otros vértices del grafo y una ventaja de este algoritmo es que puede tener pesos negativos contrario a otros algoritmos de enrutamiento como el Dijkstra (Bang, 2007). El algoritmo tiene como entrada un grafo dirigido con pesos y ningún ciclo negativo con el vértice s fijo. Además tiene como salida las distancias más cortas a cada vértice desde s. Se usa la simbología δv= 0 para representar la distancia mínima a partir del vértice s al vértice v. Propiamente el algoritmo tiene tres etapas que se describen a continuación (Bang, 2007):
Se define la distancias δs= 0 y δv= ∞, para todo v distinto de s. Si hay n vértices, para todo i=1 hasta n-1 para cada para cada arco v-u con un peso w entre ellos, si δv+ w < δu, entonces δu = δv+ w. Para cada arco v-u revisar si δu > δv+ w y en dado caso mostrar el mensaje “el grafo contiene un ciclo negativo”.
Figura 10: Ejemplo del algoritmo de Bellman-Ford-Moore durante cinco iteraciones del algoritmo (Bang, 2007)
Un ejemplo del algoritmo de Bellman-Ford es el que se encuentra 9 donde se muestra cómo se lleva cabo el algoritmo con el intercambio de tablas para definir el camino más corto (Tanenbaum, 2012).
Figura 11: Tablas de enrutamiento usando el algoritmo de Bellman-Ford. Conclusiones El protocolo RIP sirve como base para entender cómo en los protocolos de enrutamiento se busca la mejor ruta posible tomando en consideración diferentes parámetros (en el caso de RIP el número de saltos), para favorecer y permitir la comunicación entre distintos enrutadores en partes lejanas geográficamente. Gracias al desarrollo de esta tecnología innovadora en la capa de red del modelo TCP/IP se ha podido construir la infraestructura de lo que hoy conocemos como Internet mediante el establecimiento de conexiones confiables cuyos datos van a llegar al lugar de destino esperado en el mejor tiempo posible. Referencias Bang-Jensen, J. Gutin, G. (2007). Digraphs Theory, Algorithms and Applications. Springer Verlag. New York Graziani, R., Johnson, A. (2008) Conceptos y protocolos de enrutamiento Editorial : Cisco Network Academy Huitema, Christian. (2000). Routing in the Internet. 2nd edition. Prentince Hall 2000. Lindqvist, Janne. (2004). Counting to Infinity.Helsinki University of Technology. Tanenbaum, Andrew S. (2012). Redes de Computadoras. Pearson Education, Inc, México, 5ta. Edición.