nfvbenchvm: fix image URL in build log
[nfvbench.git] / docs / development / design / ndrpdr.rst
1 .. This work is licensed under a Creative Commons Attribution 4.0 International
2 .. License.
3 .. http://creativecommons.org/licenses/by/4.0
4 .. (c) Cisco Systems, Inc
5
6 NDR/PDR Binary Search
7 =====================
8
9 The NDR/PDR binary search algorithm used by NFVbench is based on the algorithm used by the
10 FD.io CSIT project, with some additional optimizations.
11
12 Algorithm Outline
13 -----------------
14
15 The ServiceChain class (nfvbench/service_chain.py) is responsible for calculating the NDR/PDR
16 or all frame sizes requested in the configuration.
17 Calculation for 1 frame size is delegated to the TrafficClient class (nfvbench/traffic_client.py)
18
19 Call chain for calculating the NDR-PDR for a list of frame sizes:
20
21 - ServiceChain.run()
22     - ServiceChain._get_chain_results()
23         - for every frame size:
24             - ServiceChain.__get_result_per_frame_size()
25                 - TrafficClient.get_ndr_pdr()
26                     - TrafficClient.__range_search() recursive binary search
27
28 The search range is delimited by a left and right rate (expressed as a % of line rate per direction).
29 The search always start at line rate per port, e.g. in the case of 2x10Gbps, the first iteration
30 will send 10Gbps of traffic on each port.
31
32 The load_epsilon configuration parameter defines the accuracy of the result as a % of line rate.
33 The default value of 0.1 indicates for example that the measured NDR and PDR are within 0.1% of line rate of the
34 actual NDR/PDR (e.g. 0.1% of 10Gbps is 10Mbps). It also determines how small the search range must be in the binary search.
35 Smaller values of load_epsilon will result in more iterations and will take more time but may not
36 always be beneficial if the absolute value falls below the precision level of the measurement.
37 For example a value of 0.01% would translate to an absolute value of 1Mbps (for a 10Gbps port) or
38 around 10kpps (at 64 byte size) which might be too fine grain.
39
40 The recursion narrows down the range by half and stops when:
41
42 - the range is smaller than the configured load_epsilon value
43 - or when the search hits 100% or 0% of line rate
44
45 Optimization
46 ------------
47
48 Binary search algorithms assume that the drop rate curve is monotonically increasing with the Tx rate.
49 To save time, the algorithm used by NFVbench is capable of calculating the optimal Tx rate for an
50 arbitrary list of target maximum drop rates in one pass instead of the usual 1 pass per target maximum drop rate.
51 This saves time linearly to the number target drop rates.
52 For example, a typical NDR/PDR search will have 2 target maximum drop rates:
53
54 - NDR = 0.001%
55 - PDR = 0.1%
56
57 The binary search will then start with a sorted list of 2 target drop rates: [0.1, 0.001].
58 The first part of the binary search will then focus on finding the optimal rate for the first target
59 drop rate (0.1%). When found, the current target drop rate is removed from the list and
60 iteration continues with the next target drop rate in the list but this time
61 starting from the upper/lower range of the previous target drop rate, which saves significant time.
62 The binary search continues until the target maximum drop rate list is empty.
63
64 Results Granularity
65 -------------------
66 The binary search results contain per direction stats (forward and reverse).
67 In the case of multi-chaining, results contain per chain stats.
68 The current code only reports aggregated stats (forward + reverse for all chains) but could be enhanced
69 to report per chain stats.
70
71
72 CPU Limitations
73 ---------------
74 One particularity of using a software traffic generator is that the requested Tx rate may not always be met due to
75 resource limitations (e.g. CPU is not fast enough to generate a very high load). The algorithm should take this into
76 consideration:
77
78 - always monitor the actual Tx rate achieved as reported back by the traffic generator
79 - actual Tx rate is always <= requested Tx rate
80 - the measured drop rate should always be relative to the actual Tx rate
81 - if the actual Tx rate is < requested Tx rate and the measured drop rate is already within threshold
82   (<NDR/PDR threshold) then the binary search must stop with proper warning because the actual NDR/PDR
83   might probably be higher than the reported values