Spanning tree

En comunicaciones, STP es un protocolo de red de capa 2 del modelo OSI (capa 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 (necesarios en muchos casos para garantizar la disponibilidad de las conexiones). El protocolo permite a los dispositivos de interconexión activar o desactivar automáticamente los enlaces de conexión, de forma que se garantice la eliminación de bucles. STP es transparente a las estaciones de usuario.

Historia

Está basado en un algoritmo diseñado por Radia Perlman mientras trabajaba para DEC. Hay 2 versiones del STP: la original (DEC STP) y la estandarizada por el IEEE (IEEE 802.1D), que no son compatibles entre sí. En la actualidad, se recomienda utilizar la versión estandarizada por el IEEE.

Existen múltiples variantes del STP debido, principalmente, al tiempo que tarda en converger el algoritmo utilizado. Una de estas variantes es el Rapid Spanning Tree Protocol, estándar IEEE 802.1D-2004 que hoy en día ha reemplazado el uso del STP original. 2012 IEEE 802.1aq fue aprobado como un estándar para reemplazar IEEE 802.1D, IEEE 802.1w, IEEE 802.1s

Motivación

Los bucles ocurren cuando hay rutas alternativas hacia un mismo destino (sea una máquina o segmento de red). Estas rutas alternativas son necesarias para proporcionar redundancia y así ofrecer una mayor fiabilidad a la red, dado que en caso de que un enlace falle, los otros pueden seguir soportando el tráfico de ésta. Los problemas aparecen cuando utilizamos dispositivos de interconexión de nivel de enlace, como un puente de red o un conmutador de paquetes.

Cuando existen bucles en la topología de red, los dispositivos de interconexión de nivel de enlace de datos reenvían indefinidamente las tramas broadcast y multicast, creando así un bucle infinito que consume tanto el ancho de banda de la red como CPU de los dispositivos de enrutamiento. Esto provoca que se degrade el rendimiento de la red en muy poco tiempo, pudiendo incluso llegar a quedar inutilizable. Al no existir un campo TTL (tiempo de vida) en las tramas de capa 2, éstas se quedan atrapadas indefinidamente hasta que un administrador de sistemas rompa el bucle. Un router, por el contrario, sí podría evitar este tipo de reenvíos indefinidos. La solución consiste en permitir la existencia de enlaces físicos redundantes, pero creando una topología lógica libre de bucles. STP calcula una única ruta libre de bucles entre los dispositivos de la red pero manteniendo los enlaces redundantes desactivados como reserva, con el fin de activarlos en caso de fallo.

Si la configuración de STP cambia, o si un segmento en la red redundante llega a ser inalcanzable, el algoritmo reconfigura los enlaces y restablece la conectividad, activando uno de los enlaces de reserva. Si el protocolo falla, es posible que ambas conexiones estén activas simultáneamente, lo que podrían dar lugar a un bucle de tráfico infinito en la LAN.

El árbol de expansión (Spanning tree) permanece vigente hasta que ocurre un cambio en la topología, situación que el protocolo es capaz 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.

Funcionamiento

El algoritmo transforma una red física con forma de malla, en la que existen bucles, por una red lógica en forma de árbol (libre de bucles). Los puentes se comunican mediante mensajes de configuración llamados Bridge Protocol Data Units (BPDU).

El protocolo establece identificadores por puente y elige el que tiene la prioridad más alta (el número más bajo de prioridad numérica), como el puente raíz (Root Bridge). Este puente raíz establecerá el camino de menor coste para todas las redes; cada puerto tiene un parámetro configurable: el Span path cost. Después, entre todos los puentes que conectan un segmento de red, se elige un puente designado, el de menor coste (en el caso de que haya el mismo coste en dos puentes, se elige el que tenga el menor identificador "dirección MAC"), para transmitir las tramas hacia la raíz. En este puente designado, el puerto que conecta con el segmento, es el puerto designado y el que ofrece un camino de menor coste hacia la raíz, el puerto raíz. Todos los demás puertos y caminos son bloqueados, esto es en un estado ya estacionario de funcionamiento.

Elección del puente raíz

La primera decisión que toman todos los switches de la red es identificar el puente raíz ya que esto afectará al flujo de tráfico. Cuando un switch se enciende, supone que es el switch raíz y envía las BPDUs que contienen la dirección MAC de sí mismo tanto en el BID raíz como emisor. El BID es el Bridge IDentifier: Bridge Priority + Bridge Mac Address. El Bridge Priority es un valor configurable que por defecto está asignado en 32768. El Bridge Mac Address es la dirección MAC (única) del Puente.

Cada switch reemplaza los BID de raíz más alta por BID de raíz más baja en las BPDU que se envían. Todos los switches reciben las BPDU y determinan que el switch que cuyo valor de BID raíz es el más bajo será el puente raíz. En caso de empate, el switch root sería el que menor MAC tuviera. El administrador de red puede establecer la prioridad de switch en un valor más pequeño que el del valor por defecto (32768), el nuevo valor debe ser múltiplo de 4096, lo que hace que el BID sea más pequeño. Esto sólo se debe implementar cuando se tiene un conocimiento profundo del flujo de tráfico en la red

Elección de los puertos raíz

Una vez elegido el puente raíz hay que calcular el puerto raíz para los otros puentes que no son raíz. El procedimiento a seguir para cada puente es el mismo: entre todos los puertos del puente, se escoge como puerto raíz el puerto que tenga el menor costo hasta el puente raíz. En el caso de que haya dos o más puertos con el mismo costo hacia el puente raíz, se utiliza la dirección MAC que tenga menor valor para calcular el costo y establecer el puerto raíz.

Elección de los puertos designados

Una vez elegido el puente raíz y los puertos raíz de los otros puentes pasamos a calcular los puertos designados de cada segmento de red. En cada enlace que exista entre dos switches habrá un puerto designado, el cual será el puerto del switch que tenga un menor coste para llegar al puente raíz, este coste administrativo será un valor que estará relacionado al tipo de enlace que exista en el puerto (Ethernet, FastEthernet, GigabitEthernet). Cada tipo de enlace tendrá un coste administrativo distinto, siendo de un coste menor el puerto con una mayor velocidad. Si hubiese empate entre los costes administrativos que tienen los dos switches para llegar al root bridge, entonces se elegirá como Designated Port, el puerto del switch que tenga un menor Bridge ID (BID).

Puertos bloqueados

Aquellos puertos que no sean elegidos como raíz ni como designados deben bloquearse. Estos puertos evitan los lazos.

Mantenimiento del Spanning Tree

El cambio en la topología puede ocurrir de dos formas:

El puerto se desactiva o se bloquea
El puerto pasa de estar bloqueado o desactivado a activado

Cuando se detecta un cambio el switch notifica al puente raíz dicho cambio y entonces el puente raíz envía por broadcast dicho cambio. Para ello, se introduce una BPDU especial denominada notificación de cambio en la topología (TCN). Cuando un switch necesita avisar acerca de un cambio en la topología, comienza a enviar TCN en su puerto raíz. La TCN es una BPDU muy simple que no contiene información y se envía durante el intervalo de tiempo de saludo. El switch que recibe la TCN se denomina puente designado y realiza el acuse de recibo mediante el envío inmediato de una BPDU normal con el bit de acuse de recibo de cambio en la topología (TCA). Este intercambio continúa hasta que el puente raíz responde.

Unidades de datos del protocolo puente

Las reglas anteriores describen una forma de determinar qué árbol de expansión será calculado por el algoritmo, pero las reglas como están escritas requieren el conocimiento de toda la red. Los puentes tienen que determinar el puente raíz y calcular las funciones de los puertos (de raíz, designados o bloqueados) con sólo la información que tienen. Para asegurarse de que cada puente tiene suficiente información, los puentes utilizan tramas de datos especiales llamados Unidades de Datos de Protocolo Puente (BPDU) para intercambiar información acerca de los identificadores de puentes y costes de la ruta raíz.

Un puente envía una trama de BPDU usando la dirección MAC única del propio puerto como dirección de origen, y una dirección de destino, la dirección multicast STP 01:80:C2:00:00:00.

Hay dos tipos de BPDU en la especificación original STP (The Rapid Spanning Tree (RSTP)) utiliza una BPDU RSTP específica:

Configuración de BPDU (CBPDU), utilizado para el cálculo de árbol de expansión.
Notificación de cambio de topología (TCN) BPDU utilizado para anunciar los cambios en la topología de red.

Los BPDU se intercambian regularmente (cada 2 segundos de forma predeterminada) y permiten a los switches realizar un seguimiento de cambios en la red y para iniciar y detener el reenvío de puertos según sea necesario.

Cuando un dispositivo se conecta primero a un puerto de un switch, no iniciará de inmediato a enviar datos. En su lugar, pasará por una serie de estados mientras procesa BPDU y determina la topología de la red. Cuando un host se une, como un ordenador, impresora o un servidor, el puerto siempre va a entrar en el estado de envío, aunque con un retraso de unos 30 segundos, mientras que pasa a través de la escucha y de los estados de aprendizaje (ver más abajo). El tiempo pasado en los estados de escucha y aprendizaje está determinado por un valor conocido como el retardo de envío (por defecto 15 segundos y fijado por el puente de la raíz).

Sin embargo, si es otro switch el que está conectado, el puerto puede permanecer en modo de bloqueo, si se determina que causaría un bucle en la red. La notificación de cambio de topología (TCN) BPDU se utiliza para informar a otros conmutadores de si el puerto cambia. Las tramas TCN se inyectan en la red mediante un switch que no sea root y propagado a la raíz. Tras la recepción de la TCN, el switch de la raíz establecerá una bandera de cambio de topología en su BPDU normal. Esta flag se propaga a todos los otros switches para instruirlos a envejecer rápidamente sus entradas de la tabla de reenvío.

Estado de los puertos

Los estados en los que puede estar un puerto son los siguientes:

Bloqueo: En este estado se pueden recibir BPDU's pero no las enviará. Las tramas de datos se descartan y no se actualizan las tablas de direcciones MAC (mac-address-table). Los switch comienzan en este estado ya que si realizan envíos (forwarding) podrían estar generando un loop o bucle.
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 de que la nueva ruta tenga un coste mayor, se vuelve al estado de Bloqueo. Las tramas de datos se descartan y no se actualiza la tabla de direcciones MAC (mac-address-table). 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 aprenden por primera vez). Se procesan las BPDU.
Envío: A este estado se llega desde Aprendizaje, en este estado el puerto puede enviar y recibir datos. 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 este falla. No se procesan las BPDU.