Pattern-Aware Virtual Network Embedding Optimization for Cloud Data Centers Binquan Guoa,c , Zhou Zhangb , Junfeng Zhaia , Zheng Zhanga , Marie Siewc , and Zehui Xiongd a
School of Telecommunications Engineering, Xidian University, Xi’an, P. R. China College of Computer Science and Electronic Engineering, Hunan University, Changsha, P. R. China c Pillar of ISTD, Singapore University of Technology and Design, 487372, Singapore d School of Electronics, Electrical Engineering and Computer Science, Queen’s University Belfast, BT9 5BN Belfast, U.K. Email:[email protected], [email protected], [email protected], [email protected], marie [email protected], [email protected]
arXiv:2609.21302v1 [cs.NI] 18 Sep 2026
b
Abstract—The network virtualization (NV) technology has enabled the sharing of multiple resources among virtual networks (VNs) in cloud data centers. One of the key challenges is to allocate resources in real-time for virtual network request (VNR), which is known as online virtual network embedding (VNE). However, the existing online VNE methods do not exploit the multi-dimensional complementary relationship among diverse VNRs, resulting in the fragmentation and waste of substrate resources. In this paper, we propose the pattern matching based online VNE approach by constructing appropriate matching rules among observed patterns to maximize resources utilization. We devise the clustering based VNRs quantization method and conduct rigorous study on the pattern combination filtering problem by modeling it as an integer linear programming problem. Then, we utilize the column generation to solve it and construct the pattern matching rules. Based on the rules, we propose an online pattern matching VNE algorithm with linear worst-case complexity. Evaluation on a 106-server testbed using Alibaba production cluster trace dataset shows that our algorithm achieves close-to-offline performance and more accepted workloads that outperforms traditional designs by 25%-30%. Index Terms—Cloud data centers, pattern matching, binpacking, column generation, integer programming.
I. I NTRODUCTION As a promising technology, network virtualization (NV) has attracted significant interest in academia and industry and is widely used in data center networks. It enables multiple heterogeneous virtual networks (VNs) to share a common substrate network (SN), addressing the rigidity of traditional architectures. Each VN specifies its demands in a virtual network request (VNR), including computing resources for nodes and bandwidth for links. Efficient real-time mapping of VNRs onto the SN, known as online virtual network embedding (VNE) [1], is essential. However, the unpredictable arrivals and diverse topologies of VNRs complicate embedding decisions and require effective admission control. This work was supported by A*STAR under its IAF-ICP (H25MCP3438). The corresponding authors are Zhou Zhang and Marie Siew.
Recently, VNE has attracted significant research attention. It has been shown that VNE with joint node and link constraints can be reduced to the multi-way separator problem, which is NP-hard [2]. Existing approaches are generally classified into exact and heuristic methods [1]. Exact methods target offline scenarios and solve MIP or ILP formulations with high computational complexity [3]. For online scenarios, most heuristic methods adopt two-stage node and link mapping strategies, which reduce complexity but may cause resource fragmentation and low utilization [4]. Hybrid approaches combine heuristic and exact methods to balance complexity and performance [5]. However, these methods often ignore historical information and VNR characteristics, leading to inefficient resource allocation. Theoretically, traditional methods [2], [5] mainly focus on the matching between VNRs and resources. In fact, inspired by [6], VNE can be transformed to a pattern matching problem, so that the online algorithm can approximate the offline performance. However, the matching method in [6] is designed for single dimension resource and cannot be directly applied to multi-dimensional scenarios. The reason is that the complementary rules in multiple dimensions cannot be formulated without the pattern characteristics of VNRs, where the historical data is required. Authors in [7] considered the characteristics of historical data. However, their objective is to maximize the acceptance rate, which cannot guarantee the resource utilization of substrate nodes. Moreover, the authors in [8] aimed at maximizing the utilization of physical resources through reinforcement learning. However, the prediction based model suffers from unbalanced resource allocation and cannot widely adapt to the production data center environment. In this paper, we propose a pattern matching based online VNE framework that maximizes resource utilization through appropriate matching rules. We devise the clustering based VNR quantization method and model the pattern combination filtering problem as an integer linear programming problem.
Then, we utilize the column generation method to solve it and construct the pattern matching rules. Based on the rules, we propose Online Pattern Matching VNE algorithm with worst case complexity of O(N ). Testbed evaluation on the Alibaba cluster trace shows near offline performance and 25%-30% improvement over traditional methods in accepted workloads. II. S YSTEM M ODEL AND P ROBLEM F ORMULATION A. Substrate Network We consider a typical substrate network composed of a large number of servers in a data center, connected via a switch-centric topology. The network is modeled as an undirected weighted graph, where each node represents a server and each edge represents a link between servers. Resources are categorized into node and link types. Node resources include CPU, memory, and disk, while link resources refer to the bandwidth between servers. The substrate network resource is denoted by G = (N , E, AN , AE ), where • N = {Nq |1 ≤ q ≤ |N |} is the set of substrate nodes, and Nq denotes a server. • E = {(Nu , Nv )|Nu ∈ N , Nv ∈ N , u ̸= v} is the link set of the substrate network. Specifically, each pair of servers is connected, thus |E| = |N | · (|N | − 1)/2. • AN = {C(Nq )|1 ≤ q ≤ |N |} represents the node attribute of the substrate network, where C(Nq ) = [c1q , c2q , ..., cdq ] is the capacity vector of node Nq . Each element in C(Nq ) corresponds to the capacity of one type resource at node Nq . • AE = {b(u,v) |(Nu , Nv ) ∈ E} represents the link attribute of the substrate network. Specifically, b(u,v) is the weight value of bandwidth for the link (Nu , Nv ). It is assumed b(u,v) = b(v,u) , ∀Nu , Nv ∈ N , u ̸= v. Using the b(u,v) , the bandwidth capacity of the node Nq denoted as cbq can be calculated as cbq = max {b(q,v) or b(v,q) }, q ̸= v, ∀Nq ∈ N . ∀Nv ∈N
Furthermore, during the embedding process, the remaining resource vector at node Nq is denoted as Rcq = [rq1 , rq2 , ..., rqd ]. Similarly, the remaining bandwidth resource at b b link (Nu , Nv ) is denoted as ruv . Using the ruv , the remaining b bandwidth of the node Nq denoted as rq is calculated as b b rqb = max {rqv or rvq }, q ̸= v, ∀Nq ∈ N . ∀Nv ∈N
Besides, we assume that servers are fully connected as in [8]. For any two nodes Nu and Nv , as long as their remaining bandwidth is nonzero, there exists at least one path between them with capacity min(rub , rvb ), which can be obtained using shortest path algorithms such as Dijkstra’s algorithm. B. Virtual Network The users send a virtual network request (VNR) in the form of an undirected graph Gv = {N v , E v , AN v , AE v }. Each Gv is comprised of a set of virtual machines (VMs)
denoted as N v = {Vi |1 ≤ j ≤ |N v |} and a set of virtual links E v = {(Vi , Vj )|Vi ∈ N v , Vj ∈ N v , i ̸= j}. Each VM Vi is associated with resource demand vector Div ∈ AN v , where Div = [d1i , d2i , ..., ddi ]. The bandwidth demand of the virtual link between VM Vi and Vj is denoted by bvij . Then, the bandwidth demand of a VM Vi is calculated as X dbi = bvij , i ̸= j, ∀Vi ∈ N v . ∀Vj ∈N v
C. Problem formulation For each upcoming VNR, we define the binary variable xiq to indicate if VM Vi is assigned to server Nq . If Vi is assigned to Nq , xiq = 1, and otherwise 0. Further, for each VM, by merging its bandwidth demand dbi into its resource demand vector Div , we can form an augmented demand vector D̃i , where D̃i = [d1i , d2i , ..., ddi , dbi ]. Similarly, for each server Nq , we combine its remaining resource vector Rcq with its remaining bandwidth rqb to form an augmented remaining vector R̃cq = [rq1 , rq2 , ..., rqd , rqb ]. Its augmented capacity vector can be constructed by combining the resource vector C(Nq ) with cbq as C̃(Nq ) = [c1q , c2q , ..., cdq , cbq ], which is (d + 1)-dimensional like D̃i and R̃cq . Objective: The objective of online VNE is to maximize the average resource utilization while satisfying resource capacity constraints. The objective function is written as P cx −r x wx · Nq ∈N q cx q X q X max U = , x x xiq ∈x |{q| (c − r ) = ̸ 0, ∀Nq ∈ N }| q q x∈{1,d+1} x∈{1,d+1}
|
{z
E1
where U is the average resource utilization of the servers, and wx is the predefined weight factor of the x-th type resource such as CPU, memory, and bandwidth of each node. The symbol | · | is the cardinality of a set, and expression E1 represents the number of servers that are currently used. We consider that each type of different resources have the 1 same weight, i.e., wx = d+1 , thus U is calculated as P 1 Nq ∈N [(C̃q − R̃q ) ⊙ C̃q ] U= , |{q|[(C̃q − R̃q ) ⊙ 1T ] ̸= 0, ∀Nq ∈ N }| where 1 ∈ R(d+1)×1 , and [(C̃q − R̃q ) ⊙ 1T ] is the sum of each type resource utilization of node Nq . The symbol ⊙ is the Hadamard product. Constraints: For each upcoming VNR Gv , the following constraints must be satisfied. 1) Place at most once: Each VM can be assigned to only one machine as specified in (1), meaning no VM is split. However, this does not restrict how many VMs from the same VNR can be embedded on a single server. X xiq <= 1, ∀Vi ∈ N v . (1) Nq ∈N
}
2) Accept all VMs or reject: A VNR must be mapped as a whole, meaning all its VM demands must be satisfied as in (2); otherwise, the entire VNR is rejected. X X xiq = xjq , ∀Vi , Vj ∈ N v , i ̸= j. (2) Nq ∈N
Nq ∈N
3) Capacity constraints: When a VM is placed on a server, the resources in all dimensions must be sufficient to meet the total demand of all VMs assigned to it, as in (3). X dxi · xiq <= rqx , ∀Nq ∈ N , ∀1 ≤ x ≤ d. (3) Vi ∈N v
4) Mutual exclusion (optional): For security and reliability, VMs from the same VNR should be placed on different servers as in (4), which is optional. X xiq ≤ 1, ∀Nq ∈ N (4) Vi ∈N v
Finally, the online VNE problem can be formulated as OP : max U xiq ∈x
s.t. (1) − (4). The OP is an online multi-dimensional bin packing problem and is NP-hard. Even with optimal placement for each incoming VNR, long-term resource utilization remains suboptimal. In online settings, resource fragmentation often occurs when one resource type is exhausted while others remain unused, and load balancing cannot fully prevent this accumulation. Therefore, we aim to design an online approach that achieves near-offline performance by exploiting VNR patterns. III. T HE PATTERN MATCHING BASED VNE A PPROACH In this section, we propose an online VNE method based on quantized VNR patterns that exploits multi-dimensional complementarity, consisting of two stages. A. Quantization-Based VNR Pattern Representation In order to overcome the complexity caused by the diversity of VNR, we quantify the VNRs to group similar VNRs together and divide them into disjoint sets. Definition 1 (VNR pattern). A VNR pattern refers to a complete set composed of a group of VMs from the real-world VNRs with similar resource demands, in which the Euclidean distance between the maximum and minimum elements is less than a specific parameter, and the demand of the VMs within it can be uniformly represented by the maximum element of the set with the allowable waste. In a given period, we have a set of historical VNRs H. VNR patterns can be obtained by applying clustering models to H. If the number of clusters is known in advance, the KMeans algorithm can be used to quantify both historical and newly arrived VNRs. In Algorithm 1, we present a pattern quantization procedure to obtain VNR patterns. Firstly, assume the number of patterns does not exceed kmax . Each pattern can be denoted by Xˆh , 1 ≤ h ≤ kmax .
Algorithm 1 Clustering based Pattern Quantization Input: Historical VN dataset H = {Gv1 , Gv2 , ..., Gvh } Output: Pattern quantization model m∗, pattern maximum point representative set P, pattern statistics p(P). 1: Initialize k ∗ = −1, P = { }, p(P) = { }, X = { }. 2: for each VN Gvl in VN dataset H do 3: for each VM Vi in VN Gvl do 4: X ←− X ∪ {D̃i }. 5: for each k in [1, 2, ..., kmax ] do (parallel) 6: Define a candidate model m = KMeans(k). 7: Feed X for training the model by calling m.fit(X ). 8: Classify X into k categories X̂h ⊆ X , h ∈ [1, 2, ..., k]. 9: if ∀h ∈ [1, 2, ..., k], ||max(X̂h ) − min(X̂h )||2 ≤ θ then 10: m∗ ←− m, k ∗ ←− k, break. 11: if k∗ ≤ 0 then 12: return // No feasible model found, and stop procedure. 13: for each h ∈ [1, 2, ..., k ∗ ] do X̂h | 14: P ←− P ∪ {max(X̂h )}, p(P) ←− p(P) ∪ { ||X | × 100%} 15: return m∗ , P, p(P).
Firstly, we define a threshold θ to represent the Euclidean distance between the minimum element min(Xˆh ) and the maximum element max(Xˆh ) within each pattern. By traversing over the historical data, the augmented vector of all VMs are collected into set X as the input of the clustering algorithm. For each 1 ≤ k ≤ kmax , we initialize the KMeans model and feed X for training the parameters. The value of k will be adjusted repeatedly until the maximum Euclidean distance conditions ||max(X̂h ) − min(X̂h )||2 ≤ θ, 1 ≤ h ≤ k are satisfied. If all the conditions are satisfied, the resulting quantization model m∗ is obtained, and the maximum element max(Xˆh ) of each set Xˆh is taken as the representative element to form a pattern set P. Finally, the statistics of patterns are obtained and collected into a set p(P) = {p(Pz )|∀Pz ∈ P}. B. Statistics-Aware Pattern Combination Filtering Problem Based on the quantized VNR patterns, we further define the concept of pattern combination to represent a feasible packing scheme of substrate nodes. Definition 2 (Pattern combination). A pattern combination is defined as a vector Br , where each element ahr ∈ Br is a nonnegative integer representing the maximum number of the h-th pattern expected in a packing scheme Br , h ∈ [1, 2, ..., k ∗ ]. During virtual network embedding, each server will be labeled with one pattern combination, e.g., Sq ← Br = (a1r , a2r , ..., ahr , ..., ak∗ r )T , indicating the server Sq is expected to host at most ahr numbers of h−th pattern. Let Ψx be the expected utilization threshold for x-type resource, where Ψx ∈ (0, 100%], x ∈ [1, d + 1]. We regard a pattern combination whose resource utilization upper bound
in every dimensions are higher than the expected thresholds as a superior combination. Obviously, one superior combination cannot fit all real-world VNR distributions. Consider a scenario, in which the probability of pattern Pless is small, applying a superior combination expecting a large number of Pless , will inevitably lead to the idleness of servers, since pattern Pless may not occur for a long period. Therefore, we need to design a method to filter the superior patterns combinations suitable for the given VNR statistics. In order to obtain the superior pattern combinations for a given VNR statistics, we formulate the Statistics-Aware Pattern Combination Filtering Problem. Firstly, let B be the set composed of all pattern combinations, where each Br ∈ B represents a pattern combination. We define an integer variable λBr , where λBr > 0 means that the combination Br will be selected as a matching rule, otherwise λBr = 0. Moreover, we define a companion variable for each λBr as λ̃Br ∈ {0, 1}, and the two variables are associated in the following way. λBr − 1 ≤ M · λ̃Br − ϵ · (1 − λ̃Br ).
(5)
In (5), if λBr > 0, then λ̃Br = 1. M is a big positive constant. Let cx ∈ C be the capacity of x−type resource, x ∈ [1, d+1]. The Statistics-Aware Pattern Combination Filtering Problem is formulated as X MP :min λBr ,
pattern Ph ∈ P. Then, we remove the constraints (7) and define the restricted master problem (RMP) as X RMP :min λBr , Br ∈B̂
s.t.
X
ahr λBr ≥ p(Ph )M, ∀h ∈ [1, 2, ..., k ∗ ]
Br ∈B̂
(9) λBr ∈ N, ∀Br ∈ B̂.
RMP is initialized by a set of feasible pattern combinations B̂, and each pattern corresponds to at least one feasible pattern combination in B̂. In practice, we can form an initial B̂ by initializing k ∗ pattern combinations. For instance, suppose each pattern combination contains only one pattern, e.g. Ph , then the maximum feasible number ⌊ PC̃h ⌋ of this pattern in a server can be calculated. By building a k ∗ dimensional vector with h-th value as ⌊ PC̃h ⌋ and filling other positions with 0, a feasible pattern combination for pattern Ph can be obtained. Then, the linear programming relaxation of RMP is solved to obtain dual variables πh corresponding to constraints (6). X LRMP :min λBr Br ∈B̂
s.t. (9) λBr ≥ 0, ∀Br ∈ B̂.
Br ∈B
s.t. (5), X
ahr λBr ≥ p(Ph )M, ∀h ∈ [1, 2, ..., k ∗ ], (6)
(11)
The dual variables πh are provided to the pricing problem PP to generate new superior pattern combination. In detail, ∗
Br ∈B̃
X
(10)
ahr Phx ≥ Ψx λ̃Br , ∀Br ∈ B,
(7)
PP :max
ahr ∈Br
λBr ∈ N, λ̃Br ∈ {0, 1}, ∀Br ∈ B,
(8)
Phx
is the x-th value in Ph , x ∈ [1, d + 1]. Note where that MP is in the form of ILP, and its aim is to solve a subset of pattern combinations with desired average resource utilization expectation, while covering all patterns of the given VNR statistics. When |B| is small, it can be solved by the brute-force search. However, when |B| is large, searching for its optimal solution will be intractable. Therefore, we design a column generation based method to reduce its solving complexity. C. Column Generation-Based Pattern Combination Selection Intuitively, solving MP requires all pattern combinations in advance, which is intractable since the number of combinations |B| grows exponentially with the number of VNR patterns and resource types. To address this, column generation (CG) is used to iteratively generate better pattern combinations using only a small subset of variables in each iteration [9]. Initially, a small set of feasible pattern combinations B̂ is used for MP, including at least one combination for each
s.t
k X h=1 k∗ X h=1 k∗ X
πh zh Phx zh ≤ cx ,
(12)
Phx zh ≥ Ψx cx ,
(13)
h=1
zh ≥ 0, 1 ≤ h ≤ k ∗ , zh ∈ N,
(14)
where integer variable zh denotes the number of pattern Ph included in a new pattern combination. The constraint (12) ensures the new generated combination cannot exceed the total capacity of substrate resources among each dimension. PP is designed to find feasible pattern∗ combinations with the Pk minimum reduced cost ψ = 1 − h πh zh . LRMPs and PPs are solved iteratively until the termination condition is met. If ψ < ϵ, the new generated pattern combination from PP is added to LRMP. If ψ ≥ ϵ, the new generated pattern combination from PP is no longer added to LRMP. Finally, to guarantee the optimal solution, MP is solved using existing columns, by replacing B with B̂ and utilizing the Branch and Cut (B&C) algorithm [9], [10]. The ϵ is a negative small constant near to zero, typically
Algorithm 2 Column Generation Based Superior Pattern Combination Selection Algorithm Input: Quantized pattern set P, and its statistics p(P). Output: Pattern combination set S. 1: Initialize A = [ PC̃ , ..., PC̃ , ..., PC̃ ∗ ], B̂ = {ah |ah ∈ 1 h k ⌊diag(A)⌋}. 2: Solve the LRMP with B̂ to obtain the dual variable π and put π into PP. P 3: while ψ = 1 − h πh zh ≤ ϵ do 4: Solve PP by B&C to obtain new column Zopt and ψ. 5: Add new column to current LRMP( B̂ ←− B̂∪{Zopt }). 6: Go to 5. 7: Solve MP with B̂ using the B&C to obtain optimal λB̂ . 8: Set S = {B̂x |λBx > 0, ∀B̂x ∈ B̂}, 9: return S.
in the order of −10−4 , allowing numerical inaccuracies in the computed reduced costs [9]. The detailed procedure is presented in Algorithm 2. Note that |B̂| can be much smaller than |B|, which shortens the solution procedure. D. Online Pattern Matching VNE Algorithm With the filtered pattern combinations S, the Online Pattern Matching Algorithm is proposed to quickly embed each VNR. We regard each pattern combination Sx ∈ S as a scheme (or a tag), which is used to label each server during node mapping. For clarity, we group the vectors in S to form a scheme matrix S, and each column in S corresponds to a scheme. During the online embedding, we label each active server with a scheme and update its residual vector. The residual vector is initialized to be the same as the scheme vector. A VM with pattern Ph can only be assign to servers whose h-th value of the residual vector is larger than zero. When a VM of pattern Ph is embedded into a server, the hth value of its residual vector is subtracted by 1. The scheme vectors and the residual vectors of servers are collected into L and M respectively, and both matrixs will be updated simultaneously. The new coming VNRs will retrieve available resources from matrix M. Initially, we label a small set of servers with arbitrary schemes, and update L and M accordingly. When a VNR arrives, we quantify each VM Vi in it to obtain its corresponding pattern x. The x-th row of M will be checked to determine whether there are available resources for pattern x. If there exists one element, e.g., the y-th element, in the x-th row is greater than 0, the VM will be mapped onto the y-th server. Otherwise, a new server will be labeled with a scheme containing pattern x and used to place VM Vi . Only when all the servers run out of resources for patten x, will the VNR be rejected. Moreover, a temporary set can be maintained to avoid conflict, when mutual exclusion constraint is required. The detailed procedure is specified in Algorithm 3.
Algorithm 3 Online Pattern Matching VNE Algorithm Input: Upcoming VNRs, SN G = (N , E) Output: Embedding decision for each Gv −→ G. 1: Initialization: 2: Build a matrix S ∈ R|S|×|P| from S, where each column is a matching rule, and each row corresponds to a pattern. 3: Label a few servers with arbitrary columns from S. 4: Initialize the resource and the residual matrix L and M. 5: while new VN Gv comes do 6: Build a temporary set Yi = { } to handle conflicts. 7: for each VM Vi in VN Gv do 8: Classify D̃i into pattern x ∈ P using model m∗ . 9: Select the x-th row of M as candidate set F . 10: Mute conflicts nodes by setting Fρ = 0, ∀ρ ∈ Yi . 11: if ∄Fj ∈ F, Fj > 0 and |F | = |N | then 12: Reject Gv and roll back L and M; break. 13: if ∃Fj ∈ F, Fj > 0 then 14: Assign VM Vi to server Nj and add Nj to Yi . 15: Update the residual matrix M. 16: else 17: Select a scheme Sy ∈ S containing x. 18: Label a new server Nnew with scheme Sy . 19: Assign Vi to server Nnew and add Nnew to Yi . 20: Update the matrix L and M using Sy . 21: Map virtual nodes in Gv to servers in Yi respectively. 22: Map virtual links in Gv using shortest path algorithm.
To map a virtual node, only a sparse vector with at most |N | non-negative integer values is checked. Thus, the worst case complexity of Algorithm 3 for a VNR is O(|N | · |Nv |). In addition, the substrate nodes that can no longer host some patterns can be muted in advance to reduce the complexity. Compared with the traditional online (d + 1)-dimensional mapping methods, whose computational complexity is O(|N |d+1 ·|Nv |), the performance is improved by at least |N |d . IV. T ESTBED E VALUATION A. Testbed Environment Our testbed has 106 servers, connected via SDN-enabled switches via a spine-leaf topology. Each server is equipped with 64-vCPUs, 256G memory, forming a cluster orchestrated by Kubernetes. The transmission rate between any pair of servers is 10Gbps. Three servers are configured as master, which are cordoned off and not allowed to host VMs. We define a JSON format to describe each VNR, and implement the proposed algorithm using python language. The output of the algorithm is in the form of a YAML file and sent to Kubernetes for execution. In the process pattern combination filtering, the column generation procedure is implemented with the help of both the simplex method in CVX [11] and the Branch and Cut algorithm in Gurobi [12].
cpu utilizaiton mem utilizaiton net utilizaiton 0
1000
2000
3000
4000
5000
40
20
0
6000
cpu utilizaiton mem utilizaiton net utilizaiton 0
80
60
40
cpu utilizaiton mem utilizaiton net utilizaiton
20
0
0
1000
2000
3000
4000
5000
Number of upcoming VMs
2000
3000
4000
5000
80
60
40
20
0
6000
cpu utilizaiton mem utilizaiton net utilizaiton 0
Number of upcoming VMs
Best Fit Algorithm
6000
Average resource utilization (%)
Average resource utilization (%)
Number of upcoming VMs
100
1000
80
60
40
cpu utilizaiton mem utilizaiton net utilizaiton
20
0
0
1000
2000
3000
4000
5000
Number of upcoming VMs
1000
2000
3000
4000
5000
6000
Number of upcoming VMs
Kubernetes Default Algorithm
100
6000
Average resource utilization (%)
0
60
Load Balance Algorithm
100
Random Algorithm
100
80
60
40
cpu utilizaiton mem utilizaiton net utilizaiton
20
0
0
1000
2000
3000
4000
5000
6000
Number of upcoming VMs
Average accepted number of VMs
40
80
Average resource utilization (%)
60
20
First Fit Algorithm
100
80
Average resource utilization
Average resource utilization (%)
Pattern Matching Algorithm
100
1400 1200 1000 800
Pattern Matching Algorithm First Fit Algorithm Load Balance Algorithm Best Fit Algorithm Kubernetes Default Algorithm Random Algorithm
600 400 200 0 0
1000
2000
3000
4000
5000
6000
Number of upcoming VMs
Fig. 2. Comparison of different algorithms in terms of the accepted VMs.
Fig. 1. Comparison of different algorithms in terms of utilization.
V. C ONCLUSION B. Trimmed Alibaba Production Cluster Trace Dataset We use the Alibaba production cluster trace dataset [13], which includes 4030 servers and 71,476 VMs. From this, we extract a subset of 142 servers with only online services, resulting in 753 applications and 1,698 VMs. Each VM has CPU and memory demands, and its bandwidth demand is defined as the maximum traffic rate during its lifetime. After normalization, we set the quantization threshold to 1% for each resource type, yielding 49 patterns. VNRs are then generated based on these patterns for evaluation. C. Performance Comparison Similar with work [7], we compared the proposed algorithms with five classical online methods, i.e., First Fit algorithm, Load Balance algorithm, Best Fit algorithm, Kubernetes Default algorithm and Random algorithm respectively, and carried out 20 comparative experiments using stressful workloads on the testbed. For each time, we clean up all the VMs in the 103 servers before we run an algorithm. The VNRs used in each comparison experiment for different algorithms are the same. The number of VMs in each VNR is randomly set according to the distribution of VM number of applications in the dataset. We averaged over 20 runs. In Fig. 1, we plot the resource utilization curve versus the arrival of VNRs for six different algorithms. It can be seen that the pattern matching algorithm may reject a VM even though it fits one server for further performance, thus the VM can achieve higher and more balanced long-term resource utilization. On the contrary, for the other five algorithms, the utilization of a CPU resource grows very fast, resulting in the fragmentation and under-utilization of other resources. In Fig. 2, we compare the average number of maximum VMs accepted by different algorithms. Compared with the other five algorithms, the proposed algorithm can hold 25%30% more VMs, which shows that taking advantage of the admission control mechanism and the complementary relationship can significantly improve the overall performance.
In this paper, we have proposed a pattern matching based online VNE approach for cloud data center networks, which exploits the complementary relationship of VNRs to maximize resource utilization. Testbed evaluation using Alibaba production cluster trace dataset has shown that our algorithm achieves close-to-offline performance and more accepted workloads that outperforms traditional designs by 25%-30%. In future, we will develop more dynamic mechanisms and adjustment features to adapt the production environment. R EFERENCES [1] A. Fischer, J. F. Botero, M. T. Beck, H. De Meer, and X. Hesselbach, “Virtual network embedding: A survey,” IEEE Communications Surveys & Tutorials, vol. 15, no. 4, pp. 1888–1906, 2013. [2] M. Dolati, S. B. Hassanpour, M. Ghaderi, and A. Khonsari, “Deepvine: Virtual network embedding with deep reinforcement learning,” in IEEE Conf. Computer Commun. (INFOCOM WKSHPS), 2019, pp. 879–885. [3] M. Melo, S. Sargento, U. Killat, A. Timm-Giel, and J. Carapinha, “Optimal virtual network embedding: Node-link formulation,” IEEE Trans. Netw. Serv. Manag., vol. 10, no. 4, pp. 356–368, 2013. [4] M. Chowdhury, M. R. Rahman, and R. Boutaba, “Vineyard: Virtual network embedding algorithms with coordinated node and link mapping,” IEEE/ACM Trans. Netw., vol. 20, no. 1, pp. 206–219, 2011. [5] H. Cao, Y. Zhu, G. Zheng, and L. Yang, “A novel optimal mapping algorithm with less computational complexity for virtual network embedding,” IEEE Trans. Netw. Serv. Manag., vol. 15, no. 1, pp. 356– 371, 2017. [6] C. C. Lee and D.-T. Lee, “A simple on-line bin-packing algorithm,” Journal of the ACM (JACM), vol. 32, no. 3, pp. 562–572, 1985. [7] D. Naori and D. Raz, “Online placement of virtual machines with prior data,” in IEEE Conf. Computer Commun. (INFOCOM), 2020, pp. 2539–2548. [8] H. K. Thakkar, C. K. Dehury, and P. K. Sahoo, “Muvine: Multi-stage virtual network embedding in cloud data centers using reinforcement learning-based predictions,” IEEE Journal on Selected Areas in Communications, vol. 38, no. 6, pp. 1058–1074, 2020. [9] J. Desrosiers and M. E. Lübbecke, “A primer in column generation,” in Column generation. Springer, 2005, pp. 1–32. [10] B. Guo, Z. Zhang, Y. Yan, and H. Li, “Optimal job scheduling and bandwidth augmentation in hybrid data center networks,” in IEEE Global Commun. Conf., 2022, pp. 5686–5691. [11] M. Grant and S. Boyd, “Cvx: Matlab software for disciplined convex programming, version 2.1,” 2014. [12] L. Gurobi Optimization, “Gurobi optimizer reference manual,” 2021. [Online]. Available: http://www.gurobi.com [13] J. Guo, Z. Chang, S. Wang, H. Ding, Y. Feng, L. Mao, and Y. Bao, “Who limits the resource efficiency of my datacenter: An analysis of alibaba datacenter traces,” in 2019 IEEE/ACM 27th International Symposium on Quality of Service (IWQoS). IEEE, 2019, pp. 1–10.