Este procedimiento opera en el nivel de enlace de datos. Cada puente asocia,

durante un tiempo de guarda, el puerto por donde es primero recibida una trama con una dirección MAC origen hasta que una trama unicast de respuesta confirma el camino bidireccional coincidente entre direcciones origen y destino. Cualquier trama del mismo origen recibida por otro puerto distinto es descartada. Cada puente reenvía por el resto de puertos, salvo los que supongan giros prohibidos (abajo-arriba), las tramas broadcast recibidas y desvía por el árbol de expansión (u opcionalmente devuelve) las tramas unicast con dirección de destino desconocida o caducada.

El protocolo puede funcionar con encapsulado en los puentes frontera o sin encapsulado, utilizando en este caso reemplazamiento de direcciones universales MAC en los puentes frontera por direcciones locales MAC. Opcionalmente, el establecimiento y control de caminos puede realizarse proactivamente por los puentes frontera, especialmente los puentes conectados a servidores.

Procedimiento de encaminamiento de tramas de datos y puente de red.

Campo técnico de la invención

La presente invención se encuadra en el marco de las tecnologías de la información y las comunicaciones en general, aplicándose más particularmente para las redes de área local (LAN) y metropolitanas (MAN), como por ejemplo las redes campus Ethernet.

Antecedentes de la invención

En la actualidad, las redes campus implantadas para la conexión de centros de enseñanza e investigación son redes troncales de alta velocidad (Gigabit Ethernet,...), integrando diferentes entornos y servicios (voz, datos, video) en una única infraestructura IP ("Internet Protocol"), soportando distancias de transmisión que pueden ir desde ámbito local hasta rangos idénticos a los de redes de área amplia (WAN).

El encaminamiento de las tramas en los puentes de red ("bridges", en inglés) para interconectar este tipo de redes que actualmente se usa es derivado del definido en el estándar IEEE 802.1D. Pero el uso de los actuales protocolos estándar de Árbol de Expansión (STP: "Spanning Tree Protocol", en inglés) en los puentes 802.1D tiene, para la implantación de redes de tamaño medio o grande, las siguientes carencias:

- Se infrautiliza mucha infraestructura costosa debido a los enlaces bloqueados por el Árbol de Expansión (STP) y se produce congestión en los enlaces activos.

- Hay que asignar y gestionar las direcciones IP, y la dirección IP cambia al cambiar el usuario de lugar de conexión.

- Deben fragmentarse los dominios de conmutación para limitar la propagación de problemas tales como tormentas de tramas. Para ello, se requiere emplear encaminadores o enrutadores de nivel de red ("routers", en inglés), o bien utilizar Conmutadores Multicapa para fragmentar en subredes más pequeñas.

- Cuando se emplean redes LAN virtuales (VLANs), estandarizadas según IEEE 802.1Q, para separar el tráfico y los dominios de difusión dentro del dominio conmutado, es posible utilizar de forma eficiente la infraestructura, pero es necesario configurar y administrar las VLANs, así como diseñar y configurar los Árboles de Expansión según el estándar 802.1Q, para luego asignar las VLAN a los mismos.

- Por otra parte, la tecnología de Árboles Múltiples De Expansión (MSTP: "Múltiple Spanning Tree Protocol") es un terreno escasamente explorado en la práctica fuera del estándar (IEEE 802.1s y 802.1Q-2003) y susceptible de optimización. El MSTP es una extensión del Árbol De Expansión Rápida (RSTP) que, a su vez, es una evolución de la primera especificación del estándar 802.1D donde se define el STP: RSTP se define en la norma 802.1w, que pasó a ser la edición del año 2004 (802.1D-2004) de la 802.1D.

También son conocidos los conmutadores con encaminamiento centralizado que se usan en Autonet ["Autonet: A High-Speed, Self-Configuring Local Area Network Using Point-to-Point Links" de M. Shoreder et al., IEEE Journal on Selected Areas in Communications, Vol. 9, No. 8, p. 1318-1335, 1991]. El mecanismo de encaminamiento que utiliza Autonet se denomina encaminamiento arriba/abajo ("Up/Down routing", en inglés) y se basa en asignar un sentido a todos los enlaces de la red según la posición del vértice del enlace en el árbol de distribución: arriba, si está mas cercano al Puente Raíz (el nodo del árbol que no tiene padre); hacia abajo, si es al contrario. Para ello, se asignan identificadores crecientes a los puentes partiendo del puente raíz y descendiendo nivel a nivel hasta los Puentes Hoja (los que no tienen hijos; un nodo A es padre de B si existe un enlace de A al nodo B). Los enlaces entre nodos a la misma altura reciben la orientación según la identidad del puente sea mayor o menor. Una ruta legal es la que nunca usa/atraviesa un enlace en la dirección hacia arriba después de haber usado uno hacia abajo, es decir, se evitan los bucles prohibiendo los giros abajo-arriba.

Una evolución del encaminamiento arriba/abajo la constituyen los algoritmos basados en Prohibición de Giros (TP: "Turn-Prohibition", en inglés) [por ejemplo, "Application of Network Calculus to General Topologies using Turn-Prohibition" de L. Starobinski et al., IEEE INFOCOM 2002 p. 1151-1159, 2002]. Los algoritmos de Prohibición de Giros operan normalmente en dos fases: en la primera se define el conjunto de giros prohibidos y posteriormente se construyen las tablas de encaminamiento. La definición de los giros prohibidos consta a su vez de tres fases: construcción del árbol de expansión, etiquetado de nodos según el árbol de expansión y algoritmo de definición del conjunto de giros prohibidos.

Otra solución existente es el encaminamiento jerárquico RSJ (Protocolo RSTAA-STAR Jerárquico) que se propone en la Tesis Doctoral de G. Ibáñez ["Contribución al diseño de redes campus Ethernet autoconfigurables", Universidad Carlos III de Madrid, 2005; disponible también en http://enjambre.it.uc3m.es/∼gibanez/tesisgif69.pdf]. No obstante, las direcciones en RSJ son de longitud variable, no utilizables dentro de los campos estándar de una trama Ethernet, por lo que se requiere un encapsulado adicional de la trama. El RSJ es una extensión del protocolo STAR ("Spanning Tree Alternate Routing Protocol") y no resuelve los bucles por caminos transversales en el árbol.

Otra solución, denominada HURP ["Hierarchical Up/Down routing architecture for ethernet backbones and campus networks", Ibáñez, G. A., et al., IEEE Conference on Computer Communications Workshops, INFOCOM, p.p. 1-6, 13-18 April 2008] es una arquitectura de encaminamiento de nivel dos que se basa en la asignación a cada nodo de un identificador jerárquico mediante un mecanismo asociado al protocolo RSTP ("Rapid Spanning Tree Protocol"). Utiliza una versión mejorada del protocolo arriba/abajo (U/D) para prohibir determinados giros en determinados nodos en lugar de inhabilitar enlaces (tal como hace RSTP) para garantizar caminos sin bucles. Este protocolo tiene un rendimiento similar o mejor que otros también basados en prohibición de giros y además presenta una menor complejidad O(Nd) y mejor escalabilidad. HURP mejora el rendimiento de U/D gracias al conocimiento que sobre la topología de la red le proporcionan las direcciones MAC locales jerárquicas (HLMAC: "Hierarchical Local MAC"). Así, están permitidos los giros que alcanzan bien el nodo destino bien la rama del árbol que contiene al destino, aunque constituyan giros prohibidos para un reenvío cualquiera, gracias a que una vez la trama alcanza la rama destino del árbol ya es reenviada sobre ella sin necesidad de nuevas decisiones de encaminamiento. Cada puente debe comprobar si alguno de sus vecinos es un prefijo o contiene la dirección HLMAC del destino, para proceder al reenvío independientemente del algoritmo de prohibición de giros. Esta solución emplea encaminamiento por los enlaces transversales implementado en el plano de control (intercambio de tablas entre puentes).

Antecedentes en la utilización de enlaces transversales más rápidos en las redes de puentes son:

- DLS (Distributed Load Sharing) que se propone en US 4811337, donde dos puentes pueden acordar encaminar el tráfico entre ellos por enlaces no pertenecientes al árbol de expansión (enlaces transversales) si dicho enlace cumple ciertas condiciones: (i) los dos puentes en los extremos del enlace seleccionado implementan DLS, (ii) los dos puentes de los extremos no pueden ser uno antecesor del otro en el árbol de expansión y (iii) la longitud del camino asociada con el enlace seleccionado debe ser menor que la suma de las longitudes de dichos puentes al puente raíz. Pero DLS puede sobreestimar la longitud real del camino por el árbol de expansión, por lo que puede elegir enlaces de camino más largo. DLS es compatible con el protocolo estándar 802.1D por lo que los puentes DLS pueden desplegarse en una red de puentes 802.1D.

- GDLS (Generalized DLS) que se propone en US 5150360 es una extensión y simplificación de la propuesta anterior para evitar algunos inconvenientes de DLS, eliminando las condiciones establecidas en DLS para el uso de enlaces transversales (no perteneciente al árbol) al permitir que cada enlace transversal sea elegible para reenvió de tramas. GDLS no compara la longitud del enlace transversal con la del camino vía árbol, sino que estima la velocidad de transmisión entre árboles midiendo el retardo mediante una trama de datos específica del protocolo (BPDU: Bridge Protocol Data Units) intercambiada entre los puentes...

1. Procedimiento de encaminamiento de tramas de datos a través de una pluralidad de puentes de red multipuerto conectados mediante enlaces punto a punto que soportan dos sentidos de propagación, formando un árbol de expansión a partir de un puente de red raíz (R) con respecto al que cada puente de red tiene una distancia, que comprende:

- asignar a cada puente de red del árbol de expansión una dirección en correspondencia con la distancia al puente de red raíz (R),

caracterizado porque adicionalmente comprende:

- recibir en un puente de red una trama, que contiene una dirección MAC origen, a través de un puerto del puente que tiene una identidad de puerto asignada,

- asociar en el puente la identidad del puerto que primero recibe la trama con la dirección MAC origen de la trama, con un indicador de caducidad de la dirección MAC origen y con un tiempo de guarda durante el que se mantiene inmodificable la asociación dirección MAC origen-identidad del puerto,

- descartar por el puente de red todas las tramas con la misma dirección MAC origen recibidas a través de un puerto del puente con una identidad de puerto distinta a la de la asociación dirección MAC origen-identidad del puerto.

2. Procedimiento según la reivindicación 1, caracterizado porque, si la trama recibida contiene una dirección MAC de destino de difusión, adicionalmente comprende enviar la trama a través de todos los puertos del puente que tienen una identidad de puerto distinta a la de la asociación identidad del puerto-dirección MAC origen de la trama.

3. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque, si la trama recibida contiene una dirección MAC unidestino diferente a la dirección MAC origen de la asociación dirección MAC origen-identidad del puerto de todos y cada uno de los puertos del puente que recibe la trama, adicionalmente comprende modificar la trama recibida sustituyendo la dirección MAC unidestino por la dirección MAC origen de la trama recibida y enviar la trama modificada a través del puerto del puente por el que se ha recibido.

4. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque, si la trama recibida contiene una dirección MAC unidestino igual a la dirección MAC origen de la asociación dirección MAC origen-identidad del puerto y el indicador de caducidad indica que la dirección está caducada, adicionalmente comprende modificar la trama recibida sustituyendo la dirección MAC unidestino por la dirección MAC origen de la trama recibida y enviar la trama modificada a través del puerto del puente por el que se ha recibido.

5. Procedimiento según cualquiera de las reivindicaciones 3 y 4, caracterizado porque adicionalmente comprende:

- recibir la trama modificada en un puente frontera conectado a un equipo terminal que tiene la dirección de destino contenida en la trama modificada,

- enviar desde el puente frontera una trama con dirección MAC de destino de difusión y dirección MAC origen igual a la dirección del puente frontera,

- recibir la trama con dirección MAC de destino de difusión en un puente de red a través de un puerto y modificar la trama sustituyendo la dirección MAC origen por la dirección del puente de red y la dirección MAC de destino de difusión por la dirección del puente frontera,

- enviar desde el puente la trama con dirección MAC origen igualada a la dirección del puente a través del puerto cuya identidad de puerto es la de la asociación dirección MAC origen-identidad del puerto en el puente.

6. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque adicionalmente comprende enviar periódicamente unas tramas trazadoras entre dos puentes frontera, un puente frontera origen que envía y un puente frontera destino que recibe, a través de un enlace en los dos sentidos de propagación, las tramas trazadoras conteniendo una dirección origen igual a la dirección del puente frontera que envía.

7. Procedimiento según la reivindicación 6, caracterizado porque las tramas trazadoras contienen una dirección destino que es igual a la dirección del puente frontera que recibe.

8. Procedimiento según la reivindicación 6, caracterizado porque las tramas trazadoras contienen una dirección destino que es de difusión.

9. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque la dirección MAC origen de la trama recibida en un puente se selecciona entre una dirección MAC universal, dirección MAC local y dirección MAC local y jerárquica.

10. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque la dirección asignada a cada puente de red del árbol de expansión es una dirección MAC local.

11. Procedimiento según la reivindicación 10, caracterizado porque la dirección asignada a cada puente de red del árbol de expansión es una dirección MAC local y jerárquica.

12. Procedimiento según cualquiera de las reivindicaciones 1 a 9, caracterizado porque la dirección asignada a cada puente frontera conectado a un equipo terminal está formada por una dirección MAC universal y un identificador en correspondencia a la distancia del puente frontera al puente de red raíz (R).

13. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque, cuando se recibe la trama en un puente frontera conectado a un equipo terminal, adicionalmente comprende encapsular la trama con una cabecera que contiene una dirección origen y una dirección destino que son direcciones MAC locales y jerárquicas.

14. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque, cuando se recibe la trama en un puente frontera conectado a un equipo terminal a través de un puerto designado con una dirección MAC local y jerárquica y la trama contiene una dirección origen que es una dirección MAC universal, el puente frontera sustituye en la dirección origen la dirección MAC universal por la dirección MAC local y jerárquica del puerto designado.

15. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque usa el protocolo de resolución de direcciones ARP.

16. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque usa prohibición de giros aplicables a encaminamiento arriba/abajo.

17. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque, si la trama recibida contiene una dirección MAC origen que es una dirección MAC universal y una dirección MAC unidestino que tiene asociado en el puente que la recibe un indicador de caducidad indicando que la dirección está caducada, adicionalmente comprende:

- borrar del puente la asociación con la dirección MAC unidestino,

- modificar la trama recibida sustituyendo la dirección MAC unidestino por una dirección MAC de multidifusión,

- enviar la trama modificada a la dirección MAC origen.

18. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque, si la trama recibida contiene una dirección MAC origen que es una dirección MAC local y jerárquica y una dirección MAC unidestino que tiene asociado en el puente que la recibe un indicador de caducidad indicando que la dirección está caducada, adicionalmente comprende:

- borrar del puente la asociación con la dirección MAC unidestino,

- modificar la trama recibida sustituyendo la dirección MAC unidestino por la dirección MAC local y jerárquica contenida en la dirección MAC origen de la trama recibida, y sustituyendo la dirección MAC origen de la trama por una dirección MAC local y jerárquica asignada al puente que la recibe;

- enviar la trama modificada a la dirección MAC local y jerárquica contenida en la dirección MAC origen de la trama recibida.

19. Procedimiento según la reivindicación 18, caracterizado porque la dirección MAC local y jerárquica contenida en la dirección MAC origen de la trama recibida corresponde a un equipo terminal.

20. Procedimiento según la reivindicación 18, caracterizado porque la dirección MAC local y jerárquica contenida en la dirección MAC origen de la trama recibida corresponde a un puente frontera conectado a un equipo terminal.

21. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque, si la trama recibida contiene una dirección MAC origen que es una dirección MAC universal y una dirección MAC unidestino que corresponde a un puente que está caído o está conectado al puente receptor de la trama mediante un enlace en el que se ha detectado una caída, adicionalmente comprende:

- borrar del puente receptor de la asociación con la dirección MAC unidestino,

- modificar la trama recibida sustituyendo la dirección MAC unidestino por una dirección MAC multidifusión,

- enviar la trama modificada a la dirección MAC origen.

22. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque, si la trama recibida contiene una dirección MAC origen que es una dirección MAC local y jerárquica y una dirección MAC unidestino que corresponde a un puente que está caído o está conectado al puente receptor de la trama mediante un enlace en el que se ha detectado una calda, adicionalmente comprende:

- borrar del puente receptor de la trama la asociación con la dirección MAC unidestino,

- modificar la trama recibida sustituyendo la dirección MAC unidestino por la dirección MAC local y jerárquica contenida en la dirección MAC origen de la trama recibida, y sustituyendo la dirección MAC origen de la trama por una dirección MAC local y jerárquica asignada al puente receptor de la trama;

- enviar la trama modificada a la dirección MAC local y jerárquica contenida en la dirección MAC origen de la trama recibida.

23. Procedimiento según la reivindicación 22, caracterizado porque la dirección MAC local y jerárquica contenida en la dirección MAC origen de la trama recibida corresponde a un equipo terminal.

24. Procedimiento según la reivindicación 22, caracterizado porque la dirección MAC local y jerárquica contenida en la dirección MAC origen de la trama recibida corresponde a un puente frontera conectado a un equipo terminal.

25. Procedimiento según cualquiera de las reivindicaciones anteriores, caracterizado porque adicionalmente comprende etiquetar en el puente la trama recibida con una etiqueta VLAN que se selecciona entre etiqueta de la VLAN del árbol de expansión y etiqueta VLAN de la red de puentes que operan según la reivindicación 1.

26. Puente de red multipuerto caracterizado porque comprende medios de procesamiento configurados para encaminar tramas en el nivel de enlace de datos y en el plano de usuario de acuerdo con el procedimiento de encaminamiento de tramas de datos definido según cualquiera de las reivindicaciones 1 a 25.

27. Red de telecomunicaciones conmutada caracterizada porque comprende al menos un puente de red definido según la reivindicación 26 conectado a un puente de red raíz (R) en un árbol de expansión.