Scheduling of packets in network devices

Patent metadata

Field	Value
Publication number	US-10425347-B2
Application number	US-201615553632-A
Country	US
Kind code	B2
Filing date	Mar 17, 2016
Priority date	Mar 20, 2015
Publication date	Sep 24, 2019
Grant date	Sep 24, 2019

Abstract

Network device for transmitting packets having packet properties, including at least two input-output-buffers for queuing packets in the network device; a sojourn time calculator for calculating a sojourn related time for each head packet in the at least two input-output-buffers; a sojourn related time adaptor for, based on an adaptation function assigned to the corresponding input-output-buffer, adapting the sojourn related time into an adapted time for each head packet in the at least two input-output-buffers; and a scheduler for scheduling outgoing packets based on the adapted time.

First claim

The invention claimed is:

1. Network device for transmitting packets having packet properties, comprising:
at least two input-output-buffers for queuing packets in the network device;
a sojourn time calculator for calculating a sojourn related time, based on the time a packet resides in the network device, for each head packet in the at least two input-output-buffers;
a sojourn related time adaptor for, based on an adaptation function assigned to the corresponding input-output-buffer, adapting said sojourn related time into an adapted time for each head packet in the at least two input-output-buffers;
a scheduler for scheduling outgoing packets based on the adapted time, wherein the scheduler is adapted for scheduling the head packet with the highest or lowest adapted time as next outgoing packet,
wherein the adaptation function comprises a formula (Ta=a×Ts+b), wherein Ta is the adapted time, wherein Ts is the sojourn time, and wherein a and b are predetermined first and second parameters defined for each of the at least two input-output-buffers.

2. Network device according to claim 1 , wherein the network device further comprises a classifier to classify received packets into one of the at least two input-output buffers based on the packet properties.

3. Network device according to claim 1 , wherein the sojourn time calculator and the sojourn related time adaptor are provided to periodically re-calculate at least the adapted time for each head packet in the at least two input-output-buffers.

4. Network device according to claim 3 , wherein the network device further comprises a timestamp adding means to add a timestamp to the received packets when classifying the received packets, and wherein the sojourn time calculator is provided to subtract the timestamp from a further timestamp determined at the moment of calculation.

5. Network device according to claim 1 , wherein for at least one of the at least two input-output-buffers the first parameter a deviates from 1 and/or the second parameter b deviates from 0.

6. Method for scheduling packets in a network device for transmitting packets, wherein the method comprises:
calculating a sojourn related time, based on the time a packet resides in the network device, for each head packet in the at least two input-output buffers
adapting, based on an adaptation function assigned to the corresponding input-output buffer, said sojourn related time into an adapted time for each head packet in the at least two input-output buffers;
scheduling outgoing packets based on the adapted time, wherein the step of scheduling comprises selecting the head packet with the highest or lowest adapted time as next outgoing packet,
wherein the adaptation function is calculated using a formula (Ta=a×Ts+b), wherein Ta is the adapted time, Ts is the sojourn related time, and wherein a and b are predetermined first and second parameters defined for each of the at least two input-output-buffers.

7. Method according to claim 6 , wherein at least one of the calculating and the adapting are periodically repeated to keep at least the adapted time up-to-date.

8. Method according to claim 6 , wherein the method further comprises adding a timestamp to each received packet upon classifying the packet in the buffers.

9. A non-transitory computer readable storage medium comprising instructions, which, when executed cause a data processing apparatus to carry out the steps of the method of claim 6 .

Assignees

• Provenance Asset Group Llc

Inventors

• De Schepper Koen
• Tsang Ing-Jyh

Classifications

• H04L47/6215

  Individual queue per QOS, rate or priority · CPC title

• H04L47/6205

  Arrangements for avoiding head of line blocking · CPC title

• H04L47/6285

  Provisions for avoiding starvation of low priority queues · CPC title

• H04L47/566 Primary

  Deadline varies as a function of time spent in the queue · CPC title

• H04L47/283

  in response to processing delays, e.g. caused by jitter or round trip time [RTT] · CPC title