We prove a strong inapproximability result for routing on directed
graphs with low congestion. Given as input a directed graph on $N$
vertices and a set of source-destination pairs that can be connected
via edge-disjoint paths, we prove that it is hard, assuming NP
doesn't have $n^{O(\log\log n)}$ time randomized algorithms, to
route even a $1/N^{\Omega(1/c(N))}$ fraction of the pairs, even if we
are allowed to use each edge on $c(N)$ paths. Here the congestion
$c(N)$ can be any function in the range $1 \le c(N) \le \alpha \log
N/\log\log N$ for some absolute constant $\alpha > 0$.

The hardness result is in the right ballpark since a factor
$N^{O(1/c(N))}$ approximation algorithm is known for this problem. An
important feature of our result is that it holds with perfect
completeness, and shows hardness of low-congestion routing of
instances where {\bf all} the input source-destination pairs can be
routed on {\em edge-disjoint paths}. Consequently, our result also
implies that it is hard to find a routing of all the
source-destination pairs that incurs congestion at most $\alpha \log
N/\log \log N$, even if there exists an edge-disjoint (i.e.,
congestion $1$) routing of all the pairs. This shows the optimality,
up to constant factors, of the approximation guarantee of the classic
Raghavan-Thompson algorithm based on randomized rounding of the
fractional multicommodity flow solution.