# Traffic-Based Heuristics for Regenerator Placement in Translucent Dynamic Optical Networks
## 2 Related Works  
In this work, we propose two new approaches to perform sparse regenerator placement in translucent optical networks under ad-hoc/dynamic traffic. Thus, we deal with the problem defined in Section 1 as RPP-3. Note, however, that there are few works in the literature that fully realize the RPP-3 goals by using the network blocking probability information to guide the regenerator placement itself. In this section, we review some algorithms proposed in the literature seeking the solution to RPP-3. Two main types of algorithms are reviewed, the algorithms that fully accomplish the RPP-3 goals (RPP-3d) as well as those that do not use the blocking probability information directly during the placement decision but, instead, apply heuristics whose ultimate goal is to reduce the network blocking probability (RPP-3h). [PERSON] and [PERSON] [1] propose four different heuristic algorithms to solve the RPP. Each heuristic assigns a score to each network node and the \(N\) best-scored nodes receive a predetermined number of \(X\) regenerators (\(N\)-\(X\) policy). The proposed NDF and CNF algorithms give the score for each network node based, respectively, on the node degree and on how centered in the network the node is. These are topological-based heuristics because only information from the network topology is used during the placement decision. The work also proposed the TLP and SQP traffic-based heuristics. They are traffic-based heuristics because a set of dynamic call requests are simulated to evaluate each network node score. The TLP scores the network node \(i\) based on the number of times that a call request is routed through the node \(i\) and the SQP does the same but considering the transparent reach in terms of the number of hops. Some other traffic-based placement proposals use a similar idea and a network simulation engine to simulate a set of dynamic call requests. The statistics of node usage during the simulations are used to score the network nodes towards a regenerator placement decision. Applying this idea, [PERSON] et al. [4] proposed the MU and MSU heuristics and [PERSON] et al. [29] proposed the SAUR heuristic. The MU scores each node \(i\) based on the number of times that the node \(i\) is assigned as a regeneration point during the simulation, whereas the MSU algorithm scores each node \(i\) based on the maximum number of regenerators simultaneously assigned in the node \(i\) during the simulation. In both cases, the total number of regenerators to be deployed in the network are distributed among the network nodes proportionally to each node score. The SAUR heuristic further improves the MSU idea by taking into account not only the number of simultaneously used regenerators in a node but also the statistics regarding the usage. As mentioned in Section 1, [PERSON] [2] proposes a statistical framework to tackle RPP-3h in translucent optical networks under ad-hoc traffic. The mentioned \(pdf_{3R}(i)\) function is evaluated accordingly to the selected heuristics. He proposes to evaluate the \(pdf_{3R}(i)\) considering only topological information such as node degrees and shortest paths between each pair of nodes. Thus, only the topological-based placement is considered in the work. The \(pdf_{3R}(i)\) is evaluated using four different strategies: (1) equal value for all nodes (UN); (2) proportionally to the node degree (ND); (3) proportionally to the number of shortest paths that pass through the node \(i\) (RO); (4) the same as RO but also considering the transmission reach (RR). Moreover, applying topological-based placement, [PERSON] and [PERSON] [12] propose the DA heuristic. This heuristic also assigns a score to each network node. The score of the node \(i\) is evaluated by the quotient between the sum of the lengths of the links connected to the node \(i\) by the total length of all links in the network. Then, the regenerators are distributed proportionally to each node score. The algorithms reviewed so far apply the RPP-3h approach. On the other hand, [PERSON] et al.