Several Quality of Service models have been proposed for the next generation of Internet, being Differentiated Service foreseen to support it in core networks. A new routing architecture must be adopted, to efficiently cope with these service differentiation mechanisms. This paper proposes an extension to traditional intra-domain routing protocols which takes into account service differentiation. In the new approach, routing paths must be selected according to network traffic conditions and Service Level Agreements. A new path selection mechanism is proposed, which guides higher priority traffic through the shortest path and diverts lower priority traffic through longer paths when service performance degradation is foreseen.