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/ | =====================================
_______________________________________________ alto mailing list [email protected] https://www.ietf.org/mailman/listinfo/alto
