Embodiments provide a method, network device, and computer program product for optimizing traffic in a link-state network distributed across a plurality of sites. The method, network device, and computer program product include receiving a multi-destination message at a first node within the link-state network. Additionally, the method, network device, and computer program product include identifying a plurality of multi-destination trees within the network, each tree having a respective root node. The method, network device, and computer program product determine a plurality of cost values corresponding to each of the plurality of multi-destination trees, based on one or more links along a shortest path from the first node to the respective root node of each tree. Based on the determined cost values, the method, network device, and computer program product select one or more of the multi-destination trees and transmit the multi-destination message using the selected tree.