Predictive management of a network buffer

Patent metadata

Field	Value
Publication number	US-9686201-B2
Application number	US-201414164165-A
Country	US
Kind code	B2
Filing date	Jan 25, 2014
Priority date	Jan 25, 2013
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

Abstract

Predictive management of a network buffer is contemplated. The network buffer maybe predictively managed to control packet drop based at least in part on predicted sojourn time. The predicted sojourn time may be determined to predict time needed from an arriving packet to travel through a queue of the network buffer.

First claim

What is claimed is:

1. A method for predictively managing a network element configured for transmitting packets over a network, the network element including a buffer and a queue, a capacity of the buffer being split into at least a first portion and a second portion, the second portion being greater than the first portion and including an entirety of the queue, the queue being configured to enqueue packets at a queue input and to dequeue packets at a queue output, the packets traveling through the buffer in a first-in-first-out manner whereby the packets travel through the first portion and thereafter through the queue of the second portion from the queue input to the queue output, the method comprising:
receiving a first packet at a buffer input of the buffer;
predicting a first sojourn time prior to the first packet exiting the first portion, the first sojourn estimating time needed for the first packet to travel through the queue from the queue input to the queue output;
determining whether to tail drop or not tail drop the first packet prior to being enqueued into the queue input based at least in part on the first sojourn time;
dropping the first packet prior to reaching the queue input when the determination is to tail drop; and
passing the first packet from the first portion to the queue input when the determination is to not tail drop.

2. The method of claim 1 further comprising determining the first sojourn time as a ratio of a number of bytes in the queue relative to an egress rate of the network buffer, the number of bytes in the queue and the egress rate being determined proximate to or before receipt of the first packet at the buffer input, including determining to tail drop the first packet when the sojourn time is greater than a threshold and to not tail drop the first packet when the sojourn time is less than or equal to the threshold.

3. The method of claim 2 further comprising determining the egress rate as a bit per second (bps) value representing a speed the network is able to dequeue packets from the queue output to the network.

4. The method of claim 3 further comprising measuring the bps value prior to the first packet reaching the buffer input.

5. The method of claim 3 further comprising estimating the bps value as a function of a plurality of egress rates measured prior to the first packet reaching the buffer input.

6. The method of claim 1 further comprising determining to tail drop the first packet if the first sojourn time is greater than a sojourn threshold and to not tail drop the first packet if the first sojourn time is less than or equal to the sojourn threshold.

7. The method of claim 1 further comprising:
determining whether a drop state is one of active and inactive;
if the drop state is active and the first sojourn time is greater than a sojourn threshold, determining to tail drop the first packet;
if the drop state is inactive and the first sojourn time is greater than the sojourn threshold, determining to not tail drop the first packet.

8. The method of claim 1 further comprising enqueuing the first packet into the queue input without adding a timestamp such that the first packet travels through the queue without addition of a time-based marking the determination is to not tail drop.

9. The method of claim 1 further comprising determining whether to tail drop or not tail drop the first packet prior to being enqueued into the queue input without processing a timestamp and without measuring a first time that the first packet is within the first portion.

10. The method of claim 9 further comprising:
measuring a second time that the first packet is within the second portion when the decision is to not tail drop;
determining whether to head drop or not head drop the first packet based on the second time;
dropping the first packet after dequeuing from the queue output and prior to being transmitted over the network when the determination is to head drop; and
transmitting the first packet from the network element to the network when the determination is to not head drop.

11. A non-transitory computer-readable medium having instructions, operable with a processor, to facilitate predictively managing a network buffer, the network buffer having a queue configured to enqueue packets at an input and to dequeue packets at an output, the non-transitory computer-readable medium comprising instructions for:
predicting sojourn time for each of a plurality of packets prior to being enqueued into the queue, the sojourn time predicting time needed for the corresponding packet to travel through the queue; and
determining whether to tail drop or not tail drop a first packet of the plurality of packets prior to being enqueued into the queue

based at least in part on the sojourn time predicted therefore;
dropping the first packet prior to reaching the queue input when the determination is to tail drop; and
passing the first packet to the queue input when the determination is to not tail drop.

12. The non-transitory computer-readable medium of claim 11 further comprising instructions for determining the sojourn times as a ratio of a number of bytes in the queue relative to an egress rate proximate in time to receipt of each packet.

13. The non-transitory computer-readable medium of claim 11 further comprising instructions for:
determining whether to tail drop or not tail drop the first packet prior to being enqueued based on a comparison of the corresponding sojourn time to a sojourn threshold.

14. The non-transitory computer-readable medium of claim 11 further comprising instructions for enqueuing the first packet when determined to be not tail drop without adding a timestamp such that the first packet travels through the queue without addition of a time-based marking.

15. A network element comprising:
a queue operable to queue a plurality of packets for subsequent transport over a link; and
a controller having a non-transitory computer-readable medium and a processor for executing a plurality of instructions stored on the non-transitory computer-readable medium to manage packet drops on a per packet basis, the plurality of instructions including instructions for:
i) determining a first packet of the plurality of packets received at the queue;
ii) predicting a first sojourn time needed for the first packet to travel through the queue;
iii) determining whether to tail drop or not tail drop the first packet prior to being enqueued into the queue input based at least in part on the first sojourn time;
iv) dropping the first packet prior to reaching the queue when the determination is to tail drop; and
v) passing the first packet to the queue input when the determination is to not tail drop.

16. The network element of claim 15 wherein the plurality of instructions include instructions for determining to tail drop the first packet when the first sojourn time is above a sojourn threshold and determining to not tail drop the first packet when the first sojourn time equal to or less than the sojourn threshold.

17. The network element of claim 16 wherein:
the queue is included as part of a buffer, the buffer being a memory for temporarily storing the packets, wherein a first portion of a capacity of the buffer is allocated for storing packets prior to entry in to the queue and a second portion of the capacity is allocated to the queue; and
the plurality of instructions includes instructions for enqueuing the first packet without adding a timestamp thereto and without associating a timestamp

therewith such that t

Assignees

• Cable Television Laboratories Inc

Inventors

• White Gregory C
• Padden Joey
• Hayakawa Takashi

Classifications

• H04L47/56

  implementing delay-aware scheduling · CPC title

• H04L43/0864

  Round trip delays · CPC title

• H04L1/1835

  Buffer management · CPC title

• H04L43/0858

  One way delays · CPC title

• H04W28/02

  Traffic management, e.g. flow control or congestion control · CPC title