  We consider the FCFS $GI/GI/n$ queue, and prove the first simple and explicit
bounds that scale as $\frac{1}{1-\rho}$ under only the assumption that
inter-arrival times have finite second moment, and service times have finite
$2+\epsilon$ moment for some $\epsilon > 0$. Here $\rho$ denotes the
corresponding traffic intensity. Conceptually, our results can be viewed as a
multi-server analogue of Kingman's bound. Our main results are bounds for the
tail of the steady-state queue length and the steady-state probability of
delay. The strength of our bounds (e.g. in the form of tail decay rate) is a
function of how many moments of the service distribution are assumed finite.
Our bounds scale gracefully even when the number of servers grows large and the
traffic intensity converges to unity simultaneously, as in the Halfin-Whitt
scaling regime. Some of our bounds scale better than $\frac{1}{1-\rho}$ in
certain asymptotic regimes. In these same asymptotic regimes we also prove
bounds for the tail of the steady-state number in service.
  Our main proofs proceed by explicitly analyzing the bounding process which
arises in the stochastic comparison bounds of Gamarnik and Goldberg for
multi-server queues. Along the way we derive several novel results for suprema
of random walks and pooled renewal processes which may be of independent
interest. We also prove several additional bounds using drift arguments (which
have much smaller pre-factors), and point out a conjecture which would imply
further related bounds and generalizations. We also show that when all moments
of the service distribution are finite and satisfy a mild growth rate
assumption, our bounds can be strengthened to yield explicit tail estimates
decaying as $O\big(\exp(-x^{\alpha})\big)$, with $\alpha \in (0,1)$ depending
on the growth rate of these moments.
