# An Adaptive Throughput-First Packet Scheduling Algorithm for DPDK-Based Packet Processing Systems
## 3 The Proposed Packet Scheduling Algorithm
When the load factor of the target core exceeds the pre-configured value, meaning that the core is likely to be overloaded, the proposed algorithm will change the scheduling decision at once; hence, packets in the Subflow will not be scheduled to the core. Using Subflow-based adjustment, we reduce the probability of packet loss, thus achieving higher throughput. The hash-based design is adopted in our proposed method with an adaptive Subflow-based adjustment. The hash algorithm we use is High Random Weight (HRW), first presented in [22], which is used to map a request to a specific server in the server cluster. The lower overhead and better load balancing make it a popular choice for packet scheduling [17; 22; 23]. In this paper, the definition of HRW function is as follows: Suppose \(\vartheta(p_{i},\text{C})\) is a pseudo-random weight function, where \(\vartheta:\text{P}\times\{1,2,\ldots,\text{bsz\_rd}\}\rightarrow[0,\text{n}]\). Here, C is the set of processing cores, written as \(\text{C}=(c_{1},c_{2},\ldots,c_{N})\), where N is the number of them. P is the set of packets fetched from NIC. \(\vartheta\) is assumed to generate a random value in \([0,\text{n}]\) with uniform distribution. For each packet \(p_{i}\) in the burst, the target core is calculated as below:  
\[LB_{HRW}(p_{i},\text{C})=c_{j}, \tag{1}\]  
where \(c_{j}=\underset{1\leq j\leq N}{\max}\vartheta\big{(}p_{i},\ c_{j}\big{)}\) and \(LB_{HRW}\) is the scheduling function used in this paper. The packets sharing the same 5-tuples should have the same weight, thus the same target core if no adjustment happens. As mentioned in [4], the pseudo-random weight function plays a vital role in the performance of the HRW algorithm; hence, we follow the one provided in [22]:  
\[\vartheta(p_{i},\text{C})=(A\cdot((A\cdot T+B)\oplus D(p_{i}))+B)mod2^{31}, \tag{2}\]  
where \(A=1103515245\) and \(B=12345\). \(D(p_{i})\) is a 31-bit digest of the packet identifier (ID), and the packet ID is generated based on 5-tuple of the packet. \(T\) is the ID of the processing core. For each packet in the burst, the \(LB_{HRW}\) will generate a target value to which the packet should be dispatched. When the target core is obtained, we check the number of packets waiting in its ring, written as \(n\_mbufs\). If \(n\_mbufs\) is larger than zero, i.e., there are some packets queued in the ring waiting to be sent to the target core, we just add the current packet to the ring to maintain the cache locality as much as possible. The adjustment will only be triggered when the following two conditions are both met: (1) \(n\_mbufs\) is zero; and (2) the utilization of the target core, named _load factor_ in this paper, exceeds the pre-configured threshold. Borrowed from the design of the hash function, we use _load factor_ to define the occupancy of the cores' queue as follows: \(\tau=\frac{Q_{used}}{Q_{total}}\), where \(Q_{total}\) is the total number of rings allocated to the core and \(Q_{used}\) is the number of rings occupied by the packets waiting to be processed. We discuss the selection of a suitable threshold in the Experimental Section 4.1. It is well known that the adjustment means another computing of the hash weight. At the same time, there is the case that the target core generated by the \(LB_{HRW}\) is still an overloading core. To avoid this issue, we introduce an adaptive hash function when the adjustment is needed. The final weight function \(\vartheta^{\prime}\) can be formulated as: \(\vartheta^{\prime}\big{(}p_{i},C_{N_{i}},\ \mu\big{)}=\mu\cdot\vartheta \big{(}p_{i},C_{N_{i}}\big{)}\), where \(C_{N_{i}}\) is a subset of C.  
The adjustment factor \(\mu\) is defined as \(\mu=1-\tau\), which shows the available position in each queue. The adaptive scheduling function \(LB_{AHRW}\) is depicted as:  
\[LB_{AHRW}\big{(}p_{i},C_{N_{i}},\mu\big{)}=c_{j}, \tag{3}\]where \(c_{j}=\max\limits_{1\leq j\leq N_{i}}\theta^{\prime}(p_{i},c_{j},\mu)\).