Token bucket with active queue management

Systems and methods are provided for a new type of quality of service (QoS) primitive at a network device that has better performance than traditional QoS primitives. The QoS primitive may comprise a token bucket with active queue management (TBAQM). Particularly, the TBAQM may receive a data packet that is processed by the token bucket; adjust tokens associated with the token bucket, where the tokens are added based on a configured rate and subtracted in association with processing the data packet; determine a number of tokens associated with the token bucket, comprising: when the token bucket has zero tokens, initiating a first action with the data packet, and when the token bucket has more than zero tokens, determining a marking probability based on the number of tokens and initiating a second action based on the marking probability.

BACKGROUND

Data packets transmitted via communication networks are common. When a bulk of data packets are transmitted simultaneously, processing of these data packets can be delayed when existing network devices are unable to handle the processing capacity. As such, the number of data packets causes network congestion in the wider communication network.

One metric to help minimize network congestion involves defining a predetermined incoming packet rate. However, incoming packet rates can vary in a set of network devices in the communication network. If any network device involved in the processing of data packets receives packets at a higher rate than it can process, then the data packets can back up, which can give rise to a delayed queue of data packets.

Larger scale data processing congestion can occur when network devices are overloaded and the number of data packets backed up in the queue becomes excessive. As a simple example, network routers have a finite amount of buffer space for queuing packets awaiting transmission over outgoing network paths. If the incoming packet rate is too high, queue lengths can increase to the point where router buffers are too full to adequately process incoming and outgoing traffic. In some cases, data packets are dropped and may cause data loss or further delay.

Traditionally, communication networks offer a “best effort” services, where all users of the network can receive the same level of service. However, a network quality of service (QoS) policy can allow the network to offer different level of service to different users, connections, data types, protocols, requesting devices, network environments, geographic locations, etc. For example, some users may receive from the network higher priority, higher bandwidth, or lower latency. QoS can be implemented via network devices and network traffic rules using QoS primitives that are implemented in the network devices.

A QoS primitive executes on a network device and performs various tasks related to QoS policies. In some examples, the QoS primitive can process packets and enforce QoS policies in the network. In other examples, the QoS primitive can inform devices of the QoS requirements in a platform independent implementation, process data packets, and make decisions that impact the level of service received by the packet, such as when the packet will be forwarded by the device. Some example QoS primitives include a priority queue (e.g., each data packet has a priority value associated with it and the data packet with the highest priority is transmitted/processed first) and communication traffic policer (e.g., monitor data traffic to enforce the QoS policy associated within, and discarding or marking non-compliant data traffic).

DETAILED DESCRIPTION

Existing QoS primitives have limitations. For example, priority queues can have difficulty scaling to a large number of QoS classes (e.g., more than one thousand). In another example, policers can have poor performance with common Transmission Control Protocol/Internet Protocol (TCP/IP) traffic.

Examples of the application describe a token bucket with active queue management (TBAQM), which can correspond with a new type of QoS primitive that has better performance than traditional QoS primitives. The TBAQM can limit the transmission or acceptance rate of network traffic by not using a queue (like most standard QoS primitives), but rather a policer implemented using a token bucket (e.g., where the policer uses the token bucket state as input). For example, as the policer of the TBAQM processes the packets, it may make a decision immediately to perform one of the following: let the packet pass unmodified, change a header value and then let the packet pass, or drop the packet. Which action is taken is based on the number of tokens in the token bucket and the output of the TBAQM.

The TBAQM also improves upon standard QOS primitives by incorporating any AQM algorithm (e.g., designed for a queue and that rely on a standard queue length or estimated dequeue rate to regulate traffic or packet processing). For example, the TBAQM is implemented with a proportional integral controller algorithm, where the queue length variable is replaced by the difference between the bucket size and the number of tokens and where the estimated dequeue rate is replaced by the configured rate of the token bucket.

The TBAQM QoS primitive can reduce jitters and bursts on the communication network, making TCP traffic more smooth across the communication network, minimize time when the communication network is oversubscribed, and minimize time when TCP cannot use the bandwidth provided by the QoS primitive. In some examples, the TBAQM QoS primitive is an improved policer and, because it's a policer, it can also implement greater scalability than priority queues.

Technical improvements are realized throughout the disclosure. For example, the token bucket with active queue management (TBAQM) described herein can reduce congestion, implement a large data packet burst size to increase efficiency of packet transmission across the network, and decrease packet losses. This can improve the data network overall. These technical improvements may be realized by users relying on the communication network as well. For example, real-time applications (e.g., streaming video) will be less frequently impacted by high network usage and dropped data packets or network transmission hiccups from TCP applications may be reduced.

Additionally, the TBAQM can create a scalable QoS primitive that has good performance with TCP congestion control. It can replace conventional token buckets with less sensitivity to the configuration of the burst size, better regulation of TCP throughput, and better support of bursty traffic.

Further, the TBAQM can be implemented in hardware and software in any network device to implement QoS control and rate limiting. When implementing packet processing as a service, the TBAQM can improve the QoS offering to users, enabling users better management of their network. The improved scalability can correlate with finer grained QoS implementations and a large set of tenants or applications can be supported.

FIG.1illustrates some traditional forms of implementing a communication network using a QoS policy, in accordance with some examples of the disclosure. In the illustrative computing environment100, sender computing device110, network120, and receiver computing device130are provided.

In this illustration, sender computing device110transmits one or more data packets to receiver computing device130via networks120(illustrated as first network120A and second network120B). Sender computing device110and receiver computing device130(e.g., clients, servers) may be endpoints in a communication network that connects the endpoints. Various sender computing devices may send data packets to various receiver computing devices, although a single sender computing device and a single receiver computing device is provided for simplicity of explanation.

Computing environment100can connect these and other computing devices (e.g., client devices or servers) to forward data packets and allow for data transmissions between sender computing device110and receiver computing device130via network120. Each of these devices can forward data packets from a source to a destination, whether or not the source is the original device that generated the data packet or original recipient that will ultimately receive the data packet. Each of these devices may exist along the network path, which can cross multiple network devices.

The default forwarding behavior of a network device computing environment100in can correspond with a “best effort” to transmit the data packet. Every packet is forwarded the same way, so every user of the network can receive the same level of service in transmitting its data. Best effort for network is most often based on data packets, so every user gets the same opportunity to forward the data packet.

Computing environment100may enable data packet transmissions using a QoS policies. The QoS policies can offer different level of services for transmitted data packets via network120. In some examples, the QoS policies can correspond with a number of QoS classes or QoS policies, where each QoS class is the unit of management for QoS policies. Each QoS class can also correspond with a different level of service. For example, a QoS class may get higher priority, higher bandwidth, or lower latency than another QoS class. Traffic from users and network devices can be associated to the various QoS classes based on complex policies implemented by network device140.

Network device140can be broadly separated in three parts, including QoS controller142, QoS classifier144, and QoS primitives146. In some examples, QoS controller142is implemented outside of network device140, and a single QoS controller142can manage a plurality of QoS devices. In some examples, QoS primitives146may comprise a scheduler. In some examples, network device140can be thought of as including these three QoS related parts, the QoS controller142, the QoS classifier144, and the QoS primitives146. The QoS primitives146generally process packets, implement the QoS class, and enforce the QoS policy. QoS primitives146may decide what is the packet priority, when the packet will be forwarded, or if the packet should be dropped. The QoS primitives146may be configured manually by an admin or dynamically by the QoS controller142.

QoS controller142is configured to manage QoS policies. It may assign users to classes based on identity, user needs and QoS policies, and may verify that users don't violate the term of the policy. It may manage the QoS policies, and may change the overall allocation of network resources to meet the goal of each policy. In some examples, QoS controller142is not implemented programmatically and the network administrator statically configures the QoS policy in the network devices.

QoS classifier144is configured to recognize the traffic and associate it with its corresponding QoS class. There are many different ways to implement such classifier. In some case, the application on the sender device can tag its traffic with the QoS class, for example setting the differentiated services code point (DSCP) field of the TCP header with the appropriate value. In other examples, the network device may use complex packet parsing and deep packet inspection to infer the QoS class from the traffic itself.

QoS primitives146may be implemented with the network devices that process packets, implement the QoS class, and enforce the QoS policy. It may decide what is the packet priority, when the packet can be forwarded, or if the packet should be dropped. The QoS primitives may be configured either manually by an administrative user or dynamically by QoS controller142.

In some examples, computing environment100may implement one or more network queues and scheduling in QoS primitives146. A scheduler may be part of the QoS primitives. Scheduler may be implemented with a queue or set of queues, and can decide in which order packets are processed and how often packets are processed. With a suitable set of queues and QoS classifier, very complex and elaborate QoS policies can be implemented.

FIG.2illustrates processing packets to be added to a queue using an active queue management (AQM) technique, in accordance with some examples of the disclosure. In this illustration200, active queue management (AQM)230, queue240, and scheduler250are provided to process one or more packets202in an updated QoS primitive210of network device140. The rest of the devices and networks may remain similar to the illustrative example shown inFIG.1, including sender computing device110, network120, receiver computing device130, as well as the other components associated with network device140(e.g., QoS controller142and QoS classifier144).

In some examples, scheduler250may implement prioritization. For example, some queues are given precedence over other queues. The classifier may decide in which queue the received packet should be placed. Scheduler250can dequeue the queues, starting with the highest priority queue. These data packets in the higher priority queues can be forwarded before data packets of lower priority queues and will experience lower latency.

In some examples, scheduler250can also control bandwidth. The process of controlling bandwidth by scheduler may include allocating a specific amount of bandwidth to specific queues, with each queue being be mapped to a QoS class. This mapping can managed individually (e.g., by an administrative user) and get specific level of service.

The downside of queues and scheduler250is that they are complex and costly to implement, and they don't scale to large number of classes. In theory, for each packet that needs to be forwarded, scheduler250may be configured to consult all queues to make a decision, and this may scale linearly to the number of queues. To reduce the overhead of scheduler250, some schedulers dequeue packets from queues as batches, instead of individually, but this decreases the effectiveness of the QoS and can introduce performance issues with TCP congestion control.

The number of queues managed by scheduler250may be a tradeoff between the need for a greater number of QoS classes and the overhead of having more queues. In most hardware and software implementations, the number of queues may be around 1024. As the number of tenants and applications in a data center keep keeps increasing, such number is not sufficient to give one QoS class for every tenant or application.

In some examples, queue240is implemented as a first in first out (FIFO) queue. For example, incoming packet are just added at the tail of the queue (input) and scheduler250removes them from the head of queue240(output) for forwarding.

Some FIFO queues may have a maximum size corresponding with either a maximum number of packets or bytes. If packets arrive at the queue faster than scheduler250can process them, the packets may accumulate in the queue and the queue can become longer. When the queue is full, incoming packets may be dropped, which is sometimes referred to as “tail dropping.” When network traffic is bursty, the queues may need to be large enough to handle a burst of traffic without dropping too many packets in normal operation.

In some examples, tail dropping may be avoided. Some reasons to avoid tail dropping is that the packet that is dropped could be retransmitted in order to avoid losing that data contained in the packet. This retransmission can take additional time and slow down processing for other packet transmissions. As such, the congestion created by packet drops can indicate that too many packets are sent to the queue using network120.

Some traditional systems implement a version of TCP congestion control that rely on the packet loss value exclusively as the way to regulate the rate at which they are sending data and to avoid network congestion. These versions of TCP congestion control can repetitively induce tail dropping to infer when the network path is congested, and the packet losses can identify when the network is congested and can initiate TCP congestion control.

In some examples, tail dropping and large queues can lead to performance issues with TCP congestion control. With tail dropping, the TCP congestion control can stop pushing more traffic when the queue is full, so the queue may be close to full on average (e.g., within a threshold value of a maximum queue value). This makes the queuing delay high, as newly transmitted data packets may wait for the whole queue to be processed. The congestion signal represented by the packet drop may wait for the whole queue to be processed, this increases the latency of the TCP control loop and can also result in TCP oscillations and starvation.

In some examples, active queue management (AQM)230can remedy the defects of tail dropping. AQM230may implement a congestion signal with a lower delay and is finer grained. AQM230may add additional processing at queue240to drop packets before queue240is full. TCP congestion control reacts to those losses by reducing its sending rate. The end result is that sender computing device110may slow down data transmissions before queue240is full, the average size of queue240may be smaller. AQM230can decrease the overall delay of packets and congestion signal, which can increase the TCP performance.

In some examples, random early detection (RED) may implement AQM230. RED can define a probability of drop based on the queue occupancy. For example, when queue240is almost empty, the probability value may be close to zero and the packet drop may be very unlikely. When queue240is almost full, the probability value may be higher and packet drop may be more likely.

Other processes may also implement AQM230, such as Blue, Adaptive Random Early Detection (ARED), Proportional Integral controller Enhanced (PIE), and controlled delay (CoDel). In these processes, a small occupancy of queue240may be maintained by dropping packets preventively and proactively. The probability of drop may be based on queuing delay. For example, CoDel tries to maintain the queue delay for the data packets that are below a configured threshold.

In some examples, the use of AQM230can reduce packet losses, but may not completely eliminate it, as packet losses can slow down TCP congestion control. Explicit congestion notification (ECN) can add a mechanism in the TCP protocol to carry a congestion signal without dropping packets. A bit or flag in the TCP header part of the packet may be updated from zero to one to indicate congestion. For example, sender computing device110can set this bit to zero. In some examples, other network devices can experience congestion by setting the bit or flag as well. When receiver computing device130can reflect the bit to sender computing device110. If sender computing device110sees the bit set, it can assume that the congestion is present and reduce its sending rate, as if that packet was dropped.

In some examples, ECN may be combined with a form of AQM230, absent implementation of tail dropping. When the AQM230detects congestion at queue240and that packet supports ECN, instead of dropping packets, sender computing device110can set the ECN bit in the TCP header to signal that congestion.

However, ECN may not be supported by all implementations. So, when the network experiences congestion, the device that implements AQM230can mark packets that need to carry the congestion signal. If the packet supports ECN, the packet may be marked. This marking can result in modifying the packet to set the ECN bit. Otherwise, marking the packet can result in the packet being dropped.

The ECN bit can identify congestion in the network and replace packet loss. The ECN bit can have a statistical property. In particular, packet losses may be low to avoid network inefficiencies, so the probability of AQM230dropping a packet or setting the ECN bit may be low (e.g., around one to two percent in practice).

Having such a low probability of congestion signal may be problematic in practice. The congestion signal may be generated for fairly strong levels of congestion. The congestion may accumulate for some time before the ECN signal is sent. The reaction of sender computing device110to such signal may to may be strong, because it indicates strong congestion. As such, in practice, the signal may not be sent often in accordance with the stored instructions and rules. This may result in delay when notifying sender computing device110of the new congestion level. This delay can make the overall feedback loop of the control system fairly slow and unstable.

In some examples, the signal congestion experienced (SCE) process may be implemented as a finer grained congestion signal. For example, SCE may correspond with an adaptation of the congestion signal in data center TCP (DCTCP), which is not related to packet loss. In implementations of SCE, a bit/flag can be sent more often than ECN and can be associated with lower levels of congestion. In some examples, the probability of SCE in the stream of packets can encode an actual level of congestion in the network. The SCE can help TCP congestion control adapt closer and faster to the actual congestion, for example, by identifying network congestions without waiting until the queue is full.

FIG.3illustrates processing packets to be added to a queue using an Active Queue Management (AQM) technique using a PI controller, in accordance with some examples of the disclosure. For example, processing packets may be added to a queue using the Proportional Integral controller Enhanced (PIE) or Proportional Integral improved with a square (PI2) algorithms, which may correspond with AQM techniques using the PI controller.

In illustrative example300, both PIE and PI2AQMs are shown. For example, when a packet arrives, PI controller350can compute a marking probability of data packets, ‘p’ and can estimate the queuing delay342. The queuing delay342may be based on the length of the queue370and the estimated dequeue rate340. PI controller350may then compare queuing delay342to target delay322, and determine the difference between queuing delay342to target delay322. A standard policer may not implement a marking probability based on the number of tokens or implement a second action based on the marking probability.

PI controller350may compute the probability of marking packets ‘p’360based on the difference between queuing delay342to target delay322and using parameters alpha and beta. For example, alpha and beta may configure the strength of the reaction of PI controller350. In some examples, alpha and beta may be adjusted so that PI controller350reacts fast enough but does not over-react.

The probability of drop ‘p’ is compared324to a pseudo random process320. The comparison may help decide whether to mark the incoming packet. If the incoming packet is determined to be marked, marking block330will mark the packet by, for example, either “drop the packet” or “change the ECN bit in the header.” If the incoming packet is determined not to be marked, then it passes to queue370unmodified.

In some examples, proportional integral (PI) controller350may be implemented with computing environment300to assist sender computing device310and receiver computing device312. PI controller350can maintain a process variable (PV) at a particular set point (SP). For example, PI controller350can measure the error (e.g., the difference between PV and SP) and include two feedback components, one that is proportional to the error and one using the integral of the error. The proportional component can provide a bigger correction when the two values are far apart, and smaller correction as the two values are close (e.g., within a threshold value). The integral component can eliminate biases in the sensing and actuation by tracking how the proportional component misses the target.

Proportional integral enhanced (PIE) process can apply PI controller350and the control theory to AQM. The goal of the PI controller350is to maintain the queuing delay342of packets below a specific duration. PIE may not directly impact the sending rate of packets at sender computing device310, so PI controller350can generate congestion signals using packet losses or setting ECN to achieve its goal. In some examples, the queuing delay342may not be measured, but rather inferred from the queue length370and the estimated output rate of the queue340. The PIE process can derive the optimal packet marking probability from the predicted queuing delay342. The packet marking can be implemented by dropping the packet or setting the ECN bit in the header of the packet.

The PI2process may improve PIE by implementing the same PI controller350and changing the formula and heuristics to derive packet marking to be more universal and simpler. The PI2process may generate finer grained congestion signals which is somewhat similar to the SCE process.

In some examples, a rate limiter is implemented in QoS primitive146of computing environment100. Rate limiting may help to enforce the network policy. For example, the rate limiter may be used to confirm that the traffic does not exceed a certain rate. This can be implemented for a policy reason (e.g., as the result of a contractual agreement) or to smooth out the burstiness of the traffic across network.

Rate limiting may be implemented as a shaper. The shaper can correspond with a queue, where the scheduler can process packets no faster than the committed rate. The queue in the shaper can help handle the burstiness of traffic and smooth out traffic, but may also add delay. The shaper may behave like other queues discussed herein and may correspond with the same scalability issues.

Rate limiting may be implemented as a meter or policer. The policer can enforce the committed rate by discarding the excess traffic. The policer may not have a queue. Rather, the policer may process packets instantly and decide if the packet should be kept, dropped, or some part of the header modified.

One of the challenges for the policer is how to handle common traffic burstiness. For example, if traffic arrives in a burst, the instantaneous rate may exceed the committed rate during the burst. If the traffic arrives between bursts, the policer may be idle for some time and the instantaneous rate may be lower than the committed rate. In some examples, the policer may include a bursting mechanism that enables average bandwidth utilization across the bursts. The policer may also enable the traffic to exceed the committed rate in the short term, as long at the longer term average of the traffic does not exceed the committed rate.

In some examples, a token bucket or leaky bucket may be implemented. The token bucket may implement a rate limiter, a shaper (e.g., with a queue), or a policer (e.g., with dropping packets). The leaky bucket may be similar to a token bucket used as a shaper.

FIG.4illustrates processing packets, refilling tokens, and removing tokens from a policer implemented using a token bucket, in accordance with some examples of the disclosure. The illustrative policer400includes token bucket405with a plurality of tokens415that are added and removed from token bucket405, as described herein.

Token bucket405of policer400may try to enforce a long term rate for the traffic passing through it (e.g., sometimes called target rate or committed rate). The enforcement may be implemented by dropping packets that exceed the committed rate. Some network traffic may be both discrete (e.g., the packets may not be split) and bursty, so token bucket405may include a mechanism for averaging enforcement.

Policer400may perform an action425with the packet. The action425may enforce an existing rule in order to, for example, keep, drop, or modify the packet in some way (e.g., the header of the packet). In some examples, the action425may be implemented by dropping packets that exceed the committed rate. Alternatively, the action425may be implemented by changing the drop precedence value in the DSCP field of the packet header, which may cause those packets to be dropped in subsequent processing.

Token bucket405may be a container of virtual credits or tokens415, which can allow smooth and average instantaneous variations in input traffic. For example, when a packet is ready to be forwarded, a number of credits or tokens415may be removed from token bucket405at block410.

In some examples, an action425may be performed based on the number of tokens in the token bucket405. If token bucket405is empty (e.g., zero tokens), no token can be removed and the packet may be dropped as action425. Token bucket405may be refilled with tokens415at a constant rate (e.g., the desired committed rate) at block420and the size of token bucket405may correspond with a burst size (BS) and/or a maximum capacity. When token bucket405is full, new tokens may be discarded, so that the token bucket does not grow beyond its maximum size BS and to prevent excessively long burst of packets.

Token bucket405may create variations in the instantaneous output rate. If the input traffic rate is below the target rate for some time, token bucket405may become full. If new traffic arrives at token bucket405, its output rate may be unconstrained as long as tokens are available in token bucket405. The burst of packets can have a rate much higher than the target rate (e.g., the burst rate). When token bucket405is finally empty, the target rate may be enforced on the traffic and/or other new data packets. In some examples, policer400does not have a queue to handle traffic variations and burstiness (e.g., rather it has token bucket405). In these examples, token bucket405may use a bursting mechanism allowing traffic to exceed its committed rate in the short term.

In some examples, the policer400may not have a queue to handle traffic variations and burstiness (e.g., as illustrated withFIGS.2and3). Instead, the policer400may use a bursting mechanism allowing traffic to exceed its committed rate in the short term. This configuration of the bursting mechanism is done using burst size BS, the maximum number of tokens that can accumulate in token bucket405. The burst size BS may represent a number of packets or bytes.

The configuration of the bursting mechanism may sometimes cause poor performance of policers. When the burst size BS is too small, the policer400may not accommodate a common traffic burst. For example, the tail end of the traffic burst may exceed the number of tokens available in token bucket405and the tail end of packets may be dropped. The packet drops may impact TCP which can reduce sending rate. On the other hand, the idle time between bursts may not be fully credited to the rate average because not enough tokens can accumulate in token bucket405. In this instance, the policer may be underutilized and the traffic may not take advantage of the full committed bandwidth.

When the burst size BS is too big, the policer400may produce long sequences of packets that exceed the committed rate. For the duration of the burst, that policer400may not protect the network downstream from the excess traffic and the long sequences may impact the QoS of other traffic competing downstream. The excess traffic may overflow the downstream queues. In some examples, the long sequences may also increase the TCP reaction time, since it may take more time for TCP to see the congestion loss. This may make TCP congestion control unstable, as TCP alternately sees a congested and uncongested path.

The burst size BS can be configured as a tradeoff between too small and too big. Some tradeoffs can depend on the traffic characteristics, such as the type of TCP congestion control, the overall round trip time of that particular path, and the timing behavior of other network devices (e.g., devices upstream of the policer400, devices that are not known in advance, or devices that may change over time). In some examples, the policer400may not be configured to deliver both good TCP performance and minimal impact (e.g., downstream network paths with large bandwidth delay).

As such, traditional network solutions may be inadequate for managing packet delay (e.g., because of the difficulty of managing the bursting mechanism, the preference to deploy shapers which are much more predictable and have better performance).

Policer400can implement a rate limiting of network traffic using token bucket405. For example, token bucket405may make a decision immediately to perform one of the following actions425: let the packet pass unmodified, change a header value and then let the packet pass, or drop the packet. For the system to determine a particular action425may be based on the number of tokens in token bucket405. In some examples, the action425is taken only if the number of tokens is zero in token bucket405. In some examples, the action425is taken depending on the policer configuration and information present in packet header (e.g., the value of the drop precedence in the DSCP field of the packet header or other values in the header of the data packet).

FIG.5illustrates different components of the token bucket with active queue management (TBAQM) and how it processes packets, in accordance with some examples of the disclosure. The TBAQM500may be an updated QoS primitive502of network device140. QoS primitive502may implement TBAQM500. The rest of the devices and networks associated with network device140may remain similar to the illustrative example shown inFIG.1, including sender computing device110, network120, receiver computing device130, as well as the other components associated with network device140(e.g., QoS controller142and QoS classifier144).

In some examples, TBAQM500implements an improved policer from the policer400illustrated inFIG.4. Since TBAQM500implements a policer, it can also implement greater scalability than priority queues implemented as standard QoS primitives. TBAQM500may make traffic more smooth, minimize time when the communication network is oversubscribed, and minimize time when TCP cannot use the bandwidth provided by some QoS primitive implemented in other systems, like the policer400using token bucket illustrated inFIG.4, as described herein.

TBAQM500may be an improved QoS primitive502to rate limit traffic using a token bucket505and PI controller545to generate fine grained congestion signals and better interact with TCP congestion control. TBAQM500may improve on traffic queues and policers by having both great scalability and good performance with TCP traffic. TBAQM500may implement processes to (1) rate limit traffic to a configured bandwidth, (2) integrate in existing QoS frameworks, (3) increase scalability to help support a large number of QoS classes without performance degradation and limited implementation footprint, (4) improve performance with a maximum TCP traffic throughput being close to the configured bandwidth and QoS downstream of TBAQM500is maintained at small time frame.

The token bucket505can be implemented with TBAQM500. The token bucket505may help implement rate limiting of network traffic by not using a queue, but rather a policer560with the state of the token bucket505as input. For example, as the policer processes the packets, it may make a decision immediately to perform one of the following actions at525,570: let the packet pass unmodified, change a header value and then let the packet pass, or drop the packet. Which action is taken is based on the number of tokens in the token bucket and the output of the TBAQM.

In some examples, action525may perform similar actions to the actions described with action425inFIG.4. For example, the action525may enforce an existing rule in order to, for example, keep, drop, or modify the packet in some way (e.g., the header of the packet). In some examples, the action525may be implemented by dropping packets that exceed the committed rate. Alternatively, the action525may be implemented by changing the drop precedence value in the DSCP field of the packet header, which may cause those packets to be dropped in subsequent processing.

In some examples, action570may differ from action525in the timing of performing various actions. For example, whether the action570is taken is based on the output of PI controller545. Which action570is performed may be based on the configuration of the TBAQM500.

In some examples, by using token bucket505, TBAQM500may implement early losses using action570instead of waiting for the bursting mechanism to run out of tokens and apply action525. For example, the token bucket505may implement a bursting mechanism to average bursty traffic. Experience with AQM and queues has shown that TCP can perform better when the congestion signal (e.g., the bit/flag or packet drop) is transmitted earlier than determining that the queue is full. Similarly, TCP can perform better when the congestion signal is transmitted earlier by TBAQM500than determining that the token bucket has run out of tokens.

In some examples, the solutions to solving the congestion may be more gradual and proportional to the level of congestion. In this way, the congestion signal may be sent to the sender device110earlier than traditional policers so that the TBAQM500can start signaling congestion before the token bucket505runs out of tokens.

TBAQM500may provide good TCP performance, even though the performance of TCP congestion control over a complex network path is very difficult to predict. There exist many variations of the TCP congestion control and the system may not know which TCP congestion control is used for each traffic source using the token bucket. Additionally, the TCP congestion control may be a moving target as new TCP congestion controls are designed to better take advantage of modern networks and AQM.

TBAQM500may be similar to existing the AQM process, which implements a queue rather than a token bucket, as described herein. TBAQM500may replace the queue with token bucket505that can respond to congestion in the same way as a queue with AQM, yet improved from a queue in that it can allow to smooth and average instantaneous variations in input traffic. In other words, the profile of congestion signals for different congestion levels can be similar to the AQM queue. In this way, TBAQM500can take portions of an existing AQM designed for use with a queue and adapt it to work in the context of a token bucket, while also creating new properties that would depend on traditional queue properties.

An illustrative flow using TBAQM500is also provided. For example, tokens may be added to the token bucket505(e.g., as an initial step) at block520. In some examples, the tokens may be added based on a configured rate and subtracted based on the packets processed at block510.

When the token bucket505receives a packet515, TBAQM500may determine whether there are tokens remaining in the token bucket505.

If there are tokens available, TBAQM500may compute a marking probability545based on the number of remaining tokens. In some examples, the marking probability545may correspond with the PIE or PI2processes implemented by TBAQM500to compute the marking probability545based on the number of tokens. In some examples, the marking probability545may correspond with the algorithm that can increase probability as the number of tokens decrease.

In some examples, TBAQM500may determine whether to mark the packet. TBAQM500may use a pseudo-random process550to decide if the packet must be marked. The pseudo-random process may be based on the marking probability.

In some examples, TBAQM500may let the packet pass unmodified to receiver computing device130. This block may allow the packet to pass in an unmodified state, will not drop the packet, and will not mark the packet.

In some examples, TBAQM500may determine whether packet marking is enabled in the packet and/or whether packet marking is implemented and configured in TBAQM. The determination from this block may either drop the received packet as action570or change a value in the header of the received packet as action570.

In some examples, TBAQM500may be statically configured to only drop packets or only do ECN (e.g., change the header value of the received packet) as action570. In another example, packet marking may be done through changing one or more other fields in the packet header. For example, action570modifies the SCE bit of the type of service (ToS) field header in the packet header. In other examples, action570modifies the drop precedence in the DSCP field in the packet header. In yet another example, a bit in the TCP header of the packet indicates if this TCP connection does support ECN or not. If ECN support is indicated, then ECN marking is used. If ECN support is not indicated, packet dropping is used.

In some examples, the packet may be dropped and not sent to receiver computing device130as action570. Otherwise, the packet value in the header may be changed as action570. For example, the bit or flag in the TCP header part of the packet may be updated from zero to one to indicate congestion as action570. Once the packet value is changed, the packet may be transmitted from TBAQM500to receiver computing device130as action570.

In some examples, the AQM process may be re-implemented in the TBAQM500where the queue length variable is replaced by the difference between the size of the token bucket505and the number of tokens.

For example, a traditional AQM process may be adapted to a token bucket implementation, at least in part, using a correlation between a policer and a tail drop queue. Then, the policies that implement the AQM process can be applied to the tail drop queue corresponding to the token bucket. For example, the AQM process measures some property of the queue, so if the policer was replaced by a corresponding tail drop queue, some properties of the corresponding queue may also correlate with the AQM process.

InFIG.5, the process may assume a token bucket505with rate TR, burst size BS (maximum number of tokens), and current number of tokens Tn. For simplicity, assume TR is provided in packets per second and packets arrive at the token bucket at rate SP. If a queue were implemented instead of token bucket505, the corresponding queue would have a maximum size BS. The packets may be removed from the queue at rate TR, and the queue size would be Qn.

If SP is greater than TR (block560), tokens may be consumed at block510at rate SP and replenished at block520at rate TR, so the net decrease rate is SP−TR, until Tn reaches zero. If a queue were implemented instead of token bucket505, the corresponding queue would be filled at rate SP and emptied at rate TR. The net increase may correspond with SP−TR until Qn reaches BS. For the token bucket, once Tn reaches zero, the committed rate may be applied and packets may be dropped at rate SP−TR. For the queue, once Qn reaches BS, the queue may be full (in tail drop mode) and packets may be dropped at rate SP−TR.

If SP is less than TR, tokens may be replenished at block520at rate TR and consumed at block510at rate SP, so the net increase rate may be TR−SP until Tn reaches BS. If a queue were implemented instead of token bucket505, the corresponding queue, it may be emptied at rate TR and filled at rate SP, so the net decrease may be TR−SP, until Qn reaches zero. For the token bucket, if Tn is not zero, no loss happens. For the queue, if Qn is not BS, no loss happens.

So, with respect to losses, the token bucket505may behave like a tail drop queue of same size and same rate, corresponding with Qn=BS−Tn. The correlation may apply to losses and queue size between the token bucket and the queue, and the delay of packet and the burstiness may be different between the token bucket and the queue. The computation of the delay with the queue may depend on the queue size Qn and the rate TR. The correlation between the queue and token bucket may also apply to the input of the queue (e.g., where packets are admitted to the queue) while the output of the token bucket and the output of queue can be different (e.g., the queue adds delay).

TBAQM500may also apply the AQM process to the state of the corresponding queue that matches the state of the token bucket505. In some examples, a process somewhat similar to CoDel can be implemented (e.g., not the CoDel process since it is difficult to adapt to a token bucket). For example, on periodic basis, CoDel can drop packets from the output of the queue. This can be implemented with TBAQM500where packets are dequeued.

With PIE and PI2, the processing may be completed at the input of the queue, when a data packet is received by the queue. When a data packet is received, the PIE or PI2process decides if it should be marked (e.g., dropped or modified) or enqueued. The fact that most of the processing is at the input of the queue, can make these processes highly compatible with a token bucket.

In some examples, PIE and PI2measure the queue length and the queue output rate to estimate the queue delay. Comparably, with a token bucket, the length of the corresponding queue is the difference between the bucket size and the number of tokens. For TBAQM500that implements token bucket505, replace the queue length in the PIE and PI2processes with BS−Tn.

In some examples, PIE and PI2may use the average dequeue rate of the queue. In the corresponding queue, packets cannot be dequeued at a rate greater than TR (e.g., the committed rate of the token bucket505). The average output rate of the token bucket (e.g., when busy) is its committed rate TR, so that the output rate of the corresponding queue would be the same and the rate cannot exceed TR. The rate can be less than TR if the input rate is lower than TR and the queue become temporarily empty.

However, by having a temporarily empty queue, this may cause starvation of the queue and negatively affect the estimation process of the rate for PIE and PI2. In some examples, the estimation of packet delay in the queue assumes that the estimated rate when the queue is fully busy processing packets, because any queue starvation would not increase packet delay. PIE and PI2may ignore this underestimation of the rate because packet marking may only be needed when the queue is congested. For this reason, TR may be the proper estimate of the dequeue rate for the corresponding queue, and when modeling the process after PIE and PI2, the estimated rate may be replaced with TR.

Packet marking may be implemented when the token bucket is congested. In some examples, the average output rate of the token bucket can correspond with its committed rate. The output rate of the corresponding queue can be the same, therefore when implementing the PIE and PI2processes, TBAQM can replace the estimated rate with TR. In this way, TBAQM500may include a token bucket with a modified PIE or PI2controller545. The queue length variable may be replaced by the inverse of the number of remaining tokens, BS−Tn. The estimated rate variable may be replaced by the committed rate, TR.

In some examples, the PIE and PI2processes can also include two configuration parameters, alpha and beta, that help control the feedback. The PI controller545may compute the marking probability ‘p’ based on PIE or PI2process, and using BS−Tn, TR, alpha and beta. These parameters can depend on TCP congestion control and may be implemented with TBAQM500. For example, PIE and PI2can mark the packet by either modifying or dropping it in action570, depending on support for ECN and SCE. This can remain the same with a token bucket500implemented with TBAQM500. In some examples, TBAQM500can generate ECN and SCE signals, which can help decrease packet losses.

Additional features may be implemented with TBAQM500that are somewhat similar to PIE and PI2. For example, TBAQM500can implement one or more heuristics that are available in PIE. In PI2, the marking probability can be used with TBAQM500to support multiple styles of congestion control (e.g., like classic TCP (probability is squared) and DCTCP (probability is not squared)). When PIE and PI2are applied this way to a token bucket505, they can modify or drop packets as if the token bucket was replaced with a queue, so the impact on TCP can be the same.

TBAQM500can improve a policer by using PIE and PI2signal congestion (e.g., send early congestion signals) by regulating TCP congestion control properly. In this example, there may be less need to make the burst size of the token bucket505small because the traditional downsides associated with a large burst size may be much less likely to happen. The burst size can be safely increased, which can make the token bucket505more friendly to bursty traffic and also decrease packet losses. Through the use of a larger token bucket505size and ECN and SCE marking, TBAQM500can regulate TCP traffic with almost no packet losses and increase network efficiency.

FIG.6illustrates a process implemented by the token bucket with active queue management (TBAQM), in accordance with some examples of the disclosure. In this illustration, TBAQM500ofFIG.5can perform these steps.

At block605, a token bucket505may be implemented with TBAQM500. In this initial step, tokens may also be added to the token bucket based on a configured rate and subtracted based on the data packets processed.

At block610, the token bucket505may receive a data packet.

At block615, TBAQM may determine whether there are tokens remaining in the token bucket. If there are no tokens left, the process may proceed to block620. If there are tokens left, the process may proceed to block625.

At block620, the received data packet is dropped.

At block625, if there are tokens available, TBAQM may compute a marking probability based on the number of remaining tokens. In some examples, the marking probability may correspond with the PIE or PI2processes implemented by TBAQM to compute a marking probability based on the number of tokens. In some examples, the marking probability may correspond with the algorithm that can increase probability as the number of tokens decrease.

At block630, TBAQM may determine whether to mark the data packet. TBAQM500may use a pseudo-random process to decide if the data packet must be marked. The pseudo-random process may be based on the marking probability. If no, the process may proceed to block635. If yes, the process may proceed to block640.

At block635, TBAQM may let the packet pass unmodified to receiver computing device130. This block may allow the packet to pass in an unmodified, will not drop the packet, and will not mark the packet.

At block640, TBAQM may determine whether packet marking is enabled in the data packet and/or whether is data packet marking is implemented and configured in TBAQM500. The determination from this block may either drop the received data packet or change a value in the header of the received data packet. If yes, the process may proceed to block650. If no, the process may proceed to block645.

Various implementations are possible for block640. For example, TBAQM may be statically configured to only drop data packets or only do ECN. In another example, a bit in the TCP header of the data packet indicates if this TCP connection does support ECN or not. If ECN support is indicated, then ECN marking is used. If ECN support is not indicated, data packet dropping is used.

At block645, the data packet may be dropped and not sent to receiver computing device130.

At block650, the packet value in the header may be changed. For example, the bit or flag in the TCP header part of the data packet may be updated from zero to one to indicate congestion. Once the packet value is changed, the data packet may be transmitted from TBAQM to receiver computing device130.

In some examples, the AQM process may be implemented where the queue length variable is replaced by the difference between the bucket size and the number of tokens.

For example, a traditional AQM process may be adapted to a token bucket implementation, at least in part, using a correlation between a policer and a tail drop queue. Then, the policies that implement the AQM process can be applied to the tail drop queue corresponding to the token bucket. For example, the AQM process measures some property of the queue, so if the policer was replaced by a corresponding tail drop queue, some properties of the corresponding queue may also correlate with the AQM process.

In this illustration, assume a token bucket with rate TR, burst size BS (maximum number of tokens), and current number of tokens Tn. For simplicity, assume TR is provided in packets per second and data packets arrive at the token bucket at rate SP. The corresponding queue would have a maximum size BS. The data packets may be removed from the queue at rate TR, and the queue size would be Qn.

If SP is greater than TR, tokens may be consumed at rate SP and replenished at rate TR, so the net decrease rate is SP−TR, until Tn reaches zero. In the corresponding queue, it is filled at rate SP and emptied at rate TR. The net increase may correspond with SP−TR until Qn reaches BS. For the token bucket, once Tn reaches zero, the committed rate may be applied and data packets may be dropped at rate SP−TR. For the queue, once Qn reaches BS, the queue may be full (in tail drop mode) and data packets may be dropped at rate SP−TR.

If SP is less than TR, tokens may be replenished at rate TR and consumed at rate SP, so the net increase rate may be TR−SP until Tn reaches BS. In the corresponding queue, it may be emptied at rate TR and filled at rate SP, so the net decrease may be TR−SP, until Qn reaches zero. For the token bucket, if Tn is not zero, no loss happens. For the queue, if Qn is not BS, no loss happens.

So, with respect to losses, the token bucket may behave like a tail drop queue of same size and same rate, corresponding with Qn=BS−Tn. The correlation may apply to losses and queue size between the token bucket and the queue, and the delay of data packet and the burstiness may be different between the token bucket and the queue. The computation of the delay with the queue may depend on the queue size Qn and the rate TR. The correlation between the queue and token bucket may also apply to the input of the queue (e.g., where data packets are admitted to the queue) while the output of the token bucket and the output of queue can be different (e.g., the queue adds delay).

TBAQM may also apply the AQM process to the state of the corresponding queue that matches the state of the token bucket. In some examples, a process somewhat similar to CoDel can be implemented (e.g., not the CoDel process since it is difficult to adapt to a token bucket). For example, on periodic basis, CoDel can drop data packets from the output of the queue. This can be implemented with TBAQM where data packets are dequeued.

With PIE and PI2, all the processing is done at the input of the queue, when a packet is received by the queue. When a data packet is received, the PIE or PI2process decides if it should be marked (e.g., dropped or modified) or enqueued. The fact that most of the processing is at the input of the queue can make these processes highly compatible with a token bucket.

In some examples, PIE and PI2measure the queue length and the queue output rate to estimate the queue delay. Comparably, with a token bucket, the length of the corresponding queue is the difference between the bucket size and the number of tokens. For TBAQM, replace the queue length in the PIE and PI2processes with BS−Tn.

In some examples, PIE and PI2may use the average dequeue rate of the queue. In the corresponding queue, the data packet cannot be dequeued at a rate greater than TR (e.g., the committed rate of the token bucket). The average output rate of the token bucket (e.g., when busy) is its committed rate TR, so that the output rate of the corresponding queue would be the same and the rate cannot exceed TR. The rate can be less than TR if the input rate is lower than TR and the queue become temporarily empty. However, this may cause starvation of the queue and negatively affect the estimation process of the rate for PIE and PI2. In some examples, the estimation of packet delay in the queue assumes that the estimated rate when the queue is fully busy processing data packets, because any queue starvation would not increase packet delay. PIE and PI2may ignore this underestimation of the rate because packet marking may be needed when the queue is congested. For this reason, TR may be the proper estimate of the dequeue rate for the corresponding queue, and when modeling the process after PIE and PI2, the estimated rate may be replaced with TR.

Packet marking may be implemented when the token bucket is congested. In some examples, the average output rate of the token bucket can correspond with its committed rate. The output rate of the corresponding queue can be the same, therefore when implementing the PIE and PI2processes, TBAQM can replace the estimated rate with TR. In this way, TBAQM may include a token bucket with a modified PIE or PI2controller. The queue length variable may be replaced by the inverse of the number of remaining tokens, BS−Tn. The estimated rate variable may be replaced by the committed rate, TR.

In some examples, the PIE and PI2processes can also include two configuration parameters, alpha and beta, that help control the feedback. These parameters can depend on TCP congestion control and may be implemented with TBAQM. For example, PIE and PI2can mark the data packet by either modifying or dropping it, depending on support for ECN and SCE. This can remain the same with a token bucket implemented with TBAQM. In some examples, TBAQM can generate ECN and SCE signals, which can help decrease data packet losses.

Additional features may be implemented with TBAQM that are somewhat similar to PIE and PI2. For example, TBAQM can implement one or more heuristics that are available in PIE. In PI2, the marking probability can be used with TBAQM to support multiple styles of congestion control (e.g., like classic TCP (probability is squared) and DCTCP (probability is not squared)). When PIE and PI2are applied this way to a token bucket, they can modify or drop data packets exactly as if the token bucket was replaced with a queue, so the impact on TCP can be the same.

TBAQM can improve PIE and PI2signal congestion (e.g., which can implement TCP too early) by regulating TCP congestion control properly. In this example, there may be less need to make the burst size of the token bucket small because the traditional downsides associated with a large burst size may be much less likely to happen. The burst size can be safely increased, which can make the token bucket more friendly to bursty traffic and also decrease data packet losses. Through the use of a larger bucket size and ECN and SCE marking, TBAQM can regulate TCP traffic with almost no data packet losses and increase network efficiency.

It should be noted that the terms “optimize,” “optimal” and the like as used herein can be used to mean making or achieving performance as effective or perfect as possible. However, as one of ordinary skill in the art reading this document will recognize, perfection cannot always be achieved. Accordingly, these terms can also encompass making or achieving performance as good or effective as possible or practical under the given circumstances, or making or achieving performance better than that which can be achieved with other settings or parameters.

FIG.7illustrates an example computing component that may be used to implement a token bucket with active queue management in accordance with various examples. Referring now toFIG.7, computing component700may be, for example, a server computer, a controller, or any other similar computing component capable of processing data. In the example implementation ofFIG.7, the computing component700includes a hardware processor702, and machine-readable storage medium for704.

Hardware processor702may be one or more central processing units (CPUs), semiconductor-based microprocessors, and/or other hardware devices suitable for retrieval and execution of instructions stored in machine-readable storage medium704. Hardware processor702may fetch, decode, and execute instructions, such as instructions706-712, to control processes or operations for implementing a token bucket with active queue management. As an alternative or in addition to retrieving and executing instructions, hardware processor702may include one or more electronic circuits that include electronic components for performing the functionality of one or more instructions, such as a field programmable gate array (FPGA), application specific integrated circuit (ASIC), or other electronic circuits.

Hardware processor702may execute instruction706to receive a data packet. For example, a network device comprising a controller (e.g., that implements a token bucket with active queue management (TBAQM)) may receive the data packet. The data packet may be processed by the TBAQM at the network device.

Hardware processor702may execute instruction708to adjust a number of tokens associated with the TBAQM. For example, the network device may adjust a number of tokens associated with the TBAQM, where the tokens are added based on a configured rate and subtracted in association with processing the data packet.

Hardware processor702may execute instruction710to determine a number of tokens associated with the TBAQM. For example, the network device may determine a number of tokens associated with the TBAQM. When the TBAQM has zero tokens, the network device may drop the data packet. When the TBAQM has more than zero tokens, the network device may determine a marking probability based on the number of tokens.

Hardware processor702may execute instruction712to initiate an action. For example, the network device may initiate an action based on the marking probability. More than one action may be performed, as described throughout the disclosure.

In some examples, the marking probability is based on the number of tokens. The network device may implement a pseudo-random process based on the marking probability; and based on the pseudo-random process, determine that the data packet will be marked as the action.

In some examples, when the data packet will be marked, determine to drop the data packet as the action. In some examples, when the data packet will be marked, determine to change a value in a header of the data packet as the action.

FIG.8depicts a block diagram of an example computer system800in which various of the examples described herein may be implemented. The computer system800includes a bus802or other communication mechanism for communicating information, one or more hardware processors804coupled with bus802for processing information. Hardware processor(s)804may be, for example, one or more general purpose microprocessors.

The computer system800also includes a main memory806, such as a random access memory (RAM), cache and/or other dynamic storage devices, coupled to bus802for storing information and instructions to be executed by processor804. Main memory806also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor804. Such instructions, when stored in storage media accessible to processor804, render computer system800into a special-purpose machine that is customized to perform the operations specified in the instructions.

The computer system800further includes a read only memory (ROM)808or other static storage device coupled to bus802for storing static information and instructions for processor804. A storage device810, such as a magnetic disk, optical disk, or USB thumb drive (Flash drive), is provided and coupled to bus802for storing information and instructions.

The computer system800may be coupled via bus802to a display812, such as a liquid crystal display (LCD) (or touch screen), for displaying information to a computer user. An input device814, including alphanumeric and other keys, is coupled to bus802for communicating information and command selections to processor804. Another type of user input device is cursor control816, such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor804and for controlling cursor movement on display812. In some examples, the same direction information and command selections as cursor control may be implemented via receiving touches on a touch screen without a cursor.

The computer system800also includes a communication interface818coupled to bus802. Communication interface818provides a two-way data communication coupling to one or more network links that are connected to one or more local networks. For example, communication interface818may be an integrated services digital network (ISDN) card, cable modem, satellite modem, or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface818may be a local area network (LAN) card to provide a data communication connection to a compatible LAN (or WAN component to communicated with a WAN). Wireless links may also be implemented. In any such implementation, communication interface818sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

The computer system800can send messages and receive data, including program code, through the network(s), network link and communication interface818. In the Internet example, a server might transmit a requested code for an application program through the Internet, the ISP, the local network and the communication interface818.