Kaicheng Yang

Kaicheng Yang

Auto-generated profile, based on publicly available information

Kaicheng Yang

Peking University, Beijing, China

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 August 2023 in IEEE Transactions on Parallel and Distributed Systems
Verified
Journal Article
Closed access
KYKaicheng Yang
Kaicheng Yang
SLSheng Long
Sheng Long
QSQilong Shi
Qilong Shi
YLYuanpeng Li
Yuanpeng Li
ZLZirui Liu
Zirui Liu
ZJZhengyi Jia
Zhengyi Jia
Network measurement is indispensable to network operations. INT solutions that can provide fine-grained per-switch per-packet information serve as promising solutions for per-flow per-switch measurement. The main shortcoming of INT is its high network overhead incurred by collecting INT information, making INT impractical for production deployment. Sketches that can compactly record per-flow information with small memory footprint, are a promising choice for compressing INT information to reduce INT overhead. An ideal sketch for efficiently compressing INT information in practice should achieve both simplicity and accuracy, but no existing sketch achieves both. Motivated by this, we first design SketchINT to combine INT and sketches, aiming to obtain all per-flow per-switch information with low network overhead. Second, we design a new sketch for SketchINT, namely TowerSketch, which achieves both simplicity and accuracy. The key idea of TowerSketch is to use different-sized counters for different arrays under the property that the number of bits used for different arrays stays the same. TowerSketch can automatically record larger flows in larger counters and smaller flows in smaller counters. To further ease the configuration and give network operators more confidence on performance of TowerSketch, we propose a method for precise error bound estimation. We have fully implemented our SketchINT prototype on a testbed consisting of 10 switches. We also implement our TowerSketch on P4, single-core CPU, multi-core CPU, and FPGA platforms to verify its deployment flexibility. Extensive experimental results verify that 1) TowerSketch achieves better accuracy than prior art on various tasks, outperforming the state-of-the-art ElasticSketch up to 27.7 times in terms of error; 2) Compared to INT, SketchINT reduces the number of packets belonging to the control plane overhead by $3 \sim 4$ orders of magnitude with an error smaller than 5%; 3) The estimated error bound of TowerSketch can almost match the actual error bound.

10 September 2023
Verified
Conference Paper
Open access
KYKaicheng Yang
Kaicheng Yang
YWYuhan Wu
Yuhan Wu
RMRuijie Miao
Ruijie Miao
TYTong Yang
Tong Yang
ZLZirui Liu
Zirui Liu
GXGaogang Xie
Gaogang Xie

10 September 2023
Verified
Conference Paper
Open access
YZYikai Zhao
Yikai Zhao
WLWenrui Liu
Wenrui Liu
FDFenghao Dong
Fenghao Dong
TYTong Yang
Tong Yang
YLYuanpeng Li
Yuanpeng Li
YYYongqiang Yang
Yongqiang Yang

26 May 2023 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
YLYuanpeng Li
Yuanpeng Li
FWFeiyu Wang
Feiyu Wang
XYXiang Yu
Xiang Yu
YYYilong Yang
Yilong Yang
KYKaicheng Yang
Kaicheng Yang
SUSteve Uhlig
Steve Uhlig
Data stream processing is critical in streaming databases. Existing works pay a lot of attention to frequent items. To improve the accuracy for frequent items, existing solutions focus on accurately filtering infrequent items. While these solutions are effective, they keep track of all infrequent items and require multiple hash computations and memory accesses. This increases memory and time overhead. To reduce this overhead, we propose LadderFilter, which candiscard infrequent items efficiently in terms of both memory and time. To achieve memory efficiency, LadderFilter discards (approximately) infrequent items using multiple LRU queues. To achieve time efficiency, we leverage SIMD instructions to implement LRU policy without timestamps. We apply LadderFilter to four types of sketches. Our experimental results show that LadderFilter improves the accuracy by up to 60.6×, and the throughput by up to 1.37×, and can maintain high accuracy with small memory usage. All related code is provided open-source at Github.

14 July 2023 in IEEE Transactions on Parallel and Distributed Systems
Verified
Journal Article
Closed access
ZLZirui Liu
Zirui Liu
YZYikai Zhao
Yikai Zhao
ZFZhuochen Fan
Zhuochen Fan
TYTong Yang
Tong Yang
XLXiaodong Li
Xiaodong Li
BCBin Cui
Bin Cui
Layer-3 load balancing is a key topic in the networking field. It is well acknowledged that flowlet is the most promising solution because of its good trade-off between load balance and packet reordering. However, we find its one significant limitation: it makes the forwarding paths of flows unpredictable. To address this limitation, this article presents BurstBalancer, a simple yet efficient load balancing system with a sketch, named BalanceSketch. Our design philosophy is doing less changes to keep the forwarding path of most flows fixed, which guides the design of BalanceSketch and our balance operations. We have fully implemented BurstBalancer in a small-scale testbed built with Tofino switches, and conducted both large-scale event-level (NS-2) and ESL (electronic system level) simulations. Our results show that BurstBalancer achieves 5% $\sim$ 35% smaller FCT than LetFlow in symmetric topology and up to 30× smaller FCT in asymmetric topology, while 58× fewer flows suffer from path changing. All related codes are open-sourced at GitHub.

4 August 2023
Verified
Conference Paper
Open access
RMRuijie Miao
Ruijie Miao
YZYiyao Zhang
Yiyao Zhang
GQGuanyu Qu
Guanyu Qu
KYKaicheng Yang
Kaicheng Yang
TYTong Yang
Tong Yang
BCBin Cui
Bin Cui
Sketching algorithms are considered as promising solutions for answering approximate query on massive data stream. In real scenarios, a large number of problems can be abstracted as subset query over multiple attributes. Existing sketches are designed for query on single attributes, and therefore are inefficient for query on multiple attributes. In this work, we propose Hyper-USS, an innovative sketching algorithm that supports subset query over multiple attributes accurately and efficiently. To the best of our knowledge, this work is the first sketching algorithm designed to answer approximate query over multi-attribute data stream. We utilize the key technique, Joint Variance Optimization, to guarantee high estimation accuracy on all attributes. Experiment results show that, compared with the state-of-the-art (SOTA) sketches that support subset query on single attributes, Hyper-USS improves the accuracy by 16.67X and the throughput by 8.54X. The code is open-sourced at Github.