Universal-Stability Results and Performance Bounds for Greedy Contention-Resolution Protocols

We consider packet routing when packets are injected continuously into Aa network. We develop an adversarial theory of queuing aimed at addressing some Aof the restrictions inherent Ain probabilistic analysis and queuing Atheory based on time-invariant stochastic generation. We Aexamine the Astability of queuing networks and policies when the arrival process is Aadversarial, Aand provide some preliminary results in this direction. AOur approach sheds light on various Aqueuing policies in simple Anetworks, and paves the way for a systematic study of queuing with Afew or no probabilistic assumptions.