Technique for efficiently managing bandwidth registration for multiple spanning tree options

• US 20070263554A1
• Filed: 05/10/2006
• Published: 11/15/2007
• Est. Priority Date: 05/10/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Finn, Norman
• Granted Patent: US 8,144,577 B2
• Time in Patent Office: Days
• US Class Current: 370/256
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 12/4691 GVRP [GARP VLAN registration protocol]
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees

Abstract

A technique efficiently manages bandwidth (BW) registration for multiple spanning tree options in a computer network. According to the novel technique, an entry bridge determines multiple spanning tree paths to other bridges of the network (namely, one or more available spanning trees rooted at one or more bridges of the network) and determines a utilized (registered) BW on each of those paths. Upon receiving a request to initiate BW registration for a data flow to a destination end point, e.g., from an application source end point, the entry bridge selects one of the spanning tree paths to utilize for the data flow. Selection of the spanning tree path from among the multiple available paths may be based on (i) available bandwidth of the paths, (ii) a shortest of the paths, and (iii) a lowest bridge identifier ID for the bridge root for the path. The entry bridge sends a registration message for the data flow towards the destination end point along the selected spanning tree path. If successful, the data flow is transmitted on the selected path. If not, the entry bridge attempts to register the data flow on a next best alternate spanning tree, e.g., until a successful registration or until a determination that no further alternate spanning trees exist.

Claims

1. A method for use at an entry bridge for efficiently managing bandwidth (BW) registration for multiple spanning tree options in a computer network, the method comprising:

determining a plurality of spanning tree paths to one or more other bridges of the network;

determining a registered BW on each of the spanning tree paths;

receiving a request to initiate BW registration for a data flow from a source end point to a destination end point; and

, in response

selecting one of the plurality of spanning tree paths to utilize for the data flow based on the registered BW on each of the spanning tree paths.

2. The method as in claim 1, wherein the step of determining a plurality of spanning tree paths further comprises:

determining a spanning tree rooted at each of the one or more other bridges of the network.

3. The method as in claim 1, wherein the step of selecting one of the plurality of spanning tree paths further comprises:

determining which spanning tree path to utilize based on a remaining available bandwidth of the spanning tree paths, and a metric of the spanning tree paths.

4. The method as in claim 3, further comprising:

determining that two or more spanning tree paths have sufficient remaining available bandwidth for the data flow, and that the two or more spanning tree paths have equal metrics; and

selecting the one of the plurality of spanning tree paths to utilize for the data flow based on a bridge identifier (ID) for a bridge root for the two or more spanning tree paths having equal metrics.

5. The method as in claim 3, wherein the cost is a length of the spanning tree paths.

6. The method as in claim 1, further comprising:

sending a registration message for the data flow toward the destination end point along the selected spanning tree path.

7. The method as in claim 6, further comprising:

determining that the registration is successful; and

transmitting the data flow on the selected spanning tree path.

8. The method as in claim 7, further comprising:

informing the source end point of the selected spanning tree to utilize for the data flow.

9. The method as in claim 7, further comprising:

detecting the data flow; and

placing traffic of the data flow on the selected spanning tree.

10. The method as in claim 6, further comprising:

determining that the registration is unsuccessful; and

, in response

determining whether an alternate spanning tree path of the plurality of spanning tree paths may be utilized for the data flow; and

, if so,

sending a registration message for the data flow toward the destination end point along the selected alternate spanning tree path.

11. The method as in claim 10, further comprising:

determining that the registration along the selected alternate spanning tree path is successful; and

transmitting the data flow on the selected alternate spanning tree path.

12. The method as in claim 10 further comprising:

performing the steps of the method of claim 10 until one of either a successful registration or determining that no further alternate spanning trees exist.

13. The method as in claim 1, further comprising:

using a virtual local area network (VLAN) identifier (VID) to indicate which selected spanning tree path to utilize.

14. The method as in claim 1, further comprising:

determining that the selected spanning tree path is not rooted at the entry bridge and; and

utilizing a special forwarding to be kept separate from conventional forwarding of a spanning tree path that is rooted at the entry bridge.

15. A bridge for use with efficiently managing bandwidth (BW) registration for multiple spanning tree options in a computer network, the bridge comprising:

two or more network ports;

a processor coupled to the two or more ports and adapted to execute software processes; and

a memory adapted to store a BW management process executable by the processor, the BW management process configured to;

i) determine a plurality of spanning tree paths to one or more other bridges of the network, ii) determine a registered BW on each of the spanning tree paths, iii) receive a request to initiate BW registration for a data flow from a source end point to a destination end point, and, iv) in response, select one of the plurality of spanning tree paths to utilize for the data flow based on the registered BW on each of the spanning tree paths.

16. An apparatus for use at an entry bridge for efficiently managing bandwidth (BW) registration for multiple spanning tree options in a computer network, the apparatus comprising:

means for determining a plurality of spanning tree paths to one or more other bridges of the network;

means for determining a registered BW on each of the spanning tree paths;

means for receiving a request to initiate BW registration for a data flow from a source end point to a destination end point; and

, in response

means for selecting one of the plurality of spanning tree paths to utilize for the data flow based on the registered BW on each of the spanning tree paths.

17. A computer readable medium containing executable program instructions for efficiently managing bandwidth (BW) registration for multiple spanning tree options in a computer network, the computer readable medium adapted for execution on an entry bridge of the network, the executable program instructions comprising program instructions for:

determining a plurality of spanning tree paths to one or more other bridges of the network;

determining a registered BW on each of the spanning tree paths;

receiving a request to initiate BW registration for a data flow from a source end point to a destination end point; and

, in response

selecting one of the plurality of spanning tree paths to utilize for the data flow based on the registered BW on each of the spanning tree paths.