# Delay Bounded Multi-Source Multicast in Software-Defined Networking
## 5 DBMS Routing Algorithm
### Transformation of the Problem
7 end if
8 else
9 Fill the cell \(C[i,j]\) in \(D_{k}\) table with value \(d[i,j]\) of \(D_{k-1}\) table. 10 end if
11 On the sequence table
12 if\(C[i,j]\) and \(C[j,i]\) in \(D_{k}\) and \(D_{k-1}\) are the same, then
13 Fill \(C[i,j]\) and \(C[j,i]\) in \(S_{k}\) table with \(S_{k-1}\) value. 14 end if
15 else
16 At the end of the \(k^{th}\) loop, we get the required table with the minimum delay paths. 17 end if
18 Return the minimum delay and the delay path between any two nodes
19
20 end if
```  
**Algorithm 1**_Pseudocode for DBMS-DelayPath_  
Return the complexity of Algorithm 2._Pseudocode for DBMS-MST_  
```
Data: Array Result: DBMS-Minimum Spanning Tree
1 begin
2 Create an array of size \(v\) and initialize it to \(NULL\)
3 Create a min Priority Queue \(H\) of size \(v\)
4 Insert all vertices into \(H\) such that key value of starting vertex is \(0\) and other vertices is set to \(\infty\)
5 if\(H\) is not empty,then
6\(u\) = extractmin(\(H\)). 7 end if
8 forevery adjacent \(v\) of \(u\),do
9 if\(v\in H\),then
10 Update key values of \(v\) in \(H\) if delay of link (\(u\)-\(v\)) \(<u\). 11 end if
12
13 end for
14 Parrent[\(v\)] = u
15 Return minimum spanning tree
16
17 end for
```  
**Algorithm 2**_Pseudocode for DBMS-MST_As we suggested in Section 1, the DBMS scheme can be treated as a set of deterministic multicasts, each with a different source. Accordingly, we select the SMTs with the least delay cost to form the DBMS-Forest of the DBMS scheme. This method suffers the complexity of solving a set of NP-hard SMT problems. The DBMS scheme involving multiple sources may cost less total delay cost than the picked best SMT; hence, the prior approaches for traditional multicast remain inapplicable to the proposed DBMS scheme. For this reason, we propose the DBMS algorithm. Algorithm 3 summarizes the procedure of solving our MILP for Equations (1) and (2). In line 2, Algorithm 3 will creates a set \(Q\), then add the virtual source to that set. In line 5, Algorithm 3 will compare the delay cost of path \(P\) from the virtual source to each destination node with the input delay bound \(\delta\). The algorithm will add to set \(Q\) (lines 6-11) all the nodes that satisfy the delay bound, then use Algorithm 2 to find in set \(Q\), the minimum delay cost from each potential source node \(s\in S\) to each destination node \(d\in D\) according to our MILP presented in Section 4. ```
Data:\(G\) = (\(V,E\)), \(\left\lvert S\right\rvert\), \(\left\lvert D\right\rvert\) and the \(\delta\). Result: A DBMS-Forest, formed by the minimum delay cost trees rooting at each potential \(\left\lvert S\right\rvert\), the \(\left\lvert D\right\rvert\) that do not satisfy the \(\delta\). 1 begin
2 Create Graph \(G\) with a virtual source node
3 Create set \(Q\) which include the virtual source node
4 Connect all nodes in set \(\left\lvert S\right\rvert\) to the virtual source node, with \(\delta(u,v)=\infty\)
5 Call _DBMS-DelayPath_ to get the minimum delay cost path between the virtual source node and \(\left\lvert D\right\rvert\)
6 Compare the total delay cost of the path \(P\), from the virtual source node to \(\left\lvert D\right\rvert\) with the delay bound \(\delta\), according to equations (2) and (3)
7 if\(\delta(P)>\delta\), then
8 The path to the destination node does not satisfy the delay bound. 9 end if
10 else
11 Add nodes to set \(Q\). 12
13 end if
14 Call _DBMS-MST_ on set \(Q\) to get the minimum spanning trees
15 Return the DBMS-Forest
16
17 end for
```  
**Algorithm 3**_Pseudocode for DBMS algorithm_