From owner-psamp@ops.ietf.org Wed Jan 5 15:52: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 PAA10556 for ; Wed, 5 Jan 2005 15:52:52 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1CmHyi-00041F-H8 for psamp-data@psg.com; Wed, 05 Jan 2005 20:42:00 +0000 Received: from [132.151.1.176] (helo=ietf.org) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1CmHye-0003zN-91 for psamp@ops.ietf.org; Wed, 05 Jan 2005 20:41:56 +0000 Received: from CNRI.Reston.VA.US (localhost [127.0.0.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA09852; Wed, 5 Jan 2005 15:41:52 -0500 (EST) Message-Id: <200501052041.PAA09852@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-framework-10.txt Date: Wed, 05 Jan 2005 15:41:52 -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 : A Framework for Packet Selection and Reporting Author(s) : N. Duffield Filename : draft-ietf-psamp-framework-10.txt Pages : 35 Date : 2005-1-5 This document specifies a framework for the PSAMP (Packet Sampling) protocol. The functions of this protocol are to select packets from a stream according to a set of standardized reports, form a stream of reports on the selected packets, and to export that stream to a collector. This framework details the components of this architecture, then describes some generic requirements, motivated the dual aims of ubiquitous deployment and utility of the reports for applications. Detailed requirements for selection, reporting and export are described, along with configuration of the PSAMP functions. A URL for this Internet-Draft is: http://www.ietf.org/internet-drafts/draft-ietf-psamp-framework-10.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-framework-10.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-framework-10.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-1-5153155.I-D@ietf.org> ENCODING mime FILE /internet-drafts/draft-ietf-psamp-framework-10.txt --OtherAccess Content-Type: Message/External-body; name="draft-ietf-psamp-framework-10.txt"; site="ftp.ietf.org"; access-type="anon-ftp"; directory="internet-drafts" Content-Type: text/plain Content-ID: <2005-1-5153155.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 Mon Jan 24 11:12:03 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id LAA25907 for ; Mon, 24 Jan 2005 11:12:02 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1Ct6jD-000NEP-72 for psamp-data@psg.com; Mon, 24 Jan 2005 16:06:11 +0000 Received: from [195.37.70.40] (helo=smtp0.netlab.nec.de) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1Ct6aw-000Izu-BF for psamp@psg.com; Mon, 24 Jan 2005 15:57:38 +0000 Received: from europa.office (europa.office [10.1.1.2]) by smtp0.netlab.nec.de (Postfix) with ESMTP id 3A4C722921 for ; Mon, 24 Jan 2005 16:46:05 +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: Hashing function for PSAMP Date: Mon, 24 Jan 2005 16:56:44 +0100 Message-ID: Thread-Topic: Hashing function for PSAMP Thread-Index: AcUCLU5WGly7zv8TTxC16bZYmpRTLQ== From: "Saverio Niccolini" To: X-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-1.7 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, I would like to ask a simple question to the list. As you have seen in the "Sampling and Filtering Techniques for IP Packet Selection" draft we have tried to give suggestions on which is the best hash function in order to do packet sampling. Hash Functions Suitable for Packet Selection 1. IPSX (2. BOB) Hash Functions Suitable for Packet Digesting 1. CRC-32 (2. BOB) Thinking about it and doing some additional tests it turned out that: 1) IPSX can only accepts 16 bytes as input --> it is not useful for IPv6 packets. Do we want to stay with IPSX that is 7 times faster than BOB but can not be used with IPv6 packets? What is the list feeling about this? 2) BOB is faster than CRC-32 (on software implementation) and achieves as good collision probability as CRC-32. Do we still want to recommend CRC-32 because we believe that hardware implementation of CRC-32 are already out or we just would like to promote BOB to recommended and CRC-32 as optional? I am asking this because we are going to submit a new version of the draft and we would definitely like to fix this issue. Thanks in advance for your comments, Saverio =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Dr. Saverio Niccolini Research Staff Member Network Laboratories, NEC Europe Ltd. Kurfuerstenanlage 36, D-69115 Heidelberg Tel. +49 (0)6221 90511-18 Fax: +49 (0)6221 90511-55 e-mail: saverio.niccolini@netlab.nec.de =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D -- 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 Jan 24 13:27:48 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA09150 for ; Mon, 24 Jan 2005 13:27:47 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1Ct8qd-000NBt-1t for psamp-data@psg.com; Mon, 24 Jan 2005 18:21:59 +0000 Received: from [193.63.211.19] (helo=mail.dante.org.uk) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1Ct8qZ-000N2B-GF for psamp@psg.com; Mon, 24 Jan 2005 18:21:55 +0000 Received: from [127.0.0.1] (helo=localhost) by mail.dante.org.uk with esmtp (Exim 4.43) id 1Ct8qY-0007bT-Hg; Mon, 24 Jan 2005 18:21:54 +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 29181-03; Mon, 24 Jan 2005 18:21:42 +0000 (GMT) Received: from [193.63.211.62] (helo=[193.63.211.62]) by mail.dante.org.uk with esmtp (Exim 4.43) id 1Ct8qM-0007bK-8F; Mon, 24 Jan 2005 18:21:42 +0000 Message-ID: <41F53CB6.5020200@dante.org.uk> Date: Mon, 24 Jan 2005 18:21:42 +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: Saverio Niccolini CC: psamp@psg.com Subject: Re: Hashing function for PSAMP References: In-Reply-To: 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 Saverio Niccolini wrote: >Dear all, >I would like to ask a simple question to the list. >As you have seen in the "Sampling and Filtering Techniques for IP Packet >Selection" draft we have tried to give suggestions on which is the best >hash function in order to do packet sampling. > >Hash Functions Suitable for Packet Selection >1. IPSX >(2. BOB) > >Hash Functions Suitable for Packet Digesting >1. CRC-32 >(2. BOB) > >Thinking about it and doing some additional tests it turned out that: >1) IPSX can only accepts 16 bytes as input --> it is not useful for IPv6 >packets. >Do we want to stay with IPSX that is 7 times faster than BOB but can not >be used with IPv6 packets? What is the list feeling about this? > > One thing to clarify is if IPSX cannot really be extended. by looking at its (very simple) description, 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; where f1, f2, f3 and f4 are the four 32 bit input words, my guess would be that for extending it to six 32 bit input word it would be necessary to select other two 32 bit word from the packet (say f5 and f6) and add four other shifting and XOR steps. That is: 11. v3 = f5 ^ f6; 12. h1 ^= v3 << N; 13. h1 ^= v3 >> M; ............ The point is to understand what is the rationale of the choice of the number of shift positions and their direction in steps 3 to 10. Is there is a "rule" this can be extended to other steps? Or was more or less a "random choice"? or is there any reason for which an extension should not work? I think we need Nick's opinion on that... Maurizio >2) BOB is faster than CRC-32 (on software implementation) and achieves >as good collision probability as CRC-32. >Do we still want to recommend CRC-32 because we believe that hardware >implementation of CRC-32 are already out or we just would like to >promote BOB to recommended and CRC-32 as optional? > >I am asking this because we are going to submit a new version of the >draft and we would definitely like to fix this issue. > >Thanks in advance for your comments, >Saverio > >============================================================ >Dr. Saverio Niccolini >Research Staff Member >Network Laboratories, NEC Europe Ltd. >Kurfuerstenanlage 36, D-69115 Heidelberg >Tel. +49 (0)6221 90511-18 >Fax: +49 (0)6221 90511-55 >e-mail: saverio.niccolini@netlab.nec.de >============================================================ > > >-- >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 Mon Jan 24 15:27:27 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA20614 for ; Mon, 24 Jan 2005 15:27:26 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1CtAgV-000GSO-FS for psamp-data@psg.com; Mon, 24 Jan 2005 20:19:39 +0000 Received: from [192.20.225.110] (helo=mail-white.research.att.com) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1CtAgR-000GRY-OI for psamp@psg.com; Mon, 24 Jan 2005 20:19:35 +0000 Received: from NJFPSRVEXG2KCL.research.att.com (njfpsrvexg2k2.research.att.com [135.207.21.32]) by mail-green.research.att.com (Postfix) with ESMTP id 4A1F9A7BCF; Mon, 24 Jan 2005 15:19:35 -0500 (EST) 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.0.6603.0 Subject: RE: Hashing function for PSAMP Date: Mon, 24 Jan 2005 15:19:35 -0500 Message-ID: <387B5A9BF31B5D43A2B18DD9F326B8E1915439@NJFPSRVEXG2KCL.research.att.com> Thread-Topic: Hashing function for PSAMP Thread-Index: AcUCQbFUuJFhrpzKTPaNYTnoG1hYtgADwPoA From: To: , Cc: 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,NO_REAL_NAME autolearn=no version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: quoted-printable Maurizio, > -----Original Message----- > From: owner-psamp@ops.ietf.org [mailto:owner-psamp@ops.ietf.org] On Behalf > Of Maurizio Molina > Sent: Monday, January 24, 2005 1:22 PM > To: Saverio Niccolini > Cc: psamp@psg.com > Subject: Re: Hashing function for PSAMP >=20 > Saverio Niccolini wrote: >=20 > >Dear all, > >I would like to ask a simple question to the list. > >As you have seen in the "Sampling and Filtering Techniques for IP Packet > >Selection" draft we have tried to give suggestions on which is the best > >hash function in order to do packet sampling. > > > >Hash Functions Suitable for Packet Selection > >1. IPSX > >(2. BOB) > > > >Hash Functions Suitable for Packet Digesting > >1. CRC-32 > >(2. BOB) > > > >Thinking about it and doing some additional tests it turned out that: > >1) IPSX can only accepts 16 bytes as input --> it is not useful for IPv6 > >packets. > >Do we want to stay with IPSX that is 7 times faster than BOB but can not > >be used with IPv6 packets? What is the list feeling about this? > > > > > One thing to clarify is if IPSX cannot really be extended. > by looking at its (very simple) description, >=20 > 1. v1 =3D f1 ^ f2; > 2. v2 =3D f3 ^ f4; > 3. h1 =3D v1 << 8; > 4. h1 ^=3D v1 >> 4; > 5. h1 ^=3D v1 >> 12; > 6. h1 ^=3D v1 >> 16; > 7. h1 ^=3D v2 << 6; > 8. h1 ^=3D v2 << 10; > 9. h1 ^=3D v2 << 14; > 10. h1 ^=3D v2 >> 7; >=20 > where f1, f2, f3 and f4 are the four 32 bit input words, my guess would > be that for extending it to six 32 bit input word it would be > necessary to select other two 32 bit word from the packet (say f5 and > f6) and add four other shifting and XOR steps. > That is: >=20 > 11. v3 =3D f5 ^ f6; > 12. h1 ^=3D v3 << N; > 13. h1 ^=3D v3 >> M; > ............ >=20 > The point is to understand what is the rationale of the choice of the > number of shift positions and their direction in steps 3 to 10. > Is there is a "rule" this can be extended to other steps? Or was more or > less a "random choice"? or is there any reason for which an extension > should not work? > I think we need Nick's opinion on that... The rationale was to exploit variability expected and/or found empirically in different fields in the IPv4 packet header. A number of other variants on this theme were evaluated. The final choice represented a good combination of computational simplicity, and quasi-randomness, observed in testing. It is possible to extend the form to longer inputs, along the lines that you suggest above. However, evaluation of different variants is difficult in practice. Due to the comparatively small deployment of IPv6, it is questionable whether IPv6 traces available today would be representative (in terms of the variability of their fields) of what could be expected in future. This is a problem for the evaluation of any hash. Nick >=20 > Maurizio >=20 > >2) BOB is faster than CRC-32 (on software implementation) and achieves > >as good collision probability as CRC-32. > >Do we still want to recommend CRC-32 because we believe that hardware > >implementation of CRC-32 are already out or we just would like to > >promote BOB to recommended and CRC-32 as optional? > > > >I am asking this because we are going to submit a new version of the > >draft and we would definitely like to fix this issue. > > > >Thanks in advance for your comments, > >Saverio > > > = >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > >Dr. Saverio Niccolini > >Research Staff Member > >Network Laboratories, NEC Europe Ltd. > >Kurfuerstenanlage 36, D-69115 Heidelberg > >Tel. +49 (0)6221 90511-18 > >Fax: +49 (0)6221 90511-55 > >e-mail: saverio.niccolini@netlab.nec.de > = >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > > > > >-- > >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 >=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: -- 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 Jan 25 07:07:29 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id HAA27197 for ; Tue, 25 Jan 2005 07:07:29 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1CtPLT-000Aye-S8 for psamp-data@psg.com; Tue, 25 Jan 2005 11:58:55 +0000 Received: from [193.63.211.19] (helo=mail.dante.org.uk) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1CtPLP-000Ay0-GS for psamp@psg.com; Tue, 25 Jan 2005 11:58:51 +0000 Received: from [127.0.0.1] (helo=localhost) by mail.dante.org.uk with esmtp (Exim 4.43) id 1CtPLL-0003VF-SY; Tue, 25 Jan 2005 11:58:47 +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 13389-03; Tue, 25 Jan 2005 11:58:36 +0000 (GMT) Received: from [193.63.211.62] (helo=[193.63.211.62]) by mail.dante.org.uk with esmtp (Exim 4.43) id 1CtPLA-0003VB-LD; Tue, 25 Jan 2005 11:58:36 +0000 Message-ID: <41F6346C.2060609@dante.org.uk> Date: Tue, 25 Jan 2005 11:58:36 +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: duffield@research.att.com CC: Saverio.Niccolini@netlab.nec.de, psamp@psg.com Subject: Re: Hashing function for PSAMP References: <387B5A9BF31B5D43A2B18DD9F326B8E1915439@NJFPSRVEXG2KCL.research.att.com> In-Reply-To: <387B5A9BF31B5D43A2B18DD9F326B8E1915439@NJFPSRVEXG2KCL.research.att.com> 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=AWL,BAYES_00 autolearn=ham version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: 7bit duffield@research.att.com wrote: >Maurizio, > > > >>-----Original Message----- >>From: owner-psamp@ops.ietf.org [mailto:owner-psamp@ops.ietf.org] On >> >> >Behalf > > >>Of Maurizio Molina >>Sent: Monday, January 24, 2005 1:22 PM >>To: Saverio Niccolini >>Cc: psamp@psg.com >>Subject: Re: Hashing function for PSAMP >> >>Saverio Niccolini wrote: >> >> >> >>>Dear all, >>>I would like to ask a simple question to the list. >>>As you have seen in the "Sampling and Filtering Techniques for IP >>> >>> >Packet > > >>>Selection" draft we have tried to give suggestions on which is the >>> >>> >best > > >>>hash function in order to do packet sampling. >>> >>>Hash Functions Suitable for Packet Selection >>>1. IPSX >>>(2. BOB) >>> >>>Hash Functions Suitable for Packet Digesting >>>1. CRC-32 >>>(2. BOB) >>> >>>Thinking about it and doing some additional tests it turned out that: >>>1) IPSX can only accepts 16 bytes as input --> it is not useful for >>> >>> >IPv6 > > >>>packets. >>>Do we want to stay with IPSX that is 7 times faster than BOB but can >>> >>> >not > > >>>be used with IPv6 packets? What is the list feeling about this? >>> >>> >>> >>> >>One thing to clarify is if IPSX cannot really be extended. >>by looking at its (very simple) description, >> >> 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; >> >>where f1, f2, f3 and f4 are the four 32 bit input words, my guess >> >> >would > > >>be that for extending it to six 32 bit input word it would be >>necessary to select other two 32 bit word from the packet (say f5 and >>f6) and add four other shifting and XOR steps. >>That is: >> >> 11. v3 = f5 ^ f6; >> 12. h1 ^= v3 << N; >> 13. h1 ^= v3 >> M; >> ............ >> >>The point is to understand what is the rationale of the choice of the >>number of shift positions and their direction in steps 3 to 10. >>Is there is a "rule" this can be extended to other steps? Or was more >> >> >or > > >>less a "random choice"? or is there any reason for which an extension >>should not work? >>I think we need Nick's opinion on that... >> >> > >The rationale was to exploit variability expected and/or found >empirically in different fields in the IPv4 packet header. A number of >other variants on this theme were evaluated. The final choice >represented a good combination of computational simplicity, and >quasi-randomness, observed in testing. > >It is possible to extend the form to longer inputs, along the lines that >you suggest above. However, evaluation of different variants is >difficult in practice. Due to the comparatively small deployment of >IPv6, it is questionable whether IPv6 traces available today would be >representative (in terms of the variability of their fields) of what >could be expected in future. This is a problem for the evaluation of any >hash. > > My idea, to start with, was to evaluate the "IPSX extension" on the IPv4 traces. Saverio did some tests (on traces of the of the MAWI project). His results showed that all hashes (BOB, CRC-32, IPSX, MMH) showed a poor uniformity (according to the Chi-square tests) with 16 input bytes. Moving from 16 input bytes to 20 (and then further to 24, 28, 32, etc), some of the hases (BOB, CRC-32) showed a big improvement in their uniformity behavior, while MMH didn't. For IPSX, it was only possible to test it on 16 bytes, where it showed a poor uniformity behaviour as all the other functions. If we can have an IPSX variant, we'll be at least able to understand if moving from 16 to 20 input bytes (and then possibly to 24, 28, etc...) it will improve its behaviour (like BOB and CRC-32) or not (like MMH). This will already be an interestring result for PSAMP to give a reccomendation. Maurizio >Nick > > > >>Maurizio >> >> >> >>>2) BOB is faster than CRC-32 (on software implementation) and >>> >>> >achieves > > >>>as good collision probability as CRC-32. >>>Do we still want to recommend CRC-32 because we believe that hardware >>>implementation of CRC-32 are already out or we just would like to >>>promote BOB to recommended and CRC-32 as optional? >>> >>>I am asking this because we are going to submit a new version of the >>>draft and we would definitely like to fix this issue. >>> >>>Thanks in advance for your comments, >>>Saverio >>> >>>============================================================ >>>Dr. Saverio Niccolini >>>Research Staff Member >>>Network Laboratories, NEC Europe Ltd. >>>Kurfuerstenanlage 36, D-69115 Heidelberg >>>Tel. +49 (0)6221 90511-18 >>>Fax: +49 (0)6221 90511-55 >>>e-mail: saverio.niccolini@netlab.nec.de >>>============================================================ >>> >>> >>>-- >>>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 Thu Jan 27 08:44:59 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id IAA04729 for ; Thu, 27 Jan 2005 08:44:58 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1Cu9pe-00030u-SB for psamp-data@psg.com; Thu, 27 Jan 2005 13:37:10 +0000 Received: from [195.37.70.21] (helo=kyoto.netlab.nec.de) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1Cu9pb-00030U-9s for psamp@ops.ietf.org; Thu, 27 Jan 2005 13:37:07 +0000 Received: from [10.1.1.171] (mito.netlab.nec.de [195.37.70.39]) by kyoto.netlab.nec.de (Postfix) with ESMTP id 3188B1BAC4D for ; Thu, 27 Jan 2005 14:37:06 +0100 (CET) Date: Thu, 27 Jan 2005 14:37:15 +0100 From: Juergen Quittek To: psamp@ops.ietf.org Subject: Re: Hashing function for PSAMP Message-ID: <1F29E699573152EF47921D9C@[10.1.1.171]> In-Reply-To: References: 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-Spam-Checker-Version: SpamAssassin 3.0.1 (2004-10-22) on psg.com X-Spam-Status: No, score=-2.4 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, 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 -- 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 --On 24.01.2005 16:56 Uhr +0100 Saverio Niccolini wrote: > Dear all, > I would like to ask a simple question to the list. > As you have seen in the "Sampling and Filtering Techniques for IP Packet > Selection" draft we have tried to give suggestions on which is the best > hash function in order to do packet sampling. > > Hash Functions Suitable for Packet Selection > 1. IPSX > (2. BOB) > > Hash Functions Suitable for Packet Digesting > 1. CRC-32 > (2. BOB) > > Thinking about it and doing some additional tests it turned out that: > 1) IPSX can only accepts 16 bytes as input --> it is not useful for IPv6 > packets. > Do we want to stay with IPSX that is 7 times faster than BOB but can not > be used with IPv6 packets? What is the list feeling about this? > > 2) BOB is faster than CRC-32 (on software implementation) and achieves > as good collision probability as CRC-32. > Do we still want to recommend CRC-32 because we believe that hardware > implementation of CRC-32 are already out or we just would like to > promote BOB to recommended and CRC-32 as optional? > > I am asking this because we are going to submit a new version of the > draft and we would definitely like to fix this issue. > > Thanks in advance for your comments, > Saverio > > ============================================================ > Dr. Saverio Niccolini > Research Staff Member > Network Laboratories, NEC Europe Ltd. > Kurfuerstenanlage 36, D-69115 Heidelberg > Tel. +49 (0)6221 90511-18 > Fax: +49 (0)6221 90511-55 > e-mail: saverio.niccolini@netlab.nec.de > ============================================================ > > > -- > 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 Fri Jan 28 08:48:41 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id IAA01186 for ; Fri, 28 Jan 2005 08:48:40 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1CuWOA-000HDA-Tr for psamp-data@psg.com; Fri, 28 Jan 2005 13:42:18 +0000 Received: from [171.71.176.72] (helo=sj-iport-3.cisco.com) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1CuWO7-000HCi-Oi for psamp@ops.ietf.org; Fri, 28 Jan 2005 13:42:15 +0000 Received: from sj-core-1.cisco.com (171.71.177.237) by sj-iport-3.cisco.com with ESMTP; 28 Jan 2005 06:51:35 +0000 X-BrightmailFiltered: true X-Brightmail-Tracker: AAAAAA== Received: from mira-sjc5-c.cisco.com (IDENT:mirapoint@mira-sjc5-c.cisco.com [171.71.163.17]) by sj-core-1.cisco.com (8.12.10/8.12.6) with ESMTP id j0SDgBM8020909; Fri, 28 Jan 2005 05:42:11 -0800 (PST) Received: from abierman-xp.cisco.com (sjc-vpn2-624.cisco.com [10.21.114.112]) by mira-sjc5-c.cisco.com (MOS 3.4.5-GR) with ESMTP id BDE43661; Fri, 28 Jan 2005 05:42:12 -0800 (PST) Message-Id: <4.3.2.7.2.20050128053350.020066d0@fedex.cisco.com> X-Sender: abierman@fedex.cisco.com X-Mailer: QUALCOMM Windows Eudora Version 4.3.2 Date: Fri, 28 Jan 2005 05:42:12 -0800 To: Juergen Quittek From: Andy Bierman Subject: Re: Hashing function for PSAMP Cc: psamp@ops.ietf.org In-Reply-To: <1F29E699573152EF47921D9C@[10.1.1.171]> References: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" 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 At 05:37 AM 1/27/2005, Juergen Quittek wrote: >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? I prefer (2) because we can't ignore IPv6 and we are selecting a hash algorithm for interoperability, so we really only need one of them. (Consider the extra expense for HW-assisted implementations.) >Thanks, > > Juergen Andy >-- >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 > > >--On 24.01.2005 16:56 Uhr +0100 Saverio Niccolini wrote: > >>Dear all, >>I would like to ask a simple question to the list. >>As you have seen in the "Sampling and Filtering Techniques for IP Packet >>Selection" draft we have tried to give suggestions on which is the best >>hash function in order to do packet sampling. >> >>Hash Functions Suitable for Packet Selection >>1. IPSX >>(2. BOB) >> >>Hash Functions Suitable for Packet Digesting >>1. CRC-32 >>(2. BOB) >> >>Thinking about it and doing some additional tests it turned out that: >>1) IPSX can only accepts 16 bytes as input --> it is not useful for IPv6 >>packets. >>Do we want to stay with IPSX that is 7 times faster than BOB but can not >>be used with IPv6 packets? What is the list feeling about this? >> >>2) BOB is faster than CRC-32 (on software implementation) and achieves >>as good collision probability as CRC-32. >>Do we still want to recommend CRC-32 because we believe that hardware >>implementation of CRC-32 are already out or we just would like to >>promote BOB to recommended and CRC-32 as optional? >> >>I am asking this because we are going to submit a new version of the >>draft and we would definitely like to fix this issue. >> >>Thanks in advance for your comments, >>Saverio >> >>============================================================ >>Dr. Saverio Niccolini >>Research Staff Member >>Network Laboratories, NEC Europe Ltd. >>Kurfuerstenanlage 36, D-69115 Heidelberg >>Tel. +49 (0)6221 90511-18 >>Fax: +49 (0)6221 90511-55 >>e-mail: saverio.niccolini@netlab.nec.de >>============================================================ >> >> >>-- >>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 Fri Jan 28 13:36:24 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA27784 for ; Fri, 28 Jan 2005 13:36:23 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1Cuas3-0008Wa-F6 for psamp-data@psg.com; Fri, 28 Jan 2005 18:29:27 +0000 Received: from [192.20.225.110] (helo=mail-white.research.att.com) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1Cuas0-0008WH-UA for psamp@ops.ietf.org; Fri, 28 Jan 2005 18:29:25 +0000 Received: from NJFPSRVEXG2KCL.research.att.com (njfpsrvexg2k2.research.att.com [135.207.21.32]) by mail-green.research.att.com (Postfix) with ESMTP id 3F9A4A7BD5; Fri, 28 Jan 2005 13:29:24 -0500 (EST) 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.0.6603.0 Subject: RE: Hashing function for PSAMP Date: Fri, 28 Jan 2005 13:29:23 -0500 Message-ID: <387B5A9BF31B5D43A2B18DD9F326B8E191543B@NJFPSRVEXG2KCL.research.att.com> Thread-Topic: Hashing function for PSAMP Thread-Index: AcUFP277bKgKH/fJSSmyIk9IkpE82gAG64uA From: To: , Cc: 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,NO_REAL_NAME autolearn=no version=3.0.1 Sender: owner-psamp@ops.ietf.org Precedence: bulk Content-Transfer-Encoding: quoted-printable Andy, Note that distinct hashes are required for selection and digesting. This could be achieved using a single parameterizable hash function, i.e., using different parameters to get different hashes. Both CRC32 and BOB have initial vectors that could be used for this purpose.=20 Any choice of initial vectors should be evaluated to determine whether they work (i.e. produce two sufficiently random and mutually independent hashes). Users will want to be able to set and change these parameters, and keep them private in order to keep prevent subversion of the hash. Is there any need to standardize the parameters? Perhaps it is useful to recommend one pair of parameters that works (in the above sense). 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?=20 It seems there is still some benefit to having IPSX available for selection. (i) IPSX is fast so could more easily be used by psamp devices with lower computational abilities.=20 (ii) IPSX is independent of the other hash functions under consideration (BOB and CRC32)=20 (iii) IPSX is very simple, so there is not much more overhead it making it available;=20 (iv) IPSX could be simply extended to take input for IPv6 (either more input, or just a different 16 bytes). Or if we already have one IPv6 capable selection hash function standardized (say BOB), does any additional standardized hash function also need to be IPv6 capable, or is IPv4 sufficient? Nick > -----Original Message----- > From: owner-psamp@ops.ietf.org [mailto:owner-psamp@ops.ietf.org] On Behalf > Of Andy Bierman > Sent: Friday, January 28, 2005 8:42 AM > To: Juergen Quittek > Cc: psamp@ops.ietf.org > Subject: Re: Hashing function for PSAMP >=20 > At 05:37 AM 1/27/2005, Juergen Quittek wrote: > >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? >=20 > I prefer (2) because we can't ignore IPv6 and we are selecting > a hash algorithm for interoperability, so we really only need > one of them. (Consider the extra expense for HW-assisted > implementations.) >=20 >=20 > >Thanks, > > > > Juergen >=20 > Andy >=20 >=20 > >-- > >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 > > > > > >--On 24.01.2005 16:56 Uhr +0100 Saverio Niccolini wrote: > > > >>Dear all, > >>I would like to ask a simple question to the list. > >>As you have seen in the "Sampling and Filtering Techniques for IP Packet > >>Selection" draft we have tried to give suggestions on which is the best > >>hash function in order to do packet sampling. > >> > >>Hash Functions Suitable for Packet Selection > >>1. IPSX > >>(2. BOB) > >> > >>Hash Functions Suitable for Packet Digesting > >>1. CRC-32 > >>(2. BOB) > >> > >>Thinking about it and doing some additional tests it turned out that: > >>1) IPSX can only accepts 16 bytes as input --> it is not useful for IPv6 > >>packets. > >>Do we want to stay with IPSX that is 7 times faster than BOB but can not > >>be used with IPv6 packets? What is the list feeling about this? > >> > >>2) BOB is faster than CRC-32 (on software implementation) and achieves > >>as good collision probability as CRC-32. > >>Do we still want to recommend CRC-32 because we believe that hardware > >>implementation of CRC-32 are already out or we just would like to > >>promote BOB to recommended and CRC-32 as optional? > >> > >>I am asking this because we are going to submit a new version of the > >>draft and we would definitely like to fix this issue. > >> > >>Thanks in advance for your comments, > >>Saverio > >> > = >>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > >>Dr. Saverio Niccolini > >>Research Staff Member > >>Network Laboratories, NEC Europe Ltd. > >>Kurfuerstenanlage 36, D-69115 Heidelberg > >>Tel. +49 (0)6221 90511-18 > >>Fax: +49 (0)6221 90511-55 > >>e-mail: saverio.niccolini@netlab.nec.de > = >>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > >> > >> > >>-- > >>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: >=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: -- 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 Jan 28 13:46:49 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA28731 for ; Fri, 28 Jan 2005 13:46:48 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1Cub4c-000AAd-7h for psamp-data@psg.com; Fri, 28 Jan 2005 18:42:26 +0000 Received: from [171.71.176.72] (helo=sj-iport-3.cisco.com) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1Cub3p-000A23-Jd for psamp@ops.ietf.org; Fri, 28 Jan 2005 18:41:37 +0000 Received: from sj-core-5.cisco.com (171.71.177.238) by sj-iport-3.cisco.com with ESMTP; 28 Jan 2005 11:51:01 +0000 X-BrightmailFiltered: true X-Brightmail-Tracker: AAAAAA== Received: from mira-sjc5-c.cisco.com (IDENT:mirapoint@mira-sjc5-c.cisco.com [171.71.163.17]) by sj-core-5.cisco.com (8.12.10/8.12.6) with ESMTP id j0SIfYNt005083; Fri, 28 Jan 2005 10:41:34 -0800 (PST) Received: from abierman-xp.cisco.com (sjc-vpn2-624.cisco.com [10.21.114.112]) by mira-sjc5-c.cisco.com (MOS 3.4.5-GR) with ESMTP id BDE68900; Fri, 28 Jan 2005 10:41:33 -0800 (PST) Message-Id: <4.3.2.7.2.20050128103540.021cef08@fedex.cisco.com> X-Sender: abierman@fedex.cisco.com X-Mailer: QUALCOMM Windows Eudora Version 4.3.2 Date: Fri, 28 Jan 2005 10:41:33 -0800 To: From: Andy Bierman Subject: RE: Hashing function for PSAMP Cc: , In-Reply-To: <387B5A9BF31B5D43A2B18DD9F326B8E191543B@NJFPSRVEXG2KCL.rese arch.att.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" 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 At 10:29 AM 1/28/2005, duffield@research.att.com wrote: >Andy, I'm not suggesting that we remove any hash functions from the spec. All but one can be SHOULD or MAY implement, and one can be MUST implement. If that needs to be different for selection and digesting then that's fine. I don't believe that it has been demonstrated that IPSX is vital to PSAMP, such that it should be a MUST requirement. (MAY is okay). I don't think that SW-based speed improvement for IPv4 is a good enough reason to make this mandatory for all implementations. Andy >Note that distinct hashes are required for selection and digesting. This >could be achieved using a single parameterizable hash function, i.e., >using different parameters to get different hashes. Both CRC32 and BOB >have initial vectors that could be used for this purpose. > >Any choice of initial vectors should be evaluated to determine whether >they work (i.e. produce two sufficiently random and mutually independent >hashes). Users will want to be able to set and change these parameters, >and keep them private in order to keep prevent subversion of the hash. >Is there any need to standardize the parameters? Perhaps it is useful to >recommend one pair of parameters that works (in the above sense). > >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? > >It seems there is still some benefit to having IPSX available for >selection. > >(i) IPSX is fast so could more easily be used by psamp devices with >lower computational abilities. > >(ii) IPSX is independent of the other hash functions under consideration >(BOB and CRC32) > >(iii) IPSX is very simple, so there is not much more overhead it making >it available; > >(iv) IPSX could be simply extended to take input for IPv6 (either more >input, or just a different 16 bytes). Or if we already have one IPv6 >capable selection hash function standardized (say BOB), does any >additional standardized hash function also need to be IPv6 capable, or >is IPv4 sufficient? > > >Nick > > >> -----Original Message----- >> From: owner-psamp@ops.ietf.org [mailto:owner-psamp@ops.ietf.org] On >Behalf >> Of Andy Bierman >> Sent: Friday, January 28, 2005 8:42 AM >> To: Juergen Quittek >> Cc: psamp@ops.ietf.org >> Subject: Re: Hashing function for PSAMP >> >> At 05:37 AM 1/27/2005, Juergen Quittek wrote: >> >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? >> >> I prefer (2) because we can't ignore IPv6 and we are selecting >> a hash algorithm for interoperability, so we really only need >> one of them. (Consider the extra expense for HW-assisted >> implementations.) >> >> >> >Thanks, >> > >> > Juergen >> >> Andy >> >> >> >-- >> >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 >> > >> > >> >--On 24.01.2005 16:56 Uhr +0100 Saverio Niccolini wrote: >> > >> >>Dear all, >> >>I would like to ask a simple question to the list. >> >>As you have seen in the "Sampling and Filtering Techniques for IP >Packet >> >>Selection" draft we have tried to give suggestions on which is the >best >> >>hash function in order to do packet sampling. >> >> >> >>Hash Functions Suitable for Packet Selection >> >>1. IPSX >> >>(2. BOB) >> >> >> >>Hash Functions Suitable for Packet Digesting >> >>1. CRC-32 >> >>(2. BOB) >> >> >> >>Thinking about it and doing some additional tests it turned out >that: >> >>1) IPSX can only accepts 16 bytes as input --> it is not useful for >IPv6 >> >>packets. >> >>Do we want to stay with IPSX that is 7 times faster than BOB but can >not >> >>be used with IPv6 packets? What is the list feeling about this? >> >> >> >>2) BOB is faster than CRC-32 (on software implementation) and >achieves >> >>as good collision probability as CRC-32. >> >>Do we still want to recommend CRC-32 because we believe that >hardware >> >>implementation of CRC-32 are already out or we just would like to >> >>promote BOB to recommended and CRC-32 as optional? >> >> >> >>I am asking this because we are going to submit a new version of the >> >>draft and we would definitely like to fix this issue. >> >> >> >>Thanks in advance for your comments, >> >>Saverio >> >> >> >>============================================================ >> >>Dr. Saverio Niccolini >> >>Research Staff Member >> >>Network Laboratories, NEC Europe Ltd. >> >>Kurfuerstenanlage 36, D-69115 Heidelberg >> >>Tel. +49 (0)6221 90511-18 >> >>Fax: +49 (0)6221 90511-55 >> >>e-mail: saverio.niccolini@netlab.nec.de >> >>============================================================ >> >> >> >> >> >>-- >> >>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 Mon Jan 31 10:47:47 2005 Received: from psg.com (mailnull@psg.com [147.28.0.62]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id KAA14228 for ; Mon, 31 Jan 2005 10:47:46 -0500 (EST) Received: from majordom by psg.com with local (Exim 4.43 (FreeBSD)) id 1CvdgE-0001bR-SG for psamp-data@psg.com; Mon, 31 Jan 2005 15:41:34 +0000 Received: from [144.254.224.140] (helo=ams-iport-1.cisco.com) by psg.com with esmtp (Exim 4.43 (FreeBSD)) id 1CvdgD-0001bE-Qo for psamp@ops.ietf.org; Mon, 31 Jan 2005 15:41:33 +0000 Received: from ams-core-1.cisco.com (144.254.224.150) by ams-iport-1.cisco.com with ESMTP; 31 Jan 2005 16:51:09 +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 j0VFfSPm005248; Mon, 31 Jan 2005 16:41:28 +0100 (MET) Received: from cisco.com (ams-clip-vpn-dhcp4344.cisco.com [10.61.80.247]) by cisco.com (8.8.8-Cisco List Logging/8.8.8) with ESMTP id PAA18926; Mon, 31 Jan 2005 15:41:24 GMT Message-ID: <41FE51A4.2090902@cisco.com> Date: Mon, 31 Jan 2005 15:41:24 +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: duffield@research.att.com CC: abierman@cisco.com, quittek@netlab.nec.de, psamp@ops.ietf.org Subject: Re: Hashing function for PSAMP References: <387B5A9BF31B5D43A2B18DD9F326B8E191543B@NJFPSRVEXG2KCL.research.att.com> In-Reply-To: <387B5A9BF31B5D43A2B18DD9F326B8E191543B@NJFPSRVEXG2KCL.research.att.com> 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 > 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: