# FANT: Flexible Attention-Shifting Network Telemetry
## 5 Attention-Switching Strategy
### Basic Idea  
The basic workflow of our algorithm is as follows: Step 1: Based on an existing probe generation algorithm, we generate probe traces for network-wide measurements. Step 2: We transform the relationship between probes and links into a 0-1 matrix (if probe \(p\) measures link \(l\), then \(\text{Matrix\_huge}(p,l)\gets 1\)). Step 3: We identify the suspicious links in the measurement cycle \(t\) as links 1, 3, 4, and 7. Subsequently, we remove columns not corresponding to these links and delete rows that become entirely zeros following this column removal. This process yields a smaller matrix, which serves as the actual input for the algorithm. Step 4: As shown in the data structure in Figure 3, we store this smaller matrix in a Two-Dimensional Doubly Circular Linked List (TDDCL) [24; 25] to enhance the efficiency of subsequent computations. Step 5: We conduct a search using rapid pruning and iterative deepening techniques to find the most cost-effective combination that satisfies requirement R1.2 (i.e., setting probes 2, 3, and 6 for detailed measurements at time \(t+1*\delta t\)). In this workflow, we introduce four optimizations to significantly enhance the efficiency of the algorithm. **A. Reducing the Input:** Based on the suspicious links (marked in blue) from basic measurements, we compress the original matrix that represents the coverage relationship between the entire network's probes and links to generate a smaller input matrix. Specifically, we first remove all non-blue columns (\(l_{2}\), \(l_{5}\), \(l_{6}\)). After deleting these columns, rows that do not cover any links (such as \(p_{1}\), \(p_{5}\)) are also removed. (Step 3). **B. Cost-Based Iterative Deepening Search:** To manage space and time efficiently while solving NP-hard problems, FANT employs a cost-based iterative deepening search. By limiting the cost of the current solution (search node), FANT avoids getting stuck in deep search branches, which could consume excessive time and resources. For instance, the solution (\(p_{2}\), \(p_{6}\)) is only attempted when the allowable cost exceeds 4. When the allowable cost is 2, the solution (\(p_{2}\)) does not try to add \(p_{6}\) to the solution. Moreover, the allowable cost does not increase incrementally by 1 like traditional iterative deepening search algorithms [26]. Instead, it updates based on the minimum value that exceeded the allowable cost during the previous search (the allowable cost jumps to 4 from 2). **C. Early Pruning Based on Quick Estimation:** When the allowable cost is set at 5 and the solution is (\(p_{4}\)), FANT does not attempt to construct complete solutions such as (\(p_{4}\), \(p_{3}\), \(p_{6}\)), (\(p_{4}\), \(p_{3}\), \(p_{7}\)), or (\(p_{4}\), \(p_{6}\)) and then calculate their costs to decide whether to backtrack. Instead, a conservative quick estimation is used to assess the minimum additional cost required to achieve full coverage based on the current solution. If the current cost plus the estimated minimum cost exceeds the limit, the search backtracks immediately. The quick estimation process operates as follows: when solution (\(p_{4}\)) is selected, it is observed that \(l_{3}\) remains uncovered. Consequently, FANT utilizes all paths that include \(l_{3}\), such as \(p_{3}\) and \(p_{6}\), to estimate the coverage of links (\(l_{3}\), \(l_{7}\)). Then, FANT computes the estimated cost by adding the minimum costs of \(p_{3}\) and \(p_{6}\), which is 2. Therefore, FANT estimates that choosing \(p_{4}\), regardless of how optimally the remaining selections are made, will necessitate a minimum total cost of 6 (2+4). This results in the immediate backtracking of the search. **D. Fast Recursion and Backtracking:** The attention-shifting strategy, employing a TDDCL data structure to store the current search state, enhances the efficiency of iteration and backtracking by accelerating the deletion and restoration of rows and columns.