• 服务器集群负载均衡优化器

  1. 项目背景与问题描述

  随着大规模云计算与 GPU 集群的普及，服务器节点之间的负载不均衡成为影响系统吞吐率和资源利用率的重要问题。本项目在给定服务器节点容量、任务需求以及网络拓扑结构的前提下，设计并实现一个服务器集群负载均衡优化器，通过迁移部分任务以实现整体负载平衡，并在更高要求下考虑迁移成本与网络带宽约束。

  本项目分为三个层次：

  • 基础要求：在不考虑迁移成本和带宽限制的情况下，给出一个满足容量约束的可行负载平衡方案；
  • 高级要求：在满足容量约束的前提下，尽量减少任务迁移的总成本；
  • 附加要求：在高级要求的基础上，引入网络链路带宽限制，并模拟迁移过程所需的时间轮次。

  2. 总体设计思路

  从理论角度看，本项目涉及的问题与 装箱问题（Bin Packing）、广义指派问题（Generalized Assignment Problem） 以及 多商品流调度（Multi-Commodity Flow Scheduling） 密切相关，这些问题在一般情况下均为 NP-hard。因此，本项目并不追求全局最优解，而是采用**贪心（Greedy）+ 启发式（Heuristic）**的方法，在合理的时间复杂度内获得可行且质量较高的解。

  整体设计遵循以下原则：

  1. 分阶段求解：严格区分基础、高级和附加要求，每一阶段在前一阶段的基础上逐步引入新的约束；
  2. 清晰的数据结构设计：明确区分服务器、任务以及集群整体状态；
  3. 算法与数据解耦：通过 ServerCluster 类统一管理状态与算法，避免逻辑分散；
  4. 工程可读性优先：在保证正确性的前提下，注重代码结构清晰与注释说明。

  3. 数据结构设计

  3.1 服务器节点（Server）

  每个服务器节点包含以下信息：

  • 节点编号 index；
  • 最大可用 GPU 数量 capacity；
  • 当前已使用 GPU 数量 gpu_used；
  • 当前分配到该节点的任务列表 assigned_tasks。

  其中，gpu_used 始终维护为 assigned_tasks 中所有任务需求量之和，保证服务器状态的一致性。

  3.2 任务（Task）

  每个任务包含：

  • 任务编号 index；
  • 初始所在节点 start_node；
  • 当前所在节点 current_node；
  • 所需 GPU 数量 demand；
  • 累计迁移成本 migration_cost。

  通过区分 start_node 和 current_node，可以在输出阶段直接得到任务的迁移结果。

  3.3 服务器集群（ServerCluster）

  ServerCluster 统一维护系统的整体状态，包括：

  • 服务器列表 servers；
  • 网络拓扑的邻接矩阵 adjacency_matrix（用于最短路径计算）；
  • 网络带宽矩阵 bandwidth_matrix；
  • 任务列表 tasks；
  • Floyd 算法使用的路径恢复矩阵 parent。

  该设计使得不同阶段的算法能够在同一套数据结构上运行，逻辑清晰且易于扩展。

  4. 算法设计与实现

  4.1 基础要求：可行负载平衡方案

  设计思路

  在基础要求中，仅需满足容量约束，不考虑迁移成本和网络带宽限制。具体做法如下：

  1. 使用 Floyd 算法判断任意两台服务器之间是否连通；
  2. 对每一台超载服务器，计算其超出容量的负载量；
  3. 将该服务器上的任务按需求量从大到小排序；
  4. 依次尝试将任务迁移到任意一个仍有剩余容量且连通的服务器节点上，直到超载问题解决或无法继续迁移。

  该策略属于典型的贪心算法，能够快速得到一个满足约束的可行解。

  正确性说明

  • 每个任务最终被分配到某一服务器；
  • 任意服务器最终负载不超过其容量；
  • 不涉及迁移成本计算，严格符合基础要求。

  4.2 高级要求：迁移成本最小化

  设计思路

  在高级要求中，需要在满足容量约束的前提下尽量降低迁移成本。本阶段在基础要求的基础上引入以下改动：

  1. 使用 Floyd 算法计算任意两节点之间的最短路径代价；

  2. 对每个待迁移任务，在所有可行目标服务器中选择最短路径代价最小的节点作为迁移目标；

  3. 任务的迁移成本定义为：

     最短路径总代价 × 任务所需 GPU 数量

  该策略为局部最优贪心策略，在实践中能够显著降低总迁移成本。

  关于最优性的讨论

  由于该问题本质上是 NP-hard 的，项目中并不要求给出全局最优解。本实现采用的局部最优贪心策略在时间复杂度和解的质量之间取得了良好平衡，符合工程实践中的常见做法。

  4.3 附加要求：带宽约束与时间轮次模拟

  设计思路

  在附加要求中，引入网络链路带宽限制，并模拟迁移过程。实现步骤如下：

  1. 使用 Floyd 算法并维护 parent 矩阵，记录最短路径上的节点序列；
  2. 对所有需要迁移的任务，生成迁移计划（包括路径信息），并加入待执行队列；
  3. 以时间轮次（time step）为单位进行模拟：
     • 每一轮初始化当前可用带宽；
     • 检查迁移路径上所有链路是否有足够带宽；
     • 若满足条件，则执行迁移并扣除对应带宽；
  4. 重复上述过程，直到所有迁移完成或检测到死锁。

  实现特点

  • 迁移计划与迁移执行过程分离，逻辑清晰；
  • 显式检测带宽不足导致的死锁情况，避免死循环；
  • 输出每一轮迁移的详细信息，便于分析与调试。

  5. 时间复杂度分析

  • Floyd 算法：$O(N^3)$$，其中 ($N \le 50$)，在可接受范围内；
  • 基础 / 高级阶段的任务迁移：最坏情况下为$ O(N \cdot T \log T)$；
  • 附加要求的时间轮次模拟：与迁移任务数量和路径长度线性相关。

  在题目给定规模下，程序能够在限定时间内稳定运行。

  6. 测试与结果说明

  在给定的测试样例以及自行构造的随机测试中，程序均能：

  • 正确读入输入数据；
  • 输出符合格式要求的结果；
  • 保证服务器容量约束不被违反；
  • 在高级和附加要求下正确统计迁移成本与时间轮次。

  7. 总结与收获

  通过本项目的实现，加深了对以下内容的理解：

  • 图结构表示与最短路径算法（Floyd）；
  • 贪心算法在 NP-hard 问题中的实际应用；
  • 在工程约束（带宽、时间）下进行调度与模拟；
  • 复杂系统中数据结构与算法协同设计的重要性。

  本项目在满足课程要求的同时，也体现了工程实现中“可行性优先、性能与复杂度权衡”的设计思想。