A network device is described that includes one or more processors configured to select a prioritized sub-set of a plurality of routing protocol sessions based on peer priority information. The one or more processors are configured to establish one or more routing protocol sessions of the prioritized sub-set. The one or more processors are configured to, in response to determining that a threshold for establishing the prioritized sub-set of the plurality of routing protocol sessions is satisfied, establish one or more routing protocol sessions of the plurality of routing protocol sessions that are not included in the prioritized sub-set. The one or more processors are configured to forward network traffic using the established one or more routing protocol sessions of the prioritized sub-set and the established one or more routing protocol sessions of the plurality of routing protocol sessions that are not included in the prioritized sub-set.