A method for verifying update information in Border Gateway Protocol (BGP), includes: upon receipt of an update message, verifying, by an Autonomous System (AS), the update message according to a determined maximum time of verifications; and trusting the update message if the verifications are successful. The update message may be AS_PATH and/or prefix. In the invention, upon receipt of an update message, the AS verifies the update information according to the maximum time of verifications, which ensures that the time of verifications will not exceed the maximum time of verifications when the AS verifies the update information. Accordingly, load on CPU is decreased during verification of the update information and hence the network convergence speed is improved.