Adversarial Queuing on the Multiple Access Channel

作者：Chlebus Bogdan S^*; Kowalski Dariusz R; Rokicki Mariusz A

来源：ACM Transactions on Algorithms, 2012, 8(1): 5.

DOI：10.1145/2071379.2071384

• Adversarial queuing
• deterministic protocol
• distributed broadcasting
• multiple access channel
• packet latency
• stability

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 are O(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, where n is the number of stations, and show that fair latency is impossible to achieve for injection rates that are omega(1/log n). For For channels without collision detection, we present a full-sensing protocol of fair latency for injection rates that are at most 1/clg(2)n, for some c %26gt; 0. We show that there exists an acknowledgment-based protocol that has fair latency for injection rates that are at most 1/enlg(2)n, for some c %26gt; 0, and develop an explicit acknowledgment-based protocol of fair latency for injection rates that are at most 1/27n(2)ln n. Regarding impossibility to achieve just stability by restricted 7 In protocols, we prove that no acknowledgment-based protocol can be stable for injection rates larger than 3/1+lgn.

• 出版日期2012-1