Chen Qian

CNS-1750704

CAREER: Othello Hashing and Its Applications to Scalable and Dynamic Network Forwarding and Functions

2018-2023

University of California Santa Cruz

Project Summary

Providing high-speed Internet services to communities and businesses while limiting the infrastructure cost has been a long-term goal of network protocol designs. There have been challenges in achieving fast, scalable, and fine-grained network processing while maintaining low network cost, mainly due to the limited resources on network devices such as fast memory. The promising approach of exploiting programmable networks, such as software defined networking, were considered difficult to execute on conventional network devices. This project aims to use an innovative hashing scheme, Othello, to improve network performance without special and expensive hardware by exploring fast, memory-efficient, and portable primitives for network processing based on innovative data structures and algorithms.

This project proposes Othello Hashing, a key-value lookup algorithm developed on the theoretical foundation of Minimal Perfect Hashing. Othello Hashing achieves faster lookup speed and much smaller memory cost compared to existing network lookup methods. It utilizes network programmability to support dynamic updates on its lookup structures. This project plans to develop a number of important network primitives using Othello, including forwarding information bases, software load balancers, distributed data placement, and private data access. The success of this project will demonstrate Othello Hashing as a fundamental tool in designing novel network algorithms, protocols, and systems, for which existing tools may not be suitable. The impact of Othello Hashing may go beyond the networking research: the collaboration of the PI with genome biology researchers on applying Othello to metagenomic sequence classification has led to promising results. The project also offers a number of education activities for student training, undergraduate research participation, diversity promotion, and outreach activities.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation.

Project Publications

[ToN] Minmei Wang, et al, Collaborative Validation of Public-Key Certificates for IoT by Distributed Caching, in IEEE/ACM Transactions on Networking

[ToN] Xiaofeng Shi, et al, TagAttention: Mobile Object Tracing with Zero-Appearance Knowledge by Vision-RFID Fusion, in IEEE/ACM Transactions on Networking.

[ToN] Huazhe Wang,?Xin Li, Yang Wang,?Yu Zhao,?Ye Yu, Hongkun Yang, Chen Qian, SICS: Secure and Dynamic Middlebox Outsourcing, in IEEE/ACM Transactions on Networking.

[HotNets]?Chen Qian,?Shouqian Shi,?Xiaofeng Shi,?Minmei Wang, Don't Work on Individual Data Plane Algorithms. Put Them Together! in Proc. of ACM HotNets, 2020 (Accept rate: 24.8%)

[SIGCOMM] Shouqian Shi and Chen Qian, Concurrent Entanglement Routing for Quantum Networks: Model and Designs, in Proc. of ACM SIGCOMM 2020. (Acceptance rate: 21.6%) [Code of Quantum Entanglement Routing]?[pdf]

[SIGMETRICS] Shouqian Shi and Chen Qian, Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems, (long-paper presentation) in Proc. of ACM SIGMETRICS?2020, (journal version) in Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS). (Accept rate: 15.4%) [Code of Ludo hashing]?[pdf]

[SOCC]?Shouqian Shi,?Ye Yu,?Minghao Xie,?Xin Li, Xiaozhou Li, Ying Zhang, Chen Qian, Concury: A Fast and Light-weight Software Cloud Load Balancer, in?Proc. of ACM SOCC, 2020 (Accept rate: 24%)

[INFOCOM'19] Minmei Wang, Chen Qian, Xin Li, Shouqian Shi, Collaborative Validation of Public-Key Certificates for IoT by Distributed Caching, in Proc. of IEEE INFOCOM, 2019 (Accept rate: 288/1464 = 19.7%)

[HPCA'19] M. Ogleari, Y. Yu, C. Qian, E. Miller, J. Zhao, String Figure: A Scalable and Elastic Memory Network Architecture, in Proc. of IEEE HPCA, 2019 (Acceptance rate: 19.7%)

[Genome Biology] Ye Yu, Jinpeng Liu, Xinan Liu, Yi Zhang, Eamonn Magner, Erik Lehnert , Chen Qian and Jinze Liu, SeqOthello: querying RNA-seq experiments at scale, in Genome Biology, 2018. (Impact factor: 13.2) [pdf]

[ToN] Y. Yu, D. Belazzougui, C. Qian, Q. Zhang, Memory-efficient and Ultra-fast Network Lookup and Forwarding using Othello Hashing, accepted to IEEE/ACM Transactions on Networking. [Code of Othello Hashing] [pdf]