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

From: Sebastian Kiesel <[email-masked]>
Date: Fri, 1 Nov 2013 20:13:03 +0100

Dear all,

Let's focus on IP prefixes in PID definitions as this has to be
clarified before the protocol document can be finalized.
In other words we are talking about section 5.2.1 of
draft-ietf-alto-protocol-20.txt.

it seems that we could not agree on a tiebreaker algorithm to be
used by the client if it receives a network map defining multiple
PIDs each containing the same IP prefix.

Let me try to summarize with two examples:

MapA:  A1 = 10.0.0.0/15
       A2 = 10.0.0.0/16, 10.1.0.0/16

is legal, and 10.0.0.1 should be in A2

this is what follows from the current specification, though it may
be surprising to some of us.

MapB:  B1 = 10.0.0.0/15
       B2 = 10.0.0.0/15, 192.168.0.0/16

is NOT legal.

So my proposal to move forward:  

1. clarify that this kind of map as in example B is illegal:

In Sec. 5.2.1:

Old:

   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.

Replace with:

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

2. optional: specify client behavior in this error condition

Append a sentence at the end of 5.2.1.

    If an ALTO client receives an invalid network map defining two or
    more PIDs that contain an identical IP prefix, the ALTO client
    SHOULD ignore that prefix and behave as if the prefix did not occur
    in any PID definition.

or:

    If an ALTO client receives an invalid network map defining two or
    more PIDs that contain an identical IP prefix, the ALTO client
    SHOULD completely ignore the complete network map.

3. optional:  add a clarification that example A above is legal and A2
is the result.

I think that we should add 1) and the first text proposal for 2).
I don't think that we need 3) but I will not object if someone
comes up with a good text proposal.

Comments?

Thanks
Sebastian

---

From: Wendy Roome <[email-masked]>
Date: Fri, 01 Nov 2013 16:27:30 -0400

I don't like saying that the client should just ignore all occurrences of
a duplicate CIDR. I think that if the server created a map with duplicate
CIDRs, the server has a major problem, and I wouldn't trust that server.

After all, even if a server automatically creates the network map from
network data, how hard would it be for the server to test for and remove
duplicates?  Especially because we expect the client to be smart enough to
detect duplicates??

There's an old saying: If you add a teaspoon of excrement to a barrel of
fine wine, you have a barrel of excrement. If a network map has duplicate
CIDRs, I think that network map is junk.

 	- Wendy Roome

---

From: Sebastian Kiesel <[email-masked]>
Date: Fri, 1 Nov 2013 21:56:29 +0100

Hi Wendy,

so you are saying that for issue 2) we should go with the second
text proposal?  I don't have strong feelings about that.

What about 3) ?  Do you want to propose text? Or should we go without
a clarification?

Thanks
Sebastian

---

From: Wendy Roome <[email-masked]>
Date: Mon, 04 Nov 2013 09:18:15 -0500

Actually I'm in favor or the second alternative for #2 -- ignore the map

>    SHOULD completely ignore the complete network map.

Sorry for the confusion! I thought that was #3.

	- Wendy

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 4 Nov 2013 15:44:23 +0100

Hi Wendy,

so the conclusion is: 
at the end of section 5.2.1 of draft-ietf-alto-protocol-20.txt,
we REMOVE

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

and ADD instead

+   A network map MUST NOT define two or more PIDs that contain
+   an identical IP prefix, in order to ensure that the longest-prefix
+   matching algorithm maps each endpoint into exactly one PID.
+
+   If an ALTO client receives an invalid network map defining two or
+   more PIDs that contain an identical IP prefix, the ALTO client
+   SHOULD completely ignore the whole network map.

OK? I support this change.

Do you think we should add another paragraph saying that

    MapA:  A1 = 10.0.0.0/15

?  I don't think that this is neccesssary but I won't object against
adding an explicit statement.

What do you think?

Thanks
Sebastian

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 4 Nov 2013 15:41:58 +0000

I disagree.  The central question is not whether an IP prefix can appear
in more than one PID but rather if we allow overlapping PIDs.

For example, what if we use MAC addresses, can they appear in more than
one PID? The new text does not cover that.

Whether a client ignores the whole map or not is implementation dependent.
It can provide an error only for those IP addresses that fall within the
prefix, still using the rest of the map. Or can just choose one PID at
random as tie break.

On 11/4/13 6:44 AM, "Sebastian Kiesel" <[email-masked]> wrote:

>> >> I don't like saying that the client should just ignore all
>>occurrences
>> >>of
>> >> duplicates?  Especially because we expect the client to be smart
>>enough
>> >>to
>> >> detect duplicates??
>> >>

---

From: Sebastian Kiesel <[email-masked]>
Date: Mon, 4 Nov 2013 17:11:10 +0100

Reinaldo,

> one PID? The new text does not cover that.

section 5.2.1 is about the endpoint address type "IP address".
This is what has to be resolved before we can publish the base protocol.

If you want to use MAC addresses as endpoint addresses, you will have
to write a separate document that defines this address type, which may
define other rules regarding m:n mappings to PIDs.

> prefix, still using the rest of the map. Or can just choose one PID at

I think it does make sense to mandate a client behavior.

If we can agree on a specific tie break algorithm, fine. If we agree to
say "just ignore the prefix in question but not the whole map", fine.
But I think we should agree on something.

We shouldn't repeat the good old days of the WWW, where web servers sent
special versions of the content to some user agents as workaround for
known bugs in these browsers, and user agents pretended to be a
different one to get the "right" content ...

Just my $0.02
Sebastian

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 4 Nov 2013 17:06:26 +0000

>This is what has to be resolved before we can publish the base protocol.

The current text seems perfect fine.

>different one to get the "right" content ...

I do not think this we are comparing apples to apples.

A better comparison is: If a router gets a bad route (say, pointing back
to its own interface) , does it throw away the entire routing table?

If client throws away the entire map, it has no guidance, falls back to
regular behavior 
If client disregard only that prefix, it falls back to regular behavior
for that prefix.

---

From: Wendy Roome <[email-masked]>
Date: Mon, 04 Nov 2013 12:30:17 -0500

If the client just discards the both instances of the duplicate CIDR, in
most cases, the endpoint addresses under that CIDR will end up in the
default PID -- the one with 0.0.0.0/0. As a result, the costs to or from
those endpoints are probably useless.

Here's another alternative: if a client detects a duplicate CIDR, the
client removes that CIDR from all PIDs, and adds it to a list of
"duplicate CIDRs". When the client maps an address to a PID, if the
longest prefix match is a CIDR in the "duplicate" list, then the client
assumes that the ALTO server cannot return a cost to or from that
endpoint. Eg, the cost is unknown.

A client could easily implement that by creating a PID with an otherwise
invalid name, like "*DUPLICATES*", and moving those CIDRs to that phantom
PID. The ALTO server will never return that PID in a cost map, so to the
client, the costs for those addresses are unknown.

	- Wendy Roome

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 4 Nov 2013 17:37:41 +0000

>those endpoints are probably useless.

This is like saying all IP prefixes that fall under the the default PID
are useless which is clearly not the case. There are many prefixes that
will map to the default PID that will have a default cost.

>"duplicate CIDRs".

ALTO client should be dead simple. In the very beginning of ALTO protocol
Bittorrent folks mentioned that a ALTO client should be able to work by
simply downloading a text file from a well known URL/IP address and doing
longest prefix matching so that it could be implemented in the simple
devices like sensors. This is something I still believe we should strive
for. 

>When the client maps an address to a PID, if the

---

From: Wendy Roome <[email-masked]>
Date: Mon, 04 Nov 2013 13:06:06 -0500

I think we've already lost that battle.  First, the client has to
understand HTTP 1.1, including features like chunking.  Second, JSON is
simpler than XML, but it's not trivial to parse.  Third, the client really
should understand the IRD to select the default network map and associated
cost map resources, because the server may change the resource uris at any
time. And finally, the client should detect duplicate CIDRs.

If you really want to simplify things for a sensor, then some other ALTO
client can retrieve the network map from the ALTO server, eliminate
duplicates, recast the network map as (CIDR,PID) pairs, sort by increasing
CIDR length, write the result into a plain text file in some web server,
and give the uri to the simple client. The simple client reads the
(CIDR,PID) pairs and matches against the CIDRs. First match gives the PID.

	- Wendy Roome

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Mon, 4 Nov 2013 18:13:50 +0000

On 11/4/13 10:06 AM, "Wendy Roome" <[email-masked]> wrote:

>simpler than XML, but it's not trivial to parse.

We were behind changing from XML to JSON. So, this was a conscious choice.
The original protocol was XML based.

>Third, the client really

This we should *definitely* fix. If you/folks are at Vancouver we should
sit down and try to hash this out. We should have a _always work_, URI,
_fall back_ default network and cost map.