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. 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. *[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.
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.
[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 protected]> wrote:
> 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 protected]> 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 protected]>
>> Date: Saturday, November 9, 2013 12:38 AM
>> To: IETF ALTO <[email protected]>
>> Subject: [alto] New text on handling overlapping prefixes
>>
>> 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.
>>
>
>
>
> --
> --
> =====================================
> | Y. Richard Yang <[email protected]> |
> | Professor of Computer Science |
> | http://www.cs.yale.edu/~yry/ |
> =====================================
>
--
--
=====================================
| Y. Richard Yang <[email protected]> |
| Professor of Computer Science |
| http://www.cs.yale.edu/~yry/ |
=====================================
_______________________________________________
alto mailing list
[email protected]
https://www.ietf.org/mailman/listinfo/alto
