The demand for live and interactive multimedia services over the Internet raises questions on how well the Internet Protocol (IP)’s best-effort effort service can be adapted to provide adequate end-to-end quality of service (QoS) for the users. Although the Internet community has developed two different IP-based QoS architectures, neither has been widely deployed. Overlay networks are seen as a step to address the demand for end-to-end QoS until a better solution can be obtained. As part of the telecommunication research at Blekinge Institute of Technology (BTH) in Karlskrona, Sweden we are investigating new theories and algorithms concerning QoS routing. We are in the process of developing Overlay Routing Protocol (ORP), a framework for overlay QoS routing consisting of two protocols: Route Discovery Protocol (RDP) and Route Management Protocol (RMP). In this paper we describe RDP and provide preliminary simulation results for it.