Network Measurement Technologies, Models And Algorithms Based On Active And Passive Measurement

The explosive growth in Internet deployment for a constantly growing variety of applications has created a massive increase in demand for network performance parameters, such as latency, bandwidth, throughput, which are important for providing differentiated network services. Knowledge of the up-to-date network performance is critical for numerous important network management tasks, including proactive and reactive resource management and traffic engineering, as well as providing QoS guarantees for end-user applications. In particular, as modern network management systems shift their focus forward service-level and application-level management, the network monitoring process requires more data to be collected and at much higher frequencies.There is recently sighificant interest in developing network measure technologies and network monitoring infrastructures. In general, conventional schemes to measure network performance are classified into two types: active and passive measurements. Active measurement measures network performance parameters, such as latency, bandwidth, packet loss by sending probe packets and monitoring them. Passive measurement records statistics about the network characteristics of network flows by the probe device accessing the network. The thesis has studied the network measurement technologies, network measurement model and its optimization algorithms based on active and passive measurement. And the thesis makes the following contributions:(1) The optimization problem of distributed active measurement model and its approximation algorithmsThe cost of active measurement includes deployment cost and measuring cost. Once a set of measuring stations has been deployed, we need determine the measurement strategies to minimize the measuring cost of measuring all links of a network.The measure assignment problem of distributed active measuring link-bandwidth model is proposed. This problem is NP hard and its integer programming formulation is shown. This thesis gives a 2-approximation algorithm for the measure assignment problem using dynamic programming and greedy strategy. The effectiveness of this approximation algorithm is validated by simulations evaluation over a wide range of network topologies. This scheme and approximation algorithms for optimizing the measuring assignment for measuring link-bandwidth could also be applied to measure latency and packet loss. This research is helpful to design and develop distributed active measuring systems.(2) The optimization problem of low-overhead link-bandwidth passive monitoring model and its approximation algorithms...