Shulou(Shulou.com)06/01 Report--

How to carry out MV-Sketch analysis, in view of this problem, this article introduces the corresponding analysis and solutions in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

Network measurement is the most basic means to characterize network behavior, quantify various indicators, fully understand and correctly understand the Internet, and support the development of SDN. Network administrators can grasp the network state through network measurement, and then optimize the network structure, improve network service quality, diagnose network faults and recover in time. Sketch's rapid detection of heavy flow (heavy flow) and heavy changer (sudden change flow) with less memory contributes to the deployment of a large number of SDN cloud data centers.

Now that Sketch is mentioned, let's introduce what Sketch is. Sketch is a compact sub-linear data structure for traffic data statistics. Use Hash algorithm to map to Sketch, compress a large number of network flows to a small part of memory space, do not need to store all network flows, in order to achieve the purpose of saving memory, and obtain traffic statistics through query operations. The reason for using Sketch is that it stores streams with the same hash value in the same bucket, which can greatly reduce storage space while ensuring accuracy.

Next, we will introduce MV-SKetch, which is an efficient, compact and reversible Sketch, which can quickly detect heavy flow in small memory, mainly using MJTRY algorithm (main voting algorithm). Compared with dynamic allocation of streaming storage space, static allocation helps to reduce memory management overhead, and SIMD can be used to accelerate MV-Sketch.

The data structure of MV-Sketch consists of r rows, each row has w buckets, and three elements Vi,j, Ki,j, and Ci,j are recorded in each bucket. Vi,j represents the sum of all streams in this bucket, Ki,j represents the reflow candidate in the current bucket, and Ci,j records the count value of the reflow candidate in the current bucket to determine whether to retain the reflow candidate. As shown in the following figure:

When the packet arrives, MV-Sketch uses r independent hash functions to map the packet to 1-r rows, and the mapped column order j is determined by the hash value hi (x). After hashing to a bucket, the re-flow candidate is updated according to the MJRTY algorithm. When querying, the estimated value is determined according to whether the candidates of the new stream and the reflow in the bucket are consistent, and finally the minimum estimated value in all rows is returned. At the end of a cycle, MV-Sketch determines the reflow based on whether it is greater than the set threshold.

The MJRTY algorithm used by MV-SKetch is used to determine which of any number of candidates has won a majority of votes, and those with more than half of the total votes must be the main candidate. Example: assume that there are three candidates A, B and C, and that delegates are voted in the following order: An An A C C B B C C C B C C

After recording the third vote, A took the lead by three votes. In processing the next three ballots, three A votes are matched with three other votes (two C votes and one B vote) (offset). After all the votes were recorded, C became the main candidate.

Algorithm 1:MV-Sketch update algorithm

MV-Sketch draws lessons from the MJRTY algorithm, when performing the update operation (algorithm 1 [2]), first accumulate Vi,j = Vi,j + vx (Vi,j increases the number of new stream bytes), and then compare the new stream x with the current bucket heavy flow candidate Ki,j, if the same, then the counter Ci,j increases the number of bytes of the new stream, otherwise it decreases accordingly; if it is reduced to below zero (that is, Ci,j)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.