Performance evaluation and traffic engineering in IP networks
View Patent ↗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.
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.