A plurality of network nodes are deployed in a network, each network node configured to apply a service function to traffic that passes through the respective network nodes. A controller generates information for a service chain that involves application to traffic of one or more service functions at corresponding ones of the plurality of network nodes along a forward path through the one or more network nodes. The controller identifies one or more of the service functions within the service chain that is stateful. When one or more of the service functions of the service chain is stateful, the controller generates information for a reverse path through the one or more service nodes for the one or more stateful service functions. The controller binds a forward chain identifier for the forward path with a reverse chain identifier for the reverse path for the service chain.