# An Initial Load-Based Green Software Defined Network +
## 5 Heuristic Green Routing Algorithm
The algorithm is named as \(GreenRoutingOneVd\). The complexity of this algorithm is the same as Algorithm 2. **Case (4): Neither \(v_{s}\) nor \(v_{d}\) belongs to the virtual topology**  
The processing of this case is described in Algorithm 3. In such a situation, \(G^{\prime}_{v}\) may be empty. If it is, calculate a path in \(G^{\prime}\) directly by calling function \(LeastEnergyPath\) (Line 3). Then end the algorithm. Note that in function \(LeastEnergyPath\), the Dijkstra algorithm is used similarly, but the link weights are set to be the energy consumptions of the links. If it is not, finding the optimal path begins with \(v_{s}\). Firstly, the vertical path \(path_{s}\) between \(v_{s}\) and \(G_{v}^{\prime}\) is calculated (Line 6). Denote \(path_{s}\) as \(\{v_{s}...v_{1}\}\), then calculate the connected set of \(v_{1}\) in \(G_{v}^{\prime}\) (Line 7). \(path_{s}\) and \(VCSet_{n}\) construct a connected sub-topology \(G_{v_{s}}\) which includes \(v_{s}\) (Line 8). Now the case is as same as the case 2, so call the Algorithm 2 in the next step (Line 9); and the optimal path \(path_{v_{s}}\) will be obtained. Doing the same procedure begins with \(v_{d}\), which means calculating vertical paths between \(G_{v}^{\prime}\) and \(v_{d}\) first, then doing the series of steps gets the optimal path \(path_{v_{d}}\) (Lines 10\(\sim\)13). The topology consisting of the sleepy links is denoted as \(G_{test}^{\prime}\) (Line 14). The least energy consumption path from \(v_{s}\) to \(v_{d}\) in \(G_{test}^{\prime}\) denoted as \(path_{t}\) is calculated in the next step (Line 15). Comparing the three paths acquired above, get one with the least additional energy consumption to \(G_{v}^{\prime}\). If their energy consumptions are the same, then choose the shortest one. If the distance of the paths are the same, choose one randomly (Line 16). In this case, the complexity of function \(LeastEnergyPath\) is equal to [PERSON]'s, and the complexity of other functions is \(O(|V|(|E|+|V|log|V|))\). Thus the complexity of Algorithm 3 is \(O(|V|(|E|+|V|log|V|))\). ```
1:\(G^{\prime}\), \(G_{v}^{\prime}\), \(v_{s}\), \(v_{d}\)
2:\(Path_{best}\);
3:procedureGreenRoutingNone
4:if\(G_{v}^{\prime}\) is empty then
5:\(Path_{best}=LeastEnergyPath(G^{\prime},v_{s},v_{d})\)
6:return
7:else
8:\(path_{s}=DistanceTopology(G^{\prime},v_{s},G_{v}^{\prime})\)
9:\(VCSet_{1}=FindConnectedSet(G_{v}^{\prime},v_{1})\)
10:\(G_{v_{s}}\gets VCSet_{1}\cup paths_{s}\)
11:\(path_{v_{s}}\gets GreenRoutingOneVs(G^{\prime},G_{v_{s}},v_{d})\)
12:\(path_{d}=DistanceTopology(G^{\prime},G_{v}^{\prime},v_{d})\)
13:\(VCSet_{n}=FindConnectedSet(G_{v}^{\prime},v_{n})\)
14:\(G_{v_{d}}\gets VCSet_{n}\cup path_{d}\)
15:\(path_{v_{d}}\gets GreenRoutingOneVd(G^{\prime},G_{v_{d}},v_{s},v_{d})\)
16:\(G_{test}^{\prime}\gets G^{\prime}-G_{v}^{\prime}\)
17:\(path_{t}=LeastEnergyPath(G_{test}^{\prime},v_{s},v_{d})\)
18:\(Path_{best}=\mathit{compare}(path_{v_{s}},path_{v_{d}},path_{t})\)
19:endif
20:endprocedure
```  
**Algorithm 3** GreenRoutingNone  
Based on the complexity analysis of the four cases, the complexity of CWGA is decreased in three cases. The improved algorithm is called as ICWGA.