AS path extensions

Curtis,

Sorry that I took so long to reply. I tried to get a copy of the posix
standard but failed. Someone told me gnu regexp library is posix
compliant, and I looked there for the syntax.

Curtis Villamizar (curtis at ans.net) on March 13:
> 
> In message <199503132215.AA15414 at cat.isi.edu>, Cengiz Alaettinoglu writes:
> > 
> > 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.
> 
> Ranges would be nice.  As far as reducing states, this is not the
> case, since gated internals automatically builds ranges where
> appropriate.

Neat.

> 
> > Apparently, gated internals do support ranges. I asked this
> > feature to be present in our route server implementation. Ramesh
> > hacked gated, we can now specify ranges like (AS1 - AS100), and above
> > as path expression can be written as "(AS1 - AS99 | AS101 -
> > AS65535)*". This is a short term fix. I think more grep like syntax is
> > desired. 
> 
> If you add ranges, POSIX and gated syntax have essentially the same
> capability and in many cases the same operators.  In fact, could you
> point out which ones are different:
> 
>   .	match anything
>   *	zero to many
>   +	one to many
>   ?	zero or one
>   ()	grouping
>   |	logical OR

I think (I am not sure) | is different.
In gnu regexp, foo|bar matches foo or bar.
In gated, I think it matches fooar and fobar.

This is a minor difference.

> 
>   gated also has
>   {m,n}
>   {m}
>   {m,}
> 
>   POSIX has
> 
>   ^	negate
>   []	equiv () with |

actually posix has
	[] and [^]
it does not have negate like Dennis has.

>   -	range when used within []

Posix also has ^, $ to mean the beginning and end of a string. These
two are not important, because posix does substring matching and gated
does string matching. I.e. "9" will only match the string "9" in gated
however will match any string containing 9 in posix. I think the two
are equivalent.

> 
> These would be easy to add to the parse and hook back into the asmatch
> code.
> 
> > Since we are at it, and you are the one who implemented as path
> > matching in gated (correct me if I am wrong), there is another feature
> > in gated that I had to find a fix around. Perhaps there is a better
> > way of doing it. Again suggestions are very much appreciated.
> > 
> > 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
> > The ordering of these two terms in gated config file is very important
> > since gated stops after finding the first as path match. But there can
> > be as paths which are matched by the both expressions. That is, there
> > is no correct ordering.
> 
> This is not gated syntax, but extended ripe-181 with gated AS
> matching.  Code exists for this?  OK.

Some code exist that only understand the as paths of the form 
"AS# .*". I.e. the ones used in export filters. Full as path support
will be added after IETF.

> How about:
> 	import as-path-exp-1
> 		net-list-1 pref 1
> 		all continue;
> 	import as-paths-exp-2
> 		net-list-2 pref 2
> 		all restrict;

I think "continue" is the right answer for this problem.

1> If this becomes a hardship (n becomes large), the config syntax could
> be changed so you could make a specification like the extended
> ripe-181 and the machinery gets built at run time more like what gated
> needs to run fast.  Don't ask who does this or when it gets done.

Actually, Craig Labovitz of Merit was playing with this idea. I think
he can input very simple ripe-181 policies to his gated and generate
the machinery. Run time processing overhead was not one of his goals
to optimize and it could not handle nested logical operators.

> 
> What was the question again?  :-)

Thank you for your time, ideas and clarifications.

> 
> Curtis


Cengiz

-- 
Cengiz Alaettinoglu       Information Sciences Institute
(310) 822-1511            University of Southern California



-------- Logged at  Fri Mar 17 05:12:41 MET 1995  ---------