Abstract
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(⌈lg n⌈+1), where n is the number of stations, and show that fair latency is impossible to achieve for injection rates that are ω(1/log n). For channels without collision detection, we present a full-sensing protocol of fair latency for injection rates that are at most 1/clg 2n, for some c > 0. We show that there exists an acknowledgment-based protocol that has fair latency for injection rates that are at most 1/cnlg 2 n , for some c > 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 protocols, we prove that no acknowledgment-based protocol can be stable for injection rates larger than 3/1+lg n.
Original language | English (US) |
---|---|
Article number | 5 |
Journal | ACM Transactions on Algorithms |
Volume | 8 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2012 |
Externally published | Yes |
Keywords
- Adversarial queuing
- Deterministic protocol
- Distributed broadcasting
- Multiple access channel
- Packet latency
- Stability
ASJC Scopus subject areas
- Mathematics (miscellaneous)