[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits] [IPR]

Versions: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 RFC 5474

INTERNET-DRAFT                                   Nick Duffield (Editor)
draft-ietf-psamp-framework-01.txt                      Albert Greenberg
November 2002                                     Matthias Grossglauser
Expires: May 2003                                      Jennifer Rexford
                                                   AT&T Labs - Research
                                                            Derek Chiou
                                                          Avici Systems
                                                        Peram Marimuthu
                                                       Ganesh Sadasivan
                                                          Cisco Systems

               A Framework for Passive Packet Measurement

    Copyright (C) The Internet Society (2002).  All Rights Reserved.

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at


   A wide range of traffic engineering and troubleshooting tasks rely
   on reliable, timely, and detailed traffic measurements. We describe
   a framework for passive packet measurement that is (a) general
   enough to serve as the basis for a wide range of operational tasks,
   and (b) needs only a small set of packet selection operations that
   facilitate ubiquitous deployment in router interfaces or dedicated
   measurement devices, even at very high speeds.

   Comments on this document should be addressed to the PSAMP WG
   mailing list: psamp@ops.ietf.org
   To subscribe: psamp-request@ops.ietf.org, in body: subscribe
   Archive: https://ops.ietf.org/lists/psamp/

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 1]

Internet-Draft          Passive Packet Measurement         November 2002

0 Contents

   1 Motivation  .................................................  3
   2 Requirements  ...............................................  3
   3 Elements, Terminology, and Architecture  ....................  5
   4 Packet Selection Operations  ................................  7
     4.1 Filtering  ..............................................  7
     4.2 Sampling  ...............................................  7
     4.3 Hashing .................................................  7
     4.4 Selection According to Packet Treatment  ................  8
     4.5 Classification and Relation of Selection Operations  ....  9
     4.6 Proposal on Requirements for Selection Operations  ......  9
   5 Reporting  ..................................................  9
   6 Export and Congestion Avoidance  ............................ 10
     6.1 Collector Destination  .................................. 10
     6.2 Local Export  ........................................... 10
     6.3  Reliable vs. Unreliable Transport  ..................... 11
     6.4 Limiting Delay in Exporting Measurement Packets  ........ 11
     6.5 Configurable Export Rate Limit  ......................... 11
     6.6 Congestion-aware Unreliable Transport  .................. 12
     6.7 Collector-based Rate Reconfiguration  ................... 12
       6.7.1 Changing the Export Rate and Other Rates  ........... 12
       6.7.2 Notions of Fairness  ................................ 13
       6.7.3 Behavior Under Overload and Failure  ................ 13
   7 Parallel Measurement Processes  ............................. 13
   8 Configuration and Management  ............................... 14
   9 Feasibility and Complexity  ................................. 14
     9.1 Feasibility  ............ ............................... 14
       9.1.1 Filtering  .......................................... 14
       9.1.2 Sampling  ........................................... 14
       9.1.3 Hashing  ............................................ 15
       9.1.4 Reporting  .......................................... 15
       9.1.5 Export  ............................................. 15
     9.2 Potential Hardware Complexity  .......................... 15
   10 Applications  .............................................. 16
     10.1 Baseline Measurement and Drill Down  ................... 16
     10.2 Customer Performance  .................................. 17
     10.3 Troubleshooting  ....................................... 17
   11 References  ................................................ 19
   12 Authors' Addresses  ........................................ 20
   13 Intellectual Property Statement  ........................... 21
   14 Full Copyright Statement  .................................. 21

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 2]

Internet-Draft          Passive Packet Measurement         November 2002

1 Motivation

   This document describes a framework in which to define a standard
   set of capabilities for network elements to sample subsets of
   packets by statistical and other methods. The framework will
   accommodate future work to (i) specify a set of selection
   operations by which packets are sampled (ii) specify the
   information that is to be made available for reporting on sampled
   packets; (iii) describe protocols by which information on sampled
   packets is reported to applications; (iv) describe protocols by
   which packet selection and reporting are configured.

   The motivation to standardize these capabilities 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, the manner
   in which the resulting measurements are presented, and
   consequently, consistency of the interpretation that can be put on

   The capabilities are positioned as suppliers of packet samples to
   higher level consumers, including both remote collectors and
   applications, and on board measurement-based applications.  Indeed,
   development of the standards within the framework described here
   should be open to influence by the requirements of standards in
   related IETF WGs, for example, IP Performance Metrics (IPPM)
   [PAMM98] and Internet Traffic Engineering (TEWG) [LCTV02].
   Conversely, we expect that aspects of this framework not
   specifically concerned with the central issue of packet selection
   may be able to leverage work in other WGs. Potential examples are
   the format and export of measurement reports, which may leverage
   the work in IP Flow Information Export (IPFIX) [QZCZCN02], and work
   in congestion aware unreliable transport in the Datagram Congestion
   Control Protocol (DCCP) [FHK02].

2 Requirements

   The broad requirements for the measurement capabilities are:

   * Ubiquity: The capabilities must be simple enough to be
       implemented ubiquitously at maximal line rate. In particular,
       they must involve only minimal per-packet processing and
       require only minimal additional state. Capabilities should not
       be tightly integrated with other packet control actions such as
       policing, marking, shaping, and queueing.

   * Applicability: the set of selection operations must be rich
       enough to support a range of existing and emerging measurement
       based applications and protocols. The standard will have to
       find a workable trade-off between the range of traffic
       engineering applications and operational tasks it enables, and
       the complexity of the set of capabilities.

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 3]

Internet-Draft          Passive Packet Measurement         November 2002

   * Timeliness: reports on selected packets should be made available
       to the collector quickly enough to support real time

   * Transparency: allow transparent interpretation of measurements as
       communicated by PSAMP reporting, without need to obtain
       additional information from the measuring device.

   * Robustness: allow robust interpretation of measurements with
       respect to reports missing due to loss, e.g. in transport, or
       omission at the measurement device. Inclusion in reporting of
       information enabling accuracy of measurements to be determined.

   * Privacy: selection of the content of packet reports will be
       cognizant of privacy and anonymity issues while being
       responsive to the needs of measurement applications, and in
       accordance with RFC 2804.  Full packet capture of arbitrary
       packet streams is explicitly out of scope.

   * Faithfulness: all reported quantities that relate to the packet
       treatment must reflect the router state and configuration
       encountered by the packet in the PSAMP device.

   * Configuration: ease of configuration of sampling and export
       parameters, e.g. for automated remote reconfiguration in
       response to measurements.

   * Security: the use of secure means of configuration and reporting,
       and robustness of packet selection w.r.t. attempts to evade

   * Extensibility: to allow for additional packet selection
       operations to support future applications.

   * Flexibility: to support measurement of packets using different
       network protocols or encapsulation layers (e.g. IPv4, IPv6,
       MPLS, etc), and under packet encryption.

   * Parallel measurements: support multiple independent measurements
       at the same device, each possibly with different selection,
       reporting and export configuration.

   * Congestion Avoidance: export of a report stream across a network
       must be congestion avoiding in compliance with RFC 2914.

   Reuse of existing protocols will be encouraged provided the
   protocol capabilities are compatible with the above requirements.

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 4]

Internet-Draft          Passive Packet Measurement         November 2002

3 Elements, Terminology, and Architecture

   This section defines the basic elements of the PSAMP framework.

   * PSAMP Device: a device hosting at least an observation point and
       a measurement process.

   * Observation Point: The observation point is a location in the
       network where packets can be observed. Examples are, a line
       to which a probe is attached, a shared medium, such as an
       Ethernet-based LAN, a single port of a router, or set of
       interfaces (physical or logical) of a router, an embedded
       measurement subsystem within an interface.

   * Measurement Process: a packet measurement process comprising the
       following: a selection process, a reporting process, and an
       export process.

   * Selection Process: A selection process selects packets for
       reporting at an observation point. The inputs to the selection
       process are the packets observed at the observation point
       (including packet encapsulation headers), information derived
       from the packets' treatment at the observation point, and
       selection state that may be maintained by the observation
       point. Selection is accomplished through operating on these
       inputs with one or more selection operations.

   * Selection Operation: A configurable packet selection operation.
       It takes as input the selection process input for a single
       packet. The output is a binary outcome of whether or not the
       packet was sampled. Selection operations may also change the
       selection state.

   * Selection State: the observation point may maintain state
       information for use by the reporting process, and/or by
       multiple selection operations, either on the same packet, or on
       different packets. Examples include counters, timestamps,
       iterators for pseudorandom number generators, calculated hash
       values, and indicators of whether a packet was selected by a
       given selection operation.

   * Composite Selection Operation: a selection operation that is
       expressed as a combination of other selection operations. A
       packet deemed selected by the composite operation if it is
       selected by all its constituent selection operations.

   * Reporting Process: the creation of a report stream of information
       on packets selected by a selection process, in preparation for
       export. The input to a reporting process comprises that
       information available to a selection process, for the selected
       packets.  The report stream contains two distinguished types of
       information: packet reports, and report interpretation.

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 5]

Internet-Draft          Passive Packet Measurement         November 2002

   * Packet Reports: a configurable subset of the per packet input to
       the reporting process.

   * Report Interpretation: subsidiary information relating to, and
       used for the interpretation the reports on, one or more
       packets. Examples include counters, and configuration parameters
       of the PSAMP device, and the selection and reporting process.

   * Export Process: sends the output of the reporting process
       from the PSAMP device to one or more collectors.

   * Collector: a collector receives a report stream exported by one
       or more measurement processes. The collector may or may not be
       co-located with the PSAMP device.

   * Measurement packets: report interpretation and/or one or more
       packet reports are bundled by the export process into a
       measurement packet for export to a collector.

   * Parallel Measurement Processes: a given PSAMP device may host
       multiple independent measurement processes, each with
       potentially different constituent selection, reporting and
       export processes, and destination collectors. The parallel
       processes may or may not use derive their input from the same
       observation point.

   The various possibilities for the high level architecture of these
   elements is as follows. Note in the last case: the PSAMP device may
   also be a collector.

   +---------------------+                 +------------------+
   |PSAMP Device(1)      |                 | Collector(1)     |
   |[Obsv. Point(s)]     |                 |                  |
   |[Meas. Process(1)]<--+---------------->|                  |
   |[Meas. Process(2)]<--+-----------+---->|                  |
   |[Meas. Process(3)]<--+--------+  |     |                  |
   +---------------------+        |  |     +------------------+
                                  |  |
   +---------------------+        |  |     +------------------+
   |PSAMP Device(2)      |        |  +---->| Collector(2)     |
   |[Obsv. Point(s)]     |        +------->|                  |
   |[Meas. Process(4)]<--+---------------->|                  |
   +---------------------+                 +------------------+

   +---------------------+                 +------------------+
   |PSAMP Device(3)      |                 | Collector(3)     |
   |[Obsv. Point(s)]     |                 |                  |
   |[Meas. Process(5)]<--+---------------->|                  |
   |[Meas. Process(6)]<--+---\             +------------------+

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 6]

Internet-Draft          Passive Packet Measurement         November 2002

4 Packet Selection Operations

   The function of packet selection is to select a subset out of the
   stream of all packets.  Selection may be used to select a subset of
   packets of interest based on their content, and/or to reduce the
   rate of packets into the measurement flow regardless of
   content. This section details some candidate operations for
   standardization. No restriction on the allowed combination of these
   into composite selection operations is imposed in this
   document. Packet selection techniques are discussed in [ZMR02].

   4.1 Filtering

   Filtering can be accomplished by applying deterministic operations,
   such as match/mask, to any combination of bit positions in the
   generic selection function input. Higher level interfaces to the
   match/mask operations may be used to specify mask and matches for
   particular fields, for example, for IP addresses and/or TCP/UDP
   port numbers.

   4.2 Sampling

   In current practice, sampling has been performed using particular
   algorithms, e.g., (i) pseudorandomly independent sampling with
   probability 1/N; (ii) periodic sampling of every Nth packet. The
   aim is to select packets representatively in conformance with some
   desired probabilistic selection law. Examples of selection laws are
   selecting packets (i) with long term probability 1/N; (ii)
   independently with probability 1/N; (iii) n out of every m packets
   independently; (iv) by importance, non-uniformly according to field
   contents, e.g. sample larger packets or certain protocols more
   frequently. A given sampling algorithm will reproduce the selection
   law if the packets under observation conform to a certain
   probabilistic content law. Examples of content laws are (i)
   correlations between contents of different packets decay at a
   specified rate; (ii) the contents of certain complimentary
   subfields are significantly variable and essentially uncorrelated.

   It follows that the extent to which sampling algorithms should be
   realized as distinct selection operations depends on the functional
   requirements, as expressed by the selection laws that are desired
   and the content laws that one is prepared to assume. For example,
   under the content law that correlations between packet contents
   vanish for packets separated by at least N-1 positions in the
   packet stream, then sampling every Nth packet periodically yields
   the same selection law as sampling independently with probability
   1/N. With a weaker content law (i.e. admitting stronger

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 7]

Internet-Draft          Passive Packet Measurement         November 2002

   correlations between packets), then only the long term selection
   probabilities may be 1/N.  One task for the work under the PSAMP
   framework will be to decide the appropriate level of functional
   granularity, e.g. whether to distinguish periodic from pseudorandom
   sampling as a packet selection operations, or to regard them only
   as different possible implementations of the same packet selection

   Sampling at full line rate, i.e. with probability 1, is not
   excluded in principle, although resource constraints may not
   support it in practice.

   4.3 Hashing

   A hashing function operates on the selection function input for a
   packet, and associates the resulting hash with the packet.  Bit
   positions can be excluded from the input to the hashing function by
   masking. This ability would be used, for example, by applications
   that require the hash to be independent on packet header fields,
   such as TTL or header CRC, that are mutable on its passage through
   the network.

   Packets may be selected by filtering on the hash value, this
   regarded as part of the selection state.  Although hashing and
   filtering are deterministic operations, a good choice of the hash
   function and its inputs should yield a selection law that is almost
   indistinguishable from independent sampling (for a given subfield
   of the packet) given an appropriate content law (that the contents
   of complimentary subfields are sufficiently uncorrelated and

   At the application level, hash-based sampling is of interest since
   using the same hash functions at different PSAMP devices satisfies
   a functional requirement that the same sampling decision be made on
   a given packet observed at different devices; in [DuGr01] this is
   called Trajectory Sampling. It enables reconstruction of the
   network paths followed by individual packets, from packet reports
   exported from different PSAMP devices. In this application, a
   second distinct hash, called the label hash, may be calculated for
   selected packets in order to identify them at the collector. PSAMP
   devices are expected to be able to use a more complex hash for this
   second purpose, since it is only applied to the reduced set of
   selected packets.

   Calculating and reporting a set of hashes for all packets
   (i.e. without selecting a subset) would be required in order to
   support some packet tracing applications; see [SPSJTKS01].

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 8]

Internet-Draft          Passive Packet Measurement         November 2002

   4.4 Selection According to Packet Treatment

   Router architectural considerations may preclude some information
   concerning the packet treatment, e.g routing state, being available
   at line rate for selection of packets. However, if selection not
   based on routing state has reduced down from line rate,
   subselection based on routing state may be feasible.

   4.5 Classification and Relation of Selection Operations

   From the above examples, it is clear that notions of sampling,
   filtering and hashing are not distinct. For example: (i) sampling
   can be accomplished by hashing and filtering; and (ii) since a
   sampling selection law can depend on packet content, filtering can
   be regarded as a degenerate case of sampling, although it does not
   appear useful to do so. For this reason, it is likely to be more
   fruitful to standardize selection operations according to agreed
   functional requirements, than to strive to define a non-overlapping
   classification of selection operations.

   4.6 Proposal on Requirements for Selection Operations

   Section 10 describes potential PSAMP applications. These would be
   supported by the following set of selection operations:

   (i) filtering by match/mask to support drill down
   (ii) hash-based sampling to support Trajectory Sampling
   (iii) independent sampling method to support widespread baselineing

5 Reporting

   Information eligible for inclusion in packet reports includes (i)
   the packet content itself (including encapsulating headers); (ii)
   information relating to the packet treatment: incoming and outgoing
   interfaces, subinterfaces and channel identifiers, routing state
   applied to or derived from the packet e.g. next hop IP address,
   routing prefixes, source and destination AS numbers; (iii)
   selection state associated with the packet, e.g. timestamps,
   counters, hash values.

   In order to satisfy the requirement of ubiquity, it may be
   necessary to admit different levels of reporting. Concerning the
   packet content: some devices may not have the resource capacity or
   functionality to identify all fields within a packet. Concerning
   packet treatment: routing state is unlikely to be available on
   devices that do not route. At a minimum, all PSAMP devices must
   support simple reporting of packet content, specifically of some
   number of bytes contiguous packet bytes, as measured from an
   offset. In this style of reporting, the burden of interpretation is
   placed at the collector or applications that it supplies. More
   detailed reporting, by fields of specific protocols, is desirable
   where feasible.

Duffield et. al.     draft-ietf-psamp-framework-01.txt          [Page 9]

Internet-Draft          Passive Packet Measurement         November 2002

   Information for use in report interpretation includes (i)
   configuration parameters of the selectors of the packets reported
   on; (ii) format of the packet reports (iii) configuration
   parameters and state information of the network element; (iv)
   quantities (e.g. sequence numbers) that enable collectors and
   applications to infer attained packet sampling rates, detect
   loss during selection, report loss in transmission, and correct for
   information missing from the packet report stream; (v) indication
   of the inherent accuracy of the reported quantities, e.g., of

   The requirements for robustness and transparency are motivations
   for including report interpretation in the report stream. Inclusion
   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 selection configuration, and
   leaves an architectural hostage for network management systems to
   coherently manage both configuration and data collection.

   It is not envisaged that all report interpretation be included in
   every report. Many of the quantities listed above are expected to
   be relatively static; they could be communicated periodically, and
   upon change.

   To conserve network bandwidth and resources at the collector, the
   PSAMP device may compress the measurement records before export.
   Compression should 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 reports. Any consequent
   delay should not violate the timeliness requirement for
   availability of packet reports at the collector.

6 Export and Congestion Avoidance

   6.1 Collector Destination

   At least when exporting to a remote collector, the export process
   is configured to transmit to the collector, as identified by IP
   address and port number.

   6.2 Local Export

   The report stream may be directly exported to on-board measurement
   based applications, for example those that for composite statistics
   from more than one packet. Local export may be presented through an
   interface direct to the higher level applications, i.e., without
   employing the transport used for off-board export.

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 10]

Internet-Draft          Passive Packet Measurement         November 2002

   6.3  Reliable vs. Unreliable Transport

   The export of the report stream does not does require reliable
   export. On the contrary, retransmission of lost measurement packets
   consumes additional network resources and require maintenance of
   state by the export process. The PSAMP device would have to be
   addressable, and able to receive and process acknowledgments, and to
   store unacknowledged data.  These requirements would be a
   significant impediment to having ubiquitous support PSAMP.

   Instead, it is proposed that PSAMP devices support an unreliable
   export mechanism.  Sequence numbers on the measurement packets would
   indicate when loss has occurred, and the analysis of the collected
   measurement data can account for this loss.  In some sense, packet
   loss becomes another form of sampling (albeit a less desirable, and
   less controlled, form of sampling).

   6.4 Limiting Delay in Exporting Measurement Packets

   The device may queue the report stream in order to export multiple
   records in a single measurement. Any consequent delay should not
   violate the timeliness requirement availability of packet reports
   at the collector.

   6.5 Configurable Export Rate Limit

   The export process must be able to limit its export rate; otherwise
   it could overload the network and/or the collector. (Note this
   problem would be exacerbated if using reliable transport mode,
   since the PSAMP device  would retransmit any lost packets,
   thereby imposing an additional load on the network).

   At times, the device may generate new records faster than the
   allowed export rate.  In this situation, the device should discard
   the excess records rather than transmitting them to the collection
   system.  The device may record information (such as sequence
   numbers, or packet and byte counter values accumulated at the
   inputs and outputs of a packet selector) to aid the collection
   system in compensating for the missing data in any subsequent

   The export rate must be configurable per export process. Note that
   since congestion loss can occur at any link on the export path, it
   is not sufficient to limit rate simply as a function of the
   bandwidth of the interface out of which export takes place.

   A candidate for implementation of rate limiting is the leaky
   bucket, with tokens corresponding e.g. to bytes or packets.

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 11]

Internet-Draft          Passive Packet Measurement         November 2002

   6.6 Congestion-aware Unreliable Transport

   Exported measurement traffic competes for resources with other
   Internet transfers.  Congestion-aware export is important to ensure
   that the measurement records do not overwhelm the capacity of the
   network or unduly degrade the performance of other applications,
   while making good use of available bandwidth resources.

   The PSAMP WG will evaluate (at least) the following alternatives
   for congestion aware unreliable transport:

   (i) protocols under development, including the Datagram Congestion
   Control Protocol (DCCP); see [FHK02]
   (ii) protocols adopted in the future by the IPFIX WG,
   (iii) collector-based rate reconfiguration, as now described.

   6.7 Collector-based Rate Reconfiguration

   Since collector-based rate reconfiguration is a new proposal, this
   draft will discuss it in some detail.

   The collector can detect congestion loss along the path from the
   PSAMP device through lost packets, manifest as gaps in the sequence
   numbers, or the absence of packets for a period of time. The server
   can run an appropriate congestion-control algorithm to compute a
   new export rate limit, then reconfigure the PSAMP device with the
   new rate.  This is an attractive alternative to requiring the PSAMP
   device to receive acknowledgment packets.  Implementing the
   congestion control algorithm in the collection server has the added
   advantages of flexibility in adapting the sending rate and the
   ability to incorporate new congestion-control algorithms as they
   become available.

   6.7.1 Changing the Export Rate and Other Rates

   Forcing the PSAMP device to discard excess records is an effective
   control under short term congestion. Alternatively, the device
   could be reconfigured to select fewer packets, and/or send smaller
   reports on each selected packet. This may be a more appropriate
   reaction to long-term congestion. In some cases, a collection
   server may receive measurement records from more than one device,
   and could decide to reduce the export or other rates at one device
   rather than another, in order to prioritize the measurement data.
   This type of flexibility is valuable for network operators that
   collect measurement data from multiple locations to drive multiple

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 12]

Internet-Draft          Passive Packet Measurement         November 2002

   6.7.2 Notions of Fairness

   In some cases, it may be reasonable to allow the collection server
   to have flexibility in deciding how aggressively to respond to
   congestion.  For example, the PSAMP device and the collection
   server may have a very small round-trip time relative to other
   traffic.  Conventional TCP-friendly congestion control would
   allocate a very large share of the bandwidth to this traffic.
   Instead, the collection server could apply an algorithm that reacts
   more aggressively to congestion to give a larger share of the
   bandwidth to other traffic (with larger RTTs). In other cases, the
   measurement records may require a larger share of the bandwidth
   than other flows.  For example, consider a link that carries tens
   of thousands of flows, including some non TCP-friendly DoS attack
   traffic.  Restricting the PSAMP traffic to a fair share allocation
   may be too restrictive, and might limit the collection of the data
   necessary to diagnose the DoS attack. In order to maintain report
   collection during periods of congestion, PSAMP report streams may
   claim more than a fair share of link bandwidth, provided the number
   of report streams in competition with fair sharing traffic is
   limited. The collection server could also employ policies that
   allocate bandwidth in certain proportions amongst different
   measurement processes.

   6.7.3 Behavior Under Overload and Failure

   The congestion control algorithm has to be robust to severe
   overload or complete loss of connectivity between the device and
   the collection system, and also to the failure of the device or the
   collection system. For example, in a scenario where the collection
   system is unable to reconfigure the export rate because of loss of
   reverse (collection system to device) connectivity, it is desirable
   that the device reduce the export rate automatically. Similarly, if
   no measurement reports reach the collection system because of loss
   of forward connectivity, the collection system should not react to
   this by increasing the export rate. This problem may be solved
   through periodic heartbeat packets in both directions (i.e.,
   measurement reports in the forward direction, configuration refresh
   messages in the reverse direction). This allows each side to
   detect a loss in connectivity or outright failure and to react

7 Parallel Measurement Processes

   Because of the increasing number of distinct measurement
   applications, with varying requirements, it is desirable to set up
   parallel measurement processes on a stream of packets.  Each
   process should consist of independently-configurable selection,
   reporting and export processes.

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 13]

Internet-Draft          Passive Packet Measurement         November 2002

   Each of the parallel measurement processes should be, as far as
   possible, 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 information flow; other information flows need
   only report that they selected the packet. The priority amongst
   information flows to report packets must be configurable.

   It is not proposed to standardize the number of parallel
   measurement processes available.

8 Configuration and Management

   A key requirement for PSAMP is the easy reconfiguration of
   parameters the parameters of the measurement process: those for
   selection, packet reports and export. Examples are (i) support of
   measurement based applications that want to drill-down on traffic
   detail in real-time; (ii) collector-based rate reconfiguration.

   To facilitate reconfiguration and retrieval of parameters, they are
   to reside in a Management Information Base (MIB). CLI and SNMP
   access to these parameters must be available.

9 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.

   9.1 Feasibility

   9.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.

   9.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) are also straightforward given a small number of them.

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 14]

Internet-Draft          Passive Packet Measurement         November 2002

   9.1.3 Hashing

   Hashing functions vary greatly in complexity.  Execution of a small
   number of sufficient simple hash functions is implementable at line

   9.1.4 Reporting

   The simplest packet report would duplicate the first n bytes of the
   packet. However, such an uncompressed format may tax the bandwidth
   capabilities of the PSAMP device for high sampling rates; reporting
   selected fields would save on bandwidth within the PSAMP
   device. Thus there is a trade-off between simplicity and bandwidth
   limitations within the PSAMP device.

   9.1.5  Export

   Ease of exporting measurement packets depends on the system
   architecture. Most systems should be able to support PSAMP export
   by insertion of measurement packets, even through the software

   9.2 Potential Hardware Complexity

   We now comment on the complexity of possible hardware
   implementations. Achieving low constants for performance while
   minimizing hardware resources is, of course, a challenge,
   especially at very high clock frequencies. Most of these
   operations, however, are very basic and their implementations very
   well understood; in fact, the average ASIC designer simply uses
   canned library instances of these operations rather then 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(lg(M)) stages of logic, where M is the
   number of bits involved in the comparison.  The lg(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(lg(M)) stages
   of logic operation. Optimized implementations of arithmetic

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 15]

Internet-Draft          Passive Packet Measurement         November 2002

   operations are also O(lg(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 technique.  Thus, the
   increment/decrement is also an O(lg(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(lg(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 from
   ubiquitous use at full line rate. This motivates exploring the use
   of selection hash functions with complexity somewhere between that
   of MD5 and CRC. However, identification hashing with MD5 on only
   selected packets is feasible at a sufficiently low sampling rate.

10 Applications

   We first describe several representative operational applications
   that require traffic measurements at various levels of temporal and
   spatial granularity enabled by a PSAMP device.

   10.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 such that each packet entering the
   network is seen at least once, for example, on all ingress and
   egress links. Unfiltered sampling with a relatively low rate
   establishes baseline measurements of the network traffic. 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 sampled traffic volumes through division by
   either the target sampling rate, or the attained sampling rate (as
   derived by interface packet counters included in the report stream)

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 16]

Internet-Draft          Passive Packet Measurement         November 2002

   Suppose an operator or a measurement based application detects an
   interesting subset of traffic identified by a particular packet
   attribute. Real-time drill-down to that subset is achieved by
   instantiating a new measurement process at the PSAMP device from
   which the subset was reported. The selection process of the new
   measurement process filters according to the attribute of interest,
   and composes with sampling if necessary to manage the rate of
   packet selection.

   10.2 Customer Performance

   Hash-based 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 SLAs, and
   troubleshooting following a customer complaint.

   In this application, Trajectory Sampling is enabled at all ingress
   and egress interfaces. The label hash is used to match up ingress
   and egress samples. Rates of loss in transit between ingress and
   egress are estimated from the proportion of trajectories for which
   no egress report is received. Note loss of customer packets is
   distinguishable from loss of packet reports through use of report
   sequence numbers. Assuming synchronization of clock between PSAMP
   devices, delay of customer traffic across the network may also be

   Extending hash-sampling to all interfaces in the network would
   enable attribution of poor performance to individual network links.

   10.3 Troubleshooting

   PSAMP 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 and vendor-specific

   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.

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 17]

Internet-Draft          Passive Packet Measurement         November 2002

   Baseline PSAMP measurement the congested link, as described in
   Section 10.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 to pinpoint precisely the nature of the offending
   traffic. For example, in the case of a 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 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 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 to diagnose
   the effect of this bug, while an indirect method would not.

   Trajectory sampling by enabling common hash-based sampling on all
   routers in a domain supports such diagnoses. In particular, routing
   loops are revealed as cycles in trajectories.

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 18]

Internet-Draft          Passive Packet Measurement         November 2002

11 References

   [B88] R.T. Braden, A pseudo-machine for packet monitoring and
   statistics, in Proc ACM SIGCOMM 1988

   [DuGr01] N. G. Duffield and M. Grossglauser, Trajectory Sampling for
   Direct Traffic Observation, IEEE/ACM Trans. on Networking, 9(3), pp.
   280-292, June 2001.

   [FHK02] S. Floyd, M. Handley. E. Kohler, Problem Statement for
   DCCP, Internet Draft draft-ietf-dccp-problem-00.txt, work in
   progress, October 2002.

   [LCTV02] W.S. Lai, B.Christian, R.W. Tibbs, S. Van den Berghe, A
   Framework for Internet Traffic Engineering Measurement, Internet
   Draft draft-ietf-tewg-measure-03.txt, work in progress, September

   [PAMM98] V. Paxson, G. Almes, J. Mahdavi, M. Mathis,  Framework for
   IP Performance Metrics, RFC 2330, May 1998

   [QZCZCN02] J. Quittek, T. Zseby, B. Claise, S. Zander, G. Carle,
   K.C. Norseth,  Requirements for IP Flow Information Export,
   Internet Draft draft-ietf-ipfix-reqs-06.txt, work in progress,
   October 2002.

   [SPSJTKS01] A. C. Snoeren, C. Partridge, L. A. Sanchez, C. E. Jones,
   F. Tchakountio, S. T. Kent, W. T. Strayer, Hash-Based IP Traceback,
   Proc. ACM SIGCOMM 2001, San Diego, CA, September 2001.

   [ZMR02] T. Zseby, M. Molina, F. Raspall, Sampling and Filtering
   Techniques for IP Packet Selection, Internet Draft
   draft-ietf-psamp-sample-tech-00.txt, work in progress, October

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 19]

Internet-Draft          Passive Packet Measurement         November 2002

12 Authors' Addresses

   Nick Duffield
   AT&T Labs - Research
   Room B-139
   180 Park Ave
   Florham Park NJ 07932, USA
   Phone: +1 973-360-8726
   Email: duffield@research.att.com

   Albert Greenberg
   AT&T Labs - Research
   Room A-161
   180 Park Ave
   Florham Park NJ 07932, USA
   Phone: +1 973-360-8730
   Email: albert@research.att.com

   Matthias Grossglauser
   AT&T Labs - Research
   Room A-167
   180 Park Ave
   Florham Park NJ 07932, USA
   Phone: +1 973-360-7172
   Email: mgross@research.att.com

   Jennifer Rexford
   AT&T Labs - Research
   Room A-169
   180 Park Ave
   Florham Park NJ 07932, USA
   Phone: +1 973-360-8728
   Email: jrex@research.att.com

   Derek Chiou
   Avici Systems
   101 Billerica Ave
   North Billerica, MA 01862
   Phone: +1 978-964-2017
   Email: dchiou@avici.com

   Peram Marimuthu
   Cisco Systems
   170, W. Tasman Drive
   San Jose, CA 95134
   Phone: (408) 527-6314
   Email: peram@cisco.com

   Ganesh Sadasivan
   Cisco Systems
   170 W. Tasman Drive
   San Jose, CA 95134
   Phone: (408) 527-0251
   Email: gsadasiv@cisco.com

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 20]

Internet-Draft          Passive Packet Measurement         November 2002

13 Intellectual Property Statement

   AT&T Corp. may own intellectual property applicable to this
   contribution. AT&T is currently reviewing its licensing intent
   relative to the Intellectual Property and will notify the IETF when
   AT&T has made a determination of that intent.

14 Full Copyright Statement

   Copyright (C) The Internet Society (1999).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain
   it or assist in its implementation may be prepared, copied,
   published and distributed, in whole or in part, without restriction
   of any kind, provided that the above copyright notice and this
   paragraph are included on all such copies and derivative works.
   However, this document itself may not be modified in any way, such
   as by removing the copyright notice or references to the Internet
   Society or other Internet organizations, except as needed for the
   purpose of developing Internet standards in which case the
   procedures for copyrights defined in the Internet Standards process
   must be followed, or as required to translate it into languages
   other than English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on

Duffield et. al.     draft-ietf-psamp-framework-01.txt         [Page 21]

Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/