Source: http://www.google.com/patents/US7889681?dq=456322
Timestamp: 2016-10-27 19:40:42
Document Index: 154582035

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'art 505', 'art 510', 'art 515', 'art 515', 'art 510', 'art 515', 'art 505', 'art 510', 'art 515', 'art 505', 'art 505', 'art 505', 'art 505', 'art 505', 'art 510', 'art 505', 'art 510', 'art 505', 'art 515']

Patent US7889681 - Methods and devices for improving the multiple spanning tree protocol - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsThe 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.com/patents/US7889681?utm_source=gb-gplus-sharePatent US7889681 - Methods and devices for improving the multiple spanning tree protocolAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7889681 B2Publication typeGrantApplication numberUS 11/182,564Publication dateFeb 15, 2011Filing dateJul 14, 2005Priority dateMar 3, 2005Fee statusPaidAlso published asCN101558605A, CN101558605B, EP1854249A2, EP1854249A4, US20060198323, WO2006096315A2, WO2006096315A3Publication number11182564, 182564, US 7889681 B2, US 7889681B2, US-B2-7889681, US7889681 B2, US7889681B2InventorsNorman FinnOriginal AssigneeCisco Technology, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (42), Non-Patent Citations (7), Referenced by (6), Classifications (13), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMethods and devices for improving the multiple spanning tree protocol
US 7889681 B2Abstract
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.
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
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.
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 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.
at the first bridge of the network, receiving a third frame having a bit of a field set to “No”; and
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.
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;
This application claims priority to U.S. Provisional Patent Application No. 60/658,804, filed Mar. 3, 2005 and U.S. Provisional Patent Application No. 60/661,279, filed Mar. 11, 2005, both of which are entitled “Optimal Bridging” and both of which are hereby incorporated by reference for all purposes.
The present invention relates to communication networks. More particularly, the present invention relates to the use of protocols such as spanning tree protocol (“STP”), rapid spanning tree protocol (“RSTP”) and multiple spanning tree protocol (“MSTP”) in communication networks.
FIG. 1 depicts simple network 100 that includes layer 2 Ethernet bridges conforming to IEEE Std.™ 802.1D-2004 (IEEE 802.1D) or IEEE Std. 802.1Q-2003 (IEEE 802.1Q) 105. In this example, there are 9 bridges A-I and three stations, 140-142, connected via 12 local area networks (LANS) 125, 130, and 150 (10 instances). The letters A-I are Bridge IDs. Lower letters (e.g., A) are “better” than higher letters (e.g., D), according to the convention of IEEE 802.1D or IEEE 802.1Q, which are hereby incorporated by reference for all purposes. Port path costs 110 are indicated for each LAN. This diagram assumes that all bridge ports attached to the same LAN have the same value configured for their port path cost, though this is not required either by IEEE 802.1D or by the present invention.
Bridges create a spanning tree over network 100 by exchanging protocol packets called Bridge Protocol Data Units (BPDUs). Using these packets, the protocol state machines implemented in each bridge select certain ports to be part of the active topology of the network and certain others to be blocked. (For the purposes of this invention, STP and RSTP are equivalent; in any context where STP is mentioned, RSTP is equally applicable.) The spanning tree is “spanning” in the sense that all LANs are connected. It is a “tree” in that there is exactly one path between any given pair of bridges or stations.
According to STP, one of the bridges of network 100 (in this example, bridge A) will be elected as the “Root Bridge”. The tree is constructed by each bridge selecting the port that is closest to the Root Bridge as its “Root Port,” where “closest” is defined as the path to the root bridge with the least numerical sum of root path costs for the bridge ports traversed. (Only ingress from a LAN to a bridge counts in this summation, not egress from a bridge to a LAN.) Where two or more paths have the same sum of port path costs, tiebreaker values are used. The tiebreaker values are Bridge IDs and Port IDs, as defined in IEEE 802.1D and IEEE 802.1Q. Bridge E selects from among three equal cost paths, thus breaking three potential spanning tree loops, by using the bridge IDs of the adjacent bridges to select port 117 as its root port, and to mark as “alternate ports” and block ports 115 and 120. (Although these terms can have different meanings when used by those of skill in the art, the terms “packet” and “frame” will sometimes be used interchangeably herein.)
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 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.
Some aspects of the invention provide a method for controlling a network. The method includes the steps of configuring each bridge in a region of the network as a root of a Multiple Spanning Tree Instance (“MSTI”) and of sending unicast frames according to an MSTI having a receiving bridge as a root bridge. Multicast frames may be sent according to an MSTI having a sending bridge as a root bridge. Access ports may use simple Ethernet frames.
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 comprise a simple Ethernet frame encapsulated by an encapsulation layer having a bridge ID as a destination MAC address.
A bridge may include more than 1 MAC-in-MAC translation unit (“MTU”), each MTU having a MAC address. If so, the method may include the step of sending an announcement packet advertising the MAC address of each of the bridge's MTUs.
Other methods of controlling a network are provided herein. One such method includes the steps of forming a field of a frame having one bit for each 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. The method may also include the steps of 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.
The methods described herein may be implemented in hardware, firmware or software. For example, some aspects of the invention may be implemented by one or more network devices in a communication network, e.g. as software for controlling one or more of the network devices. One such implementation of the invention provides a network that may be apportioned into a plurality of regions. The network comprises 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.
Bridges of the network may be configured to form a field of a frame having one bit for each MSTI of the region. If so, each bridge may be 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.
FIG. 1 illustrates the use of conventional STP.
Like network 100, network 200 may be configured with an MSTI having bridge A as the root, as shown in FIG. 2. Such an MSTI will sometimes be identified herein according to the root bridge. For example, an MSTI having bridge A as the root will sometimes be referred to as “MSTI A” or the like. In preferred implementations of the invention, multicast traffic originating from bridge A travels along MSTI A. As will be apparent to those of skill in the art, as long as the port path cost for all bridge ports connected to a LAN are equal, there is no more optimal path between A and any other bridge or station than the path along MSTI A.
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 500 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 used 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.
Root Part 505 specifies which Root Bridge is used when routing the frame. Root Part 505 is constant for each bridge. For example, when bridge E in network 200 receives an untagged frame, it places a value indicating “MSTI E” in Root Part 505 when it transmits that frame to another bridge in the network. Similarly, bridge G would place a value indicating “MSTI G” in Root Part 505 when transmitting a frame received without a VLAN tag 500, typically from a station connected directly to bridge G. Thus, by using Root Part 505 to indicate the Root Bridge, traffic between bridges G and E never use MSTI A, and thus can take the direct path between the two bridges G and E. Optimal routing thus is achieved.
Multipath Part 510 specifies which set of port path cost parameters is used when routing the frame. Spanning trees, like OSPF or IS-IS, are constructed by minimizing the sum of the “costs” of the ports into which a frame may pass into a bridge. Every MSTI with the same Multipath Part has the same port path cost structure. MSTIs with different Multipath Parts may have different port path costs. This allows one to specify alternate paths across the network for different flows.
In preferred implementations of the invention, R Part 505 and M Part 510, together, select the MSTI to be used for forwarding the frame. There are (number of M Parts)*(number of R Parts) separate MSTIs. The Root of each Bridge Protocol Data Unit (“BPDU”) says, in effect, “This is the Root Port” for each MSTI
According to the previously-described implementations, all frames are transmitted on the “source MSTI”; that is, the first bridge in the network to receive an untagged frame supplies a value for the Root Part 505 that identifies an MSTI of which that bridge is the root bridge. There is a problem, however, in that MAC address learning cannot work properly.
Accordingly, preferred implementations of the invention ensure that 2 bridges connected by a LAN use the same port path cost for that L. In some such implementations, the bridge advertises the port path cost configured for each different Multipath Part in the BPDUs transmitted on that port. All bridges on a given LAN use, instead of their configured port path costs, the port path costs advertised by the Common and Internal Spanning Tree instance (“CIST”) designated bridge, as described in IEEE 802.1Q. The CIST port path costs are not altered by this procedure. One port path cost parameter is required for each M-Part. In such implementations, a bridge's bridge priority as defined in IEEE 802.1Q must be the same in all MSTIs that that differ only in their Root Parts.
It has been observed often, in IEEE 802.1, that when a bridge has a number of non-designated ports from which to select its Root Port, any decision it is perfectly compatible with the spanning tree algorithms. Furthermore, as long as the port path costs are forced to be symmetrical by the CIST tie-breaker, the following is true: if any Bridge “X” has an equal-cost root port choice on MSTI Y, then Bridge Y has an equal-cost root port choice on MSTI X. Any such equal-cost paths are a potential source of the asymmetry shown in FIG. 7A. Non-equal costs paths are not a problem; because the port path costs are equal in both directions, the least-cost path for MSTI A will be the same as the least-cost path for MSTI B.
Since the both bridges know about the problem, they can do something about it. Accordingly, some preferred implementations of the invention add, for each MSTI in a BPDU, a Reflection Vector containing one bit of information about each of the other MSTIs. For convenience in describing the Reflection Vector, the MSTI to which the Reflection Vector is attached in the BPDU is the “Owning MSTI”, and the MSTI for which a given bit in the Reflection Vector carries information is the “Bit MSTI”. A bit in a Reflection Vector is set to “Yes” if, along the path from the Owning MSTI's Root Bridge, the bridge port from which the BPDU carrying this MSTI's information was transmitted was the Root Port for the Bit MSTI. Otherwise, the bit is set to “No”.
Looking at the Root Part values for bridges A and I, bridges B and E will each want to block one port for one of the two Root Parts' MSTIs. Here, bridge E has blocked port 805 to form MSTI 810 rooted in bridge I (“MSTI I”). Port 806 is now the Root Port. Similarly, bridge B has blocked port 815 to form MSTI 820 rooted in bridge A (“MSTI A”). Port 816 is now the Root Port.
When the Root Bridge of an MSTI initiates the Reflection Vector as a per-bridge per-MSTI variable, all of the other MSTIs' bits are Yes. For example, when bridge I initiates a Reflection Vector at stage 825, all of the other MSTIs' bits are Yes. The Reflection Vector received for a given Owner MSTI from the Regional Root Port of that MSTI is saved as per-bridge per-MSTI variable. Whenever an Owner MSTI's information, including the Reflection Vector, is transmitted in a BPDU on a bridge port that is a Designated Port for the Owner MSTI, the transmitted Reflection Vector is the per-bridge per-MSTI Reflection Vector, except that the bit in the transmitted Reflection Vector corresponding to each other Bit MSTI is reset to “No” if the port on which the BPDU is transmitted is not a Regional Root Port for that Bit MSTI. Accordingly, because path 820 corresponds with MSTI A, the Reflection Vector passes unchanged and remains set to Yes at stages 830, 835 and 840. This information is not stored in bridge E, however, because it is not received on the Regional Root Port for MSTI I; it is received on an Alternate Port for MSTI I.
When the Reflection Vector from the Root Port is transmitted on a port that is not an MSTI Regional Root Port on any MSTI, that MSTI's bit is set to “No” in the Reflection Vector, whatever its former value. This rule applies to the ports on the Root Bridge, as well. Accordingly, because port 815 of bridge B is not an MSTI Regional Root Port on MSTI A, MSTI A's bit is set to “No” in the Reflection Vector at stage 845. This BPDU is stored in bridge E, because port 806 is the Regional root Port for MSTI I. Therefore, it is the “No” that is transmitted to bridge A for Owner MSTI I, Bit MSTI A at stage 850.
Similarly, because port 805 of bridge E is not an MSTI Regional Root Port on MSTI I, MSTI I's bit is set to “No” in MSTI A's Reflection Vector at stage 855. This BPDU reaches bridge B (at stage 820) because port 816 of bridge B is the Regional Root Port for MSTI A. Accordingly, at stage 860, bridge I also knows that MSTI A and MSTI I are not in synch. It will be appreciated by those of skill in the art that stage 860 could occur at approximately the same time as stage 850, slightly earlier or slightly later.
According to some preferred implementations of the invention, a bridge will make a predetermined action if the following conditions arise: the bridge receives a Reflection Vector for Owning MSTI 1 on an Regional Alternate Port for MSTI 1 that has the same Root Path Cost as the Regional Root Port for MSTI 1, that received Reflection Vector contains a “Yes” for Bit MSTI 2, and MSTI 1's Root Bridge ID (or alternatively, its MSTID) is worse than Root 2's. If these conditions exist, then the bridge selects that Regional Alternate Port as the Regional Root Port for MSTI 1.
This implementation of the Reflection Vector brings home the point that defining a Reflection Vector is an “o(n2)” problem, because both sources and destinations must be taken into account. Accordingly, such implementations can potentially require a lot of bits to fully define a Reflection Vector. In fact, a BPDU that carries information for the maximum number of MSTIs allowed by IEEE 802.1Q, 64, would have to be larger than the maximum frame size (1518 octets) in order to contain all 64 Reflection Vectors, each with 64 bits, as well as carrying at least one Port Path Cost.
In an alternate implementation, instead of tagging each untagged frame with a Root Part 515 indicating the source bridge's MSTI, the frame can be tagged with the destination bridge's MSTI, instead. This technique is called, “destination tagging”, as opposed to the “source tagging” so far described. The advantage of destination tagging is that each bridge along the path to the destination bridge may transmit the frame through either the Regional Root Port or a Regional Alternate Port for the destination bridge's MSTI, thus adding a load-sharing capability that can make fuller use of the bandwidth available on all LANs. In order to use destination tagging, however, certain conditions must be met: 1) the identity of the destination bridge must be known to the bridge inserting the tag; and either 2a) the selection of frames transmitted through the Root and Alternate ports must be made in such a way that the utility of learning MAC addresses is not compromised, or 2b) MAC addresses must not be learned in the network. We address these criteria separately.
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” 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.
As noted above, in some implementations of the invention a bridge will have more than one MAC-in-MAC translation unit (“MTU”). Each MTU needs its own MAC address. Some implementations of the invention fulfill this requirement by using hierarchical MAC addresses. However, such implementations require that the high-order part of the MAC address must be assigned. Accordingly, such implementations lack a “plug-and-play” capability. Therefore, in some preferred implementations of the invention, the MTP units use universal MAC addresses, and each bridge sends Announcement Packets advertising all of the MAC addresses of all of its MTP units.
Announcement Packets also include any multicast addresses wanted by its locally-attached access ports. Such access ports include ports attached to any device that does not implement the methods of the present invention, e.g., end stations and legacy bridges. These “wants” can be expressed via configuration, IEEE 802.1Q General Attribute Registration Protocol (GARP), Multicast Registration Protocol (GMRP), IETF RFC 2236 Internet Group Management Protocol (IGMP), etc. In some preferred implementations, the Announcement Packets tell, for each bridge, which {Multicast Address, Domain Part} pairs the bridge needs to receive to satisfy its locally-connected access ports. Announcement Packets also include the list of VLANs' Domain Parts required by locally-attached access ports. Again, these may be known via configuration, IEEE 802.1Q GARP VLAN Registration Protocol (GVRP), etc.
Announcement Packets are preferably simple multicasts, addressed to the “all Bridges” multicast address. As noted above, these multicasts will be sent along the sending bridge's MSTI. An Announcement Packet is an ordinary multicast; it is not passed hop-by-hop. The information is kept in every receiving Bridge. This information replaces the use of GMRP or IGMP for multicast information, and GVRP for VLAN information.
Modifications to IEEE 802.1Q According to Some Preferred Implementations
The following definitions are provided in order to state clearly the modifications to IEEE 802.1Q according to some preferred implementations of the invention:
Reflection Vector: A per-MSTI (the “Owning MSTI”) bit vector with one bit per MSTI (the “Bit MSTI”) known to the sender, including the Owning MSTI. A bit is set to 1 if all of the Bridge Ports along the path from the Owning MSTI's Regional Root, including the Bridge Port on which the Reflection Vector is transmitted, are an MSTI Root Port for the Bit MSTI; otherwise it is set to 0.
SVL Groups and the MST Configuration Table
The 4096-integer MST Configuration table defined in IEEE 802.1Q is redesignated the “MSTI Table”. An additional SVL Group Table of 4096 2-octet integers is appended to the end of the MSTI Table to form the new MST Configuration Table. Each integer in the SVL Group Table corresponds to one VLAN ID, and assigns that VID to a specific Filtering Database ID (FID). The SVL Group Table is, therefore, simply a normalization of the VID to FID allocation table described in Clause 12.10.3 of IEEE 802.1Q. The CIST, which corresponds to VID 0 in the SVL Group Table, is always assigned to FID 0.
This does not fit into a single maximum-length frame. If the Multiple Registration Protocol (see IEEE Project 802.1ak, “Multiple Registration Protocol,” which is hereby incorporated by reference) is used to distribute multicast address and VLAN registrations, instead of the technique given in Section 4.0, then no MSTP Message need contain information about inferior (higher numbered) MSTI IDs in its Reflection Vector. In that case, the first MSTI needs no Reflection Vector, the next eight MSTIs need only a single octet each to hold their Reflection Vectors, the following eight need only two octets, etc., for a total of 8(8+1)/2*8−8=280 octets. The total requirement for 64 MSTIs is then:
The worst case for the convergence of MSTP (not counting the “counting to infinity” problem, wherein stale and current data chase each other around a physical loop in the network) is when an MSTI Regional Root positioned at the edge of a network quietly expires, and the best backup MSTI Regional Root is on the opposite side of the network. MSTP converges in two passes across the network in this case. In pass one, the loss of the MSTI Regional Root is propagated across the network to the new MSTI Regional Root, and in pass two, that new MSTI Regional Root's information is propagated back across the network.
This is because, if the MSTI Regional Root of MSTI 1 is near the original failed MSTI 0 Regional Root, then when the information from the new MSTI 0 Regional Root reaches the MSTI 1 Regional Root, MSTI 0's Reflection Vector may cause MSTI 1 to switch its MSTI Regional Root Port. Only MSTI 0's Reflection Vector can affect MSTI 1. In the worst case, where the even-numbered MSTIs are on one side of the network and the odd-numbered MSTIs are on the other side, it is possible (though unlikely) that each additional MSTI requires an additional propagation pass of information across the network to reach convergence. Thus, an obMSTP network with n MSTIs can require take (n+1) passes across the network in order to converge. Placing the highest priority (lowest numbered) MSTI Regional Roots towards the center of the network is the easiest way to prevent this “sloshing.”
VLAN=((VLAN ID from tag) (Port VLAN Mask)) (PVID (Port VLAN Mask)) (1)
This enables the D and M parts to be applied when receiving a frame from a VLAN-aware end station. As a workaround, the end station (perhaps a router, perhaps a router imbedded in the same chassis as the bridge) can ignore the D and M parts of the VLAN ID when receiving a frame, and always transmit appropriate D and M values. In other words, the port mask, PVID application, and/or VLAN ID translation can be performed on either end of a point-to-point connection between the bridge and a VLAN-aware end station.
FIG. 11 illustrates an example of a network device that may be configured to implement some methods of the present invention. In some embodiments, network device 1160 is a Catalyst™ switch provided by Cisco Systems, Inc. Network device 1160 includes a master central processing unit (CPU) 1162, interfaces 1168, and a bus 1167 (e.g., a PCI bus). Generally, interfaces 1168 include ports 1169 appropriate for communication with the appropriate media. In some embodiments, one or more of interfaces 1168 includes at least one independent processor 1174 and, in some instances, volatile RAM. Independent processors 1174 may be, for example ASICs or any other appropriate processors. According to some such embodiments, these independent processors 1174 perform at least some of the functions of the logic described herein. In some embodiments, one or more of interfaces 1168 control such communications-intensive tasks as media control and management. By providing separate processors for the communications-intensive tasks, interfaces 1168 allow the master microprocessor 1162 efficiently to perform other functions such as routing computations, network diagnostics, security functions, etc.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3855422 *Jul 5, 1973Dec 17, 1974IbmTime division multiplexer with each frame consisting of a fixed length bit oriented address field and a variable length character oriented data fieldUS4706080Aug 26, 1985Nov 10, 1987Bell Communications Research, Inc.Interconnection of broadcast networksUS4926375 *May 5, 1987May 15, 1990Ge Fanuc Automation North America, Inc.Multiple nodes broadcast communication method with receiver identification by bit position in transferred massageUS5195086 *Apr 12, 1990Mar 16, 1993At&T Bell LaboratoriesMultiple call control method in a multimedia conferencing systemUS5303233 *May 20, 1991Apr 12, 1994Nec CorporationArrangement favorably carrying out a connection by the use of an intermediate conversion parameter between input and output virtual channel identifiers (VCI's)US5360005Apr 9, 1992Nov 1, 1994Wilk Peter JMedical diagnosis device for sensing cardiac activity and blood flowUS5506838 *Dec 29, 1994Apr 9, 1996Emc CorporationPacket propagation and dynamic route discovery apparatus and techniquesUS5742604Mar 28, 1996Apr 21, 1998Cisco Systems, Inc.Interswitch link mechanism for connecting high-performance network switchesUS5959968Jul 30, 1997Sep 28, 1999Cisco Systems, Inc.Port aggregation protocolUS5959989Jun 25, 1997Sep 28, 1999Cisco Technology, Inc.System for efficient multicast distribution in a virtual local area network environmentUS6035105Jan 2, 1996Mar 7, 2000Cisco Technology, Inc.Multiple VLAN architecture systemUS6049834May 8, 1998Apr 11, 2000Cisco Technology, Inc.Layer 3 switch unicast protocolUS6163543May 17, 1999Dec 19, 2000Cisco Technology, Inc.Port aggregation protocolUS6219699Mar 26, 1999Apr 17, 2001Cisco Technologies, Inc.Multiple VLAN Architecture systemUS6298061Sep 19, 2000Oct 2, 2001Cisco Technology, Inc.Port aggregation protocolUS6304901Sep 22, 2000Oct 16, 2001Cisco Technology, Inc.Multiple VLAN architecture systemUS6411628 *Feb 2, 1998Jun 25, 2002Intel CorporationDistributed arbitration on a full duplex busUS6533736May 30, 2000Mar 18, 2003Mark MooreWireless medical stethoscopeUS6694034Dec 28, 2000Feb 17, 2004Etymotic Research, Inc.Transmission detection and switch system for hearing improvement applicationsUS6714563 *Apr 26, 1999Mar 30, 2004Cisco Technology, Inc.Network clock synchronization schemeUS6728205 *Feb 4, 1998Apr 27, 2004Massachusetts Institute Of TechnologyMethod and apparatus for automatic protection switchingUS6813250Dec 22, 2000Nov 2, 2004Cisco Technology, Inc.Shared spanning tree protocolUS6879695Oct 3, 2002Apr 12, 2005Advanced Bionics CorporationPersonal sound link moduleUS6889254 *Mar 30, 1999May 3, 2005International Business Machines CorporationScalable merge technique for information retrieval across a distributed networkUS6937576 *Oct 17, 2000Aug 30, 2005Cisco Technology, Inc.Multiple instance spanning tree protocolUS6952483Sep 5, 2002Oct 4, 2005Genisus Systems, Inc.Voice transmission apparatus with UWBUS7177946 *Dec 6, 2001Feb 13, 2007Cisco Technology, Inc.Optimal sync for rapid spanning tree protocolUS7352765 *Oct 29, 2003Apr 1, 2008Broadcom CorporationPacket switching fabric having a segmented ring with token based resource control protocol and output queuing controlUS20020046271 *Apr 3, 2001Apr 18, 2002Huang James Ching-LiangSingle switch image for a stack of switchesUS20020154606 *Jul 2, 2001Oct 24, 2002Duncan Robert JamesNetwork management apparatus and method for determining the topology of a networkUS20020176373 *May 21, 2002Nov 28, 2002Yasuo SatoNode device for ring system, and system and method for constructing multiple spanning trees by using the same node deviceUS20040047300 *Aug 18, 2003Mar 11, 2004Nec CorporationNetwork system, spanning tree configuration method, spanning tree configuration node, and spanning tree configuration programUS20040264458Jun 18, 2004Dec 30, 2004AlcatelArchitecture for bridged ethernet residential access networksUS20050008175May 10, 2004Jan 13, 2005Hagen Lawrence T.Portable system for programming hearing aidsUS20050013260 *Jun 9, 2003Jan 20, 2005Foundry Networks, Inc.System and method for multiple spanning tree protocol domains in a virtual local area networkUS20050100182Nov 12, 2004May 12, 2005Gennum CorporationHearing instrument having a wireless base unitUS20050249372May 3, 2005Nov 10, 2005Siemens Audiologische Technik GmbhHearing aid device and corresponding operating methodUS20060013212 *Jul 13, 2004Jan 19, 2006Hartej SinghPort aggregation across stack of devicesUS20060018496Jul 21, 2005Jan 26, 2006Torsten NiederdrankHearing aid system and operating method therefor in the audio reception modeUS20060098589Jun 14, 2005May 11, 2006Cisco Technology, Inc.Forwarding table reduction and multipath network forwardingUS20070064628 *Sep 16, 2005Mar 22, 2007Tallet Francois ESystem and method for generating symmetrical spanning treesUSD518179Nov 8, 2004Mar 28, 2006David William HolmesHearing aid eartip* Cited by examinerNon-Patent CitationsReference1IEEE Standard for Local and Metropolitan Area Networks Media Access Control (MAC) Bridges, IEEE Std. 802.1D-2004, IEEE Computer Society, Jun. 9, 2004, 295 pages.2IEEE Standard for Local and Metropolitan Area Networks Media Access Control (MAC) Bridges, IEEE Std. 802.1D—2004, IEEE Computer Society, Jun. 9, 2004, 295 pages.3IEEE Standards for Local and Metropolitan Area Networks, Virtual Bridged Local Area Networks, IEEE Std. 802.1Q, 2003 Edition, Institute of Electrical and Electronics Engineers, Inc., May 7, 2003, 368 pages.4PCT Corrected International Search Report and Written Opinion mailed Mar. 26, 2009 in Application No. PCT/US06/05982 [P438WO].5PCT Search Report mailed Sep. 20, 2007, from International Application No. PCT/US06/05982, including Notification of Transmittal (3 pp.).6Understanding Multiple Spanning Tree Protocol (802.1s), Document ID: 24248, Introduction Where to Use MST PVST+ Case Standard 802.1q Case, 12 pages, Apr. 17, 2007.7Written Opinion of the International Searching Authority mailed Sep. 20, 2007, from International Application No. PCT/US06/05982, (5 pp.).Referenced byCiting PatentFiling datePublication dateApplicantTitleUS9008088Nov 22, 2011Apr 14, 2015Rpx Clearinghouse LlcMulticast implementation in a link state protocol controlled ethernet networkUS9148403 *Jan 21, 2011Sep 29, 2015Paul Allen BottorffMethod for aggregating media access control addresses using a summary media access control address(es)US20120188990 *Jul 26, 2012Paul Allen BottorffMethod for aggregating media access control addresses using a summary media access control address(es)US20130148660 *Dec 14, 2012Jun 13, 2013Rockstar Consortium Us LpMulticast implementation in a link state protocol controlled ethernet networkUS20140226527 *Apr 22, 2014Aug 14, 2014Rockstar Consortium Us LpMethod and Apparatus for Exchanging Routing Information and the Establishment of Connectivity Across Multiple Network AreasWO2007133539A2May 8, 2007Nov 22, 2007Cisco Technology, Inc.A technique for efficiently managing bandwidth registration for multiple spanning tree options* Cited by examinerClassifications U.S. Classification370/256, 370/255International ClassificationH04L12/28Cooperative ClassificationH04L12/4645, H04L45/16, H04L12/462, H04L45/00, H04L45/48, H04L12/4633European ClassificationH04L12/46B7, H04L45/00, H04L45/48, H04L45/16Legal EventsDateCodeEventDescriptionJul 14, 2005ASAssignmentOwner name: CISCO TECHNOLOGY, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:FINN, NORMAN;REEL/FRAME:016752/0062Effective date: 20050713Aug 15, 2014FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services