公开(公告)号：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的整数，该固定集合由 网络; 并且基于所构建的向量，估计所集合的所有节点已经接收到多少接收到的数据分组，或者估计接收到的数据分组的多少流具有已经通过所有节点的数据分组 组。 所述构造包括响应于接收到数据分组的所述节点之一更新所述节点之一的向量的分量。 该更新包括通过对由该节点之一接收到的数据分组的属性进行哈希来选择用于更新的分量。

公开(公告)号：US20100299287A1

公开(公告)日：2010-11-25

申请号：US12453815

申请日：2009-05-22

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

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

IPC分类号： G06F15/18 ,  G06F17/10 ,  G06F11/00 ,  G06F17/14 ,  G06N5/02

CPC分类号： H04L41/147 ,  H04L41/06 ,  H04L41/142 ,  H04L41/145 ,  H04W24/08

摘要： In one embodiment, a statistical model is generated based on observed data, the observed data being associated with a network device, online parameter fitting is performed on parameters of the statistical model, and for each newly observed data value, a forecast value is generated based on the statistical model, the forecast value being a prediction of a next observed data value, a forecasting error is generated based on the forecast value and the newly observed data value, and whether the data of the network stream is abnormal is determined based on a log likelihood ratio test of the forecasting errors and a threshold value.

摘要翻译： 在一个实施例中，基于观察数据生成统计模型，观察到的数据与网络设备相关联，对统计模型的参数进行在线参数拟合，并且对于每个新观察的数据值，基于 在统计模型中，预测值是对下一观察数据值的预测，基于预测值和新观测数据值生成预测误差，以及基于网络流的网络流的数据是否异常来确定 预测误差的对数似然比检验和阈值。

公开(公告)号：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.

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

公开(公告)号：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.

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

公开(公告)号：US08400933B2

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

申请号：US12110380

申请日：2008-04-28

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

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

IPC分类号： H04J1/16

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的整数，该固定集合由 网络; 并且基于所构建的向量，估计所集合的所有节点已经接收到多少接收到的数据分组，或者估计接收到的数据分组的多少流具有已经通过所有节点的数据分组 组。 所述构造包括响应于接收到数据分组的所述节点之一更新所述节点之一的向量的分量。 该更新包括通过对由该节点之一接收到的数据分组的属性进行哈希来选择用于更新的分量。

公开(公告)号：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.

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

公开(公告)号：US20090006607A1

公开(公告)日：2009-01-01

申请号：US11770430

申请日：2007-06-28

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

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

IPC分类号： G06F15/173 ,  G06F17/30

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 <= i <= D，包括各自具有K个桶的独立于Mi的哈希表，其中每个桶具有相关联的业务量。 每个密钥对应于每个散列数组i的每个Mi独立哈希表的单个桶。 数据网络的密钥分为D个字。 当一个密钥接收到流量时，更新与密钥对应的每个桶的流量总和。 然后可以使用散列数组来识别具有大于阈值的流量总和的独立散列表的高流量桶。 高流量桶可用于检测数据网络的重要流量模式。

公开(公告)号：US20070091937A1

公开(公告)日：2007-04-26

申请号：US11256122

申请日：2005-10-21

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

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

IPC分类号： H04J3/06

CPC分类号： H04L41/00 ,  H04L43/0852

摘要： There is provided a system and method for estimating network tomography. More specifically, there is provided a computer system configured to measure the transmission delay along a path from a source endpoint of a computer network to a plurality of destination endpoints of the computer network, wherein the path includes at least two data links and wherein at least one of the data links is shared by the plurality of destination endpoints for transmissions from the source endpoint, to calculate a characteristic function of the measured transmission delay, and to calculate a performance parameter of one of the data links based on the characteristic function.

摘要翻译： 提供了一种用于估计网络层析成像的系统和方法。 更具体地，提供了一种被配置为测量沿着从计算机网络的源端点到计算机网络的多个目的地端点的路径的传输延迟的计算机系统，其中该路径包括至少两个数据链路，并且其中至少 数据链接中的一个由多个目的地端点共享用于来自源端点的传输，以计算所测量的传输延迟的特征函数，并且基于特征函数来计算数据链路之一的性能参数。