Wireless Pers Commun DOI 10.1007/s11277-015-2534-8

An Optimal Virtual Network Mapping Model Based on Dynamic Threshold Isha Pathak1 • Deo Prakash Vidyarthi1

 Springer Science+Business Media New York 2015

Abstract To support maximum number of users/applications the concept of virtualization is employed. Network virtualization deals with supporting the concurrent wired/ wireless network activities and utilizing the available physical (substrate) network efficiently by implementing an ideal virtual network embedding algorithm. Mapping virtual network requests to substrate network is an important problem and is done to optimize certain characteristic parameters of the network system. Most of the virtual network mapping models consider, mapping of the network requests on a single physical network. This work proposes a model for the virtual network mapping onto multiple substrate networks with the objective to optimize the revenue for the network service providers. In the process, some other parameters such as acceptance ratio of the VN requests etc. also improve. Experimental study reinforces the efficacy of the proposed model. Keywords Virtual network (VN)  Substrate network (SN)  VN embedding  Graph theoretic approach  Network revenue

1 Introduction Internet is rapidly expanding its usage for various distributed applications in order to facilitate communication and information processing. However, this growing infrastructure has resulted in newer requirements on the functional and behavioral front such as decoupling of network services from hardware for operational simplification, rapidly configuring the machines in order to meet the applications’ specific resource needs etc. To

& Deo Prakash Vidyarthi [email protected]; [email protected] Isha Pathak [email protected] 1

School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi, India

123

I. Pathak, D. P. Vidyarthi

incorporate this fundamental flexibility, alternative network architecture was recently brought to the scene—a Virtual Network Architecture. Network virtualization, often carried out among heterogeneous networks, has been extended from wired to wireless networks [1]. It improves the efficiency and the utilization of the network services enabling customized services and multi-tenancy. New virtualization architecture, as evolved in the wired domain, has been projected in the major wireless domains as well such as cellular network, WiFi etc. Virtualization, regardless of wired or wireless networks, can be considered as a process splitting the entire network system. The future internet design highly relies on Network Virtualization. It refers to the formation of isolated logical network partitions that provide the services similar to that of a traditional dedicated network. Thus, it eases the whole network environment and provides a greater flexibility. In a virtual network (VN) environment, a physical network acts as a host for several heterogeneous virtual networks that are overlaid on it. These virtual networks share the resources of the underlying physical network for the manageability and operability. The physical network, also called substrate network (SN), is managed by multiple infrastructure providers (InPs) which support varied co-existing virtual networks from different service providers (SPs) [2]. Thus, by decoupling service providers from InPs, virtual network architecture brings the much needed de-ossification of the current internet architecture. One of the major problems in the domain of network virtualization is virtual network mapping problem (also known as virtual network embedding (VNE) problem). It deals with the mapping of a virtual network on the substrate network in an optimal manner. To define the VNE problem, the virtual and substrate networks are represented by a graph in which vertices of the graph depict the network nodes and the edges depict the network links. Resource demand of the vertices and edges, of the virtual network, should be less than that available with a substrate network. For example, a 100 MBit/s virtual link cannot be mapped on a 10 MBit/s substrate link. Further, resources available with the substrate network should not be overbooked and be spent economically for an optimal mapping. The challenge of network virtualization to embed multiple resource constrained virtual networks on to the substrate network in order to spend its resources efficiently is known as VNE problem. Some VNE algorithms, proposed in the literature [3, 4] assume that the demands of the virtual networks are known in advance. These are referred as Static VNE algorithms. Few other algorithms use on-demand mechanisms in which resources are allocated to the virtual networks dynamically and are called Dynamic VNE algorithms [5, 6]. Literature also mentions centralized VNE algorithms [7] wherein one centralized entity is responsible for performing the embedding contrary to Distributed VNE algorithms [8] where multiple entities take part in decision making for the embedding. Virtual network embedding focuses on the requirement of future networks and provides guaranteed end-to-end services to the users while fulfilling the optimization goals. The optimality may be decided in terms of various Quality of Service (QoS) metrics viz. profit earned by the InP, security, energy efficiency, cost, acceptance ratio, throughput, algorithm runtime etc. A great deal of work has been done in recent past, considering these metrics, to solve this NP-hard problem. Sun et al. [9] introduced VNE problem for evolving virtual network requests with a dynamic heuristic optimization solution. In this, the authors have considered reconfigurations of VN to dynamically update the VNEs as and when the demand changes. This may however lead to costly resource reconfigurations. Another aspect, termed as survivability in network virtualization, is addressed to offer continuous services to the end users at the time of possible node/link failure during the embedding of virtual networks. The heuristics [10] applied for this problem excels in terms of acceptance

123

An Optimal Virtual Network Mapping Model Based on Dynamic…

ratio, economic profit of the InPs, bandwidth efficiency and response time. An integer linear programming is formulated to solve dynamic VNE problem in [11] with the aim to minimize the resource consumption of the virtual networks. Zhang et al. [12] too consider substrate resources as precious one and has given an opportunistic resource sharing mechanism rather than reserving fixed resources throughout the lifetime of a virtual network. Many meta-heuristic approaches based on Particle Swarm Optimization (PSO) [13], Ant Colony Optimization (ACO) [14], Memetic algorithm [15] have also been introduced for solving the VNE problem. It has been observed that most of the work in VNE problem majorly focuses on single InP and hence single substrate network serving multiple virtual networks. Consideration of single InP is far from reality. Little attention has been paid on VNE problem which considers multiple InPs and hence multiple substrate networks managed by these InPs to fulfill the virtual network requests [16]. The work, in this paper, inclines in the direction where multiple substrate networks are involved to support the mapping of multiple virtual networks. Priority based traffic control algorithms are developed which decide on accepting or rejecting a VN request. These decisions not only satisfy the QoS requirements of the VN requests but also results in optimizing the revenue of the substrate networks owned and managed by the InPs. A concept of ‘reward’, associated with each VN request, is introduced upon successful embedding. In contrast, a ‘penalty’ is imposed when a VN request is rejected. The motivation in introducing the reward/penalty is to account for the QoS and priority requirements of the VN requests. Basically, a mathematical assessment of the trade-off between priority based and non-priority based traffic control virtual network mapping design is made through these parameters. In a network virtualization environment, performance degrades significantly when more number of virtual networks share the resources of the substrate networks. Since each virtual network may have different demands, a traffic control mechanism is warranted to manage the virtual network traffic. One such mechanism is being introduced in this work to meet the QoS guaranteed embedding of VN requests onto multiple substrate networks. Various situations prevail in VN environment where these QoS requirements are explicitly demanded by the virtual networks owing to the variety of services and applications. For example, a virtual network offering voice over IP (VoIP) services may demand high CPU, medium bandwidth and low delays. Video hosting services such as YouTube requires low latency but guaranteed high bandwidth. A virtual network imparting peer-to-peer (P2P) services may count on moderate bandwidth and CPU requirement with no major bounds on delay. Social networking sites e.g. Facebook, Twitter etc. extend their requirements for high parallel processing and low response delay [17]. If these requirements are not satisfied, it will result in poor resource utilization and affect the overall performance. A good amount of work on substrate network allocation gives emphasis primarily on fair allocation. This work simplifies the VNE problem by prioritizing the VN requests. Traffic control algorithms are designed to accept and reject VN requests on multiple substrate networks. This satisfies the varied demands of virtual networks along with optimizing the revenue of the InPs based on the performance criteria. For this, capacity of the substrate network is divided into several priority based threshold values. The system accepts or declines a VN request based on these values. A threshold based traffic control embedding algorithm is proposed with the aim that traffic control can be administered not only on the requirements of the VNs but also on the load characteristics of these requests. The threshold values are adjusted dynamically as and when a change occurs in the workload characteristics. It has been discussed how the substrate networks maximize the revenue by implementing a

123

I. Pathak, D. P. Vidyarthi

threshold based VNE algorithm without violating the continuous requirements of the virtual networks. The algorithm also tries to increase the acceptance ratio of the virtual networks by mapping a larger number of VN requests while using the resources of the multiple substrate networks optimally. The rest of the paper is organized as follows. In Sect. 2, VNE problem on multiple substrate networks is discussed. Section 3 presents the model in which various proposed traffic control algorithms viz. open threshold, strict threshold and dynamic threshold are elaborated. Experimental evaluations of the proposed work have been detailed in Sect. 4. Finally, Sect. 5 concludes the paper giving the avenues for the future work.

2 The VN Embedding Problem The available resources of the substrate network are allocated upon receiving the VN requests from various users for successful embedding. This section describes a general VNE problem in presence of multiple substrate networks. Various terms and definitions have been deliberated upon.

2.1 Virtual Network Model As mentioned, both VN and SN are represented by a graph. VN request graph is a set of virtual vertices interconnected via virtual edges. VN request topology is represented by a weighted undirected graph Gv = (V, Vr, E, Er) where V denotes the vertices in the virtual network Gv, Vr denotes the total units of resources on virtual vertices, E denotes the edges in virtual network Gv and Er denotes total units of resources on virtual edges.

2.2 Substrate Network Model Similar to the virtual network, a substrate network is represented by a weighted undirected graph Gs = (N, Nr, L, Lr) where N denotes the nodes in the substrate network Gs, Nr denotes the total units of resources on substrate nodes, L denotes the links in the substrate network Gs and Lr denotes total units of resources on substrate links. The terms vertices and edges are used in context of virtual networks whereas nodes and links are referred for the substrate networks. For vertices and nodes, CPU is considered as a resource. For links and edges, bandwidth is taken as a resource. Virtual network request arrives as depicted by a virtual network graph with the specifications of the required resources by its vertices and edges. The traffic control algorithm, after analyzing the virtual network request, decides whether to admit a request or reject it. The requirements of a VN request are compared with the available resources of the substrate networks. If no set of substrate networks meets the requirement of the virtual network, the request is rejected informing the service provider which manages the virtual networks, about the rejection. On the other hand, if the VN requirements are met, the selected substrate networks embed the corresponding parts of the virtual network using the VNE algorithm. Each substrate network strives to maximize the revenue and minimize the embedding cost. When all the vertices and the edges of a VN are mapped onto the nodes and links of the SN respectively with the desired objectives, VN is said to be completely embedded on the underlying network. To accommodate more number of co-existing virtual networks, it is important to effectively translate the SP’s request to avail the resources from the substrate networks for

123

An Optimal Virtual Network Mapping Model Based on Dynamic…

5 10

12

12 10

15

15

15

5

5

5

10

10

8

5

10 8

VN1

VN2

VN3

Virtual Network Requests

22

5

30 20

25

20 45

15

30

35

55

28 10

25 18

22

40

20

22

22

30

12

40

15

30 32

22

22

20

10 SN1

SN2

SN3

SN4

Fig. 1 Virtual network requests embedded on substrate networks

the mapping of VNs. Figure 1 exhibit a scenario depicting virtual network requests and the multiple substrate networks serving these requests. The values inside the nodes/vertices show the weights of the nodes/vertices determined by quantifying the CPU as a resource while values on the links/edges show the weights on the links/edges determined by quantifying the bandwidth as a resource.

3 The Proposed Model A virtual network traffic control model is being proposed in which the substrate networks accept/reject new VN requests. Further, the accepted VN requests are mapped onto the substrate networks applying the VNE algorithm. This work addresses priority scheduling issues and proposes a traffic control algorithm which accepts or rejects a VN request with a QoS demand. The algorithm aims for higher revenue and thus optimizes the resource spending goal. For this, the terms ‘reward’ and ‘penalty’ are introduced which are associated with each VN request. A VN request is assigned a reward (a positive value) if it is successfully embedded and a penalty (a negative value) if rejected. Three traffic control algorithms, based on a threshold, are discussed in growing sequence of revenue maximization. These are as follows.

3.1 Open Threshold This is the simplest virtual network traffic control policy, termed as ‘open threshold’. It accepts a new VN request irrespective of its priority (i.e. whether it is a high priority or a

123

I. Pathak, D. P. Vidyarthi

low priority VN request) as long as the substrate networks have sufficient resources to meet it. It is similar to the first come first serve mechanism. This policy will be the base policy against which other two proposed traffic control algorithms will be compared. In this algorithm, there is no distinction on the criteria of priority among the VN requests. The arrival rate of high priority VNs is kH and low priority ones is kL. Thus, the total arrival rate of all the VN requests would be k = kH ? kL. The departure rate, when there are m = (Vm, Vmr, Em, Emr) VN requests in the system is ml, where m [ Gv. The probability H that a new VN request is of high priority is kHkþk and the probability that a new VN request L L . The whole network system behaves as M/M/n/n system [18] and is of low priority is kHkþk L thus the loss rate of all VN requests that arrive (i.e. when they are not served by the substrate networks) is as given in Eq. 1. It is assumed that the total number of substrate networks serving the VN requests is s.  s

kH þkL l

1 s!

Loss rateopen ¼ ðkH þ kL Þ  1þ

Ps

1 i¼1 i!



kH þkL l

i

ð1Þ

The first term, in Eq. 1, is the combined arrival rates of high and low priority VN requests. The second term is the probability that all the resources of the substrate networks serving the VN requests are occupied. For successful VN embedding, the reward of a high priority VN request is rH and of a low priority VN request is rL. For each state m, depicting the virtual network requests in the system, the reward rate is as given in Eq. 2.   kH kL ð2Þ Reward rateopen ¼ wm l  rH  þ rL  kH þ kL kH þ kL where wm = Vmr ? Emr (total unit of resources on the mth virtual network request). On the contrary, if the penalty of a high priority VN request on rejection is pHwhile that of a low priority VN requestis pL, then state s depicts that all substrate networks are used up for embedding and no resources are left. The associated penalty rate is given by Eq. 3. Penalty rateopen ¼ pH  kH þ pL  kL

ð3Þ

The net revenue, under the open threshold system, is calculated by adding the reward rates weighted by their independent probabilities and deducing the penalty rates due to rejection of virtual network requests when all substrate networks are occupied. This is as given in Eq. 4.   s X kH kL Revenueopen ðs; kH ; kL ; l; rH ; rL ; pH ; pL Þ ¼ wm l  rH  þ rL  kH þ kL kH þ kL m¼1  m 1þ

Ps

1 i¼1 i!

1 s!

 1þ

123

kH þkL l

1 m!





Ps



kH þkL l

1 i¼1 i!

kH þkL l s



kH þkL l

i ; ðpH  kH þ pL  kL Þ

i

ð4Þ

An Optimal Virtual Network Mapping Model Based on Dynamic…

3.2 Strict Threshold In the strict threshold traffic algorithm, substrate networks (SH), SH B s are allocated to high priority VN requests only. Remaining substrate networks (sL = s - sH) are allocated explicitly to low priority VN requests. When all the substrate networks allocated to high priority virtual networks are exhausted (correspondingly those to low priority requests), a new arriving high priority VN (low priority VN) is rejected even if there are still available substrate networks to serve low priority VN (high priority VN) requests. In this scenario, it appears that the substrate networks are managing two different queues. One for high priority VN requests with an arrival rate kH and service rate ml and when there are m = (Vm, Vmr, Em, Emr) high priority VN requests in the system being served, m [ Gv. The number of substrate networks assigned to embed these VN requests are SH. The other queue is for low priority VN requests with the arrival rate kL, service rate ml and when there are m = (Vm, Vmr, Em, Emr) low priority VN requests in the system being serviced, m [ Gv and the number of substrate networks assigned to embed these VN requests are sL. Thus, the rate of loss of the VN requests that arrive but not served by the substrate networks is calculated by adding the loss due to high priority VN requests and due to low priority VN requests which is as given in Eq. 5.  s H  sL 1 sH !

Loss ratestrict ¼ kH  1þ

kH l

PsH

1 i¼1 i!

 i þ kL  kH l

kL l

1 sL !

1þ

P sL

1 i¼1 i!

ð5Þ

 i kL l

The corresponding reward rates of wml 9 rH (and wml 9 rL for low priority VNs) are associated for state m when there are m high priority VN requests (low priority VN requests) in the system. SH number of substrate networks are allocated for their service (correspondingly, SL number of substrate networks are allocated for low priority virtual network requests). The penalty rates are subtracted when SH substrate networks are used up and all their resources are exhausted by high priority virtual network requests (correspondingly sL are used up by low priority VNs). Thus, the overall revenue under the strict threshold algorithm is generated as given in Eq. 6.  m 1 kH sH sL X X m! l wm l  rH  þ wm l  rL Revenuestrict ðsH ;sL ;kH ;kL ;l;rH ;rL ;pH ;pL Þ ¼   P H 1 kH i m¼1 m¼1 1 þ si¼1 i! l  m  s H 1 kL m! l

 1þ

PsL

 i  pH kH 

1 kL i¼1 i! l

 sL

1 kL sL ! l

 pL kL  1þ

PsL

 i

1 kH sH ! l

1þ

PsH

 i

1 kH i¼1 i! l

ð6Þ

1 kL i¼1 i! l

3.3 Dynamic Threshold In the dynamic threshold traffic control policy, the s number of substrate networks are divided into three slots: sH, sL and sMsH slot is exclusively allocated to high priority VN requests, sL to low priority VN requests and the remaining sM is shareable to both. When a

123

I. Pathak, D. P. Vidyarthi

high priority or a low priority VN request arrives and if resources are available in the sH slot of substrate networks (correspondingly in sL slots for low priority VN request), the request is accepted otherwise it is rejected. sM slots of substrate networks accepts the requests only after the sH and sL slots for high and low priority VN requests respectively have been exhausted. This algorithm covers the previous two traffic control algorithms. When sM = 0, the algorithm behaves like strict threshold traffic control policy while when sH = sL = 0, it behaves like open threshold policy. In this algorithm, when sL = 0, the high priority VN requests can use the sM slots that are for high and low priority virtual network requests both, as long as there are resources available in sM. However, the low priority VN requests can avail no sH slots that are allocated to high priority virtual network requests. The queue of virtual networks, being served by the sM slot of substrate networks, has an arrival rate of DH ? DL and the service rate equal to l. DH and DL are arrival rates of high priority and low priority VN requests after sH and sL substrate networks have been occupied by high and low priority VNs respectively. DH and DL can be computed as given in Eqs. 7 and 8 respectively,  s H 1 sH !

DH ¼ kH  1þ

PsH

1 i¼1 i!

1 sL !

DL ¼ kL  1þ

kH l

 i

ð7Þ

kH l

 sL kL l

PsL

1 i¼1 i!

 i

ð8Þ

kL l

The overall revenue, in this traffic control policy, is the sum of the revenue earned due to the sH and sL substrate networks assigned to high and low priority VNs only and that earned due to the shared sM substrate networks. It is as depicted in Eq. 9.  m 1 kH sH X m! l wm l  rH  Revenuedynamic ðsH ; sM ; sL ; kH ; kL ; l; rH ;rL ; pH ; pL Þ ¼ PsH 1 kH i m¼1 1 þ i¼1 i! l  m 1 kL sL X m! l þ wm l  rL  P L 1 kL i m¼1 1 þ si¼1 i! l þ Revenueopen ðDH ; DL ; l; rH ; rL ; pH ; pL Þ ð9Þ where Revenueopen can be derived from Eq. 4. For the case when sH = sL = 0, we have DH = kH, DL = kL. This will make the first two terms in Eq. 9 to zero, and hence Revenuedynamic(0, s, 0…) = Revenueopen(s,…), where the dynamic traffic control algorithm slips to open traffic control algorithm. For the case when sM = 0, we have Revenueopen(0,…) = -pHDH - pLDL, and hence Revenuedynamic (sH, 0, sL…) = Revenuestrict(SH, SL,…) where the dynamic traffic control algorithm slips to strict traffic control algorithm. Equation 9 aptly satisfies these conditions. With this reward/penalty concept, the traffic control VN embedding problem can be considered as a revenue optimization problem i.e. building a traffic control algorithm which can dynamically adjust priority reservation for VN requests as the input characteristics of the requests change dynamically. This is so as to maximize the revenue of the

123

An Optimal Virtual Network Mapping Model Based on Dynamic…

substrate networks. To accept high priority or low priority VN requests arriving dynamically, in order to maximize the revenue, the substrate networks are divided into number of priority threshold slots. The analytical solution, to be discussed further in Sect. 4, is employed by the substrate networks at the time of dynamic arrival of VN requests for the revenue maximization of the network virtualization system.

3.4 VN Embedding Algorithm The VN requests, admitted to be served, by the substrate networks through traffic control policy, are embedded using the following VN embedding algorithm. Given two graphs Gv = (V, Vr, E, Er) and Gs = (N, Nr, L, Lr), first a p 9 q matrix R = rij is constructed where p is the number of vertices in the virtual network and q is the number of nodes in the substrate network. Each element rij in R denotes the difference between the resource on vertex i [ p and resource on node j [ q calculated as j - i. All rij C 0 are considered while rij \ 0 are discarded for further calculations. Wese vertex-node resource difference pairs generated from the matrix R, the corresponding set of positive edge-link resource difference pairs are generated that obey the graph theoretic one to one and onto property. These vertex-node resource differences rij with their corresponding edgelink resource difference PErLr are summed up and the minimum summed up difference is retained. The resultant minimum sum of vertex-node resource difference and the corresponding edge-link resource difference gives the residual saved amount of resources of the substrate network Gs that can be used to further serve other VN requests. Thus, the final embedding Evs of graph Gv over Gs is achieved with minimal utilization of substrate resources while fulfilling the VN request throughout. The pseudo code for the Graph Embedding Algorithm is as follows [19]. Algorithm: Graph Theoretic Based One Stage Embedding Algorithm Input: Virtual Network Graph Output: Embedding of Graph

and Substrate Network Graph over Graph

Initialize R: For each , = j-i. For i = 1:p in each column of matrix R If ≥0 Generate the corresponding pairs If pairs fulfill one-one and onto property and to their corresponding Add Else check next pairs

≥0

End End Calculate: Residual = Min( + ) Save the embedding of Graph on Graph Updated Residual is ready to embed further requests of another VN Graph

4 Experimental Evaluation The inputs to the traffic control embedding algorithms are the arrival rates i.e. kH, kL of the VN requests, the departure rate l and the reward and penalty parameters i.e. rH, rL, pH and pL. The outputs are Revenueopen for open, Revenuestrict for strict and Revenuedynamic for

123

I. Pathak, D. P. Vidyarthi

dynamic threshold policies. The number of ways of dividing s into P separate groups is C(s ? P - 1, P - 1) with C(x,y) = x!/(y!(x - y)!). So, to determine the combinations of (sH, sL) in case of strict threshold and (sH, sM, sL) in case of dynamic threshold, same method can be adopted. Thus, the number of combinations to find the revenue for the strict and dynamic algorithms are C(s ? 1,1) = s ? 1 and C(s ? 2,2) = (s ? 2)(s ? 1)/2, respectively. To check every combination of (sH, sL) and (sH, sM, sL) and applying Eqs. 6 and 9, the time required is O(s) for strict and O(s2) for dynamic threshold policies. The number of cases for a given s are finite and is exactly (s ? 2)(s ? 1)/2 under the dynamic threshold algorithm. Thus, it is possible to determine the revenue in each case and hence the set that yields the maximum revenue. Open algorithm and strict algorithm are just the sub-cases of the dynamic algorithmin which the open algorithm generates one special caseresults when sH = sL = 0 and sM = s while the strict algorithm generates s ? 1 special cases for which sM = 0. The threshold values, for all the algorithms, can be calculated using the dynamic algorithm only. In dynamic algorithm, under a given set of parameters, an optimal threshold value for the set (sH, sM, sL) always exists for which the substrate networks revenue can be maximized. The analysis result discussed above can be applied to the dynamic traffic control virtual network mapping algorithm in the following two ways. 1.

2.

Statically generating a table and performing a table lookup at the VN request mapping time. This method can be applied when rH, rL, pH and pL can be determined statically by the network virtualization environment based on the characteristics of the VN requests. In this scenario, the optimal (sH, sM, sL) sets can be evaluated statically for different combinations of kH, kL and l that are expected to change dynamically. Another way is to apply enumeration and Eq. 9 at the time of mapping to select the optimal (sH, sM, sL) threshold values while treating rH, rL, pH and pL also as variables. As the complexity of the algorithm is O(s2), this should be done only sporadically. A process runs in the background to calculate average parameter values and again computes the next set of optimal (sH, sM, sL) values to be used by the network virtualization system for the next period. The system continues using the old set of (sH, sM, sL) to map the VN requests while the background process computes new optimal threshold values.

4.1 Experimental Setup The values for the reward and penalty parameters for the low priority VN requests are set as rL = pL = 1. As the loss due to the rejection of VN request is negligible in comparison to the gain for accepting the same request, it is assumed that rH/rL [ pH/pL. This implies that the loss the system bears from VN request rejection is less compared to the reward received from accepting the same request in an absolute value. The penalty parameter pH for the high priority virtual network requests is set to 2. The proposed model is evaluated on the substrate networks of 20 nodes connected to each other with a probability of 0.5. The weights (resources) on the nodes are uniformly distributed between 20 and 25. The weights (resources) on the links are uniformly distributed between 20 and 30. Similarly, nodes in the virtual networks vary from 2 to 10 connected to each other with a probability of 0.5. The weights (resources) on the vertices as well as edges are uniformly distributed between 1 and 20. The service rate (l) for the VN requests (both high priority and low priority) is set to 1 for all the experiments. The experimental scenario is divided into three sets to analyze the results.

123

An Optimal Virtual Network Mapping Model Based on Dynamic…

Set A (Small)

Set B (Medium) Set C (Large)

This set consists of less number of substrate networks (s = 10) to embed the VN requests. The average arrival rate of high priority VN requests kH and low priority VN requests kL vary in the range of 1–10 for this set. Medium set contains the number of substrate networks (s = 15) to embed the VN requests. The average arrival rates of high priority VN requests kH and low priority VN requests kL vary in the range of 10–15. For the large set, the number of substrate networks considered is (s = 20). The average arrival rates of high priority VN requests kH and low priority VN requests kL vary in the range of 15–20.

Further, the revenue obtained is observed on three instances each of Set A, Set B and Set C by varying the reward parameter for high priority VN requests rH. As discussed, it is possible to have several combinations for (sH, sM, sL) for a given S, only some of them are considered here to maximize the revenue due to space constraint. Also, as all traffic control policies are sub parts of the dynamic traffic control policy, the dynamic and strict threshold control policy is combined into one (dynamic policy) and is compared with the open threshold policy to make the analysis less complex.

4.2 Experimental Results The results, for the above mentioned three sets, have been demonstrated in this section. Simulation is done in Matlab and three traffic control policies on the VNE algorithm are analyzed.

4.2.1 Revenue for Set A (instance 1) In this experiment, the revenue under the open threshold and dynamic threshold policy is generated for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10. Average arrival rates are kH = 2, kL = 8. The changes are observed in Fig. 2. The revenue earned under open threshold algorithm are 123, 154 and 163 while that under dynamic threshold algorithm are 125, 155 and 165 for the above mentioned reward parameters respectively.

4.2.2 Revenue for Set A (instance 2) Another instance of set A generates the revenue under the open threshold and dynamic threshold policy for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10 in this experiment and the changes are observed as can be seen in Fig. 3. Average arrival rates are kH = 4, kL = 5. The revenue earned under the open threshold algorithm are 156, 188 and 224 while that under the dynamic threshold algorithm are 156, 190 and 228 for the above mentioned reward parameters respectively.

4.2.3 Revenue for Set A (instance 3) The third instance of set A generates the revenue under the open threshold and dynamic threshold policy for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10 in this experiment and the changes are observed as can be seen in Fig. 4. Average arrival rates are kH = 7, kL = 2.

123

I. Pathak, D. P. Vidyarthi 180

Fig. 2 Revenue for Set A (instance 1)

160 140

Revenue

120 100 80 60 40 20 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

Revenue(dynamic)

250

Fig. 3 Revenue for Set A (instance 2)

Revenue

200 150 100 50 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

Revenue(dynamic)

The revenue earned under the open threshold algorithm are 284, 327 and 662 while that under the dynamic threshold algorithm are 289, 335 and 680 for the above mentioned reward parameters respectively.

4.2.4 Revenue for Set B (instance 1) In this experiment, medium number of substrate networks are considered and the revenue under the open threshold and dynamic threshold policy for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10 is generated. Average arrival rates are kH = 10, kL = 14. Changes in the revenue are observed as depicted in Fig. 5.

123

An Optimal Virtual Network Mapping Model Based on Dynamic… 800

Fig. 4 Revenue for Set A (instance 3)

700

Revenue

600 500 400 300 200 100 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

Revenue(dynamic)

800

Fig. 5 Revenue for Set B (instance 1)

700

Revenue

600 500 400 300 200 100 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

Revenue(dynamic)

The revenue earned under open threshold algorithm are 254, 399 and 689 while that under dynamic threshold algorithm are 260, 409 and 693 for the above mentioned reward parameters respectively.

4.2.5 Revenue for Set B (instance 2) Another instance of set B generates the revenue under the open threshold and dynamic threshold policy for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10 in this experiment. Average arrival rates are kH = 10, kL = 11. Changes in the revenue are observed as depicted in Fig. 6. The revenue earned under the open threshold algorithm are 363, 421 and 722 while that under the dynamic threshold algorithm are 365, 426 and 756 for the above mentioned reward parameters respectively.

123

I. Pathak, D. P. Vidyarthi 800

Fig. 6 Revenue for Set B (instance 2)

700

Revenue

600 500 400 300 200 100 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

Revenue(dynamic)

4.2.6 Revenue for Set B (instance 3) The third instance of set B generates the revenue under the open threshold and the dynamic threshold policy for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10 in this experiment as can be seen in Fig. 7. Average arrival rates are kH = 15, kL = 10. The revenue earned under the open threshold algorithm are 377, 555 and 921 while that under the dynamic threshold algorithm are 381, 571 and 977 for the above mentioned reward parameters respectively.

4.2.7 Revenue for Set C (instance 1) In this experiment, a large number of substrate networks are considered and revenue is generated under the open threshold and dynamic threshold policy for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10. Average arrival rates are kH = 15, kL = 18. Changes in the revenue are observed as depicted in Fig. 8. 1200

Fig. 7 Revenue for Set B (instance 3)

1000

Revenue

800 600 400 200 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

123

Revenue(dynamic)

An Optimal Virtual Network Mapping Model Based on Dynamic… 1200

Fig. 8 Revenue for Set C (instance 1)

Revenue

1000 800 600 400 200 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

Revenue(dynamic)

1400

Fig. 9 Revenue for Set C (instance 2)

1200

Revenue

1000 800 600 400 200 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

Revenue(dynamic)

The revenue earned under the open threshold algorithm are 594, 714 and 1022 while that under the dynamic threshold algorithm are 601, 720 and 1028 for the above mentioned reward parameters respectively.

4.2.8 Revenue for Set C (instance 2) Another instance of set C generates the revenue under the open threshold and dynamic threshold policy for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10 in this experiment. Average arrival rates are kH = 15, kL = 16. Changes in the revenue are observed as depicted in Fig. 9. The revenue earned under the open threshold algorithm are 335, 682 and 1125 while that under the dynamic threshold algorithm are 336, 685 and 1148 for the above mentioned reward parameters respectively.

123

I. Pathak, D. P. Vidyarthi 2500

Fig. 10 Revenue for Set C (instance 3)

Revenue

2000 1500 1000 500 0 2

5

10

Reward for embedding high priority VNs Revenue(open)

Revenue(dynamic)

4.2.9 Revenue obtained for Set C (instance 3) The third instance of set C generates the revenue under the open threshold and dynamic threshold policy for the high priority VNs reward parameters rH = 2, rH = 5 and rH = 10 in this experiment. Average arrival rates are kH = 20, kL = 15. Changes in the revenue are observed as depicted in Fig. 10. The revenue earned under the open threshold algorithm are 666, 845 and 1850 while that under the dynamic threshold algorithm are 681, 890 and 2253 for the above mentioned reward parameters respectively.

4.2.10 Number of VNs Mapped In this experiment, it is observed that how many virtual networks are mapped after applying both the open and the dynamic threshold algorithms onvarying average arrival rates of high and low priority virtual networks. The arrival rates vary in the range of 1–10, 10–15 and 15–20. The plot in Fig. 11 shows that the dynamic threshold based algorithm performs better in comparison to the open threshold based algorithm under different arrival rates of VN requests.

4.2.11 Average Node Utilization Experiment is also performed to observe the average node utilization with the proposed methods. The average node utilization of the substrate network is measured by averaging the stress of all the substrate nodesof the substrate networks. The stress of the substrate nodes is defined as the total amount of CPU capacity allocated to different virtual nodes nv [ V hosted on the substrate node ns [ N and is calculated using Eq. 10. The comparison on this performance metric for the open and dynamic threshold algorithms is observed. Experiment is performed for 10,000 time units and the result is depicted by a graph in Fig. 12. X Vr ðnvÞ ð10Þ Stress (ns) ¼ nv!ns

123

An Optimal Virtual Network Mapping Model Based on Dynamic…

Number of VNs mapped

Fig. 11 Comparison of number of VNs mapped

20 18 16 14 12 10 8 6 4 2 0 1 to 10

10 to 15

15 to 20

Average arrival rates of high and low priority VNs Open Threshold

Dynamic Threshold

Fig. 12 Average node utilization

The plot in Fig. 12 depicts that the average node utilization for the dynamic threshold based embedding algorithm is better in comparison to the open threshold based embedding algorithm.

4.2.12 Average Link Utilization Another experiment to observe the average link utilization with the proposed methods is also performed. The average link utilization of the substrate network is measured by averaging the stress of all the substrate links of the substrate networks. The substrate links stress is defined as the total amount of bandwidth reserved for the virtual links ev [ E whose substrate paths pass through the substrate link es [ L and is calculated using Eq. 11. The comparison on this performance metric for the open and dynamic threshold algorithms is observed. Experiment is performed for 10,000 time units and the result is depicted by a graph in Fig. 13.

123

I. Pathak, D. P. Vidyarthi

Fig. 13 Average link utilization

Stress (es) ¼

X

Er ðevÞ

ð11Þ

ev!es

The plot in Fig. 13 depicts that the average link utilization for dynamic threshold based embedding algorithm is better in comparison to the open threshold based embedding algorithm.

4.3 Observations The following observations are inferred from the experimental results. • The revenue obtained, with the optimal slots of substrate networks for high, low and sharable VN requests under the dynamic threshold traffic control policy are much higher than open threshold traffic control policy. • In Figs. 2, 5 and 8, for kH \ kL, fewer slots are reserved for the high priority virtual networks relative to the low priority virtual networks and so high priority virtual network requests have to strive to gain the sharable substrate network slots in competition with the low priority ones. Also, when the reward rate for high priority VNs (rH = 2) is not much than that of a low priority VN (rL = 1), the revenue generated for both dynamic and open policies is more or less same. • On the contrary, in Figs. 4, 7 and 10, when kH C kL, more slots of substrate networks are assigned to high priority VN requests to maximize the revenue generated. Also, when reward rate rH for embedding these virtual networks increasesin these cases, the revenue generated by dynamic threshold policy is much higher than that by open threshold policy. • Figure 11 demonstrates the number of virtual networks embedded in all the scenarios of Set A, Set B and Set C. It is observed that when the load of VN requests is less, the VNs mapped after applying both the dynamic and open policies is almost same. On the other hand, if the VN requests increases, the dynamic threshold algorithm is able to map more virtual networks on the substrate networks incomparison to the open policy. • Figures 12 and 13 demonstrate the average node and link utilization for all the scenarios of Set A, Set B and Set C. As the number of VNs mapped using dynamic scenario is more compared to open scenario, it results in high node and link utilization of the substrate networks too.

123

An Optimal Virtual Network Mapping Model Based on Dynamic…

In summary, when the arrival rate kH, reward rH, and penalty pH of high priority VN requests increases, more substrate network slots will be reserved for high priority VNs to maximize the overall revenue. In the opposite case, when the order of magnitude of the above mentioned parameters is lower than that of low-priority VNs, the high priority VNs may have to compete with the low priority VNs to occupy the shareable slots. The arrival rates (kH, kL) also play a vital role in embedding more number of virtual networks. When the load of virtual networks to be embedded is less, the threshold based traffic control policy is insignificant because the probability of accepting a new VN request by substrate networks is high and thus the open policy behaves equally well as threshold based policy. But, if the load of VN requests is moderate or heavy, the effect of threshold based policies is reflected well. It is because the substrate networks can effectively manage their resources (with thresholds) based on the knowledge regarding the requests of the VNs to optimize the revenue.

5 Conclusion In this work, the traffic control VNE strategies are proposed and compared with different threshold based approaches to benefit the system from the perspective of revenue optimization and also satisfy the QoS requirements of VN requests. The equations, derived for revenue generation, help to identify the optimizing (sH, sM, sL) set under specific VN request load and predicts how much revenue the system can gain by adopting the threshold based traffic control policies for VN embedding. It is believed that the VNE algorithm should not only consider the limited substrate networks’ resources but also consider the revenue gain that can be brought to the network by accepting or rejecting VN requests. The reward/penalty parameters are introduced and some threshold based traffic control algorithms are investigated to optimize these parameters. Revenue is computed in terms of these parameters. The expressions for the overall revenue are derived that can be used to accept/reject a VN request and can help the network to determine how much benefit it may gain by embedding VN requests on applying the threshold based traffic control algorithms. The proposed approach is particularly useful when the VN requests may change dynamically. The solution proposed, in this paper, helps adjusting the threshold values accordingly based on the characteristics of VNs request with the objective that network can gain the optimal revenue without disrupting the continuity of requirement and thus embed more and more virtual networks on substrate networks. Future work will concentrate to apply some machine intelligence techniques to increase the revenue for the InPs with efficient embedding. Conflict of interest The author(s) declare that they have no competing interests.

References 1. Hong, K., Lee, S., & Shin, M. (2013). Mobility management in WLAN-based virtualized networks. Wireless Personal Communications, 72(1), 581–596. 2. Schaffrath, G., Werle, C., Papadimitriou, P., Feldmann, A., Bless, R., Greenhalgh, A., Wundsam, A., Kind, M., Maennel, O., & Mathy, L. (2009). Network virtualization architecture: Proposal and initial prototype. In Proceedings of the 1st ACM workshop on virtualized infrastructure systems and architectures ser, VISA’09 (pp. 63–72). New York, NY: ACM.

123

I. Pathak, D. P. Vidyarthi 3. Masti, S. B., & Raghavan, S. V. (2012). Vna: An enhanced algorithm for virtual network embedding. In Proceedings of 21st international conference on computer communications and networks (ICCCN) 2012 (pp. 1–9). 4. Sun, G., Yu, H., Anand, V., Li, L., & Di, H. (2012). Optimal provisioning for virtual network request in cloud-based data centers. Photonic Network Communications, 24(2), 118–131. 5. Zhang, S. L., & Qiu, X. S. (2011). A novel virtual network mapping algorithm for cost minimizing. Journal of Selected Areas in Telecommunications, 29(1), 1–9. 6. Schaffrath, G., Schmid, S., & Feldmann, A. (2012). Optimizing long-lived cloud nets with migrations. In Proceedings of the 2012 IEEE/ACM fifth international conference on utility and cloud computing (pp. 99–106). 7. Chowdhury, M., Rahman, M. R., & Boutaba, R. (2012). Vineyard: Virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Transactions on Networking (TON), 20(1), 206–219. 8. Esposito, F., Di Paola, D., & Matta, I. (2014). On distributed virtual network embedding with guarantees. IEEE/ACM Transactions on Networking. doi:10.1109/TNET.2014.2375826. 9. Sun, G., Yu, H., Anand, V., & Li, L. (2013). A cost efficient framework and algorithm for embedding dynamic virtual network requests. Future Generation Computer Systems, 29(5), 1265–1277. 10. Rahman, M. R., & Boutaba, R. (2013). SVNE: Survivable virtual network embedding algorithms for network virtualization. IEEE Transactions on Network and Service Management, 10(2), 105–118. 11. Melo, M., Sargento, S., Killat, U., Timm-Giel, A., & Carapinha, J. (2013). Optimal virtual network embedding: Node-link formulation. IEEE Transactions on Network and Service Management (IEEE TNSM), 10(4), 356–368. 12. Zhang, S., Qian, Z., Wu, J., Lu, S., & Epstein, L. (2014). Virtual network embedding with opportunistic resource sharing. IEEE Transactions on Parallel and Distributed Systems, 25(3), 816–827. 13. Cheng, X., Su, S., Zhang, Z., Shuang, K., Yang, F., Luo, Y., & Wang, J. (2012). Virtual network embedding through topology awareness and optimization. Computer Networks, 56(6), 1797–1813. 14. Fajjari, I., Aitsaadi, N., Pujolle, G., & Zimmermann, H. (2011). VNE-AC: Virtual network embedding algorithm based on ant colony meta-heuristic. In Proceedings on IEEE international conference communications (ICC) (pp. 1–6). 15. Infu¨hr, J., & Raidl, G. (2014). A memetic algorithm for the virtual network mapping problem. Journal of Heuristics. doi:10.1007/s10732-014-9274-x. 16. Chowdhury, M., Samuel, F., & Boutaba, R. (2010). Polyvine: Policy-based virtual network embedding across multiple domains. In Proceedings of the second ACM SIGCOMM workshop on virtualized infrastructure systems and architectures (pp. 49–56). 17. Le, M., Gallagher, A., Tamir, Y., & Turner, Y. (2009). Maintaining network QoS across NIC device driver failures using virtualization. In Eighth IEEE international symposium on network computing and applications, 2009, NCA (pp. 195–202). 18. Kleinrock, L. (1975). Queueing systems (Vol. 1). New York: Wiley. 19. Pathak, I., & Vidyarthi, D. P. (2014). A graph theoretic algorithm for virtual network embedding. International Journal of Business Data Communications and Networking (IJBDCN), 10(2), 1–14. Isha Pathak did her M.Tech in Information Technology from Banasthali Vidyapeeth in India in the year 2010 and is pursuing her Ph.D. in the area of Virtualization in Cloud Computing. Her research interest includes Cloud and Mobile Networks.

123

An Optimal Virtual Network Mapping Model Based on Dynamic… Deo Prakash Vidyarthi is working as Professor in the School of Computer and System Sciences, Jawaharlal Nehru University, New Delhi. Earlier, he was with the Department of Computer Science, Banaras Hindu University, Varanasi for more than 12 years. Dr. Vidyarthi has published around 60 research papers in various International Journals and Transactions (including IEEE, Elsevier, Springer, Wiley, World Scientific etc.) and around 30 research papers in proceedings of various peer-reviewed conferences in India and abroad. He has contributed chapters in many edited books. He is in the editorial board of many international journals and also in the reviewer’s panel of many international journals. Dr. Vidyarthi has co-authored a book (research monograph) entitled ‘‘Scheduling in Distributed Computing Systems: Design, Analysis and Models’’ published by Springer, USA released in 2009. Another book (edited) by Dr. Vidyarthi is ‘‘Technologies and Protocols for the Future Internet Design: Reinventing the Web’’, by IGI-Global (USA) released in the year 2012. Dr. Vidyarthi is the member of the IEEE, International Society of Research in Science and Technology (ISRST), USA, senior member of the International Association of Computer Science and Information Technology (IACSIT), Singapore and International Association Of Engineers (IAENG). His research interest includes parallel and distributed system, grid and cloud computing, mobile computing.

123