A graceful restart is provided in a NSF capable router. When a switchover to a standby controller is required, the standby controller receives replicated link state message headers from an active controller. The standby controller generates a link state request (LSR) message from the link state message headers and transmits the LSRs to neighboring routers. The standby controller receives a link state update that includes the link state messages. By using the LSRs, the standby controller can be quickly synchronized with its neighbors well within the grace period, thereby maintaining adjacency.