# Two Optimization Algorithms for Name-Resolution Server Placement in Information-Centric Networking
## 4 Proposed Algorithms
### IIT-UP Algorithm
This procedure continues until all K servers are placed in the network, or all users are allocated;
* K-Mediods [45]: this approach is a variant of K-means, which is commonly used to cluster a data set into K groups automatically. In this approach, K initial cluster centers are selected and then iteratively refined. In every iteration, a new cluster center is selected to minimize the within-cluster sum of the access delay. This procedure continues until no cluster center changes, and the last iteration's cluster centers are placed servers;
* Top-K: this approach places the K servers on k nodes with the largest degree. Users are allocated to their closest servers;
* Random-K: this approach randomly selects K nodes and places servers on them. Users are allocated to their closest servers. Since the approaches above mainly focus on single-layer networks, we extended them accordingly to adapt them to the situation of multilayer overlay networks with nested constraints. The IIT-UP algorithm was set as a benchmark. That is to say, in every layer, the parameter K was chosen from the results output by IIT-UP. The experiment also involved 15 turns, and the same topologies were guaranteed for each approach in each turn. The determined-access-latency coverage rate of users was used as an evaluation of the performance of each approach. As shown in Figure 10, the IIT-UP algorithms always guarantee the full coverage rate, because the strict latency constraint is applied in the procedure of server selection and user allocation. However, uncovered users exist in other approaches. The primary trend that we figured out is that as the level goes from high to low, the coverage rate becomes lower. Among these approaches, DBC outperforms other K placement approaches and can maintain more than 90 percent of the coverage in each layer. The K-Mediods approach performs at a slightly lower level. An impressive result in our experiment was that in level 1 (Figure 10c) and level 2 (Figure 10b), the random-K approach even outperformed the Top-K approach. This means that if we simply choose top-k degree nodes for server placement, this may result in more unsatisfactory results. Figure 10: The coverage rate of K placement algorithms. (**a**) The layer with the latency upper bound at 50 ms. (**b**) The layer with the latency upper bound at 25 ms. (**c**) The layer with the latency upper bound at 10 ms.

### Real-World Dataset

We also utilized the dataset for Shanghai Telecom's base stations [58; 59] for algorithm comparison. Shanghai is a typical densely populated city, and its base station distribution is also dense. This dataset contains location information for more than 3000 base stations. In our experiment, we randomly chose 1000 base stations and used their location information to calculate the Euclidean distances between each pair of base stations. Then, we calculated the propagation latency between two base stations by considering an approximate propagation time of 5 \(\upmu\)s/km [60]. Since the spans of distances among Shanghai base stations are small, we chose T = {0.01 ms, 0.05 ms, 0.2 ms} as the corresponding narrowing. Table 3 shows the results of each algorithm, including the execution time, name-resolution server at each layer, and total cost. The results show that the performance of each algorithm is the same as that of the simulation network shown in Section 5.1. It can be seen that the IIT-UP algorithm can minimize the total costs. Fewer name-resolution servers were chosen in level 2 by IIT-DOWN and MDSM. However, the LHP algorithm did not perform well in terms of either the execution time or the total costs. ## 6 Conclusions

In this paper, we first studied the placement problem of the name-resolution server in multilayer overlay networks and formulated it as an integer linear program problem with the objective of minimizing the deployment costs. Then, two algorithms based on the heuristic ideas of inter-layer information transfer and server reuse were developed. The first was called IIT-DOWN.