# Delay Bounded Multi-Source Multicast in Software-Defined Networking
## 4 Problem Formulation
### Mixed Integer Linear Programming  
We design a Mixed Integer Linear Programming (MILP) formulation for the DBMS problem. Let \(Nv\) denote the set of all neighbor nodes of node \(v\) in \(G\), and \(u\) is in \(Nv\) if (\(u\),\(v\)) is a link from \(u\) to \(v\). Let \(\mid S\mid\) denote the potential source set of the DBMS scheme, and \(\mid D\mid\) denote the destination set. The DBMS scheme needs to ensure that there is only one path in each tree from every destination node \(d\in D\) to only one source node \(s\in S\) in output DBMS-Forest. Assuming that path \(P\) from the multicast source node \(s\in S\) to the destination node \(d\in D\) satisfy the delay bound \(\delta\). Given \(G(V,E)\), \(S\), \(D\) and \(\delta\), the DBMS scheme's task is to construct a DBMS-Forest, consisting of trees \(T\left(V,E\right)\), such that \(V^{{}^{\prime}}~{}\subseteq~{}V\), \(E~{}\subseteq~{}E\), and (i) \(\delta(T)\) is minimum, (ii) \(\forall d\in D\exists P\) such that \(P\) is a path from \(s\) to \(d\) in \(T\), and \(\delta(P)~{}\leq~{}\delta\). To achieve this goal, our DBMS scheme includes the following binary decision variables. All other major notations used in this paper are listed in Table 2.  
Let binary variable \(\varpi_{(d_{S})}\) denote whether a destination node \(d\) selects a source node \(s\) as the root node. Meaning, there is a path from \(d\) to \(s\) if \(\varpi_{(d_{S})}=1\). In this setting, let binary variable \(\pi_{(d,u,v)}\) denote whether link (\(u\),\(v\)) is in the path \(P\) from the destination node \(d\) to the source node \(s\). Let binary variable \(\varepsilon_{(u,v)}\) denote whether link (\(u\),\(v\)) is in the output tree \(T\). Intuitively, we should find the path from each destination \(d\) to just one source node \(s\) with \(\varpi_{(d_{S})}=1\). Thus, every link (\(u\),\(v\)) in the path has \(\pi_{(d,u,v)}=1\)Let binary variable \(\delta_{(u,v)}\) denote a delay that a packet experiences across link (\(u\),\(v\)). Given the above notation, the delay experienced by a packet traversing a path \(P\) is defined as \(\delta(P)=\sum\delta_{(u,v)}\forall_{(u,v)}\in E\). The routing of the resultant DBMS-Forest with \(\varepsilon_{(u,v)}=1\) for every link (\(u\),\(v\)) in the DBMS-Forest can be achieved by the union of the paths from all the destination nodes in \(D\) to at least one source node in \(S\). Our goal is to find trees with minimum delay cost as defined in Equation (1) under the delay constraint defined in Equation (2). This means that, we need to solve the following problems;  
\[\min\delta(T)=\sum_{(u,v)\in E}\delta_{(u,v)}\times\varepsilon_{(u,v)} \tag{1}\]  
where the weight \(\delta_{(u,v)}\) denote the delay of link (\(u\),\(v\)), and \(\forall d\in D\)  
\[\delta(P_{(s,d)})=\sum_{(u,v)\in P_{(s,d)}}\delta_{(u,v)}<\delta \tag{2}\]  
where, \(P_{(s,d)}\) is a path on tree \(T\) from \(s\) to \(d\) and (\(u\),\(v\)) is a link on \(P_{(s,d)}\). The bounded delay requirement is additive over individual paths from every \(s\) to its destinations \(d\) on the tree \(T\). To ensure the existence of such a tree which satisfies Equation (2), the following condition must hold, where \(SDP\) (\(s\), \(d\)) is the Shortest Delay Path from source \(s\) to destination \(d\):  
\[\forall d\in D:\sum_{(\delta)\in SDP(s,d)}\delta_{(u,v)}<\delta \tag{3}\]  
Otherwise, a routing tree which can meet the delay bound \(\delta\) does not exist.