netEmbed:
A Network Resource Mapping Service For
Distributed Applications

The goal of this proyect is to develop effient resource management methods for overlays on top of wide area networks. We are particularly interesested in the problem mapping a desired virtual topology into an existing physical network while satisfying a set of given constraints. This is what we refer to as the Resource Mapping Problem.

Brief description

The next figure illustrates the main components the mapping:

Where

• The Hosting network (also called Real network or Physical network) is the representation of the network on top of which the overlay will be allocated, given as a GraphML document and describes not only the topology itself, but also the characteristics of both its nodes and edges. This network representation can be constructed based on the information obtained from a monitoring service (as we do for Planetlab), of synthetically as we are currently doing with BRITE.
• The Query network (also called the Virtual network or the Virtual Overlay) describes the overlay we want to create. Its specification is also a GraphML document containing the topology and attributes of the desired network.
• The Constraint Expression establishes the conditions to link the real and virtual networks. This expressions provides flexibility in specifiying how the attributes will be matched, for example certain attributes may allow for a range match, other may require that the mapping provides certain type of resource, and so on.
• The matching algorithm finds the mappings for the virtual network in the real network that satisfy both the topology and the attribute constraints. Currently we have two algorithms to perform this process. The first one is an improved Depth First Search with aggressive prunning. It main characteristic is that it is able to find all possible mappings for the given network. The other algorithm combines the prunning techniques of the previous with a randomized approach to obtain a single solution. Its performance is more deterministic and its memory requirements much lower. It can also search new mappings reusing the state information left by the previous execution, making it ideal for optimization applications.
• The mapping is the final result. The demos below illustrated present two representations of the mapping. The first one is a one-to-one set of tuples of the form { (v_i,r_i), ... }, i.e. the virtual nodes and their matching real nodes. The second representation is the one used by the search algorithms. It is a tree representing the set of matches available for each node. The structure of this tree is optimized in a way that minimizes its size and provides for efficient search methods.

Demos

To run the demos you need a recent version of the Java Runtime Environment and a supported browser. If you have problem running the demos, please refer to the troubleshooting page.

Planetlab

This demo illustrates the process of finding a set of sites that match a desired topology under some constraints. Currently available is the site topology consistent of 296 sites and the delays between these sites.

Go to Planetlab demo

Brite

Synthetic network topologies generated with BRITE. This synthetic networks very closely resemble the characteristics of the Internet. This demo illustrates the application of our algorithms on a very large network of 2000 nodes created with this tool.

Go to BRITE demo

Incremental updates

This demo illustrates the process of making updates on a mapping. Updates include adding/removing edges and nodes from the virtual network as well as changing their attributes. In many cases updates can be resolved quickly using the information of the previous search.

Note: In this demo, one must first import a complete virtual network (topo-6-10 in the provided examples) and then do updates on this virtual topology (extend-*, remove-* examples). The results will appear in both the mappings and the tree tabs... so please don't close them while doing updates.

Go to Incremental Updates demo

Publications

Sponsors:

	The netEmbed project is supported partially by a number of National Science Foundation grants, including CISE/CSR Award #0720604, ENG/EFRI Award #0735974, CISE/CNS Award #0524477, CNS/NeTS Award #0520166, CNS/ITR Award #0205294, and CISE/EIA RI Award #0202067.
	Disclaimer: Any opinions, findings, conclusions, or recommendations expressed in materials available from this site are those of their author(s) and do not necessarily reflect the views of Boston University or of the National Science Foundation.
	Jorge Londoño is supported in part by the Universidad Pontificia Bolivariana and COLCIENCIAS–Instituto Colombiano para el Desarrollo de la Ciencia y la Tecnología “Francisco José de Caldas"