Subject: Re: ranger operator clashes

From: Cengiz Alaettinoglu <[email-masked]>
Date: Tue, 8 Sep 1998 14:53:35 -0700 (PDT)

Jerry,

Thanks for bringing the issue to the list.

We have the following operators
	^+		inlusive more specifics
	^-		exclusive more specifics
	^n		length n more specifics
	^n-m		length n to m more specifics

They are distributed over sets. I.e.
	{ prefix1, prefix2, ...}^n-m
is
	{ prefix1^n-m, prefix2^n-m, ...} // same for rs-foo^n-m

All of these operators are a special case of the ^n-m operator. Now
your question arises when we encounter: 
	prefix^op1^op2
Current spec says this is an error. But as you outlined in your talk,
this is difficult to catch and enforce (unless we make one of the
simplifying assumptions you mentioned).

Having thought about this after your talk in IETF, I think there is a
simple rule for prefix^op1^op2 that seems to work:

	prefix^n-m^k-l	==	prefix^max(n,k)-l	if l>=max(n,k)
				empty			otherwise

The best way to view this is to apply the first operator, construct
the resulting prefix set and distribute over the second operator. Here
are some examples:

128.9.0.0/16 ^20-24 ^26-28 == 128.9.0.0/16 ^26-28
128.9.0.0/16 ^20-24 ^22-28 == 128.9.0.0/16 ^22-28
128.9.0.0/16 ^20-24 ^18-28 == 128.9.0.0/16 ^20-28
128.9.0.0/16 ^20-24 ^18-22 == 128.9.0.0/16 ^20-22
128.9.0.0/16 ^20-24 ^18-19 == empty

Same general rule applies (and makes sense) for other operators as
well: 

128.9.0.0/16^+^-	== 128.9.0.0/16^-
128.9.0.0/16^-^+	== 128.9.0.0/16^-
128.9.0.0/16^17^24	== 128.9.0.0/16^24	

What do you think? I commented on your second question below.

Cengiz

-- 
Cengiz Alaettinoglu           Information Sciences Institute
http://www.isi.edu/~cengiz    University of Southern California

Gerald Andrew Winters ([email-masked]) on September 2:
> 
> Hello Everyone,
> 
>   I gave a talk on irrd and experiences with rpsl at the
> rps meeting in Chicago last week and in that talk I focused
> on route-set expansion and range operator clashes.  I tried 
> to show that distributing range operators over range operators 
> led to some unclear situations and that route-set expansion 
> could be carried out in several different ways.  
>   The rps group decided it would be best for me to bring 
> this topic to the mailing list to see if some sort of 
> consensus could be reached.
>   Okay, so here goes...
> 
> Example 1.  expand route-set 'rs-foo'
> 
> route-set: rs-foo
> members:   rs-bar^-
> 
> route-set: rs-bar
> members:   rs-car^24-32
> 
> comments: How do I distribute the exclusive more specifics
> operator over (rs-car^24-32)^- ?
>   There are 4 distinct range operators and 6 distinct
> combinations of 2.  And of those 6 combinations all
> of them seem to make sense except the combination
> of ^- and ^n-m.
> 

Once you expand to the prefix level, I think the rule I mentioned
above makes sense.

> 
> Example 2. expand route-set 'rs-foo'
> 
> route-set: rs-foo
> members:   rs-bar^24-32, rs-car^8-16
> 
> route-set: rs-bar
> members:   rs-car
> 
> comments: This example is supposed to show a possible
> unintended side affect and that this problem should not 
> be dismissed as simply a range operator combination issue.  
> Note that the maintainer of rs-foo appears to be interested 
> in only the prefixes of length 8-16 from rs-car (as indicated 
> by the rs-car^8-16 in the members of rs-foo).
>   However, note that in the expansion of rs-bar that when
> we distribute ^24-32 over the members of rs-bar that rs-car 
> becomes rs-car^24-32.  So the final expansion will have rs-car^24-32
> and rs-car^8-16.

First level expansion of rs-foo into 

	 route-set: rs-foo
	 members:   rs-car^24-32, rs-car^8-16

makes sense to me.
  
>   Should we say to the maintainers "caveat emptor",
> or should we build something into the route-set
> expansion algorithm that avoids this situation?

I think the maintainer has to be more careful if this is not his
intentions. 

> (eg, we could return an error or only expand a route-set
> at most once)
> 
> 
> Our initial choices:
> 
> 1. Don't distribute range operators over range operators.
>    -- so in Example 1. we would expand 'rs-car^24-32'.
> 
> 2. Expand a given route set at most once.
>    -- so in Example 2. we would expand 'rs-car^24-32'
>       and silently drop 'rs-car^8-16'.  This may
>       or may not be what the user wants but it was
>       this easiest thing to do from an algorithmic
>       standpoint.  A better way of expansion might
>       be to do a 'breadth first' instead of 'depth first'
>       expansion which we currently perform.
> 
> The only other comment I would like to make is
> giving an error message would most certainly not
> work well with the RaToolSet tools.  So because
> of this consideration, I would be more in favor
> of coming to an agreement on a default algorithm 
> concerning range operator clashes that allows the 
> route-set expansion to complete.
> 
> --jerry