Coordinating loop-free forwarding table updates

• US 6,768,740 B1
• Filed: 08/08/2000
• Issued: 07/27/2004
• Est. Priority Date: 08/08/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Hendel, Ariel, Perlman, Radia J., Cassiday, Daniel R.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): SCHULTZ, WILLIAM C
• Application Number:
  US09/633,969
• Time in Patent Office: 1,449 Days
• Field of Search: 370/230, 370/231, 370/238, 370/252, 370/389, 370/392, 370/255, 370/256, 370/402
• US Class Current: 370/392
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/18 Loop-free operations

Abstract

A central node in a network computes for, and sends to, each node a forwarding table which consists of the set of neighbors to which the node should forward a message intended for a particular destination. The message includes a version number in the packet field header indicating which forwarding table version the node should use to forward the packet. The node does not begin marking and forwarding packets according to the new version number immediately. The node may wait a period of time after receiving the new table or may wait until receiving notification from the fabric manager to begin using the new version number. When a node receives a message from an end node, it inserts either the most recently received version number in one embodiment or uses the version dictated by the fabric manager in another embodiment. If the node receives a message from another node with a forwarding table version not resident at the node, the node will forward the packet with the most recent version of the forwarding table it has resident and change the version in the message accordingly prior to forwarding.

Claims

1. A method for forwarding a packet comprising:

receiving in a switch the packet including an incoming version identifier representing a forwarding table associated with the packet; and

changing the version identifier to represent an earlier forwarding table if the forwarding table represented by the version identifier is not resident on the switch.

2. The method of claim 1, further comprising:

forwarding the packet according to the forwarding table represented by the incoming version identifier if the version identifier was not updated,

otherwise forwarding the packet according to the forwarding table represented by the updated version identifier.

3. The method of claim 2, further comprising:

changing the version identifier to represent a latest forwarding table if the packet is from an end node.

4. The method of claim 2, further comprising:

associating a buffer with the version identifier; and

buffering the packet in the buffer associated with the version identifier.

5. A method of forwarding a packet comprising:

storing at least one forwarding table;

receiving a packet having a forwarding table identifier;

determining whether the forwarding table identifier is associated with the at least one forwarding table;

modifying the forwarding table identifier to show association with the at least one stored forwarding table if the forwarding table identifier is not associated with the at least one forwarding table; and

forwarding the packet according to the at least one forwarding table.

6. A method for forwarding a packet comprising:

receiving in a switch the packet including a version identifier representing a forwarding table associated with the packet; and

modifying the version identifier in the packet if the forwarding table represented by the version identifier is not resident on the switch.

7. The method of claim 6, further comprising modifying the version identifier to reflect an earlier version identifier associated with an earlier forwarding table and forwarding the packet according to the earlier forwarding table.

8. The method of claim 7, further comprising:

modifying the version identifier in the packet if the packet is from an end node to reflect a latest version identifier associated with a latest forwarding table and forwarding the packet according to the latest forwarding table;

forwarding the packet according to the forwarding table represented by the version identifier if the forwarding table represented by the version identifier is resident on the switch.

9. A method of forwarding a packet in a switch comprising:

receiving a first forwarding table;

receiving a second forwarding table;

receiving a packet including a forwarding table identifier;

forwarding the packet according to the first forwarding table if the forwarding table identifier is associated with the first forwarding table; and

forwarding the packet according to the second forwarding table if the forwarding table identifier is associated with the second forwarding table.

10. The method of claim 9, further comprising:

buffering the packet in a first buffer if the forwarding table identifier is associated with the first forwarding table; and

buffering the packet in a second buffer if the forwarding table identifier is associated with the second forwarding table.

11. A method of forwarding a packet comprising:

receiving a packet including an incoming version identifier representing a forwarding table associated with the packet;

modifying the incoming version identifier if the packet is from an end node; and

forwarding the packet according to the forwarding table associated with the modified version number if the version identifier was modified, otherwise the forwarding table associated with the incoming version identifier.

12. The method of claim 11, further comprising:

buffering the packet in a first buffer associated with the forwarding table corresponding to the modified version identifier if the version identifier was modified; and

buffering the packet in a second buffer associated with the forwarding table corresponding to the incoming version identifier if the version identifier was not modified.

13. A method of forwarding a packet comprising:

receiving a packet; and

modifying a current table identifier in accordance with a version identifier field in the packet if the version identifier field represents a version greater than the current table identifier.

14. The method of claim 13, further comprising forwarding packet according to a forwarding table associated with the current table identifier.

15. The method of claim 13, further comprising:

modifying the packet to indicate the current table identifier prior to forwarding if the version identifier field is absent or invalid.

16. The method of claim 14, further comprising:

modifying the packet to indicate the current table identifier prior to forwarding if the version identifier field represents a version lesser than the current table identifier.

17. The method of claim 15, further comprising:

modifying the packet to indicate the current table identifier prior to forwarding if the version identifier field represents a version lesser than the current table identifier.

27. The system of claim 15, wherein the sending a respective new forwarding table includes sending an indication of the differences between the old forwarding table and the new forwarding table.

18. A method of updating forwarding information in a plurality of switches comprising:

calculating a new forwarding table for each switch;

sending a respective new forwarding table to each of the plurality of switches;

determining whether each of the plurality of switches has received its respective new forwarding table; and

sending a message to each of the plurality of switches allowing each switch to delete an old forwarding table after determining that each of the switches received its respective new forwarding table.

19. A method of updating of routing information in a plurality of switches comprising:

calculating a new forwarding table for each switch;

sending a respective new forwarding table to each of the plurality of switches;

determining whether each of the plurality of switches has received its respective new forwarding table;

sending to each switch an indication to forward according to the new forwarding table after determining that each of the switches received its respective new forwarding table.

20. The method of claim 19, further comprising:

determining whether each of the plurality of switches has received its respective indication to forward according to the new forwarding table; and

sending a message to each of the plurality of switches allowing each switch to delete an old forwarding table after determining that each of the switches received its indication.

21. A system for forwarding a packet comprising:

a memory configured to store forwarding tables;

a receiver configured to receiving the packet from a node and determine a forwarding table version; and

a forwarding unit configured to forward the packet according to a forwarding table associated with the forwarding table version.

22. The system of claim 21, further compromising:

a plurality of buffers each corresponding to a respective forwarding table; and

the forwarding unit includes a module configured to place the packet in the buffer corresponding to the forwarding table version.

23. The system of claim 21, further compromising:

a modifying unit configured to modifying the forwarding table version in the packet if an associated forwarding table is not stored in the memory.

24. The system of claim 21, further compromising:

a current forwarding table indicator; and

a marking unit is configured to modify the packet to indicate the current forwarding table.

25. The system of claim 24, wherein the current forwarding table indicator is a single bit.

26. The system of claim 25, wherein the modifying unit is configured to modify a single bit in the packet.