A network node has a graceful restart mode in which the node: sends a graceful restart notification to one or more neighbouring nodes; attempts to re-establish an adjacency with the neighbouring node(s); receives link state data from at least one of the neighbouring node(s), the received data being sent in response to said attempt; derives pre-restart link data from the received data, the derived data identifying formerly active links, including the node, for routing traffic before the restart; routes network traffic in accordance with routing information stored in the router; detects one or more links, of the formerly active links, which are currently inactive; continues with graceful restart after said detection; determines one or more links, of the formerly active links, which are currently active; and exits the graceful restart mode in response to successful re-establishment of adjacencies with a respective neighbouring node for each of the currently active link(s).