Re: [homenet] on prefix comparison

[Pierre Pfister <[e-mail]>]

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
> 
>