A first router generates session establishment metrics for use in network path selection. For example, a plurality of routers connect a client device to a network service instance hosted by a server. A first router is connected to the network service instance via first and second paths. The first router receives session performance requirements for a session between the client device and the network service instance. The first router forwards, along the first path, network traffic for the session by modifying a first packet of the session to include a session identifier for the session. The first router determines that session establishment metrics for the session do not satisfy the session performance requirements. In response, the first router forwards, along the second path, the network traffic for the session by modifying a second packet of the session to include the session identifier for the session.