At&t Intellectual Property I, L.p.

At+t Corp.

Mikkel Thorup

Nicholas G Duffield

Carsten Lund

Edith Cohen

Haim Kaplan

Mihai Patrascu

Mauricio Guilherme De Carvalho Resende

Luciana Salete Buriol

Diogo Vieira Andrade

Bernard Fortz

Oliver Spatscheck

Alexandre Gerber

Frederick True

Adam Hersh

Philip Bille

Methods, systems, and products describe a robust solution for the dictionary problem of data structures. A hash function based on tabulation is twisted to utilize an additional xoring operation and a shift. This twisted tabulation offers strong robustness guarantees over a set of queries in both linear probing and chaining.

Methods, systems, and product for twisted tabulation

Methods, systems, and product for hashing using twisted tabulation

Methods, systems and products for hashing using twisted tabulation

Improved matching of a regular expression in an input string. A system first identifies a number of substrings (k) in a regular expression of length (m). The system receives a stream of start states for each of the substrings generated according to a regular expression matching process and receives a stream of end occurrences generated according to a multi-string matching process. The system identifies all instances where an end occurrence of a particular substring matches a positive start state of the particular substring, and enters the instances as positive substring accept states in the regular expression matching process on the input string. In one aspect, the system is much more efficient when (k) is much less than (m). The system can match the regular expression based on a bit offset between the first and second stream.

System and method for regular expression matching with multi-strings and intervals

A current key is received at a current arrival time at a computer. An index in an array corresponding to the current key is determined using a hash function. A previous key and a previous arrival time are retrieved from the array at the index. The array is transformed by replacing the previous key and the previous arrival time with the current key and the current arrival time in the array at the index. The previous key and the previous arrival time are inserted into a nearest eligible sequential index in the array.

Time-outs with time-reversed linear probing

A method for producing a summary A of data points in an unaggregated data stream wherein the data points are in the form of weighted keys (a, w) where a is a key and w is a weight, and the summary is a sample of k keys a with adjusted weights w. A first reservoir L includes keys having adjusted weights which are additions of weights of individual data points of included keys and a second reservoir T includes keys having adjusted weights which are each equal to a threshold value &#x3c4; whose value is adjusted based upon tests of new data points arriving in the data stream. The summary combines the keys and adjusted weights of the first reservoir L with the keys and adjusted weights of the second reservoir T to form the sample representing the data stream upon which further analysis may be performed. The method proceeds by first merging new data points in the stream into the reservoir L until the reservoir contains k different keys and thereafter applying a series of tests to new arriving data points to determine what keys and weights are to be added to or removed the reservoirs L and T to provide a summary with a variance that approaches the minimum possible for aggregated data sets. The method is composable, can be applied to high speed data streams such as those found on the Internet, and can be implemented efficiently.

Method for summarizing data in unaggregated data streams

A method and apparatus for composite link assignment are provided such that network capacity is sufficient to handle all the traffic (e.g., load) while an objective function, e.g., the total cost of the capacity is minimized. The present method receives a plurality of weights for a plurality of arcs and a load for the network. An objective function is selected for minimization, where the present method then determines the composite link assignment to handle the load while the objective function is minimized. In one embodiment, the composite link assignment comprises a plurality of different link types for the plurality of arcs.

Method and apparatus for providing composite link assignment in network design

Two regularized estimators that avoid the pathologies associated with variance estimation are disclosed. The regularized variance estimator adds a contribution to estimated variance representing the likely error, and hence ameliorates the pathologies of estimating small variances while at the same time allowing more reliable estimates to be balanced in the convex combination estimator. The bounded variance estimator employs an upper bound to the variance which avoids estimation pathologies when sampling probabilities are very small.

Optimal combination of sampled measurements

The present invention relates to a method of obtaining a generic sample of an input stream. The method is designated as VAROPT. The method comprises receiving an input stream of items arriving one at a time, and maintaining a sample S of items i. The sample S has a capacity for at most k items i. The sample S is filled with k items i. An nitem i is received. It is determined whether the nitem i should be included in sample S. If the nitem i is included in sample S, then a previously included item i is dropped from sample S. The determination is made based on weights of items without distinguishing between previously included items i and the nitem i. The determination is implemented thereby updating weights of items i in sample S. The method is repeated until no more items are received.

Variance-optimal sampling-based estimation of subset sums

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.

Methods and apparatus to bound network traffic estimation error for multistage measurement sampling and aggregation

A method of analyzing data traffic includes receiving a request at a data analysis system to store a string related to header information associated with a data packet. The method also includes applying a hash function to the string, thereby obtaining a 32-bit intermediate, and applying another hash function to the 32-bit intermediate, thereby obtaining a hash number. Further, the method includes storing the string in an array position corresponding to the hash number, when the array position is empty.

System and method for analyzing data traffic

The preferred embodiments of the present invention can include sampling packets transmitted over a network based on the content of the packets. If a packet is sampled, the sampling unit can add one or more fields to the sampled packet that can include a field for a number of bytes contained in the packet, a packet count, a flow count, a sampling type, and the like. The sampled packets can be analyzed to discern desired information from the packets. The additional fields that are added to the sampled packets can be used during the analysis.

Sampling and analyzing packets in a network

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 (NF), and adjusted weight (A) of a flow (f) is calculated as follows: A(f)=i(f)/p'; i(f) being the number of packets counted for a flow f, and p&#x2032; being the sampling rate at end of a measurement period; or (b) Adaptive Sample-and-Hold (SH), and adjusted weight (A) of a flow (f) is calculated as follows: A(f)=i(f)+(1&#x2212;p&#x2032;)/p&#x2032;; i(f) being the number of packets counted for a flow f, and p&#x2032; being the sampling rate at end of a measurement period.

Growing community of inventors

Florence, MA, United States of America

Mikkel Thorup