# An Adaptive Throughput-First Packet Scheduling Algorithm for DPDK-Based Packet Processing Systems
## 3 The Proposed Packet Scheduling Algorithm
As mentioned above, our method uses the Subflow as the scheduling unit and packets in the same Subflow have the same 5-tuple, thus producing the same processing core. In the case where the adjustment does not happen, we can store the decision for the Subflow to avoid computing the hash weight for each packet repeatedly. Meanwhile, when the adjustment is needed, we still can store the adjustment decision for the Subflow since the Subflow is also the adjustment unit, which means the adjustment for a Subflow happens only once in the current burst. Subsequent packets in the burst belonging to the Subflow follow the same decision. It is negligible that the memory overhead to store the decision since our packet scheduling algorithm is based on the Subflow. Besides, it also can be used repeatedly for different bursts. Finally, the whole algorithm is described in Algorithm 1. ```
1:target[bsz_rd] \(\leftarrow\) {\(-1\)}
2:for each packet in the burst fetched from the NIC3
3:\(\mathrm{index}\leftarrow\mathrm{P_{l}}^{\circ}\)\(\mathrm{obsz_{rd}}\)
4:\(\mathrm{c_{i}}\leftarrow\mathrm{target[index]}\)
5:if \(\mathrm{c_{i}}==-1\)
6:\(\mathrm{c_{i}}\leftarrow\mathrm{LB_{HRW}(p_{i},\mathrm{C})}\)
7:\(\mathrm{target[index]}\leftarrow\mathrm{c_{i}}\)
8:endif
9:\(\mathrm{n\_mbuf_{i}}\leftarrow\mathrm{Get\_pktnum(c_{i})}\)
10:if \(\mathrm{n\_mbuf_{i}}==0\)
11:load \(\mathrm{factor_{i}}>\mathrm{Threshold}\)
12:\(\mathrm{c_{i}}\leftarrow\mathrm{LB_{AHRW}(p_{i},\mathrm{C}_{N_{i}},\mu)}\)
14:\(\mathrm{target[index]}\leftarrow\mathrm{c_{i}}\)
15:endif
16:endif
17:endfor
```  
**Algorithm 1** Subflow-based packet scheduling  
For a burst of packets fetched from the NIC, Line 1 clears the target array to guarantee that the previous scheduling strategy is not active for the current burst. The initial value can be any value except the logical number of Worker cores. For simplicity, we set the initial values of the array to \(-1\), indicating that the scheduling decision is not done. For each packet in the burst, we use the packet ID to mod the size of the array to get the index of the value, thus getting the scheduling decision, as Line 3 shows. If the decision is not done for the packet, we use the load balancing algorithm to get the target processing core and record the decision in the array. Lines 5-8 show the procedure. When the processing core is obtained, we use the function provided by DPDK to get the number of packets waiting in the out queue, as Line 9 shows. If the number of packets is larger than zero, we apply the greed strategy and directly schedule the packet to the core; otherwise, the queue utilization of the target core is needed, as Line 11 shows. Line 12 shows that, if the load factor of the core is larger than a pre-configured value, the adjustment of the scheduling decision is needed. According to the proposed method in this paper, another processing core is chosen, and the decision is recorded in the array. Lines 12-15 show the procedure. When Line 12 is not satisfied, meaning the target core has enough capacity to handle these packets, we distribute the packet to it directly. One more thing that should be noted is that the adjustment will lead to packets belonging to the same flow being processed by different processing cores; thus, poor cache performance degrades the throughput of the system. Furthermore, packets may need to be reordered for some applications, but not for ours. In our packet processing system, the processing core is responsible for parsing the payload of the packets, and the information needed is sent to the Log module. The Log module is responsible for the integration of the flow information for users. Therefore, in our system, we pay no attention to the problem of packet out-of-order.