Last modified: 10/19/04 10:41:57 AM
D. Nicol, S.W. Smith, M. Zhao.
"Evaluation of Efficient Security for BGP Route Announcements
using Parallel Simulation."
Simulation Modelling Practice and Theory.
12: 187--216. 2004.
The Border Gateway Protocol (BGP) determines how Internet traffic is
routed throughout the entire world; malicious behavior by one or more
BGP speakers could create serious security issues. Since the protocol
depends on a speaker honestly reporting path information sent by
previous speakers and involves a large number of
independent speakers, the Secure BGP (S-BGP) approach uses public-key
cryptography to ensure that a malicious speaker cannot fabricate this
information. However, such public-key cryptography is expensive: S-BGP
requires a digital signature operation on each announcement sent to
each peer, and a linear (in the length of the path) number of
verifications on each receipt. We use simulation of a 110 AS system
derived from the Internet to evaluate the impact that the
processing costs of cryptography have on BGP convergence time. We
find that under heavy load the convergence time using ordinary S-BGP
is nearly twice as large as under BGP. We examine the impact of highly
aggressive caching and pre-computation optimizations for S-BGP, and
find that convergence time is much closer to BGP. However,
these optimizations may be unrealistic, and are certainly expensive
of memory. We consequently use the structure of BGP processing to
design optimizations that reduce cryptographic overhead by amortizing
the cost of private-key signatures over many messages. We call this
method Signature-Amortization (S-A). We find that S-A provides as
good or better convergence times as the highly optimized S-BGP, but
without the cost and complications of caching and pre-computation. It
is possible therefore to minimize the impact route validation has on
convergence, by being careful with signatures, rather than
consumptive of memory.
PDF of preliminary version