Exact Mixed-Integer Conic Liftings for Queueing-Based Content Delivery Network Design

Víctor Blanco † and Miguel Martínez-Antón ‡ † Institute of Mathematics (IMAG), Universidad de Granada ‡ Institute of Mathematics (IMUS), Universidad de Sevilla [email protected] , [email protected] · 2026

Read Exact Mixed-Integer Conic Liftings for Queueing-Based Content Delivery Network Design by Víctor Blanco † and Miguel Martínez-Antón ‡ † Institute of Mathematics (IMAG), Universidad de Granada ‡ Institute of Mathematics (IMUS), Universidad de Sevilla [email protected] , [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-30491.txt.

Introduction

Víctor Blanco and Miguel Martínez-Antón study content delivery network design problems with queueing-based response times. Their models include congestion effects, producing nonlinear expressions involving ratios, reciprocal terms, and multi-class interactions. To address these challenges, they develop a framework based on mixed-integer conic liftings enabling exact reformulations of such expressions. The framework starts with one server, where the optimal solution connects with the classical Fermat-Weber problem, then extended to the multi-server case.

Catalog record

CREATORVíctor Blanco † and Miguel Martínez-Antón ‡ † Institute of Mathematics (IMAG), Universidad de Granada ‡ Institute of Mathematics (IMUS), Universidad de Sevilla [email protected] , [email protected]
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121537
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.30491

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Exact Mixed-Integer Conic Liftings for Queueing-Based Content Delivery Network Design Víctor Blanco † and Miguel Martínez-Antón ‡ † Institute of Mathematics (IMAG), Universidad de Granada ‡ Institute of Mathematics (IMUS), Universidad de Sevilla [email protected] , [email protected] Abstract . We study a class of content delivery network design problems in which service performance is explicitly modeled through queueing-based response times. In contrast to standard formulations relying on distance-based approximations, the resulting models incorporate congestion effects and give rise to nonlinear expressions involving ratios of affine mappings, reciprocal terms, and interactions across multiple traffic classes. To address these challenges, we develop a systematic framework based on mixed-integer conic liftings that enables exact reformulations of such expressions within a tractable optimization paradigm. The proposed approach combines McCormick-type envelopes and second-order cone representations to derive mixed-integer conic programming formulations that jointly capture geometric design decisions and stochastic service dynamics within the same system. The framework is first introduced in a single-server setting, where the optimal solution exhibits a connection with the classical Fermat–Weber problem, and is then extended to the multi-server case, leading to a general formulation that simultaneously optimizes server locations, capacity allocation, and routing decisions. Computational experiments on a realistic case study illustrate the impact of congestion-aware modeling on network design and demonstrate the effectiveness of the proposed formulations when solved using modern conic optimization solvers. 1. Introduction Mixed-integer conic optimization provides a unified framework for modeling problems that combine discrete decisions with nonlinear convex structures ( Ben Tal and Nemirovski 2001 ; Boyd and Vandenberghe 2004 ) . A central aspect of this framework is the construction of extended formulations in which nonlinear expressions are lifted into higher-dimensional spaces and represented through conic constraints ( Conforti et al. 2010 ; Vielma 2015 ) . Such representations are particularly effective when the underlying models involve ratios, reciprocal terms, or interactions between multiple variables, since many of these functions admit exact or tight conic representations through standard cones. More generally, a broad class of convex optimization problems can be expressed, or arbitrarily well approximated, using combinations of a small family of canonical cones, often referred to as the Big Five , namely the nonnegative orthant, second-order cone, positive semidefinite cone, power cone, and exponential cone ( Bertsimas et al. 2026 ) . This expressive power explains the broad applicability of conic optimization as a modeling paradigm. Nevertheless, a fundamental challenge in this area is to identify classes of optimization problems whose intrinsic nonlinear structure can be systematically represented through exact conic liftings while preserving low representational complexity. Although many standard convex sets and functions admit well-known conic formulations, more intricate nonlinear expressions arising in stochastic systems, congestion models, and service-network optimization are often handled through ad hoc reformulations or piecewise-linear approximations ( Pham et al. 2025 ; Atamtürk and Narayanan 2010 ) . In particular, queueing-based optimization models naturally generate rational expressions involving reciprocal load factors, ratios of affine mappings, and nonlinear interactions between traffic and service variables, whose exact representability is far from immediate. Developing optimization frameworks in which conic lifting is not merely a computational device, but rather the natural representational language of the underlying stochastic structure, remains an important direction of research in mixed-integer conic optimization. This paper develops such a framework in the context of the design of content delivery networks (CDNs for short), which constitutes a fundamental component of modern Internet infrastructure ( Pallis and Vakali 2006 ; Verma 2003 ) . CDNs aim to deliver digital content, such as web pages, video streams, software updates, and cloud services, to geographically distributed users with low latency and high reliability. To achieve this objective, content is replicated across a set of distributed surrogate servers, referred to as edge servers , which are deployed closer to users than the original repositories, known as origin servers . When a user issues a request, it is routed to an appropriate edge server capable of serving the content locally whenever possible, while cache misses require retrieving the content from the origin layer. This architecture significantly reduces end-to-end latency, alleviates network congestion, and improves scalability ( Liu et al. 2012 ) . As a consequence, CDNs play a central role in modern digital services, including large-scale video streaming platforms ( Ghabashneh and Rao 2020 ; Krishnappa et al. 2015 ) , cloud computing infrastructures ( Ling et al. 2013 ) , software distribution systems ( Nygren et al. 2010 ) , and emerging edge computing environments supporting latency-sensitive applications such as online gaming, augmented reality, and Internet-of-Things services ( Aral et al. 2019 ; George and George 2021 ) . From an optimization perspective, the efficient design and operation of CDNs raises several challenging problems involving the placement of edge servers, the allocation of user demand, the routing of requests across the network, the management of content replication, and the provisioning of service capacity. These decisions strongly affect both system performance and operational costs. A substantial body of research has examined these questions from both optimization and performance viewpoints ( Verma 2003 ; Buyya et al. 2008 ; Pallis and Vakali 2006 ; Nygren et al. 2010 ) . Early works addressed pricing and economic aspects of CDN deployment ( Hosanagar et al. 2008 ) , while subsequent contributions formulated server placement and mirror selection problems using classical facility location and k -center models ( Hillmann et al. 2016 ) . Further developments have considered the joint optimization of caching and routing decisions ( Poularakis et al. 2014 ; Guo et al. 2019 ; Ghabashneh and Rao 2020 ) , as well as network-level optimization problems such as transit routing and traffic engineering ( Liu et al. 2012 ; Ahmed et al. 2018 ) . More recently, cloud-oriented CDN architectures have been studied, where resource allocation and replica placement are integrated within virtualized environments ( Papagianni et al. 2013 ; Ling et al. 2013 ) . Comprehensive surveys of these approaches can be found in Salahuddin et al. 2018 ; Pathan and Buyya 2007 . Despite this extensive literature, most existing optimization models and methods rely on simplified representations of service performance, typically approximating response times through deterministic proxies based on geographic distance or clustering strategies ( Verma 2003 ; Pallis and Vakali 2006 ) . However, these approximations neglect congestion effects arising from the stochastic dynamics of request processing at edge servers. In practice, user-perceived latency depends not only on propagation delays, but also on queueing effects induced by heterogeneous service requirements and fluctuating traffic conditions, as highlighted in optimization-based overlay CDN models that explicitly account for dynamic traffic and resource allocation under real-time constraints ( Caviglione and Cervellera 2011 ) . Incorporating these effects naturally leads to nonlinear expressions derived from queueing theory involving ratios of affine mappings, reciprocal terms, and interactions between multiple flow components, as observed in standard queueing models ( Gross et al. 2008 ; Kleinrock 1975 ) . These queueing-induced expressions define convex performance measures over the stability region of the system, but do not admit direct formulations compatible with standard mixed-integer optimization methodologies. Rather than approximating or linearizing such nonlinearities, in this paper we show that they possess an intrinsic structure particularly amenable to exact conic lifting.

Read the complete text