Intelligent dynamic route selection based on active probing of network operational characteristics

• US 20020165957A1
• Filed: 10/02/2001
• Published: 11/07/2002
• Est. Priority Date: 05/02/2001
• Status: Abandoned Application

• Current Assignee: Estreet Venture Fund I, LLC
• Original Assignee: Estreet Venture Fund I, LLC
• Inventors: Devoe, Jiva Gandhara, Estes, Nicholas Michael, Jacobson, Jay D.
• Application Number:
  US09/970,398
• Publication Number:
  US 20020165957A1
• Time in Patent Office: Days
• US Class Current: 709/224
• 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/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

A method for building a network route map is described in which network operational characteristics are gathered by actively probing multiple network routes, and building the network route map based on the operational characteristics. Route maps are generated which provide a view of the network from the perspective of a particular routing device in the network. Embodiments include methods for gathering the operational data by transmitting one or more data packets, receiving responses thereto, and determining time differentials based on the responses. Other embodiments include methods for processing the operational data to determine various metrics, and normalizing the data with similar data gathered from other network route probes. Finally, additional embodiments include propagation of the preferred route information to multiple routing devices to provide intelligent route selection thereto.

Claims

1. A method for building a network route map, the method comprising the steps of:

actively probing a plurality of network routes to gather one or more network operational characteristics; and

building the network route map based on the operational characteristics that were gathered by actively probing.

2. The method of claim 1 wherein the step of building the network route map comprises the step of:

determining from the one or more operational characteristics a metric related to lost data packets for each of one or more hops between network devices on the plurality of network routes; and

building the network route map based, at least in part, on the metric.

3. The method of claim 2 wherein the step of determining the metric comprises the step of:

transmitting a data packet from a source to a host address, wherein the metric is determined based on absence of an acknowledgement in response to the data packet from one or more of the network devices.

4. The method of claim 1 wherein the step of building the network route map comprises the step of:

determining from the one or more operational characteristics a metric related to operational latency for each of one or more hops between network devices on the plurality of network routes; and

building the network route map based, at least in part, on the metric.

5. The method of claim 4 wherein the step of determining the metric comprises the step of:

transmitting a data packet from a source to a host address;

receiving a response to the data packet from each of the network devices between the source and a destination device at the host address and including the destination device; and

determining a time differential between the step of transmitting the data packet and the step of receiving each of the responses;

wherein the metric is determined based on the time differential.

6. The method of claim 5 wherein the step of transmitting the data packet from the source includes transmitting the data packet including a time to live value and wherein the step of receiving the response is according to a reaction to the data packet.

7. The method of claim 5 wherein the step of transmitting the data packet from the source includes transmitting the data packet to a port number that does not identify a port on which the destination device is listening, and wherein the step of receiving the response is according to a reaction to the data packet.

8. The method of claim 1 wherein the step of building the network route map comprises the step of:

determining from the one or more operational characteristics a metric related to a number of hops from a source to a host address for the plurality of network routes; and

building the network route map based, at least in part, on the metric.

9. The method of claim 8 wherein the step of determining the metric comprises the step of:

transmitting a data packet from a source to the host address;

receiving a response to the data packet from each of the network devices between the source and a destination device at the host address and including the destination device; and

determining a time differential between the step of transmitting the data packet and the step of receiving each of the responses;

wherein the metric is determined based on the time differential.

10. The method of claim 9 wherein the step of transmitting the data packet from the source includes transmitting the data packet including a time to live value and wherein the step of receiving the response is according to a reaction to the data packet.

11. The method of claim 9 wherein the step of transmitting the data packet from the source includes transmitting the data packet to a port number that does not identify a port on which the destination device is listening, and wherein the step of receiving the response is according to a reaction to the data packet.

12. The method claim 1 wherein the step of building the network route map comprises the step of:

determining from the one or more operational characteristics one or more metrics from a set consisting of network access point congestion, circuit congestion, and network route reliability; and

building the network route map based, at least in part, on the metrics.

13. The method of claim 12 wherein the step of determining one or more metrics comprises the step of:

transmitting a data packet from a source to a host address, wherein the metric is determined based on absence of an acknowledgement in response to the data packet from one or more network devices on the network route between the source and the host address and including a destination device at the host address.

14. The method claim 1 wherein the step of building the network route map comprises the step of:

determining from the one or more operational characteristics one or more metrics from a set consisting of throughput, historical reliability, maximum circuit capacity, and TCP/IP characteristics; and

building the network route map based, at least in part, on the metrics.

15. The method of claim 1 wherein the step of building the network route map comprises normalizing data representing the one or more of the operational characteristics among a plurality of network routes.

16. The method of claim 15 wherein the step of building the network route map comprises the step of:

applying weighting factors to each of the normalized data and summing the weighted normalized data to determine a route score for one or more of the plurality of network routes; and

wherein the network route map is based on the route scores.

17. The method of claim 1 further comprising the step of:

transmitting data representing the operational characteristics to a processor over a network;

wherein the step of building the network route map is performed by the processor.

18. The method of claim 17 further comprising the steps of:

receiving the network route map from the processor;

configuring a next-hop gateway according to the network route map;

creating a translated representation of the network route map; and

propagating the one or more translated representations of the network route map to one or more peer network devices over the network.

19. The method of claim 1 further comprising the step of:

propagating the network route map to one or more network routing devices.

20. The method of claim 1 further comprising the step of:

injecting the network route map into a network routing device on an ongoing basis.

21. The method of claim 20 wherein the step of injecting the network route map comprises the steps of:

configuring the routing device as a Border Gateway Protocol peer; and

advertising the network route map on an ongoing basis.

22. The method of claim 1 wherein the step of building the network route map comprises building the network route map for a particular routing device and from the perspective of the routing device.

23. The method of claim 1 wherein the step of building the network route map comprises building the network route map for a particular routing device and from the perspective of a network of which the routing device is constituent.

24. The method of claim 1

wherein the step of actively probing comprises:

actively y probing a plurality of network routes in which a particular routing device is constituent, whereby the routing device is actively probed from multiple perspectives; and

wherein the step of building the network route map comprises;

consolidating network operational characteristics from the multiple perspectives associated with the particular routing device.

25. The method of claim 1 wherein the step of actively probing is performed by a plurality of probe devices located at different locations on the network.

26. The method of claim 1 wherein the step of actively probing is performed according to a user specification of a network route for actively probing.

27. The method of claim 1 wherein the step of actively probing is performed according to a user specification of a network route to exclude from actively probing.

28. The method of claim 1 wherein the network route map is further based on a user specification of a telecommunication carrier preference and the step of building the network route map is according to the carrier preference.

30. The system of claim 29 further comprising:

a server configured for propagating the network route map to one or more network routing devices.

31. The system of claim 30 further comprising:

a translator configured for translating the network route map from a first format associated with the route optimization engine to a second format associated with the server.

32. The system of claim 30 wherein the server is a Border Gateway Protocol server.

33. The system of claim 29 further comprising:

a load balancer configured for queuing the data representing the operational characteristics prior to reception by the route optimization engine.

34. The system of claim 33 wherein the load balancer is further configured for authenticating the probe device.

35. The system of claim 29 wherein the route optimization engine is further configured for responding to a request for a network route map wherein the route map is from a perspective associated with the routing device.

36. The system of claim 29 wherein the probe device is one of a plurality of probe devices and the route optimization engine is configured to receive data representing operational characteristics from the plurality of probe devices and to determine the network route map based on the data received from the plurality of probe devices.

37. The system of claim 36 wherein at least one of the plurality of probe devices and the route optimization engine are located on a single machine.

38. The system of claim 36 wherein at least one of the plurality of probe devices and the route optimization engine are located on separate machines.

39. The system of claim 29 wherein the routing device is capable of using Border Gateway Protocol to exchange routing information with other devices on a network.

40. The system of claim 29 wherein failure of the probe device does not prohibit the routing device from forwarding network traffic.

41. The system of claim 29 wherein the probe device can be configured to actively probe a specified network route for operational characteristics related to the specified network route.

42. The system of claim 29 wherein the probe device can be configured to exclude a specified network route from probing for operational characteristics related to the specified network route.

43. The system of claim 29 wherein the probe device can be installed external to the one or more network routing devices whereby the probe device is external to network data streams.

29. A system comprising:

a probe device configured to actively probe for operational characteristics related to one or more network routes communicatively connected to a routing device; and

a route optimization engine communicatively connected to the probe device and configured to receive data representing the operational characteristics and to determine a network route map for network traffic through the routing device based on the data.

44. A method for routing information on a network, the method comprising the steps of:

actively probing a plurality of network routes to gather one or more network operational characteristics; and

providing data representing the operational characteristics to a processor for processing the data and for building a network route map based on the data for routing information on the network.

45. The method of claim 44, further comprising the steps of:

receiving the network route map;

creating a representation of each of one or more network routes based on the network route map; and

providing the representations to one or more network routing devices.

46. The method of claim 44 wherein a user can specify a network route to actively probe to gather one or more network operational characteristics and wherein the step of actively probing is performed according to the user specification.

47. The method of claim 44 wherein a user can specify a network route to exclude from actively probing to gather one or more network operational characteristics and wherein the step of actively probing is performed according to the user specification.

50. The apparatus of claim 49, further comprising:

means for propagating representations of network routes based on the network route map to network routing devices.

48. A method for routing information on a network, the method comprising the steps of:

receiving data representing network operational characteristics obtained from actively probing a plurality of network routes to gather the operational characteristics;

building a network route map based on the data; and

providing the network route map to a module for generating network routes based on the network route map for routing information on the network, the module including a server program for propagating the network routes to network routing devices.

49. An apparatus for building a network route map, the apparatus comprising:

means for actively probing a plurality of network routes to gather one or more network operational characteristics; and

means for building the network route map based on the operational characteristics that were gathered by the means for actively probing.

51. A computer-readable medium carrying one or more sequences of instructions for building a network route map, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

actively probing a plurality of network routes to gather one or more network operational characteristics; and

building the network route map based on the operational characteristics that were gathered by actively probing.

52. A computer-readable medium carrying one or more sequences of instructions for routing information on a network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

actively probing a plurality of network routes to gather one or more network operational characteristics; and

providing data representing the operational characteristics to a processor for processing the data and for building a network route map based on the data for routing information of the network.

53. A computer-readable medium carrying one or more sequences of instructions for routing information on a network, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

receiving data representing network operational characteristics obtained from probing a plurality of network routes to gather the operational characteristics;

building a network route map based on the data; and

providing the network route map to a module for generating network routes based on the network route map for routing information on the network.

54. A method for locating a host device in a network, comprising the steps of:

specifying a maximum time to live value for a data packet probe;

transmitting from a source a first data packet probe with a time to live value equal or approximate to one half the maximum time to live value;

determining, based on a response to the first data packet probe, whether the host device is between the source and a network location represented by the one half maximum time to live value or between the network location represented by the one half maximum time to live value and a network location represented by the maximum time to live value; and

if determined that the host device is between the source and a network location represented by the one half maximum time to live value, then determining, based on the response to the first data packet probe, the network location of the host device.

55. The method of claim 54, wherein if determined that the host device is between the network location represented by the one half maximum time to live value and the network location represented by the maximum time to live value, the method further comprising the steps of:

(a) specifying a first minimum time to live value for a second data packet probe equal to the one half maximum time to live value;

(b) transmitting from the source the second data packet probe with a time to live value equal or approximate to one half the difference between the maximum time to live value and the first minimum time to live value;

(c) determining, based on a response to the second data packet probe, whether the host device is between a network location represented by the first minimum time to live value and the one half the difference or between the network location represented by the one half the difference and the network location represented by the maximum time to live value;

(d) if determined that the host device is between the network location represented by the first minimum time to live value and the one half the difference, then determining, based on the response to the second data packet probe, the network location of the host device; and

(e) if determined that the host device is between the network location represented by the one half the difference and a network location represented by the maximum time to live value, then iterating steps (a)-(d) by continuing to bisect the remaining distance between the network location represented by one half the difference and the network location represented by the maximum time to live value until the host device is located.