# Two Optimization Algorithms for Name-Resolution Server Placement in Information-Centric Networking
## 4 Proposed Algorithms
### IIT-UP Algorithm
All algorithms were run with the same experiment environment and input topology. We recorded several indicators for analysis, including the costs, execution time, number of HMs, and average latency. The performances we analyzed were as follows. #### 5.1.1 Deployment Costs

We assumed that the costs of each server were the same and calculated the total costs of servers that were placed to satisfy the transmission latency constraints under different network scales using each algorithm. The simulation results are shown in Figure 5. It can be seen that the two IIT algorithms performed better than the LHP algorithm and the RA algorithm in finding cost-efficient solutions. The performance of the MDSM algorithm was in the middle. We analyzed the data from the experiment. The cost of the solution obtained by IIT-DOWN was about 59.6% of that obtained by the LHP algorithm, and about 67.9% of that obtained by MDSM. For the IIT-UP algorithm, the ratios of the same comparison were 56.8% and 64.8%, respectively. We can draw the conclusion that the costs of deployment can be effectively reduced by passing information between layers to coordinate server placement and reusing servers. In addition, the relationship between costs and network size was shown to be linear for all algorithms. #### 5.1.2 HM Count

We also analyzed the number of HMs in each layer, as shown in Figure 6. We figured out that IIT algorithms can reduce the number of HMs at each level. Although the IIT-UP algorithm gives the best results in terms of cost, we found that the IIT-DOWN algorithm outputs a lower HM count in the higher-level layers, because it gives priority to dealing with the higher-level layer. In the situation where servers deployed at the higher-level layer use more resources, such as bandwidth, storage, and computation, IIT-DOWN becomes the best choice. We mentioned above that the HM choice problem is similar to the MDS problem in graph theory, [PERSON] et al. proved that in the BA scale-free model, the size of the MDS is \(\theta(n)\)[57], where n is the number of nodes in the network. Our simulation results also confirmed this conclusion. We can use this conclusion to estimate the number of name-resolution servers we have to deploy in a target network if the network is in line with the BA scale-free model. Figure 5: Deployment cost comparison for each algorithm with different network sizes. #### 5.1.3 Execution Time

With an increment in the network size, the network becomes more and more complex. The time to solve the problem will become increasingly more difficult to accept. When minimizing the costs of server deployment is considered the optimization goal, we must consider the operation efficiency of the algorithm. As shown in Figure 7, we compared the execution time of each algorithm on different network scales. First, we figured out that the execution times of these algorithms increased sharply with an increment in the network size. Then we found that IIT algorithms output better results in less time compared with the LHP algorithm. The MDSM algorithm removes neighbor nodes to reduce the complexity and accelerate problem resolving. Still, we can see that the running times between it and IIT-DOWN have little difference. Among these algorithms, IIT-UP has the best operation efficiency, which means it can handle more extensive networks within a reasonable solving time. #### 5.1.4 Average Latency

In multilayer overlay networks, it is enough for us to satisfy the requirement that the data transmission time does not exceed the upper bound of latency. We also analyzed the average latency at each level after the HEA partition using these algorithms. Figure 8c shows that at the bottom layer with the upper bound latency of 10 ms, LHP algorithms result in a lower average latency, and the algorithms proposed by us are not as good. However, it is unfair to only compare the average latency because the

Figure 6: HM count at each layer. In each layer, inter-layer information transfer (IIT) algorithms perform better than other algorithms.