Link-state routing protocols are widely used for intradomain routing in the Internet. These protocols are simple to administer and automatically update paths between sources and destinations when the topology changes. However, finding link weights that optimize network performance, even for a given traffic scenario, is computationally hard. The situation is even more complex when the traffic is uncertain or time-varying. We present an efficient heuristic for finding link settings that give uniformly good performance, even under large changes in the traffic. The heuristic combines efficient search techniques with a novel objective function. The objective function combines the network performance with a cost of deviating from desirable features of robust link weight settings. We assess performance of our method using traffic data from an operational IP backbone.