# Traffic-Based Heuristics for Regenerator Placement in Translucent Dynamic Optical Networks
Eventually, a demand that requires a route longer than the MOR (i.e., it requires regeneration) may be routed throughout nodes with no free regenerators, which causes blocking of the demand. The three mentioned RPP versions are computationally complex and classified either as NP-complete or NP-hard [4; 9; 10; 11]. Thus, heuristics [3; 12] or meta-heuristics [4; 11; 13] are often used to solve RPP. Note, however, that the minimization target of RPP-1 and RPP-2 has a linear characteristic (either sum of the number of regenerators deployed or sum of nodes with regeneration capability) and, for this reason, there are several approaches in the literature using (M)ILP to solve either RPP-1 [10; 14] or RPP-2 optimally [9; 15; 16; 17; 18; 19; 20]. Typically, however, (M)ILP methods solve the problem for networks with a low number of nodes [9; 10; 15; 16; 17]. In RPP-3, on the other hand, the minimization target is the network blocking probability. Clearly, the network blocking probability has a non-linear dependence on the number of regenerators deployed in each network node which prevents the use of (M)ILP methods to solve the RPP-3 problem optimally. To optimally solve the RPP-3,BP modeling is required. Very few BP modelings for translucent networks are available in the literature and they assume several simplifications to reach a very complex (and computationally intensive) set of formulas [21]. This fact prevents using an optimization method over this set of equations to solve RPP-3 in an acceptable time optimally. In this paper, we are interested in addressing networks under ad-hoc traffic. Clearly, RPP-1 can only solve the design of networks under static traffic. RPP-2, on the other hand, can be used to resolve networks with ad-hoc traffic. However, it cannot do the optimization to reduce BP, nor with the objective of reducing the network implementation cost because it only defines which nodes in the network must have regenerators without answering how many regenerators should actually be installed on each node. Thus, the only approach capable of handling the optimization of both performance (BP) and capex (cost) for networks under ad-hoc traffic is the RPP-3. In this paper, we focus on solving RPP-3, hereafter named as RPP, under ad-hoc traffic. For this reason, we used, in this paper, the heuristic approach to solve the RPP. The Poison/Markovian process using exponential distribution for connection request inter-arrival and holding times are largely assumed in the literature to model the ad-hoc/dynamic traffic in optical circuit-switched networks [1; 2; 11; 12; 13; 16; 21; 22; 23; 24]. Nevertheless, some classical works [25] bring to attention the self-similar characteristics of data networks traffic, pointing out the inadequacy of the Poison/Markovian process to characterize such network traffic. However, based on observation of actual data traffic, more recent papers have shown that the Poison/Markovian process can closely represent the traffic of current high-speed backbone networks data traffic, mainly because the burstiness of the inter-arrival times decreases significantly in current backbone networks [26; 27; 28]. There are two main approaches to solving RPP-3 under ad-hoc traffic heuristically: (1) using either topological or traffic characteristics of the network (such as the degrees of the nodes, number of routes that pass through a node, etc.) to infer the amount of regenerators that should be placed in each node to reduce the BP or (2) using the BP returned by a network simulator and applying this information as a guide during the regenerator placement. The disadvantage of the strategies that use the first approach [1; 2; 4; 12; 22; 29] is that they do not consider BP information during the RPP solution. Strategies that use the second approach [11; 13; 30], on the other hand, take into account BP information during the RPP decision. However, they require a network simulator to return those BPs, which may lead to large complexity and excessive time to reach the RPP solution.