In one example, a network device receives a packet to be forwarded according to a label switching protocol, determines a service to be performed on the packet by a service network device, sends a label request message to the service network device, wherein the label request message indicates support for labels having a particular length, wherein the particular length is larger than twenty bits (e.g., forty bits), and wherein the label request message specifies the service to be performed on the packet, receives, in response to the label request message, a label mapping message defining a label of the particular length, appends the label to the packet to form a Multi-Protocol Label Switching (MPLS)-encapsulated packet, and forwards the MPLS-encapsulated packet according to the label switching protocol.