Learn, Adapt, and Profile (LeAP):
Beating the odds in traffic measurements/detection with optimal online learning and adaptive policies
A key tool for understanding and engineering Internet backbone is the analysis of packet traces. However, given the increasing backbone speed towards 100Gbps, it is prohibitive to monitor individual flows at all times. This project develops optimal online learning and adaptation strategies for accurate traffic sampling, inference, and detection under hard resource constraints (e.g., limited CPU or memory at routers) and dynamic network/traffic conditions. Based on theories and techniques in multi-arm bandits, group testing, and compressed sensing, optimal or near-optimal solutions will be developed by exploiting the unique structures of the specific measurement application under study. Challenges addressed include learning from observations with heavy-tailed distributions and long-range dependencies, coping with sparse and/or imperfect observations, and distributed learning strategies that involve multiple monitors and decision points.
If successful, this research will provide fundamental design principles for a flexible traffic measurement infrastructure under the software-defined networking (SDN) paradigm. Reconfigurable measurements based on a learning process can be realized in commodity router/switches using SDN APIs such as OpenFlow, leading to potential development of new services.
People
Faculty
- Chen-Nee Chuah, UC Davis - ECE (PI)
- Qing Zhao, Cornell Univ. - ECE (Co-PI)
Collaborators
- Puneet Sharma, Hewlett-Packard Laboratories
Graduate Students
- Mehdi Malboubi, ECE (PhD)
- Chao Wang, ECE (PhD)
- Chang Liu, ECE (PhD)
- Santhosh Chandrasekar (MS)
Alumni
- Liyuan Wang, ECE (MS, Dec 2013)
- Shu-Ming Peng, ECE (MS, Mar 2015)
- Ruogu Zhang, ECE (MS, Mar 2015)
- Lingxuan Li, ECE (MS, June 2015)
- Prof. Xiong Wang, Visiting Scholar (2013-14), University of Electronic Science and Technology of China (UESTC)
- Dr. Kobi Kohen, Postdoc, UC Davis
Undergrads
- Ryan Marquiss
- Joshua Vaughen
- Qijia Cao
- Chingyeung Fang
Publications
- M. Malboubi, C. Vu, C-N. Chuah, and P. Sharma, "Decentralizing Network Inference Problems with Multiple-Description Fusion Estimation (MDFE),"to appear in IEEE/ACM Transactions on Networking.
- C. Liu, M. Malboubi, and C-N. Chuah, "OpenMeasure: Adaptive Flow Measurement and Inference with Online Learning in SDN," IEEE Global Internet Symposium, April 2016. (Best Paper Award)
- X. Wang, M. Malboubi, S. Wang, S. Xu, and C-N. Chuah, "Practical Approach to Identifying Additive Link Metric with Shortest Path Routing," IEEE Globecom, Dec 2015. [pdf]
- M. Malboubi, Y. Gong, W. Xiong, C-N. Chuah, and P. Sharma, "Software defined Network Inference with Passive/active Evolutionary-optimal pRobing (SNIPER)," To appear in IEEE International Conference on Computer Communications and Networks (ICCCN), August 2015 (Invited Paper). [pdf]
- Y. Gong, X. Wang, S. Wang, S. Xu, M. Malboubi, and C-N. Chuah, "Towards Accurate Online Traffic Matrix Estimation in Software-Defined Networks," ACM Symposium on Software-Defined Networking Research (SOSR), June 2015. [pdf]
- K. Cohen and Q. Zhao, "Asymptotically Optimal Anomaly Detection via Sequential Testing," in IEEE Transactions on Signal Processing, vol. 63, no. 11, pp. 2929-2941, June, 2015.
- K. Cohen and Q. Zhao, "Active Hypothesis Testing for Anomaly Detection," in IEEE Transactions on Information Theory, vol. 61, no. 3, pp. 1432-1450, March, 2015.
- C. Wang, Q. Zhao, C-N. Chuah, "Group Testing under Sum Observations for Heavy Hitter Detection," Information Theory and Application Workshop (ITA), February 2015. (invited paper) [url]
- K. Cohen, Q. Zhao, "Anomaly Detection over Independent Processes: Switching with Memory," in Proc. of the 52nd Annual Allerton Conference on Communication, Control, and Computing, October, 2014.
- M. Malboubi, L. Wang, C-N. Chuah, and P. Sharma, "Intelligent SDN based Traffic (de)Aggregation and Measurement Paradigm (iSTAMP)," IEEE INFOCOM, April/May 2014. [pdf]
- M. Malboubi, C. Vu, C-.N. Chuah, and P. Sharma, "Compressive Sensing Network Inference with Multiple-Description Fusion Estimation," IEEE Globecom, December 2013. [pdf]
Thesis/Reports
- L. Li, "Adaptive Network Estimation in Data Centers: A Software Defined Networking Approach," MS Report, UC Davis, June 2015.
- S. Peng, "Adaptive Network Traffic Sampling and Inference," MS Report, UC Davis, March 2015.
- R. Zhang, "Simulation of Two Heavy Hitter Detection Algorithms: Nested Group Testing and Sampling," MS Report, UC Davis, March 2015.
- L. Wang, Adaptive Network Traffic Estimation using OpenFlow: An Implementation in Mininet, MS Thesis, UC Davis, December 2013.
Demos
Some of the algorithms developed in this project have been demonstrated as part of the GENI Science Shakedown Experiments.- M. Malboubi, S-M. Peng, C-N. Chuah, M. Bishop, B. Yoo, Z. Zhang, C. Zeng, X. Wang, "Intelligent SDN based Traffic (de)Aggregation and Measurement Paradigm (iSTAMP): A Demonstration", Technical demonstration, video, and poster presented at GENI Engineering Conference 21, Oct 2014.
- C. Liu, and S-M. Peng, M. Malboubi, C-N. Chuah, M. Bishop, B. Yoo, "Distributed Iceberg detection with SDN-enabled Online Learning", Technical demonstration, video, and poster presented at GENI Engineering Conference 23, June 2015.
Funding
This project is supported by National Science Foundation CNS-1321115 grant (2013-2016) and HP Labs 2013 Innovation Research Award.