A network controller can register WAN edge routers and WAN optimizers distributed across a WAN. The controller can receive a request to establish a WAN optimized connection between first and second hosts. The controller can identify a first WAN optimizer to perform first services (e.g., de-duplication, compression, application acceleration, caching, etc.) for first traffic from the first host to the second host and first complementary services for second traffic from the second host to the first host, and a second WAN optimizer for the second traffic and second complementary services for the first traffic. The controller can establish the optimized connection comprising a first path including the first host, WAN optimizer, and router; a second path including the first router and a second router, and a third path including the second router, WAN optimizer, and host. The controller can route the first and second traffic through the optimized connection.