# 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
Figure 2: Results of preliminary examination for four scenarios. Through the aforementioned process, we can quickly search for the interval between \(MinInterval\) and \(MaxInterval\) that maximizes the performance. ```
Data:\(interval_{low}\), \(interval_{high}\), \(perf_{low}\), \(perf_{high}\), \(temp\), distance, selected, \(R\), \(MinDistance\), \(MaxInterval\) and \(MinInterval\). Input:\(round\), \(bytes\), interval Output: The next poling interval
1 Function\(golden\_section\_searching(void)\,(round\_bytes\),interval): if\(round=0\)then
2\(distance\gets R\times(MaxInterval-MinInterval)\); \(interval_{low}\gets MinInterval+distance\); return\(interval_{low}\)
3 end if
4 if\(round=1\)then
5\(perf_{low}\gets bytes\); \(interval_{high}\gets MaxInterval-distance\);
6\(selected\gets High\); return\(interval_{high}\)
7 end if
8 if\(selected\) = Lowthen
9\(perf_{low}\gets bytes\);
10 else
11\(perf_{high}\gets bytes\);
12
13 end if
14 if\(distance\) <= \(MinDistance\)then
15 return\(interval\)
16
17 end if
18\(distance\gets distance\times R\);
19 if\(perf_{low}>perf_{high}\)then
20\(temp\gets interval_{high}\);
21\(interval_{high}\gets interval_{low}\);
22\(interval_{low}\gets temp\) + \(distance\);
23\(perf_{high}\gets perf_{low}\);
24\(selected\gets Low\);
25\(return\)\(interval_{low}\)
26
27 else
28\(temp\gets interval_{low}\);
29\(interval_{low}\gets interval_{high}\);
30\(interval_{high}\gets temp\) - \(distance\);
31\(perf_{low}\gets perf_{high}\);
32\(selected\gets High\);
33 return\(interval_{high}\)
34
35 end if
36
37 end if
```

**Algorithm 2**Golden-section search algorithm to find the near-optimal interval

For the implementation in the Linux kernel, \(R\) and \(distance\) were calculated and entered in advance as constant values. This is because floating-point operations cannot be performed within the Linux kernel. \(MinInterval\) and \(MaxInterval\) were set to 100 and 4000, respectively. The numbers are chosen according to the results of our preliminary examination, which showed that the near-optimal polling intervals can be found between 500 and 3000 us. In addition, _MinDistance_ was set to 30, so that the number of searches was limited to 11 iterations. The set of all distances is as follows: \(2410,1490,921,569,352,217,134,83,51,32\). Note that the first distance is used twice, at the first and second rounds. ## 4 Evaluation

We implemented NetAP on Linux v5.1.5 and evaluated the performance. We attempted to answer the following questions. * What is the most proper round length for performance collection and golden-section search algorithm? (Section 4.1)
* How does the polling interval change at runtime? (Section 4.2)
* What is the impact of NetAP on CPU utilization and response time? (Section 4.2)
* Is NetAP also effective for various packet sizes and different system environments? (Section 4.3)

The experimental environment was the same as that described in Section 3.4.2. In addition, for all experiments, the existing unmodified VirtIO processing was run at the beginning. Subsequently, we applied NetAP after 30 s (in Section 4.1) or 20 s (in Section 4.2 and 4.3) to observe the impact of NetAP on the performance of VMs easily. In the first and second experiments, we measured network bandwidth for 64B packets only. This was because a substantial amount of data center traffic consists of small packets, which consume more CPU resources than large packets [32; 33]. Furthermore, _perf_ and _pidstat_ were used to measure CPU utilization. ### First Experiment: Round Length

The first experiment evaluated the adaptation performance of NetAP depending on the round length. To find the near-optimal polling interval, the golden-section searching algorithm collects performance over a period (i.e., a round length). Subsequently, the changed interval is applied to VirtIO processing until the next round. If the round is very short, the polling interval changes frequently, which makes it difficult for the algorithm to find the near-optimal polling interval.