domingo, 23 de agosto de 2009

Spanning Tree Protocol (IEEE 802.1D)

El presente tutorial es el resultado de leer más de 7 artículos en internet sobre este tema y una serie de 6 tutoriales, diapositivas y manuales (que pienso compartirlos en un post más adelante).

Al igual que todas mis entradas (o tutoriales) sobre las materias de Redes I y Redes II (Redes y Telecomunicaciones), éstas están basadas en las tareas que nos daba el docente de la materia el Ing. Jorge Gonzales.

1.- Conceptos Básicos.

Spanning Tree Protocol (STP) es un protocolo de red de nivel 2 de la capa OSI, (nivel de enlace de datos).

Su función es la de gestionar la presencia de bucles en topologías de red debido a la existencia de enlaces redundantes. El protocolo permite a los dispositivos de interconexión activar o desactivar automáticamente los enlaces de conexión, de forma que se garantice que la topología esté libre de bucles.

Considere dos LANs que estén conectadas por dos bridges (Figura 1), asuma que el host n está transmitiendo un Frame (Trama) F, con un destino desconocido.
Figura 1.- Escenario de red redundante.

¿Que pasaría?, estaríamos en presencia de lo siguiente:
  • El Bridge A envía este Frame a la LAN 2.
  • El Bridge B ve este Frame F en la LAN 2 (with unknown destination, con destino desconocido), y envía este Frame a la LAN 1.
  • El Bridge A hace lo mismo y el reenvío continua.
¿Dónde está el problema?, ¿cuál es la solución?

El problema está en que ocurre un bucle, también conocido como loop o lazo. Cuando hay bucles en la topología de red, los dispositivos de interconexión de nivel de enlace (como un puente de red o un conmutador de paquetes) reenvían indefinidamente las tramas Broadcast y Multicast, al no existir ningún campo TTL (Time To Live, Tiempo de Vida) en la Capa 2, tal y como ocurre en la Capa 3. Se consume entonces una gran cantidad de ancho de banda, y en muchos casos la red queda inutilizada. La solución consiste en permitir la existencia de enlaces físicos redundantes, pero creando una topología lógica libre de bucles. STP permite solamente una trayectoria activa a la vez entre dos dispositivos de la red (esto previene los bucles) pero mantiene los caminos redundantes como reserva, para activarlos en caso de que el camino inicial falle.

El árbol de expansión (Spanning Tree) permanece vigente hasta que ocurre un cambio en la topología, situación que el protocolo es capáz de detectar de forma automática. El máximo tiempo de duración del árbol de expansión es de cinco minutos. Cuando ocurre uno de estos cambios, el puente raíz actual redefine la topología del árbol de expansión o se elige un nuevo puente raíz.

2.- Funcionamiento.

Este algoritmo cambia una red física con forma de malla, en la que existen bucles, por una red lógica en forma de árbol en la que no existe ningún bucle. Los puentes se comunican mediante mensajes de configuración llamados Bridges Protocol Data Units (BPDU).

3.- Estado de los puertos.

Los estados en los que puede estar un puerto son los sgtes.:
  • Bloqueo: En este estado sólo se pueden recibir BPDU's. Las tramas de datos se descartan y no se actualizan las tablas de direcciones MAC (mac-address-table).
  • Escucha: A este estado se llega desde Bloqueo. En este estado, los switches determinan si existe alguna otra ruta hacia el puente raíz. En el caso que la nueva ruta tenga un coste mayor, se vuelve al estado de Bloqueo. Las tramas de datos se descartan y no se actualizan las tablas ARP. Se procesan las BPDU.
  • Aprendizaje: A este estado se llega desde Escucha. Las tramas de datos se descartan pero ya se actualizan las tablas de direcciones MAC (aquí es donde se aprende por primera vez). Se procesan las BPDU.
  • Envío: A este estado se llega desde aprendizaje. Las tramas de datos se envían y se actualizan las tablas de direcciones MAC (mac-address-table). Se procesan las BPDU.
  • Desactivado: A este estado se llega desde cualquier otro. Se produce cuando un administrador deshabilita el puerto o éste falla. No se procesan las BPDU.

Figura 2.- Estado de los puertos de los switches/bridges.

4.- STP en la teoría.

El algoritmo consta de tres partes y requiere que cada conmutador tenga un ID y pueda saber el estado de cada puerto conectado a él. Las partes son:
  1. Se elige el bridge con ID más chico (pequeño, menor) como root.
  2. Cada bridge calcula el camino más corto hacia el root y marca el puerto correspondiente como "root port".
  3. Para cada LAN todos los bridges conectados a él deben acordar cuál de ellos será el designado. Para hacerlo intercambian paquetes llamados BPDUs. El bridge designado será, en orden de preferencia:
  • El más cercano al root.
  • El más cercano y con menor ID en caso de que sea necesario desempatar.

5.- STP en la práctica.

Los bridges se sincronizan enviándose paquetes llamados BPDUs que contienen:
  • ID del emisor.
  • ID del que el emisor piensa que es el root.
  • distancia del emisor al root.
6.- Ejemplo.

Para entender mejor como se dividen las partes del algoritmo y como termina convergiendo aplicaremos el algoritmo sobre la sgte. topología (Figura 3) y veremos la reacción de los bridges.
Figura 3.- Topología inicial de nuestra red.

Al principio todos los bridges se creen root, por lo tanto preparan BPDU's que dicen eso y lo envían por todos sus puertos para avisarle a los bridges adyacentes.

En la sgte. figura (Figura 4) los bridges root están marcados de color rojo y los puertos del root también.
Figura 4.- Todos los bridges se creen root.

En la "primera oleada" (Figura 5) los paquetes de los bridges adyacentes llegan. Ahora, si un bridge considera que un paquete que llegó es mejor al suyo cambia su estado.

Un paquete es considerado mejor cuando:
  • El root ID recibido es menor.
  • El root ID es igual pero la distancia al root es menor.
  • El root ID y la distancia son iguales pero el ID del emisor es menor.
Figura 5.- Primera transferencia de BPDUs.

En la Figura 5 vemos como quedaría ahora el estado de cada bridge. Están marcados en rojo los "root ports" que son los puertos de cada bridge que apuntan al root. Para entender mejor los casos anteriormente mencionados vamos a ver dónde se dieron en nuestra red.

Los bridges 24, 92 y 12 recibieron un paquete del bridge número 3, vieron que existe un bridge con número menor estricto que ellos por lo tanto cambian su estado y forwardean los recibido por los puertos que no recibieron el paquete. Más adelante veremos como reccionan los bridges de más abajo.

Los bridges de la segunda línea (los de más abajo) todavía no recibieron el paquete del bridge número 3, por lo tanto sólo mejoraron un poco lo conocido dentro de su alcance. El bridge 7 sabe que el 5 es mejor que él (e ignoró el paquete del 92 por ser mucho peor que él). El bridge número 4 todavía no se vió superado y se cree el rey del mundo.

En la próxima iteración (Figura 6) los paquetes del bridge 3 llegan a la línea de abajo y se estabiliza la sección del root.
Figura 6.- Segunda transferencia de BPDUs y elección unánime del root.

Es importante ver que durante esta segunda iteración no produjeron paquetes nuevos los bridges que cambiaron su estado durante la primera iteración (de la primera línea) sino que forwardearon el paquete proveniente del bridge número 3. Con esto me refiero a que, por ejemplo, el bridge número 12 no generó un paquete y lo envió por su root port. Si lo hubiera hecho habríamos tenido problemas graves de convergencia en cuanto a los puertos designados que es lo que vamos a ver ahora.

Los puertos designados son los que cada bridge cree que tiene que forwardear. El próximo paso es bloquear algunos de estos puertos para convertir el grafo en un árbol.

Los bridges envían paquetes hacia las LANs (no por los root ports sino por los designados) y escuchan a los demás bridges.
  • Si reciben un root ID igual pero una distancia menor al root bloquean este puerto y dejan que el otro bridge se encargue de mandar los mensajes desde y hacia esa LAN. En este paso ya no debería haber paquetes circulando con root ID menor al mío (porque dijimos que ya habíamos acordado un root). Sin embargo si ese fuera el caso simplemente se procede como antes y en la próxima iteración quedaremos listos para sincronizar los puertos designados.
  • Si reciben un root ID y una misma distancia se desempata con el menor ID del emisor.
En la sgte. figura (Figura 7) podemos ver como quedan asignados los puertos:
Figura 7.- Elección de puertos designados.

Finalmente al converger el algoritmo se tiene un árbol y todos los bridges están sincronizados (Figura 8). Cada un intervalo de tiempo se generan paquetes con información para mantener la asignación y estar atentos a los cambios.
Figura 8.- Fin del algoritmo.
7.- Enlaces de interés.
  • www.es.wikipedia.org, un resúmen claro y simple se encuentra en nuestra querida enciclopedia abierta.
  • www.ordenadores-y-portatiles.com, una buena explicación sobre el STA (Spanning Tree Algorithm, Algoritmo del Arbol de Expansión), que es el algoritmo que usa el STP que aplicamos en el ejemplo.
  • www.decom-uv.cl, un documento en pdf desarrollado por la Universidad de Valparaíso - Chile.
  • www.fis.unab.edu.co, una diapositiva en pdf desarrollado por la Facultad de Ingeniería de Sistemas de la unab (Universidad Autónoma de Bucaramanga), con más de 40 páginas sobre el tema, muy completo y recomendable.

8 comentarios :

  1. Muy buena tu información, es muy didactica. Te felicito.

    ResponderEliminar
  2. Hola, gracias por tus anónimas y agradecidas palabras; me ayudan a seguir adelante. La verdad que sé que mucha gente se pasa por aquí a buscar información, se la llevan y no dejan ni pisca de su presencia.

    ResponderEliminar
  3. Gracias!
    Una gran recopilación.

    ResponderEliminar
  4. Hola! ¿Qué otro artículo tendría que leerme para poder entender un poco más acerca de este? No cojo bien los conceptos como 'bridges', bucles y algo más.

    ¿Estoy equivocado cuando pienso que este protocolo sólo sirve para mejorar la comunicación entre switches o és válido para todo dispositivo de red?

    Saludos,


    Sergio

    ResponderEliminar
  5. Bueno Sergio, los enlaces de interés con más artículos déjame buscarlos y ni bien los encuentre los añadiré en esta misma entrada.

    Pero mientras déjame tratar de despejarte tus dudas:

    1.- Los bridges o puentes son dispositivos de red que trabajan a nivel de la capa 2 de OSI (nivel de enlace de datos) al igual que los swtichs.

    2.- Los bucles o loops son de dos tipos FISICOS y LOGICOS. Los loop FISICOS están presentes en topologías de redes en las cuales por ejemplo un segmento de red A puede comunicarse con otro segemento de red B por medio de más de un dispositivo de capa 2.

    Cuando existe un loop físico entonces puede existir un loop LOGICO. Los loops LOGICOS generalmente ocurren cuando un host manda una trama Broadcast, esa trama puede llegar a su destino pero seguirá dando vueltas (bucles o loops) indefinidamente por la red, causando saturación e inestabilidad entre otras cosas.

    Para evitar estos bucles o loops LOGICOS (para acortar llamados solo bucles o loops) y todos los problemas que acarrea el mismo es que nace el Spanning Tree Protocol o Protocolo de Arbol de expansión (Estándar IEEE 802.1d).

    2.- Este protocolo sirve para todo los dispositivos de la capa de enlace de datos que soporten el mismo; es decir swtichs y bridges (puentes).

    De todos modos para que me entiendas mejor, además de añadir los enlaces de interés también insertaré unas imágenes en este mismo artículo con lo que se puede entender mejor los bucles. Y si quieres también puedo publicar otro artículo con diapositivas y manuales sobre STP (Spanning Tree Protocol).

    Saludos y gracias por participar. Si tienes más dudas o comentarios hazlos con toda confianza.

    ResponderEliminar
  6. Buenas, llego un poco tarde... Tenía algunas dudas sobre STP y han quedado despejadas. Sobre todo el ejemplo gráfico ha sido fundamental. Muchas gracias por tu esfuerzo.

    ResponderEliminar

Encuesta: ¿Quién es el mejor catedrático de la carrera de Ing. Informática de la UAGRM?