Methods, apparatuses and systems facilitating determination of network path metrics

• US 20030204619A1
• Filed: 04/26/2002
• Published: 10/30/2003
• Est. Priority Date: 04/26/2002
• Status: Active Grant

• Current Assignee: Transaction Network Services Incorporated (Trident Private Holdings I LLC)
• Original Assignee: Transaction Network Services Incorporated (Trident Private Holdings I LLC)
• Inventors: Bays, Robert James
• Granted Patent: US 7,260,645 B2
• Time in Patent Office: Days
• US Class Current: 709/238
• CPC Class Codes: H04L 41/0253 using browsers or web-pages for accessing management information
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 41/0803 Configuration setting
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• 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/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/26 : Route discovery packet
• CPC Class Codes: H04L 45/34 : Source routing
• CPC Class Codes: H04L 47/10 : Flow control; Congestion control
• CPC Class Codes: H04L 47/115 : using a dedicated packet
• CPC Class Codes: H04L 47/20 : Traffic policing
• CPC Class Codes: H04L 47/286 : Time to live
• CPC Class Codes: H04L 47/32 : by discarding or delaying data units, e.g. packets or frames

Abstract

Methods, apparatuses and systems relating to the control and application of policies for routing data over a computer network, such as the Internet. Some implementations of the invention facilitate the configuration, deployment and/or maintenance of network routing policies. Some implementations of the invention are particularly useful for controlling the routing of data among autonomous systems or organizations. Certain implementations allow for dynamic modification of routing policy based on such factors as current Internet performance, load sharing, user-defined parameters, and time of day. In one embodiment, the present invention provides methods, apparatuses and systems implementing enhanced network path testing methodologies that enhance the efficiency of processes associated with testing of a network path, while reducing the perceived intrusiveness of test packets associated with such metrics tests.

Claims

1. A method facilitating the testing of a path to a destination network, the path including at least one intermediate system between a source network and the destination network, wherein the at least one intermediate system supports a communications protocol allowing for hop-limited packets and the transmission of error messages in response to expired, hop-limited packets, the method comprising

identifying a target intermediate system in a path to a destination network;

and

testing the path in relation to at least one metric using at least one hop-limited test packet, wherein the at least one hop-limited test packet is addressed to the destination network, but configured to expire at the target intermediate system in the path.

2. The method of claim 1 wherein the destination network includes a broadcast address, and wherein the at least one hop-limited test packet is transmitted to the broadcast address of the destination network.

3. The method of claim 1 wherein the target intermediate system is the last intermediate system in the path.

4. The method of claim 1 wherein the identifying step comprises

probing a path by transmitting a series of hop-limited probe packets to the destination network until detection of an event indicating the end of the path has been reached, said probe packets in the series configured to expire at an intermediate system in the path after a successively increasing number of hops;

recording the computer network address of the responding intermediate system(s) in association with the number of hops associated with the probe packet(s) triggering the response(s); and

selecting the intermediate system associated with the largest number of hops.

5. The method of claim 1 wherein the testing steps comprises

transmitting the at least one hop-limited test packet;

examining the response to detect a change in the configuration of the path; and

repeating the identifying the target intermediate system step for the path, if a change is detected.

6. The method of claim 5 wherein the examining step comprises

comparing the computer network address of the identified target intermediate system to the computer network address corresponding to the source of the response.

7. The method of claim 5 wherein the examining step comprises

verifying that the response indicates that the at least one hop-limited test packet expired at the target intermediate system.

8. The method of claim 5 wherein the identifying the target intermediate system step for the path is repeated, if no response is received within a threshold period of time.

9. The method of claim 1 wherein the identifying step comprises

transmitting at least one hop-limited probe packet to the broadcast address of the destination network, wherein the at least one hop-limited probe packet is configured to expire at the first intermediate system in the path;

monitoring for a response to said at least one hop-limited probe packet;

if a response is received, storing the computer network address of the intermediate system sourcing the response in association with a corresponding hopcount value;

repeating the transmitting, monitoring and conditional storing steps for subsequent intermediate systems in the path until detection of an event indicative of having reached the last intermediate system in the path; and

selecting the intermediate system associated with the largest hopcount.

10. The method of claim 9 wherein the event comprises the expiration of a threshold period of time after the transmitting step before a response is received to at least one of the at least one hop-limited probe packets.

11. The method of claim 9 wherein the event comprises the expiration of a threshold period of time after the transmitting step before a response is received to at least one of the at least one hop-limited probe packets, or the receipt of a response to a hop-limited probe packet indicating that the destination is unreachable.

12. The method of claim 9 wherein the selecting step comprises

removing duplicate computer network addresses stored in the storing step, wherein duplicate computer network addresses associated with the larger hopcounts are removed;

and

selecting the intermediate system associated with the largest hopcount.

13. The method of claim 12 further comprising

if the response received from the selected intermediate system does not allow for an explicit determination that the end of the path has been reached, then validating the selected intermediate system with reference to route information obtained from autonomous systems in the computer network.

14. The method of claim 13 wherein the validating step comprises

accessing a routing system to look up route information associated with the destination network corresponding to the broadcast address and to identify the last and second-to-last autonomous systems in the route to the destination network;

accessing the routing system to look up route information associated with the computer network address of the selected intermediate system and to identify the last autonomous system in the route to the selected intermediate system; and

verifying that the last autonomous system in the route to the selected intermediate system matches either the last or second-to-last autonomous system in the route to the destination network.

15. A method allowing for non-obtrusive testing of a path to a destination network in a packet communications environment employing the IP protocol, the path including at least one intermediate system between a source network and the destination network, the method comprising

identifying a target intermediate system in a path to a destination network and the number of hops to the target intermediate system;

and

testing the path in relation to at least one metric using at least one hop-limited test packet, wherein the at least one hop-limited test packet is addressed to the destination network, and wherein the Time-to-Live (TTL) value in the header of the at least one hop-limited test packet is set to the number of hops to the target intermediate system.

16. The method of claim 15 herein the at least one hop-limited test packet is transmitted to the broadcast address of the destination network.

17. The method of claim 15 herein the target intermediate system is the last intermediate system in the path.

18. The method of claim 15 herein the identifying step comprises

probing a path by transmitting a series of hop-limited probe packets to the destination network until detection of an event indicating the end of the path has been reached, said probe packets in the series having successively increasing TTL values;

recording the computer network address of the responding intermediate system(s) in association with the initial TTL value associated with the probe packet(s) triggering the response(s);

selecting the intermediate system associated with the largest TTL value.

19. The method of claim 15 wherein the identifying step comprises transmitting at least one hop-limited probe packet to the broadcast address of the destination network, wherein the at least one hop-limited probe packet has a TTL value of one;

monitoring for a response to said at least one hop-limited probe packet;

if a response is received, storing the computer network address of the intermediate system sourcing the response in association with the corresponding TTL value;

incrementing the TTL value used in subsequent hop-limited probe packets;

repeating the transmitting, monitoring, incrementing, and conditional storing steps until detection of an event indicative of having reached the last intermediate system in the path; and

selecting the intermediate system associated with the largest TTL value.

20. The method of claim 19 wherein the event comprises the expiration of a threshold period of time after the transmitting step before a response is received to at least one of the at least one hop-limited probe packets.

21. The method of claim 19 wherein the event comprises the expiration of a threshold period of time after the transmitting step before a response is received to at least one of the at least one hop-limited probe packets, or the receipt of a response to a hop-limited probe packet indicating that the destination is unreachable.

22. The method of claim 19 wherein the selecting step comprises

removing duplicate computer network addresses stored in the storing step, wherein duplicate computer network addresses associated with the larger TTL values are removed;

and

selecting the intermediate system associated with the largest TTL value.

23. The method of claim 22 further comprising

if the response received from the selected intermediate system is not a host unreachable error response, then validating the selected intermediate system with reference to route information obtained from autonomous systems in the computer network.

24. The method of claim 23 wherein the validating step comprises

accessing a routing system to look up route information associated with the destination network corresponding to the broadcast address and to identify the last and second-to-last autonomous systems in the route to the destination network;

accessing the routing system to look up route information associated with the computer network address of the selected intermediate system and to identify the last autonomous system in the route to the selected intermediate system; and

verifying that the last autonomous system in the route to the selected intermediate system matches either the last or second-to-last autonomous system in the route to the destination network.

25. A method facilitating the testing of paths to destination networks in relation to at least one metric, each destination network associated with at least one path, comprising

segregating a plurality of destination networks into at least two groups;

interleaving, based on the groups created in the segregating step, the injection and testing of paths associated with the plurality of destination networks.

26. A method facilitating the testing of paths to destination networks in relation to at least one metric, each destination network associated with at least one path, comprising

(a) segregating a plurality of destination networks into at least two groups;

(b) injecting a set of routes associated with corresponding destination networks in a first group of the at least two groups into a routing domain;

(c) injecting a set of routes associated with corresponding destination networks in the next group of the at least two groups into the routing domain;

(d) testing the set of previously injected routes associated with the preceding group in relation to at least one metric; and

,

(e) repeating the injecting and testing steps (c) and (d), cycling through the at least two groups, until all paths associated with the plurality of destination networks have been tested.

27. The method of claim 26 wherein the routes are host routes to the respective broadcast addresses associated with the destination networks.

28. The method of claim 26 wherein the number of groups is determined by dividing the number of desired destination networks by the number of available testing resources.

29. The method of claim 26 further comprising

as to each path, identifying a target intermediate system;

and wherein the testing step comprises;

transmitting, as to each route, at least one hop-limited test packet, wherein the at least one hop-limited test packet is addressed to the destination network, but configured to expire at the target intermediate system in the route.