Chang Liu

Chang Liu

PhD Candidate

University of Massachusetts Amherst

140 Governors Drive
Computer Science Building 216
College of Information and Computer Sciences
University of Massachusetts Amherst
Amherst, MA, 01003

I am a Ph.D. student advised by Prof. Don Towsley at School of Computer Science at the University of Massachusetts Amherst (UMass, Amherst). I am a member of the Computer Networks Research Group.

My research interests include computer networking with emphasis on analytical aspects of networks and complex systems. I am particularly interested in optimization, modeling, and performance evaluation of resource allocation, experiment and algorithm design for communication networks.

Education:

Ph.D. student, University of Massachusetts Amherst, 2010-present (w/ Don Towsley)
B.S., Xi'an Jiaotong University, 2010.

AREAS OF INTEREST:

News:

Publications:

2016
  1. Chang Liu, Ramesh K. Sitaraman, Don Towsley, Go-With-The-Winner: Performance Based Client-Side Server Selection, IFIP Networking 2016 (Networking'16),[pdf]
    Abstract []
    Content delivery networks deliver much of the world's web and video content by deploying a large distributed network of servers. We model and analyze a simple paradigm for client-side server selection that is commonly used in practice where each user independently measures the performance of a set of candidate servers and selects the one that performs the best. For web (resp., video) delivery, we propose and analyze a simple algorithm where each user randomly chooses two or more candidate servers and selects the server that provided the best hitrate (resp., bitrate). We prove that the algorithm converges quickly to an optimal state where all users receive the best hitrate (resp., bitrate), with high probability. We also show that if each user chose just one random server instead of two, some users receive a hitrate (resp., bitrate) that tends to zero. We simulate our algorithm and evaluate its performance with varying choices of parameters, system load, and content popularity.
2015
  1. Chang Liu, Ting He, Ananthram Swami, Don Towsley, Theodoros Salonidis, Andrei Iu. Bejan, Paul Yu, Multicast vs. Unicast for Loss Tomography on Tree Topologies, IEEE Military Communications Conference 2015 (MILCOM'15),[pdf]
    Abstract []
    Loss tomography using multicast and unicast mea- surements have been investigated separately. In this paper we compared the performance of loss tomography using multicast and unicast on tree structures. We proved identifiability of unicast measurements on tree structures with no 2-degree nodes. To theoretically compare multicast and unicast, we built an obser- vation model for multicast on trees and developed expressions for calculating the Crame ́r-Rao bound. We applied measurement design for unicast in trees and developed a simpler solution than our earlier work. Using a packet level simulator, we evaluated and compared the per link MSE of multicast and unicast under varying parameter settings include link weights, link loss rate distribution and size of the tree. The results show that in contrast to general belief that multicast outperforms unicast, unicast can outperform multicast under tight constraint on probing overhead, especially in terms of a weighted average of per-link MSEs. Meanwhile, multicast achieves more consistent performance wrt varying link success distribution or tree size.
  2. Ting He, Chang Liu, Ananthram Swami, Don Towsley, Theodoros Salonidis, Andrei Iu. Bejan, Paul Yu, Fisher Information-based Experiment Design for Network Tomography, ACM SIGMETRICS 2015 (SIGMETRICS'15), (Best Student Paper Award) [pdf]
    Abstract []
    Network tomography aims to infer the individual performance of networked elements (e.g., links) using aggregate measurements on end-to-end paths. Previous work on network tomography focuses primarily on developing estimators using the given measurements, while the design of measurements is often neglected. We fill this gap by proposing a framework to design probing experiments with focus on probe allocation, and applying it to two concrete problems: packet loss tomography and packet delay variation (PDV) tomography. Based on the Fisher Information Matrix (FIM), we design the distribution of probes across paths to maximize the best accuracy of unbiased estimators, asymptotically achievable by the maximum likelihood estimator. We consider two widely-adopted objective functions: determinant of the inverse FIM (D-optimality) and trace of the inverse FIM (A-optimality). We also extend the A-optimal criterion to incorporate heterogeneity in link weights. Under certain conditions on the FIM, satisfied by both loss and PDV tomography, we derive explicit expressions for both objective functions. When the number of probing paths equals the number of links, these lead to closed-form solutions for the optimal design; when there are more paths, we develop a heuristic to select a subset of paths and optimally allocate probes within the subset. Observing the dependency of the optimal design on unknown parameters, we further propose an algorithm that iteratively updates the design based on parameter estimates, which converges to the design based on true parameters as the number of probes increases. Using packet-level simulations on real datasets, we verify that the proposed design effectively reduces estimation error compared with the common approach of uniformly distributing probes.
2014
  1. Chang Liu, Ting He, Ananthram Swami, Don Towsley, Theodoros Salonidis, Andrei Iu. Bejan, and Paul Yu, Experiment Design for Link Loss Tomography, ITA Annual Fall Meeting (short paper), October 2014 [pdf]
    Abstract []
    We study experiment design to infer link loss rates from end-to-end losses on selected paths using network tomography. Since the inverse Fisher information matrix (FIM) establishes a lower bound on the error of any unbiased estimator, we formulate the problem as the design of probabilities in selecting probing paths to minimize an objective function based on the FIM. We consider two widely-adopted objective functions: the determinant of the inverse FIM (D-optimality) and the trace of the inverse FIM (A-optimality), where the former characterizes the volume of error ellipsoid and the latter characterizes the sum mean square error (MSE). Using a special property of the FIM, we obtain closed-form expressions for both objective functions, which lead to closed-form solutions for the optimal path selection probabilities. In particular, we show that the D-optimal design is uniform probing, i.e., probing each path with an equal probability. We verify through simulations that the A-optimal design can reduce the MSE compared with uniform probing.
2013
  1. Chang Liu, Ramesh K. Sitaraman, Don Towsley, Go-With-The-Winner: Client-Side Server Selection for Content Delivery, December 2013 [pdf][arXiv:1401.0209]
    Abstract []
    Content delivery networks deliver much of the web and video content in the world by deploying a large distributed network of servers. We model and analyze a simple paradigm for client-side server selection that is commonly used in practice where each user independently measures the performance of a set of candidate servers and selects the one that performs the best. For web (resp., video) delivery, we propose and analyze a simple algorithm where each user randomly chooses two or more candidate servers and selects the server that provided the best hitrate (resp., bitrate). We prove that the algorithm converges quickly to an optimal state where all users receive the best hitrate (resp., bitrate), with high probability. We also show that if each user chose just one random server instead of two, some users receive a hitrate (resp., bitrate) that tends to zero. We simulate our algorithm and evaluate its performance with varying choices of parameters, system load, and content popularity.
  2. Chang Liu, Ting He, Ananthram Swami, Don Towsley, Theodoros Salonidis, Andrei Iu. Bejan, and Kin K Leung, Measurement Design Framework for Network Tomography Using Fisher Information, ITA Annual Fall Meeting (short paper), 2013 [pdf]
    Abstract []
    In this paper, we study the design of measurements to infer link parameters by measuring end-to-end Performance along selected paths. While existing work focuses on the inference problem under given path measurements, the accuracy of inference fundamentally hinges on the set of available measurements. To this end, we propose a generic framework to design measurements for link parameter tomography to allow for most accurate inference of link parameters. Given a link model and a set of path measurements, it is known from estimation theory that the Fisher information matrix (FIM) characterizes a lower bound on the error of the optimal unbiased estimator, asymptotically achievable by the maximum likelihood estimator (MLE). We therefore formulate our measurement design problem to minimize a function of the FIM that represents the total estimation error. We apply this framework to inferring link loss rates from path losses.

Teaching:

Services: