Nowadays, Internet still lacks of an adequate support for QoS-sensitive applications, such as VoIP, Videoconference, and Video-on-Demand. To a large extent, this is due to the fact that Internet was originally designed to provide only a best-effort packet delivery service. In recent years, Service Overlay Networks (SONs) have emerged as a profitable way to address these issues without changing the underlying infrastructure. In this paper, we analyze the topology design problem of a SON from a performance point of view. Since the analytical solution of the problem is computationally too complex, we compare the performance of a limited set of well-known topologies. Based on heuristics, we also propose three new traffic demand-aware overlay topologies. Through extensive simulations, we investigate the performance of the candidate overlay topologies in different network scenarios, taking into account overhead and accepted traffic between the overlay nodes.