AS path extensions

Cengiz,

> Cisco is using a different syntax which is closer to grep. However,
> gated's as path syntax misses a feature that I think is important.
> Perhaps I should use the posix syntax as Daniel suggested.
[...]
> It is not possible to specify ranges, and negation of ranges
> (i.e. [AS1 - AS100] or [^AS1]).  I do not think one can specify an as
> path expression for "as paths not containing AS100" without listing
> all 65K AS numbers in that expression. This would be
> "^[^AS100]*$". There are other advantages of ranges, they reduce the
> number of states in the compiled pattern.

I'm currently independently reworking some of this stuff for a gated v4.0
someday.  I've included negation, so the above pattern becomes (I think)
"(!100)*".  Ranges are not supported, not necessarily because they couldn't
be supported within the syntax but rather because I'm having difficulty
figuring out why one would want them other than to hack around the lack
of negation.

Note that your last sentence isn't true for my reimplementation (I'm not even
sure it was before), ranges don't reduce the number of states in the compiled
pattern compared to or'd lists.  Since long lists of |'d AS numbers occur
frequently, patterns of the form ( 86 | 200 | 201 | ... ) also compile to
a single state in the DFA in a data structure which makes the actual match
pretty fast.

> AS65535)*". This is a short term fix. I think more grep like syntax is
> desired. 

I can't figure out the grep-like part.  I'm pretty sure there is nothing
which can be written in grep-like syntax which can't be represented in
the syntax gated uses, and I suspect the reverse probably true as well
(with some proviso's, for example it isn't clear to me how one would do

	.* (1239 | 1240 | (86 179))

in grep without blowing it out to multiple lines, and multiple line regexp's
will very likely be either harder to compile efficiently or slower to execute).
I think you're complaining about features rather than syntax, features can
be added to either syntax.

The other thing the reimplementation does is attempt to do something with
AS sets.  In particular,

	86 .* [200 201 .*]

matches a path beginning with 86 (or a set which includes 86) and ending with
a set which includes at least 200 and 201.

	[86] .* [200 201]

matches a path with an initial sequence starting with AS 86 and ending with
a set of exactly 200 and 201.

> Lets say we want to import routes as follows:
>	extended-as-in: AS1 1 as-path-exp-1 AND net-list-1 
>	extended-as-in: AS1 2 as-path-exp-2 AND net-list-2
[...]
> My solution to this was to generate a config file with the following:
> 	import as-path-exp-1 intersection as-paths-exp-2 
> 		net-list-1 pref 1
> 		net-list-2 setminus net-list-1 pref 2
> 		all restrict
> 	import as-path-exp-1
> 		net-list-1 pref 1
> 		all restrict
> 	import as-paths-exp-2
> 		net-list-2 pref 2
> 		all restrict

I do this as

	import as-path-exp-1 preference 1 {
		net ...
		net ...
		all continue ;
	} ;
	import as-paths-exp-2 preference 2 {
		net ...
		net ...
		all restrict ;
	} ;

Dennis



-------- Logged at  Tue Mar 14 03:53:06 MET 1995  ---------