In the last years, Service Overlay Networks (SONs) have emerged as a promising means to address some of the issues (e.g. end-to-end QoS) affecting the current Internet and to favor the development and deployment of new value-added Internet services. The deployment of an SON is a capital-intensive investment, since bandwidth with certain QoS guarantees must be purchased from the individual network domains through bilateral Service Level Agreements. Thus, minimizing the economic cost of the logical end-to-end service delivery infrastructure is one of the key objectives for the SON provider. When a SON is aimed at end-to-end QoS provisioning, its topology must be designed so as to also satisfy the specific requirements of QoS-sensitive applications. This paper deals with the problem of planning the SON topology in order to take into account both cost and QoS constraints. More specifically, the paper proposes a set of new algorithms for the design of an optimized SON topology, which minimizes the economic cost while simultaneously meeting bandwidth and delay constraints. A performance comparison among such algorithms is finally carried out.