# FANT: Flexible Attention-Shifting Network Telemetry
## 5 Attention-Switching Strategy
### Implementation
The implementation of EPCR involves three steps: (A) a downward search, (B) recursive calls, and (C) upward backtracking:  
A. The downward search consists of three deletion steps:  
* D1 (Lines 18-19): Iterate over all columns in \(M\) and remove the current column \(c\) using the function \(remove\_columns\). * D2 (Lines 20-21): For each path \(p\) (by traversing horizontally from the column node, we can find each \(p\)'s path header and add \(p\) to A) that contains column \(c\), add \(p\) to \(A\) and remove this row \(p\) from \(M\) (details on row and column removal are provided in Section 5.2). * D3 (Lines 22-23): Remove all links (columns) contained in the row \(p\) (the row currently being removed in D2), thereby completing the necessary updates to \(M\). Note that, unlike [PERSON]'s approach [25] of removing all rows containing the column (\(c\)_rows_), only the currently selected row \(p\) is removed from \(c\)_rows_. B. After completing the downward search, Lines 24-25 recursively call EPCR with the updated \(M\), \(A\), and the cost reduced by the cost of the selected path \(p\). If the return value of the call is true, the recursion of EPCR will stop, indicating that a feasible solution has been found. If not, we perform upward backtracking. C. Upward backtracking is the reverse process of the downward search and includes three restoration steps:  
* U1 (Lines 27-28): Restore the columns that were previously removed due to the selection of \(p\) by calling \(restore\_column\) for each \(c^{\prime}\) in \(p\). * U2 (Line 29): Then, restore row \(p\) by calling restore_row and remove \(p\) from \(A\). * U3 (Line 30-31): Continue to select another suitable \(p\). If all selections of \(p\) are unsuccessful, further backtrack by restoring the initially covered element \(c\) (previouslyremoved in step D1) using restore_column. If all recursive searches have been finished without finding a feasible solution, return false. ```
Input:\(R,P,a_{1},a_{2}\) Output:\(A\)
1\(A\leftarrow\emptyset\), \(M\leftarrow\emptyset\)\(\triangleright\)\(M\) is an empty dual-directional circular linked list for\(p\in P_{b}\)do
2 if\(p\cap R\
eq\emptyset\)then
3\(p\gets p\cap R\); \(M\).add_row(\(p\)) ; \(\triangleright\)\(M\).rows is a \(p\) set; \(M\).columns is a \(e\) set
4
5 Function ECC(\(M\)):
6\(Cover\leftarrow\emptyset\); \(Count\_out\gets 0\); \(Count\_in\gets 0\);
7 for\(c\in M\).columns \(\setminus\)\(Cover\)do
8\(E_{c}\leftarrow\bigcap_{p\in c\).rows \(p\); \(Cover\_add(e),e\in E_{c}\);
9\(Count\_in\leftarrow|c\).rows\(|\); \(Count\_out\gets Count\_out+1\);
10\(CostH\leftarrow CostH+\min(cost(c\).rows))*(Count\_in*a_{1}+(1-a_{1}))\);
11 return\(CostH\gets CostH*(Count\_out*a_{2}+(1-a_{2}))\)
12
13 Function EPCR(\(M\), \(A\), \(T\)):
14 ifECC(\(M\)) \(>\)\(T\)then
15 if\(T_{min}\)\(>\) ECC(\(M\)) \(+\)\(\sum_{p\in A}cost(p)\)then
16\(T_{min}\leftarrow\) ECC(\(M\)) \(+\)\(\sum_{p\in A}cost(p)\)
17
18 return\(false\)
19 if\(M=\emptyset\)then
20 return\(true\)
21
22 for\(c\in M\).columnsdo
23M.remove_column(\(c\))\(\triangleright\)\(c\).rows \(=\{p\in M\).rows \(|\)\(c\in p\}\)for\(p\in c\).rows do
24\(A\).add(\(p\));M.remove_row(\(p\));
25 for\(c^{\prime}\in p\)do
26\(M\).remove_column(\(c^{\prime}\));
27
28 ifEPCR(\(M\), \(A\), \(T\) - cost(\(p\))) then
29 return\(true\)
30 else
31 for\(c^{\prime}\in p\)do
32\(M\).restore_column(\(c^{\prime}\))
33\(M\).restore_row(\(p\)); \(A\).delete(\(p\))
34
35\(M\).restore_column(\(c\))
36
37 return\(false\)
38\(T\gets H(M)\);
39 whileTrue do
40\(T_{min}\leftarrow+\infty\)
41 ifEPCR(\(M\), \(A\), \(T\)) then
42 return\(A\)\(\triangleright\) This is the output of Attention shifting strategy
43
44
45 else
46\(T\gets Max(T_{min},T+1)\)
47
48
49 Line 32 calls ECC with the initialized \(M\) to determine the allowed cost for the first search. Lines 33-38 continuously execute the following logic: FANT initializes \(T_{min}\) to a high value to facilitate updating it to the minimum value during the recursion of PECR. Then, check if the EPCR function returns true.