Subject: [icnrg] "Name Segment Hashing" @ 16th ICNRG meeting (Interim)

From: Massimo Gallo <[email-masked]>
Date: Tue, 14 Apr 2015 18:17:05 +0200

Dear all, Irecently take a look to the material of the last icnrg 
meeting at Dallas and I have few comments/clarifications about Marc's 
presentation.

1.Marc report as main result (citation from the slides)/://Unlike ALU 
evaluation, we find no penalty for using 2+2 encoding, especially for 
randomly distributed name lengths/.In Boston I presented the cost of 
computing all the required hashes given that the LPM is a k-components 
name prefix. In this case there is indeed a penalty in computing all the 
hashes with the all-in-one method.  Marc's evaluation does not account 
for that penalty as it only reports the cost of computing a hash for a 
k-component name prefix without taking into account the longest prefix 
match length (NB not the cost of performing the FIB lookup itself).See 
point 3 for clarifications.

2. I have general a comment on the methodology used to produce the 
results presented by Marc in the slides (link 
<https://www.ietf.org/proceedings/interim/2015/03/22/icnrg/slides/slides-interim-2015-icnrg-2-0.pptx>). 
Marc points out he follows the Intel benchmarking technique (Link 
<1.%20http:/www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmark-code-execution-paper.pdf>). 
Our evaluation is  performed using an Intel DPDK implementation. In DPDK 
there is a function called rte_rdtsc_precise() that ensures the cycle 
reading operation is performed exactly in the desired place. Hence, our 
methodology is conformant to the Intel benchmarking methodology.

3. I have a comment on the comparison Marc makes between what I 
presented in Boston and Dallas presentation(link 
<https://www.ietf.org/proceedings/interim/2015/03/22/icnrg/slides/slides-interim-2015-icnrg-2-0.pptx>,slide 
16).  The two curves do not report the same thing:
     - Marc's performance curve reports the number of cycles used to 
computing the hash of the name with  N components (with N=1,2,...5)
    - The performance curve that I presented in Boston reports the 
number of cycles used to computing all the required hashes + packet 
parse (not FIB lookup) given the fact that the LPM (longest prefix 
match) is an N components prefix (N=1,2,3,4,5). I assume the following 
basic lookup technique to find the LPM: search for N components prefix 
match (say the full name in this analysis), in case of no match search 
the N-1 components prefix match and so on up to the 1 component prefix.

To clarify:
     - name_prefix(k) is the k-components name prefix
     - hash(name_prefix(k)) is the hash computation of the k-components 
name prefix
     - PPC = Packet Parsing Cost

Hence I report the following cost assuming k is the LPM prefix match 
lengths:

k = 1 => hash(sum_k=1,...,5 name_prefix(k))+ PPC
k = 2 => hash(sum_k=2,...,5 name_prefix(k))+ PPC
k = 3 => hash(sum_k=3,...,5 name_prefix(k))+ PPC
k = 4 => hash(sum_k=4,...,5 name_prefix(k))+ PPC
k = 5 => hash(name_prefix(5))+ PPC

being PPC = packet parsing cost

If I am not wrong, Marc reports   k vs  hash(name_prefix(k))

That explains why my curve is decreasing and Marc's is increasing with 
increasing k. I hope this clarifies the differences between the two set 
of experiments.

Regards
Max

---

From: <[email-masked]>
Date: Tue, 14 Apr 2015 23:43:36 +0000

Max,

Thank you for clarifying some of these points.  Please see comments below.

On Apr 14, 2015, at 9:17 AM, Massimo Gallo <[email-masked]<mailto:[email-masked]>> wrote:

Dear all, I recently take a look to the material of the last icnrg meeting at Dallas and I have few comments/clarifications about Marc's presentation.

1.     Marc report as main result (citation from the slides): Unlike ALU evaluation, we find no penalty for using 2+2 encoding, especially for randomly distributed name lengths. In Boston I presented the cost of computing all the required hashes given that the LPM is a k-components name prefix. In this case there is indeed a penalty in computing all the hashes with the all-in-one method.  Marc’s evaluation does not account for that penalty as it only reports the cost of computing a hash for a k-component name prefix without taking into account the longest prefix match length (NB not the cost of performing the FIB lookup itself). See point 3 for clarifications.

I did not consider anything beyond calculating the hash for performing the FIB lookup.  AFAIK, doing the LMP FIB lookup will require the same time regardless of encoding (ok, if one is longer the memcmp to compare hash table keys might be slightly longer).

In the result slides, e.g. slide 13, there are two data sets.  The first data set of solid lines is the one-by-one hash time.  The second data set of dashed lines are to hash all at once out to k components.  So, if you have a strategy of starting, for example, at name component 5 and want to hash out to there first then backup, this data set shows the time to hash all the way out to 5.

2. I have general a comment on the methodology used to produce the results presented by Marc in the slides (link<https://www.ietf.org/proceedings/interim/2015/03/22/icnrg/slides/slides-interim-2015-icnrg-2-0.pptx>). Marc points out he follows the Intel benchmarking technique (Link<x-msg://15/1.%20http:/www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmark-code-execution-paper.pdf>). Our evaluation is  performed using an Intel DPDK implementation. In DPDK there is a function called rte_rdtsc_precise() that ensures the cycle reading operation is performed exactly in the desired place. Hence, our methodology is conformant to the Intel benchmarking methodology.

Then I believe we are doing the same method for measuring time.

During the session, it was suggested that the difference on slide 15 (10Bx6) between the ALU format and the 2+2 format could be cache misses.  I plan on re-running these tests using a random order to prevent the CPU from pre-fetching data so in all cases there should be a cache miss.

3. I have a comment on the comparison Marc makes between what I presented in Boston and Dallas presentation(link<https://www.ietf.org/proceedings/interim/2015/03/22/icnrg/slides/slides-interim-2015-icnrg-2-0.pptx>,slide 16).  The two curves do not report the same thing:
    - Marc’s performance curve reports the number of cycles used to computing the hash of the name with  N components (with N=1,2,…5)
   - The performance curve that I presented in Boston reports the number of cycles used to computing all the required hashes  + packet parse (not FIB lookup) given the fact that the LPM (longest prefix match) is an N components prefix (N=1,2,3,4,5). I assume the following basic lookup technique to find the LPM: search for N components prefix match (say the full name in this analysis), in case of no match search the N-1 components prefix match and so on up to the 1 component prefix.

To clarify:
    - name_prefix(k) is the k-components name prefix
    - hash(name_prefix(k)) is the hash computation of the k-components name prefix
    - PPC = Packet Parsing Cost

Hence I report the following cost assuming k is the LPM prefix match lengths:

k = 1 => hash(sum_k=1,…,5 name_prefix(k))+ PPC
k = 2 => hash(sum_k=2,…,5 name_prefix(k))+ PPC
k = 3 => hash(sum_k=3,…,5 name_prefix(k))+ PPC
k = 4 => hash(sum_k=4,…,5 name_prefix(k))+ PPC
k = 5 => hash(name_prefix(5))+ PPC

That explains why my curve is decreasing and Marc's is increasing with increasing k. I hope this clarifies the differences between the two set of experiments.

The times I report include parsing the name (or name plus offset vector in the ALU case) to determine the byte boundaries.  That might not be the exact same as your PPC, but it’s not 0 in my tests either. It does not include time to process the rest of the packet to get to the name.

I will repeat my tests using the formula you give here and share that with the list.

Regards
Max

_______________________________________________
icnrg mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/icnrg

---

From: Massimo Gallo <[email-masked]>
Date: Wed, 15 Apr 2015 09:37:55 +0200

I realized there is also a mismatch in the definitions "all-in-one" and 
"multiple". Let's stick to the definition you give on slide 6 of the 
Dallas presentation:

- All in one: hash all the name components (up to prefix length you are 
trying to match in the FIB ) then match backwards in the FIB.

-multiple: do a component by component hash (and obtain the complete set 
of hases of all the name prefixes of length k=1,..,5)

Now that we have a common definition, take the case of what you call 
"all in one" hash calculation (explained in slide 6 of you pres.). 
According to what I print in my curves, it is strictly impossible 
(unless you perform wired things) that having a match at name prefix len 
k=4 costs less (in terms of hash calculation) than having the match at 
k=5. Indeed, if you expand the formula I gave, you obtain:

Formula: [sum_k=1,...,5 hash(name_prefix(k)) ]+ PPC.            I 
rewrote it in a clearer way here.

k=4 hash(name_prefix(5))+ hash(name_prefix(4)) + PPC
k=5 hash(name_prefix(5)) + PPC

Also, If you consider the "multiple hash" technique,  you compute all 
the hashes of the name prefix at length k=1,..,5 while parsing the name. 
Hence, you always have to compute all the hashes while parsing the name 
and you use a subset of them, according to the length of the prefix 
match. Hence, what is printed in my slides for "multiple hash" is:

For each k, [sum_k=1,..5 hash(name_prefix(k))]+ PPC

Hope that helps in clarifying the differences.

Regards Max

On 15/04/2015 01:43, [email-masked] wrote:
> On Apr 14, 2015, at 9:17 AM, Massimo Gallo 
> <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>> computing all the required hashes given that the LPM is a 
>> k-components name prefix. In this case there is indeed a penalty in 
>> computing all the hashes with the all-in-one method.  Marc's 
>> evaluation does not account for that penalty as it only reports the 
>> cost of computing a hash for a k-component name prefix without taking 
>> into account the longest prefix match length (NB not the cost of 
>> performing the FIB lookup itself).See point 3 for clarifications.
>
> I did not consider anything beyond calculating the hash for performing 
> the FIB lookup.  AFAIK, doing the LMP FIB lookup will require the same 
> time regardless of encoding (ok, if one is longer the memcmp to 
> compare hash table keys might be slightly longer).
>
> In the result slides, e.g. slide 13, there are two data sets.  The 
> first data set of solid lines is the one-by-one hash time.  The second 
> data set of dashed lines are to hash all at once out to k components. 
>  So, if you have a strategy of starting, for example, at name 
> component 5 and want to hash out to there first then backup, this data 
> set shows the time to hash all the way out to 5.
>>
>> <x-msg://15/1.%20http:/www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmark-code-execution-paper.pdf>). 
>> Our evaluation is  performed using an Intel DPDK implementation. In 
>> DPDK there is a function called rte_rdtsc_precise() that ensures the 
>> cycle reading operation is performed exactly in the desired place. 
>> Hence, our methodology is conformant to the Intel benchmarking 
>> methodology.
>>
> During the session, it was suggested that the difference on slide 15 
> (10Bx6) between the ALU format and the 2+2 format could be cache 
> misses.  I plan on re-running these tests using a random order to 
> prevent the CPU from pre-fetching data so in all cases there should be 
> a cache miss.
>>
>> match) is an N components prefix (N=1,2,3,4,5). I assume the 
>> following basic lookup technique to find the LPM: search for N 
>> components prefix match (say the full name in this analysis), in case 
>> of no match search the N-1 components prefix match and so on up to 
>> the 1 component prefix.
>>
>> To clarify:
>> That explains why my curve is decreasing and Marc's is increasing 
>> with increasing k. I hope this clarifies the differences between the 
>> two set of experiments.
>>
> The times I report include parsing the name (or name plus offset 
> vector in the ALU case) to determine the byte boundaries.  That might 
> not be the exact same as your PPC, but it's not 0 in my tests either. 
> It does not include time to process the rest of the packet to get to 
> the name.
>
>> [email-masked] <mailto:[email-masked]>
> [email-masked]