In this paper, we improve, implement and extensively evaluate such a monitoring system. We further make the following contributions: i) scalability analysis which shows that for reasonably large n (e.g., 100), k is only in the range of O(n log n), ii) efficient adaptation algorithms for topology changes, such as the addition/removal of end hosts and interconnections, iii) measurement load balancing scheme for better scalability, iv) topology measurement error handling for better accuracy. Both simulation and Internet experiments demonstrate that we achieve high path loss rate estimation accuracy while adapting to topology changes within seconds and handling topology errors. We can also continuously update the loss rate estimations online. For example, in the Internet experiments, the average update time is 0.16 second for all 2550 paths, the absolute error of loss rate estimation is 0.0027 and the average error factor is 1.1.