Learning-NUM: Network Utility Maximization With Unknown Utility Functions and Queueing Delay
Learning-NUM: Network Utility Maximization With Unknown Utility Functions and Queueing Delay
复制标题
DOI：
10.1145/3466772.3467031
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Xinzhe Fu;E. Modiano
中科院分区：
文献类型：
--
作者：
Xinzhe Fu;E. Modiano
网络效用最大化（NUM）研究在网络资源约束条件下，为网络用户分配业务速率以最大化用户的总效用的问题。在本文中，我们提出了一个新的NUM框架，学习NUM，其中用户的效用函数是未知的先验和业务速率的效用函数值只能观察到后，相应的业务被交付到目的地，这意味着效用反馈经验的延迟。我们的目标是设计一个政策，逐步学习的效用函数，使速率分配和网络调度/路由决策，以最大限度地提高总效用在有限的时间范围$T$。除了未知的效用函数和随机约束，我们的问题的一个核心挑战在于观察的延迟，这可能是无界的，并取决于政策的决定。我们首先证明了最佳动态策略所得到的期望总效用是静态优化问题的解的上界。在不考虑反馈时延的情况下，我们设计了一种基于梯度估计和最大权调度思想的算法。为了处理反馈延迟，我们将算法嵌入到并行实例范例中，以形成实现$\tilde {O}（T^{3/4}）$ -遗憾的策略，即，最佳动态策略与我们的策略所获得的期望效用之间的差异在$\tilde {O}（T^{3/4}）$中。此外，我们扩展我们的政策，以处理的情况下，效用的意见是嘈杂的，并表明它实现$\tilde {O}（T^{7/8}）$ -后悔。最后，为了证明Learning-NUM框架的实用性，我们将其应用于三个应用场景，包括数据库查询，作业调度和视频流。我们进一步进行模拟的作业调度应用程序，以评估我们的政策的实证表现。
Network Utility Maximization (NUM) studies the problems of allocating traffic rates to network users in order to maximize the users’ total utility subject to network resource constraints. In this paper, we propose a new NUM framework, Learning-NUM, where the users’ utility functions are unknown apriori and the utility function values of the traffic rates can be observed only after the corresponding traffic is delivered to the destination, which means that the utility feedback experiences queueing delay. The goal is to design a policy that gradually learns the utility functions and makes rate allocation and network scheduling/routing decisions so as to maximize the total utility obtained over a finite time horizon $T$ . In addition to unknown utility functions and stochastic constraints, a central challenge of our problem lies in the queueing delay of the observations, which may be unbounded and depends on the decisions of the policy. We first show that the expected total utility obtained by the best dynamic policy is upper bounded by the solution to a static optimization problem. Without the presence of feedback delay, we design an algorithm based on the ideas of gradient estimation and Max-Weight scheduling. To handle the feedback delay, we embed the algorithm in a parallel-instance paradigm to form a policy that achieves $\tilde {O}(T^{3/4})$ -regret, i.e., the difference between the expected utility obtained by the best dynamic policy and our policy is in $\tilde {O}(T^{3/4})$ . Furthermore, we extend our policy to deal with the case where the utility observations are noisy and show that it achieves $\tilde {O}(T^{7/8})$ -regret. Finally, to demonstrate the practical applicability of the Learning-NUM framework, we apply it to three application scenarios including database query, job scheduling and video streaming. We further conduct simulations on the job scheduling application to evaluate the empirical performance of our policy.