Technique for efficient probing to verify policy conformance

• US 8,072,901 B1
• Filed: 09/29/2005
• Issued: 12/06/2011
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Blair, Dana, Metzger, Larry R.
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): LIU, BEN H
• Application Number:
  US11/239,595
• Time in Patent Office: 2,259 Days
• Field of Search: 370/400, 370/401, 370/402, 370/403, 370/404, 370/405, 370229-240, 370254-258, 370/351
• US Class Current: 370/254
• CPC Class Codes: G01V 1/28 Processing seismic data, e.g. for interpretation or for event detection G01V1/48 takes precedence
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0866 Checking the configuration
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 65/1101 Session protocols

Abstract

A technique efficiently sends probe packets from a source to a target in a destination prefix over two or more paths of a computer network. According to the novel technique, the source, e.g., configured for optimized edge routing (OER), sends probe packets (probes) over all available paths (exits) to the target in the destination prefix in order to select a preferred path based on received responses to the probes, e.g., according to one or more policies. Once the preferred path is selected, the source sends probes to that target only over the preferred path until a trigger occurs, such as, e.g., an out of policy (OOP) event, a policy change, or an optional timer-based trigger. Upon being triggered, the source again probes all paths to reselect the preferred path.

Claims

1. A method for efficiently sending probe packets from a source in a first autonomous system to a destination prefix in a second autonomous system over two or more paths, the method comprising:

sending probe packets from the source in the first autonomous system to the destination prefix in the second autonomous system over each of the two or more paths that use different border routers of the first autonomous system to reach the destination prefix in the second autonomous system;

selecting a preferred path to the destination prefix out of the two or more paths based on received responses to the probe packets;

in response to the selecting a preferred path, sending probe packets from the source to the destination prefix only over the preferred path for a period of time until a trigger occurs;

determining that the trigger has occurred; and

in response to the trigger, again sending probe packets from the source to the destination prefix over each of the two or more paths.

2. The method as in claim 1, further comprising:

after again sending probe packets from the source in the first autonomous system to the destination prefix in the second autonomous system over each of the two or more paths, repeating the steps of selecting the preferred path, and sending probe packets over the preferred path.

3. The method as in claim 1, further comprising:

determining that the trigger has occurred based on an event selected from the group consisting of;

an out of policy (OOP) event, a policy change, and expiration of a timer.

4. The method as in claim 1, further comprising:

selecting the preferred path to the destination prefix in the second autonomous system out of the two or more paths based on received responses to the probe packets according to one or more policies.

5. The method as in claim 1, further comprising:

sending the probe packets to one or more targets within the destination prefix in the second autonomous system.

6. The method as in claim 1, further comprising:

selecting a plurality of preferred paths; and

sending probe packets from the source in the first autonomous system to the destination prefix in the second autonomous system only over the plurality of preferred paths.

7. The method as in claim 1, wherein the two or more paths from the source in the first autonomous system to the destination prefix in the second autonomous system are a selected subset of all available paths from the source to the destination.

8. The method as in claim 1, wherein the source in the first autonomous system is configured for Optimized Edge Routing (OER).

9. An apparatus for efficiently sending probe packets from a source in a first autonomous system to a destination prefix in a second autonomous system over two or more paths, the apparatus comprising:

means for sending probe packets from the source in the first autonomous system to the destination prefix in the second autonomous system over each of the two or more paths that use different border routers of the first autonomous system to reach the destination prefix in the second autonomous system;

means for selecting a preferred path to the destination prefix out of the two or more paths based on received responses to the probe packets;

means for sending probe packets from the source to the destination prefix only over the preferred path in response to selection of the preferred path for a period of time until a trigger occurs;

means for determining that the trigger has occurred; and

means for again sending probe packets from the source to the destination prefix over each of the two or more paths in response to the trigger.

10. A computer readable medium containing executable program instructions for efficiently sending probe packets from a source in a first autonomous system to a destination prefix in a second autonomous system over two or more paths, the executable program instructions comprising program instructions for:

sending probe packets from the source in the first autonomous system to the destination prefix in the second autonomous system over each of the two or more paths that use different border routers of the first autonomous system to reach the destination prefix in the second autonomous system;

selecting a preferred path to the destination prefix out of the two or more paths based on received responses to the probe packets;

in response to the selecting a preferred path, sending probe packets from the source to the destination prefix only over the preferred path for a period of time until a trigger occurs;

determining that the trigger has occurred; and

in response to the trigger, again sending probe packets from the source to the destination prefix over each of the two or more paths.

11. The computer readable medium as in claim 10, the executable program instructions further comprising program instructions for:

after again sending probe packets from the source to the destination prefix over each of the two or more paths, repeating the steps of selecting the preferred path, and sending probe packets over the preferred path.

12. A system for efficiently sending probe packets over two or more paths, the system comprising:

a source in a first autonomous system configured to send probe packets over each of the two or more paths that use different border routers of the first autonomous system; and

a destination prefix in a second autonomous system configured to receive the probe packets over the two or more paths and to return responses to the probe packets over the two or more paths;

wherein the source in the first autonomous system is further configured to select a preferred path to the destination prefix in the second autonomous system out of the two or more paths based on received responses to the probe packets, in response to selection of the preferred path, send probe packets to the destination prefix only over the preferred path for a period of time until a trigger occurs, determine that the trigger has occurred, and in response to the trigger, again send probe packets from the source to the destination prefix over each of the two or more paths.

13. The system as in claim 12, wherein the source in the first autonomous system is further configured to, after again sending probe packets to the destination prefix over each of the two or more paths, select the preferred path, and send probe packets over only the preferred path.

14. A source node in a first autonomous system for efficiently sending probe packets to a destination prefix in a second autonomous system over two or more paths, the node comprising:

one or more network interfaces to send probe packets to the destination prefix in the second autonomous system over the two or more paths that use different border routers of the first autonomous system to reach the destination prefix in the second autonomous system;

a processor coupled to the one or more network interfaces and adapted to execute software processes; and

a memory adapted to store an Optimized Edge Routing (OER) process executable by the processor, the OER process configured to i) send probe packets to the destination prefix in the second autonomous system over each of the two or more paths, ii) select a preferred path to the destination prefix out of the two or more paths based on received responses to the probe packets, iii) in response to selection of the preferred path, send probe packets from the source in the first autonomous system to the destination prefix in the second autonomous system only over the preferred path for a period of time until a trigger occurs, iv) determine that the trigger has occurred, and v) in response to the trigger, again send probe packets from the source to the destination prefix over each of the two or more paths.

15. The node as in claim 14, wherein the OER process is further configured to, after again sending probe packets from the source to the destination prefix over each of the two or more paths, select the preferred path, and send probe packets only over the preferred path.

16. A method comprising:

sending probe packets from a source node in a first autonomous system to a destination prefix in a second autonomous system over each of two or more available paths that use different border routers of the first autonomous system to reach the destination prefix in the second autonomous system;

selecting a preferred path to the destination prefix out of the two or more available paths based on received responses to the probe packets;

once the preferred path is selected, entering a steady state, and during the steady state sending probe packets from the source to the destination prefix only over the preferred path, and not over other available paths to the destination prefix;

subsequently, determining that a trigger has occurred; and

in response to the trigger, again sending probe packets from the source to the destination prefix over each of the two or more available paths to the destination prefix in the second autonomous system.

17. The method of claim 16 wherein the preferred path is selected according to a particular policy and the trigger is occurrence of an out of policy (OOP) event where the preferred path no longer satisfies the particular policy.

18. The method of claim 16 wherein the preferred path is selected according to a particular policy and the trigger is occurrence of a change in the particular policy.

19. The method of claim 16 wherein the trigger is expiration of a timer.

20. A method comprising:

sending probe packets from a source in a first autonomous system to a destination prefix in a second autonomous system over each of the two or more paths to reach the destination prefix in the second autonomous system;

based on received responses to the probe packets, selecting a preferred path to the destination prefix that satisfies a particular policy from among the two or more paths;

once the preferred path has been selected, no longer sending probe packets over each of the two or more paths, and instead sending probe packets from the source to the destination prefix only over the preferred path;

subsequently, determining that the preferred path no longer satisfies the particular policy; and

in response to determining that the preferred path no longer satisfies the particular policy, no longer sending probe packets from the source to the is destination prefix only over the preferred path, and instead sending probe packets from the source to the destination prefix over each of the two or more paths.

21. A method comprising:

sending probe packets from a source in a first autonomous system to a destination prefix in a second autonomous system over each of the two or more paths to reach the destination prefix in the second autonomous system;

selecting a preferred path to the destination prefix out of the two or more paths based on received responses to the probe packets;

once the preferred path has been selected, no longer sending probe packets over each of the two or more paths, and instead sending probe packets from the source to the destination prefix only over the preferred path;

subsequently, determining that a timer has expired; and

in response to timer having expired, no longer sending probe packets from the source to the destination prefix only over the preferred path, and instead sending probe packets from the source to the destination prefix over each of the two or more paths.