# An Extensible Automated Failure Localization Framework Using NetKAT, Felix, and SDN Traceroute
## 4 Use-Cases
### Performance
#### 4.4.2 Performance of a Single Test  
The time required to perform the test of a single host pair can be given by the following equation:  
\[\tau_{\text{test}}=\tau_{\text{generation}}^{\text{packet}}+\tau_{\text{ detection}}^{\text{packet detection}}+\tau_{\text{evaluation}}^{\text{packet detection}}+\tau_{\text{evaluation}}^{\text{route discovery}}+\tau_{\text{update}}^{\text{PM}}.\]  
\(\tau_{\text{generation}}^{\text{packet}}\), the time required for sending out test packets, depends on host capabilities and the network path to reach the host. Control and test packets are small in size; thus, the main factor here comes from the number of hops the control packet takes to reach the host. The time required for detecting these packets at the destination (\(\tau_{\text{detection}}^{\text{packet}}\)) should be determined by the network specification, and it also depends on the path the packets take. In a worst-case scenario, the control message and test packets travel on the longest forwarding path in the physical network, \(d_{\text{PHY}}\). We can give an upper bound for these two components based on the round trip time along the longest forwarding path:  
\[\tau_{\text{generation}}^{\text{packet}}+\tau_{\text{detection}}^{\text{ packet}}=\mathcal{O}(\text{RTT}(d_{\text{PHY}})).\]\(\tau_{\text{evaluation}}^{\text{packet detection}}\), evaluation of the incoming test packets is an insignificant amount of time, since only measurement data and the number of sent packets are compared at this step. \(\tau^{\text{route discovery}}\) is the execution time of SDN traceroute. According to [17], average latency of the tool is 1.23 ms per hop. In a worst-case scenario, it is \((d_{\text{PHY}}-2)\cdot 1.23\) ms on average since SDN traceroute is not able to test links between hosts and switches. To check if the reported path satisfies the network specification, the framework has two options. When the path consists of a single link only, the Path matrix has enough information to decide if the reported link is part of the correct path or not. In this case:  
\[\tau_{\text{evaluation}}^{\text{route discovery}}=\mathcal{O}(T_{\text{Im}}^{ \text{PM}}).\]  
If a longer link sequence is used, the order of the reported links need to be checked as well, which is done by executing Felix queries. Felix tests take at least one query (when the path proves to be correct) and \((d_{\text{PHY}}-2)\) tests at most (when the last link on the path proves to be incorrect only). Since Felix queries do not contain host to switch links, we can estimate this part of the equation with the following formula:  
\[\tau_{\text{evaluation}}^{\text{route discovery}}\leq(d_{\text{PHY}}-2) \cdot\tau_{\text{query}}^{\text{Felix}}.\]  
As seen in the previous section, Felix execution is dependent on the number of compiled terms, and [12] reports that execution time increases linearly: At 100 terms, it is around 20 ms and reaches 1 s at 10,000 terms, consequently:  
\[\tau_{\text{query}}^{\text{Felix}}=0.1\cdot|\text{terms}|\leq 0.1(2+d_{ \text{PHY}})(|p|+|t|)+0.2(n+d_{\text{PHY}}).\]  
As \(T_{\text{update}}^{\text{PM}}=\mathcal{O}(d_{\text{PHY}})\), the execution time will depend on \(d_{\text{PHY}}\) as well, thus: \(\tau_{\text{update}}^{\text{PM}}=\mathcal{O}(d_{\text{PHY}})\). Since the update operation modifies a list of size \(d_{\text{PHY}}\) at maximum, we can assume a short execution time; as such, operations take less than 1 ms even on a mid-range laptop when dealing with lists having tens of thousands items.