Method and apparatus for improving performance in a network using a virtual queue and a switched poisson process traffic model

• US 8,391,145 B2
• Filed: 03/17/2010
• Issued: 03/05/2013
• Est. Priority Date: 05/11/2007
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Services Organization Incorporated (Verizon Communications Inc.)
• Inventors: Jones, Lawrence W.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Shand, Roberta A
• Application Number:
  US12/725,537
• Publication Number:
  US 20100172264A1
• Time in Patent Office: 1,084 Days
• Field of Search: 370/229, 370/232, 370/252, 370412-418, 370/428, 709223-226
• US Class Current: 370/232
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6235 Variable service order
• CPC Class Codes: H04L 47/6255 queue load conditions, e.g. longest queue first
• CPC Class Codes: H04L 47/627 policing

Abstract

A method for improving network performance using a virtual queue is disclosed. The method includes measuring characteristics of a packet arrival process at a network element, establishing a virtual queue for packets arriving at the network element, and modeling the packet arrival process based on the measured characteristics and a computed performance of the virtual queue.

Claims

1. A computer-implemented method for improving performance of a network device, comprising:

storing packets arriving at the network device in a virtual queue that emulates a buffer of infinite size;

generating a virtual queue occupancy histogram from said virtual queue;

removing the packets from the virtual queue in accordance with a specified service rate;

determining a distribution of the packets stored in the virtual queue, the determining comprising using said virtual queue occupancy histogram to determine a survivor function for the number of packets stored in the virtual queue;

modeling the performance of the network device based at least in part on the rate of arrival of the packets and on the distribution of the packets stored in the virtual queue; and

controlling a parameter of the network device based on the model.

3. The method of claim 1, wherein the controlled parameter of the network device includes at least one of an output link capacity of the network device or a buffer size of the network device.

4. The method of claim 1, wherein the parameter of the network device is controlled in accordance with a network performance objective.

5. The method of claim 4, wherein the network performance objective includes at least one of a desired bound on maximum service delay or a desired bound on maximum loss of packets.

6. The method of claim 1, wherein modeling the performance of the network device comprises:

approximating the packet arrival as a two-state Markov Modulated Poisson Process, and

estimating packet arrival rates and state transition rates associated with the two states,

wherein the parameter of the network device is controlled based on the estimated packet arrival rates and state transition rates.

7. The method of claim 1, further comprising modeling the performance of the network based on at least one of a packet arrival tally or an Index of Dispersion of Counts of packets arriving at the network device in a specified time duration.

8. The method of claim 1, further comprising controlling the parameter of the network device based further on a size distribution of the packets.

2. A computer-implemented method for improving performance of a network device, comprising:

storing packets arriving at the network device in a virtual queue;

removing the packets from the virtual queue in accordance with a specified service rate;

determining a distribution of the packets stored in the virtual queue, the determining comprising determining a survivor function for the number of packets stored in the virtual queue;

modeling the performance of the network device based at least in part on the rate of arrival of the packets and on the distribution of the packets stored in the virtual queue;

controlling a parameter of the network device based on the model;

estimating characteristics of a curve approximating the distribution of the packets stored in the virtual queue; and

modeling the performance of the network device based at least in part on the estimated characteristics of the curve.

9. A network device, comprising:

an ingress port configured to receive packets arriving at the network device;

an egress queue configured to store the packets for transmission by the network device;

an egress port configured to transmit the packets on a network; and

a monitoring module configured to;

store the arriving packets in a virtual queue that emulates a buffer of infinite size;

generate a virtual queue occupancy histogram from said virtual queue;

remove the packets from the virtual queue in accordance with a specified service rate;

use said virtual queue histogram to determine a distribution of the packets stored in the virtual queue as survivor function for the number of packets stored in the virtual queue;

model performance of the network device based at least in part on the rate of arrival of the packets and on the distribution of the packets stored in the virtual queue; and

control a parameter of at least one of the egress queue and the egress port based on the model.

10. The network device of claim 9, wherein the controlled parameter includes at least one of an output link capacity or a buffer size associated with at least one of the egress queue and the egress port.

11. The network device of claim 9, wherein monitoring module is configured to control the parameter in accordance with a network performance objective.

12. The network device of claim 11, wherein the network performance objective includes at least one of a maximum service delay or a maximum loss of packets.

13. The network device of claim 9, wherein the monitoring module is further configured to:

approximate the packet arrival as a two-state Markov Modulated Poisson Process;

estimate packet arrival rates and state transition rates associated with the two states; and

model the performance of the network device based on the estimated packet arrival rates and state transition rates.

14. The network device of claim 9, wherein the monitoring module is configured to model the performance of the network device based further on at least one of a packet arrival tally or an Index of Dispersion of Counts of packets arriving in a specified time duration.

15. The network device of claim 9, wherein the monitoring module is further configured to control the parameter based further on a size distribution of the packets.

16. A network device, comprising:

an ingress port configured to receive packets arriving at the network device;

an egress queue configured to store the packets for transmission by the network device;

an egress port configured to transmit the packets on a network; and

a monitoring module configured to;

store the arriving packets in a virtual queue;

remove the packets from the virtual queue in accordance with a specified service rate;

determine a distribution of the packets stored in the virtual queue as survivor function for the number of packets stored in the virtual queue;

model performance of the network device based at least in part on the rate of arrival of the packets and on the distribution of the packets stored in the virtual queue;

control a parameter of at least one of the egress queue and the egress port based on the model;

estimate characteristics of a curve approximating the distribution of the packets stored in the virtual queue; and

model the performance of the network device based on the estimated characteristics of the curve.

17. A tangibly embodied non-transitory computer-readable storage medium storing instructions which, when executed by a network monitoring module, cause the network monitoring module to perform the steps of:

storing packets arriving at the network device in a virtual queue that emulates a buffer of infinite size;

generating a virtual queue occupancy histogram from said virtual queue;

removing the packets from the virtual queue in accordance with a specified service rate;

using said virtual queue occupancy histogram to determine a distribution of the packets stored in the virtual queue by determining a survivor function for the number of packets stored in the virtual queue;

modeling the performance of the network device based at least in part on the rate of arrival of the packets and on the distribution of the packets stored in the virtual queue; and

controlling a parameter of the network device based on the model.

18. The computer-readable storage medium of claim 17, wherein the controlled parameter of the network device includes at least one of an output link capacity of the network device or a buffer size of the network device.

19. The computer-readable storage medium of claim 17, wherein the parameter of the network device is controlled in accordance with a network performance objective.

20. The computer-readable storage medium of claim 19, wherein the network performance objective includes at least one of a maximum service delay or a maximum loss of packets.

21. The computer-readable storage medium of claim 17, wherein modeling the performance of the network device comprises:

approximating the packet arrival as a two-state Markov Modulated Poisson Process; and

estimating packet arrival rates and state transition rates associated with the two states,

wherein the parameter of the network device is controlled based on the estimated packet arrival rates and state transition rates.

22. The computer-readable storage medium of claim 17, further comprising modeling the performance of the network based further on at least one of a packet arrival tally or an Index of Dispersion of Counts of packets arriving in a specified time duration.

23. The computer-readable storage medium of claim 17, further comprising controlling the parameter of the network device based further on a size distribution of the packets.

24. A tangibly embodied non-transitory computer-readable storage medium storing instructions which, when executed by a network monitoring module, cause the network monitoring module to perform the steps of:

storing packets arriving at the network device in a virtual queue;

removing the packets from the virtual queue in accordance with a specified service rate;

determining a distribution of the packets stored in the virtual queue, the determining comprising determining a survivor function for the number of packets stored in the virtual queue;

modeling the performance of the network device based at least in part on the rate of arrival of the packets and on the distribution of the packets stored in the virtual queue;

controlling a parameter of the network device based on the model;

estimating characteristics of a curve approximating the distribution of the packets stored in the virtual queue; and

modeling the performance of the network device based further on the estimated characteristics of the curve.