Methods and apparatus to select composite link cost-out thresholds

• US 7,974,213 B2
• Filed: 11/21/2008
• Issued: 07/05/2011
• Est. Priority Date: 11/21/2008
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Oikonomou, Kostas N., Sinha, Rakesh Kumar
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Davenport; Mon Cheri S
• Application Number:
  US12/275,948
• Publication Number:
  US 20100128629A1
• Time in Patent Office: 956 Days
• Field of Search: 370/216, 370/241, 370/241.1, 370/242, 370/248, 370/253, 370/254, 370/255, 370/351, 370/431, 370/437, 370/464, 370/465, 709/226, 709/227
• US Class Current: 370/252
• CPC Class Codes: H04L 41/0681 Configuration of triggering conditions
• CPC Class Codes: H04L 43/0835 One way packet loss
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity

Abstract

Methods and apparatus to select composite link cost-out thresholds are disclosed. A disclosed example method comprises collecting traffic statistics for a communication network, computing, based on the collected traffic statistics, a plurality of flow rates for a composite link of the communication network for respective ones of a plurality of potential fault conditions for the composite link, computing a plurality of remaining capacities of the composite link for respective ones of the plurality of fault conditions, computing a plurality of differences between respective ones of the plurality of flow rates and the plurality of remaining capacities, and selecting a cost-out threshold for the composite link based on the plurality of computed differences.

Claims

1. A method comprising:

collecting traffic statistics for a communication network;

computing, based on the traffic statistics, a plurality of projected flow rates for a composite link of the communication network for respective ones of a plurality of potential fault conditions for the composite link;

computing a plurality of projected remaining capacities of the composite link for respective ones of the plurality of fault conditions, each of the plurality of projected remaining capacities representing a difference between a projected capacity of the composite link were the corresponding potential fault condition to occur and the corresponding projected flow rate;

selecting a cost-out threshold for the composite link based on the plurality of projected flow rates and the plurality of projected remaining capacities, the cost-out threshold representing an actual remaining capacity of the composite link when a router stops at least one of routing or transporting data via the composite link; and

configuring the router associated with the composite link with the cost-out threshold.

2. A method as defined in claim 1, wherein the composite link comprises first and second communication paths, and wherein a first potential fault condition comprises a first defect in the first communication path and a second potential fault condition comprises a second defect in the second communication path.

3. A method as defined in claim 1, further comprising comparing an operating capacity of the composite link to the cost-out threshold to determine whether to cost-out data from the composite link to another communication path.

4. A method as defined in claim 1, further comprising:

computing a plurality of arithmetic differences between respective ones of the plurality of flow rates and the plurality of remaining capacities;

eliminating differences that are less than or equal to zero from the plurality of differences to form a plurality of losses;

computing a first expected loss based on at least one of the plurality of losses having a first associated remaining capacity;

computing a second expected loss based on at least one of the plurality of losses having a second associated remaining capacity, wherein the second remaining capacity is greater than the first remaining capacity; and

computing a third expected loss based on at least one of the plurality of losses having a third associated remaining capacity, wherein the third remaining capacity is greater than the second remaining capacity, and wherein the cost-out threshold is selected based on the first, second and third expected losses.

5. A method as defined in claim 4, further comprising:

computing a first arithmetic difference between the first and second expected losses;

computing a second arithmetic difference between the second and third expected losses; and

selecting the first associated remaining capacity as the cost-out threshold when the first arithmetic difference is less than the second arithmetic difference.

6. A method as defined in claim 1, further comprising:

computing a first network-wide packet loss for the communication network based on the cost-out threshold selected and the traffic statistics collected;

adjusting the cost-out threshold;

computing a second network-wide packet loss for the communication network based on the cost-out threshold adjusted and the traffic statistics collected; and

comparing the first and second network-wide packet losses to determine whether to select the cost-out threshold adjusted.

7. An apparatus comprising:

a collector to collect traffic statistics for a communication network;

a network modeler to compute, based on the traffic statistics, a plurality of projected flow rates for a composite link of the communication network for respective ones of a plurality of potential fault conditions for the composite link, and to compute a plurality of projected remaining capacities of the composite link for respective ones of the plurality of fault conditions, each of the plurality of projected remaining capacities representing a difference between a projected capacity of the composite link were the corresponding potential fault condition to occur and the corresponding projected flow rate; and

a threshold chooser to select a cost-out threshold for the composite link based on the plurality of projected flow rates and the plurality of projected remaining capacities computed, the cost-out threshold representing an actual remaining capacity of the composite link when a router stops at least one of routing or transporting data via the composite link.

8. An apparatus as defined in claim 7, wherein the composite link comprises first and second communication paths, and wherein a first potential fault condition comprises a first defect in the first communication path and a second potential fault condition comprises a second defect in the second communication path.

9. An apparatus as defined in claim 7, further comprising:

a router associated with the composite link to compare an operating capacity of the composite link to the cost-out threshold to determine whether to cost-out data from the composite link to another communication path; and

a router configurer to configure the router with the cost-out threshold selected.

10. An apparatus as defined in claim 7, further comprising a first data structure having a plurality of entries for respective ones of the plurality of fault conditions, wherein a first entry of the first data structure comprises a first flow rate, a first remaining capacity and a first loss associated with a first fault condition.

11. An apparatus as defined in claim 10, wherein the threshold chooser is to eliminate from the first data structure a second entry comprising a second loss that is less than or equal to zero.

12. An apparatus as defined in claim 7, wherein the threshold chooser is to:

compute a plurality of arithmetic differences between respective ones of the plurality of flow rates and the plurality of remaining capacities;

compute a first expected loss based on at least one of the plurality of differences having a first associated remaining capacity;

compute a second expected loss based on at least one of the plurality of differences having a second associated remaining capacity, wherein the second remaining capacity is greater than the first remaining capacity;

compute a third expected loss based on at least one of the plurality of differences having a third associated remaining capacity, wherein the third remaining capacity is greater than the second remaining capacity, and

select the cost-out threshold based on the first, second and third expected losses.

13. An apparatus as defined in claim 12, wherein the threshold chooser is to:

compute a first arithmetic difference between the first and second expected losses;

compute a second arithmetic difference between the second and third expected losses; and

select the first associated remaining capacity as the cost-out threshold when the first arithmetic difference is less than the second arithmetic difference.

14. An apparatus as defined in claim 7, further comprising a threshold optimizer to:

compute a first network-wide packet loss for the communication network based on the cost-out threshold selected and the traffic statistics collected;

adjust the cost-out threshold;

compute a second network-wide packet loss for the communication network based on the cost-out threshold adjusted and the traffic statistics collected; and

compare the first and second network-wide packet losses to determine whether to select the cost-out threshold adjusted.

15. A tangible article of manufacture excluding propagating signals and storing machine-readable instructions that, when executed, cause a machine to:

collect traffic statistics for a communication network;

compute, based on the traffic statistics, a plurality of projected flow rates for a composite link of the communication network for respective ones of a plurality of potential fault conditions for the composite link;

compute a plurality of projected remaining capacities of the composite link for respective ones of the plurality of fault conditions, each of the plurality of projected remaining capacities representing a difference between a projected capacity of the composite link were the corresponding potential fault condition to occur and the corresponding projected flow rate;

compute a plurality of arithmetic differences between respective ones of the plurality of projected flow rates and the plurality of projected remaining capacities; and

select a cost-out threshold for the composite link based on the plurality of arithmetic differences, the cost-out threshold representing an actual remaining capacity of the composite link when a router stops at least one of routing or transporting data via the composite link.

16. An article of manufacture as defined in claim 15, wherein the composite link comprises first and second communication paths, and wherein a first potential fault condition comprises a first defect in the first communication path and a second potential fault condition comprises a second defect in the second communication path.

17. An article of manufacture as defined in claim 15, wherein the machine-readable instructions, when executed, cause the machine to compare an operating capacity of the composite link to the cost-out threshold to determine whether to cost-out data from the composite link to another communication path.

18. An article of manufacture as defined in claim 15, wherein the machine-readable instructions, when executed, cause the machine to configure a router associated with the composite link with the cost-out threshold.

19. An article of manufacture as defined in claim 15, wherein the machine-readable instructions, when executed, cause the machine to:

eliminate differences that are less than or equal to zero from the plurality of differences to form a plurality of losses;

compute a first expected loss based on one or more of the plurality of losses having a first associated remaining capacity;

compute a second expected loss based on one or more of the plurality of losses having a second associated remaining capacity, wherein the second remaining capacity is greater than the first remaining capacity; and

compute a third expected loss based on one or more of the plurality of losses having a third associated remaining capacity, wherein the third remaining capacity is greater than the second remaining capacity, and wherein the cost-out threshold is selected based on the first, second and third expected losses.

20. An article of manufacture as defined in claim 19, wherein the machine-readable instructions, when executed, cause the machine to:

compute a first arithmetic difference between the first and second expected losses;

compute a second arithmetic difference between the second and third expected losses; and

select the first associated remaining capacity as the cost-out threshold when the first arithmetic difference is less than the second arithmetic difference.

21. An article of manufacture as defined in claim 15, wherein the machine-readable instructions, when executed, cause the machine to:

compute a first network-wide packet loss for the communication network based on the cost-out threshold selected and the traffic statistics collected;

adjust the cost-out threshold;

compute a second network-wide packet loss for the communication network based on the cost-out threshold adjusted and the traffic statistics collected; and

compare the first and second network-wide packet losses to determine whether to select the cost-out threshold adjusted.