Technique for handling forwarding transients with link state routing protocol
First Claim
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).
0 Assignments
0 Petitions
Accused Products
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.
150 Citations
34 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). - View Dependent Claims (2, 3, 4, 5, 6, 7, 34)
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. - View Dependent Claims (9, 10, 11, 12)
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). - View Dependent Claims (14, 15, 16, 17)
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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25)
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. - View Dependent Claims (28, 29, 30, 31, 32, 33)
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.
Specification