Method and system for shortcut trunking of LAN bridges

• US 6,370,121 B1
• Filed: 06/29/1998
• Issued: 04/09/2002
• Est. Priority Date: 06/29/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hausman, Richard
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/107,023
• Time in Patent Office: 1,380 Days
• Field of Search: 370/241, 370/248, 370/252, 370/400, 370/401-2, 370/254, 370/256
• US Class Current: 370/256
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone

Abstract

The invention provides a method and system for routing traffic between LAN bridges. A method and system for enabling a blocked link to allow forwarding of traffic across the blocked link includes determining whether the blocked link is a point-to-point connection between two bridges, each one of the two bridges having a plurality of ports, ascertaining whether each one of the two bridges operates a Shortcut Trunking Exchange protocol, and calculating whether on at least one of the two bridges, a port cost of the blocked link is equal to or lower than a port cost of each other one of the plurality of ports. In addition, a method for selecting traffic to forward on a blocked link, the traffic having a source and a destination address, includes building an outside address list for a first bridge, the outside address list including each address “outside” the first bridge, building an outside address list for a second bridge, the outside address list including each address “outside” the second bridge, determining that the source and destination addresses are both “outside” the first and second bridges using the outside address lists for the first and second bridges, and forwarding the traffic if the traffic is unicast traffic when the source and destination addresses are both “outside” the first and second bridges.

Claims

1. A method for enabling a blocked link to allow forwarding of traffic on the blocked link, the method including the following steps:

determining whether the blocked link is a point-to-point connection between two bridges, each one of the two bridges having a plurality of ports; and

ascertaining whether each one of the two bridges operates a Shortcut Trunking Exchange protocol; and

calculating whether on at least one of the two bridges, a port cost of the blocked link is equal to or lower than a port cost of each other one of the plurality of ports.

2. The method according to claim 1, wherein the calculating step includes the following sub-steps:

locating a first bridge and a second bridge bordering the blocked link, the first and second bridges each having a plurality of ports;

determining for the first bridge a port cost of the blocked link; and

determining for the first bridge whether the port cost of the blocked link is of equal or lower cost than the port cost of a port for a spanning tree path connection between the bridges.

3. The method according to claim 2, wherein the calculating step includes the following sub-steps:

determining for the second bridge a port cost of the blocked link; and

determining for the second bridge whether the port cost of the blocked link is of equal or lower cost than the port cost of a port for a spanning tree path connection from the second bridge to a spanning tree root node.

4. A method for selecting traffic to forward on a blocked link, the traffic having a source and a destination address, the method including the following steps:

building an outside address list for a first bridge, the outside address list including each address “

outside”

the first bridge;

building an outside address list for a second bridge, the outside address list including each address “

outside”

the second bridge;

determining that the input interface and destination address are both “

outside”

the first and second bridges using the outside address lists for the first and second bridges; and

forwarding unicast traffic when the input interface and destination address are both “

outside”

the first and second bridges.

5. The method according to claim 4, wherein the determining step includes the following sub-steps:

sending from the first bridge a Shortcut Trunking Exchange protocol packet out every Spanning Tree Protocol enabled port of the first bridge to learn which Spanning Tree Protocol enabled port leads to the second bridge;

sending from the second bridge a Shortcut Trunking Exchange protocol packet out every Spanning Tree Protocol enabled port of the second bridge to learn which Spanning Tree Protocol enabled port leads to the first bridge;

sending an acknowledgment through the blocked link from the first bridge;

sending an acknowledgment through the blocked link from the second bridge;

building a shortcut address list for the first bridge based upon the outside address list for the first bridge, the shortcut address list excluding the Spanning Tree Protocol enabled port leading to the second bridge;

building a shortcut address list for the second bridge based upon the outside address list for the second bridge, the shortcut address list excluding the Spanning Tree Protocol enabled port leading to the first bridge;

sending the shortcut address list for the first bridge across the blocked link;

sending the shortcut address list for the second bridge across the blocked link; and

using the shortcut address lists for the first and second bridges to determine whether traffic should be forwarded across the blocked link.

6. The method according to claim 5, the method including the following sub-step:

adding an address to the shortcut address list for the first bridge.

7. The method according to claim 6, wherein the adding step includes the following sub-steps:

forwarding the address along the Spanning Tree Protocol enabled port leading to the second bridge; and

sending an acknowledgment from the second bridge across the blocked link to the first bridge.

8. The method according to claim 5, the method including the following step:

replacing an address from the shortcut address list for the first bridge with an received address for said shortcut address list.

9. The method according to claim 8, wherein the removing step includes the following sub-steps:

forwarding the address along the shortcut to the second bridge; and

sending an acknowledgment from the second bridge to the first bridge along the Spanning Tree Protocol enabled port leading to the first bridge.

10. A method for selecting one of two blocked links within a network, the two blocked links including a first shortcut link and a second shortcut link, the first shortcut link bordered by a bridge and a first shortcut bridge, the second shortcut link bordered by the bridge and a second shortcut bridge, the method including the following steps:

discovering an STP enabled port between the two shortcut bridges;

reporting from the first shortcut bridge to the bridge whether the STP enabled port between the two shortcut bridges is identical to an STP enabled port from the first shortcut bridge to the bridge;

reporting from the second shortcut bridge to the bridge whether the STP enabled port between the two shortcut bridges is identical to an STP enabled port from the second shortcut bridge to the bridge; and

selecting one of the two shortcut links when the first shortcut bridge reporting step and the second shortcut bridge reporting step indicate that the STP enabled port between the two shortcut bridges is identical to the STP enabled port from the first shortcut bridge to the bridge and identical to the STP enabled port from the second shortcut bridge to the bridge.

11. The method according to claim 10, wherein the selecting step includes the following sub-steps:

defining a multicast discovery frame;

sending the multicast discovery frame along each STP enabled path via a Shortcut Trunking Exchange protocol enabled bridge within the network;

appending a bridge address to the multicast discovery frame;

forwarding the multicast discovery frame along each remaining STP enabled port within the Shortcut Trunking Exchange protocol enabled bridge; and

shortcutting addresses requested by the first shortcut bridge and the second shortcut bridge to a bridge corresponding to an address list appended to the multicast discovery frame.

12. An apparatus for enabling a blocked link to allow forwarding of traffic on the blocked link, including:

means for determining whether the blocked link is a point-to-point connection between two bridges, each one of the two bridges having a plurality of ports; and

means for ascertaining whether each one of the two bridges operates a Shortcut Trunking Exchange protocol; and

means for calculating whether on at least one of the two bridges, a port cost of the blocked link is equal to or lower than a port cost of a port for a spanning tree path connection between the bridges.

13. The apparatus according to claim 12, wherein the means for calculating includes:

means for locating a first bridge and a second bridge bordering the blocked link, the first and second bridges each having a plurality of ports;

means for determining for the first bridge a port cost of the blocked link; and

means for determining for the first bridge whether the port cost of the blocked link is of equal or lower cost than the port cost of a port for a spanning tree path connection between the said first bridge and a spanning tree root node.

14. The apparatus according to claim 13, wherein the means for calculating includes:

means for determining for the second bridge a port cost of the blocked link; and

means for determining for the second bridge whether the port cost of the blocked link is of equal or lower cost than the port cost of a port for a spanning tree path to a spanning tree root node.

15. An apparatus for selecting traffic to forward on a blocked link, the traffic having a source and a destination address, the apparatus including:

means for building an outside address list for a first bridge, the outside address list including each address “

outside”

the first bridge;

means for building an outside address list for a second bridge, the outside address list including each address “

outside”

the second bridge;

means for determining that the source and destination addresses are both “

outside”

the first and second bridges using the outside address lists for the first and second bridges; and

means for forwarding the traffic if the traffic is unicast traffic when the source and destination addresses are both “

outside”

the first and second bridges.

16. The apparatus according to claim 15, wherein the means for determining includes:

means for sending from the first bridge a Shortcut Trunking Exchange protocol packet out every Spanning Tree Protocol enabled port of the first bridge to learn which Spanning Tree Protocol enabled port leads to the second bridge;

means for sending from the second bridge a Shortcut Trunking Exchange protocol packet out every Spanning Tree Protocol enabled port of the second bridge to learn which Spanning Tree Protocol enabled port leads to the first bridge;

means for sending an acknowledgment through the blocked link from the first bridge;

means for sending an acknowledgment through the blocked link from the second bridge;

means for building a shortcut address list for the first bridge based upon the outside address list for the first bridge, the shortcut address list excluding the Spanning Tree Protocol enabled port leading to the second bridge;

means for building a shortcut address list for the second bridge based upon the outside address list for the second bridge, the shortcut address list excluding the Spanning Tree Protocol enabled port leading to the first bridge;

means for sending the shortcut address list for the first bridge across the blocked link;

means for sending the shortcut address list for the second bridge across the blocked link; and

means for using the shortcut address lists for the first and second bridges to determine whether traffic should be forwarded across the blocked link.

17. The apparatus according to claim 16, the apparatus including means for adding an address to the shortcut address list for the first bridge.

18. The apparatus according to claim 17, wherein the means for adding includes:

means for forwarding the address along the Spanning Tree Protocol enabled port leading to the second bridge; and

means for sending an acknowledgment from the second bridge across the blocked link to the first bridge.

19. The apparatus according to claim 16, the apparatus including means for removing an address from the shortcut address list for the first bridge.

20. The apparatus according to claim 19, wherein the means for removing includes:

means for forwarding the address along the shortcut to the second bridge; and

means for sending an acknowledgment from the second bridge to the first bridge along the Spanning Tree Protocol enabled port leading to the first bridge.

21. An apparatus for selecting one of two blocked links within a network, the two blocked links including a first shortcut link and a second shortcut link, the first shortcut link bordered by a bridge and a first shortcut bridge, the second shortcut link bordered by the bridge and a second shortcut bridge, the apparatus including

means for discovering an STP enabled port between the two shortcut bridges;

means for reporting from the first shortcut bridge to the bridge whether the STP enabled port between the two shortcut bridges is identical to an STP enabled port from the first shortcut bridge to the bridge;

means for reporting from the second shortcut bridge to the bridge whether the STP enabled port between the two shortcut bridges is identical to an STP enabled port from the second shortcut bridge to the bridge; and

means for selecting one of the two shortcut links when the first shortcut bridge reporting step and the second shortcut bridge reporting step indicate that the STP enabled port between the two shortcut bridges is identical to the STP enabled port from the first shortcut bridge to the bridge and identical to the STP enabled port from the second shortcut bridge to the bridge.

22. The apparatus according to claim 21, wherein the means for selecting includes the following:

means for defining a multicast discovery frame;

means for sending the multicast discovery frame along each STP enabled path via a Shortcut Trunking Exchange protocol enabled bridge within the network;

means for appending a bridge address to the multicast discovery frame;

means for forwarding the multicast discovery frame along each remaining STP enabled port within the Shortcut Trunking Exchange protocol enabled bridge; and

means for shortcutting addresses requested by the first shortcut bridge and the second shortcut bridge to a bridge corresponding to an address last appended to the multicast discovery frame.

23. A method for routing traffic across a blocked link, the traffic having a source and a destination address, the method including the following steps:

determining whether the blocked link is a point-to-point connection between two bridges, each one of the two bridges having a plurality of ports; and

ascertaining whether each one of the two bridges operates a Shortcut Trunking Exchange protocol;

calculating whether on at least one of the two bridges, a port cost of the blocked link is equal to or lower than a port cost of a port for a spanning tree path;

building an outside address list for a first bridge, the outside address list including each address “

outside”

the first bridge;

building an address list for a second bridge, the outside address list including each address “

outside”

the second bridge;

determining that the source and destination addresses are both “

outside”

the first and second bridges using the outside address lists for the first and second bridges; and

forwarding the traffic if the traffic is unicast traffic when the source and destination addresses are both “

outside”

the first and second bridges.

24. An apparatus for routing traffic across a blocked link, the traffic having a source and a destination address, including:

means for determining whether the blocked link is a point-to-point connection between two bridges, each one of the two bridges having a plurality of ports; and

means for ascertaining whether each one of the two bridges operates a Shortcut Trunking Exchange protocol;

means for calculating whether on at least one of the two bridges, a port cost of the blocked link is equal to or lower than a port cost of a port for a spanning tree path;

means for building an outside address list for a first bridge, the outside address list including each address “

outside”

the first bridge;

means for building an outside address list for a second bridge, the outside address list including each address “

outside”

the second bridge;

means for determining that the source and destination addresses are both “

outside”

the first and second bridges using the outside address lists for the first and second bridges; and

means for forwarding the traffic if the traffic is unicast traffic when the source and destination addresses are both “

outside”

the first and second bridges.

25. A method for routing traffic in a network having a spanning tree, said spanning tree including a plurality of nodes in said network and a plurality of links coupling pairs of said nodes, said plurality of nodes including a root node and at least one non-root node, said plurality of links forming a path coupling each non-root node to said root node, and said plurality of links forming a path coupling a first said non-root node to a second said non-root node through said route node, said spanning tree including substantially all nodes in said network and excluding a set of links in said network, said method including steps for

determining a set of shortcut routes for said network, each said shortcut route including at least one link excluded from said spanning tree, each said shortcut route having a set of shortcut destinations associated therewith, said set of shortcut routes excluding a closed loop of links, whereby messages routed within a union of said spanning tree and said set of shortcut routes are not returned in a closed loop to a point of origin.

26. A method as in claim 25, wherein said steps for determining include

selecting a set of shortcut routes, each said shortcut route including at least one link excluded from said spanning tree;

associating a set of shortcut destinations with each said shortcut route, wherein said steps for associating include steps for transmitting a list of shortcut destinations to a node coupled to said shortcut route.

27. A method as in claim 26, wherein

said steps for transmitting are performed substantially periodically;

and

said list of shortcut destinations includes a substantially complete list.

28. A method as in claim 26, wherein

said steps for transmitting are performed substantially periodically;

and

said list of shortcut destinations includes a set of updates.

29. A method as in claim 26, wherein

said steps for associating include steps for, at least one said node coupled to said shortcut route, aging said shortcut destinations.