A method for initializing the border gateway protocol (BGP) on network devices. The method includes predicting, by the network device, using a set of prediction heuristics, a first possible internet protocol version 6 (IPv6) address of a first peer network device. The method further includes sending, by the network device, a first neighbor discovery protocol (NDP) request for the first possible IPv6 address, and receiving, by the network device, from the first peer network device, in response to the NDP request, a first media access control (MAC) address. The method also includes establishing, after receiving the first MAC address, a BGP session with the first peer network device and exchanging route updates with the first peer network device, and processing a packet. The processing of the packet is delayed until the first MAC address is received.