From owner-psamp@ops.ietf.org Tue Feb 1 05:29:26 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA11578 for ; Tue, 1 Feb 2005 05:29:25 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1CvvAJ-000Ccl-01 for psamp-data@psg.com; Tue, 01 Feb 2005 10:21:47 +0000 Received: from [128.30.2.16] (helo=rozz.csail.mit.edu) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1Cvr81-0003tj-EA for psamp@ops.ietf.org; Tue, 01 Feb 2005 06:03:09 +0000 Received: from cs6625145-173.austin.rr.com ([66.25.145.173] helo=[192.168.0.101]) by rozz.csail.mit.edu with esmtpsa (TLSv1:RC4-MD5:128) (Exim 4.43) id 1Cvr7v-0002zY-DI; Tue, 01 Feb 2005 01:03:03 -0500 Message-ID: <41FF1B78.2080508@ece.utexas.edu> Date: Tue, 01 Feb 2005 00:02:32 -0600 From: Derek Chiou User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Stewart Bryant CC: duffield@research.att.com, abierman@cisco.com, quittek@netlab.nec.de, psamp@ops.ietf.org Subject: Re: Hashing function for PSAMP References: <387B5A9BF31B5D43A2B18DD9F326B8E191543B@NJFPSRVEXG2KCL.research.att.com> <41FE51A4.2090902@cisco.com> In-Reply-To: <41FE51A4.2090902@cisco.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Happy is a difficult thing to say. I agree with Stewart. In general, if a router doesn't support it today, it won't. Hardware cannot be changed and NP resources in extant boxes are already stretched to the limit. That said, CRC32 is not a big deal in new hardware; my expectation is that the same is true for BOB (I'm not familiar with it.) Thus, if it's a real requirement that router manufacturers see it as a serious differentiator that sells boxes, you will see it in future products. Stewart Bryant wrote: > >> Are router development folks happy with the computational requirement >> for BOB (or CRC32) to be computed on every packet, if it is used as the >> selection hash? > > > The short answer is NO ): > > A lot depends on where you imagine this will be deployed. > On a pure s/w edge router there will be a measurable > headline performance hit with either of these, but perhaps > that does not matter in that environment. On a hardware > /microcoded core router, I would say that the chances > of getting either in the main path of existing hardware > are for all practical purposes zero. > > If you were thinking that they would be run after > some primary sampler at a relatively low packet rate > in the export process, then there is less of an issue. > > You canot use the existing CRC32 hardware to perform the > hash. So both BOB and CRC32 would need new hardware or > would need to be performed in software/microcode. > > Software CRC32 implementations trade lookup table space > for compute cycles. Both of these resources are in > critically short supply on a high-end forwarder. > Even if you did find the resources (and on many > implementations they would simply not be available) > the result would be a crippling hit on headline > forwarding performance. > > I have not done a detailed comparison of BOB and CRC32 > execution speeds, but my first impression is that BOB > takes even more cycles to execute than CRC32 although > perhaps not if you take into account the cache stalls > in doing the table fetch. > > - Stewart > > > > > > -- > to unsubscribe send a message to psamp-request@ops.ietf.org with > the word 'unsubscribe' in a single line as the message text body. > archive: -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Tue Feb 1 08:29:06 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id IAA00410 for ; Tue, 1 Feb 2005 08:29:05 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1Cvxva-000BH0-1M for psamp-data@psg.com; Tue, 01 Feb 2005 13:18:46 +0000 Received: from [195.37.70.40] (helo=smtp2.netlab.nec.de) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1CvxvP-000BGD-FE for psamp@ops.ietf.org; Tue, 01 Feb 2005 13:18:35 +0000 Received: from europa.office (europa.office [10.1.1.2]) by smtp2.netlab.nec.de (Postfix) with ESMTP id 5C42D1F6D7 for ; Tue, 1 Feb 2005 14:20:48 +0100 (CET) X-MimeOLE: Produced By Microsoft Exchange V6.5.7226.0 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Subject: RE: Hashing function for PSAMP Date: Tue, 1 Feb 2005 14:18:34 +0100 Message-ID: Thread-Topic: Hashing function for PSAMP Thread-Index: AcUISNEp3MfRZauCTXW4ONetIEVYXgAE6q6Q From: "Saverio Niccolini" To: X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.1 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: quoted-printable Dear all, what you are saying applies to BOB, CRC32 or IPSX as to other hash functions. Then your suggestions are just NOT to use a hash function as selection method... This is understandable but it is not what the question was about. I think what it is important here is to think: IF we are going to use a hash packet based sampling, are you happy with=20 BOB (or CRC32) or would you prefer to see IPSX in the RFC? And this leads us to the question from Juergen Quittek: 1. Make IPSX mandatory for IPv4 packet selection and BOB mandatory for IPv6 packet selection. Then, with BOB implemented anyway, we should then replace CRC32 with BOB for packet digest, because both perform similarly and there is no good reason for forcing implementors to support also a third hash function. 2. Just make BOB mandatory for packet selection and packet digest. This would simplify implementation, because only a single function is required. For packet digest this should be OK, see 1. A disadvantage is that BOB is slower than IPSX by factor 7. An advantage is, that BOB is free of IPR, while IPSX is protected by a patent. Looking at your answer it seems to me that you can easily say: I prefer (2). Since one function or another is anyway not good for what you have in mind, the option number (2) gives you the chance of implementing only one hash function (instead of two) that you are not going to use anyway. Regards, Saverio P.S.: from the software implementation that we have tested, we saw that CRC32 is 4 times slower than BOB (86 ns of execution time for BOB against 320 ns for CRC32). The absolute numbers are relative to our PC characteristics but the relative numbers should be right. > -----Original Message----- > From: owner-psamp@ops.ietf.org=20 > [mailto:owner-psamp@ops.ietf.org] On Behalf Of Derek Chiou > Sent: Tuesday, February 01, 2005 7:03 AM > To: Stewart Bryant > Cc: duffield@research.att.com; abierman@cisco.com; Juergen=20 > Quittek; psamp@ops.ietf.org > Subject: Re: Hashing function for PSAMP >=20 > Happy is a difficult thing to say. >=20 > I agree with Stewart. In general, if a router doesn't=20 > support it today, it won't. Hardware cannot be changed and=20 > NP resources in extant boxes are already stretched to the limit. >=20 > That said, CRC32 is not a big deal in new hardware; my=20 > expectation is that the same is true for BOB (I'm not=20 > familiar with it.) Thus, if it's a real requirement that=20 > router manufacturers see it as a serious differentiator that=20 > sells boxes, you will see it in future products. >=20 >=20 > Stewart Bryant wrote: >=20 > > > >> Are router development folks happy with the computational=20 > requirement=20 > >> for BOB (or CRC32) to be computed on every packet, if it=20 > is used as=20 > >> the selection hash? > > > > > > The short answer is NO ): > > > > A lot depends on where you imagine this will be deployed. > > On a pure s/w edge router there will be a measurable headline=20 > > performance hit with either of these, but perhaps that does=20 > not matter=20 > > in that environment. On a hardware /microcoded core router, I would=20 > > say that the chances of getting either in the main path of existing=20 > > hardware are for all practical purposes zero. > > > > If you were thinking that they would be run after some=20 > primary sampler=20 > > at a relatively low packet rate in the export process, then=20 > there is=20 > > less of an issue. > > > > You canot use the existing CRC32 hardware to perform the=20 > hash. So both=20 > > BOB and CRC32 would need new hardware or would need to be=20 > performed in=20 > > software/microcode. > > > > Software CRC32 implementations trade lookup table space for compute=20 > > cycles. Both of these resources are in critically short supply on a=20 > > high-end forwarder. > > Even if you did find the resources (and on many=20 > implementations they=20 > > would simply not be available) the result would be a=20 > crippling hit on=20 > > headline forwarding performance. > > > > I have not done a detailed comparison of BOB and CRC32 execution=20 > > speeds, but my first impression is that BOB takes even more=20 > cycles to=20 > > execute than CRC32 although perhaps not if you take into=20 > account the=20 > > cache stalls in doing the table fetch. > > > > - Stewart > > > > > > > > > > > > -- > > to unsubscribe send a message to psamp-request@ops.ietf.org=20 > with the=20 > > word 'unsubscribe' in a single line as the message text body. > > archive: >=20 >=20 > -- > to unsubscribe send a message to psamp-request@ops.ietf.org=20 > with the word 'unsubscribe' in a single line as the message text body. > archive: >=20 -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Tue Feb 1 09:10:09 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id JAA05001 for ; Tue, 1 Feb 2005 09:10:09 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1Cvyeg-0006Jp-NL for psamp-data@psg.com; Tue, 01 Feb 2005 14:05:22 +0000 Received: from [144.254.224.140] (helo=ams-iport-1.cisco.com) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1Cvyed-0006JJ-C9 for psamp@ops.ietf.org; Tue, 01 Feb 2005 14:05:19 +0000 Received: from ams-core-1.cisco.com (144.254.224.150) by ams-iport-1.cisco.com with ESMTP; 01 Feb 2005 15:15:12 +0100 X-BrightmailFiltered: true X-Brightmail-Tracker: AAAAAA== Received: from cisco.com (mrwint.cisco.com [64.103.71.48]) by ams-core-1.cisco.com (8.12.10/8.12.6) with ESMTP id j11E5FPm028151; Tue, 1 Feb 2005 15:05:15 +0100 (MET) Received: from cisco.com (dhcp-rea-gp250-64-103-65-45.cisco.com [64.103.65.45]) by cisco.com (8.8.8-Cisco List Logging/8.8.8) with ESMTP id OAA05500; Tue, 1 Feb 2005 14:05:15 GMT Message-ID: <41FF8C9A.5070308@cisco.com> Date: Tue, 01 Feb 2005 14:05:14 +0000 From: Stewart Bryant User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.4) Gecko/20030624 Netscape/7.1 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Saverio Niccolini CC: psamp@ops.ietf.org Subject: Re: Hashing function for PSAMP References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Saverio Niccolini wrote: > Dear all, > what you are saying applies to BOB, CRC32 or IPSX as to other hash > functions. > Then your suggestions are just NOT to use a hash function as selection > method... We were answering the exact question that we were asked :) > This is understandable but it is not what the question was about. > > I think what it is important here is to think: > IF we are going to use a hash packet based sampling, are you happy with > BOB (or CRC32) or would you prefer to see IPSX in the RFC? > From a pure forwarding point of view, we need an algorithm that is easy to imlement in harware, and easy to execute in a typical microcode engine. Typical forwarding microcode engines have fast access to a tiny fraction of the packet. A very simple instruction set. A tiny register set. A massive cost of fetching anything else from memory. > And this leads us to the question from Juergen Quittek: > 1. Make IPSX mandatory for IPv4 packet selection and BOB mandatory > for IPv6 packet selection. > Then, with BOB implemented anyway, we should then replace CRC32 > with BOB for packet digest, because both perform similarly and > there is no good reason for forcing implementors to support also > a third hash function. > > 2. Just make BOB mandatory for packet selection and packet digest. > This would simplify implementation, because only a single function > is required. For packet digest this should be OK, see 1. > A disadvantage is that BOB is slower than IPSX by factor 7. > An advantage is, that BOB is free of IPR, while IPSX is protected > by a patent. > > Looking at your answer it seems to me that you can easily say: > I prefer (2). > Since one function or another is anyway not good for what you have in > mind, > the option number (2) gives you the chance of implementing only one hash > function > (instead of two) that you are not going to use anyway. > > Regards, > Saverio > > P.S.: from the software implementation that we have tested, we saw that > CRC32 > is 4 times slower than BOB (86 ns of execution time for BOB against 320 > ns for CRC32). > The absolute numbers are relative to our PC characteristics but the > relative numbers > should be right. Timing the execution on a PC is interesting, but does not tell you much about execution performance on a forwarder. The environments are very different. Also you need to specify the CRC32 algorithm that you were using, and assuming that you were using a table algorithm, the table size needs to be stated. - Stewart > > >>-----Original Message----- >>From: owner-psamp@ops.ietf.org >>[mailto:owner-psamp@ops.ietf.org] On Behalf Of Derek Chiou >>Sent: Tuesday, February 01, 2005 7:03 AM >>To: Stewart Bryant >>Cc: duffield@research.att.com; abierman@cisco.com; Juergen >>Quittek; psamp@ops.ietf.org >>Subject: Re: Hashing function for PSAMP >> >>Happy is a difficult thing to say. >> >>I agree with Stewart. In general, if a router doesn't >>support it today, it won't. Hardware cannot be changed and >>NP resources in extant boxes are already stretched to the limit. >> >>That said, CRC32 is not a big deal in new hardware; my >>expectation is that the same is true for BOB (I'm not >>familiar with it.) Thus, if it's a real requirement that >>router manufacturers see it as a serious differentiator that >>sells boxes, you will see it in future products. >> >> >>Stewart Bryant wrote: >> >> >>>>Are router development folks happy with the computational >> >>requirement >> >>>>for BOB (or CRC32) to be computed on every packet, if it >> >>is used as >> >>>>the selection hash? >>> >>> >>>The short answer is NO ): >>> >>>A lot depends on where you imagine this will be deployed. >>>On a pure s/w edge router there will be a measurable headline >>>performance hit with either of these, but perhaps that does >> >>not matter >> >>>in that environment. On a hardware /microcoded core router, I would >>>say that the chances of getting either in the main path of existing >>>hardware are for all practical purposes zero. >>> >>>If you were thinking that they would be run after some >> >>primary sampler >> >>>at a relatively low packet rate in the export process, then >> >>there is >> >>>less of an issue. >>> >>>You canot use the existing CRC32 hardware to perform the >> >>hash. So both >> >>>BOB and CRC32 would need new hardware or would need to be >> >>performed in >> >>>software/microcode. >>> >>>Software CRC32 implementations trade lookup table space for compute >>>cycles. Both of these resources are in critically short supply on a >>>high-end forwarder. >>>Even if you did find the resources (and on many >> >>implementations they >> >>>would simply not be available) the result would be a >> >>crippling hit on >> >>>headline forwarding performance. >>> >>>I have not done a detailed comparison of BOB and CRC32 execution >>>speeds, but my first impression is that BOB takes even more >> >>cycles to >> >>>execute than CRC32 although perhaps not if you take into >> >>account the >> >>>cache stalls in doing the table fetch. >>> >>>- Stewart >>> >>> >>> >>> >>> >>>-- >>>to unsubscribe send a message to psamp-request@ops.ietf.org >> >>with the >> >>>word 'unsubscribe' in a single line as the message text body. >>>archive: >> >> >>-- >>to unsubscribe send a message to psamp-request@ops.ietf.org >>with the word 'unsubscribe' in a single line as the message text body. >>archive: >> > > -- > to unsubscribe send a message to psamp-request@ops.ietf.org with > the word 'unsubscribe' in a single line as the message text body. > archive: > > -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Sun Feb 13 18:14:05 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA04861 for ; Sun, 13 Feb 2005 18:14:04 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D0Sok-0008HX-Id for psamp-data@psg.com; Sun, 13 Feb 2005 23:06:18 +0000 Received: from [144.254.15.119] (helo=strange-brew.cisco.com) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D0Soj-0008HG-A5 for psamp@ops.ietf.org; Sun, 13 Feb 2005 23:06:17 +0000 Received: from [10.59.24.3] ([10.59.24.3]) by strange-brew.cisco.com (8.11.7p1+Sun/8.8.8) with ESMTP id j1DN6E100241 for ; Mon, 14 Feb 2005 00:06:15 +0100 (CET) Message-ID: <420FB874.7000702@cisco.com> Date: Sun, 13 Feb 2005 21:28:36 +0100 From: Benoit Claise User-Agent: Mozilla Thunderbird 1.0 (Windows/20041206) X-Accept-Language: en-us, en MIME-Version: 1.0 To: psamp Subject: some more comments on draft-ietf-psamp-sample-tech-05.txt Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Dear all, In order to produce the next version of the PSAMP MIB, I've reviewed the "sampling and filtering techniques for IP packet selection" draft... this time with a PSAMP MIB hat. I still have a few comments on the draft. 1. section 2 "PSAMP Documents Overview" [PSAMP-MIB] "Definitions of Managed Objects for Packet Sampling" describes the PSAMP management Information Base. I see that the current MIB description use the same definition. However, the MIB specifications go well beyond sampling... there is also filtering and hashing! What about "definitions of managed objects for sampling and filtering techniques for IP packet selection"? Note - the draft "A Framework for Packet Selection and Reporting" should be changed accordingly - the MIB definition should be changed accordingly 2. "Packet Content" definition [IPFIX-REQUIRE] -> [IPFIX-REQ] 3. If I recall correctly, the following terms have been changed in the latest "A Framework for Packet Selection and Reporting" (at least I recall some discussions on the mailing list): population size, sample size, configured selection fraction, attained selection fraction 4. Table in section 4 Change "Filter" to "Filtering" in the category column Same section, change "cascade of a filter and a Sampling scheme" to "cascade of Filtering and Sampling schemes" 5. Section 5.2.2.3 Still non-ascii characters with "sample and hold" and "local export" 6. Section 6.2.1.1 "In the former case determines pseudorandom variates rather than selection probabilities" ?? 7. Section 6.3 "Router State Filtering" Remove the OR. 8. Section 7 "In order to be compliant with PSAMP, it is sufficient to implement one of the proposed schemes". As far as I recall, this will be a standard track document, so it should be written in a more formal way. "In order to be compliant with PSAMP, one least of the proposed scheme MUST be implemented" 9. section 7.1 SELECTOR_ID: ... the ID can be calculated under consideration of the ASSOCIATIONS and a local ID. What does the "under consideration" mean? 10. section 7.1 case non-uniform probabilistic and case flow state both refer to section 5.2.2.4. However, both the method descriptions and the 5.2.2.4 section don't clearly explain which SELECTOR_PARAMETERS we need 11. section 7.1 "The ASSOCIATIONS field describes the Observation Point and (possibly) the IPFIX processes" Possibly -> optionally without parentheses. Note: the MIB should take care that these parameters are optional. Proposal: a value of 0 means unspecified? 12. section 7.1 Case Matching -> this is not too clear that these are pairs of (field, value). And that in case of multiple match criteria, we have several "case matching" bound by a logical AND. BTW, IPFIX speaks of information element and not field, so I guess it should be a (information element, value) pair. 13. section 7.1 case hashing -> this is not too clear how the parameters in there match the definitions of hash domain, hash range, hash selection range, hash-based selection, etc... BTW I have the same problem with the MIB definitions (which obviously match these definitions) 14. section 7.1 "all router state entries can be linked by AND, OR, NOT operators" ->to be limited by AND 15. there are still a lot of capitalized terms before definition. The list is too long is to described in an email. Either use the find function, either call me as I marked them down on the paper draft I reviewed. Regards, Benoit. -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Mon Feb 14 12:39:44 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA25592 for ; Mon, 14 Feb 2005 12:39:44 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D0k2N-0007Uu-I9 for psamp-data@psg.com; Mon, 14 Feb 2005 17:29:31 +0000 Received: from [144.254.15.119] (helo=strange-brew.cisco.com) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D0k2M-0007Tw-9q for psamp@ops.ietf.org; Mon, 14 Feb 2005 17:29:30 +0000 Received: from [10.59.24.6] ([10.59.24.6]) by strange-brew.cisco.com (8.11.7p1+Sun/8.8.8) with ESMTP id j1EHTR108525; Mon, 14 Feb 2005 18:29:28 +0100 (CET) Message-ID: <4210DAE9.4010304@cisco.com> Date: Mon, 14 Feb 2005 18:07:53 +0100 From: Benoit Claise User-Agent: Mozilla Thunderbird 1.0 (Windows/20041206) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Juergen Quittek CC: psamp@ops.ietf.org Subject: Re: Hashing function for PSAMP References: <1F29E699573152EF47921D9C@[10.1.1.171]> In-Reply-To: <1F29E699573152EF47921D9C@[10.1.1.171]> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Dear all, Regarding PSAMP compliance, I was under the impression that the agreement was (even If I could not find a trace of it, after looking approx. 30 sec ;)): If you want to be PSAMP compliant, you MUST implement at least one of the "method" described in the draft. So I concluded that one filtering or one sampling mechanism would be sufficient. Now, the discussion below is about a compulsory hash function. Can we please clarify the situation regarding PSAMP compliance, so where is/are the MUST(s): - MUST implement one of the filtering or sampling mechanism (note: hashing is a filtering function)? - Or MUST implement one of the filtering and one of the sampling mechanism (note: hashing is a filtering function)? - Or MUST implement one of the filtering, sampling, or hashing mechanism? - Or MUST implement one of the filtering, sampling, and hashing mechanism? - Or something else? From there, we will deduce if we even need a compulsory hash function... Regards, Benoit. > Dear all, > > Currently, the packet selection document has IPSX mandatory for packet > selection and CRC32 mandatory for packet digest. > > The problem I see with this recommendation is that IPSX is not suitable > for IPv6. It does not sound like a good idea to have it mandatory for > IPv6 systems. > > Here are two alternatives: > > 1. Make IPSX mandatory for IPv4 packet selection and BOB mandatory > for IPv6 packet selection. > Then, with BOB implemented anyway, we should then replace CRC32 > with BOB for packet digest, because both perform similarly and > there is no good reason for forcing implementors to support also > a third hash function. > > 2. Just make BOB mandatory for packet selection and packet digest. > This would simplify implementation, because only a single function > is required. For packet digest this should be OK, see 1. > A disadvantage is that BOB is slower than IPSX by factor 7. > An advantage is, that BOB is free of IPR, while IPSX is protected > by a patent. > > Does anybody have a preferences for 1., 2., or the current choice? > > Thanks, > > Juergen -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Wed Feb 16 03:57:16 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id DAA13871 for ; Wed, 16 Feb 2005 03:57:16 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D1Kj5-0009FQ-P9 for psamp-data@psg.com; Wed, 16 Feb 2005 08:40:03 +0000 Received: from [193.174.154.14] (helo=mailhub.fokus.fraunhofer.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D1Kj2-0009Ci-21 for psamp@ops.ietf.org; Wed, 16 Feb 2005 08:40:00 +0000 Received: from [195.37.78.204] (dhcp204 [195.37.78.204]) by mailhub.fokus.fraunhofer.de (8.11.6p2/8.11.6) with ESMTP id j1G8drA02555; Wed, 16 Feb 2005 09:39:53 +0100 (MET) Message-ID: <421306D7.7090102@fokus.fraunhofer.de> Date: Wed, 16 Feb 2005 09:39:51 +0100 From: Tanja Zseby User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Benoit Claise CC: Juergen Quittek , psamp@ops.ietf.org Subject: Re: Hashing function for PSAMP References: <1F29E699573152EF47921D9C@[10.1.1.171]> <4210DAE9.4010304@cisco.com> In-Reply-To: <4210DAE9.4010304@cisco.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Hi Benoit, I remember that we decided that you MUST implement at least one of the selection method described in the draft in order to be PSAMP compliant. So I agree, it is sufficient to implement either a sampling or a filtering method. We explicitely decided not to favor one scheme over another. The hash-section just gives recommendations for the case that someone decided to implement a hash-based scheme. I see no reason to change this decision. Regards Tanja P.S.: if you have time, can you call me and give me the list of typos that you have on your paper version ? Or we make a short editing session at the IETF ? Benoit Claise wrote: > Dear all, > > Regarding PSAMP compliance, I was under the impression that the > agreement was (even If I could not find a trace of it, after looking > approx. 30 sec ;)): > If you want to be PSAMP compliant, you MUST implement at least one of > the "method" described in the draft. > So I concluded that one filtering or one sampling mechanism would be > sufficient. > > Now, the discussion below is about a compulsory hash function. > > Can we please clarify the situation regarding PSAMP compliance, so > where is/are the MUST(s): > - MUST implement one of the filtering or sampling mechanism (note: > hashing is a filtering function)? > - Or MUST implement one of the filtering and one of the sampling > mechanism (note: hashing is a filtering function)? > - Or MUST implement one of the filtering, sampling, or hashing mechanism? > - Or MUST implement one of the filtering, sampling, and hashing > mechanism? > - Or something else? > > From there, we will deduce if we even need a compulsory hash function... > > Regards, Benoit. > >> Dear all, >> >> Currently, the packet selection document has IPSX mandatory for packet >> selection and CRC32 mandatory for packet digest. >> >> The problem I see with this recommendation is that IPSX is not suitable >> for IPv6. It does not sound like a good idea to have it mandatory for >> IPv6 systems. >> >> Here are two alternatives: >> >> 1. Make IPSX mandatory for IPv4 packet selection and BOB mandatory >> for IPv6 packet selection. >> Then, with BOB implemented anyway, we should then replace CRC32 >> with BOB for packet digest, because both perform similarly and >> there is no good reason for forcing implementors to support also >> a third hash function. >> >> 2. Just make BOB mandatory for packet selection and packet digest. >> This would simplify implementation, because only a single function >> is required. For packet digest this should be OK, see 1. >> A disadvantage is that BOB is slower than IPSX by factor 7. >> An advantage is, that BOB is free of IPR, while IPSX is protected >> by a patent. >> >> Does anybody have a preferences for 1., 2., or the current choice? >> >> Thanks, >> >> Juergen > > > > > > -- > to unsubscribe send a message to psamp-request@ops.ietf.org with > the word 'unsubscribe' in a single line as the message text body. > archive: -- Dipl.-Ing. Tanja Zseby Fraunhofer Institute FOKUS Email: zseby@fokus.fraunhofer.de Kaiserin-Augusta-Allee 31 Phone: +49-30-3463-7153 D-10589 Berlin, Germany Fax: +49-30-3463-8153 -------------------------------------------------------------------------------------- "Living on earth is expensive but it includes a free trip around the sun." (Anonymous) -------------------------------------------------------------------------------------- -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Wed Feb 16 04:40:05 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id EAA18155 for ; Wed, 16 Feb 2005 04:40:04 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D1LZh-0008kj-Dy for psamp-data@psg.com; Wed, 16 Feb 2005 09:34:25 +0000 Received: from [144.254.15.119] (helo=strange-brew.cisco.com) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D1LZg-0008kQ-6L for psamp@ops.ietf.org; Wed, 16 Feb 2005 09:34:24 +0000 Received: from [10.59.24.3] ([10.59.24.3]) by strange-brew.cisco.com (8.11.7p1+Sun/8.8.8) with ESMTP id j1G9YE107040; Wed, 16 Feb 2005 10:34:14 +0100 (CET) Message-ID: <42131391.3030506@cisco.com> Date: Wed, 16 Feb 2005 10:34:09 +0100 From: Benoit Claise User-Agent: Mozilla Thunderbird 1.0 (Windows/20041206) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Tanja Zseby CC: Juergen Quittek , psamp@ops.ietf.org Subject: Re: Hashing function for PSAMP References: <1F29E699573152EF47921D9C@[10.1.1.171]> <4210DAE9.4010304@cisco.com> <421306D7.7090102@fokus.fraunhofer.de> In-Reply-To: <421306D7.7090102@fokus.fraunhofer.de> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Hi Tanja, Thanks for the clarification/confirmation. So I'm confused by the discussion in this thread, as it seems that we are discussing a mandatory hash function? Doesn't it contradict the statement "you MUST implement at least one of the selection method described in the draft in order to be PSAMP compliant."? Regards, Benoit. > Hi Benoit, > > I remember that we decided that you MUST implement at least one of the > selection method described in the draft in order to be PSAMP compliant. > So I agree, it is sufficient to implement either a sampling or a > filtering method. We explicitely decided not to favor one scheme over > another. The hash-section just gives recommendations for the case that > someone decided to implement a hash-based scheme. I see no reason to > change this decision. > > Regards > Tanja > P.S.: if you have time, can you call me and give me the list of typos > that you have on your paper version ? Or we make a short editing > session at the IETF ? > > Benoit Claise wrote: > >> Dear all, >> >> Regarding PSAMP compliance, I was under the impression that the >> agreement was (even If I could not find a trace of it, after looking >> approx. 30 sec ;)): >> If you want to be PSAMP compliant, you MUST implement at least one of >> the "method" described in the draft. >> So I concluded that one filtering or one sampling mechanism would be >> sufficient. >> >> Now, the discussion below is about a compulsory hash function. >> >> Can we please clarify the situation regarding PSAMP compliance, so >> where is/are the MUST(s): >> - MUST implement one of the filtering or sampling mechanism (note: >> hashing is a filtering function)? >> - Or MUST implement one of the filtering and one of the sampling >> mechanism (note: hashing is a filtering function)? >> - Or MUST implement one of the filtering, sampling, or hashing >> mechanism? >> - Or MUST implement one of the filtering, sampling, and hashing >> mechanism? >> - Or something else? >> >> From there, we will deduce if we even need a compulsory hash function... >> >> Regards, Benoit. >> >>> Dear all, >>> >>> Currently, the packet selection document has IPSX mandatory for packet >>> selection and CRC32 mandatory for packet digest. >>> >>> The problem I see with this recommendation is that IPSX is not suitable >>> for IPv6. It does not sound like a good idea to have it mandatory for >>> IPv6 systems. >>> >>> Here are two alternatives: >>> >>> 1. Make IPSX mandatory for IPv4 packet selection and BOB mandatory >>> for IPv6 packet selection. >>> Then, with BOB implemented anyway, we should then replace CRC32 >>> with BOB for packet digest, because both perform similarly and >>> there is no good reason for forcing implementors to support also >>> a third hash function. >>> >>> 2. Just make BOB mandatory for packet selection and packet digest. >>> This would simplify implementation, because only a single function >>> is required. For packet digest this should be OK, see 1. >>> A disadvantage is that BOB is slower than IPSX by factor 7. >>> An advantage is, that BOB is free of IPR, while IPSX is protected >>> by a patent. >>> >>> Does anybody have a preferences for 1., 2., or the current choice? >>> >>> Thanks, >>> >>> Juergen >> >> >> >> >> >> >> -- >> to unsubscribe send a message to psamp-request@ops.ietf.org with >> the word 'unsubscribe' in a single line as the message text body. >> archive: > > > -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Wed Feb 16 04:46:28 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id EAA18648 for ; Wed, 16 Feb 2005 04:46:27 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D1LgT-0009tj-AU for psamp-data@psg.com; Wed, 16 Feb 2005 09:41:25 +0000 Received: from [193.174.154.14] (helo=mailhub.fokus.fraunhofer.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D1LgO-0009t9-Jd for psamp@ops.ietf.org; Wed, 16 Feb 2005 09:41:20 +0000 Received: from [195.37.78.204] (dhcp204 [195.37.78.204]) by mailhub.fokus.fraunhofer.de (8.11.6p2/8.11.6) with ESMTP id j1G9fHA12459; Wed, 16 Feb 2005 10:41:17 +0100 (MET) Message-ID: <4213153B.1050100@fokus.fraunhofer.de> Date: Wed, 16 Feb 2005 10:41:15 +0100 From: Tanja Zseby User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Benoit Claise CC: Juergen Quittek , psamp@ops.ietf.org Subject: Re: Hashing function for PSAMP References: <1F29E699573152EF47921D9C@[10.1.1.171]> <4210DAE9.4010304@cisco.com> <421306D7.7090102@fokus.fraunhofer.de> <42131391.3030506@cisco.com> In-Reply-To: <42131391.3030506@cisco.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Hi Benoit, I fully agree. The discussion can be only about what we recommend IF someone decides to implement a hash-based packet selection. Regards Tanja Benoit Claise wrote: > Hi Tanja, > > Thanks for the clarification/confirmation. > So I'm confused by the discussion in this thread, as it seems that we > are discussing a mandatory hash function? Doesn't it contradict the > statement "you MUST implement at least one of the selection method > described in the draft in order to be PSAMP compliant."? > > Regards, Benoit. > >> Hi Benoit, >> >> I remember that we decided that you MUST implement at least one of >> the selection method described in the draft in order to be PSAMP >> compliant. >> So I agree, it is sufficient to implement either a sampling or a >> filtering method. We explicitely decided not to favor one scheme over >> another. The hash-section just gives recommendations for the case >> that someone decided to implement a hash-based scheme. I see no >> reason to change this decision. >> >> Regards >> Tanja >> P.S.: if you have time, can you call me and give me the list of typos >> that you have on your paper version ? Or we make a short editing >> session at the IETF ? >> >> Benoit Claise wrote: >> >>> Dear all, >>> >>> Regarding PSAMP compliance, I was under the impression that the >>> agreement was (even If I could not find a trace of it, after looking >>> approx. 30 sec ;)): >>> If you want to be PSAMP compliant, you MUST implement at least one >>> of the "method" described in the draft. >>> So I concluded that one filtering or one sampling mechanism would be >>> sufficient. >>> >>> Now, the discussion below is about a compulsory hash function. >>> >>> Can we please clarify the situation regarding PSAMP compliance, so >>> where is/are the MUST(s): >>> - MUST implement one of the filtering or sampling mechanism (note: >>> hashing is a filtering function)? >>> - Or MUST implement one of the filtering and one of the sampling >>> mechanism (note: hashing is a filtering function)? >>> - Or MUST implement one of the filtering, sampling, or hashing >>> mechanism? >>> - Or MUST implement one of the filtering, sampling, and hashing >>> mechanism? >>> - Or something else? >>> >>> From there, we will deduce if we even need a compulsory hash >>> function... >>> >>> Regards, Benoit. >>> >>>> Dear all, >>>> >>>> Currently, the packet selection document has IPSX mandatory for packet >>>> selection and CRC32 mandatory for packet digest. >>>> >>>> The problem I see with this recommendation is that IPSX is not >>>> suitable >>>> for IPv6. It does not sound like a good idea to have it mandatory for >>>> IPv6 systems. >>>> >>>> Here are two alternatives: >>>> >>>> 1. Make IPSX mandatory for IPv4 packet selection and BOB mandatory >>>> for IPv6 packet selection. >>>> Then, with BOB implemented anyway, we should then replace CRC32 >>>> with BOB for packet digest, because both perform similarly and >>>> there is no good reason for forcing implementors to support also >>>> a third hash function. >>>> >>>> 2. Just make BOB mandatory for packet selection and packet digest. >>>> This would simplify implementation, because only a single function >>>> is required. For packet digest this should be OK, see 1. >>>> A disadvantage is that BOB is slower than IPSX by factor 7. >>>> An advantage is, that BOB is free of IPR, while IPSX is protected >>>> by a patent. >>>> >>>> Does anybody have a preferences for 1., 2., or the current choice? >>>> >>>> Thanks, >>>> >>>> Juergen >>> >>> >>> >>> >>> >>> >>> >>> -- >>> to unsubscribe send a message to psamp-request@ops.ietf.org with >>> the word 'unsubscribe' in a single line as the message text body. >>> archive: >> >> >> >> > > > -- > to unsubscribe send a message to psamp-request@ops.ietf.org with > the word 'unsubscribe' in a single line as the message text body. > archive: -- Dipl.-Ing. Tanja Zseby Fraunhofer Institute FOKUS Email: zseby@fokus.fraunhofer.de Kaiserin-Augusta-Allee 31 Phone: +49-30-3463-7153 D-10589 Berlin, Germany Fax: +49-30-3463-8153 -------------------------------------------------------------------------------------- "Living on earth is expensive but it includes a free trip around the sun." (Anonymous) -------------------------------------------------------------------------------------- -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Wed Feb 16 12:42:28 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA03325 for ; Wed, 16 Feb 2005 12:42:27 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D1T2i-000Ahw-O6 for psamp-data@psg.com; Wed, 16 Feb 2005 17:32:52 +0000 Received: from [193.174.154.14] (helo=mailhub.fokus.fraunhofer.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D1T2f-000AbB-WB for psamp@ops.ietf.org; Wed, 16 Feb 2005 17:32:50 +0000 Received: from [195.37.78.204] (dhcp204 [195.37.78.204]) by mailhub.fokus.fraunhofer.de (8.11.6p2/8.11.6) with ESMTP id j1GHWlA08499; Wed, 16 Feb 2005 18:32:47 +0100 (MET) Message-ID: <421383BD.3080006@fokus.fraunhofer.de> Date: Wed, 16 Feb 2005 18:32:45 +0100 From: Tanja Zseby User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Benoit Claise CC: psamp Subject: Re: some more comments on draft-ietf-psamp-sample-tech-05.txt References: <420FB874.7000702@cisco.com> In-Reply-To: <420FB874.7000702@cisco.com> Content-Type: multipart/alternative; boundary="------------000907080100070503080606" X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00,HTML_30_40, HTML_MESSAGE,HTML_TITLE_EMPTY autolearn=no version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk This is a multi-part message in MIME format. --------------000907080100070503080606 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Hi Benoit, see comments inline Benoit Claise wrote: > Dear all, > > In order to produce the next version of the PSAMP MIB, I've reviewed > the "sampling and filtering techniques for IP packet selection" > draft... this time with a PSAMP MIB hat. I still have a few comments > on the draft. > > 1. section 2 "PSAMP Documents Overview" > [PSAMP-MIB] "Definitions of Managed Objects for Packet Sampling" > describes the PSAMP management Information Base. > I see that the current MIB description use the same definition. > However, the MIB specifications go well beyond sampling... there is > also filtering and hashing! > What about "definitions of managed objects for sampling and filtering > techniques for IP packet selection"? > Note > - the draft "A Framework for Packet Selection and Reporting" should > be changed accordingly > - the MIB definition should be changed accordingly > According to out definition sampling and filtering are both packet selection techniques So in my opiniton the MIB title should change to "Definitions of Managed Objects for Packet Selection", the FW document title can remain. > 2. "Packet Content" definition > [IPFIX-REQUIRE] -> [IPFIX-REQ] > done (changed for new version) > 3. If I recall correctly, the following terms have been changed in the > latest "A Framework for Packet Selection and Reporting" (at least I > recall some discussions on the mailing list): population size, sample > size, configured selection fraction, attained selection fraction Nick and I had a teleconferecne some time ago and agreed on those terms. So they are consistent in both drafts. > 4. Table in section 4 > Change "Filter" to "Filtering" in the category column > Same section, change "cascade of a filter and a Sampling scheme" to > "cascade of Filtering and Sampling schemes" > done > 5. Section 5.2.2.3 > Still non-ascii characters with "sample and hold" and "local export" done > 6. Section 6.2.1.1 > "In the former case determines pseudorandom variates rather than > selection probabilities" ?? > changed > 7. Section 6.3 "Router State Filtering" > Remove the OR. > done (now only AND is possible) Since it seems no problem for the MIB or implementation to also have a NOT we could also allow a NOT for the matching filter combination Thomas, Benoit do you agree ? > 8. Section 7 > "In order to be compliant with PSAMP, it is sufficient to implement > one of the proposed schemes". > As far as I recall, this will be a standard track document, so it > should be written in a more formal way. > "In order to be compliant with PSAMP, one least of the proposed scheme > MUST be implemented" done > 9. section 7.1 > SELECTOR_ID: ... the ID can be calculated under consideration of the > ASSOCIATIONS and a local ID. > What does the "under consideration" mean? To get a unique ID both need to be conisdered (local ID and associations ) ==> changed the text to "calculated as combination of..." > 10. section 7.1 > case non-uniform probabilistic and case flow state both refer to > section 5.2.2.4. > However, both the method descriptions and the 5.2.2.4 section don't > clearly explain which SELECTOR_PARAMETERS we need Yes, because we decided that those techniques are not mature enough nowadays to define generic parameters for the scheme and this is stated in 5.2.2.4 > 11. section 7.1 > "The ASSOCIATIONS field describes the Observation Point and (possibly) > the IPFIX processes" > Possibly -> optionally without parentheses. > Note: the MIB should take care that these parameters are optional. > Proposal: a value of 0 means unspecified? changed. 0 (unspecified) than means it should apply to all IPFIX processes at this observation point ? > 12. section 7.1 > Case Matching -> this is not too clear that these are pairs of (field, > value). And that in case of multiple match criteria, we have several > "case matching" bound by a logical AND. > BTW, IPFIX speaks of information element and not field, so I guess it > should be a (information element, value) pair. changed and sentence added > 13. section 7.1 > case hashing -> this is not too clear how the parameters in there > match the definitions of hash domain, hash range, hash selection > range, hash-based selection, etc... BTW I have the same problem with > the MIB definitions (which obviously match these definitions) > done > 14. section 7.1 > "all router state entries can be linked by AND, OR, NOT operators" > ->to be limited by AND > done. Maybe possible to allow NOT operators ? > 15. there are still a lot of capitalized terms before definition. The > list is too long is to described in an email. > Either use the find function, either call me as I marked them down on > the paper draft I reviewed. > TODO Regards Tanja > Regards, Benoit. > > > -- > to unsubscribe send a message to psamp-request@ops.ietf.org with > the word 'unsubscribe' in a single line as the message text body. > archive: -- Dipl.-Ing. Tanja Zseby Fraunhofer Institute FOKUS Email: zseby@fokus.fraunhofer.de Kaiserin-Augusta-Allee 31 Phone: +49-30-3463-7153 D-10589 Berlin, Germany Fax: +49-30-3463-8153 -------------------------------------------------------------------------------------- "Living on earth is expensive but it includes a free trip around the sun." (Anonymous) -------------------------------------------------------------------------------------- --------------000907080100070503080606 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Hi Benoit,

see comments inline

Benoit Claise wrote:
Dear all,

In order to produce the next version of the PSAMP MIB, I've reviewed the "sampling and filtering techniques for IP packet selection" draft... this time with a PSAMP MIB hat. I still have a few comments on the draft.

1. section 2 "PSAMP Documents Overview"
 [PSAMP-MIB]  "Definitions of Managed Objects for Packet Sampling" describes the PSAMP management Information Base.
I see that the current MIB description use the same definition. However, the MIB specifications go well beyond sampling... there is also filtering and hashing!
What about "definitions of managed objects for sampling and filtering techniques for IP packet selection"?
Note
   - the draft "A Framework for Packet Selection and Reporting" should be changed accordingly
   - the MIB definition should be changed accordingly

According to out definition sampling and filtering are both packet selection techniques So in my opiniton the MIB title should change to "Definitions of Managed Objects for Packet Selection",  the FW document title can remain.

2. "Packet Content" definition
[IPFIX-REQUIRE] -> [IPFIX-REQ]

done (changed for new version)
3. If I recall correctly, the following terms have been changed in the latest "A Framework for Packet Selection and Reporting" (at least I recall some discussions on the mailing list): population size, sample size, configured selection fraction, attained selection fraction
Nick and I had a teleconferecne some time ago and agreed on those terms. So they are consistent in both drafts.

4. Table in section 4
Change "Filter" to "Filtering" in the category column
Same section, change "cascade of a filter and a Sampling scheme" to "cascade of Filtering and Sampling schemes"

done
5. Section 5.2.2.3
Still non-ascii characters with "sample and hold" and "local export"
done
6. Section 6.2.1.1
"In the former case determines pseudorandom variates rather than selection probabilities" ??

changed
7. Section 6.3 "Router State Filtering"
Remove the OR.

done (now only AND is possible)
Since it seems no problem for the MIB or implementation to also have a NOT we could also allow a NOT for the matching filter combination
Thomas, Benoit do you agree ?

8. Section 7
"In order to be compliant with PSAMP, it is sufficient to implement one of the proposed schemes".
As far as I recall, this will be a standard track document, so it should be written in a more formal way.
"In order to be compliant with PSAMP, one least of the proposed scheme MUST be implemented"
done
9. section 7.1
SELECTOR_ID: ... the ID can be calculated under consideration of the ASSOCIATIONS and a local ID.
What does the "under consideration" mean?
To get a unique ID both need to be conisdered (local ID and associations ) ==> changed the text to "calculated as combination of..."

10. section 7.1
case non-uniform probabilistic and case flow state both refer to section 5.2.2.4.
However, both the method descriptions and the 5.2.2.4 section don't clearly explain which SELECTOR_PARAMETERS we need
Yes, because we decided that those techniques are not mature enough nowadays to define generic parameters for the scheme and this is stated in 5.2.2.4

11. section 7.1
"The ASSOCIATIONS field describes the Observation Point and (possibly) the IPFIX processes"
Possibly -> optionally without parentheses.
Note: the MIB should take care that these parameters are optional. Proposal: a value of 0 means unspecified?
changed. 0 (unspecified) than means it should apply to all IPFIX processes at this observation point ?

12. section 7.1
Case Matching -> this is not too clear that these are pairs of (field, value). And that in case of multiple match criteria, we have several "case matching" bound by a logical AND.
BTW, IPFIX speaks of information element and not field, so I guess it should be a (information element, value) pair.
changed and sentence added
13. section 7.1
case hashing -> this is not too clear how the parameters in there match the definitions of hash domain, hash range, hash selection range, hash-based selection, etc... BTW I have the same problem with the MIB definitions (which obviously match these definitions)

done
14. section 7.1
"all router state entries can be linked by AND, OR, NOT operators" ->to be limited by AND

done. Maybe possible to allow NOT operators ?
15. there are still a lot of capitalized terms before definition. The list is too long is to described in an email.
 Either use the find function, either call me as I marked them down on the paper draft I reviewed.

TODO

Regards
Tanja
Regards, Benoit.


--
to unsubscribe send a message to psamp-request@ops.ietf.org with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/psamp/> 

-- 
Dipl.-Ing. Tanja Zseby			    	      	
Fraunhofer Institute FOKUS			Email: zseby@fokus.fraunhofer.de	
Kaiserin-Augusta-Allee 31			Phone: +49-30-3463-7153
D-10589 Berlin, Germany				Fax:   +49-30-3463-8153
-------------------------------------------------------------------------------------- 
"Living on earth is expensive but it includes a free trip around the sun." (Anonymous)
--------------------------------------------------------------------------------------
--------------000907080100070503080606-- -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Thu Feb 17 04:12:57 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id EAA27156 for ; Thu, 17 Feb 2005 04:12:56 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D1hYl-0007Ce-Pl for psamp-data@psg.com; Thu, 17 Feb 2005 09:02:55 +0000 Received: from [195.37.70.40] (helo=smtp2.netlab.nec.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D1hYh-000788-0y for psamp@ops.ietf.org; Thu, 17 Feb 2005 09:02:51 +0000 Received: from europa.office (europa.office [10.1.1.2]) by smtp2.netlab.nec.de (Postfix) with ESMTP id B5DD5DC6A for ; Thu, 17 Feb 2005 10:08:58 +0100 (CET) Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: quoted-printable X-MimeOLE: Produced By Microsoft Exchange V6.5.7226.0 Subject: RE: Hashing function for PSAMP Date: Thu, 17 Feb 2005 10:02:49 +0100 Message-ID: Thread-Topic: Hashing function for PSAMP Thread-Index: AcUUDEpW812tiX8RQPyY6UwKxlsukAAwhReA From: "Saverio Niccolini" To: X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: quoted-printable Dear all, now that the meaning of "selection" is clarified I think there is still the need of recommending one of the hash functions, therefore I think the discussion we had still applies (just keep in mind that instead of "mandatory" we have a "recommended"): just make BOB recommended for packet selection and packet digest. Best regards, Saverio > -----Original Message----- > From: owner-psamp@ops.ietf.org=20 > [mailto:owner-psamp@ops.ietf.org] On Behalf Of Tanja Zseby > Sent: Wednesday, February 16, 2005 10:41 AM > To: Benoit Claise > Cc: Juergen Quittek; psamp@ops.ietf.org > Subject: Re: Hashing function for PSAMP >=20 > Hi Benoit, >=20 > I fully agree. The discussion can be only about what we=20 > recommend IF someone decides to implement a hash-based packet=20 > selection. >=20 > Regards > Tanja >=20 > Benoit Claise wrote: >=20 > > Hi Tanja, > > > > Thanks for the clarification/confirmation. > > So I'm confused by the discussion in this thread, as it=20 > seems that we=20 > > are discussing a mandatory hash function? Doesn't it contradict the=20 > > statement "you MUST implement at least one of the selection method=20 > > described in the draft in order to be PSAMP compliant."? > > > > Regards, Benoit. > > > >> Hi Benoit, > >> > >> I remember that we decided that you MUST implement at least one of=20 > >> the selection method described in the draft in order to be PSAMP=20 > >> compliant. > >> So I agree, it is sufficient to implement either a sampling or a=20 > >> filtering method. We explicitely decided not to favor one=20 > scheme over=20 > >> another. The hash-section just gives recommendations for the case=20 > >> that someone decided to implement a hash-based scheme. I see no=20 > >> reason to change this decision. > >> > >> Regards > >> Tanja > >> P.S.: if you have time, can you call me and give me the=20 > list of typos=20 > >> that you have on your paper version ? Or we make a short editing=20 > >> session at the IETF ? > >> > >> Benoit Claise wrote: > >> > >>> Dear all, > >>> > >>> Regarding PSAMP compliance, I was under the impression that the=20 > >>> agreement was (even If I could not find a trace of it,=20 > after looking=20 > >>> approx. 30 sec ;)): > >>> If you want to be PSAMP compliant, you MUST implement at=20 > least one=20 > >>> of the "method" described in the draft. > >>> So I concluded that one filtering or one sampling=20 > mechanism would be=20 > >>> sufficient. > >>> > >>> Now, the discussion below is about a compulsory hash function. > >>> > >>> Can we please clarify the situation regarding PSAMP=20 > compliance, so=20 > >>> where is/are the MUST(s): > >>> - MUST implement one of the filtering or sampling=20 > mechanism (note:=20 > >>> hashing is a filtering function)? > >>> - Or MUST implement one of the filtering and one of the sampling=20 > >>> mechanism (note: hashing is a filtering function)? > >>> - Or MUST implement one of the filtering, sampling, or hashing=20 > >>> mechanism? > >>> - Or MUST implement one of the filtering, sampling, and hashing=20 > >>> mechanism? > >>> - Or something else? > >>> > >>> From there, we will deduce if we even need a compulsory hash=20 > >>> function... > >>> > >>> Regards, Benoit. > >>> > >>>> Dear all, > >>>> > >>>> Currently, the packet selection document has IPSX mandatory for=20 > >>>> packet selection and CRC32 mandatory for packet digest. > >>>> > >>>> The problem I see with this recommendation is that IPSX is not=20 > >>>> suitable for IPv6. It does not sound like a good idea=20 > to have it=20 > >>>> mandatory for > >>>> IPv6 systems. > >>>> > >>>> Here are two alternatives: > >>>> > >>>> 1. Make IPSX mandatory for IPv4 packet selection and BOB=20 > mandatory > >>>> for IPv6 packet selection. > >>>> Then, with BOB implemented anyway, we should then replace CRC32 > >>>> with BOB for packet digest, because both perform similarly and > >>>> there is no good reason for forcing implementors to=20 > support also > >>>> a third hash function. > >>>> > >>>> 2. Just make BOB mandatory for packet selection and=20 > packet digest. > >>>> This would simplify implementation, because only a=20 > single function > >>>> is required. For packet digest this should be OK, see 1. > >>>> A disadvantage is that BOB is slower than IPSX by factor 7. > >>>> An advantage is, that BOB is free of IPR, while IPSX=20 > is protected > >>>> by a patent. > >>>> > >>>> Does anybody have a preferences for 1., 2., or the=20 > current choice? > >>>> > >>>> Thanks, > >>>> > >>>> Juergen > >>> > >>> > >>> > >>> > >>> > >>> > >>> > >>> -- > >>> to unsubscribe send a message to=20 > psamp-request@ops.ietf.org with the=20 > >>> word 'unsubscribe' in a single line as the message text body. > >>> archive: > >> > >> > >> > >> > > > > > > -- > > to unsubscribe send a message to psamp-request@ops.ietf.org=20 > with the=20 > > word 'unsubscribe' in a single line as the message text body. > > archive: >=20 >=20 > --=20 > Dipl.-Ing. Tanja Zseby =09 > Fraunhofer Institute FOKUS Email:=20 > zseby@fokus.fraunhofer.de=09 > Kaiserin-Augusta-Allee 31 Phone: +49-30-3463-7153 > D-10589 Berlin, Germany Fax: =20 > +49-30-3463-8153 > -------------------------------------------------------------- > ------------------------ > "Living on earth is expensive but it includes a free trip=20 > around the sun." (Anonymous) > -------------------------------------------------------------- > ------------------------ >=20 >=20 > -- > to unsubscribe send a message to psamp-request@ops.ietf.org with > the word 'unsubscribe' in a single line as the message text body. > archive: >=20 -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Thu Feb 17 13:47:17 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA18784 for ; Thu, 17 Feb 2005 13:47:15 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D1qUB-000Owj-45 for psamp-data@psg.com; Thu, 17 Feb 2005 18:34:47 +0000 Received: from [193.174.154.14] (helo=mailhub.fokus.fraunhofer.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D1qU4-000OwF-6n for psamp@ops.ietf.org; Thu, 17 Feb 2005 18:34:41 +0000 Received: from [195.37.78.204] (dhcp204 [195.37.78.204]) by mailhub.fokus.fraunhofer.de (8.11.6p2/8.11.6) with ESMTP id j1HIYc522633 for ; Thu, 17 Feb 2005 19:34:39 +0100 (MET) Message-ID: <4214E3BC.3020100@fokus.fraunhofer.de> Date: Thu, 17 Feb 2005 19:34:36 +0100 From: Tanja Zseby User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: psamp Subject: new packet selection draft version Content-Type: multipart/mixed; boundary="------------040603020700040807080401" X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-1.3 required=5.0 tests=AWL,BAYES_50,HTML_40_50, HTML_MESSAGE,HTML_TITLE_EMPTY autolearn=no version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk This is a multi-part message in MIME format. --------------040603020700040807080401 Content-Type: multipart/alternative; boundary="------------090002080204080507080107" --------------090002080204080507080107 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Hi all, I just submited a new version of the packet selection draft (attached). There were only minor changes in the document, but a few open issues came up on the mailling list. Many thanks especially to Stewart, Benoit and Thomas for their comments. Changes: - Associations: if no IPFIX process specified, packet selector applies to all processes on observation point - Use of correct hash terminology in section 7.2. ( e.g. Use of Hash Selection Range instead of Selection Interval Specification) - Only AND for router state filters (as for the others) - Address changes (3 of the 5 authors changed affiliation...) - Some clarifications that came up from MIB definition - Some re-wording <> Some proposed changes not addressed: - simplicity of filter model was criticized but it was the intention to substitute the complex model by an extremely simple one which only allows AND (result of last IETF discussion) - terminology remains in both documents - nothing changed regarding recommended hash function because of still ongoing discussion Open Issues: - Which hash-function should be recommended ==> discussion on psamp list - What to recommend for IPv6 (depends on hash discussion) - As it seems not difficult to implement: Should we allow NOT operation for filter concatenation (all filter types) ? - CRC performance not sufficient ? (see Stewarts mail) - Include a better reference for IPSX ? Todo - Change references to documents if titles of other documents change (as proposed by Benoit, e.g. MIB) - Some terminology re-wording proposed by Stewart that need to be consistent with FW draft - Benoit has corrected some typos on his paper version ==> I propose to have a small editing session with Nick and Benoit at the IETF Regards Tanja -- Dipl.-Ing. Tanja Zseby Fraunhofer Institute FOKUS Email: zseby@fokus.fraunhofer.de Kaiserin-Augusta-Allee 31 Phone: +49-30-3463-7153 D-10589 Berlin, Germany Fax: +49-30-3463-8153 -------------------------------------------------------------------------------------- "Living on earth is expensive but it includes a free trip around the sun." (Anonymous) -------------------------------------------------------------------------------------- --------------090002080204080507080107 Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Hi all,

I just submited a new version of the packet selection draft (attached). There were only minor changes in the document, but a few open issues came up on the mailling list. Many thanks especially to Stewart, Benoit and Thomas for their comments.

Changes:
- Associations: if no IPFIX process specified, packet selector applies to all processes on observation point
- Use of correct hash terminology in section 7.2. ( e.g. Use of Hash Selection Range instead of Selection Interval Specification)
- Only AND for router state filters (as for the others)
- Address changes (3 of the 5 authors changed affiliation…)
- Some clarifications that came up from MIB definition
- Some re-wording <>

Some proposed changes not addressed:
- simplicity of filter model was criticized but it was the intention to substitute the complex model by an extremely simple one which only allows AND (result of last IETF discussion)
- terminology remains in both documents
- nothing changed regarding recommended hash function because of still ongoing discussion

Open Issues:
- Which hash-function should be recommended ==> discussion on psamp list
- What to recommend for IPv6 (depends on hash discussion)
- As it seems not difficult to implement: Should we allow NOT operation for filter concatenation (all filter types) ?
- CRC performance not sufficient ? (see Stewarts mail)
- Include a better reference for IPSX ?

Todo
- Change references to documents if titles of other documents change (as proposed by Benoit, e.g. MIB)
- Some terminology re-wording proposed by Stewart that need to be consistent with FW draft
- Benoit has corrected some typos on his paper version
==> I propose to have a small editing session with Nick and Benoit at the IETF

Regards
Tanja






-- 
Dipl.-Ing. Tanja Zseby			    	      	
Fraunhofer Institute FOKUS			Email: zseby@fokus.fraunhofer.de	
Kaiserin-Augusta-Allee 31			Phone: +49-30-3463-7153
D-10589 Berlin, Germany				Fax:   +49-30-3463-8153
-------------------------------------------------------------------------------------- 
"Living on earth is expensive but it includes a free trip around the sun." (Anonymous)
--------------------------------------------------------------------------------------
--------------090002080204080507080107-- --------------040603020700040807080401 Content-Type: text/plain; name="draft-ietf-psamp-sample-tech-06.txt" Content-Transfer-Encoding: 8bit Content-Disposition: inline; filename="draft-ietf-psamp-sample-tech-06.txt" Content-Transfer-Encoding: 8bit Internet Draft Document: T. Zseby Expires: August 2005 Fraunhofer FOKUS M. Molina DANTE N. Duffield AT&T Labs – Research S. Niccolini NEC Europe Ltd. F. Raspall EPSC-UPC February 2005 Sampling and Filtering Techniques for IP Packet Selection Status of this Memo This document is an Internet-Draft and is subject to all provisions of section 3 of RFC 3667. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she become aware will be disclosed, in accordance with RFC 3668. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C) The Internet Society (2004). Zseby, Molina, Duffield, Niccolini, Raspall [Page 1] Internet Draft Techniques for IP Packet Selection February 2005 Abstract This document describes Sampling and Filtering techniques for IP packet selection. It provides a taxonomy and classification of schemes and defines what parameters are needed to describe the most common selection schemes. Furthermore it shows how techniques can be combined to build more elaborate packet Selectors. The document provides the basis for the definition of information models for configuring selection techniques in measurement processes and for reporting the technique in use to a Collector. Zseby, Molina, Duffield, Niccolini, Raspall [Page 2] Internet Draft Techniques for IP Packet Selection February 2005 Table of Contents 1. Introduction.................................................4 2. PSAMP Documents Overview.....................................4 3. Terminology..................................................5 3.1 Observation Points, Packet Streams and Packet Content.....5 3.2 Selection Process.........................................6 3.3 Reporting Process.........................................7 3.4 Measurement Process.......................................8 3.5 Exporting Process.........................................8 3.6 PSAMP Device..............................................8 3.7 Collector.................................................9 3.8 Selection Methods.........................................9 4. Categorization of Packet Selection Techniques...............11 5. Sampling....................................................13 5.1 Systematic Sampling......................................13 5.2 Random Sampling..........................................14 5.2.1 n-out-of-N Sampling......................................14 5.2.2 Probabilistic Sampling...................................15 5.2.2.1 Uniform Probabilistic Sampling...........................15 5.2.2.2 Non-Uniform Probabilistic Sampling.......................15 5.2.2.3 Non-Uniform Flow State Dependent Sampling................15 5.2.2.4 Configuration of non-uniform probabilistic and flow- state Sampling..........................................16 6. Filtering...................................................17 6.1 Field Match Filtering....................................17 6.2 Hash-based Filtering.....................................17 6.2.1 Application Examples for Hash-based Selection............18 6.2.1.1 Approximation of Random Sampling.........................18 6.2.1.2 Trajectory Sampling and Consistent packet selection......19 6.2.2 Guarding Against Pitfalls and Vulnerabilities............20 6.2.3 Recommendations of Specific Hash Fuctions................20 6.2.3.1 Hash Functions Suitable for Packet Selection.............20 6.2.3.2 Hash Functions Suitable for Packet Digesting.............21 6.3 Router State Filtering...................................21 7. Parameters for the Description of Selection Techniques......22 7.1 Description of Sampling Techniques.......................22 7.2 Description of Filtering Techniques......................24 8. Composite Techniques........................................26 8.1 Cascaded Filtering->Sampling or Sampling->Filtering......27 8.2 Stratified Sampling......................................27 9. Security Considerations.....................................28 10. Acknowledgements............................................28 11. Normative References........................................28 12. Informative References......................................29 13. Author's Addresses..........................................31 14. Intellectual Property Statement.............................32 15. Copyright Statement.........................................32 Zseby, Molina, Duffield, Niccolini, Raspall [Page 3] Internet Draft Techniques for IP Packet Selection February 2005 16. Disclaimer..................................................33 17. Appendix: Hash Functions....................................33 17.1 IP Shift-XOR (IPSX) Hash Function........................33 17.2 "Bob" Hash Function......................................34 1. Introduction There are two main drivers for the growth in measurement infrastructures and their underlying technology. First, network data rates are increasing, with a concomitant growth in measurement data. Secondly, the growth is compounded by the demand by measurement-based applications for increasingly fine grained traffic measurements. Devices such as routers, which perform the measurements, require increasingly sophisticated and resource intensive measurement capabilities, including the capture of packet headers or even parts of the payload, and classification for flow analysis. All these factors can lead to an overwhelming amount of measurement data, resulting in high demands on resources for measurement, storage, transport and post processing. The sustained capture of network traffic at line rate can be performed by specialized measurement hardware. However, the cost of the hardware and the measurement infrastructure required to accommodate the measurements preclude this as a ubiquitous approach. Instead some form of data reduction at the point of measurement is necessary, and in current practice, this reduction is achieved at routers through packet Sampling, Filtering, or aggregation. The motivation for Sampling is to select a representative subset of packets that allow accurate estimates of properties of the unsampled traffic to be formed. The motivation for Filtering is to remove all packets that are not of interest. Aggregation allows compact pre-defined views of the traffic. Aggregation is out of scope of this document. Examples of applications that benefit from packet selection are given in [PSAMP-FW]. 2. PSAMP Documents Overview [PSAMP-FW]: "A Framework for Packet Selection and Reporting" describes the PSAMP framework for network elements to select subsets of packets by statistical and other methods, and to export a stream of reports on the selected packets to a Collector. [PSAMP-TECH]: "Sampling and Filtering Techniques for IP Packet Selection" (this document) describes the set of packet selection techniques supported by PSAMP. Zseby, Molina, Duffield, Niccolini, Raspall [Page 4] Internet Draft Techniques for IP Packet Selection February 2005 [PSAMP-MIB]: "Definitions of Managed Objects for Packet Sampling" describes the PSAMP Management Information Base. [PSAMP-PROTO]: "Packet Sampling (PSAMP) Protocol Specifications" specifies the export of packet information from a PSAMP Exporting Process to a PSAMP Colleting Process. [PSAMP-INFO]: "Information Model for Packet Sampling Exports" defines an information and data model for PSAMP. 3. Terminology The PSAMP terminology defined here includes all terms listed in [PSAMP-FW]. We here define additional terms required for the description of the packet selection methods. An architecture overview and possible configurations of PSAMP elements can be found in [PSAMP-FW]. PSAMP terminology also aims to be consistent with terms used in [IPFIX-REQ]. The relationship between some PSAMP and IPFIX terms is described in [PSAMP-FW]. 3.1 Observation Points, Packet Streams and Packet Content * Observation Point An Observation Point is a location in the network where packets can be observed. Examples include: (i) a line to which a probe is attached; (ii) a shared medium, such as an Ethernet-based LAN; (iii) a single port of a router, or set of interfaces (physical or logical) of a router; (iv) an embedded measurement subsystem within an interface. Note that one Observation Point may be a superset of several other Observation Points. For example one Observation Point can be an entire line card. This would be the superset of the individual Observation Points at the line card's interfaces. * Observed Packet Stream The Observed Packet Stream is the set of all packets observed at the Observation Point. * Packet Stream Zseby, Molina, Duffield, Niccolini, Raspall [Page 5] Internet Draft Techniques for IP Packet Selection February 2005 A packet stream denotes a subset of the Observed Packet Stream that flows past some specified point within the measurement process. An example of a Packet Stream is the output of the selection process. * Packet Content The packet content denotes the union of the packet header (which includes link layer, network layer and other encapsulation headers) and the packet payload. Note that packets selected from a stream, e.g. by Sampling, do not necessarily possess a property by which they can be distinguished from packets that have not been selected. For this reason the term "stream" is favored over "flow", which is defined as set of packets with common properties [IPFIX-REQ]. 3.2 Selection Process * Selection Process A selection process takes the Observed Packet Stream as its input and selects a subset of that stream as its output. * Selection State A selection process may maintain state information for use by the selection process and/or the reporting process. At a given time, the selection state may depend on packets observed at and before that time, and other variables. Examples include: (i) sequence numbers of packets at the input of Selectors; (ii) a timestamp of observation of the packet at the Observation Point; (iii) iterators for pseudorandom number generators; (iv) hash values calculated during selection; (v) indicators of whether the packet was selected by a given Selector; Selection processes may change portions of the selection state as a result of processing a packet. Selection state for a packet is to reflect the state after processing the packet. * Selector Zseby, Molina, Duffield, Niccolini, Raspall [Page 6] Internet Draft Techniques for IP Packet Selection February 2005 A Selector defines the action of a selection process on a single packet of its input. If selected, the packet becomes an element of the output packet stream. The Selector can make use of the following information in determining whether a packet is selected: (i) the packet's content; (ii) information derived from the packet's treatment at the Observation Point; (iii) any selection state that may be maintained by the selection process. * Composite Selector A Composite Selector is an ordered composition of Selectors, in which the output Packet Stream issuing from one Selector forms the input Packet Stream to the succeeding Selector. * Primitive Selector A Selector is primitive if it is not a Composite Selector. 3.3 Reporting Process * Reporting Process: A reporting process creates a report stream on packets selected by a selection process, in preparation for export. The input to the reporting process comprises that information available to the selection process per selected packet, specifically: (i) the selected packet's content; (ii) information derived from the selected packet's treatment at the Observation Point; (iii) any selection state maintained by the inputting selection process, reflecting any modifications to the selection state made during selection of the packet. * Packet Reports Packet reports comprise a configurable subset of a packet's input to the reporting process, including the packet's content, information relating to its treatment(for example, Zseby, Molina, Duffield, Niccolini, Raspall [Page 7] Internet Draft Techniques for IP Packet Selection February 2005 the output interface), and its associated selection state (for example, a hash of the packet's content) * Report Interpretation: Report interpretation comprises subsidiary information, relating to one or more packets, that is used for interpretation of their packet reports. Examples include configuration parameters of the selection process and of the reporting process. * Report Stream: The report stream is the output of a reporting process, comprising two distinguished types of information: packet reports, and report interpretation. 3.4 Measurement Process * Measurement Process A Measurement Process is the composition of a selection process that takes the Observed Packet Stream as its input, followed by a reporting process. 3.5 Exporting Process * Exporting Process: An Exporting Process sends, in the form of Export Packet, the output of one or more measurement processes to one or more Collectors. * Export Packets: An Export Packet is a combination of report interpretation and/or one or more packet reports are bundled by the Exporting Process into a Export Packet for exporting to a Collector. 3.6 PSAMP Device * PSAMP Device A PSAMP Device is a device hosting at least an Observation Point, a measurement process and an Exporting Process. Typically, corresponding Observation Point(s), measurement process(es) and Exporting Process(es) are co-located at this device, for example at a router. Zseby, Molina, Duffield, Niccolini, Raspall [Page 8] Internet Draft Techniques for IP Packet Selection February 2005 3.7 Collector * Collector A Collector receives a report stream exported by one or more Exporting Processes. In some cases, the host of the measurement and/or Exporting Processes may also serve as the Collector. 3.8 Selection Methods * Filtering A filter is a Selector that selects a packet deterministically based on the packet content, or its treatment, or functions of these occurring in the selection state. Examples include match Filtering, and Hash-based Selection. * Sampling A Selector that is not a filter is called a Sampling operation. This reflects the intuitive notion that if the selection of a packet cannot be determined from its content alone, there must be some type of Sampling taking place. * Content-independent Sampling A Sampling operation that does not use packet content (or quantities derived from it) as the basis for selection is called a content-independent Sampling operation. Examples include systematic Sampling, and uniform pseudorandom Sampling driven by a pseudorandom number whose generation is independent of packet content. Note that in content- independent Sampling it is not necessary to access the packet content in order to make the selection decision. * Content-dependent Sampling A Sampling operation where selection is dependent on packet content is called a Content-dependent Sampling operation. Examples include pseudorandom selection according to a probability that depends on the contents of a packet field. Note that this is not a filter, because the selection is not deterministic. * Hash Domain A subset of the packet content and the packet treatment, viewed as an N-bit string for some positive integer N. Zseby, Molina, Duffield, Niccolini, Raspall [Page 9] Internet Draft Techniques for IP Packet Selection February 2005 * Hash Range A set of M-bit strings for some positive integer M. * Hash Function A deterministic map from the Hash Domain into the Hash Range. * Hash Selection Range A subset of the Hash Range. The packet is selected if the action of the Hash Function on the Hash Domain for the packet yields a result in the Hash Selection Range. * Hash-based Selection Filtering specified by a Hash Domain, a Hash Function, and Hash Range and a Hash Selection Range. * Approximative Selection Selectors in any of the above categories may be approximated by operations in the same or another category for the purposes of implementation. For example, uniform pseudorandom Sampling may be approximated by Hash-based Selection, using a suitable Hash Function and Hash Domain. In this case, the closeness of the approximation depends on the choice of Hash Function and Hash Domain. * Population A Population is a Packet Stream, or a subset of a Packet Stream. A Population can be considered as a base set from which packets are selected. An example is all packets in the Observed Packet Stream that are observed within some specified time interval. * Population Size The Population Size is the number of all packets in the Population. * Sample Size The number of packets selected from the Population by a Selector. * Configured Selection Fraction Zseby, Molina, Duffield, Niccolini, Raspall [Page 10] Internet Draft Techniques for IP Packet Selection February 2005 The Configured Selection Fraction is the ratio of the number of packets selected by a Selector from an input Population, to the Population Size, as based on the configured selection parameters. * Attained Selection Fraction The Attained Selection Fraction is the actual ratio of the number of packets selected by a Selector from an input Population, to the Population Size. For some sampling methods the Attained Selection Fraction can differ from the Configured Selection Fraction due to, for example, the inherent statistical variability in sampling decisions of probabilistic Sampling and Hash-based Selection. Nevertheless, for large Population Sizes and properly configured Selectors, the Attained Selection Fraction usually approaches the Configured Selection Fraction. 4. Categorization of Packet Selection Techniques Packet selection techniques generate a subset of packets from an Observed Packet Stream at an Observation Point. We distinguish between Sampling and Filtering. Sampling is targeted at the selection of a representative subset of packets. The subset is used to infer knowledge about the whole set of observed packets without processing them all. The selection can depend on packet position, and/or on packet content, and/or on (pseudo) random decisions. Filtering selects a subset with common properties. This is used if only a subset of packets is of interest. The properties can be directly derived from the packet content, or depend on the treatment given by the router to the packet. Filtering is a deterministic operation. It depends on packet content or router treatment. It never depends on packet position or on (pseudo) random decisions. Note that a common technique to select packets is to compute a Hash Function on some bits of the packet header and/or content and to select it if the Hash Value falls in the Hash Selection Range. Since hashing is a deterministic operation on the packet content, it is a Filtering technique according to our categorization. Nevertheless, Hash Functions are sometimes used to emulate random Sampling. Depending on the chosen input bits, the Hash Function and the Hash Selection Range, this technique can be used to emulate the random selection of packets with a Zseby, Molina, Duffield, Niccolini, Raspall [Page 11] Internet Draft Techniques for IP Packet Selection February 2005 given probability p. It is also a powerful technique to consistently select the same packet subset at multiple Observation Points [DuGr00] The following table gives an overview of the schemes described in this document and their categorization. An X in brackets (X) denotes schemes for which also content-independent variants exist. It easily can be seen that only schemes with both properties, content dependence and deterministic selection, are considered as filters. Selection Scheme | Deterministic | Content- | Category | Selection | dependent| ------------------------+---------------+----------+---------- Systematic | X | _ | Sampling Count-based | | | ------------------------+---------------+----------+---------- Systematic | X | - | Sampling Time-based | | | ------------------------+---------------+----------+---------- Random | - | - | Sampling n-out-of-N | | | ------------------------+---------------+----------+---------- Random | - | - | Sampling Uniform probabilistic | | | ------------------------+---------------+----------+---------- Random | - | (X) | Sampling Non-uniform probabil. | | | ------------------------+---------------+----------+---------- Random | - | (X) | Sampling Non-uniform flow-state | | | ------------------------+---------------+----------+---------- Field match filtering | X | X | Filter ------------------------+---------------+----------+---------- Hash Function | X | X | Filter ------------------------+---------------+----------+---------- Router state filtering | X | (X) | Filter ------------------------+---------------+----------+---------- The categorization just introduced is mainly useful for the definition of an information model describing Primitive Selectors. More complex selection techniques can be described through the composition of cascaded Sampling and Filtering operations. For example, a packet selection that weights the selection probability on the basis of the packet length can be described as a cascade of a filter and a Sampling scheme. Zseby, Molina, Duffield, Niccolini, Raspall [Page 12] Internet Draft Techniques for IP Packet Selection February 2005 However, this descriptive approach is not intended to be rigid: if a common and consolidated selection practice turns out to be too complex to be described as a composition of the mentioned building blocks, an ad hoc description can be specified instead and added as a new scheme to the information model. 5. Sampling The deployment of Sampling techniques aims at the provisioning of information about a specific characteristic of the parent population at a lower cost than a full census would demand. In order to plan a suitable Sampling strategy it is therefore crucial to determine the needed type of information and the desired degree of accuracy in advance. First of all it is important to know the type of metric that should be estimated. The metric of interest can range from simple packet counts [JePP92] up to the estimation of whole distributions of flow characteristics (e.g. packet sizes)[ClPB93]. Secondly, the required accuracy of the information and with this, the confidence that is aimed at, should be known in advance. For instance for usage-based accounting the required confidence for the estimation of packet counters can depend on the monetary value that corresponds to the transfer of one packet. That means that a higher confidence could be required for expensive packet flows (e.g. premium IP service) than for cheaper flows (e.g. best effort). The accuracy requirements for validating a previously agreed quality can also vary extremely with the customer demands. These requirements are usually determined by the service level agreement (SLA). The Sampling method and the parameters in use must be clearly communicated to all applications that use the measurement data. Only with this knowledge a correct interpretation of the measurement results can be ensured. Sampling methods can be characterized by the Sampling algorithm, the trigger type used for starting a Sampling interval and the length of the Sampling interval. These parameters are described here in detail. The Sampling algorithm describes the basic process for selection of samples. In accordance to [AmCa89] and [ClPB93] we define the following basic Sampling processes: 5.1 Systematic Sampling Systematic Sampling describes the process of selecting the start points and the duration of the selection intervals according to Zseby, Molina, Duffield, Niccolini, Raspall [Page 13] Internet Draft Techniques for IP Packet Selection February 2005 a deterministic function. This can be for instance the periodic selection of every k-th element of a trace but also the selection of all packets that arrive at pre-defined points in time. Even if the selection process does not follow a periodic function (e.g. if the time between the Sampling intervals varies over time) we consider this as systematic Sampling as long as the selection is deterministic. The use of systematic Sampling always involves the risk of biasing the results. If the systematics in the Sampling process resemble systematics in the observed stochastic process (occurrence of the characteristic of interest in the network), there is a high probability that the estimation will be biased. Systematics in the observed process might not be known in advance. Here only equally spaced schemes are considered, where triggers for Sampling are periodic, either in time or in packet count. All packets occurring in a selection interval (either in time or packet count) beyond the trigger are selected. Systematic count-based In systematic count-based Sampling the start and stop triggers for the Sampling interval are defined in accordance to the spatial packet position (packet count). Systematic time-based In systematic time-based Sampling time-based start and stop triggers are used to define the Sampling intervals. All packets are selected that arrive at the Observation Point within the time-intervals defined by the start and stop triggers (i.e. arrival time of the packet is larger than the start time and smaller than the stop time). Both schemes are content-independent selection schemes. Content dependent deterministic Selectors are categorized as filter. 5.2 Random Sampling Random Sampling selects the starting points of the Sampling intervals in accordance to a random process. The selection of elements are independent experiments. With this, unbiased estimations can be achieved. In contrast to systematic Sampling, random Sampling requires the generation of random numbers. One can differentiate two methods of random Sampling: 5.2.1 n-out-of-N Sampling Zseby, Molina, Duffield, Niccolini, Raspall [Page 14] Internet Draft Techniques for IP Packet Selection February 2005 In n-out-of-N Sampling n elements are selected out of the parent population that consists of N elements. One example would be to generate n different random numbers in the range [1,N] and select all packets which have a packet position equal to one of the random numbers. For this kind of Sampling the Sample Size n is fixed. 5.2.2 Probabilistic Sampling In probabilistic Sampling the decision whether an element is selected or not is made in accordance to a pre-defined selection probability. An example would be to flip a coin for each packet and select all packets for which the coin showed the head. For this kind of Sampling the Sample Size can vary for different trials. The selection probability does not necessarily has to be the same for each packet. Therefore we distinguish between uniform probabilistic Sampling (with the same selection probability for all packets) and non-uniform probabilistic Sampling (where the selection probability can vary for different packets). 5.2.2.1 Uniform Probabilistic Sampling For Uniform Probabilistic Sampling packets are selected independently with a uniform probability p. This Sampling can be count-driven, and is sometimes referred to as geometric random Sampling, since the difference in count between successive selected packets are independent random variables with a geometric distribution of mean 1/p. A time-driven analog, exponential random Sampling, has the time between triggers exponentially distributed. Both geometric and exponential random Sampling are examples of what is known as additive random Sampling, defined as Sampling where the intervals or counts between successive samples are independent identically distributed random variable. 5.2.2.2 Non-Uniform Probabilistic Sampling This is a variant of Probabilistic Sampling in which the Sampling probabilities can depend on the selection process input. This can be used to weight Sampling probabilities in order e.g. to boost the chance of Sampling packets that are rare but are deemed important. Unbiased estimators for quantitative statistics are recovered by renormalization of sample values; see [HT52]. 5.2.2.3 Non-Uniform Flow State Dependent Sampling Zseby, Molina, Duffield, Niccolini, Raspall [Page 15] Internet Draft Techniques for IP Packet Selection February 2005 Another type of Sampling that can be classified as probabilistic Non-Uniform is closely related to the flow concept as defined in [IPFIX-REQ], and it is only used jointly with a flow monitoring function (IPFIX metering process). Packets are selected, dependent on a selection state. The point, here, is that the selection state is determined also by the state of the flow the packet belongs to and/or by the state of the other flows currently being monitored by the associated flow monitoring function. An example for such an algorithm is the "sample and hold" method described in [EsVa01]: - If a packet accounts for a flow record that already exists in the IPFIX flow recording process, it is selected (i.e. the flow record is updated) - If a packet doesn't account to any existing flow record, it is selected with probability p. If it has been selected a new flow record has to be created. A further algorithm that fits into the category of non-uniform flow state dependent Sampling is described in [Moli03]. This type of Sampling is content dependent because the identification of the flow the packet belongs to requires analyzing part of the packet content. If the packet is selected, then it is passed as an input to the IPFIX monitoring function (this is called "Local Export" in [PSAMP-FW] Selecting the packet depending on the state of a flow cache is useful when memory resources of the flow monitoring function are scarce (i.e. there is no room to keep all the flows that have been scheduled for monitoring). See [MolFl03] for a more detailed description of the motivations for this type of Sampling and the impact on the IPFIX metering. 5.2.2.4 Configuration of non-uniform probabilistic and flow-state Sampling Many different specific methods can be grouped under the terms non-uniform probabilistic and flow state Sampling. Dependent on the Sampling goal and the implemented scheme, a different number and type of input parameters is required to configure such scheme. Some concrete proposals for such methods exist from the research community (e.g. [EsVa01],[DuLT01],[Moli03]). Some of these proposals are still in an early stage and need further investigations to prove their usefulness and applicability. It is not our aim to indicate preference amongst these methods. Instead, we only describe here the basic methods and leave the Zseby, Molina, Duffield, Niccolini, Raspall [Page 16] Internet Draft Techniques for IP Packet Selection February 2005 specification of explicit schemes and their parameters up to vendors (e.g. as extension of the information model). 6. Filtering Filtering is the deterministic selection of packets based on the packet content, the treatment of the packet at the Observation Point, or deterministic functions of these occurring in the selection state. The packet is selected if these quantities fall into a specified range. The role of Filtering, as the word itself suggest, is to separate all the packets having a certain property from those not having it. A distinguishing characteristic from Sampling is that the selection decision does not depend on the packet position in time or in the space, or on a random process. We identify and describe in the following three Filtering techniques. The first two (Match Filtering and Hashing Filtering) are stateless, and therefore can make their decision based on the analysis of portion of the packet only. The other (router state Filtering) requires to access state information after the analysis of part of the packet and is therefore more complex: its usage makes sense only in particular circumstances, as described below. 6.1 Field Match Filtering We here define a basic Filtering schemes based on the IPIFIX flow definition. With this method a packet is selected if a specific field in the packet equals a predefined value. Possible filter fields are all IPFIX flow attributes specified in [IPFIX- INFO]. Further fields can be defined by vendor specific extensions. A packet is selected if Field=Value. Masks and ranges are only supported to the extend to which [IPFIX-INFO] allows them e.g. by providing explicit fields like the netmasks for source and destination addresses. AND operations are possible by concatenating filters. OR operations are not supported with this basic model. More sophisticated filters (e.g. supporting bitmasks, ranges or OR operations etc.) can be realized as vendor specific schemes. 6.2 Hash-based Filtering A Hash Function h maps the packet content c, or some portion of it, onto a Hash Range R. The packet is selected if h(c) is an element of S, which is a subset of R called the Hash Selection Range. Thus Hash-based Selection is indeed a particular case of Filtering: the object is selected if c is in inv(h(S)). But for desirable Hash Functions the inverse image inv(h(S)) will be Zseby, Molina, Duffield, Niccolini, Raspall [Page 17] Internet Draft Techniques for IP Packet Selection February 2005 extremely complex, and hence h would not be expressible as, say, a match/mask filter or a simple combination of these. Hash-based selection has mainly two types of usage: it offers a way to approximate random Sampling by using packet content to generate pseudorandom variates, and a way to consistently select subsets of packets that share a common property (e.g. at different Observation Points). In the following subsections we give more details about them. However, both usages require that the Hash Functions has two statistical properties. First, the Hash Function h must have good mixing properties, in the sense that small changes in the input (e.g. the flipping of a single bit) cause large changes in the output (many bits change). Then any local clump of values of c is spread widely over R by h, and so the distribution of h(c) is fairly uniform even if the distribution of c is not. Then the Sampling Fraction is #S/#R, which can be tuned by choice of S. The second desirable property depends more closely on the statistics of the content c. In applications, the content c comprises a number of distinct fields, c1 ... cm, e.g. source and destination IP Address, IP identification, and TCP/UDP port numbers (if present) for a packet. With a Hash Function satisfying the first properties above, selection decisions will appear uncorrelated with the contents of any individual field, if the complementary fields are (i) sufficiently variable themselves, and (ii) sufficiently uncorrelated with cj. 6.2.1 Application Examples for Hash-based Selection 6.2.1.1 Approximation of Random Sampling Although pseudorandom number generators with well understood properties have been developed, they may not be the method of choice in settings where computational resources are scarce. A convenient alternative is to use Hash Functions of packet content as a source of randomness. The hash (suitably renormalized) is a pseudorandom variate in the interval [0,1]. Other schemes may use packet fields in iterators for pseudorandom numbers. However, the statistical properties of an ideal packet selection law (such as independent Sampling for different packets, or independence on packet content) may not be exactly rendered by an implementation, but only approximately so. Use of packet content to generate pseudorandom variates shares with non-uniform probabilistic Sampling (see Section 3.1.2.2.2 Zseby, Molina, Duffield, Niccolini, Raspall [Page 18] Internet Draft Techniques for IP Packet Selection February 2005 above) the property that selection decisions depend on packet content. However, there is a fundamental difference between the two. In the former case the content determines pseudorandom variates. In the latter case the content only determines the selection probabilities: selection could then proceed e.g by use of random variates obtained by an independent pseudorandom number generator. 6.2.1.2 Trajectory Sampling and Consistent packet selection. Trajectory Sampling is the consistent selection of a subset of packets at either all of a set of Observation Points or none of them. Trajectory Sampling is realized by Hash-based Selection if all Observation Points in the set use a common Hash Function, Hash Domain and selection range. The Hash Domain comprises all or part of the packet content that is invariant along the packet path. Fields such as Time-to-Live, which is decremented per hop, and header CRC, which is recalculated per hop, are thus excluded from the Hash Domain. The Hash Domain needs to be wider than just a flow key, if packets are to be selected quasirandomly within flows. The trajectory (or path) followed by a packet is reconstructed from PSAMP reports on it that reach a Collector. Reports on a given packet originating from different observations points are associated by matching a label from the reports. The label may comprise that portion invariant packet content that is reported, or possibly some digest of the invariant packet content that is inserted into the packet report at the Observation Point. Such a digest may be constructed by applying a second Hash Function (distinct from that used for selection) to the invariant packet content. The reconstruction of trajectories, and methods for dealing with possible ambiguities due to label collisions (identical labels reported for different packets) and potential loss of reports in transmission, are dealt with in [DuGr01], [DuGeGr02] and [DuGr04]. Applications of trajectory Sampling include (i) estimation of the network path matrix, i.e., the traffic intensities according to network path, broken down by flow key; (ii) detection of routing loops, as indicated by self-intersecting trajectories; (iii) passive performance measurement: prematurely terminating trajectories indicate packet loss, packet one way delay can be determined if reports include (synchronized) timestamps of packet arrival at the Observation Point; (iv) network attack tracing, of the actual paths taken by attack packets with spoofed source addresses. Zseby, Molina, Duffield, Niccolini, Raspall [Page 19] Internet Draft Techniques for IP Packet Selection February 2005 6.2.2 Guarding Against Pitfalls and Vulnerabilities A concern for Hash-based Selection is whether some large set of related packets could have an Attained Sampling Fraction significantly different from the Configured Sampling Fraction, either (i) through unanticipated behavior in the Hash Function, or (ii) because the packets had been deliberately crafted to have this property. The first point underlines the importance of using a Hash Function with good mixing properties. Examples of such are CRC32 and Hash Functions based on modular arithmetic, see 6.4 in [Knuth98]. The statistical properties of candidate Hash Functions need to be evaluated, preferably on packet traces before adoption for hash-based Sampling Hash-based selection could be overloaded or evaded by an attacker if the Hash Function and the selection range are both known. A service provider could build a first defense keeping the Hash Selection Range S private. Then, an attacker could not determine whether a crafted packet is selected, but would still know that a crafted set of packets all with the same hash is either all selected or all not selected. A stronger defense is to employ a parametrizable Hash Function and keep the parameter private. Without knowledge of the parameter, a set of packets with common hash value cannot be constructed. Examples of parameters are the initial vector in CRC32, and moduli in hashes based on modular arithmetic. 6.2.3 Recommendations of Specific Hash Fuctions We here indicate some Hash Functions that can be used for packet selection. The description of these Hash Functions (IPSX and BOB) can be found in the appendix or, in the case of the CRC-32 function, in [crc32]. In [MNiD04] different Hash Functions were compared for collision probability, the uniformity of the distribution of selected packets and the speed of the functions. A detailed description of the IPSX and the BOB function is provided in the appendix. Further Hash Functions are described in [MNiD04]. Note that all Hash Functions were evaluated only for IPv4. 6.2.3.1 Hash Functions Suitable for Packet Selection For hash-based packet selection, the most important requirements for the Hash Function are high execution speed (since selection must operate and line rate, and uniformity of hash distribution Zseby, Molina, Duffield, Niccolini, Raspall [Page 20] Internet Draft Techniques for IP Packet Selection February 2005 (in order to approximate random Sampling at a specified Sampling Fraction). For this purpose the IPSX Hash Function is recommended. It is simple with high execution speed, and good uniformity of distribution. Other functions (like BOB) may be used. 6.2.3.2 Hash Functions Suitable for Packet Digesting For digesting packet content for inclusion in a reported label, the most important property is a low collision frequency. A secondary requirement is the ability to accept variable length input, in order to allow inclusion of maximal amount of packet as input. (Execution speed is of secondary importance, since the digest need only be formed from selected packets). For this purpose CRC-32 is recommended. Other functions (such as like BOB) may be used. Among the functions capable of operating with variable length input BOB and CRC-32 have the fastest execution, BOB being slightly faster. Nevertheless, CRC-32 has already been widely applied (for other scopes) and is therefore preferred for its wider implementation basis. IPSX is not recommended for digesting because it has significantly higher collision rate and takes only a fixed length input. 6.3 Router State Filtering This class of filters select a packet on the basis of router state conditions. The following list gives examples for such conditions. Conditions can be combined with AND operators. - Ingress interface at which the packet arrives equals a specified value - Egress interface to which the packet is routed equals a specified value - Packet violated Access Control List (ACL) on the router - Reverse Path Forwarding (RPF) failed for the packet - Resource Reservation is insufficient for the packet - No route found for the packet - Origin BGP AS [RFC1771] equals a specified value or lies within a given range - Destination BGP AS equals a specified value or lies within a given range Router architectural considerations may preclude some information concerning the packet treatment, e.g. routing state, being available at line rate for selection of packets. However, if selection not based on routing state has reduced down from line rate, subselection based on routing state may be feasible. Zseby, Molina, Duffield, Niccolini, Raspall [Page 21] Internet Draft Techniques for IP Packet Selection February 2005 7. Parameters for the Description of Selection Techniques This section gives an overview of different alternative selection schemes and their required parameters. In order to be compliant with PSAMP at least one of proposed schemes MUST be implemented. The decision whether to select a packet or not is based on a function which is performed when the packet arrives at the selection process. Packet selection schemes differ in the input parameters for the selection process and the functions they require to do the packet selection. The following table gives an overview. Scheme | input parameters | functions ---------------+------------------------+------------------- systematic | packet position | packet counter count-based | Sampling pattern | ---------------+------------------------+------------------- systematic | arrival time | clock or timer time-based | Sampling pattern | ---------------+------------------------+------------------- random | packet position | packet counter, n-out-of-N | Sampling pattern | random numbers | (random number list) | ---------------+------------------------+------------------- uniform | Sampling | random function probabilistic | probability | ---------------+------------------------+------------------- non-uniform |e.g. packet position, | selection function, probabilistic | packet content(parts) | probability calc. ---------------+------------------------+------------------- non-uniform |e.g. flow state, | selection function, flow-state | packet content(parts) | probability calc. ---------------+------------------------+------------------- field match | packet content(parts) | filter function ---------------+------------------------+------------------- hash-based | packet content(parts) | Hash Function ---------------+------------------------+------------------- router state | router state | router state | | discovery ---------------+------------------------+------------------- 7.1 Description of Sampling Techniques In this section we define what elements are needed to describe the most common Sampling techniques. Here the selection function is pre-defined and given by the Selector ID. Zseby, Molina, Duffield, Niccolini, Raspall [Page 22] Internet Draft Techniques for IP Packet Selection February 2005 Sampler Description: SELECTOR_ID SELECTOR_TYPE SELECTOR_PARAMETERS ASSOCIATIONS Where: SELECTOR_ID: Unique ID for the packet sampler, calculated as combination of the ASSOCIATIONS and a local ID. SELECTOR_TYPE For Sampling processes the SELECTOR TYPE defines what Sampling algorithm is used. Values: Systematic Count-based | Systematic Time-based | Random n-out-of-N | Uniform Probabilistic | Non-uniform Probabilistic | Non-uniform Flow-state SELECTOR_PARAMETERS For Sampling processes the SELECTOR PARAMETERS define the input parameters for the process. Interval length in systematic Sampling means, that all packets that arrive in this interval are selected. The spacing parameter defines the spacing in time or number of packets between the end of one Sampling interval and the start of the next succeeding interval. Case n out of N: - Population size N, Sample size n Case Systematic Time Based: - Interval length (in usec), Spacing (in usec) Case Systematic Count Based: - Interval length(in packets), Spacing (in packets) Case Uniform Probabilistic (with equal probability per packet): - Sampling probability p Case Non-uniform Probabilistic: - Calculation function for Sampling probability p (see also section 5.2.2.4) Case flow state: - Information reported for flow state can be found in [MolFl03](see also section 5.2.2.4) ASSOCIATIONS Zseby, Molina, Duffield, Niccolini, Raspall [Page 23] Internet Draft Techniques for IP Packet Selection February 2005 The ASSOCIATIONS field describes the Observation Point and optionally the IPFIX processes to which the packet Selector is associated. If no IPFIX process is specified, the selector is applied to all IPFIX processes on the observation point. The STREAM ID denotes the origin of the data stream that is input to the selection function. It can be the Observation Point directly or the ID of another Selector. With this it is possible to define combined schemes. If the STREAM ID contains IDs from other Selectors, one can derive the original Observation Point from the Selector definitions of these specified Selectors. Values: With STREAM ID: Observation point ID AND List of SELECTOR_IDs 7.2 Description of Filtering Techniques In this section we define what elements are needed to describe the most common Filtering techniques. The structure closely parallels the one presented for the Sampling techniques. Filter Description: SELECTOR_ID SELECTOR_TYPE SELECTOR_PARAMETERS ASSOCIATIONS Where: SELECTOR_ID: Unique ID for the packet filter. The ID can be calculated under consideration of the ASSOCIATIONS and a local ID. SELECTOR_TYPE For Filtering processes the SELECTOR TYPE defines what Filtering type is used. Values: Matching | Hashing | Router_state SELECTOR_PARAMETERS For Filtering processes the SELECTOR PARAMETERS define formally the common property of the packet being filtered. For the filters of type Matching and Hashing the definitions have a lot of points in common. Values: Case Matching - Information Element (from [IPFIX-INFO]) - Value (type in accordance to [IPFIX-INFO]) Zseby, Molina, Duffield, Niccolini, Raspall [Page 24] Internet Draft Techniques for IP Packet Selection February 2005 In case of multiple match criteria, multiple "case matching" have to be bound by a logical AND. Case Hashing: - Hash Domain (Input bits from packet) -
- -
- - - - Hash Function - Hash function name - Length of input key (eliminate 0x bytes) - Output value (length M and bitmask) - Hash Selection Range, as a list of non overlapping intervals [start value, end value] where value is in [0,2^M-1] - Additional parameters dependent on specific Hash Function (e.g. hash input bits (seed)) Notes to input bits for Case Hashing: - Input bits can be from header part only, from the payload part only or from both. - The bit specification, for the header part, can be specified for ipv4 or ipv6 only, or both - In case of ipv4, the bit specification is a sequence of 20 Hexadecimal numbers [00,FF] specifying a 20 bytes bitmask to be applied to the header. - In case of ipv6, it is a sequence of 40 Hexadecimal numbers [00,FF] specifying a 40 bytes bitmask to be applied to the header - The bit specification, for the payload part, is a sequence of Hexadecimal numbers [00,FF] specifying the bitmask to be applied to the first N bytes of the payload, as specified by the previous field. In case the Hexadecimal number sequence is longer then N, only the first N numbers are considered. - In case the payload is shorter than N, the Hash Function cannot be applied. Other options, like padding with zeros, may be considered in the future. - A Hash Function cannot be defined on the options field of the ipv4 header, neither on stacked headers of ipv6. - The Hash Selection Range defines a range of hash-values (out of all possible results of the Hash-Operation). If the hash result for a specific packet falls in this range, the packet is selected. If the value is outside the range, the packet is not selected. E.g. if the selection interval Zseby, Molina, Duffield, Niccolini, Raspall [Page 25] Internet Draft Techniques for IP Packet Selection February 2005 specification is [1:3], [6:9] all packets are selected for which the hash result is 1,2,3,6,7,8, or 9. In all other cases the packet is not selected. Case Router State: - Ingress interface at which the packet arrives equals a specified value - Egress interface to which the packet is routed equals a specified value - Packet violated Access Control List (ACL) on the router - Reverse Path Forwarding (RPF) failed for the packet - Resource Reservation is insufficient for the packet - No route found for the packet - Origin AS equals a specified value or lies within a given range - Destination AS equals a specified value or lies within a given range Note to Case Router State: - All Router state entries can be linked by AND operators ASSOCIATIONS The ASSOCIATIONS field describes the Observation Point and optionally the IPFIX processes to which the packet Selector is associated. If no IPFIX process is specified, the Selector is applied to all IPFIX processes on the observation point. The STREAM ID denotes the origin of the data stream that is input to the selection function. It can be the Observation Point directly or the ID of another Selector. With this it is possible to define combined schemes. If the STREAM ID contains IDs from other Selectors, one can derive the original Observation Point from the Selector definitions of these specified Selectors. Values: With STREAM ID: Observation point ID AND List of SELECTOR_IDs 8. Composite Techniques Composite schemes are realized by using the STREAM ID in the information models. The STREAM ID denotes from which Selectors the input stream originates. If multiple stream IDs are given, this means that the Selector operates on the packet stream simply resulting from the time superposition of the output of all the listed filters and samplers. Some examples of composite schemes are reported below. Zseby, Molina, Duffield, Niccolini, Raspall [Page 26] Internet Draft Techniques for IP Packet Selection February 2005 8.1 Cascaded Filtering->Sampling or Sampling->Filtering If a filter precedes a Sampling process the role of Filtering is to create a set of "parent populations" from a single stream that can then be fed independently to different Sampling functions, with different parameters tuned for the population itself (e.g. if streams of different intensity result from Filtering, it may be good to have different Sampling rates). If Filtering follows a Sampling process, the same Sampling Fraction and type is applied to the whole stream, independently of the relative size of the streams resulting from the Filtering function. Moreover, also packets not destined to be selected in the Filtering operation will "load" the Sampling function. So, in principle, Filtering before Sampling allows a more accurate tuning of the Sampling procedure, but if filters are too complex to work at full line rate (e.g. because they have to access router state information), Sampling before Filtering may be a need. 8.2 Stratified Sampling Stratified Sampling is one example for using a composite technique. The basic idea behind stratified Sampling is to increase the estimation accuracy by using a-priori information about correlations of the investigated characteristic with some other characteristic that is easier to obtain. The a-priori information is used to perform an intelligent grouping of the elements of the parent population. With this a higher estimation accuracy can be achieved with the same Sample Size or the Sample Size can be reduced without reducing the estimation accuracy. Stratified Sampling divides the Sampling process into multiple steps. First, the elements of the parent population are grouped into subsets in accordance to a given characteristic. This grouping can be done in multiple steps. Then samples are taken from each subset. The stronger the correlation between the characteristic used to divide the parent population (stratification variable) and the characteristic of interest (for which an estimate is sought after), the easier is the consecutive Sampling process and the higher is the stratification gain. For instance if the dividing characteristic were equal to the investigated characteristic, each element of the sub-group would be a perfect representative of that characteristic. In this case it would be sufficient to take one arbitrary element out of each subgroup to get the actual distribution of the characteristic in the parent population. Therefore stratified Sampling can reduce the costs Zseby, Molina, Duffield, Niccolini, Raspall [Page 27] Internet Draft Techniques for IP Packet Selection February 2005 for the Sampling process (i.e. the number of samples needed to achieve a given level of confidence). For stratified Sampling one has to specify classification rules for grouping the elements into subgroups and the Sampling scheme that is used within the subgroups. The classification rules can be expressed by multiple filters. For the Sampling scheme within the subgroups the parameters have to be specified as described above. The use of stratified Sampling methods for measurement purposes is described for instance in [ClPB93] and [Zseb03]. 9. Security Considerations Malicious users or attackers may wish to hide packets from service providers or network operators. For instance if packet Selectors are used for accounting or intrusion detection applications, users may want to prevent certain packets from being selected. If a deterministic Sampling scheme is used or a selection scheme that takes packet content into account, the user can shape or send packets in a way that they are less likely to be selected (see also section 6.2.2). Even if the selection function is unknown to the user, some insight into the function can be obtained by performing experiments with different packet sequences. This has to be taken into account when choosing an appropriate packet selection technique. Further security threats can occur if the configuration of Sampling parameters or the communication of Sampling parameters to the application is corrupted. This document only describes Sampling schemes that can be used for packet selection. It neither describes a mechanism how those parameters are configured nor how these parameters are communicated to the application. Therefore the security threats that originate from this kind of communication cannot be assessed with the information given in this document. 10. Acknowledgements We would like to thank the PSAMP group, especially Benoit Claise and Stewart Bryant, for fruitful discussions and for proofreading the document. 11. Normative References [PSAMP-FW] Nick Duffield (Ed.): A Framework for Packet Selection and Reporting, RFC XXXX [currently Internet Draft draft-ietf-psamp-framework-08, work in progress, October 2004] Zseby, Molina, Duffield, Niccolini, Raspall [Page 28] Internet Draft Techniques for IP Packet Selection February 2005 [PSAMP-MIB] T. Dietz, B. Claise: Definitions of Managed Objects for Packet Sampling, RFC XXXX. [Currently Internet Draft, draft-ietf-psamp-mib-03.txt, work in progress, July 2004.] [PSAMP-PROTO] B. Claise (Ed.): Packet Sampling (PSAMP) Protocol Specifications, RFC XXXX. [Currently Internet Draft draft-ietf-psamp-protocol-01.txt, work in progress, February 2004.] [PSAMP-INFO] T. Dietz, F. Dressler, G. Carle, B. Claise: Information Model for Packet Sampling Exports, RFC XXXX. [Currently Internet Draft, draft-ietf-psamp- info-02, July 2004] [IPFIX-INFO] J. Meyer, J. Quittek, S. Bryant: Information Model for IP Flow Information Export, RFC XXXX [Currently Internet Draft, draft-ietf-ipfix-info-04, July 2004] [IPFIX-REQ] J. Quittek, T. Zseby, B. Claise, S. Zander: Requirements for IP Flow Information Export, RFC 3917, October 2004 12. Informative References [AmCa89] Paul D. Amer, Lillian N. Cassel: Management of Sampled Real-Time Network Measurements, 14th Conference on Local Computer Networks, October 1989, Minneapolis, pages 62-68, IEEE, 1989 [ClPB93] K.C. Claffy, George C. Polyzos, Hans-Werner Braun: Application of Sampling Methodologies to Network Traffic Characterization, Proceedings of ACM SIGCOMM'93, San Francisco, CA, USA, September 13 - 17, 1993 [CoGi98] I. Cozzani, S. Giordano: Traffic Sampling Methods for end-to-end QoS Evaluation in Large Heterogeneous Networks. Computer Networks and ISDN Systems, 30 (16-18), September 1998. [crc32] R. Braden, D. Borman, C. Partridge: Computing the Internet Checksum, RFC 1071, Sep. 1988 (updated by RFCs 1141 and 1624) [DuGeGr02] N.G. Duffield, A. Gerber, M. Grossglauser: Trajectory Engine: A Backend for Trajectory Zseby, Molina, Duffield, Niccolini, Raspall [Page 29] Internet Draft Techniques for IP Packet Selection February 2005 Sampling, IEEE Network Operations and Management Symposium 2002, Florence, Italy, April 15-19, 2002. [DuGr00] N.G. Duffield, M. Grossglauser: Trajectory Sampling for Direct Traffic Observation, Proceedings of ACM SIGCOMM 2000, Stockholm, Sweden, August 28 - September 1, 2000. [DuGr04] N. G. Duffield and M. Grossglauser: Trajectory Sampling with Unreliable Reporting, Proc IEEE Infocom 2004, Hong Kong, March 2004, [DuLT01] N.G. Duffield, C. Lund, and M. Thorup: Charging from Sampled Network Usage, ACM Internet Measurement Workshop IMW 2001, San Francisco, USA, November 1-2, 2001 [EsVa01] C. Estan and G. Varghese: New Directions in Traffic Measurement and Accounting, ACM SIGCOMM Internet Measurement Workshop 2001, San Francisco (CA) Nov. 2001 [HT52] D.G. Horvitz and D.J. Thompson: A Generalization of Sampling without replacement from a Finite Universe. J. Amer. Statist. Assoc. Vol. 47, pp. 663-685, 1952. [Jenk97] B. Jenkins: Algorithm Alley, Dr. Dobb's Journal, September 1997. http://burtleburtle.net/bob/hash/doobs.html [JePP92] Jonathan Jedwab, Peter Phaal, Bob Pinna: Traffic Estimation for the Largest Sources on a Network, Using Packet Sampling with Limited Storage, HP technical report, Managemenr, Mathematics and Security Department, HP Laboratories, Bristol, March 1992, http://www.hpl.hp.com/techreports/92/HPL-92-35.html [Knuth98] Donald E. Knuth: The Art of Computer Programming, Volume 3: Searching and Sorting, Addison Wesley, 1998 [MolFl03] M.Molina: Flow selection support in IPFIX, Internet Draft , work in progress, October 2003. Zseby, Molina, Duffield, Niccolini, Raspall [Page 30] Internet Draft Techniques for IP Packet Selection February 2005 [Moli03] M.Molina: A scalable and efficient methodology for flow monitoring in the internet, International Teletraffic Congress (ITC-18), Berlin, Sep. 2003 [MNiD04] M. Molina, S.Niccolini, N.G.Duffield: A Comparative Experimental Study of Hash Functions Applied to Packet Sampling, Aug. 2004, Submitted to ICC 05. [RFC1771] Rekhter, Y. and T. Li: A Border Gateway Protocol 4 (BGP-4), RFC 1771, March 1995. [Zseb03] T. Zseby: Stratification Strategies for Sampling- based Non-intrusive Measurement of One-way Delay. Passive and Active Measurement Workshop Proceedings, La Jolla, CA, USA, pp. 171-179, Apr. 2003 13. Author's Addresses Tanja Zseby Fraunhofer Institute for Open Communication Systems Kaiserin-Augusta-Allee 31 10589 Berlin Germany Phone: +49-30-34 63 7153 Email: zseby@fokus.fhg.de Maurizio Molina DANTE City House 126-130 Hills Road Cambridge CB21PQ United Kingdom Phone: +44 1223 371 300 Email: maurizio.molina@dante.org.uk Nick Duffield AT&T Labs - Research Room B-139 180 Park Ave Florham Park NJ 07932, USA Phone: +1 973-360-8726 Email: duffield@research.att.com Saverio Niccolini Network Laboratories, NEC Europe Ltd. Kurfuerstenanlage 36 69115 Heidelberg Germany Zseby, Molina, Duffield, Niccolini, Raspall [Page 31] Internet Draft Techniques for IP Packet Selection February 2005 Phone: +49-6221-9051118 Email: saverio.niccolini@netlab.nec.de Fredric Raspall EPSC-UPC Dept. of Telematics Av. del Canal Olímpic, s/n Edifici C4 E-08860 Castelldefels, Barcelona Spain Email: fredi@entel.upc.es 14. Intellectual Property Statement The IETF has been notified by AT&T Corp. of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information, see http://www.ietf.org/ietf/IPR/att-ipr-draft-ietf-psamp- framework.txt The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. 15. Copyright Statement Copyright (C) The Internet Society (2004). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Zseby, Molina, Duffield, Niccolini, Raspall [Page 32] Internet Draft Techniques for IP Packet Selection February 2005 16. Disclaimer This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 17. Appendix: Hash Functions 17.1 IP Shift-XOR (IPSX) Hash Function The IPSX Hash Function is tailored for acting on IP version 4 packets. It exploits the structure of IP packet and in particular the variability expected to be exhibited within different fields of the IP packet in order to furnish a hash value with little apparent correlation with individual packet fields. Fields from the IPv4 and TCP/UDP headers are used as input. The IPSX Hash Function uses a small number of simple instructions. Input parameters: None Built-in parameters: None Output: The output of the IPSX is a 16 bit number Functioning: The functioning can be divided into two parts: input selection, which forms are composite input from various portions of the IP packet, followed by computation of the hash on the composite. Input Selection: The raw input is drawn from the first 20 bytes of the IP packet header and the first 8 bytes of the IP payload. If IP options are not used, the IP header has 20 bytes, and hence the two portions adjoin and comprise the first 28 bytes of the IP packet. We now use the raw input as 4 32-bit subportions of these 28 bytes. We specify the input by bit offsets from the start of IP header or payload. f1 = bits 32 to 63 of the IP header, comprising the IP identification field, flags, and fragment offset. Zseby, Molina, Duffield, Niccolini, Raspall [Page 33] Internet Draft Techniques for IP Packet Selection February 2005 f2 = bits 96 to 127 of the IP header, the source IP address. f3 = bits 128 to 159 of the IP header, the destination IP address. f4 = bits 32 to 63 of the IP payload. For a TCP packet, f4 comprises the TCP sequence number followed by the message length. For a UDP packet f4 comprises the UDP checksum. Hash Computation: The hash is computed from f1, f2, f3 and f4 by a combination of XOR (^), right shift (>>) and left shift (<<) operations. The intermediate quantities h1, v1, v2 are 32-bit numbers. 1. v1 = f1 ^ f2; 2. v2 = f3 ^ f4; 3. h1 = v1 << 8; 4. h1 ^= v1 >> 4; 5. h1 ^= v1 >> 12; 6. h1 ^= v1 >> 16; 7. h1 ^= v2 << 6; 8. h1 ^= v2 << 10; 9. h1 ^= v2 << 14; 10. h1 ^= v2 >> 7; The output of the hash is the least significant 16 bits of h1. 17.2 "Bob" Hash Function "Bob" Hash Function is a Hash Function designed for having each bit of the input affecting every bit of the return value and using both 1-bit and 2-bit deltas to achieve the so called avalanche effect [Jenk97]. This function was originally built for hash table lookup with fast software implementation. Input Parameters: The input parameters of such a function are: - the length of the input string (key) to be hashed, in bytes. The elementary input blocks of Bob hash are the single bytes, therefore no padding is needed. - an init value (an arbitrary 32-bit number). Built in parameters: The Bob Hash uses the following built-in parameter: - the golden ratio (an arbitrary 32-bit number used in the hash function computation: its purpose is to avoid mapping all zeros to all zeros); Zseby, Molina, Duffield, Niccolini, Raspall [Page 34] Internet Draft Techniques for IP Packet Selection February 2005 Note: the mix sub-function (see mix (a,b,c) macro in the reference code in 3.2.4) has a number of parameters governing the shifts in the registers. The one presented is not the only possible choice. It is an open point whether these may be considered additional built-in parameters to specify at function configuration. Output. The output of the BOB function is a 32-bit number. It should be specified: - A 32 bit mask to apply to the output - The selection range as a list of non overlapping intervals [start value, end value] where value is in [0,2^32] Functioning: The hash value is obtained computing first an initialization of an internal state (composed of 3 32-bit numbers, called a, b, c in the reference code below), then, for each input byte of the key the internal state is combined by addition and mixed using the mix sub-function. Finally, the internal state mixed one last time and the third number of the state (c) is chosen as the return value. typedef unsigned long int ub4; /* unsigned 4-byte quantities */ typedef unsigned char ub1; /* unsigned 1-byte quantities */ #define hashsize(n) ((ub4)1<<(n)) #define hashmask(n) (hashsize(n)-1) /* ------------------------------------------------------ mix -- mix 3 32-bit values reversibly. For every delta with one or two bits set, and the deltas of all three high bits or all three low bits, whether the original value of a,b,c is almost all zero or is uniformly distributed, * If mix() is run forward or backward, at least 32 bits in a,b,c have at least 1/4 probability of changing. * If mix() is run forward, every bit of c will change between 1/3 and 2/3 of the time. (Well, 22/100 and 78/100 for some 2- bit deltas.) mix() was built out of 36 single-cycle latency instructions in a structure that could supported 2x parallelism, like so: a -= b; a -= c; x = (c>>13); b -= c; a ^= x; b -= a; x = (a<<8); c -= a; b ^= x; Zseby, Molina, Duffield, Niccolini, Raspall [Page 35] Internet Draft Techniques for IP Packet Selection February 2005 c -= b; x = (b>>13); ... Unfortunately, superscalar Pentiums and Sparcs can't take advantage of that parallelism. They've also turned some of those single-cycle latency instructions into multi-cycle latency instructions ------------------------------------------------------------*/ #define mix(a,b,c) \ { \ a -= b; a -= c; a ^= (c>>13); \ b -= c; b -= a; b ^= (a<<8); \ c -= a; c -= b; c ^= (b>>13); \ a -= b; a -= c; a ^= (c>>12); \ b -= c; b -= a; b ^= (a<<16); \ c -= a; c -= b; c ^= (b>>5); \ a -= b; a -= c; a ^= (c>>3); \ b -= c; b -= a; b ^= (a<<10); \ c -= a; c -= b; c ^= (b>>15); \ } /* ----------------------------------------------------------- hash() -- hash a variable-length key into a 32-bit value k : the key (the unaligned variable-length array of bytes) len : the length of the key, counting by bytes initval : can be any 4-byte value Returns a 32-bit value. Every bit of the key affects every bit of the return value. Every 1-bit and 2-bit delta achieves avalanche. About 6*len+35 instructions. The best hash table sizes are powers of 2. There is no need to do mod a prime (mod is sooo slow!). If you need less than 32 bits, use a bitmask. For example, if you need only 10 bits, do h = (h & hashmask(10)); In which case, the hash table should have hashsize(10) elements. If you are hashing n strings (ub1 **)k, do it like this: for (i=0, h=0; i= 12) { a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24)); b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24)); c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24)); mix(a,b,c); k += 12; len -= 12; } /*---------------------------- handle the last 11 bytes */ c += length; switch(len) /* all the case statements fall through*/ { case 11: c+=((ub4)k[10]<<24); case 10: c+=((ub4)k[9]<<16); case 9 : c+=((ub4)k[8]<<8); /* the first byte of c is reserved for the length */ case 8 : b+=((ub4)k[7]<<24); case 7 : b+=((ub4)k[6]<<16); case 6 : b+=((ub4)k[5]<<8); case 5 : b+=k[4]; case 4 : a+=((ub4)k[3]<<24); case 3 : a+=((ub4)k[2]<<16); case 2 : a+=((ub4)k[1]<<8); case 1 : a+=k[0]; /* case 0: nothing left to add */ } mix(a,b,c); /*-------------------------------- report the result */ return c; } Zseby, Molina, Duffield, Niccolini, Raspall [Page 37] --------------040603020700040807080401-- -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Fri Feb 18 10:12:25 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA13219 for ; Fri, 18 Feb 2005 10:12:25 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D29go-0003k6-K4 for psamp-data@psg.com; Fri, 18 Feb 2005 15:05:06 +0000 Received: from [132.151.1.176] (helo=ietf.org) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D29gh-0003Zt-6g for psamp@ops.ietf.org; Fri, 18 Feb 2005 15:04:59 +0000 Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA11282; Fri, 18 Feb 2005 10:04:56 -0500 (EST) Message-Id: <200502181504.KAA11282@ietf.org> Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: i-d-announce@ietf.org Cc: psamp@ops.ietf.org From: Internet-Drafts@ietf.org Subject: I-D ACTION:draft-ietf-psamp-sample-tech-06.txt Date: Fri, 18 Feb 2005 10:04:56 -0500 X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=AWL,BAYES_00, MIME_BOUND_NEXTPART,NO_REAL_NAME autolearn=no version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the Packet Sampling Working Group of the IETF. Title : Sampling and Filtering Techniques for IP Packet Selection Author(s) : T. Zseby, et al. Filename : draft-ietf-psamp-sample-tech-06.txt Pages : 37 Date : 2005-2-17 This document describes Sampling and Filtering techniques for IP packet selection. It provides a categorization of schemes and defines what parameters are needed to describe the most common selection schemes. Furthermore it shows how techniques can be combined to build more elaborate packet Selectors. The document provides the basis for the definition of information models for configuring selection techniques in measurement processes and for reporting the technique in use to a Collector. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-psamp-sample-tech-06.txt To remove yourself from the I-D Announcement list, send a message to i-d-announce-request@ietf.org with the word unsubscribe in the body of the message. You can also visit https://www1.ietf.org/mailman/listinfo/I-D-announce to change your subscription settings. Internet-Drafts are also available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-psamp-sample-tech-06.txt". A list of Internet-Drafts directories can be found in http://www.ietf.org/shadow.html or ftp://ftp.ietf.org/ietf/1shadow-sites.txt Internet-Drafts can also be obtained by e-mail. Send a message to: mailserv@ietf.org. In the body type: "FILE /internet-drafts/draft-ietf-psamp-sample-tech-06.txt". NOTE: The mail server at ietf.org can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e. documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ietf.org" Content-Type: text/plain Content-ID: <2005-2-18103453.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-psamp-sample-tech-06.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-psamp-sample-tech-06.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <2005-2-18103453.I-D@ietf.org> --OtherAccess-- --NextPart-- -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Fri Feb 18 15:35:33 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA09967 for ; Fri, 18 Feb 2005 15:35:32 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D2Ejm-00033m-NH for psamp-data@psg.com; Fri, 18 Feb 2005 20:28:30 +0000 Received: from [132.151.1.176] (helo=ietf.org) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D2Ejb-000331-T0 for psamp@ops.ietf.org; Fri, 18 Feb 2005 20:28:20 +0000 Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA09055; Fri, 18 Feb 2005 15:28:16 -0500 (EST) Message-Id: <200502182028.PAA09055@ietf.org> Mime-Version: 1.0 Content-Type: Multipart/Mixed; Boundary="NextPart" To: i-d-announce@ietf.org Cc: psamp@ops.ietf.org From: Internet-Drafts@ietf.org Subject: I-D ACTION:draft-ietf-psamp-mib-04.txt Date: Fri, 18 Feb 2005 15:28:16 -0500 X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,MIME_BOUND_NEXTPART, NO_REAL_NAME autolearn=no version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk --NextPart A New Internet-Draft is available from the on-line Internet-Drafts directories. This draft is a work item of the Packet Sampling Working Group of the IETF. Title : Definitions of Managed Objects for Packet Sampling Author(s) : T. Dietz, B. Claise Filename : draft-ietf-psamp-mib-04.txt Pages : 62 Date : 2005-2-18 This memo defines managed objects for sampling and filtering techniques for IP packet selection. These objects provide information about managed nodes supporting packet sampling, including packet sampling capabilities, configuration and statistics. They also allow to configure packet sampling concerning the IP interface at which packets are sampled, the packet selections methods used for sampling, and the collector to which packet samples are exported. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-psamp-mib-04.txt To remove yourself from the I-D Announcement list, send a message to i-d-announce-request@ietf.org with the word unsubscribe in the body of the message. You can also visit https://www1.ietf.org/mailman/listinfo/I-D-announce to change your subscription settings. Internet-Drafts are also available by anonymous FTP. Login with the username "anonymous" and a password of your e-mail address. After logging in, type "cd internet-drafts" and then "get draft-ietf-psamp-mib-04.txt". A list of Internet-Drafts directories can be found in http://www.ietf.org/shadow.html or ftp://ftp.ietf.org/ietf/1shadow-sites.txt Internet-Drafts can also be obtained by e-mail. Send a message to: mailserv@ietf.org. In the body type: "FILE /internet-drafts/draft-ietf-psamp-mib-04.txt". NOTE: The mail server at ietf.org can return the document in MIME-encoded form by using the "mpack" utility. To use this feature, insert the command "ENCODING mime" before the "FILE" command. To decode the response(s), you will need "munpack" or a MIME-compliant mail reader. Different MIME-compliant mail readers exhibit different behavior, especially when dealing with "multipart" MIME messages (i.e. documents which have been split up into multiple messages), so check your local documentation on how to manipulate these messages. Below is the data which will enable a MIME compliant mail reader implementation to automatically retrieve the ASCII version of the Internet-Draft. --NextPart Content-Type: Multipart/Alternative; Boundary="OtherAccess" --OtherAccess Content-Type: Message/External-body; access-type="mail-server"; server="mailserv@ietf.org" Content-Type: text/plain Content-ID: <2005-2-18144541.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-psamp-mib-04.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-psamp-mib-04.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <2005-2-18144541.I-D@ietf.org> --OtherAccess-- --NextPart-- -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Tue Feb 22 04:34:31 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id EAA05762 for ; Tue, 22 Feb 2005 04:34:30 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D3WLl-00010H-Kp for psamp-data@psg.com; Tue, 22 Feb 2005 09:29:01 +0000 Received: from [195.37.70.21] (helo=kyoto.netlab.nec.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D3WLi-0000yl-6j for psamp@ops.ietf.org; Tue, 22 Feb 2005 09:28:58 +0000 Received: from net-61.nrpn.net (net-61.nrpn.net [192.89.6.61]) by kyoto.netlab.nec.de (Postfix) with ESMTP id E74E91BAC4D for ; Tue, 22 Feb 2005 10:28:54 +0100 (CET) Date: Tue, 22 Feb 2005 10:29:09 +0100 From: Juergen Quittek To: psamp@ops.ietf.org Subject: WG last call on Sampling and Filtering Techniques until March 12 Message-ID: X-Mailer: Mulberry/3.1.6 (Mac OS X) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Dear all, Tanja has submitted a new version of our document on Sampling and Filtering Techniques for IP Packet Selection. Please find it at . The document in mature enough for entering WG last call. The call will end on March 12. This allows us bringing up and discussing comments and issues also at our session in Minneapolis. Please read the document carefully and comment on it. PLEASE ALSO COMMENT IF YOU THINK THE DOCUMENT IS FINE. Positive feedback is as welcome as comment on technical flaws and editorial nits. There is one open technical issue left that we should continue discussing and try to close during last call. The document describes the need to support hash functions for packet selection and for packet digest. We agreed already, that for each of them one hash function should be mandatory to implement. Currently it is IPSX for packet selection and CRC32 for packet digest. However, a discussion recently started on this list considered replacing both (as mandatory to implement) by the BOB hash function. We have not reached consensus on this issue. Thanks, Juergen -- Juergen Quittek quittek@netlab.nec.de Tel: +49 6221 90511-15 NEC Europe Ltd., Network Laboratories Fax: +49 6221 90511-55 Kurfuersten-Anlage 36, 69115 Heidelberg, Germany http://www.netlab.nec.de > From: Internet-Drafts@ietf.org > To: i-d-announce@ietf.org > cc: psamp@ops.ietf.org > Subject: I-D ACTION:draft-ietf-psamp-sample-tech-06.txt > Date-Sent: Freitag, 18. Februar 2005 16:04 Uhr +0100 > > A New Internet-Draft is available from the on-line Internet-Drafts directories. > This draft is a work item of the Packet Sampling Working Group of the IETF. > > Title : Sampling and Filtering Techniques for IP Packet Selection > Author(s) : T. Zseby, et al. > Filename : draft-ietf-psamp-sample-tech-06.txt > Pages : 37 > Date : 2005-2-17 > > This document describes Sampling and Filtering techniques for IP > packet selection. It provides a categorization of schemes and > defines what parameters are needed to describe the most common > selection schemes. Furthermore it shows how techniques can be > combined to build more elaborate packet Selectors. The document > provides the basis for the definition of information models for > configuring selection techniques in measurement processes and > for reporting the technique in use to a Collector. > > A URL for this Internet-Draft is: > http://www.ietf.org/internet-drafts/draft-ietf-psamp-sample-tech-06.txt > > To remove yourself from the I-D Announcement list, send a message to > i-d-announce-request@ietf.org with the word unsubscribe in the body of the message. > You can also visit https://www1.ietf.org/mailman/listinfo/I-D-announce > to change your subscription settings. > > > Internet-Drafts are also available by anonymous FTP. Login with the username > "anonymous" and a password of your e-mail address. After logging in, > type "cd internet-drafts" and then > "get draft-ietf-psamp-sample-tech-06.txt". > > A list of Internet-Drafts directories can be found in > http://www.ietf.org/shadow.html > or ftp://ftp.ietf.org/ietf/1shadow-sites.txt > -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Wed Feb 23 05:36:40 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA00107 for ; Wed, 23 Feb 2005 05:36:39 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D3tmQ-000Lth-JK for psamp-data@psg.com; Wed, 23 Feb 2005 10:30:06 +0000 Received: from [193.174.154.14] (helo=mailhub.fokus.fraunhofer.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D3tmM-000LsW-Ri for psamp@ops.ietf.org; Wed, 23 Feb 2005 10:30:03 +0000 Received: from [195.37.78.204] (dhcp204 [195.37.78.204]) by mailhub.fokus.fraunhofer.de (8.11.6p2/8.11.6) with ESMTP id j1NATx505505; Wed, 23 Feb 2005 11:29:59 +0100 (MET) Message-ID: <421C5B26.8090900@fokus.fraunhofer.de> Date: Wed, 23 Feb 2005 11:29:58 +0100 From: Tanja Zseby User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Juergen Quittek CC: psamp@ops.ietf.org Subject: Re: WG last call on Sampling and Filtering Techniques until March 12 References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Hi Juergen, just a small comment: we agreed that it is mandatory to implement one of the described selection methods to be psamp-conformant. Regarding the hash-function we just give recommendations if someone decided to implement a hash-based selection. So to my understanding we will not have one hash-function mandatory but only recommended. Do you agree ? Regards Tanja Juergen Quittek wrote: >Dear all, > >Tanja has submitted a new version of our document on Sampling and >Filtering Techniques for IP Packet Selection. Please find it at >. > >The document in mature enough for entering WG last call. >The call will end on March 12. This allows us bringing up and >discussing comments and issues also at our session in Minneapolis. > >Please read the document carefully and comment on it. > >PLEASE ALSO COMMENT IF YOU THINK THE DOCUMENT IS FINE. >Positive feedback is as welcome as comment on technical flaws and >editorial nits. > >There is one open technical issue left that we should continue >discussing and try to close during last call. The document describes >the need to support hash functions for packet selection and for >packet digest. We agreed already, that for each of them one hash >function should be mandatory to implement. Currently it is IPSX >for packet selection and CRC32 for packet digest. > >However, a discussion recently started on this list considered >replacing both (as mandatory to implement) by the BOB hash function. >We have not reached consensus on this issue. > >Thanks, > > Juergen > > -- Dipl.-Ing. Tanja Zseby Fraunhofer Institute FOKUS Email: zseby@fokus.fraunhofer.de Kaiserin-Augusta-Allee 31 Phone: +49-30-3463-7153 D-10589 Berlin, Germany Fax: +49-30-3463-8153 -------------------------------------------------------------------------------------- "Living on earth is expensive but it includes a free trip around the sun." (Anonymous) -------------------------------------------------------------------------------------- -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Wed Feb 23 05:59:53 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA02470 for ; Wed, 23 Feb 2005 05:59:53 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D3uAs-000PEM-2b for psamp-data@psg.com; Wed, 23 Feb 2005 10:55:22 +0000 Received: from [193.63.211.19] (helo=mail.dante.org.uk) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D3uAo-000PBH-Qn for psamp@ops.ietf.org; Wed, 23 Feb 2005 10:55:18 +0000 Received: from [127.0.0.1] (helo=localhost) by mail.dante.org.uk with esmtp (Exim 4.43) id 1D3uAn-0005DY-Kk; Wed, 23 Feb 2005 10:55:17 +0000 Received: from mail.dante.org.uk ([127.0.0.1]) by localhost (alpha [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 19898-09; Wed, 23 Feb 2005 10:55:08 +0000 (GMT) Received: from [193.63.211.62] (helo=[193.63.211.62]) by mail.dante.org.uk with esmtp (Exim 4.43) id 1D3uAe-0005DR-0t; Wed, 23 Feb 2005 10:55:08 +0000 Message-ID: <421C610B.4010905@dante.org.uk> Date: Wed, 23 Feb 2005 10:55:07 +0000 From: Maurizio Molina User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.3) Gecko/20040910 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Tanja Zseby CC: Juergen Quittek , psamp@ops.ietf.org Subject: Re: WG last call on Sampling and Filtering Techniques until March 12 References: <421C5B26.8090900@fokus.fraunhofer.de> In-Reply-To: <421C5B26.8090900@fokus.fraunhofer.de> X-Enigmail-Version: 0.89.5.0 X-Enigmail-Supports: pgp-inline, pgp-mime Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: amavisd-new at dante.org.uk X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Hi Tanja, "recommended" is a rather vague term. In my view, it should be made clear that in case someone implements the hash based filtering, he MUST (or SHOULD) implement the recommended hash function. Otherwise, the whole concept of trajectory sampling, which is one of the main reason for having hash based sampling, is broken. From the discussion I saw on the ML I think a consensus on a MUST is probably difficult to reach, but at least a SHOULD should be in. Maurizio Tanja Zseby wrote: > Hi Juergen, > > just a small comment: we agreed that it is mandatory to implement one > of the described selection methods to be psamp-conformant. Regarding > the hash-function we just give recommendations if someone decided to > implement a hash-based selection. So to my understanding we will not > have one hash-function mandatory but only recommended. Do you agree ? > > Regards > Tanja > > Juergen Quittek wrote: > >> Dear all, >> >> Tanja has submitted a new version of our document on Sampling and >> Filtering Techniques for IP Packet Selection. Please find it at >> . >> >> >> The document in mature enough for entering WG last call. >> The call will end on March 12. This allows us bringing up and >> discussing comments and issues also at our session in Minneapolis. >> >> Please read the document carefully and comment on it. >> >> PLEASE ALSO COMMENT IF YOU THINK THE DOCUMENT IS FINE. >> Positive feedback is as welcome as comment on technical flaws and >> editorial nits. >> >> There is one open technical issue left that we should continue >> discussing and try to close during last call. The document describes >> the need to support hash functions for packet selection and for >> packet digest. We agreed already, that for each of them one hash >> function should be mandatory to implement. Currently it is IPSX for >> packet selection and CRC32 for packet digest. >> >> However, a discussion recently started on this list considered >> replacing both (as mandatory to implement) by the BOB hash function. >> We have not reached consensus on this issue. >> >> Thanks, >> >> Juergen >> >> > -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Wed Feb 23 06:19:13 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id GAA04786 for ; Wed, 23 Feb 2005 06:19:13 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D3uTK-0001th-Fm for psamp-data@psg.com; Wed, 23 Feb 2005 11:14:26 +0000 Received: from [193.174.154.14] (helo=mailhub.fokus.fraunhofer.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D3uTI-0001tR-68 for psamp@ops.ietf.org; Wed, 23 Feb 2005 11:14:24 +0000 Received: from [195.37.78.204] (dhcp204 [195.37.78.204]) by mailhub.fokus.fraunhofer.de (8.11.6p2/8.11.6) with ESMTP id j1NBEL513548; Wed, 23 Feb 2005 12:14:21 +0100 (MET) Message-ID: <421C658C.6040502@fokus.fraunhofer.de> Date: Wed, 23 Feb 2005 12:14:20 +0100 From: Tanja Zseby User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.7.2) Gecko/20040804 Netscape/7.2 (ax) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Maurizio Molina CC: Juergen Quittek , psamp@ops.ietf.org Subject: Re: WG last call on Sampling and Filtering Techniques until March 12 References: <421C5B26.8090900@fokus.fraunhofer.de> <421C610B.4010905@dante.org.uk> In-Reply-To: <421C610B.4010905@dante.org.uk> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Hi Maurizio, as far as I know a SHOULD in the draft means that it is recommended. So having a SHOULD there is o.k. with me. So we state that if someone decides to use a hash-based selection he SHOULD use the [to be agreed on ] function . Regards Tanja Maurizio Molina wrote: > Hi Tanja, > "recommended" is a rather vague term. > In my view, it should be made clear that in case someone implements > the hash based filtering, he MUST (or SHOULD) implement the > recommended hash function. Otherwise, the whole concept of trajectory > sampling, which is one of the main reason for having hash based > sampling, is broken. > From the discussion I saw on the ML I think a consensus on a MUST is > probably difficult to reach, but at least a SHOULD should be in. > Maurizio > Tanja Zseby wrote: > >> Hi Juergen, >> >> just a small comment: we agreed that it is mandatory to implement one >> of the described selection methods to be psamp-conformant. Regarding >> the hash-function we just give recommendations if someone decided to >> implement a hash-based selection. So to my understanding we will not >> have one hash-function mandatory but only recommended. Do you agree ? >> >> Regards >> Tanja >> >> Juergen Quittek wrote: >> >>> Dear all, >>> >>> Tanja has submitted a new version of our document on Sampling and >>> Filtering Techniques for IP Packet Selection. Please find it at >>> . >>> >>> >>> The document in mature enough for entering WG last call. >>> The call will end on March 12. This allows us bringing up and >>> discussing comments and issues also at our session in Minneapolis. >>> >>> Please read the document carefully and comment on it. >>> >>> PLEASE ALSO COMMENT IF YOU THINK THE DOCUMENT IS FINE. >>> Positive feedback is as welcome as comment on technical flaws and >>> editorial nits. >>> >>> There is one open technical issue left that we should continue >>> discussing and try to close during last call. The document >>> describes the need to support hash functions for packet selection >>> and for packet digest. We agreed already, that for each of them one >>> hash function should be mandatory to implement. Currently it is >>> IPSX for packet selection and CRC32 for packet digest. >>> >>> However, a discussion recently started on this list considered >>> replacing both (as mandatory to implement) by the BOB hash function. >>> We have not reached consensus on this issue. >>> >>> Thanks, >>> >>> Juergen >>> >>> >> > > > -- > to unsubscribe send a message to psamp-request@ops.ietf.org with > the word 'unsubscribe' in a single line as the message text body. > archive: -- Dipl.-Ing. Tanja Zseby Fraunhofer Institute FOKUS Email: zseby@fokus.fraunhofer.de Kaiserin-Augusta-Allee 31 Phone: +49-30-3463-7153 D-10589 Berlin, Germany Fax: +49-30-3463-8153 -------------------------------------------------------------------------------------- "Living on earth is expensive but it includes a free trip around the sun." (Anonymous) -------------------------------------------------------------------------------------- -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Wed Feb 23 10:31:44 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA28013 for ; Wed, 23 Feb 2005 10:31:44 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D3yMp-0006vH-89 for psamp-data@psg.com; Wed, 23 Feb 2005 15:23:59 +0000 Received: from [195.37.70.40] (helo=smtp2.netlab.nec.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D3yMl-0006us-RK for psamp@ops.ietf.org; Wed, 23 Feb 2005 15:23:56 +0000 Received: from europa.office (europa.office [10.1.1.2]) by smtp2.netlab.nec.de (Postfix) with ESMTP id 1C9E9FF2B; Wed, 23 Feb 2005 16:31:36 +0100 (CET) Received: from [10.1.1.171] ([10.1.1.171]) by europa.office over TLS secured channel with Microsoft SMTPSVC(6.0.3790.211); Wed, 23 Feb 2005 16:23:54 +0100 Date: Wed, 23 Feb 2005 16:24:09 +0100 From: Juergen Quittek To: Tanja Zseby , Maurizio Molina Cc: psamp@ops.ietf.org Subject: Re: WG last call on Sampling and Filtering Techniques until March 12 Message-ID: <5CE6EAD03C89E8ACD1060B81@[10.1.1.171]> In-Reply-To: <421C658C.6040502@fokus.fraunhofer.de> References: <421C658C.6040502@fokus.fraunhofer.de> X-Mailer: Mulberry/3.1.6 (Mac OS X) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline X-OriginalArrivalTime: 23 Feb 2005 15:23:54.0659 (UTC) FILETIME=[AFA8EF30:01C519BB] X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.5 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit RFC 2119 suggest using the following paragraph: The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. As you see, 'RECOMMENDED' is well defined and equivalent to 'SHOULD'. Juergen --On 23.02.2005 12:14 Uhr +0100 Tanja Zseby wrote: > Hi Maurizio, > > as far as I know a SHOULD in the draft means that it is recommended. So > having a SHOULD there is o.k. with me. > So we state that if someone decides to use a hash-based selection he > SHOULD use the [to be agreed on ] function . > > Regards > Tanja > > Maurizio Molina wrote: > >> Hi Tanja, >> "recommended" is a rather vague term. >> In my view, it should be made clear that in case someone implements >> the hash based filtering, he MUST (or SHOULD) implement the >> recommended hash function. Otherwise, the whole concept of trajectory >> sampling, which is one of the main reason for having hash based >> sampling, is broken. >> From the discussion I saw on the ML I think a consensus on a MUST is >> probably difficult to reach, but at least a SHOULD should be in. >> Maurizio >> Tanja Zseby wrote: >> >>> Hi Juergen, >>> >>> just a small comment: we agreed that it is mandatory to implement one >>> of the described selection methods to be psamp-conformant. Regarding >>> the hash-function we just give recommendations if someone decided to >>> implement a hash-based selection. So to my understanding we will not >>> have one hash-function mandatory but only recommended. Do you agree ? >>> >>> Regards >>> Tanja >>> >>> Juergen Quittek wrote: >>> >>>> Dear all, >>>> >>>> Tanja has submitted a new version of our document on Sampling and >>>> Filtering Techniques for IP Packet Selection. Please find it at >>>> . >>>> >>>> >>>> The document in mature enough for entering WG last call. >>>> The call will end on March 12. This allows us bringing up and >>>> discussing comments and issues also at our session in Minneapolis. >>>> >>>> Please read the document carefully and comment on it. >>>> >>>> PLEASE ALSO COMMENT IF YOU THINK THE DOCUMENT IS FINE. >>>> Positive feedback is as welcome as comment on technical flaws and >>>> editorial nits. >>>> >>>> There is one open technical issue left that we should continue >>>> discussing and try to close during last call. The document >>>> describes the need to support hash functions for packet selection >>>> and for packet digest. We agreed already, that for each of them one >>>> hash function should be mandatory to implement. Currently it is >>>> IPSX for packet selection and CRC32 for packet digest. >>>> >>>> However, a discussion recently started on this list considered >>>> replacing both (as mandatory to implement) by the BOB hash function. >>>> We have not reached consensus on this issue. >>>> >>>> Thanks, >>>> >>>> Juergen >>>> >>>> >>> >> >> >> -- >> to unsubscribe send a message to psamp-request@ops.ietf.org with >> the word 'unsubscribe' in a single line as the message text body. >> archive: > > > -- > Dipl.-Ing. Tanja Zseby > Fraunhofer Institute FOKUS Email: zseby@fokus.fraunhofer.de > Kaiserin-Augusta-Allee 31 Phone: +49-30-3463-7153 > D-10589 Berlin, Germany Fax: +49-30-3463-8153 > -------------------------------------------------------------------------------------- > "Living on earth is expensive but it includes a free trip around the sun." (Anonymous) > -------------------------------------------------------------------------------------- > -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: From owner-psamp@ops.ietf.org Thu Feb 24 11:34:35 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA12710 for ; Thu, 24 Feb 2005 11:34:34 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.44 (FreeBSD)) id 1D4Lo6-0007g5-OV for psamp-data@psg.com; Thu, 24 Feb 2005 16:25:42 +0000 Received: from [195.37.70.40] (helo=smtp2.netlab.nec.de) by psg.com with esmtp (Exim 4.44 (FreeBSD)) id 1D4Lo3-0007fW-BO for psamp@ops.ietf.org; Thu, 24 Feb 2005 16:25:39 +0000 Received: from europa.office (europa.office [10.1.1.2]) by smtp2.netlab.nec.de (Postfix) with ESMTP id A8A22D9DD for ; Thu, 24 Feb 2005 17:25:38 +0100 (CET) Received: from [10.1.1.171] ([10.1.1.171]) by europa.office over TLS secured channel with Microsoft SMTPSVC(6.0.3790.211); Thu, 24 Feb 2005 17:25:37 +0100 Date: Thu, 24 Feb 2005 17:25:54 +0100 From: Juergen Quittek To: psamp@ops.ietf.org Subject: draft agenda for Minneapolis Message-ID: <53556C9545A58677CE5D8088@[10.1.1.171]> X-Mailer: Mulberry/3.1.6 (Mac OS X) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline X-OriginalArrivalTime: 24 Feb 2005 16:25:37.0971 (UTC) FILETIME=[796B4030:01C51A8D] X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.5 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit Dear all, Below please find a draft agenda for our Minneapolis session. Any comment? Thanks, Juergen -- Juergen Quittek quittek@netlab.nec.de Tel: +49 6221 90511-15 NEC Europe Ltd., Network Laboratories Fax: +49 6221 90511-55 Kurfuersten-Anlage 36, 69115 Heidelberg, Germany http://www.netlab.nec.de ============================================= Packet Sampling WG (psamp) IETF #62 March 10, 2005: 1645-1745 ============================ Chairs: Andy Bierman Juergen Quittek AGENDA: AGENDA: 1) Agenda bashing, WG Status ( 5 min) 2) Update od Packet Selection (20 min) - Sampling and Filtering Techniques for IP Packet Selection draft-ietf-psamp-sample-tech-06.txt - WG last call ends on March 12 - main issues: what is mandatory, recommended, or optional 3) PSAMP MIB (20 min) - Definitions of Managed Objects for Packet Sampling draft-ietf-psamp-mib-04.txt - few remaining issues 4) Continuation of work on PSAMP protocol (10 min) 5) Wrap up ( 5 min) - action points - schedule for remaining documents INTERNET DRAFTS: A Framework for Passive Packet Measurement http://www.ietf.org/internet-drafts/draft-ietf-psamp-framework-10.txt Sampling and Filtering Techniques for IP Packet Selection http://www.ietf.org/internet-drafts/draft-ietf-psamp-sample-tech-06.txt Definitions of Managed Objects for Packet Sampling http://www.ietf.org/internet-drafts/draft-ietf-psamp-mib-04.txt -- to unsubscribe send a message to psamp-request@ops.ietf.org with the word 'unsubscribe' in a single line as the message text body. archive: