Virtual network embedding with collocation: Benefits and limitations of pre-clustering

Given that mechanisms for resource isolation are in place, the collocation of virtual network (VNet) nodes is attractive as it reduces the inter-machine communication and hence improves the VNet embedding. However, existing VNet embedding algorithms either do not support the collocation of virtual nodes of the same VNet, or only support it implicitly by referring to the possibility to pre-cluster the VNet topology: this pre-clustered network forms the new VNet request and is embedded accordingly. This paper presents a pre-clustering algorithm OPTCUT that is optimal in the sense that it minimizes the amount of link resources needed for the embedding. It is based on a smart linear program formulation that ensures fast solutions. OPTCUT can be used together with any existing VNet embedding algorithms, and we show that it can greatly improve the state-of-the-art embedding algorithm SecondNet [16]. The paper also describes a simple algorithm LoCo that directly supports collocation. This algorithm is part of a novel and generic VNet embedding framework METATREE which may be of independent interest. We compare the performance of the pre-clustering approaches with the direct VNet embeddings by LoCo, and find that preclustering also has its limitations. In particular, the information gap between the pre-clustering and the actual algorithm, as well as an inaccurate estimation of the distribution of remaining substrate resources, may lead to a low network utilization.