Academic
Publications
Maximum throughput of multiple access channels in adversarial environments

Maximum throughput of multiple access channels in adversarial environments,10.1007/s00446-009-0086-4,Distributed Computing,Bogdan S. Chlebus,Dariusz R

Maximum throughput of multiple access channels in adversarial environments   (Citations: 8)
BibTex | RIS | RefWorks Download
We consider deterministic distributed broadcasting on multiple access channels in the frame- work of adversarial queuing. Packets are injected dynamically by an adversary that is con- strained by the injection rate and the number of packets that may be injected simultaneously; the latter we call burstiness. A protocol is stable when the number of packets in queues at the stations stays bounded. The maximum injection rate that a protocol can handle in a stable manner is called the throughput of the protocol. We consider adversaries of injection rate 1, that is, of one packet per round, to address the question if the maximum throughput 1 can be achieved, and if so then with what quality of service. We develop a protocol that achieves throughput 1 for any number of stations against leaky-bucket adversaries. The protocol has O(n 2 + burstiness) packets queued simultaneously at any time, where n is the number of sta- tions; this upper bound is proved to be best possible. A protocol is called fair when each packet is eventually broadcast. We show that no protocol can be both stable and fair for a system of at least two stations against leaky-bucket adversaries. We study in detail small systems of exactly two and three stations against window adversaries to exhibit dierences in quality of broadcast among classes of protocols. A protocol is said to have fair latency if the waiting time of packets isO(burstiness). For two stations, we show that fair latency can be achieved by a full sensing protocol, while there is no stable acknowledgment based protocol. For three stations, we show that fair latency can be achieved by a general protocol, while no full sensing protocol can be stable. Finally, we show that protocols that either are fair or do not have the queue sizes aect the order of transmissions cannot be stable in systems of at least four stations against window adversaries.
Journal: Distributed Computing - DC , vol. 22, no. 2, pp. 93-116, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...They gave full-sensing protocols achieving fair latency for rates of O(1/polylog n) and showed that no protocol could be strongly stable for rates of ω(1/logn) .T he maximum throughput defined to mean the maximum rate for which stability is achievable was studied by Chlebus, et al. [9]...
    • ...We use the most general leaky-bucket adversarial model (see [3], [9])...
    • ...We categorize deterministic protocols according to the terminology used in [2], [8], [9]...
    • ...Protocol MBTF was introduced in [9] and showed to be stable for injection rate 1...
    • ...The number of pending packets is at most 2(n 2 +b) ,a s shown in [9]...

    Lakshmi Anantharamuet al. Deterministic Broadcast on Multiple Access Channels

    • ...[1] for the maximum tolerable average message rate in a dynamic broadcast setting)...

    Stephan Holzeret al. Brief announcement: self-monitoring in dynamic wireless networks

    • ...Packets are injected into stations by a window-type adversary that is restricted by an injection rate and a window w. Adversarial queuing for multiple access channels, as introduced in [11,12], concerned adversaries determined by global injection rates for all the stations...
    • ...The weakest expectation about the time spent by packets in the system is that it is not infinite, so that every packet is eventually successfully transmitted: this is called fairness in [11,12]...
    • ...We use the terminology introduced in [11,12]: protocols that do not use control bits are called full sensing while those that use control bits are called adaptive...
    • ...The underlying motivation for this work was that individual injection rates are more realistic in moderate time spans and hopefully the limitations on quality of service with throughput 1 discovered in [12] would not hold when the rates are individual...
    • ...Indeed, bounded packet latency turns out to be achievable with individual injection rates when the aggregate rate is 1. This is in contrast with global injection rates for which achieving finite waiting times is impossible for throughput 1, as was shown in [12]...
    • ...The most restricted acknowledgment based protocols cannot achieve throughput 1, which strengthens the result for global injection rates [12]...
    • ...In a subsequent work, Chlebus, et al.[12] investigated the quality of service for the maximum throughput, that is, the maximum rate for which stability is achievable...
    • ...We refer to the adversaries defined only by global restrictions on injection rates as the model of global injection rate ,t hese adversaries were used in [11,12]...
    • ...type (� si� 1≤i≤n ,w )a nd ofaggregate type (ρ, w). The notion of aggregate type is similar to that of global type as considered in [11,12]...
    • ...Natural subclasses of deterministic protocols for adversarial settings in multiple access channel were defined in [11,12], we use the same classification...

    Lakshmi Anantharamuet al. Adversarial Multiple Access Channel with Individual Injection Rates

    • ...Maximum throughput defined as the maximum rate for which stability is achievable was investigated by Chlebus et al. [13]...
    • ...Protocols. We adapt deterministic distributed protocols, as introduced in [12,13]...
    • ...We consider two classes of protocols: full sensing protocols and adaptive ones, these definitions were introduced for deterministic protocols in [12,13]...
    • ...We recall the definition of an adversary without jamming, as used in [2,12,13]...
    • ... rate λ satisfies λ< 1. Stability is not achievable by a jamming adversary with injection rate ρ and the jamming rate λ satisfying ρ + λ> 1: this is equivalent to ρ> 1 − λ, so when the adversary is jamming with the maximum capacity, then the bandwidth remaining for transmissions is 1 − λ, while the injection rate is more than 1 − λ. It is possible to achieve stability in the case ρ + λ = 1, similarly as it was shown for ρ = 1 in ...
    • ...The corresponding upper bound on the number of packets waiting in queues is a natural performance metric, see [12,13]...
    • ...Protocol Move-Big-To-Front, abbreviated MBTF, was proposed by Chlebus et al. [13]...

    Lakshmi Anantharamuet al. Medium Access Control for Adversarial Channels with Jamming

Sort by: