The phenomenal growth of the Internet and its entry into many aspects of daily life has led to a great dependency on its services. Multimedia and content distribution applications (e.g., video streaming, online gaming, VoIP) require Quality of Service (QoS) guarantees in terms of bandwidth, delay, loss, and jitter to maintain a certain level of performance. Moreover, E-commerce applications and retail websites are faced with increasing demand for better throughput and response time performance. The most practical way to realize such applications is through the use of overlay networks, which are logical networks that implement service and resource management functionalities at the application layer.

Overlays offer better deployability, scalability, security, and resiliency properties than network layer based implementation of

services.

Network monitoring and routing are among the most important issues in the design and operation of overlay networks. Accurate monitoring

of QoS parameters is a challenging problem due to: (i) unbounded link stress in the underlying IP network, and (ii) the conflict in measurements caused by spatial and temporal overlap among

measurement tasks. In this context, the focus of this dissertation is on the design and evaluation of efficient QoS monitoring and fault location algorithms using overlay networks.

First, the issue of monitoring accuracy provided by multiple concurrent active measurements is studied on a large-scale overlay test-bed (PlanetLab), the factors affecting the accuracy are

identified, and the measurement conflict problem is introduced. Then, the problem of conducting conflict-free measurements is formulated as a scheduling problem of real-time tasks, its

complexity is proven to be NP-hard, and efficient heuristic algorithms for the problem are proposed. Second, an algorithm for minimizing monitoring overhead while controlling the IP link stress is proposed. Finally, the use of overlay monitoring to locate IP links' faults is investigated. Specifically, the problem of designing an overlay network for verifying the location of IP links'

faults, under cost and link stress constraints, is formulated as an integer generalized flow problem, and its complexity is proven to be

NP-hard. An optimal polynomial time algorithm for the relaxed problem (relaxed link stress constraints) is proposed.

A combination of simulation and experimental studies using real-life measurement tools and Internet topologies of major ISP networks is

conducted to evaluate the proposed algorithms. The studies show that the proposed algorithms significantly improve the accuracy and link

stress of overlay monitoring, while incurring low overheads. The evaluation of fault location algorithms show that fast and highly

accurate verification of faults can be achieved using overlay monitoring. In conclusion, the holistic view taken and the solutions

developed for network monitoring provide a comprehensive framework for the design, operation, and evolution of overlay networks.