Automatic link failover in data networks

• US 7,042,837 B1
• Filed: 10/25/2000
• Issued: 05/09/2006
• Est. Priority Date: 10/25/2000
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Satterfield, David L., Cassiday, Daniel R.
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Wong, Blanche
• Application Number:
  US09/697,663
• Time in Patent Office: 2,022 Days
• Field of Search: 370/237, 370/238, 370/225, 370/226, 370/227, 370/228, 370/241, 370/242, 370/244, 370/239, 709/239, 709/241
• US Class Current: 370/225
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00

Abstract

Methods and apparatus are disclosed for enabling nodes in a data network having interconnect links to continue to transmit data when a link fails. This is done in realtime, in a manner transparent to upper-level clients, and at a hardware level without software intervention. A method is described in which a data packet is received or stored in a transmitter buffer at an originating node having a failed link where the data packet is scheduled to use the failed link. The data packet is routed to a failover storage area. The failover storage area is a shared resource in the node and consists of two first-in, first-out stacks for processing and routing the failover data packets. If needed, an alternative link is selected for the data packet and the data packet is routed to a transmitter associated with the alternative link. An alternative link is selected using a primary and secondary routing table, also part of the shared resource of the node. The data packet is then transmitted to a receiver for the alternative link at a destination or multihop node. This allows the data packet to reach the remote end of a failed link by sharing alternate links connecting the local and remote ends of a failed link.

Claims

1. A method of twitting data over a network having a plurality of nodes and links when a link has failed, the method comprising:

receiving a data packet at a first node having a failed link, the data packet scheduled to use the failed link;

converting the data packet to a failover data packet at the first node by marketing the data packet as a failover pact and recomputing a CRC value;

routing the data packet to a failover storage area;

determining an alternative link for the data packet and muting the data packet to a transmitter associated with the alternative link; and

transmitting the data packet to a receiver for the alternative link in a second node, thereby allowing the data packet to reach an intended destination by effecting the first node at a hardware level and without software intervention.

2. A method as recited in claim 1 further comprising:

detecting a specific link failure at the first node; and

switching the first node to failover mode for the specific link.

3. A method as recited in claim 2 further comprising:

notifying a third node at the far-end of the specific link of the failure; and

switching the third node to failover node for the specific link.

4. A method as recited in claim 1 further comprising examining one or more failover route tables using a destination node identifier as an index and retrieving the alternative link.

5. A method as recited in claim 4 further comprising querying a primary route table using the destination node identifier to retrieve a primary link.

6. A method as recited in claim 5 further comprising querying a secondary route table to retrieve the alternative link if the primary link is a failed link.

7. A node in a communication network comprising:

a receiver including a failover buffer for routing a failover data packet;

a first-in, first-out (FIFO) data storage area for storing the failover data packet and routing the data packet to a receiver or a transmitter; and

a failover routing table including at least two rows, a row corresponding to a neighboring node, and one or more interconnect links, wherein the node is configured to detect a failure in a link connected to the node, wherein if a data packet at the node is scheduled to use the failed link, the failover route tables are configured to determine an alternative link to transmit the data packet to not disrupt the transmission of the data packet;

wherein the FIFO data storage area includes a first FIFO data stack, a second FIFO data stack, and a plurality of multiplexers.

8. A node as recited in claim 7 wherein the receiver further comprises a multiplexer for routing the failover data packet to the failover buffer.

9. A node as recited in claim 7 wherein the first FIFO data stack outputs data to a transmitter and accepts input data from a receiver and a transmitter and the second FIFO data stack outputs data to a transmitter and a receiver and accepts input data from a receiver.

10. A node as recited in claim 7 wherein the failover routing table further comprises a first column for storing a node identifier and a second column for storing a transmitter identifier.

11. A node as recited in claim 7 further comprising a transmitter having an arbitrator for determining whether a normal data packet or a failover data packet will be transmitted on a link.

12. A node as recited in claim 11 wherein the arbitrator is a multiplexer and selection control logic.

13. A method of transmitting data over a network having a plurality of nodes and links when a link has failed, the method comprising:

receiving a data packet at a first node having a failed link, the data packet scheduled to use the failed link;

storing the data packet in a failover buffer when received at the first node and before routing the data packet to a failover storage area;

routing the data packet to the failover storage area;

determining an alternative link for the data packet and routing the data packet to a transmitter associated with the alternative link; and

transmitting the data packet to a receiver for the alternative link in a second node, thereby allowing the data packet to reach an intended destination by effecting the first node at a hardware level and without software intervention.

14. A method of transmitting data over a network having a plurality of nodes and links when a link has failed, the method comprising:

receiving a data packet at a first node having a failed link, the data packet scheduled to use the failed link;

routing the data packet to a failover storage area, wherein said routing the data packet to the failover storage area further comprises routing the data packet to a first data stack or a second data stack;

determining an alternative link for the data packet and routing the data packet to a transmitter associated with the alternative link; and

transmitting the data packet to a receiver for the alternative link in a second node, thereby allowing the data packet to reach an intended destination by effecting the first node at a hardware level and without software intervention.

15. A method as recited in claim 14 further comprising determining whether the data packet is routed to the first data stack or to the second data stack.

16. A method as recited in claim 14 wherein the first data stack receives data packets from receivers and transmitters and the second data stack receives data packets from receivers only.

17. A method as recited in claim 14 further comprising forwarding the data packet form the failover storage area to the selected transmitter for the alternative link.

18. A method as recited in claim 14 further comprising sending out the data packet from the selected transmitter without storing the data packet in a buffer for the selected transmitter.

19. A method of transmitting data over a network having a plurality of nodes and links when a link has failed, the method comprising:

receiving a data packet at a first node having a failed link, the data packet scheduled to use the failed link;

routing the data packet to a failover storage area;

determining an alternative link for the data packet and routing the data packet to a transmitter associated with the alternative link;

transmitting the data packet to a receiver for the alternative link in a second node, thereby allowing the data packet to reach a intended destination by effecting the first node at a hardware level and without software intervention; and

sharing only the alternative link at the first node in order to transmit the data packet to the second node.

20. A method of transmitting data over a network having a plurality of nodes and links when a link has failed, the method comprising:

receiving a data packet at a first node having a failed link, the data packet scheduled to use the failed link;

routing the data packet to a failover storage area;

determining an alternative link for the data packet and routing the data packet to a transmitter associated with the alternative link;

transmitting the data packet to a receiver for the alternative link in a second node, thereby allowing the data packet to reach an intended destination by effecting the first node at a hardware level and without software intervention; and

determining whether the second node is in failover mode after the second node receives the data packet from the first node on the alternative link.

21. A method of transmitting data over a network having a plurality of nodes and links when a link has failed, the method comprising:

detecting a failed link coupled to a first node, wherein the first node comprises a data packet scheduled to be transmitted via the failed link;

in response to detecting the failed link, converting the data packet to a failover data packet at the first node by marking the data packet as a failover packet and recomputing a CRC value;

routing the data packet to a failover storage area;

determining an alternative link for the data packet and routing the data packet to a transmitter associated with the alternative link; and

transmitting the data packet to a receiver in a second node coupled to the alternative link.

22. A system having a plurality of nodes and links, wherein the plurality of nodes are configured to communicate with one another via the plurality of links, the system comprising:

a first node coupled to a plurality of links, wherein the first node is configured to detect a failure in a first link, wherein the first node comprises;

a receiver configured to receive a data packet scheduled to be transmitted via the first link, wherein the data packet is converted to a failover data packet in response to detecting the failure in the first link by making the data packet as a failover packet and recomputing a CRC value,

one or more failover route tables for determining an alternative link to transmit the data packet by using a destination node identifier as an index, and

a failover storage area for storing the data packet and routing the data packet to a transmitter associated with the alternative link; and

a second node coupled to the alternative link and configured to receive the data packet from the transmitter.