Source: http://www.google.com/patents/USRE42253?dq=system+for+measuring+web+traffic&ei=Lg8FT__TIIr-sQKzxaGRCg
Timestamp: 2014-11-28 15:48:50
Document Index: 713203713

Matched Legal Cases: ['art 3', 'art 3', 'art 3', 'art 3', 'art 3', 'art 3']

Patent USRE42253 - Optimizations and enhancements to the IEEE RSTP 802.1W implementation - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA method for supporting dynamic configuration changes comprises receiving a message from a current root bridge, comparing a bridge media access control (MAC) address of a receiving port to a bridge MAC address of the received message, if the bridge MAC addresses are not the same, then comparing a current...http://www.google.com/patents/USRE42253?utm_source=gb-gplus-sharePatent USRE42253 - Optimizations and enhancements to the IEEE RSTP 802.1W implementationAdvanced Patent SearchPublication numberUSRE42253 E1Publication typeGrantApplication numberUS 12/248,789Publication dateMar 29, 2011Filing dateOct 9, 2008Priority dateDec 20, 2002Fee statusPaidAlso published asUS7379429, US7720011, US8139510, US20100195661, USRE43270Publication number12248789, 248789, US RE42253 E1, US RE42253E1, US-E1-RE42253, USRE42253 E1, USRE42253E1InventorsBenny J. ThottakkaraOriginal AssigneeFoundry Networks, LlcExport CitationBiBTeX, EndNote, RefManPatent Citations (11), Non-Patent Citations (10), Referenced by (5), Classifications (10), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetOptimizations and enhancements to the IEEE RSTP 802.1W implementationUS RE42253 E1Abstract A method for supporting dynamic configuration changes comprises receiving a message from a current root bridge, comparing a bridge media access control (MAC) address of a receiving port to a bridge MAC address of the received message, if the bridge MAC addresses are not the same, then comparing a current priority value with a previous priority value of the current root bridge, determining if the receiving port is a qualified root port, and if the port is a qualified root port, then returning a superior designated message to execute an RSTP calculation.
1. A method for supporting dynamic configuration changes, the method comprising:
receiving a message from a current root bridge comprising an apparatus with bridge functionality;
comparing the bridge media access control (MAC) address currently held by the receiving port in a Port Priority Vector of the receiving port to the bridge MAC address of the received message;
if the bridge MAC addresses are not the same, then performing standard processing under the rapid spanning tree protocol to achieve dynamic configuration change.
if the current priority value is not inferior to the previous priority value of the current root bridge, then performing standard processing under the rapid spanning tree protocol to achieve dynamic configuration change.
if the port is not a qualified root port, then performing standard processing under the rapid spanning tree protocol to achieve dynamic configuration change.
5. The method of claim 1, wherein the message is a bridge protocol data unit packet.
6. A topology produced in accordance with the method of claim 1.
7. An apparatus with bridge functionality in a network, the apparatus comprising:
receive a message from a current root bridge comprising an apparatus with bridge functionality;
compare the bridge media access control (MAC) address currently held by a receiving port in a Port Priority Vector of the receiving port to the bridge MAC address of the received message;
8. The apparatus of claim 7, wherein the port information state machine is configured to perform standard processing under the rapid spanning tree protocol to achieve dynamic configuration change, if the bridge MAC addresses are not the same.
9. The apparatus of claim 7, wherein the port information state machine is configured to perform standard processing under the rapid spanning tree protocol to achieve dynamic configuration change, if the current priority value is not inferior to the previous priority value of the current root bridge.
10. The apparatus of claim 7, wherein the port information state machine is configured to perform standard processing under the rapid spanning tree protocol to achieve dynamic configuration change, if the port is not a qualified root port.
11. The apparatus of claim 7, wherein the message is a bridge protocol data unit packet.
12. A method for supporting dynamic configuration changes, the method comprising:
comparing a bridge media access control (MAC) address of a receiving port with a bridge MAC address of the received message;
if the bridge MAC addresses are not the same, then comparing a current priority value with a previous priority value of the current root bridge;
determining if the receiving port is a qualified root port; and
if the port is a qualified root port, then returning a superior designated message to execute an RSTP calculation.
13. The method of claim 12, wherein the message is a bridge protocol data unit packet.
after executing the RSTP calculation, performing a dynamic configuration change.
15. A topology produced in accordance with the method of claim 12.
16. An apparatus with bridge functionality in a network, the apparatus comprising:
compare a bridge media access control (MAC) address of a receiving port with the bridge MAC address of the received message;
if the bridge MAC addresses are not the same, then compare a current priority value with a previous priority value of the current root bridge;
determine if the receiving port is a qualified root port; and
return a superior designated message to execute an RSTP calculation, if the port is a qualified root port.
17. The apparatus of claim 16, wherein the message is a bridge protocol data unit packet.
18. A method of enhancing a Topology Change State Machine in the rapid spanning-tree protocol (RSTP), the method comprising:
determining if an event is a valid topology change event, a valid topology change event being indicated when a non-edge port of a bridge is put into a forwarding state by a Port State Transition Machine (PST), the bridge comprising an apparatus with bridge functionality;
stopping each of one or more timers on the bridge, each of the one or more timers indicating an interval for which topology change notification messages are sent through a root port;
19. The method of claim 18, wherein flushing of the learned addresses is not performed if the timers are running.
20. A topology produced in accordance with the method of claim 18.
21. An apparatus with bridge functionality in a network, the apparatus comprising:
determine if an event is a valid topology change event, a valid topology change event being indicated when a non-edge port of a bridge is put into a forwarding state by a Port State Transition Machine (PST), the bridge comprising an apparatus with bridge functionality;
stop each of one or more timers on a bridge, each of the one or more timers indicating an interval for which topology change notification messages are sent through a root port;
initiate a flushing cycle of learned addresses on all bridges across the network, in response to the new topology change event.
22. A method of enhancing a Topology Change State Machine in the rapid spanning-tree protocol (RSTP), the method comprising:
detecting if an event is valid topology change event, a valid topology change event being indicated when a non-edge port of a bridge is put into a forwarding state by a Port State Transition Machine (PST);
in response to a valid event, starting one or more timers on a bridge to propagate the valid event, each of the one or more timers indicating an interval for which topology change notification messages are sent through a root port, the bridge comprising an apparatus with bridge functionality; and
avoiding the flushing of learned MAC address in response to a subsequent topology change notice.
25. A method of steady state optimization in the rapid spanning-tree protocol (RSTP), the method comprising:
detecting for a steady state condition;
if a repeated designated message is received by a root port during said steady state condition, restarting a first timer of said root port, the first timer having a value indicating whether the port is or has recently been a current root port; and
if a repeated designated message is received on an alternate port during said steady state condition, restarting a forward delay timer of said alternate port.
26. An apparatus for steady state optimization in the rapid spanning-tree protocol (RSTP), the apparatus comprising:
an apparatus having bridge functionality and configured to:
detect for a steady state condition;
if a repeated designated message is received by a root port during said steady state condition, restart a first timer of said root port, the first timer having a value indicating whether the port is or has recently been a current root port; and
if a repeated designated message is received on an alternate port during said steady state condition, restart a forward delay timer of said alternate port.
TECHNICAL FIELD Embodiments of the present invention relate generally to communication networks. More particularly, embodiments of the present invention provide optimizations and enhancements to the IEEE RSTP 802.1w implementation.
BACKGROUND The Institute of Electrical and Electronics Engineers (IEEE) 802.1D Spanning-Tree Protocol (STP) standard provides distributed routing over multiple Local Area Networks (LANs) that are connected by bridges. The 802.1D standard is presented in detail in IEEE Standard for Local and Metropolitan Area Networks�Common Specification, Part 3: Media Access Control (MAC) Bridges (The Institute of Electrical and Electronics Engineers, Inc., New York, N.Y. 1998), which is hereby fully incorporated herein by reference. The 802.1D standard was designated at a time where recovering network connectivity within about 60 seconds after an outage was considered as adequate performance. For any network topology changes, the convergence time in the 802.1D standard is usually about 50 seconds (i.e., two times the forward delay plus a maximum age time).
The IEEE 802.1w Rapid Spanning-Tree Protocol (RSTP) standard reduces the convergence time as compared to the 802.1D standard and may be considered as an evolution of the 802.1D standard. The 802.1w standard is presented in detail in IEEE Standard for Local and Metropolitan Area Networks�Common Specification, Part 3: Media Access Control (MAC) Bridges�Amendment 2: Rapid Reconfiguration, (The Institute of Electrical and Electronics Engineers, Inc., New York, N.Y. 2001), which is hereby fully incorporated herein by reference. When a bridge failure or port failure occurs, the RSTP protocol will calculate a new proposal (a loop-free topology) within typically a response time of about 300 milliseconds by deciding which particular ports will be a forwarding port and a blocking port. A port failure can include a link failure or a creation of a new link.
SUMMARY OF EMBODIMENTS OF THE INVENTION In one embodiment of the invention, a method for supporting dynamic configuration changes, includes:
a port information state machine configured to: receive a message from a current root bridge; compare the bridge media access control (MAC) address of a receiving port to the bridge MAC address of the received message; if the bridge MAC addresses are not the same, then compare a current priority value to a previous priority value of the current root bridge; if the current priority value is inferior, then determine if the port receiving the message is a qualified root port; and if the port is a qualified root port, then return a superior designated message to permit each bridge to execute a rapid spanning tree calculation for use in a dynamic configuration change. In another embodiment of the invention, a method of enhancing a Topology Change State Machine in the rapid spanning-tree protocol (RSTP), includes:
a Topology Change State Machine configured to: determine if an event is a valid topology change event; stop a tcWhile timer; propagate a new topology change event as a latest topology change event to all bridges across the network; and initiate a flushing cycle of learned addresses on all bridges across the network, in response to the new topology change event In another embodiment of the invention, a method of steady state optimization in the rapid spanning-tree protocol (RSTP), includes:
FIG. 14 is a block diagram that illustrates a method of steady state optimization, in accordance with an embodiment of the invention.
FIGS. 1 through 4 are block diagrams shown for the purpose of describing various terminologies for port roles in the 802.1w (rapid spanning-tree protocol or RSTP) standard. The port receiving the best Bridge Protocol Data Unit (BPDU) on a bridge is a �root port�. This is the port that is closest to the root bridge in terms of path cost. In the example of FIG. 1, the root bridge 105 is coupled to a root port 110 of a bridge 115 and to a root port 120 of a bridge 125. The root bridge sends BPDUs that are more useful than BPDUs that any other bridge can send. The root bridge is the only bridge in the network that does not have a root port. All other bridges receive BPDUs on at least one port.
A port is a �designated port� if it can send the best BPDU on the segment to which it is connected. The 802.1w bridges (as well as 802.1D bridges) create a bridge domain by linking together different segments such as, for example, Ethernet segments. On a given segment, there can only be one path toward the root bridge. If there were two paths, then there would be a bridging loop in the network. All bridges connected to a given segment listen to each other's BPDUs and agree on the bridge sending the best BPDU as the designated bridge for the segment. The corresponding port on that bridge is designated. In the example of FIG. 2, the designated ports are shown as ports 205 and 210 on the root bridge 105 and port 215 on the bridge 125.
A �blocked port� is defined as not being the designated port or the root port. A blocked port receives a more useful BPDU than the BPDU it would send out on its segment. An �alternate port� is a port blocked by receiving more useful BPDUs from another bridge. In the example of FIG. 3, the alternate port is denoted as 305 on the bridge 115.
A �backup port� is a port blocked by receiving more useful BPDUs from the same bridge on which the port is located. In the example of FIG. 4, the backup port is denoted as 405 on the bridge 125.
In an embodiment, a BPDU 500 typically includes a root identification (ID) 505 which contains the same information as the bridge ID (identifier) in the following format {bridge priority: lowest MAC address}, a path cost 510, a transmitting bridge ID 515, a transmitting port ID 520, and a receiving port ID 525. To determine the more useful or better BPDU between two particular different BPDU, the BPDU values in FIG. 5 are compared. The BPDU with the numerically lower value is selected as the more useful BPDU.
As another example, if the network administrator changes the priority value to 4000, then the current priority value of 4000 will be inferior to the old priority value of 100. If the current priority value is inferior to the old priority value, then a check (730) is made to determine if the receiving port on the bridge is a qualified root port. A qualified root port is defined as: (1) while the �rrwhile� timer has not timed out, the role of the port is equal to the selected role which is equal to the root port; and (2) the �rcvdinfowhile� timer has not timed out. An rrwhile timer naming on a port means that the role of the port is ROOT PORT. Only the ROOT PORT will have the rrwhile timer at any given point on a non-root bridge. The rcvdInfowhile timer is used to determine if the message which is held by a root port, alternate port or backup port should be aged out.
If the port is a qualified root port, then the receiving port returns (750) the following BPDU message 800, as also shown in FIG. 8: �superior designated message� 805. In response to the superior designated message 805, each bridge will execute (755) the RSTP calculation, and based upon the RSTP calculation result, each bridge will perform (760) a dynamic configuration change.
An �other message� 820 is either an inferior message or a topology change indicating messages like TCN (topology change notice), or TC acknowledgement, or RST BPDU with TC flag set, or other suitable messages.
When a bridge receives a BPDU with the TC bit (TC flag) set from a neighbor, the following events typically occur as described below. The BPDU with the TC flag is hereinafter denoted as �RSTP TCN�. The RSTP TCN performs the function of topology change detection and topology change propagation across the entire network. First, the bridge clears the MAC addresses that have been learned on all its ports except the one that received the topology change. Second, the bridge starts the tcWhile timer and sends BPDUs with the TC flag set on all its designated ports and root port. The RSTP protocol no longer uses the specific TCN BPDU (Topology Change Notification BPDU), unless a legacy bridge needs to be notified. Thus, notification of the topology change is transmitted very quickly across the entire network.
The Topology Change state machine generates and propagates the topology change notification messages on each port. When a root port or a designated port goes into a forwarding state, the Topology Change state machine 1030 (FIG. 13) on those ports sends a topology change notice (TCN) to all bridges in the topology to propagate the topology change. It is noted that edge ports, alternate ports, or backup ports do not need to propagate a topology change. The TCN is sent in the RST BPDU that a port sends. Ports on other bridges in the topology once they receive the RST BPDU, and transmit the RSTP TCN to other bridges until all the bridges are informed of the topology change. For example, assume that port �Port3� in bridge �FDRY2� in FIG. 9 fails. The port �Port4� in bridge �FDRY3� becomes the new root port. The port �Port4� in bridge �FDRY3� sends an RST BPDU with a TCN to port �Port4� in bridge in bridge �FDRY4�. To propagate the above topology change, the port �Port4� in bridge �FDRY4� then starts a TCN timer on the bridge port itself, on the bridge's root port, and on other ports on that bridge with a designate role. The, the port �Port3� in bridge �FDRY4� sends an RST BPDU with the TCN to the port �Port4� in bridge �FDRY2�. Note the new active Layer 2 path in FIG. 9.
The bridge �FDRY2� then starts the TCN timer on the designated ports and sends RST BPDUs that contain the TCN as shown in FIG. 10. The port �Port5� in bridge �FDRY2� sends the TCN to port �Port2� in bridge �FDRY5�. The port �Port4� in bridge �FDRY2� sends the TCN to port �Port4� in bridge �FDRY6�. The port �Port2� in bridge �FDRY2� sends the TCN to port �Port2� in bridge �FDRY1�. Then, bridge �FDRY1�, bridge �FDRY5�, and bridge �FDRY6� send RST BPDUs that contain the TCN to bridge �FDRY3� and bridge �FDRY4� to complete the TCN propagation.
FIG. 12 is a flowchart illustrating a method 950 of enhancing the Topology Change State Machine (TCM) 1030 (FIG. 13) in the RSTP protocol, in accordance with an embodiment of the invention. The TCM first determines or recognizes (951) if an event is a valid topology change event. A valid topology change event is defined as: (1) a forwarding state on a non-edge port designated, and a forwarding state on a root port. In other words, a valid topology change is detected when a non-edge port is put into a forwarding state by a Port State Transition Machine (PST). Corresponding to this event, the Topology Change State Machine (TCM) enters into a �DETECTED� state and starts the tcwhile timer on itself. It is noted that the tcwhile timer operates on a port-level and not on a bridge-level. A root port sends out an RSTP TCN at an interval (e.g., every approximately 2 seconds) and up to the expiration of a tcWhile timer (e.g., approximately 4 seconds). Other ports in other bridges receive the RSTP TCN from the root port, and each of the other bridges then start their tcWhile timers (e.g., tcwhile timers. Since the tcWhile timers of the other bridges have started, the bridges will also send out RSTP TCNs at an interval (e.g., every 2 seconds) until their tcWhile timers expire.
FIG. 13 is a block diagram that illustrating various state machines configured for steady state optimization, in accordance with an embodiment of the invention. In the steady state, the designated ports on a bridge will send repeated designated messages. In the steady state, one goal is to minimize the invocation of the state machines 1005 to I030 due to the intensive CPU tasks that are required for the state machines. As shown in FIG. 13, a bridge 1000 typically includes the following state machines: Port Information State Machine (PIM) 1005, Port Role Selection State Machine (PRS) 1010, Port Role Transition State Machine (PRT) 1015, Port Transmit State Machine (PTX) 1020, Port State Transition State Machine (PST) 1025, and Topology Change State Machine (TCM) 1030. For a port 1035 that is enabled, 128 spanning tree instances on the 6 state machines will typically run on the port 1035.
FIG. 15 is a block diagram that illustrates another method of steady state optimization, in accordance with an embodiment of the invention. In the example of system 1500, assume the following parameters. The bridge 1505 has a root ID of (100:MAC1), the bridge 1507 has a root ID of (200:MAC2), and the bridge 1517 had a root ID of (300:MAC3). An active traffic port is formed between the designated port and root port. Thus, if a ping message is to be sent to a device 1509 (e.g., a laptop computer), then the ping message will follow the active traffic port. The PRS state machine 1010 (FIG. 13) is not invoked during the following conditions. The designated port is 1515, while the alternate port is in bridge 1517. The designated port 1515 goes into a forwarding state only after two (2) instances of expiration of the fdWhile timer and will be sending proposals to the alternate port in the bridge 1517, while this alternate port will not transmit messages to the designated port at all. In an embodiment of the invention, when a BPDU proposal flag is received, the PRS and PRT are not invoked since the designated port has been attached to the alternate port. Thus, the additional processing tasks during these state machine invocations are advantageously avoided. It is noted, however, that if the BPDU proposal was received from device 1519 (e.g., a personal computer) or switch 1521 then the PRS is invoked in order to be compliant with the 802.1w standard. In this case, the BPDU proposal may have a new value and the port designations may change. As a result, the PRS will be required to be invoked.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6330229Nov 9, 1998Dec 11, 20013Com CorporationSpanning tree with rapid forwarding database updatesUS6717950Jul 26, 2002Apr 6, 2004General Instrument CorporationMethod and apparatus for priority-based load balancing for use in an extended local area networkUS7061875Dec 7, 2001Jun 13, 2006Cisco Technology, Inc.Spanning tree loop guardUS7379429Dec 20, 2002May 27, 2008Foundry Networks, Inc.Optimizations and enhancements to the IEEE RSTP 802.1w implementationUS7564779Jul 7, 2005Jul 21, 2009Alcatel LucentRing rapid spanning tree protocolUS20010021177Mar 5, 2001Sep 13, 2001Anritsu CorporationSpanning tree bridge and route change method using the sameUS20020181412May 29, 2002Dec 5, 2002Nec CorporationCommunication device, network system using same, and method of constructing spanning treeUS20070008964Jul 7, 2005Jan 11, 2007Laurence RoseRing rapid spanning tree protocolUS20070118628Nov 21, 2005May 24, 2007Kumar Mohan JLive network configuration within a link based computing systemUS20080310421Jun 12, 2007Dec 18, 2008Teisberg Robert RManaging Connectivity in a Virtual NetworkUS20090323518Jun 8, 2009Dec 31, 2009Laurence RoseRing rapid spanning tree protocolNon-Patent CitationsReference1IEEE Standard for Local and Metropolitan Area Networks-Common Specification, Part 3: Media Access Control (MAC) Bridges (The Institute of Electrical and Electronics Engineers, Inc., New York, NY 1998).2IEEE Standard for Local and Metropolitan Area Networks�Common Specification, Part 3: Media Access Control (MAC) Bridges (The Institute of Electrical and Electronics Engineers, Inc., New York, NY 1998).3IEEE Standard for Local and Metropolitan Area Networks-Common Specification, Part 3: Media Access Control (MAC) Bridges-Amendment 2: Rapid Reconfiguration (The Institute of Electrical and Electronics Engineers, Inc., New York, NY 2001), pp. 1-108.4IEEE Standard for Local and Metropolitan Area Networks�Common Specification, Part 3: Media Access Control (MAC) Bridges�Amendment 2: Rapid Reconfiguration (The Institute of Electrical and Electronics Engineers, Inc., New York, NY 2001), pp. 1-108.5Notice of Allowance issued in U.S. Appl. No. 10/326,494, dated Mar. 17, 2008.6Notice of Allowance issued in U.S. Appl. No. 12/082,682, dated Feb. 16, 2010.7Notice of Allowance issued in U.S. Appl. No. 12/082,682, dated Mar. 30, 2010.8Office Action issued in U.S. Appl. No. 10/326,494, dated Aug. 9, 2007.9Office Action issued in U.S. Appl. No. 10/326,494, dated Jan. 3, 2007.10Office Action issued in U.S. Appl. No. 12/082,682, dated Oct. 13, 2009.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8139510 *Apr 14, 2010Mar 20, 2012Foundry Networks, LlcOptimizations and enhancements to the IEEE RSTP 802.1w implementationUS8451715Jun 30, 2010May 28, 2013Juniper Networks, Inc.Avoiding data loss in a multi-homed layer two bridging networkUS8467316 *Dec 29, 2010Jun 18, 2013Juniper Networks, Inc.Enhanced address learning in layer two computer networksUS20100195661 *Apr 14, 2010Aug 5, 2010Foundry Networks, Inc.Optimizations and Enhancements to the IEEE RSTP 802.1w ImplementationUSRE43270 *Feb 1, 2011Mar 27, 2012Foundry Networks LlcOptimizations and enhancements to the IEEE RSTP 802.1W implementation* Cited by examinerClassifications U.S. Classification370/256, 370/401, 709/238International ClassificationH04L12/28Cooperative ClassificationH04L45/48, H04L12/437, H04L12/462European ClassificationH04L12/437, H04L12/46B7, H04L45/48Legal EventsDateCodeEventDescriptionOct 24, 2011FPAYFee paymentYear of fee payment: 4Sep 26, 2011ASAssignmentFree format text: SUPPLEMENTAL PATENT SECURITY AGREEMENT;ASSIGNORS:BROCADE COMMUNICATIONS SYSTEMS, INC.;FOUNDRY NETWORKS, LLC;INRANGE TECHNOLOGIES CORPORATION;AND OTHERS;REEL/FRAME:026971/0042Effective date: 20110916Owner name: WELLS FARGO BANK, NATIONAL ASSOCIATION, AS COLLATESep 20, 2011ASAssignmentEffective date: 20110916Free format text: SUPPLEMENTAL PATENT SECURITY AGREEMENT;ASSIGNORS:BROCADE COMMUNICATIONS SYSTEMS, INC.;FOUNDRY NETWORKS, LLC;MCDATA CORPORATION;REEL/FRAME:026938/0922Owner name: BANK OF AMERICA, N.A., AS ADMINISTRATIVE AGENT, CAJul 21, 2010ASAssignmentEffective date: 20090511Owner name: FOUNDRY NETWORKS, LLC, CALIFORNIAFree format text: CHANGE OF NAME;ASSIGNOR:FOUNDRY NETWORKS, INC.;REEL/FRAME:024733/0739Jan 20, 2010ASAssignmentOwner name: WELLS FARGO BANK, NATIONAL ASSOCIATION, AS COLLATEEffective date: 20100120Free format text: SECURITY AGREEMENT;ASSIGNORS:BROCADE COMMUNICATIONS SYSTEMS, INC.;FOUNDRY NETWORKS, LLC;INRANGE TECHNOLOGIES CORPORATION;AND OTHERS;REEL/FRAME:023814/0587RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google