Utilization of redundant links in bridged networks

Abstract

A method and related apparatus for establishing a point-to-point cross-link between two bridges in a bridged communication network. The bridged communication network is first configured in a loop-free arrangement by a spanning tree algorithm that selects which links of every bridge to activate in order to form the spanning tree active configuration. Then at least one cross-link not defined by the spanning tree configuration is established for routing of messages as an alternative to a spanning tree path. A protocol in each bridge ensures that no loops are formed and that only messages to preselected locations are passed over the cross-link. An optional optimization procedure measures message propagation times in both directions between the two bridges and over both the cross-link path and the spanning tree path, to determine whether to modify usage of the cross-link. Selection of the bridges for the formation of the cross-link, and selection of the destination stations for cross-link traffic, are independent of the location of a root bridge in the spanning tree configuration.

We claim: 
     
       1. In a bridged communication network that has been pruned to form a loop-free spanning tree configuration having a root bridge, a method of exchanging messages between stations, through a point-to-point cross-link outside the spanning tree configuration, the method comprising the steps of: identifying a cross-link between any two bridges in the network, wherein the cross-link exists outside the spanning tree configuration;   selecting in at least one of the two bridges a set of destination stations for receipt of messages to be transmitted over the cross-link, the destination stations being selected without regard to their locations with respect to the root bridge in the spanning tree configuration;   advising the other of the two bridges of the identities of the selected destination stations;   examining each message received over the spanning tree at the other of the two bridges to determine if the intended destination of the message qualifies as one of the selected stations; and   forwarding the message over the cross-link if the destination station in the message qualifies.   
     
     
       2. A method as defined in claim 1, wherein the step of identifying a cross-link includes the steps of: transmitting a cross-link greeting message from each bridge in the network having inactive links not included in the spanning tree configuration, the cross-link greeting message being transmitted along each of the inactive links and containing the identity of the bridge transmitting the message; and   receiving a cross-link greeting message in at least one bridge that transmitted such a message, wherein the existence of at least one cross-link between two bridges is established and each of the two bridges is made aware of the identity of the other.   
     
     
       3. A method as defined in claim 2, and further comprising, after identifying a cross-link, the steps of: transmitting from each of the two bridges a spanning tree greeting message that is transmitted to the other bridge over the spanning tree configuration; and   recording in each bridge the identity of a spanning tree link through which the spanning tree message from the other bridge is received.   
     
     
       4. A method as defined in claim 3, wherein the step of selecting a set of destinations includes the step of: excluding stations that are reached through the spanning tree link through which the spanning tree greeting was received from the other bridge.   
     
     
       5. A method as defined in claim 1, wherein the step of advising the other bridge of the identities of the selected destination stations includes: transmitting messages to the other bridge adding to the set of selected destination stations; and   transmitting messages to the other bridge removing selected stations from the set of selected destination stations.   
     
     
       6. A method as defined in claim 3, wherein the step of examining each message received over the spanning tree includes: determining whether the received message was received through the spanning tree link through which the spanning tree greeting was received from the other bridge; and, if so,   dropping the received message as possibly invalid.   
     
     
       7. A method as defined in claim 3, and further including the steps of: examining each message received at each bridge through the cross-link;   determining whether the message destination is valid; and, if so,   forwarding the message toward its destination station.   
     
     
       8. A method as defined in claim 7, wherein the step of determining if the message destination is valid includes the step of dropping the message if any of the following conditions is true: the destination station contained in the message is not in the set of destination stations previously selected by this bridge;   the destination station contained in the message is located in a direction along the spanning tree link through which the spanning tree greeting was received from the other bridge; and   the destination station contained in the message is not one whose directional location on the spanning tree is known.   
     
     
       9. A method as defined in claim 1, and further comprising the steps of: transmitting from at least one of the two bridges a first timing message destined for the other bridge and coded for transmission over the cross-link;   transmitting from the same bridge from which the first timing message was transmitted, a second timing message also destined for the other bridge and coded for transmission over the spanning tree;   measuring propagation times of the first and second messages; and   modifying the set of destination stations associated with other bridge, in accordance with the measured message propagation times.   
     
     
       10. A method as defined in claim 9, wherein the step of modifying the set of destination stations includes: expanding the set of destination stations if the message propagation time through the cross-link is less than the message propagation time through the spanning tree; and   reducing the set of destination stations if the message propagation time through the cross-link is greater than the message propagation time through the spanning tree.   
     
     
       11. A method as defined in claim 9, wherein: the steps of transmitting timing messages and measuring propagation times are performed only when the cross-link is first established; and   the step of modifying the set of destination stations includes reducing the set to zero if the message propagation time through the cross-link is less than the propagation time through the spanning tree.   
     
     
       12. A method as defined in claim 9, wherein: the steps of transmitting timing messages and measuring propagation times and modifying the set of destination stations are performed periodically to optimize usage of the cross-link.   
     
     
       13. For use in a bridged communication network that has been pruned to form a loop-free spanning tree configuration having a root bridge, a method of establishing and using a cross-link between two bridges, such that the cross-link is not in the spanning tree configuration, the method comprising the steps of: transmitting a cross-link greeting message from each bridge in the network having inactive links no included in the spanning tree configuration, the cross-link greeting message being transmitted along each of the inactive links and containing the identity of the bridge transmitting the message;   receiving a cross-link greeting message in at least one bridge that transmitted such a message, wherein the existence of at least one cross-link between two bridges is established and each bridge is made aware of the identity of the other;   identifying at each of the two bridges a spanning tree link through which communication can take place with the other of the two bridges over the spanning tree;   selecting at each of the two bridges a set of destination stations for receipt of messages to be transmitted over the cross-link, wherein the stations are selected without regard to their locations relative to the root bridge of the spanning tree configuration, and wherein each selected station is not reached through the spanning tree link leading to the other bridge;   advising the other of the two bridges of the identities of the selected destination stations;   examining each message received over the spanning tree at each of the two bridges to determine if the intended destination of the message qualifies as one of the destination stations selected by the other of the bridges;   forwarding the message over the cross-link if the destination station in the message qualifies;   examining each message received through the cross-link at each of the two bridges to determine that the message contains a valid destination address; and   forwarding the message toward its destination station if the destination address qualifies.   
     
     
       14. A method as defined in claim 13, wherein the step of selecting a set of destinations includes the step of: excluding stations that are reached through the spanning tree link leading to the other bridge.   
     
     
       15. A method as defined in claim 13, wherein the step of advising the other bridge of the identities of the selected destination stations includes: transmitting messages to the other bridge adding to the set of selected destination stations; and   transmitting messages to the other bridge removing selected stations from the set of selected destination stations.   
     
     
       16. A method as defined in claim 13, wherein the step of examining each message received over the spanning tree includes: determining whether the received message was received through the spanning tree link leading to the other bridge; and, if so,   dropping the received message as possibly invalid.   
     
     
       17. A method as defined in claim 13, wherein the step of examining each message received over the cross-link includes the step of dropping the message if any of the following conditions is true: the destination station contained in the message is not in the set of destination stations previously selected by this bridge;   the destination station contained in the message is located in a direction along the spanning tree link through which the spanning tree greeting was received from the other bridge; and   the destination station contained in the message is not one whose directional location on the spanning tree is known.   
     
     
       18. A method as defined in claim 13, and further comprising the steps of: transmitting from each of the two bridges a first timing message destined for the other bridge and coded for transmission over the cross-link;   transmitting from each of the two bridges a second timing message destined for the other bridge and coded for transmission over the spanning tree;   measuring propagation times of the first and second messages at the others of the two bridges; and   modifying the set of destination stations associated with each of the bridges, in accordance with the measured message propagation times.   
     
     
       19. A method as defined in claim 18, wherein the step of modifying the set of destination stations includes: expanding the set of destination stations if the message propagation time through the cross-link is less than the message propagation time through the spanning tree; and   reducing the set of destination stations if the message propagation time through the cross-link is greater than the message propagation time through the spanning tree.   
     
     
       20. A method as defined in claim 18, wherein: the steps of transmitting timing messages and measuring propagation times are performed only when the cross-link is first established; and   the step of modifying the set of destination stations includes reducing the set to zero if the message propagation time through the cross-link is less than the propagation time through the spanning tree.   
     
     
       21. A method as defined in claim 18, wherein: the steps of transmitting timing messages and measuring propagation times and modifying the set of destination stations are performed periodically to optimize usage of the cross-link.   
     
     
       22. In a bridged communication network that has been pruned to form a loop-free spanning tree configuration having a root bridge, apparatus for exchanging messages between stations, through a point-to-point cross-link outside the spanning tree configuration, the apparatus comprising: means for identifying a cross-link between any two bridges in the network, wherein the cross-link exists outside the spanning tree configuration;   means for selecting at each of the two bridges a set of destination stations for receipt of messages to be transmitted over the cross-link, the destination stations being selected without regard to their locations with respect to the root bridge in the spanning tree configuration;   means for advising the other of the two bridges of the identities of the selected destination stations;   means for examining each message received over the spanning tree at each of the two bridges to determine if the intended destination of the message qualifies as one of the destination stations selected by the other of the bridges; and   means for forwarding the message over the cross-link if the destination station in the message qualifies.   
     
     
       23. Apparatus as defined in claim 22, wherein the means for identifying a cross-link includes: means for transmitting a cross-link greeting message from each bridge in the network having inactive links not included in the spanning tree configuration, the cross-link greeting message being transmitted along each of the inactive links and containing the identity of the bridge transmitting the message; and   means for receiving a cross-link greeting message in at least one bridge that transmitted such a message, wherein the existence of at least one cross-link between two bridges is established and each bridge is made aware of the identity of the other.   
     
     
       24. Apparatus as defined in claim 23, and further comprising: means for transmitting a spanning tree greeting message from each of the two bridges, the spanning tree greeting message being transmitted to the other bridge over the spanning tree configuration; and   means for recording in each bridge the identity of a spanning tree link through which the spanning tree message from the other bridge is received.   
     
     
       25. Apparatus as defined in claim 24, wherein the means for selecting a set of destinations includes: means for excluding stations that are reached through the spanning tree link through which the spanning tree greeting was received from the other bridge.   
     
     
       26. Apparatus as defined in claim 22, wherein the means for advising the other bridge of the identities of the selected destination stations includes: means for transmitting messages to the other bridge adding to the set of selected destination stations; and   means for transmitting messages to the other bridge removing selected stations from the set of selected destination stations.   
     
     
       27. Apparatus as defined in claim 22, and further comprising: means for transmitting from each of the two bridges a first timing message destined for the other bridge and coded for transmission over the cross-link;   means for transmitting from each of the two bridges a second timing message destined for the other bridge and coded for transmission over the spanning tree;   means for measuring propagation times of the first and second messages at the others of the two bridges; and   means for modifying the set of destination stations associated with each of the bridges, in accordance with the measured message propagation times.   
     
     
       28. Apparatus as defined in claim 27, wherein the means for modifying the set of destination stations includes: means for expanding the set of destination stations if the message propagation time through the cross-link is less than the message propagation time through the spanning tree; and   means for reducing the set of destination stations if the message propagation time through the cross-link is greater than the message propagation time through the spanning tree.