Appears in:

CCR April 2008 Network virtualization is a powerful way to run multiple architectures or experiments simultaneously on a shared infrastructure. However, making efficient use of the underlying resources requires effective techniques for virtual network embedding—mapping each virtual network to specific nodes and links in the substrate network. Since the general embedding problem is computationally intractable, past research restricted the problem space to allow efficient solutions, or focused on designing heuristic algorithms. In this paper, we advocate a different approach: rethinking the design of the substrate network to enable simpler embedding algorithms and more efficient use of resources, without restricting the problem space. In particular, we simplify virtual link embedding by: i) allowing the substrate network to split a virtual link over multiple substrate paths and ii) employing path migration to periodically re-optimize the utilization of the substrate network. We also explore node-mapping algorithms that are customized to common classes of virtualnetwork topologies. Our simulation experiments show that path splitting, path migration, and customized embedding algorithms enable a substrate network to satisfy a much larger mix of virtual networks.

Public Review By:

Darryl Veitch

The reviewers were unanimous in their finding that there was worthwhile novel content in the paper, specifically the two specific substrate-network strategies that were discussed in detail: path splitting and path migration. This formed the basis of the success of the paper for CCR: the ideas are new and although there are many question left unanswered, the paper clearly demonstrated that they are worth considering. Another strength is the fact that several pertinent problems are tackled together, namely an `on-line' process of request arrivals and departures, subject to admission control, and with consideration for both node and link constraints. This set the problem in a somewhat realistic context, albeit highly simplified.

The bulk of the paper concerns path splitting in the substrate network. Based on small random networks, examples were given illustrating the potential for path splitting to find solutions for virtual network requests which would have otherwise been forbidden. This reflects the intuition that a new embedding requesting large chunks of CPU resources at nodes and/or link bandwidth may be impossible to directly satisfy for the substrate at a given time, yet possible at a finer granularity. Essentially, the jug fits more H2O as water than as large chunks of ice. The examples show that large performance gains are possible, however as the reviewers pointed out, there are significant costs involved in splitting which are not taken into account here. Furthermore, larger networks may effectively increase the severity of constraints, making it difficult to find suitable split paths. Much more work is needed to determine under what circumstances splitting wins the cost-benefit battle.

As a problem class embedding strategies lies on top of, and hence its success ultimately relies upon, adequate solutions to underlying traffic engineering problems which have defied general solution for a long time. If we still do not know how to design a single network marrying the benefits of IP networks as we know them today with controlled quality of service, even for a set of predefined static traffic classes, then doing so when virtualising arbitrary networks carrying arbitrary services is ambitious to say the least. The danger is that we may end up studying and solving some of the new problems specific to virtualisation, assuming solutions for underlying performance issues which do not in fact exist. Of course, this does not mean that the attempt should not be made, and this paper is a worthy contribution to that end.

Download:

PDF (282.7 KB) Share: