Distributing the link state information may introduce a significant protocol overhead on network resources. Hence, it is critical to investigate the issue of effectively and efficiently updating link state information. In this paper, by demonstrating that link state update schemes without considering the QoS requirements of connections cannot provide satisfactory solutions to real networks, we introduce a novel link information update scheme, Routing-Oriented update SchEme (ROSE). Via theoretical analysis and extensive simulations, we show that ROSE greatly outperforms the state of the art in terms of both protocol overhead and the accuracy of link state Information. Another contribution of this paper is the introduction of a method to numerically evaluate the staleness of link state information.