Subject: [alto] New text on handling overlapping prefixes

From: "Y. Richard Yang" <[email-masked]>
Date: Sat, 9 Nov 2013 03:38:58 -0500

Dear all,

We have revised the document and handled all issues except the overlapping
prefixes. In the spirit of keeping the protocol simple, we propose the
following revision to handle the case. A fast action to resolve this final
issue will be greatly beneficial.

Thanks!

Richard

New text of Section 5.2:
---------------------------
5.2.  Endpoint Addresses

   The endpoints aggregated into a PID are denoted by endpoint
   addresses.  There are many types of addresses, such as IP addresses,
   MAC addresses, or overlay IDs.  This specification only considers IP
   addresses.

5.2.1.  IP Addresses

   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.

   A Network Map MUST define a PID for each possible address in the IP
   address space for all of the address types contained in the map.  A
   RECOMMENDED way to satisfy this property is to define a PID with the
   shortest enclosing prefix of the addresses provided in the map.  For
   a map with full IPv4 reachability, this would mean including the
   0.0.0.0/0 prefix in a PID; for full IPv6 reachability, this would be
   the ::/0 prefix.

   This document focuses on Network Maps that do not define two or more
   PIDs that contain an identical IP prefix.  We refer to such Network
   Maps as Non-Overlapping Network Maps.  To illustrate Non-Overlapping
   Network Maps, consider an example IPv4 Network Map NMa_A, which
   consists of two PIDs, where the first PID contains {10.0.0.0/15,
   0.0.0.0/0} and the second contains {10.0.0.0/16, 10.1.0.0/16}.  This
   is a Non-Overlapping Network Map. A variation of NMap_A, which can be
   derived by merging the two IP prefixes defined in the second PID of
   NMap_A as {10.0.0.0/15}, is not a Non-Overlapping Network Map.

   A Non-Overlapping Network Map ensures that the longest-prefix
   matching algorithm maps each endpoint represented by an IP address
   into exactly one PID.  Specifically, to map an IP address to its PID
   in a Non-Overlapping Network Map, one considers the set S which
   consists of all prefixes defined in the Network Map, applies the the
   longest-prefix mapping algorithm to S to identify the longest prefix
   containing the IP address, and assigns that the IP address belongs to
   the PID containing the identified longest prefix.  Consider the
   preceding example Network Map NMap_A. The IP address 10.0.0.1 will be
   identified as in the second PID.

   To handle both Non-Overlapping and Overlapping Network Maps, an ALTO
   Client moves any IP prefix that is defined in more than one PIDs into
   a special PID named .OVERLAP, and then applies the longest-prefix
   matching algorithm.  A future extension of this document may redefine
   how overlapping prefixes are handled.

5.3.  Example Network Map

   We use the Network Map shown in Figure 3 in most examples of this
   document.

   .------------------------------------------------------------.
   | An ALTO Network Map                                        |
   |                                                            |
   |  .-----------------------------------.  .----------------. |
   |  | NetLoc: PID-1                     |  | NetLoc: PID-3  | |
   |  |  .------------------------------. |  |                | |
   |  |  | 192.0.2.0/24                 | |  |  .-----------. | |
   |  |  | .--------------------------. | |  |  | 0.0.0.0/0 | | |
   |  |  | | Endpoint: 192.0.2.34     | | |  |  `-----------` | |
   |  |  | `--------------------------` | |  |                | |
   |  |  `------------------------------` |  |                | |
   |  |  .------------------------------. |  |                | |
   |  |  | 198.51.100.0/25              | |  |                | |
   |  |  | .--------------------------. | |  |                | |
   |  |  | | Endpoint: 198.51.100.100 | | |  |                | |
   |  |  | `--------------------------` | |  |                | |
   |  |  `------------------------------` |  |                | |
   |  `-----------------------------------`  |                | |
   |                                         |                | |
   |  .-----------------------------------.  |                | |
   |  | NetLoc: PID-2                     |  |                | |
   |  |  .------------------------------. |  |                | |
   |  |  | 198.51.100.128/25            | |  |                | |
   |  |  `------------------------------` |  |                | |
   |  `-----------------------------------`  `----------------` |
   `------------------------------------------------------------`

                      Figure 3: Example Network Map.

---

From: "Reinaldo Penno (repenno)" <[email-masked]>
Date: Sun, 10 Nov 2013 20:15:29 +0000

I'm not in agreement with the proposed solution because it puts even more burden on the client.  I think the question one needs to ask before the jumping head first on the engineering solution is: what harm can overlapped prefixes cause?

Assuming this would be a transient error condition, the worst possible situation is a client that flips a coin and picks a random PID. Remember that Applications that have ALTO clients should not rely on guidance to work, so an ALTO client should be always prepared to fall back to regular routing.

The ALTO Server operator by this time should have looked at some log entry, detected the problem and will work on fixing it.

-RP

From: "Y. Yang" <[email-masked]<mailto:[email-masked]>>
Date: Saturday, November 9, 2013 12:38 AM
To: IETF ALTO <[email-masked]<mailto:[email-masked]>>
Subject: [alto] New text on handling overlapping prefixes

---

From: "Y. Richard Yang" <[email-masked]>
Date: Sun, 10 Nov 2013 19:59:55 -0500

Hi Reinaldo,

I see that you put out two good perspectives:(1) additional burden on
client; and (2) what harm it can bring if multi-value PIDs.

Let me start with (1). I see burndens both in terms of programming
complexity, and in terms of performance. We compare three designs:
- D1: The original design, which bans Overlapping Network Maps;

- D2: The revised proposal, where a client is required to move the
duplicate prefixes into a special PID named .OVERLAP;

- D3: Multivalue PIDs.

I will use pseudocode to be as concrete as possible.

For these designs, a reasonable client implementation will need to use an
IP prefix matching library or write one. Assuming I am a naive programer, I
googled "ip prefix lookup linux library" and found this link, which points
out a perl(!) library:
http://search.cpan.org/~plonka/Net-Patricia-1.014/Patricia.pm

Here is the example code from the link:

  use Net::Patricia;

  my $pt = new Net::Patricia;

  $pt->add_string('127.0.0.0/8', \$user_data);
  $pt->match_string('127.0.0.1');
  $pt->match_exact_string('127.0.0.0');
  $pt->match_integer(2130706433); # 127.0.0.1

This is a typical library.

Here are what the programer needs to do to use the library:

Case 1: Assume our requirement that the ALTO Server sends only Non-Overlap
NetworkMap, then the programmer will just iterate over the Network Map and
add each prefix, something as:

 foreach pid
   for each prefix of pid
     $pt ->add_string(prefix, pid)

In other words, the programmer is assured that the user_data is the pid. If
a prefix is defined in multiple PIDs, the behavior will depend on the Trie
(or other data structures) insertion library. A high quality library will
see a duplicate and report an error, and an error-masking library may
overwrite the previous pid of the prefix. In other words, it depends on the
behavior of the library. If it is a production code and the library does
return an error if a duplicate, the client will need to check the return
value, with something as:

if ($pt->add_string(prefix, pid) == E_DUP) { //
   // How does the client handle the error?
}

Case 2: The revised proposal text. The client will need to remember the
duplicates:

foreach pid
  foreach prefix in pid
     dup_dect_map(prefix) ++; // use a hash map from string to counter
                                            // to detect duplicates
     if dup_dect_map(prefix) == 1 // a new prefix
        $pt->add_string(prefix, pid);
     else if (dup_dect_map(prefix) ==  2) // first dup detected
         $pt ->remove_string() // cannot be in its original pid
         $pt -> add_string(prefix, .OVERLAP);

Case 3: Allowing multi-value PIDs. The client will then need to keep track
of a set of the PIDs.

foreach pid
  foreach prefix in pid
              // mapped_PIDs is a hash map from prefix to a multi-set of
PIDs
     add pid to mapped_PIDs(prefix)

foreach key k of mapped_PIDs
   $pt->add_string(k, value of k in mapped_PIDs)

My personal judgement is that Case 2 and Case 3 are about equal complexity.
I like the revised proposal because it specifies a clear error handling
behavior and allows a way to go to the case of potential extension to
Overlapping Network Maps.

What do you think?

Now, consider the second good question: harm. I assume that it is Case 1.
The issue is that a good Client programmer needs to handle the errors, and
we, as the protocol designer, gives the client programmer a more explicit
guide on handling the error case.

As I said previously, I am fine with going with Case 1, and does not
specify how the client handles the error case, but we should proceed.

Richard

On Sun, Nov 10, 2013 at 3:15 PM, Reinaldo Penno (repenno) <[email-masked]
> wrote:

>  I'm not in agreement with the proposed solution because it puts even
> more burden on the client.
>
I think the question one needs to ask before the jumping head first on the
> engineering solution is: what harm can overlapped prefixes cause?
>
>  Assuming this would be a transient error condition, the worst possible
> situation is a client that flips a coin and picks a random PID. Remember
> that Applications that have ALTO clients should not rely on guidance to
> work, so an ALTO client should be always prepared to fall back to regular
> routing.
>
>  The ALTO Server operator by this time should have looked at some log
> entry, detected the problem and will work on fixing it.
>
>  -RP
>
>   From: "Y. Yang" <[email-masked]>
> To: IETF ALTO <[email-masked]>

-- 
-- 
 =====================================
| Y. Richard Yang <[email-masked]>   |
| Professor of Computer Science       |
| http://www.cs.yale.edu/~yry/        |
 =====================================

---

From: "Y. Richard Yang" <[email-masked]>
Date: Sun, 10 Nov 2013 21:35:39 -0500

To better, and quickly make a decision, here are two potential versions
(shown in context). A third option is to open the possibility of
multi-value PIDs, but this will involve major changes. A fourth option is
to allow Overlapping Network Maps, and say that a client can pick any one
value. This will add non-deterministic behaviors, which I personally prefer
that we avoid.

5.2.1.  IP Addresses

   A Network Map MUST define a PID for each possible address in the IP
   address space for all of the address types contained in the map.  *[V2]
We *
*   refer to this as the completeness property of a Network Map.[/V2]* A
   RECOMMENDED way to satisfy this property is to define a PID with the
   shortest enclosing prefix of the addresses provided in the map.  For
   a map with full IPv4 reachability, this would mean including the
   0.0.0.0/0 prefix in a PID; for full IPv6 reachability, this would be
   the ::/0 prefix.

   This document focuses on Network Maps where an identical IP prefix is
   do not included in two or more
   PIDs of the same Network Map. We refer to a Network
   Map with this property a Non-Overlapping Network Map.
   *[V2]This specification requires that a Network Map MUST be a
Non-Overlapping*
*   Network Map. *An extension may allow Overlapping Network Maps .*[/V2]*
    To illustrate Non-Overlapping
   Network Maps, consider an example IPv4 Network Map NMa_A, which
   consists of two PIDs, where the first PID contains {10.0.0.0/15,
   0.0.0.0/0} and the second contains {10.0.0.0/16, 10.1.0.0/16}.  This
   is a Non-Overlapping Network Map. A variation of NMap_A, which can be
   derived by merging the two IP prefixes defined in the second PID of
   NMap_A as {10.0.0.0/15}, is not a Non-Overlapping Network Map.

   [V1]To handle both Non-Overlapping and Overlapping Network Maps, an ALTO
   Client moves any IP prefix that is defined in more than one PIDs into
   a special PID named .OVERLAP, and then applies the longest-prefix
   matching algorithm.  [/V1]

On Sun, Nov 10, 2013 at 7:59 PM, Y. Richard Yang <[email-masked]> wrote:

> In other words, the programmer is assured that the user_data is the pid.
> If a prefix is defined in multiple PIDs, the behavior will depend on the
> Trie (or other data structures) insertion library. A high quality library
> will see a duplicate and report an error, and an error-masking library may
> My personal judgement is that Case 2 and Case 3 are about equal
> complexity. I like the revised proposal because it specifies a clear error
> handling behavior and allows a way to go to the case of potential extension
> to Overlapping Network Maps.
>
> What do you think?
>
> On Sun, Nov 10, 2013 at 3:15 PM, Reinaldo Penno (repenno) <
> [email-masked]> wrote:
>