Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
2000-12-22
2004-11-02
Ho, Duc (Department: 2665)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S402000, C370S397000
Reexamination Certificate
active
06813250
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer networks and, more specifically, to a shared spanning tree protocol for defining a plurality of loop-free paths within a computer network.
BACKGROUND OF THE INVENTION
Many organizations, including businesses, governments and educational institutions, utilize computer networks so that employees and others may share and exchange information and/or resources. A computer network typically comprises a plurality of entities interconnected by means of one or more communications media. An entity may consist of any device, such as a computer, that “sources” (i.e., transmits) or “sinks” (i.e., receives) data frames over the communications media. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the functions performed by data link and physical layers of a communications architecture (i.e., a protocol stack). In many instances, several LANs may be interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network (“WAN”) or internet that may span an entire country or continent.
One or more intermediate devices is often used to couple LANs together and allow the corresponding entities to exchange information. For example, a switch may be utilized to provide a “switching” function for transferring information, such as data frames, among entities of a computer network. Typically, the switch is a computer and includes a plurality of ports that couple the switch to the other entities. The switching function includes receiving data at a source port from an entity and transferring that data to at least one destination port for receipt by another entity.
In addition, most computer networks include redundant communications paths so that a failure of any given link does not isolate any portion of the network. Such networks are typically referred to as meshed or partially meshed networks. The existence of redundant links, however, may cause the formation of circuitous paths or “loops” within the network. Loops are highly undesirable because data frames may traverse the loops indefinitely.
Furthermore, some devices, such as bridges or switches, replicate frames whose destination is not known resulting in a proliferation of data frames along loops. The resulting traffic effectively overwhelms the network. Other intermediate devices, such as routers, that operate at higher hierarchical layers, such as the Internetwork Layer of the Transmission Control Protocol/Internet Protocol (“TCP/IP”) reference model within the protocol stack, deliver data frames and learn the addresses of entities on the network differently than most bridges or switches, such that routers are generally not susceptible to sustained looping problems.
Spanning Tree Algorithm
To avoid the formation of loops, intermediate devices, such as bridges or switches, execute what is known as a spanning tree algorithm. This algorithm effectively “severs” the redundant links within network segments. More specifically, switches exchange special messages called bridge protocol data unit (BPDU) frames that allow them to calculate a spanning tree, which is a subset of the network segment that is loop-free (i.e., a tree) and yet connects every pair of LANs within the segment (i.e., the tree is spanning). The BPDU frames contain sufficient information, such as the relative cost of transmitting data frames over the links and interconnecting LANs, for the switches to discover a loop-free tree. Using this information, the switches calculate the tree in accordance with the algorithm and typically elect to sever or block all but one of the redundant links or communications paths. The spanning tree algorithm and the BPDU messages are well-known and documented (see IEEE Standard 802.1D).
In particular, execution of the spanning tree algorithm typically causes the switches to elect a single switch, among all the switches within each network segment, to be the “root” switch. The root is the switch having the lowest identifier (switch ID) of all switches in the particular network segment. Switch IDs, moreover, typically include a fixed portion and a settable portion. Accordingly, by modifying the settable portion of the ID of a given switch, a network administrator may “force” the network to elect that switch as the root. In addition, for each LAN coupled to more than one switch, a “designated switch” is elected which will forward frames from the LAN toward the root. The designated switch is typically the closest switch to the root.
Each switch also chooses a port (e.g., the “root port”) which gives the best path from the switch to the root and selects those ports that are to be included in the spanning tree (i.e., the root port and any port for which the switch has been elected as a designated switch). These ports are placed in a forwarding mode so that data frames may be forwarded to and from the ports and thus onto the corresponding paths or links. Ports not included within the spanning are placed in a blocking mode. When a port is in the blocking mode, the associated switch will not forward any data frames to or from that port.
As links fail or are repaired or as new links are added to a network, the spanning tree is re-calculated. In response, ports may transition from the blocking mode to the forwarding mode and vice versa. Rather than transition directly from the blocking mode to the forwarding mode, ports transition through two intermediate states: a listening state and a learning state. In the listening state, a port waits for information suggesting that it should return to the blocked mode. If, at the expiration of a timer, no such information has been received, the port transitions to the learning state. In the learning state, a port still blocks the forwarding of frames but received frames are examined and the location information contained therein, including the source of the frame, is stored. At the expiration of a second timer, the port finally transitions to the forwarding mode where frames may be forwarded from and received at the port.
Virtual Local Area Networks
A computer network may also be segregated into a series of network groups. For example, U.S. Pat. No. 5,394,402, issued on Feb. 28, 1995 to Floyd E. Ross (the “'402 Patent”) discloses an arrangement that is capable of associating any port of a switch with any particular segregated network group. Specifically, according to the '402 Patent, any number of physical ports of a particular switch may be associated with any number of groups within the switch by using a virtual local area network (VLAN) arrangement that virtually associates the port with a particular VLAN designation. More specifically, Ross discloses a switch or hub for a segmented virtual local area network with shared media access that associates VLAN designations with at least one internal port and further associates those VLAN designations with messages transmitted from any of the ports to which the VLAN designation has been assigned.
The VLAN designation for each internal port is stored in a memory portion of the switch such that every time a message is received by the switch on an internal port the VLAN designation of that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in a memory based on the internal port where the message originated. In addition to the '402 patent, an IEEE standards committee is preparing a standard for Virtual Bridged Local Area Networks. See IEEE Standard 802.1Q (draft).
In many cases, it may be desirable to interconnect a plurality of these switches in order to extend the VLAN associations of ports in the network. Ross, in fact, states that an objective of his VLAN arrangement is to allow all ports and entities of the network having the same VLAN designation
Fine Michael
Gai Silvano
McCloghrie Keith
Cesari and McKenna LLP
Cisco Technology Inc.
Ho Duc
Nguyen Phuongchau Ba
LandOfFree
Shared spanning tree protocol does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shared spanning tree protocol, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared spanning tree protocol will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3301497