Re: [homenet] on prefix comparison

[Alexandru Petrescu <[e-mail]>]

Hi Pierre,

I took some time to understand the code.

But here is what I would like to say.

Your algorithm decides whether or not one prefix collides with another, 
by comparing prefix/plen pairs according to an exact match rule.

On another hand, the forwarding towards these prefixes is realized by 
longest-prefix match rule applied to an address against successive 
entries in a routing table.  By this rule an address/128 matches the 
first one entry whose prefix length is longest, if several; and default 
otherwise.

If one hears two prefix/plen pairs in RAs and decides they 'collide' by 
the exact match rule implemented by the code below then one may decide 
this is a bad configuration situation.  At the same time the forwarding 
may be set up ok, because it uses the longest-prefix match rule, not 
exact match, and has a default to escape to as well.

This is why I am saying that any method to compare prefixes may not be 
agreed on, may not lead to effective results, unless designed according 
to the rules used for forwarding.

Yours,

Alex



Le 08/10/2014 14:25, Pierre Pfister a écrit :
> A prefix can only contain another prefix if its prefix length is smaller.
>
> Here is some C-code that provides what you are looking for.
>
> Cheers,
>
> - Pierre
>
>
> /* Tell whether a prefix contains an address */
> uint8_t prefix_contains(const struct in6_addr *p, uint8_t plen, const struct in6_addr *addr)
> {
> 	int blen = plen >> 3;
> 	if(blen && memcmp(p, addr, blen))
> 		return 0;
>
> 	int rem = plen & 0x07;
> 	if(rem && ((p->s6_addr[blen] ^ addr->s6_addr[blen]) >> (8 - rem)))
> 		return 0;
>
> 	return 1;
> }
>
> /* Tell whether a prefix contains another prefix */
> uint8_t prefix_include(const struct in6_addr *p1, uint8_t plen1, const struct in6_addr *p2, uint8_t plen2)
> {
> 	if(plen1 > plen2)
> 		return 0;
> 	
> 	return prefix_contains(p1, plen1, p2);
> }
>
> /* Tell whether two prefixes are colliding */
> uint8_t prefix_collision(const struct in6_addr *p1, uint8_t plen1, const struct in6_addr *p2, uint8_t plen2)
> {
> 	return prefix_include(p1, plen1, p2, plen2) || prefix_include(p2, plen2, p1, plen1);
> }
>
>
> Le 8 oct. 2014 à 14:13, Alexandru Petrescu <[e-mail]> a écrit :
>
>> Pierre, just a small doubt, but I agree with you in general.
>>
>> Le 08/10/2014 13:58, Alexandru Petrescu a écrit :
>> [...]
>>>> Equality is never considered alone. Actually, most of the time, you
>>>> will find considerations such as: The prefix is not included or does
>>>> not include any other Assigned Prefix with a higher precedence.
>>
>> It is hard to say whether a prefix is included into another or not.  We do not have a published algorithm to say what it means for a prefix to include another.
>>
>> In general, we have a common understanding (and not published algorithm) about what it means 'longest prefix match'.  But that compares an address to a prefix, not a prefix to a prefix.
>>
>> Sure, one could assume that an address is just a /128 prefix and execute longest prefix match with it as if it were an address.
>>
>> But then again which prefix has the role of the address and which is the role of the prefix?  In other words, when hearing two prefixes on a link and want to compare them, which of them should be compared against the other by using the longest-prefix match?  There are two possibilities and two different outputs for a particular tuple of prefixes, depending on the order of this longest prefix match.
>>
>> Of course, I do not mention the easy case which compares two prefixes of precisely same length.
>>
>> Just because the length is different may make think that the prefixes are different.  Or otherwise one could be aggregated into another.  But there are several types of aggregation: matching up to the shortest length, matching up to middle, up to longest length, beyond the longest length.
>>
>> These cases are not documented and people may implement them in many different ways with different outputs when trying to tell whether this or that prefix are equal or included into one another.
>>
>> Alex
>>
>>
>
>
>