Performance evaluation and traffic engineering in IP networks

• US 6,909,693 B1
• Filed: 12/29/2000
• Issued: 06/21/2005
• Est. Priority Date: 08/21/2000
• Status: Expired due to Term

• Current Assignee: Avaya Incorporated
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Zhang, Xiaohui, Yeom, Ikjun, Firoiu, Victor
• Primary Examiner(s): Phunkulh, Bob A.
• Application Number:
  US09/752,101
• Time in Patent Office: 1,635 Days
• Field of Search: 370/229, 370/230, 370/230.1, 370/231, 370/232, 370/233, 370/234, 370/235, 370/237, 370/252, 370/412, 370/413, 370/236, 710/52, 709/230, 709/231, 709/232, 709/233, 709/234, 709/235
• US Class Current: 370/235
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]

Abstract

A model is given for performance evaluation of IP computer networks that are dominated by congestion-controlled traffic. The model includes heterogeneous TCP flows, UDP flows, short-lived TCP flows, and TCP flows in a differentiated services network. The performance of large-scale networks is estimated where flows may encounter multiple congested links.

Claims

1. A method of modeling link throughput in a computer network having a plurality of links, a plurality of heterogeneous congestion-responsive flows of varying traffic characteristics, and a plurality of constant bit rate flows, the method comprising:

determining link throughput of a given link as a function of a set of average queue sizes for paths of the flows through the given link, the function representing a sum of;

(i) a sum of the individual heterogeneous congestion-responsive flows through the given link, each term in the sum being a function of a set of average queue sizes for the plurality of links, and

(ii) a sum of the individual constant bit rate flows through the given link, each term in the sum being a function of a term reflecting a random early detection (RED) drop function of average queue size for each link in the path of the individual constant bit rate flow.

2. A method according to claim 1, further comprising:

determining link throughput for each link in the network.

3. A method according to claim 2, further comprising:

finding a set of average queue sizes for each link in the network such that the link throughput for each link is less than or equal to a maximum flow capacity for that link.

4. A method according to claim 3, wherein the finding a set of average queue sizes for each link includes:

(i) finding an initial set of average queue sizes for each link such that the link throughput for each link is less than or equal to a maximum flow capacity for that link, and

(ii) for each congestion-responsive flow, iteratively decreasing the average queue sizes for each link in the path of the congestion-responsive flow to maximize each of the congestion-responsive flows as a function of average queue size for each link in the path of the congestion-responsive flow.

5. A method according to claim 1, wherein the varying traffic characteristics include packet size.

6. A method according to claim 1, wherein the varying traffic characteristics include flow window size.

7. A method according to claim 1, wherein the varying traffic characteristics include flow round trip time.

8. A method according to claim 7, wherein for each flow, the round trip time is the great er of system time resolution and actual roundtrip time for the flow.

9. A method according to claim 1, wherein the varying traffic characteristics include average number of packets acknowledged by an acknowledgement packet received by a sender of the flow from a receiver of the flow.

10. A method according to claim 9, wherein for each flow, the average number of packets acknowledged is a ratio of a total number of packets for the flow to the product of a total number of acknowledgement packets for the flow times a term adjusting for a probability of an acknowledgement packet being dropped.

11. A method according to claim 1, wherein the plurality of constant bit rate flows include a User Datagram Protocol (UDP) flow.

12. A method according to claim 1, wherein the plurality of congestion-responsive flows include a Transmission Control Protocol (TCP) flow.

13. A method according to claim 12, wherein the TCP flow is a short-lived TCP flow.

14. A method according to claim 12, wherein the network is a differentiated services network.

15. A method according to claim 1, wherein the network is an Internet Protocol (IP) network.

16. A computer program product for use on a computer system for modeling link throughput in a computer network having a plurality of links, a plurality of heterogeneous congestion-responsive flows of varying traffic characteristics, and a plurality of constant bit rate flows, the computer program product comprising a computer usable medium having computer readable program code thereon, the computer readable program code comprising:

program code for determining link throughput of a given link as a function of a set of average queue sizes for paths of the flows through the given link, the function representing a sum of;

(i) a sum of the individual heterogeneous congestion-responsive flows through the given link, each term in the sum being a function of a set of average queue sizes for the plurality of links, and

(ii) a sum of the individual constant bit rate flows through the given link, each term in the sum being a function of a term reflecting a random early detection (RED) drop function of average queue size for each link in the path of the individual constant bit rate flow.

17. A computer program product according to claim 16, further comprising:

program code for determining link throughput for each link in the network.

18. A computer program product according to claim 17, further comprising:

program code for finding a set of average queue sizes for each link in the network such that the link throughput for each link is less than or equal to a maximum flow capacity for that link.

19. A computer program product according to claim 18, wherein the finding a set of average queue sizes for each link includes:

(i) finding an initial set of average queue sizes for each link such that the link throughput for each link is less than or equal to a maximum flow capacity for that link, and

(ii) for each congestion-responsive flow, iteratively decreasing the average queue sizes for each link in the path of the congestion-responsive flow to maximize each of the congestion-responsive flows as a function of average queue size for each link in the path of the congestion-responsive flow.

20. A computer program product according to claim 16, wherein the varying traffic characteristics include packet size.

21. A computer program product according to claim 16, wherein the varying traffic characteristics include flow window size.

22. A computer program product according to claim 16, wherein the varying traffic characteristics include flow round trip time.

23. A computer program product according to claim 22, wherein for each flow, the round trip time is the greater of system time resolution and actual roundtrip time for the flow.

24. A computer program product according to claim 16, wherein the varying traffic characteristics include average number of packets acknowledged by an acknowledgement packet received by a sender of the flow from a receiver of the flow.

25. A computer program product according to claim 24, wherein for each flow, the average number of packets acknowledged is a ratio of a total number of packets for the flow to the product of a total number of acknowledgement packets for the flow times a term adjusting for a probability of an acknowledgement packet being dropped.

26. A computer program product according to claim 16, wherein the plurality of constant bit rate flows include a User Datagram Protocol (UDP) flow.

27. A computer program product according to claim 16, wherein the plurality of congestion-responsive flows include a Transmission Control Protocol (TCP) flow.

28. A computer program product according to claim 27, wherein the TCP flow is a short-lived TCP flow.

29. A computer program product according to claim 27, wherein the network is a differentiated services network.

30. A computer program product according to claim 16, wherein the network is an Internet Protocol (IP) network.