虚拟网络嵌入（Virtual Network Embedding，VNE）是网络虚拟化和网络功能链编排中的基础性问题。简单来说，就是在一个物理网络（通常称为 substrate 网络）之上，为若干个虚拟网络请求（Virtual Network Request，VNR）分配节点资源和链路资源，使得每个虚拟节点映射到不同的物理节点，每条虚拟链路映射到一条物理路径，且路径上的带宽容量满足要求。这个问题看似直观，但已经被证明是 NP 难的，节点映射和链路映射两个子问题相互耦合，直接求解整数线性规划在大规模场景下开销极大。本文将使用 R 语言从零实现一个基于贪婪排序的启发式 VNE 求解算法，涵盖图建模、节点排序、链路映射和评价指标计算等完整环节。
一、VNE 问题的形式化描述与建模思路
在动手写代码之前，先把问题的数学模型理清楚。设物理网络为一个加权无向图 Gs = (Ns, Es)，其中每个物理节点带有 CPU 容量属性，每条物理链路带有带宽容量属性。类似地，一个虚拟网络请求为 Gv = (Nv, Ev)，每个虚拟节点有 CPU 需求，每条虚拟链路有带宽需求。
嵌入过程分为两个阶段：节点映射和链路映射。节点映射是一个函数，把每个虚拟节点指派到一个尚未被该请求占用的物理节点，且该物理节点的剩余 CPU 不小于虚拟节点的需求。链路映射则把每条虚拟链路映射到物理网络中的一条无环路径，路径上每一段的剩余带宽都要不小于虚拟链路的需求。嵌入成功的判定条件是所有节点和链路的约束都满足，否则该请求被拒绝。
在 R 中建模网络图最方便的做法是使用 igraph 包，它提供了图对象的创建、属性赋值、最短路径计算等全套能力。物理网络通常用 Waxman 随机拓扑或者基于度的拓扑生成器产生，物理节点的 CPU 容量取 100 左右的随机数，链路带宽取 50 左右的随机数，这是文献仿真中比较常见的设定。虚拟网络请求则规模较小，一般包含 2 到 10 个节点，到达过程常用泊松过程模拟，平均到达率和平均生命周期分别取常见值即可。
二、基于资源排序的贪婪节点映射算法
启发式算法的核心思想是把节点映射和链路映射解耦，先做节点映射再做链路映射，并且利用节点资源排序来降低链路映射失败的概率。经典的排序指标是节点的综合资源能力，定义为节点 CPU 资源与其所有邻接链路带宽之和的乘积。直觉上，资源需求越大的虚拟节点应该优先映射，而资源能力越强的物理节点应该优先被考虑，这样能减少把高带宽需求的虚拟链路映射到远距离物理节点的概率。
具体实现时，先为每个虚拟节点计算需求指标，再为每个物理节点计算资源指标，然后按指标降序排列。映射虚拟节点时，从候选物理节点中优先选择资源指标最高且满足 CPU 约束的节点。此外，还可以引入邻接约束，即要求映射后的物理节点与已映射的邻居虚拟节点所在的物理节点相邻，这能显著降低链路映射阶段的失败率。下面是节点排序与映射的 R 代码实现。
library(igraph)
# 计算物理节点的资源能力指标：CPU * 关联链路带宽之和
node_resource <- function(g) {
cpu <- V(g)$cpu
bwsum <- sapply(V(g), function(v) {
inc <- incident_edges(g, v)[[1]]
if (length(inc) == 0) 0 else sum(E(g)$bandwidth[get.edge.ids(g,
as.vector(t(sapply(inc, function(e) ends(g, e)))))])
})
# 简化写法：直接遍历邻接边求带宽和
bwsum <- sapply(V(g), function(v) {
nb <- neighbors(g, v)
sum(sapply(nb, function(u) {
eid <- get.edge.ids(g, c(v, u))
if (eid > 0) E(g)$bandwidth[eid] else 0
}))
})
cpu * bwsum
}
# 芪婪节点映射：虚拟节点按需求降序，物理节点按资源降序
node_mapping <- function(gs, gv) {
vorder <- order(node_resource(gv), decreasing = TRUE)
mapping <- numeric(vcount(gv))
used <- c()
for (v in vorder) {
cand <- setdiff(which(V(gs)$cpu - V(gs)$used >= V(gv)$cpu[v]), used)
if (length(cand) == 0) return(NULL) # 无可行节点，嵌入失败
res <- node_resource(gs)[cand]
mapping[v] <- cand[which.max(res)]
used <- c(used, mapping[v])
}
mapping
}这段代码中，node_resource 函数对图中的每个节点计算 CPU 与邻接带宽总和的乘积，物理网络和虚拟网络都复用同一个函数，只是输入的图不同。node_mapping 函数返回虚拟节点到物理节点的映射向量，如果中途找不到满足 CPU 约束的可用物理节点，立即返回 NULL 表示该请求嵌入失败。这种尽早失败的设计可以避免不必要的后续计算。
三、链路映射：最短路径与带宽约束检查
节点映射完成后，需要对虚拟网络中的每条链路找到一条物理路径。最常用的策略是最短路径嵌入，即在当前剩余带宽满足需求的子图上运行 Dijkstra 或 BFS，把虚拟链路映射到跳数最少的物理路径上。为了尽量保护带宽资源，可以在边权重中引入带宽因子，例如把边的代价设为流量需求除以剩余带宽，引导路径避开剩余带宽紧张的链路。
实现时要注意一个细节：链路映射必须在“剩余带宽过滤后的子图”上进行。如果直接在原图上跑最短路径，可能选中一条带宽不足的路径导致嵌入失败。下面的代码先删除剩余带宽不足的边，再调用 shortest_paths 计算路径，成功后扣减路径上所有边的带宽，并记录映射结果以便请求离开时归还资源。
# 链路映射：在满足带宽约束的子图上找最短路径
link_mapping <- function(gs, gv, mapping) {
E(gs)$remain <- E(gs)$bandwidth - E(gs)$used
paths <- list()
for (e in seq_len(ecount(gv))) {
u <- ends(gv, e)[1]
v <- ends(gv, e)[2]
src <- mapping[u]
dst <- mapping[v]
need <- E(gv)$bandwidth[e]
# 删除剩余带宽不足的边构造过滤子图
ok <- which(E(gs)$remain >= need)
sub <- subgraph.edges(gs, ok, delete.vertices = FALSE)
if (length(get.shortest.paths(sub, src, dst)$vpath[[1]]) == 0) {
return(NULL) # 找不到可行路径
}
p <- get.shortest.paths(sub, src, dst)$vpath[[1]]
ep <- E(sub, path = p)
# 注意：子图边编号与原图对应，需用真实端点重新定位
for (i in seq_along(p[-1])) {
eid <- get.edge.ids(gs, c(p[i], p[i + 1]))
E(gs)$used[eid] <- E(gs)$used[eid] + need
}
paths[[length(paths) + 1]] <- p
}
list(graph = gs, paths = paths)
}
# 请求到达：完整嵌入主流程
embed_request <- function(gs, gv) {
mapping <- node_mapping(gs, gv)
if (is.null(mapping)) return(list(success = FALSE))
res <- link_mapping(gs, gv, mapping)
if (is.null(res)) return(list(success = FALSE))
list(success = TRUE, mapping = mapping, paths = res$paths)
}这里有一个容易踩的坑：在 igraph 中对子图操作的边编号与原图并不一致，直接用子图的边编号去更新原图的带宽会导致数据错乱。上面的代码通过路径节点的相邻关系调用 get.edge.ids 重新定位原图中的边，确保资源扣减作用在正确的边上。这是 igraph 使用中非常常见的错误，务必注意。
四、事件驱动仿真与评价指标计算
完整的 VNE 实验通常是事件驱动的：虚拟网络请求按泊松过程到达，每个请求有指数分布的生命周期，到期后释放占用的节点 CPU 和链路带宽。主循环维护一个当前时间，处理到达事件时尝试嵌入，处理离开事件时归还资源。用 R 实现时可以把所有事件预先排好序放进一个数据框，再按时间顺序逐个处理。
评价算法好坏的常用指标有三个：接受率，即成功嵌入的请求数与总请求数之比；平均收益，一般定义为每个成功请求的节点 CPU 需求总和与链路带宽需求总和之和乘以生命周期权重；平均开销，即物理路径上消耗的总带宽。收益开销比越接近 1 说明算法越能找到短路径、节省带宽资源。计算公式的 R 实现如下。
# 计算单个请求的收益与开销
revenue <- function(gv, life) {
(sum(V(gv)$cpu) + sum(E(gv)$bandwidth)) * life
}
cost <- function(gv, paths) {
hops <- sapply(paths, function(p) length(p) - 1)
sum(E(gv)$bandwidth * hops)
}
# 仿真主循环骨架
simulate <- function(gs, n_req = 2000, seed = 42) {
set.seed(seed)
total_rev <- total_cost <- 0
accepted <- 0
for (i in seq_len(n_req)) {
gv <- random_vnr(n_nodes = sample(2:10, 1))
result <- embed_request(gs, gv)
if (result$success) {
accepted <- accepted + 1
life <- rexp(1, rate = 0.01)
total_rev <- total_rev + revenue(gv, life)
total_cost <- total_cost + cost(gv, result$paths)
# 实际实现中还需注册离开事件并归还资源
}
}
cat("接受率:", accepted / n_req, "\n")
cat("长期收益开销比:", total_rev / total_cost, "\n")
}需要说明的是，上面的骨架代码省略了资源归还逻辑。严格的事件驱动仿真中，请求离开时必须把映射节点的 CPU 和路径上各边的带宽加回物理网络，否则资源会被永久占用，后续请求的接受率会迅速跌到零。实际写代码时建议用一个环境对象或列表来保存所有在网请求的映射信息，离开事件触发时逐一释放。
五、算法局限性与改进方向
两阶段贪婪算法的优点是实现简单、单次嵌入速度快，缺点是节点映射阶段完全不考虑链路拓扑信息，容易把相邻的虚拟节点映射到物理网络上相距很远的节点，导致链路映射开销大甚至失败。针对这个问题的经典改进是引入协同嵌入思想，例如在节点排序指标中加入映射邻居的距离因子，或者采用基于元路径的一步式映射。
另一个改进方向是引入智能优化算法，比如模拟退火、遗传算法或强化学习。在 R 中可以借助 GA 包实现遗传算法版本的 VNE，把节点映射方案编码为染色体，适应度函数取嵌入开销的相反数。不过智能优化算法的运行时间明显更长，在请求到达率高的在线场景中不一定划算，更适合离线的批量嵌入场景。
从工程角度看，如果需要做大规模仿真，R 的性能瓶颈会比较明显，建议把核心嵌入函数用 Rcpp 重写成 C++ 代码，通常能获得一个数量级以上的加速。此外，把物理网络和请求生成部分参数化，可以方便地对比不同拓扑、不同负载强度下的算法表现，形成完整的实验报告。掌握本文的两阶段贪婪框架之后，再阅读 VNE 相关的改进文献会有更直观的理解，因为绝大多数改进工作都是在节点排序指标或链路映射策略上做文章。