静态RWA算法：从ILP到启发式

静态RWA，说白了就是提前把所有光路的波长都规划好。网络建好之后，业务需求是已知的，我们一次性算出每条光路走哪条路、用哪个波长。我刚开始接触这个领域时，总觉得这不就是个路径计算嘛，后来才发现——坑深着呢。

这一章，我们重点聊两种主流方法：整数线性规划（ILP）和启发式算法。前者追求最优解，后者追求实用解。你想想看，一个网络几百条光路，ILP算到天荒地老，但启发式可能几秒钟就搞定了。

3.1 整数线性规划（ILP）模型

ILP是静态RWA的“黄金标准”。它把问题建模成一组数学方程，然后交给求解器去算。我当年在实验室里用CPLEX跑过一个40节点的网络，结果等了三天三夜……嗯，从那以后我对ILP又爱又恨。

3.1.1 核心变量与约束

ILP模型里，我们通常定义这么几个东西：

• 二元变量 x_p,w：如果光路p使用波长w，则为1，否则为0
• 波长连续性约束：一条光路从头到尾只能用同一个波长
• 波长冲突约束：同一条光纤链路上，不同光路不能共用同一个波长
• 光路唯一性约束：每个业务请求只能分配一条光路

minimize ∑w yw
subject to:
  ∑p xp,w ≤ 1,  ∀链路, ∀波长w
  ∑w xp,w = 1,  ∀光路p
  xp,w ∈ {0,1}

这里y_w是一个辅助变量，表示波长w是否被使用。约束条件保证了每条光路只用一个波长，且同一链路上没有波长冲突。

3.1.2 ILP的优缺点

3.2 启发式算法：First-Fit 与 Best-Fit

既然ILP算不动，我们就得找“够用”的方法。启发式算法就是干这个的——不保证最优，但保证快。我个人习惯把启发式算法分成两步：先找路径，再分配波长。这里我们重点聊波长分配这一步。

3.2.1 First-Fit（首次适应）

First-Fit的思路特别简单：把所有波长排个序，比如从λ1到λ80。给每条光路分配波长时，从最小的波长开始找，第一个能用的就给它。

伪代码长这样：

for each lightpath p:
    for w = 1 to W:
        if wavelength w is available on all links of p:
            assign w to p
            break
    if no wavelength found:
        block lightpath p

你可能会问：这么简单的东西能好用吗？其实，在大多数实际网络中，First-Fit的表现已经非常接近最优解了。我见过不少运营商，他们的静态规划工具用的就是First-Fit。

3.2.2 Best-Fit（最佳适应）

Best-Fit比First-Fit“聪明”一点。它不选第一个可用的，而是选“最合适”的那个。什么叫最合适？通常是选那些使用次数最少的波长，或者让剩余波长碎片最小的波长。

我举个例子：假设波长λ3已经在5条链路上被用了，λ7只在2条链路上被用了。Best-Fit会优先选λ7，因为它更“空闲”。

3.2.3 两种算法的对比

3.3 静态RWA算法选择指南

说了这么多，到底该用哪个？我个人的经验是：

• 网络规模小（节点数<15）：用ILP，追求最优解
• 网络规模中等（15-50节点）：用First-Fit，简单可靠
• 网络规模大（>50节点）：用First-Fit或Best-Fit，配合路径预计算
• 波长资源紧张：试试Best-Fit，可能多省几个波长

下面这张图，是我自己总结的静态RWA算法选型流程：

3.4 实战中的注意事项

最后，分享几个我在实际项目中总结的经验：

• 路径预计算很重要：别每次分配波长都重新算路径。先把所有候选路径算好存起来，能省大量时间。
• 波长排序有讲究：First-Fit的波长排序不是固定的。我习惯把低损耗、低色散的波长排在前面，优先使用。
• 留有余量：别把波长用满。我一般留10%-15%的波长做保护，防止未来业务调整。
• 定期重优化：静态规划不是一劳永逸的。网络拓扑变了、业务需求变了，就得重新跑一遍。