According to examples, an apparatus may include a processor and a memory on which is stored machine readable instructions. The instructions may cause the processor to intercept a packet from a downstream service function classifier, in which the packet includes metadata that specifies an ordered set of service functions within a service function chain to be implemented on the packet, generate a correlation cookie that associates the packet with the service function chain, and encode the correlation cookie into the packet. The instructions may also cause the processor to store the correlation cookie and the metadata in a cache to correlate the correlation cookie and the metadata and send the packet with the encoded correlation cookie to the service function provider.