METHOD AND APPARATUS FOR IMPROVING PERFORMANCE IN A NETWORK USING A VIRTUAL QUEUE AND A SWITCHED POISSON PROCESS TRAFFIC MODEL

• US 20100172264A1
• Filed: 03/17/2010
• Published: 07/08/2010
• 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.
• Granted Patent: US 8,391,145 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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-38. -38. (canceled)

39. 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;

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.

40. The method of claim 39, further comprising:

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.

41. The method of claim 39, wherein determining the distribution of the packets stored in the virtual queue comprises at least one of:

determining a probability density function for the number of packets stored in the virtual queue; and

determining a survivor function for the number of packets stored in the virtual queue.

42. The method of claim 39, wherein the controlled parameter of the network device includes at least one of an output link capacity of the network device and a buffer size of the network device.

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

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

45. The method of claim 39, 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.

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

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

48. 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 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;

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.

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

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.

50. The network device of claim 48, wherein the monitoring module is further configured to determine the distribution of the packets stored in the virtual queue as at least one of a probability density function for the number of packets stored in the virtual queue and a survivor function for the number of packets stored in the virtual queue.

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

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

53. The network device of claim 52, wherein the network performance objective includes at least one of a maximum service delay and a maximum loss of packets.

54. The network device of claim 48, 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.

55. The network device of claim 48, 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 and an Index of Dispersion of Counts of packets arriving in a specified time duration.

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

57. A computer-readable storage medium storing instructions which, when executed by a network monitoring module, cause the network monitoring module to perform a method for improving performance of a network device, the method 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;

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.

58. The computer-readable storage medium of claim 57, the method further comprising:

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.

59. The computer-readable storage medium of claim 57, wherein determining the distribution of the packets stored in the virtual queue comprises at least one of:

determining a probability density function for the number of packets stored in the virtual queue; and

determining a survivor function for the number of packets stored in the virtual queue.

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

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

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

63. The computer-readable storage medium of claim 57, 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 the estimated packet arrival rates and state transition rates.

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

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