Learning in Strategic Queuing Systems with Small Buffers

Consider a large-scale data-center network where packet routing is done via simple distributed strategies. Routers use learning algorithms to select servers to process their packets, which may be rejected due to congestion. Each server has a very small buffer that can store a single packet until its processing is complete. We assume each router runs an algorithm guaranteeing \emph{no regret}, and study the joint performance of the system. We show that a small constant-factor increase in the servers' processing rates (relative to what would be needed under centralized coordination with large buffers at the servers) suffices to keep the system stable, even if servers adversarially choose which packet to serve when several packets arrive simultaneously.