System for determining network route quality using sequence numbers

• US 20050243830A1
• Filed: 04/30/2004
• Published: 11/03/2005
• Est. Priority Date: 04/30/2004
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Gardner, Edward A., Helliwell, Richard Perham, Wrenn, Richard Fitzhugh
• Granted Patent: US 7,440,458 B2
• Time in Patent Office: Days
• US Class Current: 370/394
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/247 using M:N active or standby paths
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS

Abstract

A system and method for determining route quality in a network in which multiple routes exist between a transmitting end-point and a receiving end-point. Initially, a routing sequence number is associated with each transmission sent on a route in the network, such that consecutive transmissions sent on one of the routes have consecutive routing sequence numbers. The routing sequence number for a first one of the routes is included in transmissions sent on a second one of the routes. The routing sequence number of the first route, received on the second route, is used as an indicator of the route quality of the first route, and this indicator is compared to an expected routing sequence number for the first route to determine a likelihood of whether the transmissions sent via the first route are either lost or delayed. The expected routing sequence number is normally incremented each time a transmission is received on the second route.

Claims

1. A method for determining route quality in a network in which a plurality of routes exist between a transmitting end-point and a receiving end-point comprising the steps of:

associating a routing sequence number with each transmission sent on a route in the network, such that consecutive transmissions sent on one of the routes have consecutive routing sequence numbers;

including the routing sequence number, for a first said route, in transmissions sent on a second said route;

using the routing sequence number of the first said route, received on the second said route, as an indicator of the route quality of the first said route; and

comparing the indicator to an expected routing sequence number for the first said route to determine a likelihood of whether the transmissions sent via the first said route are either lost or delayed;

wherein the expected routing sequence number is normally incremented each time a transmission is received on the second said route.

2. A method for determining relative route quality in a network in which a plurality of routes exist between a transmitting end-point and a receiving end-point comprising the steps of:

associating a routing sequence number with each transmission sent on one of the routes such that consecutive said transmissions sent on one of the routes have consecutive routing sequence numbers;

including the routing sequence number and route identifier of at least one of the plurality of routes in each of the transmissions sent on each said route, wherein the route accordingly described in each sent transmission is the described route;

computing the expected routing sequence number for each of the routes received at the receiving end-point; and

using the difference between the routing sequence number included in a received transmission and the expected routing sequence number for the corresponding described route as an indicator of the described route'"'"'s quality.

3. The method of claim 2, wherein the route on which a given said transmission is sent and received is the receive route, and wherein the receive route'"'"'s expected routing sequence number is computed by performing steps comprising:

increasing the expected routing sequence number by 1, if a received transmission describes the routing sequence number of the receive route, and if the routing sequence number described in the received transmission equals the current expected routing sequence number of the described route;

increasing the expected routing sequence number by a value of N+1, if the received transmission describes the routing sequence number of the receive route and the described routing sequence number exceeds the current expected routing sequence number of the described route by a value of N; and

increasing the expected routing sequence number by 1, if the received transmission does not describe the routing sequence number of the receive route.

4. The method of claim 3, wherein a routing sequence number described in the received transmission equals or exceeds the expected routing sequence number for the corresponding described route constitutes an indication of at least one missing transmission on the described route, unless the described route is the receive route and the described routing sequence number equals the expected routing sequence number.

5. The method of claim 3, wherein the likelihood of whether a missing transmission is lost or delayed is determined as a function of the route on which an indication of the missing transmission is received;

wherein;

when the indication of the missing transmission is obtained on the same route as the missing transmission, then the missing transmission is determined to be probably lost; and

when the indication of the missing transmission is obtained on a different route than the route on which the missing transmission should have been received, then the missing transmission is determined to be probably delayed initially, and after a predetermined period of time, the missing transmission is determined to be lost.

6. The method of claim 3, wherein, when one of the transmissions is received that includes a routing sequence number for the receive route, then transmissions are determined to be missing, by calculating the difference between the value of the routing sequence number described in the transmission and the value of the expected routing sequence number for the described route, wherein:

if the routing sequence number described in the transmission exceeds the expected routing sequence number for the described route by a value of N, then N transmissions are determined to be missing on the described route and probably lost; and

if the routing sequence number described in the transmission is less than the expected routing sequence number for the described route, then a transmission previously determined to have been lost on the described route was instead delayed.

7. The method of claim 3, wherein the route on which the transmission is sent and received is the receive route, and wherein, when one of the transmissions is received that includes a described routing sequence number for one of the routes other than the receive route, then one or more of the transmissions is determined to be missing by performing steps comprising:

determining that the transmission being described is missing on the described route and probably delayed, if the described routing sequence number equals the expected routing sequence number for the described route; and

determining that N+1 said transmissions are missing and probably delayed, if the described routing sequence number exceeds the expected routing sequence number for the described route by N.

8. A method for determining relative route quality in a network in which a plurality of routes exist between a transmitting end-point and a receiving end-point comprising the steps of:

associating a routing sequence number with each transmission sent on one of the routes such that consecutive said transmissions sent on one of the routes have consecutive routing sequence numbers;

including the routing sequence and number route identifier of a single one of the plurality of routes in each of the transmissions sent on each said route, wherein the route accordingly described in each sent transmission is the described route;

rotating the described route among the plurality of routes in the transmissions sent on said routes selected from the plurality of routes;

computing an expected routing sequence number for each of the plurality of routes at the receiving end-point;

using the difference between the routing sequence number included in a received transmission and the expected routing sequence number for the corresponding described route as an indicator of the described route'"'"'s quality; and

using the indicator to determine a likelihood of whether the transmissions sent via the described route are either lost or delayed.

9. The method of claim 8, wherein the route on which a given said transmission is sent and received is the receive route, and wherein the receive route'"'"'s expected routing sequence number is computed by performing steps comprising:

increasing the expected routing sequence number by 1, if a received transmission describes the routing sequence number of the receive route and described routing sequence equals the current expected routing sequence number of the described route;

increasing the expected routing sequence number by a value of N+1, if the received transmission describes the routing sequence number of the receive route and the described routing sequence number exceeds the current expected routing sequence number of the described route by a value of N; and

increasing the expected routing sequence number by 1, if the received transmission does not describe the routing sequence number of the receive route.

10. The method of claim 9, wherein, when a routing sequence number described in the received transmission equals or exceeds the expected routing sequence number for the corresponding described route, a determination is made that at least one transmission is missing on the described route, unless the described route is the receive route and the described routing sequence number equals the expected routing sequence number.

11. The method of claim 9, wherein the likelihood of whether a missing transmission is lost or delayed is determined as a function of the route on which an indication of the missing transmission is received, wherein:

when the indication of the missing transmission is obtained on the same route as the missing transmission, then the missing transmission is determined to be probably lost; and

when the indication of the missing transmission is obtained on a different route than the route on which the missing transmission should have been received, then the missing transmission is initially determined to be probably delayed.

12. The method of claim 11, wherein, when one of the transmissions is received that describes a routing sequence number for the receive route, then certain ones of the transmissions are determined to be missing by calculating the difference between the value of the routing sequence number described in the transmission and the value of the expected routing sequence number for the described route, wherein:

if the routing sequence number described in the transmission exceeds the expected routing sequence number for the described route by a value of N, then N transmissions are determined to be missing, and probably lost, on the described route; and

if the routing sequence number described in the transmission is less than the expected routing sequence number for the described route, then a transmission that was previously determined to have been lost on the described route is presently determined to have been delayed.

13. The method of claim 11, wherein, when one of the transmissions is received that includes a routing sequence number for a route other than the receive route, then one or more of the transmissions is determined to be missing by performing steps comprising:

determining that the transmission being described is missing on the described route and probably delayed; and

determining that N+1 said transmissions are missing and probably delayed, if the described routing sequence number exceeds the expected routing sequence number for the described route by N.

14. The method of claim 9, wherein a non-negative metric constituting transmission loss likelihood is computed for each specific route, a high value of which indicates multiple recently lost transmissions on the specific route, and a low value of which indicates few recently lost transmissions on the specific route, wherein the metric is updated each time a transmission is received that describes a routing sequence number for the receive route, by performing the step of:

if the described routing sequence number exceeds the expected routing sequence number for the described route by a value of N, then N transmissions are determined to be probably lost on the described route and the described route'"'"'s transmission loss likelihood is updated with a low-pass digital filter with input N, otherwise the described route'"'"'s transmission loss likelihood is updated with a low-pass filter with input of zero.

15. The method of claim 14, wherein the metric for the specific route is decreased each time the specific route'"'"'s transmission loss likelihood is updated and the new value is greater than a fixed threshold, and the metric for the specific route is increased each time a transmission is successfully received on the specific route.

16. The method of claim 9, wherein a non-negative transmission delay likelihood metric is computed for each specific route, a high value of the metric indicating multiple recently delayed transmissions or transmissions recently delayed for long times on the specific route, and a low value of the metric indicating few recently delayed transmissions on the specific route, wherein, when a transmission is received that describes the routing sequence number for a different route other than the receive route and the highest routing sequence number described for the different route equals or exceeds the described route'"'"'s expected routing sequence number by Y, then the transmission delay likelihood for the different route is updated with a low-pass digital filter with input (Y+1)*(current time−

mean delayed transmission expected receive time).

17. The method of claim 9, wherein a non-negative transmission delay likelihood metric is computed for each specific route, a high value of the metric indicating multiple recently delayed transmissions or transmissions recently delayed for long times on the specific route, and a low value of the metric indicating few recently delayed transmissions on the specific route, wherein, when a transmission is received that describes the routing sequence number for the receive route and the described routing sequence number equals or exceeds the receive route'"'"'s expected routing sequence number, and the receive route'"'"'s highest described routing sequence number is less than the expected routing sequence number, then the route'"'"'s transmission delay likelihood is updated with a low-pass digital filter with input zero.

18. The method of claim 9, wherein a non-negative transmission delay likelihood metric is computed for each specific route, a high value of the metric indicating multiple recently delayed transmissions or transmissions recently delayed for long times on the specific route, and a low value of the metric indicating few recently delayed transmissions on the specific route, wherein, when a transmission is received that describes a routing sequence number for the receive route, and the described routing sequence number equals or exceeds the receive route'"'"'s expected routing sequence number, and the highest described routing sequence number described prior to the received transmission equals or exceeds the expected routing sequence number by Y, then the receive route'"'"'s transmission delay likelihood is updated with a low-pass digital filter with input (Y)*(current time minus mean delayed transmission expected receive time);

wherein mean delayed transmission expected receive time is approximated as current time minus a constant.

19. The method of claim 9, wherein a mean delayed transmission expected receive time metric is computed for each said route, such that the metric approximates the mean of the expected receive times for delayed transmissions on a given said route, wherein the metric is updated when a transmission is received that describes a routing sequence number for a route other than the receive route and the described route'"'"'s highest routing sequence number described prior to the receipt of the received transmission is one less than the expected routing sequence number therefor, and the described routing sequence number equals or exceeds the described route'"'"'s expected routing sequence number by X, then the route'"'"'s mean delayed transmission expected receive time is calculated as the current time minus the inter-transmission time for the route described in the received transmission.

20. The method of claim 9, wherein a mean delayed transmission expected receive time metric is computed for each said route, such that the metric approximates the mean of the expected receive times for delayed transmissions on a given said route, wherein the metric is updated when a transmission is received that describes a routing sequence number for a route other than the receive route and the described route'"'"'s highest routing sequence number described prior to the receipt of the received transmission is one less than the expected routing sequence number therefor, and the described routing sequence number equals or exceeds the described route'"'"'s expected routing sequence number by X, then when a transmission is received that describes a routing sequence number for a different route other than the receive route and the described routing sequence number exceeds the described route'"'"'s highest routing sequence number described prior to the receipt of the received transmission and the described routing sequence number equals or exceeds the described route'"'"'s expected routing sequence number by X, then the different route'"'"'s mean delayed transmission expected receive time is calculated as the current time−

(mean delayed transmission expected receive time−

current time)*(Y+1)/(X+1).

21. The method of claim 9, wherein a mean delayed transmission expected receive time metric is computed for each said route, such that the metric approximates the mean of the expected receive times for delayed transmissions on a given said route, wherein the metric is updated when a transmission is received that describes a routing sequence number for a route other than the receive route and the described route'"'"'s highest routing sequence number described prior to the receipt of the received transmission is one less than the expected routing sequence number therefor, and the described routing sequence number equals or exceeds the described route'"'"'s expected routing sequence number by X, then when a transmission is received that describes a routing sequence number for the receive route and the described routing sequence number exceeds the highest routing sequence number described prior to the receipt of this transmission, then all transmissions thought to have been delayed previously are probably lost, and the mean delayed transmission expected receive time is set to the current time.

22. The method of claim 19, wherein a route'"'"'s quality metric is decreased each time the route'"'"'s transmission delay likelihood is increased such that its value crosses a multiple of a fixed threshold and a route'"'"'s quality metric is increased each time a transmission is successfully received on the route.

23. A system for determining route quality in a network in which a plurality of routes exist between a transmitting end-point and a receiving end-point comprising:

a routing sequence number, associated with each transmission sent on a route in the network, such that consecutive transmissions sent on one of the routes have consecutive routing sequence numbers;

wherein;

the routing sequence number, for a first said route, is included in transmissions sent on a second said route;

the routing sequence number of the first said route, received on the second said route, is used as an indicator of the route quality of the first said route; and

the indicator is compared to an expected routing sequence number for the first said route to determine a likelihood of whether the transmissions sent via the first said route are either lost or delayed;

wherein the expected routing sequence number is normally incremented each time a transmission is received on the second said route.

24. A software product comprising instructions, stored on computer-readable media, wherein the instructions, when executed by a computer, perform steps for determining route quality in a network in which a plurality of routes exist between a transmitting end-point and a receiving end-point comprising:

associating a routing sequence number with each transmission sent on a route in the network, such that consecutive transmissions sent on one of the routes have consecutive routing sequence numbers;

including the routing sequence number, for a first said route, in transmissions sent on a second said route;

using the routing sequence number of the first said route, received on the second said route, as an indicator of the route quality of the first said route; and

comparing the indicator to an expected routing sequence number for the first said route to determine a likelihood of whether the transmissions sent via the first said route are either lost or delayed;

wherein the expected routing sequence number is normally incremented each time a transmission is received on the second said route.