Adversarial Queueing Network¶
A discrete routed-packet model that tests whether edge queues stay bounded under constrained adversarial injections and a specified greedy scheduling policy.
Core Idea¶
An adversarial queueing network is a mathematical packet-routing model. Packets arrive on fixed directed paths; they wait for service at each edge they must cross.[1] An adversary chooses arrivals subject to a load limit, and a specified rule chooses which waiting packet crosses an edge when several compete.[1] The question is whether all queues remain bounded under the permitted arrivals and that rule.[1]
The model is a test, not a promise of stability. The expanded 2001 theory distinguishes deterministic adversaries, for which stability means a pathwise bound on every queue, from adaptive stochastic adversaries, for which it uses a bound on expected queue size.[1] The examples below use the deterministic case.
Structural Signature¶
- Directed routes: a graph supplies directed edges, and each packet has a prescribed path through them.[1]
- Constrained arrivals: in the deterministic cases here, the adversary may choose injection times and paths only within a per-edge, time-window load bound.[1]
- Edge queues and service: a packet waits for its next edge, which can serve at most one packet in a time step in this model.[1] This bounds service capacity, not queue storage.
- Specified policy: a greedy rule serves a waiting packet when the edge can; FIFO and longest-in-system (LIS) choose different packets.[1] A non-greedy rule may define a queue trajectory but falls outside the cited greedy-policy results.[1]
- Stability criterion: the claim must name the adversary class, graph, policy and bound. One small simulated run cannot prove the universally quantified claim.[1]
Scope of Application¶
The model belongs to the analysis of store-and-forward packet networks with fixed paths and capacity-limited edges.[1] Its results compare particular topologies, route restrictions, adversary classes and scheduling policies.[1] A theorem for one combination cannot be carried over to a different one without checking its conditions.
Sethuraman and Teo use constrained adversarial packet injections to study communication-network routing and scheduling.[2] They distinguish preassigned, non-adaptive packet paths from adaptive origin-to-destination routing; their adaptive results are context for this model family, not bounds for the fixed-path cases above.[2]
Fluid models provide a conditional proof method in a related adversarial queueing formulation.[3][4] Gamarnik's 1998 conference abstract states the one-way result that stability of the associated fluid model implies stability of the queueing network.[3] The expanded 2000 theorem requires global stability of the associated fluid network's work-conserving solutions and assumes prescribed paths, unit edge service, a per-edge injection bound and a subunit rate.[4] Its network and service conventions must be checked separately from this article's directed-edge cases; the result gives neither a converse nor a general procedure for deciding stability.[4]
Clarity¶
Adversarial does not mean arrivals are unlimited. The deterministic adversary is limited by the amount of traffic whose routes use each edge over a time window.[1] Also distinguish a network stable under every greedy policy from a policy stable across networks; these put the universal quantifier in different places.[1]
Manages Complexity¶
The model reduces a complicated packet history to four questions: What paths may packets use? What edge loads may the adversary inject? Which packet does each busy edge serve? What queue bound must hold? Keeping these separate shows whether a counterexample comes from route and policy interactions even though arrivals remain admissible.[1]
Abstract Reasoning¶
Specify the graph, routes, per-edge service and admissible load. Then name the policy and the stability quantifier. Finally match a proposed result to its exact route, rate and policy conditions. If queues grow without bound under a permitted deterministic adversary, that graph-policy combination fails the deterministic test; a positive theorem proves only what its conditions quantify.[1]
Knowledge Transfer¶
These questions can compare different packet-routing graphs and greedy priorities inside the same formal framework. They do not automatically prove a result for wireless contention, a fluid-model argument under different network conventions, or a stochastic product-form network. Those settings need their own source-backed mapping to packet routes, edge queues, admissibility and service rules.[1][4]
Examples¶
Rate-one directed ring under LIS. Borodin and colleagues construct a directed ring and an admissible deterministic rate-one injection sequence whose backlog grows without bound under LIS.[1] The paper separately establishes its FIFO case.[1] Mapped back: the ring supplies fixed routes, each edge has unit service and a queue, the phased injections meet the specified rate condition, and LIS selects packets; unbounded growth fails stability for that combination.[1]
One-bend mesh. In the paper's row-then-column mesh, packets follow a source row and then a destination column.[1] Corollary 5 gives stability at admissible rate below one under the stated greedy-policy scope.[1] Mapped back: the mesh and one-bend routes set the topology, per-edge admissibility limits arrivals, busy edges serve packets, and the theorem supplies the queue bound.[1] It does not establish the same result for arbitrary routes.
Instantiates / Related Primes¶
This entry presupposes Network and is a kind of Queueing.
The paper's packet model has arrivals, waiting and service at edge queues, with fixed routes on a directed graph.[1] In this catalog it is a strict kind of Queueing system and strictly presupposes Network. These are independent links: an ordinary single queue need not have packet routes, and a network need not have packet queues. Routing is related but concerns choosing or maintaining paths; this model takes paths as inputs.
Relationships to Other Abstractions¶
Current abstraction Adversarial Queueing Network Domain-specific
Parents (2) — outgoing typed relations
-
Adversarial Queueing Network is a kind of Queueing Prime
The routed-packet model is a queueing-system model with constrained injections, edge waiting and specified service rules.
-
Adversarial Queueing Network presupposes Network Prime
Fixed packet routes and per-edge queue loads require an underlying directed connection graph.
Hierarchy paths (3) — routes to 3 parentless roots
- Adversarial Queueing Network → is a kind of Queueing → is a kind of Allocation → presupposes Scarcity → is a decomposition of Constraint
Neighborhood in Abstraction Space¶
Adversarial Queueing Network sits in a sparse region of the domain-specific corpus (72nd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2769 abstractions)
Nearest neighbors
- Induced Path — 0.84
- Network scheduler — 0.84
- Node graph architecture — 0.83
- Network topology — 0.83
- Hadwiger number — 0.83
Computed from structural-signature embeddings · 2026-10-25
Not to Be Confused With¶
- Unlimited hostile traffic: the admissibility constraint is part of the definition.[1]
- A universal verdict that FIFO or LIS is unstable: the cited ring construction is at rate one and under its own route conditions.[1]
- A product-form stationary theorem: the deterministic result here tests bounded queues under adversarial arrivals; it does not assert a stationary distribution.[1]
- A deployed-network measurement: the ring and mesh are mathematical constructions, not operational case studies.[1]
References¶
[1] Allan Borodin, Jon Kleinberg, Prabhakar Raghavan, Madhu Sudan, and David P. Williamson, “Adversarial Queuing Theory,” Journal of the ACM 48, no. 1 (2001): 13–38, §3, Corollary 5, and §6.1 Theorem 6. https://www.cs.cornell.edu/home/kleinber/stoc96-aqt.pdf . Expanded original; the cited results are limited to their stated graph, route, rate, adversary, and greedy-policy conditions. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28
[2] Jay Sethuraman and Chung-Piaw Teo, “Effective Routing and Scheduling in Adversarial Queueing Networks,” author manuscript dated December 2003, revised June 2004, abstract and §1. https://www.columbia.edu/~js1353/pubs/st-adversarial.pdf . The manuscript distinguishes preassigned paths from adaptive routing; its adaptive results are not asserted for the fixed-path examples here. registry ↩a ↩b
[3] David Gamarnik, “Stability of Adversarial Queues via Fluid Models,” Proceedings of the 39th Annual Symposium on Foundations of Computer Science (1998), author/publisher abstract. https://research.ibm.com/publications/stability-of-adversarial-queues-via-fluid-models . The abstract supports the one-way implication, not the detailed conditions of the later theorem. registry ↩a ↩b
[4] David Gamarnik, “Using Fluid Models to Prove Stability of Adversarial Queueing Networks,” IEEE Transactions on Automatic Control 45, no. 4 (2000), §§II–IV, Definition 3 and Theorem 1. https://www.mit.edu/~gamarnik/Papers/using_fluid.pdf . Expanded theorem source; its network and service assumptions delimit the cited implication. registry ↩a ↩b ↩c ↩d