Patent ID: 7826456

Claim:
A method for verifying update information in Border Gateway Protocol referred to as BGP hereafter, comprising: upon receipt of an update message, verifying, by an Autonomous System referred to as AS hereafter, update information in the update message according to a determined maximum time of verifications; trusting the update information if the verifications are successful; wherein the update information comprises Autonomous System Paths referred to as AS_PATH hereafter, and wherein verifying the update information according to the determined maximum time of verifications comprises: verifying nested signatures of preceding ASs of the AS in the AS_PATH layer by layer; stopping verification after the number of verified signatures reaches a first maximum time of verifications; wherein the update information further comprises a prefix, and wherein verifying the prefix according to the determined maximum time of verifications further comprises: determining, by the AS, whether a total time of verifying the prefix by its preceding ASs has reached a second maximum time of verifications; trusting the prefix directly if the total time of verifying the prefix by its preceding ASs has reached the second maximum time of verifications; and verifying the prefix in the update message if the total time of verifying the prefix by its preceding ASs has not reached the second maximum time of verifications.