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)
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.
- Se comienza con un nodo v arbitrario
- El árbol se construye nodo por nodo
- 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
- 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.
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).
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.
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.
