Optimal Network Design: Edge Server Placement and Link Capacity Assignment for Delay-Constrained Services

A general communication network has a single Data Center (DC) in its "core", which serves as a gateway to the Internet. For delay-constrained services of the kind needed by online gaming, this model does not suffice because the propagation delay between the subscriber and the DC may be too high. This requires some servers to be located close to the network edge. Thus, the question of the optimal placement of these edge servers arises. To lower the network design cost, it is also essential to ensure good traffic routing, so that aggregate traffic on each link remains as low as possible. This enables lower capacity assignment on each link and thereby minimizes design cost. In this paper, we study a novel joint optimization problem of network design cost minimization. Edge server placement cost and link capacity assignment cost constitute the total cost. The problem formulated is a large Integer Linear Program (ILP). Unlike others, we provide an exact solution in reasonable time. To achieve this, we apply the Column Generation (CG) technique. The results show a 40% improvement in the design cost, when solved through CG, over other heuristics.