Patent Description:
In some nodes of a communication network, data packets are buffered in a queue before being forwarded to a next node. This results in a queuing delay. These nodes can experience traffic congestion when the rate of packets received exceeds the rate the node can handle. Active Queue Management, AQM, can manage congestion and reduce the queuing delay by marking packets upon detecting or predicting congestion. The marked packets can trigger a congestion control response in a sender that results in an adjustment of the packet transmission rate.

In traditional or unscalable congestion control a multiplicative reduction of the packet transmission rate is applied. As such, the queuing delay and utilization in the node can vary substantially when the traffic flow rate changes.

In scalable congestion control the packet transmission rate is reduced proportionally to the amount of received marked packets. This results in low latency communication because the queuing delay is limited even when the traffic flow rate scales as the average time from one congestion signal to the next remains invariant. The transition from unscalable to scalable congestion control will occur gradually, as it requires substantial adaptations to the senders, the nodes, and the receivers. <CIT> is an example of such a scalable congestion control mechanism.

The scope of protection sought for various embodiments of the invention is set out by the claims. The example embodiments and features described in this specification that do not fall within the scope of the claims, if any, are to be interpreted as examples useful for understanding various embodiments of the invention.

Amongst others, it is an object of embodiments of the invention to provide a solution for managing data traffic congestion in a network communication node.

This object is achieved, according to a first example aspect of the present disclosure, by a method for managing data traffic congestion in a network communication node. The method comprises maintaining a marking probability based on a marking ratio indicative of a ratio between a change in packets responsible for congestion in a network queue in the network communication node, and a change in a total number of packets processed by the network queue. The method further comprises classifying packets processed by the network queue as scalable packets or other packets based on an identifier included in the packets; wherein the scalable packets support scalable congestion control. The method further comprises marking the scalable packets responsible for congestion in the network queue with a congestion mark to signal data traffic congestion; and marking the other packets that support unscalable congestion control with the congestion mark based on the marking probability.

Thus, scalable packets responsible for congestion are immediately marked with the congestion mark. The other packets that support unscalable congestion control are marked with a smoothed signal according to the marking probability based on the marking ratio. The marking probability allows to determine whether an other packet should be marked to signal data traffic congestion. The marking ratio is indicative of a marking density that would be applied to packets in a scalable traffic queue reserved for scalable packets, i.e. a queue without other packets. In other words, the marking density that is applied to scalable packets for scalable congestion control is converted to a marking density for unscalable congestion control that is applied to the other traffic. By this coupling of the respective marking densities for scalable packets and other packets, fairness can be achieved in a single queue, i.e. network resources can be fairly distributed between the scalable packets and other packets in a shared queue.

The marking density for the scalable packets and for the other packets are determined by identifying or tracking packets responsible for congestion in the network queue, i.e. packets that cause a congestion parameter such as the queuing delay or the queue size to exceed a certain value. This allows to determine the marking densities without substantial convergence time, e.g. compared to a proportional integral, PI, control loop. By the marking, the scalable and unscalable congestion controls in various senders can track the capacity of the network communication node. This allows to maintain a low queue size, and thus, a low queuing delay regardless of the packet type.

It is an advantage that the marking can reduce jitter and that starvation of the network queue can be avoided. It is a further advantage that a network queue can be shared between scalable packets and other packets without affecting latency, allowing other traffic to benefit from the low latency communication provided by scalable traffic queues without latency penalties. It is a further advantage that the method is compatible with existing transport protocols that support scalable congestion control, e.g. the data centre transmission control protocol, DCTCP, or QUIC, and existing transport protocols that support unscalable congestion control, e.g. the transmission control protocol, TCP. It is a further advantage that the method is compatible with existing scalable congestion controls, e.g. BBRv2, Prague, SCReAM, and unscalable congestion controls, e.g. New Reno and CUBIC.

According to an example embodiment, the maintaining can further comprise identifying packets as responsible for congestion in the network queue before enqueuing the packet in the network queue.

The change in packets responsible for congestion can thus be updated or determined before adding the packet to the network queue, e.g. before segmentation. The network communication node can additionally update the change in total number of packets processed by the network queue, maintain the marking probability, classify the packets processed by the network queue, and/or perform the marking before enqueuing the packet in the network queue. This allows to implement the method in network communication nodes that aggregate the received packets upon enqueuing, or in network communication nodes with an inaccessible network queue, e.g. a queue that resides in an inaccessible circuitry such as a system on chip, SOC.

According to a further example embodiment, the maintaining can further comprise identifying packets as responsible for congestion in the network queue upon dequeuing the packet from the network queue.

The change in packets responsible for congestion can thus be updated or determined upon dequeuing the packet from the network queue, e.g. before serialization. The network communication node can additionally update the change in total number of packets processed by the network queue, maintain the marking probability, classify the packets processed by the network queue, and/or perform the marking upon dequeuing the packet from the network queue. This allows to implement the method in software applications, e.g. in a queuing discipline, qdisc, of a Linux network interface.

According to a further example embodiment, packets can be identified as responsible for congestion in the network queue in response to a size of the network queue exceeding a size threshold.

The size threshold represents a maximum allowable size of the network queue, e.g. a maximum amount of packets or a maximum amount of data that can be present in a queue without resulting in congestion. A packet received by the network communication node can thus be identified as responsible for congestion if enqueuing that packet results in a queue size that exceeds the size threshold.

According to a further example embodiment, packets can be identified as responsible for congestion in the network queue in response to a sojourn time of the packets in the network queue exceeding a time threshold.

The sojourn time of a packet can be indicative of the time needed for the packet to travel through the network queue, i.e. the difference between the enqueue time and the dequeue time of the packet. The sojourn time can be measured, e.g. upon dequeuing a packet, or can be estimated, e.g. based on the size of a packet and the bit rate of the network communication node upon enqueuing the packet. The time threshold represents a maximum allowable sojourn time of a packet without resulting in congestion of the network queue. A packet forwarded or outputted by the network communication node can thus be identified as responsible for congestion if the sojourn time of the packet exceeds the time threshold upon dequeuing the packet. This has the further advantage that the method can be independent of the rate at which packets are received by the network communication node, i.e. the serving rate, and/or variations in the serving rate.

According to a further example embodiment, the method can further comprise, before enqueuing the packets in the network queue, flagging the scalable packets for marking and flagging the other packets for marking based on the marking probability; and, upon dequeuing, performing the marking with the congestion mark for packets that are flagged for marking and are identified as responsible for congestion in the network queue.

Packets received by the network communication node can thus first be classified as scalable packets or other packets. The classified packets can then be flagged for marking, e.g. by adding an identifier, stamp, or flag according to their classification or packet type before enqueuing the packets in the network queue. All scalable packets receive a flag, while the other packets are flagged according to the maintained marking probability. Upon dequeuing, the packet can then be checked for the presence of the flag in addition to identifying whether the packet is responsible for congestion. This allows to reduce the performed operations, the execution time, and the consumed processing power of the method in the dequeue pipeline. This further allows to implement the method in network communication nodes with a high throughput or low serialization time per packet, i.e. with a limited available time budget in the dequeue pipeline for marking.

According to a further example embodiment, the method can further comprise dropping packets in response to a size of the network queue exceeding a first drop threshold, or in response to a sojourn time of the packets in the network queue exceeding a second drop threshold.

Dropping a packet refers to substantially removing or discarding the packet from memory. This results in packet loss as received packets may not be enqueued in the network queue or dequeued packets may not be forwarded or transmitted by the network communication node. Marked packets and/or unmarked packets can be considered for dropping. The first drop threshold can preferably be larger than the size threshold. The second drop threshold can preferably be larger than the time threshold. This can make the network queue more resilient against sudden changes in queuing delay, e.g. due to a plurality of traffic flows starting up, unresponsive traffic flows, or a sudden burst of packets.

According to a further example embodiment, the method can further comprise dropping the other packets that are eligible for marking based on the marking probability and that do not supportunscalable congestion control.

Other packets can thus support unscalable congestion control or not. This can, for example, be determined from the identifier included in the packets. Unscalable congestion control can, for example, not be supported if the sender of the packet is not provided with a congestion control algorithm, or if the traffic transport protocol of the packet does not support marking the packet with the congestion mark. This further allows to manage the congestion in the network queue in the presence of other packets that do not support congestion control. It is a further advantage that futile marking of packets that do not support scalable congestion control is avoided.

According to a further example embodiment, the congestion mark and the identifier are included in an explicit congestion notification, ECN, field of an internet protocol, IP, header of the packet.

The identifier in the ECN field can for example have a distinct value, e.g. predetermined bits, to indicate a scalable packet, an other packet supporting unscalable congestion control, or an other packet not supporting unscalable congestion control.

According to a further example embodiment, the marking can further comprise overwriting the identifier included in the explicit congestion notification, ECN, field with the congestion mark.

In other words, the value or bits included in the ECN field of the IP header can be switched or adjusted to a predetermined value to mark the packet with the congestion mark.

According to a further example embodiment, the maintaining of the marking probability comprises updating the marking probability and the marking ratio at a predetermined time interval, or at a predetermined change in the total number of packets processed by the network queue.

In other words, the marking probability is based on the change in packets responsible for congestion and the change in the total number of packets processed by the network queue during a predetermined interval. This allows to periodically derive or calculate the marking probability rather than for every packet processed by the queue. This has the further advantage that it can limit the execution time and the consumed processing power of the method.

According to a further example embodiment, the marking probability is based on a moving average of the marking ratio.

The moving average can for example, amongst others, be a simple moving average, a cumulative average, a weighted moving average, an exponential moving average, or any other moving average known to the skilled person.

According to a second example aspect, a network communication node is disclosed configured to manage data traffic congestion. The network communication node is configured to process packets having an identifier indicative of scalable packets or other packets, wherein the scalable packets support scalable congestion control. The network communication node is further configured to maintain a marking probability based on a marking ratio indicative of a ratio between a change in packets responsible for congestion in a network queue in the network communication node, and a change in a total number of packets processed by the network queue. The network communication node is further configured to classify packets processed by the network queue as scalable packets or other packets based on the identifier included in the packets. The network communication node is further configured to mark the scalable packets responsible for congestion in the network queue with a congestion mark to signal data traffic congestion; and mark the other packets that support unscalable congestion control with the congestion mark based on the marking probability.

According to a third example aspect, a computer program product is disclosed according to claim <NUM>.

According to a fourth example aspect, a computer readable storage medium is disclosed according to claim <NUM>.

<FIG> shows an example traffic flow of data packets in selected components of a communication network <NUM>. A traffic flow can be understood as a collection of data packets <NUM>, <NUM>, <NUM>, <NUM>, <NUM> that are sent from a sender <NUM>, i.e. a source node, to a receiver <NUM>, i.e. a destination node. The communication network <NUM> can include one or more senders <NUM> that transmit data as packets <NUM>, <NUM>, <NUM>, <NUM>, <NUM> to a destination node, i.e. receiver <NUM>. The data packets <NUM>, <NUM>, <NUM>, <NUM>, <NUM> can comprise information such as, for example, emails, voice calls, or streaming video. The sender <NUM> can for example, amongst others, be a server or router device. The receiver <NUM> can for example be a laptop, a smartphone, a tablet, or any other destination node in a communication network known to the skilled person. The packets <NUM>, <NUM>, <NUM>, <NUM>, <NUM> travel through one or more intermediate network nodes such as network communication node <NUM>. Network communication node <NUM> receives the transmitted packets <NUM> and forwards the packets <NUM> on the next leg of their journey, i.e. towards the intended receiver <NUM>.

The network communication node <NUM> can for example, amongst others, be a router or a switch that has input and output ports coupled to a physical transmission medium, e.g. an optical fibre, a coax cable, a copper wire, or an air interface. The network communication node <NUM> can further comprise one or more network queues <NUM> for enqueuing <NUM> and dequeuing <NUM> packets <NUM>, <NUM> at the ports to control the reception and transmission of packets <NUM>, <NUM> on an established communication link.

The communication network <NUM> can experience data traffic congestion when the rate of sent packets <NUM>, i.e. the amount of packets <NUM> sent by sender <NUM> in a certain time interval, exceed what the network communication node <NUM> can handle. This results in a build-up of excess packets <NUM> in the network communication node <NUM> as packets have to wait in the network queue <NUM> before being forwarded to the receiver <NUM>. Therefore, the network communication node <NUM> can be configured to manage or control data traffic congestion in the communications network <NUM>, typically referred to as active queue management, AQM.

To this end, an AQM module <NUM> in the network communication node <NUM> selectively drops or marks packets <NUM>, <NUM>, <NUM>, <NUM>, <NUM> under certain conditions to control congestion. In particular, the AQM module <NUM> can apply marks to packets when congestion is detected and/or predicted, i.e. when queue <NUM> is overflowing or is about to overflow and, thus, that the excess packets <NUM> are experiencing or about to experience excessive queueing delays. The receivers <NUM> can be configured to reflect these applied marks, i.e. congestion signals, back to the respective sender <NUM> of the packet. Based on the received marks, a congestion control algorithm can then adjust the packet transmission rate of the sender <NUM> to avoid congestion and the resulting network issues such as, for example, packet loss, retransmission, high latency, and/or jitter.

Traditional congestion control algorithms, also referred to as classic or unscalable congestion control, apply a multiplicative reduction of the packet transmission rate for every marked packet that is reflected to the sender <NUM>, e.g. halve the transmission rate for every marked packet. By this multiplicative reduction, the utilization and queueing delay in the network queue will vary substantially when traffic flow rates increase. Unscalable congestion control algorithms can include, for example, Tahoe, Reno, New Reno, Vegas, Hybla, binary increase congestion control, BIC, CUBIC, bottleneck bandwidth and round-trip propagation time, BBR, or any other unscalable congestion control algorithm known to the skilled person. Packets sent according to a protocol that supports unscalable congestion control, e.g. transmission control protocol, TCP, can be referred to as unscalable packets.

Scalable congestion control algorithms apply a reduction of the packet transmission rate proportionally to the amount of reflected marked packets. In scalable congestion control, the average time from one congestion signal to the next, i.e. the recovery time, remains invariant as the flow rate scales. As scalable congestion control allows senders <NUM> to closely track the link capacity of the network communication node and reduce the queuing delay, low latency communication with limited jitter can be achieved. Scalable congestion control can include, amongst others, BBRv2, Prague, and SCReaM. Packets sent according to a protocol that supports scalable congestion control, e.g. data centre transmission control protocol, DCTCP, or QUIC, can be referred to as scalable packets.

Because of the difference in packet transmission rate adjustment at the sender <NUM>, the unscalable packets and the scalable packets require a different marking strategy, i.e. a different marking density. As unscalable and scalable packets coexist in communication networks <NUM>, it can be desirable to provide network communication node <NUM> with an AQM that is compatible with both packet types.

<FIG> shows steps <NUM> according to an example embodiment for managing data traffic congestion in the network communication node of <FIG> that is compatible with scalable packets and unscalable packets.

In a first step <NUM>, a packet <NUM> processed by the network queue is classified as a scalable packet or as an other packet. A processed packet can refer to a packet <NUM> that is received by the network communication node but not yet enqueued in the network queue <NUM>, e.g. before packet segmentation. Alternatively, a processed packet can also refer to a packet <NUM> that is dequeued from the network queue but not yet transmitted or forwarded to the respective receiver, e.g. before packet serialization. Network queue <NUM> may further be a real network queue or a virtual network queue.

The classifying in step <NUM> is based on an identifier <NUM> that is included in the processed packet <NUM> in addition to data <NUM>, e.g. a message, a document, or a video stream. The identifier <NUM> can, for example, be added to the packet by the sender or by the congestion control algorithm of the sender. The identifier <NUM> can be included in an explicit congestion notification, ECN, field of an internet protocol, IP, header of the packet <NUM>. Such an identifier <NUM> in the ECN field can have a distinct value, e.g. predetermined bits, to indicate a scalable packet, an other packet supporting unscalable congestion control, or an other packet not supporting unscalable congestion control. For example, the ECN field can contain identifier bits 0b01 to indicate a scalable packet, 0b10 to indicate an other packet supporting unscalable congestion control, and 0b00 to indicate an other packet not supporting unscalable congestion control.

In a second step <NUM>, a marking probability <NUM> is maintained based on a marking ratio. The marking probability allows to determine whether an other packet should be used to signal data traffic congestion, i.e. if the packet should be marked. The marking ratio is derived as the ratio between the change in packets responsible for congestion Δpacketscongestion <NUM> and the change in total number of packets processed by the network queue Δpacketsprocessed <NUM>, i.e. <MAT>. The change in total number of packets processed by the network queue Δpacketsprocessed <NUM> can for example be tracked by updating a counter when a packet <NUM> is enqueued <NUM> in the network queue <NUM> or dequeued <NUM> from the network queue <NUM>. The change in packets responsible for congestion Δpacketscongestion <NUM> can for example be tracked by updating a counter when a packet <NUM> is identified as responsible for congestion in the network queue <NUM>. A packet responsible for congestion <NUM> can refer to a packet that causes a congestion parameter, e.g. the queuing delay <NUM> or the queue size <NUM>, to exceed a threshold <NUM>, <NUM>.

According to an example embodiment, identifying packets <NUM> as responsible for congestion in the network queue can be performed before enqueuing <NUM> the packet in the network queue <NUM>. As such, packets can be identified as responsible for congestion when a size <NUM> of the network queue exceeds a size threshold <NUM>. For example, the build-up of excess packets <NUM> in the network queue <NUM> can be identified as packets responsible for congestion. The size threshold <NUM> represents a maximum allowable size of the network queue, i.e. a maximum amount of packets <NUM> or a maximum amount of data that can be present in the queue without resulting in congestion. The size threshold <NUM> can for example be <NUM> B at a bit rate of <NUM> Mbps. A packet <NUM> received by the network communication node can thus be identified as responsible for congestion when enqueuing <NUM> that packet results in a queue size <NUM> that exceeds the size threshold <NUM>. This allows implementation in network communication nodes that aggregate the received packets <NUM> upon enqueuing <NUM>, or in network communication nodes with an inaccessible network queue <NUM>, e.g. a queue that resides in an inaccessible circuitry such as a closed or protected system on chip, SOC.

According to an alternative example embodiment, identifying packets <NUM> as responsible for congestion in the network queue can be performed upon dequeuing <NUM> the packet <NUM> from the network queue <NUM>. As such, a packet can be identified as responsible for congestion when a sojourn time <NUM> exceeds a time threshold <NUM>. For example, the build-up of excess packets <NUM> in the network queue <NUM> can be identified as packets responsible for congestion. The sojourn time <NUM> of a packet <NUM> is indicative of the time needed for the packet to travel through the network queue <NUM>, i.e. the difference between the enqueue time <NUM> and the dequeue time <NUM> of the packet <NUM>. This difference, i.e. the sojourn time <NUM>, can for example be measured upon dequeuing <NUM> the packet <NUM>. The time threshold <NUM> represents a maximum allowable sojourn time of a packet without resulting in congestion of the network queue <NUM>. The time threshold <NUM> can for example be <NUM>. A packet forwarded or outputted by the network communication node can thus be identified as responsible for congestion when the sojourn time <NUM> of the packet <NUM> exceeds the time threshold <NUM> upon dequeuing <NUM> the packet. This allows to implement the method in software applications, e.g. in a queuing discipline, qdisc, of a Linux network interface. This has the further advantage that the method can be independent of the rate at which packets are received by the network communication node, i.e. the serving rate, and/or variations in the serving rate.

It will be apparent that the congestion parameter in the example embodiments described above is interchangeable as the sojourn time <NUM> can be converted to a queue size <NUM>, and vice-versa, based on the bit rate of the network communication node. In other words, packets responsible for congestion <NUM> can also be identified based on the sojourn time <NUM> before enqueuing <NUM> the packet, and packets responsible for congestion <NUM> can also be identified based on the queue size <NUM> upon dequeuing <NUM> the packet. It will further be apparent that the maintaining of the marking probability <NUM> in step <NUM> and the identifying <NUM> of packets responsible for congestion in the network queue can be performed substantially before the classifying in step <NUM>, substantially after the classifying in step <NUM>, or substantially simultaneous with the classifying in step <NUM>, i.e. in parallel.

The marking probability <NUM> can be based on a moving average of the marking ratio. The moving average can for example, amongst others, be a simple moving average, a cumulative average, a weighted moving average, an exponential moving average, or any other moving average known to the skilled person. Such a moving average of the marking ratio at step i may, for example, be determined as <MAT> wherein Si-<NUM> represents the moving average of the marking ratio at a previous step i - <NUM> and <MAT> represents the exponentially weighted moving average determined by, for example: <MAT> wherein α is a weight factor between zero and one.

The marking probability <NUM> can, for example, be a value between zero and one. Preferably, the maintaining of the marking probability can be performed at a predetermined time interval, e.g. every <NUM>, or at a predetermined change in the total number of packets <NUM> processed by the network queue, e.g. every <NUM> packets at a bit rate of <NUM> Mbps. In other words, the marking probability <NUM> is based on the change in packets responsible for congestion <NUM> and the change in the total number of packets processed by the network queue <NUM> during a predetermined interval. This allows to periodically derive or update the marking probability <NUM> rather than for every packet processed by the queue. This has the further advantage that it can limit the execution time and the consumed processing power of the method. The marking probability can, for example, be determined as <MAT> wherein Pi(M) and Si represent the current marking probability and the moving average of the marking ratio at step i, respectively.

In a following step <NUM>, the classified packets are marked with a congestion mark <NUM> to signal congestion to the respective senders. Packets classified as scalable packets are marked with the congestion mark <NUM> when identified <NUM> as responsible for congestion. Packets classified as other packets are marked with the congestion mark <NUM> based on the marking probability <NUM> if they support unscalable congestion control. In other words, other packets that do not support unscalable congestion control may not be marked. Other packets can, for example, be marked when the marking probability Pi(M) <NUM> is equal to, or larger than a random value, e.g. when Pi(M) ≥ rand(<NUM>,<NUM>). In doing so, senders that implement an unscalable congestion control algorithm receive a smoothed congestion signal, i.e. a frequency of reflected marked packets <NUM>, compatible with their packet transmission rate adjustment mechanism.

This smoothed congestion signal for unscalable congestion control is thus coupled to the congestion signal for scalable congestion control by the marking probability <NUM>, which is based on the marking ratio. This marking ratio is indicative of the marking density that would be applied to packets in a scalable traffic queue reserved for scalable packets, i.e. a queue without other packets. In other words, the marking density that is applied to scalable packets for scalable congestion control is converted or translated to a marking density for unscalable congestion control that is applied to the other traffic. By this coupling of the respective marking densities for scalable packets and other packets, fairness can be achieved in the single queue <NUM>, i.e. network resources can be fairly distributed between the scalable packets and other packets in a shared queue.

Marking a packet can comprise adding the congestion mark <NUM> to the packet. Alternatively, marking a packet can comprise overwriting or adjusting the identifier <NUM> included in the packet <NUM>. According to an embodiment, the marking can preferably comprise overwriting an identifier <NUM> included in the explicit congestion notification, ECN, field of an internet protocol, IP, header of the packet <NUM> with the congestion mark <NUM>. In other words, the value or bits included in the ECN field of the IP header can be switched or adjusted to a predetermined value, e.g. to 0b11, to mark the packet <NUM> with the congestion mark <NUM>.

A packet <NUM> received by a network communication node can further already include a congestion mark that was applied by the AQM-module of a preceding network communication node. For example, the ECN field of a received packet can already contain the congestion mark 0b11. As this prevents the classifying of the packet as scalable or as an other packet, such a packet can preferably be treated as a scalable packet.

By the marking in step <NUM>, the scalable and unscalable congestion controls in different senders can closely track the capacity of the network communication node. This allows to maintain a low queue size <NUM>, and thus, a low queuing delay <NUM> regardless of the packet type, i.e. scalable packets or unscalable packets. The marking density for packets in the network queue <NUM> are thus directly determined by identifying or tracking packets responsible for congestion in the network queue, i.e. by leveraging a threshold-based mechanism. This allows to determine the marking densities without substantial convergence time, e.g. compared to a proportional integral, PI, control loop.

It is an advantage that the marking can reduce jitter and that starvation of the network queue <NUM> can be avoided. It is a further advantage that a network queue <NUM> can be shared between scalable traffic and other traffic without affecting latency, allowing other traffic to benefit from the low latency communication provided by scalable traffic queues without latency penalties. An example of such a scalable traffic queue can be a queue according to the low latency, low loss, scalable throughput, L4S, framework of the Internet Engineering Task Force, IETF.

It is a further advantage that the method is compatible with existing transport protocols that support scalable congestion control, e.g. data centre transmission control protocol, DCTCP, or QUIC, and existing transport protocols that support unscalable congestion control, e.g. transmission control protocol, TCP. It is a further advantage that the method is compatible with existing scalable congestion controls, e.g. BBRv2, Prague, SCReAM, and unscalable congestion controls, e.g. New Reno and CUBIC.

<FIG> shows steps <NUM> according to an example embodiment wherein the steps of the method are performed upon dequeuing <NUM> a packet <NUM> from the network queue <NUM>. Upon dequeuing <NUM> the packet <NUM>, the change in total number of packets processed by the network queue Δpacketsprocessed <NUM> can be updated, e.g. by incrementing a counter by one. In a following step <NUM>, the dequeued packet <NUM> can be identified as responsible for congestion if the sojourn time Δtpacket of the packet <NUM> exceeds the time threshold Thtime. If this is the case, the change in packets responsible for congestion Δpacketscongestion can be updated <NUM>, e.g. by incrementing a counter by one. Else, the method can continue to step <NUM> without updating Δpacketscongestion. In step <NUM>, the marking probability <NUM> can be maintained or updated as described in relation to <FIG> above.

The dequeued packet <NUM> can further be classified as a scalable packet <NUM> or an other packet <NUM> in step <NUM>. The classifying can be performed as described in relation to <FIG> above. The classifying in step <NUM> can be performed substantially after or substantially simultaneous with the identifying of packets responsible for congestion in step <NUM> and the maintaining of the marking probability in step <NUM>.

In a following step <NUM>, scalable packets <NUM> can be identified as responsible for congestion in the network queue <NUM> if the sojourn time Δtpacket of the packet <NUM> exceeds the time threshold Thtime. If this is the case, the scalable packet <NUM> is marked in step <NUM>, e.g. by overwriting identifier <NUM> with the congestion mark <NUM>. Else, the packet <NUM> is outputted in step <NUM> without marking it. Alternatively, in step <NUM>, scalable packets <NUM> can be identified as responsible for congestion in the network queue <NUM> based on a first time threshold Tht<NUM> and a second time threshold Tht<NUM>, wherein the second may be substantially larger than the first, i.e. Tht<NUM> < Tht<NUM>. For example, scalable packets <NUM> with a sojourn time Δtpacket substantially smaller than the first time threshold, i.e. Δtpacket < Tht<NUM>, may not be identified as responsible for congestion; packets with a sojourn time that exceeds the second time threshold, i.e. Tht<NUM> < Δtpacket, may always be identified as responsible for congestion; and packets with a sojourn time between the first time threshold and the second time threshold, i.e. Tht<NUM> ≤ Δtpacket ≤ Tht2, may be identified as responsible for congestion according to a probability function based on the actual sojourn time of the packet, e.g. a progressive probability to identify the packet as responsible for congestion between the first Tht<NUM> and second Tht<NUM> time threshold.

When the packet <NUM> is classified as an other packet <NUM>, the maintained or updated marking probability <NUM> is used to determine whether the packet <NUM> is eligible for marking. If, in step <NUM>, the marking probability <NUM> is larger or equal to a random value, e.g. between zero and one, the packet <NUM> is eligible for marking and the method proceeds to step <NUM>. Else, the packet <NUM> is outputted in step <NUM> without marking it.

The other packet <NUM> can be marked in step <NUM> when the other packet eligible for marking supports unscalable congestion control. This can, for example, be determined in step <NUM> based on the identifier <NUM> included in the packet <NUM>. Unscalable congestion control can, for example, not be supported when the sender of the packet <NUM> is not provided with a congestion control algorithm, or when the traffic transport protocol of the packet <NUM> does not support marking the packet with the congestion mark <NUM>. If the packet eligible for marking in step <NUM> does not support unscalable congestion control, the other packet <NUM> can be dropped in step <NUM>. Dropping a packet refers to substantially removing or discarding the packet from memory. This results in packet loss as the packet is not outputted, i.e. forwarded or transmitted, by the network communication node. This allows to manage the congestion in the network queue <NUM> in the presence of other packets <NUM> that do not support congestion control. It is a further advantage that futile marking of packets that do not support scalable congestion control can be avoided.

It will further be apparent that identifying a packet as responsible for congestion in the network queue in steps <NUM> and <NUM> can be performed only once. In a final step <NUM>, the marked scalable or other packet <NUM> can be forwarded or outputted by the network communication node.

<FIG> shows additional steps <NUM>, <NUM> according to a further example embodiment wherein the steps <NUM> of the method are performed upon dequeuing <NUM> a packet <NUM> from the network queue <NUM>.

If the marking probability <NUM> is larger or equal than a random value in step <NUM>, the other packet <NUM> can further be identified as responsible for congestion in the network queue <NUM>. This can be achieved by comparing the sojourn time Δtpacket of the packet <NUM> with the time threshold Thtime in additional step <NUM>. If the packet is identified as responsible for congestion, the method proceeds to step <NUM> and continues as described above in relation to <FIG>. Else, the method proceeds to additional step <NUM>. Alternatively, step <NUM> can be skipped and the method proceeds directly to step <NUM>.

In step <NUM>, the sojourn time Δtpacket of a packet can further be compared to a first drop threshold Thdrop. The packet can be a marked packet <NUM> originating from step <NUM>, or an unmarked packet originating from step <NUM>, <NUM>, or <NUM>. Drop threshold Thdrop can preferably be substantially larger than the time threshold Thtime, e.g. a drop threshold of <NUM> when the time threshold is <NUM>. If the sojourn time Δtpacket of the packet exceeds the first drop threshold Thdrop, the packet can be dropped in step <NUM>. In other words, additional step <NUM> provides an overload protection to the network queue <NUM>. This can make the network queue <NUM> more resilient against sudden changes in queuing delay, e.g. due to a plurality of traffic flows starting up, unresponsive traffic flows, or a sudden burst of packets. It will be apparent that additional step <NUM> need not be performed at the end of the method, step <NUM> can for example also be performed before step <NUM>.

<FIG> shows steps <NUM> according to an example embodiment wherein the steps of the method are performed before enqueuing <NUM> a packet <NUM> received by a network communication node in the network queue <NUM>. Before enqueuing <NUM> the packet <NUM>, e.g. before segmentation, the change in total number of packets processed by the network queue Δpacketsprocessed <NUM> can be updated, e.g. by incrementing a counter by one. In a following step <NUM> the received packet <NUM> can be identified as responsible for congestion if enqueuing <NUM> packet <NUM> results in a queue size Qsize of the network queue <NUM> that exceeds the size threshold Thsize. If this is the case, the change in packets responsible for congestion Δpacketscongestion can be updated <NUM>, e.g. by incrementing a counter by one. Else, the method can continue to step <NUM> without updating Δpacketscongestion. In step <NUM>, the marking probability <NUM> can be maintained or updated as described in relation to <FIG> above.

The received packet <NUM> can further be classified as a scalable packet <NUM> or an other packet <NUM> in step <NUM>. The classifying can be performed as discussed in relation to <FIG> above. The classifying in step <NUM> can be performed substantially after or substantially simultaneous with identifying packets responsible for congestion in step <NUM> and maintaining of the marking probability in step <NUM>.

In a following step <NUM>, a scalable packet <NUM> can be identified as responsible for congestion in the network queue <NUM> when enqueuing <NUM> packet <NUM> results in a queue size Qsize of the network queue <NUM> that exceeds the size threshold Thsize. If this is the case, the scalable packet <NUM> is marked in step <NUM>, e.g. by overwriting identifier <NUM> with the congestion mark <NUM>. Alternatively, in step <NUM>, scalable packets <NUM> can be identified as responsible for congestion in the network queue <NUM> based on a first size threshold Ths<NUM> and a second size threshold Ths2, wherein the second may be substantially larger than the first, i.e. Ths<NUM> < Ths2. For example, if the queue size Qsize is substantially smaller than the first size threshold, i.e. Qsize < Ths<NUM>, the scalable packet <NUM> may not be identified as responsible for congestion; if the queue size Qsize exceeds the second size threshold, i.e. Ths<NUM> < Qsize, the scalable packet <NUM> may always be identified as responsible for congestion; and if the queue size Qsize is between the first size threshold and the second size threshold, i.e. Ths<NUM> ≤ Qsize ≤ Ths<NUM>, the scalable packet <NUM> may be identified as responsible for congestion according to a probability function based on the actual queue size Qsize, e.g. a progressive probability to identify the packet as responsible for congestion between the first Ths<NUM> and second Ths<NUM> time threshold.

When the packet <NUM> is classified as an other packet <NUM>, the maintained or updated marking probability <NUM> is used to determine whether the packet <NUM> is eligible for marking. If, in step <NUM>, the marking probability <NUM> is larger or equal to a random value, e.g. between zero and one, the packet <NUM> is eligible for marking and the method proceeds to step <NUM>. Else, the packet <NUM> is enqueued <NUM> without marking it.

The other packet <NUM> can be marked in step <NUM> when the other packet eligible for marking supports unscalable congestion control. This can, for example, be determined in step <NUM> based on the identifier <NUM> included in the packet <NUM>. Unscalable congestion control can, for example, not be supported when the sender of the packet <NUM> is not provided with a congestion control algorithm, or when the traffic transport protocol of the packet <NUM> does not support marking the packet with the congestion mark <NUM>. If the packet eligible for marking in step <NUM> does not support unscalable congestion control, the other packet <NUM> can be dropped in step <NUM>. Dropping a packet refers to substantially removing or discarding the packet from memory. This results in packet loss as the packet is not enqueued in the network queue <NUM>. This allows to manage the congestion in the network queue <NUM> in the presence of other packets <NUM> that do not support congestion control. It is a further advantage that futile marking of packets that do not support scalable congestion control can be avoided.

It will further be apparent that identifying a packet as responsible for congestion in the network queue in steps <NUM> and <NUM> can be performed only once. In a final step, the marked packet <NUM> can be enqueued <NUM> in network queue <NUM> of the network communication node i.e. added to network queue <NUM>.

<FIG> shows additional steps <NUM>, <NUM> according to a further example embodiment wherein the steps <NUM> of the method are performed before enqueuing <NUM> a packet <NUM> in the network queue <NUM>.

If the marking probability <NUM> is equal to or larger than a random value in step <NUM>, the other packet <NUM> can further be identified as responsible for congestion in the network queue <NUM>. This can be achieved by comparing the queue size Qsize of the network queue <NUM> with the size threshold Thsize in additional step <NUM>. If the packet is identified as responsible for congestion, the method proceeds to step <NUM> and continues as described above in relation to <FIG>. Else, the method proceeds to additional step <NUM>. Alternatively, step <NUM> can be skipped and the method proceeds by enqueuing <NUM> the packet.

In step <NUM>, the queue size Qsize of the network queue <NUM> can further be compared to a second drop threshold Thdrop. The packet can be a marked packet <NUM> originating from step <NUM>, or an unmarked packet originating from step <NUM>, <NUM>, or <NUM>. Drop threshold Thdrop can preferably be substantially larger than the size threshold Thsize, e.g. a drop threshold of <NUM> MB when the size threshold is <NUM> MB. If the queue size Qsize of the network queue <NUM> exceeds the second drop threshold Thdrop, the packet can be dropped in step <NUM>. In other words, additional step <NUM> provides an overload protection to the network queue <NUM>. This can make the network queue <NUM> more resilient against sudden changes in queuing delay, e.g. due to a plurality of traffic flows starting up, unresponsive traffic flows, or a sudden burst of packets. It will be apparent that additional step <NUM> need not be performed at the end of the method, step <NUM> can for example also be performed before step <NUM>.

<FIG> shows steps <NUM> according to an example embodiment wherein a portion of the steps of the method are performed before enqueuing <NUM> a received packet <NUM>, and another portion of the steps are performed upon dequeuing <NUM> the packet <NUM>.

In a first step <NUM>, a packet <NUM> received by the network communication node can be classified as a scalable packet <NUM> or an other packet <NUM>. All scalable packets <NUM> are flagged for marking in step <NUM>. Other packets <NUM> are flagged for marking in step <NUM> according to the maintained marking probability <NUM>, i.e. if the marking probability <NUM> is larger than or equal to a random value in step <NUM>. Flagging a packet for marking can, for example, include adding an identifier, stamp, or flag to the packet <NUM>. Hereafter, the flagged packets <NUM> and unflagged packets <NUM> are enqueued in the network queue <NUM>.

Upon dequeuing <NUM> the packets <NUM>, <NUM>, the change in total number of packets processed by the network queue Δpacketsprocessed <NUM> can be updated, e.g. by incrementing a counter by one. In a following step <NUM>, the dequeued packet can be identified as responsible for congestion. If this is the case, the change in packets responsible for congestion Δpacketscongestion can be updated <NUM>, e.g. by incrementing a counter by one. Else, the method can continue to step <NUM> without updating Δpacketscongestion. In step <NUM>, the marking probability <NUM> can be maintained or updated as described in relation to <FIG> above.

In an optional step <NUM>, the sojourn time Δtpacket of a packet can further be compared to a first drop threshold Thdrop. If the sojourn time Δtpacket of the packet exceeds the first drop threshold Thdrop, the packet can be dropped in step <NUM>. It will be apparent that optional step <NUM> need not be performed directly after dequeuing <NUM>, step <NUM> can for example also be performed after step <NUM> or step <NUM>.

In a following step <NUM>, the packet can be checked for the presence of the flag in addition to identifying whether the packet is responsible for congestion. If this is not the case, the packet can be outputted or transmitted by the network communication node in step <NUM>. Else, the method proceeds to step <NUM> wherein it is checked if the packet eligible for marking supports congestion control. If so, the packet can be marked in step <NUM> and subsequently outputted in step <NUM>. If the packet does not support congestion control, the packet can be dropped in step <NUM>.

This allows to reduce the number of performed operations, the execution time, and the consumed processing power of the method in the dequeue pipeline of a network communication node. This further allows to implement the method in network communication nodes with a high throughput, i.e. bit rate, or low serialization time per packet, i.e. with a limited available time budget in the dequeue pipeline for marking.

It will be apparent that, while steps <NUM>, <NUM>, and <NUM> in <FIG> illustrates a time-based threshold and congestion parameter as in the embodiment illustrated in <FIG> and <FIG>, a size-based threshold and congestion parameter as illustrated in the embodiments of <FIG> and <FIG> can also be used.

<FIG> shows a suitable computing system <NUM> enabling to implement embodiments of the method for managing data traffic congestion in a network communication node. Computing system <NUM> may in general be formed as a suitable general-purpose computer and comprise a bus <NUM>, a processor <NUM>, a local memory <NUM>, one or more optional input interfaces <NUM>, one or more optional output interfaces <NUM>, a communication interface <NUM>, a storage element interface <NUM>, and one or more storage elements <NUM>. Bus <NUM> may comprise one or more conductors that permit communication among the components of the computing system <NUM>. Processor <NUM> may include any type of conventional processor or microprocessor that interprets and executes programming instructions. Local memory <NUM> may include a random-access memory (RAM) or another type of dynamic storage device that stores information and instructions for execution by processor <NUM> and/or a read only memory (ROM) or another type of static storage device that stores static information and instructions for use by processor <NUM>. Input interface <NUM> may comprise one or more conventional mechanisms that permit an operator or user to input information to the computing device <NUM>, such as a keyboard <NUM>, a mouse <NUM>, a pen, voice recognition and/or biometric mechanisms, a camera, etc. Output interface <NUM> may comprise one or more conventional mechanisms that output information to the operator or user, such as a display <NUM>, etc. Communication interface <NUM> may comprise any transceiver-like mechanism such as for example one or more Ethernet interfaces that enables computing system <NUM> to communicate with other devices and/or systems, for example with one or more source nodes, i.e. senders <NUM> of data packets, and with one or more destination nodes, i.e. receivers <NUM> of the data packets. The communication interface <NUM> of computing system <NUM> may be connected to such a source node or destination node by means of a local area network (LAN) or a wide area network (WAN) such as for example the internet. Storage element interface <NUM> may comprise a storage interface such as for example a Serial Advanced Technology Attachment (SATA) interface or a Small Computer System Interface (SCSI) for connecting bus <NUM> to one or more storage elements <NUM>, such as one or more local disks, for example SATA disk drives, and control the reading and writing of data to and/or from these storage elements <NUM>. Although the storage element(s) <NUM> above is/are described as a local disk, in general any other suitable computer-readable media such as a removable magnetic disk, optical storage media such as a CD or DVD, ROM, disk, solid state drives, flash memory cards, etc. could be used. Computing system <NUM> could thus correspond to the network communication node <NUM> as illustrated in <FIG>.

It will furthermore be understood by the reader of this patent application that the words "comprising" or "comprise" do not exclude other elements or steps, that the words "a" or "an" do not exclude a plurality, and that a single element, such as a computer system, a processor, or another integrated unit may fulfil the functions of several means recited in the claims. Any reference signs in the claims shall not be construed as limiting the respective claims concerned. The terms "first", "second", third", "a", "b", "c", and the like, when used in the description or in the claims are introduced to distinguish between similar elements or steps and are not necessarily describing a sequential or chronological order. Similarly, the terms "top", "bottom", "over", "under", and the like are introduced for descriptive purposes and not necessarily to denote relative positions. It is to be understood that the terms so used are interchangeable under appropriate circumstances and embodiments of the invention are capable of operating according to the present invention in other sequences, or in orientations different from the one(s) described or illustrated above.

Claim 1:
A method (<NUM>) for managing data traffic congestion in a network communication node that processes packets having an identifier (<NUM>) indicative of scalable packets or other packets, wherein scalable packets support scalable congestion control, the method comprising:
- maintaining (<NUM>) a marking probability (<NUM>) based on a marking ratio indicative of a ratio between a change in packets responsible for congestion (<NUM>) in a network queue (<NUM>) in the network communication node, and a change in a total number of packets (<NUM>) processed by the network queue, wherein packets responsible for congestion cause a congestion parameter to exceed a threshold;
- classifying (<NUM>) packets (<NUM>) processed by the network queue as scalable packets or other packets based on the identifier (<NUM>) included in the packets;
- marking (<NUM>) the scalable packets responsible for congestion in the network queue with a congestion mark (<NUM>) to signal data traffic congestion; and
- marking (<NUM>) the other packets that support unscalable congestion control with the congestion mark (<NUM>) based on the marking probability (<NUM>).