# Delay Bounded Multi-Source Multicast in Software-Defined Networking
## 5 DBMS Routing Algorithm
### Transformation of the Problem  
In other for us to solve our problem, we transform the multi-source multicast problem into an ordinary flow network with only one source node. Given a network \(G(V,E)\), potential source nodes set \(S\) and a destination nodes set \(D\), we introduce a virtual source node to which all the potential source nodes set \(S\) members connect to. The potential source nodes are all directly connected to the virtual source node with a delay cost \(\delta(u,v)=\infty\). This will ensure that a minimum delay cost path \(P\), from the virtual source node to any destination node \(d\), passes through one of the potential source node \(s\). That particular potential source node \(s\) on the minimum delay cost path \(P\), becomes the source node of that particular destination node \(d\). **Example 1**. : _Consider Figure 3 as an illustration of how our DBMS-Forest in a small scale network of undirected graph is formed. Let \(G(V,E)\) be the SDN network, where \(V\) denotes the set of nodes (switches), \(E\) denotes the set of links among the nodes and the virtual source node \(v\). The potential source node set \(|S|=(s_{1},s_{2},s_{3},s_{4})\) and destination node set \(|D|=(a,b,...l)\). Each link is weighted with a delay cost. Since SDN can coexist with any topology that is listed below it, in our example topology we only show SDN nodes (switches) without the controller for simplicity. The introduction of a virtual source node \(v\) on this topology enables us to convert the problem of multiple sources into an ordinary flow network with only one source node. All the potential source nodes are directly connected to the virtual source node \(v\) with a delay cost \(\delta(u,v)=\infty\)._  
All minimum delay cost paths from the virtual source node \(v\) to any of the destination nodes have to pass through one of the potential source nodes. That potential source node will then be the ultimate source for that destination node. When our DBMS algorithm is implemented using this topology, the SDN-Controller is able to find the minimum delay cost path for each destination node that satisfy the delay bound \(\delta\). In Figure 2(b) the DBMS-Forest of topology in Figure 2(a) is displayed and each source node is isolated from other source nodes in the tree. The assumption is that the delay cost is symmetric, i.e., the values are equal for both directions of a link. The source node of each multicast tree becomes the root node. Our Algorithm 3 is able to construct the DBMS-Forest for any kind of topology that satisfy our routing constraints as long as all the necessary inputs are provided. The main idea of DBMS-DelayPath algorithm (Algorithm 1) is to calculate the minimum delay cost as well as finding the minimum delay path between any two nodes. DBMS-DelayPath is based on the well known Floyd Algorithm. The algorithm firstly create a delay table and then iteratively find the  
Figure 3: An example of how our DBMS scheme is able to create minimum delay cost trees that form the DBMS-Forest. delay cost between the adjacent nodes (lines 1-9). The sequence table is then created with all the delay paths between any two nodes and the minimum delay (lines 11-18). In Algorithm 1, the complexity of all the iterations is \(O(|V|)+O(|V|)+O(|V|^{2})+O(|E|)+O(|V|^{3})+O(|V|^{4})=O(|V|^{4})\). Thus the complexity of Algorithm 1 is \(O(|V|^{4})\). DBMS-MST Algorithm 2 is tasked with creating the minimum spanning tree. In Algorithm 2, the complexity of lines (5-10) is \(O((|D|+1)^{2})\). Thus the complexity of Algorithm 2 is \(O((|D|+1)^{2})\). ```
Data: Delay Table Result: Minimum Delay and the delay path between any two nodes. 1 begin
2 Create a delay table \(D_{k}\) and sequence table \(S_{k}\) in \(k^{th}\) iteration
3\(d[i,j]\) is the distance between adjacent vertices
4 Fill each cell \(C[i,j]\) in \(D_{k}\) using the following conditions
5 if\(d[i,k]+d[k,j]<d[i,j]\), then
6 Fill the cell \(C[i,j]\) in \(D_{k}\) with the value \(d[i,k]+d[k,j]\) of \(D_{k-1}\) table.