Subject: [sidr] BBN's trust anchor

From: Andrew Chi <[email-masked]>
Date: Wed, 10 Nov 2010 11:00:26 -0500

In order to test our RPKI relying party software, we generated a testbed 
with a large number of files.  Feel free to run against this, though we 
will change and add to it fairly regularly in the coming weeks.

rsync://rpki.bbn.com/rpki/root.cer

Nominal counts at the time of this email:
CA certs: 2006
CRLs: 2006
ROAs: 10005
Manifests: 2006

Bug reports, comments, and questions are most welcome.

-Andrew

---

From: Sandra Murphy <[email-masked]>
Date: Wed, 10 Nov 2010 11:55:20 -0500 (EST)

Can you say a bit more about how you generated this test data?

--Sandy, as wg member only

On Wed, 10 Nov 2010, Andrew Chi wrote:

> In order to test our RPKI relying party software, we generated a testbed with 
> a large number of files.  Feel free to run against this, though we will 
> change and add to it fairly regularly in the coming weeks.
>
> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr
>

---

From: Andrew Chi <[email-masked]>
Date: Thu, 11 Nov 2010 05:36:02 -0500

> Can you say a bit more about how you generated this test data?

Sure.  This purpose of this testbed is to make sure BBN's validator is 
(1) correct and (2) fast enough to handle ~300,000 objects.  Our testbed 
generation software automatically constructs one or more statistically 
realistic repositories, based on current counts for RPKI certificates, 
CRLs, ROAs, and manifests.

We are *not* running up/down software.  However, creating parent-child 
relationships in a top-down manner necessarily requires us to carry out 
similar request/suballocation actions in memory.

The input to our testbed is a specification file that defines (1) the 
resources of the trust anchor, (2) a number of CA types and the *amount* 
of resources assigned to each type, and (3) the parent-child 
relationships + branching factors.

For example (this isn't the exact format and there are more fields, but 
it gives you the main idea):

[IANA]
ipv4resources = 0/0
ipv6resources = ::/0
asresources = 1-4294967295
children = 5 * RIR, 1 * MISC

[RIR]
ipv4resources = /8, /8, /8, /23, range(129)...
ipv6resources = /64, /64, /96, ...
asresources = 10, 3, 78, ...
children = 6 * NIR, 200 * LIR, 1 * ROA_TYPE1

[NIR]
ipv4resources = ...
ipv6resources = ...
asresources = ...
children = 100 * LIR, 1 * ROA_TYPE1

[LIR]
ipv4resources = ...
ipv6resources = ...
asresources = ...
children = 3 * ROA_TYPE1, 4 * ROA_TYPE2

[ROA_TYPE1]
...

[ROA_TYPE2]
...

The testbed generation program starts from the trust anchor and 
recursively builds an RPKI hierarchy (suballocates resources and 
instantiates children), based on the counts and resources defined above. 
  There can be an arbitrary number of sections, so as we get more 
information about how many CAs/resources are out there, we can build a 
better simulation of reality.

Currently, the ~12,000 objects at rpki.bbn.com are all valid, and the 
BBN validator can process them in under 5 minutes.  However, we will be 
scaling to ~300,000 in the next few weeks as well as hand-constructing 
some error cases such as data mismatch, stale CRL/manifest, out-of-order 
certificate arrival, and directory being updated in the middle of an rsync.

-Andrew

---

From: Andrew Chi <[email-masked]>
Date: Thu, 11 Nov 2010 05:52:35 -0500

Btw, thanks to Rob Austein who generated a trust anchor locator for us 
(*.ita).  It's published on his web page containing lots of current 
trust anchors:

http://subvert-rpki.hactrn.net/rcynic/sample-trust-anchors

-Andrew

---

From: Sandra Murphy <[email-masked]>
Date: Thu, 11 Nov 2010 12:44:41 -0500 (EST)

Thanks for all the info, Andrew.

On Thu, 11 Nov 2010, Andrew Chi wrote:

> Sure.  This purpose of this testbed is to make sure BBN's validator is (1) 
> correct and (2) fast enough to handle ~300,000 objects.  Our testbed 
> realistic repositories, based on current counts for RPKI certificates, CRLs, 
> ROAs, and manifests.

What's your idea of when the software would be validating all 300K entries 
at once, and would need to do so quickly?

> resources of the trust anchor, (2) a number of CA types and the *amount* of 
> resources assigned to each type, and (3) the parent-child relationships + 
> branching factors.

CA "types"??

--Sandy

---

From: Stephen Kent <[email-masked]>
Date: Mon, 15 Nov 2010 04:21:09 -0500

At 12:44 PM -0500 11/11/10, Sandra Murphy wrote:
>>Sure.  This purpose of this testbed is to make sure BBN's validator 
>>is (1) correct and (2) fast enough to handle ~300,000 objects.  Our 
>>testbed generation software automatically constructs one or more 
>>statistically realistic repositories, based on current counts for 
>>RPKI certificates, CRLs, ROAs, and manifests.
>
>What's your idea of when the software would be validating all 300K 
>entries at once, and would need to do so quickly?,

If an RTP looses state it will need to download and process all the RPKI
data.

Steve

---

From: Sandra Murphy <[email-masked]>
Date: Mon, 15 Nov 2010 10:30:04 -0500 (EST)

On Mon, 15 Nov 2010, Stephen Kent wrote:

>> at once, and would need to do so quickly?,
>

So at startup kind of events.  I get that.  But what is the "fast enough" 
part of Andrew's statement?  I speculated that this might mean "fast 
enough to avoid delaying any updates" but that seems a very strong goal.

--Sandy

---

From: Andrew Chi <[email-masked]>
Date: Mon, 15 Nov 2010 11:00:05 -0500

> enough to avoid delaying any updates" but that seems a very strong goal.

I think there are two aspects to "fast enough".

1) The "startup" cost of downloading and processing all RPKI data needs 
to be on the order of hours and not days.

2) The "update" cost of synchronizing changes to the repository must not 
cause the validator to fall behind the rate of change in the repository. 
  I.e., once we have a large collection of objects, is the 
slightly-increased marginal cost of modifying one file within acceptable 
limits?

I believe our RP software is well within these goals, but it's always 
good to test scalability assumptions like these.

As for the 300K estimate, I'm happy to be corrected, but the order of 
magnitude ought to be similar to:

(# AS's participating in BGP routing) x (small multiplier for crls, 
manifest, and tree structure)

In October 2009, RIPE published an AS count of 15,495.  If anyone else 
has better numbers, please feel free to chime in.

-Andrew

---

From: Randy Bush <[email-masked]>
Date: Mon, 15 Nov 2010 17:12:07 +0100

> to be on the order of hours and not days.

no, it has to be minutes not hours

> manifest, and tree structure)

plus roas (300k now, 1m soon enough), plus ghostbusters (o(certs))

randy

---

From: George Michaelson <[email-masked]>
Date: Mon, 15 Nov 2010 17:12:33 +0100

On 15/11/2010, at 5:00 PM, Andrew Chi wrote:

> 1) The "startup" cost of downloading and processing all RPKI data needs to be on the order of hours and not days.
> 
> 2) The "update" cost of synchronizing changes to the repository must not cause the validator to fall behind the rate of change in the repository.  I.e., once we have a large collection of objects, is the slightly-increased marginal cost of modifying one file within acceptable limits?
> 
> I believe our RP software is well within these goals, but it's always good to test scalability assumptions like these.
> 
> As for the 300K estimate, I'm happy to be corrected, but the order of magnitude ought to be similar to:
> 
> (# AS's participating in BGP routing) x (small multiplier for crls, manifest, and tree structure)
> 
> In October 2009, RIPE published an AS count of 15,495.  If anyone else has better numbers, please feel free to chime in.
> 
> -Andrew
> 

Your thinking models my assumptions.

I did a tree of around 30,000 objects. This was based on a distribution of the resource pool to the entity count I saw from delegated files, bearing in mind the number of ASN.

But, because we have split roots, and each RIR has to cross authenticate for ERX (historical) data, I made substate for my modelled clients that made them hold a distribution of resource under multiple chains, some from their 'main' RIR, and some from other RIR via indirect chains.

I didn't do roa. they didn't exist in code at the time they would have added 10-20,000 more objects. Likewise manifests.

So my total size was 30k, but it would have been of the order 100k once I add in what we have now as required structure.

I also did sqldb for indexing. It makes things much faster to have direct index to SKI, AKI, date/age and valid/invalid state flags. 

I last ran this around June 2007 btw.

cheers

-george

---

From: Sandra Murphy <[email-masked]>
Date: Mon, 15 Nov 2010 11:31:44 -0500 (EST)

> I last ran this around June 2007 btw.

Can you share the results?

--Sandy

---

From: George Michaelson <[email-masked]>
Date: Mon, 15 Nov 2010 17:37:19 +0100

> Can you share the results?

Nothing formal written up sandy.

And, Randy is right. the size of the datapool is not my 'bang all resources in one roa' but the total number of discrete routes in the BGP cloud: if you fold them all into one uber ROA you fate share the age date of the resources. And, not all resources lie under one cert chain anyway so you wind up unable to combine them into one cert.

So, the experience of a 30k tree won't inform the 300,000 tree, or the million-tree. Not enough.

The churn rate is a function of several things, every CRL is updated, as is a manifest, each cycle time. So, there are many non-ROA objects changing.

No manifests or Roas in my testbed.

But, on the plus side, rsync is pretty quick. 

-G

---

From: Andrew Chi <[email-masked]>
Date: Mon, 15 Nov 2010 11:46:33 -0500

On 11/11/2010 12:44 PM, Sandra Murphy wrote:
>> resources of the trust anchor, (2) a number of CA types and the
>> *amount* of resources assigned to each type, and (3) the parent-child

Sorry, unfortunate terminology.  Internally we call them "CA blueprints" 
or "CA factories".  In the RPKI, obviously nothing distinguishes an RIR 
CA cert from anyone else's CA cert.  However, for hierarchy generation 
purposes, there are significant differences between:

1. RIRs (they all have very different distributions of resources)
2. Large ISPs (a small number of these with a large amount of resources)
3. Small ISPs (a large number of these with few resources)

We model this by allowing the definition of an arbitrary number of 
blueprints for CAs and ROAs.  These blueprints do not contain specific 
resources ("110.35/16") but rather amounts of resources ("/16"). 
Blueprints also contain a list of pointers to other blueprints (for 
future children).

To instantiate a child CA, start from an already instantiated parent, 
suballocate the appropriate amount of resources as defined by the 
child's blueprint, and create/sign the appropriate child certificate. 
Then, take the child's "future children" blueprints (i.e. for 
grandchildren) and append to a todo list.  Process the todo list using 
the same procedure.

Clear as mud?

-Andrew

---

From: "Mark Reynolds" <[email-masked]>
Date: Sun, 21 Nov 2010 15:04:05 -0500

Let me provide a brief clarification on terminology. BBN's RP software uses
a database to maintain state. At the top level, there are only two types of
database events: initialization and update. Initialization is perform when 
one
first starts using the software, and then once every few years after that. 
Update
is performed whenever the operator wants a state update. Initialization 
takes
hours; update takes < 15 minutes.

Details. Assume a total set of 300,000 digital objects. To populate an empty
database, assuming some nominal network bandwidth model, with the set of
definitely valid or possibly-might-become-valid-in-the-future objects, takes
~ 10 hours. Assuming the operator has a backup of the DB, the only reason
to re-init the database is to clean out unreachable objects. Of course the 
DB
already handles expiration and revocation, but it does not do classic 
garbage
collection where unreachable objects are removed. Therefore, after a few
years the operator might chose to re-init. The re-init operation can be done
to an offline DB, so that the current DB is not down for the entire re-init 
period,
only for a few seconds at the end, where the pointer to the "current" DB is
switched.

For update, we assume a 5% turnover rate per day. That is, rsync changes
the contents of the local filesystem at a rate of 5% per day. In this model,
an update takes < 15 minutes. Therefore, the operator can update the DB
as often as once every hour.

Of course, as network transfer time goes up, performance goes down as
well, but this applies to any RP implementation, not just BBN's. In our Jan 
1
release, we will provide parallelized rsync's, so one slow link won't impact 
the
entire update process.

Hope this helps,

Mark Reynolds