Friday, May 27, 2011

Protocolos de Arbol Extensible STP, RSTP PVSTP y MSTP


Entender la teoría de Grafos es fundamental a la hora de estudiar STP y sus variantes, así que haremos una pequeña introducción a esta teoría y explicaremos como funcionan algunos de los algoritmos mas comunes a la hora de generar arboles extensibles.

¿Que es un árbol extensible?

Si tenemos un grafo G compuesto de nodos y aristas, un árbol extensible (Spanning Tree) es un subgrafo sin ciclos que contiene todos los nodos de G.

Si alguno de los vértices falla, se desconectaría la ramificación haciendo inaccesible al nodo o a el grupo de nodos desde la raíz, así que los árboles extensibles son poco tolerantes a fallos.


Mínimo árbol extensible (MST -Minimun Spanning Tree)
MST es un árbol de expansión donde la suma total del peso de las aristas que conforman un camino es el mínimo posible. Para encontrar este se utiliza el Algoritmo de Prim-Jarnik (similar al de Dijkstra)

  1. Se comienza con un nodo v arbitrario
  2. El árbol se construye nodo por nodo
  3. Se añade el nodo u formando la arista (v, u) en la que:
    • El nodo v ya se encuentra en el árbol
    • El nodo u no está aún en el árbol
    • El peso del vértice (v,u) es el mínimo de los pesos de todos los posibles candidatos u
  1. Cada nodo almacenado en D[u]
    • es un nodo que aún no ha sido visitado. El siguiente u debe estar adyacente a v, es decir solo a un paso de distancia, así se formará la arista (v,u) con menor peso.
    • Ventaja: reducción del tiempo de búsqueda del la arista (v,u).
Ejemplo del Algoritmo de Prim-Jarnik

Spanning Tree Protocol (STP)

Este es un protocolo de red que funciona en la capa de enlace de datos del modelo OSI. Existen dos versiones del protocolo que no son compatibles entre si, la original y la estandarizada por el IEEE, esta segunda es la que se usa comunmente hoy en día. Este protocolo es transparente para el host del usuario, y proporciona un canal de comunicación óptimos entre los hosts de una red.
STP utiliza el algoritmo de árbol extensible para configurar los puertos del switch formando topología jerárquicas de red que evitan la formación de bucles o loops, los cuales se presentan debido a la existencia de enlaces redundantes.
 STP activa automáticamente los enlaces de ciertas interfaces y bloquea las rutas físicas redundantes para garantizar un sólo camino lógico en cualquier configuración de bridges, esto asegura una topología libre de loops. Un puerto se considera bloqueado cuando el tráfico de red no puede entrar o salir de el. 

Redundancia
En un diseño jerárquico, la redundancia se logra al distribuir las aplicaciones y los dispositivos de red a través de hardware adicional y redundante,  así se generan múltiples rutas alternativas entre los dispositivos de red, Así cuando se presente la interrupción o fallo de algun camino, no hay perdida de conectividad, ya que hay  otro enlace de reserva para soportar el tráfico y la transmisión de datos.

Componentes STP
Root bridge
El algoritmo de árbol extensible designa un solo switch comocido como Root bridge, y lo utiliza como punto de referencia en todos los cálculos para determinar las rutas redundantes que serán bloqueadas, ya sea en una LAN conmutada o en un dominio de difusión. La duración máxima del árbol de expansión es de cinco minutos, este sigue siendo válido hasta que se produce un cambio de topología, el cual es detectado automáticamente por el protocolo. 
Cuando uno de estos cambios se produce, el root bridge actual redefine la topología del árbol de expansión o elige un nuevo root bridge. Los bridges se comunican entre sí mediante mensajes de configuración llamados BPDUs ( Bridge  Protocol Data Units).
El protocolo establece identificadores (ID) de Bridge, y elige al que tiene la mayor prioridad (número más pequeño) como root. El root bridge establece el camino mas corto (la ruta de menor costo) para toda la red, cada puerto tiene un parámetro configurable llamado Span Path Cost.

Bridge Designado
Son los bridges que se encuentran en el camino de menor costo y son elegidos entre todos los bridges que conectan un segmento de red para transmitir tramas al root, si hay dos puentes con el mismo costo, el criterio de selección esta definido según la dirección MAC más baja. El puerto en el bridge designado que conecta un segmento, se denomina puerto designado y ofrece el camino de menor costo hacia el puerto root. Todos los demás puertos y rutas son bloqueados en un estado estacionario.
Si la configuración STP cambia o un segmento de red redundantes se vuelve inalcanzable, el algoritmo reconfigura los enlaces y restaura la conectividad, activando uno de los enlaces reservados. Si el protocolo falla, es posible que dos conexiones estén activas simultáneamente, lo que podría llevar un loop de tráfico en la LAN.

Variaciones de STP
Cualquier disposición de puentes puede ser configurada con una topología de árbol a través de cualquiera de las cuatro versiones STP: el clásico descrito por la norma IEEE 802.1d y revisado previamente, RSTP rápido (IEEE 802.1w RSTP), STP Múltiple (MSTP 802.1s) y VLAN STP (VSTP).

MSTP: Cuando una red se divide en segmentos unidos por varios puentes, el protocolo bloquea algunos puentes para evitar que un mensaje se quede merodeando en la red.

RSTP mantiene una gran parte de la terminología STP y la mayoría de los parámetros no cambian.  Utiliza el mismo formato de BPDU, con la excepción de que el campo de la versión se establece en 2 para indicar que es RSTP. Este protocolo gestiona enlaces redundantes, reduciendo significativamente el tiempo de convergencia de la topología de la red cuando hay algún cambio o después de un fallo o durante la recuperación de un switch, el puerto o el enlace. En otras palabras, lo detecta y utiliza topologías de red que proporcionan una convergencia más rápida del árbol extensible sin crear bucles de reenvío. RSTP activa puede confirmar que un puerto pueden someterse a una transición segura para el envío de Estado sin depender de ninguna configuración del temporizador.
VLAN STP (VSTP).




Referencias: Diapositivas de Clase JKU Linz :
Univ Prof J.R.Mühlbacher & DI. Ing R.Hörmanseder, Netzwerke Management
Univ. Prof Dr Allois Fersha. Algorithem und Datenstrukturen II


 
Si tienes información adicional sobre este tema, tus comentarios o links de referencia son bienvenidos. 

    Thursday, May 26, 2011

    Protocolo de Descubrimiento de capa de enlace (LLDP -Link Layer Discovery Protocol)


    LLDP es un Protocolo de Descubrimiento de Vecindario (Neighbor Discovery Protocol NDP), el cual ha sido diseñado para dispositivos de redes Ethernet (como switches y routers), Los NDP se usan para recibir y/o transmitir información relacionada con los dispositivos de otros nodos de la red, también para almacenar la información aprendida acerca de otros dispositivos.

    LLDP es un protocolo de “un salto”; es decir que la información LLDP sólo se puede enviar y recibir por medio de dispositivos adyacentes, los cuales están conectados directamente entre sí por el mismo enlace, dichos dispositivos se denominan “vecinos”. La información anunciada nunca se reenvía a otros dispositivos en la red.

    Este es un protocolo independiente que opera únicamente en la capa 2 (enlace de datos) del modelo OSI, ha sido definido por el Estándar IEEE 802.1AB-2005. LLDP permite que los dispositivos de red Ethernet anuncien información detallada acerca de ellos mismos a otros dispositivos que también están conectados directamente a la red y que también usan LLDP, esto permite que dos sistemas que ejecutan diferentes protocolos de capa de red aprendan uno del otro. La información compartida comprende datos de configuración, capacidad, identificación, TTL, entre otros.

    ¿Como funciona LLDP?

    Los anuncios son enviados en paquetes llamados unidades de datos LLDP (LLDPDUs -LLDP Data units). Los datos enviados y recibidos a través de LLDPDUs son útiles por muchas razones. Por ejemplo, el switch puede descubrir cuáles  dispositivos en la red son vecinos, y los puerto por donde se conectan entre sí.

    Un switch se puede configurar para:
    Transmitir información sobre sí mismo a los vecinos
    Recibir información enviada desde los dispositivos vecinos
    Almacenar y administrar la información recibida en la base de gestión de información (MIB -Managment information base) para LLDP

    Cada dispositivo que utiliza LLDP tiene su propio agente LLDP, este es una entidad de software que permite la administración de accesibilidad a capas superiores y recoge la información de puntos terminales de los dispositivos adyacentes. El agente LLDP es responsable de la recepción,transmisión y gestión de LLDP.

    LLDP define:
    Un conjunto de mensajes de anuncios comunes (del tipo valores de longitud).
    Un protocolo para transmitir y recibir anuncios.
    Un método para almacenar la información que está contenida dentro de anuncios recibidos


    LLDP y SNMP

    LLDP está diseñado para operar con el Protocolo Simple de Administración de Red(SNMP - Simple Network Management Protocol). El cual nos proporcionan una interfaz de línea de comandos para administrar LLDP, sin embargo SNMP es la interfaz recomendada ya que LLDP está diseñado para ser administrado  automáticamente desde el sistemas de gestión de redes (NMS -Network Managment Systems).

    Para visualizar el vencindario LLDP se utilizan los siguientes comandos:

    Switch
    Mostrar dispositivos en el vencidario

    show lldp info remote-device
    show lldp neighbors

    Parte de esta información fue extraída de el siguiente documento:
    Descargar Documentación aquí
    Si tienes información adicional sobre este tema, tus comentarios o links de referencia son bienvenidos.