Packet Multiplexers with Adversarial Regulated Traac


We consider a nite-buuer packet multiplexer to which traac arrives from several independent sources. The traac from each of the sources is regulated, i.e., the amount of traac that can enter the multiplexer is constrained by known regulator constraints. The regulator constraints depend on the source and are more general than those resulting from cascaded leaky buckets. We assume that the traac is adversarial to the extent permitted by the regulators. For loss-less multiplexing, we show that if the original multiplexer is lossless it is possible to allocate bandwidth and buuer to the sources so that the resulting segregated systems are lossless. For lossy multiplexing, we use our results for lossless multiplexing to estimate the loss probability of the multiplexer. Our estimate involves transforming the original system into two independent resource systems, and using adversarial sources for the two independent resources to obtain a bound on the loss probabilities for the transformed system. We show that the adversarial sources are not extremal on-oo sources, even when the regulator consists of a peak rate controller in series with a leaky bucket. We explicitly characterize the form of the adversarial source for the transformed problem. We also provide numerical results for the case of the simple regulator.


0 Figures and Tables

    Download Full PDF Version (Non-Commercial Use)