[要約] RFC 5475は、IPパケットのサンプリングとフィルタリング技術に関する標準仕様です。その目的は、ネットワークトラフィックの分析やモニタリングにおいて、効果的なパケット選択手法を提供することです。

Network Working Group                                           T. Zseby
Request for Comments: 5475                              Fraunhofer FOKUS
Category: Standards Track                                      M. Molina
                                                                   DANTE
                                                             N. Duffield
                                                    AT&T Labs - Research
                                                            S. Niccolini
                                                         NEC Europe Ltd.
                                                              F. Raspall
                                                                EPSC-UPC
                                                              March 2009
        

Sampling and Filtering Techniques for IP Packet Selection

IPパケット選択のためのサンプリングおよびフィルタリング技術

Status of This Memo

本文書の位置付け

This document specifies an Internet standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the "Internet Official Protocol Standards" (STD 1) for the standardization state and status of this protocol. Distribution of this memo is unlimited.

このドキュメントは、インターネットコミュニティのインターネット標準トラックプロトコルを指定し、改善のための議論と提案を要求します。このプロトコルの標準化状態とステータスについては、「インターネット公式プロトコル標準」(STD 1)の現在のエディションを参照してください。このメモの配布は無制限です。

Copyright Notice

著作権表示

Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved.

Copyright(c)2009 IETF Trustおよび文書著者として特定された人。全著作権所有。

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document.

このドキュメントは、BCP 78およびこのドキュメントの公開日(http://trustee.ietf.org/license-info)に有効なIETFドキュメントに関連するIETF Trustの法的規定の対象となります。この文書に関するあなたの権利と制限を説明するので、これらの文書を注意深く確認してください。

This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English.

このドキュメントには、2008年11月10日までに公開または公開されたIETFドキュメントまたはIETFの貢献からの資料が含まれている場合があります。IETF標準プロセスの外。そのような資料の著作権を制御する人から適切なライセンスを取得しないと、このドキュメントはIETF標準プロセスの外側に変更されない場合があり、その派生作業は、ITF標準プロセスの外側で作成されない場合があります。RFCとしての出版または英語以外の言語に翻訳する。

Abstract

概要

This document describes Sampling and Filtering techniques for IP packet selection. It provides a categorization of schemes and defines what parameters are needed to describe the most common selection schemes. Furthermore, it shows how techniques can be combined to build more elaborate packet Selectors. The document provides the basis for the definition of information models for configuring selection techniques in Metering Processes and for reporting the technique in use to a Collector.

このドキュメントは、IPパケット選択のためのサンプリングとフィルタリング手法について説明しています。スキームの分類を提供し、最も一般的な選択スキームを記述するために必要なパラメーターを定義します。さらに、テクニックを組み合わせて、より精巧なパケットセレクターを構築する方法を示しています。このドキュメントは、メータープロセスで選択手法を構成し、使用している手法をコレクターに報告するための情報モデルの定義の基礎を提供します。

Table of Contents

目次

   1. Introduction ....................................................3
      1.1. Conventions Used in This Document ..........................4
   2. PSAMP Documents Overview ........................................4
   3. Terminology .....................................................4
      3.1. Observation Points, Packet Streams, and Packet Content .....4
      3.2. Selection Process ..........................................5
      3.3. Reporting ..................................................7
      3.4. Metering Process ...........................................7
      3.5. Exporting Process ..........................................8
      3.6. PSAMP Device ...............................................8
      3.7. Collector ..................................................8
      3.8. Selection Methods ..........................................8
   4. Categorization of Packet Selection Techniques ..................11
   5. Sampling .......................................................12
      5.1. Systematic Sampling .......................................13
      5.2. Random Sampling ...........................................14
           5.2.1. n-out-of-N Sampling ................................14
           5.2.2. Probabilistic Sampling .............................14
   6. Filtering ......................................................16
      6.1. Property Match Filtering ..................................16
      6.2. Hash-Based Filtering ......................................19
           6.2.1. Application Examples for Coordinated Packet
                  Selection ..........................................19
           6.2.2. Desired Properties of Hash Functions ...............21
           6.2.3. Security Considerations for Hash Functions .........22
           6.2.4. Choice of Hash Function ............................26
   7. Parameters for the Description of Selection Techniques .........29
      7.1. Description of Sampling Techniques ........................30
      7.2. Description of Filtering Techniques .......................31
   8. Composite Techniques ...........................................34
      8.1. Cascaded Filtering->Sampling or Sampling->Filtering .......34
      8.2. Stratified Sampling .......................................34
   9. Security Considerations ........................................35
   10. Contributors ..................................................36
   11. Acknowledgments ...............................................36
      12. References ....................................................36
      12.1. Normative References .....................................36
      12.2. Informative References ...................................36
   Appendix A. Hash Functions ........................................40
   A.1 IP Shift-XOR (IPSX) Hash Function..............................40
   A.2 BOB Hash Function..............................................41
        
1. Introduction
1. はじめに

There are two main drivers for the evolution in measurement infrastructures and their underlying technology. First, network data rates are increasing, with a concomitant growth in measurement data. Second, the growth is compounded by the demand of measurement-based applications for increasingly fine-grained traffic measurements. Devices that perform the measurements, require increasingly sophisticated and resource-intensive measurement capabilities, including the capture of packet headers or even parts of the payload, and classification for flow analysis. All these factors can lead to an overwhelming amount of measurement data, resulting in high demands on resources for measurement, storage, transfer, and post processing.

測定インフラストラクチャとその基礎となる技術の進化には、2つの主要なドライバーがあります。まず、ネットワークデータレートが増加しており、測定データが付随する成長が可能です。第二に、成長は、ますます微調整されたトラフィック測定のための測定ベースのアプリケーションの需要によって悪化します。測定を実行するデバイスには、パケットヘッダーまたはペイロードの一部のキャプチャやフロー分析の分類など、ますます洗練されたリソース集約型測定機能が必要です。これらのすべての要因は、圧倒的な量の測定データにつながる可能性があり、その結果、測定、保管、転送、および後処理のためのリソースに対する高い要求が得られます。

The sustained capture of network traffic at line rate can be performed by specialized measurement hardware. However, the cost of the hardware and the measurement infrastructure required to accommodate the measurements preclude this as a ubiquitous approach. Instead, some form of data reduction at the point of measurement is necessary.

ラインレートでのネットワークトラフィックの持続的なキャプチャは、特殊な測定ハードウェアによって実行できます。ただし、測定に対応するために必要なハードウェアと測定インフラストラクチャのコストは、これを遍在するアプローチとして排除します。代わりに、測定ポイントでの何らかの形のデータ削減が必要です。

This can be achieved by an intelligent packet selection through Sampling or Filtering. Another way to reduce the amount of data is to use aggregation techniques (not addressed in this document). The motivation for Sampling is to select a representative subset of packets that allow accurate estimates of properties of the unsampled traffic to be formed. The motivation for Filtering is to remove all packets that are not of interest. Aggregation combines data and allows compact pre-defined views of the traffic. Examples of applications that benefit from packet selection are given in [RFC5474]. Aggregation techniques are out of scope of this document.

これは、サンプリングまたはフィルタリングを通じてインテリジェントなパケット選択によって実現できます。データの量を減らす別の方法は、集約手法を使用することです(このドキュメントでは対処されていません)。サンプリングの動機は、サンプリングされていないトラフィックのプロパティの正確な推定値を形成できるようにするパケットの代表的なサブセットを選択することです。フィルタリングの動機は、興味のないすべてのパケットを削除することです。集約はデータを組み合わせて、トラフィックのコンパクトな事前定義されたビューを可能にします。パケット選択から恩恵を受けるアプリケーションの例は、[RFC5474]に記載されています。集約手法は、このドキュメントの範囲外です。

1.1. Conventions Used in This Document
1.1. このドキュメントで使用されている規則

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].

この文書のキーワード "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", および "OPTIONAL" はRFC 2119 [RFC2119]で説明されているように解釈されます。

2. PSAMP Documents Overview
2. PSAMPドキュメントの概要

This document is one out of a series of documents from the PSAMP group.

このドキュメントは、PSAMPグループの一連のドキュメントの1つです。

[RFC5474]: "A Framework for Packet Selection and Reporting" describes the PSAMP framework for network elements to select subsets of packets by statistical and other methods, and to export a stream of reports on the selected packets to a Collector.

[RFC5474]:「パケット選択とレポートのフレームワーク」は、統計的およびその他の方法でパケットのサブセットを選択し、選択したパケットのレポートのストリームをコレクターにエクスポートするためのネットワーク要素のPSAMPフレームワークを説明します。

RFC 5475 (this document): "Sampling and Filtering Techniques for IP Packet Selection" describes the set of packet selection techniques supported by PSAMP.

RFC 5475(このドキュメント):「IPパケット選択のためのサンプリングとフィルタリング手法」は、PSAMPがサポートするパケット選択手法のセットについて説明しています。

[RFC5476]: "Packet Sampling (PSAMP) Protocol Specifications" specifies the export of packet information from a PSAMP Exporting Process to a PSAMP Collecting Process.

[RFC5476]:「パケットサンプリング(PSAMP)プロトコル仕様」は、PSAMPエクスポートプロセスからPSAMP収集プロセスへのパケット情報のエクスポートを指定します。

[RFC5477]: "Information Model for Packet Sampling Exports" defines an information and data model for PSAMP.

[RFC5477]:「パケットサンプリングエクスポートの情報モデル」は、PSAMPの情報とデータモデルを定義します。

3. Terminology
3. 用語

The PSAMP terminology defined here is fully consistent with all terms listed in [RFC5474] but includes additional terms required for the description of packet selection methods. An architecture overview and possible configurations of PSAMP elements can be found in [RFC5474]. PSAMP terminology also aims at consistency with terms used in [RFC3917]. The relationship between PSAMP and IPFIX terms is described in [RFC5474].

ここで定義されているPSAMP用語は、[RFC5474]にリストされているすべての用語と完全に一致していますが、パケット選択方法の説明に必要な追加の用語が含まれています。PSAMP要素のアーキテクチャの概要と可能な構成は、[RFC5474]に記載されています。PSAMP用語は、[RFC3917]で使用される用語との一貫性も目的としています。PSAMP用語とIPFIX用語の関係は、[RFC5474]で説明されています。

In the PSAMP documents, all defined PSAMP terms are written capitalized. This document uses the same convention.

PSAMPドキュメントでは、定義されたすべてのPSAMP用語が大文字に記載されています。このドキュメントでは、同じ条約を使用しています。

3.1. Observation Points, Packet Streams, and Packet Content
3.1. 観測ポイント、パケットストリーム、およびパケットコンテンツ

* Observation Point

* 観測点

An Observation Point [RFC5101] is a location in the network where packets can be observed. Examples include:

観測点[RFC5101]は、パケットを観察できるネットワーク内の場所です。例は次のとおりです。

(i) A line to which a probe is attached;

(i) プローブが取り付けられている線。

(ii) a shared medium, such as an Ethernet-based LAN;

(ii)イーサネットベースのLANなどの共有媒体。

(iii) a single port of a router, or set of interfaces (physical or logical) of a router;

(iii)ルーターの単一のポート、またはルーターのインターフェイスのセット(物理的または論理的)。

(iv) an embedded measurement subsystem within an interface.

(iv)インターフェイス内の埋め込み測定サブシステム。

Note that one Observation Point may be a superset of several other Observation Points. For example, one Observation Point can be an entire line card. This would be the superset of the individual Observation Points at the line card's interfaces.

1つの観測点は、他のいくつかの観測点のスーパーセットである可能性があることに注意してください。たとえば、1つの観測点は、ラインカード全体にすることができます。これは、ラインカードのインターフェイスでの個々の観測ポイントのスーパーセットになります。

* Observed Packet Stream

* 観察されたパケットストリーム

The Observed Packet Stream is the set of all packets observed at the Observation Point.

観測されたパケットストリームは、観測点で観察されるすべてのパケットのセットです。

* Packet Stream

* パケットストリーム

A Packet Stream denotes a set of packets from the Observed Packet Stream that flows past some specified point within the Metering Process. An example of a Packet Stream is the output of the selection process. Note that packets selected from a stream, e.g., by Sampling, do not necessarily possess a property by which they can be distinguished from packets that have not been selected. For this reason, the term "stream" is favored over "flow", which is defined as a set of packets with common properties [RFC3917].

パケットストリームは、メータープロセス内で指定されたポイントを通過するものを流れる観測されたパケットストリームからのパケットのセットを示します。パケットストリームの例は、選択プロセスの出力です。ストリームから選択されたパケット、たとえば、サンプリングにより、選択されていないパケットと区別できるプロパティを必ずしも所有しているわけではないことに注意してください。このため、「ストリーム」という用語は「フロー」よりも好まれます。これは、共通のプロパティを持つパケットのセットとして定義されます[RFC3917]。

* Packet Content

* パケットコンテンツ

The Packet Content denotes the union of the packet header (which includes link layer, network layer, and other encapsulation headers) and the packet payload. At some Observation Points, the link header information may not be available.

パケットコンテンツは、パケットヘッダーのユニオン(リンクレイヤー、ネットワークレイヤー、およびその他のカプセル化ヘッダーを含む)とパケットペイロードを示します。いくつかの観測点では、リンクヘッダー情報が利用できない場合があります。

3.2. Selection Process
3.2. 選択プロセス

* Selection Process

* 選択プロセス

A Selection Process takes the Observed Packet Stream as its input and selects a subset of that stream as its output.

選択プロセスは、観測されたパケットストリームを入力として使用し、そのストリームのサブセットを出力として選択します。

* Selection State

* 選択状態

A Selection Process may maintain state information for use by the Selection Process. At a given time, the Selection State may depend on packets observed at and before that time, and other variables. Examples include:

選択プロセスは、選択プロセスによって使用される状態情報を維持する場合があります。特定の時点で、選択状態は、その時以前に観測されたパケットおよびその他の変数に依存する場合があります。例は次のとおりです。

(i) sequence numbers of packets at the input of Selectors;

(i) セレクターの入力でのパケットのシーケンス番号。

(ii) a timestamp of observation of the packet at the Observation Point;

(ii)観測点でのパケットの観測のタイムスタンプ。

(iii) iterators for pseudorandom number generators;

(iii)擬似ランダム番号ジェネレーターの反復因子。

(iv) hash values calculated during selection;

(iv)選択中に計算されたハッシュ値。

(v) indicators of whether the packet was selected by a given Selector.

(v) パケットが特定のセレクターによって選択されたかどうかの指標。

Selection Processes may change portions of the Selection State as a result of processing a packet. Selection State for a packet is to reflect the state after processing the packet.

選択プロセスは、パケットを処理した結果として、選択状態の一部を変更する場合があります。パケットの選択状態は、パケットを処理した後の状態を反映することです。

* Selector

* セレクタ

A Selector defines what kind of action a Selection Process performs on a single packet of its input. If selected, the packet becomes an element of the output Packet Stream.

セレクターは、入力の単一パケットで選択プロセスが実行されるアクションの種類を定義します。選択した場合、パケットは出力パケットストリームの要素になります。

The Selector can make use of the following information in determining whether a packet is selected:

セレクターは、パケットが選択されているかどうかを判断する際に、次の情報を利用できます。

(i) the Packet Content;

(i) パケットコンテンツ。

(ii) information derived from the packet's treatment at the Observation Point;

(ii)観測点でのパケットの処理から派生した情報。

(iii) any Selection State that may be maintained by the Selection Process.

(iii)選択プロセスによって維持される可能性のある選択状態。

* Composite Selector

* 複合セレクター

A Composite Selector is an ordered composition of Selectors, in which the output Packet Stream issuing from one Selector forms the input Packet Stream to the succeeding Selector.

複合セレクターは、1つのセレクターから発行される出力パケットストリームが入力パケットストリームを後続のセレクターに形成するセレクターの順序付けられた構成です。

* Primitive Selector

* プリミティブセレクター

A Selector is primitive if it is not a Composite Selector.

複合セレクターではない場合、セレクターは原始的です。

* Selection Sequence

* 選択シーケンス

From all the packets observed at an Observation Point, only a few packets are selected by one or more Selectors. The Selection Sequence is a unique value per Observation Domain describing the Observation Point and the Selector IDs through which the packets are selected.

観測点で観察されたすべてのパケットから、1つ以上のセレクターによって選択されているパケットはごくわずかです。選択シーケンスは、観測点とパケットが選択されているセレクターIDを説明する観測ドメインごとの一意の値です。

3.3. Reporting
3.3. 報告

* Packet Reports

* パケットレポート

Packet Reports comprise a configurable subset of a packet's input to the Selection Process, including the Packet's Content, information relating to its treatment (for example, the output interface), and its associated Selection State (for example, a hash of the Packet's Content).

パケットレポートでは、パケットのコンテンツ、その処理に関する情報(出力インターフェイスなど)、および関連する選択状態(たとえば、パケットのコンテンツのハッシュ)など、選択プロセスへのパケットの入力の構成可能なサブセットを含むものです。。

* Report Interpretation

* 解釈を報告します

Report Interpretation comprises subsidiary information, relating to one or more packets, that is used for interpretation of their Packet Reports. Examples include configuration parameters of the Selection Process.

レポート解釈は、パケットレポートの解釈に使用される1つ以上のパケットに関連する子会社情報で構成されています。例には、選択プロセスの構成パラメーターが含まれます。

* Report Stream

* レポートストリーム

The Report Stream is the output of a Metering Process, comprising two distinguished types of information: Packet Reports and Report Interpretation.

レポートストリームは、2つの著名な種類の情報、つまりパケットレポートとレポート解釈で構成される計測プロセスの出力です。

3.4. Metering Process
3.4. 計量プロセス

A Metering Process selects packets from the Observed Packet Stream using a Selection Process, and produces as output a Report Stream concerning the selected packets.

メータリングプロセスは、選択プロセスを使用して観測されたパケットストリームからパケットを選択し、選択したパケットに関するレポートストリームを出力として生成します。

The PSAMP Metering Process can be viewed as analogous to the IPFIX Metering Process [RFC5101], which produces Flow Records as its output, with the difference that the PSAMP Metering Process always contains a Selection Process. The relationship between PSAMP and IPFIX is further described in [RFC5477] and [RFC5474].

PSAMPメータープロセスは、IPFIXメータープロセス[RFC5101]に類似していると見なすことができます。これは、PSAMPメータリングプロセスに常に選択プロセスが含まれているという違いがある場合、その出力としてフローレコードを生成します。PSAMPとIPFIXの関係は、[RFC5477]と[RFC5474]でさらに説明されています。

3.5. Exporting Process
3.5. エクスポートプロセス

* Exporting Process

* エクスポートプロセス

An Exporting Process sends, in the form of Export Packets, the output of one or more Metering Processes to one or more Collectors.

エクスポートプロセスは、エクスポートパケットの形で、1つ以上のコレクターに1つ以上のメータープロセスの出力を送信します。

* Export Packet

* エクスポートパケット

An Export Packet is a combination of Report Interpretations and/or one or more Packet Reports that are bundled by the Exporting Process into an Export Packet for exporting to a Collector.

エクスポートパケットは、レポート解釈および/または1つ以上のパケットレポートの組み合わせであり、エクスポートプロセスによってコレクターへのエクスポートのためにエクスポートパケットにバンドルされます。

3.6. PSAMP Device
3.6. PSAMPデバイス

* PSAMP Device

* PSAMPデバイス

A PSAMP Device is a device hosting at least an Observation Point, a Metering Process (which includes a Selection Process), and an Exporting Process. Typically, corresponding Observation Point(s), Metering Process(es), and Exporting Process(es) are colocated at this device, for example, at a router.

PSAMPデバイスは、少なくとも観測ポイント、メータープロセス(選択プロセスを含む)、およびエクスポートプロセスをホストするデバイスです。通常、対応する観測点、計量プロセス(ES)、およびエクスポートプロセス(ES)は、たとえばルーターなどのこのデバイスでコロッキングされます。

3.7. Collector
3.7. コレクタ

* Collector

* コレクタ

A Collector receives a Report Stream exported by one or more Exporting Processes. In some cases, the host of the Metering and/or Exporting Processes may also serve as the Collector.

コレクターは、1つ以上のエクスポートプロセスによってエクスポートされるレポートストリームを受け取ります。場合によっては、計量プロセスおよび/またはエクスポートプロセスのホストもコレクターとして機能する場合があります。

3.8. Selection Methods
3.8. 選択方法

* Filtering

* フィルタリング

A filter is a Selector that selects a packet deterministically based on the Packet Content, or its treatment, or functions of these occurring in the Selection State. Two examples are:

フィルターは、選択状態で発生するこれらの機能に基づいて決定論的にパケットを決定的に選択するセレクターです。2つの例は次のとおりです。

(i) Property Match Filtering: A packet is selected if a specific field in the packet equals a predefined value.

(i) プロパティマッチフィルタリング:パケット内の特定のフィールドが事前定義された値に等しい場合、パケットが選択されます。

(ii) Hash-based Selection: A Hash Function is applied to the Packet Content, and the packet is selected if the result falls in a specified range.

(ii)ハッシュベースの選択:ハッシュ関数がパケットコンテンツに適用され、結果が指定された範囲にある場合はパケットが選択されます。

* Sampling

* サンプリング

A Selector that is not a filter is called a Sampling operation. This reflects the intuitive notion that if the selection of a packet cannot be determined from its content alone, there must be some type of Sampling taking place. Sampling operations can be divided into two subtypes:

フィルターではないセレクターは、サンプリング操作と呼ばれます。これは、パケットの選択をそのコンテンツだけから決定できない場合、何らかのタイプのサンプリングが行われている必要があるという直感的な概念を反映しています。サンプリング操作は、2つのサブタイプに分類できます。

(i) Content-independent Sampling, which does not use Packet Content in reaching Sampling decisions. Examples include systematic Sampling, and uniform pseudorandom Sampling driven by a pseudorandom number whose generation is independent of Packet Content. Note that in content-independent Sampling, it is not necessary to access the Packet Content in order to make the selection decision.

(i) サンプリングの決定に到達する際にパケットコンテンツを使用しないコンテンツに依存しないサンプリング。例には、系統的なサンプリング、および生成がパケットコンテンツとは無関係の擬似ランダム数によって駆動される均一な擬似ランダムサンプリングが含まれます。コンテンツに依存しないサンプリングでは、選択の決定を下すためにパケットコンテンツにアクセスする必要はないことに注意してください。

(ii) Content-dependent Sampling, in which the Packet Content is used in reaching selection decisions. An application is pseudorandom selection according to a probability that depends on the contents of a packet field, e.g., Sampling packets with a probability dependent on their TCP/UDP port numbers. Note that this is not a Filter.

(ii)選択の決定に到達する際にパケットコンテンツが使用されるコンテンツ依存サンプリング。アプリケーションは、パケットフィールドの内容に依存する確率、たとえばTCP/UDPポート番号に依存する確率のサンプリングパケットに応じた擬似ランダム選択です。これはフィルターではないことに注意してください。

* Hash Domain

* ハッシュドメイン

A Hash Domain is a subset of the Packet Content and the packet treatment, viewed as an N-bit string for some positive integer N.

ハッシュドメインは、パケットコンテンツとパケット処理のサブセットであり、正の整数NのNビット文字列と見なされます。

* Hash Range

* ハッシュ範囲

A Hash Range is a set of M-bit strings for some positive integer M that defines the range of values that the result of the hash operation can take.

ハッシュ範囲は、ハッシュ操作の結果が取ることができる値の範囲を定義する、いくつかの正の整数MのMビット文字列のセットです。

* Hash Function

* ハッシュ関数

A Hash Function defines a deterministic mapping from the Hash Domain into the Hash Range.

ハッシュ関数は、ハッシュドメインからハッシュ範囲への決定論的マッピングを定義します。

* Hash Selection Range

* ハッシュ選択範囲

A Hash Selection Range is a subset of the Hash Range. The packet is selected if the action of the Hash Function on the Hash Domain for the packet yields a result in the Hash Selection Range.

ハッシュ選択範囲は、ハッシュ範囲のサブセットです。パケットがハッシュ選択範囲になった結果を得るためのハッシュドメインでのハッシュ関数のアクションがハッシュ選択範囲になると、パケットが選択されます。

* Hash-based Selection

* ハッシュベースの選択

A Hash-based Selection is Filtering specified by a Hash Domain, a Hash Function, a Hash Range, and a Hash Selection Range.

ハッシュベースの選択は、ハッシュドメイン、ハッシュ関数、ハッシュ範囲、およびハッシュ選択範囲によって指定されたフィルタリングです。

* Approximative Selection

* 近似選択

Selectors in any of the above categories may be approximated by operations in the same or another category for the purposes of implementation. For example, uniform pseudorandom Sampling may be approximated by Hash-based Selection, using a suitable Hash Function and Hash Domain. In this case, the closeness of the approximation depends on the choice of Hash Function and Hash Domain.

上記のカテゴリのいずれかのセレクターは、実装の目的で同じまたは別のカテゴリの操作によって近似できます。たとえば、適切なハッシュ関数とハッシュドメインを使用して、ハッシュベースの選択によって均一な擬似ランダムサンプリングが近似する場合があります。この場合、近似の近さは、ハッシュ関数とハッシュドメインの選択に依存します。

* Population

* 人口

A Population is a Packet Stream or a subset of a Packet Stream. A Population can be considered as a base set from which packets are selected. An example is all packets in the Observed Packet Stream that are observed within some specified time interval.

母集団は、パケットストリームまたはパケットストリームのサブセットです。母集団は、パケットが選択されているベースセットと見なすことができます。例は、指定された時間間隔内で観測される観測されたパケットストリーム内のすべてのパケットです。

* Population Size

* 人口規模

The Population Size is the number of all packets in the Population.

人口サイズは、母集団のすべてのパケットの数です。

* Sample Size

* サンプルサイズ

The Sample Size is a number of packets selected from the Population by a Selector.

サンプルサイズは、セレクターによって母集団から選択された多数のパケットです。

* Configured Selection Fraction

* 構成された選択分数

The Configured Selection Fraction is the expected ratio of the Sample Size to the Population Size, as based on the configured selection parameters.

構成された選択パラメーターに基づいて、構成された選択画分は、サンプルサイズの母集団サイズの予想比です。

* Attained Selection Fraction

* 選択分数を達成しました

The Attained Selection Fraction is the ratio of the actual Sample Size to the Population Size. For some Sampling methods, the Attained Selection Fraction can differ from the Configured Selection Fraction due to, for example, the inherent statistical variability in Sampling decisions of probabilistic Sampling and Hash-based Selection. Nevertheless, for large Population Sizes and properly configured Selectors, the Attained Selection Fraction usually approaches the Configured Selection Fraction.

達成された選択分数は、実際のサンプルサイズと母集団サイズの比率です。一部のサンプリング方法では、達成された選択分数は、たとえば、確率的サンプリングとハッシュベースの選択のサンプリング決定に固有の統計的変動性により、構成された選択分数とは異なります。それにもかかわらず、大規模な人口サイズと適切に構成されたセレクターの場合、達成された選択分数は通常、構成された選択分数に近づきます。

4. Categorization of Packet Selection Techniques
4. パケット選択技術の分類

Packet selection techniques generate a subset of packets from an Observed Packet Stream at an Observation Point. We distinguish between Sampling and Filtering.

パケット選択技術は、観測ポイントで観測されたパケットストリームからパケットのサブセットを生成します。サンプリングとフィルタリングを区別します。

Sampling is targeted at the selection of a representative subset of packets. The subset is used to infer knowledge about the whole set of observed packets without processing them all. The selection can depend on packet position, and/or on Packet Content, and/or on (pseudo) random decisions.

サンプリングは、パケットの代表的なサブセットの選択を対象としています。サブセットは、すべてを処理することなく、観測されたパケットのセット全体に関する知識を推測するために使用されます。選択は、パケットの位置、および/またはパケットコンテンツ、および/または(擬似)ランダム決定に依存します。

Filtering selects a subset with common properties. This is used if only a subset of packets is of interest. The properties can be directly derived from the Packet Content, or depend on the treatment given by the router to the packet. Filtering is a deterministic operation. It depends on Packet Content or router treatment. It never depends on packet position or on (pseudo) random decisions.

フィルタリング共通プロパティを備えたサブセットを選択します。これは、パケットのサブセットのみが興味深い場合に使用されます。プロパティは、パケットコンテンツから直接導出されるか、ルーターによってパケットに与えられた処理に依存することができます。フィルタリングは決定論的操作です。パケットコンテンツまたはルーター処理に依存します。パケットの位置や(擬似)ランダムな決定に依存することはありません。

Note that a common technique to select packets is to compute a Hash Function on some bits of the packet header and/or content and to select it if the hash value falls in the Hash Selection Range. Since hashing is a deterministic operation on the Packet Content, it is a Filtering technique according to our categorization. Nevertheless, Hash Functions are sometimes used to emulate random Sampling. Depending on the chosen input bits, the Hash Function, and the Hash Selection Range, this technique can be used to emulate the random selection of packets with a given probability p. It is also a powerful technique to consistently select the same packet subset at multiple Observation Points [DuGr00].

パケットを選択するための一般的な手法は、パケットヘッダーおよび/またはコンテンツの一部のビットでハッシュ関数を計算し、ハッシュ値がハッシュ選択範囲にある場合にそれを選択することであることに注意してください。ハッシュはパケットコンテンツの決定論的操作であるため、分類に応じてフィルタリング手法です。それにもかかわらず、ハッシュ関数は、ランダムサンプリングをエミュレートするために使用されることがあります。選択した入力ビット、ハッシュ関数、およびハッシュ選択範囲に応じて、この手法を使用して、特定の確率pでパケットのランダム選択をエミュレートできます。また、複数の観測ポイント[DUGR00]で同じパケットサブセットを常に選択することは強力な手法です。

The following table gives an overview of the schemes described in this document and their categorization. X means that the characteristic applies to the selection scheme. (X) denotes schemes for which content-dependent and content-independent variants exist. For instance, Property Match Filtering is typically based on Packet Content and therefore is content dependent. But as explained in Section 6.1, it may also depend on router state and then would be independent of the content. It easily can be seen that only schemes with both properties, content dependence and deterministic selection, are considered as Filters.

次の表は、このドキュメントとその分類で説明されているスキームの概要を示しています。xは、特性が選択スキームに適用されることを意味します。(x)コンテンツ依存およびコンテンツに依存しないバリアントが存在するスキームを示します。たとえば、プロパティマッチフィルタリングは通常、パケットコンテンツに基づいているため、コンテンツに依存します。ただし、セクション6.1で説明したように、ルーター状態に依存し、コンテンツとは独立している可能性があります。両方のプロパティ、コンテンツの依存、および決定論的選択の両方を持つスキームのみがフィルターと見なされることが簡単にわかります。

        Selection Scheme   | Deterministic | Content -| Category
                           |  Selection    | Dependent|
   ------------------------+---------------+----------+----------
    Systematic             |       X       |     _    | Sampling
    Count-based            |               |          |
   ------------------------+---------------+----------+----------
    Systematic             |       X       |     -    | Sampling
    Time-based             |               |          |
   ------------------------+---------------+----------+----------
    Random                 |       -       |     -    | Sampling
    n-out-of-N             |               |          |
   ------------------------+---------------+----------+----------
    Random                 |       -       |     -    | Sampling
    uniform probabilistic  |               |          |
   ------------------------+---------------+----------+----------
    Random                 |       -       |    (X)   | Sampling
    non-uniform probabil.  |               |          |
   ------------------------+---------------+----------+----------
    Random                 |       -       |    (X)   | Sampling
    non-uniform Flow-State |               |          |
   ------------------------+---------------+----------+----------
    Property Match         |       X       |    (X)   | Filtering
    Filtering              |               |          |
   ------------------------+---------------+----------+----------
    Hash function          |       X       |     X    | Filtering
   ------------------------+---------------+----------+----------
        

The categorization just introduced is mainly useful for the definition of an information model describing Primitive Selectors. More complex selection techniques can be described through the composition of cascaded Sampling and Filtering operations. For example, a packet selection that weights the selection probability on the basis of the packet length can be described as a cascade of a Filtering and a Sampling scheme. However, this descriptive approach is not intended to be rigid: if a common and consolidated selection practice turns out to be too complex to be described as a composition of the mentioned building blocks, an ad hoc description can be specified instead and added as a new scheme to the information model.

導入されたばかりの分類は、主にプリミティブセレクターを説明する情報モデルの定義に役立ちます。より複雑な選択技術は、カスケードされたサンプリングおよびフィルタリング操作の構成を通じて説明できます。たとえば、パケットの長さに基づいて選択確率に重み付けされるパケット選択は、フィルタリングとサンプリングスキームのカスケードとして説明できます。ただし、この記述的アプローチは厳格であることを意図していません。一般的で統合された選択の実践が複雑すぎて、上記のビルディングブロックの構成として説明できない場合、代わりにアドホックな説明を指定し、新しいものとして追加できます。情報モデルへのスキーム。

5. Sampling
5. サンプリング

The deployment of Sampling techniques aims at the provisioning of information about a specific characteristic of the parent Population at a lower cost than a full census would demand. In order to plan a suitable Sampling strategy, it is therefore crucial to determine the needed type of information and the desired degree of accuracy in advance.

サンプリング手法の展開は、完全な国勢調査が要求するよりも低コストで親集団の特定の特性に関する情報の提供を目的としています。したがって、適切なサンプリング戦略を計画するには、必要なタイプの情報と、事前に必要な精度を決定することが重要です。

First of all, it is important to know the type of metric that should be estimated. The metric of interest can range from simple packet counts [JePP92] up to the estimation of whole distributions of flow characteristics (e.g., packet sizes) [ClPB93].

まず、推定すべきメトリックのタイプを知ることが重要です。対象のメトリックは、単純なパケット数[JEPP92]から、フロー特性(パケットサイズなど)の全分布の推定までの範囲です[CLPB93]。

Second, the required accuracy of the information and with this, the confidence that is aimed at, should be known in advance. For instance, for usage-based accounting the required confidence for the estimation of packet counters can depend on the monetary value that corresponds to the transfer of one packet. That means that a higher confidence could be required for expensive packet flows (e.g., premium IP service) than for cheaper flows (e.g., best effort). The accuracy requirements for validating a previously agreed quality can also vary extremely with the customer demands. These requirements are usually determined by the service level agreement (SLA).

第二に、情報の必要な精度とこれにより、目的とする自信は事前に知られるべきです。たとえば、使用法ベースの会計の場合、パケットカウンターの推定に必要な信頼性は、1つのパケットの転送に対応する金銭的価値に依存する可能性があります。つまり、安価なフロー(最善の努力など)よりも、高価なパケットフロー(プレミアムIPサービスなど)にはより高い信頼が必要になる可能性があります。以前に合意された品質を検証するための精度要件も、顧客の要求によって非常に異なる場合があります。これらの要件は通常、サービスレベル契約(SLA)によって決定されます。

The Sampling method and the parameters in use must be clearly communicated to all applications that use the measurement data. Only with this knowledge a correct interpretation of the measurement results can be ensured.

サンプリング方法と使用中のパラメーターは、測定データを使用するすべてのアプリケーションに明確に通知する必要があります。この知識でのみ、測定結果の正しい解釈を確保できます。

Sampling methods can be characterized by the Sampling algorithm, the trigger type used for starting a Sampling interval, and the length of the Sampling interval. These parameters are described here in detail. The Sampling algorithm describes the basic process for selection of samples. In accordance to [AmCa89] and [ClPB93], we define the following basic Sampling processes.

サンプリング方法は、サンプリングアルゴリズム、サンプリング間隔の開始に使用されるトリガータイプ、およびサンプリング間隔の長さによって特徴付けられます。これらのパラメーターについては、ここで詳しく説明します。サンプリングアルゴリズムは、サンプルの選択の基本プロセスを説明しています。[AMCA89]および[CLPB93]に従って、次の基本的なサンプリングプロセスを定義します。

5.1. Systematic Sampling
5.1. 体系的なサンプリング

Systematic Sampling describes the process of selecting the start points and the duration of the selection intervals according to a deterministic function. This can be for instance the periodic selection of every k-th element of a trace but also the selection of all packets that arrive at predefined points in time. Even if the selection process does not follow a periodic function (e.g., if the time between the Sampling intervals varies over time), we consider this as systematic Sampling as long as the selection is deterministic.

系統的サンプリングは、決定論的関数に従って、開始点と選択間隔の持続時間を選択するプロセスを説明します。これは、たとえば、トレースのすべてのk番目の要素の周期的な選択であり、事前定義されたポイントに到達するすべてのパケットの選択でもあります。選択プロセスが周期的な関数に従わない場合でも(たとえば、サンプリング間隔の間の時間が時間とともに変化する場合)、選択が決定的である限り、これは系統的なサンプリングと考えます。

The use of systematic Sampling always involves the risk of biasing the results. If the systematics in the Sampling process resemble systematics in the observed stochastic process (occurrence of the characteristic of interest in the network), there is a high probability that the estimation will be biased. Systematics in the observed process might not be known in advance.

体系的なサンプリングの使用には、常に結果にバイアスをかけるリスクが含まれます。サンプリングプロセスの系統学が、観測された確率的プロセス(ネットワークでの関心のある特性の発生)の系統に似ている場合、推定が偏っている可能性が高くなります。観察されたプロセスの系統は、事前に知られていないかもしれません。

Here only equally spaced schemes are considered, where 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.

ここでは、サンプリングのトリガーが時間内またはパケット数のいずれかで周期的である場合、等間隔のスキームのみが考慮されます。トリガーを超えて(時間またはパケットカウント)選択間隔で発生するすべてのパケットが選択されます。

Systematic count-based In systematic count-based Sampling, the start and stop triggers for the Sampling interval are defined in accordance to the spatial packet position (packet count).

体系的なカウントベースのサンプリングにおける系統的カウントベースでは、サンプリング間隔の開始と停止トリガーは、空間パケット位置(パケットカウント)に従って定義されます。

Systematic time-based In systematic time-based Sampling, time-based start and stop triggers are used to define the Sampling intervals. All packets are selected that arrive at the Observation Point within the time intervals defined by the start and stop triggers (i.e., arrival time of the packet is larger than the start time and smaller than the stop time).

体系的な時間ベースの時間ベースのサンプリング、時間ベースの開始および停止トリガーを使用して、サンプリング間隔を定義します。すべてのパケットは、開始トリガーと停止トリガーによって定義された時間間隔内で観測点に到達するすべてのパケットが選択されます(つまり、パケットの到着時間は開始時間よりも大きく、停止時間よりも小さくなります)。

Both schemes are content-independent selection schemes. Content-dependent deterministic Selectors are categorized as filters.

両方のスキームは、コンテンツに依存しない選択スキームです。コンテンツに依存する決定論的セレクターは、フィルターに分類されます。

5.2. Random Sampling
5.2. 無作為抽出

Random Sampling selects the starting points of the Sampling intervals in accordance to a random process. The selection of elements is an independent experiment. With this, unbiased estimations can be achieved. In contrast to systematic Sampling, random Sampling requires the generation of random numbers. One can differentiate two methods of random Sampling: n-out-of-N Sampling and probabilistic Sampling.

ランダムサンプリングは、ランダムプロセスに従ってサンプリング間隔の開始点を選択します。要素の選択は独立した実験です。これにより、公平な推定を達成できます。体系的なサンプリングとは対照的に、ランダムサンプリングには乱数の生成が必要です。ランダムサンプリングの2つの方法を区別できます。N-Out-of-Nサンプリングと確率的サンプリングです。

5.2.1. n-out-of-N Sampling
5.2.1. n-out-of-nサンプリング

In n-out-of-N Sampling, n elements are selected out of the parent Population that consists of N elements. One example would be to generate n different random numbers in the range [1,N] and select all packets that have a packet position equal to one of the random numbers. For this kind of Sampling, the Sample Size n is fixed.

n-out-of-nサンプリングでは、n要素がn要素で構成される親母集団から選択されます。1つの例は、範囲[1、n]でn異なる乱数を生成し、乱数の1つに等しいパケット位置を持つすべてのパケットを選択することです。この種のサンプリングでは、サンプルサイズnが固定されています。

5.2.2. Probabilistic Sampling
5.2.2. 確率的サンプリング

In probabilistic Sampling, the decision whether or not an element is selected is made in accordance to a predefined selection probability. An example would be to flip a coin for each packet and select all packets for which the coin showed the head. For this kind of Sampling, the Sample Size can vary for different trials. The selection probability does not necessarily have to be the same for each packet. Therefore, we distinguish between uniform probabilistic Sampling (with the same selection probability for all packets) and non-uniform probabilistic Sampling (where the selection probability can vary for different packets).

確率的サンプリングでは、要素が選択されているかどうかの決定は、事前定義された選択確率に従って行われます。例としては、各パケットのコインをひっくり返し、コインがヘッドを示したすべてのパケットを選択することです。この種のサンプリングでは、サンプルサイズは試行ごとに異なる場合があります。選択確率は、必ずしもパケットごとに同じである必要はありません。したがって、均一な確率的サンプリング(すべてのパケットで同じ選択確率を使用)と不均一な確率的サンプリング(選択確率が異なるパケットで異なる場合)を区別します。

5.2.2.1. Uniform Probabilistic Sampling
5.2.2.1. 均一な確率的サンプリング

For Uniform Probabilistic Sampling, packets are selected independently with a uniform probability p. This Sampling can be count-driven, and is sometimes referred to as geometric random Sampling, since the difference in count between successive selected packets is an independent random variable with a geometric distribution of mean 1/p. A time-driven analog, exponential random Sampling, has the time between triggers exponentially distributed.

均一な確率的サンプリングの場合、パケットは均一な確率pで独立して選択されます。このサンプリングはカウント駆動型であり、幾何学的なランダムサンプリングと呼ばれることもあります。これは、選択されたパケット間のカウントの違いは、平均1/pの幾何学的分布を持つ独立したランダム変数であるためです。時間駆動のアナログ、指数関数的なランダムサンプリングは、トリガー間の時間を指数関数的に分布させます。

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

幾何学的および指数関数的なランダムサンプリングの両方は、付加ランダムサンプリングと呼ばれるものの例であり、連続サンプル間の間隔またはカウントが独立した同一に分布したランダム変数であるサンプリングとして定義されます。

5.2.2.2. Non-Uniform Probabilistic Sampling
5.2.2.2. 不均一な確率的サンプリング

This is a variant of Probabilistic 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 re-normalization of sample values; see [HT52].

これは、サンプリング確率が選択プロセス入力に依存できる確率的サンプリングのバリアントです。これは、サンプリングの確率を順番に重み付けするために使用できます。定量的統計の偏りのない推定量は、サンプル値の再正規化によって回復されます。[HT52]を参照してください。

5.2.2.3. Non-Uniform Flow State Dependent Sampling
5.2.2.3. 不均一なフロー状態依存サンプリング

Another type of Sampling that can be classified as probabilistic Non-Uniform is closely related to the flow concept as defined in [RFC3917], and it is only used jointly with a flow monitoring function (IPFIX Metering Process). Packets are selected, dependent on a Selection State. The point, here, is that the Selection State is determined also by the state of the flow the packet belongs to and/or by the state of the other flows currently being monitored by the associated flow monitoring function. An example for such an algorithm is the "sample and hold" method described in [EsVa01]:

確率的不均一に分類できる別のタイプのサンプリングは、[RFC3917]で定義されているフロー概念に密接に関連しており、フロー監視関数(IPFIXメータープロセス)と共同でのみ使用されます。選択状態に応じて、パケットが選択されます。ここでのポイントは、選択状態が、パケットが属する流れの状態によっても決定されることです。このようなアルゴリズムの例は、[ESVA01]で説明されている「サンプルと保留」方法です。

- If a packet accounts for a Flow Record that already exists in the IPFIX flow recording process, it is selected (i.e., the Flow Record is updated).

- パケットがIPFIXフロー記録プロセスに既に存在するフローレコードをアカウントする場合、選択されます(つまり、フローレコードが更新されます)。

- If a packet doesn't account for any existing Flow Record, it is selected with probability p. If it has been selected, a new Flow Record has to be created.

- パケットが既存のフローレコードを考慮していない場合、確率pで選択されます。選択した場合、新しいフローレコードを作成する必要があります。

A further algorithm that fits into the category of non-uniform flow state dependent Sampling is described in [Moli03].

不均一なフロー状態依存サンプリングのカテゴリに適合するさらなるアルゴリズムは、[MOLI03]で説明されています。

This type of Sampling is content dependent because the identification of the flow the packet belongs to requires analyzing part of the Packet Content. If the packet is selected, then it is passed as an input to the IPFIX monitoring function (this is called "Local Export" in [RFC5474]). Selecting the packet depending on the state of a flow cache is useful when memory resources of the flow monitoring function are scarce (i.e., there is no room to keep all the flows that have been scheduled for monitoring).

このタイプのサンプリングは、パケットが属するフローの識別にはパケットコンテンツの一部を分析する必要があるため、コンテンツに依存します。パケットが選択されている場合、IPFIX監視関数への入力として渡されます(これは[RFC5474]の「ローカルエクスポート」と呼ばれます)。フローキャッシュの状態に応じてパケットを選択することは、フロー監視関数のメモリリソースが不足している場合に役立ちます(つまり、監視が予定されているすべてのフローを保持する余地はありません)。

5.2.2.4. Configuration of Non-Uniform Probabilistic and Flow State Sampling
5.2.2.4. 不均一な確率的およびフロー状態サンプリングの構成

Many different specific methods can be grouped under the terms non-uniform probabilistic and flow state Sampling. Dependent on the Sampling goal and the implemented scheme, a different number and type of input parameters are required to configure such a scheme.

多くの異なる特定の方法は、不均一な確率的およびフロー状態サンプリングという用語の下でグループ化できます。サンプリングの目標と実装されたスキームに依存して、このようなスキームを構成するには、入力パラメーターの異なる数とタイプが必要です。

Some concrete proposals for such methods exist from the research community (e.g., [EsVa01], [DuLT01], [Moli03]). Some of these proposals are still in an early stage and need further investigations to prove their usefulness and applicability. It is not our aim to indicate preference among these methods. Instead, we only describe here the basic methods and leave the specification of explicit schemes and their parameters up to vendors (e.g., as an extension of the information model).

そのような方法に対するいくつかの具体的な提案は、研究コミュニティから存在します(例:[ESVA01]、[Dult01]、[Moli03])。これらの提案のいくつかはまだ初期段階にあり、それらの有用性と適用性を証明するためにさらなる調査が必要です。これらの方法で好みを示すことは私たちの目的ではありません。代わりに、ここでは基本的な方法についてのみ説明し、明示的なスキームとそのパラメーターの仕様をベンダーに任せます(たとえば、情報モデルの拡張として)。

6. Filtering
6. フィルタリング

Filtering is the deterministic selection of packets based on the Packet Content, the treatment of the packet at the Observation Point, or deterministic functions of these occurring in the Selection State. The packet is selected if these quantities fall into a specified range. The role of Filtering, as the word itself suggest, is to separate all the packets having a certain property from those not having it. A distinguishing characteristic from Sampling is that the selection decision does not depend on the packet position in time or in space, or on a random process.

フィルタリングは、パケットコンテンツ、観測点でのパケットの処理、または選択状態で発生するこれらの決定論的機能に基づくパケットの決定論的選択です。これらの数量が指定された範囲に分類される場合、パケットが選択されます。単語自体が示唆するように、フィルタリングの役割は、特定のプロパティを持っているすべてのパケットを持っていないものと分離することです。サンプリングとの際立った特性は、選択決定が時間や空間のパケット位置、またはランダムプロセスに依存しないことです。

We identify and describe in the following two Filtering techniques.

次の2つのフィルタリング手法で特定して説明します。

6.1. Property Match Filtering
6.1. プロパティマッチフィルタリング

With this Filtering method, a packet is selected if specific fields within the packet and/or properties of the router state equal a predefined value. Possible filter fields are all IPFIX flow attributes specified in [RFC5102]. Further fields can be defined by proposing new information elements or defining vendor-specific extensions.

このフィルタリング方法では、パケット内の特定のフィールドおよび/またはルーター状態のプロパティ内の特定のフィールドが事前定義された値に等しい場合、パケットが選択されます。可能なフィルターフィールドはすべて、[RFC5102]で指定されたIPFIXフロー属性です。新しい情報要素を提案するか、ベンダー固有の拡張機能を定義することにより、さらにフィールドを定義できます。

A packet is selected if Field=Value. Masks and ranges are only supported to the extent to which [RFC5102] allows them, e.g., by providing explicit fields like the netmasks for source and destination addresses.

フィールド=値の場合、パケットが選択されます。マスクと範囲は、[RFC5102]がそれらを許可する範囲でのみサポートされます。たとえば、ソースアドレスや宛先アドレスのネットマスクなどの明示的なフィールドを提供することにより。

AND operations are possible by concatenating filters, thus producing a composite selection operation. In this case, the ordering in which the Filtering happens is implicitly defined (outer filters come after inner filters). However, as long as the concatenation is on filters only, the result of the cascaded filter is independent from the order, but the order may be important for implementation purposes, as the first filter will have to work at a higher rate. In any case, an implementation is not constrained to respect the filter ordering, as long as the result is the same, and it may even implement the composite Filtering in one single step.

フィルターを連結することで操作が可能であるため、複合選択操作が生成されます。この場合、フィルタリングが発生する順序は暗黙的に定義されます(外側フィルターは内側のフィルターの後に来ます)。ただし、連結がフィルターのみにある限り、カスケードフィルターの結果は順序から独立していますが、最初のフィルターはより高いレートで動作する必要があるため、順序は実装目的で重要かもしれません。いずれにせよ、結果が同じである限り、実装はフィルターの順序を尊重するように制約されておらず、1つのステップで複合フィルタリングを実装することさえできます。

OR operations are not supported with this basic model. More sophisticated filters (e.g., supporting bitmasks, ranges, or OR operations) can be realized as vendor-specific schemes.

または、この基本モデルでは操作がサポートされていません。より洗練されたフィルター(たとえば、ビットマスク、範囲、または操作をサポートする)は、ベンダー固有のスキームとして実現できます。

All IPFIX flow attributes defined in [RFC5102] can be used for Property Match Filtering. Further information elements can be easily defined. Property match operations should be available for different protocol portions of the packet header:

[RFC5102]で定義されているすべてのIPFIXフロー属性は、プロパティマッチフィルタリングに使用できます。詳細情報要素は簡単に定義できます。プロパティマッチ操作は、パケットヘッダーのさまざまなプロトコル部分で利用できる必要があります。

(i) IP header (excluding options in IPv4, stacked headers in IPv6)

(i) IPヘッダー(IPv4のオプションを除く、IPv6の積み上げヘッダー)

(ii) transport protocol header (e.g., TCP, UDP)

(ii)輸送プロトコルヘッダー(例:TCP、UDP)

(iii) encapsulation headers (e.g., the MPLS label stack, if present)

(iii)カプセル化ヘッダー(例:MPLSラベルスタック、存在する場合)

When the PSAMP Device offers Property Match Filtering, and, in its usual capacity other than in performing PSAMP functions, identifies or processes information from IP, transport protocol or encapsulation protocols, then the information should be made available for Filtering. For example, when a PSAMP Device routes based on destination IP address, that field should be made available for Filtering. Conversely, a PSAMP Device that does not route is not expected to be able to locate an IP address within a packet, or make it available for Filtering, although it may do so.

PSAMPデバイスがプロパティマッチフィルタリングを提供し、PSAMP関数を実行する以外に通常の容量で、IP、輸送プロトコル、またはカプセル化プロトコルから情報を識別または処理する場合、情報をフィルタリングに利用できるようにする必要があります。たとえば、宛先IPアドレスに基づいてPSAMPデバイスがルーティングする場合、そのフィールドをフィルタリングに使用できるようにする必要があります。逆に、ルーティングしないPSAMPデバイスは、パケット内のIPアドレスを見つけたり、フィルタリングを利用できるようにすることはできませんが、そうすることができます。

Since packet encryption conceals the real values of encrypted fields, Property Match Filtering must be configurable to ignore encrypted packets, when detected.

パケット暗号化は暗号化されたフィールドの実際の値を隠すため、検出されたときに暗号化されたパケットを無視するようにプロパティマッチフィルタリングを構成できる必要があります。

The Selection Process may support Filtering based on the properties of the router state:

選択プロセスは、ルーター状態のプロパティに基づくフィルタリングをサポートする場合があります。

(i) Ingress interface at which a packet arrives equals a specified value

(i) パケットが到着するイングレスインターフェイスは、指定された値に等しくなります

(ii) Egress interface to which a packet is routed to equals a specified value

(ii)パケットが指定された値に等しくなるようにルーティングされる出力インターフェイス

(iii) Packet violated Access Control List (ACL) on the router

(iii)ルーター上のパケット違反アクセス制御リスト(ACL)

(iv) Failed Reverse Path Forwarding (RPF)

(iv)失敗した逆パス転送(RPF)

(v) Failed Resource Reservation Protocol (RSVP)

(v) 失敗したリソース予約プロトコル(RSVP)

(vi) No route found for the packet

(vi)パケットにはルートが見つかりません

(vii) Origin Border Gateway Protocol (BGP) Autonomous System (AS) [RFC4271] equals a specified value or lies within a given range

(vii)Origin Border Gateway Protocol(BGP)自律システム(AS)[RFC4271]は、特定の範囲内に指定された値に等しいか、

(viii) Destination BGP AS equals a specified value or lies within a given range

(viii)宛先BGPは指定された値に等しいか、特定の範囲内にあります

Packets that match the failed Reverse Path Forwarding (RPF) condition are packets for which ingress Filtering failed as defined in [RFC3704].

失敗した逆パス転送(RPF)条件に一致するパケットは、[RFC3704]で定義されているように、イングレスフィルタリングが失敗したパケットです。

Packets that match the failed Resource Reservation Protocol (RSVP) condition are packets that do not fulfill the RSVP specification as defined in [RFC2205].

失敗したリソース予約プロトコル(RSVP)条件に一致するパケットは、[RFC2205]で定義されているRSVP仕様を満たさないパケットです。

Router architectural considerations may preclude some information concerning the packet treatment being available at line rate for selection of packets. For example, the Selection Process may not be implemented in the fast path that is able to access router state at line rate. However, when Filtering follows Sampling (or some other selection operation) in a Composite Selector, the rate of the Packet Stream output from the sampler and input to the filter may be sufficiently slow that the filter could select based on router state.

ルーターアーキテクチャの考慮事項は、パケットの選択のためにラインレートで利用可能であるパケット処理に関するいくつかの情報を排除する可能性があります。たとえば、選択プロセスは、ラインレートでルーター状態にアクセスできる高速パスに実装されない場合があります。ただし、フィルタリングが複合セレクターのサンプリング(または他の選択操作)に続くと、サンプラーからフィルターへの入力からパケットストリーム出力のレートが十分に遅く、ルーター状態に基づいてフィルターが選択できる場合があります。

6.2. Hash-Based Filtering
6.2. ハッシュベースのフィルタリング

A Hash Function h maps the Packet Content c, or some portion of it, onto a Hash Range R. The packet is selected if h(c) is an element of S, which is a subset of R called the Hash Selection Range. Thus, Hash-Based selection is a particular case of Filtering. The object is selected if c is in inv(h(S)). But for desirable Hash Functions, the inverse image inv(h(S)) will be extremely complex, and hence h would not be expressible as, say, a Property Match Filter or a simple combination of these.

ハッシュ関数hは、ハッシュ範囲RにパケットコンテンツCまたはその一部をマッピングします。H(C)がSの要素である場合、ハッシュ選択範囲と呼ばれるRのサブセットである場合、パケットが選択されます。したがって、ハッシュベースの選択は、フィルタリングの特定のケースです。CがINV(h(s))にある場合、オブジェクトが選択されます。しかし、望ましいハッシュ関数の場合、逆画像INV(H(s))は非常に複雑であるため、Hはプロパティマッチフィルターまたはこれらの単純な組み合わせとして表現できません。

Hash-based Selection is mainly used to realize a coordinated packet selection. That means that the same packets are selected at different Observation Points. This is useful for instance to observe the path (trajectory) that a packet took through the network or to apply packet selection to passive one-way measurements.

ハッシュベースの選択は、主に調整されたパケット選択を実現するために使用されます。つまり、同じパケットが異なる観測ポイントで選択されます。これは、たとえば、パケットがネットワークを通過したパス(軌跡)を観察したり、パケットの選択を受動的な一方向測定に適用するために役立ちます。

A prerequisite for the method to work and to ensure interoperability is that the same Hash Function with the same parameters (e.g., input vector) is used at the Observation Points.

この方法が機能し、相互運用性を確保するための前提条件は、同じパラメーター(入力ベクトルなど)を持つ同じハッシュ関数が観測点で使用されることです。

A consistent packet selection is also possible with Property Match Filtering. Nevertheless, Hash-based Selection can be used to approximate a random selection. The desired statistical properties are discussed in Section 6.2.2.

プロパティマッチフィルタリングでは、一貫したパケット選択も可能です。それにもかかわらず、ハッシュベースの選択を使用して、ランダム選択を近似できます。目的の統計的特性については、セクション6.2.2で説明します。

In the following subsections, we give some application examples for coordinated packet selection.

次のサブセクションでは、調整されたパケット選択のアプリケーション例をいくつか紹介します。

6.2.1. Application Examples for Coordinated Packet Selection
6.2.1. 調整されたパケット選択のアプリケーションの例
6.2.1.1. Trajectory Sampling
6.2.1.1. 軌跡サンプリング

Trajectory Sampling is the consistent selection of a subset of packets at either all of a set of Observation Points or none of them. Trajectory Sampling is realized by Hash-based Selection if all Observation Points in the set use a common Hash Function, Hash Domain, and Selection Range. The Hash Domain comprises all or part of the Packet Content that is invariant along the packet path. Fields such as Time-to-Live, which is decremented per hop, and header CRC [RFC1624], which is recalculated per hop, are thus excluded from the Hash Domain. The Hash Domain needs to be wider than just a flow key, if packets are to be selected quasi-randomly within flows.

軌道サンプリングは、一連の観測点のいずれかでパケットのサブセットの一貫した選択です。軌道サンプリングは、セット内のすべての観測ポイントが共通のハッシュ関数、ハッシュドメイン、および選択範囲を使用している場合、ハッシュベースの選択によって実現されます。ハッシュドメインは、パケットパスに沿って不変のパケットコンテンツのすべてまたは一部を含みます。したがって、ホップごとに減少する時間までに減少する時間までのフィールド、およびヘッダーCRC [RFC1624]は、ハッシュドメインから除外されます。ハッシュドメインは、フロー内で準ランダムリーを選択する場合、フローキーよりも広くする必要があります。

The trajectory (or path) followed by a packet is reconstructed from PSAMP reports on it that reach a Collector. Reports on a given packet originating from different Observation Points are associated by matching a label from the reports. The label may comprise that portion of the invariant Packet Content that is reported, or possibly some digest of the invariant Packet Content that is inserted into the packet report at the Observation Point. Such a digest may be constructed by applying a second Hash Function to the invariant Packet Content. The reconstruction of trajectories and methods for dealing with possible ambiguities due to label collisions (identical labels reported for different packets) and potential loss of reports in transmission are dealt with in [DuGr00], [DuGG02], and [DuGr04].

パケットが続く軌跡(またはパス)がPSAMPレポートから再構築され、コレクターに到達します。異なる観測ポイントから発生する特定のパケットに関するレポートは、レポートのラベルを一致させることによって関連付けられます。ラベルは、報告されている不変パケットコンテンツの部分、または観測点のパケットレポートに挿入された不変パケットコンテンツの消化率を含む場合があります。このようなダイジェストは、不変のパケットコンテンツに2番目のハッシュ関数を適用することにより構築できます。ラベルの衝突(異なるパケットで報告された同一のラベル)および伝送中のレポートの潜在的な損失による可能性のある曖昧さを扱うための軌跡と方法の再構築は、[DUGR00]、[Dugg02]、および[Dugr04]で扱われます。

Applications of trajectory Sampling include (i) estimation of the network path matrix, i.e., the traffic intensities according to network path, broken down by flow key; (ii) detection of routing loops, as indicated by self-intersecting trajectories; (iii) passive performance measurement: prematurely terminating trajectories indicate packet loss, packet one-way delay can be determined if reports include (synchronized) timestamps of packet arrival at the Observation Point; and (iv) network attack tracing, of the actual paths taken by attack packets with spoofed source addresses.

軌道サンプリングのアプリケーションには、(i)ネットワークパスマトリックスの推定、つまり、フローキーによって分割されたネットワークパスに応じたトラフィック強度が含まれます。(ii)自己挿入軌道によって示されるように、ルーティングループの検出。(iii)パッシブパフォーマンス測定:軌道を時期尚早に終了する軌道のパケットの損失を示します。パケットの遅延は、レポートにパケットの到着のタイムスタンプが含まれているかどうかを決定できます。(iv)スプーフィングされたソースアドレスを使用した攻撃パケットによって取られた実際のパスのネットワーク攻撃トレース。

6.2.1.2. Passive One-Way Measurements
6.2.1.2. 受動的な一方向測定

Coordinated packet selection can be applied for instance to one-way delay measurements in order to reduce the required resources. In one-way delay measurements, packets are collected at different Observation Points in the network. A packet digest is generated for each packet that helps to identify the packet. The packet digest and the arrival time of the packet at the Observation Point are reported to a process that calculates the delay. The delay is calculated by subtracting the arrival time of the same packet at the Observation Points (e.g., [ZsZC01]). With high data rates, capturing all packets can require a lot of resources for storage, transfer, and processing. To reduce resource consumption, packet selection methods can be applied. But for such selection techniques, it has to be ensured that the same packets are collected at different Observation Points. Hash-based Selection provides this feature.

必要なリソースを削減するために、たとえば一元配置遅延測定に調整されたパケット選択を適用できます。一元配置遅延測定では、ネットワーク内の異なる観測点でパケットが収集されます。パケットの識別に役立つパケットごとにパケットダイジェストが生成されます。パケットダイジェストと観測点でのパケットの到着時間は、遅延を計算するプロセスに報告されます。遅延は、観測点で同じパケットの到着時間を差し引くことによって計算されます(例:[ZSZC01])。高いデータレートでは、すべてのパケットをキャプチャするには、ストレージ、転送、処理のために多くのリソースが必要になる場合があります。リソースの消費を減らすために、パケット選択方法を適用できます。しかし、このような選択技術については、同じパケットが異なる観測点で収集されるようにする必要があります。ハッシュベースの選択は、この機能を提供します。

6.2.1.3. Generation of Pseudorandom Numbers
6.2.1.3. 擬似ランダム数の生成

Although pseudorandom number generators with well-understood properties have been developed, they may not be the method of choice in settings where computational resources are scarce. A convenient alternative is to use Hash Functions of Packet Content as a source of randomness. The hash (suitably re-normalized) is a pseudorandom variate in the interval [0,1]. Other schemes may use packet fields in iterators for pseudorandom numbers. However, the statistical properties of an ideal packet selection law (such as independent Sampling for different packets, or independence on Packet Content) may not be exactly rendered by an implementation, but only approximately so.

よく理解されているプロパティを備えた擬似ランダム数ジェネレーターは開発されていますが、計算リソースが不足している設定では選択の方法ではない場合があります。便利な選択肢は、パケットコンテンツのハッシュ関数をランダム性のソースとして使用することです。ハッシュ(適切に再正規化)は、間隔[0,1]の擬似ランダム変動です。他のスキームは、擬似ランダム数のためにイテレーターのパケットフィールドを使用する場合があります。ただし、理想的なパケット選択法(異なるパケットの独立サンプリング、パケットコンテンツの独立性など)の統計的特性は、実装によって正確にレンダリングされるわけではありませんが、ほぼそうです。

Use of Packet Content to generate pseudorandom variates shares with non-uniform probabilistic Sampling (see Section 5.2.2.2 above) the property that selection decisions depend on Packet Content. However, there is a fundamental difference between the two. In the former case, the content determines pseudorandom variates. In the latter case, the content only determines the selection probabilities: selection could then proceed, e.g., by use of random variates obtained by an independent pseudorandom number generator.

擬似ランダムを生成するためにパケットコンテンツを使用して、選択の決定がパケットコンテンツに依存する不均一な確率的サンプリング(上記のセクション5.2.2.2を参照)を使用してシェアが変動します。ただし、2つには根本的な違いがあります。前者の場合、コンテンツは擬似ランダム変動を決定します。後者の場合、コンテンツは選択の確率を決定します。たとえば、独立した擬似ランダム番号ジェネレーターによって得られたランダムバリエートを使用することにより、選択が続行できます。

6.2.2. Desired Properties of Hash Functions
6.2.2. ハッシュ関数の望ましい特性

Here we formulate desired properties for Hash Functions. For this, we have to distinguish whether a Hash Function is used for packet selection or just as a packet digest. The main focus of this document is on packet selection. Nevertheless, we also provide some requirements for the use of Hash Functions as packet digest.

ここでは、ハッシュ関数に目的のプロパティを策定します。このためには、ハッシュ関数がパケット選択に使用されるのか、それともパケットダイジェストとして使用されるのかを区別する必要があります。このドキュメントの主な焦点は、パケットの選択です。それにもかかわらず、パケットダイジェストとしてハッシュ関数を使用するためのいくつかの要件も提供します。

First of all, we need to define suitable input fields from the packet. In accordance to [DuGr00], input field should be:

まず、パケットから適切な入力フィールドを定義する必要があります。[DUGR00]に従って、入力フィールドは次のとおりです。

- invariant on the path - variable among packets

- パス上の不変 - パケット間の変数

Only if the input fields are the same at different Observation Points is it possible to recognize the packet. The input fields should be variable among packets in order to distribute the hash results over the selection range.

入力フィールドが異なる観測ポイントで同じである場合にのみ、パケットを認識することができます。選択範囲にハッシュ結果を分散するために、入力フィールドはパケット間で変動する必要があります。

6.2.2.1. Requirements for Packet Selection
6.2.2.1. パケット選択の要件

In accordance to considerations in [MoND05] and [Henk08], we define the following desired properties of Hash Functions used for packet selection:

[MOND05]および[HENK08]の考慮事項に従って、パケット選択に使用されるハッシュ関数の次の望ましい特性を定義します。

(i) Speed: The Hash Function has to be applied to each packet that traverses the Observation Point. Therefore, it has to be fast in order to cope with the high packet rates. In the ideal case, the hash operation should not influence the performance on the PSAMP Device.

(i) 速度:ハッシュ関数は、観測点を通過する各パケットに適用する必要があります。したがって、高いパケットレートに対処するには、高速でなければなりません。理想的な場合、ハッシュ操作はPSAMPデバイスのパフォーマンスに影響を与えないはずです。

(ii) Uniformity: The Hash Function h should have good mixing properties, in the sense that small changes in the input (e.g., the flipping of a single bit) cause large changes in the output (many bits change). Then any local clump of values of c is spread widely over R by h, and so the distribution of h(c) is fairly uniform even if the distribution of c is not. Then the Attained Selection Fraction gets close to the Configured Selection Fraction (#S/#R), which can be tuned by choice of S.

(ii)均一性:ハッシュ関数hには、入力の小さな変化(たとえば、単一のビットの反転)が出力に大きな変化をもたらすという意味で、適切な混合特性が必要です(多くのビットが変化します)。その後、Cの値の局所的な塊はrによってRに広く拡散されるため、Cの分布がそうでない場合でも、H(c)の分布はかなり均一になります。その後、達成された選択画分は、構成された選択分数(#s/#r)に近づき、Sを選択することで調整できます。

(iii) Unbiasedness: The selection decision should be as independent of packet attributes as possible. The set of selected packets should not be biased towards a specific type of packets.

(iii)偏見:選択決定は、可能な限りパケット属性から独立している必要があります。選択したパケットのセットは、特定のタイプのパケットに偏ってはなりません。

(iv) Representativeness of sample: The sample should be as representative as possible for the observed traffic.

(iv)サンプルの代表性:サンプルは、観察されたトラフィックの可能な限り代表である必要があります。

(v) Non-linearity: The function should not be linear. This increases the mixing properties (uniformity criterion). In addition to this, it decreases the predictability of the output and therefore the vulnerabilities against attacks.

(v) 非線形性:関数は線形ではありません。これにより、混合特性(均一性基準)が増加します。これに加えて、出力の予測可能性、したがって攻撃に対する脆弱性が低下します。

(vi) Robustness against vulnerabilities: The Hash Function should be robust against attacks. Potential vulnerabilities are described in Section 6.2.3.

(vi)脆弱性に対する堅牢性:ハッシュ関数は攻撃に対して堅牢である必要があります。潜在的な脆弱性については、セクション6.2.3に記載されています。

6.2.2.2. Requirements for Packet Digesting
6.2.2.2. パケット消化の要件

For digesting Packet Content for inclusion in a reported label, the most important property is a low collision frequency. A secondary requirement is the ability to accept variable-length input, in order to allow inclusion of maximal amount of packet as input. Execution speed is of secondary importance, since the digest need only be formed from selected packets.

報告されたラベルに含めるためのパケットコンテンツを消化する場合、最も重要な特性は衝突周波数が低いことです。二次要件とは、最大量のパケットを入力として含めることを可能にするために、可変長入力を受け入れる機能です。ダイジェストは選択したパケットからのみ形成される必要があるため、実行速度は二次的に重要です。

6.2.3. Security Considerations for Hash Functions
6.2.3. ハッシュ関数のセキュリティ上の考慮事項

A concern for Hash-based Selection is whether some large set of related packets could be disproportionately sampled, i.e., that the Attained Selection Fraction is significantly different from the Configured Selection Fraction. This can happen either

ハッシュベースの選択の懸念は、関連するパケットの大規模なセットが不釣り合いにサンプリングされる可能性があるかどうか、つまり、選択された選択分数が構成された選択分数とは大きく異なることです。これはどちらも発生する可能性があります

(i) through unanticipated behavior in the Hash Function, or

(i) ハッシュ関数での予期しない動作を通じて、または

(ii) because the packets had been deliberately crafted to have this property.

(ii)パケットがこのプロパティを持つように意図的に作成されていたためです。

The first point underlines the importance of using a Hash Function with good mixing properties. For this, the statistical properties of candidate Hash Functions need to be evaluated. Since the hash output depends on the traffic mix, the evaluation should be done preferably on up-to-date packet traces from the network in which the Hash-based Selection will be deployed.

最初のポイントは、良好な混合特性を備えたハッシュ関数を使用することの重要性を強調しています。このためには、候補ハッシュ関数の統計的特性を評価する必要があります。ハッシュ出力はトラフィックミックスに依存するため、ハッシュベースの選択が展開されるネットワークからの最新のパケットトレースで評価を行う必要があります。

However, Hash Functions that perform well on typical traffic may not be sufficiently strong to withstand attacks specifically targeted against them. Such potential attacks have been described in [GoRe07].

ただし、典型的なトラフィックでうまく機能するハッシュ関数は、それらに対して特別に対象となる攻撃に耐えるほど強力ではない場合があります。このような潜在的な攻撃は[Gore07]で説明されています。

In the following subsections, we point out different potential attack scenarios. We encourage the use of standardized Hash Functions. Therefore, we assume that the Hash Function itself is public and hence known to an attacker.

次のサブセクションでは、さまざまな潜在的な攻撃シナリオを指摘します。標準化されたハッシュ関数の使用をお勧めします。したがって、ハッシュ機能自体が公開されているため、攻撃者に知られていると仮定します。

Nevertheless, we also assume the possibility of using a private input parameter for the Hash Function that is kept secret. Such an input parameter can for instance be attached to the hash input before the hash operation is applied. With this, at least parts of the hash operation remain secret.

それにもかかわらず、秘密にされているハッシュ関数にプライベート入力パラメーターを使用する可能性も想定しています。このような入力パラメーターは、ハッシュ操作が適用される前に、ハッシュ入力に接続できます。これにより、少なくともハッシュ操作の一部は秘密のままです。

For the attack scenarios, we assume that an attacker uses its knowledge of the Hash Function to craft packets that are then dispatched, either as the attack itself or to elicit further information that can be used to refine the attack.

攻撃シナリオの場合、攻撃者はハッシュ関数の知識を使用して、攻撃自体として派遣されるパケットを作成するか、攻撃を改良するために使用できるさらなる情報を引き出していると想定しています。

Two scenarios are considered. In the first scenario, the attacker has no knowledge about whether or not the crafted packets are selected. In the second scenario, the attacker uses some knowledge of Sampling outcomes. The means by which this might be acquired is discussed below. Some additional attacks that involve tampering with Export Packets in transit, as opposed to attacking the PSAMP Device, are discussed in [GoRe07].

2つのシナリオが考慮されます。最初のシナリオでは、攻撃者は、作成されたパケットが選択されているかどうかについて知識がありません。2番目のシナリオでは、攻撃者はサンプリングの結果に関する知識を使用しています。これが取得される可能性のある手段については、以下で説明します。PSAMPデバイスの攻撃とは対照的に、輸送中の輸出パケットの改ざんを含むいくつかの追加攻撃については、[Gore07]で説明しています。

6.2.3.1. Vulnerabilities of Hash-Based Selection without Knowledge of Selection Outcomes
6.2.3.1. 選択結果の知識なしに、ハッシュベースの選択の脆弱性

(i) The Hash Function does not use a private parameter.

(i) ハッシュ関数は、プライベートパラメーターを使用しません。

If no private input parameter is used, potential attackers can easily calculate which packets result in which hash values. If the selection range is public, an attacker can craft packets whose selection properties are known in advance. If the selection range is private, an attacker cannot determine whether a crafted packet is selected. However, by computing the hash on different trial crafted packets, and selecting those yielding a given hash value, the attacker can construct an arbitrarily large set of distinct packets with a common selection properties, i.e., packets that will be either all selected or all not selected. This can be done whatever the strength of the Hash Function.

プライベート入力パラメーターが使用されていない場合、潜在的な攻撃者は、ハッシュ値がどのパケットが生じるかを簡単に計算できます。選択範囲が公開されている場合、攻撃者は、選択プロパティが事前に既知のパケットを作成できます。選択範囲がプライベートである場合、攻撃者は細工されたパケットが選択されているかどうかを判断できません。ただし、さまざまな試行で作成されたパケットでハッシュを計算し、特定のハッシュ値を生成するものを選択することにより、攻撃者は、共通の選択プロパティを備えた個別のパケットの任意に大きなセット、つまりすべて選択されるか、すべてではないパケットを構築できます。選択。これは、ハッシュ関数の強度が何であれ、実行できます。

(ii) The Hash Function is not cryptographically strong.

(ii)ハッシュ関数は暗号的に強力ではありません。

If the Hash Function is not cryptographically strong, it may be possible to construct sequences of distinct packets with the common selection property even if a private parameter is used.

ハッシュ関数が暗号化に強い場合、プライベートパラメーターが使用されていても、共通選択プロパティを使用して個別のパケットのシーケンスを構築することが可能です。

An example is the standard CRC-32 Hash Function used with a private modulus (but without a private string post-pended to the input). It has weak mixing properties for low-order bits. Consequently, simply by incrementing the hash input, one obtains distinct packets whose hashes mostly fall in a narrow range, and hence are likely commonly selected; see [GoRe07].

例としては、プライベートモジュラスで使用される標準のCRC-32ハッシュ関数があります(ただし、入力にポストペンで固定されたプライベート文字列がありません)。低次ビットの混合特性が弱いです。その結果、ハッシュ入力を増加させるだけで、ハッシュがほとんど狭い範囲にある別個のパケットを取得するため、一般的に選択される可能性があります。[Gore07]を参照してください。

Suitable parameterization of the Hash Function can make such attacks more difficult. For example, post-pending a private string to the input before hashing with CRC-32 will give stronger mixing properties over all bits of the input. However, with a Hash Function, such as CRC-32, that is not cryptographically strong, the possibility of discovering a method to construct packet sets with the common selected property cannot be ruled out, even when a private modulus or post-pended string is used.

ハッシュ関数の適切なパラメーター化は、そのような攻撃をより困難にする可能性があります。たとえば、CRC-32でハッシュする前に入力にプライベート文字列をポストペンディングすると、入力のすべてのビットでより強力な混合特性が得られます。ただし、CRC-32などのハッシュ関数が暗号化されていない場合、一般的な選択したプロパティを使用してパケットセットを構築する方法を発見する可能性は、プライベートモジュラスまたはポストペン付きの文字列があっても除外することはできません。使用済み。

6.2.3.2. Vulnerabilities of Hash-Based Selection Using Knowledge of Selection Outcomes
6.2.3.2. 選択結果の知識を使用したハッシュベースの選択の脆弱性

Knowledge of the selection outcomes of crafted packets can be used by an attacker to more easily construct sets of packets that are disproportionately sampled and/or are commonly selected. For this, the attacker does not need any a priori knowledge about the Hash Function or selection range.

細工されたパケットの選択結果の知識は、攻撃者が使用して、不釣り合いにサンプリングおよび/または一般的に選択されるパケットのセットをより簡単に構築できます。このために、攻撃者はハッシュ関数または選択範囲に関するアプリオリの知識を必要としません。

There are several ways an attacker might acquire this knowledge about the selection outcome:

攻撃者が選択の結果に関するこの知識を獲得する方法はいくつかあります。

(i) Billing Reports: If samples are used for billing purposes, then the selection outcomes of packets may be able to be inferred by correlating a crafted Packet Stream with the billing reports that it generates. However, the rate at which knowledge of selection outcomes can be acquired depends on the temporal and spatial granularity of the billing reports; being slower the more aggregated the reports are.

(i) 請求レポート:サンプルが請求目的で使用されている場合、作成されたパケットストリームを生成する請求レポートと相関させることにより、パケットの選択結果を推測できる場合があります。ただし、選択結果の知識を獲得できる速度は、請求レポートの時間的および空間的な粒度に依存します。レポートの集約が遅くなるほど遅くなります。

(ii) Feedback from an Intrusion Detection System: e.g., a botmaster adversary learns if his packets were detected by the intrusion detection system by seeing if one of his bots is blocked by the network.

(ii)侵入検知システムからのフィードバック:たとえば、ボットマスターの敵は、ネットワークによってボットの1つがブロックされているかどうかを確認することにより、侵入検知システムによってパケットが検出されたかどうかを学びます。

(iii) Observation of the Report Stream: Export Packets sent across a public network may be eavesdropped on by an adversary. Encryption of the Export Packets provides only a partial defense, since it may be possible to infer the selection outcomes of packets by correlating a crafted Packet Stream with the occurrence (not the content) of packets in the export stream that it generates. The rate at which such knowledge could be acquired is limited by the temporal resolution at which reports can be associated with packets, e.g., due to processing and propagation variability, and difficulty in distinguishing report on attack packets from those of background traffic, if present. The association between packets and their reports on which this depends could be removed by padding Export Packets to a constant length and sending them at a constant rate.

(iii)レポートストリームの観察:パブリックネットワーク全体で送信されるエクスポートパケットは、敵によって盗聴される可能性があります。エクスポートパケットの暗号化は、作成されたパケットストリームと生成するエクスポートストリーム内のパケットの発生(コンテンツではなく)と相関することにより、パケットの選択結果を推測できる可能性があるため、部分的な防御のみを提供します。そのような知識を獲得できる速度は、レポートをパケットに関連付けることができる時間分解能、たとえば処理と伝播の変動、および攻撃パケットのレポートをバックグラウンドトラフィックのレポートと区別することの難しさによって制限されます。パケットとこれに依存するレポートとの関連は、輸出パケットを一定の長さにパディングし、一定の速度で送信することで削除できます。

We now turn to attacks that can exploit knowledge of selection outcomes. First, with a non-cryptographic Hash Function, knowledge of selection outcomes for a trial stream may be used to further craft a packet set with the common selection property. This has been demonstrated for the modular hash f(x) = a x + b mod k, for private parameters a, b, and k. With Sampling rate p, knowledge of the Sampling outcomes of roughly 2/p is sufficient for the attack to succeed, independent of the values of a, b, and k. With knowledge of the selection outcomes of a larger number of packets, the parameters a, b, and k can be determined; see [GoRe07].

今、私たちは選択結果の知識を活用できる攻撃に頼っています。第一に、非暗号化のハッシュ関数を使用すると、試行ストリームの選択結果の知識を使用して、共通選択プロパティを使用してパケットセットをさらに作成できます。これは、モジュラーハッシュf(x)= a x b mod k、プライベートパラメーターa、b、およびkについて実証されています。サンプリングレートPでは、a、b、kの値とは無関係に、攻撃が成功するには、約2/pのサンプリング結果の知識が十分です。より多くのパケットの選択結果に関する知識により、パラメーターA、B、およびKを決定できます。[Gore07]を参照してください。

A cryptographic Hash Function employing a private parameter and operating in one of the pseudorandom function modes specified above is not vulnerable to these attacks, even if the selection range is known.

プライベートパラメーターを使用し、上記で指定された擬似ランダム関数モードの1つで動作する暗号化ハッシュ関数は、選択範囲がわかっていても、これらの攻撃に対して脆弱ではありません。

6.2.3.3. Vulnerabilities to Replay Attacks
6.2.3.3. 攻撃を再生する脆弱性

Since Hash-based Selection is deterministic, any packet or set of packets with known selection properties can be replayed into a network and experience the same selection outcomes provide the Hash Function and its parameters are not changed. Repetition of a single packet may be noticeable to other measurement methods if employed (e.g., collection of flow statistics), whereas a set of distinct packets that appears statistically similar to regular traffic may be less noticeable.

ハッシュベースの選択は決定論的であるため、既知の選択プロパティを備えたパケットまたはパケットのセットをネットワークにリプレイして体験できます。同じ選択結果がハッシュ関数を提供し、そのパラメーターは変更されません。単一のパケットの繰り返しは、採用されている場合(フロー統計の収集など)、他の測定方法に顕著になる場合がありますが、通常のトラフィックと統計的に類似しているように見える個別のパケットのセットは目立たない場合があります。

Replay attacks may be mitigated by repeated changing of Hash Function parameters. This also prevents attacks that exploit knowledge of Sampling outcomes, at least if the parameters are changed at least as fast as the knowledge can be acquired by an attacker. In order to preserve the ability to perform trajectory Sampling, parameter change would have to be simultaneous (or approximately so) across all Observation Points.

リプレイ攻撃は、ハッシュ関数パラメーターの繰り返しの変更により緩和される場合があります。これはまた、少なくともパラメーターが攻撃者が知識を獲得できるのと同じくらい速く変更される場合、サンプリング結果の知識を活用する攻撃を防ぎます。軌道サンプリングを実行する機能を維持するために、パラメーターの変更は、すべての観測点で同時に(またはほぼそう)なければなりません。

6.2.4. Choice of Hash Function
6.2.4. ハッシュ関数の選択

The specific choice of Hash Function represents a trade-off between complexity and ease of implementation. Ideally, a cryptographically strong Hash Function employing a private parameter and operating in pseudorandom function mode as specified above would be used, yielding a good emulation of a random packet selection at a target Sampling rate, and giving maximal robustness against the attacks described in the previous section. Unfortunately, there is currently no single Hash Function that fulfills all the requirements.

ハッシュ関数の特定の選択は、複雑さと実装の容易さとのトレードオフを表します。理想的には、プライベートパラメーターを使用し、上記で指定された擬似ランダム機能モードで動作する暗号化的に強力なハッシュ関数を使用し、ターゲットサンプリングレートでランダムパケット選択の良好なエミュレーションをもたらし、前の攻撃で説明した攻撃に対して最大の堅牢性を与えますセクション。残念ながら、現在、すべての要件を満たす単一のハッシュ関数はありません。

As detailed in Section 6.2.3, only cryptographic Hash Functions employing a private parameter operating in pseudorandom function mode are sufficiently strong to withstand the range of conceivable attacks. For example, fixed- or variable-length inputs could be hashed using a block cipher (like Advanced Encryption Standard (AES)) in cipher-block-chaining mode. Fixed-length inputs could also be hashed using an iterated cryptographic Hash Function (like MD5 or SHA1), with a private initial vector. For variable-length inputs, an iterated cryptographic Hash Function (like MD5 or SHA1) should employ private string post-pended to the data in addition to a private initial vector. For more details, see the "append-cascade" construction of [BeCK96]. We encourage the use of such cryptographically strong Hash Functions wherever possible.

セクション6.2.3で詳述されているように、擬似ランダム機能モードで動作するプライベートパラメーターを使用する暗号化ハッシュ関数のみが、考えられる攻撃の範囲に耐えるのに十分な強さです。たとえば、固定または可変の長さの入力は、暗号ブロックチェーンモードでブロック暗号(高度な暗号化標準(AES)など)を使用してハッシュすることができます。固定長の入力は、プライベート初期ベクトルを使用して、反復型暗号化ハッシュ関数(MD5やSHA1など)を使用してハッシュすることもできます。可変長さの入力の場合、反復型の暗号化ハッシュ関数(MD5やSHA1など)は、プライベートの初期ベクトルに加えて、データにポストペンドされたプライベート文字列を使用する必要があります。詳細については、[BECK96]の「補足」構造を参照してください。可能な限り、このような暗号的に強力なハッシュ機能の使用をお勧めします。

However, a problem with using such functions is the low performance. As shown for instance in [Henk08], the computation times for MD5 and SHA are about 7-10 times higher compared to non-cryptographic functions. The difference increases for small hash input lengths.

ただし、そのような機能を使用することの問題は、パフォーマンスが低いことです。たとえば、[HENK08]で示されているように、MD5とSHAの計算時間は、非暗号化機能と比較して約7〜10倍高くなっています。小さなハッシュ入力長の差は増加します。

Therefore, it is not assumed that all PSAMP Devices will be capable of applying a cryptographically strong Hash Function to every packet at line rate. For this reason, the Hash Functions listed in this section will be of a weaker variety. Future protocol extensions that employ stronger Hash Functions are highly welcome.

したがって、すべてのPSAMPデバイスが、すべてのパケットにラインレートで暗号化的に強力なハッシュ関数を適用できるとは想定されていません。このため、このセクションにリストされているハッシュ関数は、より弱いものになります。より強力なハッシュ関数を使用する将来のプロトコル拡張は大歓迎です。

Comparisons of Hash Functions for packet selection and packet digesting with regard to various criteria can be found in [MoND05] and [Henk08].

さまざまな基準に関するパケット選択とパケット消化のためのハッシュ関数の比較は、[MOND05]および[HENK08]に記載されています。

6.2.4.1. Hash Functions for Packet Selection
6.2.4.1. パケット選択のハッシュ関数

If Hash-based packet Selection is applied, the BOB function MUST be used for packet selection operations in order to be compliant with PSAMP. The specification of BOB is given in the appendix. Both the parameter (the init value) and the selection range should be kept private. The initial vector of the Hash Function MUST be configurable out of band to prevent security breaches like exposure of the initial vector content.

ハッシュベースのパケット選択が適用される場合、PSAMPに準拠するためには、BOB関数をパケット選択操作に使用する必要があります。ボブの仕様は付録に記載されています。パラメーター(init値)と選択範囲の両方をプライベートに保つ必要があります。ハッシュ関数の初期ベクトルは、初期ベクトルコンテンツの露出などのセキュリティ侵害を防ぐために、バンドから構成可能でなければなりません。

Other functions, such as CRC-32 and IPSX, MAY be used. The IPSX function is described in the appendix, and the CRC-32 function is described in [RFC1141]. If CRC-32 is used, the input should first be post-pended with a private string that acts as a parameter, and the modulus of the CRC should also be kept private.

CRC-32やIPSXなどの他の機能を使用できます。IPSX関数は付録で説明されており、CRC-32関数は[RFC1141]で説明されています。CRC-32を使用する場合、最初に入力はパラメーターとして機能するプライベート文字列でポストペンで留まる必要があり、CRCのモジュラスもプライベートに保つ必要があります。

IPSX is simple to implement and was correspondingly about an order of magnitude faster to execute per packet than BOB or CRC-32 [MoND05].

IPSXは実装が簡単で、それに応じて、BOBまたはCRC-32 [MOND05]よりもパケットごとに実行するのがほぼ数桁速く実行されました。

All three Hash Functions evaluated showed relatively poor uniformity with 16-byte input that was drawn from only invariant fields in the IP and TCP/UDP headers (i.e., header fields that do not change from hop to hop). IPSX is inherently limited to 16 bytes.

評価された3つのハッシュ関数はすべて、IPおよびTCP/UDPヘッダー(つまり、ホップからホップに変更しないヘッダーフィールド)の不変フィールドのみから描画された16バイトの入力で比較的均一性が低いことを示しました。IPSXは本質的に16バイトに制限されています。

BOB and CRC-32 exhibit noticeably better uniformity when 4 or more bytes from the payload are also included in the input [MoND05]. Also with other criteria BOB performed quite well [Henk08].

ボブとCRC-32は、ペイロードから4バイト以上が入力に含まれている場合、顕著に均一性を示します[MOND05]。また、他の基準では、ボブは非常にうまく機能しました[Henk08]。

Although the characteristics have been checked for different traffic traces, results cannot be generalized to arbitrary traffic. Since Hash-based Selection is a deterministic function on the Packet Content, it can always be biased towards packets with specific attributes. Furthermore, it should be noted that all Hash Functions were evaluated only for IPv4.

特性はさまざまなトラフィックトレースについてチェックされていますが、結果を任意のトラフィックに一般化することはできません。ハッシュベースの選択はパケットコンテンツの決定論的関数であるため、特定の属性を持つパケットに常に偏ることができます。さらに、すべてのハッシュ関数はIPv4に対してのみ評価されたことに注意する必要があります。

None of these Hash Functions is recommended for cryptographic purposes. Please also note that the use of a private parameter only slightly reduces the vulnerabilities against attacks. As shown in Section 6.2.3, functions that are not cryptographically strong (e.g., BOB and CRC) cannot prevent attackers from crafting packets that are disproportionally selected even if a private parameter is used and the selection range is kept secret.

これらのハッシュ関数はいずれも、暗号化の目的には推奨されません。また、プライベートパラメーターの使用は、攻撃に対する脆弱性をわずかに減らすだけであることに注意してください。セクション6.2.3に示されているように、暗号化に強くない関数(BOBやCRCなど)は、プライベートパラメーターを使用して選択範囲を秘密にしていても、攻撃者が不均衡に選択されるパケットの作成を防ぐことができません。

As described in Section 6.2.2, the input bytes for the Hash Function need to be invariant along the path the packet is traveling. Only with this it is ensured that the same packets are selected at different Observation Points. Furthermore, they should have a high variability between different packets to generate a high variation in the Hash Range. An evaluation of the variability of different packet header fields can be found in [DuGr00], [HeSZ08], and [Henk08].

セクション6.2.2で説明したように、ハッシュ関数の入力バイトは、パケットが走行している経路に沿って不変である必要があります。これによってのみ、同じパケットが異なる観測ポイントで選択されることが保証されます。さらに、ハッシュ範囲に高い変動を生成するために、異なるパケット間で高い変動性を持つ必要があります。さまざまなパケットヘッダーフィールドの変動性の評価は、[dugr00]、[hesz08]、および[henk08]にあります。

If a Hash-based Selection with the BOB function is used with IPv4 traffic, the following input bytes MUST be used.

BOB関数を使用したハッシュベースの選択がIPv4トラフィックで使用される場合、次の入力バイトを使用する必要があります。

- IP identification field

- IP識別フィールド

- Flags field

- フラグフィールド

- Fragment offset

- フラグメントオフセット

- Source IP address

- ソースIPアドレス

- Destination IP address

- 宛先IPアドレス

- A configurable number of bytes from the IP payload, starting at a configurable offset

- 設定可能なオフセットから始まるIPペイロードからの構成可能な数のバイト

Due to the lack of suitable IPv6 packet traces, all candidate Hash Functions in [DuGr00], [MoND05], and [Henk08] were evaluated only for IPv4. Due to the IPv6 header fields and address structure, it is expected that there is less randomness in IPv6 packet headers than in IPv4 headers. Nevertheless, the randomness of IPv6 traffic has not yet been evaluated sufficiently to get any evidence. In addition to this, IPv6 traffic profiles may change significantly in the future when IPv6 is used by a broader community.

適切なIPv6パケットトレースが不足しているため、[DUGR00]、[MOND05]、および[HENK08]のすべての候補ハッシュ機能は、IPv4についてのみ評価されました。IPv6ヘッダーフィールドとアドレス構造により、IPv4ヘッダーの方がIPv4ヘッダーよりもランダム性が低いと予想されます。それにもかかわらず、IPv6トラフィックのランダム性は、証拠を取得するためにまだ十分に評価されていません。これに加えて、IPv6のトラフィックプロファイルは、より広範なコミュニティで使用される場合、将来的に大幅に変化する可能性があります。

If a Hash-based Selection with the BOB function is used with IPv6 traffic, the following input bytes MUST be used.

BOB関数を使用したハッシュベースの選択がIPv6トラフィックで使用される場合、次の入力バイトを使用する必要があります。

- Payload length (2 bytes)

- ペイロード長(2バイト)

- Byte number 10,11,14,15,16 of the IPv6 source address

- IPv6ソースアドレスのバイト番号10,11,14,15,16

- Byte number 10,11,14,15,16 of the IPv6 destination address

- IPv6宛先アドレスのバイト番号10,11,14,15,16

- A configurable number of bytes from the IP payload, starting at a configurable offset. It is recommended to use at least 4 bytes from the IP payload.

- 設定可能なオフセットから始まるIPペイロードからの構成可能な数のバイト。IPペイロードから少なくとも4バイトを使用することをお勧めします。

The payload itself is not changing during the path. Even if some routers process some extension headers, they are not going to strip them from the packet. Therefore, the payload length is invariant along the path. Furthermore, it usually differs for different packets. The IPv6 address has 16 bytes. The first part is the network part and contains low variation. The second part is the host part and contains higher variation. Therefore, the second part of the address is used. Nevertheless, the uniformity has not been checked for IPv6 traffic.

ペイロード自体はパス中に変化していません。一部のルーターがいくつかの拡張ヘッダーを処理したとしても、パケットからそれらを取り除くつもりはありません。したがって、ペイロードの長さはパスに沿って不変です。さらに、通常、異なるパケットで異なります。IPv6アドレスには16バイトがあります。最初の部分はネットワーク部分で、低い変動が含まれています。2番目の部分はホスト部品で、より高い変動が含まれています。したがって、アドレスの2番目の部分が使用されます。それにもかかわらず、IPv6トラフィックの均一性はチェックされていません。

6.2.4.2. Hash Functions Suitable for Packet Digesting
6.2.4.2. ハッシュ関数パケット消化に適しています

For this purpose also the BOB function SHOULD be used. Other functions (such as CRC-32) MAY be used. Among the functions capable of operating with variable-length input, BOB and CRC-32 have the fastest execution, BOB being slightly faster. IPSX is not recommended for digesting because it has a significantly higher collision rate and takes only a fixed-length input.

この目的のために、BOB関数も使用する必要があります。他の機能(CRC-32など)を使用できます。可変長さの入力で動作できる機能の中で、BobとCRC-32の実行は最速であり、ボブはわずかに速くなります。IPSXは、衝突速度が大幅に高く、固定長の入力のみを取得するため、消化には推奨されません。

7. Parameters for the Description of Selection Techniques
7. 選択手法の説明のためのパラメーター

This section gives an overview of different alternative selection schemes and their required parameters. In order to be compliant with PSAMP, at least one of proposed schemes MUST be implemented.

このセクションでは、さまざまな代替選択スキームとその必要なパラメーターの概要を説明します。PSAMPに準拠するには、少なくとも提案されたスキームの1つを実装する必要があります。

The decision whether or not to select a packet is based on a function that is performed when the packet arrives at the selection process. Packet selection schemes differ in the input parameters for the selection process and the functions they require to do the packet selection. The following table gives an overview.

パケットを選択するかどうかの決定は、パケットが選択プロセスに到着したときに実行される関数に基づいています。パケット選択スキームは、選択プロセスの入力パラメーターと、パケット選択を行うために必要な機能が異なります。次の表を概要に示します。

     Scheme       |   Input parameters     |     Functions
   ---------------+------------------------+-------------------
    systematic    |    packet position     |  packet counter
    count-based   |    Sampling pattern    |
   ---------------+------------------------+-------------------
    systematic    |      arrival time      |  clock or timer
    time-based    |     Sampling pattern   |
   ---------------+------------------------+-------------------
    random        |  packet position       |  packet counter,
    n-out-of-N    |  Sampling pattern      |  random numbers
                  | (random number list)   |
   ---------------+------------------------+-------------------
    uniform       |        Sampling        |  random function
    probabilistic |      probability       |
   ---------------+------------------------+-------------------
    non-uniform   |e.g., packet position,  | selection function,
    probabilistic |  Packet Content(parts) |  probability calc.
   ---------------+------------------------+-------------------
    non-uniform   |e.g., flow state,       | selection function,
    flow-state    |  Packet Content(parts) |  probability calc.
   ---------------+------------------------+-------------------
    property      | Packet Content(parts)  |  filter function or
    match         | or router state        |  state discovery
   ---------------+------------------------+-------------------
    hash-based    |  Packet Content(parts) |  Hash Function
   ---------------+------------------------+-------------------
        
7.1. Description of Sampling Techniques
7.1. サンプリング手法の説明

In this section, we define what elements are needed to describe the most common Sampling techniques. Here the selection function is predefined and given by the Selector ID.

このセクションでは、最も一般的なサンプリング手法を説明するために必要な要素を定義します。ここで、選択関数は事前に定義され、セレクターIDによって与えられます。

Sampler Description: SELECTOR_ID SELECTOR_TYPE SELECTOR_PARAMETERS

サンプラーの説明:selector_id selector_type selector_parameters

Where:

ただし:

SELECTOR_ID: Unique ID for the packet sampler.

selector_id:パケットサンプラー用の一意のID。

SELECTOR_TYPE: For Sampling processes, the SELECTOR TYPE defines what Sampling algorithm is used. Values: Systematic count-based | Systematic time-based | Random |n-out-of-N | uniform probabilistic | Non-uniform probabilistic | Non-uniform flow state

selector_type:サンプリングプロセスの場合、セレクタータイプは、サンプリングアルゴリズムが使用されるものを定義します。値:系統的カウントベース|体系的な時間ベース|ランダム| n-out-of-n |均一な確率|不均一な確率|不均一なフロー状態

SELECTOR_PARAMETERS: For Sampling processes, the SELECTOR PARAMETERS define the input parameters for the process. Interval length in systematic Sampling means that all packets that arrive in this interval are selected. The spacing parameter defines the spacing in time or number of packets between the end of one Sampling interval and the start of the next succeeding interval.

Selector_Parameters:サンプリングプロセスの場合、セレクターパラメーターはプロセスの入力パラメーターを定義します。系統的サンプリングの間隔長は、この間隔で到着するすべてのパケットが選択されることを意味します。間隔パラメーターは、1つのサンプリング間隔の終了と次の成功間隔の開始の間の時間の間隔またはパケットの数を定義します。

Case n-out-of-N: - Population Size N, Sample size n

ケースn-out-of-n: - 人口サイズn、サンプルサイズn

Case systematic time-based: - Interval length (in usec), Spacing (in usec)

ケース系統的時間ベース: - 間隔長(USEC)、間隔(USEC)

Case systematic count-based: - Interval length (in packets), Spacing (in packets)

ケース系統的カウントベース: - 間隔長(パケット内)、間隔(パケット内)

Case uniform probabilistic (with equal probability per packet): - Sampling probability p

ケース均一な確率(パケットごとに等しい確率を持つ): - サンプリング確率p

Case non-uniform probabilistic: - Calculation function for Sampling probability p (see also Section 5.2.2.4)

ケース不均一な確率: - サンプリング確率Pの計算関数(セクション5.2.2.4も参照)

Case flow state: - Information reported for flow state Sampling is not defined in this document (see also Section 5.2.2.4)

ケースフロー状態: - フロー状態のサンプリングについて報告されている情報は、このドキュメントでは定義されていません(セクション5.2.2.4も参照)

7.2. Description of Filtering Techniques
7.2. フィルタリング技術の説明

In this section, we define what elements are needed to describe the most common Filtering techniques. The structure closely parallels the one presented for the Sampling techniques.

このセクションでは、最も一般的なフィルタリング手法を説明するために必要な要素を定義します。この構造は、サンプリング手法で提示された構造と密接に類似しています。

Filter Description: SELECTOR_ID SELECTOR_TYPE SELECTOR_PARAMETERS

フィルターの説明:selector_id selector_type selector_parameters

Where:

ただし:

SELECTOR_ID: Unique ID for the packet filter. The ID can be calculated under consideration of the SELECTION SEQUENCE and a local ID.

selector_id:パケットフィルター用の一意のID。IDは、選択シーケンスとローカルIDを考慮して計算できます。

SELECTOR_TYPE: For Filtering processes, the SELECTOR TYPE defines what Filtering type is used. Values: Matching | Hashing | Router_state

selector_type:フィルタリングプロセスの場合、セレクタータイプは、どのフィルタリングタイプが使用されるかを定義します。値:マッチング|ハッシュ|router_state

SELECTOR_PARAMETERS: For Filtering processes, the SELECTOR PARAMETERS define formally the common property of the packet being filtered. For the filters of type matching and hashing, the definitions have a lot of points in common.

selector_parameters:フィルタリングプロセスの場合、セレクターパラメーターは、フィルタリングされているパケットの共通プロパティを正式に定義します。タイプマッチングとハッシュのフィルターの場合、定義には共通点がたくさんあります。

Values:

値:

Case matching: - Information Element (from [RFC5102]) - Value (type in accordance to [RFC5102])

ケースマッチング: - 情報要素([RFC5102]から) - 値([RFC5102]に従って入力)

In case of multiple match criteria, multiple "case matching" has to be bound by a logical AND.

複数の一致基準の場合、複数の「ケースマッチング」は論理に拘束される必要があります。

   Case hashing:
      - Hash Domain (input bits from packet)
           - <Header type = IPv4>
           - <Input bit specification, header part>
           - <Header type =  IPv6>
           - <Input bit specification, header part>
           - <payload byte number N>
           - <Input bit specification, payload part>
      - Hash Function
           - Hash Function name
           - Length of input key (eliminate 0x bytes)
           - Output value (length M and bitmask)
           - Hash Selection Range, as a list of non-overlapping
             intervals [start value, end value] where value is in
             [0,2^M-1]
           - Additional parameters are dependent on specific Hash
             Function (e.g., hash input bits (seed))
        

Notes to input bits for case hashing:

ケースハッシュの入力ビットへのメモ:

- Input bits can be from header part only, from the payload part only, or from both.

- 入力ビットは、ヘッダーパーツのみ、ペイロードパーツのみ、または両方からです。

- The bit specification, for the header part, can be specified for IPv4 or IPv6 only, or both.

- ヘッダーパーツのビット仕様は、IPv4またはIPv6のみまたはその両方で指定できます。

- In case of IPv4, the bit specification is a sequence of 20 hexadecimal numbers [00,FF] specifying a 20-byte bitmask to be applied to the header.

- IPv4の場合、ビット仕様は、20バイトのビットマスクを指定する20の16進数[00、FF]のシーケンスです。

- In case of IPv6, it is a sequence of 40 hexadecimal numbers [00,FF] specifying a 40-byte bitmask to be applied to the header.

- IPv6の場合、ヘッダーに適用される40バイトのビットマスクを指定する40の16進数[00、ff]のシーケンスです。

- The bit specification, for the payload part, is a sequence of hexadecimal numbers [00,FF] specifying the bitmask to be applied to the first N bytes of the payload, as specified by the previous field. In case the hexadecimal number sequence is longer than N, only the first N numbers are considered.

- ペイロードパーツのビット仕様は、前のフィールドで指定されているように、ペイロードの最初のnバイトに適用するビットマスクを指定する16進数[00、ff]のシーケンスです。16進数シーケンスがNより長い場合、最初のN数のみが考慮されます。

- In case the payload is shorter than N, the Hash Function cannot be applied. Other options, like padding with zeros, may be considered in the future.

- ペイロードがNよりも短い場合、ハッシュ関数を適用できません。ゼロのパディングのような他のオプションは、将来的に考慮されるかもしれません。

- A Hash Function cannot be defined on the options field of the IPv4 header, neither on stacked headers of IPv6.

- Hash関数は、IPv4ヘッダーのオプションフィールドで定義することはできません。どちらもIPv6の積み上げヘッダーではありません。

- The Hash Selection Range defines a range of hash values (out of all possible results of the hash operation). If the hash result for a specific packet falls in this range, the packet is selected. If the value is outside the range, the packet is not selected. For example, if the selection interval specification is [1:3], [6:9] all packets are selected for which the hash result is 1,2,3,6,7,8, or 9. In all other cases, the packet is not selected.

- ハッシュ選択範囲は、ハッシュ値の範囲を定義します(ハッシュ操作のすべての可能な結果のうち)。特定のパケットの結果の結果がこの範囲にある場合、パケットが選択されます。値が範囲の外側にある場合、パケットは選択されません。たとえば、選択間隔の仕様が[1:3]、[6:9]の場合、ハッシュ結果は1,2,3,6,7,8、または9であるすべてのパケットが選択されています。パケットは選択されていません。

Case router state:

ケースルーター状態:

- Ingress interface at which the packet arrives equals a specified value

- パケットが到着するイングレスインターフェイスは、指定された値に等しくなります

- Egress interface to which the packet is routed equals a specified value

- パケットがルーティングされている出力インターフェイスは、指定された値に等しくなります

- Packet violated Access Control List (ACL) on the router

- ルーターのパケット違反アクセス制御リスト(ACL)

- Reverse Path Forwarding (RPF) failed for the packet

- パケットのリバースパス転送(RPF)が失敗しました

- Resource Reservation is insufficient for the packet

- リソースの予約は、パケットには不十分です

- No route is found for the packet

- パケットにはルートはありません

- Origin AS equals a specified value or lies within a given range

- 原点としての起源は、指定された値に等しいか、特定の範囲内にあります

- Destination AS equals a specified value or lies within a given range

- 特定の範囲内に指定された値に等しい宛先

Note to case router state:

ケースルーター状態に注意してください:

- All router state entries can be linked by AND operators

- すべてのルーター状態エントリは、およびオペレーターによってリンクできます

8. Composite Techniques
8. 複合技術

Composite schemes are realized by combining the Selector IDs into a Selection Sequence. The Selection Sequence contains all Selector IDs that are applied to the Packet Stream subsequently. Some examples of composite schemes are reported below.

複合スキームは、セレクターIDを選択シーケンスに組み合わせることで実現されます。選択シーケンスには、その後パケットストリームに適用されるすべてのセレクターIDが含まれています。複合スキームのいくつかの例を以下に報告します。

8.1. Cascaded Filtering->Sampling or Sampling->Filtering
8.1. カスケードフィルタリング - >サンプリングまたはサンプリング - >フィルタリング

If a filter precedes a Sampling process, the role of Filtering is to create a set of "parent populations" from a single stream that can then be fed independently to different Sampling functions, with different parameters tuned for the Population itself (e.g., if streams of different intensity result from Filtering, it may be good to have different Sampling rates). If Filtering follows a Sampling process, the same Selection Fraction and type are applied to the whole stream, independently of the relative size of the streams resulting from the Filtering function. Moreover, also packets not destined to be selected in the Filtering operation will "load" the Sampling function. So, in principle, Filtering before Sampling allows a more accurate tuning of the Sampling procedure, but if filters are too complex to work at full line rate (e.g., because they have to access router state information), Sampling before Filtering may be a need.

フィルターがサンプリングプロセスの前に先行する場合、フィルタリングの役割は、単一のストリームから「親集団」のセットを作成することです。これにより、異なるサンプリング関数に独立して供給され、さまざまなパラメーターが母集団自体に合わせて調整されます(たとえば、ストリームの場合、フィルタリングから異なる強度の結果、異なるサンプリングレートを持つことが良いかもしれません)。フィルタリングがサンプリングプロセスに従う場合、フィルタリング関数に起因するストリームの相対サイズとは無関係に、同じ選択画分とタイプがストリーム全体に適用されます。さらに、フィルタリング操作で選択されていないパケットもサンプリング関数を「ロード」します。したがって、原則として、サンプリング前にフィルタリングをサンプリング手順をより正確に調整することができますが、フィルターがフルラインレートで動作するには複雑すぎる場合(例えば、ルーター状態情報にアクセスする必要があるため)、フィルタリングの前にサンプリングは必要になる場合があります。。

8.2. Stratified Sampling
8.2. 層化抽出法

Stratified Sampling is one example for using a composite technique. The basic idea behind stratified Sampling is to increase the estimation accuracy by using a priori information about correlations of the investigated characteristic with some other characteristic that is easier to obtain. The a priori information is used to perform an intelligent grouping of the elements of the parent Population. In this manner, a higher estimation accuracy can be achieved with the same sample size or the sample size can be reduced without reducing the estimation accuracy.

層状サンプリングは、複合技術を使用するための一例です。層別サンプリングの背後にある基本的なアイデアは、調査された特性の相関に関するアプリオリ情報を使用して、取得しやすい他の特性と推定精度を高めることです。アプリオリ情報は、親集団の要素のインテリジェントなグループ化を実行するために使用されます。このようにして、同じサンプルサイズでより高い推定精度を達成するか、推定精度を低下させることなくサンプルサイズを縮小できます。

Stratified Sampling divides the Sampling process into multiple steps. First, the elements of the parent Population are grouped into subsets in accordance to a given characteristic. This grouping can be done in multiple steps. Then samples are taken from each subset.

層状サンプリングは、サンプリングプロセスを複数のステップに分割します。まず、親集団の要素は、特定の特性に従ってサブセットにグループ化されます。このグループ化は、複数のステップで実行できます。次に、各サブセットからサンプルが採取されます。

The stronger the correlation between the characteristic used to divide the parent Population (stratification variable) and the characteristic of interest (for which an estimate is sought after), the easier is the consecutive Sampling process and the higher is the stratification gain. For instance, if the dividing characteristic were equal to the investigated characteristic, each element of the subgroup would be a perfect representative of that characteristic. In this case, it would be sufficient to take one arbitrary element out of each subgroup to get the actual distribution of the characteristic in the parent Population. Therefore, stratified Sampling can reduce the costs for the Sampling process (i.e., the number of samples needed to achieve a given level of confidence).

親母集団(層別化変数)と関心のある特性(推定値が求められる)を分割するために使用される特性との相関が強いほど、連続したサンプリングプロセスが容易であり、高度化は成層ゲインです。たとえば、分裂特性が調査された特性と等しい場合、サブグループの各要素はその特性の完全な表現です。この場合、親集団の特性の実際の分布を取得するために、各サブグループから1つの任意の要素を取り除くだけで十分でしょう。したがって、層別サンプリングは、サンプリングプロセスのコストを削減できます(つまり、特定のレベルの信頼性を達成するために必要なサンプルの数)。

For stratified Sampling, one has to specify classification rules for grouping the elements into subgroups and the Sampling scheme that is used within the subgroups. The classification rules can be expressed by multiple filters. For the Sampling scheme within the subgroups, the parameters have to be specified as described above. The use of stratified Sampling methods for measurement purposes is described for instance in [ClPB93] and [Zseb03].

層別サンプリングの場合、要素をサブグループにグループ化するための分類ルールと、サブグループ内で使用されるサンプリングスキームを指定する必要があります。分類ルールは、複数のフィルターで表現できます。サブグループ内のサンプリングスキームの場合、上記のようにパラメーターを指定する必要があります。測定目的で層別サンプリング方法の使用は、たとえば[Clpb93]および[ZSEB03]で説明されています。

9. Security Considerations
9. セキュリティに関する考慮事項

Security considerations concerning the choice of a Hash Function for Hash-based Selection have been discussed in Section 6.2.3. That section discussed a number of potential attacks to craft Packet Streams that are disproportionately detected and/or discover the Hash Function parameters, the vulnerabilities of different Hash Functions to these attacks, and practices to minimize these vulnerabilities.

ハッシュベースの選択のハッシュ関数の選択に関するセキュリティ上の考慮事項は、セクション6.2.3で説明されています。そのセクションでは、ハッシュ関数パラメーター、これらの攻撃に対する異なるハッシュ関数の脆弱性、およびこれらの脆弱性を最小限に抑える実践の脆弱性を不釣り合いに検出したり、発見したりするパケットストリームを作成するための多くの潜在的な攻撃について説明しました。

In addition to this, a user can gain knowledge about the start and stop triggers in time-based systematic Sampling, e.g., by sending test packets. This knowledge might allow users to modify their send schedule in a way that their packets are disproportionately selected or not selected [GoRe07].

これに加えて、ユーザーは、テストパケットを送信することにより、時間ベースの体系的なサンプリングで開始トリガーと停止トリガーに関する知識を得ることができます。この知識により、ユーザーはパケットが不釣り合いに選択されているか、選択されていないように送信スケジュールを変更できる可能性があります[Gore07]。

For random Sampling, a cryptographically strong random number generator should be used in order to prevent that an advisory can predict the selection decision [GoRe07].

ランダムサンプリングの場合、アドバイザリーが選択決定を予測できることを防ぐために、暗号的に強い乱数ジェネレーターを使用する必要があります[Gore07]。

Further security threats can occur when Sampling parameters are configured or communicated to other entities. The configuration and reporting of Sampling parameters are out of scope of this document. Therefore, the security threats that originate from this kind of communication cannot be assessed with the information given in this document.

サンプリングパラメーターが他のエンティティに構成または通信されると、さらなるセキュリティの脅威が発生する可能性があります。サンプリングパラメーターの構成とレポートは、このドキュメントの範囲外です。したがって、この種の通信に由来するセキュリティの脅威は、このドキュメントに記載されている情報で評価することはできません。

Some of these threats can probably be addressed by keeping configuration information confidential and by authenticating entities that configure Sampling. Nevertheless, a full analysis and assessment of threats for configuration and reporting has to be done if configuration or reporting methods are proposed.

これらの脅威のいくつかは、おそらく構成情報を秘密にしておくことと、サンプリングを構成するエンティティを認証することによって対処できます。それにもかかわらず、構成と報告方法が提案されている場合は、構成とレポートの脅威の完全な分析と評価を行う必要があります。

10. Contributors
10. 貢献者

Sharon Goldberg contributed to the security considerations for Hash-based Selection.

シャロン・ゴールドバーグは、ハッシュベースの選択のセキュリティ上の考慮事項に貢献しました。

Sharon Goldberg Department of Electrical Engineering Princeton University F210-K EQuad Princeton, NJ 08544, USA EMail: goldbe@princeton.edu

シャロンゴールドバーグ電気工学部プリンストン大学F210-Kエクアドプリンストン、ニュージャージー州08544、米国メール:goldbe@princeton.edu

11. Acknowledgments
11. 謝辞

We would like to thank the PSAMP group, especially Benoit Claise and Stewart Bryant, for fruitful discussions and for proofreading the document. We thank Sharon Goldberg for her input on security issues concerning Hash-based Selection.

Psampグループ、特にBenoit ClaiseとStewart Bryantに、実り多い議論とドキュメントの校正について感謝します。Hashベースの選択に関するセキュリティ問題に関する彼女の意見について、Sharon Goldbergに感謝します。

12. References
12. 参考文献
12.1. Normative References
12.1. 引用文献

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC2119] Bradner、S。、「要件レベルを示すためにRFCで使用するためのキーワード」、BCP 14、RFC 2119、1997年3月。

12.2. Informative References
12.2. 参考引用

[AmCa89] Paul D. Amer, Lillian N. Cassel, "Management of Sampled Real-Time Network Measurements", 14th Conference on Local Computer Networks, October 1989, Minneapolis, pages 62-68, IEEE, 1989.

[AMCA89] Paul D. Amer、Lillian N. Cassel、「サンプリングされたリアルタイムネットワーク測定の管理」、第14回ローカルコンピューターネットワーク、1989年10月、ミネアポリス、62〜68ページ、IEEE、1989年。

[BeCK96] M. Bellare, R. Canetti and H. Krawczyk, "Pseudorandom Functions Revisited: The Cascade Construction and its Concrete Security", Symposium on Foundations of Computer Science, 1996.

[Beck96] M. Bellare、R。CanettiおよびH. Krawczyk、「擬似ランダム機能の再訪:カスケード構造とその具体的なセキュリティ」、1996年のコンピューターサイエンスの基礎に関するシンポジウム。

[ClPB93] K.C. Claffy, George C. Polyzos, Hans-Werner Braun, "Application of Sampling Methodologies to Network Traffic Characterization", Proceedings of ACM SIGCOMM'93, San Francisco, CA, USA, September 13 - 17, 1993.

[CLPB93] K.C.Claffy、George C. Polyzos、Hans -Werner Braun、「ネットワークトラフィックの特性評価へのサンプリング方法論の適用」、ACM Sigcomm'93の議事録、米国、サンフランシスコ、1993年9月13日 - 17日。

[DuGG02] N.G. Duffield, A. Gerber, M. Grossglauser, "Trajectory Engine: A Backend for Trajectory Sampling", IEEE Network Operations and Management Symposium 2002, Florence, Italy, April 15-19, 2002.

[dugg02] N.G.Duffield、A。Gerber、M。Grossglauser、「軌跡エンジン:軌道サンプリングのためのバックエンド」、IEEEネットワーク運用および管理シンポジウム2002、フィレンツェ、イタリア、2002年4月15〜19日。

[DuGr00] N.G. Duffield, M. Grossglauser, "Trajectory Sampling for Direct Traffic Observation", Proceedings of ACM SIGCOMM 2000, Stockholm, Sweden, August 28 - September 1, 2000.

[dugr00] n.g.Duffield、M。Grossglauser、「直接交通観察のための軌跡サンプリング」、ACM Sigcomm 2000の議事録、スウェーデン、ストックホルム、8月28日 - 2000年9月1日。

[DuGr04] N.G. Duffield and M. Grossglauser "Trajectory Sampling with Unreliable Reporting", Proc IEEE Infocom 2004, Hong Kong, March 2004.

[dugr04] n.g.DuffieldとM. Grossglauser「信頼性の低い報告による軌道サンプリング」、Proc IEEE Infocom 2004、香港、2004年3月。

[DuLT01] N.G. Duffield, C. Lund, and M. Thorup, "Charging from Sampled Network Usage", ACM Internet Measurement Workshop IMW 2001, San Francisco, USA, November 1-2, 2001.

[Dult01] N.G.Duffield、C。Lund、およびM. Thorup、「サンプリングされたネットワーク使用からの請求」、ACMインターネット測定ワークショップIMW 2001、サンフランシスコ、米国、2001年11月1〜2日。

[EsVa01] C. Estan and G. Varghese, "New Directions in Traffic Measurement and Accounting", ACM SIGCOMM Internet Measurement Workshop 2001, San Francisco (CA) Nov. 2001.

[ESVA01] C. EstanおよびG. Varghese、「交通測定と会計の新しい方向」、ACM Sigcomm Internet Measurement Workshop 2001、San Francisco(CA)2001年11月。

[GoRe07] S. Goldberg, J. Rexford, "Security Vulnerabilities and Solutions for Packet Sampling", IEEE Sarnoff Symposium, Princeton, NJ, May 2007.

[Gore07] S. Goldberg、J。Rexford、「パケットサンプリングのセキュリティの脆弱性とソリューション」、IEEE Sarnoff Symposium、プリンストン、ニュージャージー州、2007年5月。

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

[HT52] D.G.HorvitzとD.J.トンプソン、「有限の宇宙からの交換なしのサンプリングの一般化」J.アメル。統計学者。協会。Vol。47、pp。663-685、1952。

[Henk08] Christian Henke, Evaluation of Hash Functions for Multipoint Sampling in IP Networks, Diploma Thesis, TU Berlin, April 2008.

[HENK08] Christian Henke、IPネットワークでのマルチポイントサンプリングのためのハッシュ関数の評価、Diploma論文、TUベルリン、2008年4月。

[HeSZ08] Christian Henke, Carsten Schmoll, Tanja Zseby, Evaluation of Header Field Entropy for Hash-Based Packet Selection, Proceedings of Passive and Active Measurement Conference PAM 2008, Cleveland, Ohio, USA, April 2008.

[HESZ08] Christian Henke、Carsten Schmoll、Tanja Zseby、Hashベースのパケット選択のためのヘッダーフィールドエントロピーの評価、パッシブおよびアクティブ測定会議PAM 2008の議事録、米国オハイオ州クリーブランド、2008年4月。

[Jenk97] B. Jenkins, "Algorithm Alley", Dr. Dobb's Journal, September 1997. http://burtleburtle.net/bob/hash/doobs.html.

[Jenk97] B. Jenkins、「Algorithm Alley」、Dr。Dobb's Journal、1997年9月。http://burtleburtle.net/bob/hash/doobs.html。

[JePP92] Jonathan Jedwab, Peter Phaal, Bob Pinna, "Traffic Estimation for the Largest Sources on a Network, Using Packet Sampling with Limited Storage", HP technical report, Managemenr, Mathematics and Security Department, HP Laboratories, Bristol, March 1992, http://www.hpl.hp.com/techreports/92/HPL-92-35.html.

[Jepp92] Jonathan Jedwab、Peter Phaal、Bob Pinna、「ネットワーク上の最大のソースの交通量の推定、限られたストレージを備えたパケットサンプリングを使用して」、HPテクニカルレポート、ManageMenR、数学およびセキュリティ部門、HP研究所、ブリストル、1992年3月、http://www.hpl.hp.com/techreports/92/hpl-92-35.html。

[Moli03] M. Molina, "A scalable and efficient methodology for flow monitoring in the Internet", International Teletraffic Congress (ITC-18), Berlin, Sep. 2003.

[Moli03] M. Molina、「インターネットでのフローモニタリングのためのスケーラブルで効率的な方法論」、国際テレトラフィック議会(ITC-18)、ベルリン、2003年9月。

[MoND05] M. Molina, S. Niccolini, N.G. Duffield, "A Comparative Experimental Study of Hash Functions Applied to Packet Sampling", International Teletraffic Congress (ITC-19), Beijing, August 2005.

[MOND05] M. Molina、S。Niccolini、N.G。Duffield、「パケットサンプリングに適用されたハッシュ機能の比較実験的研究」、国際テレトラフィック議会(ITC-19)、北京、2005年8月。

[RFC1141] Mallory, T. and A. Kullberg, "Incremental updating of the Internet checksum", RFC 1141, January 1990.

[RFC1141] Mallory、T。およびA. Kullberg、「インターネットチェックサムの増分更新」、RFC 1141、1990年1月。

[RFC1624] Rijsinghani, A., Ed., "Computation of the Internet Checksum via Incremental Update", RFC 1624, May 1994.

[RFC1624] Rijsinghani、A.、ed。、「インクリメンタルアップデートによるインターネットチェックサムの計算」、RFC 1624、1994年5月。

[RFC2205] Braden, R., Ed., Zhang, L., Berson, S., Herzog, S., and S. Jamin, "Resource ReSerVation Protocol (RSVP) -- Version 1 Functional Specification", RFC 2205, September 1997.

[RFC2205] Braden、R.、Ed。、Zhang、L.、Berson、S.、Herzog、S.、およびS. Jamin、「リソース予約プロトコル(RSVP) - バージョン1機能仕様」、RFC 2205、9月1997年。

[RFC3704] Baker, F. and P. Savola, "Ingress Filtering for Multihomed Networks", BCP 84, RFC 3704, March 2004.

[RFC3704] Baker、F。およびP. Savola、「マルチホームネットワークのイングレスフィルタリング」、BCP 84、RFC 3704、2004年3月。

[RFC3917] Quittek, J., Zseby, T., Claise, B., and S. Zander, "Requirements for IP Flow Information Export (IPFIX)", RFC 3917, October 2004.

[RFC3917] Quittek、J.、Zseby、T.、Claise、B。、およびS. Zander、「IP Flow Information Export(IPFIX)の要件」、RFC 3917、2004年10月。

[RFC4271] Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A Border Gateway Protocol 4 (BGP-4)", RFC 4271, January 2006.

[RFC4271] Rekhter、Y.、Ed。、Li、T.、ed。、およびS. Hares、ed。、「A Border Gateway Protocol 4(BGP-4)」、RFC 4271、2006年1月。

[RFC5101] Claise, B., Ed., "Specification of the IP Flow Information Export (IPFIX) Protocol for the Exchange of IP Traffic Flow Information", RFC 5101, January 2008.

[RFC5101] Claise、B.、ed。、「IPトラフィックフロー情報の交換のためのIPフロー情報エクスポート(IPFIX)プロトコルの仕様」、RFC 5101、2008年1月。

[RFC5102] Quittek, J., Bryant, S., Claise, B., Aitken, P., and J. Meyer, "Information Model for IP Flow Information Export", RFC 5102, January 2008.

[RFC5102] Quittek、J.、Bryant、S.、Claise、B.、Aitken、P。、およびJ. Meyer、「IPフロー情報エクスポートの情報モデル」、RFC 5102、2008年1月。

[RFC5474] Duffield, N., Ed., "A Framework for Packet Selection and Reporting", RFC 5474, March 2009.

[RFC5474] Duffield、N.、ed。、「パケット選択とレポートのフレームワーク」、RFC 5474、2009年3月。

[RFC5476] Claise, B., Ed., "Packet Sampling (PSAMP) Protocol Specifications", RFC 5476, March 2009.

[RFC5476] Claise、B.、ed。、「パケットサンプリング(PSAMP)プロトコル仕様」、RFC 5476、2009年3月。

[RFC5477] Dietz, T., Claise, B., Aitken, P., Dressler, F., and G. Carle, "Information Model for Packet Sampling Exports", RFC 5477, March 2009.

[RFC5477] Dietz、T.、Claise、B.、Aitken、P.、Dressler、F.、およびG. Carle、「パケットサンプリングエクスポートの情報モデル」、RFC 5477、2009年3月。

[Zseb03] T. Zseby, "Stratification Strategies for Sampling-based Non-intrusive Measurement of One-way Delay", Proceedings of Passive and Active Measurement Workshop (PAM 2003), La Jolla, CA, USA, pp. 171-179, April 2003.

[ZSEB03] T. Zseby、「サンプリングベースの一元配置遅延の非侵入測定のための層別化戦略」、パッシブおよびアクティブ測定ワークショップの議事録(PAM 2003)、ラホーヤ、カリフォルニア州、171-179、pp。171-179、2003年4月。

[ZsZC01] Tanja Zseby, Sebastian Zander, Georg Carle. Evaluation of Building Blocks for Passive One-way-delay Measurements. Proceedings of Passive and Active Measurement Workshop (PAM 2001), Amsterdam, The Netherlands, April 23-24, 2001.

[ZSZC01]タンジャ・ズビー、セバスチャン・ザンダー、ジョージ・カール。受動的な一方向測定のためのビルディングブロックの評価。パッシブおよびアクティブ測定ワークショップの議事録(PAM 2001)、アムステルダム、オランダ、2001年4月23〜24日。

Appendix A. Hash Functions
付録A. ハッシュ関数
A.1. IP Shift-XOR (IPSX) Hash Function
A.1. IP Shift-XOR(IPSX)ハッシュ関数

The IPSX Hash Function is tailored for acting on IP version 4 packets. It exploits the structure of IP packets and in particular the variability expected to be exhibited within different fields of the IP packet in order to furnish a hash value with little apparent correlation with individual packet fields. Fields from the IPv4 and TCP/UDP headers are used as input. The IPSX Hash Function uses a small number of simple instructions.

IPSXハッシュ関数は、IPバージョン4パケットに作用するために調整されています。IPパケットの構造、特に個々のパケットフィールドとの明らかな相関関係がほとんどないハッシュ値を提供するために、IPパケットの異なるフィールド内で展示されると予想される変動性を活用します。IPv4およびTCP/UDPヘッダーのフィールドは、入力として使用されます。IPSXハッシュ関数は、少数の簡単な命令を使用します。

Input parameters: None

入力パラメーター:なし

Built-in parameters: None

組み込みパラメーター:なし

Output: The output of the IPSX is a 16-bit number

出力:IPSXの出力は16ビット番号です

Functioning:

機能:

The functioning can be divided into two parts: input selection, whose forms are composite input from various portions of the IP packet, followed by computation of the hash on the composite.

機能は、入力選択の2つの部分に分けることができます。そのフォームは、IPパケットのさまざまな部分からのコンポジット入力であり、続いて複合材のハッシュを計算します。

Input Selection:

入力選択:

The raw input is drawn from the first 20 bytes of the IP packet header and the first 8 bytes of the IP payload. If IP options are not used, the IP header has 20 bytes, and hence the two portions adjoin and comprise the first 28 bytes of the IP packet. We now use the raw input as four 32-bit subportions of these 28 bytes. We specify the input by bit offsets from the start of IP header or payload.

生の入力は、IPパケットヘッダーの最初の20バイトとIPペイロードの最初の8バイトから描画されます。IPオプションを使用していない場合、IPヘッダーには20バイトがあるため、2つの部分がIPパケットの最初の28バイトに隣接して構成されます。現在、生の入力をこれらの28バイトの4つの32ビットサブポーションとして使用します。IPヘッダーまたはペイロードの開始からビットオフセットで入力を指定します。

f1 = bits 32 to 63 of the IP header, comprising the IP identification field, flags, and fragment offset.

F1 = IPヘッダーの32〜63のビット。IP識別フィールド、フラグ、およびフラグメントオフセットを含む。

f2 = bits 96 to 127 of the IP header, the source IP address.

F2 = IPヘッダーのビット96〜127、ソースIPアドレス。

f3 = bits 128 to 159 of the IP header, the destination IP address.

F3 = IPヘッダーの128〜159、宛先IPアドレス。

f4 = bits 32 to 63 of the IP payload. For a TCP packet, f4 comprises the TCP sequence number followed by the message length. For a UDP packet, f4 comprises the UDP checksum.

F4 = IPペイロードの32〜63。TCPパケットの場合、F4はTCPシーケンス番号に続いてメッセージの長さが続きます。UDPパケットの場合、F4はUDPチェックサムで構成されています。

Hash Computation:

ハッシュ計算:

The hash is computed from f1, f2, f3, and f4 by a combination of XOR (^), right shift (>>), and left shift (<<) operations. The intermediate quantities h1, v1, and v2 are 32-bit numbers.

ハッシュは、XOR(^)、右シフト(>>)、および左シフト(<<)操作の組み合わせにより、F1、F2、F3、およびF4から計算されます。中間量H1、V1、およびV2は32ビット数です。

1. v1 = f1 ^ f2; 2. v2 = f3 ^ f4; 3. h1 = v1 << 8; 4. h1 ^= v1 >> 4; 5. h1 ^= v1 >> 12; 6. h1 ^= v1 >> 16; 7. h1 ^= v2 << 6; 8. h1 ^= v2 << 10; 9. h1 ^= v2 << 14; 10. h1 ^= v2 >> 7;

1. v1 = f1 ^ f2;2. v2 = f3 ^ f4;3. H1 = V1 << 8;4. h1 ^= v1 >> 4;5. H1 ^= V1 >> 12;6. H1 ^= V1 >> 16;7. H1 ^= V2 << 6;8. H1 ^= V2 << 10;9. H1 ^= V2 << 14;10. H1 ^= V2 >> 7;

The output of the hash is the least significant 16 bits of h1.

ハッシュの出力は、H1の最も重要ではない16ビットです。

A.2. BOB Hash Function
A.2. ボブハッシュ機能

The BOB Hash Function is a Hash Function designed for having each bit of the input affecting every bit of the return value and using both 1-bit and 2-bit deltas to achieve the so-called avalanche effect [Jenk97]. This function was originally built for hash table lookup with fast software implementation.

BOBハッシュ関数は、入力の各ビットを返す値のすべてに影響を与え、1ビットと2ビットの両方のデルタを使用して、いわゆる雪崩効果を実現するために設計されたハッシュ関数です[jenk97]。この関数は、元々、高速ソフトウェア実装によりハッシュテーブル検索用に構築されました。

Input parameters:

入力パラメーター:

The input parameters of such a function are:

このような関数の入力パラメーターは次のとおりです。

- the length of the input string (key) to be hashed, in bytes. The elementary input blocks of BOB hash are the single bytes; therefore, no padding is needed.

- ハッシュする入力文字列(キー)の長さ、バイトで。Bob Hashの基本入力ブロックは、単一バイトです。したがって、パディングは必要ありません。

- an init value (an arbitrary 32-bit number).

- init値(任意の32ビット番号)。

Built-in parameters:

組み込みパラメーター:

The BOB hash uses the following built-in parameter:

Bob Hashは、次の組み込みパラメーターを使用します。

- the golden ratio (an arbitrary 32-bit number used in the Hash Function computation: its purpose is to avoid mapping all zeros to all zeros).

- ゴールデン比(ハッシュ関数計算で使用される任意の32ビット数:その目的は、すべてのゼロをすべてのゼロにマッピングすることを避けることです)。

Note: The mix sub-function (see mix (a,b,c) macro in the reference code below) has a number of parameters governing the shifts in the registers. The one presented is not the only possible choice.

注:ミックスサブ機能(以下の参照コードのミックス(a、b、c)マクロを参照)には、レジスタのシフトを管理する多くのパラメーターがあります。提示されたものは、可能な選択だけではありません。

It is an open point whether these may be considered additional built-in parameters to specify at function configuration.

これらが関数構成で指定する追加の組み込みパラメーターと見なされるかどうかは、オープンポイントです。

Output:

出力:

The output of the BOB function is a 32-bit number. It should be specified:

BOB関数の出力は32ビット数です。指定する必要があります。

- A 32-bit mask to apply to the output

- 出力に適用する32ビットマスク

- The Selection Range as a list of non-overlapping intervals [start value, end value] where value is in [0,2^32]

- [0,2^32]に値がある場合、重複しない間隔のリストとしての選択範囲[開始値、終了値]

Functioning:

機能:

The hash value is obtained computing first an initialization of an internal state (composed of three 32-bit numbers, called a, b, c in the reference code below), then, for each input byte of the key the internal state is combined by addition and mixed using the mix sub-function. Finally, the internal state mixed one last time and the third number of the state (c) is chosen as the return value.

ハッシュ値は取得され、最初に内部状態の初期化(下の参照コードでa、b、cと呼ばれる3つの32ビット数値で構成される)の初期化が取得され、次に、キーの入力バイトごとに内部状態が結合されます。ミックスサブ機能を使用して追加および混合。最後に、内部状態は最後に混合され、状態の3番目の数(c)が返品値として選択されます。

   typedef unsigned long int  ub4;   /* unsigned 4-byte quantities
   */
   typedef unsigned      char ub1;   /* unsigned 1-byte quantities
   */
        
   #define hashsize(n) ((ub4)1<<(n))
   #define hashmask(n) (hashsize(n)-1)
        
   /* ------------------------------------------------------
     mix -- mix three 32-bit values reversibly.
        

For every delta with one or two bits set, and the deltas of all three high bits or all three low bits, whether the original value of a,b,c is almost all zero or is uniformly distributed, * If mix() is run forward or backward, at least 32 bits in a,b,c have at least 1/4 probability of changing. * If mix() is run forward, every bit of c will change between 1/3 and 2/3 of the time (well, 22/100 and 78/100 for some 2- bit deltas) mix() was built out of 36 single-cycle latency instructions in a structure that could support 2x parallelism, like so:

1つまたは2つのビットがセットされたすべてのデルタ、および3つのハイビットすべてまたは3つの低ビットすべてのデルタについて、A、B、Cの元の値がほぼすべてゼロであるか、均一に分布しているか、 * MIX()が実行される場合 *前方または後方、A、B、Cの少なくとも32ビットには、少なくとも1/4の確率が変化する可能性があります。* Mix()が前方に実行されると、Cのすべてのビットが1/3から2/3の間に変化します(約2ビットDeltasの場合、22/100および78/100)MIX()が組み込まれました。36シングルサイクルのレイテンシー命令2倍の並列性をサポートできる構造のように、

           a -= b;
           a -= c; x = (c>>13);
           b -= c; a ^= x;
           b -= a; x = (a<<8);
           c -= a; b ^= x;
           c -= b; x = (b>>13);
           ...
   Unfortunately, superscalar Pentiums and Sparcs can't take
   advantage of that parallelism.  They've also turned some of
   those single-cycle latency instructions into multi-cycle latency
   instructions
        
   ------------------------------------------------------------*/
        
     #define mix(a,b,c)  \
     { \
       a -= b; a -= c; a ^= (c>>13); \
       b -= c; b -= a; b ^= (a<<8); \
       c -= a; c -= b; c ^= (b>>13); \
       a -= b; a -= c; a ^= (c>>12);  \
       b -= c; b -= a; b ^= (a<<16); \
       c -= a; c -= b; c ^= (b>>5); \
       a -= b; a -= c; a ^= (c>>3);  \
       b -= c; b -= a; b ^= (a<<10); \
       c -= a; c -= b; c ^= (b>>15); \
     }
        
     /* -----------------------------------------------------------
   hash() -- hash a variable-length key into a 32-bit value
   k       : the key (the unaligned variable-length array of bytes)
   len     : the length of the key, counting by bytes
   initval : can be any 4-byte value
   Returns a 32-bit value.  Every bit of the key affects every bit
   of the return value.  Every 1-bit and 2-bit delta achieves
   avalanche.  About 6*len+35 instructions.
        
   The best hash table sizes are powers of 2.  There is no need to do
   mod a prime (mod is so slow!).  If you need less than 32 bits, use a
   bitmask.  For example, if you need only 10 bits, do h = (h &
   hashmask(10)), in which case, the hash table should have hashsize(10)
   elements.
        
   If you are hashing n strings (ub1 **)k, do it like this: for (i=0,
   h=0; i<n; ++i) h = hash( k[i], len[i], h);
        
   By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use
   this code any way you wish, private, educational, or commercial.
   It's free.  See http://burtleburtle.net/bob/hash/evahash.html.
   Use for hash table lookup, or anything where one collision in 2^^32
   is acceptable.  Do NOT use for cryptographic purposes.
    ----------------------------------------------------------- */
        
     ub4 bob_hash(k, length, initval)
     register ub1 *k;        /* the key */
     register ub4  length;   /* the length of the key */
     register ub4  initval;  /* an arbitrary value */
     {
        register ub4 a,b,c,len;
        
        /* Set up the internal state */
        len = length;
        a = b = 0x9e3779b9; /*the golden ratio; an arbitrary value
   */
        c = initval;         /* another arbitrary value */
        
   /*------------------------------------ handle most of the key */
        
        while (len >= 12)
        {
           a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16)
   +((ub4)k[3]<<24));
           b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16)
   +((ub4)k[7]<<24));
           c += (k[8] +((ub4)k[9]<<8)
   +((ub4)k[10]<<16)+((ub4)k[11]<<24));
           mix(a,b,c);
           k += 12; len -= 12;
        }
        
        /*---------------------------- handle the last 11 bytes */
        c += length;
        switch(len)       /* all the case statements fall through*/
        {
        case 11: c+=((ub4)k[10]<<24);
        case 10: c+=((ub4)k[9]<<16);
        case 9 : c+=((ub4)k[8]<<8);
           /* the first byte of c is reserved for the length */
        case 8 : b+=((ub4)k[7]<<24);
        case 7 : b+=((ub4)k[6]<<16);
        case 6 : b+=((ub4)k[5]<<8);
        case 5 : b+=k[4];
        case 4 : a+=((ub4)k[3]<<24);
        case 3 : a+=((ub4)k[2]<<16);
        
        case 2 : a+=((ub4)k[1]<<8);
        case 1 : a+=k[0];
          /* case 0: nothing left to add */
        }
        mix(a,b,c);
        /*-------------------------------- report the result */
        return c;
     }
        

Authors' Addresses

著者のアドレス

Tanja Zseby Fraunhofer Institute for Open Communication Systems Kaiserin-Augusta-Allee 31 10589 Berlin Germany Phone: +49-30-34 63 7153 EMail: tanja.zseby@fokus.fraunhofer.de

Tanja Zseby Fraunhofer Open Communication Systems for Open Communication Systems Kaiserin-Augusta-Allee 31 10589ベルリンドイツ電話:49-30-34 63 7153メール:tanja.zseby@fokus.fraunhofer.de

Maurizio Molina DANTE City House 126-130 Hills Road Cambridge CB21PQ United Kingdom Phone: +44 1223 371 300 EMail: maurizio.molina@dante.org.uk

Maurizio Molina Dante City House 126-130 Hills Road Cambridge CB21PQ英国電話:44 1223 371 300メール:maurizio.molina@dante.org.uk

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

Nick Duffield AT&T Labs-Research Room B-139 180 Park Ave Florham Park、NJ 07932 USA電話:1 973-360-8726メール:duffield@research.att.com

Saverio Niccolini Network Laboratories, NEC Europe Ltd. Kurfuerstenanlage 36 69115 Heidelberg Germany Phone: +49-6221-9051118 EMail: saverio.niccolini@netlab.nec.de

Saverio Niccolini Network Laboratories、Nec Europe Ltd. Kurfuerstenanlage 36 69115 Heidelbergドイツ電話:49-6221-9051118メール:saverio.niccolini@netlab.nec.de

Frederic Raspall EPSC-UPC Dept. of Telematics Av. del Canal Olimpic, s/n Edifici C4 E-08860 Castelldefels, Barcelona Spain EMail: fredi@entel.upc.es

Frederic Raspall EPSC-UPC Dept. of Telematics Av。Del Canal Olimpic、S/N Edifici C4 E-08860 CastellDefels、バルセロナスペインメール:fredi@entel.upc.es