# Traffic-Based Heuristics for Regenerator Placement in Translucent Dynamic Optical Networks
## 4 Proposed Regenerator Placement Heuristics
### Time Complexity Analysis of the Proposed Algorithms  
Let us start the analysis of the time complexity of the proposed algorithms by discussing the time complexity required to evaluate both the \(M_{ij}\) and \(M^{\prime}_{ij}\) combinations. As shown in Sections 3.2 and 3.3 for a route \(\pi_{ij}\), \(M_{ij}=\binom{H_{ij}-2}{K_{ij}}\) and \(M^{\prime}_{ij}=\binom{H^{\prime}_{ij}}{K_{ij}^{\prime}}\). Note that, for each route, the value of \(K_{ij}\) is constant and known in advance. In such case, the evaluation of all combinations can be done in polynomial time if \(K_{ij}\) is not close to \((H_{ij}-2)/2\), considering \(M_{ij}\) evaluation, and \((H^{\prime}_{ij}/2)\), considering \(M^{\prime}_{ij}\) evaluation. In a typical mesh optical network, it is expected that the signal may propagate for \(k\) hops before a regeneration is required (i.e., usually \(k\) is larger than 2). Therefore, \(K_{ij}\) is usually smaller than \(H_{ij}/2\), which means that both \(M_{ij}\) and \(M^{\prime}_{ij}\) can be evaluated in polynomial time. Even in the case in which \(K_{ij}\) is close to either \((H_{ij}-2)/2\) or \(H^{\prime}_{ij}/2\), the required time to evaluate both the \(M_{ij}\) and \(M^{\prime}_{ij}\) combinations is low if \(H_{ij}\) is small. All routes with few (i.e., 2 to 5) hops fit in this case regardless of the number of hops the signal may traverse without regeneration. Typically, such cases represent the majority of the routes in a mesh optical network. Moreover, it is expected that the number of hops in a route can be considerably smaller than the number of nodes in the network. This is expected even for long routes. Thus, it could be concluded that the evaluation of the combinations is not prohibitive even for networks with a high number of nodes.  
The most time-consuming step in Algorithm 1 is the \(\Gamma_{n}\) evaluation. It requires, in the worst case, finding the shortest path (SP) between all node pairs (\(\mathcal{O}(N^{3})\)) and, for each SP, the evaluation of either all PRCs (for FLD) or all FRCs (for DLD). By defining \(Z=\max_{i,j}M_{ij}\) (maximum number of PRCs) and \(Z^{\prime}=\max_{i,j}M^{\prime}_{ij}\) (maximum number of FRCs) we may write that the DLD shows \(\mathcal{O}(R\cdot N^{3}\cdot Z^{\prime})\) complexity whereas FLD (and Routing-&-Reach) shows \(\mathcal{O}(N^{3}\cdot Z)\). Note that DLD requires \(\Gamma_{n}\) reevaluation after each 3R inclusion and FLD does not. Given the above time complexities and the fact that \(M^{\prime}_{ij}\leq M_{ij}\), we can say, for the sake of comparison, that DLD requires, in the worst case, \(R\) times more time to solve the RPP problem than FLD.  
```
0: Total amount of regenerators to be deployed R
0: Traffic matrices forecast { \(\omega_{ij}\) } and { \(\gamma_{ij}\) } and the topology \(r\gets R\)  Determine all essential nodes \(e\leftarrow\) Amount of essential nodes \(r\gets r-e\)  Place one regenerator in each essential node while\(r>0\)do for\(n=1\) to \(N\)do  Place a temporary regenerator in node \(n\)  Evaluate \(\Gamma_{n}\) of all nodes  Evaluate \(\Delta(n)\)  Remove the temporary regenerator placed at node \(n\)  Place one reg. in node \(n\) with highest value \(\Delta(n)\) \(r\gets r-1\)
```  
**Algorithm 1** Pseudocode for proposed heuristics