To approximate sums of values in key-value data streams, sketches are widely used in databases and networking systems.They offer high-confidence approximations for any given key while ensuring low time and space overhead.While existing sketches are proficient in estimating individual keys, they struggle to maintain this high confidence across all keys collectively, an objective that is critically important in both algorithm theory and its practical applications.We propose ReliableSketch, the first to control the error of all keys to less than Λ with a small failure probability Δ, requiring only 𝑂 (1 + Δ ln ln( 𝑁 Λ )) amortized time and 𝑂 ( 𝑁 Λ + ln( 1 Δ )) space.Furthermore, its simplicity makes it hardware-friendly, and we implement it on CPU servers, FPGAs, and programmable switches.Our experiments show that under the same small space, ReliableSketch not only keeps all keys' errors below Λ but also delivers competitive throughput among accuracy-oriented baselines, outperforming * Both authors contributed equally to this research.

The detection of Heavy Hitters (HH) of flows in a network plays a crucial role in a variety of critical applications, including network topology optimization, congestion control, and network security (e.g., DDoS mitigation). In high-performance data centers, tasks such as optimizing model training and detecting anomalies require microsecond-level granularity for burst and congestion detection, demanding higher accuracy and fine granularity in HH detection. However, existing HH detection schemes primarily focus on traffic accumulation over longer periods and ignore instantaneous flow rates, making them incapable of detecting short-duration heavy hitters (at the granularity of milliseconds to microseconds) that can significantly affect network performance. This paper proposes a rate-sensitive definition of HHs and introduces HeavyFinder, a framework for enabling efficient HH detection of flows at microsecond granularity and accurately describing their traffic changes. It detects HHs based on inherent characteristics of both traffic volume and instantaneous flow rates, and improves the existing elephant flow filtering mechanism. Furthermore, this framework provides an efficient information aggregation method for reporting HH information, which can reduce overhead further. We deployed and tested HeavyFinder on x86 CPUs and evaluated its performance by using real network trace data. Results show that HeavyFinder achieves sub-$\mathbf{1 0}$-microsecond accuracy in detection for the start and end times of HHs, with$3-10 \times$lower reporting overhead compared to existing frameworks.

Reports show that DDoS attacks are ubiquitous on the Internet and may jeopardize networks' stable operation. In order to understand the nature of this threat and further to enable effective control and management, a whole picture of the Internet-wide attacks is a necessity. Traditional methods use darknets to this end. However, with the IPv4 address space exhaustion, darknets become hard to acquire. In this paper, we seek to detect Internet-wide attacks using a live network. In particular, we focus on the most prevalent SYN flooding attacks. First, a complete attack scenario model is introduced according to the positions of the attacker, the victim and the attacking address. Then, after discussing the features of all scenarios, an algorithm named WSAND is proposed to detect Internet-wide SYN flooding attacks using Netflow data. In order to evaluate it, the algorithm is deployed at 28 main PoPs (Points of Presence) of the China Education and Research Network (CERNET) and the total internal address space is up to 200/16 blocks. A large quantity of Internet-wide SYN flooding attacks detected in March 2014 is discussed in detail. With the help of the detected attacks, a case study of detecting an internal zombie is presented.