Network Coordinates Research at Tsinghua University
 
Overview
  • Network coordinates (NC) system is an efficient mechanism for Internet latency prediction with scalable measurements. Our goal is to make a practical, secure and useful NC system.
  • Two of our early works focus on improving the performance of the representative NC system - Vivaldi. One is Pharos, which uses a two layer hierarchy to improve the prediction accuracy from Vivaldi. The other one is Myth, which is a scalable manner to reduce the accuracy decrease of Vivaldi under node churn.
  • Since large-scale distributed NC systems have serious security issues which can greatly affect the accuracy of NC Systems, we design a powerful security policy for NC Systems as well as implementing it into actual network to secure various applications based on NC Systems. Unlike other proposed security policy using reputation mechanism or vote approach, we are designing a distributed security policy based on social relationship to secure NC systems from various attacks.
  • Most of the NC work use Euclidean distance for latency prediction. However, the prediction accuracy is largely hurt by Triangle Inequality Violation (TIV). Besides this widely used Euclidean model, we explore the potential of matrix factorization model in depth and propose a more accurate NC system called Phoenix. Phoenix remove the constraints of TIV as well as reducing the error propagation, thus it can achieve much better prediction accuracy than existing NC systems. [NEW]
  • We release an accurate, lightweight and robust NC implementation, so-called Toread (tested on PlanetLab). [NEW]
  • We release a simulator which is able to evaluate different decentralized NC systems, so-called NCSim.[NEW]
  • We now investigate applying NC in social graph analysis. We propose Pomelo, aiming at the accurate estimation of the shortest-path distances of the node pairs in a social graph with low computational cost.
People
  • Prof. Xing Li (Advisor, deputy director of CERNET, head of NGN Lab)
  • Prof. Beixing Deng (PI, deputy-director of Network and Human-Machine Speech Communication Research Institute)
  • Dr. Yang Chen (Co-PI and former student leader, now Research Associate at Duke University, USA, while partially affiliated with NGN Lab as adjunct research scientist)
  • Guodong Wang (Student leader, master student at NGN Lab)
  • Qiuchen Zheng (master student at NGN Lab)
  • Zhiting Tang (master student at NGN Lab)
  • Zhuo Chen (bachelor student at NGN Lab)
  • Yibo Zhu (bachelor student at NGN Lab)
  • Prof. Xiaoming Fu (our collaborator at Georg-August-University of Goettingen, Germany)
  • Dr. Eng Keong Lua (our collaborator at College of Engineering, Carnegie Mellon University, Pittsburgh, USA)
  • Ang Li (our collaborator at Department of Computer Science, Duke University, USA)
  • Genyi Zhao (former bachelor student, now PhD student at Department of Electrical Engineering, Stanford University, USA)
  • Zengbin Zhang (former master student, now PhD student at Department of Computer Science, U.C. Santa Barbara, USA)
  • Xiaohan Zhao (former master student, now PhD student at Department of Computer Science, U.C. Santa Barbara, USA)
  • Xiao Wang (former bachelor student, now PhD student at University of Washington, USA)
  • Xiaoxiao Song (former bachelor student, now PhD student at Yale University, USA)
  • Yao Li (former bachelor student at NGN Lab, now PhD student at Tsinghua Univerisity)
  • Peng Sun (former bachelor student at NGN Lab, now PhD student at Department of Computer Science, Princeton University, USA)
  • Gang Wang (former bachelor student at NGN Lab, now PhD student at Department of Computer Science, U.C. Santa Barbara, USA)
  • Shining Wu (former bachelor student at NGN Lab, now master student at University of Goettingen, Germany)
  • Chengbo Dong (former bachelor student at NGN Lab)
Publications
  • Yang Chen, Xiao Wang, Cong Shi, Eng Keong Lua, Xiaoming Fu, Beixing Deng, Xing Li. Phoenix: A Weight-based Network Coordinate System Using Matrix Factorization. IEEE Transactions on Network and Service Management, 2011, 8(4):334-347. [PDF]
  • Zhuo Chen, Yang Chen, Yibo Zhu, Cong Ding, Beixing Deng, Xing Li. Tarantula: Towards an Accurate Network Coordinate System by Handling Major Portion of TIVs. In Proc. of the 54th Annual IEEE Global Telecommunications Conference (GLOBECOM'11), Houston, USA, Dec. 2011. [PDF]
  • Zhuo Chen, Yang Chen, Cong Ding, Beixing Deng, Xing Li. Pomelo: Accurate and Decentralized Shortest-path Distance Prediction in Social Graphs. ACM SIGCOMM Computer Communication Review, 2011, 41(4):406-407. [PDF]
  • Yibo Zhu, Yang Chen, Zengbin Zhang, Xiaoming Fu, Dan Li, Beixing Deng, Xing Li. Taming the Triangle Inequality Violations with Network Coordinate System on Real Internet. In Proc. of the 3rd ACM International Workshop on Re-Architecting the Internet (ReArch'10) held in conjunction with 6th International Conference on emerging Networking EXperiments and Technologies (CoNEXT'10), Philadelphia, USA, Nov. 2010. [PDF]
  • Yibo Zhu, Yang Chen, Guodong Wang, Xiaoming Fu, Dan Li, Beixing Deng, Xing Li. Toread: Towards Efficiently Searching Detours. To appear in Poster Session of 18th IEEE International Conference on Network Protocols (ICNP'10), Kyoto, Japan, Oct. 2010.
  • Yang Chen, Peng Sun, Xiaoming Fu, Tianyin Xu. Improving Prediction Accuracy of Matrix Factorization Based Network Coordinate Systems. In Proc. of the 19th International Conference on Computer Communications and Networks (ICCCN'10), Zurich, Switzerland, Aug. 2010. [PDF]
  • Chengbo Dong, Guodong Wang, Yang Chen, Beixing Deng, Xing Li. Handling Triangle Inequality Violations in Euclidean Distance based Network Coordinate Systems. In Proc. of IEEE IWQoS, Beijing, China, Jun. 2010.
  • Yibo Zhu, Yang Chen, Guodong Wang, Beixing Deng, Xing Li. NC-APT: An Efficient and Scalable Download Mirror Selecting System. In Proc. of the 29th IEEE Conference on Computer Communications Student Workshop (INFOCOM-SW'10), San Diego, CA, USA, Mar. 2010. [PDF]
  • Peng Sun, Yang Chen, Yibo Zhu, Xiaoming Fu, Beixing Deng, Xing Li. Dimension Reduction of Network Bottleneck Bandwidth Data Space. In Proc. of the 29th IEEE Conference on Computer Communications Student Workshop (INFOCOM-SW'10), San Diego, CA, USA, Mar. 2010. [PDF]
  • Yuan Lin, Yang Chen, Guodong Wang, Beixing Deng. Rigel: A Scalable and Lightweight replica selection Service for Replicated Distributed File System. In Proc. of the 10th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid'10), Melbourne, Australia, May 2010.
  • Yang Chen, Genyi Zhao, Ang Li, Beixing Deng, Xing Li. Handling Node Churn in Decentralized Network Coordinate System. IET Communications, 2009, 3(10):1578-1586. [PDF]
  • Chengbo Dong, Guodong Wang, Beixing Deng, Xing Li. AIDE: An Accurate Internet Distance Estimation System. In Poster Session of 17th IEEE International Conference on Network Protocols (ICNP'09), Princeton, New Jersey, USA, Oct. 2009. [PDF|Poster]
  • Peng Sun, Yang Chen, Beixing Deng, Xing Li. Neighbor Selection Based on TIV Severity Sort Model in Vivaldi Network Coordinate System. In Poster Session of 17th IEEE International Conference on Network Protocols (ICNP'09), Princeton, New Jersey, USA, Oct. 2009. [PDF|Poster]
  • Chengbo Dong, Guodong Wang, Xuan Zhang, Beixing Deng, Xing Li. Two-layer network coordinate system for Internet distance prediction. In Proc. of the First International Workshop on Peer-To-Peer Networking (P2PNet'09) held in conjunction with International Conference on Ultra Modern Telecommunications (ICUMT'09), St.-Petersburg, Russia, Oct. 2009. [PDF|PPT]
  • Yao Li, Beixing Deng, Xuan Zhang, Rui Wang, Xing Li. An Empirical Study on Embeddable Overlay Networks. In Proc. of the First International Workshop on Peer-To-Peer Networking (P2PNet'09) held in conjunction with International Conference on Ultra Modern Telecommunications (ICUMT'09), St.-Petersburg, Russia, Oct. 2009. [PDF|PPT]
  • Gang Wang, Shining Wu, Guodong Wang, Beixing Deng, Xing Li. Experimental Study on Neighbor Selection Policy for Phoenix Network Coordinate System. In Proc. of the First International Workshop on Peer-To-Peer Networking (P2PNet'09) held in conjunction with International Conference on Ultra Modern Telecommunications (ICUMT'09), St.-Petersburg, Russia, Oct. 2009. [PDF|PPT]
  • Yang Chen, Xiao Wang, Xiaoxiao Song, Eng Keong Lua, Cong Shi, Xiaohan Zhao, Beixing Deng, Xing Li. Phoenix: Towards an Accurate, Practical and Decentralized Network Coordinate System. In Proc. of 8th International IFIP-TC6 Networking Conference (Networking'09), Aachen, Germany, May.2009. [PDF|PPT|Simulator]
  • Guodong Wang, Yang Chen, Lei Shi, Eng Keong Lua, Beixing Deng, Xing Li. Proxima: Towards Lightweight and Flexible Anycast Service. In Proc. of the 28th IEEE Conference on Computer Communications Student Workshop (INFOCOM-SW'09), Rio de Janeiro, Brazil, Apr. 2009. [PDF]
  • Xiaohan Zhao, Eng Keong Lua, Yang Chen, Xiaoxiao Song, Beixing Deng, Xing Li. Sniper: Social-link Defense for Network Coordinate Systems. In Proc. of the 28th IEEE Conference on Computer Communications Student Workshop (INFOCOM-SW'09), Rio de Janeiro, Brazil, Apr. 2009. [PDF]
  • Xiaoxiao Song, Xiaohan Zhao, Eng Keong Lua, Zengbin Zhang, Beixing Deng, Xing Li. SLINCS: A Social Link based Evaluation System for Network Coordinate Systems. In Proc. of the 6th Annual IEEE Consumer Communications and Networking Conference (CCNC'09), Las Vegas, Nevada, Jan. 2009. [PDF]
  • Yang Chen, Yongqiang Xiong, Xiaohui Shi, Jiwen Zhu, Beixing Deng, Xing Li. Pharos: Accurate and Decentralised Network Coordinate System. IET Communications, 2009, 3(4):539-548. [PDF| Simulator|Implementation]
  • Xiao Wang, Yang Chen, Beixing Deng, Xing Li. Nonlinear Modeling of the Internet Delay Structure. In Proc. of the
    4th ACM International Conference on emerging Networking EXperiments and Technologies Student Workshop (CoNEXT-SW'08), Madrid, Spain, Dec.2008. [PDF|Poster]
  • Xiaohan Zhao, Xiaoxiao Song, Xiao Wang, Yang Chen, Beixing Deng, Xing Li. Attacks on PIC: Evaluation of PIC Security Policy. In Proc. of the 2008 International Symposium on Computer Science and its Applications (CSA'08), Hobart, Australia, Oct. 2008. [PDF]
  • Yang Chen, Genyi Zhao, Ang Li, Beixing Deng, Xing Li. Myth: An Accurate and Scalable Network Coordinate System under High Node Churn Rate. In Proceeding of the 15th IEEE International Conference on Networks (ICON'07), Adelaide, Australia, Nov. 2007. [PDF]
  • Yang Chen, Yongqiang Xiong, Xiaohui Shi, Beixing Deng, Xing Li. Pharos: A Decentralized and Hierarchical Network Coordinate System for Internet Distance Prediction. In Proceeding of the 50th Annual IEEE Global Telecommunications Conference (GLOBECOM'07), Washington, D.C., USA, Nov. 2007. [PDF]
Related Projects
Funding
  • This work is supported by the National Basic Research Program of China (No.2007CB310806) and the National Science Foundation of China (No.60473087, No.60703052, No.60850003).