A. NOTATION

S: source node;

D: destination node;

B: bandwidth demand;

N: number of slots between two nodes;

C: number of core;

V: set of nodes

$e_{u,v,n}$ : the n^th edges connecting u and v;

$E=\left\{e_{u,v,n}\right\}$ : set of edges;

$G=\left(V,E,W\right)$ : label multigraph composed of edges E and a set of edge weight, W.

$m=1,\cdots ,M$ : modulation formats;

B_m: bandwidth demand in slots in the basis of the modulation format chosen;

$R\left(s,d,b\right)$ : request from the node s to the node d with bandwidth demand b;

$\delta \left(G,r\left(s,d,b_m\right)\right)$ : shortest path between s and d in G that satisfies the request for $b_m$ slots:

$\omega \left(e_{u,v,n}\right)$ : Weight of the edge $e_{u,v,n}$ ;

${\tilde{G}}_{n,b_m}=\left(\tilde{V},\tilde{E},\tilde{W}\right)$ : the n^th labeled graph such that $\tilde{E}$ is the set of edges connecting $\left\{\tilde{u},\tilde{v}\right\}\in \tilde{V}$ and $\tilde{W}$ is the set of costs associated with $\tilde{E}$ . The edges in $\tilde{E}$ correspond to the mapping of $b_m$ edges in G, starting at the n^th edges;

$\sigma =\left|\left\{{\tilde{G}}_{n,b_m}\right\}\right|=C\times \left(N-b_m+1\right)$ : Number of graphs extracted from the multigraph;

$\tau \left(G,C,b_m\right)=\left\{{\tilde{G}}_{n,b_m}\right\}$ : Function which produces all σ graphs from G;

$P_n$ : chain of ${\tilde{G}}_{n,b_m}$ such that the source node s is the least ordered node and d is the greatest ordered node;

$W\left(P_n\right)$ : Weight of the path $P_n$ , which is the sum of the weights of all the edges in the chain;

$W_{P_{s,d}}$ = weight of the shortest path between s and d;

$B_n$ : Chain of ${\tilde{G}}_{n,b_m}$ such that the number of vertices is equal to the number of edges, and every vertex has degree 2;

$B_{u,v}$ : set of all p-cycles containing the vertices u and v in G;

$\theta \left({\tilde{G}}_{n,b_m},P_n,r\left(s,d,b\right)\right)$ : Shortest cycle between s and d in ${\tilde{G}}_{n,b_m}$ , which $P_{B_{s,d}}$ ate link disjoint to $P_n$ ;

$\upsilon \left(P_n,B_{u,v},r\left(s,d,b\right)\right)$ : P-cycle in $B_{u,v}$ which $P_{B_{u,v}}$ are link disjoint to $P_n$ and satisfies the request of bandwidth b;

$W\left(B_n\right)$ : The weight of the p-cycle $B_n$ , which is the sum of the weights of all the edges in the chain;

$W_{B_{s,d}}$ = weight of the p-cycle which protects the path between s and d;

B. POPETA

The POPETA algorithm is introduced in Algorithm 1. Line 1 transforms the multigraph into $C\times \left(N-b_m+1\right)$ graphs. Line 2 finds the shortest path for all ${\tilde{G}}_{n,b_m}$ graphs and chooses the cheapest one. If all of the shortest path weights are ∞, it signifies that there is no path for demand b that observes the contiguity requirement.

Line 3 chooses the shortest path with the lowest weight value out of all the shortest paths. There is no path in the network that satisfies the request for $b_m$ slots under the contiguity constraint if the weight of all the shortest paths is ∞ (Line 4). The request is blocked if no path is available (Line 5).

Otherwise, a p-cycle is required to preserve this light-path (Line 7). When a p-cycle shields both an active and a new request, a light-path (Line 8) is constructed, with the weight of the associated edges in the multi-graph G altered to ∞ (Line 9).

If no such p-cycle exists, one is constructed to protect the newly established light-path (Line 12). The shortest possible cycle between source and destination nodes is considered while creating the p-cycle, however if no such p-cycle can be found, the request is blocked (Line 15).

Aside from that, the major path and the p-cycle (Line 17) have been established. Lines 18 and 19 alter the weight of relevant edges in the multi-graph G to ∞, indicating that the slots have been assigned to the newly formed light-path. The PERFECTA algorithm’s complexity is examined next. $M\times O\left(\Vert E\Vert +\Vert V\Vert \right)$ , where M is the number of modulation levels that can be employed, is the complexity of changing the original multi-graph into alp graphs. The Dijkstras algorithm is run at least $M\times C\times \left(N-b\right)$ times for the major path. The Suurballe algorithm is run at least $M\times C\times \left(N-b\right)$ times to generate p-cycles. Given that both Dijkstra’s and Suurballe’s algorithms have a complexity of $O\left(\Vert E\Vert +\Vert V\Vert \log \Vert V\Vert \right)$ , Because C, N, M, and b are constants, the PERFECTA algorithm’s complexity is $O\left(\Vert E\Vert +\Vert V\Vert \log \Vert V\Vert \right)$ .