Subject: [sidr] Scaling properties of caching in a globally deployed RPKI / BGPSEC system

From: Eric Osterweil <[email-masked]>
Date: Wed, 14 Nov 2012 22:47:57 -0500

Hey everyone,

A couple of us have done some quick back-of-the-envelope style calculations to help get an idea of what a global deployment of RPKI (supporting a global BGPSEC deployment) might look like, if we were to be able to deploy it.  We've written up our methodology, evaluation, and findings in a short little tech-note here:
	http://techreports.verisignlabs.com/tr-lookup.cgi?trid=1120005

What we tried to do was calculate an extreme _lower_bound_ on what the overall gather/fetch times might be for a cache trying to gather a fully deployed RPKI repository.  This seemed to be particularly opportune moment to raise this topic, re: some comments recently posted in the thread, ``Re: [sidr] additions and changes to agenda on Friday:''
>  1) size of a single repository (pick a large ISP as a for-instance,
> some one like L3 who has ~30k customers, each with 5 routes average x2
> for keyroll situations? - or better yet, make up your own set of
> numbers, document them and the reasoning why)
>  2) number of repositories in existence (say, number of ASN in the
> global table, or ...)
>  3) re-fetch times of every repository (3 hrs for instance for any
> object type?)
>  4) average network latency from fetcher to fetchee (~150ms for instance)
> 
> document that and then start looking at tradeoffs and consequences?

What we found is that by creating a  _systematic_ estimate of what a global RPKI would look like, we wind up with roughly 1.5 million objects (we explain why we feel this is a large _underestimate_ in the tech-note), and in order to ensure that all caches have received updated information (such as getting new certificates/CRLs/etc disseminated), repositories may have to wait about a month (roughly 32 days by our estimates), just for gatherers to reliably pick up a repo's changes.  Or, a month before a key compromise might get remediated throughout the RPKI system.

Our sincere hope is that this tech note will be a living document.  To that end, comments, corrections, and feedback are very welcome.

Eric

---

From: Bryan Weber <[email-masked]>
Date: Wed, 14 Nov 2012 23:29:45 -0500

I have quite a few questions/statements about this document. If you feel that this list is not the appropriate place to answer them please respond to me at [email-masked].  Thanks.

*) Aren't the EE certs contained in the Certificate, Manifest and ROA artifacts? Should they be counted as separate items to retrieve?

*) I'm not sure about the status of ghostbuster records today. Has any RIR implemented or deployed them yet? To my knowledge an RPKI repository contains CA certs with RFC 3779 extensions, manifests, CRLs and ROAs. Admittedly I am not familiar with the implementations of all of the RIRs.

*) Is there any reason that ARIN's pilot is listed? The service is deprecated and the production system is live at this point. Granted it probably does not have a large volume of data yet.

*) You note that 

"In addition, in regards to multihoming, we need one ROA and one EE certiﬁcate for each feasible origin for
a preﬁx, yet we will only see on entry in a RIB."

but on the other hand because of the maximum length in a ROA I believe that it is very difficult to surmise a relationship between the number of ROAs and the number of entries in the RIB.

*) Just as a side note, combining tables 1 and 2 might make the data easier to read. In separate tables I am forced to keep find the correlated rows.

*) Just for my own education, what are the router EE certs?

*) Another question: should the set of interconnected repositories be considered a directed graph or a tree hierarchy? Since the certs are hierarchical shouldn't the URIs pointing to external repositories be hierarchical as well?

*) Does cache synching have to be done serially?

If these estimates are accurate then the I think the current expiry periods of manifests in some of the RIRs would be considered woefully inadequate. 

Regards,
Bryan

On Nov 14, 2012, at 10:47 PM, Eric Osterweil <[email-masked]> wrote:

> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr

---

From: Arturo Servin <[email-masked]>
Date: Thu, 15 Nov 2012 02:36:34 -0200

Erick

	Very interesting research. But I am finding difficult to understand how
you got 1.4 M objects.

	Let me try to explain what I have seen in the young deployment of RPKI.
For simplicity let's use the "hosted" model of RIRs.

	Let's suppose, each RIR issues in average 1 certificate per member
containing all the resources (v4,v6,ASNs). I would say that there are
40,000 entities holding IP(4 and 6) prefixes and/or ASNs in the world
(same as number of ASs). What I have see is that most prefix holders
issue one roa with all the resources, but let's use 5 ROAs per
organization as average. Then we have:

40,000 certificates
200,000 roas
80,000 CRL,manifest
40,000 ghostbuster (not very deployed but let's count it)

	Am I missing something besides the Router EE? Or is the Router EE that
makes the difference?

	It seems that we agree that Ototal is the same equation, but the values
for Cas, Eas, etc. are different.
	
	But, anyways. It's aprox 350K objects. If we want to load all in 5
minutes (it would be good to define what is acceptable) we need to
deliver objects in less 0.00085 secs.
	
Regards,
as

---

From: Christopher Morrow <[email-masked]>
Date: Thu, 15 Nov 2012 00:23:32 -0500

1 quick note on the numbers below (I've not read the paper, just the commentary)

also, thanks to eric for making some work available, and taking a stab
at the numbers/sizing/speeding.

>         But, anyways. It's aprox 350K objects. If we want to load all in 5

x2 - keyrollover

-chris

---

From: Randy Bush <[email-masked]>
Date: Fri, 16 Nov 2012 21:38:14 +0700

first, thanks for getting a larger model started.

but i think many of the numbers are off.  i have had no time this last
week, and will not for another week.  so i will pick on just three, as
examples.

for bgpsec, i would assume a million routers each having the current
signing cert and the next one, i.e. two million total.  scattered over
O(100) repositories.

the best handle we have on rcynic time today is the ripe repository,
4,400 objects in 47 seconds, i.e. about .01 secs/obj.  and note that,
thank you rsync, time is seriously sub-linear in object count.

and a roa has it's ee cert built in for free.  so there is a factor of
two there.

i have not had time to look further, but i think, when numbers are a
factor of two to a factor of six off, and you are multiplying, a bit
more rigor is appropriate.

randy

---

From: Tim Bruijnzeels <[email-masked]>
Date: Fri, 16 Nov 2012 16:45:54 +0100

Hi,

Some more comments on the numbers and formula..

> for Cas, Eas, etc. are different.

I don't agree with the formula although my O total is closer..

The formula in the document confuses SIAs with the number of repository (rsync) servers.

Apart from any signed objects it may publish, every CA typically has:
= 1 certificate published by its parent
= 1 manifest
= 1 CRL
= 1 GB record (as Arturo said not widely deployed, but let's throw it in for full deployment)

So that's 4 objects.

During a key roll the CA will have the following additional objects:
= 1 cert published by the parent
= 1 manifest
= 1 CRL

Making 7 objects. But typically not all CAs roll at the same time.

The number of signed ROAs and Router certificates does, in my opinion, not depend on the number of CAs, but:
= ROA -> The number of announcements seen in BGP * some aggregation factor (1 / # average prefixes on one ROA)
= Router certs -> The number of ASNs * the number of keys for each ASN

So I think a better model would be to say:

number           object
#CA                 CA cert
#CA                 MFT
#CA                 CRL
#CA                 GB

#prefixes * X  ROAs

#ASNs * Y      Router certs

 Ototal  = 4 * #CA + #prefixes * X + #ASNs * Y

As for the numbers.. this is a bit of a guessing game.. we just really don't know at this time. We can take our best guess, but should keep in mind that our best guess is probably off, and needs re-evaluation in years to come.

 #CAs

If this were the total number of current members for all RIRs this number would be around 40k. However, there are also PI users that are not direct members of the RIRs, and some members will delegate some of their resources further. For reference I believe that in the RIPE region we have around 25k PI prefixes. I expect that a lot of the organisations that hold these resources will be happy to let a sponsoring RIR member (LIR in our region) manage their ROAs. But not all.. So I think that in a full deployment world this number may be significantly bigger. If anyone has any ideas on this, please chime in… Going on nothing more than gut feeling I would say the total could be in the order of: 
   
 = 40k RIR members plus 40k self managing PI holders / children of members?

   80k. 

#prefixes and 'X'

The number of announced prefixes is still rising. Currently we are nearing 500k.
Worst case X is 1, meaning every ASN - prefix combination has its own ROA.

In reality this number will be lower because we can and do aggregate. But not all implementers will do this. There is something to be said for *not* fate-sharing ROAs for different prefixes from the same ASN. Also, most our members are fairly small, and they do not do huge numbers of announcements individually. Our current aggregation rate -- and we really try... is:
  792 ROAs / (2197 IPv4 + 468 IPv6 prefixes) = 0.3 ROA/prefix

(see: http://certification-stats.ripe.net/) 

For scalability assessment I am not sure though that a factor of (1/0.3=) 3 between this level of aggregation, which seems best case, and no aggregation, worst case, is that significant in the big picture. I will use the mean of these two numbers below..

#ASNs * Y

The number of current ASNs is approx. 40k. I have no good idea about how many keys are needed at a single ASN. I know there was discussion about a single key per router, and re-using the same key for different routers. The suggested number 10 seems as good as any guess I could make. If anyone has more clue here, again, chime in please..

> 	But, anyways. It's aprox 350K objects.

Combining the above guesses I arrive at:

 O total = 4 * 80k + 500k * 0.65 + 40k * 10    ==> ~ 1M

> If we want to load all in 5

In principal I like the approach to turn this around and define what an acceptable average delivery rate would be given the total number of objects and the maximum sync time. But on the other hand this can lead to rejecting any infrastructure we could come up with.. just set the goals high enough and nothing will be enough. So I think we should be cautious here. If there are absolute objective minimal requirements it would be good to know them. But other than that it may be best to be pragmatic about it and turn this back.. try to think of other ways and see if they actually perform significantly better..

Bearing with the document, if we take the current rsync repositories as a starting point to see where we are heading without changes:
= It should be noted that fetch times depend on lay-out, hierarchical layout, allowing recursive, saves a lot of overhead (and latency)
= We *do* recursive fetches on all current RIR repositories (yes, we hacked in which base directory to use)
= Testing on my laptop I typically see fetch times of around 20ms per object, not 628ms

A full fetch based on today's numbers would then take 1M * 20 ms = 20k seconds = 330 minutes = 5.5 hours = 0.25 days.

So this is quite a bit faster. Eric, Danny how did you get to the numbers in table 3? Like I said: I just got some times from validation runs done on my laptop. We do collect data from our validators 'in the wild' though.. unfortunately the format of this data (we store a *lot*) is such that it will take some time for me to dig out more representative numbers. More time than I have now, but I will try….

Another important factor is the amount of RPs that we can expect.. I know that Rob and Randy et al are looking into ways to let RPs share data and be less reliant on central repository servers. On the other hand if all ASNs run at least 1 rpki validation cache that talks to the repositories directly then we're looking at 40k clients. If they want updates, say just 3 times per day, that's 120k requests per day, so something like 1 - 1.5 per second.

Our server scalability experiments that I talked about at the Vancouver IETF suggest that we would have a hard time scaling rsyncd to these numbers:
http://www.ietf.org/proceedings/interim/2012/07/27/sidr/slides/slides-interim-2012-sidr-5-0.pdf

= Slide #24.

NOTE: This slide does not show the time it takes for a relying party to download the repository.

This slide shows the happy case where all RPs are up to date, and they just check with the server to see if there are any updates. So importantly this does not include long running data transfers.. This is not server grade hardware (just a mac mini) but it's useful as an order of magnitude indication imo. We see that the total number of RPs just checking for updates that the server can handle / second depends linearly on the repository size (it needs to do an O(n) scan). The total number of concurrent RPs also depends on the repository size. It appears that some list / index is kept in memory for every connection. Long story short, we can only process small numbers of RPs per second and it's quite trivial to end up with too many concurrent RPs pushing the servers to the memory limited cliff for huge repositories.

It's because of this that I keep going on about:
= We should have a separate delta protocol and notification mechanism and not rely on rsync for this
= For scalability:
     = the hard work (CPU) should be done by the clients, not the server
     = it should be possible to offload connections & memory away from the server (proxies)
= It makes sense to look at http and scalability of existing CDNs for delivery

My gut feeling (yes it's involved a lot today) tells me that this SHOULD scale a lot better.. For example serving a small update notification file over http using a CDN, 10ks of request / second, easy.. Data transfer to RPs.. probably not a whole lot better actually if you need it all -- though using existing CDNs with a global infrastructure closer to RPs may help here. But if we have a notification file that points to small deltas and fetching these small files is cheap this may actually be a big improvement.. So although it may take a while to do the first sync, *staying* in sync may actually perform a lot better. Well.. all this is thought experiment at this stage. Without a pilot and actual measurements it's hard to be sure.

Regards

Tim

---

From: Arturo Servin <[email-masked]>
Date: Fri, 16 Nov 2012 15:34:11 -0200

A small comment about yours and Erick/Danny's number.

	Are you supposing #roas = #routes ?

	These is because you are assuming the worst scenario?

	Because in reality I have seen that operators are using a single ROA
for multiple prefixes.

Regards,
as

On 16/11/2012 13:45, Tim Bruijnzeels wrote:
> On Nov 15, 2012, at 5:36 AM, Arturo Servin <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
>> Erick
>>
> = ROA -> The number of announcements seen in BGP * some aggregation
> factor (1 / # average prefixes on one ROA)
> As for the numbers.. this is a bit of a guessing game.. we just really
> don't know at this time. We can take our best guess, but should keep in
> mind that our best guess is probably off, and needs re-evaluation in
> years to come.
> 
>  #CAs
> 
> If this were the total number of current members for all RIRs this
> number would be around 40k. However, there are also PI users that are
> not direct members of the RIRs, and some members will delegate some of
> their resources further. For reference I believe that in the RIPE region
> we have around 25k PI prefixes. I expect that a lot of the organisations
> that hold these resources will be happy to let a sponsoring RIR member
> (LIR in our region) manage their ROAs. But not all.. So I think that in
> a full deployment world this number may be significantly bigger. If
> anyone has any ideas on this, please chime in… Going on nothing more
> than gut feeling I would say the total could be in the order of: 
>    
> In reality this number will be lower because we can and do aggregate.
> But not all implementers will do this. There is something to be said for
> *not* fate-sharing ROAs for different prefixes from the same ASN. Also,
> most our members are fairly small, and they do not do huge numbers of
> announcements individually. Our current aggregation rate -- and we
> really try... is:
> For scalability assessment I am not sure though that a factor of
> (1/0.3=) 3 between this level of aggregation, which seems best case, and
> no aggregation, worst case, is that significant in the big picture. I
> will use the mean of these two numbers below..
> 
> 
> #ASNs * Y
> 
> The number of current ASNs is approx. 40k. I have no good idea about how
> many keys are needed at a single ASN. I know there was discussion about
> a single key per router, and re-using the same key for different
> routers. The suggested number 10 seems as good as any guess I could
> make. If anyone has more clue here, again, chime in please..
> 
> In principal I like the approach to turn this around and define what an
> acceptable average delivery rate would be given the total number of
> objects and the maximum sync time. But on the other hand this can lead
> to rejecting any infrastructure we could come up with.. just set the
> goals high enough and nothing will be enough. So I think we should be
> cautious here. If there are absolute objective minimal requirements it
> would be good to know them. But other than that it may be best to be
> pragmatic about it and turn this back.. try to think of other ways and
> see if they actually perform significantly better..
> 
> Bearing with the document, if we take the current rsync repositories as
> a starting point to see where we are heading without changes:
> = It should be noted that fetch times depend on lay-out, hierarchical
> layout, allowing recursive, saves a lot of overhead (and latency)
> A full fetch based on today's numbers would then take 1M * 20 ms = 20k
> seconds = 330 minutes = 5.5 hours = 0.25 days.
> 
> So this is quite a bit faster. Eric, Danny how did you get to the
> numbers in table 3? Like I said: I just got some times from validation
> runs done on my laptop. We do collect data from our validators 'in the
> wild' though.. unfortunately the format of this data (we store a *lot*)
> is such that it will take some time for me to dig out more
> representative numbers. More time than I have now, but I will try….
> 
> 
> Another important factor is the amount of RPs that we can expect.. I
> know that Rob and Randy et al are looking into ways to let RPs share
> data and be less reliant on central repository servers. On the other
> hand if all ASNs run at least 1 rpki validation cache that talks to the
> repositories directly then we're looking at 40k clients. If they want
> updates, say just 3 times per day, that's 120k requests per day, so
> something like 1 - 1.5 per second.
> 
> Our server scalability experiments that I talked about at the Vancouver
> IETF suggest that we would have a hard time scaling rsyncd to these numbers:
> This slide shows the happy case where all RPs are up to date, and they
> just check with the server to see if there are any updates. So
> importantly this does not include long running data transfers.. This is
> not server grade hardware (just a mac mini) but it's useful as an order
> of magnitude indication imo. We see that the total number of RPs just
> checking for updates that the server can handle / second depends
> linearly on the repository size (it needs to do an O(n) scan). The total
> number of concurrent RPs also depends on the repository size. It appears
> that some list / index is kept in memory for every connection. Long
> story short, we can only process small numbers of RPs per second and
> it's quite trivial to end up with too many concurrent RPs pushing the
> servers to the memory limited cliff for huge repositories.
> 
> My gut feeling (yes it's involved a lot today) tells me that this SHOULD
> scale a lot better.. For example serving a small update notification
> file over http using a CDN, 10ks of request / second, easy.. Data
> transfer to RPs.. probably not a whole lot better actually if you need
> it all -- though using existing CDNs with a global infrastructure closer
> to RPs may help here. But if we have a notification file that points to
> small deltas and fetching these small files is cheap this may actually
> be a big improvement.. So although it may take a while to do the first
> sync, *staying* in sync may actually perform a lot better. Well.. all
> this is thought experiment at this stage. Without a pilot and actual
> measurements it's hard to be sure.
> 
> 
> 
> Regards
> 
> Tim
> 
>

---

From: Eric Osterweil <[email-masked]>
Date: Fri, 16 Nov 2012 16:44:03 -0500

Hey Bryan,

Thanks a lot for the comments!  My thoughts are inline:

> *) Aren't the EE certs contained in the Certificate, Manifest and ROA artifacts? Should they be counted as separate items to retrieve?

afaik, EE certs are not contained in manifests.  Manifests enumerate things like EE certs, but they are separate objects (with a different cardinality).  I do believe that the cardinality of EE certs is 1:1 with ROAs.  Though, they are still separately managed objects and have different management overheads (like managing crypto information when reissuing, etc).

> *) I'm not sure about the status of ghostbuster records today. Has any RIR implemented or deployed them yet? To my knowledge an RPKI repository contains CA certs with RFC 3779 extensions, manifests…

Well, I think by the same token, not all ASes have deployed SIA repositories, or issued ROAs yet.  The goal of the document is to represent a global RPKI as prescribed.  In the future, if an AS is to run its own SIA (which I believe is envisioned to be far and away be the common case), I believe it _must_ have a ghostbuster record so that RPs can tell whose Cert they are dealing with.  There's no other way to (say) find the administrative contact for a routing object.

> *) Is there any reason that ARIN's pilot is listed? The service is deprecated and the production system is live at this point. Granted it probably does not have a large volume of data yet.

We only listed the repositories in the the cited presentation, but we felt it was important to include them all for completeness and to avoid bias.  We were trying to be unbiased and use the numbers and measurements that the BGPSEC design team has been publicizing.  I don't know what their metric was for including those measurements, but I suspect others in the wg could explain better.

> but on the other hand because of the maximum length in a ROA I believe that it is very difficult to surmise a relationship between the number of ROAs and the number of entries in the RIB.

It is, admittedly, a rough estimate, and we are totally open to other systematic measures.  However, to illustrate why it is tough to find a good estimate, while some aspects of using the RIB cause this number to seem large (as you have stated), consider also that the allocation/suballocation/subsuballocation hierarchy requires resource holders to issue a chain of certificates (from holder to holder to holder).  From there, a single entry in the RIB could correspond to multiple allocation objects.  This would inflate the number of objects, but we didn't see an obvious/clean way to estimate this either.  As such, we definitely acknowledge that this is an imperfect estimator, but we felt it was likely a good ballpark.  Make sense?

> *) Just as a side note, combining tables 1 and 2 might make the data easier to read. In separate tables I am forced to keep find the correlated rows.

Gotcha, thanks.

> *) Just for my own education, what are the router EE certs?

In BGPSEC, each router must be able to sign each update it transmits (originates and forwards).  The design team seems to have recently acknowledged that pushing a single organizational signing cert's private key to all routers in (say) a multinational AS could be a security concern.  As such, each CA can/should have separate EE certs issued for routers, such that these certs have their authority delegated from an organizational CA cert.

> *) Another question: should the set of interconnected repositories be considered a directed graph or a tree hierarchy? Since the certs are hierarchical shouldn't the URIs pointing to external repos…

Well, can you be sure that there will be no cycles in this envisioned set?  I, for example, cannot be sure that an object in one repo does not point to an external repo that in turn has an object that does not point back to the original. In fact, this issue is mentioned in the RPKI arch RFC (6480) as a possibility.  Nothing ever goes to plan in the Internet, so I think it is a very realistic concern.

> *) Does cache synching have to be done serially?

I believe the time estimates in the presentation that we cited are actual downloads, so I believe this is using whatever the current best practices are, though I admit the details were not 100% clear to me.

> If these estimates are accurate then the I think the current expiry periods of manifests in some of the RIRs would be considered woefully inadequate. 

Agreed. :(

Eric

---

From: Eric Osterweil <[email-masked]>
Date: Fri, 16 Nov 2012 16:44:22 -0500

Hey AS,

We are very open to feedback, but the numbers below seem to be derived somewhat more qualitatively than the estimations we used.  Would it be possible to frame the questions in terms of the numbers we estimated?  Clearly we acknowledge that anyone is 100% encouraged to agree with us, disagree with us, or create their own estimates, but I think the numbers below miss some the important aspects that we included in our evaluation.  If, perhaps, you think some of the justification is wrong in the tech-note, I'd be much obliged if you would point it out.  We tried very hard not to ballpark too many numbers, and use actual deployment statistics, as opposed to qualitatively evaluating.  We worried that being too qualitative may open up the possibility of measurement biases.  Would you mind taking a look at the reported methodology and estimates?

On Nov 14, 2012, at 11:36 PM, Arturo Servin wrote:

> (same as number of ASs).

And if an entity is a member of multiple RIRs?  I think that would inflate the above, but perhaps just claiming there are #AS Autonomous Somethings lets us use the CIDR report's 42,000. ;)

> What I have see is that most prefix holders
> organization as average.

See, I don't understand this generalization. You can't have one ROA for non-overlapping allocations, so we already know the above is not a good mapping.  I don't know why we would guess 5.  That's why we chose a systematic estimator.  I'd be happy to look at others, but this seems a little too qualitative for this type of estimation (imho).  Also, there's no discussion of router EE certs below (except acknowledgement of their omission) From here, I think the numbers are based on a foundation I have trouble following, so I think it might be easier to frame this discussion on replacing/addressing the estimates we were using?

Thanks,

Eric

> Then we have:

---

From: Eric Osterweil <[email-masked]>
Date: Fri, 16 Nov 2012 16:44:36 -0500

> On Nov 15, 2012, at 5:36 AM, Arturo Servin <[email-masked]> wrote:

<snip>

> = 1 certificate published by its parent

But, as I asked Arturo, would we expect to have a CA from each parent (i.e. each RIR that an org may allocations from)?  While this may often still just be 1, it seems important to note, no?  THat was one reason we had for breaking it apart.  I'm more than willing to believe that I'm wrong here, but I'd like to understand how. 

> = 1 GB record (as Arturo said not widely deployed, but let's throw it in for full deployment)

How does the RPKI certify ASN allocations?  This is needed to certify router EE certs (they are tied to an ASN, no?).  Such an AS cert would add another 1 to the above and make it 5, right?  Otherwise, how does a forward signing peer associate itself with the ASN, instead of some prefix?  The ASN isn't necessarily allocated by the same RIR as any of the allocations, so IP allocation and ASN allocation are orthogonal, no?

> Making 7 objects. But typically not all CAs roll at the same time.

Unless it is an algorithm rollover, and that is expected to last for years (iirc).  Then this set would be doubled (plus double the numbers below), right?

> 
> The number of signed ROAs and Router certificates does,

And EE certs.  While 1:1 with ROAs, they require additional (very different) processing, esp if you start down the road of HSMs.  So, we claimed this additional operational requirement means that even if you double up on the downloads, those are still two separate objects.  You have to manage EE rollover keeping crypto material the same or changing it, depending on details of the ROA, etc.  That won't come for free, and (again) needing HSMs makes this a big deal.  So, we really felt it was important to call this complexity out by counting each. 

> in my opinion, not depend on the number of CAs, but:

I, pretty much agree with this (as I think the tech-note said).  I do, however have to note that with MOAS, you need multiple ROAs.  Small point, but worth stating. :)

> = Router certs -> The number of ASNs * the number of keys for each ASN

\times The number of eBGP speakers you mean, right?

> So I think a better model would be to say:

Ack, we just estimated this as the # of SIAs, and then varied it from 5 to 42,000.

> #prefixes * X  ROAs

Yeah, but we didn't guestimate the $X$ value.  It sounds like we should, but is there any data we can use to do so?

>  Ototal  = 4 * #CA + #prefixes * X + #ASNs * Y

Re: the above, I think this would be 

O^Total = 4 * #CA + #ASNs + #prefixes + X * #prefixes + Y * #ASNs

We had called out the need for AS EE cert (which was not in the equation you outlined), and we felt it was important to not omit EE certs (if for no other reason than the operational complexity they bring).

> As for the numbers.. this is a bit of a guessing game.. we just really don't know at this time. We can take our best guess, but should keep in mind that our best guess is probably off, and needs re…

100% agree.  That is why we called this a back-of-the-envelope calculation and are totally seeking feedback, and are absolutely interested in pushing revisions as things evolve.

>  = 40k RIR members plus 40k self managing PI holders / children of members?

Really?  I had been thinking that this number was tied to the origins, but I can see your logic.  It would great to try and find a way to estimate this, so I'd like to echo your request for anyone with info to chime in.

> For scalability assessment I am not sure though that a factor of (1/0.3=) 3 between this level of aggregation, which seems best case, and no aggregation, worst case, is that significant in the big…

Fair enough.  I can certainly see the logic here, but if we wound up with a good way to do the estimation that would be even better, no? :)

<snip>

> In principal I like the approach to turn this around and define what an acceptable average delivery rate would be given the total number of objects and the maximum sync time. But on the other hand…

I can respect this concern, but we really do have to deal with any systemic/complexity/operational/etc. facets of the system that we have designed.  We need to know how this design is going to behave if we are going to enshrine it.  For example, the above calculations, and ours, and any derivative formulation would make revoking a key within an hour seem to be impossible.  Is it a day, a week, a month, etc?  That may still be unclear (depending on how we model this), but how can we go any farther forward without taking a careful look at this design?  We must know if it meets our requirements, and I think measurements like these help tell us how feasible this will all be.

> = Testing on my laptop I typically see fetch times of around 20ms per object, not 628ms

To be perfectly fair, I just used the #s I found form the BGPSEC design team's measurements.  I was very hesitant to use any particular set of numbers here.  As I'm sure you know, there are opinions about rsync, what it looks like under load, with asynchrony, repos' operational uptimes, restarting because of changes in the repository (I think that was something from your preso), etc.  I think you likely know (much better than me) that if a repo is under heavy load, churn, or just having an outage, that can cause cache's sync time to suffer.  Hence, I really liked getting real operational data from non-lab measurements.  I actually really feel that data is quite useful.  Consider this, you all (who are running these things) are the experts.  If we wind up w/ ~42,000 repos, they will _not_ all be run as well as you run them.

> A full fetch based on today's numbers would then take 1M * 20 ms = 20k seconds = 330 minutes = 5.5 hours = 0.25 days.

Sorry, but I really think this has some problems.  First, the numbers I see in the cited preso are way larger than this, and just for the object sets we see today.  So, I have to say that this calculation doesn't seem to jive with Randy's numbers.

> So this is quite a bit faster. Eric, Danny how did you get to the numbers in table 3? Like I said: I just got some times from validation runs done on my laptop. We do collect data from our validato…

The citation at the end of the document comes from Randy.  It shows (MRT?) graphs with these numbers on them.  This doesn't include issues like repos under load from 42,000 caches DNS, outages, etc.  I think the numbers taken from his preso are very charitable, and they are actual measurements.  Moreover, his own experiments showed that replicating this all inside a ``fairly large scale'' experiment took 660 minutes by itself... and that was with just 14,000 objects.  This actually totally contradicts the numbers you calculated above.  Sorry, I think it just doesn't add up.

> Another important factor is the amount of RPs that we can expect.. I know that Rob and Randy et al are looking into ways to let RPs share data and be less reliant on central repository servers. On…

Again, I used Randy's numbers and even his experiments on 14k objects on a small topology show it takes twice as long as your global estimates.

> This slide shows the happy case where all RPs are up to date, and they just check with the server to see if there are any updates. So importantly this does not include long running data transfers..…

Yeah, I was wondering about that.  It felt like it was beyond my perspective to estimate, so I tried to focus this sizing analysis on a more general systemic view.  I totally appreciate the above comment, but maybe we could try to model that in another tech-note?  I'm happy to try and help, if you would like.

> = It makes sense to look at http and scalability of existing CDNs for delivery

ibid.

> My gut feeling (yes it's involved a lot today) tells me that this SHOULD scale a lot better.. For example serving a small update notification file over http using a CDN, 10ks of request / second, e…

I really think these are they types of conversations that we should be having.  Thank you very much for putting your thoughts here!

Eric

---

From: Eric Osterweil <[email-masked]>
Date: Fri, 16 Nov 2012 16:50:16 -0500

> week, and will not for another week.  so i will pick on just three, as

Great, thanks.

> signing cert and the next one, i.e. two million total.  scattered over

Really?  I didn't realize such a large estimate was the case.  Do others agree with the 1m.  Also, the standby cert is a good point, I hadn't factored that in.

> thank you rsync, time is seriously sub-linear in object count.

I just used the numbers that I think you measured and presented at NANOG, etc.  You had some sync performance graphs with average #objects and average sync time in the lower right/left corners.  I just used those, but that made things seem a little more bleak.

> and a roa has it's ee cert built in for free.  so there is a factor of

I just put some text to the rationale behind calling this out separately into an email to Tim (on list).  Rather than re-type, maybe we can converse over that?

> more rigor is appropriate.

I'm totally happy to address the formulation.  It could, very well, be off.  However, I think having such a formulation is critical, so can we talk about evolving what's there to something that lets us measure?

Thanks,

Eric

---

From: Bryan Weber <[email-masked]>
Date: Sat, 17 Nov 2012 08:34:20 -0500

Eric,

More comments in line:

> Thanks a lot for the comments!  My thoughts are inline:

No problem. I'm happy to provide feedback.

> afaik, EE certs are not contained in manifests.  Manifests enumerate things like EE certs, but they are separate objects (with a different cardinality).  I do believe that the cardinality of EE cer…

Yes the manifest enumerates the certificates, ROAs and CRL associated with (or signed by) the certificate, but it also contains an EE cert.

From RFC 6486 that describes the RPKI Manifest:

Every RPKI signed object includes, in the Cryptographic Message
   Syntax (CMS) [RFC3370] wrapper of the object, the EE certificate used
   to verify it [RFC6488].  Thus, there is no requirement to separately
   publish that EE certificate at the CA's repository publication point.

It does recommend a one time use EE cert.

And yes, ROAs do have a 1:1 cardinality with an EE cert assuming a one time cert as the RFC recommends. The ROA is also a CMS object that always contains an EE cert. For performance reasons an EE cert could be re-used to prevent the expensive key generation portion on the crypto side.

> Well, I think by the same token, not all ASes have deployed SIA repositories, or issued ROAs yet.  The goal of the document is to represent a global RPKI as prescribed.  In the future, if an AS is…

Certainly not all of them have. :) But point taken on what you are trying to accomplish.

> We only listed the repositories in the the cited presentation, but we felt it was important to include them all for completeness and to avoid bias.  We were trying to be unbiased and use the number…

OK, so this was just point in time data. 

> It is, admittedly, a rough estimate, and we are totally open to other systematic measures.  However, to illustrate why it is tough to find a good estimate, while some aspects of using the RIB cause…

I think that a heuristic, like average, is probably the only way this estimate can be done, but likely we'll need more participation to get enough data for the average to be statistically significant (my guess). I would also expect to see a power law distribution here (again my guess).

> In BGPSEC, each router must be able to sign each update it transmits (originates and forwards).  The design team seems to have recently acknowledged that pushing a single organizational signing cer…

And the intent of the EE cert is to verify the transmitted updates? I'll have to read up a little more on this side of the specs, but I'm assuming that the EE private key associated with the EE cert must be kept by the router to sign the updates? I could be way off base here, I'll go read more like I suggested. :) 

> Well, can you be sure that there will be no cycles in this envisioned set?  I, for example, cannot be sure that an object in one repo does not point to an external repo that in turn has an object t…

OK, I see and I agree. I can envision business partnerships that could lead to this sort of scenario. 

Thanks,
Bryan

---

From: Randy Bush <[email-masked]>
Date: Sat, 17 Nov 2012 21:48:11 +0700

> if an AS is to run its own SIA (which I believe is envisioned to be
> far and away be the common case)

quite the opposite.  the vast majority of ASs will likely use the RIRs'
or a tier-1's hosted model.  look at the euro region today, a thousand+
in the ncc repository and three or four playing with up-down.

randy

---

From: Eric Osterweil <[email-masked]>
Date: Sat, 17 Nov 2012 16:20:43 -0500

> in the ncc repository and three or four playing with up-down.

Hey Randy,

Heh, my crystal ball is clearly neither as big nor as shiny as yours is. ;)  Kidding, actually, I really don't claim to know this, which is why we modeled deployments with 5, 10, 100, 1,000, and 42,000 repos.  As you should be able to see from Figure 1 in our tech-note, this results in only about a 10% difference in gathering time (significant, but still leaves us in the same ballpark).  Our hope with this measurement was to accommodate differences in opinions between all of our crystal balls by evaluating the spectrum of possibilities here. :)

Though, as you and others have pointed out, some of our model's numbers might need some work.  For example, I think you pointed out that our estimates for the number of router certs appears to be an order of magnitude too small.  We are currently culling corrections so that we can update the tech-note.

Eric

---

From: Christopher Morrow <[email-masked]>
Date: Tue, 20 Nov 2012 00:04:48 -0500

>> in the ncc repository and three or four playing with up-down.

I think that even if you use a hosted service, your URL is probably
going to evolve into a separate connection from mine on the same
hosted model. That single hosted URL seems like a great target to poke
at with the ddos-cannon :(

In the DNS world, many folk use different /24's for each set of
cctld/etc NS hosts, when folk like godaddy/worldnic do NOT we learn
how much of the internet namespace lives behind their ips :(

(note that both providers above have more than 2-4 ips in play, but
all of them have many resources behind a shared smaller set of
targets)

> Heh, my crystal ball is clearly neither as big nor as shiny as yours is. ;)  Kidding, actually,
> I really don't claim to know this, which is why we modeled deployments with 5, 10, 100,
> 1,000, and 42,000 repos.  As you should be able to see from Figure 1 in our tech-note,

in the end, modeling at 42k is the 'worst case' right? (worst today,
tomorrow it'll be 42001, of course).

-chris

---

From: Eric Osterweil <[email-masked]>
Date: Tue, 20 Nov 2012 14:26:38 -0500

> tomorrow it'll be 42001, of course).

Exactly.

Eric

---

From: Tim Bruijnzeels <[email-masked]>
Date: Fri, 23 Nov 2012 17:26:32 +0100

Hi Eric,

Sorry for the late response..

With regards to some of your comments regarding requirements and ideas for alternative deltas, some responses inline below, but other than that see the thread where both Bryan Weber and I talk about our ideas. This is somewhat separate from the questions about "how a fully deployed RPKI tree would look like", and "what churn we might see" and "how many connecting RPs, and how frequent". All that can feed into requirements, but is in essence another discussion, so I suggest we keep them separate.

> How does the RPKI certify ASN allocations?  This is needed to certify router EE certs (they are tied to an ASN, no?).  Such an AS cert would add another 1 to the above and make it 5, right?  Otherw…

Okay, let me rephrase.. it gets confusing when talking about organisations as CAs, and CA certificates: i.e. certificates that have the CA bit set and can sign and publish other certificates, signed objects etc.

We're talking 4 objects for each CA Certificate:
= 1 CA Certificate with IPv4, IPv6 and/or ASN
= 1 mft
= 1 CRL
= 1 GB

An organisation may have more than one CA certificate:
= if it has different parents and get certificates from more than one
= if it has 'minority space'. For example if one of our members has resources for which another RIR is the majority holder, then this is not on our normal certificate. We get a certificate with all such resources signed by the other RIR, and then we use this to sign an additional certificate for this member. Certificates can have only one parent, so we can not merge this.

Regarding the second point: I haven't done detailed analysis on our data yet. This does affect at least a portion of our members, so the average number of CA certs per member organisation is more than 1. I expect that it will not be a *lot* higher, but like I said I haven't analysed the data yet.

Having said that, it seems that the relative component of these, in a sense, boilerplate objects of the total count, are of a different order than the amount of expected ROAs and router certificates.

> Unless it is an algorithm rollover, and that is expected to last for years (iirc).  Then this set would be doubled (plus double the numbers below), right?

I did not consider algorithm roll over, but I think you're right.

> And EE certs.  While 1:1 with ROAs, they require additional (very different) processing, esp if you start down the road of HSMs.  So, we claimed this additional operational requirement means that e…

I don't understand the use of EE certs and HSMs here. And I don't see how this can significantly raise the object count.

In the rpki EE certs can only be used to sign rpki signed objects and they are embedded in those objects, not published separately.

All keys in our online system are protected by HSMs. The keys in EE certificates even more so: they are generated in an HSM, used only once, and then forgotten. In the online system the HSM protects against key theft if an attacker somehow gets access to the database/file system.. The will not be able to export the keys without access to a quorum of key cards that protect the internal key of the HSM.

If you want to use an *offline* key protected by an HSM, then you would have an additional CA cert (and mft, crl and gb). This is what we do with our TA at least:

TA (offline) -> signs CA cert for online use => signs member CAs

The idea being that if the worst happens to our online system, we can rebuild and re-issue using the more secure offline key. The hosted members don't have their own offline key, they are protected by the same one.. Non-hosted CAs may want to use an intermediate offline certificate. This adds some overhead: 4 objects per offline key (CA cert, mft, crl, gb). 

> I, pretty much agree with this (as I think the tech-note said).  I do, however have to note that with MOAS, you need multiple ROAs.  Small point, but worth stating. :)

Yes, a ROA can have one ASN only, but multiple prefixes.

We aggregate prefixes for the same ASN as much as we can on a single ROA. So far we are managing a factor of around 3 prefixes per ROA. Lacnic is similar. The other RIRs seem to aggregate a bit less at this time.

See here:
http://certification-stats.ripe.net/

> \times The number of eBGP speakers you mean, right?

Yes. My model assumes that this number of speakers can related to the number of ASNs.

Randy suggested a number of physical bhp sec speaking routers and that they may have two keys. That may well be a better model.

> Ack, we just estimated this as the # of SIAs, and then varied it from 5 to 42,000.

5 here would mean the current RIR TAs without any other signed content.

The total object count for this depends on the number of CA certs. See my previous best estimate below.

> To be perfectly fair, I just used the #s I found form the BGPSEC design team's measurements.  I was very hesitant to use any particular set of numbers here.  As I'm sure you know, there are opinion…

I understand your concern about many repos, some of them small and possibly not well managed.

But the number of repos is not 1:1 the number of organisations acting as CAs.

We currently see 5 different repositories for the hosted solutions provided by the RIRs. Non-hosted is being worked on, but so far not done in the production environment. When this arrives, some non-hosted people will want to do their own publishing, some others will use a bigger repository, for example with their RIR, or it may be that 3rd parties will start providing this service. In any case 42k repositories seems a bit much, though more than 5 is very likely.

> Sorry, but I really think this has some problems.  First, the numbers I see in the cited preso are way larger than this, and just for the object sets we see today.  So, I have to say that this calc…

As you can read in my other emails I agree in general. I don't think rsync can scale to the levels we need.

But the numbers on today's *small* repositories can be improved a lot by making them hierarchical, or if your validator happens to know that it can use a higher directory. We do that last thing, rcynic does not. We made our repository hierarchical though.

I think Randy's numbers may be outdated and represent the totals for our old *flat* rsync repo. This adds a huge amount of latency and setup overhead.

The numbers I got was by just running our validator* and watch the log for lines like:
16:51:12,883 INFO  Prefetching 'rsync://rpki.ripe.net/repository/'
16:52:06,980 INFO  Done prefetching for 'rsync://rpki.ripe.net/repository/'
16:52:26,189 INFO  Finished validating RIPE NCC RPKI Root, fetched 4447 valid Objects

So the crypto took 20 seconds. The fetching of 4447 objects took 54 seconds => 12 ms/object. For Lacnic: 280 objects in 5 seconds => 17 ms/object from my laptop on a wireless in Amsterdam to South America.

*: http://www.ripe.net/lir-services/resource-management/certification/tools-and-resources

> Again, I used Randy's numbers and even his experiments on 14k objects on a small topology show it takes twice as long as your global estimates.

We are talking about different things here:
= You're looking at how long it takes for 1 RP to get in sync.
= I was referring to the number of RPs that a repository can expect to connect per second.

> Yeah, I was wondering about that.  It felt like it was beyond my perspective to estimate, so I tried to focus this sizing analysis on a more general systemic view.  I totally appreciate the above c…

This is one of the main reasons why I think that rsync won't scale to the needs we can expect in full deployment. Even if all RIR repositories are hierarchical, and we don't see a lot of non-hosted CAs publishing elsewhere. We can not expect to keep getting that number of say 20 ms/object.. Not without very *huge* investments in setting up some home grown rsync CDN, spreading them like very busy root servers over the world. Not something that the non-hosted folk will likely want to do either btw..

Then regarding non-hosted CAs not publishing in their RIR repository.. I hadn't really thought of this before, but he advantage of the recursive rsync is lost here. Say 5 organisations do non-hosted and they all publish with a 3rd party providing a repository service.. they are siblings. This repo is flat.

So apart from the other things I list in the document I sent yesterday, I think we have a requirement that the delta protocol is not dependent on the PKI hierarchy.

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Tue, 27 Nov 2012 18:17:48 -0500

This email is somewhat long. 
So I also have a tech-note (pdf) version of this (including the table, figure, etc.).
If you prefer to read it in the tech-note format, you may skip the rest of this email and click:
http://www.nist.gov/itl/antd/upload/rpki-rsync-delay-technote.pdf
 
Hi Eric,

These are comments from Doug and I.
We have read your/Danny's tech-note and also followed the email thread. 
Thank you for the study. We have several comments.

A. Consideration of a range of basic rsync fetch time measurements (seconds/object):

Regarding the basic rpki rsync measurement of fetch time (seconds per object), 
there seems to be more evidence that it could be a lot faster than the measurements 
you have used from Randy's NANOG presentation. Tim has reaffirmed once again 
in his most recent post ( http://www.ietf.org/mail-archive/web/sidr/current/msg05369.html ) 
that the fetch times seem to be in the range of 10 to 20 ms per object rather than 
the 628 ms that you've used. Tim mentions that "Randy's numbers may be outdated 
and represent the totals for our old *flat* rsync repo. This adds a huge amount of latency 
and setup overhead." Randy also separately mentioned the updated 10 ms/object 
measurement in one of his responses to your original post.
  
So we thought it would be good to redo your total RPKI rsync delay numbers considering 
these lower measurements from Tim/Randy. The resulting table and plot are shown 
in slides 1 and 2 at this link:
http://www.nist.gov/itl/antd/upload/RPKI-rsync-delay.pdf 

As you can see from Table 1, for the same number of total rpki objects (approx. 1.5M) 
that you have used, the total rpki rsync delays is only about 4 hours and 8 hours, respectively, 
for 10 ms/object and 20 ms/object, which are 63 and 31 times smaller, respectively, 
as compared to the 260 hours number in your table. 
A plot of the data in Table 1 is shown in Figure 1. Note that both axes are logarithmic.

It is also important to note that a running RP fetches only *changed* RPKI objects 
during each polling instance in normal (steady-state) operation 
(i.e., whatever the delta happens to be since the previous polling instance). 
The RP would download *all* RPKI objects rather rarely, e.g., when there is a restart 
(i.e., failure recovery). So the common fetch delay seen at RPs would be 
more like seconds or minutes as shown in the lower left corner of plot on slide 2 
(or, top of the table in slide 1), corresponding to fetches of 100 to 10,000 changed rpki objects.

B. Estimate of RPKI repositories:

It is known that 84% of all ASes are stub, and 16% are non-stub. So about 35,280 are stub ASes 
and only 6,720 are non-stub. The stub ASes are likely to only run simplex bgpsec and 
they would likely contract out publication point service to their upstream ISP or a third party 
(Tim also observed this). Even many non-stub ASes can be expected to do the same. 
So in the end, we think the total number of repositories (what you call SIAs) 
will be O(100) or O(1000), much less than the 42,000 you have assumed.

C. Number of router certs:

Observe that per-router certs are not required; certs can be per AS. It remains to be seen 
what granularity (ranging from per AS to per router) will be used. But, for worse case, 
if we assume per-router certs in all ASes, then a conservative estimate can be obtained as follows. 
The stub ASes will have a low average # eBGPSEC routers (say, 2 per AS), 
and the non-stub ASes will have a relatively larger value for the same (say, 20 per AS). 
Then the total number of eBGPSEC routers can be estimated at 204,960 (= 20*6720 + 2*35280).  
You had assumed 420,000 (10 x 42,000). Also, there should be 4 certs per *non-stub* eBGPSEC router; 
one pair (current and next) for origination prefixes and another pair (current and next) for transit ASes 
(please see draft-rogaglia-sidr-bgpsec-rollover and draft-sriram-replay-protection-design-discussion). 
And there should be only 2 certs per *stub* eBGPSEC router since it does not have transit prefixes. 
That gives us an estimate of 678,720 (=4*20*6720 + 2*2*35280) for the total # router certs. 
We think this number is conservative (high) but reasonable for now.

D. Time for caches to receive updated RPKI info:

Quoting from your original post in this thread:

> in order to ensure that all caches have received updated information 
>(such as getting new certificates/CRLs/etc disseminated), 
>repositories may have to wait about a month (roughly 32 days by our estimates), 
>just for gatherers to reliably pick up a repo's changes.  
>Or, a month before a key compromise might get remediated throughout the RPKI system.

We find it hard to understand your assumptions and computation here 
(including the details about this in your tech-note). Here we should focus on fetching only 
the delta (changes) since the last fetch. From my table (slide 1), the delta fetch should take 
only seconds to minutes (also noted above in comment A for fetches of RPKI changes 
up to 1000 or 10,000 objects).  If you factor in time-jittered polling from caches once every z hours, 
then the delay is of the order of z hours for the caches to fetch updated info from the time 
the info is available at the publication points. 
Clearly, Randy's NANOG results (60 to 80 minute delay range) are dominated by 
the one hour jitter on polling gatherers. It seems that the major contributing factor 
is the polling interval and not the workload at the publication points.

E. Characterizing the Size and Shape of RPKI (pointer to a NIST study):

Okhee Kim (colleague at NIST) had led an effort to characterize the size and shape of 
a deployed RPKI a couple of years ago. She based it on measurements of 
address space registrations (inet-num in RPSL, NetHandle in SWIP), 
AS registrations (aut-num in RPSL, AS-Handle in SWIP) and route object registrations (in IRRs, RADB). 
The presentation slides of this study can be accessed at:
http://www.nist.gov/itl/antd/upload/RPKI-size-shape-modeling.pdf  
This work was done almost two years ago and we haven't had a chance to 
update the results since then. But you may glance through the slides just to get an idea. 
There are some interesting analyses and insights reported in the presentation.      

We hope that the comments/analysis offered here are helpful.

Sriram

---

From: Randy Bush <[email-masked]>
Date: Wed, 28 Nov 2012 15:18:14 +0900

thank you.  this makes a lot more sense than taking well-known
exteme worst cases (since fixed) and using them to calculate a
so called 'lower bound.'  your document looks like responsible
engineering and describes about the numbers we have been
expecting and talking all along.  thanks.

randy

---

From: Russ White <[email-masked]>
Date: Wed, 28 Nov 2012 07:40:47 -0500

> will be O(100) or O(1000), much less than the 42,000 you have assumed.

Several points:

1. It is never a good idea to "just right" engineer a system to the
"best available numbers from today." Yes, I know the old saw about the
glass being neither half empty nor half full, but overengineered --but I
also know that virtually every system that counts on a specific traffic
pattern, or a specific rate of usage, finds those underlying assumptions
completely and totally wrong.

2. If I ran a large network (like a big financial, or major traffic
sink), I would never hand my certificate advertisement over to my SP. If
I've taken the time and trouble to get my own addresses in order to
maintain some level of independence from my provider, I wouldn't undo my
independence by using that same provider as the point of advertisement
for my routes in a system that can take 4+ hours to synchronize (only in
SIDR do we talk about minutes and hours as if they are "short"
convergence times).

3. So, I would assume a much higher number than the O(1000) you're
assuming here, and bring the number closer to the 40,000 contained in
the original process.

> We think this number is conservative (high) but reasonable for now.

I don't think this is right, either --you're assuming a "stub AS" will
only have two routers, which is completely off base. The smallest stub
AS will have two routers, larger ones will have more as they scale
upwards. Several large enterprise networks I've worked on have at least
20, if not more, edge routers across a single AS, into multiple providers.

The size of a transit is also questionable --I can't imagine an average
of 20 edge routers for a transit provider. Are there really so many 2
and 3 edge router transits that it would offset AT&T, Level 3, and many
others we know must be on the order of hundreds of edges?

204k eBGP speakers is a gross understimate of the size of the Internet
at large.

Russ

-- 
<><
[email-masked]
[email-masked]

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Thu, 29 Nov 2012 19:40:59 -0500

>can take 4+ hours to synchronize (only in SIDR do we talk about minutes and
>hours as if they are "short"
>convergence times).

As has been noted before, a *running* rpki cache server has low delays at each
polling instance (see top of Table 1 for 100 up to 10,000 *changed* RPKI objects). 
For a *new* rpki cache server that is starting up and fetching all 1.5 million objects, 
the rpki rsync delay is larger (4 hours). Routers would not be using this *new* server 
until it signals it is ready to serve. In the meanwhile, routers are being served
by other *up and running* rpki cache servers.

>
>3. So, I would assume a much higher number than the O(1000) you're assuming
>here, and bring the number closer to the 40,000 contained in the original
>process.

As Eric has also shown, it makes a difference of only about 10% in the total rpki rsync delay
when you increase the # SIAs (repositories) from 5 to 42,000. 
BTW, just to note here again Tim's comment to Eric about this, 
"In any case 42k repositories seems a bit much, though more than 5 is very likely." 

>> C. Number of router certs:
--snip --
>I don't think this is right, either --you're assuming a "stub AS" will only have two
>routers, which is completely off base. The smallest stub AS will have two
>routers, larger ones will have more as they scale upwards. Several large
>enterprise networks I've worked on have at least 20, if not more, edge routers
>across a single AS, into multiple providers.
>
>The size of a transit is also questionable --I can't imagine an average of 20 edge
>routers for a transit provider. Are there really so many 2 and 3 edge router
>transits that it would offset AT&T, Level 3, and many others we know must be
>on the order of hundreds of edges?
>
>204k eBGP speakers is a gross understimate of the size of the Internet at large.

Would you like to share a ball park number you know that is a better estimate
for the # eBGP speakers? It is a parameter in the model; so easy to rerun.

Sriram

---

From: Russ White <[email-masked]>
Date: Fri, 30 Nov 2012 11:50:12 -0500

> by other *up and running* rpki cache servers.

So the routing system is being secured by information that is at least
several minutes behind actual topology changes. What impact will this
have on the overall number of updates, speed of reachability, etc. --and
what's the business impact?

We don't live in a world of minutes and hours any longer.

> for the # eBGP speakers? It is a parameter in the model; so easy to rerun.

I would guess at least 6 per stub as.

For transit AS' --if you look at the maps on navigators.com, you'll find
every ISP on there shows at least 50 interconnect points, each of which
is at least 1 router --and this doesn't count private peering points. So
I would say 50 is a minimal number, and something larger is probably
more likely.

But again, this all predicated on current numbers --building scaling
around, "this is what we have today," is a recipe for disaster within a
matter of years.

Of course, SIDR has never cared about what happens ten years from now,
since that's beyond the time horizon for the actual goals at hand.

Russ

---

From: "Montgomery, Douglas" <[email-masked]>
Date: Fri, 30 Nov 2012 13:10:14 -0500

>We don't live in a world of minutes and hours any longer.

RPKI does not reflect run-time changes in topology.   It is a declarative
system in which one would expect information to typically change with
human driven processes (e.g., allocation of addresses, establishment of
peering relationships, etc.)

Routing itself can proceed at the speed of light.

>since that's beyond the time horizon for the actual goals at hand.

? SIDR has never cared about what happens in the near term ... Where did
you get this idea.

---

From: Russ White <[email-masked]>
Date: Fri, 30 Nov 2012 13:23:39 -0500

> Routing itself can proceed at the speed of light.

Given BGP is actually mostly about policy, what you're saying is:

"Policy (routing) can move at the speed of light, even though policy
(human action) can't/won't."

Somehow I find this to be a distinction without a difference.

The RPKI needs to react in seconds, rather than minutes, hours, or days.

Russ

---

From: Christopher Morrow <[email-masked]>
Date: Fri, 30 Nov 2012 13:37:08 -0500

> what's the business impact?

You mean ROA updates, for instance... or router/asn ee-cert, right?
should the expectation be that you can start announcing and using a
prefix in seconds or is a more planned process to be expected?

---

From: "Montgomery, Douglas" <[email-masked]>
Date: Fri, 30 Nov 2012 13:37:04 -0500

>Somehow I find this to be a distinction without a difference.

That is not what I was saying ... And it seems a bit confused.

Policy never has, nor likely never will move at the speed of light.
Policy by definition is a reflection of human intent.

Routing moves at the speed of bits, while passing through what are
typically relatively static policy filters and functions.

Not sure what you are referring to, unless it was just a fun semantic
transformation, when you say policy moves at the speed of light.

>The RPKI needs to react in seconds, rather than minutes, hours, or days.

Based upon what analysis or requirement?

dougm

---

From: Christopher Morrow <[email-masked]>
Date: Fri, 30 Nov 2012 13:38:19 -0500

> since that's beyond the time horizon for the actual goals at hand.

this isn't a particularly useful line of commentary, could we stick
with the problem we're discussion and leave editorializing out?

---

From: Danny McPherson <[email-masked]>
Date: Fri, 30 Nov 2012 14:00:43 -0500

> Based upon what analysis or requirement?

Good question Doug. 

Today I have a requirement as an operator to mitigate DDoS attacks in seconds to single digit minutes and this commonly requires routing system changes that may not have been envisioned beforehand - hours and days of delay [imposed by a system that does little more than control what's routed - not if it's routed in a way I believe is secure] breaks this.

Where are the requirements that informed the current design?

-danny

---

From: Russ White <[email-masked]>
Date: Fri, 30 Nov 2012 14:02:10 -0500

> Policy by definition is a reflection of human intent.

And humans don't have intent that moves at the speed of light?

> Based upon what analysis or requirement?

That people expect their networks to react within seconds to change, not
minutes, hours, or days.

What do you base your requirement that it's okay for the routing system
to react in minutes on? Are you certain those requirements will hold
into the future, or do you think convergence speed requirements
(including policy propagation) will increase?

Russ

---

From: Danny McPherson <[email-masked]>
Date: Fri, 30 Nov 2012 14:16:30 -0500

> peering relationships, etc.)

It's not a question of speed, it's a question of reaction time.

As _one example, I know of many commercial DDoS products and services that automate these processes, RPKI as designed hampers our ability to respond in less than hours, and BGPSEC likely much longer.  How do I rationalize this when it doesn't even fix things that I consider routing security issues (e.g., the Google sanfu weeks back?)?

Here the cure may well be worse than the disease.  Mefloquine, anyone?

-danny

---

From: Arturo Servin <[email-masked]>
Date: Fri, 30 Nov 2012 17:37:55 -0200

If you only have one cache, and this fails, and you need to restore the
whole repository(ies): then yes. You have a problem.

	But if you have two cache servers, perhaps you would not even notice
while the second one is getting the whole repository(ies).

	But I am not sure if I am following your and Russ rationale.

Regards,
as

---

From: Russ White <[email-masked]>
Date: Fri, 30 Nov 2012 14:43:37 -0500

> while the second one is getting the whole repository(ies).

This isn't about rebuilding an entire cache, it's about one off changes
to that cache. What I'm hearing is that one-off changes could take
minutes, hours, or even days in some circumstances. In a world that
moves in the subsecond range, seconds are the minimal requirement, not
minutes. There's more here than the startup case.

What will be the scaling of getting even a single change out to hundreds
of thousands of caches, and from thence to hundreds of thousands of
routers, so a change in the correct origin can actually be reflected in
the policy tables of the Internet at large? It seems, to me, like a
pertinent question --and hand waving isn't a good answer at this point.

Russ

P.S. That we're discussion how well a system will scale and perform
after it has been designed and standardized seems a little odd, at least
to me.

-- 
<><
[email-masked]
[email-masked]

---

From: Danny McPherson <[email-masked]>
Date: Fri, 30 Nov 2012 14:48:58 -0500

> 	But I am not sure if I am following your and Russ rationale.

I'm not talking about the new attack surface elements we're introducing here Arturo, that's an orthogonal second order concern.

I'm talking about my inability to assert reachability for new destinations on the Internet (i.e., my infrastructure or DDoS customers prefixes) when attacks occur, without hours or days of downtime on the properties being attacked, until RPKI objects are fetched from every publication point on the Internet, controls are derived, and propagated to every RPKI cache in every operators network, and distributed to some sort of policy engine in routers for validation (and such) for routes in BGP.  This is not a worry I have today when responding to these threats, and a serious problem if it exists.

The fact that the RPKI itself could be attacked is just gravy.

-danny

---

From: "Montgomery, Douglas" <[email-masked]>
Date: Fri, 30 Nov 2012 14:52:18 -0500

On 11/30/12 2:00 PM, "Danny McPherson" <[email-masked]> wrote:

>Today I have a requirement as an operator to mitigate DDoS attacks in
>seconds to single digit minutes and this commonly requires routing system
>changes that may not have been envisioned beforehand - hours and days of
>delay [imposed by a system that does little more than control what's
>routed - not if it's routed in a way I believe is secure] breaks this.

I for one have long recognized that the current proposed system may have
limits on its reaction time.   Certainly from my perspective, more suited
to pre-publishing preventative data, then creating reactionary data.

The question is if there is consensus on the use cases like those above,
if it is impossible to pre-publish the potential origination ROAs before
their need/use, and if not, could the system be made more reactive and at
what other scaling cost?

Remember a ROA is an authorization to originate, not a declaration that is
currently happening.   If the business relationships that bring customers
to your DDoS mitigation service are established at a slower rate, might
one pre-publish the necessary ROAs?

>Where are the requirements that informed the current design?

My own opinion is ... The observation that ResCerts are inherently linked
to the business process of number resource allocation, and the time scales
that operators seemed comfortable in current systems that construct policy
from out of band data sets.  RPKI should be able to move faster than those
current processes.

Also a personal opinion, but I am not sure that policy systems that
operate much much faster than the underlying processes/human systems they
are linked to, is necessarily a good thing.  I hear lots of operator feed
back on relative comfort levels of things becoming "too automated".

Dougm

---

From: Christopher Morrow <[email-masked]>
Date: Fri, 30 Nov 2012 14:53:13 -0500

>         But I am not sure if I am following your and Russ rationale.

a worked example is something like:

ROA in repository for X years:
 as701-1.2.3.0/24

Time T0:
   bgp route: 1.2.3.0/24 as-path: 701

Time T1:
  dos attack on 1.2.3.4/32

Time T2:
  AS701 says: "oh, ddos_svc, pls to help us!! Yes, we are a new customer
                      we just signed up on your website, please helpz!!"

Time T3:
  new-roa: 1.2.3.0/24 - AS-DDOS_SVCS

Time T4:
   bgp-route: 1.2.3.0/24 as-path: AS-DDOS_SVCS

Time T5:
   routing validates and things divert to ddos-svc

I think Danny (and russ as well, at least) are worried that in the
case of no prior agreements the time TODAY for this process is
'minutes', and that if I have to publish a new roa, ship that around,
make sure everyone gets it ... the time is 'longer' tomorrow. (eric's
numbers would say full replication and availability of the data is
O(2days) or something)

today there's no validation on the origin so if you pick your
upstreams 'right' you can get reach-ability from a large portion of
the network quickly. tomorrow in a 'only validated routes' world, you
have to wait for propagation of the roa content.

So, the (a) question is:
  "How fast does the certified resources data (as seen by bgp
speakers) have to meet up with reality?"

-chris

---

From: Eric Osterweil <[email-masked]>
Date: Fri, 30 Nov 2012 15:02:36 -0500

``Confirmation bias ... connotes the seeking or interpreting of evidence in ways that are partial to existing beliefs, expectations, or a hypothesis in hand.'' [ 1 ]

> expecting and talking all along.  thanks.

Actually, Randy, engineering with the upper bound is pretty typical.  The counter tends to be viewed as quite amateurish.  Understanding failures and failings is part of responsible engineering.  In fact, codifying a system's design after building an implementation, and then retrofitting requirements to that design so that we can _then_ back into a threat model that befits a system's capabilities is typically frowned upon by engineers.

ymmv,

Eric

[ 1 ] 	Nickerson, Raymond S. "Confirmation bias: A ubiquitous phenomenon in many guises." 
	Review of General Psychology; Review of General Psychology 2, no. 2 (1998): 175.

---

From: Danny McPherson <[email-masked]>
Date: Fri, 30 Nov 2012 15:11:15 -0500

> to pre-publishing preventative data, then creating reactionary data.

And the state of the art in DDoS mitigation doesn't allow this, period.

> their need/use, and if not, could the system be made more reactive and at

Most folks don't buy DDoS protection services proactively (admittedly, more are beginning to), they buy them when they're being attack.  We get a phone call and offer one of n options to mitigation, with a routing assertion being a key techniques employed in the mix.  We also have many techniques related to hour core businesses that require routing changes that may not have been pre-envisioned.  Many commercial products and solutions allow codifying of this as well, if you so choose.

> one pre-publish the necessary ROAs?

See above..  And also note that pre-publishing ROAs may well be a *policy* thing (e.g., disclosure attack, "methods") that those who may get attacked don't wish to exposure before absolutely necessary.

> back on relative comfort levels of things becoming "too automated".

Talk to anyone on the receiving end of a large scale DDoS attack Doug, you shouldn't have to go far.  Go tell them why it may well take hours or days to respond, because we've "secured" the routing system (when we've not done enough for me to justify investment in RPKI to my CFO).

As one reasonably skilled in the art of DDoS mitigation services, and commercial products that enable them, and as CSO of Verisign in my day job where we are commonly on the end of lots of targeted and leveraged DDoS attacks, and offer a service to mitigate them, this is my informed opinion.  

-danny

---

From: Danny McPherson <[email-masked]>
Date: Fri, 30 Nov 2012 15:14:00 -0500

> have to wait for propagation of the roa content.

Right!   and hope it's not a multi-mode attack that exploits just that "property" of this new system with a rogue route announcement from one of the millions of keyboards that have enable access to BGP speaking routers.

> speakers) have to meet up with reality?"

Interesting we're visiting requirements now :-)

I'd prefer it make my routing changes no slower than they are today.  

-danny

---

From: Christopher Morrow <[email-masked]>
Date: Fri, 30 Nov 2012 16:08:33 -0500

> And the state of the art in DDoS mitigation doesn't allow this, period.

it sure does, if there's a contract in place... it's the 'oh noz! now
we're under attack and need to bring in $DDOSPROVIDER!!' that isn't
covered.

---

From: Danny McPherson <[email-masked]>
Date: Fri, 30 Nov 2012 16:19:33 -0500

> we're under attack and need to bring in $DDOSPROVIDER!!' that isn't

Right, IF there's a contract in place..  

Perhaps this new latency will drive folks to be more proactive..  not!   :-)

-danny

---

From: Randy Bush <[email-masked]>
Date: Sat, 01 Dec 2012 08:37:59 +0900

> Actually, Randy, engineering with the upper bound is pretty typical.

from your document

"The calculations in this document, while just candidate representations
of RPKI, project a very long lower-bound on the potential time needed
for RP caches to gather all objects in the RPKI"

> The counter tends to be viewed as quite amateurish.

personally, i would be professionally embarrassed to have my name on
such wild assed cabbage throwing as that document.

> codifying a system's design after building an implementation, and then
> retrofitting requirements to that design so that we can _then_ back
> into a threat model that befits a system's capabilities is typically
> frowned upon by engineers.

let's be honest here.  the threat model was done in the late '80s.  the
base of the design in the early '90s.  we're just slogging through the
saussage machine.

randy