Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-03-31
2003-04-29
Vu, Huy D. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S403000, C370S469000, C709S242000
Reexamination Certificate
active
06556574
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to operation of routers in computer networks, and more particularly to maintenance of tables of Route Information Field information (RIF information) used in Source Routing Bridge subnets (SRB subnets).
BACKGROUND
A computer network comprises, in the simplest instance, a plurality of computers connected together by a communications media so that the computers can exchange messages. The computers are usually referred to as “stations”.
In an exemplary embodiment, the communications media is arranged as a continuous ring and the stations are attached to the ring. This embodiment is referred to as a “token ring” local area network. The stations pass a special control message referred to as a “token” around the ring from one station to the next, and the station which holds the token transmits its messages onto the ring. When it is finished, the station transfers the token to the next station on the ring.
In an alternative exemplary embodiment, a local area network may implement the Ethernet protocol, or the closely related IEEE 802.3 Standard protocol. In an Ethernet system all terminals are connected to a common bus. Any station can transmit when it determines that the bus is free, and if a collision of packets is detected on the bus, then the stations quit transmitting and back off for a “backoff time interval”, and then try again. Other alternative network hardware technologies comprise FDDI token ring, ATM networks, etc.
The present discussion will focus particularly on token ring local area networks and their interconnection into larger networks.
A more complex token ring computer network comprises several token rings connected together by specialized stations referred to as “bridges”. A message originating at a source station on one token ring can reach a destination station on another token ring by passing through one or more bridges, where the specialized job of the bridges is to forward messages from one token ring to another. In an exemplary embodiment, there may be a plurality of bridges between a first token ring and a second token ring. And the path which the message takes from a source station on a source token ring may pass through several intermediate token rings, before reaching the destination station on the destination token ring. Further, with a plurality of bridges between each pair of a plurality of token rings, there are many paths through token rings and bridges which the message can take from the source station and the destination station.
In an exemplary embodiment of computer networks, referred to as “source route bridge (SRB) networks”, the source station puts a specification of the path into the message. The specification is placed in the Route Information Field, the RIF, of the message. The RIF determines the path that the message is to follow through the bridges and token rings as it travels from the source station to the destination station. The RIF is placed by the source station into a header of the message. The bridges read the header and forward the message in accordance with the RIF specification.
A router is another specialized station which enables joining many computer networks together. For example, a router can join several computer networks formed from token rings and bridges. Also a router can join a token ring network to an Ethernet network, an FDDI network, etc., a telephone line or a telephone like line, etc. to form a Wide Area Network (WAN). The parts of a WAN may be widely separated, and joined by the telephone like line.
Routers are used to implement hierarchical addressing. Hierarchical addressing commonly uses a two level addressing method. A first level corresponds to Layer 2 of the OSI communications model, and a second level corresponds to Layer 3 of the OSI communications model. Hierarchical addressing permits Layer 3 to be independent of the communications media. The OSI model Layer 2 depends upon the communications media, the Layer 2 hardware technology (such as token ring, Ethernet, etc.), and other Layer 1 and Layer 2 details. Accordingly, a programmer can write code to implement Layer 3 functions without having concern for media dependent details which are handled by Layer 2 functions.
Hierarchical addressing is important in the construction of large networks, for example networks having many thousands of stations, by permitting a single computer to maintain a table of network addresses without having to keep a table giving the physical address of each individual computer on an entire network (for example, the Internet). A packet is sent to a router on the designated destination network, and that router keeps a table of the Layer 2 address of computers on the destination network. Without hierarchical addressing each router would have to keep tables of the Layer 2 addresses of all computers on the entire network, rather than simply keeping a network address referring to the computers on that particular network, and there are many fewer networks than there are computers. Radia Perlman treats hierarchical addressing in her book
Interconnections, Bridges and Routers
, published by Addison Wesley Publishing Company, in 1992, all disclosures of which are incorporated herein by reference, particularly in Chapter 6, pages 149-164.
Commonly used terminology refers to a small local area network as a “subnet”. For example, a plurality of token rings joined by bridges is a subnet. Also an Ethernet with one bus, or with several busses joined by bridges, is a subnet. A “network” then refers to several subnets joined by a router. A router or a bridge can be connected to a telephone type line and join subnets in distant cities. For example, a bridge may forward frames using Data Link Switching to interconnect subnets in distant cities. A “wide area network” (WAN) refers to subnets joined by routers or bridges, with the subnets typically being widely separated, for example, in different cities.
Each station has a physical address, also referred to as the MAC address, and the physical address is the OSI model Layer 2 address. The Layer 2 address is also referred to as the “Link Address”. Also, each station is assigned a Layer 3 address or network address. For example, in the TCP/IP protocol the Layer 3 (network) address is referred to as the Internet Protocol address, or IP, address. The two levels of hierarchical addressing, the Layer 2 address and Layer 3 address, are typically used in the OSI model to implement subnets and networks.
The physical address is written into a semi-permanent memory device when the station is manufactured, and is referred to as the “burned in” address. However, the physical address may be changed by the owner of the station, by overriding the burned in address with a locally administered address, referred to as a LAA address.
On a subnet, a message is addressed to both the physical address and the Network address of the destination station. A bridge simply forwards the message. In the SRB network embodiment, where the message carries RIF information, the bridge obeys the instructions in the RIF of the message and forwards the message only along the path specified by the RIF.
However, when the source station and the destination station are on different subnets, the message is addressed to the physical address of a router and the Network address of the destination station. The addressed router is a station on the subnet of the source station. The router recognizes its physical address in the message, reads the Network address of the destination station from the header of the message, and then makes a decision as to how to route the message so that it goes to the destination station. The router writes a new header into the packet message before forwarding it onto the next SRB subnet The new header contains a new RIF. The new RIF directs the message through the token rings and bridges of the new SRB subnet. Alternatively, the new subnet may an Ethernet LAN, and in this case the router builds an Ethernet packet.
In making its decision, the router uses tables which co
Karkhanis Nitin
Livingston Richard
Pearce Bernie Paul
Cesari and McKenna LLP
Cisco Technology Inc.
Ho Duc
Vu Huy D.
LandOfFree
Duplicate ignore delay timer for ARP like protocol messages... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Duplicate ignore delay timer for ARP like protocol messages..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Duplicate ignore delay timer for ARP like protocol messages... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3056587