Contention resolution without collision detection
Contention resolution without collision detection
复制标题
无需冲突检测的争用解决方案
DOI：
10.1145/3357713.3384305
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pettie, Seth
中科院分区：
文献类型：
--
作者：
Bender, Michael A.;Kopelowitz, Tsvi;Kuszmaul, William;Pettie, Seth
本文主要研究不支持冲突检测的共享通信信道上的竞争解决问题。共享通信信道是多址信道，它由一系列同步时隙组成。信道上的播放器可以尝试在任何时隙中广播分组（消息）。如果在该时段内没有其他玩家广播，则该玩家的广播成功。如果两个或多个玩家在同一时间段广播，则广播冲突，两个广播都失败。缺少冲突检测意味着监视频道的播放器不能区分两个或更多个播放器在同一时隙中广播（冲突）和零个播放器广播的情况。在竞争解决问题中，参与者随着时间的推移到达信道，每个参与者都有一个数据包要传输。目标是协调参与者，以便每个参与者能够在合理的时间内成功传输其数据包。然而，玩家只能通过选择广播或不广播来通过共享信道进行通信。一个竞争解决协议是衡量其吞吐量（信道利用率）。以前的工作竞争决议，实现恒定的吞吐量假设，无论是球员可以检测到冲突，或球员的到达模式是由一个无记忆（非对抗性）process.The基本问题本文回答的是冲突检测是奢侈品还是必要的，当目标是实现恒定的吞吐量。我们表明，即使没有冲突检测，可以解决竞争的决议，实现恒定的吞吐量，具有很高的概率。
This paper focuses on the contention resolution problem on a shared communication channel that does not support collision detection. A shared communication channel is a multiple access channel, which consists of a sequence of synchronized time slots. Players on the channel may attempt to broadcast a packet (message) in any time slot. A player's broadcast succeeds if no other player broadcasts during that slot. If two or more players broadcast in the same time slot, then the broadcasts collide and both broadcasts fail. The lack of collision detection means that a player monitoring the channel cannot differentiate between the case of two or more players broadcasting in the same slot (a collision) and zero players broadcasting. In the contention-resolution problem, players arrive on the channel over time, and each player has one packet to transmit. The goal is to coordinate the players so that each player is able to successfully transmit its packet within reasonable time. However, the players can only communicate via the shared channel by choosing to either broadcast or not. A contention-resolution protocol is measured in terms of its throughput (channel utilization). Previous work on contention resolution that achieved constant throughput assumed that either players could detect collisions, or the players' arrival pattern is generated by a memoryless (non-adversarial) process.The foundational question answered by this paper is whether collision detection is a luxury or necessity when the objective is to achieve constant throughput. We show that even without collision detection, one can solve contention resolution, achieving constant throughput, with high probability.
登录
查看更多内容
影响因子：
6.7
作者：
通讯作者：
--
无线网络中的唤醒问题
影响因子：
1.3
作者：
Bogdan S. Chlebus;L. Gąsieniec;D. Kowalski;T. Radzik
通讯作者：
T. Radzik
多路访问信道上的对抗性排队
影响因子：
1.3
作者：
Chlebus B
通讯作者：
Chlebus B
DOI：
10.4230/lipics.disc.2018.28
发表时间：
2018
期刊：
2015 IEEE International Symposium on Information Theory (ISIT)
影响因子：
--
作者：
P. Garncarek;T. Jurdzinski;D. Kowalski
通讯作者：
D. Kowalski
DOI：
10.1145/23005.23006
发表时间：
1987-04
期刊：
J. ACM
影响因子：
--
作者：
A. Greenberg;P. Flajolet;R. Ladner
通讯作者：
A. Greenberg;P. Flajolet;R. Ladner