Lesser disruptive open shortest path first handling of bidirectional forwarding detection state changes

• US 7,961,601 B2
• Filed: 08/16/2007
• Issued: 06/14/2011
• Est. Priority Date: 08/16/2007
• Status: Active Grant

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Inventors: Lu, Wenhu, Kini, Sriganesh
• Primary Examiner(s): LY, ANH VU H
• Application Number:
  US11/894,249
• Publication Number:
  US 20090046579A1
• Time in Patent Office: 1,398 Days
• Field of Search: None
• US Class Current: 370/225
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/028 Dynamic adaptation of the update intervals, e.g. event-triggered updates
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A method and apparatus for processing link down events associated with links between adjacent nodes is described. A node receives link down events associated with a link fault protocol for a link between the node and a neighboring node. In response to receiving the link down event, the node removes a data structure associated with the neighboring node from a forwarding table associated with a routing protocol running on the node. The node reserves the data structure for speedy adjacency recovery. In addition, the node places the neighboring node in the initialize state of the routing protocol.

Claims

1. A computerized method comprising:

receiving a link down event associated with a link fault protocol for a link between a first node and a neighboring node;

removing a data structure associated with the neighboring node from a forwarding table with a routing protocol running on the first node, in response to receiving the link down event;

reserving the data structure for adjacency recovery;

placing the neighboring node in the initialize state of the routing protocol;

resetting a penalty decay timer;

increasing a penalty associated with the penalty decay timer; and

triggering a kill neighbor event of the routing protocol for the first node that places the neighboring node in the down state if the penalty exceeds a threshold.

2. The computerized method of claim 1, further comprising:

notifying other nodes of the link down; and

withdrawing a set of affected routes from the forwarding table.

3. The computerized method of claim 1, further comprising:

receiving a link up event associated with the link fault protocol;

adding the data structure to the forwarding table; and

placing the neighboring node in the up state of the routing protocol.

4. The computerized method of claim 3, further comprising:

sending a hello message to the neighboring node.

5. The computerized method of claim 3, further comprising:

electing a dominant router for the routing protocol;

notifying other routers of the link up; and

reinstalling the set of affected routes.

6. The computerized method of claim 1, further comprising:

triggering a one-way event of the routing protocol for the first node that places the neighboring node in the initialize state of the routing protocol if the penalty is less than or equal to a threshold.

7. The computerized method of claim 1, wherein the link fault protocol is bidirectional forwarding detection protocol.

8. The computerized method of claim 1, wherein the routing protocol is one of open shortest path first (OSPF) and intermediate system to intermediate system (IS-IS).

9. A non-transitory tangible machine-readable storage medium that stores computer executable instructions, which when executed by a set of one or more processors, cause said set of processors to perform operations comprising:

receiving a link down event associated with a link fault protocol for a link between a first node and a neighboring node;

removing a data structure associated with the neighboring node from a forwarding table with a routing protocol running on the first node, in response to receiving the link down event;

reserving the data structure for adjacency recovery;

placing the neighboring node in the initialize state of the routing protocol;

resetting a penalty decay timer;

increasing a penalty associated with the penalty decay timer; and

triggering a kill neighbor event of the routing protocol for the first node that places the neighboring node in the down state if the penalty exceeds a threshold.

10. The non-transitory tangible machine-readable storage medium of claim 9, further comprising:

notifying other nodes of the link down; and

withdrawing a set of affected routes from the forwarding table.

11. The non-transitory tangible machine-readable storage medium of claim 9, further comprising:

receiving a link up event associated with the link fault protocol;

adding the data structure to the forwarding table; and

placing the neighboring node in the up state of the routing protocol.

12. The non-transitory tangible machine-readable storage medium of claim 11, further comprising:

sending a hello message to the neighboring node.

13. The non-transitory tangible machine-readable storage medium of claim 11, further comprising:

electing a dominant router for the routing protocol;

notifying other routers of the link up; and

reinstalling the set of affected routes.

14. The non-transitory tangible machine-readable storage medium of claim 9, further comprising:

triggering a one-way event of the routing protocol for the first node that places the neighboring node in the initialize state of the routing protocol if the penalty is less than or equal to a threshold.

15. The non-transitory tangible machine-readable storage medium of claim 9, wherein the link fault protocol is bidirectional forwarding detection protocol.

16. The non-transitory tangible machine-readable storage medium of claim 9, wherein the routing protocol is one of open shortest path first (OSPF) and intermediate system to intermediate system (IS-IS).

17. An apparatus comprising:

a link state change module to generate a link down event; and

a routing table module to receive the link down event associated with a link fault protocol for a link between a first node and a neighboring node, remove a data structure associated with the neighboring node from a forwarding table with a routing protocol running on the first node, in response to receiving the link down event, reserve the data structure for adjacency recovery, place the neighboring node in the initialize state of the routing protocol, a timer module to reset a penalty decay timer and increase a penalty associated with the penalty decay timer, and wherein the routing table module triggers a kill neighbor event of the routing protocol for the first node that places the neighboring node in the down state if the penalty exceeds a threshold.

18. The apparatus of claim 17, wherein the routing table module notifies other nodes of the link down and withdraws a set of affected routes from the forwarding table.

19. The apparatus of claim 17, wherein the link state change module generates a link up event associated with the link fault protocol, and the routing table module receives the link up event associated with the link fault protocol, adds the data structure to the forwarding table, and places the neighboring node in the up state of the routing protocol.

20. The apparatus of claim 17, wherein the routing table module triggers a one-way event of the routing protocol for the first node that places the neighboring node in the initialize state of the routing protocol if the penalty is less than or equal to a threshold.

21. A network element comprising:

a set of one or more line cards, wherein each line card is configured to,

receive a link down event associated with a link fault protocol for a link between a first node and a neighboring node,

remove a data structure associated with the neighboring node from a forwarding table with a routing protocol running on the first node, in response to receiving the link down event,

reserve the data structure for adjacency recovery, and

place the neighboring node in the initialize state of the routing protocol;

a set of one or more control cards, the control cards to control forwarding of packets between the set of one or more line cards;

wherein the each line card is configured to reset a penalty decay timer and increase a penalty associated with the penalty decay timer; and

wherein the each line card is configured to trigger a kill neighbor event of the routing protocol for the first node that places the neighboring node in the down state if the penalty exceeds a threshold.

22. The network element of claim 21, wherein the each line card is configured to notify other nodes of the link down and withdraw a set of affected routes from the forwarding table.

23. The network element of claim 21, wherein the each line card is configured to receive a link up event associated with the link fault protocol, add the data structure to the forwarding table, and place the neighboring node in the up state of the routing protocol.

24. The network element of claim 21, wherein the each line card is configured to trigger a one-way event of the routing protocol for the first node that places the neighboring node in the initialize state of the routing protocol if the penalty is less than or equal to a threshold.