A surprising result due to Racke shows that every network has an oblivious routing scheme such that the congestion incurred on any edge when demands are routed according to this scheme, is no more than log3 n times the optimum congestion for these set of demands.
Racke's original construction ran in exponential time. In a subsequent paper the construction is made polynomial time with a slight worsening of the guarantee to log^4n. The proofs are also simplified.
The guarantee is improved to log^2n loglog n in a later paper.