AS path extensions

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.

> 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

  gated also has
  {m,n}
  {m}
  {m,}

  POSIX has

  ^	negate
  []	equiv () with |
  -	range when used within []

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.

> 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
> (The intersection above is a regular-expression-intersection,
> i.e. given two 	regular-expressions, it returns a regular-expression
> which matches the strings which are matched by both
> regular-expressions), and is done during the config file generation.

A union is written into aspath_merge_regex.  I don't think
intersection would be too hard.  Somehow I don't think that is the
best or easiest solution.

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;

> This works. However, it is very expensive. It can create 2^n import
> statements in gated if there are n regular-expressions in the original
> expression. In practise, I do not expect a big growth since many
> intersections will evaluate to empty regular-expressions and need not
> be written to the config file. However, the computation requirements
> of the config file generation is still exponential.

I get it now.  You are converting from extended-as-in: <bletch> to
gated syntax and concerned about the gated first match way of doing
policy.  You have to keep in mind that gated is designed to make it
easy for gated to run fast at run time, and not to make your life
easy.  Gated will match and stop at first match to save time.

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.

> A good way to solve this would involve changes to gated. That is:
> 	1) do not add "all restrict" by default to each import
> 	   statement
> 	2) continue looking for other as-path matches after matching
> 	   an as-path and there is no explicit address prefix match
> 	3) add an import statement with ".*" as path expression and 
> 	   "all restrict" network list to the end of import statements
> 	   so that by default all routes are rejected.
> 
> What do you think?

The code was designed to allow an action to be tagged on to the end of
the search process, so you could do a single search and come up with a
four byte cookie that means something to you (like a cost or restrict,
or a pointer to structure with something more complex).  The current
termination is an empty asps_tree member in an asp_state.  You could
terminate with a value and implement the union so that a function is
provided to merge the terminate values on an overlap.  The function
that merges netlists with a continue just chains structs so that an AS
path that matches as-path-exp-1 and as-paths-exp-2 returns a netlist
with an action of "pref 1" and a hook to a second netlist with "pref
2" and a hook to "restrict" if neither netlist matches.

Much simpler to code but slightly less efficient would be to keep the
current implementation and match the first AS path expression, match
the netlist, then match the second AS path, and so on.

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

What was the question again?  :-)

Curtis



-------- Logged at  Tue Mar 14 06:24:01 MET 1995  ---------