本研究由上海交通大学的Shuyuan Zhang、Shu Shan和Shizhen Zhao（通讯作者）完成，论文发表于2023年6月29日至30日在中国香港举行的第七届亚太网络研讨会（APNet 2023），由ACM出版。
随着数据中心网络（DCN）流量呈现高度偏斜和时变特性，传统Clos拓扑在带宽提供成本上日益难以承受。混合光电数据中心网络通过引入光电路交换机（OCS）层，使逻辑拓扑能够根据实时流量模式进行重构，从而提高性能成本比。然而，重构时间直接决定可重构性的实际收益。重构时间由两部分组成：拓扑求解器运行时间和触发重构后的网络收敛时间。前者取决于算法复杂度，后者取决于重构过程中需要变更的链路数量。现有算法存在明显局限：暴力求解将问题建模为整数线性规划（ILP），虽可获最优解但NP难问题导致实际规模下无法求解；Zhao等人提出的贪心最小重连算法利用最小费用流（MCF）虽速度快但重连数远非最优；Google专利中的二分算法虽重连数较低但仍依赖ILP，运行极慢。因此，本研究的目标是设计一种既具有低算法复杂度又能有效减少重连链路数量的拓扑求解算法。
在问题建模层面，作者考虑一个由m个架顶交换机（ToR）和n个OCS组成的扁平拓扑。物理拓扑由参数a和b刻画，分别表示从OCS到交换机及从交换机到OCS的连接数；逻辑拓扑由矩阵c表示交换机间的等效连接数。所有OCS的匹配状态由三维张量x表示。可行匹配需满足三个约束：每个OCS的输出端口约束、输入端口约束以及逻辑拓扑约束。优化目标为最小化新旧匹配之间的断连总数，即目标函数为所有位置上旧连接数减去新连接数取正部后的和。作者指出该问题具有高度困难性：即使所有参数限定在0和1之间，判定可行解集合是否为空也是NP完全的；在某些条件下问题甚至不具备常数比近似算法。为降低难度，作者引入“比例物理拓扑”的定义——存在正向量r以及正向量α和β，使得所有OCS的连接数可按比例分解，其中r的所有分量为1时称为“均匀物理拓扑”。本文在均匀拓扑基础上放宽为比例拓扑，这是对已有文献约束的适度放松。
算法设计分为两个核心部分。第一部分针对n=2的特殊情况提出精确多项式时间算法。当只有两个OCS时，约束(3)使得x{ij1}+x{ij2}=c{ij}，因此可以用x{ij2}=c{ij}-x{ij1}消元，将原问题转化为仅含x{ij1}的单变量优化问题。约束(6a)和(6b)分别对应第一个OCS的输出和输入端口限制，约束(6c)保证非负性，而约束(6d)和(6e)可由前三个约束以及可行性条件推导得出，故可忽略。此时目标函数中每一项f{ij}(x)=(u{ij1}-x)^+ +(u{ij2}-c{ij}+x)^+在区间[0,c{ij}]上是凸分段线性函数。作者将该问题等价地转化为整数最小费用流问题：构造m个供给节点和m个需求节点，供给节点si具有b{i1}单位供给，需求节点dj具有a{j1}单位需求；对于每对(s_i,dj)，将凸分段线性函数f{ij}(·)按不可微点分段，在每一段上用该段斜率作为费用、段长为容量添加一条弧。这样，凸分段线性费用被转化为多条线性费用弧，原问题等价于标准的整数最小费用流问题，可由经典算法在多项式时间内求解。
第二部分针对一般情况n>2提出递归二分算法。算法流程如下：在solve函数中，若s=1则直接返回c；否则将维度为s的OCS集合任意非空地二分为K_1和K2两组。合并步骤中，将两组OCS分别视为一个虚拟OCS，旧匹配u在两个虚拟OCS上的值分别由组内求和得到，从而得到一个n=2的近似问题；利用第一部分的算法求解该近似问题的最优解x^*。分解步骤中，将x^*在两个虚拟OCS上的分配结果分别作为两个子问题的逻辑拓扑c^(1)和c^(2)，并分别递归调用solve函数求解各子组内的匹配。最后将子问题的解合并为原问题的可行解。算法的正确性关键在于证明第8行的近似问题总是可行的。定理4.1给出了证明：构造一个实数解x{ij1}，其值为第一组OCS的rk权重占比乘以两组OCS在(i,j)位置上的旧连接总数。该实数解满足约束(6c)是因为x{ij1}不超过两组旧连接总数（即c_{ij}的对应分量）；满足约束(6a)和(6b)是因为比例物理拓扑的r_k因子使得按比例分配恰好匹配各虚拟OCS的端口容量。由于整数最小费用流问题具有“若存在实数可行解则必存在整数可行解”的性质，因此近似问题必定可行。在时间复杂度上，若每次采用均等二分，根调用的时间满足递推关系T(m,n)=2T(m,n/2)+O(m^4 log m)+O(m^2 n)。使用费用缩放算法求解MCF时，主定理给出总复杂度为O(m^4 n log m+m^2 n log n)，其中第一项为主导项。
评估部分使用Facebook数据中心的开放流量迹数据生成期望逻辑拓扑。仿真场景假设每个ToR交换机有32条上行链路均匀连接到各OCS，测试了4、8、16个OCS三种规模，并分别使用包含155个和324个ToR交换机的Facebook集群A和集群B的迹数据。流量矩阵在固定时间窗δt=10分钟内聚合，通过求解一个最小化流量加权逻辑连接的优化问题得到期望逻辑拓扑。程序使用Java实现，ILP求解器采用Gurobi，MCF求解器使用JGraphT库。评估对比了本文算法（ours）、贪心MCF算法（gm）和二分算法（bi），暴力算法因在4个OCS的最简单情况下也常无法在1分钟内找到可行解而未纳入结果。运行时间方面，本文算法在所有测试场景下均显著优于其他算法，部分情况下比第二快的贪心MCF算法快达10倍；贪心MCF次之，二分算法最慢。断连数方面，本文算法的近似比与二分算法相当，在多数情况下优于贪心MCF算法。综合来看，本文算法在保证低断连数的同时实现了显著的速度提升，整体性能优于现有算法。
研究结论指出，本文首次将拓扑求解问题形式化为具有分段凸费用的最小费用流问题，通过结合二分与最小费用流思想，提出了一种多项式时间算法，在求解器运行时间和网络收敛时间之间取得了更好的平衡。基于真实流量迹的评估验证了算法在速度上的压倒性优势以及断连数上的可比近似比。该算法有望提升混合光电数据中心的性能并促进OCS的部署。
本文的亮点在于：第一，首次将拓扑配线问题建模为凸分段线性费用的MCF问题，并通过弧分裂技术转化为标准MCF，从而利用成熟的多项式时间算法求解；第二，提出递归二分框架，通过合并OCS降低维度，再将解分解回原空间，兼顾了求解效率和解质量；第三，在比例物理拓扑条件下形式化证明了算法的可行性，这是对均匀拓扑假设的有意义推广。相关工作部分还讨论了Graver基与n-fold ILP理论、凸费用MCF的专用算法等，指出这些理论方法虽在多项式时间可解但实际规模下仍不实用。未来工作包括建立算法最坏情况界的理论性质以及在实际硬件上验证算法有效性。
代码和测试用例已在GitHub公开仓库提供。该研究得到了国家自然科学基金（项目号62272292和61902246）的资助。