Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-07-22
2003-09-30
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C256S013000
Reexamination Certificate
active
06628661
ABSTRACT:
BACKGROUND
This invention relates to recovering spanning trees in computer networks.
A computer network is two or more autonomous computers (or “end-stations”) interconnected by communication links to facilitate the exchange of information. A Local Area Network (LAN) is a network typically implemented within a relatively small geographical area, such as with a factory or college campus. As a practical matter, each LAN has a maximum number of end-stations that it can support. If the practical upper limit of end-stations is approached or exceeded, network performance falls off dramatically. Accordingly, to enable virtually any number of end-stations to communicate with one another over a network, multiple LANs can be connected to each other with bridges (equivalently, gateways or switches).
FIG. 1
shows an example of a structure—referred to as an “extended LAN” or, equivalently, a “bridged, multiple segment LAN” —that results from interconnecting LANs. In this example, nine individual LANs (numbered
1
-
9
) are interconnected by ten bridges (lettered A-J). As a result of the bridge interconnections, an end-station on LAN
9
, for example, can communicate with end-stations on any of the other eight LANs by routing messages (e.g., communication packets or “frames”) as appropriate through one or more of the Bridges A-J. Each bridge that receives a frame forwards it on to the other bridges as appropriate to deliver the message to its intended recipient.
Two basic bridging architectures exist for interconnecting LANs: “source routing” and “transparent bridging.” A third bridging architecture—source routing transparent bridging—is a hybrid of the other two. Source routing transparent bridging is described in ANSI/IEEE Std. 802.1D, 1993 Edition, which is incorporated by reference.
In the source routing architecture, the specific route that a frame is to take through the network—that is, from the “source” end-station to the “destination” end-station—is carried within the frame itself. The routing information in a source routing frame must specify each step along the way from the source end-station to the destination end-station. Accordingly, prior to sending a frame, the sending end-station must have knowledge of the network topology so that a specific “source route” can be specified in the frame to be sent. This knowledge of the network topology is obtained by sending a preliminary frame known as an “explorer frame,” which propagates through the network and gathers information about each network bridge and LAN through which it passes. A detailed description of the source routing architecture and related protocols is set forth in IEEE standards such as IEEE 802.1 and IEEE 802.5.
In the transparent bridging architecture, in contrast, routing information for a frame is not carried within the frame and thus need not be known to, or specified by, the source end-station prior to sending a frame. Rather, routing is determined by the destination address of a frame (i.e., the network address of the destination end-station) and by routing tables maintained at each bridge in the network. In particular, each bridge maintains a table that can include the identity of all potential destinations (end-stations) in the network. For each potential destination, a bridge's routing table identifies an associated “destination LAN” —that is, a particular one of the various LANs connected to the bridge that leads to, either directly or indirectly, the specified destination end-station.
When a bridge receives an incoming frame from one of its connected LANs (referred to as the “source LAN”), the bridge inspects the destination address in the frame and forwards the frame on to the destination LAN specified in the routing table. If, however, the destination LAN is the same as the source LAN, then the frame is discarded. On the other hand, if the destination address specified in the frame is unknown (i.e., not listed in the bridge's routing table), then the bridge forwards the frame on to all LANs to which it is connected (except for the source LAN)—a process known as “flooding.”
A potential consequence of flooding is that, if each physical port in each bridge in the network is allowed to transmit and receive frames, infinite loops are likely to result. Consequently, frames will be cycled through the network perpetually and eventually will clog the network when enough accumulate.
To prevent such infinite loops, a concept known as a “spanning tree” is employed. In a spanning tree, a loop-free topology is realized by selectively designating physical ports on the bridges as either “blocking” or “forwarding.” “Forwarding” ports on a bridge are allowed to pass frames while “blocking” ports are prohibited from passing frames on to the LAN connected to the blocked port
FIG. 2
shows an example of a spanning tree that could be used for the network k of FIG.
1
. The solid lines between Bridges A-J represent connections between bridge ports that are in forwarding states. These connections form part of the spanning tree for the network. The dotted lines, in contrast, represent connection between bridge ports that are in a blocking state and thus which are not part of the spanning tree for the network.
As an example of spanning tree routing, assume a frame originates at source LAN
8
and is bound for destination LAN
6
. Such a frame would be routed according to the spanning tree in
FIG. 2
as follows: LAN
8
to Bridge H to LAN
5
to Bridge D to LAN
2
to Bridge B to LAN
3
to Bridge E to LAN
6
. Note that the otherwise shorter (lower cost) path through Bridge G is unavailable because Bridge G is not part of the spanning tree. Although in some situations, as in this example, the use of a spanning tree results in a longer path from source to destination, it nevertheless ensures a loop-free topology with connectivity between each end-station.
When a network is first installed, the spanning tree needs to be generated in the first instance. To do so, first the bridges have to choose one bridge that will serve as the root of the tree. Typically, this is accomplished by having each bridge broadcast a special packet referred to as a BPDU (“Bridge Protocol Data Unit”) packet. The BPDU packet includes the bridge's serial number—or MAC (Media Access Control) address—which is installed by the bridge manufacturer and is guaranteed to be worldwide unique. Then, the bridge having the lowest MAC address is chosen as the root. Next, a spanning tree is constructed from the root to every bridge and LAN in the network based on the least cost path between each LAN, with least cost being related to bandwidth. An algorithm for generating a spanning tree is specified in the IEEE 802.1D standard (1993 ed.), which is incorporated by reference.
Under normal operating conditions, various situations may arise that require the re-generation of a spanning tree. For example, when a network is taken down for whatever reason and then brought back up, the spanning tree must be re-generated before useful network communications can occur. As another example, when a communication failure occurs after the spanning tree already has been generated (e.g., either by a bridge or a communication link failing), the bridges in the network typically will re-run the spanning tree algorithm to build a new spanning tree that reflects the changed network topology. During this re-generation of the spanning tree, which typically takes anywhere between 10 and 50 seconds to complete, no communication between LAN end-stations can occur.
SUMMARY
Various implementations of the invention may include one or more of the following features.
In general, in one aspect, a spanning tree is managed (e.g., generated and/or recovered) in a computer network by identifying a network core (e.g., a high bandwidth portion of the computer network), determining a distance to the network core for each switch in the network, and generating and/or recovering a spanning tree for the network based on the switches' relative distances to the network core. Prior to determining
Dyrga Ryszard W.
Goldman Tomasz J.
Tondering Claus
Fish & Richardson P.C.
Intel Corporation
Nguyen Brian
Olms Douglas
LandOfFree
Spanning tree recovery in computer networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Spanning tree recovery in computer networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanning tree recovery in computer networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3048536