Technique for handling forwarding transients with link state routing protocol

• US 6,597,663 B1
• Filed: 07/26/1999
• Issued: 07/22/2003
• Est. Priority Date: 03/03/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Rekhter, Yakov
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Pezzlo, John
• Application Number:
  US09/360,711
• Time in Patent Office: 1,457 Days
• Field of Search: 370/386, 370/400, 370/469, 370/352-356, 370/248, 370/392, 370/401, 370/238, 370/235-237, 370/252, 370/254-258, 370/389, 370/351, 370/396, 370/408, 370/468, 709/200, 709/238-241, 709/242, 709/220-222, 707/1-10
• US Class Current: 370/252
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

A detection technique detects inconsistencies in forwarding databases of a router and its neighbor, i.e., a next-hop router, during routing transients in a computer network. The technique enables the router to detect when its view of a computed path to a destination station is inconsistent with the view of its neighbor along that path. Upon detecting such an inconsistent state, the router invokes one of a plurality of forwarding mechanisms with respect to a packet intended for the destination station in an attempt to suppress forwarding loops that may arise during the transients.

Claims

1. A method for efficiently detecting an inconsistency in a forwarding database of a router during routing transients in a computer network, the method comprising the steps of:

computing a path and a first hop-count parameter to a destination station (hop-count (D)) at the router;

receiving an update message at the router in response to a change in a second hop-count (D) at a next-hop (NH) neighbor, the update message containing an address of the destination station and the second hop-count (D) associated with that address;

comparing the second hop-count (D) with the first hop-count (D) at the router; and

detecting an inconsistency in the forwarding database of the router if the second hop-count (D) is not less than the first hop-count (D).

2. The method of claim 1 further comprising the step of invoking one of a plurality of forwarding options with respect to a packet received at the router and intended for the destination station to suppress forwarding loops during the routing transients.

3. The method of claim 2 wherein the step of invoking one of the forwarding options comprises the step of discarding the packet.

4. The method of claim 2 wherein the step of invoking one of the forwarding options comprises the steps of:

decrementing one of a time-to-live and lifetime entry of a network layer header of the packet; and

forwarding the packet to the destination station over the computed path.

5. The method of claim 4 further comprising the step of:

discarding the packet if the time-to-live or lifetime entry has expired.

6. The method of claim 2 wherein the step of invoking one of the forwarding options further comprises the step of forwarding the packet to the destination over the computed path if no inconsistencies are found.

7. The method of claim 1 further comprising the steps of:

constructing an augmented forwarding database at the router; and

storing the first hop-count (D) in the augmented forwarding database.

34. A computer readable media, comprising:

said computer readable media containing instructions for execution in a processor for the practice of the method of claim 1 or claim 18).

8. Apparatus for detecting an inconsistency in a view of a path to a destination station of a computer network, the apparatus comprising:

a router coupled to the network, the router having a processing element for processing routing information to compute a path and first hop-count parameter from the router to the destination station;

means, coupled to the router, for executing a control mechanism to determine whether a second hop-count parameter computed by a neighboring router to the destination is less than the first hop-count parameter; and

means, coupled to the router, for invoking a forwarding mechanism with respect to a packet intended for the destination station if the second hop-count parameter is not less than the first hop-count parameter.

9. The apparatus of claim 8 wherein the means for executing the control mechanism further comprises means for comparing the first hop-count parameter with the second hop-count parameter.

10. The apparatus of claim 9 further comprising an augmented forwarding database coupled to the router for storing the first hop-count parameter.

11. The apparatus of claim 10 wherein the means for invoking the forwarding mechanism comprises means for discarding the packet.

12. The apparatus of claim 10 wherein the means for invoking the forwarding mechanism comprises:

means for decrementing one of a time-to-live and lifetime entry of a network layer header of the packet; and

means for forwarding the packet to the destination station over the computed path.

13. A computer readable medium containing executable program instructions for efficiently detecting an inconsistency in a forwarding database of a router during routing transients in a computer network, the executable program instructions comprising program instructions for:

computing a path and a first hop-count parameter to a destination station (hop-count (D)) at the router;

receiving an update message at the router in response to a change in a second hop-count (D) at a next-hop (NH) neighbor, the update message containing an address of the destination station and the second hop-count (D) associated with that address;

comparing the second hop-count (D) with the first hop-count (D) at the router; and

detecting an inconsistency in the forwarding database of the router if the second hop-count (D) is not less than the first hop-count (D).

14. The medium of claim 13 further comprising program instructions for invoking one of a plurality of forwarding options with respect to a packet received at the router and intended for the destination station to suppress forwarding loops during the routing transients.

15. The medium of claim 14 wherein the program instructions for invoking one of the forwarding options comprises program instructions for discarding the packet.

16. The medium of claim 14 wherein the program instructions for invoking one of the forwarding options comprises program instructions for:

decrementing one of a time-to-live and lifetime entry of a network layer header of the packet; and

forwarding the packet to the destination station over the computed path.

17. The medium of claim 13 further comprising program instructions for:

constructing an augmented forwarding database at the router; and

storing the first hop-count (D) in the augmented forwarding database.

18. A method for use in a router having a forwarding database, the method comprising the steps of:

computing a path and a first hop-count to a destination;

receiving a second hop-count to the destination from a next-hop neighbor;

comparing the second hop-count with the first hop-count; and

detecting an inconsistency in the forwarding database if the second hop-count is not less than the first hop-count.

19. The method of claim 18 further comprising:

said step of receiving is during routing transients.

20. The method of claim 19 further comprising the step of:

invoking one of a plurality of forwarding options with respect to a packet received at the router and intended for the destination to suppress forwarding loops during the routing transients.

21. The method of claim 20 wherein the step of invoking one of the forwarding options further comprises the step of discarding the packet.

22. The method of claim 20 wherein the step of invoking one of the forwarding options further comprises the steps of:

decrementing one of a time-to-live and lifetime entry of a network layer header of the packet; and

forwarding the packet to the destination over the computed path.

23. The method of claim 22 further comprising the step of:

discarding the packet if the time-to-live or lifetime entry has expired.

24. The method of claim 20 wherein the step of invoking one of the forwarding options further comprises the step of forwarding the packet to the destination over the computed path if no inconsistencies are found.

25. The method of claim 18 further comprising the steps of:

constructing an augmented forwarding database at the router; and

storing the first hop-count in the augmented forwarding database.

26. A router, comprising:

means for computing a path and a first hop-count to a destination;

means for receiving a second hop-count to the destination from a next-hop neighbor;

means for comparing the second hop-count with the first hop-count; and

means for detecting an inconsistency in the forwarding database if the second hop-count is not less than the first hop-count.

27. A router, comprising:

a processor to compute a path and a first hop-count to a destination;

an input port to receive a second hop-count to the destination from a next-hop neighbor; and

a processor to compare the second hop-count with the first hop-count, and to detect an inconsistency in the forwarding database if the second hop-count is not less than the first hop-count.

28. The router of claim 27 further comprising:

a processor to invoke one of a plurality of forwarding options with respect to a packet received at the router and intended for the destination to suppress forwarding loops during routing transients.

29. The router of claim 28 further comprising:

wherein one of the plurality of forwarding options is discarding the packet.

30. The router of claim 28 further comprising:

an output port to foward the packet; and

wherein one of the plurality of forwarding options is decrementing one of a time-to-live and lifetime entry of a network layer header of the packet, and forwarding the packet to the destination over the computed path.

31. The router of claim 30 further comprising:

wherein one of the plurality of forwarding options is to discard the packet if the time-to-live or lifetime entry has expired.

32. The router of claim 28 further comprising:

an output port to forward the packet to the destination over the computed path if no inconsistencies are found.

33. The router of claim 27 further comprising:

an augmented forwarding database to store the first-hop count.