NetEmbed: A network resource mapping service for distributed applications

Emerging configurable infrastructures (large-scale overlays, grids, distributed testbeds, and sensor networks among others) comprise diverse sets of computing resources and network conditions. The distributed applications to be deployed on these infrastructures exhibit increasingly complex constraints and requirements on the resources they require. Thus, a common problem facing the efficient deployment of distributed applications on these infrastructures is that of mapping application-level requirements onto the network in such a manner that the requirements of the application are realized. We present two new techniques to tackle this combinatorially-hard problem that thanks to a number of heuristics, are able to find feasible solutions or determine the non-existence of a solution in most cases, where otherwise the problem would be intractable. These techniques are also false negative free, a common problem among other heuristics currently in use.