Some embodiments provide a method that identifies multiple paths between a first site and a second site. A security association (SA) is established for transmitting encrypted payload from the first site to the second site in a virtual private network (VPN) session. The method selects a path based on metrics that are obtained for the paths. The selected path is defined by a first endpoint address of the first site and a second endpoint address of the second site. The method sends a message from the first site to the second site to update the SA to switch from using an original path to using the selected path. The message indicates the first and second endpoint addresses. The method transmits a packet including a payload that is encrypted according to the updated SA.