idnits 2.17.1 draft-ietf-psamp-framework-13.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1808. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1783. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1783. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1789. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (June 27, 2008) is 5779 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-11) exists of draft-ietf-psamp-info-08 ** Obsolete normative reference: RFC 5101 (Obsoleted by RFC 7011) ** Obsolete normative reference: RFC 5102 (Obsoleted by RFC 7012) ** Obsolete normative reference: RFC 4960 (Obsoleted by RFC 9260) == Outdated reference: A later version (-11) exists of draft-ietf-psamp-sample-tech-10 -- Obsolete informational reference (is this intentional?): RFC 2460 (Obsoleted by RFC 8200) Summary: 5 errors (**), 0 flaws (~~), 3 warnings (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 ` 3 Internet Draft Nick Duffield (Editor) 4 Document: draft-ietf-psamp-framework-13.txt AT&T Labs - Research 5 Intended status: Informational June 27, 2008 6 Expires: December 2008 8 A Framework for Packet Selection and Reporting 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents 13 that any applicable patent or other IPR claims of which he or 14 she is aware have been or will be disclosed, and any of which 15 he or she becomes aware will be disclosed, in accordance with 16 Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet 19 Engineering Task Force (IETF), its areas, and its working 20 groups. Note that other groups may also distribute working 21 documents as Internet-Drafts. 23 Internet-Drafts are draft documents valid for a maximum of 24 six months and may be updated, replaced, or obsoleted by 25 other documents at any time. It is inappropriate to use 26 Internet-Drafts as reference material or to cite them other 27 than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed 33 at http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on December, 2008. 37 Copyright Notice 39 Copyright (C) The IETF Trust (2008). 41 Abstract 43 This document specifies a framework for the PSAMP (Packet 44 SAMPling) protocol. The functions of this protocol are to select 45 packets from a stream according to a set of standardized 46 selectors, to form a stream of reports on the selected packets, 47 and to export the reports to a collector. This framework details 48 the components of this architecture, then describes some generic 49 requirements, motivated by the dual aims of ubiquitous deployment 50 and utility of the reports for applications. Detailed 51 requirements for selection, reporting and exporting are 52 described, along with configuration requirements of the PSAMP 53 functions. 55 Table of Contents 57 1. Introduction................................................3 58 2. PSAMP Documents Overview....................................4 59 3. Elements, Terminology and High-level Architecture...........4 60 3.1 High-level description of the PSAMP Architecture............4 61 3.2 Observation Points, Packet Streams and Packet Content.......5 62 3.3 Selection Process...........................................6 63 3.4 Reporting...................................................7 64 3.5 Metering Process............................................7 65 3.6 Exporting Process...........................................8 66 3.7 PSAMP Device................................................8 67 3.8 Collector...................................................8 68 3.9 Possible Configurations.....................................9 69 4. Generic Requirements for PSAMP.............................10 70 4.1 Generic Selection Process Requirements.....................10 71 4.2 Generic Reporting Requirements.............................11 72 4.3 Generic Exporting Process Requirements.....................12 73 4.4 Generic Configuration Requirements.........................12 74 5. Packet Selection...........................................12 75 5.1 Two Types of Selector......................................12 76 5.2 PSAMP Packet Selectors.....................................13 77 5.3 Selection Fraction Terminology.............................16 78 5.4 Input Sequence Numbers for Primitive Selectors.............17 79 5.5 Composite Selectors........................................18 80 5.6 Constraints on the Selection Fraction......................18 81 6. Reporting..................................................18 82 6.1 Mandatory Contents of Packet Reports: Basic Reports........18 83 6.2 Extended Packet Reports....................................19 84 6.3 Extended Packet Reports in the Presence of IPFIX...........19 85 6.4 Report Interpretation......................................20 86 7. Parallel Metering Processes................................20 87 8. Exporting Process..........................................21 88 8.1 Use of IPFIX...............................................21 89 8.2 Export Packets.............................................21 90 8.3 Congestion-aware Unreliable Transport......................21 91 8.4 Configurable Export Rate Limit.............................22 92 8.5 Limiting Delay for Export Packets..........................22 93 8.6 Export Packet Compression..................................23 94 8.7 Collector Destination......................................24 95 8.8 Local Export...............................................24 96 9. Configuration and Management...............................24 97 10. Feasibility and Complexity.................................25 98 10.1 Feasibility................................................25 99 10.1.1 Filtering.................................................25 100 10.1.2 Sampling..................................................25 101 10.1.3 Hashing...................................................25 102 10.1.4 Reporting.................................................25 103 10.1.5 Exporting.................................................26 104 10.2 Potential Hardware Complexity..............................26 105 11. Applications...............................................27 106 11.1 Baseline Measurement and Drill Down........................27 107 11.2 Trajectory Sampling........................................28 108 11.3 Passive Performance Measurement............................28 109 11.4 Troubleshooting............................................29 110 12. Security Considerations....................................30 111 12.1 Relation of PSAMP and IPFIX Security for Exporting Process.30 112 12.2 PSAMP Specific Privacy Considerations......................30 113 12.3 Security Considerations for Hash-Based Selection...........30 114 12.3.1 Modes and Impact of vulnerabilities.......................31 115 12.3.2 Use of Private Parameters in Hash Functions...............31 116 12.3.3 Strength of Hash Functions................................32 117 12.4 Security Guidelines for Configuring PSAMP..................32 118 13. IANA Considerations........................................33 119 14. References.................................................33 120 14.1 Normative References.......................................33 121 14.2 Informative References.....................................33 122 15. Authors' Addresses.........................................35 123 16. Contributors...............................................36 124 17. Acknowledgements...........................................36 125 18. Intellectual Property Statements...........................36 126 19. Copyright Statement........................................37 127 20. Disclaimer.................................................37 129 1. Introduction 131 This document describes the PSAMP framework for network elements 132 to select subsets of packets by statistical and other methods, 133 and to export a stream of reports on the selected packets to a 134 collector. 136 The motivation for the PSAMP standard comes from the need for 137 measurement-based support for network management and control 138 across multivendor domains. This requires domain-wide 139 consistency in the types of selection schemes available, and the 140 manner in which the resulting measurements are presented and 141 interpreted. 143 The motivation for specific packet selection operations comes 144 from the applications that they enable. Development of the PSAMP 145 standard is open to influence by the requirements of standards in 146 related IETF Working Groups, for example, IP Performance Metrics 147 (IPPM) [RFC-2330] and Internet Traffic Engineering (TEWG). 149 The name PSAMP is a contraction of the phrase Packet Sampling. 150 The word "sampling" captures the idea that only a subset of all 151 packets passing a network element will be selected for reporting. 152 But PSAMP selection operations include random selection, 153 deterministic selection (filtering), and deterministic 154 approximations to random selection (hash-based selection). 156 2. PSAMP Documents Overview 158 PSAMP-FW: "A Framework for Packet Selection and Reporting" (this 159 document). This document describes the PSAMP framework for 160 network elements to select subsets of packets by statistical and 161 other methods, and to export a stream of reports on the selected 162 packets to a collector. Definitions of terminology and the use 163 of the terms "must", "should" and "may" in this document are 164 informational only. 166 [PSAMP-TECH]: "Sampling and Filtering Techniques for IP Packet 167 Selection", describes the set of packet selection techniques 168 supported by PSAMP. 170 [PSAMP-PROTO]: "Packet Sampling (PSAMP) Protocol Specifications" 171 specifies the export of packet information from a PSAMP Exporting 172 Process to a PSAMP Colleting Process 174 [PSAMP-INFO]: "Information Model for Packet Sampling Exports" 175 defines an information and data model for PSAMP. 177 3. Elements, Terminology and High-level Architecture 179 3.1 High-level description of the PSAMP Architecture 181 Here is an informal high level description of the PSAMP protocol 182 operating in a PSAMP Device (all terms will be defined 183 presently). A stream of packets is observed at an Observation 184 Point. A Selection Process inspects each packet to determine 185 whether or not it is to be selected from reporting. The 186 Selection Process is part of the Metering Process, which 187 constructs a report on each selected packet, using the Packet 188 Content, and possibly other information such as the packet 189 treatment at the Observation Point or the arrival timestamp. An 190 Exporting Process sends the Packet Reports to a Collector, 191 together with any subsidiary information needed for their 192 interpretation. 194 The following figure indicates the sequence of the three 195 processes (Selection, Metering, and Exporting) within the PSAMP 196 device. 198 +------------------+ 199 | Metering Process | 200 | +-----------+ | +-----------+ 201 Observed | | Selection | | | Exporting | 202 Packet--->| | Process |--------->| Process |--->Collector 203 Stream | +-----------+ | +-----------+ 204 +------------------+ 206 The following sections give the detailed definitions of each of 207 all the objects just named. 209 3.2 Observation Points, Packet Streams and Packet Content 211 This section contains the definition of terms relevant to 212 obtaining the packet input to the selection process. 214 * Observation Point 216 An Observation Point is a location in the network where IP 217 packets can be observed. Examples include: a line to which a 218 probe is attached, a shared medium, such as an Ethernet-based 219 LAN, a single port of a router, or a set of interfaces 220 (physical or logical) of a router. 222 Note that every Observation Point is associated with an 223 Observation Domain (defined below), and that one Observation 224 Point may be a superset of several other Observation Points. 225 For example one Observation Point can be an entire line card. 226 That would be the superset of the individual Observation Points 227 at the line card's interfaces. 229 * Observed Packet Stream 231 The Observed Packet Stream is the set of all packets observed 232 at the Observation Point. 234 * Packet Stream 236 A Packet Stream denotes a subset of the Observed Packet Stream 237 that flows past some specified point within the Selection 238 Process. 239 An example of a Packet Stream is the output of the Selection 240 Process. Note that packets selected from a stream, e.g. by 241 sampling, do not necessarily possess a property by which they 242 can be distinguished from packets that have not been selected. 243 For this reason the term "stream" is favored over "flow", which 244 is defined as set of packets with common properties [RFC-3917]. 246 * Packet Content 247 The Packet Content denotes the union of the packet header 248 (which includes link layer, network layer and other 249 encapsulation headers) and the packet payload. 251 3.3 Selection Process 253 This section defines the selection process and related objects. 255 * Selection Process 257 A Selection Process takes the Observed Packet Stream as its 258 input and selects a subset of that stream as its output. 260 * Selection State: 262 A Selection Process may maintain state information for use by 263 the Selection Process. At a given time, the Selection State 264 may depend on packets observed at and before that time, and 265 other variables. Examples include: 267 (i) sequence numbers of packets at the input of 268 Selectors; 270 (ii) a timestamp of observation of the packet at the 271 Observation Point; 273 (iii) iterators for pseudorandom number generators; 275 (iv) hash values calculated during selection; 277 (v) indicators of whether the packet was selected by a 278 given Selector. 280 Selection Processes may change portions of the Selection State 281 as a result of processing a packet. Selection state for a 282 packet is to reflect the state after processing the packet. 284 * Selector: 286 A Selector defines the action of a Selection Process on a 287 single packet of its input. If selected, the packet becomes an 288 element of the output Packet Stream. 290 The Selector can make use of the following information in 291 determining whether a packet is selected: 293 (i) the Packet Content; 295 (ii) information derived from the packet's treatment at the 296 Observation Point; 298 (iii) any selection state that may be maintained by the 299 Selection Process. 301 * Composite Selector: 303 A Composite Selector is an ordered composition of Selectors, in 304 which the output Packet Stream issuing from one Selector forms 305 the input Packet Stream to the succeeding Selector. 307 * Primitive Selector: 309 A Selector is primitive if it is not a Composite Selector. 311 3.4 Reporting 313 * Packet Reports 315 Packet Reports comprise a configurable subset of a packet's 316 input to the Selection Process, including the Packet Content, 317 information relating to its treatment (for example, the output 318 interface), and its associated selection state (for example, a 319 hash of the Packet Content). 321 * Report Interpretation: 323 Report Interpretation comprises subsidiary information, 324 relating to one or more packets, that are used for 325 interpretation of their Packet Reports. Examples include 326 configuration parameters of the Selection Process. 328 * Report Stream: 330 The Report Stream is the output of a Metering Process, 331 comprising two distinguished types of information: Packet 332 Reports, and Report Interpretation. 334 3.5 Metering Process 336 A Metering Process selects packets from the Observed Packet 337 Stream using a Selection Process, and produces as output a Report 338 Stream concerning the selected packets. 340 The PSAMP Metering Process can be viewed as analogous to the 341 IPFIX metering process [RFC-5101], which produces flow records as 342 its output. While the Metering Process definition in this 343 document specifies the PSAMP definition, the PSAMP protocol 344 specifications [PSAMP-PROTO] will use the IPFIX Metering Process 345 definition, which also suits the PSAMP requirements. The 346 relationship between PSAMP and IPFIX is described more in [PSAMP- 347 INFO] and [PSAMP-PROTO]. 349 3.6 Exporting Process 351 * Exporting Process: 353 An Exporting Process sends, in the form of Export Packets, the 354 output of one or more Metering Processes to one or more 355 Collectors. 357 * Export Packets: 359 An Export Packet is a combination of Report Interpretation(s) 360 and/or one or more Packet Reports that are bundled by the 361 Exporting Process into a Export Packet for exporting to a 362 Collector. 364 3.7 PSAMP Device 366 A PSAMP Device is a device hosting at least an Observation Point, 367 a Metering Process (which includes a Selection Process) and an 368 Exporting Process. Typically, corresponding Observation 369 Point(s), Metering Process(es) and Exporting Process(es) are co- 370 located at this device, for example at a router. 372 3.8 Collector 374 A Collector receives a Report Stream exported by one or more 375 Exporting Processes. In some cases, the host of the Metering 376 and/or Exporting Processes may also serve as the Collector. 378 3.9 Possible Configurations 380 Various possibilities for the high level architecture of these 381 elements are as follows. 383 MP = Metering Process, EP = Exporting process 385 PSAMP Device 386 +---------------------+ +------------------+ 387 |Observation Point(s) | | Collector(1) | 388 |MP(s)--->EP----------+---------------->| | 389 |MP(s)--->EP----------+-------+-------->| | 390 +---------------------+ | +------------------+ 391 | 392 PSAMP Device | 393 +---------------------+ | +------------------+ 394 |Observation Point(s) | +-------->| Collector(2) | 395 |MP(s)--->EP----------+---------------->| | 396 +---------------------+ +------------------+ 398 PSAMP Device 399 +---------------------+ 400 |Observation Point(s) | 401 |MP(s)--->EP---+ | 402 | | | 403 |Collector(3)<-+ | 404 +---------------------+ 406 The most simple Metering Process configuration is composed of: 408 +------------------------------------+ 409 | +----------+ | 410 | |Selection | | 411 Observed | |Process | Packet | 412 Packet-->| |(primitive|-> Stream -> |--> Report Stream 413 Stream | | selector)| | 414 | +----------+ | 415 | Metering Process | 416 +------------------------------------+ 418 A Metering Process with a composite selector is composed of: 420 +--------------------------------------------------... 421 | +-----------------------------------+ 422 | | +----------+ +----------+ | 423 | | |Selection | |Selection | | 424 Observed | | |Process | |Process | | 425 Packet-->| | |(primitive|-Packet->|(primitive|---> Packet ... 426 Stream | | |selector1)| Stream |selector2)| | Stream 427 | | +----------+ +----------+ | 428 | | Composite Selector | 429 | +-----------------------------------+ 430 | Metering Process 431 +--------------------------------------------------... 433 ...-------------+ 434 | 435 | 436 | 437 | 438 |---> Report Stream 439 | 440 | 441 | 442 | 443 | 444 ...-------------+ 446 4. Generic Requirements for PSAMP 448 This section describes the generic requirements for the PSAMP 449 protocol. A number of these are realized as specific 450 requirements in later sections. 452 4.1 Generic Selection Process Requirements. 454 (a) Ubiquity: The Selectors must be simple enough to be 455 implemented ubiquitously at maximal line rate. 457 (b) Applicability: the set of Selectors must be rich enough to 458 support a range of existing and emerging measurement based 459 applications and protocols. This requires a workable 460 trade-off between the range of traffic engineering 461 applications and operational tasks it enables, and the 462 complexity of the set of capabilities. 464 (c) Extensibility: the protocol must be able to accommodate 465 additional packet Selectors not currently defined. 467 (d) Flexibility: the protocol must support selection of packets 468 using various network protocols or encapsulation layers, 469 including Internet Protocol Version 4 (IPv4) [RFC-0791], 470 Internet Protocol Version 6 (IPv6) [RFC-2460], and 471 Multiprotocol Label Switching (MPLS) [RFC-3031]. 473 (e) Robust Selection: packet selection must be robust against 474 attempts to craft an Observed Packet Stream from which 475 packets are selected disproportionately (e.g. to evade 476 selection, or overload measurement systems). 478 (f) Parallel Metering Processes: the protocol must support 479 simultaneous operation of multiple independent Metering 480 Processes at the same host. 482 (g) Causality: the selection decision for each packet should 483 depend only weakly, if at all, upon future packets 484 arrivals. This promotes ubiquity by limiting the 485 complexity of the selection logic. 487 (h) Encrypted Packets: Selectors that interpret packet fields 488 must be configurable to ignore (i.e. not select) encrypted 489 packets, when they are detected. 491 Specific Selectors are outlined in Section 5, and described in 492 more detail in the companion document [PSAMP-TECH]. 494 4.2 Generic Reporting Requirements 496 (i) Self-defining: the Report Stream must be complete in the 497 sense that no additional information need be retrieved from 498 the Observation Point in order to interpret and analyze the 499 reports. 501 (j) Indication of Information Loss: the Report Stream must 502 include sufficient information to indicate or allow the 503 detection of loss occurring within the Selection, Metering, 504 and/or Exporting Processes, or in transport. This may be 505 achieved by the use of sequence numbers. 507 (k) Accuracy: the Report Stream must include information that 508 enables the accuracy of measurements to be determined. 510 (l) Faithfulness: all reported quantities that relate to the 511 packet treatment must reflect the router state and 512 configuration encountered by the packet at the time it is 513 received by the Metering Process. 515 (m) Privacy: although selection of the content of Packet 516 Reports must be responsive to the needs of measurement 517 applications, it must also conform with [RFC-2804]. In 518 particular, full packet capture of arbitrary packet streams 519 is explicitly out of scope. 521 See section 6 for further discussions on Reporting. 523 4.3 Generic Exporting Process Requirements 525 (n) Timeliness: configuration must allow for limiting of 526 buffering delays for the formation and transmission for 527 Export Packets. See Section 8.5 for further details. 529 (o) Congestion Avoidance: export of a Report Stream across a 530 network must be congestion avoiding in compliance with 531 [RFC-2914]. This is discussed further in Section 8.3. 533 (p) Secure Export: 535 (i) confidentiality: the option to encrypt exported data must 536 be provided. 538 (ii) integrity: alterations in transit to exported data must be 539 detectable at the Collector 541 (iii) authenticity: authenticity of exported data must be 542 verifiable by the Collector in order to detect forged data. 544 The motivation here is the same as for security in IPFIX export; 545 see Sections 6.3 and 10 of [RFC-3917]. 547 4.4 Generic Configuration Requirements 549 (q) Ease of Configuration: of sampling and export parameters, 550 e.g. for automated remote reconfiguration in response to 551 collected reports. 553 (r) Secure Configuration: the option to configure via protocols 554 that prevent unauthorized reconfiguration or eavesdropping 555 on configuration communications must be available. 556 Eavesdropping on configuration might allow an attacker to 557 gain knowledge that would be helpful in crafting a packet 558 stream to evade subversion, or overload the measurement 559 infrastructure. 561 Configuration is discussed in Section 9. 563 5. Packet Selection 565 This section details specific requirements for the Selection 566 Process, motivated by the generic requirements of Section 3.3. 568 5.1 Two Types of Selector 570 PSAMP categorizes selectors into two types: 572 * Filtering: a filter is a Selector that selects a packet 573 deterministically based on the Packet Content, or its 574 treatment, or functions of these occurring in the Selection 575 State. Two examples are: 577 (i) Property match filtering: a packet is selected if a 578 specific field in the packet equals a predefined value. 580 (ii) Hash-based selection: a hash function is applied to the 581 Packet Content, and the packet is selected if the result 582 falls in a specified range. 584 * Sampling: a selector that is not a filter is called a sampling 585 operation. This reflects the intuitive notion that if the 586 selection of a packet cannot be determined from its content 587 alone, there must be some type of sampling taking place. 589 Sampling operations can be divided into two subtypes: 591 (i) Content-independent sampling, which does not use Packet 592 Content in reaching sampling decisions. Examples include 593 systematic sampling, and uniform pseudorandom sampling 594 driven by a pseudorandom number whose generation is 595 independent of Packet Content. Note that in Content- 596 independent Sampling it is not necessary to access the 597 Packet Content in order to make the selection decision. 599 (ii) Content-dependent sampling, in which the Packet Content 600 is used in reaching selection decisions. An application is 601 pseudorandom selection according to a probability that 602 depends on the contents of a packet field, e.g., sampling 603 packets with a probability dependent on their TCP/UDP port 604 numbers. Note that this is not a Filter. 606 5.2 PSAMP Packet Selectors 608 A spectrum of packet selectors is described in detail in [PSAMP- 609 TECH]. Here we only briefly summarize the meanings for 610 completeness. 612 A PSAMP Selection Process must support at least one of the 613 following Selectors. 615 * systematic count based sampling: packet selection is triggered 616 periodically by packet count, a number of successive packets 617 being selected subsequent to each trigger. 619 * systematic time based sampling: similar to systematic count 620 based except that selection is reckoned with respect to time 621 rather than count. Packet selection is triggered at periodic 622 instants separated by a time called the spacing. All packets 623 that arrive within a certain time of the trigger (called the 624 interval length) are selected. 626 * probabilistic n-out-of-N sampling: from each count-based 627 successive block of N packets, n are selected at random. 629 * uniform probabilistic sampling: packets are selected 630 independently with fixed sampling probability p. 632 * non-uniform probabilistic sampling: packets are selected 633 independently with probability p that depends on Packet 634 Content. 636 * property match filtering 638 With this Filtering method a packet is selected if a specific 639 field within the packet and/or on properties of the router 640 state equal(s) a predefined value. Possible filter fields are 641 all IPFIX flow attributes specified in [RFC-5102]. Further 642 fields can be defined by vendor specific extensions. 644 A packet is selected if Field=Value. Masks and ranges are only 645 supported to the extent to which [RFC-5102] allows them e.g. by 646 providing explicit fields like the netmasks for source and 647 destination addresses. 649 AND operations are possible by concatenating filters, thus 650 producing a composite selection operation. In this case, the 651 ordering in which the filtering happens is implicitly defined 652 (outer filters come after inner filters). However, as long as 653 the concatenation is on filters only, the result of the 654 cascaded filter is independent from the order, but the order 655 may be important for implementation purposes, as the first 656 filter will have to work at a higher rate. In any case, an 657 implementation is not constrained to respect the filter 658 ordering, as long as the result is the same, and it may even 659 implement the composite filtering in filtering in one single 660 step. 662 OR operations are not supported with this basic model. More 663 sophisticated filters (e.g. supporting bitmasks, ranges or OR 664 operations etc.) can be realized as vendor specific schemes. 666 Property match operations should be available for different 667 protocol portions of the packet header: 669 (i) the IP header (excluding options in IPv4, stacked 670 headers in IPv6) 672 (ii) transport header 673 (iii) encapsulation headers (e.g. the MPLS label stack, if 674 present) 676 When the PSAMP Device offers property match filtering, and, in 677 its usual capacity other than in performing PSAMP functions, 678 identifies or processes information from IP, transport or 679 encapsulation protocols, then the information should be made 680 available for filtering. For example, when a PSAMP Device is a 681 router that routes based on destination IP address, that field 682 should be made available for filtering. Conversely, a PSAMP 683 Device that does not route is not expected to be able to locate 684 an IP address within a packet, or make it available for 685 Filtering, although it may do so. 687 Since packet encryption alters the meaning of encrypted fields, 688 property match filtering must be configurable to ignore 689 encrypted packets, when detected. 691 The Selection Process may support filtering based on the 692 properties of the router state: 694 (i) Ingress interface at which packet arrives equals a 695 specified value 697 (ii) Egress interface to which packet is routed to equals a 698 specified value 699 (iii) Packet violated Access Control List (ACL) on the 700 router 702 (iv) Failed Reverse Path Forwarding (RPF). Packets that 703 match the Failed Reverse Path Forwarding (RPF) condition are 704 packets for which ingress filtering failed as defined in 705 [RFC3704]. 707 (v) Failed Resource Reservation (RSVP). Packets that match 708 the Failed Resource Reservation condition are packets that 709 do not fulfill the RSVP specification as defined in 710 [RFC-2205]. 712 (vi) No route found for the packet 714 (vii) Origin Border Gateway Protocol (BGP) Autonomous System 715 (AS) [RFC-4271] equals a specified value or lies within a 716 given range 718 (viii) Destination BGP AS equals a specified value or lies 719 within a given range 721 Router architectural considerations may preclude some 722 information concerning the packet treatment being available at 723 line rate for selection of packets. For example, the Selection 724 Process may not be implemented in the fast path that is able to 725 access routing state at line rate. However, when filtering 726 follows sampling (or some other selection operation) in a 727 Composite Selector, the rate of the Packet Stream output from 728 the sampler and input to the filter may be sufficiently slow 729 that the filter could select based on routing state. 731 * Hash-based Selection: 733 Hash-based selection will employ one or more hash functions to 734 be standardized. A hash function is applied to a subset of 735 Packet Content, and the packet is selected of the resulting 736 hash falls in a specified range. The stronger the hash 737 function, the more closely hash-based selection approximates 738 uniform random sampling. Privacy of hash selection range and 739 hash function parameters obstructs subversion of the selector 740 by packets that are crafted either to avoid selection or to be 741 selected. Privacy of the hash function is not required. 742 Robustness and security considerations of hash-based selection 743 are further discussed in further in [PSAMP-TECH]. Applications 744 of hash-based sampling are described in Section 11. 746 5.3 Selection Fraction Terminology 748 * Population: 750 A population is a Packet Stream, or a subset of a Packet 751 Stream. A Population can be considered as a base set from 752 which packets are selected. An example is all packets in the 753 Observed Packet Stream that are observed within some specified 754 time interval. 756 * Population Size: 758 The Population Size is the number of all packets in a 759 Population. 761 * Configured Selection Fraction 763 The Configured Selection Fraction is the ratio of the number of 764 packets selected by a Selector from an input Population, to the 765 Population Size, as based on the configured selection 766 parameters. 768 * Attained Selection Fraction 770 The Attained Selection Fraction is the actual ratio of the 771 number of packets selected by a Selector from an input 772 Population, to the Population Size. 774 For some sampling methods the Attained Selection Fraction can 775 differ from the Configured Selection Fraction due to, for 776 example, the inherent statistical variability in sampling 777 decisions of probabilistic sampling and hash-based selection. 778 Nevertheless, for large Population Sizes and properly configured 779 Selectors, the Attained Selection Fraction usually approaches the 780 Configured Selection Fraction. 782 The notions of Configured/Attained Selection Fraction extend 783 beyond Selectors. An illustrative example is the Configured 784 Selection Fraction of the composition of the Metering Process 785 with the Exporting Process. Here the Population is the Observed 786 Packet Stream or a subset thereof. The Configured Selection 787 Fraction is the fraction of the Population for which Packet 788 Reports which are expected to reach the Collector. This quantity 789 may reflect additional parameters, not necessarily described in 790 the PSAMP protocol, that determine the degree of loss suffered by 791 Packet Reports en route to the Collector, e.g., the transmission 792 bandwidth available to the Exporting Process. In this example, 793 the Attained Selection Fraction is the fraction of Population 794 packets for which reports did actually reach the Collector, and 795 thus incorporates the effect of any loss of Packet Reports due, 796 e.g, to resource contention at the Observation Point, or during 797 transmission. 799 5.4 Input Sequence Numbers for Primitive Selectors 801 Each instance of a Primitive Selector must maintain a count of 802 packets presented at its input. The counter value is to be 803 included as a sequence number for selected packets. The sequence 804 numbers are considered as part of the packet's Selection State. 806 Use of input sequence numbers enables applications to determine 807 the Attained Selection Fraction, and hence correctly normalize 808 network usage estimates regardless of loss of information, 809 regardless of whether this loss occurs because of discard of 810 packet reports in the Metering Process (e.g. due to resource 811 contention in the host of these processes), or loss of export 812 packets in transmission or collection. See [RFC-3176] for 813 further details. 815 As an example, consider a set of n consecutive packet reports r1, 816 r2,... , rn, selected by a sampling operation and received at a 817 Collector. Let s1, s2,..., sn be the input sequence numbers 818 reported by the packets. The Attained Selection Fraction for the 819 composite of the measurement and exporting processes, taking into 820 account both packet sampling at the Observation Point and loss in 821 transmission, is computed as R = (n-1)/(sn-s1). (Note R would be 822 1 if all packets were selected and there were no transmission 823 loss). 825 The Attained Selection Fraction can be used to estimate the 826 number of bytes present in a portion of the Observed Packet 827 Stream. Let b1, b2,..., bn be the number of bytes reported in 828 each of the packets that reached the Collector, and set B = 829 b1+b2+...+bn. Then the total bytes present in packets in the 830 Observed Packet Stream whose input sequence numbers lie between 831 s1 and sn is estimated by B/R, i.e, scaling up the measured bytes 832 through division by the Attained Selection Fraction 834 With Composite Selectors, an input sequence number must be 835 reported for each Selector in the composition. 837 5.5 Composite Selectors 839 The ability to compose Selectors in a Selection Process should be 840 provided. The following combinations appear to be most useful 841 for applications: 843 * concatentation of property match filters. This is useful for 844 constructing the AND of the component filters. 846 * filtering followed by sampling. 848 * sampling followed by filtering. 850 Composite Selectors are useful for drill down applications. The 851 first component of a composite selector can be used to reduce the 852 load on the second component. In this setting, the advantage to 853 be gained from a given ordering can depends on the composition of 854 the packet stream. 856 5.6 Constraints on the Selection Fraction 858 Sampling at full line rate, i.e. with probability 1, is not 859 excluded in principle, although resource constraints may not 860 permit it in practice. 862 6. Reporting 864 This section details specific requirements for reporting, 865 motivated by the generic requirements of Section 3.4 867 6.1 Mandatory Contents of Packet Reports: Basic Reports 869 Packet Reports must include the following: 871 (i) the input sequence number(s) of any Selectors that acted 872 on the packet in the instance of a Metering Process which 873 produced the report. 875 (ii) the identifier of the Metering Process that produced 876 the selected packet 878 The Metering Process must support inclusion of the following in 879 each Packet Report, as a configurable option: 881 (iii) a basic report on the packet, i.e., some number of 882 contiguous bytes from the start of the packet, including the 883 packet header (which includes network layer and any 884 encapsulation headers) and some subsequent bytes of the 885 packet payload. 887 Some devices may not have the resource capacity or functionality 888 to provide more detailed packet reports than those in (i), (ii) 889 and (iii) above. Using this minimum required reporting 890 functionality, the Metering Process places the burden of 891 interpretation on the Collector, or on applications that it 892 supplies. Some devices may have the capability to provide 893 extended packet reports, described in the next section. 895 6.2 Extended Packet Reports 897 The Metering Process may support inclusion in Packet Reports of 898 the following information, inclusion any or all being 899 configurable as an option. 901 (iv) fields relating to the following protocols used in the 902 packet: IPv4, IPV6, transport protocols, and encapsulation 903 protocols including MPLS 905 (v) packet treatment, including: 907 - identifiers for any input and output interfaces of the 908 Observation Point that were traversed by the packet 910 - source and destination BGP AS 912 (vi) Selection State associated with the packet, including: 914 - the timestamp of observation of the packet at the 915 Observation Point. The timestamp should be reported to 916 microsecond resolution. 918 - hashes, where calculated. 920 It is envisaged that selection of fields for Extended Packet 921 Reporting may be used to reduce reporting bandwidth, in which 922 case the option to report information in (iii) may not be 923 exercised. 925 6.3 Extended Packet Reports in the Presence of IPFIX 927 If an IPFIX metering process is supported at the Observation 928 Point, then in order to be PSAMP compliant, Extended Packet 929 Reports must be able to include all fields required in the IPFIX 930 information model [RFC-5102], with modifications appropriate to 931 reporting on single packets rather than flows. 933 6.4 Report Interpretation 935 The Report Interpretation must include: 937 (i) configuration parameters of the Selectors of the packets 938 reported on. 940 (ii) format of the Packet Report; 942 (iii) indication of the inherent accuracy of the reported 943 quantities, e.g., of the packet timestamp. 945 The accuracy measure in (iii) is of fundamental importance for 946 estimating the likely error attached to estimates formed from the 947 Packet Reports by applications. 949 The requirements for robustness and transparency are motivations 950 for including Report Interpretation in the Report Stream: it 951 makes the Report Stream self-defining. The PSAMP framework 952 excludes reliance on an alternative model in which interpretation 953 is recovered out of band. This latter approach is not robust 954 with respect to undocumented changes in Selector configuration, 955 and may give rise to future architectural problems for network 956 management systems to coherently manage both configuration and 957 data collection. 959 It is not envisaged that all Report Interpretation be included in 960 every Packet Report. Many of the quantities listed above are 961 expected to be relatively static; they could be communicated 962 periodically, and upon change. 964 7. Parallel Metering Processes 966 Because of the increasing number of distinct measurement 967 applications, with varying requirements, it is desirable to set 968 up parallel Metering Processes on a given Observed Packet Stream. 969 A device capable of hosting a Metering Process should be able to 970 support more than one independently configurable Metering Process 971 simultaneously. Each such Metering Process should have the 972 option of being equipped with its own Exporting Process; 973 otherwise the parallel Metering Processes may share the same 974 Exporting Process. 976 Each of the parallel Metering Processes should be independent. 977 However, resource constraints may prevent complete reporting on a 978 packet selected by multiple Selection Processes. In this case, 979 reporting for the packet must be complete for at least one 980 Metering Process; other Metering Processes need only record that 981 they selected the packet, e.g., by incrementing a counter. The 982 priority amongst Metering Processes under resource contention 983 should be configurable. 985 It is not proposed to standardize the number of parallel Metering 986 Processes. 988 8. Exporting Process 990 This section details specific requirements for the Exporting 991 Process, motivated by the generic requirements of Section 3.6 993 8.1 Use of IPFIX 995 PSAMP will use the IP Flow Information eXport (IPFIX) protocol 996 for export of the Report Stream. The IPFIX protocol is well 997 suited for this purpose, because the IPFIX architecture matches 998 the PSAMP architecture very well and the means provided by the 999 IPFIX protocol are sufficient for PSAMP purposes. On the other 1000 hand, not all features of the IPFIX protocol will need to be 1001 implemented by some PSAMP devices. For example, a device that 1002 offers only content-independent sampling and basic PSAMP 1003 reporting has no need to support IPFIX capabilities based on 1004 packet fields. 1006 8.2 Export Packets 1008 Export packets may contain one or more Packet Reports, and/or 1009 Report Interpretation. Export packets must also contain: 1011 (i) An identifier for the Exporting Process 1013 (ii) An export packet sequence number. 1015 An export packet sequence number enables the Collector to 1016 identify loss of export packets in transit. Note that some 1017 transport protocols, e.g. UDP, do not provide sequence 1018 numbers. Moreover, having sequence numbers available at the 1019 application level enables the Collector to calculate packet 1020 loss rate for use, e.g., in estimating original traffic 1021 volumes from export packet that reach the Collector. 1023 8.3 Congestion-aware Unreliable Transport 1025 The export of the Report Stream does not require reliable export. 1026 Section 5.4 shows that the use of input sequence numbers in 1027 packet Selectors means that the ability to estimate traffic rates 1028 is not impaired by export loss. Export packet loss becomes 1029 another form of sampling, albeit a less desirable, and less 1030 controlled, form of sampling. 1032 In distinction, retransmission of lost Export Packets consumes 1033 additional network resources. The requirement to store 1034 unacknowledged data is an impediment to having ubiquitous support 1035 for PSAMP. 1037 In order to jointly satisfy the timeliness and congestion 1038 avoidance requirements of Section 4.3, a congestion-aware 1039 unreliable transport protocol may be used. IPFIX is compatible 1040 with this requirement, since it mandates support of the Stream 1041 Control Transmission Protocol (SCTP) [RFC-4960] and the SCTP 1042 Partial Reliability Extension [RFC-3758]. 1044 IPFIX also allows the use of User Datagram Protocol (UDP) [RFC- 1045 768] although it is not a congestion-aware protocol. However, in 1046 this case, the Export Packets must remain wholly within the 1047 administrative domains of the operators [RFC-5101]. The PSAMP 1048 exporting process is equipped with a configurable export rate 1049 limit (see Section 8.4 following) that can be used to limit the 1050 export rate when a congestion aware transport protocol is not 1051 used. The Collector, upon detection of export packet loss 1052 through missing export sequence numbers, may reconfigure the 1053 export rate limit downwards in order to avoid congestion. 1055 8.4 Configurable Export Rate Limit 1057 The exporting process must have an export rate limit, 1058 configurable per Exporting Process. This is useful for two 1059 reasons: 1061 (i) Even without network congestion, the rate of packet 1062 selection may exceed the capacity of the Collector to 1063 process reports, particularly when many Exporting Processes 1064 feed a common Collector. Use of an Export Rate Limit allows 1065 control of the global input rate to the Collector. 1067 (ii) IPFIX provides export using UDP as the transport 1068 protocol in some circumstances. An Export Rate Limit allows 1069 the capping of the export rate to match both path link 1070 speeds and the capacity of the Collector. 1072 8.5 Limiting Delay for Export Packets 1074 Low measurement latency allows the traffic monitoring system to 1075 be more responsive to real-time network events, for example, in 1076 quickly identifying sources of congestion. Timeliness is 1077 generally a good thing for devices performing the sampling since 1078 it minimizes the amount of memory needed to buffer samples. 1080 Keeping the packet dispatching delay small has other benefits 1081 besides limiting buffer requirements. For many applications a 1082 resolution of 1 second is sufficient. Applications in this 1083 category would include: identifying sources associated with 1084 congestion, tracing denial of service attacks through the 1085 network, and constructing traffic matrices. Furthermore, keeping 1086 dispatch delay within the resolution required by applications 1087 eliminates the need for timestamping by synchronized clocks at 1088 observation points, or for the Observation Points and Collector 1089 to maintain bi-directional communication in order to track clock 1090 offsets. The Collector can simply process Packet Reports in the 1091 order that they are received, using its own clock as a "global" 1092 time base. This avoids the complexity of buffering and 1093 reordering samples. See [DuGeGr02] for an example. 1095 The delay between observation of a packet and transmission of a 1096 Export Packet containing a report on that packet has several 1097 components. It is difficult to standardize a given numerical 1098 delay requirement, since in practice the delay may be sensitive 1099 to processor load at the Observation Point. Therefore, PSAMP 1100 aims to control that portion of the delay within the Observation 1101 Point that is due to buffering in the formation and transmission 1102 of Export Packets. 1104 In order to limit delay in the formation of Export Packets, the 1105 Exporting Process must provide the ability to close out and 1106 enqueue for transmission any Export Packet during formation as 1107 soon as it includes one Packet Report. 1109 In order to limit the delay in the transmission of Export 1110 Packets, a configurable upper bound to the delay of an Export 1111 Packet prior to transmission must be provided. If the bound is 1112 exceeded the Export Packet is dropped. This functionality can be 1113 provided by the timed reliability service of the SCTP Partial 1114 Reliability Extension [RFC-3758]. 1116 The Exporting Process may enqueue the Report Stream in order to 1117 export multiple Packet Reports in a single export packet. Any 1118 consequent delay must still allow for timely availability of 1119 Packet Reports as just described. The timed reliability service 1120 of the SCTP Partial Reliability Extension [RFC-3758] allows the 1121 dropping of packets from the export buffer once their age in the 1122 buffer exceeds a configurable bound. A suitable default value 1123 for the bound should be used in order to avoid a low transmission 1124 rate due to misconfiguration. 1126 8.6 Export Packet Compression 1128 To conserve network bandwidth and resources at the Collector, the 1129 Export Packets may be compressed before export. Compression is 1130 expected to be quite effective since the sampled packets may 1131 share many fields in common, e.g. if a filter focuses on packets 1132 with certain values in particular header fields. Using 1133 compression, however, could impact the timeliness of Packet 1134 Reports. Any consequent delay must not violate the timeliness 1135 requirement for availability of Packet Reports at the Collector. 1137 8.7 Collector Destination 1139 When exporting to a remote Collector, the Collector is identified 1140 by IP address, transport protocol, and transport port number. 1142 8.8 Local Export 1144 The Report Stream may be directly exported to on-board 1145 measurement based applications, for example those that form 1146 composite statistics from more than one packet. Local export may 1147 be presented through an interface direct to the higher level 1148 applications, i.e., through an API, rather than employing the 1149 transport used for off-board export. Specification of such an 1150 API is outside the scope of the PSAMP framework. 1152 A possible example of Local Export could be that packets selected 1153 by the PSAMP Metering Process serve as the input for the IPFIX 1154 protocol, which then forms flow records out of the stream of 1155 selected packets. 1157 9. Configuration and Management 1159 A key requirement for PSAMP is the easy reconfiguration of the 1160 parameters of the Metering Process, including those for selection 1161 and packet reports, and of the Exporting Process. An important 1162 example is to support measurement-based applications that want to 1163 adaptively drill-down on traffic detail in real-time. 1165 To facilitate retrieval and monitoring of parameters, they are to 1166 reside in a Management Information Base (MIB). Mandatory 1167 monitoring objects will cover all mandatory PSAMP functionality. 1168 Alarming of specific parameters could be triggered with 1169 thresholding mechanisms such as the RMON event and alarm [RFC- 1170 2819] or the event MIB [RFC-2981]. 1172 For configuring parameters of the Metering Process, several 1173 alternatives are available including a MIB module with writeable 1174 objects, as well as other configuration protocols. For 1175 configuring parameters of the Exporting Process, the Packet 1176 Report, and the Report Interpretation, which is an IFPIX task, 1177 the IPFIX configuration method(s) should be used. 1179 Although management and configuration of collectors is out of 1180 scope, a PSAMP device, to the extent that it employs IPFIX as an 1181 export protocol, inherits from IPFIX the capability to detect and 1182 recover from collector failure; see Section 8.2 of [IPFIX-ARCH]. 1184 10. Feasibility and Complexity 1186 In order for PSAMP to be supported across the entire spectrum of 1187 networking equipment, it must be simple and inexpensive to 1188 implement. One can envision easy-to-implement instances of the 1189 mechanisms described within this draft. Thus, for that subset of 1190 instances, it should be straightforward for virtually all system 1191 vendors to include them within their products. Indeed, sampling 1192 and filtering operations are already realized in available 1193 equipment. 1195 Here we give some specific arguments to demonstrate feasibility 1196 and comment on the complexity of hardware implementations. We 1197 stress here that the point of these arguments is not to favor or 1198 recommend any particular implementation, or to suggest a path for 1199 standardization, but rather to demonstrate that the set of 1200 possible implementations is not empty. 1202 10.1 Feasibility 1204 10.1.1 Filtering 1206 Filtering consists of a small number of mask (bit-wise logical), 1207 comparison and range (greater than) operations. Implementation 1208 of at least a small number of such operations is straightforward. 1209 For example, filters for security access control lists (ACLs) are 1210 widely implemented. This could be as simple as an exact match on 1211 certain fields, or involve more complex comparisons and ranges. 1213 10.1.2 Sampling 1215 Sampling based on either counters (counter set, decrement, test 1216 for equal to zero) or range matching on the hash of a packet 1217 (greater than) is possible given a small number of selectors, 1218 although there may be some differences in ease of implementation 1219 for hardware vs. software platforms. 1221 10.1.3 Hashing 1223 Hashing functions vary greatly in complexity. Execution of a 1224 small number of sufficient simple hash functions is implementable 1225 at line rate. Concerning the input to the hash function, 1226 hop-invariant IP header fields (IP address, IP identification) 1227 and TCP/UDP header fields (port numbers, TCP sequence number) 1228 drawn from the first 40 bytes of the packet have been found to 1229 possess a considerable variability; see [DuGr01]. 1231 10.1.4 Reporting 1232 The simplest Packet Report would duplicate the first n bytes of 1233 the packet. However, such an uncompressed format may tax the 1234 bandwidth available to the Exporting Process for high sampling 1235 rates; reporting selected fields would save on this bandwidth. 1236 Thus there is a trade-off between simplicity and bandwidth 1237 limitations. 1239 10.1.5 Exporting 1241 Ease of exporting export packets depends on the system 1242 architecture. Most systems should be able to support export by 1243 insertion of export packets, even through the software path. 1245 10.2 Potential Hardware Complexity 1247 Achieving low constants for performance while minimizing hardware 1248 resources is, of course, a challenge, especially at very high 1249 clock frequencies. Most of the Selectors, however, are very 1250 basic and their implementations very well understood; in fact, 1251 the average Application Specific Integrated Circuit (ASIC) 1252 designer simply uses canned library instances of these operations 1253 rather than design them from scratch. In addition, networking 1254 equipment generally does not need to run at the fastest clock 1255 rates, further reducing the effort required to get reasonably 1256 efficient implementations. 1258 Simple bit-wise logical operations are easy to implement in 1259 hardware. Such operations (NAND/NOR/XNOR/NOT) directly translate 1260 to four-transistor gates. Each bit of a multiple-bit logical 1261 operation is completely independent and thus can be performed in 1262 parallel incurring no additional performance cost above a single 1263 bit operation. 1265 Comparisons (EQ/NEQ) take O(log(M)) stages of logic, where M is 1266 the number of bits involved in the comparison. The log(M) is 1267 required to accumulate the result into a single bit. 1269 Greater than operations, as used to determine whether a hash 1270 falls in a selection range, are a determination of the most 1271 significant not-equivalent bit in the two operands. The operand 1272 with that most-significant-not-equal bit set to be one is greater 1273 than the other. Thus, a greater than operation is also an 1274 O(log(M)) stages of logic operation. Optimized implementations 1275 of arithmetic operations are also O(log(M)) due to propagation of 1276 the carry bit. 1278 Setting a counter is simply loading a register with a state. 1279 Such an operation is simple and fast O(1). Incrementing or 1280 decrementing a counter is a read, followed by an arithmetic 1281 operation followed by a store. Making the register dual-ported 1282 does take additional space, but it is a well-understood 1283 technique. Thus, the increment/decrement is also an O(log(M)) 1284 operation. 1286 Hashing functions come in a variety of forms. The computation 1287 involved in a standard Cyclic Redundancy Code (CRC) for example 1288 are essentially a set of XOR operations, where the intermediate 1289 result is stored and XORed with the next chunk of data. There 1290 are only O(1) operations and no log complexity operations. Thus, 1291 a simple hash function, such as CRC or generalizations thereof, 1292 can be implemented in hardware very efficiently. 1294 At the other end of the range of complexity, the MD5 function 1295 uses a large number of bit-wise conditional operations and 1296 arithmetic operations. The former are O(1) operations and the 1297 latter are O(log(M)). MD5 specifies 256 32b ADD operations per 1298 16B of input processed. Consider processing 10Gb/sec at 100MHz 1299 (this processing rate appears to be currently available). This 1300 requires processing 12.5B/cycle, and hence at least 200 adders, a 1301 sizeable number. Because of data dependencies within the MD5 1302 algorithm, the adders cannot be simply run in parallel, thus 1303 requiring either faster clock rates and/or more advanced 1304 architectures. Thus, selection hashing functions as complex as 1305 MD5 may be precluded for ubiquitous use at full line rate. This 1306 motivates exploring the use of selection hash functions with 1307 complexity somewhere between that of MD5 and CRC. In some 1308 applications (see Section below) a second hash may be calculated 1309 on only selected packets; MD5 is feasible for this purpose if the 1310 rate of production of selected packets is sufficiently low. 1312 11. Applications 1314 We first describe several representative operational applications 1315 that require traffic measurements at various levels of temporal 1316 and spatial granularity. Some of the goals here appear similar 1317 to those of IPFIX, at least in the broad classes of applications 1318 supported. The major benefit of PSAMP is the support of new 1319 network management applications, specifically, those enabled by 1320 the packet Selectors that it supports. 1322 11.1 Baseline Measurement and Drill Down 1324 Packet sampling is ideally suited to determine the composition of 1325 the traffic across a network. The approach is to enable 1326 measurement on a cut-set of the network links such that each 1327 packet entering the network is seen at least once, for example, 1328 on all ingress links. Unfiltered sampling with a relatively low 1329 selection fraction establishes baseline measurements of the 1330 network traffic. Packet Reports include packet attributes of 1331 common interest: source and destination address and port numbers, 1332 prefix, protocol number, type of service, etc. Traffic matrices 1333 are indicated by reporting source and destination AS matrices. 1334 Absolute traffic volumes are estimated by renormalizing the 1335 sampled traffic volumes through division by either the Configured 1336 Selection Fraction, or by the Attained Selection Fraction (as 1337 derived from input packet counters included in the Report Stream) 1339 Suppose an operator or a measurement-based application detects an 1340 interesting subset of a Packet Stream, as identified by a 1341 particular packet attribute. Real-time drill-down to that subset 1342 is achieved by instantiating a new Metering Process on the same 1343 Observed Packet Stream from which the subset was reported. The 1344 Selection Process of the new Metering Process filters according 1345 to the attribute of interest, and composes with sampling if 1346 necessary to manage the attained fraction of packets selected. 1348 11.2 Trajectory Sampling 1350 The goal of trajectory sampling is the selection of a subset of 1351 packets at all enabled Observation Points at which they are 1352 observed in a network domain. Thus the selection decisions are 1353 consistent in the sense that each packet is selected either at 1354 all enabled Observation Points, or at none of them. Trajectory 1355 sampling is realized by hash-based selection if all enabled 1356 Observation Points apply a common hash function to a portion of 1357 the Packet Content that is invariant along the packet path. 1358 (Thus, fields such at TTL and CRC are excluded). 1360 The trajectory followed by a packet is reconstructed from Packet 1361 Reports on it that reach the Collector. Reports on a given 1362 packet are associated either by matching a label comprising the 1363 invariant reported Packet Content, or possibly some digest of it. 1364 The reconstruction of trajectories, and methods for dealing with 1365 possible ambiguities due to label collisions (identical labels 1366 reported by different packets) and potential loss of reports in 1367 transmission are dealt with in [DuGr01], [DuGeGr02] and [DuGr04]. 1369 11.3 Passive Performance Measurement 1371 Trajectory sampling enables the tracking of the performance 1372 experience by customer traffic, customers identified by a list of 1373 source or destination prefixes, or by ingress or egress 1374 interfaces. Operational uses include the verification of Service 1375 Level Agreements (SLAs), and troubleshooting following a customer 1376 complaint. 1378 In this application, trajectory sampling is enabled at all 1379 network ingress and egress interfaces. Rates of loss in transit 1380 between ingress and egress are estimated from the proportion of 1381 trajectories for which no egress report is received. Note that 1382 loss of customer packets is distinguishable from loss of packet 1383 reports through use of report sequence numbers. Assuming 1384 synchronization of clocks between different entities, delay of 1385 customer traffic across the network may also be measured; see 1386 [Zs02]. 1388 Extending hash-selection to all interfaces in the network would 1389 enable attribution of poor performance to individual network 1390 links. 1392 11.4 Troubleshooting 1394 PSAMP Packet Reports can also be used to diagnose problems whose 1395 occurrence is evident from aggregate statistics, per interface 1396 utilization and packet loss statistics. These statistics are 1397 typically moving averages over relatively long time windows, 1398 e.g., 5 minutes, and serve as a coarse-grain indication of 1399 operational health of the network. The most common method of 1400 obtaining such measurements are through the appropriate SNMP MIBs 1401 (MIB-II [RFC-1213] and vendor-specific MIBs.) 1403 Suppose an operator detects a link that is persistently 1404 overloaded and experiences significant packet drop rates. There 1405 is a wide range of potential causes: routing parameters (e.g., 1406 OSPF link weights) that are poorly adapted to the traffic matrix, 1407 e.g., because of a shift in that matrix; a denial of service 1408 attack or a flash crowd; a routing problem (link flapping). In 1409 most cases, aggregate link statistics are not sufficient to 1410 distinguish between such causes, and to decide on an appropriate 1411 corrective action. For example, if routing over two links is 1412 unstable, and the links flap between being overloaded and 1413 inactive, this might be averaged out in a 5 minute window, 1414 indicating moderate loads on both links. 1416 Baseline PSAMP measurement of the congested link, as described in 1417 Section 11.1, enables measurements that are fine grained in both 1418 space and time. The operator has to be able to determine how 1419 many bytes/packets are generated for each source/destination 1420 address, port number, and prefix, or other attributes, such as 1421 protocol number, MPLS forwarding equivalence class (FEC), type of 1422 service, etc. This allows the precise determination of the 1423 nature of the offending traffic. For example, in the case of a 1424 Distributed Denial of Service(DDoS) attack, the operator would 1425 see a significant fraction of traffic with an identical 1426 destination address. 1428 In certain circumstances, precise information about the spatial 1429 flow of traffic through the network domain is required to detect 1430 and diagnose problems and verify correct network behavior. In 1431 the case of the overloaded link, it would be very helpful to know 1432 the precise set of paths that packets traversing this link 1433 follow. This would readily reveal a routing problem such as a 1434 loop, or a link with a misconfigured weight. More generally, 1435 complex diagnosis scenarios can benefit from measurement of 1436 traffic intensities (and other attributes) over a set of paths 1437 that is constrained in some way. For example, if a multihomed 1438 customer complains about performance problems on one of the 1439 access links from a particular source address prefix, the 1440 operator should be able to examine in detail the traffic from 1441 that source prefix which also traverses the specified access link 1442 towards the customer. 1444 While it is in principle possible to obtain the spatial flow of 1445 traffic through auxiliary network state information, e.g., by 1446 downloading routing and forwarding tables from routers, this 1447 information is often unreliable, outdated, voluminous, and 1448 contingent on a network model. For operational purposes, a 1449 direct observation of traffic flow provided by trajectory 1450 sampling is more reliable, as it does not depend on any such 1451 auxiliary information. For example, if there was a bug in a 1452 router's software, direct observation would allow the diagnosis 1453 the effect of this bug, while an indirect method would not. 1455 12. Security Considerations 1457 12.1 Relation of PSAMP and IPFIX Security for Exporting Process 1459 As detailed in Section 4.3, PSAMP shares with IPFIX security 1460 requirements for export, namely, confidentiality, integrity and 1461 authenticity of the exported data; see also Sections 6.3 and 10 1462 of [RFC-3917]. Since PSAMP will use IPFIX for export, it can 1463 employ the IPFIX protocol [RFC-5101] to meet its requirements. 1465 12.2 PSAMP Specific Privacy Considerations 1467 In distinction with IPFIX, a PSAMP device may, in some 1468 configurations, report some number of initial bytes of the 1469 packet, which may include some part of a packet payload. This 1470 option is conformant with the requirements of [RFC-2804] since it 1471 does not mandate configurations that would enable capture of an 1472 entire packet stream of a flow: neither a unit sampling rate (1 1473 in 1 sampling) nor reporting a specific number of initial bytes, 1474 are required by the PSAMP protocol. 1476 To preserve privacy of any users acting as sender or receiver of 1477 the observed traffic the contents of the packet reports must be 1478 able to remain confidential in transit between the exporting 1479 PSAMP device and the collector. PSAMP will use IPFIX as the 1480 exporting protocol, and the IPFIX protocol must provide 1481 mechanisms to ensure confidentiality of the exporting process, 1482 for example, encryption of export packets [RFC-5101]. 1484 12.3 Security Considerations for Hash-Based Selection 1485 12.3.1 Modes and Impact of vulnerabilities 1487 A concern for Hash-based Selection is whether some large set of 1488 related packets could be disproportionately sampled, either 1490 (i) through unanticipated behavior in the Hash Function, or 1491 (ii) because the packets had been deliberately crafted to have 1492 this property. 1494 As detailed below, only cryptographic hash functions (e.g. one 1495 based on MD5) employing a private parameter are sufficiently 1496 strong to withstand the range of conceivable attacks. However, 1497 implementation considerations may preclude operating the 1498 strongest hash functions at line rate. For this reason PSAMP is 1499 not expected to standardize around a cryptographic hash function 1500 at the present time. The purpose of this section is to inform 1501 discussion of the vulnerabilities and trade-offs associated with 1502 different hash function choices. Section 6.2.2 of [PSAMP-TECH] 1503 does this in more detail. 1505 An attacker able to predict packet sampling outcomes could craft 1506 a packet stream that could evade selection; or another that could 1507 overwhelm the measurement infrastructure with all its packets 1508 being selected. An attacker may attempt to do this based on 1509 knowledge of the hash function. An attacker could employ 1510 knowledge of selection outcomes of a known packet stream to 1511 reverse engineer parameters of the hash function. This knowledge 1512 could be gathered e.g. from billing information, reactions of 1513 intrusion detection systems, or observation of a report stream. 1515 Since hash-based selection is deterministic, it is vulnerable to 1516 replay attacks. Repetition of a single packet may be noticeable 1517 to other measurement methods if employed (e.g. collection of flow 1518 statistics), whereas a set of distinct packets that appears 1519 statistically similar to regular traffic may be less noticeable. 1520 The impact of replay attacks on hash based selection may be 1521 mitigated by repeated changing of hash function parameters. 1522 . 1524 12.3.2 Use of Private Parameters in Hash Functions 1526 Because hash functions for Hash-based selection are to be 1527 standardized and hence public, the packet selection decision must 1528 be controlled by some private quantity associated with the hash- 1529 based Selector. Making private the range of hash values for which 1530 packets are selected is not alone sufficient to prevent an 1531 attacker crafting a stream of distinct packets that are 1532 disproportionately selected. A private parameter must be used 1533 within the hash function, for example, a private modulus in a 1534 hash function, or by concatenating the hash input with a private 1535 string prior to hashing. 1537 12.3.3 Strength of Hash Functions 1539 The specific choice of hash function and it usage determines the 1540 types of potential vulnerability: 1542 * Cryptographic hash functions: when a private parameter is used, 1543 future selection outcomes cannot be predicted even by an 1544 attacker with knowledge of past selection outcomes. 1546 * Non-cryptographic hash functions: 1548 Using knowledge of past selection outcomes: some well known 1549 hash functions, e.g., CRC-32, are vulnerable to attacks, in 1550 the sense that their private parameter can be determined 1551 with knowledge of sufficiently many past selections, even 1552 when a private parameter is used; see [GoRe07]. 1554 No knowledge of past selection outcomes: using a private 1555 parameter hardened the hash function to classes of attacks 1556 that work when the parameter is public, although 1557 vulnerability to future attacks is not precluded. 1559 12.4 Security Guidelines for Configuring PSAMP 1561 Hash-function parameters configured in a PSAMP device are 1562 sensitive information, which must be kept private. As well as 1563 using probing techniques to discover parameters of non- 1564 cryptographic hash functions as described above, implementation 1565 and procedural weaknesses may lead to attackers discovering 1566 parameters, whatever class of hash function is used. The 1567 following measures may prevent this from occurring: 1569 Hash function parameters must not be displayable in cleartext on 1570 PSAMP devices. This reduces the chance for the parameters to be 1571 discovered by unauthorized access to the PSAMP device. 1573 Hash function parameters must not be remotely set in cleartext 1574 over a channel which may be eavesdropped. 1576 Hash function parameters must be changed regularly. Note that 1577 such changes must be synchronized over all PSAMP devices in a 1578 domain under which Trajectory Sampling is employed in order to 1579 maintain consistent sampling of packets over the domain. 1581 Default hash function parameter values should be initialized 1582 randomly, in order to avoid predictable values that attackers 1583 could exploit. 1585 13. IANA Considerations 1587 This document has no actions for IANA. 1589 14. References 1591 14.1 Normative References 1593 [PSAMP-PROTO] B. Claise (Ed.) Packet Sampling (PSAMP) Protocol 1594 Specifications, RFC XXXX. [Currently Internet Draft 1595 draft-ietf-psamp-protocol-09.txt, work in progress, 1596 December 2007.] 1598 [PSAMP-INFO] T. Dietz, F. Dressler, G. Carle, B. Claise, 1599 Information Model for Packet Sampling Exports, RFC XXXX. 1600 [Currently Internet Draft, draft-ietf-psamp-info-08, 1601 February 2008.] 1603 [RFC-5101] B. Claise (Ed.) "Specification of the IP Flow 1604 Information Export (IPFIX) Protocol for the Exchange of 1605 IP Traffic Flow Information'', RFC 5101, January 2008. 1607 [RFC-0791] J. Postel, "Internet Protocol", STD 5, RFC 791, 1608 September 1981. 1610 [RFC-5102] J. Quittek, S. Bryant, B. Claise, P. Aitken, J. Meyer, 1611 "Information Model for IP Flow Information Export", RFC 1612 5102, January 2008. 1614 [RFC-4960] R. Stewart, (ed.) "Stream Control Transmission 1615 Protocol", RFC 4960, September 2007. 1617 [RFC-3758] R. Stewart, M. Ramalho, Q. Xie, M. Tuexen, P. Conrad, 1618 "SCTP Partial Reliability Extension", RFC 3758, May 2004. 1620 [PSAMP-TECH] T. Zseby, M. Molina, F. Raspall, N. G. Duffield, S. 1621 Niccolini, Sampling and Filtering Techniques for IP 1622 Packet Selection, RFC XXXX. [Currently Internet Draft, 1623 draft-ietf-psamp-sample-tech-10.txt, work in progress, 1624 July 2005. 1626 14.2 Informative References 1628 [RFC3704] F. Baker, P. Savola, Ingress Filtering for 1629 Multihomed Networks, RFC3704, March 2004. 1631 [RFC-2205] R. Braden (Ed.), L. Zhang, S. Berson, S. Herzog, 1632 S. Jamin, Resource ReSerVation Protocol (RSVP) - Version 1633 1 Functional Specification, RFC2205, September 1997. 1635 [RFC-2460] S. Deering, R. Hinden, Internet Protocol, Version 1636 6 (IPv6) Specification, RFC 2460, December 1998. 1638 [DuGr01] N. G. Duffield and M. Grossglauser, Trajectory 1639 Sampling for Direct Traffic Observation, IEEE/ACM Trans. 1640 on Networking, 9(3), 280-292, June 2001. 1642 [DuGeGr02] N.G. Duffield, A. Gerber, M. Grossglauser, 1643 Trajectory Engine: A Backend for Trajectory Sampling, 1644 IEEE Network Operations and Management Symposium 2002, 1645 Florence, Italy, April 15-19, 2002. 1647 [DuGr04] N. G. Duffield and M. Grossglauser, Trajectory 1648 Sampling with Unreliable Reporting, Proc IEEE Infocom 1649 2004, Hong Kong, March 2004, 1651 [RFC-2914] S. Floyd, Congestion Control Principles, RFC 1652 2914, September 2000. 1654 [GoRe07] S. Goldberg, J. Rexford, "Security 1655 Vulnerabilities and Solutions for Packet Sampling", IEEE 1656 Sarnoff Symposium, Princeton, NJ, May 2007. 1658 [RFC-2804] IAB and IESG, Network Working Group, IETF Policy 1659 on Wiretapping, RFC 2804, May 2000 1661 [RFC-2981] R. Kavasseri, Ed., ''Event MIB'', RFC 2981, October 1662 2000. 1664 [RFC-1213] K. McCloghrie, M. Rose, Management Information 1665 Base for Network Management of TCP/IP-based 1666 internets:MIB-II, RFC 1213, March 1991. 1668 [RFC-3176] P. Phaal, S. Panchen, N. McKee, InMon 1669 Corporation's sFlow: A Method for Monitoring Traffic in 1670 Switched and Routed Networks, RFC 3176, September 2001 1672 [RFC-2330] V. Paxson, G. Almes, J. Mahdavi, M. Mathis, 1673 Framework for IP Performance Metrics, RFC 2330, May 1998 1675 [RFC-768] J. Postel, "User Datagram Protocol" RFC 768, 1676 August 1980 1678 [RFC-3917] J. Quittek, T. Zseby, B. Claise, S. Zander, 1679 Requirements for IP Flow Information Export, RFC 3917, 1680 October 2004. 1682 [RFC-4271] Y. Rekhter, T. Li, S. Hares, "A Border Gateway 1683 Protocol 4 (BGP-4)", RFC 4271, January 2006. 1685 [RFC-3031] E. Rosen, A. Viswanathan, and R. Callon, 1686 "Multiprotocol Label Switching Architecture", RFC 3031, 1687 January 2001. 1689 [IPFIX-ARCH] G. Sadasivan, N. Browlee, B. Claise, J. 1690 Quittek, ''Architecture for IP Flow Information Exp'', RFC- 1691 XXXX. [currently internet draft draft-ietf-ipfix- 1692 architecture-12, work in progress, September 2006] 1694 [RFC-2819] S. Waldbusser, ''Remote Network Monitoring 1695 Management Information Base'', RFC 2819, May 2000. 1697 [Zs02] T. Zseby, ``Deployment of Sampling Methods for SLA 1698 Validation with Non-Intrusive Measurements'', Proceedings 1699 of Passive and Active Measurement Workshop (PAM 2002), 1700 Fort Collins, CO, USA, March 25-26, 2002 1702 15. Authors' Addresses 1704 Derek Chiou 1705 Department of Electrical and Computer Engineering 1706 University of Texas at Austin 1707 1 University Station, Stop C0803, ENS Building room 135, 1708 Austin TX, 78712, USA 1709 Phone: +1 512 232 7722 1710 Email: Derek@ece.utexas.edu 1712 Benoit Claise 1713 Cisco Systems 1714 De Kleetlaan 6a b1 1715 1831 Diegem 1716 Belgium 1717 Phone: +32 2 704 5622 1718 Email: bclaise@cisco.com 1720 Nick Duffield 1721 AT&T Labs - Research 1722 Room B139 1723 180 Park Ave 1724 Florham Park NJ 07932, USA 1725 Phone: +1 973-360-8726 1726 Email: duffield@research.att.com 1727 Albert Greenberg 1728 One Microsoft Way 1729 Redmond, WA 98052-6399 1730 USA 1731 Phone: +1 425-722-8870 1732 Email: albert@microsoft.com 1734 Matthias Grossglauser 1735 School of Computer and Communication Sciences 1736 EPFL 1737 1015 Lausanne 1738 Switzerland 1739 Email: matthias.grossglauser@epfl.ch 1741 Jennifer Rexford 1742 Department of Computer Science 1743 Princeton University 1744 35 Olden Street 1745 Princeton, NJ 08540-5233, USA 1746 Phone: +1 609-258-5182 1747 Email: jrex@cs.princeton.edu 1749 16. Contributors 1751 Sharon Goldberg contributed to Section 12.3 on security 1752 considerations for hash-based selection. 1754 Sharon Goldberg 1755 Department of Electrical Engineering 1756 Princeton University 1757 F210-K EQuad 1758 Princeton, NJ 08544, USA 1759 Email: goldbe@princeton.edu 1761 17. Acknowledgements 1763 The authors would like to thank Peram Marimuthu and Ganesh 1764 Sadasivan for their input in early versions of this document. 1766 18. Intellectual Property Statements 1768 The IETF takes no position regarding the validity or scope of 1769 any Intellectual Property Rights or other rights that might 1770 be claimed to pertain to the implementation or use of the 1771 technology described in this document or the extent to which 1772 any license under such rights might or might not be 1773 available; nor does it represent that it has made any 1774 independent effort to identify any such rights. Information 1775 on the procedures with respect to rights in RFC documents can 1776 be found in BCP 78 and BCP 79. 1777 Copies of IPR disclosures made to the IETF Secretariat and 1778 any assurances of licenses to be made available, or the 1779 result of an attempt made to obtain a general license or 1780 permission for the use of such proprietary rights by 1781 implementers or users of this specification can be obtained 1782 from the IETF on-line IPR repository at 1783 http://www.ietf.org/ipr. 1785 The IETF invites any interested party to bring to its 1786 attention any copyrights, patents or patent applications, or 1787 other proprietary rights that may cover technology that may 1788 be required to implement this standard. Please address the 1789 information to the IETF at ietf-ipr@ietf.org. 1791 19. Copyright Statement 1793 Copyright (C) The IETF Trust (2008). 1795 This document is subject to the rights, licenses and 1796 restrictions contained in BCP 78, and except as set forth 1797 therein, the authors retain all their rights. 1799 20. Disclaimer 1801 This document and the information contained herein are provided 1802 on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE 1803 REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE 1804 IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL 1805 WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY 1806 WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE 1807 ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR 1808 FITNESS FOR A PARTICULAR PURPOSE.