公开(公告)号：US09571366B2

公开(公告)日：2017-02-14

申请号：US12647537

申请日：2009-12-27

Applicant: Nicholas Duffield ,  Paul Barford ,  Amos Ron ,  Joel Sommers

Inventor： Nicholas Duffield ,  Paul Barford ,  Amos Ron ,  Joel Sommers

IPC: G06F11/00 ,  H04L12/26 ,  H04L12/24

CPC classification number: H04L43/0852 ,  H04L41/5003 ,  H04L43/0823 ,  H04L43/10 ,  H04L43/16

Abstract: A method and apparatus for detecting and localizing an anomaly for a network are disclosed. For example, the method sends a first set of probe packets on at least one path of the network, and detects a performance anomaly on a first path of the at least one path. The method then identifies at least one link on the first path that is responsible for the performance anomaly by applying a second set of probe packets.

Abstract translation: 公开了一种用于检测和定位网络异常的方法和装置。 例如，该方法在网络的至少一个路径上发送第一组探测包，并且检测至少一个路径的第一路径上的性能异常。 该方法然后通过应用第二组探测分组来识别负责性能异常的第一路径上的至少一个链路。

公开(公告)号：US09258217B2

公开(公告)日：2016-02-09

申请号：US12568044

申请日：2009-09-28

Applicant: Nicholas Duffield ,  Patrick Haffner ,  Balachander Krishnamurthy ,  Haakon Andreas Ringberg

Inventor： Nicholas Duffield ,  Patrick Haffner ,  Balachander Krishnamurthy ,  Haakon Andreas Ringberg

IPC: H04L12/721 ,  H04L12/26 ,  G06F21/55 ,  H04L12/703 ,  H04L12/801 ,  H04L12/851 ,  H04L29/06 ,  H04L12/24

CPC classification number: H04L63/20 ,  G06F21/552 ,  G06N5/025 ,  H04L41/00 ,  H04L41/0604 ,  H04L41/16 ,  H04L43/026 ,  H04L43/028 ,  H04L43/16 ,  H04L45/28 ,  H04L45/38 ,  H04L47/10 ,  H04L47/24 ,  H04L63/14 ,  H04L63/1416 ,  H04L63/1425 ,  H04L63/30

Abstract: A system to detect anomalies in internet protocol (IP) flows uses a set of machine-learning (ML) rules that can be applied in real time at the IP flow level. A communication network has a large number of routers that can be equipped with flow monitoring capability. A flow collector collects flow data from the routers throughout the communication network and provides them to a flow classifier. At the same time, a limited number of locations in the network monitor data packets and generate alerts based on packet data properties. The packet alerts and the flow data are provided to a machine learning system that detects correlations between the packet-based alerts and the flow data to thereby generate a series of flow-level alerts. These rules are provided to the flow time classifier. Over time, the new packet alerts and flow data are used to provide updated rules generated by the machine learning system.

Abstract translation: 检测互联网协议（IP）流中的异常的系统使用一组机器学习（ML）规则，可以在IP流级别实时应用。 通信网络具有大量可配备流量监控功能的路由器。 集流器在通信网络中收集来自路由器的流数据，并将其提供给流分类器。 同时，网络中有限数量的位置监视数据包，并根据数据包数据属性生成警报。 分组警报和流数据被提供给机器学习系统，其检测基于分组的警报和流数据之间的相关性，从而生成一系列流级别警报。 这些规则提供给流时间分类器。 随着时间的推移，新的数据包警报和流数据用于提供机器学习系统生成的更新规则。

公开(公告)号：US08064359B2

公开(公告)日：2011-11-22

申请号：US12343007

申请日：2008-12-23

Applicant: Nicholas Duffield ,  Lee M. Breslau ,  Cheng Ee ,  Alexandre Gerber ,  Carsten Lund ,  Subhabrata Sen

Inventor： Nicholas Duffield ,  Lee M. Breslau ,  Cheng Ee ,  Alexandre Gerber ,  Carsten Lund ,  Subhabrata Sen

IPC: H04L12/26

CPC classification number: H04L43/026 ,  H04L43/024 ,  Y02D50/30

Abstract: Disclosed herein are systems, computer-implemented methods, and computer-readable media for sampling network traffic. The method includes receiving a desired quantity of flow record to sample, receiving a plurality of network flow record each summarizing a network flow of packets, calculating a hash for each flow record of based on one or more invariant part of a respective flow, generating a quasi-random number from the calculated hash for each respective flow record, generating a priority from the calculated hash for each respective flow record, and sampling exactly the desired quantity of flow records, selecting flow records having a highest priority first. In one aspect, the method further partitions the plurality of flow records into groups based on flow origin and destination, generates an individual priority for each partitioned group, and separately samples exactly the desired quantity of flow records from each partitioned group, selecting flows having a highest individual priority first.

Abstract translation: 本文公开了系统，计算机实现的方法和用于对网络业务进行采样的计算机可读介质。 该方法包括接收所需数量的流记录到采样中，接收多个网络流记录，每个汇总分组的网络流，基于相应流的一个或多个不变部分计算每个流记录的散列， 从每个相应流记录的计算散列中产生准随机数，从每个相应流记录的计算散列生成优先级，并精确地采样所需数量的流记录，首先选择具有最高优先级的流记录。 在一个方面，该方法还基于流源和目的地进一步将多个流记录划分为组，为每个分区组生成一个单独的优先级，并且从每个分区组中分别精确地采集所需数量的流记录，选择具有 最高个人优先。

公开(公告)号：US07990982B2

公开(公告)日：2011-08-02

申请号：US12335074

申请日：2008-12-15

Applicant: Nicholas Duffield ,  Carsten Lund ,  Mikkel Thorup ,  Edith Cohen

Inventor： Nicholas Duffield ,  Carsten Lund ,  Mikkel Thorup ,  Edith Cohen

IPC: H04L12/28 ,  H04L12/56

CPC classification number: H04L43/16 ,  H04L41/0681 ,  H04L41/12 ,  H04L43/02

Abstract: Methods and apparatus to bound network traffic estimation error for multistage measurement sampling and aggregation are disclosed. An example method disclosed herein comprises determining a hierarchical sampling topology representative of multiple data sampling and aggregation stages, the hierarchical sampling topology comprising a plurality of nodes connected by a plurality of edges, each node corresponding to at least one of a data source and a data aggregation operation, and each edge corresponding to a data sampling operation characterized by a generalized sampling threshold, selecting a first generalized sampling threshold from a set of generalized sampling thresholds associated with a respective set of edges originating at a respective set of descendent nodes of a target node undergoing network traffic estimation, and transforming a measured sample of network traffic into a confidence interval for a network traffic estimate associated with the target node using the first generalized sampling threshold and an error parameter.

Abstract translation: 公开了多级测量采样和聚合的绑定网络流量估计误差的方法和装置。 本文公开的示例性方法包括确定表示多个数据采样和聚合阶段的分层采样拓扑，所述分层采样拓扑包括由多个边缘连接的多个节点，每个节点对应于数据源和数据中的至少一个 并且每个边缘对应于由广义采样阈值表征的数据采样操作，从与源于目标的相应的一组后代节点的相应的一组边缘相关联的一组广义采样阈值中选择第一广义采样阈值 节点进行网络流量估计，并且使用第一广义采样阈值和误差参数将网络流量的测量样本变换为与目标节点相关联的网络流量估计的置信区间。

公开(公告)号：US07924739B2

公开(公告)日：2011-04-12

申请号：US12317420

申请日：2008-12-22

Applicant: Subhabrata Sen ,  Lee Breslau ,  Nicholas Duffield ,  Yu Gu

Inventor： Subhabrata Sen ,  Lee Breslau ,  Nicholas Duffield ,  Yu Gu

IPC: H04J3/14 ,  H04L12/26 ,  G06F11/30

CPC classification number: H04L43/0835 ,  H04L41/0213 ,  H04L41/142 ,  H04L41/5009 ,  H04L43/026 ,  H04L43/103 ,  Y02D50/30

Abstract: A packet loss estimation technique is disclosed that utilizes the sampled flow level statistics that are routinely collected in operational networks, thereby obviating the need for any new router features or measurement infrastructure. The technique is specifically designed to handle the challenges of sampled flow-level aggregation such as information loss resulting from packet sampling, and generally comprises: receiving a first record of sampled packets for a flow from a first network element; receiving a second record of sampled packets for the flow from a second network element communicating with the first network element; correlating sampled packets from the flow at the first network element and the second network element to a measurement interval; and estimating the packet loss using a count of the sampled packets correlated to the measurement interval.

Abstract translation: 公开了一种利用在操作网络中常规收集的采样流量统计信息的分组丢失估计技术，从而避免了对任何新的路由器特征或测量基础设施的需要。 该技术专门设计用于处理采样流级聚合的挑战，例如由分组采样导致的信息丢失，并且通常包括：从第一网络元件接收流的第一采样分组记录; 从与第一网络元件通信的第二网络元件接收用于流的采样分组的第二记录; 将来自第一网元和第二网元的流的采样分组相关联到测量间隔; 以及使用与测量间隔相关联的采样分组的计数来估计分组丢失。

公开(公告)号：US07898976B2

公开(公告)日：2011-03-01

申请号：US12236369

申请日：2008-09-23

Applicant: Nicholas Duffield ,  Carsten Lund ,  Subhabrata Sen ,  Yin Zhang ,  Sumeet Singh

Inventor： Nicholas Duffield ,  Carsten Lund ,  Subhabrata Sen ,  Yin Zhang ,  Sumeet Singh

IPC: G06F11/30 ,  G06F12/00

CPC classification number: H04L63/1425 ,  H04L29/12801 ,  H04L61/6004 ,  H04L63/1441 ,  H04L63/1458 ,  Y10S707/99945 ,  Y10S707/99948

Abstract: An efficient streaming method and apparatus for detecting hierarchical heavy hitters from massive data streams is disclosed. In one embodiment, the method enables near real time detection of anomaly behavior in networks.

Abstract translation: 公开了一种用于从海量数据流检测分层重击打者的有效的流传输方法和装置。 在一个实施例中，该方法能够近似实时地检测网络中的异常行为。

公开(公告)号：US20100161791A1

公开(公告)日：2010-06-24

申请号：US12342957

申请日：2008-12-23

Applicant: Nicholas Duffield ,  Lee M. Breslau ,  Cheng Ee ,  Alexandre Gerber ,  Carsten Lund ,  Subhabrata Sen

Inventor： Nicholas Duffield ,  Lee M. Breslau ,  Cheng Ee ,  Alexandre Gerber ,  Carsten Lund ,  Subhabrata Sen

IPC: G06F15/173

CPC classification number: H04L43/04 ,  H04L43/022 ,  H04L43/026 ,  H04L43/062

Abstract: Disclosed herein are systems, computer-implemented methods, and computer-readable media for sampling network traffic. The method includes receiving a plurality of flow records, calculating a hash for each flow record based on one or more invariant part of a respective flow, generating a quasi-random number from the calculated hash for each respective flow record, and sampling flow records having a quasi-random number below a probability P. Invariant parts of flow records include destination IP address, source IP address, TCP/UDP port numbers, TCP flags, and network protocol. A plurality of routers can uniformly calculate hashes for flow records. Each router in a plurality of routers can generate a same quasi-random number for each respective flow record and uses different values for probability P. The probability P can depend on a flow size. The method can divide the quasi-random number by a maximum possible hash value.

Abstract translation: 本文公开了系统，计算机实现的方法和用于对网络业务进行采样的计算机可读介质。 该方法包括：接收多个流记录，基于相应流的一个或多个不变部分计算每个流记录的散列，从针对每个相应流记录的计算出的散列生成准随机数，以及对具有 低于概率P的准随机数。流记录的不变部分包括目的地IP地址，源IP地址，TCP / UDP端口号，TCP标志和网络协议。 多个路由器可以统一计算流记录的哈希值。 多个路由器中的每个路由器可以为每个相应的流记录生成相同的准随机数，并对概率P使用不同的值。概率P可以取决于流量大小。 该方法可以将准随机数除以最大可能的哈希值。

公开(公告)号：US20090303901A1

公开(公告)日：2009-12-10

申请号：US12136725

申请日：2008-06-10

Applicant: Nicholas Duffield ,  Edith Cohen ,  Haim Kaplan ,  Carsten Lund ,  Mikkel Thorup

Inventor： Nicholas Duffield ,  Edith Cohen ,  Haim Kaplan ,  Carsten Lund ,  Mikkel Thorup

IPC: H04L12/26

CPC classification number: H04L43/024

Abstract: The invention relates to streaming algorithms useful for obtaining summaries over unaggregated packet streams and for providing unbiased estimators for characteristics, such as, the amount of traffic that belongs to a specified subpopulation of flows. Packets are sampled from a packet stream and aggregated into flows and counted by implementation of Adaptive Sample-and-Hold (ASH) or Adaptive NetFlow (ANF), adjusting the sampling rate based on a quantity of flows to obtain a sketch having a predetermined size, the sampling rate being adjusted in steps; and transferring the count of aggregated packets from SRAM to DRAM and initializing the count in SRAM following adjustment of the sampling rate.

Abstract translation: 本发明涉及用于在未分组的分组流上获得摘要的用于提供用于特征的无偏估计器的流式传输算法，例如属于指定的流量子群的业务量。 分组从分组流中采样并聚合成流，并通过实施自适应采样保持（ASH）或自适应净流（ANF）进行计数，根据流量调整采样率，以获得具有预定尺寸的草图 采样率逐步调整; 并将汇总数据包从SRAM传输到DRAM，并在采样率调整后初始化SRAM中的计数。

公开(公告)号：US20090303879A1

公开(公告)日：2009-12-10

申请号：US12136705

申请日：2008-06-10

Applicant: Nicholas Duffield ,  Edith Cohen ,  Haim Kaplan ,  Carsten Lund ,  Mikkel Thorup

Inventor： Nicholas Duffield ,  Edith Cohen ,  Haim Kaplan ,  Carsten Lund ,  Mikkel Thorup

IPC: H04L12/56

CPC classification number: H04L47/10 ,  H04L43/024 ,  H04L43/026 ,  H04L43/045 ,  H04L47/22 ,  H04L47/41 ,  Y02D50/30

Abstract: The invention relates to streaming algorithms useful for obtaining summaries over unaggregated packet streams and for providing unbiased estimators for characteristics, such as, the amount of traffic that belongs to a specified subpopulation of flows. Packets are sampled from a packet stream and aggregated into flows and counted by implementation of: (a) Adaptive Sampled NetFlow (ANF), and adjusted weight (AANF) of a flow (f) is calculated as follows: AANF(f)=i(f)/p′; i(f) being the number of packets counted for a flow f, and p′ being the sampling rate at end of a measurement period; or (b) Adaptive Sample-and-Hold (ASH), and adjusted weight (AASH) of a flow (f) is calculated as follows: AASH(f)=i(f)+(1−p′)/p′; i(f) being the number of packets counted for a flow f, and p′ being the sampling rate at end of a measurement period.

Abstract translation: 本发明涉及用于在未分组的分组流上获得摘要的用于提供用于特征的无偏估计器的流式传输算法，例如属于指定的流量子群的业务量。 分组从分组流中采样并聚合成流，并通过实现计算：（a）自适应采样NetFlow（ANF）和流（f）的调整权重（AANF）计算如下：AANF（f）= i （f）/ p'; i（f）是流f计数的分组数，p'是测量周期结束时的采样率; 或（b）自适应采样保持（ASH）和流（f）的调整权重（AASH）如下计算：AASH（f）= i（f）+（1-p'）/ p' ; i（f）是流f计数的分组数，p'是测量周期结束时的采样率。

公开(公告)号：US07587761B2

公开(公告)日：2009-09-08

申请号：US11216972

申请日：2005-08-31

Applicant: Nicholas Duffield ,  Weibo Gong ,  Don Towsley ,  Changchun Zou

Inventor： Nicholas Duffield ,  Weibo Gong ,  Don Towsley ,  Changchun Zou

IPC: G06F11/00 ,  G06F15/16

CPC classification number: H04L63/1408 ,  H04L63/1441 ,  H04L2463/141

Abstract: An apparatus for optimizing a filter based on detected attacks on a data network includes an estimation means and an optimization means. The estimation means operates when a detector detects an attack and the detector transmits an inaccurate attack severity. The estimation means determines an accurate attack severity. The optimization means adjusts a parameter and the parameter is an input to a filter.

Abstract translation: 基于检测到的对数据网络的攻击来优化过滤器的装置包括估计装置和优化装置。 当检测器检测到攻击并且检测器发送不准确的攻击严重性时，估计装置进行操作。 估计装置确定准确的攻击严重性。 优化方法调整参数，参数是过滤器的输入。