AS path extensions

Curtis Villamizar (curtis at ans.net) on March  8:
> Thanks for the doc.  I think the Cisco syntax is also known as the
> Yakov memorial AS path syntax.  It is documented in the gated config
> section as well.  See:
> 
>   http://www.gated.cornell.edu
>   http://www.gated.cornell.edu//gated-R3_5Alpha_9/config_guide/aspath.html
> 
> If Cisco is using a different syntax, then don't use it.  Use the
> syntax in RFC 1164 (same as gated syntax).  The gated config section
> describes this concisely.  You can just cite the RFC or duplicate it.

Curtis,

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.

This mail sounds like suggestions to improve gated's as path
pattern syntax. Hence I have CC'ed to gated-alpha. Here are my reasons
why I do not want to use that syntax. Perhaps my understanding of
gated syntax is wrong or perhaps there are undocumented features.
Any suggestions are welcome. 

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.

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. 

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.

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.

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.

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?

Cengiz

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



-------- Logged at  Mon Mar 13 23:29:28 MET 1995  ---------