1.. SPDX-License-Identifier: BSD-3-Clause 2 Copyright(c) 2010-2014 Intel Corporation. 3 4Quality of Service (QoS) Framework 5================================== 6 7This chapter describes the DPDK Quality of Service (QoS) framework. 8 9Packet Pipeline with QoS Support 10-------------------------------- 11 12An example of a complex packet processing pipeline with QoS support is shown in the following figure. 13 14.. _figure_pkt_proc_pipeline_qos: 15 16.. figure:: img/pkt_proc_pipeline_qos.* 17 18 Complex Packet Processing Pipeline with QoS Support 19 20 21This pipeline can be built using reusable DPDK software libraries. 22The main blocks implementing QoS in this pipeline are: the policer, the dropper and the scheduler. 23A functional description of each block is provided in the following table. 24 25.. _table_qos_1: 26 27.. table:: Packet Processing Pipeline Implementing QoS 28 29 +---+------------------------+--------------------------------------------------------------------------------+ 30 | # | Block | Functional Description | 31 | | | | 32 +===+========================+================================================================================+ 33 | 1 | Packet I/O RX & TX | Packet reception/ transmission from/to multiple NIC ports. Poll mode drivers | 34 | | | (PMDs) for Intel 1 GbE/10 GbE NICs. | 35 | | | | 36 +---+------------------------+--------------------------------------------------------------------------------+ 37 | 2 | Packet parser | Identify the protocol stack of the input packet. Check the integrity of the | 38 | | | packet headers. | 39 | | | | 40 +---+------------------------+--------------------------------------------------------------------------------+ 41 | 3 | Flow classification | Map the input packet to one of the known traffic flows. Exact match table | 42 | | | lookup using configurable hash function (jhash, CRC and so on) and bucket | 43 | | | logic to handle collisions. | 44 | | | | 45 +---+------------------------+--------------------------------------------------------------------------------+ 46 | 4 | Policer | Packet metering using srTCM (RFC 2697) or trTCM (RFC2698) algorithms. | 47 | | | | 48 +---+------------------------+--------------------------------------------------------------------------------+ 49 | 5 | Load Balancer | Distribute the input packets to the application workers. Provide uniform load | 50 | | | to each worker. Preserve the affinity of traffic flows to workers and the | 51 | | | packet order within each flow. | 52 | | | | 53 +---+------------------------+--------------------------------------------------------------------------------+ 54 | 6 | Worker threads | Placeholders for the customer specific application workload (for example, IP | 55 | | | stack and so on). | 56 | | | | 57 +---+------------------------+--------------------------------------------------------------------------------+ 58 | 7 | Dropper | Congestion management using the Random Early Detection (RED) algorithm | 59 | | | (specified by the Sally Floyd - Van Jacobson paper) or Weighted RED (WRED). | 60 | | | Drop packets based on the current scheduler queue load level and packet | 61 | | | priority. When congestion is experienced, lower priority packets are dropped | 62 | | | first. | 63 | | | | 64 +---+------------------------+--------------------------------------------------------------------------------+ 65 | 8 | Hierarchical Scheduler | 5-level hierarchical scheduler (levels are: output port, subport, pipe, | 66 | | | traffic class and queue) with thousands (typically 64K) leaf nodes (queues). | 67 | | | Implements traffic shaping (for subport and pipe levels), strict priority | 68 | | | (for traffic class level) and Weighted Round Robin (WRR) (for queues within | 69 | | | each pipe traffic class). | 70 | | | | 71 +---+------------------------+--------------------------------------------------------------------------------+ 72 73The infrastructure blocks used throughout the packet processing pipeline are listed in the following table. 74 75.. _table_qos_2: 76 77.. table:: Infrastructure Blocks Used by the Packet Processing Pipeline 78 79 +---+-----------------------+-----------------------------------------------------------------------+ 80 | # | Block | Functional Description | 81 | | | | 82 +===+=======================+=======================================================================+ 83 | 1 | Buffer manager | Support for global buffer pools and private per-thread buffer caches. | 84 | | | | 85 +---+-----------------------+-----------------------------------------------------------------------+ 86 | 2 | Queue manager | Support for message passing between pipeline blocks. | 87 | | | | 88 +---+-----------------------+-----------------------------------------------------------------------+ 89 | 3 | Power saving | Support for power saving during low activity periods. | 90 | | | | 91 +---+-----------------------+-----------------------------------------------------------------------+ 92 93The mapping of pipeline blocks to CPU cores is configurable based on the performance level required by each specific application 94and the set of features enabled for each block. 95Some blocks might consume more than one CPU core (with each CPU core running a different instance of the same block on different input packets), 96while several other blocks could be mapped to the same CPU core. 97 98Hierarchical Scheduler 99---------------------- 100 101The hierarchical scheduler block, when present, usually sits on the TX side just before the transmission stage. 102Its purpose is to prioritize the transmission of packets from different users and different traffic classes 103according to the policy specified by the Service Level Agreements (SLAs) of each network node. 104 105Overview 106~~~~~~~~ 107 108The hierarchical scheduler block is similar to the traffic manager block used by network processors 109that typically implement per flow (or per group of flows) packet queuing and scheduling. 110It typically acts like a buffer that is able to temporarily store a large number of packets just before their transmission (enqueue operation); 111as the NIC TX is requesting more packets for transmission, 112these packets are later on removed and handed over to the NIC TX with the packet selection logic observing the predefined SLAs (dequeue operation). 113 114.. _figure_hier_sched_blk: 115 116.. figure:: img/hier_sched_blk.* 117 118 Hierarchical Scheduler Block Internal Diagram 119 120 121The hierarchical scheduler is optimized for a large number of packet queues. 122When only a small number of queues are needed, message passing queues should be used instead of this block. 123See `Worst Case Scenarios for Performance`_ for a more detailed discussion. 124 125Scheduling Hierarchy 126~~~~~~~~~~~~~~~~~~~~ 127 128The scheduling hierarchy is shown in :numref:`figure_sched_hier_per_port`. 129The first level of the hierarchy is the Ethernet TX port 1/10/40 GbE, 130with subsequent hierarchy levels defined as subport, pipe, traffic class and queue. 131 132Typically, each subport represents a predefined group of users, while each pipe represents an individual user/subscriber. 133Each traffic class is the representation of a different traffic type with specific loss rate, 134delay and jitter requirements, such as voice, video or data transfers. 135Each queue hosts packets from one or multiple connections of the same type belonging to the same user. 136 137.. _figure_sched_hier_per_port: 138 139.. figure:: img/sched_hier_per_port.* 140 141 Scheduling Hierarchy per Port 142 143 144The functionality of each hierarchical level is detailed in the following table. 145 146.. _table_qos_3: 147 148.. table:: Port Scheduling Hierarchy 149 150 +---+--------------------+----------------------------+---------------------------------------------------------------+ 151 | # | Level | Siblings per Parent | Functional Description | 152 | | | | | 153 +===+====================+============================+===============================================================+ 154 | 1 | Port | - | #. Output Ethernet port 1/10/40 GbE. | 155 | | | | | 156 | | | | #. Multiple ports are scheduled in round robin order with | 157 | | | | all ports having equal priority. | 158 | | | | | 159 +---+--------------------+----------------------------+---------------------------------------------------------------+ 160 | 2 | Subport | Configurable (default: 8) | #. Traffic shaping using token bucket algorithm (one token | 161 | | | | bucket per subport). | 162 | | | | | 163 | | | | #. Upper limit enforced per Traffic Class (TC) at the | 164 | | | | subport level. | 165 | | | | | 166 | | | | #. Lower priority TCs able to reuse subport bandwidth | 167 | | | | currently unused by higher priority TCs. | 168 | | | | | 169 +---+--------------------+----------------------------+---------------------------------------------------------------+ 170 | 3 | Pipe | Configurable (default: 4K) | #. Traffic shaping using the token bucket algorithm (one | 171 | | | | token bucket per pipe. | 172 | | | | | 173 +---+--------------------+----------------------------+---------------------------------------------------------------+ 174 | 4 | Traffic Class (TC) | 13 | #. TCs of the same pipe handled in strict priority order. | 175 | | | | | 176 | | | | #. Upper limit enforced per TC at the pipe level. | 177 | | | | | 178 | | | | #. Lower priority TCs able to reuse pipe bandwidth currently | 179 | | | | unused by higher priority TCs. | 180 | | | | | 181 | | | | #. When subport TC is oversubscribed (configuration time | 182 | | | | event), pipe TC upper limit is capped to a dynamically | 183 | | | | adjusted value that is shared by all the subport pipes. | 184 | | | | | 185 +---+--------------------+----------------------------+---------------------------------------------------------------+ 186 | 5 | Queue | High priority TCs: 1, | #. All the high priority TCs (TC0, TC1, ...,TC11) have | 187 | | | Lowest priority TC: 4 | exactly 1 queue, while the lowest priority TC (TC12), | 188 | | | | called Best Effort (BE), has 4 queues. | 189 | | | | | 190 | | | | #. Queues of the lowest priority TC (BE) are serviced using | 191 | | | | Weighted Round Robin (WRR) according to predefined weights| 192 | | | | weights. | 193 | | | | | 194 +---+--------------------+----------------------------+---------------------------------------------------------------+ 195 196Application Programming Interface (API) 197~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 198 199Port Scheduler Configuration API 200^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 201 202The rte_sched.h file contains configuration functions for port, subport and pipe. 203 204Port Scheduler Enqueue API 205^^^^^^^^^^^^^^^^^^^^^^^^^^ 206 207The port scheduler enqueue API is very similar to the API of the DPDK PMD TX function. 208 209.. code-block:: c 210 211 int rte_sched_port_enqueue(struct rte_sched_port *port, struct rte_mbuf **pkts, uint32_t n_pkts); 212 213Port Scheduler Dequeue API 214^^^^^^^^^^^^^^^^^^^^^^^^^^ 215 216The port scheduler dequeue API is very similar to the API of the DPDK PMD RX function. 217 218.. code-block:: c 219 220 int rte_sched_port_dequeue(struct rte_sched_port *port, struct rte_mbuf **pkts, uint32_t n_pkts); 221 222Usage Example 223^^^^^^^^^^^^^ 224 225.. code-block:: c 226 227 /* File "application.c" */ 228 229 #define N_PKTS_RX 64 230 #define N_PKTS_TX 48 231 #define NIC_RX_PORT 0 232 #define NIC_RX_QUEUE 0 233 #define NIC_TX_PORT 1 234 #define NIC_TX_QUEUE 0 235 236 struct rte_sched_port *port = NULL; 237 struct rte_mbuf *pkts_rx[N_PKTS_RX], *pkts_tx[N_PKTS_TX]; 238 uint32_t n_pkts_rx, n_pkts_tx; 239 240 /* Initialization */ 241 242 <initialization code> 243 244 /* Runtime */ 245 while (1) { 246 /* Read packets from NIC RX queue */ 247 248 n_pkts_rx = rte_eth_rx_burst(NIC_RX_PORT, NIC_RX_QUEUE, pkts_rx, N_PKTS_RX); 249 250 /* Hierarchical scheduler enqueue */ 251 252 rte_sched_port_enqueue(port, pkts_rx, n_pkts_rx); 253 254 /* Hierarchical scheduler dequeue */ 255 256 n_pkts_tx = rte_sched_port_dequeue(port, pkts_tx, N_PKTS_TX); 257 258 /* Write packets to NIC TX queue */ 259 260 rte_eth_tx_burst(NIC_TX_PORT, NIC_TX_QUEUE, pkts_tx, n_pkts_tx); 261 } 262 263Implementation 264~~~~~~~~~~~~~~ 265 266Internal Data Structures per Port 267^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 268 269A schematic of the internal data structures in shown in with details in. 270 271.. _figure_data_struct_per_port: 272 273.. figure:: img/data_struct_per_port.* 274 275 Internal Data Structures per Port 276 277 278.. _table_qos_4: 279 280.. table:: Scheduler Internal Data Structures per Port 281 282 +---+----------------------+-------------------------+---------------------+------------------------------+---------------------------------------------------+ 283 | # | Data structure | Size (bytes) | # per port | Access type | Description | 284 | | | | | | | 285 | | | | +-------------+----------------+---------------------------------------------------+ 286 | | | | | Enq | Deq | | 287 | | | | | | | | 288 +===+======================+=========================+=====================+=============+================+===================================================+ 289 | 1 | Subport table entry | 64 | # subports per port | - | Rd, Wr | Persistent subport data (credits, etc). | 290 | | | | | | | | 291 +---+----------------------+-------------------------+---------------------+-------------+----------------+---------------------------------------------------+ 292 | 2 | Pipe table entry | 64 | # pipes per port | - | Rd, Wr | Persistent data for pipe, its TCs and its queues | 293 | | | | | | | (credits, etc) that is updated during run-time. | 294 | | | | | | | | 295 | | | | | | | The pipe configuration parameters do not change | 296 | | | | | | | during run-time. The same pipe configuration | 297 | | | | | | | parameters are shared by multiple pipes, | 298 | | | | | | | therefore they are not part of pipe table entry. | 299 | | | | | | | | 300 +---+----------------------+-------------------------+---------------------+-------------+----------------+---------------------------------------------------+ 301 | 3 | Queue table entry | 4 | #queues per port | Rd, Wr | Rd, Wr | Persistent queue data (read and write pointers). | 302 | | | | | | | The queue size is the same per TC for all queues, | 303 | | | | | | | allowing the queue base address to be computed | 304 | | | | | | | using a fast formula, so these two parameters are | 305 | | | | | | | not part of queue table entry. | 306 | | | | | | | | 307 | | | | | | | The queue table entries for any given pipe are | 308 | | | | | | | stored in the same cache line. | 309 | | | | | | | | 310 +---+----------------------+-------------------------+---------------------+-------------+----------------+---------------------------------------------------+ 311 | 4 | Queue storage area | Config (default: 64 x8) | # queues per port | Wr | Rd | Array of elements per queue; each element is 8 | 312 | | | | | | | byte in size (mbuf pointer). | 313 | | | | | | | | 314 +---+----------------------+-------------------------+---------------------+-------------+----------------+---------------------------------------------------+ 315 | 5 | Active queues bitmap | 1 bit per queue | 1 | Wr (Set) | Rd, Wr (Clear) | The bitmap maintains one status bit per queue: | 316 | | | | | | | queue not active (queue is empty) or queue active | 317 | | | | | | | (queue is not empty). | 318 | | | | | | | | 319 | | | | | | | Queue bit is set by the scheduler enqueue and | 320 | | | | | | | cleared by the scheduler dequeue when queue | 321 | | | | | | | becomes empty. | 322 | | | | | | | | 323 | | | | | | | Bitmap scan operation returns the next non-empty | 324 | | | | | | | pipe and its status (16-bit mask of active queue | 325 | | | | | | | in the pipe). | 326 | | | | | | | | 327 +---+----------------------+-------------------------+---------------------+-------------+----------------+---------------------------------------------------+ 328 | 6 | Grinder | ~128 | Config (default: 8) | - | Rd, Wr | Short list of active pipes currently under | 329 | | | | | | | processing. The grinder contains temporary data | 330 | | | | | | | during pipe processing. | 331 | | | | | | | | 332 | | | | | | | Once the current pipe exhausts packets or | 333 | | | | | | | credits, it is replaced with another active pipe | 334 | | | | | | | from the bitmap. | 335 | | | | | | | | 336 +---+----------------------+-------------------------+---------------------+-------------+----------------+---------------------------------------------------+ 337 338Multicore Scaling Strategy 339^^^^^^^^^^^^^^^^^^^^^^^^^^ 340 341The multicore scaling strategy is: 342 343#. Running different physical ports on different threads. The enqueue and dequeue of the same port are run by the same thread. 344 345#. Splitting the same physical port to different threads by running different sets of subports of the same physical port (virtual ports) on different threads. 346 Similarly, a subport can be split into multiple subports that are each run by a different thread. 347 The enqueue and dequeue of the same port are run by the same thread. 348 This is only required if, for performance reasons, it is not possible to handle a full port with a single core. 349 350Enqueue and Dequeue for the Same Output Port 351"""""""""""""""""""""""""""""""""""""""""""" 352 353Running enqueue and dequeue operations for the same output port from different cores is likely to cause significant impact on scheduler's performance 354and it is therefore not recommended. 355 356The port enqueue and dequeue operations share access to the following data structures: 357 358#. Packet descriptors 359 360#. Queue table 361 362#. Queue storage area 363 364#. Bitmap of active queues 365 366The expected drop in performance is due to: 367 368#. Need to make the queue and bitmap operations thread safe, 369 which requires either using locking primitives for access serialization (for example, spinlocks/ semaphores) or 370 using atomic primitives for lockless access (for example, Test and Set, Compare And Swap, an so on). 371 The impact is much higher in the former case. 372 373#. Ping-pong of cache lines storing the shared data structures between the cache hierarchies of the two cores 374 (done transparently by the MESI protocol cache coherency CPU hardware). 375 376Therefore, the scheduler enqueue and dequeue operations have to be run from the same thread, 377which allows the queues and the bitmap operations to be non-thread safe and 378keeps the scheduler data structures internal to the same core. 379 380Performance Scaling 381""""""""""""""""""" 382 383Scaling up the number of NIC ports simply requires a proportional increase in the number of CPU cores to be used for traffic scheduling. 384 385Enqueue Pipeline 386^^^^^^^^^^^^^^^^ 387 388The sequence of steps per packet: 389 390#. *Access* the mbuf to read the data fields required to identify the destination queue for the packet. 391 These fields are: port, subport, traffic class and queue within traffic class, and are typically set by the classification stage. 392 393#. *Access* the queue structure to identify the write location in the queue array. 394 If the queue is full, then the packet is discarded. 395 396#. *Access* the queue array location to store the packet (i.e. write the mbuf pointer). 397 398It should be noted the strong data dependency between these steps, as steps 2 and 3 cannot start before the result from steps 1 and 2 becomes available, 399which prevents the processor out of order execution engine to provide any significant performance optimizations. 400 401Given the high rate of input packets and the large amount of queues, 402it is expected that the data structures accessed to enqueue the current packet are not present 403in the L1 or L2 data cache of the current core, thus the above 3 memory accesses would result (on average) in L1 and L2 data cache misses. 404A number of 3 L1/L2 cache misses per packet is not acceptable for performance reasons. 405 406The workaround is to prefetch the required data structures in advance. The prefetch operation has an execution latency during which 407the processor should not attempt to access the data structure currently under prefetch, so the processor should execute other work. 408The only other work available is to execute different stages of the enqueue sequence of operations on other input packets, 409thus resulting in a pipelined implementation for the enqueue operation. 410 411:numref:`figure_prefetch_pipeline` illustrates a pipelined implementation for the enqueue operation with 4 pipeline stages and each stage executing 2 different input packets. 412No input packet can be part of more than one pipeline stage at a given time. 413 414.. _figure_prefetch_pipeline: 415 416.. figure:: img/prefetch_pipeline.* 417 418 Prefetch Pipeline for the Hierarchical Scheduler Enqueue Operation 419 420 421The congestion management scheme implemented by the enqueue pipeline described above is very basic: 422packets are enqueued until a specific queue becomes full, 423then all the packets destined to the same queue are dropped until packets are consumed (by the dequeue operation). 424This can be improved by enabling RED/WRED as part of the enqueue pipeline which looks at the queue occupancy and 425packet priority in order to yield the enqueue/drop decision for a specific packet 426(as opposed to enqueuing all packets / dropping all packets indiscriminately). 427 428Dequeue State Machine 429^^^^^^^^^^^^^^^^^^^^^ 430 431The sequence of steps to schedule the next packet from the current pipe is: 432 433#. Identify the next active pipe using the bitmap scan operation, *prefetch* pipe. 434 435#. *Read* pipe data structure. Update the credits for the current pipe and its subport. 436 Identify the first active traffic class within the current pipe, select the next queue using WRR, 437 *prefetch* queue pointers for all the 16 queues of the current pipe. 438 439#. *Read* next element from the current WRR queue and *prefetch* its packet descriptor. 440 441#. *Read* the packet length from the packet descriptor (mbuf structure). 442 Based on the packet length and the available credits (of current pipe, pipe traffic class, subport and subport traffic class), 443 take the go/no go scheduling decision for the current packet. 444 445To avoid the cache misses, the above data structures (pipe, queue, queue array, mbufs) are prefetched in advance of being accessed. 446The strategy of hiding the latency of the prefetch operations is to switch from the current pipe (in grinder A) to another pipe 447(in grinder B) immediately after a prefetch is issued for the current pipe. 448This gives enough time to the prefetch operation to complete before the execution switches back to this pipe (in grinder A). 449 450The dequeue pipe state machine exploits the data presence into the processor cache, 451therefore it tries to send as many packets from the same pipe TC and pipe as possible (up to the available packets and credits) before 452moving to the next active TC from the same pipe (if any) or to another active pipe. 453 454.. _figure_pipe_prefetch_sm: 455 456.. figure:: img/pipe_prefetch_sm.* 457 458 Pipe Prefetch State Machine for the Hierarchical Scheduler Dequeue 459 Operation 460 461 462Timing and Synchronization 463^^^^^^^^^^^^^^^^^^^^^^^^^^ 464 465The output port is modeled as a conveyor belt of byte slots that need to be filled by the scheduler with data for transmission. 466For 10 GbE, there are 1.25 billion byte slots that need to be filled by the port scheduler every second. 467If the scheduler is not fast enough to fill the slots, provided that enough packets and credits exist, 468then some slots will be left unused and bandwidth will be wasted. 469 470In principle, the hierarchical scheduler dequeue operation should be triggered by NIC TX. 471Usually, once the occupancy of the NIC TX input queue drops below a predefined threshold, 472the port scheduler is woken up (interrupt based or polling based, 473by continuously monitoring the queue occupancy) to push more packets into the queue. 474 475Internal Time Reference 476""""""""""""""""""""""" 477 478The scheduler needs to keep track of time advancement for the credit logic, 479which requires credit updates based on time (for example, subport and pipe traffic shaping, traffic class upper limit enforcement, and so on). 480 481Every time the scheduler decides to send a packet out to the NIC TX for transmission, the scheduler will increment its internal time reference accordingly. 482Therefore, it is convenient to keep the internal time reference in units of bytes, 483where a byte signifies the time duration required by the physical interface to send out a byte on the transmission medium. 484This way, as a packet is scheduled for transmission, the time is incremented with (n + h), 485where n is the packet length in bytes and h is the number of framing overhead bytes per packet. 486 487Internal Time Reference Re-synchronization 488"""""""""""""""""""""""""""""""""""""""""" 489 490The scheduler needs to align its internal time reference to the pace of the port conveyor belt. 491The reason is to make sure that the scheduler does not feed the NIC TX with more bytes than the line rate of the physical medium in order to prevent packet drop 492(by the scheduler, due to the NIC TX input queue being full, or later on, internally by the NIC TX). 493 494The scheduler reads the current time on every dequeue invocation. 495The CPU time stamp can be obtained by reading either the Time Stamp Counter (TSC) register or the High Precision Event Timer (HPET) register. 496The current CPU time stamp is converted from number of CPU clocks to number of bytes: 497*time_bytes = time_cycles / cycles_per_byte, where cycles_per_byte* 498is the amount of CPU cycles that is equivalent to the transmission time for one byte on the wire 499(e.g. for a CPU frequency of 2 GHz and a 10GbE port,*cycles_per_byte = 1.6*). 500 501The scheduler maintains an internal time reference of the NIC time. 502Whenever a packet is scheduled, the NIC time is incremented with the packet length (including framing overhead). 503On every dequeue invocation, the scheduler checks its internal reference of the NIC time against the current time: 504 505#. If NIC time is in the future (NIC time >= current time), no adjustment of NIC time is needed. 506 This means that scheduler is able to schedule NIC packets before the NIC actually needs those packets, so the NIC TX is well supplied with packets; 507 508#. If NIC time is in the past (NIC time < current time), then NIC time should be adjusted by setting it to the current time. 509 This means that the scheduler is not able to keep up with the speed of the NIC byte conveyor belt, 510 so NIC bandwidth is wasted due to poor packet supply to the NIC TX. 511 512Scheduler Accuracy and Granularity 513"""""""""""""""""""""""""""""""""" 514 515The scheduler round trip delay (SRTD) is the time (number of CPU cycles) between two consecutive examinations of the same pipe by the scheduler. 516 517To keep up with the output port (that is, avoid bandwidth loss), 518the scheduler should be able to schedule n packets faster than the same n packets are transmitted by NIC TX. 519 520The scheduler needs to keep up with the rate of each individual pipe, 521as configured for the pipe token bucket, assuming that no port oversubscription is taking place. 522This means that the size of the pipe token bucket should be set high enough to prevent it from overflowing due to big SRTD, 523as this would result in credit loss (and therefore bandwidth loss) for the pipe. 524 525Credit Logic 526^^^^^^^^^^^^ 527 528Scheduling Decision 529""""""""""""""""""" 530 531The scheduling decision to send next packet from (subport S, pipe P, traffic class TC, queue Q) is favorable (packet is sent) 532when all the conditions below are met: 533 534* Pipe P of subport S is currently selected by one of the port grinders; 535 536* Traffic class TC is the highest priority active traffic class of pipe P; 537 538* Queue Q is the next queue selected by WRR within traffic class TC of pipe P; 539 540* Subport S has enough credits to send the packet; 541 542* Subport S has enough credits for traffic class TC to send the packet; 543 544* Pipe P has enough credits to send the packet; 545 546* Pipe P has enough credits for traffic class TC to send the packet. 547 548If all the above conditions are met, 549then the packet is selected for transmission and the necessary credits are subtracted from subport S, 550subport S traffic class TC, pipe P, pipe P traffic class TC. 551 552Framing Overhead 553"""""""""""""""" 554 555As the greatest common divisor for all packet lengths is one byte, the unit of credit is selected as one byte. 556The number of credits required for the transmission of a packet of n bytes is equal to (n+h), 557where h is equal to the number of framing overhead bytes per packet. 558 559.. _table_qos_5: 560 561.. table:: Ethernet Frame Overhead Fields 562 563 +---+--------------------------------+----------------+---------------------------------------------------------------------------+ 564 | # | Packet field | Length (bytes) | Comments | 565 | | | | | 566 +===+================================+================+===========================================================================+ 567 | 1 | Preamble | 7 | | 568 | | | | | 569 +---+--------------------------------+----------------+---------------------------------------------------------------------------+ 570 | 2 | Start of Frame Delimiter (SFD) | 1 | | 571 | | | | | 572 +---+--------------------------------+----------------+---------------------------------------------------------------------------+ 573 | 3 | Frame Check Sequence (FCS) | 4 | Considered overhead only if not included in the mbuf packet length field. | 574 | | | | | 575 +---+--------------------------------+----------------+---------------------------------------------------------------------------+ 576 | 4 | Inter Frame Gap (IFG) | 12 | | 577 | | | | | 578 +---+--------------------------------+----------------+---------------------------------------------------------------------------+ 579 | 5 | Total | 24 | | 580 | | | | | 581 +---+--------------------------------+----------------+---------------------------------------------------------------------------+ 582 583Traffic Shaping 584""""""""""""""" 585 586The traffic shaping for subport and pipe is implemented using a token bucket per subport/per pipe. 587Each token bucket is implemented using one saturated counter that keeps track of the number of available credits. 588 589The token bucket generic parameters and operations are presented in :numref:`table_qos_6` and :numref:`table_qos_7`. 590 591.. _table_qos_6: 592 593.. table:: Token Bucket Generic Parameters 594 595 +---+------------------------+--------------------+---------------------------------------------------------+ 596 | # | Token Bucket Parameter | Unit | Description | 597 | | | | | 598 +===+========================+====================+=========================================================+ 599 | 1 | bucket_rate | Credits per second | Rate of adding credits to the bucket. | 600 | | | | | 601 +---+------------------------+--------------------+---------------------------------------------------------+ 602 | 2 | bucket_size | Credits | Max number of credits that can be stored in the bucket. | 603 | | | | | 604 +---+------------------------+--------------------+---------------------------------------------------------+ 605 606.. _table_qos_7: 607 608.. table:: Token Bucket Generic Operations 609 610 +---+------------------------+------------------------------------------------------------------------------+ 611 | # | Token Bucket Operation | Description | 612 | | | | 613 +===+========================+==============================================================================+ 614 | 1 | Initialization | Bucket set to a predefined value, e.g. zero or half of the bucket size. | 615 | | | | 616 +---+------------------------+------------------------------------------------------------------------------+ 617 | 2 | Credit update | Credits are added to the bucket on top of existing ones, either periodically | 618 | | | or on demand, based on the bucket_rate. Credits cannot exceed the upper | 619 | | | limit defined by the bucket_size, so any credits to be added to the bucket | 620 | | | while the bucket is full are dropped. | 621 | | | | 622 +---+------------------------+------------------------------------------------------------------------------+ 623 | 3 | Credit consumption | As result of packet scheduling, the necessary number of credits is removed | 624 | | | from the bucket. The packet can only be sent if enough credits are in the | 625 | | | bucket to send the full packet (packet bytes and framing overhead for the | 626 | | | packet). | 627 | | | | 628 +---+------------------------+------------------------------------------------------------------------------+ 629 630To implement the token bucket generic operations described above, 631the current design uses the persistent data structure presented in :numref:`table_qos_8`, 632while the implementation of the token bucket operations is described in :numref:`table_qos_9`. 633 634.. _table_qos_8: 635 636.. table:: Token Bucket Persistent Data Structure 637 638 +---+------------------------+-------+----------------------------------------------------------------------+ 639 | # | Token bucket field | Unit | Description | 640 | | | | | 641 +===+========================+=======+======================================================================+ 642 | 1 | tb_time | Bytes | Time of the last credit update. Measured in bytes instead of seconds | 643 | | | | or CPU cycles for ease of credit consumption operation | 644 | | | | (as the current time is also maintained in bytes). | 645 | | | | | 646 | | | | See Section 26.2.4.5.1 "Internal Time Reference" for an | 647 | | | | explanation of why the time is maintained in byte units. | 648 | | | | | 649 +---+------------------------+-------+----------------------------------------------------------------------+ 650 | 2 | tb_period | Bytes | Time period that should elapse since the last credit update in order | 651 | | | | for the bucket to be awarded tb_credits_per_period worth or credits. | 652 | | | | | 653 +---+------------------------+-------+----------------------------------------------------------------------+ 654 | 3 | tb_credits_per_period | Bytes | Credit allowance per tb_period. | 655 | | | | | 656 +---+------------------------+-------+----------------------------------------------------------------------+ 657 | 4 | tb_size | Bytes | Bucket size, i.e. upper limit for the tb_credits. | 658 | | | | | 659 +---+------------------------+-------+----------------------------------------------------------------------+ 660 | 5 | tb_credits | Bytes | Number of credits currently in the bucket. | 661 | | | | | 662 +---+------------------------+-------+----------------------------------------------------------------------+ 663 664The bucket rate (in bytes per second) can be computed with the following formula: 665 666*bucket_rate = (tb_credits_per_period / tb_period) * r* 667 668where, r = port line rate (in bytes per second). 669 670.. _table_qos_9: 671 672.. table:: Token Bucket Operations 673 674 +---+-------------------------+-----------------------------------------------------------------------------+ 675 | # | Token bucket operation | Description | 676 | | | | 677 +===+=========================+=============================================================================+ 678 | 1 | Initialization | *tb_credits = 0; or tb_credits = tb_size / 2;* | 679 | | | | 680 +---+-------------------------+-----------------------------------------------------------------------------+ 681 | 2 | Credit update | Credit update options: | 682 | | | | 683 | | | * Every time a packet is sent for a port, update the credits of all the | 684 | | | the subports and pipes of that port. Not feasible. | 685 | | | | 686 | | | * Every time a packet is sent, update the credits for the pipe and | 687 | | | subport. Very accurate, but not needed (a lot of calculations). | 688 | | | | 689 | | | * Every time a pipe is selected (that is, picked by one | 690 | | | of the grinders), update the credits for the pipe and its subport. | 691 | | | | 692 | | | The current implementation is using option 3. According to Section | 693 | | | `Dequeue State Machine`_, the pipe and subport credits are | 694 | | | updated every time a pipe is selected by the dequeue process before the | 695 | | | pipe and subport credits are actually used. | 696 | | | | 697 | | | The implementation uses a tradeoff between accuracy and speed by updating | 698 | | | the bucket credits only when at least a full *tb_period* has elapsed since | 699 | | | the last update. | 700 | | | | 701 | | | * Full accuracy can be achieved by selecting the value for *tb_period* | 702 | | | for which *tb_credits_per_period = 1*. | 703 | | | | 704 | | | * When full accuracy is not required, better performance is achieved by | 705 | | | setting *tb_credits* to a larger value. | 706 | | | | 707 | | | Update operations: | 708 | | | | 709 | | | * n_periods = (time - tb_time) / tb_period; | 710 | | | | 711 | | | * tb_credits += n_periods * tb_credits_per_period; | 712 | | | | 713 | | | * tb_credits = min(tb_credits, tb_size); | 714 | | | | 715 | | | * tb_time += n_periods * tb_period; | 716 | | | | 717 +---+-------------------------+-----------------------------------------------------------------------------+ 718 | 3 | Credit consumption | As result of packet scheduling, the necessary number of credits is removed | 719 | | (on packet scheduling) | from the bucket. The packet can only be sent if enough credits are in the | 720 | | | bucket to send the full packet (packet bytes and framing overhead for the | 721 | | | packet). | 722 | | | | 723 | | | Scheduling operations: | 724 | | | | 725 | | | pkt_credits = pkt_len + frame_overhead; | 726 | | | if (tb_credits >= pkt_credits){tb_credits -= pkt_credits;} | 727 | | | | 728 +---+-------------------------+-----------------------------------------------------------------------------+ 729 730Traffic Classes 731""""""""""""""" 732 733Implementation of Strict Priority Scheduling 734'''''''''''''''''''''''''''''''''''''''''''' 735 736Strict priority scheduling of traffic classes within the same pipe is implemented by the pipe dequeue state machine, 737which selects the queues in ascending order. 738Therefore, queue 0 (associated with TC 0, highest priority TC) is handled before 739queue 1 (TC 1, lower priority than TC 0), 740which is handled before queue 2 (TC 2, lower priority than TC 1) and it conitnues until queues of all TCs except the 741lowest priority TC are handled. At last, queues 12..15 (best effort TC, lowest priority TC) are handled. 742 743Upper Limit Enforcement 744''''''''''''''''''''''' 745 746The traffic classes at the pipe and subport levels are not traffic shaped, 747so there is no token bucket maintained in this context. 748The upper limit for the traffic classes at the subport and 749pipe levels is enforced by periodically refilling the subport / pipe traffic class credit counter, 750out of which credits are consumed every time a packet is scheduled for that subport / pipe, 751as described in :numref:`table_qos_10` and :numref:`table_qos_11`. 752 753.. _table_qos_10: 754 755.. table:: Subport/Pipe Traffic Class Upper Limit Enforcement Persistent Data Structure 756 757 +---+-----------------------+-------+-----------------------------------------------------------------------+ 758 | # | Subport or pipe field | Unit | Description | 759 | | | | | 760 +===+=======================+=======+=======================================================================+ 761 | 1 | tc_time | Bytes | Time of the next update (upper limit refill) for the TCs of the | 762 | | | | current subport / pipe. | 763 | | | | | 764 | | | | See Section `Internal Time Reference`_ for the | 765 | | | | explanation of why the time is maintained in byte units. | 766 | | | | | 767 +---+-----------------------+-------+-----------------------------------------------------------------------+ 768 | 2 | tc_period | Bytes | Time between two consecutive updates for the all TCs of the current | 769 | | | | subport / pipe. This is expected to be many times bigger than the | 770 | | | | typical value of the token bucket tb_period. | 771 | | | | | 772 +---+-----------------------+-------+-----------------------------------------------------------------------+ 773 | 3 | tc_credits_per_period | Bytes | Upper limit for the number of credits allowed to be consumed by the | 774 | | | | current TC during each enforcement period tc_period. | 775 | | | | | 776 +---+-----------------------+-------+-----------------------------------------------------------------------+ 777 | 4 | tc_credits | Bytes | Current upper limit for the number of credits that can be consumed by | 778 | | | | the current traffic class for the remainder of the current | 779 | | | | enforcement period. | 780 | | | | | 781 +---+-----------------------+-------+-----------------------------------------------------------------------+ 782 783.. _table_qos_11: 784 785.. table:: Subport/Pipe Traffic Class Upper Limit Enforcement Operations 786 787 +---+--------------------------+----------------------------------------------------------------------------+ 788 | # | Traffic Class Operation | Description | 789 | | | | 790 +===+==========================+============================================================================+ 791 | 1 | Initialization | tc_credits = tc_credits_per_period; | 792 | | | | 793 | | | tc_time = tc_period; | 794 | | | | 795 +---+--------------------------+----------------------------------------------------------------------------+ 796 | 2 | Credit update | Update operations: | 797 | | | | 798 | | | if (time >= tc_time) { | 799 | | | | 800 | | | tc_credits = tc_credits_per_period; | 801 | | | | 802 | | | tc_time = time + tc_period; | 803 | | | | 804 | | | } | 805 | | | | 806 +---+--------------------------+----------------------------------------------------------------------------+ 807 | 3 | Credit consumption | As result of packet scheduling, the TC limit is decreased with the | 808 | | (on packet scheduling) | necessary number of credits. The packet can only be sent if enough credits | 809 | | | are currently available in the TC limit to send the full packet | 810 | | | (packet bytes and framing overhead for the packet). | 811 | | | | 812 | | | Scheduling operations: | 813 | | | | 814 | | | pkt_credits = pk_len + frame_overhead; | 815 | | | | 816 | | | if (tc_credits >= pkt_credits) {tc_credits -= pkt_credits;} | 817 | | | | 818 +---+--------------------------+----------------------------------------------------------------------------+ 819 820Weighted Round Robin (WRR) 821"""""""""""""""""""""""""" 822 823The evolution of the WRR design solution for the lowest priority traffic class (best effort TC) from simple to complex is shown in :numref:`table_qos_12`. 824 825.. _table_qos_12: 826 827.. table:: Weighted Round Robin (WRR) 828 829 +---+------------+-----------------+-------------+----------------------------------------------------------+ 830 | # | All Queues | Equal Weights | All Packets | Strategy | 831 | | Active? | for All Queues? | Equal? | | 832 +===+============+=================+=============+==========================================================+ 833 | 1 | Yes | Yes | Yes | **Byte level round robin** | 834 | | | | | | 835 | | | | | *Next queue* queue #i, i = *(i + 1) % n* | 836 | | | | | | 837 +---+------------+-----------------+-------------+----------------------------------------------------------+ 838 | 2 | Yes | Yes | No | **Packet level round robin** | 839 | | | | | | 840 | | | | | Consuming one byte from queue #i requires consuming | 841 | | | | | exactly one token for queue #i. | 842 | | | | | | 843 | | | | | T(i) = Accumulated number of tokens previously consumed | 844 | | | | | from queue #i. Every time a packet is consumed from | 845 | | | | | queue #i, T(i) is updated as: T(i) += *pkt_len*. | 846 | | | | | | 847 | | | | | *Next queue* : queue with the smallest T. | 848 | | | | | | 849 | | | | | | 850 +---+------------+-----------------+-------------+----------------------------------------------------------+ 851 | 3 | Yes | No | No | **Packet level weighted round robin** | 852 | | | | | | 853 | | | | | This case can be reduced to the previous case by | 854 | | | | | introducing a cost per byte that is different for each | 855 | | | | | queue. Queues with lower weights have a higher cost per | 856 | | | | | byte. This way, it is still meaningful to compare the | 857 | | | | | consumption amongst different queues in order to select | 858 | | | | | the next queue. | 859 | | | | | | 860 | | | | | w(i) = Weight of queue #i | 861 | | | | | | 862 | | | | | t(i) = Tokens per byte for queue #i, defined as the | 863 | | | | | inverse weight of queue #i. | 864 | | | | | For example, if w[0..3] = [1:2:4:8], | 865 | | | | | then t[0..3] = [8:4:2:1]; if w[0..3] = [1:4:15:20], | 866 | | | | | then t[0..3] = [60:15:4:3]. | 867 | | | | | Consuming one byte from queue #i requires consuming t(i) | 868 | | | | | tokens for queue #i. | 869 | | | | | | 870 | | | | | T(i) = Accumulated number of tokens previously consumed | 871 | | | | | from queue #i. Every time a packet is consumed from | 872 | | | | | queue #i, T(i) is updated as: *T(i) += pkt_len * t(i)*. | 873 | | | | | *Next queue* : queue with the smallest T. | 874 | | | | | | 875 +---+------------+-----------------+-------------+----------------------------------------------------------+ 876 | 4 | No | No | No | **Packet level weighted round robin with variable queue | 877 | | | | | status** | 878 | | | | | | 879 | | | | | Reduce this case to the previous case by setting the | 880 | | | | | consumption of inactive queues to a high number, so that | 881 | | | | | the inactive queues will never be selected by the | 882 | | | | | smallest T logic. | 883 | | | | | | 884 | | | | | To prevent T from overflowing as result of successive | 885 | | | | | accumulations, T(i) is truncated after each packet | 886 | | | | | consumption for all queues. | 887 | | | | | For example, T[0..3] = [1000, 1100, 1200, 1300] | 888 | | | | | is truncated to T[0..3] = [0, 100, 200, 300] | 889 | | | | | by subtracting the min T from T(i), i = 0..n. | 890 | | | | | | 891 | | | | | This requires having at least one active queue in the | 892 | | | | | set of input queues, which is guaranteed by the dequeue | 893 | | | | | state machine never selecting an inactive traffic class. | 894 | | | | | | 895 | | | | | *mask(i) = Saturation mask for queue #i, defined as:* | 896 | | | | | | 897 | | | | | mask(i) = (queue #i is active)? 0 : 0xFFFFFFFF; | 898 | | | | | | 899 | | | | | w(i) = Weight of queue #i | 900 | | | | | | 901 | | | | | t(i) = Tokens per byte for queue #i, defined as the | 902 | | | | | inverse weight of queue #i. | 903 | | | | | | 904 | | | | | T(i) = Accumulated numbers of tokens previously consumed | 905 | | | | | from queue #i. | 906 | | | | | | 907 | | | | | *Next queue* : queue with smallest T. | 908 | | | | | | 909 | | | | | Before packet consumption from queue #i: | 910 | | | | | | 911 | | | | | *T(i) |= mask(i)* | 912 | | | | | | 913 | | | | | After packet consumption from queue #i: | 914 | | | | | | 915 | | | | | T(j) -= T(i), j != i | 916 | | | | | | 917 | | | | | T(i) = pkt_len * t(i) | 918 | | | | | | 919 | | | | | Note: T(j) uses the T(i) value before T(i) is updated. | 920 | | | | | | 921 +---+------------+-----------------+-------------+----------------------------------------------------------+ 922 923Subport Traffic Class Oversubscription 924"""""""""""""""""""""""""""""""""""""" 925 926Problem Statement 927''''''''''''''''' 928 929Oversubscription for subport traffic class X is a configuration-time event that occurs when 930more bandwidth is allocated for traffic class X at the level of subport member pipes than 931allocated for the same traffic class at the parent subport level. 932 933The existence of the oversubscription for a specific subport and 934traffic class is solely the result of pipe and 935subport-level configuration as opposed to being created due 936to dynamic evolution of the traffic load at run-time (as congestion is). 937 938When the overall demand for traffic class X for the current subport is low, 939the existence of the oversubscription condition does not represent a problem, 940as demand for traffic class X is completely satisfied for all member pipes. 941However, this can no longer be achieved when the aggregated demand for traffic class X 942for all subport member pipes exceeds the limit configured at the subport level. 943 944Solution Space 945'''''''''''''' 946 947summarizes some of the possible approaches for handling this problem, 948with the third approach selected for implementation. 949 950.. _table_qos_13: 951 952.. table:: Subport Traffic Class Oversubscription 953 954 +-----+---------------------------+-------------------------------------------------------------------------+ 955 | No. | Approach | Description | 956 | | | | 957 +=====+===========================+=========================================================================+ 958 | 1 | Don't care | First come, first served. | 959 | | | | 960 | | | This approach is not fair amongst subport member pipes, as pipes that | 961 | | | are served first will use up as much bandwidth for TC X as they need, | 962 | | | while pipes that are served later will receive poor service due to | 963 | | | bandwidth for TC X at the subport level being scarce. | 964 | | | | 965 +-----+---------------------------+-------------------------------------------------------------------------+ 966 | 2 | Scale down all pipes | All pipes within the subport have their bandwidth limit for TC X scaled | 967 | | | down by the same factor. | 968 | | | | 969 | | | This approach is not fair among subport member pipes, as the low end | 970 | | | pipes (that is, pipes configured with low bandwidth) can potentially | 971 | | | experience severe service degradation that might render their service | 972 | | | unusable (if available bandwidth for these pipes drops below the | 973 | | | minimum requirements for a workable service), while the service | 974 | | | degradation for high end pipes might not be noticeable at all. | 975 | | | | 976 +-----+---------------------------+-------------------------------------------------------------------------+ 977 | 3 | Cap the high demand pipes | Each subport member pipe receives an equal share of the bandwidth | 978 | | | available at run-time for TC X at the subport level. Any bandwidth left | 979 | | | unused by the low-demand pipes is redistributed in equal portions to | 980 | | | the high-demand pipes. This way, the high-demand pipes are truncated | 981 | | | while the low-demand pipes are not impacted. | 982 | | | | 983 +-----+---------------------------+-------------------------------------------------------------------------+ 984 985Typically, the subport TC oversubscription feature is enabled only for the lowest priority traffic class, 986which is typically used for best effort traffic, 987with the management plane preventing this condition from occurring for the other (higher priority) traffic classes. 988 989To ease implementation, it is also assumed that the upper limit for subport best effort TC is set to 100% of the subport rate, 990and that the upper limit for pipe best effort TC is set to 100% of pipe rate for all subport member pipes. 991 992Implementation Overview 993''''''''''''''''''''''' 994 995The algorithm computes a watermark, which is periodically updated based on the current demand experienced by the subport member pipes, 996whose purpose is to limit the amount of traffic that each pipe is allowed to send for best effort TC. 997The watermark is computed at the subport level at the beginning of each traffic class upper limit enforcement period and 998the same value is used by all the subport member pipes throughout the current enforcement period. 999illustrates how the watermark computed as subport level at the beginning of each period is propagated to all subport member pipes. 1000 1001At the beginning of the current enforcement period (which coincides with the end of the previous enforcement period), 1002the value of the watermark is adjusted based on the amount of bandwidth allocated to best effort TC at the beginning of the previous period that 1003was not left unused by the subport member pipes at the end of the previous period. 1004 1005If there was subport best effort TC bandwidth left unused, 1006the value of the watermark for the current period is increased to encourage the subport member pipes to consume more bandwidth. 1007Otherwise, the value of the watermark is decreased to enforce equality of bandwidth consumption among subport member pipes for best effort TC. 1008 1009The increase or decrease in the watermark value is done in small increments, 1010so several enforcement periods might be required to reach the equilibrium state. 1011This state can change at any moment due to variations in the demand experienced by the subport member pipes for best effort TC, for example, 1012as a result of demand increase (when the watermark needs to be lowered) or demand decrease (when the watermark needs to be increased). 1013 1014When demand is low, the watermark is set high to prevent it from impeding the subport member pipes from consuming more bandwidth. 1015The highest value for the watermark is picked as the highest rate configured for a subport member pipe. 1016:numref:`table_qos_14` and :numref:`table_qos_15` illustrates the watermark operation. 1017 1018.. _table_qos_14: 1019 1020.. table:: Watermark Propagation from Subport Level to Member Pipes at the Beginning of Each Traffic Class Upper Limit Enforcement Period 1021 1022 +-----+---------------------------------+----------------------------------------------------+ 1023 | No. | Subport Traffic Class Operation | Description | 1024 | | | | 1025 +=====+=================================+====================================================+ 1026 | 1 | Initialization | **Subport level**: subport_period_id= 0 | 1027 | | | | 1028 | | | **Pipe level**: pipe_period_id = 0 | 1029 | | | | 1030 +-----+---------------------------------+----------------------------------------------------+ 1031 | 2 | Credit update | **Subport Level**: | 1032 | | | | 1033 | | | if (time>=subport_tc_time) | 1034 | | | | 1035 | | | { | 1036 | | | subport_wm = water_mark_update(); | 1037 | | | | 1038 | | | subport_tc_time = time + subport_tc_period; | 1039 | | | | 1040 | | | subport_period_id++; | 1041 | | | | 1042 | | | } | 1043 | | | | 1044 | | | **Pipelevel:** | 1045 | | | | 1046 | | | if(pipe_period_id != subport_period_id) | 1047 | | | | 1048 | | | { | 1049 | | | | 1050 | | | pipe_ov_credits = subport_wm \* pipe_weight; | 1051 | | | | 1052 | | | pipe_period_id = subport_period_id; | 1053 | | | | 1054 | | | } | 1055 | | | | 1056 +-----+---------------------------------+----------------------------------------------------+ 1057 | 3 | Credit consumption | **Pipe level:** | 1058 | | (on packet scheduling) | | 1059 | | | pkt_credits = pk_len + frame_overhead; | 1060 | | | | 1061 | | | if(pipe_ov_credits >= pkt_credits{ | 1062 | | | | 1063 | | | pipe_ov_credits -= pkt_credits; | 1064 | | | | 1065 | | | } | 1066 | | | | 1067 +-----+---------------------------------+----------------------------------------------------+ 1068 1069.. _table_qos_15: 1070 1071.. table:: Watermark Calculation 1072 1073 +-----+------------------+----------------------------------------------------------------------------------+ 1074 | No. | Subport Traffic | Description | 1075 | | Class Operation | | 1076 +=====+==================+==================================================================================+ 1077 | 1 | Initialization | **Subport level:** | 1078 | | | | 1079 | | | wm = WM_MAX | 1080 | | | | 1081 +-----+------------------+----------------------------------------------------------------------------------+ 1082 | 2 | Credit update | **Subport level (water_mark_update):** | 1083 | | | | 1084 | | | tc0_cons = subport_tc0_credits_per_period - subport_tc0_credits; | 1085 | | | | 1086 | | | tc1_cons = subport_tc1_credits_per_period - subport_tc1_credits; | 1087 | | | | 1088 | | | tc2_cons = subport_tc2_credits_per_period - subport_tc2_credits; | 1089 | | | | 1090 | | | tc3_cons = subport_tc3_credits_per_period - subport_tc3_credits; | 1091 | | | | 1092 | | | tc4_cons = subport_tc4_credits_per_period - subport_tc4_credits; | 1093 | | | | 1094 | | | tc5_cons = subport_tc5_credits_per_period - subport_tc5_credits; | 1095 | | | | 1096 | | | tc6_cons = subport_tc6_credits_per_period - subport_tc6_credits; | 1097 | | | | 1098 | | | tc7_cons = subport_tc7_credits_per_period - subport_tc7_credits; | 1099 | | | | 1100 | | | tc8_cons = subport_tc8_credits_per_period - subport_tc8_credits; | 1101 | | | | 1102 | | | tc9_cons = subport_tc9_credits_per_period - subport_tc9_credits; | 1103 | | | | 1104 | | | tc10_cons = subport_tc10_credits_per_period - subport_tc10_credits; | 1105 | | | | 1106 | | | tc11_cons = subport_tc11_credits_per_period - subport_tc11_credits; | 1107 | | | | 1108 | | | tc_be_cons_max = subport_tc_be_credits_per_period - (tc0_cons + tc1_cons + | 1109 | | | tc2_cons + tc3_cons + tc4_cons + tc5_cons + tc6_cons + tc7_cons + tc8_cons + | 1110 | | | tc9_cons + tc10_cons + tc11_cons); | 1111 | | | | 1112 | | | if(tc_be_consumption > (tc_be_consumption_max - MTU)){ | 1113 | | | | 1114 | | | wm -= wm >> 7; | 1115 | | | | 1116 | | | if(wm < WM_MIN) wm = WM_MIN; | 1117 | | | | 1118 | | | } else { | 1119 | | | | 1120 | | | wm += (wm >> 7) + 1; | 1121 | | | | 1122 | | | if(wm > WM_MAX) wm = WM_MAX; | 1123 | | | | 1124 | | | } | 1125 | | | | 1126 +-----+------------------+----------------------------------------------------------------------------------+ 1127 1128Worst Case Scenarios for Performance 1129~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1130 1131Lots of Active Queues with Not Enough Credits 1132^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1133 1134The more queues the scheduler has to examine for packets and credits in order to select one packet, 1135the lower the performance of the scheduler is. 1136 1137The scheduler maintains the bitmap of active queues, which skips the non-active queues, 1138but in order to detect whether a specific pipe has enough credits, 1139the pipe has to be drilled down using the pipe dequeue state machine, 1140which consumes cycles regardless of the scheduling result 1141(no packets are produced or at least one packet is produced). 1142 1143This scenario stresses the importance of the policer for the scheduler performance: 1144if the pipe does not have enough credits, 1145its packets should be dropped as soon as possible (before they reach the hierarchical scheduler), 1146thus rendering the pipe queues as not active, 1147which allows the dequeue side to skip that pipe with no cycles being spent on investigating the pipe credits 1148that would result in a "not enough credits" status. 1149 1150Single Queue with 100% Line Rate 1151^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1152 1153The port scheduler performance is optimized for a large number of queues. 1154If the number of queues is small, 1155then the performance of the port scheduler for the same level of active traffic is expected to be worse than 1156the performance of a small set of message passing queues. 1157 1158.. _Dropper: 1159 1160Dropper 1161------- 1162 1163The purpose of the DPDK dropper is to drop packets arriving at a packet scheduler to avoid congestion. 1164The dropper supports the Random Early Detection (RED), 1165Weighted Random Early Detection (WRED) and tail drop algorithms. 1166:numref:`figure_blk_diag_dropper` illustrates how the dropper integrates with the scheduler. 1167The DPDK currently does not support congestion management 1168so the dropper provides the only method for congestion avoidance. 1169 1170.. _figure_blk_diag_dropper: 1171 1172.. figure:: img/blk_diag_dropper.* 1173 1174 High-level Block Diagram of the DPDK Dropper 1175 1176 1177The dropper uses the Random Early Detection (RED) congestion avoidance algorithm as documented in the reference publication. 1178The purpose of the RED algorithm is to monitor a packet queue, 1179determine the current congestion level in the queue and decide whether an arriving packet should be enqueued or dropped. 1180The RED algorithm uses an Exponential Weighted Moving Average (EWMA) filter to compute average queue size which 1181gives an indication of the current congestion level in the queue. 1182 1183For each enqueue operation, the RED algorithm compares the average queue size to minimum and maximum thresholds. 1184Depending on whether the average queue size is below, above or in between these thresholds, 1185the RED algorithm calculates the probability that an arriving packet should be dropped and 1186makes a random decision based on this probability. 1187 1188The dropper also supports Weighted Random Early Detection (WRED) by allowing the scheduler to select 1189different RED configurations for the same packet queue at run-time. 1190In the case of severe congestion, the dropper resorts to tail drop. 1191This occurs when a packet queue has reached maximum capacity and cannot store any more packets. 1192In this situation, all arriving packets are dropped. 1193 1194The flow through the dropper is illustrated in :numref:`figure_flow_tru_droppper`. 1195The RED/WRED algorithm is exercised first and tail drop second. 1196 1197.. _figure_flow_tru_droppper: 1198 1199.. figure:: img/flow_tru_droppper.* 1200 1201 Flow Through the Dropper 1202 1203 1204The use cases supported by the dropper are: 1205 1206* * Initialize configuration data 1207 1208* * Initialize run-time data 1209 1210* * Enqueue (make a decision to enqueue or drop an arriving packet) 1211 1212* * Mark empty (record the time at which a packet queue becomes empty) 1213 1214The configuration use case is explained in :ref:`Section2.23.3.1 <Configuration>`, 1215the enqueue operation is explained in :ref:`Section 2.23.3.2 <Enqueue_Operation>` 1216and the mark empty operation is explained in :ref:`Section 2.23.3.3 <Queue_Empty_Operation>`. 1217 1218.. _Configuration: 1219 1220Configuration 1221~~~~~~~~~~~~~ 1222 1223A RED configuration contains the parameters given in :numref:`table_qos_16`. 1224 1225.. _table_qos_16: 1226 1227.. table:: RED Configuration Parameters 1228 1229 +--------------------------+---------+---------+------------------+ 1230 | Parameter | Minimum | Maximum | Typical | 1231 | | | | | 1232 +==========================+=========+=========+==================+ 1233 | Minimum Threshold | 0 | 1022 | 1/4 x queue size | 1234 | | | | | 1235 +--------------------------+---------+---------+------------------+ 1236 | Maximum Threshold | 1 | 1023 | 1/2 x queue size | 1237 | | | | | 1238 +--------------------------+---------+---------+------------------+ 1239 | Inverse Mark Probability | 1 | 255 | 10 | 1240 | | | | | 1241 +--------------------------+---------+---------+------------------+ 1242 | EWMA Filter Weight | 1 | 12 | 9 | 1243 | | | | | 1244 +--------------------------+---------+---------+------------------+ 1245 1246The meaning of these parameters is explained in more detail in the following sections. 1247The format of these parameters as specified to the dropper module API 1248corresponds to the format used by Cisco* in their RED implementation. 1249The minimum and maximum threshold parameters are specified to the dropper module in terms of number of packets. 1250The mark probability parameter is specified as an inverse value, for example, 1251an inverse mark probability parameter value of 10 corresponds 1252to a mark probability of 1/10 (that is, 1 in 10 packets will be dropped). 1253The EWMA filter weight parameter is specified as an inverse log value, 1254for example, a filter weight parameter value of 9 corresponds to a filter weight of 1/29. 1255 1256.. _Enqueue_Operation: 1257 1258Enqueue Operation 1259~~~~~~~~~~~~~~~~~ 1260 1261In the example shown in :numref:`figure_ex_data_flow_tru_dropper`, q (actual queue size) is the input value, 1262avg (average queue size) and count (number of packets since the last drop) are run-time values, 1263decision is the output value and the remaining values are configuration parameters. 1264 1265.. _figure_ex_data_flow_tru_dropper: 1266 1267.. figure:: img/ex_data_flow_tru_dropper.* 1268 1269 Example Data Flow Through Dropper 1270 1271 1272EWMA Filter Microblock 1273^^^^^^^^^^^^^^^^^^^^^^ 1274 1275The purpose of the EWMA Filter microblock is to filter queue size values to smooth out transient changes 1276that result from "bursty" traffic. 1277The output value is the average queue size which gives a more stable view of the current congestion level in the queue. 1278 1279The EWMA filter has one configuration parameter, filter weight, which determines how quickly 1280or slowly the average queue size output responds to changes in the actual queue size input. 1281Higher values of filter weight mean that the average queue size responds more quickly to changes in actual queue size. 1282 1283Average Queue Size Calculation when the Queue is not Empty 1284"""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 1285 1286The definition of the EWMA filter is given in the following equation. 1287 1288.. image:: img/ewma_filter_eq_1.* 1289 1290Where: 1291 1292* *avg* = average queue size 1293 1294* *wq* = filter weight 1295 1296* *q* = actual queue size 1297 1298.. note:: 1299 1300 The filter weight, wq = 1/2^n, where n is the filter weight parameter value passed to the dropper module 1301 on configuration (see :ref:`Section2.23.3.1 <Configuration>` ). 1302 1303Average Queue Size Calculation when the Queue is Empty 1304^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1305 1306The EWMA filter does not read time stamps and instead assumes that enqueue operations will happen quite regularly. 1307Special handling is required when the queue becomes empty as the queue could be empty for a short time or a long time. 1308When the queue becomes empty, average queue size should decay gradually to zero instead of dropping suddenly to zero 1309or remaining stagnant at the last computed value. 1310When a packet is enqueued on an empty queue, the average queue size is computed using the following formula: 1311 1312.. image:: img/ewma_filter_eq_2.* 1313 1314Where: 1315 1316* *m* = the number of enqueue operations that could have occurred on this queue while the queue was empty 1317 1318In the dropper module, *m* is defined as: 1319 1320.. image:: img/m_definition.* 1321 1322Where: 1323 1324* *time* = current time 1325 1326* *qtime* = time the queue became empty 1327 1328* *s* = typical time between successive enqueue operations on this queue 1329 1330The time reference is in units of bytes, 1331where a byte signifies the time duration required by the physical interface to send out a byte on the transmission medium 1332(see Section `Internal Time Reference`_). 1333The parameter s is defined in the dropper module as a constant with the value: s=2^22. 1334This corresponds to the time required by every leaf node in a hierarchy with 64K leaf nodes 1335to transmit one 64-byte packet onto the wire and represents the worst case scenario. 1336For much smaller scheduler hierarchies, 1337it may be necessary to reduce the parameter s, which is defined in the red header source file (rte_red.h) as: 1338 1339.. code-block:: c 1340 1341 #define RTE_RED_S 1342 1343Since the time reference is in bytes, the port speed is implied in the expression: *time-qtime*. 1344The dropper does not have to be configured with the actual port speed. 1345It adjusts automatically to low speed and high speed links. 1346 1347Implementation 1348"""""""""""""" 1349 1350A numerical method is used to compute the factor (1-wq)^m that appears in Equation 2. 1351 1352This method is based on the following identity: 1353 1354.. image:: img/eq2_factor.* 1355 1356 1357This allows us to express the following: 1358 1359.. image:: img/eq2_expression.* 1360 1361 1362In the dropper module, a look-up table is used to compute log2(1-wq) for each value of wq supported by the dropper module. 1363The factor (1-wq)^m can then be obtained by multiplying the table value by *m* and applying shift operations. 1364To avoid overflow in the multiplication, the value, *m*, and the look-up table values are limited to 16 bits. 1365The total size of the look-up table is 56 bytes. 1366Once the factor (1-wq)^m is obtained using this method, the average queue size can be calculated from Equation 2. 1367 1368Alternative Approaches 1369"""""""""""""""""""""" 1370 1371Other methods for calculating the factor (1-wq)^m in the expression for computing average queue size 1372when the queue is empty (Equation 2) were considered. 1373These approaches include: 1374 1375* Floating-point evaluation 1376 1377* Fixed-point evaluation using a small look-up table (512B) and up to 16 multiplications 1378 (this is the approach used in the FreeBSD* ALTQ RED implementation) 1379 1380* Fixed-point evaluation using a small look-up table (512B) and 16 SSE multiplications 1381 (SSE optimized version of the approach used in the FreeBSD* ALTQ RED implementation) 1382 1383* Large look-up table (76 KB) 1384 1385The method that was finally selected (described above in Section 26.3.2.2.1) out performs all of these approaches 1386in terms of run-time performance and memory requirements and 1387also achieves accuracy comparable to floating-point evaluation. 1388:numref:`table_qos_17` lists the performance of each of these alternative approaches relative to the method that is used in the dropper. 1389As can be seen, the floating-point implementation achieved the worst performance. 1390 1391.. _table_qos_17: 1392 1393.. table:: Relative Performance of Alternative Approaches 1394 1395 +------------------------------------------------------------------------------------+----------------------+ 1396 | Method | Relative Performance | 1397 | | | 1398 +====================================================================================+======================+ 1399 | Current dropper method (see :ref:`Section 23.3.2.1.3 <Dropper>`) | 100% | 1400 | | | 1401 +------------------------------------------------------------------------------------+----------------------+ 1402 | Fixed-point method with small (512B) look-up table | 148% | 1403 | | | 1404 +------------------------------------------------------------------------------------+----------------------+ 1405 | SSE method with small (512B) look-up table | 114% | 1406 | | | 1407 +------------------------------------------------------------------------------------+----------------------+ 1408 | Large (76KB) look-up table | 118% | 1409 | | | 1410 +------------------------------------------------------------------------------------+----------------------+ 1411 | Floating-point | 595% | 1412 | | | 1413 +------------------------------------------------------------------------------------+----------------------+ 1414 | **Note**: In this case, since performance is expressed as time spent executing the operation in a | 1415 | specific condition, any relative performance value above 100% runs slower than the reference method. | 1416 | | 1417 +-----------------------------------------------------------------------------------------------------------+ 1418 1419Drop Decision Block 1420^^^^^^^^^^^^^^^^^^^ 1421 1422The Drop Decision block: 1423 1424* Compares the average queue size with the minimum and maximum thresholds 1425 1426* Calculates a packet drop probability 1427 1428* Makes a random decision to enqueue or drop an arriving packet 1429 1430The calculation of the drop probability occurs in two stages. 1431An initial drop probability is calculated based on the average queue size, 1432the minimum and maximum thresholds and the mark probability. 1433An actual drop probability is then computed from the initial drop probability. 1434The actual drop probability takes the count run-time value into consideration 1435so that the actual drop probability increases as more packets arrive to the packet queue 1436since the last packet was dropped. 1437 1438Initial Packet Drop Probability 1439""""""""""""""""""""""""""""""" 1440 1441The initial drop probability is calculated using the following equation. 1442 1443.. image:: img/drop_probability_eq3.* 1444 1445Where: 1446 1447* *maxp* = mark probability 1448 1449* *avg* = average queue size 1450 1451* *minth* = minimum threshold 1452 1453* *maxth* = maximum threshold 1454 1455The calculation of the packet drop probability using Equation 3 is illustrated in :numref:`figure_pkt_drop_probability`. 1456If the average queue size is below the minimum threshold, an arriving packet is enqueued. 1457If the average queue size is at or above the maximum threshold, an arriving packet is dropped. 1458If the average queue size is between the minimum and maximum thresholds, 1459a drop probability is calculated to determine if the packet should be enqueued or dropped. 1460 1461.. _figure_pkt_drop_probability: 1462 1463.. figure:: img/pkt_drop_probability.* 1464 1465 Packet Drop Probability for a Given RED Configuration 1466 1467 1468Actual Drop Probability 1469""""""""""""""""""""""" 1470 1471If the average queue size is between the minimum and maximum thresholds, 1472then the actual drop probability is calculated from the following equation. 1473 1474.. image:: img/drop_probability_eq4.* 1475 1476Where: 1477 1478* *Pb* = initial drop probability (from Equation 3) 1479 1480* *count* = number of packets that have arrived since the last drop 1481 1482The constant 2, in Equation 4 is the only deviation from the drop probability formulae 1483given in the reference document where a value of 1 is used instead. 1484It should be noted that the value pa computed from can be negative or greater than 1. 1485If this is the case, then a value of 1 should be used instead. 1486 1487The initial and actual drop probabilities are shown in :numref:`figure_drop_probability_graph`. 1488The actual drop probability is shown for the case where 1489the formula given in the reference document1 is used (blue curve) 1490and also for the case where the formula implemented in the dropper module, 1491is used (red curve). 1492The formula in the reference document results in a significantly higher drop rate 1493compared to the mark probability configuration parameter specified by the user. 1494The choice to deviate from the reference document is simply a design decision and 1495one that has been taken by other RED implementations, for example, FreeBSD* ALTQ RED. 1496 1497.. _figure_drop_probability_graph: 1498 1499.. figure:: img/drop_probability_graph.* 1500 1501 Initial Drop Probability (pb), Actual Drop probability (pa) Computed Using 1502 a Factor 1 (Blue Curve) and a Factor 2 (Red Curve) 1503 1504 1505.. _Queue_Empty_Operation: 1506 1507Queue Empty Operation 1508~~~~~~~~~~~~~~~~~~~~~ 1509 1510The time at which a packet queue becomes empty must be recorded and saved with the RED run-time data 1511so that the EWMA filter block can calculate the average queue size on the next enqueue operation. 1512It is the responsibility of the calling application to inform the dropper module 1513through the API that a queue has become empty. 1514 1515Source Files Location 1516~~~~~~~~~~~~~~~~~~~~~ 1517 1518The source files for the DPDK dropper are located at: 1519 1520* DPDK/lib/librte_sched/rte_red.h 1521 1522* DPDK/lib/librte_sched/rte_red.c 1523 1524Integration with the DPDK QoS Scheduler 1525~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1526 1527RED functionality in the DPDK QoS scheduler is disabled by default. 1528The parameter is found in the build configuration files in the DPDK/config directory. 1529RED configuration parameters are specified in the rte_red_params structure within the rte_sched_port_params structure 1530that is passed to the scheduler on initialization. 1531RED parameters are specified separately for four traffic classes and three packet colors (green, yellow and red) 1532allowing the scheduler to implement Weighted Random Early Detection (WRED). 1533 1534Integration with the DPDK QoS Scheduler Sample Application 1535~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1536 1537The DPDK QoS Scheduler Application reads a configuration file on start-up. 1538The configuration file includes a section containing RED parameters. 1539The format of these parameters is described in :ref:`Section2.23.3.1 <Configuration>`. 1540A sample RED configuration is shown below. In this example, the queue size is 64 packets. 1541 1542.. note:: 1543 1544 For correct operation, the same EWMA filter weight parameter (wred weight) should be used 1545 for each packet color (green, yellow, red) in the same traffic class (tc). 1546 1547:: 1548 1549 ; RED params per traffic class and color (Green / Yellow / Red) 1550 1551 [red] 1552 tc 0 wred min = 28 22 16 1553 tc 0 wred max = 32 32 32 1554 tc 0 wred inv prob = 10 10 10 1555 tc 0 wred weight = 9 9 9 1556 1557 tc 1 wred min = 28 22 16 1558 tc 1 wred max = 32 32 32 1559 tc 1 wred inv prob = 10 10 10 1560 tc 1 wred weight = 9 9 9 1561 1562 tc 2 wred min = 28 22 16 1563 tc 2 wred max = 32 32 32 1564 tc 2 wred inv prob = 10 10 10 1565 tc 2 wred weight = 9 9 9 1566 1567 tc 3 wred min = 28 22 16 1568 tc 3 wred max = 32 32 32 1569 tc 3 wred inv prob = 10 10 10 1570 tc 3 wred weight = 9 9 9 1571 1572 tc 4 wred min = 28 22 16 1573 tc 4 wred max = 32 32 32 1574 tc 4 wred inv prob = 10 10 10 1575 tc 4 wred weight = 9 9 9 1576 1577 tc 5 wred min = 28 22 16 1578 tc 5 wred max = 32 32 32 1579 tc 5 wred inv prob = 10 10 10 1580 tc 5 wred weight = 9 9 9 1581 1582 tc 6 wred min = 28 22 16 1583 tc 6 wred max = 32 32 32 1584 tc 6 wred inv prob = 10 10 10 1585 tc 6 wred weight = 9 9 9 1586 1587 tc 7 wred min = 28 22 16 1588 tc 7 wred max = 32 32 32 1589 tc 7 wred inv prob = 10 10 10 1590 tc 7 wred weight = 9 9 9 1591 1592 tc 8 wred min = 28 22 16 1593 tc 8 wred max = 32 32 32 1594 tc 8 wred inv prob = 10 10 10 1595 tc 8 wred weight = 9 9 9 1596 1597 tc 9 wred min = 28 22 16 1598 tc 9 wred max = 32 32 32 1599 tc 9 wred inv prob = 10 10 10 1600 tc 9 wred weight = 9 9 9 1601 1602 1603 tc 10 wred min = 28 22 16 1604 tc 10 wred max = 32 32 32 1605 tc 10 wred inv prob = 10 10 10 1606 tc 10 wred weight = 9 9 9 1607 1608 tc 11 wred min = 28 22 16 1609 tc 11 wred max = 32 32 32 1610 tc 11 wred inv prob = 10 10 10 1611 tc 11 wred weight = 9 9 9 1612 1613 tc 12 wred min = 28 22 16 1614 tc 12 wred max = 32 32 32 1615 tc 12 wred inv prob = 10 10 10 1616 tc 12 wred weight = 9 9 9 1617 1618With this configuration file, the RED configuration that applies to green, 1619yellow and red packets in traffic class 0 is shown in :numref:`table_qos_18`. 1620 1621.. _table_qos_18: 1622 1623.. table:: RED Configuration Corresponding to RED Configuration File 1624 1625 +--------------------+--------------------+-------+--------+-----+ 1626 | RED Parameter | Configuration Name | Green | Yellow | Red | 1627 | | | | | | 1628 +====================+====================+=======+========+=====+ 1629 | Minimum Threshold | tc 0 wred min | 28 | 22 | 16 | 1630 | | | | | | 1631 +--------------------+--------------------+-------+--------+-----+ 1632 | Maximum Threshold | tc 0 wred max | 32 | 32 | 32 | 1633 | | | | | | 1634 +--------------------+--------------------+-------+--------+-----+ 1635 | Mark Probability | tc 0 wred inv prob | 10 | 10 | 10 | 1636 | | | | | | 1637 +--------------------+--------------------+-------+--------+-----+ 1638 | EWMA Filter Weight | tc 0 wred weight | 9 | 9 | 9 | 1639 | | | | | | 1640 +--------------------+--------------------+-------+--------+-----+ 1641 1642Application Programming Interface (API) 1643~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1644 1645Enqueue API 1646^^^^^^^^^^^ 1647 1648The syntax of the enqueue API is as follows: 1649 1650.. code-block:: c 1651 1652 int rte_red_enqueue(const struct rte_red_config *red_cfg, struct rte_red *red, const unsigned q, const uint64_t time) 1653 1654 1655The arguments passed to the enqueue API are configuration data, run-time data, 1656the current size of the packet queue (in packets) and a value representing the current time. 1657The time reference is in units of bytes, 1658where a byte signifies the time duration required by the physical interface to send out a byte on the transmission medium 1659(see Section 26.2.4.5.1 "Internal Time Reference" ). 1660The dropper reuses the scheduler time stamps for performance reasons. 1661 1662Empty API 1663^^^^^^^^^ 1664 1665The syntax of the empty API is as follows: 1666 1667.. code-block:: c 1668 1669 void rte_red_mark_queue_empty(struct rte_red *red, const uint64_t time) 1670 1671The arguments passed to the empty API are run-time data and the current time in bytes. 1672 1673Traffic Metering 1674---------------- 1675 1676The traffic metering component implements the Single Rate Three Color Marker (srTCM) and 1677Two Rate Three Color Marker (trTCM) algorithms, as defined by IETF RFC 2697 and 2698 respectively. 1678These algorithms meter the stream of incoming packets based on the allowance defined in advance for each traffic flow. 1679As result, each incoming packet is tagged as green, 1680yellow or red based on the monitored consumption of the flow the packet belongs to. 1681 1682Functional Overview 1683~~~~~~~~~~~~~~~~~~~ 1684 1685The srTCM algorithm defines two token buckets for each traffic flow, 1686with the two buckets sharing the same token update rate: 1687 1688* Committed (C) bucket: fed with tokens at the rate defined by the Committed Information Rate (CIR) parameter 1689 (measured in IP packet bytes per second). 1690 The size of the C bucket is defined by the Committed Burst Size (CBS) parameter (measured in bytes); 1691 1692* Excess (E) bucket: fed with tokens at the same rate as the C bucket. 1693 The size of the E bucket is defined by the Excess Burst Size (EBS) parameter (measured in bytes). 1694 1695The trTCM algorithm defines two token buckets for each traffic flow, 1696with the two buckets being updated with tokens at independent rates: 1697 1698* Committed (C) bucket: fed with tokens at the rate defined by the Committed Information Rate (CIR) parameter 1699 (measured in bytes of IP packet per second). 1700 The size of the C bucket is defined by the Committed Burst Size (CBS) parameter (measured in bytes); 1701 1702* Peak (P) bucket: fed with tokens at the rate defined by the Peak Information Rate (PIR) parameter 1703 (measured in IP packet bytes per second). 1704 The size of the P bucket is defined by the Peak Burst Size (PBS) parameter (measured in bytes). 1705 1706Please refer to RFC 2697 (for srTCM) and RFC 2698 (for trTCM) for details on how tokens are consumed 1707from the buckets and how the packet color is determined. 1708 1709Color Blind and Color Aware Modes 1710^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1711 1712For both algorithms, the color blind mode is functionally equivalent to the color aware mode with input color set as green. 1713For color aware mode, a packet with red input color can only get the red output color, 1714while a packet with yellow input color can only get the yellow or red output colors. 1715 1716The reason why the color blind mode is still implemented distinctly than the color aware mode is 1717that color blind mode can be implemented with fewer operations than the color aware mode. 1718 1719Implementation Overview 1720~~~~~~~~~~~~~~~~~~~~~~~ 1721 1722For each input packet, the steps for the srTCM / trTCM algorithms are: 1723 1724* Update the C and E / P token buckets. This is done by reading the current time (from the CPU timestamp counter), 1725 identifying the amount of time since the last bucket update and computing the associated number of tokens 1726 (according to the pre-configured bucket rate). 1727 The number of tokens in the bucket is limited by the pre-configured bucket size; 1728 1729* Identify the output color for the current packet based on the size of the IP packet 1730 and the amount of tokens currently available in the C and E / P buckets; for color aware mode only, 1731 the input color of the packet is also considered. 1732 When the output color is not red, a number of tokens equal to the length of the IP packet are 1733 subtracted from the C or E /P or both buckets, depending on the algorithm and the output color of the packet. 1734