A method comprising: receiving, by a controller network device of a network, a request for network connectivity between a service entry point and a service exit point for a service chain that defines three or more service points to be applied in a particular order to provide a composite service for application to packet flows associated to the service chain; receiving and storing, by the controller network device, active topology information for the network; computing, for each pair of the service points in the particular order and by the controller network device based on the active topology information, at least one end-to-end sub-path through a sub-network connecting the pair of the service points, wherein each end-to-end sub-path is locally optimal according to one or more local constraints; computing, by the controller network device and based on the end-to-end sub-path for each pair of the service points, a service path between the service entry point and the service exit point for the service chain, wherein the service path satisfies local and global constraints for the request; computing, by the controller network device and based on the active topology information, an end-to-end path between the service entry point and the service exit point for the service chain, wherein the end-to-end path is computed using constrained shortest path first, CSPF, routing such that the end-to-end path includes each of the service points; comparing, by the controller network device, the end-to-end path and the service path to determine which of the end-to-end path and the service path is a most satisfactory path according to the global constraint for the request; and providing, by the controller network device in response to the request for network connectivity, an indication that the request for network connectivity is granted to permit use of the most satisfactory path for sending network traffic along the service chain. receiving, by a controller network device of a network, a request for network connectivity between a service entry point and a service exit point for a service chain that defines three or more service points to be applied in a particular order to provide a composite service for application to packet flows associated to the service chain; receiving and storing, by the controller network device, active topology information for the network; computing, for each pair of the service points in the particular order and by the controller network device based on the active topology information, at least one end-to-end sub-path through a sub-network connecting the pair of the service points, wherein each end-to-end sub-path is locally optimal according to one or more local constraints; computing, by the controller network device and based on the end-to-end sub-path for each pair of the service points, a service path between the service entry point and the service exit point for the service chain, wherein the service path satisfies local and global constraints for the request; computing, by the controller network device and based on the active topology information, an end-to-end path between the service entry point and the service exit point for the service chain, wherein the end-to-end path is computed using constrained shortest path first, CSPF, routing such that the end-to-end path includes each of the service points; comparing, by the controller network device, the end-to-end path and the service path to determine which of the end-to-end path and the service path is a most satisfactory path according to the global constraint for the request; and providing, by the controller network device in response to the request for network connectivity, an indication that the request for network connectivity is granted to permit use of the most satisfactory path for sending network traffic along the service chain.