Research On Optimization Method Of Split Transmission And Analyzer-side Reconstruction Of Switch Sketch In High-speed Network Measurement

Sketch-based measurement is an effective network measurement method in today’s hyper-scale and high-speed network.However,in order to transmit the sketch deployed in the switch to the analyzer-side,it is usually necessary to establish a dedicated out-of-band channel between the switch and analyzer-side,or to transfer sketch after compressing,which will sacrifice the query accuracy.Based on In-band Network Telemetry(INT),LightGuardian first proposed the method of "split sketch to sketchlets at the switch,reconstruct sketch by collecting sketchlets at the analyzer-side".However,this method simply selects the buckets of a column in sketch to add to sketchlet,resulting in inaccurate measurement of the reconstructed sketch,which mainly stems from invalid and stale data in the reconstructed sketch.In order to improve the query accuracy of reconstructed sketch,two major problems must be solved:how to efficiently split switch sketch and how to select valuable buckets to form sketchlet.To this end,this paper proposes a novel optimization method of sketch split transmission and analyzer-side reconstruction,which has the following three contributions:Firstly,we design a new scatter sketchlet,which consists of valuable buckets within a certain range in sketch,so as to transmit measurement data more effectively.Based on scatter sketchlet,we optimize the corresponding sketch reconstruction method.Secondly,this paper proposes lightweight data structures called bitmap and cookie,which are used to trace the "validity" and "freshness" of sketch buckets.Then this paper combines these two data structures to design efficient algorithms to select these valuable buckets.Thirdly,the proposed algorithm is implemented in real hardware programmable switch,which improves the practicability.Finally,this paper makes a full theoretical analysis and proves the high efficiency of proposed method.In the meanwhile,a real experimental testbed is built,and experimental verification is carried out under the drive of real network traffic.The results show that with less than 0.36%loss of the packet forwarding rate,the proposed method avoids up to 60%errors in the reconstructed sketch.