[Sidrops] On validating AS paths

[Iljitsch van Beijnum <[e-mail]>]

(I hope the list retains my non-proportional font. Reformat if necessary.)

After an interesting discussion with Job Snijders the other day about our respective drafts, I think it would be helpful to analyze the issue of AS path validation further before discussion specific solutions.

I'm interested to hear if my assumptions and conclusions are shared.

I think we can agree that any AS path that doesn't conform to the valley-free model. A quick refresher: the valley-free model assumes four types of relationships between ASes:

customer-provider:  /
provider-customer:  \
peer-peer:          ^
sibling-sibling:    -

I've invented the / \ ^ - characters to indicate relationships myself, the idea being that they'll visually show valleys if a path isn't valley-free.

You can visualize valley-freeness as the customer ASes at the bottom sending many up the hierarchy, and the money will only flow up, not down. So if you have a "valley" in the relationships between the ASes in a path, someone isn't getting paid and the whole thing doesn't work economically.

The model also allows for mutual backup arrangements, where basically two ASes provide transit to each other (also called a sibling relationship). How that works financially is a bit murky, but the interesting thing here is that if nobody implements any policies or filters, you have a network with only sibling relationships.

So with these four relationships and the valley-free restriction we should be able model any working real-world relationship between two or more ASes.

(We'll ignore the possibility that the relationships between ASes may be different for different address families and/or prefixes for now.)

For a formal definition of the valley-free model, read "On inferring autonomous system relationships in the internet", Gao, 2001.

I'll state it in the form of the following AS path validation procedure.

In addition to / \ ^ - we'll also allow ? to indicate an unknown relationship between two adjacent ASes in the path. And we'll assume the sibling relationship between an AS and itself (i.e., if there is AS path prepending).

The steps:

1. Trim from the right (origin) side all \ and - relationships
2. Trim from the left side all / and - relationships
3. If the path is now empty or contains just one ^, the path is valley-free and therefore valid
6. If the path still contains / or \ or contains multiple ^, the path is invalid

Here are a few valid paths:

A: //\\ 
B: /^\
C: ^
D: ^\-\

So the steps produce:

            A       B       C       D
            //\\    /^\     ^       ^\-\
Step 1      //      /^      ^       ^
Step 2              ^       ^       ^
Step 3      valid   valid   valid   valid

If we look at RFC 7908, the first four types of route leaks are caused by the following relationships:

1: \/
2: ^^
3: ^/
4: \^

So the steps produce:

            Type 1  Type 2  Type 3  Type 4
            \/      ^^      ^/      \^
Step 1      \/      ^^      ^/      \^
Step 2      \/      ^^      ^/      \^
Step 3      \/      ^^      ^/      \^
Step 5      invalid invalid invalid invalid

Now what if we have unknown relationships in the path?

/?^\ could be:

//^\    /-^\    /^^\    /\^\
valid   valid   invalid invalid

/?\ could be:

//\     /-\     /^\     /\\
valid   valid   valid   valid

In other words: if steps 1 and 2 above just leave a ?, then regardless of what the unknown relationship turns out to be, we know the path will be valley-free and valid.

So we can now extend the validation steps to consider unknown relationships and see even if we assume a best case scenario, we still end up with an invalid path:

1. Trim from the right (origin) side all \ and - relationships
2. Trim from the left side all / and - relationships
3. If the path is now empty or contains just one ^ or just one ?, the path is valley-free and therefore valid
4. Trim from the right (origin) side all \, - and ? relationships
5. Trim from the left side all /, - and ? relationships
6. If the path still contains / or \ or contains multiple ^, the path is invalid
7. Else the path validity is unknown

Now all of the above assumes that the relationship between two ASes is uncontested. But what if the two ASes claim to have different relationships?

One approach would be to just assume an unknown relationship ?, so the path will only validate under worst case assumptions.

In my opinion, a better approach would be just keep track of claims of a customer-provider relationship from the customer side (where the sibling relationship is simply a mutual customer-provider relationship claim).

Overclaiming of the relationship by a customer is relatively unproblematic, because the claimed provider will simply not provide the service with no ill effect. Overclaiming by the provider, on the other hand, could be harmful, the combination of the relationship overclaim and incorrect BGP filters will now create a route leak that our path validation system will declare to have a valid path.

There is probably no reason to publish peer-to-peer relationships, as a path with ? where there should be ^ will also validate.

One interesting issue is route servers, as deployed by internet exchanges. Typically (universally?) those don't add their AS to the AS path, breaking the BGP specification in the process. In that case, the route server is invisible, so validation will have the same result as with a direct peering relationship.

If this behavior is not universal, we should either assume a - relationship for route servers, or define a new type of relationship that will be removed from the valley-free validation process.

With all of the above out of the way, we'll have to think about which relationship claims to carry in-band and which out-of-band.