# SDNPS: A Load-Balanced Topic-Based Publish/Subscribe System in Software-Defined Networking
## 4 Traffic Optimization Algorithm
### Problem Model  
First, we model the nodes's publish and subscribe interests formally: given a set of nodes \(V\) and a set of topics \(T\), a publish interest function \(PubInt\), which is defined to be a probability-valued function over domain \(V\times T\), and a subscription interest function \(SubInt\), which is similarly defined to be a Boolean-valued function over the same domain. That is to say, we say a node is interested in publishing an event with topic \(t\) iff \(PubInt(v,t)\in(0,1)\), and a node is interested in receiving a topic \(t\) iff \(SubInt(v,t)=true\). Then, The problem is formally defined as follows: Given \(G=(V,E)\), link bandwidth capacity c: C(E)\(\rightarrow{R_{+}}\), a publish interest function \(PubInt\) and a subscribe interest function \(SubInt\) over \(V\times T\), a topic \(t\in T\), we define the topic-connected subgraph \(G_{t}=(V_{t}\), \(E_{t})\) of G for topic t to be a minimal support graph induced by \(\delta_{t}=(PubInt_{t},SubInt_{t},Pubpr_{t})\), such that the cost is minimum. It is worth noting that the'minimum' can be measured in different ways, such as minimal cost or minimal numbers of nodes and edges. We call it 'the minimal cost topic-connected overlay' problem (MCTCO). **Definition 1** (The bottleneck bandwidth of the path). : _Given \(G=(V,E)\), \(r(e)\) is the available bandwidth of edge \(e\) (\(e\in E\)), a path path(s, d) between \(s\) and \(d\) is described by a sequence of links \(e\)(s, i), \(ei,j\)), \(e\)(\(j\), \(k\)), \(\cdots\), \(e\)(\(u\), d), each of which belongs to \(E\). The bottleneck bandwidth of path(\(u,v\)) is given in the following:_  
\[rp(path(u,v))=\min(r(s,i),r(i,j),r(j,k),\cdots,r(u,d)) \tag{1}\]  
**Definition 2** (MCTCO). : _Given \(G=(V,E)\), a cost matrix \(c(E)\), a topic \(t\), two interest function \(PubInt_{t}\) and \(SubInt_{t}\) over \(V\times T\), construct a topic-connected overlay network \(G_{t}=(V_{t}\), \(E_{t})\), such that \(\Sigma_{e\in E_{t}}C(e)\) is minimum, limited \((PubInt_{t}\bigcup SubInt_{t})\subseteq V_{t}\subseteq V\), \(E_{t}\subseteq E\)._  
The following lemma goes immediately after Definition 2. **Lemma 1**. : _MCTCO is NP-hard._  
Proof. : Consider the distinguished Steiner tree problem in graphs. Given an undirected graph G(V, E), an accident with a cost function \(c\): \(c(E)\)\(\rightarrow{R_{+}}\), and a terminal set \(D\) where \(D\subseteq\) V(G), find a tree \(Tr\) in \(G\), such that D \(\subseteq V(Tr)\) and \(C(E(Tr))\) is minimum. [PERSON] _et al._ has proven that the Steiner tree problem is one of the classical \(NP\)-hard problems [PERSON] _et al._ (2016). Now, consider the MCTCO problem. According to the definition, the constructed overlay network must be acyclic; that means a tree spanning all of the publish nodes (set \(S\)) and subscribe nodes (set \(D\)). There are probably some indispensable relay nodes. Note that the MCTCO is identical to the Steiner tree problem if we select one node \(s\) from \(S\) as the root node and treat \(S-\{s\}\bigcup D\) as terminal nodes. Therefore, MCTCO can be reducible to the Steiner tree problem. Hence, the MCTCO problem is \(NP\)-hard. Note that the above problem considers only one topic. For a set of topics, we can construct a set of minimal topic-connected overlay subgraphs. To avoid the imbalance of link traffic, when constructing minimal topic-connected overlay subgraphs, link residual bandwidth is considered as an important factor. Following, we define the residual bandwidth of graph \(G\). **Definition 3** (The residual bandwidth of graph \(G\)). : _Given \(G=(V,E)\). \(\mathrm{Y}(e)\) is the residual bandwidth of link \(e\), the residual bandwidth of graph \(G\) is defined as the minimum available bandwidth for all links in \(E\). That is,_  
\[\Re(G)=\min_{e\in E}(\mathrm{Y}(e)) \tag{2}\]  
With the above definitions, the load-balanced MCTCO problem can be mathematically stated as follows:Maximize \(\Re(G)\).