This disclosure describes techniques that include adding information to a network service header in packets being processed by a set of compute nodes in a service chain. The information added to the network service header can be used during selection of the next hop in a service chain, and may be used to help ensure that service level agreements (SLA) are met with respect to one or more metrics. In one example, this disclosure describes a method that includes receiving, by a service complex having a plurality of service nodes, a packet associated with a service chain representing a series of services to be performed on the packet by one or more of the plurality of service nodes; identifying, by the service complex, one or more service chain constraints associated with the service chain; and modifying the packet, by the service complex, to include information about the service chain constraints.