Network Utility Maximization Under Maximum Delay Constraints and Throughput Requirements
Network Utility Maximization Under Maximum Delay Constraints and Throughput Requirements
复制标题
DOI：
10.1109/tnet.2020.3007842
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Qingyu Liu;Haibo Zeng;Minghua Chen
中科院分区：
文献类型：
--
作者：
Qingyu Liu;Haibo Zeng;Minghua Chen
我们考虑了在多跳网络上最大化聚合用户效用的多路径路由问题，该问题受链路容量约束、最大端到端延迟约束和用户吞吐量要求的限制。用户效用是实现吞吐量或经历最大延迟的凹函数。该问题对于支持实时多媒体流量非常重要，并且由于需要同时考虑最大延迟约束和吞吐量要求，因此具有独特的挑战性。在本文中，我们首先证明了(i)构造严格满足所有约束的可行解，或（ii）在放宽最大延迟约束或吞吐量要求后获得最优解是np完全的。然后，我们开发了一个名为PASS的多项式时间近似算法。PASS的设计利用了对非凸最大延迟感知问题和凸平均延迟感知问题之间的新理解，这可以是独立的兴趣，并为解决最大延迟感知网络优化问题提供了新的途径。我们证明了PASS总是得到近似解（即，具有理论性能保证），代价是同时违反最大延迟约束和吞吐量要求，最高可达常数比率。我们还开发了PASS的两种变体，称为PASS- m和PASS- t，以以违反最大延迟约束或吞吐量要求为代价生成近似解，其代价高达与问题相关的比率。我们在支持视频会议流量的Amazon EC2数据中心上进行了大量模拟，以评估我们的解决方案。与现有算法和可想象的基线相比，我们的解决方案通过满足吞吐量要求而将最大延迟限制放宽到实际视频会议应用可接受的程度，从而获得了高达100%的效用改进。
We consider a multi-path routing problem of maximizing the aggregate user utility over a multi-hop network, subject to link capacity constraints, maximum end-to-end delay constraints, and user throughput requirements. A user’s utility is a concave function of the achieved throughput or the experienced maximum delay. The problem is important for supporting real-time multimedia traffic and is uniquely challenging due to the need of simultaneously considering maximum delay constraints and throughput requirements. In this paper, we first show that it is NP-complete either (i) to construct a feasible solution strictly meeting all constraints, or (ii) to obtain an optimal solution after relaxing either the maximum delay constraints or the throughput requirements. We then develop a polynomial-time approximation algorithm named PASS. The design of PASS leverages a novel understanding between non-convex maximum-delay-aware problems and their convex average-delay-aware counterparts, which can be of independent interest and suggests a new avenue for solving maximum-delay-aware network optimization problems. We prove that PASS always obtains approximate solutions (i.e., with theoretical performance guarantees), at the cost of violating both the maximum delay constraints and the throughput requirements by up to constant ratios. We also develop two variants of PASS, named PASS-M and PASS-T, to generate approximate solutions at the cost of violating either the maximum delay constraints or the throughput requirements by up to problem-dependent ratios. We evaluate our solutions using extensive simulations on Amazon EC2 datacenters supporting video-conferencing traffic. Compared to the existing algorithms and a conceivable baseline, our solutions obtain up to 100% improvement of utilities, by meeting the throughput requirements but relaxing the maximum delay constraints to the extent acceptable for practical video conferencing applications.