论文标题
传递队列
Pass-and-Swap Queues
论文作者
论文摘要
Berezner，Kriel和Krzesinski于1995年提出的独立订单独立（OI）队列扩大了多级队列的家族，这些家族通过允许复杂的类依赖类的服务速率来扩展具有产品形式的固定分布。本文通过引入通行证（P＆S）队列，这是OI队列的扩展，从而进一步拓宽了这个家庭，在该服务完成后，完成服务的客户不一定是离开系统的客户。更确切地说，我们在客户类上使用无向图来补充OI队列模型，我们称之为交换图，因此，如果这些类的客户可以互相交换，则两个类之间的优势。当客户完成服务时，它会在队列的其余部分中跨越客户，直到找到可以与该类别的客户交换的客户，该客户是图表中的邻居。反过来，从其位置弹出的客户将与下一个客户的位置交换，依此类推。重复这一点，直到客户再也找不到另一个客户。该客户是离开队列的客户。在证明P＆S队列具有产品形式的固定分布之后，我们为（开放网络的）P＆S排队提供了必要且充分的稳定性条件，该条件也适用于OI队列。然后，我们研究P＆S队列的封闭网络的不可约性特性，并得出相应的产品形式固定分布。最后，我们证明了P＆S队列的封闭网络可以应用于描述在作业具有分配约束的机器簇中新的和现有的负载分布和调度协议的动态。
Order-independent (OI) queues, introduced by Berezner, Kriel, and Krzesinski in 1995, expanded the family of multi-class queues that are known to have a product-form stationary distribution by allowing for intricate class-dependent service rates. This paper further broadens this family by introducing pass-and-swap (P&S) queues, an extension of OI queues where, upon a service completion, the customer that completes service is not necessarily the one that leaves the system. More precisely, we supplement the OI queue model with an undirected graph on the customer classes, which we call a swapping graph, such that there is an edge between two classes if customers of these classes can be swapped with one another. When a customer completes service, it passes over customers in the remainder of the queue until it finds a customer it can swap positions with, that is, a customer whose class is a neighbor in the graph. In its turn, the customer that is ejected from its position takes the position of the next customer it can be swapped with, and so on. This is repeated until a customer can no longer find another customer to be swapped with; this customer is the one that leaves the queue. After proving that P&S queues have a product-form stationary distribution, we derive a necessary and sufficient stability condition for (open networks of) P&S queues that also applies to OI queues. We then study irreducibility properties of closed networks of P&S queues and derive the corresponding product-form stationary distribution. Lastly, we demonstrate that closed networks of P&S queues can be applied to describe the dynamics of new and existing load-distribution and scheduling protocols in clusters of machines in which jobs have assignment constraints.
