针对量子纠缠交换的“在d个选择中服务最长队列”策略
Service-the-Longest-Queue Among d Choices Policy for Quantum Entanglement Switching
摘要 Abstract
量子纠缠生成开关(EGS)是一种量子网络中心节点,通过共享有限数量的枢纽资源为一组连接的节点提供纠缠态。当纠缠请求到达时,它们会加入到与请求来源节点对应的专用队列中。我们提出了一种负载均衡策略,其中EGS通过随机从所有可用请求队列中采样d个队列并选择其中最长的一个进行服务。该策略是之前为经典系统(如数据中心)引入的“d个选择的力量”范式的实例。然而,与之前的模型不同,我们将队列放置在节点上而不是直接放置在EGS上,这具有一些实际优势。此外,我们在负载均衡方案中引入了一个可调的退避机制,以减少网络中的经典通信负载。为了研究该策略,我们考虑了一个均匀的星型网络拓扑结构,其中EGS位于中心,并将其建模为一个请求按照泊松过程到达且服务时间呈指数分布的排队系统。我们通过对描述平均场极限动态的一组微分方程进行推导并给出相应唯一平衡状态的表达式,对该系统的渐近行为进行了分析。与经典系统随机负载均衡的类似结果一致,我们观察到当采样过程中d的数量从1增加到2时,请求的平均处理时间显著减少,但选择数量更多时收益递减。我们还观察到,我们的平均场模型可以很好地用于研究甚至中等规模的系统。
An Entanglement Generation Switch (EGS) is a quantum network hub that provides entangled states to a set of connected nodes by enabling them to share a limited number of hub resources. As entanglement requests arrive, they join dedicated queues corresponding to the nodes from which they originate. We propose a load-balancing policy wherein the EGS queries nodes for entanglement requests by randomly sampling d of all available request queues and choosing the longest of these to service. This policy is an instance of the well-known power-of-d-choices paradigm previously introduced for classical systems such as data-centers. In contrast to previous models, however, we place queues at nodes instead of directly at the EGS, which offers some practical advantages. Additionally, we incorporate a tunable back-off mechanism into our load-balancing scheme to reduce the classical communication load in the network. To study the policy, we consider a homogeneous star network topology that has the EGS at its center, and model it as a queueing system with requests that arrive according to a Poisson process and whose service times are exponentially distributed. We provide an asymptotic analysis of the system by deriving a set of differential equations that describe the dynamics of the mean-field limit and provide expressions for the corresponding unique equilibrium state. Consistent with analogous results from randomized load-balancing for classical systems, we observe a significant decrease in the average request processing time when the number of choices d increases from one to two during the sampling process, with diminishing returns for a higher number of choices. We also observe that our mean-field model provides a good approximation to study even moderately-sized systems.