CN113297430B - High-performance arbitrary partial key measurement method and system based on Sketch - Google Patents

Abstract

The invention relates to a Sketch-based high-performance arbitrary part key measurement method and system. The method consists of: extracting the full key and its size from each packet and hash mapping it into one bucket of each array in the sketch; updating each mapped bucket with the full key, and based on random The variance minimization technique determines the estimated size of the full key; builds a lookup table containing all full keys and their estimated size based on the sketch in the data plane; when querying partial keys, aggregates the full keys corresponding to each partial key in the control plane collection to get the estimated size of the partial keys. The invention achieves high accuracy on any part of the key measurement task, can achieve high-speed operation in a small memory space, and at the same time the measured part of the key number has no obvious impact on the system performance; by increasing the hardware parallelism and eliminating With circular dependency, the present invention can be implemented on both software platform and hardware platform with excellent performance.

Description

High performance arbitrary partial key measurement method and system based on Sketch

technical field

The invention relates to the field of arbitrary partial key measurement in network measurement, in particular to a method for implementing high-precision measurement of arbitrary partial keys on a software and hardware platform by utilizing a probabilistic data structure named CocoSketch (Cornucopia Sketch, wishful sketch). system.

Background technique

Currently, network monitoring and measurement have become the basis for various network management tasks, such as traffic engineering, load balancing, traffic scheduling, and anomaly detection. These tasks often require timely and accurate estimation of network traffic metrics. In this regard, sketch-based algorithms are able to estimate these metrics with high accuracy in large networks using few resources. Usually, in the same network, different network measurement tasks need to obtain different statistics based on different flow keys. For example, host-level traffic engineering requires the use of SrcIP as the flow key for tracking large flows, while traffic scheduling requires quintuple as the flow key. Furthermore, in security detection and diagnosis tasks, we need to exhaustively track all possible flow keys, including quintuple, SrcIP, DstIP, and their arbitrary prefixes, to locate abnormal flows. But existing sketch-based designs usually focus on estimating statistics defined on a single stream key, and maintaining a sketch for each stream key is usually not feasible due to resource constraints. Therefore, a sketch algorithm that can support multi-key measurement is urgently needed to solve the query problem of arbitrary partial keys.

In order to solve this problem, some attempts have been made so far. R-HHH (Randomized Hierarchical Heavy Hitters, see "Ran Ben-Basat, Gil Einziger, Roy Friedman, Marcelo Caggiani Luizelli, and Erez Waisbard. Constant time updates inhierarchical heavy hitters. In SIGCOMM 2017. ACM, 2017.") is mainly used for finding A collection of large streams that share some IP prefix, which is a special case of arbitrary partial key queries. It maintains a sketch for each flow key (IP prefix), and randomly selects a sketch to update based on the sampling technique when inserting, thereby reducing the sketch update operation of each packet. However, this method only supports IP prefixes as partial keys, and is not suitable for hardware platforms due to excessive memory usage. USS (Unbiased SpaceSaving, see "Daniel Ting.Data sketches fordisaggregated subset sum and frequent item estimation.In SIGMOD 2018.ACM,2018.") is based on the subset sum estimation theory to solve the problem of arbitrary partial key query, which holds that any A specific partial key can be represented by a specific set of full keys. USS applies variance minimization techniques to SpaceSaving to solve the subset sum estimation problem, enabling querying of arbitrary partial keys. However, since each update of USS needs to be based on all recorded flow information, it cannot achieve high resource efficiency and can only run on a software platform.

SUMMARY OF THE INVENTION

In order to overcome the shortcomings of the existing arbitrary part key query algorithm with low precision, slow processing speed, excessive resource occupation and poor platform compatibility, the present invention proposes a high-performance arbitrary part key measurement system based on CocoSketch, which can High-accuracy arbitrary-part key measurement tasks can be realized with fast processing speed on resource-limited hardware and software platforms.

The technical scheme adopted by the present invention to solve its technical problems is:

A high-performance arbitrary partial key measurement method based on Sketch, including the following steps:

Extract the full key and its size from each packet and hash it into one bucket per array in the data plane's sketch;

Update each mapped bucket with the full key and determine the estimated size of the full key based on random variance minimization techniques;

Build a lookup table with all the full keys and their estimated sizes based on the data plane sketch;

When querying partial keys, aggregate the set of full keys corresponding to each partial key in the control plane to get the estimated size of the partial keys.

Further, the sketch consists of d arrays, each array contains l <key, value> pairs, each pair is called a bucket, and records a full key k _F and its estimated value; let B _i [ j].K and B _i [j].V are the key value of the j-th bucket in the i-th array and its estimated value, 1≤i≤d, 1≤j≤l; the d arrays are respectively associated with d are associated with two independent hash functions (h ₁ (.),...,h _d (.)).

Further, in the software version algorithm, the full key is used to update each mapped bucket, and the estimated size of the full key is determined based on the random variance minimization technique, including:

When inserting packets, represent each incoming packet as a pair (e, w), where e is the full key and w is its size; for packet (e, w), based on the hash index h ₁ (e),...,h _d (e), there are d possible buckets in d arrays that will be updated, and the bucket to be updated is selected according to random variance minimization, there are two cases:

(1) If the full key e is recorded in any one of the d buckets, increase the size of the bucket by w;

(2) Otherwise, update the bucket with the smallest storage value in a random manner.

Further, updating the bucket with the smallest value in a random manner includes:

用e替换B_k[h_k(e)].K；Assuming the bucket with the smallest value is in the k ^th array, to update that bucket, first increase B _k [h _k (e)].V by w, then, with probability

Replace B _k [h _k (e)].K with e;

If multiple buckets hold the same minimum value, a bucket is randomly selected to update.

Further, the estimated value of the full key is queried in the following way:

For the full key e to be queried, based on the hash indexes h ₁ (e),...,h _d (e), find d corresponding buckets in d arrays;

If the k ^th array corresponds to the full key B _k [h _k (e)].K=e stored in the bucket, then return B _k [h _k (e)].V as the estimated value of the full key e; otherwise, then Returns 0.

Further, for the hardware version algorithm, the full key is used to update each mapped bucket, and the estimated size of the full key is determined based on the random variance minimization technique, including:

Split each bucket array into independent estimates and full key arrays, with updates to each array run in parallel or in a pipelined fashion to increase hardware parallelism and improve throughput;

For each packet (e,w), each array will be updated independently through the following two steps:

(1) Increase the B _i [ _hi (e)].V of the mapped bucket by w;

用e替换B_i[h_i(e)].K。(2) with probability

Replace B _i [h _i (e)].K with e.

Further, if the same full key appears in multiple arrays, the average estimated size in the different arrays is taken as its final estimated size.

A Sketch-based high-performance arbitrary partial key measurement system using the above method, comprising:

Data plane component that extracts the full key and its size from each packet and hash-maps it into one bucket per array in sketch; updates each mapped bucket with the full key, and Determine the estimated size of the full key based on random variance minimization techniques;

The control plane component is used to build a query table containing all full keys and their estimated sizes based on the sketch of the data plane; when querying partial keys, aggregate the set of full keys corresponding to each partial key to obtain the estimated size of the partial keys.

Beneficial effects of the present invention: by using the random variance minimization technology, the present invention achieves high accuracy on any partial key measurement task, and can achieve high-speed operation in a small memory space, while the measured number of partial keys There is no significant impact on system performance; instead, the present invention can be implemented on both software platforms (eg: Open vSwitch and CPU) and hardware platforms (eg: FPGA and programmable ASIC) using techniques that increase hardware parallelism and eliminate circular dependencies. Excellent performance.

Description of drawings

FIG. 1 is the overall system architecture of the present invention.

Figure 2 is an illustration of a random variance minimization technique.

Figure 3 is an illustration of a technique for increasing hardware parallelism.

Figure 4 is an illustration of a circular dependency elimination technique.

Figure 5 is an example of data plane software version algorithm insertion.

Figure 6 is an example of data plane hardware version algorithm insertion.

Figure 7 is an example of a control plane arbitrary part key query.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be described in further detail below with reference to the examples in the accompanying drawings. It should be understood that the specific examples described herein are only used to explain the present invention, but not to limit the present invention.

The main contents of the present invention include: minimizing random variance, increasing hardware parallelism, and eliminating cyclic dependencies.

Technique 1: Random Variance Minimization

Previous theoretical results suggest that variance minimization based on full-key estimates helps achieve arbitrary partial-key queries with high accuracy. For each packet insertion, USS utilizes variance minimization techniques for updates, resulting in high accuracy on arbitrary partial-key query problems. However, its method of minimizing variance needs to use the information of all recorded streams, and the calculation amount of the update operation is too large. Therefore, the present invention designs a random variance minimization technique. For the insertion of each data packet, the method of the present invention minimizes the variance based only on the information of the map stream (selected by the hash map). Figure 2 is an illustration of a random variance minimization technique.

Technique 2: Increase hardware parallelism

Using only technique 1, it is necessary to access all the buckets mapped in the array before updating, and then update one of the buckets based on the random variance minimization technique, which means that the insertion process of the algorithm needs to access the same memory twice. But hardware platforms generally do not allow access to the same memory in different stages of the pipeline, as this could lead to read and write hazards while the pipeline is running. As a result, everything must be done serially in the same stage, which will significantly reduce throughput. Therefore, the present invention improves throughput by increasing hardware parallelism. The present invention decouples the update operations in each array. Specifically, the present invention independently updates one bucket of each array based on a random variance minimization technique. Updates to each array can then be run in parallel or in a pipelined fashion, increasing throughput. Figure 3 is an illustration of a technique for increasing hardware parallelism.

Technique 3: Eliminate circular dependencies

In the stochastic variance minimization operation, it can be found that there is a circular dependency between the update of the stream key and its estimated value. As mentioned above, the same memory cannot be accessed in different stages of the pipeline. Therefore, two consecutive conditional judgments must be made, and the same memory space is accessed twice in one stage. However, Tofino switches do not allow such operations to ensure high wire speed. The present invention finds that the circular dependency in the second technique can be further eliminated. In technique 2, stochastic variance minimization only needs to process one mapped bucket, so the update process of the estimated value and stream key can be operated independently, put into different stages and run the processing in a pipelined fashion. By combining techniques two and three, the present system can achieve higher throughput on hardware platforms and become feasible on P4-based hardware platforms. Figure 4 is an illustration of a circular dependency elimination technique.

Based on the above three technical solutions, the system overview and specific algorithm design solutions of the present invention are as follows:

Fig. 1 is the overall system architecture of the present invention. As shown in Fig. 1, the system consists of two components (or modules) of the data plane and the control plane:

The data plane processes each packet as follows: (1) First, extract the full key _kF and its size from each packet and hash it into one bucket per array in sketch; ( 2) Second, each mapped bucket is updated with the corresponding full key _kF , whose estimated size is determined based on random variance minimization techniques.

The control plane provides a query front-end for arbitrary partial keys: (1) First, based on the sketch on the data plane, build a lookup table containing all full keys and their estimated sizes. (2) Second, aggregate the full key set corresponding to each specific partial key to obtain the estimated size of the partial key.

Among them, "full key" refers to the complete flow key, such as quintuple, SrcIP or DstIP, etc.; "partial key" refers to a subset of the full key, for example, SrcIP and DstIP are both partial keys of quintuple, IP address, etc. Any prefix of is a partial key for that IP address.

For the CocoSketch algorithm of the data plane, the present invention designs a software version and a hardware version. "Technology 2: Increase hardware parallelism" and "Technology 3: Eliminate circular dependencies" of the present invention are both applied to the hardware version. The software version and the hardware version are independent of each other, the software version is applied to the software platform, and the hardware version is applied to the hardware platform.

用e替换B_k[h_k(e)].K。如果多个存储桶存有相同的最小值，则随机选择一个存储桶进行更新。查询时，对于要查询的全键e，基于哈希索引h₁(e)，…，h_d(e)，在d个数组中找到d个对应的存储桶。若k^th数组对应存储桶中存储的全键B_k[h_k(e)].K＝e，则返回B_k[h_k(e)].V作为全键e的估计值；反之，则返回0。The data structure of the software version, namely, sketch, consists of d arrays, each of which contains l <key, value> pairs. Each pair (also called a bucket, ie the "bucket" mentioned earlier) records a full key k _F and its estimated value. Let B _i [j].K and B _i [j].V be the key and its estimated value of the jth bucket (1≤i≤d, 1≤j≤l) in the ith array. The d arrays are each associated with d independent hash functions (h ₁ (.), ..., h _d (.)). When inserting, each incoming packet is represented as a pair (e, w), where e is the full key and w is its size. For packet (e,w), based on the hash indices _h1 (e),...,hd(e), there are _d possible buckets in d arrays to be updated, selected according to random variance minimization The bucket to update. Intuitively, there are two cases: (1) if the full key e is recorded in any of the d buckets, increase the size of that bucket by w; (2) otherwise, update the storage in a "random" fashion The bucket with the smallest value. Suppose the bucket with the smallest value is in the k ^th array. To update the bucket, first increase B _k [h _k (e)].V by w. Then, with probability

Replace B _k [h _k (e)].K with e. If multiple buckets hold the same minimum value, a bucket is randomly selected to update. When querying, for the full key e to be queried, based on the hash indexes h ₁ (e), ..., h _d (e), find d corresponding buckets in d arrays. If the k ^th array corresponds to the full key B _k [h _k (e)].K=e stored in the bucket, then return B _k [h _k (e)].V as the estimated value of the full key e; otherwise, then Returns 0.

用e替换B_i[h_i(e)].K。这样，每个数组的插入逻辑都可以独立分布在整个硬件上，以提高并行性。The main difference between the hardware version and the software version is that the insertion steps for each array are expected to be hardware independent of each other. The reason is that the architecture of network hardware (eg: FPGA) is usually designed in massive parallelism by logic devices, and algorithm design should consider increasing parallelism for better utilization of resources. Specifically, the present invention splits each bucket array in the software version into an independent estimated value array and a full key array. Here, the present invention mainly considers the case of d=1. When d=1, the value of the map storage area is incremented by w regardless of whether the key of the record is e. For each packet (e,w), each array will be updated independently by the following two steps: (1) B _i [h _i (e)].V of the bucket mapped to is incremented by w; (2) ) with probability

Replace B _i [h _i (e)].K with e. This way, the insertion logic for each array can be independently distributed across the hardware to improve parallelism.

In the control plane, the present invention provides a front end to query the size of any partial key. First, build a full key lookup table based on sketch in the data plane, which records each full key and its estimated value. When the size of a partial key needs to be queried, the full key set corresponding to the partial key is aggregated to obtain the required estimated size of the partial key. In hardware versions, the same full key may appear in multiple arrays, taking the average estimated size in the different arrays as its final estimated size.

Figure 5 shows a specific insertion example of the data plane software version algorithm. As shown in Figure 5, let d=2. To insert a packet with full key e ₃ and size 4, the software version first maps it to one bucket in each array. Since e ₃ is not recorded in any of the mapped buckets, try to find the bucket with the smallest estimate and find the smallest estimate in the second mapped bucket. So, first update the estimate to 16, then replace e ₂ of the storage area with e ₃ with probability 4/16. For packets with full key e ₅ and size 1, the software version maps it to one bucket in each array. Of these two buckets, e ₅ was found to be recorded in the first bucket. Therefore, increment the corresponding value by 1 (from 15 to 16).

Figure 6 shows a specific insertion example of the data plane hardware version algorithm. As shown in Figure 6, let d=1. To insert a packet with full key e ₄ and size 4, the hardware version first directly adds 4 to the count value of the bucket to which the hash maps in the estimate value array, and then for the corresponding position in the full key array, starts with (13- 4) The probability of /13 does not perform full key replacement; for a data packet with a full key of e ₁ and a size of 2, the hardware version first directly adds 2 to the count value of the bucket to which the hash is mapped in the estimated value array, and then uses The probability of 2/15 replaces the full key at the corresponding position in the full key array with e ₁ , but since the original full key stored in this position is e ₁ , the effect of replacement and non-replacement is the same.

Figure 7 shows an example of a partial key query performed by the control plane. As shown in Figure 7, assuming that the full key is SrcIP, the partial key to be queried is the first 8-bit prefix of SrcIP. First obtain the measurement results of the full key. Then, aggregate the results based on the first byte of the full key. There are two specific full keys that are prefixed with 19.*, so add up their sizes, i.e. the estimated size of the 19.* prefix is 1041 (520+521). Only one particular full key is prefixed with 56.*, so the estimated size of the 56.* prefix is equal to the size of that full key (856).

The high-performance arbitrary partial key measurement method based on CocoSketch of the present invention can be used to measure any partial key in the network. The operator only needs to pre-set a possible full key range (eg quintuple) before measurement, without specifying a specific measurement flow key. During measurement, according to the requirements of different measurement tasks, a specific measurement flow key (for example: SrcIP or DstIP) is specified on the control plane as a partial key, and the corresponding measurement results can be aggregated. Specifically, for example, in the task of security detection and diagnosis, due to security reasons, we usually cannot determine which flow keys need to be measured in advance. If traditional measurement methods are used, we need to track all possible flow keys in detail, including five Only tuples, SrcIP, DstIP and their arbitrary prefixes can locate the abnormal flow, which will cause a lot of resource consumption and is not feasible in most cases. However, using the measurement method proposed by the present invention only needs to set the whole key as a quintuple in advance, and the size of all partial keys within the quintuple range can be obtained in the control plane, thereby efficiently completing the network measurement task.

Experimental data:

1. Heavy Hitters Detection

Recall: CocoSketch typically has a recall above 95% regardless of the number of partial keys tracked. When measuring 6 flow keys, the accuracy of the CocoSketch of the present invention is 28.4% and 51.6% higher than that of the existing Elastic Sketch and SpaceSaving, respectively.

Accuracy: CocoSketch is typically above 90% accurate, 57% higher than USS.

Average relative error: The average relative error of CocoSketch is usually less than 0.1, which is 3.1 times that of USS. When measuring 6 partial keys, the average relative error of CocoSketch is about 9.3 times that of other algorithms.

2. Heavy Changes detection

Recall: CocoSketch typically has a recall higher than 95% regardless of the number of flow keys. When measuring 6 flow keys, the recall of CocoSketch of the present invention is 78%, 69%, 27% and 87% higher than the existing C-Heap, CM-Heap, Elastic Sketch and Univmon, respectively.

Accuracy: CocoSketch is usually more than 90% accurate. When measuring 6 flow keys, CocoSketch is 69%, 51%, 5% and 81% more accurate than the existing C-Heap, CM-Heap, Elastic Sketch and Univmon, respectively.

3.Hierarchical Heavy Hitters (referred to as HHH) detection

One-dimensional HHH: Under 1MB memory, CocoSketch's F1 Score is higher than 99.5%. The average relative error of CocoSketch is about 1282 times smaller than that of R-HHH.

2D HHH: CocoSketch's F1 Score is higher than 99.5% when the memory is 5MB. The average relative error of CocoSketch is about 32539 times that of R-HHH.

Based on the same inventive concept, another embodiment of the present invention provides an electronic device (computer, server, smart phone, etc.), which includes a memory and a processor, the memory stores a computer program, and the computer program is configured to be The processor is executed, and the computer program includes instructions for performing the steps in the method of the present invention.

Based on the same inventive concept, another embodiment of the present invention provides a computer-readable storage medium (eg, ROM/RAM, magnetic disk, optical disk), where the computer-readable storage medium stores a computer program, and when the computer program is executed by a computer , realize each step of the method of the present invention.

The specific embodiments of the present invention disclosed above are intended to help understand the content of the present invention and implement them accordingly. Those skilled in the art can understand that various substitutions, changes and modifications can be made without departing from the spirit and scope of the present invention. Modifications are possible. The present invention should not be limited to the contents disclosed in the embodiments of this specification, and the protection scope of the present invention shall be subject to the scope defined by the claims.

Claims (7)

1. A high-performance arbitrary partial key measurement method based on Sketch is characterized by comprising the following steps:

extracting a full key and the size thereof from each data packet, and mapping the hash thereof to a bucket of each array in the sketch of the data plane;

updating each mapped bucket using a full key and determining an estimated size of the full key based on a random variance minimization technique;

constructing a lookup table containing all full keys and the estimated sizes thereof based on the sketch of the data plane;

when a partial key is inquired, aggregating a full key set corresponding to each partial key in a control plane to obtain the estimated size of the partial key;

the sketch consists of d arrays, and each array comprises l arrays<key，value>Pairs of numbers, each pair being called a bucket, recording a full key k _F And its estimated value; let B _i [j]K and B _i [j]V is the key value of the jth bucket in the ith array and its estimated value, i is greater than or equal to 1 and less than or equal to d, j is greater than or equal to 1 and less than or equal to l; d arrays and d independent hash functions (h) respectively ₁ (.),…,h _d (.)) to be connected;

in the software version algorithm, the updating each mapped bucket using a full key and determining an estimated size of the full key based on a random variance minimization technique includes:

when inserting a packet, representing each incoming packet as a pair of numbers (e, w), where e is the full key and w is its size; for packet (e, w), index h is based on hash ₁ (e),…,h _d (e) There are d possible buckets to be updated in the d arrays, and the bucket to be updated is selected based on the random variance minimization, in two cases:

(1) if a full key e is recorded in any of the d buckets, increasing the size of the bucket by w;

(2) otherwise, updating the bucket with the minimum storage value in a random mode;

for a hardware version algorithm, the updating each mapped bucket using a full key and determining an estimated size of the full key based on a random variance minimization technique, comprising:

splitting each storage bucket array into an independent estimation value array and a full key array, wherein updating of each array is operated in parallel or in a pipeline mode so as to increase hardware parallelism and improve throughput;

for each packet (e, w), each array will be updated independently by the following two steps:

(1) b of bucket to be mapped to _i [h _i (e)]B increasing w;

(2) by probability

Replacement of B by e _i [h _i (e)].K。

2. The method of claim 1, wherein randomly updating the buckets with the smallest values comprises:

assume the bucket with the smallest value is at k ^th In the array, to update the bucket, first B _k [h _k (e)]V increases w, then with probability

Replacement of B by e _k [h _k (e)].K；

If a plurality of buckets have the same minimum value, one bucket is randomly selected for updating.

3. The method of claim 2, wherein the estimate of the full key is queried in the following manner:

indexing h based on hash for a full key e to be queried ₁ (e),…,h _d (e) D corresponding buckets are found in the d arrays;

if k is ^th Full key B stored in array corresponding storage bucket _k [h _k (e)]If K is e, then return to B _k [h _k (e)]V as an estimate of the full key e; otherwise, 0 is returned.

4. The method of claim 1, wherein if the same full key appears in multiple arrays, the average estimated size in the different arrays is taken as its final estimated size.

5. Sketch-based high-performance arbitrary partial key measurement system using the method of any one of claims 1 to 4, comprising:

the data plane component is used for extracting a full key and the size of the full key from each data packet and mapping the hash of the full key to a bucket of each array in the sketch; updating each mapped bucket using a full key and determining an estimated size of the full key based on a random variance minimization technique;

the control plane component is used for constructing a lookup table containing all full keys and the estimated sizes of the full keys based on the sketch of the data plane; and when the partial keys are inquired, aggregating the full key set corresponding to each partial key to obtain the estimated sizes of the partial keys.

6. An electronic apparatus, comprising a memory and a processor, the memory storing a computer program configured to be executed by the processor, the computer program comprising instructions for performing the method of any of claims 1 to 4.

7.A computer-readable storage medium, characterized in that the computer-readable storage medium stores a computer program which, when executed by a computer, implements the method of any one of claims 1 to 4.

Images