This paper develops Quality of Service (QoS) based routing and priority class assignment algorithms using an end-to-end delay satisfaction balancing approach. Unlike the single-class delay satisfaction balancing optimization problem, the nonlinear multi-priority formulation is only convex within specific regions, and is infeasible otherwise. At first, a centralized off-line computation technique is proposed to calculate both the route configuration and end-to-end priority assignment. A gradient-based solution in the convex region and a heuristic to overcome the discontinuity are derived. An on-line distributed approximation is then presented. Performance evaluation shows that combining route and priority class assignment enables the network to accommodate more users of varying end-to-end delay requirements.