On the Hardness of Devising Interval Routing Schemes