Yung Yi

Rethinking Virtual Network Embedding: Substrate Support for Path Splitting and Migration

By: 
Minlan Yu, Yung Yi, Jennifer Rexford, and Mung Chiang
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.

Public Review By: 
Darryl Veitch

The attractions of network virtualisation are clear: a flexible means for supporting networks of diverse nature, and for experimenting with network architectures, protocols, and user interactions, over a common physical infrastructure. This paper covers new ground in this young and challenging area by focussing attention on strategies the underlying substrate network can adopt to make the embedding of `virtual network requests’ more flexible, and therefore more efficient, seeking “..to make the substrate network more supportive of the VN embedding problem.” At this high level, an analogy can be made with an approach common in statistics, namely moving from a non-parametric framework, where the space of possible behaviours is too large to allow for universally optimal solutions, to a semi-parametric one, where broad decisions are made in advance which restrict this range, allowing typical variations to be accomodated simply by parameter fitting. This is a sensible approach when dealing with overwhelming possibilities and seems well suited to the embedding problem.
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.

Syndicate content