In the last few years the Internet has witnessed a tremendous growth in the area of multimedia services. For example YouTube, used for videosharing [1] and Skype, used for Internet telephony [2], enjoy a huge popularity, counting their users in millions. Traditional media services, such as telephony, radio and TV, once upon a time using dedicated networks are now deployed over the Internet at an accelerating pace. The triple play and quadruple play business models, which consist of combined broadband access, (fixed and mobile) telephony and TV over a common access medium, are evidence for this development. Multimedia services often have strict requirements on quality of service (QoS) metrics such as available bandwidth, packet delay, delay jitter and packet loss rate. Existing QoS architectures (e. g. , IntServ and DiffServ) are typically used within the service provider network, but have not seen a wide Internet deployment. Consequently, Internet applications are still forced to rely on the Internet Protocol (IP)’s best-effort service. Furthermore, wide availability of computing resources at the edge of the network has lead to the appearance of services implemented in overlay networks. The overlay networks are typically spawned between end-nodes that share resources with each other in a peer-to-peer (P2P) fashion. Since these services are not relying on dedicated resources provided by a third-party, they can be deployed with little effort and low cost. On the other hand, they require mechanisms for handling resource fluctuations when nodes join and leave the overlay. This dissertation addresses the problem of unicast QoS routing implemented in overlay networks. More precisely, we are investigating methods for providing a QoS-aware service on top of IP’s best-effort service, with minimal changes to existing Internet infrastructure. A framework named Overlay Routing Protocol (ORP) was developed for this purpose. The framework is used for handling QoS path discovery and path restoration. ORP’s performance was evaluated through a comprehensive simulation study. The study showed that QoS paths can be established and maintained as long as one is willing to accept a protocol overhead of maximum 1.5% of the network capacity. We studied the Gnutella P2P network as an example of overlay network. An 11-days long Gnutella link-layer packet trace collected at Blekinge Institute of Technology (BTH) was systematically decoded and analyzed. Analysis results include various traffic characteristics and statistical models. The emphasis for the characteristics has been on accuracy and detail, while for the traffic models the emphasis has been on analytical tractability and ease of simulation. To the author’s best knowledge this is the first work on Gnutella that presents statistics down to message level. The models for Gnutella’s session arrival rate and session duration were further used to generate churn within the ORP simulations. Finally, another important contribution is the evaluation of GNU Linear Programming Toolkit (GLPK)’s performance in solving linear optimization problems for flow allocation with the simplex method and the interior point method, respectively. Based on the results of the evaluation, the simplex method was selected to be integrated with ORP’s path restoration capability.