# Delay Bounded Multi-Source Multicast in Software-Defined Networking
## 4 Problem Formulation  
In this section, we firstly look at the important observations about our DBMS scheme, thereafter we present the problem formulation and prove its NP-hardness. Lastly, we present a mixed integer linear programming model for the DBMS scheme. Multicast is a natural approach of routing content from a source to a set of destination nodes. Unlike the unicast, it benefits in efficiently saving the bandwidth consumption and reducing the load on the source. The total cost of a multicast tree, which spans the single source and all destinations is widely used as the performance metric of a multicast. In most cases, the cost of multicast tree depends on the amount of links occupied without considering the diversity that exists among the network links. To minimize tree delay cost, given a multicast group, many approximation methods like in [19] have been proposed to construct the SMT. Given the same set of destinations, the delay of a multicast group is sensitive to the selection of the source. In many situations, the content replica design [18] can be used to ensure that the source of a multicast transfer does not necessarily have to be located in a specific location. A simple method for exploiting such opportunities is to calculate the SMTs for multicast groups with same set of destinations but different sources. When multiple sources participate simultaneously, a more efficient multicast can be formed. The best picked SMT with a single source may not be the optimal selection when using multiple sources. Such a preferred design of having multiple sources participating simultaneously, however, cannot be achieved by the approaches in the literature, which are relying on a traditional single-source multicast. Those approaches remain inapplicable to the DBMS problem we are proposing in this paper. Since we focus on the delay bounded multi-source problem in the data forwarding plane, we assume that each switch connects to the controller with a direct link in this paper. The topology of the network without the controller is modeled as a di-graph \(G(V,E)\), where \(V\) denotes the set of nodes (switches), and \(E\) denotes the set of edges (links) among the nodes. Each link \(e\in E\) is associated with a delay cost \(\delta_{(u,v)}\) i.e., for link \((u,v)\). Given a destination set \(D\in V\) and a potential source set \(S\in V\), DBMS tries to deliver the content to the whole set of destinations in \(D\) from partial or even all potential sources in set \(S\). There is a constraint that each destination in set \(D\) must just reach to one and only one potential source in set \(S\). This simply means that when set \(S\) contains only one source, then the DBMS is actually equivalent to the deterministic multicast. This does not impose any constraint on the selection of used sources for each destination \(d\in D\). Therefore, DBMS will still be a deterministic if all destinations access any \(s\in S\) as their common source even if \(\left\lvert S\right\rvert>1\). The transmission delay cost of DBMS is basically dominated by the strategies of using such sources, hence, in the following paragraphs we explain the process of constructing a DBMS-Forest. DBMS-Forest in this case is a product of minimum delay cost trees formed by the DBMS scheme. The DBMS scheme creates DBMS-Forest from trees spanning each destination \(d\in D\) with only one source, such that the total delay of utilized links in each tree is minimized. Any pair of source nodes \(s_{1}\) and \(s_{2}\) appearing in a multicast tree must be isolated into different trees. Isolating the source nodes ensures that no destination node can be reached by more than one source node, as this can increase the delay cost of the resultant DBMS-Forest. This will also reduce the congestion at each source. Thus, if there are \(k\) potential sources in \(S\), then the DBMS-Forest will consists of \(k\) isolated trees, each of which roots at one of those \(k\) sources. The DBMS becomes the deterministic multicast when the source set contains only one element.