Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1998-12-09
2003-09-30
Nguyen, Steven (Department: 2663)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S252000, C370S401000
Reexamination Certificate
active
06628624
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer networks, and more specifically, to a method and apparatus for improving and facilitating the identification and selection of loop-free topologies in computer networks.
BACKGROUND OF THE INVENTION
A computer network typically comprises a plurality of interconnected entities. An entity may consist of any device, such as a computer or end station, that “sources” (i.e., transmits) or “sinks” (i.e., receives) data frames. 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 the 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 intranet that may span an entire country or continent.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a “bridging” function between two or more LANs. Alternatively, a switch may be utilized to provide a “switching” function for transferring information between a plurality of LANs or end stations. Typically, the bridge or switch is a computer and includes a plurality of ports that couple the device to the LANs or end stations. Ports used to couple switches to each other are generally referred to as a trunk ports, whereas ports used to couple a switch to LANs or end stations are generally referred to as access ports. The switching function includes receiving data from a sending entity at a source port and transferring that data to at least one destination port for forwarding to the receiving entity.
Switches and bridges typically learn which destination port to use in order to reach a particular entity by noting on which source port the last message originating from that entity was received. This information is then stored by the bridge in a block of memory referred to as a filtering database. Thereafter, when a message addressed to a given entity is received on a source port, the bridge looks up the entity in its filtering database and identifies the appropriate destination port to reach that entity. If no destination port is identified in the filtering database, the bridge floods the message out all ports, except the port on which the message was received. Messages addressed to broadcast or multicast addresses are also flooded.
Additionally, most computer networks include redundant communications paths so that a failure of any given link or device does not isolate any portion of the network. 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, because switches and bridges replicate (i.e., flood) frames whose destination port is unknown or which are directed broadcast or multicast addresses, the existence of loops may cause a proliferation of data frames that effectively overwhelms the network.
Spanning Tree Algorithm
To avoid the formation of loops, most intermediate network devices execute a spanning tree algorithm which allows them to calculate an active network topology that is loop-free (i.e., a tree) and yet connects every pair of LANs within the network (i.e., the tree is spanning). The Institute of Electrical and Electronics Engineers (IEEE) has promulgated a standard (the 802.1D standard) that defines a spanning tree protocol to be executed by 802.1D compatible devices. In general, by executing the spanning tree algorithm, bridges elect a single bridge to be the “root” bridge. Since each bridge has a unique numerical identifier (bridge ID), the root is typically the bridge with the lowest bridge ID. In addition, for each LAN coupled to more than one bridge, only one (the “designated bridge”) is elected to forward frames to and from the respective LAN. The designated bridge is typically the one closest to the root. Each bridge also selects one port (its “root port”) which gives the lowest cost path to the root. The root ports and designated bridge ports are selected for inclusion in the active topology and are placed in a forwarding state so that data frames may be forwarded to and from these ports and thus onto the corresponding paths or links of the network. Ports not included within the active topology are placed in a blocking state. When a port is in the blocking state, data frames will not be forwarded to or received from the port. A network administrator may also exclude a port from the spanning tree by placing it in a disabled state.
To obtain the information necessary to run the spanning tree protocol, bridges exchange special messages called configuration bridge protocol data unit (BPDU) messages.
FIG. 1
is a block diagram of a conventional BPDU message
100
. The BPDU message
100
includes a message header
102
compatible with the Media Access Control (MAC) layer of the respective LAN standard. The message header
102
comprises a destination address (DA) field
104
, a source address (SA) field
106
, and a Service Access Point (SAP) field
108
, among others. The DA field
104
carries a unique bridge multicast destination address assigned to the spanning tree protocol. Appended to header
102
is a BPDU message area
110
that also contains a number of fields, including a root identifier (ROOT ID) field
112
, a root path cost field
114
, a bridge identifier (BRIDGE ID) field
116
, a port identifier (PORT ID) field
118
, a message age (MSG AGE) field
120
, a maximum age (MAX AGE) field
122
, a hello time field
124
, and a forward delay (FWD DELAY) field
126
, among others. The root identifier field
112
typically contains the identifier of the bridge assumed to be the root and the bridge identifier field
116
contains the identifier of the bridge sending the BPDU. The root path cost field
114
contains a value representing the cost to reach the assumed root from the port on which the BPDU is sent and the port identifier field
118
contains the port number of the port on which the BPDU is sent.
Each bridge initially assumes itself to the be the root and transmits BPDU messages accordingly. As a result, bridges continuously receive BPDU messages. Upon receipt of a BPDU message, its contents are examined and compared with similar information (e.g., assumed root and lowest root path cost) stored by the receiving bridge. If the information from the received BPDU is “better” than the stored information, the bridge adopts the better information and uses it in the BPDUs that it sends (adding the cost associated with the receiving port to the root path cost) from its ports, other than the port on which the “better” information was received. Although BPDU messages are not forwarded by bridges, the identifier of the root is eventually propagated to and adopted by all bridges as described above, allowing them to select their root port and any designated port(s).
In order to adapt the active topology to failures, the root periodically (e.g., every hello time) transmits BPDU messages. The hello time utilized by the root is also carried in the hello time field
124
of its BPDU messages. The default hello time is two seconds. In response to receiving BPDUs, bridges transmit their own BPDUs. Thus, every two seconds BPDUs are propagated throughout the bridged network, thereby confirming the active topology. As shown in
FIG. 1
, BPDU messages stored by the bridges also include a message age field
120
which corresponds to time since the root instigated the generation of this BPDU information. That is, BPDU messages from the root have their message age field
120
set to “0”. Thus, every hello time, BPDU messages with a mes
Jain Praveen
Mahajan Umesh
Mellacheruvu Ramana
Cesari and McKenna LLP
Cisco Technology Inc.
Duong Duc
Reinemann Michael R.
LandOfFree
Value-added features for the 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 Value-added features for the spanning tree protocol, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Value-added features for the spanning tree protocol will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3071474