Source: http://www.google.ca/patents/US20060198323
Timestamp: 2017-11-23 13:19:07
Document Index: 266904908

Matched Legal Cases: ['art.\n12', 'art 505', 'art 510', 'art 515', 'art 505', 'art 510', 'art 515', 'art 505', 'art 510', 'art 515', 'art 505', 'art 510', 'art 515', 'art 515', 'art 510', 'art 515', 'art 505', 'art 510', 'art 515', 'art 505']

Patent US20060198323 - Methods and devices for improving the multiple spanning tree protocol - Google Patents
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...http://www.google.ca/patents/US20060198323?utm_source=gb-gplus-sharePatent US20060198323 - Methods and devices for improving the multiple spanning tree protocol
Publication number US20060198323 A1
Also published as CN101558605A, CN101558605B, EP1854249A2, EP1854249A4, US7889681, WO2006096315A2, WO2006096315A3
Publication number 11182564, 182564, US 2006/0198323 A1, US 2006/198323 A1, US 20060198323 A1, US 20060198323A1, US 2006198323 A1, US 2006198323A1, US-A1-20060198323, US-A1-2006198323, US2006/0198323A1, US2006/198323A1, US20060198323 A1, US20060198323A1, US2006198323 A1, US2006198323A1
Patent Citations (42), Referenced by (121), Classifications (13), Legal Events (2)
US 20060198323 A1
configuring each bridge in a region of the network as a root of a Multiple Spanning Tree Instance (“MSTI”); and
sending unicast frames according to an MSTI having a receiving bridge as a root bridge.
5. The method of claim 1, wherein a bridge includes more than 1 MAC-in-MAC translation unit (“MTU”), each MTU having a MAC address, further comprising the step of sending an announcement packet advertising the MAC address of each of the bridge's MTUs.
6. The method of claim 1, wherein the network comprises a plurality of MAC-in-MAC translation units (“MTUs”), the method further comprising:
receiving a simple Ethernet frame by a first MTU;
encapsulating the simple Ethernet frame as a MAC-in-MAC frame that indicates at least a destination bridge ID and an MSTI; and
forwarding the MAC-in-MAC frame according to the MSTI.
7. 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.
receiving the MAC-in-MAC frame by a second MTU;
decapsulating the MAC-in-MAC frame to reveal the simple Ethernet frame; and
sending the simple Ethernet frame to an access port.
9. The method of claim 7, wherein the encapsulation layer comprises a VLAN tag.
10. The method of claim 9, wherein the VLAN tag indicates a root bridge of an MSTI.
11. The method of claim 9, wherein the VLAN tag comprises a Root Part, a Multipath Part and a Domain Part.
12. A method of controlling a network, comprising:
forming a field of a frame having one bit for each Multiple Spanning Tree Instance (“MSTI”) of a region; and
setting a bit of the field to “No” when the frame is passed through a port that is not a root port of any MSTI of the region.
receiving a frame having a bit of the field set to “No”; and
applying a protocol to determine which bridge will select a new root port.
14. A network apportioned into a plurality of regions, the network comprising a plurality of bridges in a region of the network, each bridge configured as a root of a Multiple Spanning Tree Instance (“MSTI”) and further configured to send unicast frames according to an MSTI having a receiving bridge as a root bridge.
15. The network of claim 14, farther comprising means for forming a field of a frame having one bit for each MSTI of the region, wherein each bridge is further configured to set a bit of the field to “No” when the frame is passed through a port that is not a root port of any MSTI of the region.
means for determining that the network device is in a region of a network;
means for configuring the network device as a root of a first Multiple Spanning Tree Instance (“MSTI”); and
means for sending multicast frames according to the first MSTI.
means for sending unicast frames according to a second MSTI, wherein a receiving bridge in the region of the network is a root bridge of the second MSTI.
Although STP provides for the orderly flow of packets, it does not allow for all LANs in a network to be used in an optimal fashion. There is never a path from any bridge or station in the network to the root that has a lower sum of path costs than the path along that root bridge's spanning tree, but paths between other pairs of bridges or stations may not be optimal. For example, if ports 115 and 120 are blocked, the path from station 142 to station 141 is 142-E-F-I-A-B-D-G-141, for a total cost of a 11 (station 141 does not count the cost of the last hop), instead of the much shorter path 142-E-G-141, cost 3. It would be desirable to address this limitation of the prior art.
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 EEE 802.1Q. According to preferred aspects of the invention, each bridge is the root of its own spanning tree instance (“MSTI”). Some methods 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.
In some such implementations, the network may include a plurality of MAC-in-MAC translation units (“MTUs”) and the unicast frames may be MAC-in-MAC frames. Each MAC-in-MAC frame may comprises a simple Ethernet frame encapsulated by an encapsulation layer having a bridge ID as a destination MAC address.
FIG. 5 illustrates one example of a VLAN tag. VLAN tag 500 includes Root Part 505, Multipath Part 510 and Domain Part 515. In one implementation, the one shown in FIG. 5, VLAN Tag 505 is identical in format to the VLAN tag specified in IEEE 802.1Q. In FIG. 5, the Type Field 501, the Priority Field 502, and the Canonical Format Identifier Field 503 are exactly as specified in IEEE 802.1Q. The Root Part 505, Multipath Part 510 and Domain Part 515 together occupy the same bits as the VLAN ID (VID) field in IEEE 802.1Q. In other words, the IEEE 802.1Q VID field is subdivided into the Root Part 505, Multipath Part 510 and Domain Part 515. An alternative to the format of FIG. 5 is shown in FIG. 6.
If a frame with no VLAN tag 500 (an “untagged frame”) is received by a bridge, that bridge assigns the frame a value for the Priority, CFI, Root Part 505, Multipath Part 510 and Domain Part 515 in the same manner as described in IEEE 802.1Q, with certain exceptions: Such untagged frames are typically received from stations connected to the bridge; frames from other bridges would already have a VLAN tag 500. Domain Part 515 of VLAN tag 505 is assigned in the same manner as the PVID (Port VLAN ID) of IEEE 802.1Q; it is typically a constant per bridge port, though it may be assigned based on both the bridge port and the Layer 3 protocol present in the frame. The Multipath Part 510 and Domain Part 515 are assigned based on other criteria. Once assigned by a bridge, Root Part 505, Multipath Part 510 or Domain Part 515 are use by the bridges in the network to forward the frame; these three values are not changed during the forwarding of the frame through the network.
The underlying problem will be described in more detail with reference to FIGS. 7A et seq. Suppose the VLANs rooted on Bridges A and E are blocked as shown. MSTI E is implemented by having bridge A block port 710 and by having bridge B block port 720. MSTI A is implemented by having bridge E block ports 730 and 740.
Suppose that A receives a frame from station 761 with a destination MAC address indicating station 762, and that none of the bridges A through I have that destination MAC address in their Filtering Databases. A marks the frame with a VLAN tag 500 that includes a Root Part 505 that specifies MSTI A. This frame is flooded throughout the network, including to bridge B via the LAN connecting B to F. B floods to frame to at least the port to which station 762 is attached. Typically, the frame's VLAN tag 500 is removed from the frame before it is transmitted on the LAN connecting to station 762. Until then, as this frame traverses the network, each bridge learns the frame's source MAC address. The MAC address and the FID are used as the key into the Filtering Database, and the port on which the frame was received is stored as the payload. Thus, each bridge learns that station 761 can be found in the direction of the root port for MSTI A.
Bridge E then advertises its decision, i.e. changes the bits for MSTI I in all of the Reflection Vectors for which ports 805 or 806 are Designated Ports. As shown in FIG. 10, Reflection Vectors 1005 and 100 inform bridge A and bridge I that MSTI A and MSTI I are now in synch.
Therefore, some implementations use a technique, called “MAC-in-MAC,” that allows local MAC addresses to be used, and thus allows the identification of the destination bridge for any given destination MAC address. U.S. patent application Ser. No. 11/152,991, filed Jun. 14, 2005 and entitled “Forwarding Table Reduction and Multipath Network Forwarding” (attorney docket CISCP431) and IEEE standard 802.1AH describe relevant information and are hereby incorporated by reference for all purposes. An exemplary format of a MAC-in-MAC frame will now be described with reference to FIGS. 4A and 4B.
Field 440 is reserved for a VLAN tag. Some options for implementing VLAN tag 440 are discussed elsewhere herein with reference to FIGS. 5 et seq. Frame 450 ends with a CRC field 450 that applies to the outer MAC layer.
(Port VLAN Mask)) (1)
US3855422 * 5 Jul 1973 17 Dec 1974 Ibm Time division multiplexer with each frame consisting of a fixed length bit oriented address field and a variable length character oriented data field
US7352765 * 29 Oct 2003 1 Apr 2008 Broadcom Corporation Packet switching fabric having a segmented ring with token based resource control protocol and output queuing control
US20040264458 * 18 Jun 2004 30 Dec 2004 Alcatel Architecture for bridged ethernet residential access networks
US20050249372 * 3 May 2005 10 Nov 2005 Siemens Audiologische Technik Gmbh Hearing aid device and corresponding operating method
US20070064628 * 16 Sep 2005 22 Mar 2007 Tallet Francois E System and method for generating symmetrical spanning trees
USD518179 * 8 Nov 2004 28 Mar 2006 David William Holmes Hearing aid eartip
US7697528 * 1 Nov 2005 13 Apr 2010 Nortel Networks Limited Multilink trunking for encapsulated traffic
US7746892 * 30 Sep 2006 29 Jun 2010 Nortel Networks Limited Method and apparatus for transporting ethernet services
US7796506 * 28 Sep 2005 14 Sep 2010 Alcatel-Lucent Usa Inc. Load balancing network using Ethernet bridges
US7916741 2 Apr 2007 29 Mar 2011 William Marsh Rice University System and method for preventing count-to-infinity problems in ethernet networks
US7929554 23 Dec 2008 19 Apr 2011 Cisco Technology, Inc. Optimized forwarding for provider backbone bridges with both I and B components (IB-PBB)
US7944860 4 Jun 2009 17 May 2011 Cisco Technology, Inc. Preventing loss of network traffic due to inconsistent configurations within the network
US8085811 * 24 May 2010 27 Dec 2011 Nortel Networks, Ltd. Method and apparatus for transporting ethernet services
US8149836 * 10 Sep 2007 3 Apr 2012 Tejas Israel Ltd Method and system for relaying frames through an ethernet network and bridge therefor
US8203970 * 16 Oct 2006 19 Jun 2012 Hewlett-Packard Development Company, L.P. Method and apparatus for selecting spanning tree root
US8248920 * 25 Jul 2006 21 Aug 2012 Cisco Technology, Inc. Alternate spanning tree for faster indirect link failure recovery
US8531941 * 13 Jul 2007 10 Sep 2013 Cisco Technology, Inc. Intra-domain and inter-domain bridging over MPLS using MAC distribution via border gateway protocol
US8547877 * 30 Mar 2010 1 Oct 2013 Telefonaktiebolaget L M Ericsson (Publ) RSTP tracking
US8553584 * 8 Sep 2010 8 Oct 2013 Telefonaktiebolaget L M Ericsson (Publ) Automated traffic engineering for 802.1AQ based upon the use of link utilization as feedback into the tie breaking mechanism
US8588237 * 2 Nov 2011 19 Nov 2013 Rockstar Consortium Us Lp Method and apparatus for transporting ethernet services
US8694664 23 Nov 2010 8 Apr 2014 Cisco Technology, Inc. Active-active multi-homing support for overlay transport protocol
US8792474 * 14 Mar 2013 29 Jul 2014 International Business Machines Corporation Multipath effectuation within singly contiguous network fabric via switching device routing logic programming
US8842574 * 15 Nov 2011 23 Sep 2014 Marvell Israel (M.I.S.L) Ltd. Energy efficient networking
US8971322 * 3 Mar 2009 3 Mar 2015 Telefonaktiebolaget Lm Ericsson (Publ) Multicast interworking systems and methods
US9083646 * 4 Jun 2013 14 Jul 2015 Rpx Clearinghouse Llc Method and apparatus for transporting Ethernet services
US9118573 * 31 May 2012 25 Aug 2015 International Business Machines Corporation Multipath effectuation within singly contiguous network fabric via switching device routing logic programming
US9160651 9 Dec 2013 13 Oct 2015 Telefonaktiebolaget L M Ericsson (Publ) Metric biasing for bandwidth aware tie breaking
US9166887 26 Dec 2013 20 Oct 2015 Telefonaktiebolaget L M Ericsson (Publ) Multicast convergence
US9294398 * 2 Jun 2014 22 Mar 2016 International Business Machines Corporation Multipath effectuation within singly contiguous network fabric via switching device routing logic programming
US9426093 * 15 Jan 2015 23 Aug 2016 Telefonaktiebolaget Lm Ericsson (Publ) Multicast interworking systems and methods
US9548887 18 Feb 2014 17 Jan 2017 Cisco Technology, Inc. Proactive creation of multicast state in an overlay transport network to achieve fast convergence on failover
US9628334 19 Dec 2014 18 Apr 2017 Cisco Technology, Inc. VLAN tagging in a virtual environment
US20060268748 * 29 Mar 2006 30 Nov 2006 Laurence Rose Facilitating Computation of Role and State Information for Multiple Spanning Tree Instances
US20070071011 * 28 Sep 2005 29 Mar 2007 Lucent Technologies Inc. Load balancing network using Ethernet bridges
US20070116045 * 30 Sep 2006 24 May 2007 Nortel Networks Limited Method and apparatus for transporting ethernet services
US20080025203 * 25 Jul 2006 31 Jan 2008 Francois Tallet Alternate spanning tree for faster indirect link failure recovery
US20080062994 * 10 Sep 2007 13 Mar 2008 Ethos Networks Ltd Method and system for relaying frames through an ethernet network and bridge therefor
US20100226376 * 24 May 2010 9 Sep 2010 Dinesh Mohan Method and Apparatus for Transporting Ethernet Services
US20100309820 * 4 Jun 2009 9 Dec 2010 Cisco Technology, Inc. Preventing loss of network traffic due to inconsistent configurations within the network
US20110243140 * 30 Mar 2010 6 Oct 2011 Telefonaktiebolaget L M Ericsson RSTP Tracking
US20110299529 * 3 Mar 2009 8 Dec 2011 Telefonaktiebolaget L M Ericsson (Publ) Multicast Interworking Systems and Methods
US20120044939 * 2 Nov 2011 23 Feb 2012 Dinesh Mohan Method and Apparatus for Transporting Ethernet Services
US20120057603 * 8 Sep 2010 8 Mar 2012 Telefonaktiebolaget L M Ericsson (Publ) Automated Traffic Engineering for 802.1AQ Based Upon the Use of Link Utilization as Feedback into the Tie Breaking Mechanism
US20120127894 * 15 Nov 2011 24 May 2012 Nachum Gai Energy efficient networking
US20130272308 * 4 Jun 2013 17 Oct 2013 Rockstar Consortium Us Lp Method and Apparatus for Transporting Ethernet Services
US20130322292 * 14 Mar 2013 5 Dec 2013 International Business Machines Corporation Multipath effectuation within singly contiguous network fabric via switching device routing logic programming
US20130322454 * 31 May 2012 5 Dec 2013 Casimer M. DeCusatis Multipath effectuation within singly contiguous network fabric via switching device routing logic programming
US20140023078 * 20 Sep 2013 23 Jan 2014 Rockstar Consortium Us Lp Method and Apparatus for Transporting Ethernet Services
US20140023081 * 20 Sep 2013 23 Jan 2014 Rockstar Consortium Us Lp Method and Apparatus for Transporting Ethernet Services
US20140286340 * 2 Jun 2014 25 Sep 2014 International Business Machines Corporation Multipath effectuation within singly contiguous network fabric via switching device routing logic programming
US20150124811 * 15 Jan 2015 7 May 2015 Telefonaktiebolaget L M Ericsson (Publ) Multicast interworking systems and methods
US20170195213 * 30 Dec 2015 6 Jul 2017 Stmicroelectronics, Inc. Multipath switching using per-hop virtual local area network classification
CN102761463A * 29 Apr 2011 31 Oct 2012 鸿富锦精密工业（深圳）有限公司 Network equipment and method for implementation of energy conservation and electricity saving of network equipment in local area network
EP2154821A1 * 4 Feb 2008 17 Feb 2010 Alcatel Lucent Method and apparatus for sending and receiving multicast packets
EP2154821A4 * 4 Feb 2008 4 Sep 2013 Alcatel Lucent Method and apparatus for sending and receiving multicast packets
EP2582103A2 * 11 Dec 2008 17 Apr 2013 Nortel Networks Limited Tie-breaking in shortest path determination
EP2582103A3 * 11 Dec 2008 31 Jul 2013 Nortel Networks Limited Tie-breaking in shortest path determination
WO2016100765A3 * 18 Dec 2015 25 Aug 2016 Cisco Technology, Inc. Vlant tagging in a virtual environment
Cooperative Classification H04L12/4645, H04L45/00, H04L12/462, H04L45/16, H04L45/48, H04L12/4633
European Classification H04L45/00, H04L45/48, H04L45/16, H04L12/46B7