Subject: [alto] Problem with "longest prefix" rule for mapping endpoints to PIDs

From: Wendy Roome <[email-masked]>
Date: Wed, 23 Oct 2013 15:23:50 -0400

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

---

From: "Y. Richard Yang" <[email-masked]>
Date: Wed, 23 Oct 2013 15:54:49 -0400

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:

> _______________________________________________
> alto mailing list
> [email-masked] <javascript:;>
> https://www.ietf.org/mailman/listinfo/alto
>

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Wed, 23 Oct 2013 20:32:24 +0000

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-masked]<mailto:[email-masked]>>
Date: Wednesday, October 23, 2013 12:54 PM
To: Wendy Roome <[email-masked]<mailto:[email-masked]>>
Cc: IETF ALTO <[email-masked]<mailto:[email-masked]>>
Subject: Re: [alto] Problem with "longest prefix" rule for mapping endpoints to PIDs

Hi Wendy,

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

>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

   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.

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

        - Wendy

_______________________________________________
alto mailing list
[email-masked]<javascript:;>
https://www.ietf.org/mailman/listinfo/alto

---

From: Sebastian Kiesel <[email-masked]>
Date: Wed, 23 Oct 2013 22:50:46 +0200

Hi Wendy,

On Wed, Oct 23, 2013 at 03:23:50PM -0400, Wendy Roome wrote:
> PID2. 

I don't agree.  It should be in PID1.
That's how longest prefix matching works.

I am not sure whether your example is relevant in pracice. Maybe you
don't like the beahavior of this algorithm in this example, but at least
it's well-defined and deterministic, and you have the possibility to
define your map in a different way (e.g., completely omit PID1 OR PID2,
whatever you prefer).

So I don't think we should add any additional mechanism, exception, etc.
here.

Just my $0.02
Sebastian

---

From: "Y. Richard Yang" <[email-masked]>
Date: Wed, 23 Oct 2013 18:47:26 -0400

These are fast responses. It seems that the majority (3:1) is to keep the
non-merging semantics. If we do not hear other objections, we will keep the
current version, but do clarify using the good example from Wendy.

Cheers,

Richard
Hi Wendy,

Just my $0.02
Sebastian
[email-masked]

---

From: Wendy Roome <[email-masked]>
Date: Thu, 24 Oct 2013 10:33:20 -0400

I'm glad to see I can still raise up a controversy!

Here's the problem I saw. Consider two network maps:

> MapA:  A1 = 10.0.0.0/14
>                A2 = 10.0.0.0/15
> 
> MapB:  B1 = 10.0.0.0/16, 10.1.0.0/16, 10.2.0.0/16, 10.3.0.0/16
>                B2 = 10.0.0.0/15
> 
PIDs A1 and B1 cover exactly the same set of endpoint addresses. So the
naïve view is that those two network maps are dentical.

But if we strictly apply the "longest prefix match" rule, they are NOT
identical. In MapA, 10.0.0.0 is in A2, while in MapB, it's in B1. To me,
that's counterintuitive.  If y'all like that, fine. I can live with that!
But it should be documented, because I think this has serious potential for
misinterpretation.

And the next bake-off should have a test case for this -- eg, the network
map should define PIDs like B1 and B2, and there should be a test that
10.0.0.0 is in B1, not B2.

- Wendy Roome

From:  "Y. Richard Yang" <[email-masked]>
Date:  Wed, October 23, 2013 18:47
To:  Sebastian Kiesel <[email-masked]>
Cc:  IETF ALTO <[email-masked]>, Wendy Roome <[email-masked]>
Subject:  Re: [alto] Problem with "longest prefix" rule for mapping
endpoints to PIDs

Cheers,

Richard

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 24 Oct 2013 11:47:51 -0400

Wendy,

> I'm glad to see I can still raise up a controversy!
It is a very good discussion!

> identical.
In MapA, 10.0.0.0 is in A2, while in MapB, it's in B1. To me, that's
> counterintuitive.  If y'all like that, fine. I can live with that!  But it
> should be documented, because I think this has serious potential for
> misinterpretation.
>

Yes. We should document it clearly in the document. The semantics is that:

(1) No prefix should belong to two PIDs.; (2) One obtains the union of all
prefixes defined by all PIDs; call this set of prefixes P; (3) The longest
prefix matching an IP address is identified in P. (4) The PID containing
the prefixed identified in (3) is the PID of the IP address.

> 10.0.0.0 is in B1, not B2.
Good idea to test this in the next bake-off!

Richard

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Thu, 24 Oct 2013 17:23:24 +0000

I disagree again.  If you have a prefix 0.0.0.0/0 in one PID does that mean no other prefix can appear in any other PID? it means that all other prefixes will overlap with it.

The prefixes below could have been imported from BGP at t=0 and at t=1 they will be broken up. Or the PIDs can have different properties (as we discussed before).

Date: Thursday, October 24, 2013 8:47 AM

Wendy,

On Thu, Oct 24, 2013 at 10:33 AM, Wendy Roome <[email-masked]<mailto:[email-masked]>> wrote:
I'm glad to see I can still raise up a controversy!

MapA:  A1 = 10.0.0.0/14<http://10.0.0.0/14>
               A2 = 10.0.0.0/15<http://10.0.0.0/15>

MapB:  B1 = 10.0.0.0/16<http://10.0.0.0/16>, 10.1.0.0/16<http://10.1.0.0/16>, 10.2.0.0/16<http://10.2.0.0/16>, 10.3.0.0/16<http://10.3.0.0/16>
               B2 = 10.0.0.0/15<http://10.0.0.0/15>

PIDs A1 and B1 cover exactly the same set of endpoint addresses. So the naïve view is that those two network maps are dentical.

But if we strictly apply the "longest prefix match" rule, they are NOT identical.
In MapA, 10.0.0.0 is in A2, while in MapB, it's in B1. To me, that's counterintuitive.  If y'all like that, fine. I can live with that!  But it should be documented, because I think this has serious potential for misinterpretation.

(1) No prefix should belong to two PIDs.; (2) One obtains the union of all prefixes defined by all PIDs; call this set of prefixes P; (3) The longest prefix matching an IP address is identified in P. (4) The PID containing the prefixed identified in (3) is the PID of the IP address.

And the next bake-off should have a test case for this -- eg, the network map should define PIDs like B1 and B2, and there should be a test that 10.0.0.0 is in B1, not B2.

Richard

- Wendy Roome

From: "Y. Richard Yang" <[email-masked]<mailto:[email-masked]>>
Date: Wed, October 23, 2013 18:47
To: Sebastian Kiesel <[email-masked]<mailto:[email-masked]>>
Cc: IETF ALTO <[email-masked]<mailto:[email-masked]>>, Wendy Roome <[email-masked]<mailto:[email-masked]>>

These are fast responses. It seems that the majority (3:1) is to keep the non-merging semantics. If we do not hear other objections, we will keep the current version, but do clarify using the good example from Wendy.

Cheers,

Richard

---

From: Wendy Roome <[email-masked]>
Date: Thu, 24 Oct 2013 13:39:38 -0400

I think the protocol document should have an explicit example, such as
"MapB", as well as giving Richard's algorithm.

Case in point: Two years ago, when I first started working on an ALTO
server, I implemented the algorithm Richard described, exactly as is. For
"MapB", my server does indeed say that 10.0.0.0 is in B1, not B2.

And until I tried that test case, I had no idea it would behave that way. I
really thought it would say 10.0.0.0 is in B2.

So I think we need to hit people over the head with this one.

- Wendy Roome

From:  "Y. Richard Yang" <[email-masked]>
Date:  Thu, October 24, 2013 11:47
To:  Wendy Roome <[email-masked]>
Cc:  Sebastian Kiesel <[email-masked]>, IETF ALTO <[email-masked]>
Subject:  Re: [alto] Problem with "longest prefix" rule for mapping
endpoints to PIDs

>> MapA:  A1 = 10.0.0.0/14 <http://10.0.0.0/14>
>>                A2 = 10.0.0.0/15 <http://10.0.0.0/15>
>> 
>> MapB:  B1 = 10.0.0.0/16 <http://10.0.0.0/16> , 10.1.0.0/16
>> <http://10.1.0.0/16> , 10.2.0.0/16 <http://10.2.0.0/16> , 10.3.0.0/16
>> <http://10.3.0.0/16>
>>                B2 = 10.0.0.0/15 <http://10.0.0.0/15>
>> 
> PIDs A1 and B1 cover exactly the same set of endpoint addresses. So the naïve
> view is that those two network maps are dentical.
>  

(1) No prefix should belong to two PIDs.; (2) One obtains the union of all
prefixes defined by all PIDs; call this set of prefixes P; (3) The longest
prefix matching an IP address is identified in P. (4) The PID containing the
prefixed identified in (3) is the PID of the IP address.

---

From: Sebastian Kiesel <[email-masked]>
Date: Thu, 24 Oct 2013 20:43:16 +0200

Wendy,

> that's counterintuitive.  If y'all like that, fine. I can live with that!

Believe it or not, but for me this client behavior *is* intuitive.
Another story is, why would one create such a strange map?

Maybe in a scenario like this:

At time t0:

C1 = 10.0.0.0/14
C101 = 10.0.0.0/16, 10.2.0.0/16
C102 = 10.1.0.0/16, 10.3.0.0/16

and the corresponding cost map tells you (in an appropriate metric):

C1 is manually and statically configured as a catch-all for my whole
prefix. I can't say where these IP addresses are located exactly, but
at least they are somewhere in my network.

C101 is automatically exported from the network management system. The
routing protocol says these prefixes are in my westcoast data center
and the detailed properties are as follows: foo

C102 is ... eastcoast ... : bar

some time later, all prefixes move to westcoast. So at time t1:

if the management system / map generator is not too clever:

D1 = 10.0.0.0/14
D101 = 10.0.0.0/16, 10.2.0.0/16, 10.1.0.0/16, 10.3.0.0/16
D102 = (empty or undefined)

In this case for me it would be intuitive to say that matching
10.0.0.1 to D101 should give better information than D1.

if the management system / map generator is a bit more clever and
figures out that prefixes can be aggregated, but not clever enough
to remove the "screened" default entry:

E1 = 10.0.0.0/14
E101 = 10.0.0.0/14
E102 = (empty or undefined)

Again, the intuitive answer is that E101 would probably give better
results than E1.  But what does the spec say? All I could find was:

   Each endpoint MUST map into exactly one PID.  Since longest-prefix
   matching is used to map an endpoint to a PID, this can be
   accomplished by ensuring that no two PIDs contain an identical IP
   prefix.  (sec. 5.2.1.)

This wording seems a bit strange to me. Does the "can" in the second
sentence suggest that there are alternatives? I think this should be
reworded. I see several options:

1.  clarify what we have now, e.g.:

    A valid network map MUST NOT define two or more PIDs which contain
    an identical IP prefix, in order to ensure that the longest-prefix
    matching algorithm maps each endpoint into exactly one PID.

2.  specify what should happen if a map contains two PIDs with the
    same prefix:

    2a) the client may randomly chose one
    2b) the client must use the pid with the prefix that appeared
        first in the json structure
    2c) the client must use the pid with the prefix that appeared
        last in the json structure
    2d) the client must lexicographically sort the PID names
        of PIDs that contain the prefix and take the first one
    2e) the client must lexicographically sort the PID names
        of PIDs that contain the prefix and take the last one

I'd prefer one of the 2d) or 2e) options. 

Any thoughts on that?

Thanks,
Sebastian

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 24 Oct 2013 15:51:02 -0400

On Thu, Oct 24, 2013 at 1:23 PM, Reinaldo Penno (repenno) <[email-masked]
> wrote:

>  I disagree again.  If you have a prefix 0.0.0.0/0 in one PID does that
> mean no other prefix can appear in any other PID? it means that all other
> prefixes will overlap with it.
>

Not sure I understand the issue. Which condition among the three:

Is it (1)?

Richard

>
>  The prefixes below could have been imported from BGP at t=0 and at t=1
> they will be broken up. Or the PIDs can have different properties (as we
> discussed before).
>
>
>   From: "Y. Yang" <[email-masked]>
> Cc: IETF ALTO <[email-masked]>
>>  And the next bake-off should have a test case for this -- eg, the
>> network map should define PIDs like B1 and B2, and there should be a test
>> that 10.0.0.0 is in B1, not B2.
>>
>>
>>  These are fast responses. It seems that the majority (3:1) is to keep
>> the non-merging semantics. If we do not hear other objections, we will keep
>> the current version, but do clarify using the good example from Wendy.
>>
>> Cheers,
>>
>> Richard
>>
>
>

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 24 Oct 2013 15:54:18 -0400

Hi Wendy,

On Thu, Oct 24, 2013 at 1:39 PM, Wendy Roome <[email-masked]>wrote:

> And until I tried that test case, I had no idea it would behave that way.
> I really thought it would say 10.0.0.0 is in B2.
>

Agree, and can do so with the example that you proposed, at least to those
who find it less intuitive.

Richard

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Thu, 24 Oct 2013 19:56:42 +0000

From: "Y. Yang" <[email-masked]<mailto:[email-masked]>>
Date: Thursday, October 24, 2013 12:51 PM
To: Cisco Employee <[email-masked]<mailto:[email-masked]>>
Cc: Wendy Roome <[email-masked]<mailto:[email-masked]>>, IETF ALTO <[email-masked]<mailto:[email-masked]>>
Subject: Re: [alto] Problem with "longest prefix" rule for mapping endpoints to PIDs

On Thu, Oct 24, 2013 at 1:23 PM, Reinaldo Penno (repenno) <[email-masked]<mailto:[email-masked]>> wrote:
I disagree again.  If you have a prefix 0.0.0.0/0<http://0.0.0.0/0> in one PID does that mean no other prefix can appear in any other PID? it means that all other prefixes will overlap with it.

Not sure I understand the issue. Which condition among the three:
(1) No prefix should belong to two PIDs.;

[RP] Wendy pointed out that this is already in the draft. Thanks for that. But I'm not sure this is necessary, but that is for another time.

(2) One obtains the union of all prefixes defined by all PIDs; call this set of prefixes P; (3) The longest prefix matching an IP address is identified in P. (4) The PID containing the prefixed identified in (3) is the PID of the IP address.

[RP] What is needed to be said? Above is already in the draft. The way I see it the draft already has everything needed.

Is it (1)?

Richard

Wendy,

Richard

- Wendy Roome

Cheers,

Richard

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 24 Oct 2013 16:02:03 -0400

On Thu, Oct 24, 2013 at 2:43 PM, Sebastian Kiesel <[email-masked]>wrote:

> > naďve view is that those two network maps are dentical.
> >
> D102 = (empty or undefined)
Interesting scenario.

>     matching algorithm maps each endpoint into exactly one PID.
A good clarification.

> If I have to choose among the five choices, 2d) and 2e) look reasonable.
But for this case, a simpler statement is that the server misbehaved, and
sends a wrong piece of information, and our protocol does not have a 3rd
step to send feedback to the server. It falls to the domain of client
verifying server information. I would classify it as a case that can be
handled by Section 15.2? Does this make sense?

Richard

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 24 Oct 2013 16:10:32 -0400

On Thu, Oct 24, 2013 at 3:56 PM, Reinaldo Penno (repenno) <[email-masked]

> To: Cisco Employee <[email-masked]>
> Cc: Wendy Roome <[email-masked]>, IETF ALTO <[email-masked]>
>
> On Thu, Oct 24, 2013 at 1:23 PM, Reinaldo Penno (repenno) <
> [email-masked]> wrote:
>
>  [RP] Wendy pointed out that this is already in the draft. Thanks for
> that. But I'm not sure this is necessary, but that is for another time.
>
>
Good statement. No-duplicate is not a necessary condition, but only a
sufficient condition. The wording in the current draft is "can", as
Sebastian pointed out. We often use "can" to imply "only sufficient" in
such a setting. It is not necessary when one considers the following case
(the duplicated prefix is dominated by a more specific prefix both PIDs).
But for now, I am fine with Sebastian's wording of enforcing the sufficient
condition.

>     (2) One obtains the union of all prefixes defined by all PIDs; call
> this set of prefixes P; (3) The longest prefix matching an IP address is
> identified in P. (4) The PID containing the prefixed identified in (3) is
> the PID of the IP address.
>
>  [RP] What is needed to be said? Above is already in the draft. The way I
> see it the draft already has everything needed.
>
>
> The current draft already has everything. Putting the conditions together
is to make potential issues more explicit, and can make the draft easier to
read.

Richard

>> On Thu, Oct 24, 2013 at 10:33 AM, Wendy Roome <[email-masked]
>> > wrote:
>>
>>>  PIDs A1 and B1 cover exactly the same set of endpoint addresses. So
>>> the naïve view is that those two network maps are dentical.
>>>
>>>
>> (1) No prefix should belong to two PIDs.; (2) One obtains the union of
>> all prefixes defined by all PIDs; call this set of prefixes P; (3) The
>> longest prefix matching an IP address is identified in P. (4) The PID
>> containing the prefixed identified in (3) is the PID of the IP address.
>>
>>
>>>

---

From: Sebastian Kiesel <[email-masked]>
Date: Thu, 24 Oct 2013 22:31:16 +0200

> On Thu, Oct 24, 2013 at 2:43 PM, Sebastian Kiesel <[email-masked]>wrote:

[same prefix in the definition of two PIDs, e.g.]
> handled by Section 15.2? Does this make sense?

Our protocol design indeed does not provide a mechanism by which the
client could inform the server that the server's previous reply could
not be understood or was "illegal".  Exactly because of that it seems
tempting to me to not define this (admittedly questionable) map layout
as "illegal", but instead define a deterministic and sort-of reasonable
client behavior for that case. If you are a server operator and don't
like that behavior, just define your maps in an unambiguous way.

What do you think?

S.

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 24 Oct 2013 17:06:07 -0400

On Thu, Oct 24, 2013 at 4:31 PM, Sebastian Kiesel <[email-masked]>wrote:

> > On Thu, Oct 24, 2013 at 2:43 PM, Sebastian Kiesel <[email-masked]
> >wrote:
>

Here is a concern. If we specify a "recovery" operation such as 2d) and
2e), then we will not need to specify the no-duplicate requirement, as we
are essentially saying "X is not allowed, but if you do X, then we are OK
and understand X as this..." It is a bit contradicting. WIthout specifying
any "recovering" operation seems to be cleaner, but I am willing to learn
more on the basic principles of handling non-confirming behaviors. It is a
good discussion!

Richard

---

From: Sebastian Kiesel <[email-masked]>
Date: Thu, 24 Oct 2013 23:24:52 +0200

Richard,

On Thu, Oct 24, 2013 at 05:06:07PM -0400, Y. Richard Yang wrote:
> and understand X as this..." It is a bit contradicting.

right. what I didn't say explicitly: options 1) and 2?) are mutually
exclusive.

if we go for 2?) we can add a "note" or maybe a "recommendation" which
says that clear and non-overlapping map definitions should be preferred
for the sake of easier readability. But we should not declare multiple
occurences of one prefix as illegal, and we should also avoid the term
"ambiguous", because with a well-defined algoritm the result may be
unexpected or counterintuitive but it is unambiguous.

Sebastian

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Thu, 24 Oct 2013 22:37:19 +0000

Right. Routers have forwarding entries that point to N different
interfaces. Sometimes they have the same weight, sometimes flow load
balancing or some other tie breaking internal to the router. And ALTO has
prefixes that are mapped to two different PIDs. Just another day in the
Internet. 

On 10/24/13 2:24 PM, "Sebastian Kiesel" <[email-masked]> wrote:

>But we should not declare multiple
>occurences of one prefix as illegal,

---

From: "Y. Richard Yang" <[email-masked]>
Date: Fri, 25 Oct 2013 15:39:56 -0400

> prefixes that are mapped to two different PIDs. Just another day in the

Mapping to multiple prefixes in fib has well defined semantics, such as
load balancing paths, as you mentioned. It is not clear the use cases for
mapping to multiple PIDs, and our current assignment to resolve the case
(e.g., 2d or 2e) may not provide the intended semantics (e.g., hash on IP
to achieve load balancing). Hence, I am still in the pushing-back mode for
simplicity...

Richard

---

From: Wendy Roome <[email-masked]>
Date: Mon, 28 Oct 2013 09:02:04 -0400

Here's my take. A PID is a collection of endpoints whose "cost metrics" are
sufficiently similar that we can lump them together as a group. PIDs
partition the endpoint space into equivalence classes. By that definition,
an endpoint can only be in one PID.

I think the problem is that we're confusing "PIDs" with "routes". A PID is
*not* a route.  If there are multiple routes to the endpoints in a PID, the
network picks the best route, and the ALTO server's cost metric should
reflect the cost of that best route. But the route to an endpoint does *not*
determine the endpoint's PID. An endpoint is always in the same PID,
regardless of the route the network uses to get to that endpoint.

Example: An office has a network with 500 endpoints.  The office network has
a hierarchy of internal routers, and (say) two gateway routers that connect
to the rest of the internet via two different ISPs. As I see it, those 500
endpoints are in one PID, regardless of how many gateway routers connect
them to the outside, and whether or not they're working. The ALTO server may
say that the gateway routers are in the office PID, or they may be in the
ISP's PIDs, or they may each be in their own PID. That's the ALTO server's
call. 

But the PID for an endpoint in that office does *not* depend on the route
used to get to it. It's always in the same PID, regardless of which router
is active. The endpoints do not move from one PID to another if a gateway
router goes down.

I agree with Richard that saying, "A server must not do 'foo', but if it
does, a client should recover by doing 'bar'" seems wrong. If a server
violates the protocol, that's an error.

As for situations where an ALTO server might put the same CIDR in two PIDs
because the server is automagically deduces PIDs from network routes, well,
it's the server's responsibility to detect that duplication and resolve it
by picking a PID. It's not the client's job.

- Wendy

From:  "Y. Richard Yang" <[email-masked]>
Date:  Fri, October 25, 2013 15:39
To:  "Reinaldo Penno, (repenno)" <[email-masked]>
Cc:  Sebastian Kiesel <[email-masked]>, IETF ALTO <[email-masked]>,
Wendy Roome <[email-masked]>
Subject:  Re: [alto] Problem with "longest prefix" rule for mapping
endpoints to PIDs

> prefixes that are mapped to two different PIDs. Just another day in the

Mapping to multiple prefixes in fib has well defined semantics, such as load
balancing paths, as you mentioned. It is not clear the use cases for mapping
to multiple PIDs, and our current assignment to resolve the case (e.g., 2d
or 2e) may not provide the intended semantics (e.g., hash on IP to achieve
load balancing). Hence, I am still in the pushing-back mode for
simplicity...

Richard

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 28 Oct 2013 14:13:20 +0100

Wendy, all,

I agree, PIDs are not the same as routes.

I am wondering whether we should specify client behavior if a server
sends a map with the same prefix in two PIDs.  Should it ignore the
complete map, or just the duplicate prefix(es)?  Or can we find a
sort-of reasonable algorithm to resolve the ambiguity?

Defining a map with certain properties as "illegal" (i.e., saying that
the server MUST NOT send it) but completely leaving unspecified how the
client should react if the server does it anyway is IMO not a good
practise.

Sebastian

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 28 Oct 2013 14:37:51 +0000

A few points to consider.

Yes, an endpoint can move from one PID to another in case of Mobile IP

Yes, and endpoint can be found in multiple PIDs if it is in a multi-homed network, I.e., a network where the gateway is connected to multiple networks.

Yes, and endpoint  can move from one PID to another if the Gateway is down since a host interface can be withdraw and the endpoint will move.

Thanks,

Reinaldo

From: Wendy Roome <[email-masked]<mailto:[email-masked]>>
Date: Monday, October 28, 2013 6:02 AM
To: "Y. Yang" <[email-masked]<mailto:[email-masked]>>, Cisco Employee <[email-masked]<mailto:[email-masked]>>
Cc: Sebastian Kiesel <[email-masked]<mailto:[email-masked]>>, IETF ALTO <[email-masked]<mailto:[email-masked]>>
Subject: Re: [alto] Problem with "longest prefix" rule for mapping endpoints to PIDs

Here's my take. A PID is a collection of endpoints whose "cost metrics" are sufficiently similar that we can lump them together as a group. PIDs partition the endpoint space into equivalence classes. By that definition, an endpoint can only be in one PID.

I think the problem is that we're confusing "PIDs" with "routes". A PID is *not* a route.  If there are multiple routes to the endpoints in a PID, the network picks the best route, and the ALTO server's cost metric should reflect the cost of that best route. But the route to an endpoint does *not* determine the endpoint's PID. An endpoint is always in the same PID, regardless of the route the network uses to get to that endpoint.

Example: An office has a network with 500 endpoints.  The office network has a hierarchy of internal routers, and (say) two gateway routers that connect to the rest of the internet via two different ISPs. As I see it, those 500 endpoints are in one PID, regardless of how many gateway routers connect them to the outside, and whether or not they're working. The ALTO server may say that the gateway routers are in the office PID, or they may be in the ISP's PIDs, or they may each be in their own PID. That's the ALTO server's call.

But the PID for an endpoint in that office does *not* depend on the route used to get to it. It's always in the same PID, regardless of which router is active. The endpoints do not move from one PID to another if a gateway router goes down.

I agree with Richard that saying, "A server must not do 'foo', but if it does, a client should recover by doing 'bar'" seems wrong. If a server violates the protocol, that's an error.

As for situations where an ALTO server might put the same CIDR in two PIDs because the server is automagically deduces PIDs from network routes, well,  it's the server's responsibility to detect that duplication and resolve it by picking a PID. It's not the client's job.

- Wendy

From: "Y. Richard Yang" <[email-masked]<mailto:[email-masked]>>
Date: Fri, October 25, 2013 15:39
To: "Reinaldo Penno, (repenno)" <[email-masked]<mailto:[email-masked]>>
Cc: Sebastian Kiesel <[email-masked]<mailto:[email-masked]>>, IETF ALTO <[email-masked]<mailto:[email-masked]>>, Wendy Roome <[email-masked]<mailto:[email-masked]>>
Subject: Re: [alto] Problem with "longest prefix" rule for mapping endpoints to PIDs

> prefixes that are mapped to two different PIDs. Just another day in the

Mapping to multiple prefixes in fib has well defined semantics, such as load balancing paths, as you mentioned. It is not clear the use cases for mapping to multiple PIDs, and our current assignment to resolve the case (e.g., 2d or 2e) may not provide the intended semantics (e.g., hash on IP to achieve load balancing). Hence, I am still in the pushing-back mode for simplicity...

Richard
>
> On 10/24/13 2:24 PM, "Sebastian Kiesel" <[email-masked]<mailto:[email-masked]>> wrote:
>

---

From: Wendy Roome <[email-masked]>
Date: Mon, 28 Oct 2013 10:57:06 -0400

I agree with #1 & #3. But those just move an endpoint between PIDs. That's
fine. At any given time, the endpoint is only in one PID.

But I disagree with #2. The endpoints in a multi-homed network may have two
different routes, but they are in one PID, not two PIDs. Here's how I look
at it: if I want to send a packet to 10.0.0.1, I just tell the network to
send the packet. I do *not* tell the network the route or which gateway to
use. That's the network's job. And the network does its best to hide that
from users. Similarly, an ALTO client just wants the cost from endpoint A to
B. The client doesn't want to guess the best route. That's the ALTO server's
job.

- Wendy

From:  "Reinaldo Penno (repenno)" <[email-masked]>
Date:  Mon, October 28, 2013 10:37
To:  Wendy Roome <[email-masked]>, "Y. Richard Yang"
<[email-masked]>
Cc:  Sebastian Kiesel <[email-masked]>, IETF ALTO <[email-masked]>
Subject:  Re: [alto] Problem with "longest prefix" rule for mapping
endpoints to PIDs

Yes, and endpoint can be found in multiple PIDs if it is in a multi-homed
network, I.e., a network where the gateway is connected to multiple
networks. 

Yes, and endpoint  can move from one PID to another if the Gateway is down
since a host interface can be withdraw and the endpoint will move.

Thanks,

Reinaldo

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 28 Oct 2013 15:08:51 +0000

[RP] And endpoint is an application, not an IP.  So, an endpoint can be in many PIDs.

More inline..

From: Wendy Roome <[email-masked]<mailto:[email-masked]>>
Date: Monday, October 28, 2013 7:57 AM
To: Cisco Employee <[email-masked]<mailto:[email-masked]>>, "Y. Yang" <[email-masked]<mailto:[email-masked]>>
Cc: Sebastian Kiesel <[email-masked]<mailto:[email-masked]>>, IETF ALTO <[email-masked]<mailto:[email-masked]>>
Subject: Re: [alto] Problem with "longest prefix" rule for mapping endpoints to PIDs

I agree with #1 & #3. But those just move an endpoint between PIDs. That's fine. At any given time, the endpoint is only in one PID.

But I disagree with #2. The endpoints in a multi-homed network may have two different routes, but they are in one PID, not two PIDs. Here's how I look at it: if I want to send a packet to 10.0.0.1, I just tell the network to send the packet. I do *not* tell the network the route or which gateway to use.

[RP] The interface and source selection address determines to a great extend the path  the packet will take through a network. Both are possible today and with IPv6 will be much more pervasive.

That's the network's job. And the network does its best to hide that from users. Similarly, an ALTO client just wants the cost from endpoint A to B. The client doesn't want to guess the best route. That's the ALTO server's job.

- Wendy

From: "Reinaldo Penno (repenno)" <[email-masked]<mailto:[email-masked]>>
Date: Mon, October 28, 2013 10:37
To: Wendy Roome <[email-masked]<mailto:[email-masked]>>, "Y. Richard Yang" <[email-masked]<mailto:[email-masked]>>
Cc: Sebastian Kiesel <[email-masked]<mailto:[email-masked]>>, IETF ALTO <[email-masked]<mailto:[email-masked]>>
Subject: Re: [alto] Problem with "longest prefix" rule for mapping endpoints to PIDs

Thanks,

Reinaldo

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 28 Oct 2013 16:48:14 +0100

> [RP] And endpoint is an application, not an IP.  So, an endpoint can be in many PIDs.

True in general. but for that we probably would have to define a new
endpoint type.  This discussion is about the type IP prefix.

Sebastian

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 28 Oct 2013 15:56:55 +0000

If I rephrased I would say when the representation of an endpoint is an
IP, that IP can appear in only one PID.

We could create this constraint within a single map. Across maps,
certainly an IP can be mapped to different PIDs.

But I'm still not convinced (but can be) that in real deployments an IP
will appear in only one PID such as in the case of multi-homed networks.

---

From: Wendy Roome <[email-masked]>
Date: Wed, 30 Oct 2013 10:30:56 -0400

I agree with Sebastian.  This discussion is about IP addresses, not
abstract services/applications. If an application runs on a box with
multiple interfaces, and hence has multiple IP addresses, then those IP
addresses may be in different PIDs, with different costs. A client can use
the cost map to select one of the application's IP addresses.

But at any given time, each of the application's IP addresses is in one,
and only one, PID.

The concept of an application as an entity with a number of different IP
addresses, possibly with different costs, is interesting, but so far is
beyond the scope of ALTO. BTW, that also raises the question of whether
those N addresses go to the same host, or whether they go to different
hosts that cooperate to provide a consistent service. And the next
question is whether a client would know -- or care -- whether an
application is distributed over a number of cooperating hosts.

	- Wendy Roome