An example method of optimizing connectivity between data centers in a hybrid cloud system having a first data center managed by a first organization and a second data center managed by a second organization, the first organization being a tenant in the second data center. The method includes probing a wide area network (WAN) with test packets by varying an internet protocol (IP) flow tuple of the test packets across a set of IP flows. The method includes identifying a plurality of paths between a gateway of the first data center and another gateway of the second data center associated with the set of IP flows. The method further includes selecting an IP flow from the set of IP flows for an application executing in the first data center. The method further includes establishing a path-optimized connection between the gateway and the other gateway through the WAN having the selected IP flow for use by the application.