INTERNET-DRAFT                                            Nick Duffield
draft-ietf-psamp-framework-02.txt                      Albert Greenberg
March 2003                                        Matthias Grossglauser
Expires: September 2003                                Jennifer Rexford
                                                   AT&T Labs - Research
                                                            Derek Chiou
                                                          Avici Systems
							  Benoit Claise
							Peram Marimuthu
                                                       Ganesh Sadasivan
                                                          Cisco Systems
                                                         

               A Framework for Passive Packet Measurement


    Copyright (C) The Internet Society (2003).  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-
   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.

Abstract

   A wide range of traffic engineering and troubleshooting tasks rely
   on timely and detailed traffic measurements that can be
   consistently interpreted. 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-02.txt          [Page 1]

Internet-Draft          Passive Packet Measurement            March 2003

0 Contents

   1 Motivation  .................................................  3
   2 Elements, Terminology, and Architecture  ....................  4
   3 Requirements  ...............................................  6  
     3.1 Selection Process Requirements  .........................  6
     3.2 Reporting Process Requirements  .........................  7
     3.3 Export Process Requirements  ............................  7
     3.4 Configuration Requirements  .............................  7
   4 Packet Selection ............................................  8
     4.1 Filtering  ..............................................  8
     4.2 Systematic Sampling  ....................................  8
     4.3 Random Sampling  ........................................  8
       4.3.1 Uniform Random Sampling  ............................  8 
       4.3.2 Stratified Random Sampling  .........................  9 
       4.3.3 Non-uniform Independent Random Sampling  ............  9 
     4.4 Hash-based Selection  ...................................  9
       4.3.1 Consistent Flow Sampling  ........................... 10 
       4.3.2 Trajectory Sampling  ................................ 10 
     4.5 Generation of Pseudorandom Variates  .................... 11
     4.6 Criteria for Choice of Selection Operations  ............ 11
       4.6.1 Evaluating the Need for Distinct Selection Operations 11 
       4.6.2 Comparison of Uniform Sampling Methods  ............. 12 
     4.7 Constraints on the Sampling Rate  ....................... 12
     4.8 Selection According to Packet Treatment  ................ 12
     4.9 Input Sequence Numbers for Primitive Selection Operations 12
     4.10 Selection Operations and Application Requirements  ..... 13
       4.10.1 Mandatory Selection Operations  .................... 13 
       4.10.2 Recommended Selection Operations  .................. 13 
       4.10.3 Optional Selection Operations  ..................... 14
   5 Reporting  .................................................. 14
     5.1 Mandatory Reporting  .................................... 14
     5.2 Recommended Reporting  .................................. 15
     5.3 Report Interpretation  .................................  15
   6 Export and Congestion Avoidance  ............................ 16
     6.1 Collector Destination  .................................. 16
     6.2 Local Export  ........................................... 16
     6.3 Reliable vs. Unreliable Transport  ...................... 16
     6.4 Limiting Delay in Exporting Measurement Packets  ........ 17
     6.5 Configurable Export Rate Limit  ......................... 17
     6.6 Congestion-aware Unreliable Transport  .................. 17
     6.7 Collector-based Rate Reconfiguration  ................... 18
       6.7.1 Changing the Export Rate and Other Rates  ........... 18
       6.7.2 Notions of Fairness  ................................ 18
       6.7.3 Behavior Under Overload and Failure  ................ 19
   7 Parallel Measurement Processes  ............................. 19
   8 Configuration and Management  ............................... 19
   9 Feasibility and Complexity  ................................. 20
     9.1 Feasibility  ............ ............................... 20
       9.1.1 Filtering  .......................................... 20 
       9.1.2 Sampling  ........................................... 20 
       9.1.3 Hashing  ............................................ 20 

Duffield et. al.     draft-ietf-psamp-framework-02.txt          [Page 2]

Internet-Draft          Passive Packet Measurement            March 2003

       9.1.4 Reporting  .......................................... 20
       9.1.5 Export  ............................................. 21 
     9.2 Potential Hardware Complexity  .......................... 21 
   10 Applications  .............................................. 22
     10.1 Baseline Measurement and Drill Down  ................... 22
     10.2 Passive Customer Performance Measurements  ............. 23
     10.3 Troubleshooting  ....................................... 23
   11 References  ................................................ 24
   12 Authors' Addresses  ........................................ 25
   13 Intellectual Property Statement  ........................... 26
   14 Full Copyright Statement  .................................. 27








   

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 a protocol by which information on sampled
   packets is reported to applications; (iv) describe a protocol 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
   them.

   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
   and report formation may be able to leverage work in other
   WGs. Potential examples are the format and export of measurement

Duffield et. al.     draft-ietf-psamp-framework-02.txt          [Page 3]

Internet-Draft          Passive Packet Measurement            March 2003

   reports, which may leverage the information model and export
   protocols of IP Flow Information Export (IPFIX) [QZCZCN02], and
   work in congestion aware unreliable transport in the Datagram
   Congestion Control Protocol (DCCP) [FHK02].


2 Elements, Terminology, and Architecture

   This section defines the basic elements of the PSAMP framework.

   * PSAMP Device: a device hosting at least one of each of the
       following: an observation point, a measurement process, and an
       export 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: the combination of a selection process
       followed by a reporting 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. If the packet is selected, this same information may be
       considered as the output. Selection operations may 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 sequence numbers of packets
       at the input of packet selectors, 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 an ordered composition of other selection
       operations. Thus a packet is selected by the composite
       operation if it is selected by all its constituent selection

Duffield et. al.     draft-ietf-psamp-framework-02.txt          [Page 4]

Internet-Draft          Passive Packet Measurement            March 2003

       operations in order. 

   * Primitive Selection Operation: a selection operation that is not
       a composite of other selection operations.

   * Reporting Process: the creation of a report stream of information
       on packets selected by a selection processes, 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.

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

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

   * Export Process: sends the output of one or more 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. In some cases, the PSAMP device
       may serve as the collector.

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

   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.

   OP = Observation Point, MP = Measurement Process, EP = Export Process

   +---------------------+                 +------------------+
   |PSAMP Device(1)      |                 | Collector(1)     |
   |Observation Point(s) |                 |                  |
   |MP(s)--->EP----------+---------------->|                  |    
   |MP(s)--->EP----------+-------+-------->|                  |
   +---------------------+       |         +------------------+
                                 |    
   +---------------------+       |         +------------------+
   |PSAMP Device(2)      |       +-------->| Collector(2)     |
   |Observation Point(s) |                 |                  |
   |MP(s)--->EP----------+---------------->|                  |
   +---------------------+                 +------------------+
                                   
   +---------------------+         

Duffield et. al.     draft-ietf-psamp-framework-02.txt          [Page 5]

Internet-Draft          Passive Packet Measurement            March 2003

   |PSAMP Device(3)      |         
   |Observation Point(s) |         
   |MP(s)--->EP---+      |         
   |              |      |         
   |Collector(3)<-+      |
   +---------------------+  


3 Requirements   

   3.1 Selection Process Requirements.

   * Ubiquity: The selection operations must be simple enough to be
       implemented ubiquitously at maximal line rate. 

   * Applicability: the set of selection operations 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. 

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

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

   * Visibility: robustness of packet selection w.r.t. attempts to evade
       measurement.
  
   * Parallel measurements: support multiple independent measurement
       processes at the same device.

   * Non-contingency: in order to satisfy the ubiquity requirement,
       the selection decision for each packet must not depend on
       future packets.  Rather, the selection decision must be capable
       of being made on the basis of the selection process input up to
       and including the packet in question. This excludes selection
       functions that require caching of packet for selection
       contingent on subsequent packets. See also the timeliness
       requirement following.

   A range of candidate selection operations is given in Section 4.
   Some detailed requirements of all selection operations are given in
   Section 4.9. Those selection operations to be required by the PSAMP
   standard are described in Section 4.10. Parallel measurement
   processes are discussed in Section 8. A target set of applications
   for PSAMP to support are described in Section 10.



Duffield et. al.     draft-ietf-psamp-framework-02.txt          [Page 6]

Internet-Draft          Passive Packet Measurement            March 2003

   3.2 Reporting Process Requirements

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

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

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

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

   A specific reporting processes meeting these requirements, and the
   requirement for ubiquity, is described in Section 5.

   3.3 Export Process Requirements

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

   * Secure Export: the ability to export securely, e.g. by encryption
 
   Candidate export processes meeting these requirements are described
   in Section 6.
   
   3.4 Configuration Requirements

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

   * Secure Configuration: configuration via protocols that prevent
       unauthorized reconfiguration.   

   Specific configuration capabilities that meet these requirements
   are discussed in Section 8. Feasibility and complexity of PSAMP
   operations is discussed in Section 9.

   Reuse of existing protocols will be encouraged provided the

Duffield et. al.     draft-ietf-psamp-framework-02.txt          [Page 7]

Internet-Draft          Passive Packet Measurement            March 2003

   protocol capabilities are compatible with the requirements laid out
   in this section.

4 Packet Selection 

   The function of packet selection is to select a subset from the
   stream of all packets visible at an observation point. Selection
   can be used to select packets of based on their content, and/or to
   reduce the rate of packets reports regardless of content. This
   section details some candidate primitive selection operations for
   standardization that satisfy the requirements of Section 3.1. Not
   all operations listed here are intended for standardization. Those
   that are are listed in Section 4.10. Packet selection techniques
   are discussed in more detail in [ZMR03].

   4.1 Filtering

   Filtering is the selection of packets based only the packet
   content, the treatment of the packet at the observation point, and
   deterministic functions of these occurring in the selection
   state. The packet is selection if these quantities fall into a
   specified range. Hash-based packet selection (see Section 4.3) can
   also be regarded as a filter)

   An example is a match/mask filter applied to a combination of bit
   positions. The packet is selected if the bits and the match are
   equal after taking the logical AND of both with the mask.  Higher
   level interfaces may be used to specify mask and matches for
   particular fields, for example, for IP addresses. Filtering on
   information derived from packet treatment, e.g., AS numbers derived
   from routing state, is another possibility; see Section
   4.8. Filtering based on calculated hashes is described separately
   in Section 4.4.

   4.2 Systematic Sampling

   In systematic sampling, the triggers for sampling are periodic,
   either in time or in packet count. All packets occurring in a
   selection interval (either in time or packet count) beyond the
   trigger are selected. The case that the selection interval covers
   only the first available packet for count-based sampling is often
   called 1 in N sampling: packets are selected with count period N.
   More generally, some number M<N of consecutive packets are selected.

   4.3 Random Sampling

   4.3.1 Uniform Random Sampling

   Packets are selected according to a probabilistic law. In the first
   instance, we consider Independent Uniform Random Sampling: packets
   are selected independently with some uniform probability 1/N. This
   count-driven sampling is sometimes referred to a geometric random

Duffield et. al.     draft-ietf-psamp-framework-02.txt          [Page 8]

Internet-Draft          Passive Packet Measurement            March 2003

   sampling, since the difference in count between successive selected
   packets are independent random variables with a geometric
   distribution of mean N. A time-driven analog, exponential random
   sampling, has the time between triggers exponentially distributed.
   Both geometric and exponential random sampling are examples of what
   is known as additive random sampling, defined as sampling where the
   intervals or counts between successive samples are independent
   identically distributed random variable.

   4.3.2 Stratified Random Sampling 
 
   Generally, in stratified random sampling, packets are assigned to
   strata according to an attribute, then a number of elements are
   drawn randomly from each stratum. Stratification reduces variance
   of single packet statistics if the variance between strata is
   greater than the variance within strata. In uniform stratified
   sampling, the number of elements in each stratum is the same, as is
   the number selected from each stratum. Thus each packet has the
   same selection probability, but some combination selections are
   disallowed.

   With the non-contingency requirement on sampling, the only allowed
   uniform stratification is that based on packet count. Each group of
   N successive packets forms a stratum, then some number M<N of
   each are drawn at random. This is non-contingent because the random
   positions of the selected packets can be generated in advance for
   each stratum.
    
   4.3.3 Non-Uniform Independent Random Sampling

   Also known as non-uniform probability sampling, or content
   dependent sampling, this is a variant of independent random
   sampling in which the sampling probabilities can depend on the
   selection process input. This can be used to weight sampling
   probabilities in order e.g. to boost the chance of sampling packets
   that are rare but are deemed important. Unbiased estimators for
   quantitative statistics are recovered by renormalization of sample
   values; see [HT52].

   4.4 Hash-based Selection

   Hash-based selection offers both a way to emulate random selection
   by generating from the packets' content pseudorandom variates on
   which to make packet selection decisions, while consistently select
   subsets of packets that share a common property. A hash function h
   operates on the selection function input for a packet, and maps in
   onto a range R. The packet is selected if the resulting hash falls
   in a specified range S. Thus hashing is a filter. But for good hash
   functions (see below) the inverse image inv(h(S)) will be extremely
   complex, and hence h would not be expressible as, say, a match/mask
   filter or a simple combination of these.


Duffield et. al.     draft-ietf-psamp-framework-02.txt          [Page 9]

Internet-Draft          Passive Packet Measurement            March 2003

   A hash function should have good mixing properties, in that
   changing one bit of the input should change many bits of the
   output. Then the distribution of hashes will be be fairly uniform,
   independent of the distribution of the input. The sampling rate is
   then #S/#R. If the input comprises distinct packet fields, c1
   ... cm, selection decisions will appear uncorrelated with the
   contents of any individual field, if the complementary fields are
   sufficiently variable and uncorrelated with cj.
 
   Even with a publicly known hash-function, accidental or
   deliberate evasion (or overwhelming) of hash-based sampling is
   militated against by keeping the selection range private, and/or
   employing a parameterizable hash function and keeping the parameter
   private.
  
   4.4.1 Consistent Flow Sampling

   Hash-based sampling can be used to select all packets from a
   pseudorandom set of flows. The flow key of each packet is hash
   sampled, and selected packets are reported on. All packets with a
   given key are either selected or not selected together.

   4.4.2 Trajectory Sampling

   In trajectory sampling, PSAMP devices in a network hash-sample
   packets using identical hash function and selection range. The
   domain of the hash is restricted to those fields that are invariant
   from hop to hop. Fields such as Time-to-Live, which is decremented
   per hop, and header CRC, which is recalculated per hop, are thus
   excluded from the hash domain. Thus a given packet is selected at
   all either all points on its path through the network, or at
   none. The domain of the hash function needs to be wider than just a
   flow key, if packets are to be selected pseudorandomly within flows;
   see [DuGr01]. A report on each selected packet is exported to a
   collector. The collector can reconstruct trajectories of the
   selected packets provided it can match different reports on the
   same packet, and distinguish these from reports on different
   packets. For this purpose, reports may also contain a second
   distinct hash, the identification hash, of the selected packets
   and/or timing information. The identification hash can be
   considered as part of the selection state.
 
   Applications of trajectory sampling include (i) estimation of the
   network path matrix, i.e., the traffic intensities accordng to
   network path, broken down by flow; (ii) detection of routing loops,
   as indicated by self-intersecting trajectories; (iii) passive
   performance measurement: prematurely terminating trajectories
   indicate packet loss, and packet latencies can be determined if
   reports include (synchronized) timestamps; (iv) network attack
   tracing, of the actual paths taken by attack packets with spoofed
   source addresses. Applications are discussed in Section 10.


Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 10]

Internet-Draft          Passive Packet Measurement            March 2003

   4.5 Generation of Pseudorandom Variates  
   
   Although pseudorandom number generators with well understood
   properties have been developed, they may not be the method of
   choice in setting where computational resources are scarce. A
   convenient alternative is to use packet content as a source of
   randomness. Hash-based sampling is an example: the hash (suitably
   renormalized) is a pseudorandom variate in the interval
   [0,1]. Other schemes may use packet fields in iterators for
   pseudorandom numbers. The point here, is that the statistical
   properties of the idealized packet selection law (such as
   independence of sampling decisions for different packets, or
   independence on packet content) may not be exactly shared by an
   implementation, but only approximately so.

   Although the selection decisions for non-uniform independent random
   sampling (see Section 4.3.3 above) also depend on the packet
   content, this form of sampling is distinguished from the use of
   packet content to generate variates. In the former case, the
   content only determines the selection probabilities: selection
   could then proceed e.g by use of a variates obtained by an
   independent pseudorandom number generator. In the latter case, the
   content determines the pseudorandom variates rather than the
   probabilities.

   4.6 Criteria for Choice of Selection Operations

   4.6.1 Evaluating the Need for Distinct Selection Operations

   In current practice, sampling has been performed using particular
   algorithms, including: 
          - pseudorandom independent sampling with probability 1/N; 
          - systematic sampling of every Nth packet.  
   The question arises as to whether both of these should be
   standardized as distinct selection operations, or whether they can
   be regarded as different implementations of a single selection
   operation.

   To determine the answer to this question, we need to consider 

      (a) measured or assumed statistical properties of the packet
      stream, e.g., one or more of the following:
          - contents of different packets are statistically independent
          - correlations between contents of different packets decay
            at a specified rate
          - contents of certain fields within the same packet are
            significantly variable and exhibit small cross correlation 
      (b) the desired reference sampling model, e.g., one of:
          - sample packets with long term probability 1/N
          - sample packets independent with probability 1/N
      (c) the set of possible alternatives and implementations, e.g., 
      one of:

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 11]

Internet-Draft          Passive Packet Measurement            March 2003

          - pseudorandom independent sampling with probability 1/N
          - systematic sampling with period N
          - hash-based sampling with target probability 1/N
      (d) the tolerance for error in the applications that use the 
          measurements. 

   We can say that a given alternative from (c) reproduces a reference
   model (b) for the applications if the results obtained using them
   are sufficiently accurate in (d) for traffic satisfying an assumed
   statistical properties in (a). Clearly, application to evaluate
   methods in (c) requires developing agreement on the relevant
   properties in (a), (b) and (d).

   Example: systematic sampling with period N will not count the
   occurrence of closely space packets (less than N counts apart) from
   the same flow. Thus for applications that are concerned with the
   joint statistics of multiple packets within flows, systematic
   sampling may not reproduce the results obtained with random
   sampling sufficiently accurately.

   4.6.2 Comparison of Uniform Sampling Methods

   A comparison of sampling methods, and their accuracy for estimating
   single packet statistics (e.g. mean and distribution of packet
   length) has been performed in [CPB93]. It was found that
   estimation using count-based methods was uniformly more accurate
   than that using time-based methods. Time based methods were found
   to be particularly inaccurate for assessing interarrival times,
   since they may miss traffic bursts. There was comparatively little
   difference between the systematic, stratified and random sampling,
   at least for the single packet statistics examined. For this
   reasons, we believe PSAMP should focus on count-based
   methods. Amongst these, accuracy of single packet statistics is not
   a great deciding factor. Systematic and random sampling are easier
   to implement than stratified sampling.

   4.7. Constraints on the Sampling Rate

   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.8 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.9 Input sequence numbers for primitive selection operations.
  

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 12]

Internet-Draft          Passive Packet Measurement            March 2003

   Each instance of a primitive selection operation MUST maintain a
   count of packets presented at its input. The counter value is to be
   included as a sequence number for selected packets. This enables
   applications to determine the attained rate at which packets are
   selected, and hence correctly normalize network usage estimates
   regardless of loss of information, whether this occurs because of
   discard of packet reports in the PSAMP device, or loss of
   measurement packets in transmission or collection; see [PPM01].
   The sequence numbers are considered as part of the packet's
   selection state.

   4.10 Standardized Selection Operations and Application Requirements

   In this section we list selection operations in three categories:
   mandatory (MUST), recommended (SHOULD) and optional (MAY). In each
   case, we list the applications (described in Section 10) that are
   supported.

   4.10.1 Mandatory Selection Operations

   PSAMP devices MUST support the following:

	(i) either count-based 1 in N systematic sampling or
	count-based simple random sampling.

   Either operation supports widespread baseline measurement. They
   reflect current practice: both exist in various routers that are
   currently available.  Furthermore, initial implementation of PSAMP
   may be constrained to be implemented in software, for devices whose
   hardware was not designed with PSAMP in mind. It is reasonable that
   such devices be PSAMP compliant by offering (i) above.

   4.10.2 Recommended Selection Operations

   PSAMP devices SHOULD support the following:

        (ii) both options in 4.10.1(i) above.

        (iii) general count-based systematic sampling.
 
	(iv) The PSAMP device identifies packet fields relating to
	different protocols, including IPv4, IPv6, MPLS and AToM. 

	(v) filtering by match/mask, or by single numerical range, on
	all/any of the fields identified in (iv), together with packet
	treatment, if any, performed by the PSAMP device.

        (vi) hash-based selection on a configurable input comprising
        any/all of the fields identified in (iv), using one or more
        hash functions to be standardized.

	(vii) composite sampling operations comprising filtering and any

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 13]

Internet-Draft          Passive Packet Measurement            March 2003

	other selection operation, configurably composed in either
	order.

	(viii) at least two parallel independent selection processes,
	one or both of which can be composite.

   Filtering, and its combination with sampling, support drill down
   analysis. Having at least two parallel independent selection
   processes (and their associated reporting processes) allows drill
   down to be simultaneously performed with baseline
   measurements. Hash-based sampling supports trajectory sampling.

   The operations (ii)-(viii) are listed as recommended, rather than
   mandatory, in recognition of the fact that some PSAMP devices
   e.g. simple switches or hubs, may not have the native capabilities
   to provide detailed protocol information, or perform computations
   for any selection other than sampling.

   Conversely, when a PSAMP device is, in its usual capacity, capable
   of recognizing use of a given protocol in the packet, then the
   protocol fields MUST be identifiable in (iv) above, and the
   contents made available for input to filters and hash-based
   sampling. Thus, for example, a device which routes at the IP level,
   must make IP field available for filtering.

   Similarly, any information relating to packet treatment performed
   by the device MUST be made available for filtering. Thus if the
   device is a router, routing state MUST be made available for
   filtering.  (See also Section 4.8).

   4.10.3 Optional Selection Operations

   PSAMP devices MAY support the following:

        (i) non-uniform independent random sampling, based on fields
        identified in 4.10.2(iv).  

5 Reporting

   Information eligible for inclusion in packet reports includes (i)
   the packet content itself (including encapsulating headers), but
   not the requiring the full packet payload; (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, sequence numbers, hash values.

   5.1 Mandatory Reporting     

   All PSAMP devices MUST report the following for each selected packet:


Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 14]

Internet-Draft          Passive Packet Measurement            March 2003

       (i) identifiers for the input and output interfaces of the
       PSAMP device that were traversed by the packet.

       (ii) the input sequence number(s) of any elementary selection
       operation(s) that acted on the packet.

       (iii) some number of contiguous bytes from the start of the
       packet. 

   The motivation is that some devices may not have the resource
   capacity or functionality to identify fields within a packet. The
   burden of interpretation is placed on the collector or applications
   that it supplies.

   5.2 Recommended Reporting

   PSAMP devices SHOULD report as follows for each selected packet:

	(iv) identification of packet fields relating to different
	protocols, including IPv4, IPv6, MPLS and AToM.

	(v) configurable inclusion of any/all fields from (iv) in the
	packet report, together with information from packet treatment
	if present.

	(vi) selection state associated with the packet, including
        timestamps and hashes calculated.

   Similar considerations apply as those of Section 4.10.2: if a device
   has the native capability to recognize protocol fields and/or treat
   packets, the the field contents and packet treatment MUST be made
   available for reporting.

   5.3 Report Interpretation

   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)
   indication of the inherent accuracy of the reported quantities,
   e.g., of timestamps.

   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 must be included

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 15]

Internet-Draft          Passive Packet Measurement            March 2003

   in every packet 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 packets 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

   When exporting to a remote collector, the collector is 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., through an
   API, rather than employing the transport used for off-board export.

   A possible example of the local export could be that the selected
   packets from the PSAMP measurement process serve as the input for
   the IPFIX protocol, i.e. delivering flow records out of the packets
   selected out via PSAMP. Note that IPFIX being still developed,
   this is just listed as a possible example.

   6.3  Reliable vs. Unreliable Transport

   The export of the report stream does not 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 able
   to receive and process acknowledgments, and to store unacknowledged
   data. Furthermore, the PSAMP device may not possess its own network
   address (for example an embedded measurement subsystem in an
   interface) at which to receive acknowledgments. 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

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 16]

Internet-Draft          Passive Packet Measurement            March 2003

   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
   reports in a single measurement packet. Any consequent delay should
   still allow for timely 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 packet reports faster than
   the allowed export rate.  In this situation, the device should
   discard the excess reports rather than transmitting them to the
   collector. Sequence numbers reported for selector input enable
   correction for lost reports. An additional sequence number for
   dispatched measurement packets enables the collector to determine
   the degree of loss in transmission.
 
   There are two options for a configurable rate limit. First, if the
   transport protocol has a configurable rate limit, that can be used.
   The second option is to limit the rate at which measurement packets
   are supplied to the transport protocol. A candidate for
   implementation of rate limiting is the leaky bucket, with tokens
   corresponding e.g. to bytes or packets.
    
   The export rate limit 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.

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

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 17]

Internet-Draft          Passive Packet Measurement            March 2003


   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 collector 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 reports 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 collector may
   receive measurement reports 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
   applications.

   6.7.2 Notions of Fairness

   In some cases, it may be reasonable to allow the collector to have
   flexibility in deciding how aggressively to respond to congestion.
   For example, the PSAMP device and the collector 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 collector 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 packets 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 which
   overloads links over which measurement packets are carried. In
   order to maintain report collection during periods of congestion,

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 18]

Internet-Draft          Passive Packet Measurement            March 2003

   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 collector 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 PSAMP device
   and the collector, and also to the failure of the device or the
   collector. For example, in a scenario where the collector is unable
   to reconfigure the export rate because of loss of reverse
   (collector to PSAMP device) connectivity, it is desirable that
   the device reduce the export rate automatically. Similarly, if no
   measurement reports reach the collector because of loss of
   forward connectivity, the collector 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
   appropriately.

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.

   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 measurement process; other measurement processes
   need only report that they selected the packet. The priority
   amongst measurement processes to report packets must be
   configurable.

   It is not proposed to standardize the number of parallel
   measurement processes available beyond the recommendation of
   Section 4.10.2.

8 Configuration and Management

   A key requirement for PSAMP is the easy reconfiguration of
   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.

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 19]

Internet-Draft          Passive Packet Measurement            March 2003


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

   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) is possible given a small number of selectors, although there
   may be some differences in ease of implementation for hardware
   vs. software platforms.

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

   9.1.4 Reporting

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 20]

Internet-Draft          Passive Packet Measurement            March 2003


   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 export
   by insertion of measurement packets, even through the software
   path.
 
   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 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(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
   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

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 21]

Internet-Draft          Passive Packet Measurement            March 2003

   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. Some of the goals
   here appear similar to those of IPFIX, at least in the broad
   classes of applications supported. However, there are two major
   differences:

       - PSAMP aims for ubiquitous deployment, thus offering broader
       reach for existing applications.
       - PSAMP can support new applications.

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

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 22]

Internet-Draft          Passive Packet Measurement            March 2003

   either the target sampling rate, or the attained sampling rate (as
   derived by interface packet counters included in the report stream)

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

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

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 23]

Internet-Draft          Passive Packet Measurement            March 2003

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

11 References

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

   [ClPB93] K.C. Claffy, G.C. Polyzos, H.-W. Braun, Application of
   Sampling Methodologies to Network Traffic Characterization,

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 24]

Internet-Draft          Passive Packet Measurement            March 2003

   Proceedings of ACM SIGCOMM'93, San Francisco, CA, USA, September
   13-17, 1993

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

   [HT52] D.G. Horvitz and D.J. Thompson, A Generalization of Sampling
   without replacement from a Finite Universe. J. Amer. Statist.
   Assoc. Vol. 47, pp. 663-685, 1952.

   [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-04.txt, work in progress, September
   2002.

   [PPM01] P. Phaal, S. Panchen, N. McKee, InMon Corporation's
   sFlow: A Method for Monitoring Traffic in Switched and Routed
   Networks, RFC 3176, September 2001

   [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-08.txt, work in progress,
   January 2003.

   [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-01.txt, work in progress, March 2003.

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

Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 25]

Internet-Draft          Passive Packet Measurement            March 2003

   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


13 Intellectual Property Statement

   AT&T Corporation may own intellectual property applicable to this
   contribution. The IETF has been notified of AT&T's licensing intent
   for the specification contained in this document. See
   http://www.ietf.org/ietf/IPR/ATT-GENERAL.txt for AT&T's IPR
   statement.


Duffield et. al.     draft-ietf-psamp-framework-02.txt         [Page 26]

Internet-Draft          Passive Packet Measurement            March 2003

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
   an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIMS 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 et. al.     draft-ietf-psamp-framework-02.txt         [Page 27]