# An Initial Load-Based Green Software Defined Network +
## 5 Heuristic Green Routing Algorithm  
In our previous work [14], two routing algorithms, CWGA and DWGA, that can be used in the green scheme were presented. As analyzed in [14], CWGA performs better than DWGA in saving energy, but the computation complexity of CWGA is higher than that of DWGA. In this section, we work on decreasing the computation complexity of CWGA. The distance between two subgraphs in a connected graph which will be used in the algorithm, is defined. **Definition 1**. : _If \(G_{a}(V_{a},E_{a})\) and \(G_{b}(V_{b},E_{b})\) are two subgraphs in a connected graph \(G(V,E)\), the distance from \(G_{a}\) to \(G_{b}\) is the shortest distance from \(v_{i}\) to \(v_{j}\) in \(G\), \(\forall v_{i}\in V_{a}\), \(\forall v_{j}\in V_{b}\), i.e.,_  
\[d(G_{a},G_{b})=min\{d(v_{i},v_{j})\}\qquad\forall v_{i}\in V_{a},\forall v_{j} \in V_{b} \tag{7}\]  
We call this shortest distance between two subgraphs the vertical distance, and the path between two subgraphs with this vertical distance the vertical path. Note that \(G_{a}\) and \(G_{b}\) can be a single node in graph \(G\). For example, in Figure 2a, graph \(G\) consists of 10 nodes and 21 links. Denote \(\{v_{1}\}\) as \(G_{a}\), and the part with solid lines in Figure 2b as \(G_{b}\). Assuming that each edge has the same weight, and equals to 1, the distances between \(v_{1}\) and the nodes in \(G_{b}\) are \(d(1,0)=1\), \(d(1,2)=1\), \(d(1,4)=1,d(1,5)=2,d(1,7)=2\), and \(d(1,9)=2\); then the vertical paths between \(G_{a}\) and \(G_{b}\) are \((1,0)\), \((1,2)\) and \((1,4)\). The capacity constraint is considered first before calculating the path for the demand. For all the links in \(G\), if the load of this link will exceed its capacity after taking the current demand bandwidth, then remove it from \(G\) temporarily, and the new physical topology is denoted as \(G^{\prime}\). If this link belongs to \(G_{v}\) too, remove it from \(G_{v}\) at the same time and denote the new virtual topology as \(G^{\prime}_{v}\). After this action, all links in the new topology \(G^{\prime}\) and \(G^{\prime}_{v}\) will meet the bandwidth demand. So the paths calculated based on \(G^{\prime}\) and \(G^{\prime}_{v}\) can always satisfy the capacity constrain. To decrease the complexity of CWGA, the communication demands are classified into four cases based on the source node \(v_{s}\) and destination node \(v_{d}\): (1) \(v_{s}\) and \(v_{d}\) both belong to the virtual topology; (2) \(v_{s}\) belongs to the virtual topology, and \(v_{d}\) not; (3) \(v_{s}\) doesn't belong to the virtual topology, and \(v_{d}\) does; (4) Neither \(v_{s}\) nor \(v_{d}\) belongs to the virtual topology. The four cases will be treated differently; after calculating the path for \((v_{s},v_{d})\), \(G_{v}\) and \(u_{ij}\) will be updated according to this path. In the following text, the four cases will be described, each in turn. **CASE (1): \(v_{s}\) and \(v_{d}\) both belong to the virtual topology**  
As described in Algorithm 1, in this case, first we calculate whether there is a feasible path in \(G^{\prime}_{v}\) (Line 2). To do this, the classical shortest path algorithm (Dijkstra algorithm) is used in function \(\mathit{ShortestPath}\). If there is a path, then a path without changing virtual topology is acquired. Obviously, this is the optimal path for saving energy. If there is not a path, then find the connected nodes of \(v_{s}\) in \(G^{\prime}_{v}\) by calling function \(\mathit{FindConnectedSet}\) (Line 4). Similarly, the Dijkstra algorithm is used in function \(\mathit{FindConnectedSet}\) to get the distances from \(v_{s}\) to the other nodes in \(G^{\prime}_{v}\). \(v_{s}\) is connected to another node if the distance between them is limited, otherwise they are unconnected. Note that the connected nodes include \(v_{s}\) itself. Then the connected nodes and the links among them in \(G^{\prime}_{v}\) construct a connected sub-topology including \(v_{s}\) of \(G^{\prime}_{v}\).