The cloud-native paradigm advocates agile development and deployment of virtualized micro-services, introducing a flexibility and dynamicity for service endpoints that may exist in many locations of a provider’s network, not just data centers. Such ability leaves open the problem of scheduling traffic from clients to those possible locations. In this paper, we position our solution to this problem at the data plane level, avoiding the shortfalls of existing solutions in terms of latency and path stretch. For this, we present a system model for forwarding service requests based on compute information, with a distributed scheduler realizing the traffic steering decision at line rate and with measurable performance gains against existing networklevel solutions. We evaluate our solution against several design aspects to provide insights for real-world deployments, while quantifying performance improvements for use cases where such scheduling decisions could indeed be performed at the level of each service request. Here we show that our improvements in request completion time may lead to serving up to 162% more clients within the bounded request time that would ensure acceptable quality of experience.