# NetAP: Adaptive Polling Technique for Network Packet Processing in Virtualized Environments
## 3 Design
### Adaptation Using Golden-Section Search
#### 3.4.1 Considerations for Alternative Algorithms  
We choose the golden-section search rather than other line search algorithms, such as the bisection, Newton's, Quasi-Newton's, and Nelder--Mead methods, because Golden-section searching is unconstrained and derivative-free [28]. First, we need an unconstrained method, because the target function to be searched is not specified. Because NetAP should supports various workloads with different characteristics, we cannot assume any constraints for the searching algorithm. We only assume that the target function is one-dimensional, so we avoid using complex multi-dimensional algorithms, such as the gradient, random search, and Nelder-Mead methods [29]. Second, we need a derivative-free method, because we do not know the complete function in the mathematical form. We only know few points that are collected from the execution results during the round. In addition, the derivative cannot be correctly calculated in the Linux kernel, because the floating point operations are not allowed in the kernel mode in order to maintain the user context in the floating point unit [30]. Thus, we avoid algorithms that are based on derivatives, such as the bisection search, [PERSON]'s method, and [PERSON]'s method [31]. ```
Data:
1 round indicates the number corresponding to the current round, \(round\_length\) is a predefined length of a round in seconds, \(next\_time\) indicates the next time for updating the interval, \(current\_time()\) returns a current wall-clock time, \(bytes\) is the sizes of processed packets in the current round, \(interval\) is a polling interval in the current round, \(MaxRound\) is the maximum number of rounds without changing the interval, \(MinChange\) is the minimum ratio of processed packet sizes between previous and current rounds, \(RX\_queue\), and \(TX\_queue\) are the queues for the packets received and packets to be transmitted. 1 Function\(the\_packet\_handler\_of\_a\_host\_system(void)\):
2 start: \(next\_time\gets current\_time()\);
3\(round\gets 0\);
4\(bytes\gets 0\);
5\(interval\gets 0\);
6 while\(true\)do
7 Disable interrupts for packet arrivals;
8 if\(current\_time()>=next\_time\)then
9\(interval\gets golden\_searching(round,bytes,interval)\);
10 if\(interval\) is not changed AND bytes is changed more than \(MinChange\)then
11 go to start;
12
13 end if
14\(next\_time\gets current\_time()+round\_length\);
15\(bytes\gets 0\);
16\(round\gets round+1\);
17 if\(round=MaxRound\)then
18 go to start;
19
20 end if
21
22 end if
23\(bytes\gets bytes+handle\_packets\_in\_the\_queue(RX\_queue)\);
24\(bytes\gets bytes+handle\_packets\_in\_the\_queue(TX\_queue)\);
25 Enable interrupts;
26 Sleep for interval;
27
28 end if
29
30 end if
31 Function\(handle\_packets\_in\_the\_queue(queue)\);
32\(processed\_bytes=0\);
33 whilequeue has a packetdo
34 Lock the queue;
35 Dequeue a packet;
36 Process the packet;
37\(processed\_bytes\) is increased by the size of the packet;
38 Unlock the queue;
39
40 end if
41 return\(processed\_bytes\)
42
43 end if
44 Function\(current\_time(void)\):
45 return Current wall-clock time;
46
47 end if
48

#### 3.4.2 Preliminary Examination for Golden-Section Search Algorithm

Before we apply the algorithm to solve our problem, there are two requirements to examine: the target function must be unimodal, and a near-optimal value must exist within a range of possible intervals to perform a search. Thus, we demonstrate in advance whether our problem can be solved by the golden-section search algorithm. We performed a preliminary examination to determine whether a golden-section search can find near-optimal polling intervals. As a result, we made two observations. First, the change in performance over various polling intervals appears as a unimodal function. Second, there is a range of periods that can be commonly applied to various workloads. The environment of the experiment is as follows: the host system is equipped with a CPU with six physical cores, 16 GB of memory, and a 10 GbE NIC.