# Delay Bounded Multi-Source Multicast in Software-Defined Networking
## 2 Related Work  
In recent years, a lot of research has been devoted to the development of multicast routing algorithms to construct a delay constrained Steiner tree. [PERSON] et al. [19] considered an algorithm for constructing delay bounded minimum cost multicast trees. This idea and several other solutions were proposed in the literature. Based on their design objectives, the proposed solutions can be viewed as members of one of two possible classes. The first class solutions include algorithms which are designed to accommodate Internet environments. The second class is more based on algorithms which aim at reducing the cost of the multicast tree, while bounding the end-to-end delay. [PERSON] et al. [20] gave the first heuristic for delay constrained minimum Steiner tree problem, normally referred to as KPP. This heuristic computes a constrained closure graph which takes approximation time of \(O\left(U|V|^{3}\right)\). When the link delays and the user specified delay bound (_U_) takes non-integer values, KPP multiplies out fractional values to get integer and \(V\) is the set of vertices. Following this approach, KPP is guaranteed to construct a constrained tree if one exists. The bounded shortest multicast algorithm (BSMA) is another delay-constrained minimum Steiner tree algorithm that is considered the best in terms of tree cost [21]. This algorithm iteratively replaces the edges in the tree until the tree cost cannot be further reduced. BSMA used \(k\)-shortest path algorithm to find lower cost edges. The time complexity for BSMA is \(O\left(K|V|^{3}log|V|\right)\), where \(K\) may be very large in cases of large, densely connected networks and it may be difficult to achieve acceptable running time. The approaches of the above mentioned algorithms are limited to a single source on a normal network as opposed to multiple sources in SDN that we have considered in this paper. The utilization of the SDN controller and traffic engineering can make the above algorithms more effective as they are based on the traditional networks. A fast and effective algorithm which approximates the SMT problem using a minimum spanning tree (MST) was presented in [22]. Other algoritms based on greedy strategies achieve better approximation ratio of about 1.693 in [23] and 1.55 in [24]. These methods can incur considerably high time complexity than the MST approximation algorithm. Although the fast SMT algorithm does not achieve the optimal approximation ratio, it significantly saves more computation time than other algorithms. Therefore, it is more suitable for large multicast groups and large-scale networks than other algorithms. Such SMT algorithms, however, remain inapplicable to the DBMS problem proposed by this paper as they are based on a single source multicast. Fortunately, the emergence of SDN makes it possible to realize novel multicast protocols. A new SDN based reliable multicast routing algorithm by [PERSON] et al. [24], called RAERA is a typical example. Given any multicast group, RAERA constructs a shortest-path and reliable multicast tree. It enables each destination to retrieve content from at least one reliable recovery node along the path towards the source if necessary. Table 1 lists some papers in literature based on multicast routing on SDN and their major contributions. Authors in [3] studied the relationship between cost and coverage in the partially deployed SDNs. They deduced that after such partial deployment, the benefits of SDN potentially extend over the whole network through the SDN-enabled nodes. The most related research work involving routing with multi-source was done by [PERSON] et al. [25]. This work involved utilizing the aspect of uncertain source nodes, however it leaves out the important factor of traffic delay constraint that we study in this paper. Another closely related work was done on multi-source multicast in [26], which deals with delivering a stream from multiple sources to a group of destinations.