Mung Chiang

How to Bid the Cloud

Liang Zheng, Carlee Joe-Wong, Chee Wei Tan, Mung Chiang, Xinyu Wang
Appears in: 
CCR August 2015

Amazon's Elastic Compute Cloud (EC2) uses auction based spot pricing to sell spare capacity, allowing users to bid for cloud resources at a highly reduced rate. Amazon sets the spot price dynamically and accepts user bids above this price. Jobs with lower bids (including those already running) are interrupted and must wait for a lower spot price before resuming. Spot pricing thus raises two basic questions: how might the provider set the price, and what prices should users bid?

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

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 “ 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.

Don't Optimize Existing Protocols, Design Optimizable Protocols

Jiayue He, Jennifer Rexford, and Mung Chiang
Appears in: 
CCR July 2007

As networks grow in size and complexity, network management has become an increasingly challenging task. Many protocols have tunable parameters, and optimization is the process of setting these parameters to optimize an objective. In recent years, optimization techniques have been widely applied to network management problems, albeit with mixed success.

Syndicate content