# Two Optimization Algorithms for Name-Resolution Server Placement in Information-Centric Networking
## 4 Proposed Algorithms
### IIT-UP Algorithm
IIT-DOWN and multilayer minimum dominating set (MDSM) algorithms need less name-resolution servers in higher-level layers. (**a**) The layer with the latency upper bound at 50 ms. Note that the results of IIT-DOWN and MDSM overlap. (**b**) The layer with the latency upper bound at 25 ms. (**c**) The layer with the latency upper bound at 10 ms.

Figure 7: Execution time comparison of each algorithm with different network sizes. IIT algorithms require less time to solve a problem, which means that they can solve problems in more extensive networks. The latency-aware hierarchical elastic area partitioning (LHP) algorithms may not complete the calculation in a reasonable time. (**a**) Comparison of all five algorithms. (**b**) Comparisons of MDSM, IIT-DOWN, and IIT-UP are presented in detail. LHP algorithm uses more servers than IIT algorithms. Interestingly, when it comes to higher-level layers (Figure 8a,b), IIT algorithms result in a lower average latency, although we know that the LHP still uses more servers. This may be caused by the user allocations strategy and the accuracy of the HEA partition. The IIT-UP algorithm has the shortest average latency in higher-level layers, which means it has the most accurate partition and the highest server utilization. Also, we found that the average latency does not increase with an increment in the network size, mainly because the number of HMs grows linearly with the size of the network, and the balanced partition maintains the stability of the average latency. #### 5.1.5 Cost Parameter

In Section 5.1.1, name-resolution servers at different latency levels are assumed to have the same deployment cost weight. However, in reality, servers that cover a broader range often require higher configurations, such as central processing unit (CPU), bandwidth, and storage, which also incurs higher costs. Assuming that the ratio of deployment costs for servers at adjacent latency layers is \(k\), a further study about the impact of \(k\) on deployment costs was undertaken. Figure 9 shows the change in the total cost relative to the \(k\) value under the three algorithms when the network size is 1000. When the difference in server costs at different levels is small, IIT-UP gives the solution with the lowest cost, since it can minimize the total number of servers. However, as \(k\) increases, its cost will gradually exceed that of IIT-DOWN and MDSM. The exceedance points were 1.45 and 5.9 in this experiment, respectively. In addition, we noticed that the IIT-DOWN algorithm always has a cost advantage over the MDSM approach. Figure 8: Average name-resolution latency at each layer. LHP provides a shorter average latency at the lowest level because it uses more name-resolution nodes. However, in higher-level layers, IIT algorithms perform better. (**a**) The layer with the latency upper bound at 50 ms. Note that the results of IIT-DOWN and MDSM overlap. (**b**) The layer with the latency upper bound at 25 ms. (**c**) The layer with the latency upper bound at 10 ms.

Figure 9: Impact of \(k\) on deployment costs. ### Coverage in K Placement Algorithms

The study above was undertaken to minimize the server cost under the constraint of the deterministic delay structure. The count of servers cannot be forecast before solving the problem. When the budget is limited, the server placement problem turns into the K placement problem. We also set up experiments to find proper methods that can be used in this situation. We compared our proposed IIT-UP algorithm with several algorithms, as follows:

* Density-based clustering (DBC) [38]: DBC first selects one node which has the largest degree among all the nodes in the network and places one server on this node. Subsequently, all users that have an access delay within this server's coverage and have not been allocated are allocated to this server.