A method for establishing a neighbor relationship, where corresponding authentication information is added to packets that are sent from a first network device and a second network device to each other. The first network device sends a hello packet to the second network device. The second network device receives the hello packet, performs authentication, and responds to the hello packet using an extended unidirectional link (UDL) link state packet (LSP) when the authentication succeeds. The first network device receives the extended UDL LSP, and performs authentication. When an authentication result includes that both the first network device and the second network device enable authentication and the authentication succeeds, a neighbor relationship between the first network device and the second network device may be established.