Research On Key Technologies Of Network Measurement Based On Tomography

With the development of information technologies and the increasing demand for communications,various network systems and services have emerged.On the one hand,the increase in the number of users has made the scale of wired IP networks more and more massive,and multi-hop connections have become a basic prerequisite for the normal communication among hosts that widely distributed in the global.On the other hand,the maturity of Internet of Things(Io T)technologies has promoted the growth of Io T devices.The number of global Io T devices has reached 11 billion until the end of 2019.In order to connect the resource-constrained Io T devices,many low-power multi-hop data transmission technologies have been proposed.In this regard,how to efficiently measure the performance of these large-scale multi-hop networks becomes an essential problem.Network measurement provides the fine-grained performance metrics to service providers and network managers,which is the basis of network management and network optimization.Network tomography is an external approach that uses end-to-end measurements among monitors to infer the internal network states,thereby incurring low overhead.Existing works mainly focus on identifying the exact values of all link metrics,which results in high implementation complexity and non-negligible operational cost.Moreover,existing works usually assumes an ideal network model where the topology is fixed and all network elements are reliable,without considering the impact of topology changes and link failures on network measurement.Due to the complicated composition,frequent topology changes and communication failures of large-scale multi-hop networks,the existing network tomography methods could not achieve the desired performance.To this end,this dissertation summarizes the main challenges of large-scale network performance measurement,and proposes four key technologies to build a flexible,efficient and robust measurement system.1)Bound-based network tomography for inferring link metrics.The problem of inferring the performance bounds on a set of target links(i.e.,interesting links)is investigated.By flexibly adjusting the accuracy of link performance measurement that satisfies the application requirements,the implementation complexity and monitoring overhead can be significantly reduced.Specifically,this dissertation first develops an efficient solution to obtain the tightest upper and lower bounds of interesting links in an arbitrary network with a given set of monitors and end-to-end measurements.Based on this solution,this dissertation further proposes an algorithm to place new monitors over existing ones such that the bounds of interesting links can be maximally tightened.Compared with state-of-the-art approaches,the proposed algorithms noticeably reduce the bound interval lengths of all interesting links and the number of monitors.This work has been published in the proceedings of IEEE INFOCOM 2020.2)Bound-based network tomography for inferring path metrics.In order to verify the performance of the paths running critical services,the problem of inferring performance bounds for a set of paths of interest is considered.Specifically,this dissertation first presents an efficient solution to infer the tightest upper bounds and lower bounds of all interesting paths in an arbitrary network with a given set of monitors and end-to-end measurements.Moreover,this dissertation develops a monitor placement algorithm so that a newly added monitor can maximally tighten the performance bounds of interesting paths.The proposed algorithms substantially reduce the bound interval lengths of all interesting paths and use much fewer monitors than state-of-the-art approaches.This work has been submitted to IEEE/ACM Transactions on Networking.3)Link performance tomography based on time-varying topology sequence.This dissertation studies the problem of inferring the link metrics from end-to-end measurements in the face of topology changes.Based on the prediction of network connectivity,a concise and generic time-varying topology model is designed.This dissertation also proposes an efficient algorithm to place monitors proactively so that during network planning,service provider and network manager can meet the demands of monitor placement at runtime,which avoids frequent reconfigurations and instability in the monitoring system.Compared with existing methods,the proposed algorithm relaxes the assumptions about network model and is suitable for more practical application scenarios.This work has been published in the proceedings of IEEE ICNP 2017 and IEEE/ACM Transactions on Networking.4)Link performance tomography based on failure classification modeling.In view of the vulnerability of network communication,the link performance tomography with considering different kinds of link failures is studied.Specifically,based on the predictability and unpredictability of link failures,this dissertation models them in different forms.Moreover,this dissertation proposes a set of robust monitor placement algorithms which place monitors to compute the metrics of all non-failed links by end-to-end measurements between monitors,including:(i)two straightforward solutions(i.e.,simple union placement and one-time placement algorithms)that apply an existing algorithm for unpredictable link failures to a set of predicted topologies generated by predictable link failures,(ii)an incremental placement algorithm that sequentially places monitors in each predicted topology,(iii)a joint placement algorithm that jointly considers monitor requirements of all network topologies by casting the problem as a hitting set problem.A monitor removal method is also developed to identify and remove the redundant monitors.Compared with existing methods,these proposed algorithms can guarantee the link identifiability with various tradeoffs between the measurement overhead and time complexity.This work has been published in the proceedings of ACM TUR-C 2017 and IEEE/ACM Transactions on Networking.