[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

new packet selection draft version



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)
--------------------------------------------------------------------------------------



                                                                         
 Internet Draft                                                          
 Document: <draft-ietf-psamp-sample-tech-06.txt>                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: <STREAM ID, IPFIX Metering process ID, IPFIX Exporting 
    process ID, IDs of other associated processes> 
    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) 
            - <Header type = ipv4> 
            - <Input bit specification, header part> 
            - <Header type =  ipv6> 
            - <Input bit specification, header part> 
            - <payload byte number N> 
            - <Input bit specification, payload part> 
       - 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: <STREAM ID, IPFIX Metering process ID, IPFIX Exporting 
    process ID, IDs of other associated processes> 
    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 <draft-molina-flow-selection-00.txt>, 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<n; ++i) h = hash( k[i], len[i], h);  
     
    By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may 
    use this code any way you wish, private, educational, or 
    commercial.  It's free.  
        
   See http://burtleburtle.net/bob/hash/evahash.html  
    Use for hash table lookup, or anything where one collision in 
    2^^32 is acceptable.  Do NOT use for cryptographic purposes.  
     ----------------------------------------------------------- */  
        




 Zseby, Molina, Duffield, Niccolini, Raspall              [Page 36] 
 Internet Draft  Techniques for IP Packet Selection   February 2005 



      ub4 bob_hash(k, length, initval)  
      register ub1 *k;        /* the key */  
      register ub4  length;   /* the length of the key */  
      register ub4  initval;  /* an arbitrary value */  
      {  
         register ub4 a,b,c,len;  
        
         /* Set up the internal state */  
         len = length;  
         a = b = 0x9e3779b9; /*the golden ratio; an arbitrary value 
    */ 
         c = initval;         /* another arbitrary value */  
        
    /*------------------------------------ handle most of the key */  
        
         while (len >= 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]