# A Multicast Routing Scheme for the Internet: Simulation and Experimentation in Large-Scale Networks
## Appendix A  
As commented on in Section 5.1, we consider an ILP formulation to obtain the near optimal solution for an ST algorithm adapting the LP model provided in [PERSON]'s Graph Library [38].  
Given the same definition provided in Section 3.1: a network topology modelled by an undirected weighted graph \(G=(V,E,\omega)\), where the set \(V,|V|=n\) represents the finite set of vertices or nodes (all multicast capable), the set \(E,|E|=e\) represents the finite set of edges or links, and \(\omega\) is a non-negative weight or cost function \(\omega:E\rightarrow\mathbb{R}+\). Given a set \(M\) of vertices, we want to find an acyclic sub-graph of minimum cost, \(T_{s,M}=(V_{T},E_{T})\), linking all of them together. This sub-graph \(T_{s,M}\) of \(G\) has \(\mathcal{V}=|V_{T}|\) vertices and \(\mathcal{E}=|E_{T}|=|V_{T}|-1\) edges and contains each vertex from \(M\). We set \(e_{i}\) and \(e_{o}\) as any incoming and outgoing edge, respectively.  
The following two binary variables are defined to know if an edge \(e\) or a vertex \(v\) is part of the sub-graph \(T_{s,M}\):  
\[x_{e}=\begin{cases}1&\text{if edge }e\in T_{s,M}\\ 0&\text{otherwise}\end{cases}x_{v}=\begin{cases}1&\text{if vertex }v\in T_{s,M}\\ 0&\text{otherwise}\end{cases} \tag{1}\]  
The objective of the optimisation problem is to minimise the total number of edges used to connect all the vertices in \(M\).  
\[\min\ U=\sum_{e\in\mathcal{E}}w_{e}\times x_{e} \tag{2}\]  
subject to  
\[\sum_{\begin{subarray}{c}e_{o}\in\mathcal{E}\\ e\sim v\end{subarray}}x_{e}\geq 1,\quad\forall v\in M, \tag{3}\] \[\sum_{e_{i}\in\mathcal{E}}x_{e}\leq 0,\quad v=s,\] (4) \[\sum_{\begin{subarray}{c}e_{i}\in\mathcal{E}\\ e_{i}\sim v\end{subarray}}x_{e}\leq 1,\quad\forall v\in V,\forall e_{i}\in \mathcal{E},\] (5) \[x_{e}\leq x_{v},\quad e\sim v,\forall v\in\mathcal{V},\forall e \in\mathcal{E}, \tag{6}\]  
\[\sum_{\begin{subarray}{c}e_{o}\in\mathcal{E}\\ e\sim v\end{subarray}}x_{e}\leq\{x_{v}+\sum_{\begin{subarray}{c}e_{i}\in \mathcal{E}\\ e\sim v\end{subarray}}x_{e}\},\quad\forall v\in\mathcal{V}, \tag{7}\] \[\sum_{\begin{subarray}{c}e_{o}\in\mathcal{E}\\ e\sim v\end{subarray}}x_{e}\geq 1-\{(1-x_{v})+(1-\sum_{\begin{subarray}{c}e_{i}\in \mathcal{E}\\ e\sim v\end{subarray}}x_{e})\},\quad\forall v\in\mathcal{V},\] (8) \[\sum_{v\in\mathcal{V}}x_{v}-\sum_{e\in\mathcal{E}}x_{e}=1 \tag{9}\]  
Equation (3) proves that each node of the multicast group must have at least one of its edges, either incoming or outgoing, as part of the sub-graph. Equation (4) providesthat the source node can not have any of its incoming links as part of the sub-graph. Equation (A5) defines that only one incoming link of the node can be part of the sub-graph. Equation (A6) means that if an edge is part of the sub-graph so it is the vertex. Equations (A7) and (A8) that guarantee that, if a node is not part of the multicast group and it has one incoming edge, it must have at least one outgoing edge as part of the sub-graph too. Finally, Equation (A9) says that the total number of vertexes is equal to the number of edges plus one.