计算机科学与技术（参考文献）An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks

2012 Proceedings IEEE INFOCOM An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks Sheng Zhang',Zhuzhong Qian',Jie Wu,and Sanglu Lu' State Key Lab.for Novel Software Technology,Nanjing University,China Department of Computer and Information Sciences,Temple University,USA zhangsheng @dislab.nju.edu.cn,(qzz,sanglu)@nju.edu.cn,jiewu@temple.edu Abstract-Network virtualization provides a promising way resources are utilized in an efficient and effective manner.As to overcome Internet ossification.A major challenge is virtual this problem is proven to be NP-complete [5],many heuristic network mapping,i.e,how to embed multiple virtual network algorithms [6-15]have been proposed. requests with resource constraints into a substrate network,such that physical resources are utilized in an efficient and effective However,these early algorithms did not take workload manner.Since this problem is known to be NP-complete,a variety fluctuation,e.g.,Auckland Data Trace [16],into consideration. of heuristic algorithms have been proposed.In this paper,we re- Most web-based service providers potentially target users all examine this problem and propose a virtual network mapping over the world,so it is extremely difficult to predict the framework,ORSTA,which is based on Opportunistic Resource workload before they are ready to serve end users.To cope Sharing and Topology-Aware node ranking.Opportunistic re- source sharing is taken into consideration at the entire network with a peak workload on demand,service providers often over- level for the first time and we develop an online approxima- purchase physical resources,which may lead to a considerable tion algorithm,FFA,for solving the corresponding time slot waste of resources for a normal workload.What is more assignment problem.To measure the topology importance of infrastructure providers may lose some upcoming customers a substrate node,a node ranking method,MCRank,based on due to inefficient resource utilization Markov chain is presented.We also devise a simple and practical method to estimate the residual resource of a substrate node/link. In this paper,we re-examine the virtual network mapping Extensive simulation experiments demonstrate that the proposed problem through two novel aspects,Opportunistic Resource framework enables the substrate network to achieve efficient Sharing and Topology-Aware node ranking,and we propose a physical resource utilization and to accept many more virtual novel framework,ORSTA,which provides efficient physical network requests over time. resource utilization and deployment. Index Terms-virtual network mapping;opportunistic re- source sharing;bin packing;topology-aware;markov chain Inspired by opportunistic spectrum access [17],we envision opportunistic resource sharing.Generally speaking,we model the workload in a virtual network as the combination of a I.INTRODUCTION basic sub-workload,which always exists,and a variable sub- The Internet has been extremely successful in optimizing workload,which occurs with some probability.Then,multiple the way we exchange and process information.However,due variable sub-workloads from different virtual networks are to the competing policies and interests of its stakeholders allowed to share some common resources to achieve efficient and the ever-expanding scale of Internet use,the Internet resource utilization,while for a basic sub-workload,we allo- has become resistant to fundamental changes [1,2].Network cate the corresponding,required resources as usual. virtualization has been proposed as a promising approach that Furthermore,topology-awareness is considered due to the claims to overcome the current ossification of the Internet following fact:suppose that there are two substrate nodes with [1-4].In a network virtualization environment,infrastructure the same residual CPU resources,but the residual resources providers (InPs)maintain physical/substrate networks (SNs). on their neighbors vary a lot.It is then reasonable to choose while service providers (SPs)purchase slices of physical the substrate node with more resources in its proximity,so as resources (e.g.,CPU,bandwidth,memory space,disk storage) to heuristically reduce the length of embedded virtual links. from InPs and then create customized virtual networks (VNs)Hence,to facilitate the efficient embedding of virtual networks to offer their own value-added services to end users.This we develop a Markov Chain-based substrate node ranking decoupling of traditional Internet service providers brings a algorithm to measure the "importance"of each substrate node layered service architecture,which provides flexibility and by assigning a numerical value. diversity to everyone. The contributions of this paper are the following.(i)To the One of the fundamental problems in network virtualization best of our knowledge,this is the first attempt that consid- is the virtual network embedding/mapping (VNE)problem, ers virtual network mapping in the context of opportunistic i.e.,how to embed multiple virtual network requests with re- resource sharing at the entire network level.In our previous source constraints into a substrate network,such that physical work [18],we only considered how to share bandwidth among 978-1-4673-0775-8/12/$31.00©20121EEE 2408

An Opportunistic Resource Sharing and Topology-Aware Mapping Framework for Virtual Networks Sheng Zhang† , Zhuzhong Qian† , Jie Wu‡ , and Sanglu Lu† † State Key Lab. for Novel Software Technology, Nanjing University, China ‡ Department of Computer and Information Sciences, Temple University, USA † zhangsheng@dislab.nju.edu.cn, {qzz,sanglu}@nju.edu.cn, ‡ jiewu@temple.edu Abstract—Network virtualization provides a promising way to overcome Internet ossification. A major challenge is virtual network mapping, i.e., how to embed multiple virtual network requests with resource constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. Since this problem is known to be NP-complete, a variety of heuristic algorithms have been proposed. In this paper, we re￾examine this problem and propose a virtual network mapping framework, ORS T A, which is based on Opportunistic Resource Sharing and Topology-Aware node ranking. Opportunistic re￾source sharing is taken into consideration at the entire network level for the first time and we develop an online approxima￾tion algorithm, FFA, for solving the corresponding time slot assignment problem. To measure the topology importance of a substrate node, a node ranking method, MCRank, based on Markov chain is presented. We also devise a simple and practical method to estimate the residual resource of a substrate node/link. Extensive simulation experiments demonstrate that the proposed framework enables the substrate network to achieve efficient physical resource utilization and to accept many more virtual network requests over time. Index Terms—virtual network mapping; opportunistic re￾source sharing; bin packing; topology-aware; markov chain I. Introduction The Internet has been extremely successful in optimizing the way we exchange and process information. However, due to the competing policies and interests of its stakeholders and the ever-expanding scale of Internet use, the Internet has become resistant to fundamental changes [1, 2]. Network virtualization has been proposed as a promising approach that claims to overcome the current ossification of the Internet [1–4]. In a network virtualization environment, infrastructure providers (InPs) maintain physical/substrate networks (SNs), while service providers (SPs) purchase slices of physical resources (e.g., CPU, bandwidth, memory space, disk storage) from InPs and then create customized virtual networks (VNs) to offer their own value-added services to end users. This decoupling of traditional Internet service providers brings a layered service architecture, which provides flexibility and diversity to everyone. One of the fundamental problems in network virtualization is the virtual network embedding/mapping (VNE) problem, i.e., how to embed multiple virtual network requests with re￾source constraints into a substrate network, such that physical resources are utilized in an efficient and effective manner. As this problem is proven to be NP-complete [5], many heuristic algorithms [6–15] have been proposed. However, these early algorithms did not take workload fluctuation, e.g., Auckland Data Trace [16], into consideration. Most web-based service providers potentially target users all over the world, so it is extremely difficult to predict the workload before they are ready to serve end users. To cope with a peak workload on demand, service providers often over￾purchase physical resources, which may lead to a considerable waste of resources for a normal workload. What is more, infrastructure providers may lose some upcoming customers due to inefficient resource utilization. In this paper, we re-examine the virtual network mapping problem through two novel aspects, Opportunistic Resource Sharing and Topology-Aware node ranking, and we propose a novel framework, ORS T A, which provides efficient physical resource utilization and deployment. Inspired by opportunistic spectrum access [17], we envision opportunistic resource sharing. Generally speaking, we model the workload in a virtual network as the combination of a basic sub-workload, which always exists, and a variable sub￾workload, which occurs with some probability. Then, multiple variable sub-workloads from different virtual networks are allowed to share some common resources to achieve efficient resource utilization, while for a basic sub-workload, we allo￾cate the corresponding, required resources as usual. Furthermore, topology-awareness is considered due to the following fact: suppose that there are two substrate nodes with the same residual CPU resources, but the residual resources on their neighbors vary a lot. It is then reasonable to choose the substrate node with more resources in its proximity, so as to heuristically reduce the length of embedded virtual links. Hence, to facilitate the efficient embedding of virtual networks, we develop a Markov Chain-based substrate node ranking algorithm to measure the “importance” of each substrate node by assigning a numerical value. The contributions of this paper are the following. (i) To the best of our knowledge, this is the first attempt that consid￾ers virtual network mapping in the context of opportunistic resource sharing at the entire network level. In our previous work [18], we only considered how to share bandwidth among 2012 Proceedings IEEE INFOCOM 978-1-4673-0775-8/12/$31.00 ©2012 IEEE 2408

multiple virtual links in a single substrate link.(ii)We propose In general,although opportunistic resource sharing brings a formal formulation of opportunistic resource sharing-based performance degradation when virtual networks encounter time slot assignment and develop an online approximation a peak workload,it enables better utilization of physical solution,FFA.(iii)We take topology into consideration and resources,increases the InPs'revenue and decreases the SPs' design a Markov chain-based node ranking method,MCRank, rent.We believe that opportunistic resource sharing can benefit to measure the "importance"of a substrate node.(iv)A simple all parties through reasonable pricing.We will not discuss how and practical method for estimating the residual resource of to set prices in this paper as it is out of the scope. a substrate node/link is devised.(v)Extensive simulations validate the effectiveness of ORS TA. III.PROBLEM FORMULATION The remainder of this paper is organized as follows.Sec- A.Assumptions tion II presents our motivation.We describe the assumptions, CPU and bandwidth are the main constraints we consider notations,and problem formulation in Section III.Then in in this paper,which is the typical case in almost all of the Sections IV and V,we give an overview of ORSTA and related literatures [6-15]on virtual network mapping so far. detailed algorithms,respectively.We evaluate ORSTA using To unify the resource notations,we assume that the substrate experiments in Section VI.Before concluding this paper in network is based on time division multiplexing,where time Section VIII,we survey related work in Section VII. is partitioned into multiple frames of equal length,and each II.MOTIVATION frame is further divided into L equal time slots,tsi,ts2.....tsL. In this way,both CPU and bandwidth can be expressed in SPs lease physical resources from InPs to create their own time slots.An SP only needs to specify the number of the virtual networks and deploy services aimed at end users.As time slots for a particular virtual node/link when he makes a we mentioned before,SPs over-purchase resources to cater request for virtual network mapping.Therefore,we will only for potentially high workload rates,otherwise,customers will focus on opportunistic bandwidth sharing in Section V-A;the suffer bad experiences when SPs purchase no more than basic results can be directly applied to opportunistic CPU sharing resources.In doing so,SPs may waste the additional purchased without any major changes. resources due to traffic fluctuation.From the perspective of an SPs deploy end-to-end value-added services aimed at the InP,the physical resources he owns are limited and constant end users,who access the services and leave at any time. in a relatively long period,so he may wish to make efficient These dynamic customers lead to workload fluctuations and use of his resources and accept more virtual networks,which further cause a waste of physical resources.As it is difficult allows for more revenue. to capture the characteristics of workload fluctuation,we use A motivational example is illustrated as follows.Suppose a simplified model:the work load wli of virtual network i that an infrastructure provider,InP-A,owns a physical link is composed of a basic sub-workload basici,which exists with a capacity of 10MB/s,and all of the other service all of the time,and a variable sub-workload variai,which providers,SP-1,SP-2 and SP-3,require a virtual link with occurs with a small probability pwli in unit time.We let a capacity of 4MB/s.We assume that InP-A charges I dollar bwl;=basici/wl;represent basic sub-workload percentage. for 1MB/s bandwidth in unit time.In the case without oppor- Workloads in different virtual networks are assumed to be tunistic resource sharing,InP-A can accept only two requests independent of each other. among three because 4MB/s *3 12MB/s 10MB/s. We believe that this model is reasonable although it is Therefore,InP-A gets 8 dollars per unit time in this case. simple.For example,in a layered video streaming service Let us take network traffic fluctuation into consideration and [19],each video frame is encoded into multiple video packets assume that each 4MB/s traffic flow is composed of a basic corresponding to multiple quality layers.These video packets sub-flow 3MB/s,which always exists,and a variable sub-flow are classified as a base or enhancement layer to meet different 1MB/s,which occurs with probability 0.1.Now,InP-A has an network conditions.The workload in this scenario is very allocation method to accept all three virtual links:by letting similar to our model.We hope that this simplified model can three variable sub-flows share the same 1MB/s and allocating provide some insights on the design of other VNE algorithms. the residual 9MB/s to three basic sub-flows.We assume that Since both the network traffic and CPU time will fluctuate flows in different virtual links are independent of each other, as the workload fluctuates,both the amounts of network flow which is reasonable,thus the probability that more than two in a virtual link and the CPU time in a virtual node are variable sub-flows occur (a collision)is: assumed to be proportional to the workload for simplicity. 1-(0.9*0.9*0.9+3*0.9*0.9*0.1)=0.109 More specifically,the flow in a virtual link is composed of a basic part,whose percentage is bwli,and a variable part, For variable sub-flows,InP-A should decrease the charge,e.g., which occurs with probability pwli.And the same statement 0.1 US dollar for 1MB/s in unit time.Therefore,in this case holds for the CPU time. with opportunistic resource sharing,InP-A can get (3+0.1)* 3=9.3 dollars,which is more than the original income;SP-1 B.Notations or SP-2 or SP-3 just needs to pay 3+0.1=3.1 dollars,which Substrate Network:a substrate network is modeled as a is less than the previous charge of 4 dollars. weighted undirected graph,Gs =(Ns,Es,Cs,B),where Ns 2409

multiple virtual links in a single substrate link. (ii) We propose a formal formulation of opportunistic resource sharing-based time slot assignment and develop an online approximation solution, FFA. (iii) We take topology into consideration and design a Markov chain-based node ranking method, MCRank, to measure the “importance” of a substrate node. (iv) A simple and practical method for estimating the residual resource of a substrate node/link is devised. (v) Extensive simulations validate the effectiveness of ORS T A. The remainder of this paper is organized as follows. Sec￾tion II presents our motivation. We describe the assumptions, notations, and problem formulation in Section III. Then in Sections IV and V, we give an overview of ORS T A and detailed algorithms, respectively. We evaluate ORS T A using experiments in Section VI. Before concluding this paper in Section VIII, we survey related work in Section VII. II. Motivation SPs lease physical resources from InPs to create their own virtual networks and deploy services aimed at end users. As we mentioned before, SPs over-purchase resources to cater for potentially high workload rates, otherwise, customers will suffer bad experiences when SPs purchase no more than basic resources. In doing so, SPs may waste the additional purchased resources due to traffic fluctuation. From the perspective of an InP, the physical resources he owns are limited and constant in a relatively long period, so he may wish to make efficient use of his resources and accept more virtual networks, which allows for more revenue. A motivational example is illustrated as follows. Suppose that an infrastructure provider, InP-A, owns a physical link with a capacity of 10MB/s, and all of the other service providers, SP-1, SP-2 and SP-3, require a virtual link with a capacity of 4MB/s. We assume that InP-A charges 1 dollar for 1MB/s bandwidth in unit time. In the case without oppor￾tunistic resource sharing, InP-A can accept only two requests among three because 4MB/s ∗ 3 = 12MB/s > 10MB/s. Therefore, InP-A gets 8 dollars per unit time in this case. Let us take network traffic fluctuation into consideration and assume that each 4MB/s traffic flow is composed of a basic sub-flow 3MB/s, which always exists, and a variable sub-flow 1MB/s, which occurs with probability 0.1. Now, InP-A has an allocation method to accept all three virtual links: by letting three variable sub-flows share the same 1MB/s and allocating the residual 9MB/s to three basic sub-flows. We assume that flows in different virtual links are independent of each other, which is reasonable, thus the probability that more than two variable sub-flows occur (a collision) is: 1 − (0.9 ∗ 0.9 ∗ 0.9 + 3 ∗ 0.9 ∗ 0.9 ∗ 0.1) = 0.109 For variable sub-flows, InP-A should decrease the charge, e.g., 0.1 US dollar for 1MB/s in unit time. Therefore, in this case with opportunistic resource sharing, InP-A can get (3 + 0.1) ∗ 3 = 9.3 dollars, which is more than the original income; SP-1 or SP-2 or SP-3 just needs to pay 3+0.1=3.1 dollars, which is less than the previous charge of 4 dollars. In general, although opportunistic resource sharing brings performance degradation when virtual networks encounter a peak workload, it enables better utilization of physical resources, increases the InPs’ revenue and decreases the SPs’ rent. We believe that opportunistic resource sharing can benefit all parties through reasonable pricing. We will not discuss how to set prices in this paper as it is out of the scope. III. Problem Formulation A. Assumptions CPU and bandwidth are the main constraints we consider in this paper, which is the typical case in almost all of the related literatures [6–15] on virtual network mapping so far. To unify the resource notations, we assume that the substrate network is based on time division multiplexing, where time is partitioned into multiple frames of equal length, and each frame is further divided into L equal time slots, ts1, ts2, ..., tsL. In this way, both CPU and bandwidth can be expressed in time slots. An SP only needs to specify the number of the time slots for a particular virtual node/link when he makes a request for virtual network mapping. Therefore, we will only focus on opportunistic bandwidth sharing in Section V-A; the results can be directly applied to opportunistic CPU sharing without any major changes. SPs deploy end-to-end value-added services aimed at the end users, who access the services and leave at any time. These dynamic customers lead to workload fluctuations and further cause a waste of physical resources. As it is difficult to capture the characteristics of workload fluctuation, we use a simplified model: the work load wli of virtual network i is composed of a basic sub-workload basici , which exists all of the time, and a variable sub-workload variai , which occurs with a small probability pwli in unit time. We let bwli = basici/wli represent basic sub-workload percentage. Workloads in different virtual networks are assumed to be independent of each other. We believe that this model is reasonable although it is simple. For example, in a layered video streaming service [19], each video frame is encoded into multiple video packets corresponding to multiple quality layers. These video packets are classified as a base or enhancement layer to meet different network conditions. The workload in this scenario is very similar to our model. We hope that this simplified model can provide some insights on the design of other VNE algorithms. Since both the network traffic and CPU time will fluctuate as the workload fluctuates, both the amounts of network flow in a virtual link and the CPU time in a virtual node are assumed to be proportional to the workload for simplicity. More specifically, the flow in a virtual link is composed of a basic part, whose percentage is bwli , and a variable part, which occurs with probability pwli . And the same statement holds for the CPU time. B. Notations Substrate Network: a substrate network is modeled as a weighted undirected graph, G s = (N s , E s ,C s , B s ), where N s 2409

VN request G'r TABLE I bm,=09,pW,=0.t 18 Substrate network sn NOTATIONS IN THIS PAPER 108 Notation Meaning 20 15 8 17 12 G Substrate network 10 W Set of nodes b Set of links 7 7 Cs Set of CPU capacity attributes 12 B Set of bandwidth capacity attributes VN request G'2 RC* Set of residual CPU resources bwW2-0.8pwW20.2 12 9 RB Set of residual bandwidth resources 12 15 P Loop-free paths set 9 7 10 G The i virtual network Set of nodes of Gy Fig.1.Notations of virtual network embedding Set of links of G Set of CPU constraints in G 吲 Set of bandwidth constraints in G? is the set of substrate nodes,and Es is the set of substrate bwl A basic sub-workload percentage in G? links.Cs is the set of CPU capacity attributes,and Bs is pwl Probability of a variable sub-workload in G the set of bandwidth capacity attributes.We use RC"(n)and RB"(e)to denote the residual CPU of substrate node ns and residual bandwidth of substrate link e,respectively.Here,we (CB,BE],(bc)(ED),(ca)(DC)).The node mapping for would mention that the amount of residual resources in the the VN request G is (dA,eF),and the link mapping presence of opportunistic resource sharing is not obvious,we is{(de)→{AG,GF. will discuss it later when necessary.We use ps to denote the C.Objective set of loop-free paths in Gs. Virtual Network:we denote a virtual network by a Virtual network mapping is done by InPs.From InPs' weighted undirected graph,G=(N,E,C,B:,bwli,pwli). standpoint,a natural objective is to increase revenue and to N is the set of virtual nodes,and E is the set of virtual decrease cost.However,an SP is only willing to pay fee links.C is the set of CPU constraints,and B"is the set proportional to his requested resources,that is,the revenue, of bandwidth constraints.bwl;represents the percentage of R(G:),of embedding a virtual network,G',can be defined as a basic sub-workload in an overall workload.pwl;means the (following the definitions in previous works [8,10]): probability of a variable sub-workload occurring in unit time. R(G)=we· (1) The notations are summarized in Table I for reference.The ∑c+ws·∑e notation system in this paper is similar to that in [8,10,20]. The principle behind these notations is that superscript indi- where @c and are the weights for CPU and bandwidth, respectively.We learn from this definition that,given a VN cates substrate/virtual networks. Fig.1 shows an example of these notations.The corre- request,the revenue is fixed.Therefore,in order to get more sponding number near each vertex/edge is the CPU/bandwidth revenue,the InP should try to accept more VN requests but capacity/constraint.For virtual link a-b in the VN request meet their resource constraints at the same time. G',the basic sub-traffic is 8*0.9 =7.2,the variable sub-traffic To this end,virtual networks should be properly and effi- is 8-7.2=0.8 and occurs with probability 0.1. ciently deployed on top of a substrate network.Due to the Virtual Network Mapping:virtual network mapping is NP-completeness of the VNE problem [5],many heuristic usually defined as a mapping M from G?to a subset of Gs, algorithms have been proposed.However,in this paper we such that some predefined constraints are satisfied.It can be re-visit this problem from two novel aspects:opportunistic decomposed into two major components:node mapping M resource sharing and topology-aware node mapping. and link mapping M. IV.FRAMEWORK OVERVIEW The node mapping Mn:NNs maps a virtual node to We present a high level overview of our framework. a substrate node,subject to:Vn",mE Ny ORS TA,as illustrated in Algorithm 1,in this section and the Mn(n')∈Ns details of ORSTA in the next section. Mn(n)=M(m")iff m"n" Initially,we compute the amount of residual resources for each substrate node/link (lines 3-4 of Alg.1),i.e.,the available RC5(Mn(n)≥Cn) CPU/bandwidth capacity.Note that,when we perform oppor- The link mapping M Eps maps a virtual link to a tunistic resource sharing,the estimation of residual resources substrate loop-free path,subject to:Ve"=(m'n")EE" becomes complicated;we will explain our method in Sec- Mi(m'n")EP (M(m"),Ma(n")) tion V-B.Afterwards,inspired by the PageRank algorithm [21] which is used by Google to assign a numerical rank to every RB'(M(m'n')≥B(e) web page,we devise a similar ranking algorithm based on In Fig.1,the node mapping for the VN request G is Markov chain [22]to compute the rank of each substrate node, (aC,bE,cDl,and the link mapping is ((ab)denoted by MCRank (line 5 of Alg.1),which is illustrated 2410

Fig. 1. Notations of virtual network embedding is the set of substrate nodes, and E s is the set of substrate links. C s is the set of CPU capacity attributes, and B s is the set of bandwidth capacity attributes. We use RCs (n s ) and RBs (e s ) to denote the residual CPU of substrate node n s and residual bandwidth of substrate link e s , respectively. Here, we would mention that the amount of residual resources in the presence of opportunistic resource sharing is not obvious, we will discuss it later when necessary. We use P s to denote the set of loop-free paths in G s . Virtual Network: we denote a virtual network by a weighted undirected graph, G v i = (N v i , E v i ,C v i , B v i , bwli , pwli) . N v i is the set of virtual nodes, and E v i is the set of virtual links. C v i is the set of CPU constraints, and B v i is the set of bandwidth constraints. bwli represents the percentage of a basic sub-workload in an overall workload . pwli means the probability of a variable sub-workload occurring in unit time. The notations are summarized in Table I for reference. The notation system in this paper is similar to that in [8, 10, 20]. The principle behind these notations is that superscript indi￾cates substrate/virtual networks. Fig. 1 shows an example of these notations. The corre￾sponding number near each vertex/edge is the CPU/bandwidth capacity/constraint. For virtual link a − b in the VN request G v 1 , the basic sub-traffic is 8∗0.9 = 7.2, the variable sub-traffic is 8 − 7.2 = 0.8 and occurs with probability 0.1. Virtual Network Mapping: virtual network mapping is usually defined as a mapping M from G v i to a subset of G s , such that some predefined constraints are satisfied. It can be decomposed into two major components: node mapping Mn and link mapping Ml . The node mapping Mn : N v i → N s maps a virtual node to a substrate node, subject to: ∀n v , m v ∈ N v i Mn(n v ) ∈ N s Mn(n v ) = Mn(m v ) iff m v = n v RCs (Mn(n v )) ≥ C v i (n v ) The link mapping Ml : E v i → P s maps a virtual link to a substrate loop-free path, subject to: ∀e v = (m vn v ) ∈ E v i Ml(m v n v ) ∈ P S (Mn(m v ),Mn(n v )) RBs (Ml(m v n v )) ≥ B v i (e v ) In Fig. 1, the node mapping for the VN request G v 1 is {a → C, b → E, c → D}, and the link mapping is {(ab) → TABLE I Notations in this paper Notation Meaning G s Substrate network N s Set of nodes E s Set of links C s Set of CPU capacity attributes B s Set of bandwidth capacity attributes RCs Set of residual CPU resources RBs Set of residual bandwidth resources P s Loop-free paths set G v i The i th virtual network N v i Set of nodes of G v i E v i Set of links of G v i C v i Set of CPU constraints in G v i B v i Set of bandwidth constraints in G v i bwli A basic sub-workload percentage in G v i pwli Probability of a variable sub-workload in G v i {CB, BE}, (bc) → {ED}, (ca) → {DC}}. The node mapping for the VN request G v 2 is {d → A, e → F}, and the link mapping is {(de) → {AG,GF}}. C. Objective Virtual network mapping is done by InPs. From InPs’ standpoint, a natural objective is to increase revenue and to decrease cost. However, an SP is only willing to pay fee proportional to his requested resources, that is, the revenue, R(G v i ), of embedding a virtual network, G v i , can be defined as (following the definitions in previous works [8, 10]): R(G v i ) = ωc · ∑ n v∈Nv C v i (n v ) + ωb · ∑ e v∈Ev B v i (e v ) (1) where ωc and ωb are the weights for CPU and bandwidth, respectively. We learn from this definition that, given a VN request, the revenue is fixed. Therefore, in order to get more revenue, the InP should try to accept more VN requests but meet their resource constraints at the same time. To this end, virtual networks should be properly and effi- ciently deployed on top of a substrate network. Due to the NP-completeness of the VNE problem [5], many heuristic algorithms have been proposed. However, in this paper we re-visit this problem from two novel aspects: opportunistic resource sharing and topology-aware node mapping. IV. Framework Overview We present a high level overview of our framework, ORS T A, as illustrated in Algorithm 1, in this section and the details of ORS T A in the next section. Initially, we compute the amount of residual resources for each substrate node/link (lines 3-4 of Alg. 1), i.e., the available CPU/bandwidth capacity. Note that, when we perform oppor￾tunistic resource sharing, the estimation of residual resources becomes complicated; we will explain our method in Sec￾tion V-B. Afterwards, inspired by the PageRank algorithm [21] which is used by Google to assign a numerical rank to every web page, we devise a similar ranking algorithm based on Markov chain [22] to compute the rank of each substrate node, denoted by MCRank (line 5 of Alg. 1), which is illustrated 2410

=01 in Section V-C.This MCRank takes both residual resources and topology into consideration in an effort to improve the 23 12 2 12 deployment of virtual networks. When a VN request arrives,we adopt the following simple greedy heuristic.In the node mapping phase(lines 7-10 of Alg. Ph=0.1 1),all virtual nodes are sorted in a decreasing order of their CPU constraints and are placed in a queue;then,we map each ts2 ts3 ts4 ts5 ts6 virtual node in the sorted queue to the unused substrate node with the highest MCRank.In the link mapping phase (lines frame 11-13 of Alg.1),we map each virtual link to the k-shortest Fig.2.Time slot assignment in a virtual link path between its end hosts (for increasing k)to minimize the length of the substrate paths that virtual links are mapped to. Then,considering workload fluctuation,we employ op- Opportunistic resource sharing for virtual network mapping portunistic resource sharing to efficiently utilize substrate is proposed in [18]for the first time.In that paper,we studied resources at the expense of collisions (line 14 of Alg.1). opportunistic bandwidth sharing in a single physical link and We formulate this opportunistic resource sharing-based local devised two heuristic algorithms from different perspectives. time slot assignment problem as an optimization problem and Here,we employ the results from our previous work and im- devise an online approximation algorithm,which is inspired prove them by developing an online approximation algorithm. by the bin packing problem [23].The details are presented in As we assumed,both the network traffic and the CPU busy section V-A. time are proportional to the workload;for a virtual link,e', When a virtual network request is successfully embed- from virtual network G',the traffic is composed of basic ded,the framework ORSTA updates RC5(n),RB(e)and sub-traffic,which equals bwli.B'(e"),and variable sub-traffic, MCRank(n),and waits for another virtual network request. which equals(1-bwli).B:(e")and happens with probability pwli.For basic sub-traffic,the InP has no choice but to allocate Algorithm 1 The Opportunistic Resource Sharing and the required number of time slots,thus we will only consider Topology-Aware Mapping Framework(ORS TA) variable sub-traffic in the subsequent discussion. 1:Initialization Phase To conserve time slots for upcoming requests,we prefer 2:while true do that each time slot can be assigned to as much variable sub- Yn'∈Ws,update RC'(n) traffic as possible.However,when more than one variable sub- Ye'∈E',update RB'(e) traffic occurs at the same time slot,a collision happens.To 5 Run MCRank(y) break the tradeoff between utilization and collision,we have Wait until a VN request,say G,arrives the following optimization problem. Os-sorted virtual nodes in Gy according to Cy Problem 1:Given a probability threshold,ph,and a set of for i=0 to Os.length do n variable sub-traffic from e',i =1.2,...,n,each requires 9 Map o[i]to the unused substrate node with the (1-bwli).B'(e")time slots with probability pwli.Find highest MCRank an assignment of time slots for the variable sub-traffic to 10: end for minimize the number of time slots used,such that:1)for 11: for all es e Es do each variable sub-traffic flow from e,the number of time 12: Map es to the k-shortest path for increasing k slots assigned to it is at least (1-bwl).B(e);2)the collision 13: end for probability at each time slot is no more than ph. 14 Yn∈Vs and Ve'∈E',run FFA(ph) 15:end while The collision probability can be obtained as follows.Let Xi indicate whether variable sub-traffic in e'occurs,i.e.,Pr[Xi= 1]pwli.For time slot k,let D&denote the set of variable V.DETAILED ALGORITHMS sub-traffic that it is assigned to.Then,the probability of a A.Opportunistic Resource Sharing-based Local Time Slot collision happening at slot k,denoted by Preollision(De),is: Assignment PTcollision(Dg)=PrL∑X≥1] 1)Preliminaries:in ORS TA.the virtual network embed- ding is completed after line 13 of Alg.I in a macroscopical sense,i.e.,node-to-node and link-to-path matching is accom- 1--pwl)-∑pw: (2) (1-pwlj)) jeD.j≠i plished.However,at a single node/link level,we also need to deal with opportunistic resource sharing-based local time Fig.2 shows a feasible assignment.ts can be assigned slots assignment.Note that both CPU and bandwidth can be to three sub-traffic flows from e',ez,and e because they represented as time slots,so we focus on assigning time slots collide with a probability 0.064 (by Eq.(2)),which is less then in a substrate link among multiple virtual links.The results ph=0.1.ts3 can not be assigned to e"and e simultaneously can be applied to a substrate node without any major changes. because the collision probability is 0.3.0.4=0.12>Ph 2411

in Section V-C. This MCRank takes both residual resources and topology into consideration in an effort to improve the deployment of virtual networks. When a VN request arrives, we adopt the following simple greedy heuristic. In the node mapping phase (lines 7-10 of Alg. 1), all virtual nodes are sorted in a decreasing order of their CPU constraints and are placed in a queue; then, we map each virtual node in the sorted queue to the unused substrate node with the highest MCRank. In the link mapping phase (lines 11-13 of Alg. 1), we map each virtual link to the k-shortest path between its end hosts (for increasing k) to minimize the length of the substrate paths that virtual links are mapped to. Then, considering workload fluctuation, we employ op￾portunistic resource sharing to efficiently utilize substrate resources at the expense of collisions (line 14 of Alg. 1). We formulate this opportunistic resource sharing-based local time slot assignment problem as an optimization problem and devise an online approximation algorithm, which is inspired by the bin packing problem [23]. The details are presented in section V-A. When a virtual network request is successfully embed￾ded, the framework ORS T A updates RCs (n s ), RBs (e s ) and MCRank(n s ), and waits for another virtual network request. Algorithm 1 The Opportunistic Resource Sharing and Topology-Aware Mapping Framework (ORS T A) 1: Initialization Phase 2: while true do 3: ∀n s ∈ N s , update RCs (n s ) 4: ∀e s ∈ E s , update RBs (e s ) 5: Run MCRank(γ) 6: Wait until a VN request, say G v i , arrives 7: Q s ← sorted virtual nodes in G v i according to C v i 8: for i = 0 to Q s .length do 9: Map Q s [i] to the unused substrate node with the highest MCRank 10: end for 11: for all e s ∈ E s do 12: Map e s to the k-shortest path for increasing k 13: end for 14: ∀n s ∈ N s and ∀e s ∈ E s , run FFA(pth) 15: end while V. Detailed Algorithms A. Opportunistic Resource Sharing-based Local Time Slot Assignment 1) Preliminaries: in ORS T A, the virtual network embed￾ding is completed after line 13 of Alg. 1 in a macroscopical sense, i.e., node-to-node and link-to-path matching is accom￾plished. However, at a single node/link level, we also need to deal with opportunistic resource sharing-based local time slots assignment. Note that both CPU and bandwidth can be represented as time slots, so we focus on assigning time slots in a substrate link among multiple virtual links. The results can be applied to a substrate node without any major changes. Fig. 2. Time slot assignment in a virtual link Opportunistic resource sharing for virtual network mapping is proposed in [18] for the first time. In that paper, we studied opportunistic bandwidth sharing in a single physical link and devised two heuristic algorithms from different perspectives. Here, we employ the results from our previous work and im￾prove them by developing an online approximation algorithm. As we assumed, both the network traffic and the CPU busy time are proportional to the workload; for a virtual link, e v i , from virtual network G v i , the traffic is composed of basic sub-traffic, which equals bwli · B v i (e v ), and variable sub-traffic, which equals (1 − bwli) · B v i (e v ) and happens with probability pwli . For basic sub-traffic, the InP has no choice but to allocate the required number of time slots, thus we will only consider variable sub-traffic in the subsequent discussion. To conserve time slots for upcoming requests, we prefer that each time slot can be assigned to as much variable sub￾traffic as possible. However, when more than one variable sub￾traffic occurs at the same time slot, a collision happens. To break the tradeoff between utilization and collision, we have the following optimization problem. Problem 1: Given a probability threshold, pth, and a set of n variable sub-traffic from e v i , i = 1, 2, . . . , n, each requires (1 − bwli) · B v i (e v i ) time slots with probability pwli . Find an assignment of time slots for the variable sub-traffic to minimize the number of time slots used, such that: 1) for each variable sub-traffic flow from e v i , the number of time slots assigned to it is at least (1−bwli)·B v i (e v i ); 2) the collision probability at each time slot is no more than pth. The collision probability can be obtained as follows. Let Xi indicate whether variable sub-traffic in e v i occurs, i.e., Pr[Xi = 1] = pwli . For time slot k, let Dk denote the set of variable sub-traffic that it is assigned to. Then, the probability of a collision happening at slot k, denoted by Prcollision(Dk), is: Prcollision(Dk) = Pr[ ∑ i∈Dk Xi ≥ 1] = 1 − ∏ i∈Dk (1 − pwli) − ∑ i∈Dk (pwli · ∏ j∈Dk , j,i (1 − pwlj)) (2) Fig. 2 shows a feasible assignment. ts1 can be assigned to three sub-traffic flows from e v 1 , e v 2 , and e v 3 because they collide with a probability 0.064 (by Eq. (2)), which is less then pth = 0.1. ts3 can not be assigned to e v 1 and e v 4 simultaneously because the collision probability is 0.3 · 0.4 = 0.12 > pth. 2411

2)A first-fit-based online approximation algorithm:the Case I:we use a particular variable sub-traffic flow,which design of our algorithm is based on the following observation: requires dmin time slots and occurs with probability Pmin, when each variable sub-traffic requires one single time slot. to replace all of the variable sub-traffic.Then.the maximal i.e.,(1 -bwli).B'(e)=1 for all i,Problem 1 is very similar allowable number of sub-traffic,vol,in a substrate slot is to bin packing.However,the occupied size in each bin is the determined by: sum of the sizes of all of the packed items in bin packing, whereas in Problem 1,the collision probability in a time slot, 1-(1-Pmin)vol-volt Pmin(1-Pmin)vol-1=Puh as shown in Eq.2,is neither linear nor multiplicative. Hence,in this case,the number of time slots required by First-fit [23]is a heuristic algorithm with an approximation all of the n sub-traffic is: factor of 2 for bin packing.In first-fit,items are considered in an arbitrary order,and for each item,first-fit attempts to place s1=”dnn the item in the first bin that can accommodate the item.If not. the item is placed into a new bin.First-fit can be executed Case II:we use another particular variable sub-traffic flow, online and has a low time complexity. which requires dmax time slots and occurs with probability Their resemblance sheds light on the design of FFA,which Pmax,to replace all of the variable sub-traffic.Then,the is based on the core idea of first-fit.The FFA Algorithm is maximal allowable number of sub-traffic,voly,in a substrate presented in Algorithm 2. slot is determined by: 1-(1-Pmax)you-voln Pmax(1-Pmaxolu-1=Pth Algorithm 2 FFA(Pih) 1:Wait until variable sub-traffic from e arrives Similarly,the number of time slots required by all of the n 2:counter←-0 sub-traffic in this case is: 3:While(counter Pth) 6: pos←←p05+1 Theorem I:Sffa≤(dmar·voli）/(dmin·voli）Sopr 个 Proof:it is straightforward to see that: Assign tspos to e 8: counter←counter+1 0<S1≤Som≤Sffa≤Sn then: 3)Incremental Calculation:Collision(tspos,e)is a func- SifaSμ=dmaxvoll tion that returns the probability of a collision at tspos if tspos is assigned to e'.To calculate the collision probability efficiently, :≤Si=dminvol we adopt the following incremental approach.Let De be the The theorem follows immediately. ■ set of variable sub-traffic that ts is currently assigned to.Also B.Residual Resource Estimation let: A(Dk)= 1-pwli) The amount of the residual resource in a substrate node/link iED is an important metric in VNE process.In a traditional sce- B(D)= S(pwlr (1-pwl)》 nario,where opportunistic resource sharing is not considered, iED jEDu,jti the residual CPU,RC(n),of a substrate node,n,and residual then,the collision probability Preollision(D)=1-A(D)- bandwidth,RB(e),of a substrate link,e,are defined as: B(D).When slot k is to be assigned to a new sub-traffic from RCom)=Cn-∑0n,n) e,then: Vnv A(D&Ulep)=A(Dg)(1-pwlh) RB'(e)=B'(e)- ∑fi(e',e) (3) B(D&Ulep])=B(D)(1-pwlh)+A(Dg).pwlh where fe(n",n)denotes the CPU resources of ns allocated This can be used to calculate the new collision probability. to n",and fo(e",e)denotes the bandwidth resources of es 4)Approximation Ratio:we denote by Sffa the solution allocated to e". generated by FFA,and by Sop the optimal solution.Abusing However,with opportunistic resource sharing,the residual the notation a bit,we will also use Sffa and Sopr to denote resource becomes complicated.Fig.3 shows a snapshot of the the number of time slots needed by these two solutions, time slot allocation in a substrate link.Intuitively,the residual respectively,if no confusion can be caused.Let, resource consists of the right part and the available room in Pmin minisisnpwli,dmin =minisisn((1-bwli).B(e)) the middle part which is allocated to variable sub-traffic.The pmax maxisisnpwli,dmax =maxisisn((1-bwli).B(e)) former is easy to compute while the latter is not so obvious. Suppose that the capacity of a substrate link,e",is B(e), Bin packing [23]:given n items with sizes s1.52....s.(0,1].find a and there are L time slots in a frame.There are b slots allocated packing method in unit-sized bins that minimizes the number of bins used.to basic sub-traffic and another d slots allocated to variable 2412

2) A first-fit-based online approximation algorithm: the design of our algorithm is based on the following observation: when each variable sub-traffic requires one single time slot, i.e., (1 − bwli) · B v i (e v i ) = 1 for all i, Problem 1 is very similar to bin packing1 . However, the occupied size in each bin is the sum of the sizes of all of the packed items in bin packing, whereas in Problem 1, the collision probability in a time slot, as shown in Eq. 2, is neither linear nor multiplicative. First-fit [23] is a heuristic algorithm with an approximation factor of 2 for bin packing. In first-fit, items are considered in an arbitrary order, and for each item, first-fit attempts to place the item in the first bin that can accommodate the item. If not, the item is placed into a new bin. First-fit can be executed online and has a low time complexity. Their resemblance sheds light on the design of FFA, which is based on the core idea of first-fit. The FFA Algorithm is presented in Algorithm 2. Algorithm 2 FFA(pth) 1: Wait until variable sub-traffic from e v i arrives 2: counter ← 0 3: While(counter pth) 6: pos ← pos + 1 7: Assign tspos to e v i 8: counter ← counter + 1 3) Incremental Calculation: Collision(tspos, e v i ) is a func￾tion that returns the probability of a collision at tspos if tspos is assigned to e v i . To calculate the collision probability efficiently, we adopt the following incremental approach. Let Dk be the set of variable sub-traffic that tsk is currently assigned to. Also let: A(Dk) = ∏ i∈Dk (1 − pwli) B(Dk) = ∑ i∈Dk (pwli · ∏ j∈Dk , j,i (1 − pwlj)) then, the collision probability Prcollision(Dk) = 1 − A(Dk) − B(Dk). When slot k is to be assigned to a new sub-traffic from e v h , then: A(Dk ∪ {e v h }) = A(Dk)(1 − pwlh) B(Dk ∪ {e v h }) = B(Dk)(1 − pwlh) + A(Dk) · pwlh (3) This can be used to calculate the new collision probability. 4) Approximation Ratio: we denote by S f f a the solution generated by FFA, and by S opt, the optimal solution. Abusing the notation a bit, we will also use S f f a and S opt to denote the number of time slots needed by these two solutions, respectively, if no confusion can be caused. Let, pmin = min1≤i≤n pwli , dmin =min1≤i≤n((1 − bwli) · B v i (e v i )) pmax = max1≤i≤n pwli , dmax =max1≤i≤n((1 − bwli) · B v i (e v i )) 1Bin packing [23]: given n items with sizes s1,s2,...,sn ∈ (0, 1], find a packing method in unit-sized bins that minimizes the number of bins used. Case I: we use a particular variable sub-traffic flow, which requires dmin time slots and occurs with probability pmin, to replace all of the variable sub-traffic. Then, the maximal allowable number of sub-traffic, volI , in a substrate slot is determined by: 1 − (1 − pmin) volI − volI · pmin · (1 − pmin) volI−1 = pth Hence, in this case, the number of time slots required by all of the n sub-traffic is: S I = n volI · dmin Case II: we use another particular variable sub-traffic flow, which requires dmax time slots and occurs with probability pmax, to replace all of the variable sub-traffic. Then, the maximal allowable number of sub-traffic, volII, in a substrate slot is determined by: 1 − (1 − pmax) volII − volII · pmax · (1 − pmax) volII−1 = pth Similarly, the number of time slots required by all of the n sub-traffic in this case is: S II = n volII · dmax Theorem 1: S f f a ≤ (dmax · volI)/(dmin · volII) · S opt Proof: it is straightforward to see that: 0 < S I ≤ S opt ≤ S f f a ≤ S II then: S f f a S opt ≤ S II S I = dmax · volI dmin · volII The theorem follows immediately. B. Residual Resource Estimation The amount of the residual resource in a substrate node/link is an important metric in VNE process. In a traditional sce￾nario, where opportunistic resource sharing is not considered, the residual CPU, RCs (n s ), of a substrate node, n s , and residual bandwidth, RBs (e s ), of a substrate link, e s , are defined as: RCs (n s ) = C s (n s )− ∑ ∀n v fc(n v , n s ) RBs (e s ) = B s (e s )− ∑ ∀e v fb(e v , e s ) where fc(n v , n s ) denotes the CPU resources of n s allocated to n v , and fb(e v , e s ) denotes the bandwidth resources of e s allocated to e v . However, with opportunistic resource sharing, the residual resource becomes complicated. Fig. 3 shows a snapshot of the time slot allocation in a substrate link. Intuitively, the residual resource consists of the right part and the available room in the middle part which is allocated to variable sub-traffic. The former is easy to compute while the latter is not so obvious. Suppose that the capacity of a substrate link, e s , is B s (e s ), and there are L time slots in a frame. There are b slots allocated to basic sub-traffic and another d slots allocated to variable 2412

Allocated to basic Allocated to vanable -Unallocated vary greatly.In order to heuristically decrease the length of sub-traffic sub-traffic virtual links (substrate paths),we prefer the substrate node s tSp+1 s6+2 fSb-c [S with more resources in its vicinity.Therefore,we propose in the following,a Markov chain-based node ranking method, Frame length:L MCRank. Fig.3.A snapshot of time slot allocation in a substrate link 2)MCRank:we define the resource,R(n'),of a substrate node,n,as the product of its residual CPU resource and a half of the collective bandwidth resources of its outgoing links: sub-traffic.Therefore,RB(e)is (L-b-d)/L.B(e)plus the available room in the middle d slots. Rn=RCn.∑ A simple and practical measurement of residual room,rbg. e)(e) in a single time slot,ts(beNeighN()NormR() +w2· MCRank(m) k=b+1 (8) In summary: where wi and w2 are the corresponding weights. NormR(n)/eNeighN()NormR(h)can be seen as the L-b-d RB(e)= L .B(e)+B(e) .rbk impact of m'on n.Let P be a matrix with rows and columns L k=b+l corresponding to substrate nodes,and Vn',m'E Ns: (5) pa-Procomaon(D Be Wl if m3 n =(L-b-d+ L k=b+1 B(Dk) P(m',n')= W2· NormR(n) ∑SeNeigkMm)NormR(h) if(m',n)∈Es (9) RC5(n')can be analyzed in a similar way. 0 otherwise C.Markov Chain-based Node Ranking (MCRank) Then,Eq.(8)can be expressed in the following matrix form: 1)Preliminaries:PageRank [21]nicely reflects the popu- MCRank·P=MCRank (10) larity and quality of web pages.In PageRank,the rank of a Let wi+w2=1;it is easy to verify that P is stochastic,i.e.: page measures the "importance"of that page.A page has a higher rank if it is pointed to by more highly-ranked pages. P(m3,n)=P(m5,m)+ P(m',n)=1 The more pages that one page points to,the less its influence nENS nENeighN(n) on their rankings is.This intuitive idea can be formalized as Hence,MCRank is actually a stationary distribution of the follows.The World-Wide-Web is treated as a directed graph, Markov chain with transition matrix P.The following theorem with web pages as vertices and hyper-links as directed edges. gives the existence of a stationary distribution. The rank of a page p,denoted by rank(p),is supposed to Theorem 2:the Markov chain,determined by P,has a satisfy: Tank(g） stationary distribution. rank(p)= (6) Proof:it is sufficient to prove that:(i)MCRank has finite g:(g-p)EE d4(g) states,as there are a finite number of substrate nodes;(ii)the where d(g)means the number of edges going out of page g. substrate network is strongly connected,so the Markov chain Note that the sum is over edges going into p. is irreducible:(iii)the substrate node iteslf has an impact on Inspired by PageRank,we consider using a similar method its MCRank,i.e.,the chain is a lazy random walk,so it is to measure the topology importance of a substrate node.To aperiodic.The theorem follows immediately. ■ understand the topology importance,suppose that there are Based on [21],we give our algorithm to calculate the two substrate nodes with the same residual resources,but stationary distribution,i.e.,MCRank,in Algorithm 3,where the resources of their neighbors (or neighbors of neighbors) y serves as a threshold to control iterations. 2413

Fig. 3. A snapshot of time slot allocation in a substrate link sub-traffic. Therefore, RBs (e s ) is (L−b−d)/L · B s (e s ) plus the available room in the middle d slots. A simple and practical measurement of residual room, rbk, in a single time slot, tsk (b < k < b + d + 1), is defined as the probability of a variable sub-traffic flow that would cause the collision probability to be higher than pth if tsk is assigned to it. Hence, by Eq. (3), we have: 1 − A(Dk)(1 − rbk) − (B(Dk)(1 − rbk) + A(Dk) · rbk) = pth That is: rbk = A(Dk) + B(Dk) + pth − 1 B(Dk) = pth − Prcollision(Dk) B(Dk) (4) Thereby, the available room in the middle d slots that are allocated to variable sub-traffic is: B s (e s ) L · ∑ b+d k=b+1 rbk In summary: RBs (e s ) = L − b − d L · B s (e s ) + B s (e s ) L · ∑ b+d k=b+1 rbk = (L − b − d + ∑ b+d k=b+1 pth − Prcollision(Dk) B(Dk) ) B s (e s ) L (5) RCs (n s ) can be analyzed in a similar way. C. Markov Chain-based Node Ranking (MCRank) 1) Preliminaries: PageRank [21] nicely reflects the popu￾larity and quality of web pages. In PageRank, the rank of a page measures the “importance” of that page. A page has a higher rank if it is pointed to by more highly-ranked pages. The more pages that one page points to, the less its influence on their rankings is. This intuitive idea can be formalized as follows. The World-Wide-Web is treated as a directed graph, with web pages as vertices and hyper-links as directed edges. The rank of a page p, denoted by rank(p), is supposed to satisfy: rank(p) = ∑ g:(g,p)∈E rank(g) d+(g) (6) where d+(g) means the number of edges going out of page g. Note that the sum is over edges going into p. Inspired by PageRank, we consider using a similar method to measure the topology importance of a substrate node. To understand the topology importance, suppose that there are two substrate nodes with the same residual resources, but the resources of their neighbors (or neighbors of neighbors) vary greatly. In order to heuristically decrease the length of virtual links (substrate paths), we prefer the substrate node with more resources in its vicinity. Therefore, we propose in the following, a Markov chain-based node ranking method, MCRank. 2) MCRank: we define the resource, R(n s ), of a substrate node, n s , as the product of its residual CPU resource and a half of the collective bandwidth resources of its outgoing links: R(n s ) = RCs (n s ) · ∑ e s∈NeighE(n s ) 1 2 RBs (e s ) where NeighE(n s ) denotes the set of links that are adjacent to n s . The coefficient 1/2 can be seen as the bandwidth of a link is equally shared between its endpoints, though it is not in fact. We then normalize R s (n s ). NormR(n s ) = R s (n s ) ∑ ms∈Ns Rs (ms ) (7) Intuitively, if the MCRank(n s ) of a substrate node, n s , is high, the possible reasons are: (i) the node itself has ample resources; (ii) its neighbors have abundant resources. Hence, we define the MCRank(n s ) as: MCRank(n s ) = w1 · MCRank(n s ) + w2 · ∑ ms∈NeighN(n s ) NormR(n s ) ∑ h s∈NeighN(ms ) NormR(h s ) · MCRank(m s ) (8) where w1 and w2 are the corresponding weights. NormR(n s )/ ∑ h s∈NeighN(ms ) NormR(h s ) can be seen as the impact of m s on n s . Let P be a matrix with rows and columns corresponding to substrate nodes, and ∀n s , m s ∈ N s : P(m s , n s ) =    w1 if m s = n s w2 · NormR(n s ) ∑ h s∈NeighN(ms) NormR(h s ) if (m s , n s ) ∈ E s 0 otherwise (9) Then, Eq. (8) can be expressed in the following matrix form: MCRank · P = MCRank (10) Let w1 + w2 = 1; it is easy to verify that P is stochastic, i.e.: ∑ n s∈Ns P(m s , n s ) = P(m s , m s ) + ∑ n s∈NeighN(ms ) P(m s , n s ) = 1 Hence, MCRank is actually a stationary distribution of the Markov chain with transition matrix P. The following theorem gives the existence of a stationary distribution. Theorem 2: the Markov chain, determined by P, has a stationary distribution. Proof: it is sufficient to prove that: (i) MCRank has finite states, as there are a finite number of substrate nodes; (ii) the substrate network is strongly connected, so the Markov chain is irreducible; (iii) the substrate node iteslf has an impact on its MCRank, i.e., the chain is a lazy random walk, so it is aperiodic. The theorem follows immediately. Based on [21], we give our algorithm to calculate the stationary distribution, i.e., MCRank, in Algorithm 3, where γ serves as a threshold to control iterations. 2413

Algorithm 3 MCRank(y) ranking indeed improves the deployment of virtual networks 1:CRank←-NormR,i←-O and further enables the substrate network to accept more VN 2:repeat requests.We also notice that the acceptance ratio of these four 3 MCRanki1←-MCRank·P algorithms is averagely less than 0.4,which is a little low.The 4: 6-MCRanki+1 MCRankill main reason behind this may be because links in the substrate 5 i←i+1 network (ANSNET has 32 nodes and 58 links,ARPANET 6:until 6<y has 20 nodes and 32 links)are sparse,while each pair of nodes in a virtual network is connected with probability 0.5. TABLE II This leads to the topology becoming the dominating factor in PARAMETERS virtual network embedding. EIC] Expectation of CPU requirement on a virtual node E[B] Expectation of bandwidth requirement on a virtual link Fig.4 also shows that the acceptance ratio of TA is E[bwl] Expectation of a basic sub-workload percentage much higher than ORS and Greedy.while ORS achieves Elpwl Expectation of a variable sub-workload occurring probability nearly the same acceptance ratio as Greedy.This implies that distinguishing between substrate nodes is helpful in virtual network mapping while opportunistic resource sharing is not VI.EXPERIMENTAL EVALUATION significantly effective when there is no topology-aware node In this section,we first describe our evaluation environment, ranking.In Figs 5 and 6,the node/link utilization ratio means then present main evaluation results. the ratio of the allocated resources to the capacity of a substrate node/link.We observe similar results where ORSTA performs A.Evaluation Environment better than TA.ORS.and Greedy. As network virtualization is still an open field,our eval- We then try to evaluate the effects of w1,E[C"],E[B"], uations follow settings similar to [7,8,10-12,20].We use E[bwl],and E[pwl],respectively.Fig.7 shows the comparison ANSNET and ARPANET as the substrate network topologies. between ORSTAs with different w settings.We see that Both the CPU capacity at substrate nodes and bandwidth ORS TA(wI =0.5)achieves the highest acceptance ratio while capacity at substrate links are generated uniformly from ORS TA(wI =0.3)gets the lowest.This is anticipated because [50,100].The arrivals of VN requests are modeled as a Poisson in MCRank,"wi=0.5"indicates the rank of a substrate process with an average rate of 5 requests per minute.For node is half determined by itself;"w=0.3"causes the each virtual network,the number of nodes is determined by rank of a substrate node to be greatly dominated by the a uniform distribution between 2 and 10;each pair of virtual amount of residual resources of other nodes.However,the nodes is connected with probability 0.5.The lifetime of each difference is not considerably significant,which means the virtual network is assumed to be exponentially distributed with stationary distribution of our Markov chain nicely represents an average of 10 minutes.The collision probability threshold the importance of substrate nodes,irrespective of whether wi is set to 0.1 throughout our evaluation.We summarize the is large or small. parameters that we vary in our evaluations in Table II. In Fig.8,we show the results of E[C"]and E[B"].We Comparing our framework with previous research on virtual note that in the case when E[C"]and E[B"]are small,the network mapping is difficult because it is the first attempt acceptance ratio is high.However,with E[C]and E[B"] that considers virtual network mapping in the context of increasing,the substrate network resources become scarce, opportunistic resource sharing at the entire network level. which causes more and more VN requests to be rejected.In Therefore,our evaluation focuses primarily on quantifying the this figure,ORS TA(E[C"]E[B]15)achieves almost the benefits of opportunistic resource sharing and topology-aware same acceptance ratio as ORS TA(E[C"]=E[B"]=20).A rea- node ranking.The notations that we use to refer to different sonable explanation is that,E[C"]=E[B"]=15 is sufficiently algorithms are enumerated in Table III.In the following large compared to the average amount of CPU/bandwidth subsection,we present the average results after running over capacities of substrate nodes/links,i.e.,75. ANSNET 100 times.(Results over ARPANET are similar and Fig.9 illustrates the effects of E[bwl]and Efpwll.Remem- omitted due to space limitation.) ber that bwl is the percentage of a basic sub-workload in the overall workload,and pwl is the probability of a variable B.Evaluation Results sub-workload happening.In this figure,ORSTA(E[bwl] We first present the comparison results between ORSTA,0.30,E[pwl]=0.15)presents the best performance,and TA,ORS,and Greedy (refer to Table III).Figs 4,5,and ORSTA(E[bwl]=0.50,E[pwl]=0.05)achieves the second 6 show the acceptance ratio over time,CDF (cumulative best.This is to say,bwl plays a more important role than pwl. distribution function)of node utilization ratios,and link uti- In summary,our proposed framework,ORS TA,increases lization ratios,respectively.In these experiments,both E[C"]the acceptance ratio through opportunistic resource sharing. and E[B"]are set to be 10;E[bwl]0.5;E[pwl]0.15, which enables the substrate network to support more VN and w=0.7.In Fig.4,the acceptance ratio of ORSTA requests and topology-aware node ranking,which treats sub- is higher than all of the other algorithms,which indicates strate nodes differently to shorten the length of substrate paths that opportunistic resource sharing and topology-aware node that virtual links are mapped to. 2414

Algorithm 3 MCRank(γ) 1: MCRank ← NormR, i ← 0 2: repeat 3: MCRanki+1 ← MCRanki · P 4: δ ← ∥MCRanki+1 − MCRanki∥1 5: i ← i + 1 6: until δ < γ TABLE II Parameters E[C v ] Expectation of CPU requirement on a virtual node E[B v ] Expectation of bandwidth requirement on a virtual link E[bwl] Expectation of a basic sub-workload percentage E[pwl] Expectation of a variable sub-workload occurring probability VI. Experimental Evaluation In this section, we first describe our evaluation environment, then present main evaluation results. A. Evaluation Environment As network virtualization is still an open field, our eval￾uations follow settings similar to [7, 8, 10–12, 20]. We use ANSNET and ARPANET as the substrate network topologies. Both the CPU capacity at substrate nodes and bandwidth capacity at substrate links are generated uniformly from [50,100]. The arrivals of VN requests are modeled as a Poisson process with an average rate of 5 requests per minute. For each virtual network, the number of nodes is determined by a uniform distribution between 2 and 10; each pair of virtual nodes is connected with probability 0.5. The lifetime of each virtual network is assumed to be exponentially distributed with an average of 10 minutes. The collision probability threshold is set to 0.1 throughout our evaluation. We summarize the parameters that we vary in our evaluations in Table II. Comparing our framework with previous research on virtual network mapping is difficult because it is the first attempt that considers virtual network mapping in the context of opportunistic resource sharing at the entire network level. Therefore, our evaluation focuses primarily on quantifying the benefits of opportunistic resource sharing and topology-aware node ranking. The notations that we use to refer to different algorithms are enumerated in Table III. In the following subsection, we present the average results after running over ANSNET 100 times. (Results over ARPANET are similar and omitted due to space limitation.) B. Evaluation Results We first present the comparison results between ORS T A, T A, ORS , and Greedy (refer to Table III). Figs 4, 5, and 6 show the acceptance ratio over time, CDF (cumulative distribution function) of node utilization ratios, and link uti￾lization ratios, respectively. In these experiments, both E[C v ] and E[B v ] are set to be 10; E[bwl] = 0.5; E[pwl] = 0.15, and w1 = 0.7. In Fig. 4, the acceptance ratio of ORS T A is higher than all of the other algorithms, which indicates that opportunistic resource sharing and topology-aware node ranking indeed improves the deployment of virtual networks and further enables the substrate network to accept more VN requests. We also notice that the acceptance ratio of these four algorithms is averagely less than 0.4, which is a little low. The main reason behind this may be because links in the substrate network (ANSNET has 32 nodes and 58 links, ARPANET has 20 nodes and 32 links) are sparse, while each pair of nodes in a virtual network is connected with probability 0.5. This leads to the topology becoming the dominating factor in virtual network embedding. Fig. 4 also shows that the acceptance ratio of T A is much higher than ORS and Greedy, while ORS achieves nearly the same acceptance ratio as Greedy. This implies that distinguishing between substrate nodes is helpful in virtual network mapping while opportunistic resource sharing is not significantly effective when there is no topology-aware node ranking. In Figs 5 and 6, the node/link utilization ratio means the ratio of the allocated resources to the capacity of a substrate node/link. We observe similar results where ORS T A performs better than T A, ORS , and Greedy. We then try to evaluate the effects of w1, E[C v ], E[B v ], E[bwl], and E[pwl], respectively. Fig. 7 shows the comparison between ORS T As with different w1 settings. We see that ORS T A(w1 = 0.5) achieves the highest acceptance ratio while ORS T A(w1 = 0.3) gets the lowest. This is anticipated because in MCRank, “w1 = 0.5” indicates the rank of a substrate node is half determined by itself; “w1 = 0.3” causes the rank of a substrate node to be greatly dominated by the amount of residual resources of other nodes. However, the difference is not considerably significant, which means the stationary distribution of our Markov chain nicely represents the importance of substrate nodes, irrespective of whether w1 is large or small. In Fig. 8, we show the results of E[C v ] and E[B v ]. We note that in the case when E[C v ] and E[B v ] are small, the acceptance ratio is high. However, with E[C v ] and E[B v ] increasing, the substrate network resources become scarce, which causes more and more VN requests to be rejected. In this figure, ORS T A(E[C v ] = E[B v ] = 15) achieves almost the same acceptance ratio as ORS T A(E[C v ] = E[B v ] = 20). A rea￾sonable explanation is that, E[C v ] = E[B v ] = 15 is sufficiently large compared to the average amount of CPU/bandwidth capacities of substrate nodes/links, i.e., 75. Fig. 9 illustrates the effects of E[bwl] and E[pwl]. Remem￾ber that bwl is the percentage of a basic sub-workload in the overall workload, and pwl is the probability of a variable sub-workload happening. In this figure, ORS T A(E[bwl] = 0.30, E[pwl] = 0.15) presents the best performance, and ORS T A(E[bwl] = 0.50, E[pwl] = 0.05) achieves the second best. This is to say, bwl plays a more important role than pwl. In summary, our proposed framework, ORS T A, increases the acceptance ratio through opportunistic resource sharing, which enables the substrate network to support more VN requests and topology-aware node ranking, which treats sub￾strate nodes differently to shorten the length of substrate paths that virtual links are mapped to. 2414

TABLE III ALGORITHMS IN COMPARISON Notation Description ORSTA The entire framework,including opportunistic resource sharing,topology-aware ranking,and greedy node/link mapping ORS A partial framework,including opportunistic resource sharing.and greedy node/link mapping TA A partial framework.including topology-awareness,and greedy node/link mapping Greedy The traditional greedy embedding algorithm,including greedy node/link mapping ORSTA ORSTA ORSTA 0.8 0.8 Greedy Greedy 0.8 06 0.6 0.6 0.4 0.4 04 0.2 0.2 02 1000 20003000 400050006000 0.1 0.2 0.30.4 0.5 0.1 0.2 0.30.40.5 0.6 Time Node Utilization Ratio Link Utilization Ratio Fig.4. Acceptance ratio over time Fig.5. CDF of node utilization ratios Fig.6. CDF of link utilization ratios ORSTA(W,=0.3) ORSTA(EI ORSTA(Ebwl]-0.50.E PWI-0.15 0.8 口QT ORSTA 0.8 -070E 06 08 0.4 04 0.4 r70019611829911 0.2 02 0.2 2 100020003000 40005000 6000 0 1000 2000 3000 40005000 6000 0 100020003000400050006000 Time Time Time Fig.7.Effect of w Fig.8. Effect of E[C]and E[B"] Fig.9.Effect of E[bwl]and E[pwl] VII.RELATED WORK introducing the connectivity layer,which,in fact,is a special A.Network Virtualization virtual network that provides a necessary geographic footprint, reliability,and performance.He et al.[28]proposed Davinci In networking literature,virtual private networks (VPNs), architecture,where resource allocation is dynamic and used overlay networks,and network virtualization deal with select- optimization theory to show that adaptive resource allocation ing nodes to construct logical paths.However,the differences are:(i)VPNs only need to determine the locations of logical can be stable and can maximize the aggregate performance across virtual networks. links while network virtualizaiton simultaneously considers locations of logical nodes and links [7,8];(ii)only link B.Virtual Network Embedding constraints are considered in VPNs while both link and node To cope with the NP-hardness of the VNE problem,re- constraints are considered in network virtualization [7,8]; searchers resorted to heuristics to reduce computational time. (iii)overlays are designed in the application layer on top Ricci et al.[6]considered only bandwidth constraints and of the network layer [4].The most relevant work in the proposed the Assign algorithm based on simulated annealing overlay networks is [24].where Fan et al.investigated the with the assumption that the substrate node can only be used dynamic topology configuration problem in service overlay by one virtual node.Lu et al.[9]developed a method for the networks.They first acquired general properties of the optimal VNE problem in a cost-efficient way and attempted to find reconfiguration topology by observing small cases,and then the best topology in a family of backbone-star topologies. used observations as heuristics to design algorithms for large-Zhu et al.[7]assumed that the substrate nodes and links scale cases of networks. have unlimited CPU and bandwidth resources and focused In network virtualization,Ishibashi et al.[25]envisioned on load balancing and on-demand assignments.Yu et al.[10] cognitive radio-based virtual wireless networks and tried to assumed that SN supports path splitting and proposed a two- make efficient use of residual wasted bandwidth of the primary stage online algorithm:firstly,map the virtual nodes greedily, service providers.Shiomoto et al.[26]developed a network then deal with link mapping based on the multi-commodity virtualization method to represent the resources in the optical flow problem.Lischka et al.[11]proposed a backtracking backbone network of the service network.Zhu et al.[27]tried algorithm based on subgraph isomorphism detection,but re- to lower the barrier for deploying wide-area services through stricted the length of the substrate paths.Chowdhury et al.[8] 2415

TABLE III Algorithms in Comparison Notation Description ORS T A The entire framework, including opportunistic resource sharing, topology-aware ranking, and greedy node/link mapping ORS A partial framework, including opportunistic resource sharing, and greedy node/link mapping T A A partial framework, including topology-awareness, and greedy node/link mapping Greedy The traditional greedy embedding algorithm, including greedy node/link mapping 0 0.2 0.4 0.6 0.8 1 0 1000 2000 3000 4000 5000 6000 Acceptance Ratio Time ORSTA TA ORS Greedy Fig. 4. Acceptance ratio over time 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 CDF Node Utilization Ratio ORSTA TA ORS Greedy Fig. 5. CDF of node utilization ratios 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 CDF Link Utilization Ratio ORSTA TA ORS Greedy Fig. 6. CDF of link utilization ratios 0 0.2 0.4 0.6 0.8 1 0 1000 2000 3000 4000 5000 6000 Acceptance Ratio Time ORSTA(w1=0.3) ORSTA(w1=0.5) ORSTA(w1=0.7) ORSTA(w1=0.9) Fig. 7. Effect of w1 0 0.2 0.4 0.6 0.8 1 0 1000 2000 3000 4000 5000 6000 Acceptance Ratio Time ORSTA(E[Cv ]=E[Bv ]=05) ORSTA(E[Cv ]=E[Bv ]=10) ORSTA(E[Cv ]=E[Bv ]=15) ORSTA(E[Cv ]=E[Bv ]=20) Fig. 8. Effect of E[C v ] and E[B v ] 0 0.2 0.4 0.6 0.8 1 0 1000 2000 3000 4000 5000 6000 Acceptance Ratio Time ORSTA(E[bwl]=0.50,E[pwl]=0.15) ORSTA(E[bwl]=0.50,E[pwl]=0.05) ORSTA(E[bwl]=0.50,E[pwl]=0.25) ORSTA(E[bwl]=0.30,E[pwl]=0.15) ORSTA(E[bwl]=0.70,E[pwl]=0.15) Fig. 9. Effect of E[bwl] and E[pwl] VII. Related Work A. Network Virtualization In networking literature, virtual private networks (VPNs), overlay networks, and network virtualization deal with select￾ing nodes to construct logical paths. However, the differences are: (i) VPNs only need to determine the locations of logical links while network virtualizaiton simultaneously considers locations of logical nodes and links [7, 8]; (ii) only link constraints are considered in VPNs while both link and node constraints are considered in network virtualization [7, 8]; (iii) overlays are designed in the application layer on top of the network layer [4]. The most relevant work in the overlay networks is [24], where Fan et al. investigated the dynamic topology configuration problem in service overlay networks. They first acquired general properties of the optimal reconfiguration topology by observing small cases, and then used observations as heuristics to design algorithms for large￾scale cases of networks. In network virtualization, Ishibashi et al. [25] envisioned cognitive radio-based virtual wireless networks and tried to make efficient use of residual wasted bandwidth of the primary service providers. Shiomoto et al. [26] developed a network virtualization method to represent the resources in the optical backbone network of the service network. Zhu et al. [27] tried to lower the barrier for deploying wide-area services through introducing the connectivity layer, which, in fact, is a special virtual network that provides a necessary geographic footprint, reliability, and performance. He et al. [28] proposed DaVinci architecture, where resource allocation is dynamic and used optimization theory to show that adaptive resource allocation can be stable and can maximize the aggregate performance across virtual networks. B. Virtual Network Embedding To cope with the NP-hardness of the VNE problem, re￾searchers resorted to heuristics to reduce computational time. Ricci et al. [6] considered only bandwidth constraints and proposed the Assign algorithm based on simulated annealing with the assumption that the substrate node can only be used by one virtual node. Lu et al. [9] developed a method for the VNE problem in a cost-efficient way and attempted to find the best topology in a family of backbone-star topologies. Zhu et al. [7] assumed that the substrate nodes and links have unlimited CPU and bandwidth resources and focused on load balancing and on-demand assignments. Yu et al. [10] assumed that SN supports path splitting and proposed a two￾stage online algorithm: firstly, map the virtual nodes greedily, then deal with link mapping based on the multi-commodity flow problem. Lischka et al. [11] proposed a backtracking algorithm based on subgraph isomorphism detection, but re￾stricted the length of the substrate paths. Chowdhury et al. [8] 2415

proposed a VNE algorithm with better coordination between REFERENCES node mapping and link mapping based on linear programming [1]J.Turner and D.Taylor,"Diversifying the Internet,"in /EEE GLOBE- and deterministic/randomized rounding.but added location C0M2005,vol.2,2-22005,Pp.6Pp.-760. constraints to simplify the problem.Chowdhury et al.[13] [2]T.Anderson,L.Peterson,S.Shenker,and J.Turner,"Overcoming the Intemet impasse through virtualization,"Computer,vol.38,no.4.pp presented a policy-based decentralized inter-domain virtual 34-41,apml2005. network embedding framework and also designed a location- [3]N.Feamster,L.-X.Gao,and J.Rexford,"How to lease the Internet in aware VN request forwarding mechanism.Zhang et al.[20] your spare time,"ACM SIGCOMM Comput.Commun.Rev.,vol.37, no.1,Pp.61-642007. focused on flexibility and proposed a simulated annealing- [4]N.Chowdhury and R.Boutaba,"A survey of network virtualization." based algorithm to control the tradeoff between result accuracy Computer Nerworks,vol.54,no.5,pp.862-876,2010. [5]D.G.Andersen,"Theoretical approaches to node assignment,"Dec. and the running time of the embedding algorithm.Zhang et 2002,unpublished Manuscript. al.[18]investigated the opportunistic bandwidth sharing in a [6]R.Ricci,C.Alfeld,and J.Lepreau,"A solver for the network testbed single physical link among multiple virtual links from different mapping problem,"ACM SIGCOMM Comput.Commun.Rev..vol.33. VNs;however,in this paper,we study opportunistic resource no.2,pp.65-81,2003. [7]Y.Zhu and M.Ammar,"Algorithms for assigning substrate network sharing at the entire network level. resources to virtual network components,"in IEEE INFOCOM 2006. apri2006,Pp.1-12. C.Topology-Awareness in Virtual Network Mapping [8]N.Chowdhury,M.Rahman,and R.Boutaba,"Virtual network embed- ding with coordinated node and link mapping,"in IEEE INFOCOM To the best of our knowledge,there are only two research 2009,19-252009,Pp.783-791. [9]J.Lu and J.Turner,"Efficient mapping of virtual networks onto a shared articles [12,14]that incorporate topology into virtual network substrate,"Washington Universiry,Tech.Rep.WUCSE-2006-35,2006. embedding.Butt et al.[14]differentiated substrate resources [10]M.Yu,Y.Yi,J.Rexford,and M.Chiang."Rethinking virtual network by introducing scaling factors:Critical Index,which measures embedding:substrate support for path splitting and migration,"ACM the likelihood of a residual substrate network partition due to SIGCOMM Comput.Commun.Rev,vol.38.no.2.pp.17-29,2008. [11]J.Lischka and H.Karl,"A virtual network mapping algorithm based on its unavailability,and Popularity Index,which measures "how subgraph isomorphism detection."in ACM VISA 2009.2009.pp.81-88. many different VNs are affected when a link or a node is [12]X.Cheng.S.Su,Z.Zhang.H.Wang.F.Yang.Y.Luo,and J.Wang. unavailable".Cheng et al.[12]formulated a Markov random "Virtual network embedding through topology-aware node ranking, SIGCOMM Comput.Commun.Rev.,vol.41.pp.38-47,April 2011. walk model to compute the topology-aware resource ranking [13]M.Chowdhury,F.Samuel,and R.Boutaba,"Polyvine:policy-based vir- of nodes in a substrate network;however,in this paper,we tual network embedding across multiple domains,"in ACM S/GCOMM VISA 2010.New York,NY,USA:ACM,2010,pp.49-56 observe that we only need to consider a walk from a substrate [14]N.But.N.Chowdhury,and R.Boutaba,"Topology-awareness and re- node to itself or one of its neighbors because the impact is optimization mechanism for virtual network embedding,"in Nerworking, recursive in a Markov chain 2010,pp.27-39 [15]I.Houidi,W.Louati,D.Zeghlache,P.Papadimitriou,and L.Mathy, "Adaptive virtual network provisioning,"in ACM S/GCOMM VISA 2010. VIII.CONCLUSIONS ACM,2010,Pp.41-48. This paper re-examines the virtual network mapping prob- [16]Auckland Data Trace.http://pma.nlanr.net/traces/long/auck2.html. [17刀Q.Zhao and B.Sadler,.“A survey of dynamic spectrum access,.”EEE lem in network virtualization from two novel perspectives, Signal Processing Magazine..vol.24.no.3,pp.79-89.May 2007. i.e.,opportunistic resource sharing and topology-aware node [18]S.Zhang.Z.Qian,B.Tang.J.Wu,and S.Lu,"Opportunistic band- ranking,which are incorporated into our proposed framework, width sharing for virtual network mapping."in IEEE Globecom 2011. December 2011. ORSTA.ORS TA contains three main parts,opportunistic [19]H.Schwarz,D.Marpe,and T.Wiegand,"Overview of the scalable video resource sharing-based local time slot assignment,estimation coding extension of the h.264/avc standard,"IEEE TCSVT,vol.17,no.9. of residual resources and topology-aware node ranking.The Pp.1103-1120,sept.2007. [20]S.Zhang.Z.Qian,S.Guo,and S.Lu,"FELL:A flexible virtual network effectiveness of our framework is confirmed by extensive embedding algorithm with guaranteed load balancing."in IEEE ICC simulations.We are currently seeking the proof of the NP- 2011,June2011. [21]L.Page,S.Brin,R.Motwani,and T.Winograd,"The pagerank citation Completeness of Problem 1 and are exploring methods of ranking:Bringing order to the web."Stanford InfoLab,Technical Report scheduling packets when a collision occurs in a time slot. 1999-66.November 1999. [22]"Markov chain,"http:/en.wikipedia.org/wiki/Markov_chain. [23]V.V.Vazirani.Approximation Algorithms.Berlin:Springer.2003. ACKNOWLEDGMENTS (24]J.Fan and M.H.Ammar,"Dynamic topology configuration in service We would like to thank Yitong Yin for his Randomized overlay networks:A study of reconfiguration policies,"in IEEE INFO- COM2006,april2006,pp.1-12. Algorithms and Combinatorics courses,and the anonymous [25]B.Ishibashi.N.Bouabdallah,and R.Boutaba,"Qos performance reviewers for their insightful suggestion. analysis of cognitive radio-based virtual wireless networks,"in IEEE This work is supported in part by the National NSF NF0C0M2008,april2008,pp.2423-2431. [26]K.Shiomoto,I.Inoue,and E.Oki,"Network virtualization in high-speed of China under Grant No.61073028 and No.61021062: huge-bandwidth optical circuit switching network,"in /EEE INFOCOM Key Project of Jiangsu Research Program under Grant 2008 Workshops,april 2008.pp.1-6. No.BE2010179:Jiangsu Natural Science Foundation under [27]Y.Zhu,R.Zhang-Shen,S.Rangarajan,and J.Rexford,"Cabernet: connectivity architecture for better network services,"in ACM CoNEXT Grant No.BK2011510;the National 973 Basic Research 2008. New York,NY,USA:ACM,2008,pp.64:1-64:6. Program of China under Grant No.2009CB320705 and [28]J.He,R.Zhang-Shen,Y.Li,C.-Y.Lee,J.Rexford,and M.Chiang. "Davinci:dynamically adaptive virtual networks for a customized inter- No.2011CB302800;US NSF grants ECCS 1128209,CNS net,"in ACM CoNEXT 2008.ACM.2008.pp.15:1-15:12. 1065444.CCF1028167.CNS0948184.and CC℉0830289. 2416

proposed a VNE algorithm with better coordination between node mapping and link mapping based on linear programming and deterministic/randomized rounding, but added location constraints to simplify the problem. Chowdhury et al. [13] presented a policy-based decentralized inter-domain virtual network embedding framework and also designed a location￾aware VN request forwarding mechanism. Zhang et al. [20] focused on flexibility and proposed a simulated annealing￾based algorithm to control the tradeoff between result accuracy and the running time of the embedding algorithm. Zhang et al. [18] investigated the opportunistic bandwidth sharing in a single physical link among multiple virtual links from different VNs; however, in this paper, we study opportunistic resource sharing at the entire network level. C. Topology-Awareness in Virtual Network Mapping To the best of our knowledge, there are only two research articles [12, 14] that incorporate topology into virtual network embedding. Butt et al. [14] differentiated substrate resources by introducing scaling factors: Critical Index, which measures the likelihood of a residual substrate network partition due to its unavailability, and Popularity Index, which measures “how many different VNs are affected when a link or a node is unavailable”. Cheng et al. [12] formulated a Markov random walk model to compute the topology-aware resource ranking of nodes in a substrate network; however, in this paper, we observe that we only need to consider a walk from a substrate node to itself or one of its neighbors because the impact is recursive in a Markov chain. VIII. Conclusions This paper re-examines the virtual network mapping prob￾lem in network virtualization from two novel perspectives, i.e., opportunistic resource sharing and topology-aware node ranking, which are incorporated into our proposed framework, ORS T A. ORS T A contains three main parts, opportunistic resource sharing-based local time slot assignment, estimation of residual resources and topology-aware node ranking. The effectiveness of our framework is confirmed by extensive simulations. We are currently seeking the proof of the NP￾Completeness of Problem 1 and are exploring methods of scheduling packets when a collision occurs in a time slot. Acknowledgments We would like to thank Yitong Yin for his Randomized Algorithms and Combinatorics courses, and the anonymous reviewers for their insightful suggestion. This work is supported in part by the National NSF of China under Grant No. 61073028 and No. 61021062; Key Project of Jiangsu Research Program under Grant No.BE2010179; Jiangsu Natural Science Foundation under Grant No. BK2011510; the National 973 Basic Research Program of China under Grant No. 2009CB320705 and No. 2011CB302800; US NSF grants ECCS 1128209, CNS 1065444, CCF 1028167, CNS 0948184, and CCF 0830289. References [1] J. Turner and D. Taylor, “Diversifying the Internet,” in IEEE GLOBE￾COM 2005, vol. 2, 2-2 2005, pp. 6 pp. –760. [2] T. Anderson, L. Peterson, S. Shenker, and J. Turner, “Overcoming the Internet impasse through virtualization,” Computer, vol. 38, no. 4, pp. 34 – 41, april 2005. [3] N. Feamster, L.-X. Gao, and J. Rexford, “How to lease the Internet in your spare time,” ACM SIGCOMM Comput. Commun. Rev., vol. 37, no. 1, pp. 61–64, 2007. [4] N. Chowdhury and R. Boutaba, “A survey of network virtualization,” Computer Networks, vol. 54, no. 5, pp. 862–876, 2010. [5] D. G. Andersen, “Theoretical approaches to node assignment,” Dec. 2002, unpublished Manuscript. [6] R. Ricci, C. Alfeld, and J. Lepreau, “A solver for the network testbed mapping problem,” ACM SIGCOMM Comput. Commun. Rev., vol. 33, no. 2, pp. 65–81, 2003. [7] Y. Zhu and M. Ammar, “Algorithms for assigning substrate network resources to virtual network components,” in IEEE INFOCOM 2006, april 2006, pp. 1 –12. [8] N. Chowdhury, M. Rahman, and R. Boutaba, “Virtual network embed￾ding with coordinated node and link mapping,” in IEEE INFOCOM 2009, 19-25 2009, pp. 783 –791. [9] J. Lu and J. Turner, “Efficient mapping of virtual networks onto a shared substrate,” Washington University, Tech. Rep. WUCSE-2006-35, 2006. [10] M. Yu, Y. Yi, J. Rexford, and M. Chiang, “Rethinking virtual network embedding: substrate support for path splitting and migration,” ACM SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, pp. 17–29, 2008. [11] J. Lischka and H. Karl, “A virtual network mapping algorithm based on subgraph isomorphism detection,” in ACM VISA 2009, 2009, pp. 81–88. [12] X. Cheng, S. Su, Z. Zhang, H. Wang, F. Yang, Y. Luo, and J. Wang, “Virtual network embedding through topology-aware node ranking,” SIGCOMM Comput. Commun. Rev., vol. 41, pp. 38–47, April 2011. [13] M. Chowdhury, F. Samuel, and R. Boutaba, “Polyvine: policy-based vir￾tual network embedding across multiple domains,” in ACM SIGCOMM VISA 2010. New York, NY, USA: ACM, 2010, pp. 49–56. [14] N. Butt, N. Chowdhury, and R. Boutaba, “Topology-awareness and re￾optimization mechanism for virtual network embedding,” in Networking, 2010, pp. 27–39. [15] I. Houidi, W. Louati, D. Zeghlache, P. Papadimitriou, and L. Mathy, “Adaptive virtual network provisioning,” in ACM SIGCOMM VISA 2010. ACM, 2010, pp. 41–48. [16] Auckland Data Trace. http://pma.nlanr.net/traces/long/auck2.html. [17] Q. Zhao and B. Sadler, “A survey of dynamic spectrum access,” IEEE Signal Processing Magazine,, vol. 24, no. 3, pp. 79–89, May 2007. [18] S. Zhang, Z. Qian, B. Tang, J. Wu, and S. Lu, “Opportunistic band￾width sharing for virtual network mapping,” in IEEE Globecom 2011, December 2011. [19] H. Schwarz, D. Marpe, and T. Wiegand, “Overview of the scalable video coding extension of the h.264/avc standard,” IEEE TCSVT, vol. 17, no. 9, pp. 1103 –1120, sept. 2007. [20] S. Zhang, Z. Qian, S. Guo, and S. Lu, “FELL: A flexible virtual network embedding algorithm with guaranteed load balancing,” in IEEE ICC 2011, June 2011. [21] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Technical Report 1999-66, November 1999. [22] “Markov chain,” http://en.wikipedia.org/wiki/Markov chain. [23] V. V. Vazirani, Approximation Algorithms. Berlin: Springer, 2003. [24] J. Fan and M. H. Ammar, “Dynamic topology configuration in service overlay networks: A study of reconfiguration policies,” in IEEE INFO￾COM 2006, april 2006, pp. 1 –12. [25] B. Ishibashi, N. Bouabdallah, and R. Boutaba, “Qos performance analysis of cognitive radio-based virtual wireless networks,” in IEEE INFOCOM 2008, april 2008, pp. 2423 –2431. [26] K. Shiomoto, I. Inoue, and E. Oki, “Network virtualization in high-speed huge-bandwidth optical circuit switching network,” in IEEE INFOCOM 2008 Workshops, april 2008, pp. 1 –6. [27] Y. Zhu, R. Zhang-Shen, S. Rangarajan, and J. Rexford, “Cabernet: connectivity architecture for better network services,” in ACM CoNEXT 2008. New York, NY, USA: ACM, 2008, pp. 64:1–64:6. [28] J. He, R. Zhang-Shen, Y. Li, C.-Y. Lee, J. Rexford, and M. Chiang, “Davinci: dynamically adaptive virtual networks for a customized inter￾net,” in ACM CoNEXT 2008. ACM, 2008, pp. 15:1–15:12. 2416