# A Reliable Routing Algorithm Based on Path Satisfaction in the Energy Internet
## 4 Solution Approach
### Path Satisfaction-Based Service-Aware Routing Algorithm (PSSRA) for the Energy Internet  
According to the aforementioned system model and service model, a heuristic algorithm, which is to maximize path satisfaction, is presented. To ensure the reliability of service transmission, there are at least two paths to be calculated for routing switching in the case of network failures. That is, once one path has failed, services could be quickly delivered to the other paths. The pseudocode for PSSRA is shown in Algorithm 1. ```
1:Input: Service set \(\mathbb{R}\) and network topology, flag;
2:Output: Primary and alternate routing path with the maximal satisfaction path;
3: Stage 1: Calculate the maximal satisfaction path for each service
4:for service \(r\in\mathbb{R}\)
5: Search \(k\) link-disjoint path pairs by minimizing the end-to-end service latency;
6: Calculate the adjacency and availability of spectrum resources on each link according to (7);
7: Compute path satisfaction for the \(k\) path pairs according to (17), and save the values in the set of \(\mathbb{P}\). 8: Stage 2: Service path deployment
9:if\(\mathbb{P}\
eq\mathcal{O}\) then
10:if\(r(l)==3\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!Generally, Algorithm 1 is composed of two stages. The indicator of the maximal satisfaction path for each service is computed at stage 1, and reliable routing paths for services with different priorities are then allocated at stage 2. Specifically, \(k\) link-disjoint path pairs are calculated by minimizing the service delay in terms of service classes in lines 2-3. Then, one must compute the service path satisfaction and save them in line 4. In lines 5-7, if the services do not need to be allocated a dual-route path, the path with the maximal satisfaction value is chosen as the primary path. For other services, choose the path of the link-disjoint path pairs with the maximal satisfaction as the primary path, and choose the other one as the backup path. The details of Algorithm 1 are described as follows: To make it more clear and definite, the flowchart and sequence diagram for the PSSRA are shown in Figures 3 and 4. Generally speaking, services are classified into different priorities in terms of their significance to the EI when they are delivered to the control center. Then, the link-disjoint routing paths for them are searched. The path satisfaction will be computed according to the characteristics of links and nodes. The path with the maximal satisfaction is selected as the working path, and the other link-disjoint path is the backup path. ### Complexity Analysis of the PSSRA

The PSSRA is based on the \(k\)-shortest paths (KSP) algorithm. The algorithm iteratively searches link-disjoint routing paths with maximal path satisfaction for each service. Hence, it needs \(|\mathbb{R}|\) iterations at most to satisfy all service requirements. Since the time complexity of KSP is \(O(K\times|V|_{2}log_{2}|V|)\), the time complexity of the PSSRA is \(O(\mathcal{R}\times K\times|V|_{2}log_{2}|V|)\)

Figure 4: Sequence diagram of the PSSRA. Figure 3: The schematic diagram of the PSSRA. We evaluated the performance of the PSSRA in comparison with the existing routing algorithms on various network topologies as shown in Figure 2, Figure 5, and Figure 6, respectively. ### Simulation Setting

All of the simulations were conducted using MATLAB R2023a on a PC with a 2.4-GHz Intel Core i7 CPU with 12 GB of RAM. The results were obtained over multiple experiments to achieve a 95% confidence interval. The services initialization refers to the literature [36]. The OPGW availability was 99.8%, and the link availability of ADSS, the ordinary fiber, was set as 99.3% and 99%, respectively. The \(k\) was set to 5. The comparison schemes were the Shortest Distance Path Algorithm (SPA) and the Shortest Cycle Routing Algorithm (SCRA) in [39], respectively. (a) The 7-node Network

We assume that node D denotes a 500 kV substation, and that the other nodes represent 220 kV substations. The average node degree of the network is 3.14.