# FANT: Flexible Attention-Shifting Network Telemetry
## 5 Attention-Switching Strategy
### Implementation  
To make the algorithm's implementation clearer, we use the following notations: \(c.rows\) refers to the set of paths that include all paths in \(M\) containing the link \(c\). \(M.columns\) refers to the set of links that includes all links in \(M\). **Input and Output** The algorithm takes the following inputs: (i.) A set of links \(R\) (\(l\in R\)). (ii.) A probe trace set \(p\in P\) generated by a path generation algorithm chosen by the user. (iii.) Acceleration factors \(a_{1}\) and \(a_{2}\) (ranging from 0 to 1, where a higher value speeds up the algorithm but the solution deviates more from the theoretical optimum). The output is a set of paths \(A\) (\(p\in A\)), where each path \(p\) in \(A\) is set for detailed measurement in the upcoming measurement cycles. **Initialization** Lines 1-4: Initialize \(A\) as an empty set and \(M\) as the head node of a doubly circular linked list (initially empty). For each path \(p\) in \(P\), check if it shares any links with \(R\). If so, update \(p\) to the intersection of \(p\) and \(R\), and add \(p\) as a row of \(M\) to form the data structure (optimization D). If not, do not add \(p\) to \(M\). The function \(M.\)add_rows works as in the following steps: We first create column header nodes for all links \(l\) (\(l\in p\)) that are not already present in \(M.columns\). Then, create a row header node for \(p\). Next, for each links  
Figure 4: Fast recursion and backtracking based on data structures in idea D.  
in \(p\), create a node and vertically link it to the bottom of its respective column node. Finally, connect all these newly created nodes horizontally to form a circular doubly linked list. The \(function\) Estimate Coverage Cost (ECC, Lines 5-10) takes the current data structure \(M\) as input and returns an estimated cost to cover all columns in this state. **Calculation** First we initialize cover as an empty set (storing unique links already covered), \(Count\_out\) as 0 (tracking the number of coverage iterations during the estimation), and \(Count\_in\) as 0 (tracking the number of paths in each coverage iteration). The estimation process involves iterating over uncovered columns \(c\) in \(M\), selecting the union of all paths containing \(c\) as the coverage capability for this iteration and choosing the minimum cost among all paths containing \(c\) as the cost for this iteration. Update \(Count\_in\), \(Count\_Out\), and \(CostH\) (where the update amount for \(CostH\) is slightly amplified by the acceleration factor \(a_{1}\)). When cover includes all links in \(M\), it indicates that our estimation has covered the current state of \(M\). Finally, we slightly amplify the cost based on the number of coverages and the acceleration factor \(a_{2}\), then output the result. The \(function\)Explore Path Combinations Recursively (EPCR, Lines 11-33) is a recursive function that takes \(M\), \(A\), and \(T\) as inputs (the pseudocode in Algorithm 2 is written recursively to help readers understand. However, implementing the algorithm iteratively, by manually maintaining a stack, would be more efficient than implementing it recursively). \(T\) represents the maximum allowed cost in the search process (similar to the allowed search depth in traditional iterative deepening search algorithm [26]). Lines 12-15 check if the estimated cost to cover the current state is still less than the allowed cost. If it is, proceed with the logic; otherwise, return false and begin backtracking. Before backtracking, update \(T_{min}\) based on the \(cost_{sum}\) (the minimum value of the actual cost plus the estimated cost). \(T_{min}\) maintains the minimum \(cost_{sum}\) that exceeds \(T\). Lines 16-17 check if \(M\) is empty (i.e., the head node of the doubly linked list points to itself) to determine if the recursion of EPCR should stop because a feasible solution has been found. After verifying the above two conditions, EPCR is recursively invoked.