oftware defined networks (SDNs) are introduced as a new idea to facilitate the network management process through excluding control plane from data plane. SDNs are superior to traditional networks in terms of providing a central view on network state. Thus, they are more favorable option for implementing the communication backbone of cloud data centers. On the other side, hosting multi-tier applications with inherent non-SDN communication patterns is an inevitable task of cloud data centers. As a solution, the data center network must be virtualized and be shared between tenant applications. To increase the utilization of the virtualized resources an efficient virtual network embedding (VNE) algorithm is required. So, this dissertation investigates the problem of mapping non-SDN virtual networks on SDN substrates. As the main contribution of this article a two-step online VNE algorithm as well as a single shot online VNE algorithm are proposed to deal with this problem. To show effectiveness of the proposed online algorithms, their competitive ratios are calculated analytically. The competitive ratio of the two-steps algorithm is logarithmic in the size of the hosting network and the competitive ratio of the single shot algorithm is linear in terms of hosting network size. Furthermore, the calculated competitive ratio of the proposed two-steps algorithm is verified through several simulations.
