# An Initial Load-Based Green Software Defined Network +
## 4 Problem Formulation  
Since we focus on the energy saving problem in the data forwarding plane, we assume that each switch connects to the controller with a direct link in this paper. The topology of the network without the controller is modeled as a di-graph \(G(V,E)\), where \(V\) denotes the set of nodes (switches), and \(E\) denotes the set of edges (links) among the nodes. \(|V|\) and \(|E|\) denote the number of the switches and links respectively. Since the links between the controller and switches won't be turned to sleep, the controller is neglected in this topology. The following symbols are used in the problem description. * \(G_{p}(V_{p},E_{p})\): virtual topology. * \(K\): the number of new demands. * \((s_{k},d_{k})\): source and destination nodes of the \(k\)th communication demand, \(k\in\{1,2,3,...,K\}\). * \(r_{k}\): requested bandwidth of the \(k\)th communication demand, \(k\in\{1,2,3,...,K\}\). Figure 1: Green SDN Design. Awaking process: (a1) Communication demands (a2) Set of links that need to be awoken (a3) Wake command messages (a4) link status ACK (a5) Flow table. Sleeping process: (b1) Detection command message (b2) link status reply (b3)Set of links that turn to sleep (b4) sleep command messages (b5) link status ACK. \(p_{ij}\): power consumption of link \((i,j)\) when in active mode, \((i,j)\in E\). \(c_{ij}\): the capacity of link \((i,j)\), \((i,j)\in E\). \(u_{ij}\): the used bandwidth of link \((i,j)\), \((i,j)\in E\). \(y_{ij}\): binary variable indicating whether link \((i,j)\) belongs to \(E_{v}\), equals 1 if link \((i,j)\) belongs to \(E_{v}\), and otherwise equals 0. \(x_{ij}\): binary variable indicating the status of link \((i,j)\), equals 1 if in working state, and otherwise equals 0. \(f_{ij}^{k}\): the traffic of the \(k^{th}\) demand along link \((i,j)\), \(k\in\{1,2,3,...,K\}\), \((i,j)\in E\). As analyzed in Section 3, the problem can be modeled as a MILP problem as following. The objective function is:  
\[Minimize\sum_{\forall(i,j)\in E}p_{ij}x_{ij} \tag{1}\]  
Subject to:  
\[\sum_{\forall k\in K}f_{ij}^{k}\leq(c_{ij}-u_{ij})x_{ij}\qquad\forall(i,j)\in E \tag{2}\]  
\[\sum_{\{j|\forall(i,j)\in E\}}f_{ij}^{k}-\sum_{\{j|\forall(j,i)\in E\}}f_{ji}^ {k}=\left\{ \begin{array}{cc}r_{k}&j=s_{k}\\ -r_{k}&j=d_{k}\\ 0&\text{otherwise}\end{array} \right.\quad\forall j\in V,\forall k\in\{1,2,...,K\} \tag{3}\]  
\[x_{ij}\geq y_{ij}\qquad\forall(i,j)\in E \tag{4}\]  
\[x_{ij}\in\{0,1\}\qquad\forall(i,j)\in E \tag{5}\]  
\[0\leq f_{ij}^{k}\leq r_{k}\qquad\forall k\in\{1,2,...,K\},\forall(i,j)\in E. \tag{6}\]  
The objective function minimizes the energy consumption of all the links. In the formulations, the energy consumption of sleep mode is neglected since it is always far less than that of active mode. Constraint (2) ensures that the loads of links meet their capacity threshold after taking the new loads. Constraint (3) ensures that the demands are routed beginning with their source nodes and ending in their destination nodes. Constraint (4) guarantees that the links in the virtual topology are in the working state. The decision variable domains are specified in (5) and (6). Note that, in the above model, we assume that each switch connects to the controller with a direct link ideally. For the networks where the switches connect to the controller in a multihop way, links used in the switch-to-controller paths should always remain in the working state since the controller messages must be transmitted quickly. Then, these links can be treated as the links in the virtual topology in GreSDN, i.e., the variables \(y_{ij}\) of these links are always equal to 1. Once the above model is resolved, the optimal path set for energy saving can be acquired by the values of variables \(f_{ij}^{k}\), and the links that need to be woken up can be acquired through comparing \(x_{ij}\) with \(y_{ij}\). Unfortunately, without constraint (4), the above model is a multi-commodity flow problem, which is well known as a NP-hard problem.