Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-08-08
2004-07-27
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S238000
Reexamination Certificate
active
06768740
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to coordinating updates of forwarding tables in network nodes. More particularly, the present invention relates to updating forwarding tables in a network wherein the tables are determined by a central manager.
2. Description of the Related Art
A typical network consists of nodes and links. A node is a device capable of sending messages to, or receiving messages from, other nodes on the network. Examples of nodes include networked appliances, personal digital assistants, workstations, servers, storage devices, switches, routers, or any other device capable of sending and receiving messages. Nodes are connected (literally or logically) to other nodes by one or more links. The network uses switches and routers to determine over which links a message travels from one node to another. This determination is made according to a locally resident table called a “forwarding table”.
Sometimes the topology between nodes changes. That is, some nodes may be added, removed, non-operative, moved, or replaced. The topology changes may lead to a condition known as a “loop”. A loop occurs when a message is routed by some nodes based on an old topology and by other nodes based on a current topology, with the result being that the message loops between two nodes without being successfully delivered to its ultimate destination.
Various algorithms for loop free forwarding may be used to determine which links are used and which are not to create a unique path from one node to another. The algorithms construct forwarding tables to implement the unique path. One well known method for determining a loop free network is the spanning tree algorithm. The spanning tree algorithm determines a minimum cost tree structure for loop free forwarding. For the purposes of this discussion and simplicity, any node having the ability to forward a message on or within a network will be termed a switch, and any node that does not participate in routing decisions is called an end node.
The topology of the network is dynamic. Nodes or links may change for reasons including node or link failure, planned downtime, removal, upgrade, or any other reason that causes the network to change. When such a change occurs, the algorithms must be run again and the switches must be appraised of the new topology.
In some networks, each switch implements an algorithm to create its forwarding table from control messages passed between switches. Periodically, the switch runs the algorithm and creates a new forwarding table based on the new information. The benefit of each switch creating and maintaining its own forwarding table is that the system is not dependent on a central point of failure for routing information.
In other networks, a single node computes and distributes forwarding tables to the other nodes as needed. This method is beneficial because a central node is better able to create both loop free and dead lock free routing. A dead lock situation might occur when the resource needs of different flows are in conflict.
In either case, all nodes cannot be simultaneously aware of topology changes. During the time the switches are becoming aware of the topology changes either from their own determination or from receiving a new forwarding table from the computing node, there may be loops. Loops might occur when some switches are forwarding according to outdated forwarding tables and some switches are forwarding messages according to updated forwarding tables.
Some rules have been developed for maintaining loop-free forwarding in distributed routing algorithms, i.e., those algorithms in which each node is responsible for computing its own forwarding table. The bridge spanning tree algorithm, for example, requires nodes to wait for an amount of time known as the “pre-forwarding delay” prior to forwarding a message on a link not previously used in the previous spanning tree.
Another algorithm to provide loop-free forwarding and directed to distance vector routing, relies on the coordination between the switches and the delay in switching forwarding tables until the topology changes are known to have been disseminated. This technique is described in “Loop-free Routing Using Diffusing Computations,” by J. J. Garcia-Luna-Aceves, IEEE/ACM Transactions on Networking, February 1993.
Unfortunately, none of the above widely-known techniques for maintaining loop-free forwarding apply to networks in which a central node computes and disseminates loop-free forwarding tables.
BRIEF SUMMARY OF THE INVENTION
The present invention provides a system and method for forwarding messages that includes coordinating the distribution of forwarding tables. The invention includes a version identifier included in a message control portion which indicates which version of the forwarding table to use. For the purposes of this discussion, messages may be referred to as “packets”.
According to one embodiment, a switch receives a packet including its version identifier. If the version of the forwarding table is not resident on the switch, then the switch changes the version identifier to represent an earlier version of the forwarding table. The method then forwards the packet according to the version of the forwarding table represented by the received or updated version identifier as appropriate. When a packet comes from an end node, the method marks the packet with an indication of the most recently received version of the forwarding table. Additionally, when a packet is received with an invalid or absent version identifier, the method marks the packet with an indication of the most recently received version of the forwarding table
In another embodiment, the invention provides receiving a packet including a version identifier and forwarding the packet according to the version of the forwarding table associated with the version identifier wherein different packets may be forwarded according to different forwarding tables.
In another embodiment, the method provides a current table identifier which identifies which version of the forwarding table is currently being used to mark packets from end nodes. When a packet is received from an end node the method marks the packet with an indication of the current table version. A marked packet, either just recently marked from the receiving switch or previously received from another switch, is forwarded according to the version identified in the packet.
In an additional embodiment, when a packet is received that indicates a version of the forwarding table greater than the current table identifier, the method forwards the packet according to the version identified in the packet. In an additional embodiment, the method can modify the current table identifier to reflect the version indicated in the packet.
In still another additional embodiment, if the version identifier received in the packet is less recent than the version of the current table, the method modifies the version identifier in the packet to reflect the current table and forwards according to the current table.
The method may buffer packets in different buffers according to the version such that different versions have different buffers. This buffering is provided to prevent dead lock.
The invention also provides a method of updating forwarding tables in a plurality of switches. A central manager calculates new forwarding tables for each switch and sends each switch its respective table. Once the central manager has determined that all switches have received the new tables, the central manager indicates that each switch may begin using the just recently received forwarding table.
In an additional embodiment, the central manager provides an indication to each of the switches that the switch may delete an old version of the forwarding table after the central manager has determined that all of the switches have received the just recently sent forwarding table.
A system according to the invention provides a memory for storing forwarding tables, a receiver for receiving packets and determ
Cassiday Daniel R.
Hendel Ariel
Perlman Radia J.
Born, Esq. Joseph H.
Chin Wellington
Foley & Hoag LLP
Schultz William
Sun Microsystems Inc.
LandOfFree
Coordinating loop-free forwarding table updates does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Coordinating loop-free forwarding table updates, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coordinating loop-free forwarding table updates will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222146