A Framework for Packet Selection and Reporting
draft-ietf-psamp-framework-13
The information below is for an old version of the document that is already published as an RFC.
| Document | Type |
This is an older version of an Internet-Draft that was ultimately published as RFC 5474.
|
|
|---|---|---|---|
| Authors | Jennifer Rexford , Derek Chiou , Matthias Grossglauser , Benoît Claise , Albert Greenberg , Dr. Nick Duffield | ||
| Last updated | 2015-10-14 (Latest revision 2008-06-26) | ||
| RFC stream | Internet Engineering Task Force (IETF) | ||
| Intended RFC status | Informational | ||
| Formats | |||
| Reviews | |||
| Additional resources | Mailing list discussion | ||
| Stream | WG state | (None) | |
| Document shepherd | (None) | ||
| IESG | IESG state | Became RFC 5474 (Informational) | |
| Action Holders |
(None)
|
||
| Consensus boilerplate | Unknown | ||
| Telechat date | (None) | ||
| Responsible AD | Dan Romascanu | ||
| Send notices to | (None) |
draft-ietf-psamp-framework-13
`
Internet Draft Nick Duffield (Editor)
Document: draft-ietf-psamp-framework-13.txt AT&T Labs - Research
Intended status: Informational June 27, 2008
Expires: December 2008
A Framework for Packet Selection and Reporting
Status of this Memo
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 becomes aware will be disclosed, in accordance with
Section 6 of BCP 79.
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.
This Internet-Draft will expire on December, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2008).
Abstract
This document specifies a framework for the PSAMP (Packet
SAMPling) protocol. The functions of this protocol are to select
packets from a stream according to a set of standardized
selectors, to form a stream of reports on the selected packets,
and to export the reports to a collector. This framework details
the components of this architecture, then describes some generic
Duffield (Ed.) Expires December 2008 [Page 1]
Internet Draft Packet Selection and Reporting June 2008
requirements, motivated by the dual aims of ubiquitous deployment
and utility of the reports for applications. Detailed
requirements for selection, reporting and exporting are
described, along with configuration requirements of the PSAMP
functions.
Table of Contents
1. Introduction................................................3
2. PSAMP Documents Overview....................................4
3. Elements, Terminology and High-level Architecture...........4
3.1 High-level description of the PSAMP Architecture............4
3.2 Observation Points, Packet Streams and Packet Content.......5
3.3 Selection Process...........................................6
3.4 Reporting...................................................7
3.5 Metering Process............................................7
3.6 Exporting Process...........................................8
3.7 PSAMP Device................................................8
3.8 Collector...................................................8
3.9 Possible Configurations.....................................9
4. Generic Requirements for PSAMP.............................10
4.1 Generic Selection Process Requirements.....................10
4.2 Generic Reporting Requirements.............................11
4.3 Generic Exporting Process Requirements.....................12
4.4 Generic Configuration Requirements.........................12
5. Packet Selection...........................................12
5.1 Two Types of Selector......................................12
5.2 PSAMP Packet Selectors.....................................13
5.3 Selection Fraction Terminology.............................16
5.4 Input Sequence Numbers for Primitive Selectors.............17
5.5 Composite Selectors........................................18
5.6 Constraints on the Selection Fraction......................18
6. Reporting..................................................18
6.1 Mandatory Contents of Packet Reports: Basic Reports........18
6.2 Extended Packet Reports....................................19
6.3 Extended Packet Reports in the Presence of IPFIX...........19
6.4 Report Interpretation......................................20
7. Parallel Metering Processes................................20
8. Exporting Process..........................................21
8.1 Use of IPFIX...............................................21
8.2 Export Packets.............................................21
8.3 Congestion-aware Unreliable Transport......................21
8.4 Configurable Export Rate Limit.............................22
8.5 Limiting Delay for Export Packets..........................22
8.6 Export Packet Compression..................................23
8.7 Collector Destination......................................24
8.8 Local Export...............................................24
9. Configuration and Management...............................24
10. Feasibility and Complexity.................................25
10.1 Feasibility................................................25
10.1.1 Filtering.................................................25
Duffield (Ed.) Expires December 2008 [Page 2]
Internet Draft Packet Selection and Reporting June 2008
10.1.2 Sampling..................................................25
10.1.3 Hashing...................................................25
10.1.4 Reporting.................................................25
10.1.5 Exporting.................................................26
10.2 Potential Hardware Complexity..............................26
11. Applications...............................................27
11.1 Baseline Measurement and Drill Down........................27
11.2 Trajectory Sampling........................................28
11.3 Passive Performance Measurement............................28
11.4 Troubleshooting............................................29
12. Security Considerations....................................30
12.1 Relation of PSAMP and IPFIX Security for Exporting Process.30
12.2 PSAMP Specific Privacy Considerations......................30
12.3 Security Considerations for Hash-Based Selection...........30
12.3.1 Modes and Impact of vulnerabilities.......................31
12.3.2 Use of Private Parameters in Hash Functions...............31
12.3.3 Strength of Hash Functions................................32
12.4 Security Guidelines for Configuring PSAMP..................32
13. IANA Considerations........................................33
14. References.................................................33
14.1 Normative References.......................................33
14.2 Informative References.....................................33
15. Authors' Addresses.........................................35
16. Contributors...............................................36
17. Acknowledgements...........................................36
18. Intellectual Property Statements...........................36
19. Copyright Statement........................................37
20. Disclaimer.................................................37
1. Introduction
This document 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.
The motivation for the PSAMP standard comes from the need for
measurement-based support for network management and control
across multivendor domains. This requires domain-wide
consistency in the types of selection schemes available, and the
manner in which the resulting measurements are presented and
interpreted.
The motivation for specific packet selection operations comes
from the applications that they enable. Development of the PSAMP
standard is open to influence by the requirements of standards in
related IETF Working Groups, for example, IP Performance Metrics
(IPPM) [RFC-2330] and Internet Traffic Engineering (TEWG).
The name PSAMP is a contraction of the phrase Packet Sampling.
The word "sampling" captures the idea that only a subset of all
Duffield (Ed.) Expires December 2008 [Page 3]
Internet Draft Packet Selection and Reporting June 2008
packets passing a network element will be selected for reporting.
But PSAMP selection operations include random selection,
deterministic selection (filtering), and deterministic
approximations to random selection (hash-based selection).
2. PSAMP Documents Overview
PSAMP-FW: "A Framework for Packet Selection and Reporting" (this
document). This document 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. Definitions of terminology and the use
of the terms "must", "should" and "may" in this document are
informational only.
[PSAMP-TECH]: "Sampling and Filtering Techniques for IP Packet
Selection", describes the set of packet selection techniques
supported by PSAMP.
[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. Elements, Terminology and High-level Architecture
3.1 High-level description of the PSAMP Architecture
Here is an informal high level description of the PSAMP protocol
operating in a PSAMP Device (all terms will be defined
presently). A stream of packets is observed at an Observation
Point. A Selection Process inspects each packet to determine
whether or not it is to be selected from reporting. The
Selection Process is part of the Metering Process, which
constructs a report on each selected packet, using the Packet
Content, and possibly other information such as the packet
treatment at the Observation Point or the arrival timestamp. An
Exporting Process sends the Packet Reports to a Collector,
together with any subsidiary information needed for their
interpretation.
The following figure indicates the sequence of the three
processes (Selection, Metering, and Exporting) within the PSAMP
device.
Duffield (Ed.) Expires December 2008 [Page 4]
Internet Draft Packet Selection and Reporting June 2008
+------------------+
| Metering Process |
| +-----------+ | +-----------+
Observed | | Selection | | | Exporting |
Packet--->| | Process |--------->| Process |--->Collector
Stream | +-----------+ | +-----------+
+------------------+
The following sections give the detailed definitions of each of
all the objects just named.
3.2 Observation Points, Packet Streams and Packet Content
This section contains the definition of terms relevant to
obtaining the packet input to the selection process.
* Observation Point
An Observation Point is a location in the network where IP
packets can be observed. Examples include: a line to which a
probe is attached, a shared medium, such as an Ethernet-based
LAN, a single port of a router, or a set of interfaces
(physical or logical) of a router.
Note that every Observation Point is associated with an
Observation Domain (defined below), and 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 subset of the Observed Packet Stream
that flows past some specified point within the Selection
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 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 [RFC-3917].
* Packet Content
Duffield (Ed.) Expires December 2008 [Page 5]
Internet Draft Packet Selection and Reporting June 2008
The Packet Content denotes the union of the packet header
(which includes link layer, network layer and other
encapsulation headers) and the packet payload.
3.3 Selection Process
This section defines the selection process and related objects.
* 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. 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 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 Content;
(ii) information derived from the packet's treatment at the
Observation Point;
Duffield (Ed.) Expires December 2008 [Page 6]
Internet Draft Packet Selection and Reporting June 2008
(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.4 Reporting
* Packet Reports
Packet Reports comprise a configurable subset of a packet's
input to the Selection Process, including the Packet Content,
information relating to its treatment (for example, the output
interface), and its associated selection state (for example, a
hash of the Packet Content).
* Report Interpretation:
Report Interpretation comprises subsidiary information,
relating to one or more packets, that are 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.5 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 [RFC-5101], which produces flow records as
Duffield (Ed.) Expires December 2008 [Page 7]
Internet Draft Packet Selection and Reporting June 2008
its output. While the Metering Process definition in this
document specifies the PSAMP definition, the PSAMP protocol
specifications [PSAMP-PROTO] will use the IPFIX Metering Process
definition, which also suits the PSAMP requirements. The
relationship between PSAMP and IPFIX is described more in [PSAMP-
INFO] and [PSAMP-PROTO].
3.6 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 Packets:
An Export Packet is a combination of Report Interpretation(s)
and/or one or more Packet Reports that are bundled by the
Exporting Process into a Export Packet for exporting to a
Collector.
3.7 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 co-
located at this device, for example at a router.
3.8 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.
Duffield (Ed.) Expires December 2008 [Page 8]
Internet Draft Packet Selection and Reporting June 2008
3.9 Possible Configurations
Various possibilities for the high level architecture of these
elements are as follows.
MP = Metering Process, EP = Exporting process
PSAMP Device
+---------------------+ +------------------+
|Observation Point(s) | | Collector(1) |
|MP(s)--->EP----------+---------------->| |
|MP(s)--->EP----------+-------+-------->| |
+---------------------+ | +------------------+
|
PSAMP Device |
+---------------------+ | +------------------+
|Observation Point(s) | +-------->| Collector(2) |
|MP(s)--->EP----------+---------------->| |
+---------------------+ +------------------+
PSAMP Device
+---------------------+
|Observation Point(s) |
|MP(s)--->EP---+ |
| | |
|Collector(3)<-+ |
+---------------------+
The most simple Metering Process configuration is composed of:
+------------------------------------+
| +----------+ |
| |Selection | |
Observed | |Process | Packet |
Packet-->| |(primitive|-> Stream -> |--> Report Stream
Stream | | selector)| |
| +----------+ |
| Metering Process |
+------------------------------------+
Duffield (Ed.) Expires December 2008 [Page 9]
Internet Draft Packet Selection and Reporting June 2008
A Metering Process with a composite selector is composed of:
+--------------------------------------------------...
| +-----------------------------------+
| | +----------+ +----------+ |
| | |Selection | |Selection | |
Observed | | |Process | |Process | |
Packet-->| | |(primitive|-Packet->|(primitive|---> Packet ...
Stream | | |selector1)| Stream |selector2)| | Stream
| | +----------+ +----------+ |
| | Composite Selector |
| +-----------------------------------+
| Metering Process
+--------------------------------------------------...
...-------------+
|
|
|
|
|---> Report Stream
|
|
|
|
|
...-------------+
4. Generic Requirements for PSAMP
This section describes the generic requirements for the PSAMP
protocol. A number of these are realized as specific
requirements in later sections.
4.1 Generic Selection Process Requirements.
(a) Ubiquity: The Selectors must be simple enough to be
implemented ubiquitously at maximal line rate.
(b) Applicability: the set of Selectors must be rich enough to
support a range of existing and emerging measurement based
applications and protocols. This requires a workable
trade-off between the range of traffic engineering
applications and operational tasks it enables, and the
complexity of the set of capabilities.
(c) Extensibility: the protocol must be able to accommodate
additional packet Selectors not currently defined.
(d) Flexibility: the protocol must support selection of packets
using various network protocols or encapsulation layers,
Duffield (Ed.) Expires December 2008 [Page 10]
Internet Draft Packet Selection and Reporting June 2008
including Internet Protocol Version 4 (IPv4) [RFC-0791],
Internet Protocol Version 6 (IPv6) [RFC-2460], and
Multiprotocol Label Switching (MPLS) [RFC-3031].
(e) Robust Selection: packet selection must be robust against
attempts to craft an Observed Packet Stream from which
packets are selected disproportionately (e.g. to evade
selection, or overload measurement systems).
(f) Parallel Metering Processes: the protocol must support
simultaneous operation of multiple independent Metering
Processes at the same host.
(g) Causality: the selection decision for each packet should
depend only weakly, if at all, upon future packets
arrivals. This promotes ubiquity by limiting the
complexity of the selection logic.
(h) Encrypted Packets: Selectors that interpret packet fields
must be configurable to ignore (i.e. not select) encrypted
packets, when they are detected.
Specific Selectors are outlined in Section 5, and described in
more detail in the companion document [PSAMP-TECH].
4.2 Generic Reporting Requirements
(i) Self-defining: the Report Stream must be complete in the
sense that no additional information need be retrieved from
the Observation Point in order to interpret and analyze the
reports.
(j) Indication of Information Loss: the Report Stream must
include sufficient information to indicate or allow the
detection of loss occurring within the Selection, Metering,
and/or Exporting Processes, or in transport. This may be
achieved by the use of sequence numbers.
(k) Accuracy: the Report Stream must include information that
enables the accuracy of measurements to be determined.
(l) Faithfulness: all reported quantities that relate to the
packet treatment must reflect the router state and
configuration encountered by the packet at the time it is
received by the Metering Process.
(m) Privacy: although selection of the content of Packet
Reports must be responsive to the needs of measurement
applications, it must also conform with [RFC-2804]. In
particular, full packet capture of arbitrary packet streams
is explicitly out of scope.
Duffield (Ed.) Expires December 2008 [Page 11]
Internet Draft Packet Selection and Reporting June 2008
See section 6 for further discussions on Reporting.
4.3 Generic Exporting Process Requirements
(n) Timeliness: configuration must allow for limiting of
buffering delays for the formation and transmission for
Export Packets. See Section 8.5 for further details.
(o) Congestion Avoidance: export of a Report Stream across a
network must be congestion avoiding in compliance with
[RFC-2914]. This is discussed further in Section 8.3.
(p) Secure Export:
(i) confidentiality: the option to encrypt exported data must
be provided.
(ii) integrity: alterations in transit to exported data must be
detectable at the Collector
(iii) authenticity: authenticity of exported data must be
verifiable by the Collector in order to detect forged data.
The motivation here is the same as for security in IPFIX export;
see Sections 6.3 and 10 of [RFC-3917].
4.4 Generic Configuration Requirements
(q) Ease of Configuration: of sampling and export parameters,
e.g. for automated remote reconfiguration in response to
collected reports.
(r) Secure Configuration: the option to configure via protocols
that prevent unauthorized reconfiguration or eavesdropping
on configuration communications must be available.
Eavesdropping on configuration might allow an attacker to
gain knowledge that would be helpful in crafting a packet
stream to evade subversion, or overload the measurement
infrastructure.
Configuration is discussed in Section 9.
5. Packet Selection
This section details specific requirements for the Selection
Process, motivated by the generic requirements of Section 3.3.
5.1 Two Types of Selector
PSAMP categorizes selectors into two types:
Duffield (Ed.) Expires December 2008 [Page 12]
Internet Draft Packet Selection and Reporting June 2008
* 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.
5.2 PSAMP Packet Selectors
A spectrum of packet selectors is described in detail in [PSAMP-
TECH]. Here we only briefly summarize the meanings for
completeness.
A PSAMP Selection Process must support at least one of the
following Selectors.
* systematic count based sampling: packet selection is triggered
periodically by packet count, a number of successive packets
being selected subsequent to each trigger.
* systematic time based sampling: similar to systematic count
based except that selection is reckoned with respect to time
rather than count. Packet selection is triggered at periodic
Duffield (Ed.) Expires December 2008 [Page 13]
Internet Draft Packet Selection and Reporting June 2008
instants separated by a time called the spacing. All packets
that arrive within a certain time of the trigger (called the
interval length) are selected.
* probabilistic n-out-of-N sampling: from each count-based
successive block of N packets, n are selected at random.
* uniform probabilistic sampling: packets are selected
independently with fixed sampling probability p.
* non-uniform probabilistic sampling: packets are selected
independently with probability p that depends on Packet
Content.
* property match filtering
With this Filtering method a packet is selected if a specific
field within the packet and/or on properties of the router
state equal(s) a predefined value. Possible filter fields are
all IPFIX flow attributes specified in [RFC-5102]. Further
fields can be defined by vendor specific extensions.
A packet is selected if Field=Value. Masks and ranges are only
supported to the extent to which [RFC-5102] allows them e.g. by
providing explicit fields like the netmasks for source and
destination addresses.
AND operations are possible by concatenating filters, thus
producing a composite selection operation. In this case, the
ordering in which the filtering happens is implicitly defined
(outer filters come after inner filters). However, as long as
the concatenation is on filters only, the result of the
cascaded filter is independent from the order, but the order
may be important for implementation purposes, as the first
filter will have to work at a higher rate. In any case, an
implementation is not constrained to respect the filter
ordering, as long as the result is the same, and it may even
implement the composite filtering in 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 etc.) can be realized as vendor specific schemes.
Property match operations should be available for different
protocol portions of the packet header:
(i) the IP header (excluding options in IPv4, stacked
headers in IPv6)
(ii) transport header
Duffield (Ed.) Expires December 2008 [Page 14]
Internet Draft Packet Selection and Reporting June 2008
(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 or
encapsulation protocols, then the information should be made
available for filtering. For example, when a PSAMP Device is a
router that 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 alters the meaning 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 packet arrives equals a
specified value
(ii) Egress interface to which packet is routed to equals a
specified value
(iii) Packet violated Access Control List (ACL) on the
router
(iv) Failed Reverse Path Forwarding (RPF). Packets that
match the Failed Reverse Path Forwarding (RPF) condition are
packets for which ingress filtering failed as defined in
[RFC3704].
(v) Failed Resource Reservation (RSVP). Packets that match
the Failed Resource Reservation condition are packets that
do not fulfill the RSVP specification as defined in
[RFC-2205].
(vi) No route found for the packet
(vii) Origin Border Gateway Protocol (BGP) Autonomous System
(AS) [RFC-4271] equals a specified value or lies within a
given range
(viii) Destination BGP AS equals a specified value or lies
within a given range
Router architectural considerations may preclude some
information concerning the packet treatment being available at
line rate for selection of packets. For example, the Selection
Duffield (Ed.) Expires December 2008 [Page 15]
Internet Draft Packet Selection and Reporting June 2008
Process may not be implemented in the fast path that is able to
access routing 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 routing state.
* Hash-based Selection:
Hash-based selection will employ one or more hash functions to
be standardized. A hash function is applied to a subset of
Packet Content, and the packet is selected of the resulting
hash falls in a specified range. The stronger the hash
function, the more closely hash-based selection approximates
uniform random sampling. Privacy of hash selection range and
hash function parameters obstructs subversion of the selector
by packets that are crafted either to avoid selection or to be
selected. Privacy of the hash function is not required.
Robustness and security considerations of hash-based selection
are further discussed in further in [PSAMP-TECH]. Applications
of hash-based sampling are described in Section 11.
5.3 Selection Fraction Terminology
* 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 a
Population.
* Configured Selection Fraction
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.
Duffield (Ed.) Expires December 2008 [Page 16]
Internet Draft Packet Selection and Reporting June 2008
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 notions of Configured/Attained Selection Fraction extend
beyond Selectors. An illustrative example is the Configured
Selection Fraction of the composition of the Metering Process
with the Exporting Process. Here the Population is the Observed
Packet Stream or a subset thereof. The Configured Selection
Fraction is the fraction of the Population for which Packet
Reports which are expected to reach the Collector. This quantity
may reflect additional parameters, not necessarily described in
the PSAMP protocol, that determine the degree of loss suffered by
Packet Reports en route to the Collector, e.g., the transmission
bandwidth available to the Exporting Process. In this example,
the Attained Selection Fraction is the fraction of Population
packets for which reports did actually reach the Collector, and
thus incorporates the effect of any loss of Packet Reports due,
e.g, to resource contention at the Observation Point, or during
transmission.
5.4 Input Sequence Numbers for Primitive Selectors
Each instance of a Primitive Selector must maintain a count of
packets presented at its input. The counter value is to be
included as a sequence number for selected packets. The sequence
numbers are considered as part of the packet's Selection State.
Use of input sequence numbers enables applications to determine
the Attained Selection Fraction, and hence correctly normalize
network usage estimates regardless of loss of information,
regardless of whether this loss occurs because of discard of
packet reports in the Metering Process (e.g. due to resource
contention in the host of these processes), or loss of export
packets in transmission or collection. See [RFC-3176] for
further details.
As an example, consider a set of n consecutive packet reports r1,
r2,... , rn, selected by a sampling operation and received at a
Collector. Let s1, s2,..., sn be the input sequence numbers
reported by the packets. The Attained Selection Fraction for the
composite of the measurement and exporting processes, taking into
account both packet sampling at the Observation Point and loss in
transmission, is computed as R = (n-1)/(sn-s1). (Note R would be
1 if all packets were selected and there were no transmission
loss).
Duffield (Ed.) Expires December 2008 [Page 17]
Internet Draft Packet Selection and Reporting June 2008
The Attained Selection Fraction can be used to estimate the
number of bytes present in a portion of the Observed Packet
Stream. Let b1, b2,..., bn be the number of bytes reported in
each of the packets that reached the Collector, and set B =
b1+b2+...+bn. Then the total bytes present in packets in the
Observed Packet Stream whose input sequence numbers lie between
s1 and sn is estimated by B/R, i.e, scaling up the measured bytes
through division by the Attained Selection Fraction
With Composite Selectors, an input sequence number must be
reported for each Selector in the composition.
5.5 Composite Selectors
The ability to compose Selectors in a Selection Process should be
provided. The following combinations appear to be most useful
for applications:
* concatentation of property match filters. This is useful for
constructing the AND of the component filters.
* filtering followed by sampling.
* sampling followed by filtering.
Composite Selectors are useful for drill down applications. The
first component of a composite selector can be used to reduce the
load on the second component. In this setting, the advantage to
be gained from a given ordering can depends on the composition of
the packet stream.
5.6 Constraints on the Selection Fraction
Sampling at full line rate, i.e. with probability 1, is not
excluded in principle, although resource constraints may not
permit it in practice.
6. Reporting
This section details specific requirements for reporting,
motivated by the generic requirements of Section 3.4
6.1 Mandatory Contents of Packet Reports: Basic Reports
Packet Reports must include the following:
(i) the input sequence number(s) of any Selectors that acted
on the packet in the instance of a Metering Process which
produced the report.
(ii) the identifier of the Metering Process that produced
the selected packet
Duffield (Ed.) Expires December 2008 [Page 18]
Internet Draft Packet Selection and Reporting June 2008
The Metering Process must support inclusion of the following in
each Packet Report, as a configurable option:
(iii) a basic report on the packet, i.e., some number of
contiguous bytes from the start of the packet, including the
packet header (which includes network layer and any
encapsulation headers) and some subsequent bytes of the
packet payload.
Some devices may not have the resource capacity or functionality
to provide more detailed packet reports than those in (i), (ii)
and (iii) above. Using this minimum required reporting
functionality, the Metering Process places the burden of
interpretation on the Collector, or on applications that it
supplies. Some devices may have the capability to provide
extended packet reports, described in the next section.
6.2 Extended Packet Reports
The Metering Process may support inclusion in Packet Reports of
the following information, inclusion any or all being
configurable as an option.
(iv) fields relating to the following protocols used in the
packet: IPv4, IPV6, transport protocols, and encapsulation
protocols including MPLS
(v) packet treatment, including:
- identifiers for any input and output interfaces of the
Observation Point that were traversed by the packet
- source and destination BGP AS
(vi) Selection State associated with the packet, including:
- the timestamp of observation of the packet at the
Observation Point. The timestamp should be reported to
microsecond resolution.
- hashes, where calculated.
It is envisaged that selection of fields for Extended Packet
Reporting may be used to reduce reporting bandwidth, in which
case the option to report information in (iii) may not be
exercised.
6.3 Extended Packet Reports in the Presence of IPFIX
If an IPFIX metering process is supported at the Observation
Point, then in order to be PSAMP compliant, Extended Packet
Duffield (Ed.) Expires December 2008 [Page 19]
Internet Draft Packet Selection and Reporting June 2008
Reports must be able to include all fields required in the IPFIX
information model [RFC-5102], with modifications appropriate to
reporting on single packets rather than flows.
6.4 Report Interpretation
The Report Interpretation must include:
(i) configuration parameters of the Selectors of the packets
reported on.
(ii) format of the Packet Report;
(iii) indication of the inherent accuracy of the reported
quantities, e.g., of the packet timestamp.
The accuracy measure in (iii) is of fundamental importance for
estimating the likely error attached to estimates formed from the
Packet Reports by applications.
The requirements for robustness and transparency are motivations
for including Report Interpretation in the Report Stream: it
makes the Report Stream self-defining. The PSAMP framework
excludes reliance on an alternative model in which interpretation
is recovered out of band. This latter approach is not robust
with respect to undocumented changes in Selector configuration,
and may give rise to future architectural problems for network
management systems to coherently manage both configuration and
data collection.
It is not envisaged that all Report Interpretation be included in
every Packet Report. Many of the quantities listed above are
expected to be relatively static; they could be communicated
periodically, and upon change.
7. Parallel Metering Processes
Because of the increasing number of distinct measurement
applications, with varying requirements, it is desirable to set
up parallel Metering Processes on a given Observed Packet Stream.
A device capable of hosting a Metering Process should be able to
support more than one independently configurable Metering Process
simultaneously. Each such Metering Process should have the
option of being equipped with its own Exporting Process;
otherwise the parallel Metering Processes may share the same
Exporting Process.
Each of the parallel Metering Processes should be independent.
However, resource constraints may prevent complete reporting on a
packet selected by multiple Selection Processes. In this case,
reporting for the packet must be complete for at least one
Metering Process; other Metering Processes need only record that
Duffield (Ed.) Expires December 2008 [Page 20]
Internet Draft Packet Selection and Reporting June 2008
they selected the packet, e.g., by incrementing a counter. The
priority amongst Metering Processes under resource contention
should be configurable.
It is not proposed to standardize the number of parallel Metering
Processes.
8. Exporting Process
This section details specific requirements for the Exporting
Process, motivated by the generic requirements of Section 3.6
8.1 Use of IPFIX
PSAMP will use the IP Flow Information eXport (IPFIX) protocol
for export of the Report Stream. The IPFIX protocol is well
suited for this purpose, because the IPFIX architecture matches
the PSAMP architecture very well and the means provided by the
IPFIX protocol are sufficient for PSAMP purposes. On the other
hand, not all features of the IPFIX protocol will need to be
implemented by some PSAMP devices. For example, a device that
offers only content-independent sampling and basic PSAMP
reporting has no need to support IPFIX capabilities based on
packet fields.
8.2 Export Packets
Export packets may contain one or more Packet Reports, and/or
Report Interpretation. Export packets must also contain:
(i) An identifier for the Exporting Process
(ii) An export packet sequence number.
An export packet sequence number enables the Collector to
identify loss of export packets in transit. Note that some
transport protocols, e.g. UDP, do not provide sequence
numbers. Moreover, having sequence numbers available at the
application level enables the Collector to calculate packet
loss rate for use, e.g., in estimating original traffic
volumes from export packet that reach the Collector.
8.3 Congestion-aware Unreliable Transport
The export of the Report Stream does not require reliable export.
Section 5.4 shows that the use of input sequence numbers in
packet Selectors means that the ability to estimate traffic rates
is not impaired by export loss. Export packet loss becomes
another form of sampling, albeit a less desirable, and less
controlled, form of sampling.
Duffield (Ed.) Expires December 2008 [Page 21]
Internet Draft Packet Selection and Reporting June 2008
In distinction, retransmission of lost Export Packets consumes
additional network resources. The requirement to store
unacknowledged data is an impediment to having ubiquitous support
for PSAMP.
In order to jointly satisfy the timeliness and congestion
avoidance requirements of Section 4.3, a congestion-aware
unreliable transport protocol may be used. IPFIX is compatible
with this requirement, since it mandates support of the Stream
Control Transmission Protocol (SCTP) [RFC-4960] and the SCTP
Partial Reliability Extension [RFC-3758].
IPFIX also allows the use of User Datagram Protocol (UDP) [RFC-
768] although it is not a congestion-aware protocol. However, in
this case, the Export Packets must remain wholly within the
administrative domains of the operators [RFC-5101]. The PSAMP
exporting process is equipped with a configurable export rate
limit (see Section 8.4 following) that can be used to limit the
export rate when a congestion aware transport protocol is not
used. The Collector, upon detection of export packet loss
through missing export sequence numbers, may reconfigure the
export rate limit downwards in order to avoid congestion.
8.4 Configurable Export Rate Limit
The exporting process must have an export rate limit,
configurable per Exporting Process. This is useful for two
reasons:
(i) Even without network congestion, the rate of packet
selection may exceed the capacity of the Collector to
process reports, particularly when many Exporting Processes
feed a common Collector. Use of an Export Rate Limit allows
control of the global input rate to the Collector.
(ii) IPFIX provides export using UDP as the transport
protocol in some circumstances. An Export Rate Limit allows
the capping of the export rate to match both path link
speeds and the capacity of the Collector.
8.5 Limiting Delay for Export Packets
Low measurement latency allows the traffic monitoring system to
be more responsive to real-time network events, for example, in
quickly identifying sources of congestion. Timeliness is
generally a good thing for devices performing the sampling since
it minimizes the amount of memory needed to buffer samples.
Keeping the packet dispatching delay small has other benefits
besides limiting buffer requirements. For many applications a
resolution of 1 second is sufficient. Applications in this
category would include: identifying sources associated with
Duffield (Ed.) Expires December 2008 [Page 22]
Internet Draft Packet Selection and Reporting June 2008
congestion, tracing denial of service attacks through the
network, and constructing traffic matrices. Furthermore, keeping
dispatch delay within the resolution required by applications
eliminates the need for timestamping by synchronized clocks at
observation points, or for the Observation Points and Collector
to maintain bi-directional communication in order to track clock
offsets. The Collector can simply process Packet Reports in the
order that they are received, using its own clock as a "global"
time base. This avoids the complexity of buffering and
reordering samples. See [DuGeGr02] for an example.
The delay between observation of a packet and transmission of a
Export Packet containing a report on that packet has several
components. It is difficult to standardize a given numerical
delay requirement, since in practice the delay may be sensitive
to processor load at the Observation Point. Therefore, PSAMP
aims to control that portion of the delay within the Observation
Point that is due to buffering in the formation and transmission
of Export Packets.
In order to limit delay in the formation of Export Packets, the
Exporting Process must provide the ability to close out and
enqueue for transmission any Export Packet during formation as
soon as it includes one Packet Report.
In order to limit the delay in the transmission of Export
Packets, a configurable upper bound to the delay of an Export
Packet prior to transmission must be provided. If the bound is
exceeded the Export Packet is dropped. This functionality can be
provided by the timed reliability service of the SCTP Partial
Reliability Extension [RFC-3758].
The Exporting Process may enqueue the Report Stream in order to
export multiple Packet Reports in a single export packet. Any
consequent delay must still allow for timely availability of
Packet Reports as just described. The timed reliability service
of the SCTP Partial Reliability Extension [RFC-3758] allows the
dropping of packets from the export buffer once their age in the
buffer exceeds a configurable bound. A suitable default value
for the bound should be used in order to avoid a low transmission
rate due to misconfiguration.
8.6 Export Packet Compression
To conserve network bandwidth and resources at the Collector, the
Export Packets may be compressed before export. Compression is
expected to be quite effective since the sampled packets may
share many fields in common, e.g. if a filter focuses on packets
with certain values in particular header fields. Using
compression, however, could impact the timeliness of Packet
Reports. Any consequent delay must not violate the timeliness
requirement for availability of Packet Reports at the Collector.
Duffield (Ed.) Expires December 2008 [Page 23]
Internet Draft Packet Selection and Reporting June 2008
8.7 Collector Destination
When exporting to a remote Collector, the Collector is identified
by IP address, transport protocol, and transport port number.
8.8 Local Export
The Report Stream may be directly exported to on-board
measurement based applications, for example those that form
composite statistics from more than one packet. Local export may
be presented through an interface direct to the higher level
applications, i.e., through an API, rather than employing the
transport used for off-board export. Specification of such an
API is outside the scope of the PSAMP framework.
A possible example of Local Export could be that packets selected
by the PSAMP Metering Process serve as the input for the IPFIX
protocol, which then forms flow records out of the stream of
selected packets.
9. Configuration and Management
A key requirement for PSAMP is the easy reconfiguration of the
parameters of the Metering Process, including those for selection
and packet reports, and of the Exporting Process. An important
example is to support measurement-based applications that want to
adaptively drill-down on traffic detail in real-time.
To facilitate retrieval and monitoring of parameters, they are to
reside in a Management Information Base (MIB). Mandatory
monitoring objects will cover all mandatory PSAMP functionality.
Alarming of specific parameters could be triggered with
thresholding mechanisms such as the RMON event and alarm [RFC-
2819] or the event MIB [RFC-2981].
For configuring parameters of the Metering Process, several
alternatives are available including a MIB module with writeable
objects, as well as other configuration protocols. For
configuring parameters of the Exporting Process, the Packet
Report, and the Report Interpretation, which is an IFPIX task,
the IPFIX configuration method(s) should be used.
Although management and configuration of collectors is out of
scope, a PSAMP device, to the extent that it employs IPFIX as an
export protocol, inherits from IPFIX the capability to detect and
recover from collector failure; see Section 8.2 of [IPFIX-ARCH].
Duffield (Ed.) Expires December 2008 [Page 24]
Internet Draft Packet Selection and Reporting June 2008
10. Feasibility and Complexity
In order for PSAMP to be supported across the entire spectrum of
networking equipment, it must be simple and inexpensive to
implement. One can envision easy-to-implement instances of the
mechanisms described within this draft. Thus, for that subset of
instances, it should be straightforward for virtually all system
vendors to include them within their products. Indeed, sampling
and filtering operations are already realized in available
equipment.
Here we give some specific arguments to demonstrate feasibility
and comment on the complexity of hardware implementations. We
stress here that the point of these arguments is not to favor or
recommend any particular implementation, or to suggest a path for
standardization, but rather to demonstrate that the set of
possible implementations is not empty.
10.1 Feasibility
10.1.1 Filtering
Filtering consists of a small number of mask (bit-wise logical),
comparison and range (greater than) operations. Implementation
of at least a small number of such operations is straightforward.
For example, filters for security access control lists (ACLs) are
widely implemented. This could be as simple as an exact match on
certain fields, or involve more complex comparisons and ranges.
10.1.2 Sampling
Sampling based on either counters (counter set, decrement, test
for equal to zero) or range matching on the hash of a packet
(greater than) is possible given a small number of selectors,
although there may be some differences in ease of implementation
for hardware vs. software platforms.
10.1.3 Hashing
Hashing functions vary greatly in complexity. Execution of a
small number of sufficient simple hash functions is implementable
at line rate. Concerning the input to the hash function,
hop-invariant IP header fields (IP address, IP identification)
and TCP/UDP header fields (port numbers, TCP sequence number)
drawn from the first 40 bytes of the packet have been found to
possess a considerable variability; see [DuGr01].
10.1.4 Reporting
Duffield (Ed.) Expires December 2008 [Page 25]
Internet Draft Packet Selection and Reporting June 2008
The simplest Packet Report would duplicate the first n bytes of
the packet. However, such an uncompressed format may tax the
bandwidth available to the Exporting Process for high sampling
rates; reporting selected fields would save on this bandwidth.
Thus there is a trade-off between simplicity and bandwidth
limitations.
10.1.5 Exporting
Ease of exporting export packets depends on the system
architecture. Most systems should be able to support export by
insertion of export packets, even through the software path.
10.2 Potential Hardware Complexity
Achieving low constants for performance while minimizing hardware
resources is, of course, a challenge, especially at very high
clock frequencies. Most of the Selectors, however, are very
basic and their implementations very well understood; in fact,
the average Application Specific Integrated Circuit (ASIC)
designer simply uses canned library instances of these operations
rather than design them from scratch. In addition, networking
equipment generally does not need to run at the fastest clock
rates, further reducing the effort required to get reasonably
efficient implementations.
Simple bit-wise logical operations are easy to implement in
hardware. Such operations (NAND/NOR/XNOR/NOT) directly translate
to four-transistor gates. Each bit of a multiple-bit logical
operation is completely independent and thus can be performed in
parallel incurring no additional performance cost above a single
bit operation.
Comparisons (EQ/NEQ) take O(log(M)) stages of logic, where M is
the number of bits involved in the comparison. The log(M) is
required to accumulate the result into a single bit.
Greater than operations, as used to determine whether a hash
falls in a selection range, are a determination of the most
significant not-equivalent bit in the two operands. The operand
with that most-significant-not-equal bit set to be one is greater
than the other. Thus, a greater than operation is also an
O(log(M)) stages of logic operation. Optimized implementations
of arithmetic operations are also O(log(M)) due to propagation of
the carry bit.
Setting a counter is simply loading a register with a state.
Such an operation is simple and fast O(1). Incrementing or
decrementing a counter is a read, followed by an arithmetic
operation followed by a store. Making the register dual-ported
does take additional space, but it is a well-understood
Duffield (Ed.) Expires December 2008 [Page 26]
Internet Draft Packet Selection and Reporting June 2008
technique. Thus, the increment/decrement is also an O(log(M))
operation.
Hashing functions come in a variety of forms. The computation
involved in a standard Cyclic Redundancy Code (CRC) for example
are essentially a set of XOR operations, where the intermediate
result is stored and XORed with the next chunk of data. There
are only O(1) operations and no log complexity operations. Thus,
a simple hash function, such as CRC or generalizations thereof,
can be implemented in hardware very efficiently.
At the other end of the range of complexity, the MD5 function
uses a large number of bit-wise conditional operations and
arithmetic operations. The former are O(1) operations and the
latter are O(log(M)). MD5 specifies 256 32b ADD operations per
16B of input processed. Consider processing 10Gb/sec at 100MHz
(this processing rate appears to be currently available). This
requires processing 12.5B/cycle, and hence at least 200 adders, a
sizeable number. Because of data dependencies within the MD5
algorithm, the adders cannot be simply run in parallel, thus
requiring either faster clock rates and/or more advanced
architectures. Thus, selection hashing functions as complex as
MD5 may be precluded for ubiquitous use at full line rate. This
motivates exploring the use of selection hash functions with
complexity somewhere between that of MD5 and CRC. In some
applications (see Section below) a second hash may be calculated
on only selected packets; MD5 is feasible for this purpose if the
rate of production of selected packets is sufficiently low.
11. Applications
We first describe several representative operational applications
that require traffic measurements at various levels of temporal
and spatial granularity. Some of the goals here appear similar
to those of IPFIX, at least in the broad classes of applications
supported. The major benefit of PSAMP is the support of new
network management applications, specifically, those enabled by
the packet Selectors that it supports.
11.1 Baseline Measurement and Drill Down
Packet sampling is ideally suited to determine the composition of
the traffic across a network. The approach is to enable
measurement on a cut-set of the network links such that each
packet entering the network is seen at least once, for example,
on all ingress links. Unfiltered sampling with a relatively low
selection fraction establishes baseline measurements of the
network traffic. Packet Reports include packet attributes of
common interest: source and destination address and port numbers,
prefix, protocol number, type of service, etc. Traffic matrices
are indicated by reporting source and destination AS matrices.
Absolute traffic volumes are estimated by renormalizing the
Duffield (Ed.) Expires December 2008 [Page 27]
Internet Draft Packet Selection and Reporting June 2008
sampled traffic volumes through division by either the Configured
Selection Fraction, or by the Attained Selection Fraction (as
derived from input packet counters included in the Report Stream)
Suppose an operator or a measurement-based application detects an
interesting subset of a Packet Stream, as identified by a
particular packet attribute. Real-time drill-down to that subset
is achieved by instantiating a new Metering Process on the same
Observed Packet Stream from which the subset was reported. The
Selection Process of the new Metering Process filters according
to the attribute of interest, and composes with sampling if
necessary to manage the attained fraction of packets selected.
11.2 Trajectory Sampling
The goal of trajectory sampling is the selection of a subset of
packets at all enabled Observation Points at which they are
observed in a network domain. Thus the selection decisions are
consistent in the sense that each packet is selected either at
all enabled Observation Points, or at none of them. Trajectory
sampling is realized by hash-based selection if all enabled
Observation Points apply a common hash function to a portion of
the Packet Content that is invariant along the packet path.
(Thus, fields such at TTL and CRC are excluded).
The trajectory followed by a packet is reconstructed from Packet
Reports on it that reach the Collector. Reports on a given
packet are associated either by matching a label comprising the
invariant reported Packet Content, or possibly some digest of it.
The reconstruction of trajectories, and methods for dealing with
possible ambiguities due to label collisions (identical labels
reported by different packets) and potential loss of reports in
transmission are dealt with in [DuGr01], [DuGeGr02] and [DuGr04].
11.3 Passive Performance Measurement
Trajectory sampling enables the tracking of the performance
experience by customer traffic, customers identified by a list of
source or destination prefixes, or by ingress or egress
interfaces. Operational uses include the verification of Service
Level Agreements (SLAs), and troubleshooting following a customer
complaint.
In this application, trajectory sampling is enabled at all
network ingress and egress interfaces. Rates of loss in transit
between ingress and egress are estimated from the proportion of
trajectories for which no egress report is received. Note that
loss of customer packets is distinguishable from loss of packet
reports through use of report sequence numbers. Assuming
Duffield (Ed.) Expires December 2008 [Page 28]
Internet Draft Packet Selection and Reporting June 2008
synchronization of clocks between different entities, delay of
customer traffic across the network may also be measured; see
[Zs02].
Extending hash-selection to all interfaces in the network would
enable attribution of poor performance to individual network
links.
11.4 Troubleshooting
PSAMP Packet Reports can also be used to diagnose problems whose
occurrence is evident from aggregate statistics, per interface
utilization and packet loss statistics. These statistics are
typically moving averages over relatively long time windows,
e.g., 5 minutes, and serve as a coarse-grain indication of
operational health of the network. The most common method of
obtaining such measurements are through the appropriate SNMP MIBs
(MIB-II [RFC-1213] and vendor-specific MIBs.)
Suppose an operator detects a link that is persistently
overloaded and experiences significant packet drop rates. There
is a wide range of potential causes: routing parameters (e.g.,
OSPF link weights) that are poorly adapted to the traffic matrix,
e.g., because of a shift in that matrix; a denial of service
attack or a flash crowd; a routing problem (link flapping). In
most cases, aggregate link statistics are not sufficient to
distinguish between such causes, and to decide on an appropriate
corrective action. For example, if routing over two links is
unstable, and the links flap between being overloaded and
inactive, this might be averaged out in a 5 minute window,
indicating moderate loads on both links.
Baseline PSAMP measurement of the congested link, as described in
Section 11.1, enables measurements that are fine grained in both
space and time. The operator has to be able to determine how
many bytes/packets are generated for each source/destination
address, port number, and prefix, or other attributes, such as
protocol number, MPLS forwarding equivalence class (FEC), type of
service, etc. This allows the precise determination of the
nature of the offending traffic. For example, in the case of a
Distributed Denial of Service(DDoS) attack, the operator would
see a significant fraction of traffic with an identical
destination address.
In certain circumstances, precise information about the spatial
flow of traffic through the network domain is required to detect
and diagnose problems and verify correct network behavior. In
the case of the overloaded link, it would be very helpful to know
the precise set of paths that packets traversing this link
follow. This would readily reveal a routing problem such as a
loop, or a link with a misconfigured weight. More generally,
complex diagnosis scenarios can benefit from measurement of
Duffield (Ed.) Expires December 2008 [Page 29]
Internet Draft Packet Selection and Reporting June 2008
traffic intensities (and other attributes) over a set of paths
that is constrained in some way. For example, if a multihomed
customer complains about performance problems on one of the
access links from a particular source address prefix, the
operator should be able to examine in detail the traffic from
that source prefix which also traverses the specified access link
towards the customer.
While it is in principle possible to obtain the spatial flow of
traffic through auxiliary network state information, e.g., by
downloading routing and forwarding tables from routers, this
information is often unreliable, outdated, voluminous, and
contingent on a network model. For operational purposes, a
direct observation of traffic flow provided by trajectory
sampling is more reliable, as it does not depend on any such
auxiliary information. For example, if there was a bug in a
router's software, direct observation would allow the diagnosis
the effect of this bug, while an indirect method would not.
12. Security Considerations
12.1 Relation of PSAMP and IPFIX Security for Exporting Process
As detailed in Section 4.3, PSAMP shares with IPFIX security
requirements for export, namely, confidentiality, integrity and
authenticity of the exported data; see also Sections 6.3 and 10
of [RFC-3917]. Since PSAMP will use IPFIX for export, it can
employ the IPFIX protocol [RFC-5101] to meet its requirements.
12.2 PSAMP Specific Privacy Considerations
In distinction with IPFIX, a PSAMP device may, in some
configurations, report some number of initial bytes of the
packet, which may include some part of a packet payload. This
option is conformant with the requirements of [RFC-2804] since it
does not mandate configurations that would enable capture of an
entire packet stream of a flow: neither a unit sampling rate (1
in 1 sampling) nor reporting a specific number of initial bytes,
are required by the PSAMP protocol.
To preserve privacy of any users acting as sender or receiver of
the observed traffic the contents of the packet reports must be
able to remain confidential in transit between the exporting
PSAMP device and the collector. PSAMP will use IPFIX as the
exporting protocol, and the IPFIX protocol must provide
mechanisms to ensure confidentiality of the exporting process,
for example, encryption of export packets [RFC-5101].
12.3 Security Considerations for Hash-Based Selection
Duffield (Ed.) Expires December 2008 [Page 30]
Internet Draft Packet Selection and Reporting June 2008
12.3.1 Modes and Impact of vulnerabilities
A concern for Hash-based Selection is whether some large set of
related packets could be disproportionately sampled, either
(i) through unanticipated behavior in the Hash Function, or
(ii) because the packets had been deliberately crafted to have
this property.
As detailed below, only cryptographic hash functions (e.g. one
based on MD5) employing a private parameter are sufficiently
strong to withstand the range of conceivable attacks. However,
implementation considerations may preclude operating the
strongest hash functions at line rate. For this reason PSAMP is
not expected to standardize around a cryptographic hash function
at the present time. The purpose of this section is to inform
discussion of the vulnerabilities and trade-offs associated with
different hash function choices. Section 6.2.2 of [PSAMP-TECH]
does this in more detail.
An attacker able to predict packet sampling outcomes could craft
a packet stream that could evade selection; or another that could
overwhelm the measurement infrastructure with all its packets
being selected. An attacker may attempt to do this based on
knowledge of the hash function. An attacker could employ
knowledge of selection outcomes of a known packet stream to
reverse engineer parameters of the hash function. This knowledge
could be gathered e.g. from billing information, reactions of
intrusion detection systems, or observation of a report stream.
Since hash-based selection is deterministic, it is vulnerable to
replay attacks. Repetition of a single packet may be noticeable
to other measurement methods if employed (e.g. collection of flow
statistics), whereas a set of distinct packets that appears
statistically similar to regular traffic may be less noticeable.
The impact of replay attacks on hash based selection may be
mitigated by repeated changing of hash function parameters.
.
12.3.2 Use of Private Parameters in Hash Functions
Because hash functions for Hash-based selection are to be
standardized and hence public, the packet selection decision must
be controlled by some private quantity associated with the hash-
based Selector. Making private the range of hash values for which
packets are selected is not alone sufficient to prevent an
attacker crafting a stream of distinct packets that are
disproportionately selected. A private parameter must be used
within the hash function, for example, a private modulus in a
Duffield (Ed.) Expires December 2008 [Page 31]
Internet Draft Packet Selection and Reporting June 2008
hash function, or by concatenating the hash input with a private
string prior to hashing.
12.3.3 Strength of Hash Functions
The specific choice of hash function and it usage determines the
types of potential vulnerability:
* Cryptographic hash functions: when a private parameter is used,
future selection outcomes cannot be predicted even by an
attacker with knowledge of past selection outcomes.
* Non-cryptographic hash functions:
Using knowledge of past selection outcomes: some well known
hash functions, e.g., CRC-32, are vulnerable to attacks, in
the sense that their private parameter can be determined
with knowledge of sufficiently many past selections, even
when a private parameter is used; see [GoRe07].
No knowledge of past selection outcomes: using a private
parameter hardened the hash function to classes of attacks
that work when the parameter is public, although
vulnerability to future attacks is not precluded.
12.4 Security Guidelines for Configuring PSAMP
Hash-function parameters configured in a PSAMP device are
sensitive information, which must be kept private. As well as
using probing techniques to discover parameters of non-
cryptographic hash functions as described above, implementation
and procedural weaknesses may lead to attackers discovering
parameters, whatever class of hash function is used. The
following measures may prevent this from occurring:
Hash function parameters must not be displayable in cleartext on
PSAMP devices. This reduces the chance for the parameters to be
discovered by unauthorized access to the PSAMP device.
Hash function parameters must not be remotely set in cleartext
over a channel which may be eavesdropped.
Hash function parameters must be changed regularly. Note that
such changes must be synchronized over all PSAMP devices in a
domain under which Trajectory Sampling is employed in order to
maintain consistent sampling of packets over the domain.
Default hash function parameter values should be initialized
randomly, in order to avoid predictable values that attackers
could exploit.
Duffield (Ed.) Expires December 2008 [Page 32]
Internet Draft Packet Selection and Reporting June 2008
13. IANA Considerations
This document has no actions for IANA.
14. References
14.1 Normative References
[PSAMP-PROTO] B. Claise (Ed.) Packet Sampling (PSAMP) Protocol
Specifications, RFC XXXX. [Currently Internet Draft
draft-ietf-psamp-protocol-09.txt, work in progress,
December 2007.]
[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-08,
February 2008.]
[RFC-5101] B. Claise (Ed.) "Specification of the IP Flow
Information Export (IPFIX) Protocol for the Exchange of
IP Traffic Flow Information'', RFC 5101, January 2008.
[RFC-0791] J. Postel, "Internet Protocol", STD 5, RFC 791,
September 1981.
[RFC-5102] J. Quittek, S. Bryant, B. Claise, P. Aitken, J. Meyer,
"Information Model for IP Flow Information Export", RFC
5102, January 2008.
[RFC-4960] R. Stewart, (ed.) "Stream Control Transmission
Protocol", RFC 4960, September 2007.
[RFC-3758] R. Stewart, M. Ramalho, Q. Xie, M. Tuexen, P. Conrad,
"SCTP Partial Reliability Extension", RFC 3758, May 2004.
[PSAMP-TECH] T. Zseby, M. Molina, F. Raspall, N. G. Duffield, S.
Niccolini, Sampling and Filtering Techniques for IP
Packet Selection, RFC XXXX. [Currently Internet Draft,
draft-ietf-psamp-sample-tech-10.txt, work in progress,
July 2005.
14.2 Informative References
[RFC3704] F. Baker, P. Savola, Ingress Filtering for
Multihomed Networks, RFC3704, March 2004.
Duffield (Ed.) Expires December 2008 [Page 33]
Internet Draft Packet Selection and Reporting June 2008
[RFC-2205] R. Braden (Ed.), L. Zhang, S. Berson, S. Herzog,
S. Jamin, Resource ReSerVation Protocol (RSVP) - Version
1 Functional Specification, RFC2205, September 1997.
[RFC-2460] S. Deering, R. Hinden, Internet Protocol, Version
6 (IPv6) Specification, RFC 2460, December 1998.
[DuGr01] N. G. Duffield and M. Grossglauser, Trajectory
Sampling for Direct Traffic Observation, IEEE/ACM Trans.
on Networking, 9(3), 280-292, June 2001.
[DuGeGr02] 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.
[DuGr04] N. G. Duffield and M. Grossglauser, Trajectory
Sampling with Unreliable Reporting, Proc IEEE Infocom
2004, Hong Kong, March 2004,
[RFC-2914] S. Floyd, Congestion Control Principles, RFC
2914, September 2000.
[GoRe07] S. Goldberg, J. Rexford, "Security
Vulnerabilities and Solutions for Packet Sampling", IEEE
Sarnoff Symposium, Princeton, NJ, May 2007.
[RFC-2804] IAB and IESG, Network Working Group, IETF Policy
on Wiretapping, RFC 2804, May 2000
[RFC-2981] R. Kavasseri, Ed., ''Event MIB'', RFC 2981, October
2000.
[RFC-1213] K. McCloghrie, M. Rose, Management Information
Base for Network Management of TCP/IP-based
internets:MIB-II, RFC 1213, March 1991.
[RFC-3176] P. Phaal, S. Panchen, N. McKee, InMon
Corporation's sFlow: A Method for Monitoring Traffic in
Switched and Routed Networks, RFC 3176, September 2001
[RFC-2330] V. Paxson, G. Almes, J. Mahdavi, M. Mathis,
Framework for IP Performance Metrics, RFC 2330, May 1998
[RFC-768] J. Postel, "User Datagram Protocol" RFC 768,
August 1980
Duffield (Ed.) Expires December 2008 [Page 34]
Internet Draft Packet Selection and Reporting June 2008
[RFC-3917] J. Quittek, T. Zseby, B. Claise, S. Zander,
Requirements for IP Flow Information Export, RFC 3917,
October 2004.
[RFC-4271] Y. Rekhter, T. Li, S. Hares, "A Border Gateway
Protocol 4 (BGP-4)", RFC 4271, January 2006.
[RFC-3031] E. Rosen, A. Viswanathan, and R. Callon,
"Multiprotocol Label Switching Architecture", RFC 3031,
January 2001.
[IPFIX-ARCH] G. Sadasivan, N. Browlee, B. Claise, J.
Quittek, ''Architecture for IP Flow Information Exp'', RFC-
XXXX. [currently internet draft draft-ietf-ipfix-
architecture-12, work in progress, September 2006]
[RFC-2819] S. Waldbusser, ''Remote Network Monitoring
Management Information Base'', RFC 2819, May 2000.
[Zs02] T. Zseby, ``Deployment of Sampling Methods for SLA
Validation with Non-Intrusive Measurements'', Proceedings
of Passive and Active Measurement Workshop (PAM 2002),
Fort Collins, CO, USA, March 25-26, 2002
15. Authors' Addresses
Derek Chiou
Department of Electrical and Computer Engineering
University of Texas at Austin
1 University Station, Stop C0803, ENS Building room 135,
Austin TX, 78712, USA
Phone: +1 512 232 7722
Email: Derek@ece.utexas.edu
Benoit Claise
Cisco Systems
De Kleetlaan 6a b1
1831 Diegem
Belgium
Phone: +32 2 704 5622
Email: bclaise@cisco.com
Nick Duffield
AT&T Labs - Research
Room B139
180 Park Ave
Florham Park NJ 07932, USA
Phone: +1 973-360-8726
Email: duffield@research.att.com
Duffield (Ed.) Expires December 2008 [Page 35]
Internet Draft Packet Selection and Reporting June 2008
Albert Greenberg
One Microsoft Way
Redmond, WA 98052-6399
USA
Phone: +1 425-722-8870
Email: albert@microsoft.com
Matthias Grossglauser
School of Computer and Communication Sciences
EPFL
1015 Lausanne
Switzerland
Email: matthias.grossglauser@epfl.ch
Jennifer Rexford
Department of Computer Science
Princeton University
35 Olden Street
Princeton, NJ 08540-5233, USA
Phone: +1 609-258-5182
Email: jrex@cs.princeton.edu
16. Contributors
Sharon Goldberg contributed to Section 12.3 on security
considerations for hash-based selection.
Sharon Goldberg
Department of Electrical Engineering
Princeton University
F210-K EQuad
Princeton, NJ 08544, USA
Email: goldbe@princeton.edu
17. Acknowledgements
The authors would like to thank Peram Marimuthu and Ganesh
Sadasivan for their input in early versions of this document.
18. Intellectual Property Statements
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
Duffield (Ed.) Expires December 2008 [Page 36]
Internet Draft Packet Selection and Reporting June 2008
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.
19. Copyright Statement
Copyright (C) The IETF Trust (2008).
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.
20. 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, THE
IETF TRUST 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.
Duffield (Ed.) Expires December 2008 [Page 37]