Hardware based fast convergence for network failures

Patent metadata

Field	Value
Publication number	US-9544185-B1
Application number	US-201314086803-A
Country	US
Kind code	B1
Filing date	Nov 21, 2013
Priority date	Nov 5, 2013
Publication date	Jan 10, 2017
Grant date	Jan 10, 2017

Abstract

Certain features required for routing decisions are provided by hardware. For example, the router logic may be modified to provide multiple alternative paths for a link. In some implementations, hardware autonomously detects a link or port failure and routes on an alternate link without software intervention. In one approach, the router stores the alternate paths in the data plane. In some implementations, network devices are also configured for active loop avoidance and detection is implemented so that packets never loop due to multiple failures that occur close to each other.

First claim

What is claimed is:

1. A network device comprising:
(a) a plurality of interfaces for coupling with network links; and
(b) a processor with hardware logic configured to
determine that a link to one of the plurality of interfaces of the network device is not functioning properly,
look up, in a forwarding table, interfaces of the network device for reaching network addresses, the forwarding table containing, for each of one or more network addresses, a primary interface of the plurality of interfaces and one or more alternate interfaces of the plurality of interfaces, and
upon determining that the primary interface of the network device for reaching a network address is coupled to the link identified as not functioning properly, identify, in the forwarding table, one of the alternate interfaces for reaching the network address.

2. The network device of claim 1 , wherein the processor is an application specific integrated circuit.

3. The network device of claim 1 , where in the processor is a digital signal processor.

4. The network device of claim 1 , further comprising memory on the processor, wherein the memory is configured to store the forwarding table.

5. The network device of claim 4 , where in the memory is content addressable memory.

6. The network device of claim 1 , wherein the hardware logic is further configured to determine whether a packet identified for forwarding on an alternate interface listed in the forwarding table has a reroute flag set, and, if so, dropping said packet.

7. The network device of claim 6 , wherein the hardware logic is further configured to set said reroute flag in the packet when the packet does not have a previously set reroute flag.

8. The network device of claim 1 , wherein the hardware logic is further configured to
instruct the network device to send a packet on said alternate interface;
determine that the packet does not have a reroute flag set; and
set said reroute flag in the packet.

9. The network device of claim 1 , wherein said network device is configured as a spine node on a network having a multi-rooted tree topology.

10. The network device of claim 9 , further comprising program logic configured to encapsulate and de-encapsulate packets sent on an overlay of the network.

11. The network device of claim 10 , further comprising program logic for processing VxLAN encapsulation.

12. The network device of claim 1 , wherein the hardware logic is further configured to reroute a packet, in response to a detected link failure, on an alternate interface within a period of about 1 millisecond or less.

13. The network device of claim 1 , further comprising software configured to (i) maintain an updated graph of a network containing the network device, and (ii) recalculate entries for the forwarding table from said graph.

14. The network device of claim 13 , wherein the software is further configured to send control packets to other network devices, wherein said control packets contain reachability information consistent with one or more failed links on the network device.

15. The network device of claim 13 , wherein the hardware logic is configured to reroute a packet on an alternate interface before the software updates the graph and/or recalculates entries for the forwarding table in response to a detected link failure.

16. The network device of claim 1 , wherein the hardware logic is configured to determine, look up, and identify as recited in claim 1 without any software intervention.

17. The network of claim 1 , wherein a spine network device further comprises software configured to (i) maintain an updated graph of a network containing the network device, and (ii) recalculate entries for the forwarding table from said graph.

18. The network of claim 17 , wherein the software is further configured to send control packets to other network devices, wherein said control packets contain reachability information indicating consistent with one or more failed links.

19. The network of claim 18 , wherein the hardware logic of the spine network device is configured to reroute a packet on an alternate interface before the software updates the graph and/or recalculates entries for the forwarding table in response to a detected link failure.

20. A network comprising a plurality of leaf and spine network devices connected in a multi-rooted tree topology,
wherein each of at least some of the spine network devices comprises:
a plurality of interfaces for coupling with network links; and
a processor with hardware logic configured to
determine that a link to one of the plurality of interfaces is not functioning properly,
look up, in a forwarding table, interfaces for reaching network addresses, the forwarding table containing, for each of one or more network addresses, a primary interface of the plurality of interfaces and one or more alternate interfaces of the plurality of interfaces, and
identify in the forwarding table, one of the alternate interfaces for reaching a network address after the primary interface for said network address coupled to the link is identified as not functioning properly; and

wherein each of the leaf network devices comprise:
a plurality of interfaces for coupling with spine network devices and end devices.

21. The network of claim 20 , wherein the leaf network devices further comprise logic configured to
determine whether a packet is addressed to the leaf network device or to an end device attached to the leaf network device, and
if not, forward the packet to a spine network device that is not the spine network device that sent the packet to the leaf network device.

22. The network of claim 20 , wherein the processor of a spine network device is an application specific integrated circuit.

23. The network of claim 20 , wherein the processor of a spine network device further comprises memory configured to store the forwarding table.

24. The network of claim 23 , where in the memory is content addressable memory.

25. The network of claim 20 , where in the hardware logic of a spine network device is further configured to determine whether a packet identified for forwarding on an alternate interface listed in the forwarding table has a reroute flag set, and, if so, dropping said packet.

26. The network of claim 25 , wherein the hardware logic is further configured to set said reroute flag in the packet when the packet does not have a previously set reroute flag.

27. The network of claim 20 , wherein a spine network device further comprises program logic configured to encapsulate and de-encapsulate packets sent on an overlay of the network.

28. The network of claim 27 , wherein the spine network device further comprises program logic for processing VxLAN encapsulation.

29. A method of rerouting a packet when a link to a network device has failed, the network device comprising a plurality of interfaces for coupling with network links, and a processor with hardware logic, the method comprising:
(a) determining, by the network device, that a link to one of the plurality of interfaces of the network device is not functioning properly,
(b) looking up interfaces for reaching network addresses in a forwarding table containing, for each of one or more network addresses, a primary interface of the plurality of interfaces and one or more alternate interfaces of the pluralit

Assignees

• Insieme Networks Inc
• Cisco Tech Inc

Inventors

• Yadav Navindra
• Pani Ayaskant
• Chu Kit Chiu

Classifications

• H04L45/28

  using route fault recovery · CPC title

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L45/22

  Alternate routing · CPC title

• H04L41/0668 Primary

  by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure · CPC title

• H04L41/0659 Primary

  by isolating or reconfiguring faulty entities · CPC title