公开(公告)号：US20090296594A1

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

申请号：US12129883

申请日：2008-05-30

申请人： Jin Cao ,  Aiyou Chen ,  Li Li

发明人： Jin Cao ,  Aiyou Chen ,  Li Li

IPC分类号： G06F11/30

CPC分类号： H04L43/00

摘要： In one embodiment, a method of monitoring a network. The method includes: receiving, from each host of a set of two or more hosts of the network, a corresponding vector of M components constructed based on data packets received at the host during a time period, M being an integer greater than 1; and, based on the constructed vectors, using an expectation-maximization algorithm to estimate a cardinality distribution for the hosts in the set, wherein constructing a vector includes updating a component of the vector of the corresponding host in response to the corresponding host receiving a data packet, the updating including selecting the component for updating by hashing one or more fields of the data packet received by the corresponding host.

摘要翻译： 在一个实施例中，一种监视网络的方法。 该方法包括：从网络的一组两个或多个主机的每个主机接收在一段时间内基于在主机处接收到的数据分组构成的M个分量的相应向量，M是大于1的整数; 并且基于构造的向量，使用期望最大化算法来估计集合中的主机的基数分布，其中构建向量包括响应于相应主机接收到数据来更新对应主机的向量的分量 分组，所述更新包括通过对由相应主机接收的数据分组的一个或多个字段进行哈希来选择用于更新的分量。

公开(公告)号：US08589329B2

公开(公告)日：2013-11-19

申请号：US12546255

申请日：2009-08-24

申请人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Li Li

发明人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Li Li

IPC分类号： G06F17/00 ,  G06F7/00 ,  G06F7/60 ,  G06Q10/00

CPC分类号： G06F17/18

摘要： A capability for incremental tracking of multiples quantiles is provided. A method for performing an incremental quantile update using a data value of a received data record includes determining an initial distribution function, updating the initial distribution function to form a new distribution function based on the received data value, generating an approximation of the new distribution function, and determining new quantile estimates from the approximation of the new distribution function. The initial distribution function includes a plurality of initial quantile estimates and a respective plurality of initial probabilities. The new distribution function includes a plurality of quantile points identifying the respective initial quantile estimates and a respective plurality of new probabilities associated with the initial quantile estimates. The approximation of the new distribution function is generated by connecting pairs of adjacent quantile points using linear approximations of regions between the pairs of adjacent quantile points.

摘要翻译： 提供了增量跟踪多个分位数的能力。 使用接收到的数据记录的数据值来执行增量分位数更新的方法包括确定初始分布函数，基于接收到的数据值更新初始分布函数以形成新的分布函数，生成新分布函数的近似值 ，并根据新分布函数的近似来确定新的分位数估计。 初始分布函数包括多个初始分位数估计和相应的多个初始概率。 新的分布函数包括多个分位点，其分别标识相应的初始分位数估计和与初始分位数估计相关联的相应多个新概率。 通过使用相邻分位点对之间的区域的线性近似来连接相邻分位点对来产生新分布函数的近似。

公开(公告)号：US08134934B2

公开(公告)日：2012-03-13

申请号：US12563476

申请日：2009-09-21

申请人： Aiyou Chen ,  Jin Cao ,  Li Li

发明人： Aiyou Chen ,  Jin Cao ,  Li Li

IPC分类号： H04J3/14

CPC分类号： H04L43/026

摘要： A network-equipment-implemented method and apparatus for tracking durations of flows received at a network node in consecutive intervals utilizes two counting bloom filters in ping-pong operation to reduce memory and processing. Identifiers for flows that exceed a predetermined duration or number of intervals are stored in a long-duration flow-identifier table. Hash functions used within the counting bloom filters and optionally used in the long-duration flow-identifier table are chosen to minimize the probability of false positives in the detection of long-duration flows. In some embodiments, flows are sampled to conserve memory and processing resources at the risk of missing detection of some long-duration flows.

摘要翻译： 用于在连续间隔中跟踪在网络节点处接收的流的持续时间的网络设备实现的方法和装置利用乒乓操作中的两个计数绽放滤波器来减少存储器和处理。 超过预定持续时间或间隔数的流的标识符存储在长时间流标识符表中。 在计数布隆过滤器中使用的哈希函数和可选地用于长持续时间流标识符表中的哈希函数被选择以最小化长时间流检测中的误报的概率。 在一些实施例中，对流进行采样以节省存储器并处理资源，处于某些长期流量缺失检测的风险。

公开(公告)号：US20110010337A1

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

申请号：US12546344

申请日：2009-08-24

申请人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Li Li

发明人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Li Li

IPC分类号： G06F17/30 ,  G06F17/10

CPC分类号： G06F17/18

摘要： A method and apparatus are provided for incrementally tracking quantiles in the presence of multiple record types. A method for performing incremental quantile tracking includes receiving a first data record of a first record type having a first data value, determining whether a second data record of a second record type is received, determining an initial distribution function, updating the initial distribution function to form a new distribution function based on the first data value and whether a second data record is received, generating an approximation of the new distribution function, determining at least one new quantile estimate associated with at least one new probability of the new distribution function using the approximation of the new distribution function, and storing the at least one new quantile estimate and the at least one new probability associated with the at least one new quantile estimate.

摘要翻译： 提供了一种用于在存在多种记录类型的情况下递增跟踪分位数的方法和装置。 一种用于执行增量分位数跟踪的方法包括接收具有第一数据值的第一记录类型的第一数据记录，确定是否接收到第二记录类型的第二数据记录，确定初始分布函数，将初始分布函数更新为 基于第一数据值形成新的分配函数，以及是否接收到第二数据记录，生成新分布函数的近似，使用所述新分布函数确定与新分布函数的至少一个新概率相关联的至少一个新的分位数估计值 并且存储至少一个新的分位数估计和与该至少一个新的分位数估计相关联的至少一个新概率。

公开(公告)号：US08666946B2

公开(公告)日：2014-03-04

申请号：US12546344

申请日：2009-08-24

申请人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Li Li

发明人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Li Li

IPC分类号： G06F17/18 ,  G06F17/30

CPC分类号： G06F17/18

摘要： A method and apparatus are provided for incrementally tracking quantiles in the presence of multiple record types. A method for performing incremental quantile tracking includes receiving a first data record of a first record type and a second data record of a second record type, and updating a quantile probability for a quantile value, based on the first record type of the first data record and the second record type of the second data record, to obtain a new quantile probability for the quantile value.

摘要翻译： 提供了一种用于在存在多种记录类型的情况下递增跟踪分位数的方法和装置。 一种用于执行增量分位数跟踪的方法包括：接收第一记录类型的第一数据记录和第二记录类型的第二数据记录，并且基于第一数据记录的第一记录类型更新分位数值的分位数概率 和第二数据记录的第二记录类型，以获得分位数值的新的分位数概率。

公开(公告)号：US20110010327A1

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

申请号：US12546255

申请日：2009-08-24

申请人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Li Li

发明人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Li Li

IPC分类号： G06N5/02

CPC分类号： G06F17/18

摘要： A method and apparatus for incremental tracking of multiples quantiles is provided. A method for performing an incremental quantile update using a data value of a received data record includes determining an initial distribution function, updating the initial distribution function to form a new distribution function based on the received data value, generating an approximation of the new distribution function, and determining new quantile estimates from the approximation of the new distribution function. The initial distribution function includes a plurality of initial quantile estimates and a respective plurality of initial probabilities. The initial distribution function is updated to form the new distribution function based on the received data value. The new distribution function includes a plurality of quantile points identifying the respective initial quantile estimates and a respective plurality of new probabilities associated with the respective initial quantile estimates. The approximation of the new distribution function is generated by, for each pair of adjacent quantile points in the new distribution function, connecting the adjacent quantile points using a linear approximation of a region between the adjacent quantile points. The new quantile estimates and the new probabilities associated with the new quantile estimates may then be stored.

摘要翻译： 提供了一种用于增量跟踪多个分位数的方法和装置。 使用接收到的数据记录的数据值来执行增量分位数更新的方法包括确定初始分布函数，基于所接收的数据值更新初始分布函数以形成新的分布函数，生成新分布函数的近似值 ，并根据新分布函数的近似来确定新的分位数估计。 初始分布函数包括多个初始分位数估计和相应的多个初始概率。 基于收到的数据值更新初始分配函数以形成新的分布函数。 新的分布函数包括多个分位点，其识别相应的初始分位数估计以及与各自的初始分位数估计相关联的相应的多个新概率。 新分布函数的近似由新分布函数中的每对相邻分位数点产生，使用相邻分位点之间的区域的线性近似来连接相邻的分位数点。 然后可以存储新的分位数估计值和与新分位数估计值相关联的新概率。

公开(公告)号：US08406132B2

公开(公告)日：2013-03-26

申请号：US12129883

申请日：2008-05-30

申请人： Jin Cao ,  Aiyou Chen ,  Li Li

发明人： Jin Cao ,  Aiyou Chen ,  Li Li

IPC分类号： H04J3/14 ,  H04L12/28 ,  H04L12/66

CPC分类号： H04L43/00

摘要： In one embodiment, a method of monitoring a network. The method includes: receiving, from each host of a set of two or more hosts of the network, a corresponding vector of M components constructed based on data packets received at the host during a time period, M being an integer greater than 1; and, based on the constructed vectors, using an expectation-maximization algorithm to estimate a cardinality distribution for the hosts in the set, wherein constructing a vector includes updating a component of the vector of the corresponding host in response to the corresponding host receiving a data packet, the updating including selecting the component for updating by hashing one or more fields of the data packet received by the corresponding host.

摘要翻译： 在一个实施例中，一种监视网络的方法。 该方法包括：从网络的一组两个或多个主机的每个主机接收在一段时间内基于在主机处接收的数据分组构成的M个分量的相应向量，M是大于1的整数; 并且基于构造的向量，使用期望最大化算法来估计集合中的主机的基数分布，其中构建向量包括响应于相应主机接收到数据来更新对应主机的向量的分量 分组，所述更新包括通过对由相应主机接收的数据分组的一个或多个字段进行哈希来选择用于更新的分量。

公开(公告)号：US20110069632A1

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

申请号：US12563476

申请日：2009-09-21

申请人： Aiyou Chen ,  Jin Cao ,  Li Li

发明人： Aiyou Chen ,  Jin Cao ,  Li Li

IPC分类号： H04L12/26

CPC分类号： H04L43/026

摘要： A network-equipment-implemented method and apparatus for tracking durations of flows received at a network node in consecutive intervals utilizes two counting bloom filters in ping-pong operation to reduce memory and processing. Identifiers for flows that exceed a predetermined duration or number of intervals are stored in a long-duration flow-identifier table. Hash functions used within the counting bloom filters and optionally used in the long-duration flow-identifier table are chosen to minimize the probability of false positives in the detection of long-duration flows. In some embodiments, flows are sampled to conserve memory and processing resources at the risk of missing detection of some long-duration flows.

摘要翻译： 用于在连续间隔中跟踪在网络节点处接收的流的持续时间的网络设备实现的方法和装置利用乒乓操作中的两个计数绽放滤波器来减少存储器和处理。 超过预定持续时间或间隔数的流的标识符存储在长时间流标识符表中。 在计数布隆过滤器中使用的哈希函数和可选地用于长持续时间流标识符表中的哈希函数被选择以最小化长时间流检测中的误报的概率。 在一些实施例中，对流进行采样以节省存储器并处理资源，处于某些长期流量缺失检测的风险。

公开(公告)号：US07779143B2

公开(公告)日：2010-08-17

申请号：US11770430

申请日：2007-06-28

申请人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Pak-Ching Lee

发明人： Tian Bu ,  Jin Cao ,  Aiyou Chen ,  Pak-Ching Lee

IPC分类号： G06F15/16

CPC分类号： H04L43/028 ,  H04L43/0876 ,  H04L45/745 ,  H04L49/552 ,  H04L63/1408 ,  H04L63/1458

摘要： Methods and apparatuses are provided for detecting traffic patterns in a data network. A sequential hashing scheme can be utilized that has D hash arrays. Each hash array i, wherein 1≦i≦D, includes Mi independent hash tables each having K buckets, with each of the buckets having an associated traffic total. Each of the keys corresponds with a single bucket of each of the Mi independent hash tables of each hash array i. The keys of the data network are partitioned into D words. As traffic is received for a key, a traffic total of each bucket that corresponds with a key is updated. The hash arrays can then be utilized to identify high traffic buckets of the independent hash tables having a traffic total greater than a threshold value. The high traffic buckets can be used to detect significant traffic patterns of the data network.

摘要翻译： 提供了用于检测数据网络中的流量模式的方法和装置。 可以使用具有D个散列数组的顺序散列方案。 每个散列数组i，其中1＆nlE; i＆nlE; D包括每个具有K个桶的独立的独立哈希表，其中每个桶具有相关联的业务量。 每个密钥对应于每个散列数组i的每个Mi独立哈希表的单个桶。 数据网络的密钥分为D个字。 当一个密钥接收到流量时，更新与密钥对应的每个桶的流量总和。 然后可以使用散列数组来识别具有大于阈值的流量总和的独立散列表的高流量桶。 高流量桶可用于检测数据网络的重要流量模式。

公开(公告)号：US20090268623A1

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

申请号：US12110380

申请日：2008-04-28

申请人： Tian Bu ,  Jin Cao ,  Aiyou Chen

发明人： Tian Bu ,  Jin Cao ,  Aiyou Chen

IPC分类号： G06F11/00

CPC分类号： H04L41/142 ,  H04L43/026

摘要： In one embodiment, a method of monitoring a network. The method includes, at each node of a fixed set, constructing a corresponding vector of M components based on data packets received at the node during a time period, M being an integer greater than 1, the fixed set being formed of some nodes of the network; and, based on the constructed vectors, estimating how many of the received data packets have been received by all of the nodes of the set or estimating how many flows of the received data packets have data packets that have passed through all of the nodes of the set. The constructing includes updating a component of the vector of one of the nodes in response to the one of the nodes receiving a data packet. The updating includes selecting the component for updating by hashing a property of the data packet received by the one of the nodes.

摘要翻译： 在一个实施例中，一种监视网络的方法。 该方法包括：在固定集合的每个节点处，基于在一段时间内在节点处接收到的数据分组来构造M个分量的相应向量，M是大于1的整数，该固定集合由 网络; 并且基于所构建的向量，估计所集合的所有节点已经接收到多少接收到的数据分组，或者估计接收到的数据分组的多少流具有已经通过所有节点的数据分组 组。 所述构造包括响应于接收到数据分组的所述节点之一更新所述节点之一的向量的分量。 该更新包括通过对由该节点之一接收到的数据分组的属性进行哈希来选择用于更新的分量。