Learning in Strategic Queuing Systems with Small Buffers
作者: Ariana Abel, Yoav Kolumbus, Jeronimo Martin Duque, Cristian Palma Foster, Eva Tardos
分类: cs.GT, cs.AI, cs.MA
发布日期: 2025-02-13 (更新: 2025-07-19)
💡 一句话要点
在具有小缓冲区的策略性排队系统中实现学习，提升系统稳定性
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 策略性排队系统 学习算法 小缓冲区 系统稳定性 网络路由 博弈论 性能优化
📋 核心要点
- 现有研究假设服务器无缓冲区，导致模型不切实际，需要时间戳和优先级来保证系统稳定。
- 本研究为每个服务器增加小缓冲区，并取消时间戳和优先级要求，使模型更贴近实际。
- 理论分析和仿真表明，少量增加服务器容量即可保证系统稳定，即使服务器随机选择数据包。
📝 摘要（中文）
本文研究了具有轮次间传递效应的博弈中的学习结果：当前轮次的结果会影响未来的博弈。一个重要的例子是网络中的路由器，它们使用简单的学习算法来找到将数据包传递到其所需目的地的最佳方式。这种简单、短视和分布式的决策过程使得大型排队系统易于操作，但与此同时，该系统需要的容量比集中协调所有流量所需的容量更大。Gaitonde和Tardos（EC 2020和JACM 2023）开始了对此类系统的研究，将其建模为一个无限重复的博弈，其中路由器竞争服务器，并且系统维护一个状态（每个队列中保存的数据包数量），该状态由先前轮次的结果产生。然而，他们的模型假设服务器根本没有缓冲区，因此路由器必须重新发送所有未成功服务的数据包，这使得他们的系统模型不切实际。他们表明，在他们的模型中，即使相对于集中协调情况下所需的服务器容量大幅增加，确保系统稳定也需要使用时间戳和较旧数据包的优先级。本文考虑了一个具有两个重要变化，这使得模型更现实并允许更高的流量速率的系统：首先，我们为每个服务器添加一个非常小的缓冲区，允许服务器保存单个数据包以便稍后服务（如果它未能立即服务它），其次，我们不要求时间戳或较旧数据包的优先级。通过理论分析和仿真，我们表明，当队列正在学习时，与集中协调所需的服务器容量相比，服务器容量的少量常数因子增加足以保持系统稳定，即使服务器在同时到达的数据包中随机选择。
🔬 方法详解
问题定义：现有研究在策略性排队系统中，假设服务器没有缓冲区，导致模型与实际情况不符。为了保证系统稳定，需要引入时间戳和优先级机制，增加了系统的复杂性。因此，需要一个更现实的模型，能够在更高的流量速率下保持系统稳定，并且不需要额外的复杂机制。
核心思路：本研究的核心思路是在每个服务器上引入一个小的缓冲区，允许服务器暂时存储未能立即处理的数据包。通过这个小缓冲区，可以避免数据包的丢失，从而提高系统的稳定性和吞吐量。同时，取消了对时间戳和优先级的依赖，简化了系统的设计。
技术框架：该研究构建了一个策略性排队系统模型，其中路由器竞争服务器资源。每个服务器都有一个小的缓冲区，可以存储一个数据包。路由器根据学习算法选择服务器，目标是最小化数据包的延迟。系统通过仿真和理论分析来评估系统的性能，包括系统的稳定性和吞吐量。
关键创新：本研究的关键创新在于引入了小缓冲区，并取消了对时间戳和优先级的依赖。与现有模型相比，该模型更现实，并且能够在更高的流量速率下保持系统稳定。此外，该研究还证明了，即使服务器随机选择数据包，系统仍然可以保持稳定，这进一步简化了系统的设计。
关键设计：研究的关键设计包括缓冲区的大小、路由器的学习算法以及服务器的选择策略。缓冲区的大小被设置为可以存储一个数据包。路由器的学习算法采用了一种基于梯度的算法，目标是最小化数据包的延迟。服务器的选择策略可以是随机选择，也可以是基于某种优先级规则的选择。
🖼️ 关键图片
📊 实验亮点
研究表明，与集中协调所需的服务器容量相比，只需少量（常数因子）增加服务器容量，即可在队列学习时保持系统稳定。即使服务器在同时到达的数据包中随机选择，系统依然稳定，这表明该方法具有很强的鲁棒性。仿真结果验证了理论分析的正确性，并展示了该方法在实际应用中的潜力。
🎯 应用场景
该研究成果可应用于实际的网络路由系统设计，特别是在资源受限的环境中。通过在路由器中引入小缓冲区，可以提高网络的稳定性和吞吐量，同时降低系统的复杂性。该研究对于优化数据中心网络、无线网络和物联网等具有重要意义，有助于提升网络服务质量和用户体验。
📄 摘要（原文）
We consider learning outcomes in games with carryover effects between rounds: when outcomes in the present round affect the game in the future. An important example of such systems is routers in networking, as they use simple learning algorithms to find the best way to deliver packets to their desired destination. This simple, myopic, and distributed decision process makes large queuing systems easy to operate, but at the same time, the system needs more capacity than would be required if all traffic were centrally coordinated. Gaitonde and Tardos (EC 2020 and JACM 2023) initiated the study of such systems, modeling them as an infinitely repeated game in which routers compete for servers and the system maintains a state (the number of packets held at each queue) that results from outcomes of previous rounds. However, their model assumes that servers have no buffers at all, so routers have to resend all packets that were not served successfully, which makes their system model unrealistic. They show that in their model, even with hugely increased server capacity relative to what is needed in the centrally coordinated case, ensuring that the system is stable requires the use of timestamps and priority for older packets. We consider a system with two important changes, which make the model more realistic and allow for much higher traffic rates: first, we add a very small buffer to each server, allowing the server to hold on to a single packet to be served later (if it fails to serve it immediately), and second, we do not require timestamps or priority to older packets. Using theoretical analysis and simulations, we show that when queues are learning, a small constant-factor increase in server capacity, compared to what would be needed if centrally coordinating, suffices to keep the system stable, even if servers select randomly among packets arriving simultaneously.