Method and system for topology construction and path identification in a routing domain operated according to a link state routing protocol
First Claim
Patent Images
1. A method for constructing topology and routing information in a multi-area routing domain operated according to a link state routing protocol, comprising the steps of:
- acquiring topology and routing information, including route entries, for each area in the routing domain;
identifying, within each area of the routing domain, possible exit points for all route entries known in each area in the routing domain;
for all exit points identified in the identifying step as being associated with a route entry, determining a cost of a path between the exit point and its associated route entry, wherein the route entry is associated with one or more destinations in a remote non-backbone area; and
for all exit points identified in the identifying step, determining other areas, if any, to which said exit points connect.
9 Assignments
0 Petitions
Accused Products
Abstract
A method and system for extracting and building end-to-end route information 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 enables a user, such as a network administrator, to explicitly identify a full set of paths (links and routers) that a given IP packet would potentially traverse from its entry point in the area of the AS where it originates until its exit point in its intended destination or exit area.
-
Citations
16 Claims
-
1. A method for constructing topology and routing information in a multi-area routing domain operated according to a link state routing protocol, comprising the steps of:
-
acquiring topology and routing information, including route entries, for each area in the routing domain; identifying, within each area of the routing domain, possible exit points for all route entries known in each area in the routing domain; for all exit points identified in the identifying step as being associated with a route entry, determining a cost of a path between the exit point and its associated route entry, wherein the route entry is associated with one or more destinations in a remote non-backbone area; and for all exit points identified in the identifying step, determining other areas, if any, to which said exit points connect. - View Dependent Claims (14, 15)
-
-
2. A method for constructing end-to-end paths in a multi-area routing domain operated according to a link state routing protocol, comprising the steps of:
-
acquiring topology and routing information for a routing domain; determining an entry point in an origin area located in the routing domain; retrieving a route entry in the origin area, the route entry being associated with a specified destination in a remote non-backbone area; extracting a set of exit points in the origin area through which the route entry can be reached; for each exit point extracted in the extracting step, determining a total cost of reaching the route entry from the entry point via the exit point; eliminating, from the set of exit points, those exit points that do not correspond to minimum total costs; and identifying paths associated with the exit points through which the route entry is directly reachable, and eliminating those exit points from the set of exit points. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16)
-
Specification