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

Published: July 01, 2017


Vinay Sriram, Douglas C. 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.
Citation: Computer Communications
Volume: 106
Pub Type: Journals


Border Gateway Protocol, Security, Inter-domain Routing, Internet Infrastructure Protection
Created July 01, 2017, Updated November 10, 2018