PolyViNE: policy-based virtual network embedding across multiple domains

Intra-domain virtual network embedding is a well-studied problem in the network virtualization literature. For most practical purposes, however, virtual networks (VNs) must be provisioned across heterogeneous administrative domains managed by multiple infrastructure providers (InPs).In this paper, we present PolyViNE, a policy-based inter-domain VN embedding framework that embeds end-to-end VNs in a decentralized manner. PolyViNE introduces a distributed protocol that coordinates the VN embedding process across participating InPs and ensures competitive prices for service providers (SPs), i.e., VN owners, while providing monetary incentives for InPs to participate in the process even under heavy competition. We also present a location-aware VN request forwarding mechanism – basd on a hierarchical addressing scheme (COST) and a location awareness protocol (LAP) – to allow faster embedding. We outline scalability and performance characteristics of PolyViNE through quantitative and qualitative evaluations.

Related papers:

title: Overcoming the Internet impasse through virtualization
abstract: The Internet architecture has proven its worth by the vast array of applications it now supports and the wide variety of network technologies over which it currently runs. Most current Internet research involves either empirical measurement studies or incremental modifications that can be deployed without major architectural changes. Easy access to virtual testbeds could foster a renaissance in applied architectural research that extends beyond these incrementally deployable designs.

title: Diversifying the Internet
abstract: The Internet has fallen victim to its own stunning success. The interplay of the end-to-end design of IP and the vested interests of competing stakeholders has led to its growing ossification. Alterations to the Internet architecture that address its fundamental deficiencies or enable new services have been restricted to incremental changes. The slow pace of this process stifles innovation and the adoption of disruptive technology. A recent call to arms advances a research agenda to confront this impasse through virtualization (L. Peterson et al., 2004). In addition to describing a virtual testbed for the evaluation of new network architectures, it poses a question about the long-term role of virtualization in the Internet. The architectural "purist" views virtualization as a tool for architecture evaluation and the periodic deployment of successive, singular Internet architectures. In this paper, we advance the "pluralist" view that seeks to make virtualization an architectural attribute of the Internet. By enabling a plurality of diverse network architectures to coexist on a shared physical substrate, virtualization mitigates the ossifying forces at work in the current Internet and enables continual introduction of innovative network technologies. Such a diversified Internet would allow existing architectural deficiencies to be holistically addressed as well as enable the introduction of new architectures supporting new types of applications and services. We provide a detailed exposition of the diversified Internet concept, explain how it can address the problem of network ossification and discuss some of the technical challenges that must be met to turn the vision into reality

title: How to lease the internet in your spare time
abstract: Today's Internet Service Providers (ISPs) serve two roles: managing their network infrastructure and providing (arguably limited) services to end users. We argue that coupling these roles impedes the deployment of new protocols and architectures, and that the future Internet should support two separate entities: infrastructure providers (who manage the physical infrastructure) and service providers (who deploy network protocols and offer end-to-end services). We present a high-level design for Cabo, an architecture that enables this separation; we also describe challenges associated with realizing this architecture.

title: A survey of network virtualization
abstract: Due to the existence of multiple stakeholders with conflicting goals and policies, alterations to the existing Internet architecture are now limited to simple incremental updates; deployment of any new, radically different technology is next to impossible. To fend off this ossification, network virtualization has been propounded as a diversifying attribute of the future inter-networking paradigm. By introducing a plurality of heterogeneous network architectures cohabiting on a shared physical substrate, network virtualization promotes innovations and diversified applications. In this paper, we survey the existing technologies and a wide array of past and state-of-the-art projects on network virtualization followed by a discussion of major challenges in this area.

title: Algorithms for Assigning Substrate Network Resources to Virtual Network Components
abstract: Recent proposals for network virtualization provide a promising way to overcome the Internet ossification. The key idea of network virtualization is to build a diversified Internet to support a variety of network services and architectures through a shared substrate. A major challenge in network virtualization is the assigning of substrate resources to virtual networks (VN) efficiently and on-demand. This paper focuses on two versions of the VN assignment problem: VN assignment without reconfiguration (VNA-I) and VN assignment with reconfiguration (VNAII). For the VNA-I problem, we develop a basic scheme as a building block for all other advanced algorithms. Subdividing heuristics and adaptive optimization strategies are then presented to further improve the performance. For the VNA-II problem, we develop a selective VN reconfiguration scheme that prioritizes the reconfiguration of the most critical VNs. Extensive simulation experiments demonstrate that the proposed algorithms can achieve good performance under a wide range of network conditions.

title: Rethinking virtual network embedding: substrate support for path splitting and migration
abstract: 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 virtual-network 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

title: Efficient Mapping of Virtual Networks onto a Shared Substrate
abstract: Virtualization has been proposed as a vehicle for overcoming the growing problem of internet ossification . This paper studies the problem of mapping diverse virtual networks onto a common physical substrate. In particular, we develop a method for mapping a virtual network onto a substrate network in a cost-efficient way, while allocating sufficient capacity to virtual network links to ensure that the virtual network can handle any traffic pattern allowed by a general set of traffic constraints. Our approach attempts to find the best topology in a family of backbone-star topologies, in which a subset of nodes constitute the backbone, and the remaining nodes each connect to the nearest backbone node. We investigate the relative cost-effectiveness of different backbone topologies on different substrate networks, under a wide range of traffic conditions. Specifically, we study how the most cost-effective topology changes as the tightness of pairwise traffic constraints and the constraints on traffic locality are varied. In general, we find that as pairwise traffic constraints are relaxed, the least-cost backbone topology becomes increasingly “tree-like”. We also find that the cost of the constructed virtual networks is usually no more than 1.5 times a computed lower bound on the network cost and that the quality of solutions improves as the traffic locality gets weaker.

title: Virtual Network Embedding with Coordinated Node and Link Mapping
abstract: Recently network virtualization has been proposed as a promising way to overcome the current ossification of the Internet by allowing multiple heterogeneous virtual networks (VNs) to coexist on a shared infrastructure. A major challenge in this respect is the VN embedding problem that deals with efficient mapping of virtual nodes and virtual links onto the substrate network resources. Since this problem is known to be NP-hard, previous research focused on designing heuristic-based algorithms which had clear separation between the node mapping and the link mapping phases. This paper proposes VN embedding algorithms with better coordination between the two phases. We formulate the VN em- bedding problem as a mixed integer program through substrate network augmentation. We then relax the integer constraints to obtain a linear program, and devise two VN embedding algo- rithms D-ViNE and R-ViNE using deterministic and randomized rounding techniques, respectively. Simulation experiments show that the proposed algorithms increase the acceptance ratio and the revenue while decreasing the cost incurred by the substrate network in the long run.

title: A virtual network mapping algorithm based on subgraph isomorphism detection
abstract: Assigning the resources of a virtual network to the components of a physical network, called Virtual Network Mapping, plays a central role in network virtualization. Existing approaches use classical heuristics like simulated annealing or attempt a two stage solution by solving the node mapping in a first stage and doing the link mapping in a second stage.
 The contribution of this paper is a Virtual Network Mapping (VNM) algorithm based on subgraph isomorphism detection: it maps nodes and links during the same stage. Our experimental evaluations show that this method results in better mappings and is faster than the two stage approach, especially for large virtual networks with high resource consumption which are hard to map.

title: iMark: An identity management framework for network virtualization environment
abstract: In recent years, network virtualization has been propounded as an open and flexible future internetworking paradigm that allows multiple virtual networks (VNs) to co-exist on a shared physical substrate. Each VN in a network virtualization environment (NVE) is free to implement its own naming, addressing, routing, and transport mechanisms. While such flexibility allows fast and easy deployment of diversified applications and services, ensuring end-to-end communication and universal connectivity poses a daunting challenge. This paper advocates that effective and efficient management of heterogeneous identifier spaces is the key to solving the problem of end-to-end connectivity in an NVE. We propose iMark, an identity management framework based on a global identity space, which enables end hosts to communicate with each other within and outside of their own networks through a set of controllers, adapters, and well-placed mappings without sacrificing the autonomy of the concerned VNs. We describe the procedures that manipulate these mappings between different identifier spaces and provide performance evaluation of the proposed framework.

title: iREX: efficient automation architecture for the deployment of inter-domain QoS policy
abstract: The inter-domain resource exchange (iREX) architecture uses economic market mechanisms to automate the ad-hoc negotiation and deployment of end to end inter-domain quality of service policy among resource consumer and resource provider . In this paper, we explore iREX's network load distribution by comparing its performance to a lower bound for network congestion in two ways. We first present an analytical model of iREX in terms of an online algorithm and analyze its efficiency via competitive analysis. Our main result shows that the efficiency loss of iREX with respect to monetary cost is upper-bounded by a factor of 8 K/2 K+1, where K s the number of deployments, provided affine linear price functions are used. When the price functions are used to model congestion in the network, this result implies upper bounds on the efficiency loss of iREX with respect to network congestion. We then complement the analytical model with a numerical study using simulations.with optimal solutions derived from unsplittable and splittable multi-commodity flow optimization models. Our numerical results show that for nominal to high traffic loads of 40% or more, iREX deviates a maximum of about 20% from the lower bound, while the current method deviates a maximum of 300%.

title: Incorporating Trust in Network Virtualization
abstract: In this paper, we propose a trust management framework for network virtualization environments. The proposed framework helps distinguish among the infrastructure providers based on their past experiences and feedbacks from service providers. We describe the main components involved in gathering the feedbacks and managing the reputation data. We detail the proposed trust system and we define the concept of Degree of Involvement of an infrastructure provider in terms of nodes and links. We also perform a mathematical analysis of the proposed system. Simulation results confirm the effectiveness of the proposed trust management system in increasing the service providers' satisfaction and reducing the selection of infrastructure providers that do not fulfill their Service Level Agreement (SLA).

title: Geographically Informed Inter-Domain Routing
abstract: In this paper we propose a new routing protocol and address scheme, geographically informed inter-domain routing (GIRO). GIRO departs from previous geographic addressing proposals in that it uses geographic information to assist, not to replace, the provider-based IP address allocation and policy-based routing. We show that, by incorporating geographic information into the IP address structure, GIRO can significantly improve the scalability and performance of the global Internet routing system. Within the routing policy constraints, geographic information enables the selection of shortest available routing paths. We evaluate GIRO'S performance through simulations using a Rocketfuel-measured Internet topology. Our results show that, compared to the current practice, GIRO can reduce the geographic distance for 70% of the existing BGP paths, and the reduction is more than 40% for about 20% of the paths. Furthermore, encoding geographic information into IP addresses also enables GIRO to apply geographical route aggregation, and a combination of geographic and topological aggregation can lead to 75% reduction of the current BGP routing table size.

title: Experiences applying game theory to system design
abstract: We applied techniques from game theory to help formulate and analyze solutions to two systems problems: discouraging selfishness in multi-hop wireless networks and enabling cooperation among ISPs in the Internet. It proved difficult to do so. This paper reports on our experiences and explains the issues that we encountered. It describes the ways in which the straightforward use of results from traditional game theory did not fit well with the requirements of our problems. It also identifies an important characteristic of the solutions we did eventually adopt that distinguishes them from those available using game theoretic approaches. We hope that this discussion will help to highlight formulations of game theory which are well-suited for problems involving computer systems.

title: Multi-provider service negotiation and contracting in network virtualization
abstract: Network virtualization environment (VNE) affords great business flexibility to the customers and the providers as multiple providers can jointly support a customer's virtual network. Under the current network model, a group of Infrastructure Providers (InPs) peer with each other to provide a packaged deal. Such a business arrangement is not customer-driven, does not promote fair market competition and does not ensure cost minimization. Furthermore, the on-demand nature of virtual networks requires efficient and automated service negotiation and contracting. In this paper, we present V-Mart. To the InPs, V-Mart offers an environment to participate in a faithful and fair competition over the VN resources; and to the SPs, it offers a customer-driven virtual resource partitioning and contracting engine. V-Mart uses a two-stage Vickrey auction model that is strategy-proof, flexible to diverse InP pricing models, and functions over heterogenous multi-commodity market that characterizes the NVE. Through analysis and simulation we show the flexibility and effectiveness of V-Mart.

title: Distributed inter-domain lightpath provisioning in the presence of wavelength conversion
abstract: Dense wavelength division multiplexing (DWDM) has become the dominant transport layer technology for next-generation backbone networks due to its unprecedented capacity scalability. As a result, there is a pressing need to investigate lightpath provisioning in multi-domain DWDM networks. Although inter-domain provisioning has been well-studied for packet/cell-switching networks, the wavelength dimension (along with wavelength conversion) presents many added challenges. To address these concerns, a detailed GMPLS-based hierarchical routing framework for provisioning transparent/translucent/opaque multi-domain DWDM networks is presented. The scheme adapts topology abstraction to hide internal domain state so as to resolve routing scalability and security issues. Specifically a novel full-mesh topology abstraction scheme is developed for full wavelength conversion domains, i.e., to disseminate additional wavelength converter state. Related inter-domain lightpath RWA and signaling schemes are also tabled. Performance analysis results are then presented to demonstrate the effectiveness of the proposed mechanisms along with directions for future research work.

title: Lightpaths on demand: a Web-services-based management system
abstract: User-controlled optical networks play a key role in supporting electronic transfer of the enormous volumes of data generated in emerging e-science experiments. The ability of users to manage their own resources enables provisioning of bandwidth-guaranteed tunnels on demand without the costs associated with conventional managed services offered by network providers. However, building high-performance user-controlled networks has only become feasible in the last few years, as trends in the telecommunications industry have made it possible for users to purchase installed optical fiber and light it using their own premises equipment. Consequently, suitable network management technologies have not yet evolved. In particular, there is presently no means for users to easily provision bandwidth-guaranteed tunnels across multiple independent management domains. In this article we present a user-controlled lightpath management system that addresses this problem. We begin by reviewing the high-level functionality of the system. Then we examine the software architecture. Finally, we discuss design challenges faced while building the system and propose future extensions.

title: QoS-aware service composition and adaptation in autonomic communication
abstract: Advents in network technology and distributed system design have propelled network communication service beyond best effort data delivery. With the rising complexity of network infrastructures and the need for on-demand provisioning operations, a high degree of self-sufficiency and automation is required in the network service infrastructure. Guided by the autonomic communication principle, this paper first presents an autonomic service provisioning framework for establishing quality-of-service (QoS)-assured end-to-end communication paths across administratively independent domains. Through graph abstraction, we show that the domain composition and adaptation problem could be reduced to the classic k-multiconstrained optimal path (MCOP) problem. In analyzing existing k-MCOP solutions, we show their inefficiencies when applied to the service provisioning context and establish a number of new domain composition and adaptation algorithms. These new algorithms are designed for the self-configuration, self-optimization, and self-adaptation of end-to-end network communications and can provide hard QoS guarantees over domains with relative QoS differentiations. Through in-depth experimentations, we compare the performance of our algorithms with classic k-MCOP solutions and demonstrate the effectiveness of our approach.

title: Application and Use of the IPv6 Provider Independent Global Unicast Address Format
abstract: This document discusses the expected use of the Provider Independent
address format discussed in the companion document GEO  in the
Internet. Several parties have expressed interest in using this
approach as a good fit for managing their networks. With the long
timeframe that the shim6 effort will take, this approach provides a
scalable multi-homing approach for use in the interim. In addition to
covering implementations where it adds value in managing the growth of
the Internet routing tables, the document will discuss implementations
that should be avoided due to the negative impact on the routing
tables.