RFC 5475
Sampling and Filtering Techniques for IP Packet Selection
🎀 Part 1 of 9 (more coming, bestie!)
Sampling and Filtering Techniques for IP Packet Selection ✨
Okay so the tea first 🫖. This is RFC 5475, a Standards Track document from the Network Working Group, dated March 2009. It was written by T. Zseby (Fraunhofer FOKUS), M. Molina (DANTE), N. Duffield (AT&T Labs - Research), S. Niccolini (NEC Europe Ltd.), and F. Raspall (EPSC-UPC) 👩💻. The title block doesn't list anything it obsoletes or updates, so no drama there 💅.
Status of This Memo 📜
This document specifies an Internet standards track protocol for the Internet community, and asks for discussion and suggestions for improvements. Check the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited 🌸.
Copyright Notice ©️
Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved 🔒.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents, as they stand on the date this document was published (http://trustee.ietf.org/license-info). Please read these carefully, because they spell out your rights and restrictions for this document 🧾.
This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The people who control the copyright in some of that material may not have given the IETF Trust permission to allow changes to it outside the IETF Standards Process. Unless you get a proper license from whoever controls the copyright in those materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be made outside the IETF Standards Process. The one exceptions are formatting it for publication as an RFC, or translating it into languages other than English 🌈.
Abstract 🦋
This document describes Sampling and Filtering techniques for IP packet selection. It sorts the schemes into categories and defines the parameters needed to describe the most common selection schemes. It also shows how the techniques can be combined to build fancier packet Selectors. The document lays the groundwork for information models that configure selection techniques in Metering Processes and report which technique is in use to a Collector 🧠.
Table of Contents 🗂️
1. Introduction ....................................................3
1.1. Conventions Used in This Document ..........................4
2. PSAMP Documents Overview ........................................4
3. Terminology .....................................................4
3.1. Observation Points, Packet Streams, and Packet Content .....4
3.2. Selection Process ..........................................5
3.3. Reporting ..................................................7
3.4. Metering Process ...........................................7
3.5. Exporting Process ..........................................8
3.6. PSAMP Device ...............................................8
3.7. Collector ..................................................8
3.8. Selection Methods ..........................................8
4. Categorization of Packet Selection Techniques ..................11
5. Sampling .......................................................12
5.1. Systematic Sampling .......................................13
5.2. Random Sampling ...........................................14
5.2.1. n-out-of-N Sampling ................................14
5.2.2. Probabilistic Sampling .............................14
6. Filtering ......................................................16
6.1. Property Match Filtering ..................................16
6.2. Hash-Based Filtering ......................................19
6.2.1. Application Examples for Coordinated Packet
Selection ..........................................19
6.2.2. Desired Properties of Hash Functions ...............21
6.2.3. Security Considerations for Hash Functions .........22
6.2.4. Choice of Hash Function ............................26
7. Parameters for the Description of Selection Techniques .........29
7.1. Description of Sampling Techniques ........................30
7.2. Description of Filtering Techniques .......................31
8. Composite Techniques ...........................................34
8.1. Cascaded Filtering->Sampling or Sampling->Filtering .......34
8.2. Stratified Sampling .......................................34
9. Security Considerations ........................................35
10. Contributors ..................................................36
11. Acknowledgments ...............................................36
12. References ....................................................36
12.1. Normative References .....................................36
12.2. Informative References ...................................36
Appendix A. Hash Functions ........................................40
A.1 IP Shift-XOR (IPSX) Hash Function..............................40
A.2 BOB Hash Function..............................................411. Introduction 🚀
Okay so there are two big reasons measurement infrastructure keeps getting bigger 📈. First, network data rates keep climbing, and that means more and more measurement data. Second, apps that rely on measurements want increasingly fine-grained traffic info, so the demand just keeps stacking up 😩. The devices doing the measuring need more sophisticated, resource-hungry abilities too, like capturing packet headers or even bits of the payload, and classifying traffic for flow analysis. Put all that together and you get an overwhelming amount of data, which means heavy demands on resources for measurement, storage, transfer, and post-processing 💀.
Capturing traffic at line rate is totally doable with specialized measurement hardware. But the cost of that hardware, plus the measurement infrastructure needed to handle it, means it can't be the everywhere solution 💸. So some kind of data reduction at the point of measurement is necessary 🧹.
That can be done with intelligent packet selection through Sampling or Filtering 🧠. Aggregation is another way to shrink the data, but this document doesn't cover it. Sampling is all about picking a representative subset of packets so you can make accurate estimates about the unsampled traffic. Filtering is about removing every packet that isn't of interest. Aggregation combines data for compact, pre-defined views of the traffic 🖼️. Examples of apps that benefit from packet selection are in [RFC5474]. Aggregation techniques are out of scope for this document 🙅.
1.1. Conventions Used in This Document 📝
Here's the key-word rule: the words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119] 🤓.
2. PSAMP Documents Overview 🎀
This document is one out of a whole series of documents from the PSAMP group 💖.
- [RFC5474]: "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 🖥️.
- RFC 5475 (this document): "Sampling and Filtering Techniques for IP Packet Selection" describes the set of packet selection techniques supported by PSAMP 🦋.
- [RFC5476]: "Packet Sampling (PSAMP) Protocol Specifications" specifies the export of packet information from a PSAMP Exporting Process to a PSAMP Collecting Process 📤.
- [RFC5477]: "Information Model for Packet Sampling Exports" defines an information and data model for PSAMP 🧩.
3. Terminology 💅
The PSAMP terminology defined here is fully consistent with all terms listed in [RFC5474], but it adds extra terms needed to describe packet selection methods. An architecture overview and possible configurations of PSAMP elements can be found in [RFC5474]. PSAMP terminology also aims to stay consistent with terms used in [RFC3917]. The relationship between PSAMP and IPFIX terms is described in [RFC5474] 🔗.
In the PSAMP documents, all defined PSAMP terms are written capitalized, and this document follows the same convention ✨.
3.1. Observation Points, Packet Streams, and Packet Content 👀
- Observation Point
An Observation Point [RFC5101] 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. That 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
A Packet Stream denotes a set of packets from the Observed Packet Stream that flows past some specified point within the Metering Process. An example of a Packet Stream is the output of the selection process. Note that packets selected from a stream, e.g., by Sampling, do not necessarily have a property that tells them apart from packets that weren't selected. For this reason, the term "stream" is favored over "flow", which is defined as a set of packets with common properties [RFC3917] 🌊.
- 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. At some Observation Points, the link header information may not be available 🎁.
3.2. Selection Process 💖
okay so the Selection Process is the main character here 👑 it takes the Observed Packet Stream as its input and picks out a subset of that stream as its output. slay 💅
- Selection State 🧠 A Selection Process may maintain state information for use by the Selection 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 🎯 A Selector defines what kind of action a Selection Process performs 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 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.
- Selection Sequence 🦋 From all the packets observed at an Observation Point, only a few packets are selected by one or more Selectors. The Selection Sequence is a unique value per Observation Domain describing the Observation Point and the Selector IDs through which the packets are selected. ngl this is so specific it's giving detective 🔍
3.3. Reporting 📝
- Packet Reports 📦 Packet Reports comprise a configurable subset of a packet's input to the Selection Process, including the Packet's Content, information relating to its treatment (for example, 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.
- Report Stream 🌊 The Report Stream is the output of a Metering Process, comprising two distinguished types of information: Packet Reports and Report Interpretation.
3.4. Metering Process 📊
A Metering Process selects packets from the Observed Packet Stream using a Selection Process, and produces as output a Report Stream concerning the selected packets. 🎀
The PSAMP Metering Process can be viewed as analogous to the IPFIX Metering Process [RFC5101], which produces Flow Records as its output, with the difference that the PSAMP Metering Process always contains a Selection Process. The relationship between PSAMP and IPFIX is further described in [RFC5477] and [RFC5474]. it's like the cousin relationship but make it protocol 🫶
3.5. Exporting Process 📤
- Exporting Process 🚀 An Exporting Process sends, in the form of Export Packets, the output of one or more Metering Processes to one or more Collectors.
- Export Packet 🎁 An Export Packet is a combination of Report Interpretations and/or one or more Packet Reports that are bundled by the Exporting Process into an 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 Metering Process (which includes a Selection Process), and an Exporting Process. Typically, corresponding Observation Point(s), Metering Process(es), and Exporting Process(es) are colocated at this device, for example, at a router. so the router is doing all the work bestie 🙈
3.7. Collector 🗂️
- Collector 🧺 A Collector receives a Report Stream exported by one or more Exporting Processes. In some cases, the host of the Metering 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. Two examples are:
- (i) Property Match Filtering: A packet is selected if a specific field in the packet equals a predefined value.
- (ii) Hash-based Selection: A Hash Function is applied to the Packet Content, and the packet is selected if the result falls in a specified range.
- 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. Sampling operations can be divided into two subtypes:
- (i) Content-independent Sampling, which does not use Packet Content in reaching Sampling decisions. 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.
- (ii) Content-dependent Sampling, in which the Packet Content is used in reaching selection decisions. An application is pseudorandom selection according to a probability that depends on the contents of a packet field, e.g., Sampling packets with a probability dependent on their TCP/UDP port numbers. Note that this is not a Filter.
- Hash Domain 🧮 A Hash Domain is a subset of the Packet Content and the packet treatment, viewed as an N-bit string for some positive integer N.
- Hash Range 🎨 A Hash Range is a set of M-bit strings for some positive integer M that defines the range of values that the result of the hash operation can take.
- Hash Function 🪄 A Hash Function defines a deterministic mapping from the Hash Domain into the Hash Range.
- Hash Selection Range 🎯 A Hash Selection Range is 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 💅 A Hash-based Selection is Filtering specified by a Hash Domain, a Hash Function, a 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 Sample Size is a number of packets selected from the Population by a Selector.
- Configured Selection Fraction 📐 The Configured Selection Fraction is the expected ratio of the Sample Size to the Population Size, as based on the configured selection parameters.
- Attained Selection Fraction 🏆 The Attained Selection Fraction is the ratio of the actual Sample Size 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. the math is mathing 🥹
4. Categorization of Packet Selection Techniques ✨
Okay bestie, packet selection techniques basically pull a subset of packets out of an Observed Packet Stream at an Observation Point 🦋. We sort them into two big buckets: Sampling and Filtering 💖.
Sampling is all about grabbing a representative slice 🍓 so you can learn things about the whole pile without processing every single packet ✨. The pick can depend on packet position, on Packet Content, on (pseudo) random decisions, or on a mix of those 🎲.
Filtering selects a subset with common properties 🔥. You use it when only some packets are actually the ones you care about 💅. Those properties can come straight from Packet Content, or from the treatment the router gives the packet 👑. Filtering is a deterministic operation, so it depends on Packet Content or router treatment, and it never depends on packet position or on (pseudo) random decisions 🙈.
Here's a fun one 🌈. A common move is to run a Hash Function on some bits of the packet header and/or content, then select the packet if the hash value lands inside the Hash Selection Range. Hashing is deterministic on the Packet Content, so in our categorization it counts as a Filtering technique 💜. Still, Hash Functions are sometimes used to emulate random Sampling 🎀. Depending on which input bits you pick, the Hash Function, and the Hash Selection Range, you can emulate randomly selecting packets with a given probability p 🧚. It's also a seriously powerful way to consistently select the same packet subset at multiple Observation Points [DuGr00] 😭✨.
The table below gives you the overview of the schemes in this document and how they're categorized 📋. An X means the characteristic applies to that selection scheme. (X) means the scheme has both content-dependent and content-independent variants 🦋. For example, Property Match Filtering is usually based on Packet Content, so it's content dependent 💅. But as Section 6.1 explains, it can also depend on router state, and then it's independent of the content 🌸. Basically, only schemes that are both content dependent and deterministic get to be called 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 | | |
------------------------+---------------+----------+----------
Property Match | X | (X) | Filtering
Filtering | | |
------------------------+---------------+----------+----------
Hash function | X | X | Filtering
------------------------+---------------+----------+----------This categorization is mainly useful for defining an information model that describes Primitive Selectors 🧠✨. More complex selection techniques can be described by composing cascaded Sampling and Filtering operations 🔥. For example, a selection that weights the selection probability based on the packet length can be described as a cascade of a Filtering scheme and a Sampling scheme 💖. But this approach isn't meant to be rigid 🌈. If a common, well-established selection practice turns out to be too complex to describe as a composition of these building blocks, an ad hoc description can be specified instead and added as a new scheme to the information model 🫶.
5. Sampling 🌸
Sampling exists so you can get information about one specific characteristic of the parent Population without paying the cost of a full census 💅. So if you want a good Sampling strategy, you need to figure out the type of information you need and how accurate it has to be before you start 🎀.
First up, you need to know which type of metric you want to estimate 🧁. The metric can be anything from simple packet counts [JePP92] all the way up to estimating whole distributions of flow characteristics, like packet sizes [ClPB93] 📊.
Second, the required accuracy of the information, and with it the confidence you're aiming for, should be known in advance 👑. For usage-based accounting, for example, the confidence you need for estimating packet counters can depend on the monetary value of transferring one packet 💰. That means a higher confidence might be needed for expensive packet flows (like premium IP service) than for cheaper flows (like best effort) 💅. Accuracy requirements for validating a previously agreed quality can also vary a LOT depending on what customers want 😭. These requirements are usually set 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 that knowledge can you make sure the measurement results are interpreted correctly 🔍.
Sampling methods can be described by three things: the Sampling algorithm, the trigger type that starts a Sampling interval, and how long the Sampling interval is 🦋. We go through these in detail here 💖. The Sampling algorithm is the basic process for selecting samples 🎲. Following [AmCa89] and [ClPB93], we define the basic Sampling processes below 🌈.
5.1. Systematic Sampling 🍓
Systematic Sampling means selecting the start points and durations of the selection intervals according to a deterministic function 🧚. That could be something like periodically selecting every k-th element of a trace, or selecting all packets that arrive at predefined points in time ⏰. Even if the selection doesn't follow a periodic function (say the time between Sampling intervals changes over time), it still counts as systematic Sampling as long as the selection is deterministic 💜.
Systematic Sampling always carries the risk of biasing the results 🙈. If the systematics in the Sampling process look like the systematics in the observed stochastic process (how often the characteristic of interest shows up in the network), the estimate is very likely to be biased 😬. And those systematics in the observed process might not be known in advance 🤷♀️.
Here we only consider equally spaced schemes, where the Sampling triggers are periodic, either in time or in packet count 🔁. Every packet that occurs in a selection interval (whether that interval is measured in time or packet count) past the trigger gets selected ✨.
Systematic count-based: In systematic count-based Sampling, the start and stop triggers for the Sampling interval are defined by spatial packet position (packet count) 🔢.
Systematic time-based: In systematic time-based Sampling, time-based start and stop triggers define the Sampling intervals ⏱️. Every packet that arrives at the Observation Point within those intervals gets selected, meaning its arrival time is larger than the start time and smaller than the stop time 🦋.
Both of these are content-independent selection schemes 💅. Content-dependent deterministic Selectors are categorized as Filters instead 🌸.
5.2. Random Sampling 🎲
Random Sampling picks the starting points of the Sampling intervals using a random process 🎰. Each element selection is an independent experiment, which is how you can get unbiased estimations 💖. Unlike systematic Sampling, random Sampling needs random numbers to be generated 🔮. There are two methods of random Sampling: n-out-of-N Sampling and probabilistic Sampling 👑.
5.2.1. n-out-of-N Sampling 🧮
In n-out-of-N Sampling, you select n elements out of the parent Population, which has N elements 🍰. For example, you could generate n different random numbers in the range [1,N] and select every packet whose packet position equals one of those random numbers 🎯. For this kind of Sampling, the Sample Size n is fixed 🔒.
5.2.2. Probabilistic Sampling 🪙
In probabilistic Sampling, you decide whether to select an element based on a predefined selection probability 🎯. Picture flipping a coin for each packet and selecting every packet where the coin lands on heads 🪙✨. For this kind of Sampling, the Sample Size can differ between trials 🌈. The selection probability doesn't have to be the same for each packet 💅. That's why we split it into two kinds: uniform probabilistic Sampling (same selection probability for every packet) and non-uniform probabilistic Sampling (where the selection probability can vary from packet to packet) 🦋.
5.2.2.1. Uniform Probabilistic Sampling 🎀
For Uniform Probabilistic Sampling, packets are selected independently, each with a uniform probability p 🌸. This can be count-driven, and it's sometimes called geometric random Sampling 🧁. That's because the difference in count between successive selected packets is an independent random variable with a geometric distribution of mean 1/p 🤓. A time-driven analog is exponential random Sampling, where the time between triggers is exponentially distributed ⏳💜.
Both geometric and exponential random Sampling are examples of additive random Sampling 🫶. That's defined as Sampling where the intervals or counts between successive samples are independent, identically distributed random variables 💖.
5.2.2.2. Non-Uniform Probabilistic Sampling 🌈
This is a variant of Probabilistic Sampling where the Sampling probabilities can depend on the selection process input 🎛️. You can use it to weight the probabilities so you're more likely to sample packets that are rare but considered important, like giving them a little boost 🚀⭐. Unbiased estimators for quantitative statistics can be recovered by re-normalizing the sample values; see [HT52] 🧠✨.
5.2.2.3. Non-Uniform Flow State Dependent Sampling ✨
okay bestie, this one is a bop 💅 Another kind of Sampling that counts as probabilistic Non-Uniform is super tied to the flow concept from [RFC3917], and it's only used together with a flow monitoring function (the IPFIX Metering Process) 🦋. Packets get picked based on a Selection State. The big twist is that the Selection State depends on the state of the flow the packet belongs to, and/or the state of the other flows the flow monitoring function is currently watching 👀. An example is the "sample and hold" method from [EsVa01]:
- If a packet accounts for a Flow Record that already exists in the IPFIX flow recording process, it's selected (so the Flow Record gets updated) 💖
- If a packet doesn't account for any existing Flow Record, it's selected with probability p. If it got selected, a new Flow Record has to be created ✨
Another algorithm that fits in the non-uniform flow state dependent Sampling category is described in [Moli03] 🌸
This type of Sampling is content dependent, because figuring out which flow a packet belongs to means analyzing part of the Packet Content 🙈. If the packet is selected, it gets passed as an input to the IPFIX monitoring function (this is called "Local Export" in [RFC5474]). Selecting packets based on the state of a flow cache is super handy when the flow monitoring function's memory is scarce (aka there's no room to keep all the flows that were scheduled for monitoring) 💀.
5.2.2.4. Configuration of Non-Uniform Probabilistic and Flow State Sampling 🎀
Lots of different specific methods get grouped under the terms non-uniform probabilistic and flow state Sampling 🧚. Depending on the Sampling goal and the implemented scheme, a different number and type of input parameters are required to configure one.
Some concrete proposals exist from the research community (e.g., [EsVa01], [DuLT01], [Moli03]). Some of these are still in an early stage and need further investigation to prove their usefulness and applicability. It's not our aim to indicate a preference among these methods 🙅. Instead, we only describe the basic methods here and leave the specification of explicit schemes and their parameters up to vendors (e.g., as an 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 suggests, 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's position in time or in space, or on a random process.
We identify and describe two Filtering techniques in the following 🫶.
6.1. Property Match Filtering 🌈
With this Filtering method, a packet is selected if specific fields within the packet and/or properties of the router state equal a predefined value. Possible filter fields are all IPFIX flow attributes specified in [RFC5102]. More fields can be defined by proposing new information elements or defining vendor-specific extensions.
A packet is selected if Field=Value. Masks and ranges are only supported to the extent to which [RFC5102] allows them, e.g., by providing explicit fields like the netmasks for source and destination addresses.
AND operations are possible by concatenating filters, which makes a composite selection operation 🔥. The ordering here is implicitly defined (outer filters come after inner filters). As long as the concatenation is only on filters, the result of the cascaded filter doesn't depend on the order, but the order may matter for implementation purposes, since the first filter has to work at a higher rate. Either way, an implementation isn't constrained to respect the filter ordering as long as the result is the same, and it may even implement the composite Filtering in one single step ✨.
OR operations are not supported with this basic model. More sophisticated filters (e.g., supporting bitmasks, ranges, or OR operations) can be realized as vendor-specific schemes.
All IPFIX flow attributes defined in [RFC5102] can be used for Property Match Filtering. Further information elements can be easily defined. Property match operations should be available for different protocol portions of the packet header:
- (i) IP header (excluding options in IPv4, stacked headers in IPv6)
- (ii) transport protocol header (e.g., TCP, UDP)
- (iii) encapsulation headers (e.g., the MPLS label stack, if present)
When the PSAMP Device offers Property Match Filtering, and, in its usual capacity other than in performing PSAMP functions, identifies or processes information from IP, transport protocol or encapsulation protocols, then the information should be made available for Filtering 💖. For example, when a PSAMP Device routes based on destination IP address, that field should be made available for Filtering. Conversely, a PSAMP Device that does not route is not expected to be able to locate an IP address within a packet, or make it available for Filtering, although it may do so 🤷.
Since packet encryption conceals the real values of encrypted fields, Property Match Filtering must be configurable to ignore encrypted packets, when detected 🔒.
The Selection Process may support Filtering based on the properties of the router state:
- (i) Ingress interface at which a packet arrives equals a specified value
- (ii) Egress interface to which a packet is routed to equals a specified value
- (iii) Packet violated Access Control List (ACL) on the router
- (iv) Failed Reverse Path Forwarding (RPF)
- (v) Failed Resource Reservation Protocol (RSVP)
- (vi) No route found for the packet
- (vii) Origin Border Gateway Protocol (BGP) Autonomous System (AS) [RFC4271] equals a specified value or lies within a given range
- (viii) Destination BGP AS equals a specified value or lies within a given range
Packets that match the failed Reverse Path Forwarding (RPF) condition are packets for which ingress Filtering failed as defined in [RFC3704].
Packets that match the failed Resource Reservation Protocol (RSVP) condition are packets that do not fulfill the RSVP specification as defined in [RFC2205].
Router architectural considerations may preclude some information concerning the packet treatment being available at line rate for selection of packets. For example, the Selection Process may not be implemented in the fast path that is able to access router state at line rate. However, when Filtering follows Sampling (or some other selection operation) in a Composite Selector, the rate of the Packet Stream output from the sampler and input to the filter may be sufficiently slow that the filter could select based on router state 🐢.
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 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 extremely complex, and hence h would not be expressible as, say, a Property Match Filter or a simple combination of these.
Hash-based Selection is mainly used to realize a coordinated packet selection. That means the same packets are selected at different Observation Points. This is useful, for instance, to observe the path (trajectory) that a packet took through the network, or to apply packet selection to passive one-way measurements 🛤️.
A prerequisite for the method to work and to ensure interoperability is that the same Hash Function with the same parameters (e.g., input vector) is used at the Observation Points.
A consistent packet selection is also possible with Property Match Filtering. Nevertheless, Hash-based Selection can be used to approximate a random selection. The desired statistical properties are discussed in Section 6.2.2.
In the following subsections, we give some application examples for coordinated packet selection.
6.2.1. Application Examples for Coordinated Packet Selection 🌸
6.2.1.1. Trajectory Sampling 🌀
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 [RFC1624], 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 quasi-randomly 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 Observation Points are associated by matching a label from the reports. The label may comprise that portion of the 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 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 [DuGr00], [DuGG02], 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, and 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
6.2.1.2. Passive One-Way Measurements 🦋
okay so coordinated packet selection can be used for things like one-way delay measurements, and it saves a ton of resources 💅. With one-way delay measurements, packets get collected at different Observation Points in the network. For every packet, a packet digest is generated so you can tell which packet is which 🔍. The packet digest and the packet's arrival time at the Observation Point get reported to a process that works out the delay. The delay is calculated by subtracting the arrival time of the same packet at the Observation Points (e.g., [ZsZC01]). ngl, at high data rates, capturing every single packet eats up a lot of storage, transfer and processing 😭. To cut that down, packet selection methods can be applied. But with any selection technique, it has to be ensured that the same packets get collected at different Observation Points. That's exactly what Hash-based Selection gives you ✨.
6.2.1.3. Generation of Pseudorandom Numbers 🎲
Pseudorandom number generators with well-understood properties do exist 🧠, but they may not be the move when computational resources are scarce. A convenient alternative is to use Hash Functions of Packet Content as a source of randomness. The hash (suitably re-normalized) is a pseudorandom variate in the interval [0,1]. Other schemes may use packet fields in iterators for pseudorandom numbers. However, an implementation may only approximately render the statistical properties of an ideal packet selection law (such as independent Sampling for different packets, or independence on Packet Content), rather than exactly 🙃.
Using Packet Content to generate pseudorandom variates shares with non-uniform probabilistic Sampling (see Section 5.2.2.2 above) the property that selection decisions depend on Packet Content. However, there's 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.2. Desired Properties of Hash Functions 🔮
Here we lay out the properties we want Hash Functions to have. First, we have to figure out whether a Hash Function is being used for packet selection or just as a packet digest 🤔. The main focus of this document is packet selection, but we also give some requirements for using Hash Functions as packet digests.
First things first, we need to define suitable input fields from the packet. Following [DuGr00], an input field should be:
- invariant on the path
- variable among packets
Only if the input fields are the same at different Observation Points is it possible to recognize the packet. The input fields should be variable among packets so the hash results get spread over the selection range 🌈.
6.2.2.1. Requirements for Packet Selection 🎯
Building on considerations in [MoND05] and [Henk08], here are the desired properties of Hash Functions used for packet selection:
- (i) Speed: The Hash Function has to be applied to each packet that traverses the Observation Point. Therefore, it has to be fast in order to cope with the high packet rates. In the ideal case, the hash operation should not influence the performance on the PSAMP Device.
- (ii) Uniformity: The Hash Function
hshould 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 ofcis spread widely overRbyh, and so the distribution ofh(c)is fairly uniform even if the distribution ofcis not. Then the Attained Selection Fraction gets close to the Configured Selection Fraction (#S/#R), which can be tuned by choice ofS. - (iii) Unbiasedness: The selection decision should be as independent of packet attributes as possible. The set of selected packets should not be biased towards a specific type of packets.
- (iv) Representativeness of sample: The sample should be as representative as possible for the observed traffic.
- (v) Non-linearity: The function should not be linear. This increases the mixing properties (uniformity criterion). In addition to this, it decreases the predictability of the output and therefore the vulnerabilities against attacks.
- (vi) Robustness against vulnerabilities: The Hash Function should be robust against attacks. Potential vulnerabilities are described in Section 6.2.3.
6.2.2.2. Requirements 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, so you can include the maximal amount of packet as input 💯. Execution speed is of secondary importance, since the digest only needs to be formed from selected packets.
6.2.3. Security Considerations for Hash Functions 🔐
A big concern with Hash-based Selection is whether some large set of related packets could get disproportionately sampled, i.e., the Attained Selection Fraction ends up significantly different from the Configured Selection Fraction 😱. This can happen 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 is why good mixing properties in the Hash Function matter so much 🫶. The statistical properties of candidate Hash Functions need to be evaluated. Since the hash output depends on the traffic mix, the evaluation should preferably be done on up-to-date packet traces from the network where the Hash-based Selection will be deployed.
However, Hash Functions that perform well on typical traffic may not be strong enough to withstand attacks specifically targeted against them. Such potential attacks have been described in [GoRe07].
In the following subsections, we point out different potential attack scenarios. We encourage the use of standardized Hash Functions. Therefore, we assume that the Hash Function itself is public and hence known to an attacker.
Nevertheless, we also assume the possibility of using a private input parameter for the Hash Function that is kept secret. Such an input parameter can, for instance, be attached to the hash input before the hash operation is applied. With this, at least parts of the hash operation remain secret 🤫.
For the attack scenarios, we assume that an attacker uses its knowledge of the Hash Function to craft packets that are then dispatched, either as the attack itself or to elicit further information that can be used to refine the attack.
Two scenarios are considered. In the first scenario, the attacker has no knowledge about whether or not the crafted packets are selected. In the second scenario, the attacker uses some knowledge of Sampling outcomes. The means by which this might be acquired is discussed below. Some additional attacks that involve tampering with Export Packets in transit, as opposed to attacking the PSAMP Device, are discussed in [GoRe07].
6.2.3.1. Vulnerabilities of Hash-Based Selection without Knowledge of Selection Outcomes 🕵️
- (i) The Hash Function does not use a private parameter.
If no private input parameter is used, potential attackers can easily calculate which packets result in which hash values. If the selection range is public, an attacker can craft packets whose selection properties are known in advance. If the selection range is private, an attacker cannot determine whether a crafted packet is selected. However, by computing the hash on different trial crafted packets, and selecting those yielding a given hash value, the attacker can construct an arbitrarily large set of distinct packets with a common selection properties, i.e., packets that will be either all selected or all not selected. This can be done whatever the strength of the Hash Function. 🚨
- (ii) The Hash Function is not cryptographically strong.
If the Hash Function is not cryptographically strong, it may be possible to construct sequences of distinct packets with the common selection property even if a private parameter is used.
An example is the standard CRC-32 Hash Function used with a private modulus (but without a private string post-pended to the input). It has weak mixing properties for low-order bits. Consequently, simply by incrementing the hash input, one obtains distinct packets whose hashes mostly fall in a narrow range, and hence are likely commonly selected; see [GoRe07] 💀.
Suitable parameterization of the Hash Function can make such attacks more difficult. For example, post-pending a private string to the input before hashing with CRC-32 will give stronger mixing properties over all bits of the input. However, with a Hash Function, such as CRC-32, that is not cryptographically strong, the possibility of discovering a method to construct packet sets with the common selected property cannot be ruled out, even when a private modulus or post-pended string is used.
6.2.3.2. Vulnerabilities of Hash-Based Selection Using Knowledge of Selection Outcomes 🕵️♀️
okay so bestie, if an attacker knows what happened to the packets they crafted, they can build packet sets that get sampled way more than they should, or get picked over and over. ngl that's scary 😭 and the attacker doesn't even need to know the Hash Function or the selection range beforehand 💀
There are a few ways an attacker can figure out those selection outcomes:
- (i) Billing Reports: if samples get used for billing, someone can match up a crafted Packet Stream with the billing reports it creates and work out which packets got selected. The catch is that it goes slower the more aggregated the reports are, because it depends on how fine the reports are in time and space. 🧾
- (ii) Feedback from an Intrusion Detection System: e.g., a botmaster adversary finds out whether their packets got flagged by the intrusion detection system just by seeing if one of their bots gets blocked by the network. 🤖🚫
- (iii) Observation of the Report Stream: Export Packets sent across a public network can be eavesdropped on by an adversary. Encrypting them only helps a little 🙃 because someone might still infer the selection outcomes by matching a crafted Packet Stream with the occurrence (not the content) of packets in the export stream it makes. How fast that knowledge can be gathered depends on how precisely reports can be linked to packets, e.g., because of processing and propagation variability, and because it's hard to tell reports about attack packets apart from background traffic, if there is any. The link between packets and their reports, which all of this depends on, could be broken by padding Export Packets to a constant length and sending them at a constant rate. ✨
Now let's get into the attacks that can use knowledge of selection outcomes 👀. First, with a non-cryptographic Hash Function, knowing the selection outcomes for a trial stream can help someone craft a packet set with the common selection property. This has been shown for the modular hash f(x) = a x + b mod k, with private parameters a, b, and k. With Sampling rate p, knowing the Sampling outcomes of roughly 2/p packets is enough for the attack to work, no matter what the values of a, b, and k are. If you know the selection outcomes of even more packets, you can work out a, b, and k too (see [GoRe07]). That's a whole mood 😤
A cryptographic Hash Function that uses a private parameter and runs in one of the pseudorandom function modes described above is not vulnerable to these attacks, even if the selection range is known. 🔐💅
6.2.3.3. Vulnerabilities to Replay Attacks 🔁
Hash-based Selection is deterministic, which means that any packet or set of packets with known selection properties can be replayed into a network and get the exact same selection outcomes, as long as the Hash Function and its parameters don't change. 😬 Replaying one single packet over and over might be noticed by other measurement methods, if they're used (e.g., collecting flow statistics). A set of distinct packets that looks statistically similar to regular traffic, though, is a lot less noticeable. 🫣
Replay attacks can be softened by changing the Hash Function parameters on repeat. That also stops attacks that rely on knowing Sampling outcomes, at least if the parameters change at least as fast as an attacker can gather that knowledge. ⏱️ To keep trajectory Sampling working, though, the parameter change would have to happen simultaneously (or close to it) across all Observation Points. 🎯
6.2.4. Choice of Hash Function 🧮
Picking a Hash Function is a trade-off between complexity and ease of implementation. Ideally, you'd use a cryptographically strong Hash Function that uses a private parameter and runs in pseudorandom function mode as specified above. That gives a good emulation of random packet selection at a target Sampling rate, and maximal robustness against the attacks from the previous section 🏆. Unfortunately, there's no single Hash Function out there that fulfills all the requirements 😩.
As detailed in Section 6.2.3, only cryptographic Hash Functions that use a private parameter and operate in pseudorandom function mode are strong enough to withstand the whole range of conceivable attacks. For example, fixed- or variable-length inputs could be hashed using a block cipher (like Advanced Encryption Standard (AES)) in cipher-block-chaining mode. Fixed-length inputs could also be hashed using an iterated cryptographic Hash Function (like MD5 or SHA1), with a private initial vector. For variable-length inputs, an iterated cryptographic Hash Function (like MD5 or SHA1) should employ a private string post-pended to the data, in addition to a private initial vector. For more details, check out the "append-cascade" construction of [BeCK96]. We really encourage using cryptographically strong Hash Functions wherever possible 💖.
BUT, there's a catch: these functions have low performance 😭. As shown for instance in [Henk08], the computation times for MD5 and SHA are about 7-10 times higher compared to non-cryptographic functions. The difference gets bigger for small hash input lengths. 🐢
So it's not assumed that all PSAMP Devices will be able to apply a cryptographically strong Hash Function to every packet at line rate. That's why the Hash Functions listed in this section are of a weaker variety. Future protocol extensions that use stronger Hash Functions are highly welcome 🌈✨.
Comparisons of Hash Functions for packet selection and packet digesting, across various criteria, can be found in [MoND05] and [Henk08] 📚.
6.2.4.1. Hash Functions for Packet Selection 🎯
If Hash-based packet Selection is applied, the BOB function MUST be used for packet selection operations in order to be compliant with PSAMP. 🫶 The specification of BOB is given in the appendix. Both the parameter (the init value) and the selection range should be kept private. The initial vector of the Hash Function MUST be configurable out of band, to prevent security breaches like exposure of the initial vector content 🔒.
Other functions, such as CRC-32 and IPSX, MAY be used. The IPSX function is described in the appendix, and the CRC-32 function is described in [RFC1141]. If CRC-32 is used, the input should first be post-pended with a private string that acts as a parameter, and the modulus of the CRC should also be kept private 🤫.
IPSX is simple to implement, and it was about an order of magnitude faster to execute per packet than BOB or CRC-32 [MoND05] ⚡.
All three Hash Functions that were evaluated showed relatively poor uniformity with 16-byte input drawn only from invariant fields in the IP and TCP/UDP headers (i.e., header fields that don't change from hop to hop) 😬. IPSX is inherently limited to 16 bytes.
BOB and CRC-32 show noticeably better uniformity when 4 or more bytes from the payload are also included in the input [MoND05]. BOB also performed quite well with other criteria [Henk08] 👑.
Although the characteristics have been checked for different traffic traces, the results can't be generalized to arbitrary traffic. Since Hash-based Selection is a deterministic function on the Packet Content, it can always be biased towards packets with specific attributes. Also, note that all Hash Functions were evaluated only for IPv4 🙈.
None of these Hash Functions is recommended for cryptographic purposes. Please also note that using a private parameter only slightly reduces the vulnerabilities to attacks. As shown in Section 6.2.3, functions that aren't cryptographically strong (e.g., BOB and CRC) can't stop attackers from crafting packets that get disproportionally selected, even when a private parameter is used and the selection range is kept secret 💀.
As described in Section 6.2.2, the input bytes for the Hash Function need to be invariant along the path the packet travels. Only then is it ensured that the same packets get selected at different Observation Points 🎯. They should also have high variability between different packets, so there's a high variation in the Hash Range. An evaluation of the variability of different packet header fields can be found in [DuGr00], [HeSZ08], and [Henk08] 📊.
If a Hash-based Selection with the BOB function is used with IPv4 traffic, the following input bytes MUST be used:
- IP identification field
- Flags field
- Fragment offset
- Source IP address
- Destination IP address
- A configurable number of bytes from the IP payload, starting at a configurable offset
Heads up, bestie: because of the lack of suitable IPv6 packet traces, all candidate Hash Functions in [DuGr00], [MoND05], and [Henk08] were evaluated only for IPv4. Due to the IPv6 header fields and address structure, it's expected that there's less randomness in IPv6 packet headers than in IPv4 headers. Still, the randomness of IPv6 traffic hasn't been evaluated enough to have any evidence yet. On top of that, IPv6 traffic profiles may change a lot in the future, once IPv6 is used by a broader community 🌸.
If a Hash-based Selection with the BOB function is used with IPv6 traffic, the following input bytes MUST be used:
- Payload length (2 bytes)
- Byte number 10,11,14,15,16 of the IPv6 source address
- Byte number 10,11,14,15,16 of the IPv6 destination address
- A configurable number of bytes from the IP payload, starting at a configurable offset. It is recommended to use at least 4 bytes from the IP payload.
The payload itself doesn't change during the path. Even if some routers process some extension headers, they aren't going to strip them from the packet, so the payload length is invariant along the path. 🧠 Plus, it usually differs between different packets. The IPv6 address has 16 bytes. The first part is the network part and has low variation. The second part is the host part and has higher variation, so the second part of the address is used. Still, the uniformity hasn't been checked for IPv6 traffic 🫠.
6.2.4.2. Hash Functions Suitable for Packet Digesting 🧪
For this purpose, the BOB function SHOULD be used too. Other functions (such as CRC-32) MAY be used. Among the functions that can work with variable-length input, BOB and CRC-32 are the fastest to execute, with BOB being slightly faster ⚡. IPSX is not recommended for digesting, because it has a significantly higher collision rate and only takes a fixed-length input 🙅♀️.
7. Parameters for the Description of Selection Techniques ✨
okay so this section gives you an overview of the different selection schemes and the parameters each one needs 🧚 to be PSAMP compliant, at least one of the proposed schemes MUST be implemented, so no skipping!! 💅
The decision on whether to select a packet happens through a function that runs when the packet shows up at the selection process 🦋 Packet selection schemes are different from each other in their input parameters and in the functions they need to make the call. Here's the lowkey cheat sheet:
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.
---------------+------------------------+-------------------
property | Packet Content(parts) | filter function or
match | or router state | state discovery
---------------+------------------------+-------------------
hash-based | Packet Content(parts) | Hash Function
---------------+------------------------+-------------------7.1. Description of Sampling Techniques 🎀
this part is about the stuff you need to describe the most common Sampling techniques 💖 Here the selection function is already predefined and is given by the Selector ID, so you don't have to build it yourself.
Sampler Description:
SELECTOR_ID
SELECTOR_TYPE
SELECTOR_PARAMETERSWhere:
SELECTOR_ID: a unique ID for the packet sampler ✨
SELECTOR_TYPE: for Sampling processes, this defines which Sampling algorithm is being used 👑 The allowed values are Systematic count-based, Systematic time-based, Random, n-out-of-N, uniform probabilistic, Non-uniform probabilistic, and Non-uniform flow state.
SELECTOR_PARAMETERS: for Sampling processes, these hold the input parameters for the process 🌸 In systematic Sampling, the interval length means that every packet arriving in that interval gets selected. The spacing parameter is the gap, measured in time or in number of packets, between the end of one Sampling interval and the start of the next one.
Here's what each case needs:
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 Sampling is not defined in this document (see also Section 5.2.2.4)
7.2. Description of Filtering Techniques 🦋
now for the Filtering techniques 🫶 This part is set up a lot like the Sampling one, so if you get one you basically get both.
Filter Description:
SELECTOR_ID
SELECTOR_TYPE
SELECTOR_PARAMETERSWhere:
SELECTOR_ID: a unique ID for the packet filter ✨ The ID can be worked out from the SELECTION SEQUENCE plus a local ID.
SELECTOR_TYPE: for Filtering processes, this tells you which Filtering type is used 💅 The allowed values are Matching, Hashing, and Router_state.
SELECTOR_PARAMETERS: for Filtering processes, these formally define the common property of the packet being filtered 🌈 Matching and hashing filters have a lot of stuff in common, so the definitions overlap a lot.
Here are the values:
Case matching:
If you've got more than one match criterion, you bind multiple "case matching" entries together with 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 are dependent on specific Hash
Function (e.g., hash input bits (seed))Notes to input bits for case hashing:
- Input bits can come from the header part only, the payload part only, or both 🍓
- The bit specification for the header part can be given for IPv4 only, IPv6 only, or both.
- For IPv4, the bit specification is a sequence of 20 hexadecimal numbers in the range
[00,FF], which gives you a 20-byte bitmask to apply to the header. - For IPv6, it's a sequence of 40 hexadecimal numbers in the range
[00,FF], which gives you a 40-byte bitmask to apply to the header. - The bit specification for the payload part is a sequence of hexadecimal numbers in the range
[00,FF], which is the bitmask applied to the first N bytes of the payload, as set by the previous field. If the hexadecimal sequence is longer than N, only the first N numbers count. - If 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, and it can't be defined on stacked headers of IPv6 either 💀
- The Hash Selection Range defines a range of hash values, out of all the possible results of the hash operation ✨ If the hash result for a packet falls inside this range, the packet is selected. If it's outside the range, the packet is not selected. For example, if the selection interval specification is
[1:3], [6:9], then all packets whose hash result is 1, 2, 3, 6, 7, 8, or 9 are selected. 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 is 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 👑
8. Composite Techniques 🌸
composite schemes happen when you combine Selector IDs into a Selection Sequence 🧚 The Selection Sequence has every Selector ID that gets applied to the Packet Stream, one after another. Some examples of composite schemes are listed below.
8.1. Cascaded Filtering->Sampling or Sampling->Filtering 💖
if a filter comes before a Sampling process, the filter's job is to split one stream into a set of "parent populations" 🦋 Each of those can then be fed separately into different Sampling functions, with different parameters tuned for that specific Population. (For example, if the Filtering produces streams with different intensities, it may be good to use different Sampling rates.) If Filtering comes after a Sampling process, the same Selection Fraction and type get applied to the whole stream, no matter how big the streams coming out of the Filtering function are. Also, packets that the Filtering operation wouldn't select still "load" the Sampling function 🙈 So, in principle, Filtering before Sampling lets you tune the Sampling procedure more accurately. But if the filters are too complex to run at full line rate (for example, because they have to access router state information), Sampling before Filtering may be a need 😭
8.2. Stratified Sampling 🎀
Stratified Sampling is one example of a composite technique 💅 The basic idea is to boost the estimation accuracy by using a priori information about how the characteristic you're studying correlates with some other characteristic that's easier to get. That a priori information is used to do an intelligent grouping of the elements in the parent Population. This way, you can get higher estimation accuracy with the same sample size, or you can shrink the sample size without losing estimation accuracy ✨
Stratified Sampling splits the Sampling process into multiple steps 🫶 First, the elements of the parent Population get grouped into subsets according 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 (the stratification variable) and the characteristic you actually want an estimate for, the easier the consecutive Sampling process gets, and the higher the stratification gain is 🔥 For instance, if the dividing characteristic were equal to the investigated characteristic, each element of a subgroup would be a perfect representative of that characteristic. In that case, you'd only need to take one arbitrary element out of each subgroup to get the actual distribution of the characteristic in the parent Population. So stratified Sampling can cut the costs of the Sampling process, meaning the number of samples needed to hit a given level of confidence 🌈
For stratified Sampling, you have to specify classification rules for grouping the elements into subgroups, plus the Sampling scheme used within those 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. Stratified Sampling methods for measurement purposes are described, for instance, in [ClPB93] and [Zseb03] 💜
9. Security Considerations ✨
okay bestie, this part is serious but we're still gonna talk about it 💅 Hash-based selection security got covered back in Section 6.2.3. That section walked through a bunch of ways someone could craft Packet Streams so they get picked way more (or way less) than they should, or figure out the Hash Function parameters. It also compared how different Hash Functions hold up against those attacks, and what you can do to make the risk smaller 🛡️
and ngl, there's more. A user can learn when the start and stop triggers in time-based systematic Sampling happen, for example by sending test packets 👀 Once they know that, they could tweak their send schedule so their packets get selected a lot or skipped a lot. See [GoRe07].
For random Sampling, you should use a cryptographically strong random number generator 🔐 That way nobody can predict the selection decision. See [GoRe07].
Also, more threats can show up when Sampling parameters get configured or communicated to other entities. The configuration and reporting of Sampling parameters are out of scope for this doc, so this document can't tell you anything about threats that come from that kind of communication 🙈
Some of those threats can probably be handled by keeping configuration info confidential and by authenticating the entities that configure Sampling 🫶 Still, if anyone proposes configuration or reporting methods, a full analysis and assessment of the threats has to be done.
10. Contributors 🎀
Sharon Goldberg helped out with the security considerations for Hash-based Selection, and she's literally the reason that part is as solid as it is 👑
Sharon Goldberg
Department of Electrical Engineering
Princeton University
F210-K EQuad
Princeton, NJ 08544,
USA
EMail: goldbe@princeton.edu11. Acknowledgments 🌸
Huge thank-yous to the PSAMP group, especially Benoit Claise and Stewart Bryant 🦋 They had super fruitful discussions and proofread the whole document. We also thank Sharon Goldberg for her input on security issues concerning Hash-based Selection 💜
12. References 📚
12.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.12.2. 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.
[BeCK96] M. Bellare, R. Canetti and H. Krawczyk, "Pseudorandom
Functions Revisited: The Cascade Construction and its
Concrete Security", Symposium on Foundations of Computer
Science, 1996.
[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.
[DuGG02] N.G. Duffield, A. Gerber, M. Grossglauser, "Trajectory
Engine: A Backend for Trajectory 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.
[GoRe07] S. Goldberg, J. Rexford, "Security Vulnerabilities and
Solutions for Packet Sampling", IEEE Sarnoff Symposium,
Princeton, NJ, May 2007.
[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.
[Henk08] Christian Henke, Evaluation of Hash Functions for
Multipoint Sampling in IP Networks, Diploma Thesis, TU
Berlin, April 2008.
[HeSZ08] Christian Henke, Carsten Schmoll, Tanja Zseby, Evaluation
of Header Field Entropy for Hash-Based Packet Selection,
Proceedings of Passive and Active Measurement Conference
PAM 2008, Cleveland, Ohio, USA, April 2008.
[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.
[Moli03] M. Molina, "A scalable and efficient methodology for flow
monitoring in the Internet", International Teletraffic
Congress (ITC-18), Berlin, Sep. 2003.
[MoND05] M. Molina, S. Niccolini, N.G. Duffield, "A Comparative
Experimental Study of Hash Functions Applied to Packet
Sampling", International Teletraffic Congress (ITC-19),
Beijing, August 2005.
[RFC1141] Mallory, T. and A. Kullberg, "Incremental updating of the
Internet checksum", RFC 1141, January 1990.
[RFC1624] Rijsinghani, A., Ed., "Computation of the Internet
Checksum via Incremental Update", RFC 1624, May 1994.
[RFC2205] Braden, R., Ed., Zhang, L., Berson, S., Herzog, S., and S.
Jamin, "Resource ReSerVation Protocol (RSVP) -- Version 1
Functional Specification", RFC 2205, September 1997.
[RFC3704] Baker, F. and P. Savola, "Ingress Filtering for Multihomed
Networks", BCP 84, RFC 3704, March 2004.
[RFC3917] Quittek, J., Zseby, T., Claise, B., and S. Zander,
"Requirements for IP Flow Information Export (IPFIX)", RFC
3917, October 2004.
[RFC4271] Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A
Border Gateway Protocol 4 (BGP-4)", RFC 4271, January
2006.
[RFC5101] Claise, B., Ed., "Specification of the IP Flow Information
Export (IPFIX) Protocol for the Exchange of IP Traffic
Flow Information", RFC 5101, January 2008.
[RFC5102] Quittek, J., Bryant, S., Claise, B., Aitken, P., and J.
Meyer, "Information Model for IP Flow Information Export",
RFC 5102, January 2008.
[RFC5474] Duffield, N., Ed., "A Framework for Packet Selection and
Reporting", RFC 5474, March 2009.
[RFC5476] Claise, B., Ed., "Packet Sampling (PSAMP) Protocol
Specifications", RFC 5476, March 2009.
[RFC5477] Dietz, T., Claise, B., Aitken, P., Dressler, F., and G.
Carle, "Information Model for Packet Sampling Exports",
RFC 5477, March 2009.
[Zseb03] T. Zseby, "Stratification Strategies for Sampling-based
Non-intrusive Measurement of One-way Delay", Proceedings
of Passive and Active Measurement Workshop (PAM 2003), La
Jolla, CA, USA, pp. 171-179, April 2003.
[ZsZC01] Tanja Zseby, Sebastian Zander, Georg Carle. Evaluation of
Building Blocks for Passive One-way-delay Measurements.
Proceedings of Passive and Active Measurement Workshop
(PAM 2001), Amsterdam, The Netherlands, April 23-24, 2001.Appendix A. Hash Functions 🧚
A.1. IP Shift-XOR (IPSX) Hash Function 🍓
The IPSX Hash Function is tailor-made for IP version 4 packets 💖 It takes advantage of the structure of IP packets, especially how much different fields are expected to vary, so it can produce a hash value with little apparent correlation to any individual packet field ✨ It takes fields from the IPv4 and TCP/UDP headers as input, and it only uses a small number of simple instructions. So cute and efficient 🦋
- Input parameters: None
- Built-in parameters: None
- Output: The output of the IPSX is a 16-bit number
- Functioning: It works in two parts. First comes input selection, where the composite input is built from different portions of the IP packet. Then the hash gets computed on that composite.
Input Selection 🎀
The raw input comes from the first 20 bytes of the IP packet header and the first 8 bytes of the IP payload. If IP options aren't used, the IP header is 20 bytes long, so the two portions sit right next to each other and make up the first 28 bytes of the IP packet. We then treat the raw input as four 32-bit subportions of those 28 bytes, and we specify them using bit offsets from the start of the IP header or payload 🫶
f1 = bits 32 to 63 of the IP header, comprising the IP identification
field, flags, and fragment offset.
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 using a mix of XOR (^), right shift (>>), and left shift (<<) operations 💅 The intermediate quantities h1, v1, and 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 👑
A.2. BOB Hash Function ✨
okay so the BOB Hash Function is a Hash Function built so that every bit of the input affects every bit of the return value 🔥. It uses both 1-bit and 2-bit deltas to get the so-called avalanche effect [Jenk97]. It was originally made for hash table lookup with fast software implementation 💅.
Input parameters:
- the length of the input string (key) to be hashed, in bytes. The elementary input blocks of BOB hash are the single bytes, so 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) 🌈
Note: The mix sub-function (see mix (a,b,c) macro in the reference code below) 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:
Okay this part is the main character moment 👑. The hash value is computed by first initializing an internal state (made of three 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 gets mixed one last time, and the third number of the state (c) is chosen as the return value ✨.
Here is the typedef and macro setup, plus the mix code:
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 three 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 support 2x parallelism,
like so:
a -= b;
a -= c; x = (c>>13);
b -= c; a ^= x;
b -= a; x = (a<<8);
c -= a; b ^= x;
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); \
}And now the big one, the hash function itself 🧚:
/* -----------------------------------------------------------
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 so 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.
----------------------------------------------------------- */
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;
}Authors' Addresses 🫶
Tanja Zseby 💖 is at Fraunhofer Institute for Open Communication Systems. You can find her here:
Tanja Zseby
Fraunhofer Institute for Open Communication Systems
Kaiserin-Augusta-Allee 31
10589 Berlin
Germany
Phone: +49-30-34 63 7153
EMail: tanja.zseby@fokus.fraunhofer.deMaurizio Molina 💜 is at DANTE:
Maurizio Molina
DANTE
City House
126-130 Hills Road
Cambridge CB21PQ
United Kingdom
Phone: +44 1223 371 300
EMail: maurizio.molina@dante.org.ukNick Duffield 🦋 is at AT&T Labs - Research:
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.comSaverio Niccolini 🌸 is at Network Laboratories, NEC Europe Ltd.:
Saverio Niccolini
Network Laboratories, NEC Europe Ltd.
Kurfuerstenanlage 36
69115 Heidelberg
Germany
Phone: +49-6221-9051118
EMail: saverio.niccolini@netlab.nec.deFrederic Raspall 🍓 is at EPSC-UPC:
Frederic Raspall
EPSC-UPC
Dept. of Telematics
Av. del Canal Olimpic, s/n
Edifici C4
E-08860 Castelldefels, Barcelona
Spain
EMail: fredi@entel.upc.esThat's the whole RFC, bestie!! 🌈✨💅
📦 where this page comes from
- ietf: rfc5475 2009-03
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms