## 3 Inference Algorithm
### Problem Description  
Definition 1: the link control field refers to a path set which contains specified links, that is,  
\[\textit{Domain}(l_{k})\textit{=}\{p_{i}|\ p_{i}\in P\ \textit{and}\ l_{k}\in M _{i}\}\textit{Domain}(l_{k})\textit{=}\{p_{i}|\ p_{i}\in P\ \textit{and}\ l_{k}\in M_{i}\}\]  
Suppose the most likely solution to lossy links is \(X\subseteq L,\ x\) is a mark vector whose length is \(n_{e}\), when \(l_{k}\in X,\ x_{k}=1\), otherwise, \(x_{k}=0\). The problem of lossy link inferences can be described as:  
\[\left\{\begin{array}{c}\textit{minimize}\ \ 1_{n_{e}}x^{T}\\ \  
Definition 4: required links are the links that the coverage is 1.  
Definition 5: if the link \(l_{i}\) is not selected, \(R\) required links will appear in alternative links set based on \(m\), required degree of the link \(l_{i}\) is called \(R\), that is \(R(i)\).  
Heuristic strategies are proposed using the above definitions, as follows.  
Strategy 1: if there is the link \(l_{i}\) which makes \(Domain(l_{i})=P_{B}\), \(l_{i}\) is selected as the only lossy link.  
Strategy 2: required links must be selected as lossy links.  
Strategy 3: if \(Domain(li)\ \subseteq\ Domain(lj)\), the link \(li\) should be excluded.  
Strategy 4: if \(R(i)>R(j)\), the priority that link \(l_{i}\) is selected is higher than link \(l_{j}\).  
If \(l_{i}\) is not selected, the number of links which must be selected next is more than the number of links when \(l_{j}\) is excluded. The more the required links are, the harder optimization is; it is reasonable to select \(l_{i}\). It is a strategy to prevent the algorithm being too greedy.  
Strategy 5: the required degree of two links is same, the link selected to control the domain bases should be the higher one. This is a generalization of the simple greedy idea.  
Heuristic Lossy Link Inference (HLLI) is described as follows.  
Input: Network Topology _T(V,L)_, measurement data set \(D\), threshold value of arrival rate of link packets \(t_{i}\).  
(1) Initialization: suppose \(X\) is a set of lossy links. \(X=\phi\), \(P_{G}=\phi\), \(P_{B}=\phi\), initialization of mask vectors is zero, that is \(x=[0,0,\cdots 0]_{\ast}\).  
(2) Calculate \(t_{p}\) and arrival rate of link packets for each path in networks, \(\forall\ p_{i}\in P\), \(\varphi_{i}=r_{j}(r_{i}+f_{l})\). If \(\varphi_{i}=t_{p_{i}}\), \(P_{G}\subset P_{G}\cup\{p_{i}\}\), otherwise, \(P_{B}\subset P_{B}\cup\{p_{i}\}\).  
(3) Sets corresponding flag bits to \(l\) for constituent links between each path of \(P_{B}\), \(x_{i}=l\), if \(l_{i}\in M_{i_{i}}\)\(p_{i}\in P_{B}\).  
(4) Calculate path frequency, link coverage and required degree.  
(5) While \(P_{B}\
eq\phi\).  
1 If the link \(l_{i}\) exists which make \(Domain(l_{i})=P_{B}\), the link \(l_{i}\) is added into \(X\), \(X\): = \(X\cup\{l_{i}\}\); break;  
2 If required links exists, the link is added into \(X\): if \(\exists\ C(j)=1\) then \(X\): = \(X\cup\{l_{j}\}\), \(P_{B}\subset P_{B}\)-\(Domain(l_{i})\), continue; otherwise return to 3;  
3 \(\exists\ l_{i}\), \(l_{j}\), meet \(Domain(l_{i})\ \subseteq\ Domain(l_{j})\), \(P_{B}\subset P_{B}\)-\(Domain\{l_{i}\}\), continue; otherwise return to 4;  
4 Choose the link that required degree is the highest and add it to \(X\): if \(\forall\ x_{j}=1\), \(\exists\ l_{i}\), max \(R(i)\), then \(X\): = \(X\cup\{l_{j}\}\), \(P_{B}\subset P_{B}\)-\(Domain(j_{i})\), continue; otherwise return to 5;  
5 Select the links that control the biggest domain bases, add it into \(X\).  
(6) Output: \(X\).