Maximum weight matching with hysteresis in overloaded queues with setups
Maximum weight matching with hysteresis in overloaded queues with setups
复制标题
最大重量与过载队列中滞后的设置相匹配
作者：
Carri W. Chan;Mor Armony;N. Bambos
我们考虑一个系统的并行队列到达服务任务进行缓冲，根据类型。可用的服务资源被动态配置并分配给队列以处理任务。在每个时间点，调度程序都会选择队列中的服务配置，以响应队列积压。从一种服务配置切换到另一种服务配置会导致设置时间，在此期间会发生空闲，并且会丢失服务带宽。这种设置时间是制造和计算机系统中固有的。频繁的切换会严重损害这种系统的服务能力。最大权重匹配（MWM）调度器，这是已知的，以最大限度地提高吞吐量的情况下的设置，可以很容易地变得不稳定的设置，即使在低负载。为了解决这个问题，我们提出了一个新的MWM-H调度器，它利用了控制器引入滞后，并实现最大的吞吐量，即使与设置，而不需要知识的到达率和平均流量负载。在长时间的流量突发期间，队列可能变得过载，并且问题变成如何合理地分配MWM-H下不断增长的积压。它示出，通过适当地选择MWM-H参数，可以控制各个队列之间的积压，以达到所需的平衡。
We consider a system of parallel queues where arriving service tasks are buffered, according to type. Available service resources are dynamically configured and allocated to the queues to process the tasks. At each point in time, a scheduler chooses a service configuration across the queues, in response to queue backlogs. Switching from one service configuration to another incurs a setup time, during which idling occurs and service bandwidth is lost. Such setup times are inherent in manufacturing and computer systems. Frequent switchings can significantly compromise the service capacity of such systems. A maximum weight matching (MWM) scheduler, which is known to maximize throughput in the absence of setups, can easily become unstable with setups, even under low load. To remedy this problem, we propose a new MWM-H scheduler which utilizes a controller introduced hysteresis and achieves maximum throughput even with setups, without requiring knowledge of arrival rates and average traffic loads. During prolonged traffic bursts, the queues may become overloaded and the issue becomes how to reasonably distribute the growing backlog under MWM-H. It is shown that by appropriately selecting the MWM-H parameters, one can control the backlog among the individual queues in order to achieve a desired balance.