Re-marking of packets for queue control

• US 9,985,899 B2
• Filed: 03/27/2014
• Issued: 05/29/2018
• Est. Priority Date: 03/28/2013
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Briscoe, Robert John
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): Asefa, Debebe
• Application Number:
  US14/780,685
• Publication Number:
  US 20160057065A1
• Time in Patent Office: 1,524 Days
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/624 Altering the ordering of packets in an individual queue

Abstract

A method and apparatus for changing a packet tag status value from a first value to a different value upon said packet arriving at a buffer if there already is a packet in the buffer queue having the same first status value. A sequence of tag status values (112) in packets received at an end node is used to determine the queue length of the buffer in the packet network. An end node can thereafter adapt its sending rate to the rate of the buffer.

Claims

1. A method for handling packets at a node in a packet network, the node having a queue for storing one or more packets, the method comprising:

receiving at the queue a first packet carrying a status tag set to a first status value;

determining that a stored packet already in the queue at the time of arrival of the first packet has upon leaving the queue a status tag set to the same first status value;

changing the tag status value of the first packet to a different status value;

dequeuing the stored packet from the queue;

receiving at the queue a second packet carrying a status tag set to the first status value;

checking if any packet already in the queue at the time of arrival of the second packet has upon leaving the queue a status tag set to the same first status value;

transmitting a sequence of tag status values to another node in the packet network, the sequence including;

a status tag associated with the stored packet set to the first status value,

a status tag associated with the first packet set to the different status value, and

a status tag associated with the second packet set to the first status value.

2. A method according to claim 1 further comprising stamping the received first packet with an indicator tsi indicating when the first packet arrived to the queue;

storing a further indicator t0 indicating when the latest packet having a status tag set to the first status value left the queue;

comparing the indicator tsi of the received first packet with the stored indicator t0 and if tsi is smaller than or equal to t0 changing the tag status of the received first packet to the different status value and if tsi is greater than t0 keeping the first status value.

3. A method for estimating a length of a queue of packets awaiting handling at a network node, which network node is arranged to operate in accordance with the method of claim 1, said method comprising:

receiving at another node the sequence of tag status values associated with the first packet, second packet and stored packets which have been routed via said network node, where said tag status value is set to either a first or a different status value; and

estimating the length of the queue at the time of arrival of the second packet from said sequence of tag status values.

4. A method according to claim 3 further comprising estimating the queue length by either determining the spacing between two packets in the sequence having their respective status tag set to said first status value, wherein said spacing represents the queue length at the instant the second packet arrived to the intermediate node in said packet network or by determining the number, length or duration of consecutive status tags set to the different status value in the sequence.

5. A method according to claim 3 comprising a receiver node estimating the queue length from said sequence of tag status values or alternatively, the receiver node sending an encoding of the sequence of tag values to a sender node and the sender node estimating the queue length.

6. A method according to claim 3 wherein if there is more than one flow in the packet network, the sender node of each flow estimating its own contribution to an aggregate queue length by varying its own data rate and correlating the different data rates with changes in the aggregate queue length.

7. A method according to claim 3 comprising a sender node adapting its transmission rate based on the determined queue length.

8. A method according to claim 3 further comprising a sender node sending out a train of packets within which the inter-packet spacing gets closer and closer together;

determining from the sequence of status values how much of a queue that builds at a range of rates around the average rate, and adapting a sending rate up to the currently available capacity of a bottleneck node.

9. A method according to claim 3 wherein if the packets have traversed a sequence of network nodes, each comprising a queue, the node estimating the length of the longest queue.

10. A non-transitory computer readable storage medium storing computer program or suite of computer programs executable by a processor to cause the processor to perform the method of claim 3.

11. A non-transitory computer readable storage medium storing a computer program or a suite of computer programs executable by a computer processor to cause the computer processor to perform the method of claim 1.

12. The method according to claim 1, further comprising estimating the length of the queue from said sequence of tag status values, where the tag status values are set to either the first or the different status value.

13. The method according to claim 1, further comprising adapting a packet transmission rate of the node based on a length of the queue estimated based on the sequence of tag status values.

14. A node for handling packets in a packet network comprising:

an interface arranged in operation to receive and enqueue a first and second packet each having a status tag set to a first status value;

a queue for storing one or more packets; and

a computer processor for executing instructions so as to provide a module arranged in operation to;

determine that a stored packet already in the queue at the time of arrival of the first packet has upon leaving the queue a status tag set to the same first status value;

change the tag status value of the first packet to a different status value;

dequeue the stored packet from the queue;

receive at the queue a second packet carrying a status tag set to the first status value;

check if any packet already in the queue at the time of arrival of the second packet has upon leaving the queue a status tag set to the same first status value;

transmit a sequence of tag status values to another node in the packet network, the sequence including;

a status tag associated with the stored packet set to the first status value,

a status tag associated with the first packet set to the different status value, and

a status tag associated with the second packet set to the first status value.

15. A node according to claim 14 further comprising a store for storing an indicator t0 indicating when the latest packet having the status tag set to the first status value left the queue and wherein the module is further arranged in operation to stamp the received first packet with an indicator tsi indicating when the first packet arrived at the queue and to compare the indicator tsi of the received first packet with the stored indicator t0 and if tsi is smaller than or equal to t0 to change the tag status of the received first packet to the different status value or if tsi is greater than t0 to keep the first status value.

16. A node in a packet network arranged in operation to estimate a length of a queue of packets awaiting handling at a network node, which network node is adapted to operate according to claim 15, said node comprising:

an interface arranged in operation to receive the sequence of tag status values associated with the first packet, second packet and stored packets which have been routed via said network node, where said tag status value is set is to either a first or a different status value; and

a module arranged in operation to estimate the length of the queue at the time of arrival of the second packet from said sequence of tag status values.

17. A node according to claim 16 wherein the module is further arranged in operation to estimate the queue length by either determine the spacing between two packets in the sequence having their respective status tag set to said first status value, wherein said spacing represents the queue length at the instant the second packets arrived at the intermediate node in said packet network;

or to estimate the queue length from the number, length or duration of consecutive status tags in the sequence set to the different status value.

18. A node according to claim 14, wherein the computer processor executes instructions so as to provide a module arranged in operation to adapting a packet transmission rate of the node based on a length of the queue estimated based on the sequence of tag status values.