Analysis of practical backoff protocols for contention resolution with multiple servers
Analysis of practical backoff protocols for contention resolution with multiple servers
复制标题
多服务器争用解决的实用退避协议分析
DOI：
10.1006/jcss.1998.1590
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
P. MacKenzie
中科院分区：
文献类型：
--
作者：
L. A. Goldberg;P. MacKenzie
退避协议可能是用于多接入信道中的竞争解决的最广泛使用的协议。在本文中，我们分析了一组客户端和服务器之间的竞争解决退避协议的随机行为。每个服务器是处理竞争的多址信道，类似于以太网信道。我们使用标准模型，其中每个客户端根据具有指定均值的伯努利分布为给定服务器生成请求。客户？系统的服务器请求速率是所有客户端的最大值？与客户端或服务器j相关联的所有请求速率之和的服务器对（i，j）。（有一个子单元客户端？服务器请求速率是单服务器系统稳定性的必要条件。我们的主要结果是，任何超线性多项式退避协议是稳定的任何多服务器系统与一个子单元客户端？服务器请求率。我们的结果是第一个证明的任何退避协议的竞争解决多个服务器的稳定性。(The多服务器问题并不能简化为单服务器问题，因为每个客户端在任何一步都只能发送一条消息。我们的结果也是第一个证明，任何弱确认为基础的协议是稳定的竞争解决多个服务器和这样的高请求率。我们的结果的两个特殊情况是有趣的。Hastad、Leighton和Rogoff已经证明，对于一个带有子单元客户机的单服务器系统，服务器请求速率任何修改的超线性多项式退避协议是稳定的。这些修改的退避协议类似于标准退避协议，但是需要更多的随机比特来实现。我们的结果中只有一个服务器的特殊情况下，扩展了Hastad，Leighton和Rogoff的结果标准（实用）退避协议。最后，我们的结果适用于光网络中的动态路由。具体来说，我们的结果的一个特殊情况下，超线性多项式退避协议是稳定的动态路由在光网络中。
Backoff protocols are probably the most widely used protocols for contention resolution in multiple access channels. In this paper, we analyze the stochastic behavior of backoff protocols for contention resolution among a set of clients and servers. each server being a multiple access channel that deals with contention like an ethernet channel. We use the standard model in which each client generates requests for a given server according to a Bernoulli distribution with a specified mean. Theclient?server request rateof a system is the maximum over all client?server pairs (i,j) of the sum of all request rates associated with either clientior serverj. (Having a subunit client?server request rate is a necessary condition for stability for single-server systems.) Our main result is that any superlinear polynomial backoff protocol is stable for any multiple-server system with a subunit client?server request rate. Our result is the first proof of stability for any backoff protocol for contention resolution with multiple servers. (The multiple-server problem does not reduce to the single-server problem, because each client can only send a single message at any step.) Our result is also the first proof thatanyweakly acknowledgment based protocol is stable for contention resolution with multiple servers and such high request rates. Two special cases of our result are of interest. Hastad, Leighton, and Rogoff have shown that for a single-server system with a subunit client?server request rate anymodifiedsuperlinear polynomial backoff protocol is stable. These modified backoff protocols are similar to standard backoff protocols but require more random bits to implement. The special case of our result in which there is only one server extends the result of Hastad, Leighton, and Rogoff to standard (practical) backoff protocols. Finally, our result applies to dynamic routing in optical networks. Specifically, a special case of our result demonstrates that superlinear polynomial backoff protocols are stable for dynamic routing in optical networks.