# SDNPS: A Load-Balanced Topic-Based Publish/Subscribe System in Software-Defined Networking
## 4 Traffic Optimization Algorithm
### The Load-Balanced Topic-Connected Overlay Algorithm  
Aiming at the objective function mentioned above, we put forward a heuristic algorithm. This algorithm is evolved from the algorithms solving the multi-stream multi-source multicasting routing problem (MMMRP) [34]. There are other incidental algorithms proposed for inter-cluster routing. ```
1:\(G=(V,E)\), \(C(E)\)
2:// \(C(E)\) is the bandwidth capacity matrix
3:\(max(minR(E))\)
4:// \(min(R(E))=min(R_{eij})\), for \(\forall i,j\)\(e_{ij}\in E\)
5:// R(E) is residual bandwidth matrix, equals \(C(E)\) initially. 6:for each topic t do
7:\(G_{t}=MSG(S,t))\); // call for MCTCO algorithm
8: cb = \(\sum_{i=1}^{|t,PubInt|}t\cdot Pubpr(i)\cdot b\) ;
9:for each \(e\in E(G_{t})\)do
10:\(c(e)=c(e)\)-cb; // update the residual bandwidth;
11:endfor
12:endfor
13:endfor
```  
**Algorithm 1** Inter-cluster routing algorithm. The main idea of inter-cluster routing algorithm (Algorithm 1) is as follows. For every topic \(t\), we construct a topic-connected overlay subgraph \(G_{t}\) that spans its publish nodes and subscribe nodes (Line 2). Following, we compute the consumed bandwidth \(\sum_{i=1}^{|PubMed|}Pubpr_{t}(i)\cdot b\) of links in \(G_{t}\) (Line 3) with the node's publishing probability considered. Then, we update the residual bandwidth by subtracting \(\sum_{i=1}^{|PubMed|}Pubpr_{t}(i)\cdot b\) from \(c_{j}\) if \(e_{j}\) is in \(G_{t}\) (Line 5). These are repeated until all topics are processed (Lines 1-7). ```
0:\(G\) = (\(V\), \(E\)), \(PubInt\), \(SubInt\), \(P\)
0:\(G_{t}\) is a tree, \(SubInt\bigcup PublInt\in G_{t}\), \(G_{t}\subseteqq G\)\(min(\sum c(e_{j}))\), for \(\forall i,j\)\(e_{ij}\in G_{t}\)
1:if T.father is NULL then
2:\(G_{t}\) = \(\emptyset\); modify \(c(E)\) by strategy set for topic \(t\);
3:for each source \(s_{i}\in PubInt\)do
4: Tree \(T_{i}\) = WidestPTAthTree (G, \(s_{i}\));
5:endfor
6:for each \(d_{j}\in\) SubInt do
7: EnQueue (Q, \(d_{j}\));
8:endfor
9:while not empty (Q) do
10: currnode = DeQueue (Q);
11:while TRUE do
12: nextnode = the nextnode in path(currnode, \(S_{1}\));
13: nextwidth = rp(path(currnode, \(S_{1}\)));
14:for each \(s_{i}\in PubInt-\{S_{1}\}\)do
15: tempwidth=rp(path(currnode, \(s_{i}\))) in \(T_{i}\);
16:if tempwidth \(>\) nextwidth then
17: nextnode = the nextnode in path(currnode, \(s_{i}\));
18: nextwidth = tempwidth;
19:endif
20:endfor
21: Add (currnode, nextnode) to \(G_{t}\);
22:if nextnode in PublInt then
23: break;
24:endif
25: currmode = nextnode;
26:endwhile
27:endwhile
28: traverse graph \(G_{t}\) to get all the connected subgraph;
29: Add the widest edges which can connect two subgraphs to \(G_{t}\) until \(G_{t}\) is connected;
30:else
31: TF = T.father; \(G_{t}=G_{t.father.topic}\);
32: TFnodes = TF.subscribist \(\bigcup\) TF.publishist;
33: Tnodes = T.subscribist \(\bigcup\) T.publishist;
34: Bnodes = Tnodes-TFnodes;
35:for each node N in Bnodes do
36: Add the widest path from N to \(V_{G_{t}}\) to \(G_{t}\);
37:endfor
38:endif
```  
**Algorithm 2** Minimal cost topic-connected overlay algorithm (MCTCO). Algorithm 2 is constructing a topic-connected overlay network. Remember that we organize topics as a topic tree. Owing to the overlay relationship between child topic and its father topic, when a topic is in the first layer in the topic tree, we build the overlay network completely _ab initio_ for this topic; otherwise, we generate the overlay network for a topic from its father topic overlay network by adding some vertices and edges. For the first case, we firstly generate \(|PubInt|\) (also denoted with \(|S|\)) spanning trees, which are widest (Lines 2-4). There are several algorithms proposed for this, e.g., a modified [PERSON]'s algorithm or a modified Bellman-Ford algorithm, _etc._ In this paper, we adopt a modified [PERSON]'s algorithm, which has the same time complexity asymptotically and a faster run-time compared to the modified Dijkstra algorithm.