Methods, queueing system, network element and network system for queueing and processing of packets

1. A method for queueing packets in a queueing system at a network element in a packet-switched network,

wherein each packet of said packets is sent from a source in said packet-switched network to a destination in said packet-switched network via said network element,

wherein each packet of said packets comprises timing information representing a remaining time until a deadline associated with delivery of said packet at its destination;

wherein said queueing system comprises:

a plurality of N queues, wherein each queue of said plurality of N queues is configured for buffering at least one packet of said packets, and wherein said plurality of N queues has a cyclic order;

wherein said method comprises:

keeping track of a pointer, wherein at a first point in time said pointer points to a queue of said plurality of N queues;

after a second point in time succeeding said first point in time, repeatedly incrementing said pointer over said plurality of N queues, according to said cyclic order of said plurality of N queues, after each passing of a scheduling interval S, wherein said scheduling interval S represents an amount of time;

enqueueing each packet of said packets in a queue, of said plurality of N queues, that differs from the queue of said plurality of N queues to which said pointer is pointing, based on said packet's timing information and taking into account said cyclic order of said plurality of N queues,

wherein enqueueing each packet of said packets comprises:

in response to the remaining time represented by the timing information of said packet exceeding a lower threshold and being less than or equal to an upper threshold, enqueueing said packet in an i-th queue of said plurality of N queues, wherein the queue to which said pointer is pointing is excluded, wherein i is counted one-based according to said cyclic order of said plurality of N queues starting from a queue following the queue to which said pointer is pointing, wherein said lower threshold is equal or essentially equal to S*(i−1) and said upper threshold is equal or essentially equal to S*i; and

dequeueing enqueued packets from said plurality of N queues, while prioritizing dequeueing from the queue of said plurality of N queues to which said pointer is pointing.

2. The method of claim 1 , wherein prioritizing dequeueing from the queue of said plurality of N queues to which said pointer is pointing comprises:

dequeueing enqueued packets from the queue of said plurality of N queues to which said pointer is pointing, in response to the queue of said plurality of N queues to which said pointer is pointing containing any enqueued packets; and

progressively attempting to dequeue enqueued packets from next queues of said plurality of N queues following the queue of said plurality of N queues to which said pointer is pointing, according to said cyclic order of said plurality of N queues, in response to the queue of said plurality of N queues to which said pointer is pointing being empty.

3. The method of claim 1 , wherein said timing information of a packet is indicated in a header field of said packet.

4. The method of claim 3 , wherein said timing information of a packet is indicated in a header field of said packet meant for identifying differentiated services for said packet.

5. The method of claim 1 , wherein said timing information of a packet is indicated using B bits, where B is less than or equal to 6.

6. The method of claim 1 , wherein each packet's remaining time falls within a pre-determined permissible time range R; and

wherein said scheduling interval S represents an amount of time equal or essentially equal to said pre-determined permissible time range R divided by N−1.

7. The method of claim 1 , comprising dynamic adjustment of said queueing system by:

monitoring at least one buffering parameter of said queueing system, wherein said at least one buffering parameter comprises any one or more of the following: a number of filling levels of said plurality of N queues; and a number of packet drops in said queueing system;

calculating a new scheduling interval S′ for replacing said scheduling interval S, based on said at least one buffering parameter;

calculating a new number N′ for replacing said number N of said plurality of N queues, based on said at least one buffering parameter; and

adapting said queueing system according to said new scheduling interval S′ and said new number N′.

8. The method of claim 1 further comprising:

receiving each packet of said packets;

associating each packet of said packets with an arrival timestamp from a clock;

queueing each packet of said packets according to the method of claim 1 , wherein said queueing comprises dequeueing packets;

associating each dequeued packet with a departure timestamp from said clock; and

dispatching each dequeued packet from said network element, based on a difference between its departure timestamp and its arrival timestamp.

9. The method of claim 8 , wherein said dispatching comprises:

determining whether said dequeued packet has missed its deadline, based on comparing the timing information of said dequeued packet with said difference; and

in response to determining that said dequeued packet has not missed its deadline, updating the timing information of said dequeued packet based on said difference and transmitting said dequeued packet to its destination; and

in response to determining that said dequeued packet has missed its deadline, dropping said dequeued packet or transmitting said dequeued packet towards its destination.

10. The method of claim 8 , comprising:

estimating a packet delivery time for delivering a packet to its destination; and

updating the timing information of said packet, by subtracting said estimated packet delivery time from said packet's remaining time.

11. A queueing system for queueing packets at a network element in a packet-switched network,

wherein each packet of said packets is sent from a source in said packet-switched network to a destination in said packet-switched network via said network element,

wherein each packet of said packets comprises timing information representing a remaining time until a deadline associated with delivery of said packet at its destination;

wherein said queueing system comprises:

a plurality of N queues, wherein each queue of said plurality of N queues is configured for buffering at least one packet of said packets, and wherein said plurality of N queues has a cyclic order;

a pointer, wherein at a first point in time said pointer points to a queue of said plurality of N queues;

a scheduler configured for, after a second point in time succeeding said first point in time, repeatedly incrementing said pointer over said plurality of N queues, according to said cyclic order of said plurality of N queues, after each passing of a scheduling interval S, wherein said scheduling interval S represents an amount of time;

an enqueueing module configured for enqueueing each packet of said packets in a queue, of said plurality of N queues that differs from the queue of said plurality of N queues to which said pointer is pointing, based on said packet's timing information and taking into account said cyclic order of said plurality of N queues,

wherein enqueueing each packet of said packets comprises:

in response to the remaining time represented by the timing information of said packet exceeding a lower threshold and being less than or equal to an upper threshold, enqueueing said packet in an i-th queue of said plurality of N queues, wherein the queue to which said pointer is pointing is excluded, wherein i is counted one-based according to said cyclic order of said plurality of N queues starting from a queue following the queue to which said pointer is pointing, wherein said lower threshold is equal or essentially equal to S*(i−1) and said upper threshold is equal or essentially equal to S*i; and

a dequeueing module configured for dequeueing enqueued packets from said plurality of N queues, while prioritizing dequeueing from the queue of said plurality of N queues to which said pointer is pointing.

12. A network element for the queueing system of claim 11 , for processing packets in a packet-switched communication network, the network element comprising:

a clock;

an input module configured for:

receiving each packet of said packets; and

associating each packet of said packets with an arrival timestamp from said clock;

a queueing system for queueing each packet of said packets according to the queueing system of claim 11 ;

an output module configured for:

associating each dequeued packet with a departure timestamp from said clock; and

dispatching each dequeued packet from said network element, based on a difference between its departure timestamp and its arrival timestamp.

13. The method of claim 8 , wherein said output module is configured for:

determining whether said dequeued packet has missed its deadline, based on comparing the timing information of said dequeued packet with said difference; and

in response to determining that said dequeued packet has not missed its deadline, updating the timing information of said dequeued packet based on said difference and transmitting said dequeued packet to its destination; and

in response to determining that said dequeued packet has missed its deadline, dropping said dequeued packet or transmitting said dequeued packet towards its destination.

14. A non-transitory computer readable medium storing instructions, which when executed by a computer, cause the computer to perform the method of claim 1 .