Latency based random early discard for network packets
View Patent ↗Methods, systems, and apparatus used to determine whether to discard a network packet based upon the latency exhibited by an associated a network packet queue. Network devices can include a queue management module operable to identify a latency metric in network packet queues and determine whether the latency metric renders the network packet queue eligible for discarding packets based upon, for example, a latency policy.
1. A computer-implemented method, comprising:
identifying a latency metric associated with each of a plurality of queues, the plurality of queues being operable to store data packets for delivery to recipient devices, and the latency metric identifying the actual latency associated with a queue;
determining whether the latency metric associated with any of the plurality of queues exceeds a threshold latency value associated with the respective queue, wherein each queue is associated with a different threshold latency value based on the traffic flow associated with the respective queue;
determining whether to discard one or more packets from those queues where the latency metric associated with the queue exceeds the threshold value; and
wherein the determination of whether to discard one or more of the packets is a weighted probability of discard based upon the latency metric associated with the respective queue
receiving an incoming data packet;
identifying a queue with which the incoming data packet is associated from among the plurality of queues;
placing the data packet into the identified queue;
determining whether the latency metric associated with the identified queue for the incoming data packet is greater than the threshold latency value associated with the queue; and
determining whether to discard the incoming data packet responsive to a determination that the latency metric exceeds the threshold value associated with the queue.
2. The computer-implemented method of claim 1 , wherein the plurality of queues correspond to quality of service constraints.
3. The computer-implemented method of claim 1 , wherein the plurality of queues correspond to various types of traffic being delivered.
4. The computer-implemented method of claim 1 , wherein a first threshold latency value for a first queue from the plurality of queues is different than a second threshold latency value for a second queue from the plurality of queues.
5. The computer-implemented method of claim 1 , wherein identifying the latency metric comprises determining a length of time an oldest packet in a respective queue has been resident in the respective queue.
6. The computer-implemented method of claim 1 , wherein identifying the latency metric comprises identifying an oldest data packet in a respective queue.
7. The computer-implemented method of claim 6 , wherein determining whether to discard one or more packets comprises determining whether to discard the oldest data packet in a respective queue where the latency metric associated with the respective queue exceeds the threshold latency value.
8. The computer-implemented method of claim 1 , wherein identifying the latency metric comprises calculating an average latency of at least a portion of data packets in a respective queue.
9. The computer-implemented method of claim 1 , wherein identifying the latency metric comprises calculating an aggregate latency of at least a portion of data packets in a respective queue.
10. The computer-implemented method of claim 1 , wherein the latency metric is derived from a delivery schedule associated with the packets in a respective queue.
11. The computer-implemented method of claim 1 , wherein the threshold latency value comprises a dynamic threshold latency value that varies based upon a usage level of space in a respective queue.
12. The computer-implemented method of claim 1 , wherein the threshold latency value associated with each of the plurality of queues is variable according to a portion of a buffer that is occupied by packets associated with the respective queue.
13. One or more computer-readable media having instructions stored thereon, the one or more computer readable media, when executed by a processor, cause the processor to perform operations comprising:
receiving an incoming data packet;
identifying a queue with which the incoming data packet is associated from among a plurality of queues;
placing the data packet into the identified queue;
identifying a latency metric associated with the identified queues, wherein each identified queue is associated with a different threshold latency value based on the traffic flow associated with a respective queue, and the latency metric identifies the actual latency associated with data packets in the respective queue;
determining whether the latency metric associated with the identified queue exceeds a threshold latency value associated with the identified queue;
determining whether to discard one or more packets from the identified queue where the latency metric associated with the identified queue exceeds the threshold latency value; and
wherein the determination of whether to discard one or more of the packets is a weighted probability of discard based upon a usage level associated with the identified queue.
14. The one or more computer-readable media of claim 13 , wherein identifying the latency metric comprises determining a length of time an oldest packet in the identified queue has been resident in the identified queue.
15. The one or more computer-readable media of claim 13 , wherein identifying the latency metric comprises identifying an oldest data packet in the identified queue.
16. The one or more computer-readable media of claim 15 , wherein determining whether to discard one or more packets comprises determining whether to discard the oldest data packet in the identified queue where the oldest data packet in the identified queue is older than the threshold latency value.
17. The one or more computer-readable media of claim 13 , wherein identifying the latency metric comprises calculating an average latency of at least a portion of data packets in the identified queue.
18. The one or more computer-readable media of claim 13 , wherein identifying the latency metric comprises calculating an aggregate latency of at least a portion of data packets in the identified queue.
19. The one or more computer-readable media of claim 13 , wherein the latency metric is derived from a delivery schedule associated with the packets in the identified queue.
20. The one or more computer-readable media of claim 13 , wherein the threshold latency value comprises a dynamic threshold latency value that varies based upon a usage level of space in the identified queue.
21. The one or more computer-readable media of claim 13 , wherein determining whether to discard one or more packets from the identified queue where the latency metric associated with the identified queue exceeds the threshold latency value comprises determining whether to discard the incoming data packet.