Service-oriented computing represents an emerging paradigm for development and execution of distributed Internet-based applications. Development of service-oriented distributed applications is based on a composition of services available on the Internet. Development and execution of such applications is facilitated by an application-level middleware. Application-level middleware supports the deployment, discovery, composition, and communication of individual services, as well as the execution of distributed applications in the form of composite services. An integral part of application-level middleware is a virtual network. Virtual network enables creation of logically isolated communication spaces for a secure and reliable communication of services. Logical communication spaces are established on top of shared Internet infrastructure. Customization of virtual network enables an on-demand adjustment of logical communication space to the requirements of particular distributed application. In this thesis, the design and implementation of virtual network of service-oriented computing systems is presented. Virtual network provides the support for distributed service-oriented application portability, fault-tolerance regarding to failures in network nodes and communication links, secure communication of services, and privacy of their consumers and providers.