Patent application number | Description | Published |
20090268623 | EFFICIENT PROBABILISTIC COUNTING SCHEME FOR STREAM-EXPRESSION CARDINALITIES - 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. | 10-29-2009 |
20090271509 | PROBABILISTIC AGGREGATION OVER DISTRIBUTED DATA STREAMS - In one embodiment, a method of monitoring a network. The method includes, at each node of a set, constructing a corresponding vector of M components based on a stream of data packets received at the node during a time period, the set including a plurality of nodes of the network, M being greater than 1; and estimating a value of a byte traffic produced by a part of the packets based on the constructed vectors, the part being the packets received by every node of the set. The constructing includes updating a component of the vector corresponding to one of the nodes in response to the one of the nodes receiving a data packet. The updating includes selecting a component of the vector to be updated by hashing a property of the received data packet. | 10-29-2009 |
20090296594 | ESTIMATING CARDINALITY DISTRIBUTIONS IN NETWORK TRAFFIC - 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. | 12-03-2009 |
20100292995 | METHOD AND APPARATUS FOR INCREMENTAL QUANTILE ESTIMATION - A method and apparatus for incremental quantile estimation is provided. A method for performing incremental quantile estimation using an estimated cumulative distribution function includes receiving a record, identifying an entity with which the received record is associated, determining a record type of the received record based at least in part on the entity with which the received record is associated, updating the estimated cumulative distribution function based on the record type of the received record, and storing the estimated cumulative distribution function. The record type of the received record is indicative of whether the received record is an insertion record, an update record, or a deletion record. The estimated cumulative distribution function may be used to respond to quantile query requests in real-time or near-real-time. | 11-18-2010 |
20100299287 | Monitoring time-varying network streams using state-space models - 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. | 11-25-2010 |
20110010327 | METHOD AND APPARATUS FOR INCREMENTAL TRACKING OF MULTIPLE QUANTILES - 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. | 01-13-2011 |
20110010337 | METHOD AND APPARATUS FOR INCREMENTAL QUANTILE TRACKING OF MULTIPLE RECORD TYPES - 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. | 01-13-2011 |
20110038269 | Estimation method for loss rates in a packetized network - A method is provided, according to which data are collected on downstream packet losses at a single point in a network. From from the collected data, packet loss rates are estimated on at least two subnetworks downstream of the collection point. The respective subnetworks may differ by one or more links. | 02-17-2011 |
20110069632 | TRACKING NETWORK-DATA FLOWS - 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. | 03-24-2011 |
20110239299 | ADAPTIVE DISTINCT COUNTING FOR NETWORK-TRAFFIC MONITORING AND OTHER APPLICATIONS - In one embodiment, a counting method of the invention uses an adaptive sketching-update process to compress an unknown cardinality into a counter value that counts the number of binary ones in a hashed bitmap vector. The sketching-update process is probabilistic in nature and uses bit-flip probabilities that are adaptively decreased as the counter value increases. Parameters of the sketching-update process are selected so that the relative error of cardinality estimates obtained based on the counter values is relatively small and substantially constant over a relatively wide range of cardinalities, e.g., from one to about one million. Due to the latter property, the counting method can advantageously be implemented in the form of embedded software that relies on a relatively small, fixed amount of memory. | 09-29-2011 |
20120084860 | SYSTEM AND METHOD FOR DETECTION OF DOMAIN-FLUX BOTNETS AND THE LIKE - In one embodiment, a method for detecting malicious software agents, such as domain-flux botnets. The method applies a co-clustering algorithm on a domain-name query failure graph, to generate a hierarchical grouping of hosts based on similarities between domain names queried by those hosts, and divides that hierarchical structure into candidate clusters based on percentages of failed queries having at least first- and second-level domain names in common, thereby identifying hosts having correlated queries as possibly being infected with malicious software agents. A linking algorithm is used to correlate the co-clustering results generated at different time periods to differentiate actual domain-flux bots from other domain-name failure anomalies by identifying candidate clusters that persist for relatively long periods of time. Persistent candidate clusters are analyzed to identify which clusters have malicious software agents, based on a freshness metric that characterizes whether the candidate clusters continually generate failed queries having new domain names. | 04-05-2012 |
20130151429 | SYSTEM AND METHOD OF DETERMINING ENTERPRISE SOCIAL NETWORK USAGE - According to an embodiment, a computing system includes at least one computing device including a processor configured to use a logistic regression model to provide an indication of a relationship between a user's position within an enterprise and how the user interacts with other users of an enterprise social network. | 06-13-2013 |
20130262656 | SYSTEM AND METHOD FOR ROOT CAUSE ANALYSIS OF MOBILE NETWORK PERFORMANCE PROBLEMS - A method and system for identifying causes of performance metric changes in a network by selecting, from a pool of network event counters, a plurality of candidate counters relevant to a performance metric; grouping the candidate counters into clusters of similar counters; selecting, from each cluster, one or more representative counters; and fitting the selected representative counters to a model of the performance metric to determine thereby a set of representative counters most relevant to the performance metric. | 10-03-2013 |
20150043346 | CONGESTION DETECTION BASED ON RESOURCE UTILIZATION INFORMATION AND USER QUALITY-OF-EXPERIENCE INDICATORS - A capability is provided for detecting congestion in a communication network. A congestion condition is detected for the network based on resource utilization information associated with the network and a set of user quality-of-experience (QoE) indicators associated with the network. An indication of congestion in the network is detected based on resource utilization information associated with the network and a determination as to whether or not to generate detect a congestion condition for the network is made based on one or more user QoE indicators associated with the network. An indication of congestion in the network is detected based on resource utilization information associated with the network and a determination as to whether or not to generate a congestion alert for the indication of congestion in the network is made based on one or more user QoE indicators associated with the network. | 02-12-2015 |