Robustness is a desired feature for any backbone network. As a minimum requirement to be considered robust, a network must remain connected after any single node or link failure, so that each node is able to communicate with all other nodes. It turns out that some national optical backbones do not satisfy this condition, the Chilean Internet backbone being an example. To solve this problem, it is needed the addition of link(s) to the network, which can usually be done in different ways, leaving room to do that while minimizing other metrics of interest. This letter discusses metrics to evaluate the robustness of such networks (specifically, edge betweenness centrality, the number of link cutsets, and node Wiener impact) and proposes a variable neighborhood search heuristic to improve it by adding a few well-placed links. As a case of study, results are presented for the Chilean Internet backbone, considering three and four extra links.