Research And Implementation Of Buffer Queue Controlling Algorithm Based On R/s Analysis Over Data Streams

With the rapid development of network technology and computer technology, more and more data comes in the form of streaming. As data streams are burst and infinite, in a moment, the arrival rates of some streams may be suddenly sharp increase and memory overflow resulting in a short period of time, which leads to prejudice continuous aggregate queries. Therefore, considering the input and output rates of data streams in memory in the unit of time and the largest memory capacity to predict whether coming overload resulting from the data streams, and decide how to implement buffer queue management, in order to keep memory non-overflow is of great significance.Considering the arrival stream rate in a period of time as a time series are proposed in this paper. Fractal theory provides a new way to time series analysis, researching on the fractal-based time series can predict characteristics and inherent principle of time series from a new point of view. First, based on R/S analysis and by means of Hurst exponent H (0＜H＜1), the changing trend of stream rates can be identified.Second, depending on the predicted trend of stream rates, the algorithms for buffer queue controlling are proposed in this paper. They are fixed-length A algorithm and adaptive-length algorithm, where△represents the basic length changes of buffer queue in each cycle. According to the reference is the initial length or the current predicted length to calculate the length of the buffer queue, fixed-length A algorithm is divided to△_Linit algorithm and△_Lcur algorithm. Fixed-length△algorithm is that given the actual changes of queue length in the current cycle and the basic changes△ calculates the length changes of the next cycle. Adaptive-length algorithm is that based entirely on actual changes of queue length in the current cycle determines the changes of queue length in the next cycle. When the predicted length of the queue is not large enough, discards part of the data by random load shedding algorithm.Finally, three conclusions can be obtained by the experiment and analysis.1) Hurst exponent identify the changing trend of stream rates accurately.2) Adaptive-length algorithm has a closer length to the actual length and less delay comparing to the fixed-length△algorithm.3) The fixed-length△algorithm has much less load shedding when the forecast queue length does not meet the actual length of the queue.