Adversarial Queuing on the Multiple Access Channel
Adversarial Queuing on the Multiple Access Channel
复制标题
多路访问信道上的对抗性排队
DOI：
10.1145/2071379.2071384
复制
发表时间：
2012
影响因子：
1.3
通讯作者：
Chlebus B
中科院分区：
文献类型：
--
作者：
Chlebus B
我们研究确定性广播时，数据包被连续注入多个接入信道。服务质量被认为是在对抗排队的框架。对手由注入速率和突发性决定，后者表示一轮中可以同时注入的数据包数量。我们只考虑小于1的注入率。当队列中的数据包数在各轮都有界时，协议是稳定的;当队列中的数据包等待时间为O（突发/速率）时，协议是公平延迟的。对于具有碰撞检测的信道，我们给出了一个在注入速率不超过1 2（n = 1 logn + 1）时具有公平延迟的全感知协议，其中n是站点数，并证明了在注入速率为ω（1 logn）时不可能实现公平延迟.对于没有冲突检测的通道，我们提出了一种公平延迟的全感知协议，注入速率最多为1clg 2n，soc> 0。我们发现，存在一个基于双稳态的协议，具有公平的延迟，注入率是最多1cnlg 2n，soc> 0，并开发一个显式的基于双稳态的协议，公平的延迟，注入率是最多1 27 n2 lnn。关于不可能实现的限制协议的稳定性，我们证明了没有基于约束的协议可以是稳定的注入率大于31 + lgn。
We study deterministic broadcasting on multiple access channels when packets are injected continuously. The quality of service is considered in the framework of adversarial queuing. An adversary is determined by injection rate and burstiness, the latter denoting the number of packets that can be injected simultaneously in a round. We consider only injection rates that are less than 1. A protocol is stable when the numbers of packets in queues stay bounded at all rounds, and it is of fair latency when waiting times of packets in queues areO(burstiness/rate). For channels with collision detection, we give a full-sensing protocol of fair latency for injection rates that are at most 1 2(⌈lgn⌉ + 1), wherenis the number of stations, and show that fair latency is impossible to achieve for injection rates that areω(1 logn). For channels without collision detection, we present a full-sensing protocol of fair latency for injection rates that are at most 1clg2n, for somec> 0. We show that there exists an acknowledgment-based protocol that has fair latency for injection rates that are at most 1cnlg2n, for somec> 0, and develop an explicit acknowledgment-based protocol of fair latency for injection rates that are at most 1 27n2lnn. Regarding impossibility to achieve just stability by restricted protocols, we prove that no acknowledgment-based protocol can be stable for injection rates larger than 3 1 + lgn.
登录
查看更多内容
无线网络中的唤醒问题
影响因子：
1.3
作者：
Bogdan S. Chlebus;L. Gąsieniec;D. Kowalski;T. Radzik
通讯作者：
T. Radzik
DOI：
10.1137/s0097539703435522
发表时间：
2004
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Carme Àlvarez;M. Blesa;M. Serna
通讯作者：
M. Serna
多路访问信道的动态共享
DOI：
10.4230/lipics.stacs.2010.2446
发表时间：
2010
期刊：
ArXiv
影响因子：
--
作者：
Marcin Bienkowski;M. Klonowski;M. Korzeniowski;D. Kowalski
通讯作者：
D. Kowalski
最后一句话
DOI：
--
发表时间：
--
期刊：
The American journal of dental science
影响因子：
--
作者：
E. K. Wedelstaedt
通讯作者：
E. K. Wedelstaedt
DOI：
10.1007/978-1-4612-0759-7
发表时间：
1996
期刊：
2019 International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)
影响因子：
--
作者：
P. Ribenboim
通讯作者：
P. Ribenboim