Hi Wendy,
Always excellent catch! Here is what I understand it:
- Consider any two nonequal prefixes p1 and p2: there can be only two
relations, they do not overlap or one is the subset of the other. This can
be visualized by considering the full binary tree and each prefix is just a
node on the tree. Hence they either on different branches or one is the
ancestor of another.
- As a result, longest prefix is well defined when we consider only
individual prefixes: if ip1 is in both p1 and p2, then either p1 is a
subset of p2, or the other way. This defines a total order and hence there
is always a maximum.
PID with longest prefix is slightly tricker: each PID is a set of prefixes.
Suppose ip1 is in PID1, it means ip1 is in at least one prefix p1 in PID1.
Suppose ip1 is in both PID1 and PID2, and assume no prefix is allowed to be
in multiple prefixes. Then consider the set of prefixes in P = {p: ip1 in
p, and p in PID1 or PID2}. The element in P defines a total order ( because
they all have non-empty intersect), and hence there is a max. We pick the
PID containing the max. This is what I would define.
If we apply this definition to your example, 1.0.0.0 belongs to PID1.
>From a real implementation point of view, this definition, without merging
prefixes, can also be easier: suppose one uses a standard rib
lookup library to do the lookup, considering the prefixes from all PIDs. An
rib allows 4 entries as in your example: specific routing for each subfix,
and routing lookup will return 1.0.0.0/16.
What do you think?
Richard
On Wednesday, October 23, 2013, Wendy Roome wrote:
> I just noticed a possible problem with the rule for determining the PID
> for an endpoint address. {5.2.1} says,
>
> "When either an ALTO Client or an ALTO Server needs to determine which
> PID in a Network Map contains a particular IP address, longest-prefix
> matching MUST be used."
>
> Now consider the following network map fragment:
>
> PID1: 1.0.0.0/16 1.1.0.0/16 1.2.0.0/16 1.3.0.0/16
> PID2: 1.0.0.0/15
>
> Obviously PID1's definition is inefficient -- those 4 CIDRs are equivalent
> to 1.0.0.0/14. But unless I missed it, nothing in the protocol spec says
> that's illegal.
>
> So what's the PID for 1.0.0.0? I think we all agree that it should be in
> PID2. But if we apply the "longest-prefix match" on CIDRs, then the
> longest CIDR is 1.0.0.0/16 in PID1, which implies that 1.0.0.0 should be
> in PID1.
>
> I think the cleanest way to resolve that problem is to say that regardless
> of how the PIDs in a CIDR were originally specified, an ALTO server MUST
> reduce the CIDRs in a PID to minimum canonical set by combining adjacent
> CIDRs. Thus the server's config file might specify PID1 with 4 CIDRs, as
> above, but the ALTO server would immediately combine them, and Network Map
> Service would say that PID1 is 10.0.0.0/14 and PID2 is 10.0.0.0/15.
>
> But I'm not sure where is the appropriate place to say that. {5.2.1}?
> {10.4.4}? {11.2.1}?
>
> - Wendy
>
>
> _______________________________________________
> alto mailing list
> [email protected] <javascript:;>
> https://www.ietf.org/mailman/listinfo/alto
>
_______________________________________________
alto mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/alto
