Signalling congestion

Patent metadata

Field	Value
Publication number	US-9634916-B2
Application number	US-201314384097-A
Country	US
Kind code	B2
Filing date	Mar 11, 2013
Priority date	Mar 9, 2012
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

Abstract

Methods and apparatus are disclosed for signalling congestion being caused by data items such as packets, received at a network element such as a router, in a communications network such as the Internet, or being caused by items otherwise requiring service or capacity from a shared resource. Preferred embodiments of the method involve identifying whether or not received data items received at a network element are capable of carrying congestion indications such as ECN marks, and for those that are capable, assigning congestion indications to the data items in dependence on a queue length characterization based on a substantially current, instantaneous measurement of the length of the queue, whereas for those that are not capable, a sanction such as dropping may be applied in dependence on a different queue length characterization based on a weighted moving average of current, recent, and less recent measurements of the length of the queue.

First claim

The invention claimed is:

1. A method of signalling congestion being caused by data items received at a network element in a communications network, the network element having a queue having a length, the method comprising steps of:
identifying, in respect of each of a plurality of received data items, whether or not said data item is capable of carrying a congestion indication;
determining a first queue length characterisation, said first queue length characterisation being determined according to a first function such as to depend on measurements inferring the length of the queue at a plurality of different times;
determining a second queue length characterisation, said second queue length characterisation being determined according to a second function such as to depend on a current or recent measurement inferring the length of the queue, the most recent queue length being more strongly weighted in said second function than it is in said first function;
applying a sanction in respect of data items identified as not being capable of carrying congestion indications in dependence on said first queue length characterisation; and
assigning congestion indications to data items identified as being capable of carrying congestion indications in dependence on said second queue length characterisation.

2. A method of signalling congestion according to claim 1 , wherein said first function is such that the first queue length characterisation is determined as a moving average of the length of the queue at a plurality of different times.

3. A method of signalling congestion according to claim 2 wherein the first queue length characterisation is determined as a weighted moving average of the length of the queue, the first function being such that greater weight is given to more recent measurements of the length of the queue.

4. A method of signalling congestion according to claim 3 wherein the first queue length characterisation is determined as an exponentially-weighted moving average of the length of the queue.

5. A method of signalling congestion according to claim 1 , wherein said second function is such that the second queue length characterisation is the current or most recent queue length, or is indicative thereof.

6. A method of signalling congestion according to claim 1 , wherein said second function is such that the second queue length characterisation is determined as a weighted moving average of the length of the queue at a plurality of different times, the second function giving sufficient weight to the most recent measurement of the length of the queue as to be indicative of current queue length.

7. A method of signalling congestion according to claim 1 , wherein the length of the queue at a particular time is indicative of the size of a backlog of data items requiring processing and/or forwarding by the network element at that time.

8. A method of signalling congestion according to claim 1 , wherein the step of applying a sanction in respect of data items identified as not being capable of carrying congestion indications comprises performing one or more of the following actions in respect of one or more of said data items in dependence on said first queue length characterisation: dropping; truncating; delaying; de-prioritising; re-routing; forwarding to a destination other than an intended destination; issuing an out-of-band congestion notification.

9. A method of signalling congestion according to claim 1 , the method further comprising forwarding respective data items identified as not being capable of carrying congestion indications to an intended destination thereof in the event that no sanction is applied in respect thereof.

10. A method of signalling congestion according to claim 1 , the method further comprising forwarding respective data items identified as being capable of carrying congestion indications to an intended destination, said data items to which congestion indications have been assigned carrying those congestion indications.

11. A method of signalling congestion according to claim 1 , wherein the step of identifying comprises identifying, in respect of said data items, whether or not they are capable of carrying an Explicit Congestion Notification indication.

12. A method of signalling congestion according to claim 1 , wherein the queue is a virtual queue.

13. A method of signalling congestion according to claim 1 , wherein data items identified as being capable of carrying congestion indications are enqueued to a first buffer and data items identified as not being capable of carrying congestion indications are enqueued to a second buffer, and wherein the queue is a composite queue the length of which is inferred from monitoring the first and second buffers.

14. A method of signalling congestion according to claim 1 , wherein the queue is a composite queue the length of which is inferred from monitoring buffers at a plurality of network elements.

15. A method of signalling congestion according to claim 1 , wherein one or both of the steps of applying a sanction and assigning congestion indications in order to signal congestion is/are performed probabilistically in dependence on the applicable queue length characterisation.

16. A method of signalling congestion being caused by data items received at a network element in a communications network, the network element having a queue having a length, the method comprising steps of:
identifying, in respect of each of a plurality of received data items, whether or not said data item is capable of carrying a congestion indication;
determining, at each of a plurality of different times, respective queue length characterisations, each said queue length characterisation being determined according to a function such as to depend on a current or recent measurement inferring the length of the queue;
assigning congestion indications to data items identified as being capable of carrying congestion indications with a probability dependent on the most recent of said queue length characterisations; and
applying a sanction in respect of data items identified as not being capable of carrying congestion indications with a probability dependent on probabilities determined in dependence on queue length characterisations determined at a plurality of different times, the probability determined in dependence on the most recent queue length characterisation being more strongly weighted in the assigning of congestion indications to data items identified as being capable of carrying congestion indications than it is in the applying of sanctions in respect of data items identified as not being capable of carrying congestion indications.

17. A method of signalling congestion being caused by items requiring service or capacity from a shared resource, the shared resource having a queue having a length, the method comprising steps of:
identifying, in respect of each of a plurality of said items, whether or not said item is capable of carrying a congestion indication;
determining a first queue length characterisation, said first queue length characterisation being determined according to a first function such as to depend on measurements inferring the length of the queue at a plurality of different times;
determining a second queue length characterisation, said second queue length characterisation being determined according to a second function such as to depend on a current or recent measurement inferring the length of the queue, the most recent queue length being more strongly weighted in said second function than it is in said first functio

Assignees

• British Telecomm

Inventors

• Briscoe Robert John
• Di Cairano-Gilfedder Carla

Classifications

• H04L47/30

  in combination with information about buffer occupancy at either end or at transit nodes · CPC title

• H04L47/12

  Avoiding congestion; Recovering from congestion · CPC title

• H04L47/326 Primary

  with random discard, e.g. random early discard [RED] · CPC title

• H04L47/31

  by tagging of packets, e.g. using discard eligibility [DE] bits · CPC title

• H04L43/0876

  Network utilisation, e.g. volume of load or congestion level · CPC title