Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-08-31
2001-10-16
You, Kwang B. (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S408000
Reexamination Certificate
active
06304575
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer networks, and more specifically, to an improved method and apparatus for generating loop-free paths in token ring networks.
BACKGROUND OF THE INVENTION
A computer network typically comprises a plurality of interconnected nodes. A node may consist of any device, such as a host, endstation, server, etc., that transmits or receives data frames. A common type of 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 Token Ring or Ethernet, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack), such as the Transport Control Protocol/Internet Protocol (TCP/IP) Reference Model.
In a token ring network, each node or endstation is connected to a physical ring that carries data frames transmitted by the various stations in a single direction. Each station, moreover, acts like a repeater, transmitting all received data frames to the next station on the ring. The right to transmit data on the ring is controlled by a token, which continuously traverses the ring. A token that permits data transmission is referred to a free token. When a station receives the free token and has data to send, it changes the token's configuration to that of a busy token and attaches the busy token to the data frames being sent. As each data frame returns to the sending station, it is removed from the ring. Upon receipt of the last data frame, the sending station transmits a free token to the next station which may, in turn, transmit its own data frames. To simplify network maintenance and troubleshooting, each station is typically connected to the ring through a central concentrator.
Often, it is desirable to connect multiple token ring LANs together and thereby allow the endstations from one ring to exchange information with endstations on other rings. One or more intermediate devices are often used to interconnect multiple token ring LANs. For example, a bridge may be used to provide a “bridging” function between two or more token ring LANs. Alternatively, a switch may be utilized to provide a “switching” function for transferring information between a plurality of token ring LANs. Typically, the bridge or switch is a computer and includes a plurality of ports that couple the device to the token ring LANs.
Token Ring Routing Methods
There are basically two methods of routing frames across multiple interconnected token ring LANs. The first is referred to as source-route bridging (SRB). With source-route bridging, endstations are responsible for determining the route or path to be following through the network in order to reach a desired endstation. The endstations are also responsible for inserting this route information into a routing information field (RIF) of each source-route data frame being sent. The RIF is an ordered list of ring number/bridge number pairs through which the frame is to pass as it traverses the network. When such a frame is received by an SRB bridge, the contents of the RIF are examined to determine whether its entry port's ring number and its bridge number appear in the RIF field. If so, the SRB bridge forwards the frame to the destination port that is coupled to the ring number paired with its bridge number. However, if this ring number already appears in the RIF (e.g., it is paired with some other bridge number), then the frame is dropped since it presumably traversed that ring prior to reaching this SRB bridge. SRB bridges also drop any frames that do not contain an RIF.
In order to determine a path to a particular receiving station, a sending station transmits an explorer frame, such as an all routes explorer frame. SRB bridges receiving an explorer frame add routing information to the frame and forward it out all ports, other than the port on which it was received. The receiving station will thus receive multiple explorer frames, each carrying different routing information. The receiving station examines all of these explorer frames to identify the best (typically the shortest) path to the sending station. This path information is then returned to the sending station so that it may be used in any subsequent messages. With this routing scheme, SRB bridges need not maintain routing tables. All that is required is that each SRB bridge know its unique bridge identifier and the token ring numbers of each ring to which it is attached.
The other routing method is known as transparent routing. With transparent routing, a sending station does not know the path a frame should follow to reach other stations. Instead, the sending station inserts the receiving station's Media Access Control (MAC) address (known as the destination address) and its own MAC address (known as the source address) into each frame. A transparent bridge that receives the frame examines the destination address to identify the destination port onto which the frame should be forwarded. Transparent bridges typically learn which destination port to use for a given destination address by noting on which source port the latest message originating from that entity was received. This information is then stored by each bridge in a block of memory known as a filtering database. Thereafter, when a message is received on a source port, the bridge looks up the destination address in its filtering database and identifies the appropriate destination port for reaching the respective endstation. If no destination port is identified in the filtering database, the bridge floods the message out all ports, other than the source port.
The Institute of Electrical and Electronics Engineers (IEEE) has promulgated a standard, the 802. 1D standard, which governs the design and operation of bridges. This standard calls for bridges to have the capability to operate in either a source-route or a transparent mode, depending on the type of frame that it receives. That is, if the data frame includes an RIF, then the source-route transparent (SRT) bridge operates in a source-route mode with respect to this frame. If the frame does not include a RIF, the SRT bridge operates in a transparent mode by examining the destination MAC address of the frame and performing a look-up in its filtering database. Although this standard has been widely adopted, many token ring networks, especially those corresponding to the IBM Corporation token ring architecture, still utilize intermediate devices (referred to herein as legacy bridges or legacy devices) that operate only in the SRB mode.
Most computer networks also include redundant communications paths so that a failure of any given link does not isolate any portion of the network. The existence of redundant links, however, often results in the formation of circuitous paths or “loops” within the network which are highly undesirable because messages may traverse the loops indefinitely. The resulting traffic effectively overwhelms the network. For example, SRT bridges, as described above, replicate messages whose destination ports are not known or which contain broadcast or multicast destination addresses, resulting in a proliferation of data frames along any loops. Similar problems may occur with broadcast or multicast messages in networks operating in the SRB mode.
Spanning Tree Algorithm
To avoid the formation of loops, most intermediate 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). 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 token ring coupled to more than one bridge, only one (the “designated bridge”) is elected to forward f
Adams Kara J.
Carroll David A.
Jain Praveen
Potter, Jr. Kenneth H.
Cesari and McKenna LLP
Cisco Technology Inc.
You Kwang B.
LandOfFree
Token ring 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 Token ring spanning tree protocol, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Token ring spanning tree protocol will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2606270