An ALTO Server should not combine prefixes. A router does not combine prefixes and longest prefix match well understood in this context.
From: "Y. Yang" <[email protected]<mailto:[email protected]>> Date: Wednesday, October 23, 2013 12:54 PM To: Wendy Roome <[email protected]<mailto:[email protected]>> Cc: IETF ALTO <[email protected]<mailto:[email protected]>> Subject: Re: [alto] Problem with "longest prefix" rule for mapping endpoints to PIDs 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<http://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<http://1.0.0.0/16> 1.1.0.0/16<http://1.1.0.0/16> 1.2.0.0/16<http://1.2.0.0/16> 1.3.0.0/16<http://1.3.0.0/16> PID2: 1.0.0.0/15<http://1.0.0.0/15> Obviously PID1's definition is inefficient -- those 4 CIDRs are equivalent to 1.0.0.0/14<http://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<http://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<http://10.0.0.0/14> and PID2 is 10.0.0.0/15<http://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
