Methods and devices for improving the multiple spanning tree protocol

• US 7,889,681 B2
• Filed: 07/14/2005
• Issued: 02/15/2011
• Est. Priority Date: 03/03/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Finn, Norman
• Primary Examiner(s): Ryman; Daniel J
• Assistant Examiner(s): Oh; Andrew
• Application Number:
  US11/182,564
• Publication Number:
  US 20060198323A1
• Time in Patent Office: 2,042 Days
• Field of Search: 370/256
• US Class Current: 370/256
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 12/4645 Details on frame tagging routing of packets H04L45/00; support for virtual LAN H04L49/354
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

The present invention provides improved unicast routing, multicast routing and unicast load sharing as compared with conventional methods. Preferred implementations of the invention provide improvements to IEEE 802.1Q. According to preferred aspects of the invention, each bridge is the root of its own multiple spanning tree instance (“MSTI”). Preferred implementations of the invention require no learning of media access control (“MAC”) addresses on the backbone of a network. Some methods of the invention can resolve spanning tree asymmetries. Preferred implementations of the invention require a very low computational load for control protocols.

Claims

1. A method of controlling a network having a plurality of bridges, the method comprising:

configuring a bridge in a region of the network as a root of a respective Multiple Spanning Tree Instance (“

MSTI”

) after such bridge receives one or more frames from a device that does not specify another root or another MSTI; and

sending from the bridge unicast frames according to an MSTI having another receiving bridge as a root bridge;

wherein a field of the unicast frames has one bit for each MSTI of the region; and

resetting at the bridge a bit of the field of the unicast frames sent from the bridge and such bit being reset for an individual MSTI to “

No”

whenever another unicast frame is received on a port of the bridge that is not a root port of the individual MSTI.

2. The method of claim 1, further comprising sending multicast frames according to an MSTI having a sending bridge as a root bridge.

3. The method of claim 1, wherein access ports use simple Ethernet frames.

4. The method of claim 1, wherein the unicast frames are MAC-in-MAC frames.

5. The method of claim 4, wherein each MAC-in-MAC frame comprises a simple Ethernet frame encapsulated by an encapsulation layer having a bridge ID as a destination MAC address.

6. The method of claim 5, wherein the encapsulation layer comprises a VLAN tag.

7. The method of claim 6, wherein the VLAN tag indicates a root bridge of an MSTI.

8. The method of claim 6, wherein the VLAN tag comprises a Root Part, a Multipath Part and a Domain Part.

9. The method of claim 1, wherein a bridge in the region includes more than one MAC-in-MAC translation unit (“

MTU”

), each MTU having a MAC address, further comprising the step of sending from the bridge an announcement packet advertising the MAC address of the bridge'"'"'s MTUs.

10. The method of claim 1, wherein the network comprises a plurality of MAC-in-MAC translation units (“

MTUs”

), the method further comprising;

at a first one of the plurality bridges, receiving a simple Ethernet frame by a first MTU;

at the first bridge, encapsulating the simple Ethernet frame as a MAC-in-MAC frame that indicates at least a destination bridge ID and a second MSTI; and

from the first bridge, forwarding the MAC-in-MAC frame according to the second MSTI.

11. The method of claim 10, further comprising:

at a second bridge, receiving the MAC-in-MAC frame by a second MTU;

at the second bridge, decapsulating the MAC-in-MAC frame to reveal the simple Ethernet frame; and

from the second bridge, sending the simple Ethernet frame to an access port.

12. The method of claim 1, wherein the operation for configuring, sending, and resetting are repeated for each bridge.

13. A method of controlling a network, comprising:

at a first bridge of the network, forming a field of a first frame having one bit for each Multiple Spanning Tree Instance (“

MSTI”

) of a region including an individual MSTI of the first bridge; and

at the first bridge, after receiving a second frame, setting a bit of a field of the second frame that corresponds to the individual MSTI to “

No”

if the second frame was passed from a second bridge through a port of the first bridge that is not a root port of the individual MSTI.

14. The method of claim 13, further comprising:

at the first bridge of the network, receiving a third frame having a bit of a field set to “

No”

; and

at the first bridge, applying a protocol to determine which bridge will select a new root port.

15. A network apportioned into a plurality of regions, the network comprising a plurality of bridges in a region of the network, a bridge configured as a root of a respective Multiple Spanning Tree Instance (“

MSTI”

) after the bridge receives one or more frames from a device that does not specify a root or a MSTI for such device and the bridge is further configured to send unicast frames according to an MSTI having another receiving bridge as a root bridge after the other receiving bridge is configured, the bridge is further configured to form a field of a first unicast frame having one bit for each MSTI of the region, wherein the bridge is further configured to set a bit of the field that corresponds to an individual MSTI to “

No”

when a second unicast frame is passed through and received by a port of the bridge that is not a root port of the individual MSTI.

16. At least one computer readable storage medium having computer program instructions stored thereon that are arranged to perform the following operations, and wherein the at least one computer readable storage medium includes one or more of a magnetic media, magneto-optical media, or optical media:

at a network device, determining that the network device is in a region of a network;

at the network device, configuring the network device as a root of a first Multiple Spanning Tree Instance (“

MSTI”

) after such network device receives one or more frames from another device that do not specify a root or a MSTI;

from the network device, sending multicast frames according to the first MSTI;

from the network device, sending unicast frames according to a second MSTI, wherein another receiving bridge in the region of the network is a root bridge of the second MSTI, unicast frames having a field containing one bit for each MSTI in the region; and

at the network device, changing a bit corresponding to an individual MSTI whenever a unicast frame is received on a port that is not a regional root port of the individual MSTI.