Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Design and Analysis of Optimization Algorithms to Minimize Cryptographic Processing in BGP Security Protocols



Vinay Sriram, Douglas Montgomery


The Internet is subject to attacks due to vulnerabilities in its routing protocols. One proposed approach to attain greater security is to cryptographically protect network reachability announcements exchanged between Border Gateway Protocol (BGP) routers. This study proposes and evaluates the performance and efficiency of various optimization algorithms for validation of digitally signed BGP updates. In particular, this investigation focuses on the BGPSEC (BGP with SECurity) protocol, currently under consideration for standardization in the Internet Engineering Task Force. We analyze three basic BGPSEC update processing optimization algorithms: Unoptimized, ache Common Segments (CCS), and Best Path Only (BPO). We further propose and study cache management schemes to be used in conjunction with the CCS and BPO algorithms. The performance metrics used in the analyses are: (1) routing table convergence time after BGPSEC peering reset or router reboot events and (2) peak-second signature verification workload. Both analytical modeling and detailed trace-driven simulation were performed. Results show that the BPO algorithm is 330% to 628% faster than the unoptimized algorithm for routing table convergence in a typical core- facing provider edge router.
Computer Communications


Border Gateway Protocol, Security, Inter-domain Routing, Internet Infrastructure Protection


Sriram, V. and Montgomery, D. (2017), Design and Analysis of Optimization Algorithms to Minimize Cryptographic Processing in BGP Security Protocols, Computer Communications, [online], (Accessed May 27, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created June 30, 2017, Updated October 12, 2021