  This paper establishes the state of the art in both deterministic and
randomized online permutation routing in the POPS network. Indeed, we show that
any permutation can be routed online on a POPS network either with
$O(\frac{d}{g}\log g)$ deterministic slots, or, with high probability, with
$5c\lceil d/g\rceil+o(d/g)+O(\log\log g)$ randomized slots, where constant
$c=\exp (1+e^{-1})\approx 3.927$. When $d=\Theta(g)$, that we claim to be the
"interesting" case, the randomized algorithm is exponentially faster than any
other algorithm in the literature, both deterministic and randomized ones. This
is true in practice as well. Indeed, experiments show that it outperforms its
rivals even starting from as small a network as a POPS(2,2), and the gap grows
exponentially with the size of the network. We can also show that, under proper
hypothesis, no deterministic algorithm can asymptotically match its
performance.
