# An Initial Load-Based Green Software Defined Network +
## 5 Heuristic Green Routing Algorithm
Similarly, another connected sub-topology including \(v_{d}\) can be revealed by finding the connected nodes of \(v_{d}\) (Line 5). Now we have gotten two connected sub-topologies of \(G^{\prime}_{v}\). One includes \(v_{s}\), and the other includes \(v_{d}\). Since there is no path between \(v_{s}\) and \(v_{d}\) in \(G^{\prime}_{v}\), the two sub-topologies are not connected. According to the vertical path defined at the beginning of this section, the vertical path \(\mathit{path}_{m}\) of two sub-topologies in \(G^{\prime}\) can be found (Line 6). Note that, in order to find the least energy consumption path, the energy consumption \(p_{ij}\) is used as the weight of link \(\{i,j\}\) instead of distance in function \(\mathit{DistanceTopology}\). Through \(\mathit{path}_{m}\), the two sub-topologies can be connected. Denote \(\mathit{path}_{m}\) as \(\{v_{1},v_{2},...,v_{n}\}\), so the path from \(v_{s}\) to \(v_{d}\) consists of  
Figure 2: Vertical distance example. (**a**) Graph \(G\). (**b**) The part with solid lines: \(G_{b}\). three parts: \(v_{s}\) to \(v_{1}\), \(v_{1}\) to \(v_{n}\), and \(v_{n}\) to \(v_{d}\). The path from \(v_{s}\) to \(v_{1}\) denoted as \(path_{f}\) can be calculated by calling the function \(ShortestPath\) (Line 7), likewise the path from \(v_{n}\) to \(v_{d}\) denoted as \(path_{l}\) (Line 8). In the three parts of the \(Path_{best}\), only the middle part \(path_{m}\) represents additional energy consumption. Looking at the time complexity of Algorithm 1, the complexity of the Dijkstra algorithm is known as \(O(|E|+|V|log|V|)\)[19]; then the complexity of function \(ShortestPath\) is equal to the Dijkstra's. The maximum complexity of function \(FindConnectedSet\) and DistanceTopology are \(O(|V|(|E|+|V|log|V|))\) and \(O(|V|^{2}(|E|+|V|log|V|))\), respectively. Thus, the complexity of Algorithm 1 is \(O(|V|^{2}(|E|+|V|log|V|))\). The functions \(ShortestPath\), \(FindConnectedSet\) and \(DistanceTopology\) are used for the same objective in the other cases; they are omitted to eliminate repetition in the following. ```
0:\(G^{\prime}\), \(G^{\prime}_{v}\), \(v_{s}\), \(v_{d}\)
0:\(Path_{best}\);
1:procedureGreenRoutingBoth
2:\(Path_{best}=ShortestPath(G^{\prime}_{v},v_{s},v_{d})\)
3:if\(Path_{best}\) is empty then
4:\(VCSet_{s}=FindConnectedSet(G^{\prime}_{v},v_{s})\)
5:\(VCSet_{d}=FindConnectedSet(G^{\prime}_{v},v_{d})\)
6:\(path_{m}=DistanceTopology(G^{\prime},VCSet_{s},VCSet_{d})\)
7:\(path_{f}\gets ShortestPath(G^{\prime}_{v},v_{s},v_{1})\)
8:\(path_{i}\gets ShortestPath(G^{\prime}_{v},v_{n},v_{d})\)
9:\(Path_{best}\leftarrow\{path_{f}path_{m}path_{l}\}\)
10:endif
11:endprocedure
```  
**Algorithm 1** GreenRoutingBoth  
**Case (2): \(v_{s}\) belongs to the virtual topology, and \(v_{d}\) not**  
As described in Algorithm 2, in this case, we find the connected set of \(v_{s}\) in \(G^{\prime}_{v}\) first (Line 2), then calculate the vertical path \(path_{l}\) in the next step (Line 3). Denote \(path_{l}\) as \(\{v_{1},v_{2},...,v_{d}\}\). The path from \(v_{s}\) to \(v_{1}\) denoted as \(path_{f}\) in \(G^{\prime}_{v}\) can be calculated by \(ShortestPath\) (Line 4). Then the path from \(v_{s}\) to \(v_{d}\) can be acquired through two parts: \(v_{s}\) to \(v_{1}\), and \(v_{1}\) to \(v_{d}\). In Algorithm 2, the complexity of \(DistanceTopology\) in line 3 is \(O(|V|(|E|+|V|log|V|))\). Then the complexity of Algorithm 2 is \(O(|V|(|E|+|V|log|V|))\). ```
0:\(G^{\prime}\), \(G^{\prime}_{v}\), \(v_{s}\), \(v_{d}\)
0:\(Path_{best}\);
1:procedureGreenRoutingOneVs
2:\(VCSet_{s}=FindConnectedSet(G^{\prime}_{v},v_{s})\)
3:\(path_{l}=DistanceTopology(G^{\prime},VCSet_{s},v_{d})\)
4:\(path_{f}\gets ShortestPath(G^{\prime}_{v},v_{s},v_{1})\)
5:\(Path_{best}\leftarrow\{path_{f}path_{l}\}\)
6:endprocedure
```  
**Algorithm 2** GreenRoutingOneVs  
**Case (3): \(v_{s}\) doesn't belong to the virtual topology, and \(v_{d}\) does**  
This case is similar to the case 2. The difference is that the vertical paths are from \(v_{s}\) to the connected set of \(v_{d}\).