This paper addresses routing in networks with both delay-sensitive (class 1) and delay-insensitive (class 0) traffic where the class 1 traffic is to be delivered with bounded delay and the delay of class 0 traffic is to be minimized subject to this constraint. This delay-constrained routing, with constraints on the overall mean delay of class 1 traffic, is shown to be NP-hard with an M/M/1 link model. Reformulating this with a convex relaxation on the delay constraint, we propose a link-state protocol (DC-HALO) for solving this constrained convex optimization problem. DC-HALO is based on the Hop-by-hop Adaptive Link-state Optimal (HALO) routing algorithm and iteratively computes the forwarding tables for each class and the splitting ratios to eventually achieve optimality. The validity of this approach is shown using flow-based simulations.