Subject: [sidr] RIB Size Estimation for BGPSEC

From: "t.petch" <[email-masked]>
Date: Fri, 27 May 2011 17:52:43 +0200

Try again ...
and again ...

 RRG, before looking for some architectures that would solve the world's routing
 problems, did discuss the expected capacity of DFZ routers,  given the expected
 rate of growth of technology, so as to work out how long the IETF has got to
 come up with something new.

 The consensus was that routers could not be expected to support more than 1M
 entries in the RIB which is somewhat less than the 2.7M you expect in 2025.
And
 the new architecture could make the world look very different by then, with
 outer routing headers for delivery to location, and inner routing headers for
 delivery to the identified host.

 Tom Petch

> ----- Original Message -----
> From: "Sriram, Kotikalapudi" <[email-masked]>
> To: "sidr wg list" <[email-masked]>
> Sent: Tuesday, May 24, 2011 2:28 PM
> Subject: [sidr] RIB Size Estimation for BGPSEC
>
>
> In response to a request during Q&A at the SIDR WG meeting, April 1, in
Prague,
> I am posting the results of modeling and estimation of the RIB size for
BGPSEC.
> (I plan to present this work at the SIDR WG meeting in Quebec.)
>
> Here is the link for the slides:
>
> http://www.antd.nist.gov/~ksriram/BGPSEC_RIB_Estimation.pdf
> { file:///D:/Articles/BGPSEC_RIB_Estimation.pdf }
>
> I will also shortly post an excel spread sheet so you can input your view
> of the BGPSEC world (signed prefix-paths you expect to see in your PE router
> or route reflector over time), and observe the corresponding RIB size
estimates.
>
> Key observations/conclusions – mostly copied from the summary/conclusions
slide
> (Slide #26):
>
> o RIB sizes have been estimated for realistic Route Reflector (RR) and
Provider
> Edge (PE) scenarios (with input from a large, Tier 1 ISP).
>
> o Different signature algorithms considered (RSA-2048, ECDSA-256).
>
> o RIB memory needs to be engineered so it is adequate for algorithm/protocol
> transition down the road.
>
> o 15% yearly growth for # unique eBGP prefixes (377K in 2011 to 2.7M in 2025).
>
> o 9.55x multiplier applied to determine # eBGP prefix paths in RR (i.e., #
eBGP
> prefix paths in RIB = 9.55 x # unique eBGP prefixes).
>
> o BGPSEC adoption curve – truncated Normal distribution (slides 7-9).
>
> o RIB memory requirements (for the RR) are 0.5GB in 2016 to 8.3 GB in 2020 to
32
> GB in 2025 (worst case assuming RSA-2048 all the way; see Slides 14, 16).
>
> o But algorithm transition to ECDSA-256 likely (should happen) before 2020 [or
> perhaps even from Day 1 of BGPSEC deployment?].
>
> o Assuming such transition, 20 GB for RIB memory would be a conservative
> estimate –  good all the way out to 2025 (see Slide 25).
>
> Comments/suggestions are welcome.
>
> Sriram
>
> K. Sriram
> http://www.antd.nist.gov/~ksriram/
> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr
>

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Fri, 27 May 2011 13:58:20 -0400

Tom, 

Thanks for your comment. 
We have preliminary results that extend the RIB estimation (with BGPSEC) to 
LISP (or, similar map-and-encap type of protocols). 
That is, the scenario when LISP and BGPSEC are both in use.
I thought of sharing only the BGPSEC RIB modeling results for now.
Needless to say, in the scenario as you mention,
"outer routing headers for delivery to location, and inner routing headers for
delivery to the identified host", the RIB estimates for BGPSEC
would be much smaller for core PE routers or RRs.

Any thoughts on what a realistic timeline might be for adoption of 
LISP or ILNP (or any solution) for FIB scalability?
(Well, I hear you say - by the time the FIB size exceeds ~1M.)

Sriram

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of t.petch
> Sent: Friday, May 27, 2011 11:53 AM
> To: [email-masked]

-- snip ---

---

From: Tony Li <[email-masked]>
Date: Mon, 30 May 2011 11:44:01 -0700

Not to mention the fact that IPv6 is going to have a significant contribution.

Tony

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Tue, 31 May 2011 12:50:22 -0400

> Not to mention the fact that IPv6 is going to have a significant contribution.

I think you are saying (extending Tom's observation) that the transition to a 
FIB scalability solution possibly should happen sooner due to IPv6 growth
(as compared to that based on IPv4 growth considerations alone).
Whenever such transition occurs, it would be beneficial for BGPSEC
because engineered RIB capacity would be good for a far longer period.

The following related observations regarding the RIB model are worth noting.
The model assumes 15% yearly growth for # unique prefixes or total # prefix-paths.
Currently we do not explicitly break it down between IPv4 and IPv6.
Initially the bulk of the 15% growth would be due to IPv4 but one can expect that after a period of time, the IPv4 growth would trend down to a lower level while the IPv6 growth would contribute increasingly to the overall 15% yearly growth in announced prefixes.

The model is parameterized and further refined projections for 
IPv4 and IPv6 can be incorporated when available.

The BGPSEC RIB estimate for a given total # prefix-paths is minimally sensitive to the mix of 
IPv4 and IPv6. That is because a very high percentage of octets in a signed update is due 
to the signatures, and the sig size (for a given sig algorithm) is independent of IPv4 or IPv6. 

Sriram

-- snip --

---

From: Tony Li <[email-masked]>
Date: Tue, 31 May 2011 10:25:05 -0700

Not at all.  What I'm trying to say is that the IPv6 RIB is already growing at about 60% y/y.  Further, the transition to IPv6 _may_ trigger de-aggregation within the IPv4 RIB, as we maximize the utilization of the v4 address space.

Given these two factors, I'm highly skeptical of a 15% growth rate.

Tony

---

From: Randy Bush <[email-masked]>
Date: Tue, 31 May 2011 20:29:24 +0300

> Not at all.  What I'm trying to say is that the IPv6 RIB is already
> growing at about 60% y/y.  Further, the transition to IPv6 _may_
> trigger de-aggregation within the IPv4 RIB, as we maximize the
> utilization of the v4 address space.
> 

sriram was working on the effects of bgpsec on the growth rate, not
every other game being played in town.  give the man a break.

randy

---

From: Christopher Morrow <[email-masked]>
Date: Tue, 31 May 2011 13:42:47 -0400

> every other game being played in town.  give the man a break.

to be fair to both parties... the excel can be adjusted if you so
desire... (add/change/etc the routes data and watch the numbers really
get big!)

it does seem interesting to play with the numbers some, and depending
upon your particular mix of routes/paths see what damage you may bring
down.

---

From: "t.petch" <[email-masked]>
Date: Tue, 31 May 2011 18:41:34 +0200

----- Original Message -----
From: "Sriram, Kotikalapudi" <[email-masked]>
To: "t.petch" <[email-masked]>; <[email-masked]>
Sent: Friday, May 27, 2011 7:58 PM

> (Well, I hear you say - by the time the FIB size exceeds ~1M.)

Ah, you are much more ahead of the game than I realised:-)

I don't have any good data on LISP (or ILNP) except that I
expect that eventually LISP will sweep all before it.  It's a bit
like IPv6; we are out of IPv4 addresses so IPv6 is a must
so why can't I get an IPv6 service from any ISP whatsoever?  So
we run out of FIB space and noone does anything? seems
likely:-(.  Pick a figure from the air - 2020?

Tom Petch

---

From: Randy Bush <[email-masked]>
Date: Tue, 31 May 2011 20:44:32 +0300

> desire.

true.  and we could play with it to try to model lots of causes.  point
taken.

randy

---

From: Christopher Morrow <[email-masked]>
Date: Tue, 31 May 2011 15:33:24 -0400

> true.  and we could play with it to try to model lots of causes.  point

what I like it for is: "I see XX routes today, I think based on my
past I should see YY in 2 years, tell that engineering guy to tell the
procurement guy to get me more RAMZ!!!"

please use this in your measurements before buying gear, cause if it
takes you 5+ years to flip a piece of gear in/out of your network...
knowing NOW what you may need THEN would be good to tell vendors NOW
;)

-chris