Re: [Sidrops] ASPA verification algorithm error

["Sriram, Kotikalapudi (Fed)" <[e-mail]>]

Alexander and all,

I think the error that Jakob has pointed out should be fixed. He and I have discussed possible solutions. Building on insights from him and with additional observations, the downstream AS path validation algorithm described below is worth considering. Formally provable that it works correctly to classify Valid, Invalid, and Unknown. It also seems efficient and without side effects.

[Jakob and I have put together a set of slides – a pdf is attached here. The slides have figures and a more detailed description along with an implementation procedure.] 

Proposed downstream AS path validation algorithm for route leak detection:

The downstream AS path of length N (N > 1) can be represented (without loss of generality) as follows (these are unique AS numbers after the prepends are collapsed):

AS(1), AS(2), .…, AS(K-1), AS(K), AS(K+1), .…, AS(L-1), AS(L), AS(L+1), .…, AS(N-1), AS(N)

[please take help from figures in slides 4, 5 and 6 to follow along; see attached pdf]

where K is defined as follows: there is an up-ramp of K ASes on the left such that each of the ASes AS(1) through AS(K-1) attests in its ASPA that the next AS in the path is its provider. And L is defined as follows: there is a down-ramp of N-L ASes on the right such that each of the ASes AS(L) through AS(N-1) are attested to be a provider by the next AS in the path. The up-ramp ends at AS(K) and down-ramp begins at AS(L). 

Definition of g(AS(i), AS(j)): 
For simplicity in writing, the following AS hop-validity function is defined: g(AS(i), AS(j)) = Valid if the ASPA of AS(i) lists AS(j) as a provider. Else, g(AS(i), AS(j)) = Invalid if the ASPA of AS(i) does not list AS(j) as a provider. Else, g(AS(i), AS(j)) = Unknown if ASPA of AS(i) is absent. It is well understood that ASPAs are AFI dependent, so AFI is not explicitly shown in function g.    

So, for the AS path as represented above: 

g(AS(i), AS(i+1)) = Valid for i = 1,2, …, K-1 
g(AS(i+1), AS(i)) = Valid for i = L, L+2, …, N-1

Note: L=K is possible when the AS path is shaped like an inverted V. Also, K=1 when there is no up-ramp, and L=N when there is no down-ramp.

Further, when L > K, g(AS(K), AS(K+1)) = Unknown or Invalid; hence the up-ramp stops at K;

and g(AS(L), AS(L-1)) = Unknown or Invalid; hence the down-ramp starts at L. 

[Examples/figures: Please see slides 4-6.]  

Now the core part of the algorithm is presented. It relies on the following theorems which are intuitive and provable (see slides 4-8, 12-14).

Theorem 1: The downstream AS path is “Valid” if L-K = 0 or 1. If L-K > 1, then the AS path can be “Unknown” or “Invalid”, but never “Valid”.  

Theorem 2: For L-K > 1, the validity of the whole AS path is the same as that of the partial path AS(K), AS(K+1), .…, AS(L-1), AS(L). The partial path can only be either Invalid or Unknown. It is Invalid if there exist u and v (u and v in the range from K to L-1) such that u < v and g(AS(u), AS(u+1)) = Invalid and g(AS(v+1), AS(v)) = Invalid. Otherwise, the partial path is Unknown. 

Now, the core algorithm is nearly obvious and works as follows:

---- begin algorithm ------

The AS path is Valid if L-K = 0 or 1 and the procedure halts. 

(Note: For  L-K > 1, to determine whether the AS path is Invalid or Unknown, we only need to focus on the portion of the path from AS(K) to AS(L).)

Consider the partial path represented by AS(K), AS(K+1), …,  AS(L-1), AS(L).

For  L-K > 1, if there exist u and v in the range from K to L-1 such that u < v and

g(AS(u), A(u+1)) = Invalid, and
 
g(AS(v+1), A(v)) = Invalid,

then the AS path is Invalid and the procedure halts.

Else, the AS path is Unknown.

------------ end of algorithm --------------

[Please see examples in the slides to see how the algorithm works]

Slide 10 provides a detailed implementation procedure.

Comments welcome.
     
Thank you.

Sriram