Ripe 181

Thanks for more clarification.
It clarified enough so that I can continue my implementation.
More comments below.

Daniel Karrenberg (Daniel.Karrenberg at ripe.net) on October 14:
>   > This is almost but not equivalent to the following:
>   > 	Assume all preference values are in the range 0...Range
>   > 	a route is accepted from a peer with gated preference of
>   > 		as-in preference * Range + interas-in preference
> 
> It is not equivalent because this orders by interas-in preference
> across ASes if the as-in preferences are equal. See below.

Exactly.

>   > There is one problem that I foresee with your algorithm. You are
>   > trying to come-up with one total ordering (per route) whereas your
>   > input has cascade of two partial orderings.
>   > 
>   > What do you do below:
>   > 
>   > aut-num: AS1
>   > as-in: from AS2 10 accept AS100
>   > as-in: from AS3 10 accept AS100
>   > interas-in: from AS2 L1R1 10 accept AS100
>   > interas-in: from AS2 L1R2 11 accept AS100
>   > interas-in: from AS3 L1R3 12 accept AS100
>   > interas-in: from AS3 L1R4 13 accept AS100
>   > 
>   > Obviously there is no total ordering with these values.
>   > A partial ordering is fine as long as gated is concerned.
>   > However, I am not 100% sure that 
>   > one can come up with "one" partial ordering
>   > unless you compare interas-in preferences for different ASs
>   > (i.e.  10 with 12).
> 
> The intention of this is clear: 
> 
> 	Globally accept from AS2 and AS3 with equal preference. 
> 
> 	Locally prefer L1R1 over L1R2 from AS2.
> 
> 	Locally prefer L1R3 over L1R4 from AS2.
> 
> So the partial ordering is
> 
> L1R1 = L1R3 < L1R2 = L1R4
> 
> Easy to derive too.
> Is this clear now?

Not quite. This only works when you have two to choose from.
If you have more:

interas-in: from AS2 L1R1 1 accept AS100
interas-in: from AS2 L1R2 2 accept AS100
interas-in: from AS3 L1R3 1 accept AS100
interas-in: from AS3 L1R4 2 accept AS100
interas-in: from AS3 L1R5 3 accept AS100

i.e.
	L1R1 < L1R2        and           L1R3 < L1R4 < L1R5
hence there are two possible orderings:
	1. L1R1 = L1R3 < L1R2 = L1R4 < L1R5
	2. L1R1 = L1R3 < L1R4 < L1R2 = L1R5

Choosing either of them means some comparison of interas-in
preferences across AS's. 

After some local discussion here, we decided to go with 1. 
Since it is easier to compute:
	o  renumber interas-in preferences so that the smallest
           preference value is now 1, next smallest is 2, ...
	o  compare interas-in preferences across AS's as
           well to get the final ordering.
		as-in preference * Range + interas-in preference

No need to maintain ordered lists per route. (Actually with equal
preferences ordered lists in your algorithm are actually ordered
graphs).

Folks, please let me know if there are problems with this approach.

Cengiz

-- 
Cengiz Alaettinoglu       Information Sciences Institute
cengiz at isi.edu            University of Southern California




-------- Logged at  Sun Oct 16 17:20:57 MET 1994  ---------