On the mapping between logical and physical topologies

Network graphs, in general, successfully model a wide variety of interactions and relationships among entities, including both physical and logical connections. In this work, we study the problem of mapping a logical network on to a physical network; such a problem arises in various scenarios, for example, assignment of virtual machines on to physical servers in cloud computing, assignment of services on to physical devices in wireless/wire-line environments and physical resource assignment based on social networks. Specifically, in this paper, a logical network is a set of nodes with edges that denote the communication/bandwidth requirement between them, while a physical network denotes a set of physical nodes with edges that represent the available physical resources. The goal is to map the logical nodes on to the physical nodes and find physical resource allocation to meet the logical network demands, subject to physical network constraints. Towards this end, we propose a two-step approach to the problem, provide a set of novel feasibility checks for node assignment which are proved to be necessary and sufficient, and finally present a simple and fast algorithm that achieves a feasible logical to physical mapping with high probability. Illustrative simulation results are also presented to highlight the efficiency of the proposed algorithms.