Capítulo 5: Capa de red, plano de control Flashcards
¿Cuáles son los dos enfoques para la instalación y mantenimiento de las tablas de forwarding y de routing?
La instalación y mantenimiento de las tablas de forwarding y tablas de routing tiene dos enfoques:
-
Control por router: se ejecuta un algoritmo de enrutamiento en cada router. Cada router tiene un componente que se comunica con componentes de otros routers para calcular los valores de su tabla de forwarding. Los protocolos OSPF (Open Shortest Path First) y BGP (Border Gateway Protocol) están basados en este enfoque. -
Control lógicamente centralizado: se calculan las tablas de forwarding que tiene que usar cada router en un servidor centralizado y luego se distribuyen.
¿Qué problema resuelven los algoritmos de routing y cómo se puede plantear un problema de routing?
Los algoritmos de routing resuelven el problema de decidir qué camino deben tomar los paquetes para llegar desde el origen hasta su destino. Para plantear los problemas de routing se puede pensar en grafos, donde cada nodo es un router y cada arista es un enlace físico. Además cada arista tiene un peso que típicamente representa la distancia física, la velocidad o el costo monetario del enlace.
El objetivo natural para un algoritmo de routing es el de encontrar el camino menos costoso entre emisor y receptor.
¿De qué 3 formas se pueden clasificar los algoritmos de routing?
Los algoritmos de routing se pueden clasificar según 3 aspectos:
- Según la centralización (centralizados y descentralizados)
- Según la frecuencia en la que cambian las rutas (estáticos y dinámicos)
- Según su sensibilidad a la carga
¿Cómo se puede clasificar a los algoritmos de routing según la centralización?
Los algoritmos de routing se pueden clasificar según la centralización en dos grupos:
-
Algoritmos centralizados: buscan el camino mínimo conociendo la red completa, es decir, el algoritmo toma como input la conectividad entre todos los nodos y aristas. -
Algoritmos descentralizados: el cálculo del camino mínimo lo hace cada router iterativamente. Un nodo conoce a sus aristas, va intercambiando información con los nodos vecinos y así hasta saber lo suficiente para calcular el camino.
¿Cómo se clasifican los algoritmos de routing según la frecuencia en que cambian las rutas?
Los algoritmos de routing se pueden clasificar también según la frecuencia en que cambian las rutas, y también se tienen dos grupos:
-
Algoritmos estáticos: las rutas cambian muy lentamente con el tiempo, usualmente por intervención humana. -
Algoritmos dinámicos: las rutas cambian a medida que la carga de tráfico o la topología de la red cambian.
¿Cómo se clasifican los algoritmos de enrutamiento según su sensibilidad a la carga?
Los algoritmos de enrutamiento se pueden clasificar también según su sensibilidad a la carga.
En los algoritmos sensibles a la carga, los costos de enlace varían de forma dinámica para reflejar el nivel actual de congestión. De esta manera el algoritmo tenderá a elegir rutas que eviten los enlaces congestionados.
Los algoritmos de enrutamiento actuales de Internet son algoritmos no sensibles a la carga, ya que el costo de un enlace no refleja explícitamente su nivel actual de congestión.
Explicar el Algoritmo Link-State (o de estado de enlaces)
Algoritmo Link-State (o de estado de enlaces)
En este tipo de algoritmo, la topología de red y todos los costos de enlace son conocidos, por eso es un algoritmo centralizado. El algoritmo todo el tiempo mira el estado de sus enlaces, y si hay algún cambio lo tiene que avisar. Esto se logra haciendo que todos los nodos broadcasteen paquetes con el estado de los enlaces a todos los demás nodos de la red (flooding).
Funciona como protocolo intra-sistema autónomo pero no es aplicable a todo Internet por una cuestión de escala. Los enlaces se caen muy seguido, y si por cada enlace que se cae hay que informárselo a toda la red estaríamos enviando información de la topología permanentemente, estorbando al tráfico.
Los algoritmos que se usan para llegar de un router a otro son el de Dijkstra o el de Prim.
La complejidad es O(N^2), pero se puede optimizar usando un heap de Fibonacci para bajarla a O(E + Vlog(V))
Explicar el algoritmo de enrutamiento por vector de distancias (DV)
Algoritmo de enrutamiento por vector de distancias (DV)
Cada nodo le transmite a sus vecinos su tabla de ruteo, que consiste en un vector donde dice a qué distancia está de cada router. Es un algoritmo iterativo, asincrónico y distribuido.
- Es iterativo porque el algoritmo continúa hasta que no hay más intercambio de información entre vecinos.
- Es asincrónico porque no necesita que los nodos operen lockeándose entre ellos.
- Es distribuido en el sentido que cada nodo recibe información sobre sus vecinos directos, hace cálculos y distribuye los resultados de vuelta a los vecinos.
Si aplicamos DV a todo internet, la convergencia va a tardar en alcanzarse. Tiene el problema de que cuando se forman bucles, el algoritmo puede quedarse rebotando entre nodos indefinidamente, o hasta que las tablas de ruteo cambien.
Los costos mínimos están relacionados mediante la ecuación de Bellman-Ford, que establece que el costo del camino mínimo de X a Y es igual al mínimo de la sumas entre el costo de X a V y la distancia de V a Y, para todo vértice V que sea vecino de X.d_X(Y) = min_V{c(X,V) + d_V(Y)} (Los grafos cumplen las propiedades de los espacios métricos, entonces vale la desigualdad triangular).
Comparar los algoritmos de enrutamiento LS y DV
Las diferencias entre el algoritmo Link-State (LS) y el algoritmo por Vector de Distancias (DV) son 4:
-
Información: El algoritmo LS requiere información global que se obtiene via broadcast, pero un router solo informa de los costos de sus enlaces directamente conectados. Con el algoritmo DV, cada nodo solo se comunica con sus vecinos directamente conectados, pero les proporciona sus estimaciones de costo mínimo desde sí mismo a todos los demás nodos conocidos de la red. -
Mensajes: LS requiere que cada nodo conozca el costo de cada enlace de la red, esto requiere el envío de O(NE) mensajes. Además, cuando un costo cambia, el nuevo valor tiene que enviarse a todos los nodos. DV requiere intercambios de mensajes entre los vecinos directamente conectados en cada iteración. Cuando cambian los costos de los enlaces, el algoritmo propagará los nuevos valores solamente si para algún nodo conectado a ese enlace cambió algún camino mínimo. -
Convergencia: LS converge en O(N^2), y DV puede converger mucho más lentamente, con problemas si aparecen bucles de enrutamiento. -
Robustez: LS es más robusto en el sentido de que cada nodo calcula su tabla de enrutamiento, por lo que si se corrompe o elimina algún dato no afecta a toda la red. Con DV un nodo puede pasar algún costo erróneo o algún paquete corrupto a uno o a todos los destinos, pudiendo difundirse el error a través de toda la red con el correr de las iteraciones.
¿Qué son los sistemas autónomos y qué problemas resuelven?
Un sistema autónomo (AS) es un grupo de routers que se encuentran bajo el mismo control administrativo. Los routers de un mismo AS ejecutan el mismo algoritmo de enrutamiento y disponen información unos de otros.
Resuelven dos problemas, característicos de los algoritmos de enrutamiento LS y DV:
-
Escalabilidad: cuando el número de routers crece, almacenar la información de enrutamiento para todos los posibles destinos en cada uno de estos routers requeriría de cantidades de memoria muy grandes. -
Autonomía administrativa: Internet es una red de ISPs, donde cada ISP tiene su propia red de routers. Un ISP generalmente quiere operar su red a su antojo u ocultar al mundo exterior ciertos aspectos de la organización interna de su red. Idealmente, una organización debería poder operar y administrar su red como desee, sin por ello dejar de conectar su red a otras redes externas.
Explicar el protocolo OSPF (Open Shortest Path First)
¿Qué ventajas tiene?
OSPF (Open Shortest Path First) es un protocolo de link-state que utiliza “flooding of link-state information” (broadcasteo de información de enlaces a todos los nodos) y el Algoritmo de Dijkstra para el camino mínimo dentro de un sistema autónomo. Cada router construye un grafo del sistema autónomo entero, y luego ejecuta el algoritmo de Dijsktra para determinar el camino más corto a todas las subredes. Los routers broadcastean la información a todos los demás routers, no solo a sus vecinos.
Las 4 ventajas/avances principales que presenta OSPF:
- [S]
Seguridad: los intercambios dentro de OSPF pueden ser autenticados para evitar que se inyecte información incorrecta en las tablas de los routers. - [MC]
Múltiples caminos con el mismo costo: cuando hay muchos caminos a un mismo destino con el mismo costo, OSPF permite que se puedan usar múltiples caminos. - [SOP]
Soporte integrado para routeo unicast y multicast - [JER]
Permite jerarquía dentro de un sistema autónomo: se pueden definir áreas, y cada una ejecuta su propio algoritmo OSPF. Dentro de un área, se definen routers de frontera que son responsables de enrutar los paquetes hacia fuera del área. Una de las áreas es configurada como área troncal del sistema autónomo, y se ocupa de enrutar el tráfico entre las demás áreas del sistema.
Explicar el protocolo BGP.
¿Qué mecanismos proporciona?
¿Cómo se anuncia la alcanzabilidad?
¿Cuáles son los atributos más importantes al anunciar un prefijo?
BGP (Border Gateway Protocol) es un protocolo descentralizado y asincrónico utilizado por todos los sistemas autónomos en Internet para enrutar paquetes entre ellos.
En BGP los paquetes no se enrutan hacia una dirección de destino específica, sino hacia prefijos CIDR, donde cada prefijo representa a una subred o colección de subredes.
Como protocolo de enrutamiento entre sistemas autónomos, BGP proporciona a cada router mecanismos para:
- Obtener de los sistemas autónomos vecinos información acerca de la alcanzabilidad de los prefijos. En particular, BGP permite a cada subred anunciar su existencia al resto de Internet.
- Determinar las “mejores” rutas hacia los distintos prefijos.
Para anunciar la información de alcanzabilidad del prefijo X, todos los routers se van pasando un mensaje agregándose en la ruta, y de esta forma los distintos sistemas autónomos no solo aprenderán que X existe, sino también una ruta de sistemas autónomos que conduce hasta X.
- Las conexiones TCP, junto con todos los mensajes BGP enviados a través de la conexión, se denomina conexión BGP.
- Una conexión BGP que abarca dos sistemas autónomos se llama conexión BGP externa (eBGP).
- Una sesión BGP entre routers de un mismo sistema autónomo se denomina conexión BGP interna (iBGP).
Cuando un router anuncia un prefijo a través de una conexión BGP, incluye con el prefijo varios atributos. Dos de los atributos más importantes son:
- AS-PATH, que contiene la lista de sistemas autónomos por los cuales pasó el anuncio (sirve también para prevenir loops).
- NEXT-HOP, que es la dirección IP del router más cercano del sistema autónomo adyacente.
Explique los algoritmos de hot potato routing y route-selection.
El algoritmo más simple de ruteo es el hot potato routing, donde el camino elegido es aquel con el menor costo al router NEXT-HOP. El router logra reducir el costo dentro de su propio sistema autónomo, sin importar los costos que tengan las partes restantes de la ruta hasta el destino.
En la práctica, el algoritmo que más se usa es el de route-selection. El input de este algoritmo es un set con todos los caminos hacia el prefijo que ya fueron aprendidos y aceptados por el router. Si hay más de un camino al mismo prefijo, se aplican reglas de eliminación:
1. Un camino tiene asignado un atributo llamado ‘local preference’ tal que se eligen los caminos con el mayor valor.
2. De los restantes, se seleccionan los caminos con el AS-PATH más corto.
3. Para los caminos restantes se utiliza el algoritmo de hot potato.
4. Si sigue quedando más de un camino, se utilizan identificadores BGP.
¿Cómo se utiliza BGP para implementar IP-Anycast?
BGP se usa para implementar el servicio IP-anycast, utilizado comúnmente en DNS para enrutar paquetes al mejor destino desde el punto de vista de la latencia (o sea al más cercano geográficamente).
Cuando un host envía un datagrama a una dirección anycast, la infraestructura de la red usará BGP para buscar el camino más corto hasta uno de los equipos que aceptan datagramas dirigidos a la dirección anycast utilizada.
¿Qué es el plano de control SDN y cuáles son las principales características de la arquitectura SDN?
El plano de control SDN (Software Defined Networking) es la lógica de la red que controla el forwarding de paquetes entre los dispositivos compatibles con SDN de una red, así como la configuración y gestión de estos dispositivos y sus servicios.
Podemos identificar 4 características fundamentales de una arquitectura SDN:
- [SP]
Separación del plano de datos y el plano de control: El plano de datos está compuesto por los switches de la red. El plano de control está compuesto por servidores y software que determinan y gestionan las tablas de routing de los switches. - [SR]
Servidores Remotos: A diferencia de los routers tradicionales, SDN se ejecuta en servidores remotos a los switches de la red. - [RF]
Reenvío basado en el flujo: El reenvío de paquetes en los switches SDN puede estar basado en los valores de diversos campos de los headers de las capas de transporte, de red o de enlace. - [RP]
Red programable: La red se puede programar mediante las aplicaciones de control de red que se ejecutan en el plano de control.
