In one example, an edge routing device of a service provider network includes one or more network interfaces configured to send and receive packets and a processing unit configured to retrieve, from a packet received via the one or more network interfaces, priority data from an Internet protocol (IP) header of the packet, form a first tag including a first set of data in a first priority field of the first tag, wherein the first set of data represents a first portion of the priority data, form a second tag including a second set of data in a second priority field of the second tag, wherein the second set of data represents a second portion of the priority data, encapsulate the packet with the first tag and the second tag, and forward, via the one or more network interfaces, the encapsulated packet.