In this paper, we study the call admission control (CAC) and routing issue in multi-service networks. Two categories of calls are considered: a narrow-band (NB) with blocked calls cleared and a wide-band (WB) with blocked calls delayed. The objective function is formulated as reward maximisation with penalty for delay. The optimisation is subject to quality of service (QoS) constraints and, possibly, grade of service (GoS) constraints. A suboptimal solution is achieved by applying Markov decision process (MDP) theory together with a two-level approximation. First, the network is decomposed into a set of links assumed to have independent Markov and reward processes respectively. Second, the dimensions of the link Markov and reward processes are reduced by aggregation of the call classes into call categories. The CAC and routing policy is computed by the policy iteration algorithm from MDP theory. The numerical results show that the proposed CAC and routing method, based on the exact link MDP framework, is able to find an efficient trade-off between reward loss and average call set-up delay, outperforming conventional methods such as the least loaded routing (LLR).