Technique for handling forwarding transients with link state routing protocol
AssigneeCisco Technology, Inc.
InventorYakov Rekhter
Life of this patent
Estimating the term…
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.
Claims15
A method for efficiently detecting inconsistencies in forwarding databases of a router and its next-hop (NH) neighbor 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 and computing a second hop-count (D) at the NH neighbor;
- transmitting an update message from the NH neighbor to the router when the second hop-count (D) changes, 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);
- and
- detecting inconsistencies in the forwarding databases of the router and NH neighbor if the second hop-count (D) is not less than the first hop-count (D).
Apparatus for detecting inconsistencies in views of paths 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;
- a neighboring router coupled to the router via the network, the neighboring router having a processing element for processing routing information to compute a path and second hop-count parameter from the neighboring router to the destination;
- means, coupled to the router, for executing a control mechanism to determine whether the second hop-count parameter 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.
A computer readable medium containing executable program instructions for efficiently detecting inconsistencies in forwarding databases of a router and its neighbor 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 and a second hop-count (D) at the neighbor;
- transmitting an update message from the neighbor to the router when the second hop-count (D) changes, 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);
- and
- detecting inconsistencies in the forwarding databases of the router and neighbor if the second hop-count (D) is not less than the first hop-count (D).
Dependencies are inferred from the claim text.