Method and system for path change root-cause identification in packet networks
A method and system for identifying the root-cause event that affected a path change in a multi-area Internet protocol (IP) autonomous system (AS) operated according to a link state routing protocol such as the Open Shortest Path First (OSPF) protocol is disclosed. The method and system may enable a user, such as a network administrator, to explicitly identify which routing protocol events are responsible for changes to paths that are being monitored.
1. A method for identifying a root-cause event responsible for a change to a path within a multi-area routing domain, comprising:
receiving information corresponding to a first network event that may affect a path for one or more packets traveling in a multi-area routing domain;
maintaining a set of current candidate exit points for the path out of a first area;
determining whether the first network event is a shortest path event or an exit point event;
if the first network event is an exit point event, determining whether a set of taken exit points associated with the path has changed in response to the event; and
if the first network event is a shortest path event, determining whether the network event has changed either the set of taken exit points or a shortest path associated with at least one of the taken exit points.
2. The method of claim 1 wherein a node in the first area is identified as a candidate exit point for a path in the area and towards a destination address if the node advertises a longest matching route for the address in the area.
3. The method of claim 1 wherein a node in the first area is identified as a taken exit point for a path in the area and towards a destination address if the node is a candidate exit point and is the actual exit point from the area on a minimum total cost path used to reach the destination address.
4. The method of claim 1 wherein the network event is identified as the root-cause for a path change if either of the determining steps identifies the network event as having affected the set of taken exit points or their shortest paths.
5. The method of claim 1 wherein the step of determining whether the network event is a shortest path event or an exit point event comprises:
establishing if the first network event may affect any shortest path of any exit point in the set of current candidate exit points;
recomputing the shortest paths that may have been affected by the network event;
comparing the recomputed shortest paths to the original shortest paths to determine whether any shortest paths have changed; and
determining if the set of exit points taken by the path to exit the area has changed.
6. The method of claim 5 wherein the establishing step comprises:
classifying the shortest path event in one of at least four categories;
if the network event is classified in a first category, further checking if the network event affected a link of a shortest path to a candidate exit point, and recomputing the shortest path if it did;
if the network event is classified in a second category, further checking if the network event affected a link of a shortest path to a candidate exit point, and recomputing the shortest path if it did not;
if the network event is classified in a third category, recomputing the shortest paths of all candidate exit points in the set of candidate exit points; and
if the network event is classified in a fourth category, further checking if the shortest path event affected a link or a node of a shortest path to a candidate exit point, and recomputing the shortest path if it did.
7. The method of claim 6 wherein a network event is classified in the first category if it corresponds to an increase in the cost of a link in the area.
8. The method of claim 6 wherein a network event is classified in the second category if it corresponds to a decrease in the cost of a link in the area.
9. The method of claim 6 wherein a network event is classified in the third category if it corresponds to a link coming up in the area.
10. The method of claim 6 wherein a network event is classified in the fourth category if it corresponds to a link going down in the area.
11. The method of claim 5 wherein the determining step comprises:
extracting a set of chosen exit points from the set of candidate exit points;
determining if the set of chosen exit points has changed;
if the set of chosen exit points has not changed, identifying if the shortest paths of the chosen exit points have changed;
if either the set of chosen exit points or their shortest paths have changed, identifying the set of taken exit points used by the path to exit the area; and
if the set of taken exit points used by the path to exit the area or their shortest paths have changed identifying the shortest path event as the root-cause for a path change.
12. The method of claim 11 wherein the step of extracting the set of chosen exit points from the set of candidate exit points comprises:
computing for each candidate exit point a total cost to the destination by adding the cost of the shortest path to the candidate exit point to the cost from the candidate exit point to the destination;
identifying the candidate exit points that correspond to the minimum total cost to the destination; and
selecting as chosen exit points candidate exit points that have a minimum total cost to the destination.
13. The method of claim 5 wherein the determining step comprises:
determining if the exit point event is a change of cost for reaching the destination through one of the candidate exit points that affects the selection of taken exit points for the area; and
identifying if the exit point event corresponds to the advertisement of a best matching route that affects the selection of taken exit points from the area.
14. The method of claim 13 wherein the determining step comprises:
determining if the exit point event is a cost decrease on a chosen exit point or a cost increase on a non-chosen exit point;
if the exit point event is neither a cost decrease on a chosen exit point nor a cost increase on a non-chosen exit point, updating the total cost of the paths to the destination through the candidate exit points affected by the exit point event;
identifying the set of chosen exit points;
if the set of chosen exit points have changed, identifying the set of taken exit points and their shortest paths; and
examining if the set of taken exit points or their shortest paths have changed.
15. The method of claim 13 wherein the identifying step comprises:
deciding if the exit point event is a best matching route for the destination address;
updating the set of candidate exit points based on the best matching route for the destination address;
determining if the set of candidate exit points have changed;
if the set of candidate exit points has changed, computing shortest paths to the new candidate exit points and selecting chosen exit points;
determining if the set of chosen exit points has changed or if new candidate exit points belong to the shortest paths of chosen exit points;
identifying taking exit points and their shortest paths; and
examining if the set of taken exit points or their shortest paths have changed.
16. The method of claim 1 further comprising identifying the first network event as a root-cause for a path change if method identifies the network event as having affected either the set of taken exit points or their shortest paths.