RIB Size Estimation for BGP

Contacts: ksriram@nist.gov, dougm@nist.gov

K. Sriram

(with O. Borchert, O. Kim, D. Cooper, and D. Montgomery)

May 24, 2011

Trustworthy Networking Program

This research was supported by This research was supported by the Department of Homeland Securi the Department of Homeland Security under the Secure Pr

Pr

Routing Infrastructure (SPRI) program and Routing Infrastructure (SPRI) program and the NIST Information Technology Laboratory Cy

Laboratory Cy

Security Program.

Acknowledgements: Many thanks are due to the BGPSEC Design Team for comments and suggestions. 
Distribution of # Prefixes in Distribution of # Prefixes in 

eBGP Announcements eBGP Announcements 

• Prob. {# Prefixes < 100} = 99.73% 

1

10

100

1000

10000

100000

1000000

1

31

61

91

121

151

181

211

241

273

307

340

374

416

458

525

586

682

841

1010

# PREFIXES IN AN UPDATE ANNOUNCEMENT

# UPDATES
Distribution of AS Path Lengt

Distribution of AS Path Lengt

eBGP Announcements eBGP Announcements

1

10

100

1000

10000

100000

1000000

1 2 3 4 5 6 7 8 

# ASes in AS 

# AS PATHS

1

10

100

1000

10000

100000

1000000

1 3 5 7 9 11 13 15 17 19 21 23 25 27 32 34 36 38 47

# ASes in AS PATH

# AS PATHS

Prepended/Repeat ASes Not Collapsed Prepended/Repeat AS

• Avg. AS Path Length = 3.743• Std. Dev. of Path Length = 1.92• Prob. {AS Path Length < 10} = 97.82 %

• Prob. {AS Path Length < 12} = 99.06 %

• Avg. AS Path Length • Std. Dev. of Path Len• Prob. {AS Path Lengt• Prob. {AS Path Lengt
Measurement of Prefixes and Path

Measurement of Prefixes and Path

ISP’s Route Reflectors and PE Rou

s Route Reflectors and PE Ro

Measurement data from a Large, Tier 1 ISP

Provider 

Edge (PE) 

routers

# Unique Prefixes Observed 377,000 Total number of Prefix Paths Observed (Low) 750,000 Total number of Prefix Paths Observed (High) 1,100,000 Ratio of Total # Prefix Paths / # Unique Prefixes (High) 2.92 
Update Format and Signature Overh

Update Format and Signature Overh

Update Element

Octets (RSA2048 Alg.)

NLRI Length 1NLRI 4AS-n 4AS-(n-1) 4... 4AS2 4AS1 (Originating AS) 4AS-(n+1) (ASN of Subsequent AS) 4Expire Time 8Algorithm Suite Itentifier 1Signature-List Block Length 2SKI Length-n 1SKI-n 20Signature-n 256SKI Length-(n-1) 1SKI-(n-1) 20Signature-(n-1) 256.........SKI Length-2 1SKI-2 20Signature-2 256SKI Length-1 1SKI-1 20Signature-1 256Other BGP Attributes (besides NLRI & AS_PATH; measured/estimated) 40Estimated Signed Update Size (average) 1188Measured Unsigned BGP Update Size (average including all BGP attributes) 78

Sigove

15x inupdate RSA-2

Reference: draft-lepinskibgpsec-protocol

4 ASes (see Sli
Estimation of BGPSEC Update Si

Estimation of BGPSEC Update S

eBGP Update Size (Octets)

Multiplier Relative to Unsigned

Unsigned 78 1.RSA-2048 1188 15.ECDSA-256 420 5.ECDSA-224 388 4.

• It should also be noted that eBGP updates in BGP-4 ave

3.83 prefixes per update (see Slide 2) whereas the samBGPSEC have only a single prefix per update (un-optim

• Unsigned update size was measured from Routeviews d• Signed update sizes are estimated (as illustrated in Slid
BGPSEC Adoption Rate (1) BGPSEC Adoption Rate (1)

0%5%

10%15%20%25%

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2

Probability Distribution of Adoption Rate

Normal Distribution, Std Dev

=

3

Normal Distribution, Std Dev

=

2

Start of 

Adoption

Probability Distribution of Adoption (Truncated Normal Distrib
0%

10%20%30%40%50%60%70%80%90%

100%

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 20

Cumulative Distribution of Adoption Rate

Normal Distribution, Std Dev = 3Normal Distribution, Std Dev = 2

BGPSEC Adoption Rate (2) BGPSEC Adoption Rate (2)

Start of 

Adoption

Cumulative Distribution of Adoption (Truncated Normal Distri
Projection of eBGP Prefixes an

Projection of eBGP Prefixes an

Signed Prefix Paths (1) Signed Prefix Paths (1) 

• Growth in eBGP prefixes is assumed to be 15% annually [1].

[1] Geoff Huston, “BGP in 2008,” http://www.potaroo.net/ispcol/2009-03/bgp2008.html

1.0E+041.0E+051.0E+061.0E+071.0E+08

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025

YEAR

Signed Prefix Paths (Adptn. 2; RR 9.55x)Signed Prefix Paths (Adptn. 1; RR 9.55x)Unique eBGP PrefixesSigned Unique Prefixes (Adptn. 2)Signed Unique Prefixes (Adptn. 1)

Start of 

Adoption

• Adp

adoNormwith (see 

• Adp

adoNormwith (see 

• RR 

Refl

• Pref

multfor R
Projection of eBGP Prefixes an

Projection of eBGP Prefixes an

Signed Prefix Paths (2) Signed Prefix Paths (2) 

• In the following data and plots, we will a

Adoption 1 (truncated Normal distributioadoption with Std. Dev. =2) unless otherstated.
Parameters for Estimation of RIB S

Parameters for Estimation of RIB S

• For BGPSEC, we rounded up the Avg. # ASes in AS path to 4 (from 3.743)• The model (see next slide) predicts the impact on the RIB size due to signa

Parameters for Estimation of RIB Size in a BGP Router Value Units 

Average update size w/o signatures 78 Octets MAverage update size with signatures (RSA-2048 signature alg) 1188 Octets EAverage update size with signatures (ECDSA-256 signature alg) 420 Octets EAverage RIB data structure overhead per update (fraction) 5% AAvg. number of peers from which update is received for each eBGP prefix at RR 9.55

ML

Avg. number of peers from which update is received for each eBGP prefix at PE 2.92

ML

Avg. number of peers from which update is received for each internal 

prefix (PE or RR) 10 AAverage # ASes in AS path 3.743 MAverage # prefixes per update announcement 3.832 M

Growth rate per year for Internal prefixes 5% AGrowth rate per year for External prefixes 15%

TpoHw

Include Internal prefixes? 1 1 

[1] Geoff Huston, “BGP in 2008,” http://www.potaroo.net/ispcol/2009-03/bgp2008.html
Methodology for RIB Size Estimat

Methodology for RIB Size Estimat

• The model predicts the impact on RIB size due to signatures in eBGP 

well as details various components that contribute to RIB size.

• The model includes contribution to RIB size due to internal prefixes (

relatively insignificant).

Parameters for Estimation of RIB Size in a BGP Router Symbol Units Equation (Mo

Average update size w/o signatures U OctetsAverage RIB data structure overhead per update (fraction) xAverage memory requirement per update in RIB Ur Octets Ur = U*(1+xAvg. number of peers from which update is received for each eBGP prefix NuAvg. number of peers from which update is received for each internal prefix mAverage # prefixes per update announcement pTotal # Unique Internal Prefixes with routes in the BGP speaker PiTotal # Unique eBGP Prefixes with routes in the BGP speaker PeRIB memory consumed by internal prefixes iRIB GB iRIB = (Pi/pAverage update size with signatures Ua OctetsFraction of eBGP updates that are signed (adoption factor) fRIB memory consumed by eBGP updates (BGP-4) eRIBu GB eRIBu = (PeRIB memory consumed by all eBGP updates (fraction f are BGPSEC; fraction (1-f) are unsigned) eRIBs GB

eRIBs = [Pe{Pe*(1-f)/p}

Total RIB memory (BGPSEC) RIBu GB RIBu = iRIB Total RIB memory (BGP-4) RIBs GB RIBs = iRIB 
Unique Prefixes and Prefix Path

Unique Prefixes and Prefix Path

• Growth in eBGP prefixes is assumed to be 15% annually (see Slide 11)• Growth in internal prefixes is assumed to be 5% annually (see Slide 11)

• Estimates for Route Reflector (prefix-path multiplier factor = 9.55 (for eBGP

internal prefixes) ; also see Slide 4)

• Adoption Model 1 (see Slides 7-9) 

Year

# Unique Internal Prefixes

# Unique External (eBGP) prefixes

Total # Internal Prefix Paths

# Unique eBGP prefixes in BGPSEC Adoption (Signed)

# Unique Unsigned eBGP prefixes

Total # BGPSEC Signed Prefix Paths

Total UnsigeBGP Prefix Paths

2011 800000 377000 8000000 0 377000 0 3602012 840000 433550 8400000 0 433550 0 4142013 882000 498583 8820000 0 498583 0 4762014 926100 573370 9261000 0 573370 0 5472015 972405 659375 9724050 0 659375 0 6292016 1021025 758282 10210253 12174 746108 116252 7122017 1072077 872024 10720765 52057 819967 497095 7822018 1125680 1002827 11256803 152516 850311 1456390 8112019 1181964 1153252 11819644 351063 802189 3352322 7662020 1241063 1326239 12410626 663120 663120 6332177 6332021 1303116 1525175 13031157 1060895 464280 10130562 4432022 1368271 1753952 13682715 1487199 266752 14201374 2542023 1436685 2017044 14366851 1896633 120411 18111088 1142024 1508519 2319601 15085193 2282360 37241 21794419 352025 1583945 2667541 15839453 2667541 0 25472541 

BGPSEC (at RR
RIB Size Estimation RIB Size Estimation 

- Detailed Da

Detailed Da

• RSA-2048 and ECDSA-256 signature algorithms• For the prefix-path projections as shown in Slide 13

Year

RIB Requirement for Internal Prefix Paths (GB)

RIB Requirement for External (eBGP) Prefix Paths (GB)

Total RIB size (GB)

Portion of RIB due to Unsigned eBGP Prefix Paths

RIB size for eBGP Prefix Paths with Signatures (GB)

Total RIB size (GB)

Portion of RIB due to Unsigned eBGP Prefix Paths

RIB eBPaSig(G

2011 0.17 0.08 0.25 0.08 0.01 0.26 0.08 2012 0.18 0.09 0.27 0.09 0.01 0.28 0.09 2013 0.19 0.10 0.29 0.10 0.01 0.30 0.10 2014 0.20 0.12 0.31 0.12 0.01 0.32 0.12 2015 0.21 0.13 0.34 0.13 0.01 0.35 0.13 2016 0.22 0.15 0.37 0.15 0.15 0.51 0.15 2017 0.23 0.18 0.41 0.17 0.62 1.01 0.17 2018 0.24 0.20 0.44 0.17 1.82 2.23 0.17 2019 0.25 0.23 0.49 0.16 4.18 4.60 0.16 2020 0.26 0.27 0.53 0.13 7.90 8.30 0.13 2021 0.28 0.31 0.59 0.09 12.64 13.01 0.09 2022 0.29 0.36 0.65 0.05 17.71 18.06 0.05 2023 0.31 0.41 0.72 0.02 22.59 22.92 0.02 2024 0.32 0.47 0.79 0.01 27.19 27.51 0.01 2025 0.34 0.54 0.88 0.00 31.77 32.11 0.00 

BGP-4 (RR) BGPSEC (RR, RSA-2048) BGPSEC (R
Contribution to RIB Memory due only to Contribution to RIB Memory due only to 

Signed eBGP Signed eBGP Prefix Paths Prefix Paths

Total # Signed eBGP PrefixPaths in RIB

For RSA-2048 

Signature Alg. 

(GB)

For ECDSA-256 

Signature Alg. 

(GB)

500000 0.62 0.22

1000000 1.25 0.441500000 1.87 0.662000000 2.49 0.882500000 3.12 1.103000000 3.74 1.323500000 4.37 1.544000000 4.99 1.764500000 5.61 1.985000000 6.24 2.215500000 6.86 2.436000000 7.48 2.656500000 8.11 2.877000000 8.73 3.097500000 9.36 3.318000000 9.98 3.538500000 10.60 3.759000000 11.23 3.979500000 11.85 4.19

10000000 12.47 4.4110500000 13.10 4.6311000000 13.72 4.8511500000 14.35 5.0712000000 14.97 5.2912500000 15.59 5.5113000000 16.22 5.73

Total # Signed eBGP PrefixPaths in RIB

For RSA-2048 

Signature Alg. 

(GB)

Fo

S

13500000 16.84 14000000 17.46 14500000 18.09 15000000 18.71 15500000 19.33 16000000 19.96 16500000 20.58 17000000 21.21 17500000 21.83 18000000 22.45 18500000 23.08 19000000 23.70 19500000 24.32 20000000 24.95 20500000 25.57 21000000 26.20 21500000 26.82 22000000 27.44 22500000 28.07 23000000 28.69 23500000 29.31 24000000 29.94 24500000 30.56 25000000 31.19 25500000 31.81 26000000 32.43 
RIB Size RIB Size Estimation: Relative Estimation: Relative Measu

Measu

Contributions due to Contributions due to eBGP & Internal eBGP & Internal P

P

• Estimate for Route Reflector (prefix-path multiplier factor = 9.55) • Contribution to RIB size due to internal prefixes (unsigned) is very • Signed eBGP prefixes dominate 

BGPSEC

RSA-2048

048

121620242832

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 202

YEAR

RIB MEMORY (GB)

Total RIB (BGPSEC)EBGP only (BGPSEC)Total RIB (BGP-4)EBGP only (BGP-4)Internal Prefixes

Start of 

Adoption
• Estimate for Route Reflector (prefix-path multiplier factor = 9.55) • Contribution to RIB size due to internal prefixes (unsigned) is ver• Signed eBGP prefixes dominate 

E

BGPSEC ECDSA-256

02468

1012

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025

YEAR

RIB MEMORY (GB)

Total RIB (BGPSEC)EBGP only (BGPSEC)Total RIB (BGP-4)EBGP only (BGP-4)Internal Prefixes

Start of 

Adoption

RIB Size RIB Size Estimation: Relative Estimation: Relative Measu

Measu

Contributions due to Contributions due to eBGP & Internal eBGP & Internal P

P
BGPSEC

RSA-2048

0.010.101.00

10.00

100.00

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 

YEAR

RIB MEMORY (GB)

Total RIB (BGPSEC)EBGP only (BGPSEC)Total RIB (BGP-4)EBGP only (BGP-4)Internal Prefixes

RIB Size Estimation RIB Size Estimation (RSA-2048)

Same Figure as on Slide Same Figure as on Slide 16 but with Logarithmic S

but with Logarithmic S
BGPSEC

ECDSA-256

0.010.101.00

10.00

100.00

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 

YEAR

RIB MEMORY (GB)

Total RIB (BGPSEC)EBGP only (BGPSEC)Total RIB (BGP-4)EBGP only (BGP-4)Internal Prefixes

RIB Size Estimation RIB Size Estimation (ECDSA-256)

Same Figure as on Slide Same Figure as on Slide 17 but with Logarithmic S

but with Logarithmic S
Sensitivity to Adoption Rate Model Sensitivity to Adoption Rate Model (RS

• See Slides 7 and 8 for details of Adoption rate models 1 and 2

048

121620242832

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2

YEAR

RIB MEMORY (GB)

RR with RSA-2048; Adoption 1 (Normal, Std. Dev. 2)RR with RSA-2048; Adoption 2 (Normal, Std. Dev. 3)

Start of 

Adoption
Sensitivity to Adoption Rate Model Sensitivity to Adoption Rate Model (ECD

• See Slides 7 and 8 for details of Adoption rate models 1 and 2

02468

1012

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2

YEAR

RIB MEMORY (GB)

RR with ECDSA-256; Adoption 1 (Normal, Std. Dev. 2)RR with ECDSA-256; Adoption 2 (Normal, Std. Dev. 3)
RIB Size Estimation RIB Size Estimation

Route Reflector / PE Router & RSA Route Reflector / PE Router & RSA-2048 / ECD

2048 / ECD

048

121620242832

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 202

YEAR

RIB MEMORY (GB)

RR with RSA-2048RR with ECDSA-256PE with RSA-2048PE with ECDSA-256
ECDSA-256 vs. ECDSA 256 vs. ECDSA-224

• ECDSA-224 (56 octet sig) is comparable to RSA-2048 (256 octet 

terms of signature strength

• But the RIB size is only slightly higher for ECDSA-256 (64 octet s

compared to ECDSA-224

• Might as well use ECDSA-256 and have greater longevity for sig 

• 

Year

# Internal Prefixes

# External (eBGP) prefixes

Total RIB Size for ECDSA-256

Total RIB Size for ECDSA-224

2011 800000 377000 0.26 0.262012 840000 433550 0.28 0.282013 882000 498583 0.30 0.302014 926100 573370 0.32 0.322015 972405 659375 0.35 0.352016 1021025 758282 0.42 0.422017 1072077 872024 0.61 0.602018 1125680 1002827 1.05 1.012019 1181964 1153252 1.89 1.782020 1241063 1326239 3.19 2.982021 1303116 1525175 4.84 4.502022 1368271 1753952 6.61 6.132023 1436685 2017044 8.32 7.712024 1508519 2319601 9.94 9.212025 1583945 2667541 11.57 10.72
BGPSEC Signature Algorithm Transition (E

BGPSEC Signature Algorithm Transition (E

05

10152025303540

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2

YEAR

RIB MEMORY (GB)

Dual Sig-List Blocks (RSA-2048 & ECDSA-256) RSA-2048ECDSA-256Transition from RSA-2048 to ECDS-256

Start of 

Adoption

Algorithm 

Transition

• Dual signature-list blocks are used during algorithm transition (se

lepinski-bgpsec-protocol)
BGPSEC Signature Algorithm Transit

BGPSEC Signature Algorithm Transi

Followed by Protocol Transition (Exam

Followed by Protocol Transition (Exam

05

10152025303540

2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2

YEAR

RIB MEMORY (GB)

Dual Sig-List Blocks (RSA-2048 & ECDSA-256) RSA-2048Dual Sig-List Blocks (two ECDSA-256 blocks)ECDSA-256Algorithm Transition followed by Protocol Transition

Start of 

Adoption

Algorithm 

Transition

Protoco

Transitio

• Dual signature-list blocks are also used during protocol/alg transition (see draf
Summary & Conclusions Summary & Conclusions

• RIB sizes have been estimated for realistic RR and PE 

(with input from a large, Tier 1 ISP)

• Different signature algorithms considered (RSA-2048, E

256)

• RIB memory needs to be engineered so it is adequate 

algorithm/protocol transition down the road

• 15% yearly growth for unique eBGP prefixes (377K in 2

2.7M in 2025)

• BGPSEC adoption curve – truncated Normal distributio• 9.55x multiplier applied to determine # prefix paths in R• RIB memory requirement of 0.5GB in 2016 to 8.3 GB in 

32 GB in 2025 (worst case assuming RSA-2048 all the 

• Algorithm transition to ECDSA-256 likely (should happe

2020

• Assuming such transition, 20 GB for RIB memory woul

conservative estimate -- good all the way out to 2025 (S