# Delay Bounded Multi-Source Multicast in Software-Defined Networking
## 4 Problem Formulation
### Mixed Integer Linear Programming
\begin{table}
\begin{tabular}{l l} \hline \hline
**Notations** & **Description** \\ \hline \(G(VE)\) & Network topology \(G\), with node set \(V\) and link set \(E\) \\ \(S\in V\) & potential source set \\ \(D\in V\) & Destination set \\ \(s\in S\) & Each potential source node in set \(S\) \\ \(d\in D\) & Each destination node in set \(D\) \\ \((u\),\(v)\) & A link from \(u\) to \(v\) \\ \(T\) & Tree \\ \(P\) & Path \\ \(P_{(s,d)}\) & A path from \(s\) to \(d\) \\ \(\delta\) & Delay bound \\ \(\delta_{(u,v)}\) & Delay cost across link (\(u\),\(v\)) \\ \(\delta(T)\) & Delay cost of tree \(T\) \\ \(\delta(P)\) & Delay cost across path \(P\) \\ \(Nv\) & The set of all neighbor nodes of node \(v\) in \(G\) \\ \(\omega_{(d,s)}\) & Denote whether a destination node \(d\) selects source node \(s\) as the root node \\ \(\omega_{(d,s)}=1\) & There is a path from \(d\) to \(s\) \\ \(\pi_{(d,u,v)}\) & Whether link (\(u\),\(v\)) is in the path from the destination \(d\) to source \(s\) \\ \(\varepsilon_{(u,v)}\) & Whether link (\(u\),\(v\)) is in the output tree \(T\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Notations. Constraints  
To find \(\epsilon_{(u,v)}\), our MILP formulation include the following constraints, which explicitly describe the routing principles for DBMS tree creations;  
\[\sum_{s\in S}\varpi_{(d,s)}=1,\forall d\in D \tag{4}\]  
For every destination node \(d\in D\), the first constraint (4) ensures that there exist only one source node \(s\in S\) such that there exists at least one path from \(d\) to \(s\) in the output tree \(T\). Equations (5)-(7) impose constraints on finding the path from every destination \(d\) in \(D\) to its source \(s\). More precisely, given any destination node \(d,s\) is the source of the path towards \(d\). \[\sum_{v\in N_{s}}\pi_{(d,s,v)}=1,\varpi_{(d,s)}=1,\forall d\in D,\exists s\in S \tag{5}\]  
Constraint (5) implies that only one link \((s,v)\) from \(s\) to any neighbor node \(v\) needs to be selected with \(\pi_{(d,s,v)}=1\). At the same time, it ensures that there exists only one path from \(s\) to \(d\), and any pair of source nodes in the output tree \(T\) is isolated. On the other hand, every destination node \(d\) is the flow destination. \[\sum_{u\in N_{d}}\pi_{(d,u,d)}=1,\varpi_{(d,s)}=1,\forall d\in D,\exists s\in S \tag{6}\]  
Constraint (6) ensures that only one link \((u,d)\) from any neighbor node \(u\) to \(d\) must be selected with \(\pi_{(d,u,d)}=1\). \[\sum_{v\in N_{u}}\pi_{(d,u,v)}=\sum_{v\in N_{u}}\pi_{(d,v,u)}=1,\varpi_{(d,s) }=1. \tag{7}\]  
For any other node \(u\) in graph \(G\), we can infer from constraint (7) that it is either located in the path \(P\) from \(s\) to \(d\) or not. If \(u\) is located in the path \(P\), then \(u\) has one incoming flow in the path with one binary variable \(\pi_{(d,u,v)}=1\) and one outgoing flow in the path with one binary variable \(\pi_{(d,u,v)}=1\). Otherwise, \(\pi_{(d,v,u)}=0\) and \(\pi_{(d,u,v)}=0\). It is important to note that, according to the objective function, \(\pi_{(d,v,u)}=1\) is set for just one neighbor node \(v\) so as to minimize the delay cost of outgoing tree \(T\). \[\forall d\in D,\exists s\in S,\forall u\in V,u\
eq d,u\
eq s \tag{8}\]  
\[\pi_{(d,u,v)}\leq\epsilon_{(u,v)},\forall d\in D,\exists s\in S,\forall_{(u, v)}\ \in E \tag{9}\]  
The last 2 constraints (8) and (9) desires to find the routing of the outgoing tree, i.e., \(\epsilon_{(u,v)}\). More specifically, \(\epsilon_{(u,v)}\) must be 1 if link \((u,v)\) is in the path between at least one pair of source node \(s\) and destination node \(d\), i.e., \(\pi_{(d,u,v)}=1\). The output DBMS-Forest is the union of all the trees created.