论文阅读-面向公平性的分布式系统负载均衡机制

摘要

当一组自利的用户在分布式系统中共享多个资源时，我们面临资源分配问题，即所谓的负载均衡问题。特别地，负载均衡被定义为将负载分配到分布式系统的服务器上，以便最小化作业响应时间并提高服务器的利用率。在本文中，研究了一个由有限数量的服务器和有限数量的用户组成的分布式系统中的负载均衡问题。这里考虑的负载均衡问题是一个双目标问题，具有两个高度可能冲突的目标：（i）最小化作业响应时间 (ii) 提供服务器的公平利用。为了同时满足这两个目标，两个目标以综合方式考虑。接下来，将负载均衡问题构建为一个非合作博弈；为了解决博弈（即，找到纳什均衡），提出了一个分布式负载均衡算法（DLBA）。进行了实验研究以确定所提出的DLBA的有效性。此外，我们将DBLA与三种现有的负载均衡方法进行比较，以评估其相对效果。实验结果验证了DLBA相对于现有方法的有效性。

索引词—负载均衡，分布式系统，公平利用，非合作博弈，纳什均衡

1 引言

随着云计算和互联网在线服务的增长，分布式系统在过去几十年中受到了极大的关注。一般而言，分布式系统被视为由一群独立用户共享的一组自治计算资源。分布式系统的性能取决于用户作业在计算资源之间的分配方式。有效管理资源利用的问题称为负载均衡。因此，为了有效利用这些系统，需要一个高效的负载均衡方案。

我们考虑一个分布式计算系统中的负载均衡问题，其中一组独立的用户共享一组计算资源，以下称为服务器。我们假设服务器在处理速度上是异构的，并且由个人拥有，以下称为服务提供商。每个用户都是自治的和自利的。自治意味着用户可以在没有控制权威的情况下自由做出决策，自利意味着用户关心的是最小化其作业的执行/响应时间。用户总会偏好速度更快的服务器。另一方面，从服务提供商的角度来看，应该在确保跨服务器平衡分配负载的同时最大化资源的利用。换句话说，服务提供商希望最小化服务器之间的负载不平衡，以便没有服务器被过载或利用不足。

动机。几个现实世界的系统适用于上述负载均衡场景。特别是，我们的研究受到云计算系统的启发，在这些系统中，多个计算设备在多个用户之间共享。云计算中的负载均衡使用基础设施即服务（IaaS）。IaaS是一种服务模型，为客户提供一组机器（物理或虚拟）以执行他们的任务。在IaaS系统中，每台机器充当服务器，服务器的计算速度可能是同构的也可能是异构的。这样的云由个人拥有。这样的云的一个示例是Amazon EC2和HP Cloud。在这样的分布式云计算系统中，服务提供商有兴趣设计一个适当的负载均衡方案，考虑两个目标：（a）最小化用户的响应时间和（b）在避免某些资源过度利用而其他资源利用不足的情况下提高服务器的利用率，这些目标是冲突的。当服务提供商考虑第一个目标时，她会尽可能多地利用更快的服务器。结果，更快的服务器（较慢的服务器）变得过载（欠载）。另一方面，当服务提供商考虑第二个目标时，她会不考虑它们的处理速率公平地对待所有服务器，即每个服务器上的负载都被公平分配。因此，每个用户的响应时间增加。

讨论了上述示例场景后，很明显，分布式系统中的负载分配引起了一个必须小心处理的微妙问题。然而，存在大量的工作，cf. e.g., [4], [5], [6], [7], [8]（更多细节可以在第2节中找到），试图解决各种类型的分布式计算环境中的负载均衡问题。在这些工作中，问题被建模为一个非合作博弈，其中玩家的收益是作业执行时间。因此，上述所有研究都考虑了用户端的性能。

贡献。我们首先为用户定义了一个新的度量标准，称为公平性变化。这个度量标准量化了用户造成的负载不平衡。接下来，我们使用加权和方法将公平性变化度量与预期响应时间结合起来。我们将这个组合度量作为一个新的目标函数。我们将问题构建为一个非合作博弈，称为非合作负载均衡博弈。这个博弈的解是玩家达到的一个平衡点，称为纳什均衡（NE）。在NE处，没有玩家可以通过单边偏差进一步最小化其目标值；因此，找到博弈的纳什均衡等同于找到底层负载均衡问题的解决方案。为了计算博弈的NE，我们提出了一个分布式负载均衡算法（DLBA）。为了测试DLBA的性能，我们在不同的系统配置下进行了实证研究。此外，我们将其与其他三种负载均衡方案，即GOS、NCS和QNCS进行比较。实证结果表明，DLBA提供了高效的服务器利用率，并与这三种方案相比，提供了更好的系统范围内的性能。

总之，本文的主要贡献是：（i）我们将负载均衡问题建模为一个双目标优化问题，（ii）使用博弈论框架，我们将优化问题构建为一个非合作博弈，称为非合作负载均衡博弈，（iii）为了计算博弈的NE，我们提出了一个分布式负载均衡算法（DLBA），（iv）我们提出了实验研究以验证DLBA的有效性。

本文的组织结构如下。第2节介绍相关工作。第3节给出数学建模和问题陈述。第4节给出问题的博弈论构建。第5节描述了所提出的算法及其伪代码。第6节提供了实验结果及其讨论。最后，第7节总结了本文。

2 相关工作

分布式计算中的负载均衡问题已经通过使用队列模型和博弈论进行了研究，使用各种性能指标，如预期响应时间、负载不平衡百分比、用户承担的成本[1]，[2]。在这一研究线中，最初一些研究者[9]，[10]，[11]提出了资源分配问题的集中式解决方案。实际上，由于可扩展性和复杂性原因，分布式环境中负载均衡问题的集中式解决方案是不可行的。

分布式计算系统中资源分配问题的博弈论解决方案在[4]，[5]，[6]，[7]，[8]，[12]，[13]，[14]，[15]，[16]，[17]，[18]，[19]，[20]中提出。Grosu和Chronopoulos[4]将分配问题建模为一个非合作博弈。在这个博弈中，每个玩家的收益是执行其作业的预期响应时间。为了找到博弈的NE，作者提出了一个分布式算法。在[5]中，Kameda和Altman考虑了通信网络中的最优流量控制问题，并证明了在存在自利用户的情况下，分配流量的问题类似于公地悲剧问题，并且获得的NE是低效的。Subrata等[6]提出了一个基于非合作博弈的框架来解决计算网格中的分配问题。Song等[7]考虑了未来互联网的暂定架构，并使用博弈论方法解决了互联网中的负载均衡问题。在[8]中，考虑了一个与[4]中类似的负载均衡问题，但是在分布式数据中心的背景下。然而，在所有这些工作中，只考虑了玩家的作业执行时间，完全忽略了服务器利用率的影响。

Li等[26]考虑了在并行机器上分配线性恶化作业的分配问题，并提出了基于博弈论的近似算法来解决分配问题。Xiao等[13]考虑了互连系统，并使用Q-learning提出了一个公平感知的资源分配方案。Ghosh等[14]，Yu等在[15]中，以及Penmatsa和Chronopoulos[27]使用了一个双方博弈模型来捕捉用户和服务提供商之间的互动。在这个模型中，服务提供商与所有用户互动，以决定成本和负载分配。在这些工作中，只考虑了用户的成本最小化目标。

然而，在[25]，[28]中考虑了具有两个目标的资源分配问题。Zheng和Veeravalli在[28]中提出了一种聚合方法，将分配问题与定价模型结合起来。他们提出了一种提供系统范围内最优的算法。因此，他们的方法在某种程度上是集中的。Jalaparti等在[25]中提出了一种基于市场的方法来优化提供商之间以及用户和提供商之间的效用。他们研究了玩家之间的竞争如何影响他们的成本。总之，他们考虑了成本最小化作为一个目标，并提供了基于斯塔克尔伯格博弈的集中式解决方案。

Zhang等[23]提出了一种进化的多目标优化算法来解决一个包括最小化响应时间和有效利用资源的双目标工作流调度问题。在[https://img-home.csdnimg.cn/images/202307https%3A%2F%2Fimg-home.csdnimg.cn%2Fimages%2F20230724024159.png%3Forigin_url%3D24%26pos_id%3DRh0xSnZq0https%3A%2F%2Fimg-home.csdnimg.cn%2Fimages%2F20230724024159.png%3Forigin_url%3D24%26pos_id%3DRh0xSnZq159.png?origin_url=https%3A%2F%2Fimg-home.csdnimg.cn%2Fimages%2F20230724024159.png%3Forigin_url%3D24%26pos_id%3DRh0xSnZq&pos_id=Rh0xSnZq]中提出了一种基于极值优化的多目标优化方法来解决一个三目标负载均衡问题。这项工作的目标是：最小化负载不平衡、最小化进程间通信和任务迁移指标。Talukder等[29]提出了一个多目标差分进化算法来同时优化两个冲突的目标，即成本和时间。

最近，一些研究人员提供了多目标负载均衡问题的非合作解决方案。Liu等人[30]考虑了负载平衡问题，通过利用空闲的计算资源来最大化提供商的利润，并优化临时云模型的性能。在[30]中，多个提供商之间的竞争被视为一个非合作博弈；为了计算博弈的解决方案，提出了一个迭代近似算法。在[31]中提出了一种服务机制，用于在多个云提供商和多个云客户之间优化利润。在这项工作中，云用户之间的互动被建模为一个进化博弈，而提供商之间的互动被建模为一个非合作博弈。为了实现云提供商和用户之间的满意度，即双赢情况，模拟了提供商和用户的讨价还价过程。为了计算平衡，提出了一个分布式迭代算法。Zhang等[32]解决了一个包括两个冲突目标的双目标问题：在遵守先行和调度长度约束的前提下，最小化能源消耗和最大化系统可靠性。他们提出了一种称为双目标遗传算法（BOGA）的多目标优化算法，以同时优化这两个目标。尽管这些工作考虑了多目标负载均衡问题，但这些工作中没有考虑两个冲突目标，即最小化响应时间和利用不平衡。表1显示了我们提出的方法DLBA和其他最先进的负载均衡算法的比较。

3 系统模型与问题形式化

3.1 系统模型

我们考虑一个由 m 个用户和 n 个异构服务器组成的分布式系统，这些服务器独立并行工作。服务器是异构的，意味着它们具有不同的处理能力。我们用 N={1, 2, ..., n} 表示服务器集合，用 M={1, 2, ..., m} 表示用户集合，使得 m>>n。我们假设服务器 j ∈ N 的处理速率为 mj，用户 i ∈ M 的作业生成速率为 λi。与文献[4]类似，我们将每个服务器建模为一个 M/M/1-FCFS 队列，具体如下。

在每个服务器上，作业的到达遵循泊松过程。作业的执行时间呈指数分布，并且根据先到先服务（FCFS）原则执行作业。由于所有服务器都建模为 M/M/1 队列，为了稳定性，服务器的容量约束为：。

本文考虑的分布式系统模型的架构如图 1 所示。每个用户 i 假定以平均速率 λi 生成作业，根据泊松过程并且与其他用户独立。此外，类似于文献[33]，我们假设每个用户都关联有一个单独的调度器，负责将用户的作业分配给服务器。因此，用户集合与调度器集合相同。为了保持符号一致，我们假设调度器集合表示为 M={1, 2, ..., m}。本文使用的所有符号都在表 2 中给出。

3.2 响应时间最小化模型

我们给定了一组独立工作的调度器和服务器集合。我们假设调度器行为自私，不在利用服务器时进行合作。每个调度器 i 有一个大小为 λi 的作业，并希望通过分割其作业到服务器来分配其作业。调度器可以决定其作业在服务器之间的分割方式，即调度器 i 决定将 λi 的哪一部分分配给每个服务器。我们用 xij 表示分配给服务器 j 的调度器 i 工作负载的比例。因此，调度器 i 可以选择 xij 的任何值，只要 0 ≤ xij ≤ 1 并且。在决定了 xij 的值后，调度器 i 以 xijλi 的速率将工作负载分配给服务器 j。

调度器 i 的工作负载分割配置 xi 是向量，我们将其称为调度器 i 的策略。所有调度器的策略共同被称为系统的策略配置。联合策略配置 X 是调度器策略的向量 X = (x1, ..., xm)。此外，在本文的其余部分，我们表示：X = ，其中 x-i 代表除调度器 i 之外的所有其他调度器的策略。

定义 1（可行策略配置）。如果且仅如果策略配置 X=(xi, x-i) 满足以下约束，则称其为可行策略配置：(C1): xij ≥ 0 对 ∀i ∈ M, ∀j ∈ N；(C2): ；(C3): 对 ∀j ∈ N。这里，C1 代表正性约束，确保调度器始终向服务器分配非负负载。C2 对应于保守约束，确保调度器至少向一个服务器分配其作业。C3 代表稳定性约束，即服务器上的总作业到达率必须小于其处理率。

给定一个可行的策略配置 X=(xi, x-i)，服务器 j 的预期响应时间[4]是

而调度器 i 的预期响应时间是

备注 1。在此模型中，目标是找到一个可行的策略配置 X=(xi, x-i)，使得每个调度器 i ∈ M 的预期响应时间 Ri 最小化。

3.3 服务器利用率模型

给定联合负载平衡策略配置 X=(xi, x-i)，让 是分配给服务器 j 的聚合负载。服务器的利用率定义如下。

定义 2（服务器利用率）。给定联合策略配置 X=(xi, x-i)，每个服务器 j ∈ N 的利用率定义为服务器 j 上的聚合负载与其处理率的比率，即，

j可以取0到1之间的一系列值。值为0表示服务器j根本没有被利用。另一方面，值为1表示服务器j的利用率达到100%，即，服务器j过载。

定义3（公平利用策略）。一个联合负载均衡策略配置X=(xi, x-i)被认为是公平利用策略，当且仅当所有服务器的利用率相同，即，

当调度者的联合策略配置是公平利用策略时，服务器的利用被视为公平利用。为了帮助明确公平利用的概念，我们提供了以下示例。

示例1。考虑有2个调度者和3个服务器。，设定两个联合策略配置X'和X''如下：

对于两种联合策略配置，服务器的利用率为：

现在，很明显，相对于 X'，服务器的利用率是不平衡的，而相对于 X''，所有服务器的利用率都是 60%。因此，策略配置 X'' 被认为是一个公平的联合策略配置。

定义 4（公平性变异）。我们定义反映服务器之间负载不平衡的公平性变异如下。

其中表示所有服务器的平均利用率。例如，可以注意到，在示例 1 中，相对于策略 X' 和 X'' 的公平性变异分别为 (X') = 0.09 (9%) 和 (X'') = 0。理想情况下，如果系统是 100% 公平的并且每个服务器的利用率相等，则公平性变异的值将是 0。（相当于算了个方差）

在我们的案例中，负载分配决策由每个调度器自主做出。因此，我们需要从每个调度器的角度量化服务器之间的负载不平衡，如下所述。

给定联合负载平衡策略配置 X=(xi, x-i)，让 是除 i 之外的所有调度器分配给服务器 j 的聚合负载。服务器 j 对调度器 i 的可用处理率  是确定的：

调度器 i 对服务器 j 的利用率，记为 ，定义为调度器 i 分配给服务器 j 的负载 (即 xijλi) 与调度器 i 观察到的服务器 j 的可用处理率之比，即，

通过调度器 i 通过所有服务器分割其负载造成的平均利用率估计为：

调度器 i 在分割其负载通过所有服务器时造成的公平性变异是

备注 2。公平性变异 衡量了由调度器 i 引起的服务器之间的负载不平衡。随着这一标准的值降低，服务器利用率方面的公平性增加。因此，在此模型中，目标是找到一个可行的策略配置 X=(xi, x-i)，使得每个调度器 i ∈ M 的 值最小化。

3.4 问题形式化

在本文中，我们旨在解决一个负载平衡问题，该问题有两个目标：(i) 最小化调度器的预期响应时间和 (ii) 最小化每个调度器的公平性变异值，这两个目标是冲突的。冲突的原因如下。当调度器专注于第一个目标时，他们会尽可能多地利用更快的服务器。由于向更快服务器的诱惑，忽视了负载不平衡的影响，导致更快的服务器（较慢的服务器）变得过载（未充分利用）。结果，每个调度器的公平性变异值增加。另一方面，当调度器考虑第二个目标时，它会平等地目标缓慢和快速服务器。这种资源的平等利用可能会增加每个调度器的作业执行时间。因此，可以推断，改善一个目标可能会导致另一个目标的退化。

为了易于理解目标之间的冲突，我们借助示例 2 提供一个正式的解释。如果一个多目标优化问题涉及冲突的目标，那么获取一个可以同时优化所有目标的单一解决方案是不可能的。在多目标优化的背景下，最优性的概念与提供不同目标间权衡的解决方案集相关联。可以使用帕累托最优性的概念来定义目标间最佳可能的权衡。根据本文的术语，我们使用术语策略配置，类似于解决方案。

定义 5（帕累托最优性[34]）。一个策略 ，当且仅当不存在另一个能够优于X*，即，不存在这样一个X使得优于 X*，即不存在 X 使得 这里，z表示优化问题中的目标数量，Ω是可行策略空间。 换句话说，如果没有策略配置可以最小化一个目标，而不同时增加至少一个其他目标，那么X*，被称为帕累托最优。

示例 2（说明目标之间的冲突）。考虑示例 1 中的分布式系统，让我们考虑给出三个联合策略配置如下。

两个标准的值：调度器的响应时间（见方程（2）），以及每个调度器造成的公平性变异（见方程（8））如下。

为了清楚地说明两个目标（标准）之间的权衡，图 2 绘制了两个权衡曲线。图 2a 和 2b 显示了相对于三个不同策略配置的调度器 1 和 2 的权衡曲线。从这些图中可以看出：(a) 策略配置 1 在公平性变异方面对两个调度器来说都是最好的，并且在响应时间方面是最差的，(b) 策略配置 3 在响应时间方面对两个调度器来说都是最好的，并且在公平性变异方面是最差的，(c) 策略配置 2 在响应时间方面比策略配置 1（策略配置 3）好（差），在公平性变异方面比策略配置 3（策略配置 1）差（好）。总之，对于两个调度器，没有一个策略配置优于另一个。根据定义 5，这些策略配置是帕累托最优的。

3.5 问题陈述

我们的目标是找到一个可行的策略配置，以实现这两个目标之间的平衡权衡，并同时优化这两个目标的值。因此，为了找到一个可行的解决方案，我们需要为这两个目标分配相对偏好。鉴于这一目标，我们以综合方式考虑这两者。为了整合这两个目标，我们应用加权和方法。在这种方法中，我们将每个目标乘以一个权重因子，并将两个目标相加以获得一个综合目标函数。权重因子表示每个目标的相对重要性。

负载平衡具有以下两个目标函数。

在结合了这两个目标之后，我们得到了

在权重因子 0 ≤ w1, w2 ≤ 1 的条件下，满足 w1 + w2 = 1。因此，在给定的建模和作业分配给服务器的情况下，我们现在将正式陈述我们试图解决的问题。给定一个由 m 个调度器和 n 个服务器组成的异构分布式系统，以及调度器的目标函数（fi），找到一个可行的联合策略配置 X = (xi, x-i)，使得每个调度器的目标函数值最小化。

备注 3. 我们现在将在等式（11）中得到的上述函数称为调度器 i 的目标函数。

备注 4. 在目标函数 fi 中（见等式（11）），w1 的较高值意味着更多地注意到用户端（即，调度器的预期响应时间），而 w2 的较高值表明给予服务器的公平利用更多的关注。因此，选择 w1 和 w2 的适当值取决于在设计分布式系统时确定的目标。

4 游戏制定

本节将介绍一个博弈论的制定，并以其完整形式提出我们的优化问题。调度器 i 的性能度量由其目标函数 fi 给出（见等式（11））；调度器 i 寻求找到一个负载分配策略，以最小化其目标。由于目标函数取决于所有调度器的策略，结果是调度器受到所有参与调度器的策略的影响，而不是他们自己的策略。类似于 [4]，我们将负载平衡问题建模为一个非合作游戏。

定义 6（非合作负载平衡游戏）。一个非合作负载平衡游戏可以正式定义为一个三元组 ，其中 M={1; ... ; m} 是玩家集合，xi 是玩家 i ∈ M 的策略配置，每个玩家 i 的惩罚函数是 fi。

在本文中，调度器被视为玩家。每个玩家 i（i ∈ M）的惩罚函数是 fi（给定在等式（11）中）。每个玩家 i 的策略配置是 xi = (x1i; ... ; x1n)。

备注 5。一般来说，在博弈论设置中，玩家的目标函数被称为效用函数，玩家的目标是最大化效用函数。在我们的制定中，负载平衡问题被制定为最小化问题。因此，在本文中，我们不是将其称为效用函数，而是称之为惩罚函数。

在这个游戏中，玩家 i 的目标，给定其他玩家的策略，表示为 x-i，是选择一个策略 xi，使得其惩罚 fi(xi, x-i) 最小化。这个游戏的解决概念是纳什均衡，下面定义。

定义 7（纳什均衡）。一个联合策略配置 X* = (, ) 被称为负载平衡游戏 G 的纳什均衡，如果对于所有：在纳什均衡下，没有玩家可以通过选择不同的策略在保持其他人策略不变的情况下进一步最小化其惩罚。

为了展示将优化问题（等式 11）建模为非合作游戏的动机，我们考虑以下示例。

示例 3. 让我们考虑一个 G 的实例，其中 m = 2。考虑 2 个玩家：A 和 B，以及 3 个服务器，(λ1; λ2) = (2, 4) 和 (1;2;3) = (2, 3, 5)。假设每个玩家有两种策略： = (0.10; 0.50; 0.40)， = (0.10; 0.30; 0.60)， = (0.20; 0.40; 0.40)，和  = (0.15; 0.30; 0.45)。两个玩家的目标都是最小化他们的惩罚函数。

两个玩家的游戏由一个矩阵表示（见图 3），其中条目的第一个组成部分是对玩家 1 的惩罚值，第二个组成部分是对玩家 2 的惩罚。对于这个示例，我们考虑 w1 = 0.7 和 w2 = 0.3。这个游戏有四个策略配置，即 (x1A; x1B)，(x1A; x2B)，(x2A; x1B)，和 (x2A; x2B)。从图 3 可以清楚地看到，无论玩家 2 采取什么策略，玩家 1 的最佳选择都是 x2A。同样，玩家 2 的最佳选择是 x2B，不管玩家 1 采取什么策略。通过类比，定义 7 似乎表明，一个玩家应该坚持他的最佳策略，因为他通过偏离它不会更好。因此，策略配置 (x2A; x2B) 是纳什均衡。然而，纳什均衡 (x2A; x2B) 也是一个帕累托最优策略。

备注 6。我们的最终目标是最小化用户的响应时间，同时公平地利用服务器。在这方面，关于游戏（在示例 3 中讨论）的一些评论如下。两个标准的值：调度器的响应时间（给定在等式 2 中），以及每个服务器的利用率（%）（给定在等式 3 中）如下。

从上述数值可以看出，在 NE 下，(x2A; x2B)：(i) 对两个玩家的响应时间最小，(ii) 与其他服务器相比，服务器利用率是公平的，因为与其他服务器不同，没有服务器的利用率超过 60%（这是系统的总利用率）。因此，可以公平地推断，游戏的 NE 是问题的最优解。

5 负载平衡游戏的纳什均衡计算

从游戏 G 的定义中可以看出，每个玩家的目标是找到一个策略，使其成本函数的值最小化。此外，对每个调度器来说，最优的策略配置是游戏的 NE。因此，计算调度器 i 的最优策略简化为确定具有一个调度器和 n 个服务器的系统的最优策略问题（因为对于调度器 i，其他策略是固定的）。所以，对于 M 中的每个玩家 i，我们解决以下非线性优化问题（标记为 NLPi）。

备注 7。为了找到 NLPi 的解决方案，其他的策略保持不变。因此，NLPi 中的决策变量是调度器 i 的策略，即 xi。接下来，当每个调度器的策略是对其他调度器策略的最佳响应时，找到均衡策略配置 X*（纳什均衡）。玩家 i 的最佳响应被定义为 xi 的策略，它为 playeri 提供了最小的惩罚，考虑到其他玩家的策略是给定的。所以，NLPi 的解决方案是 playeri 的最佳响应。

5.1 最佳响应计算算法

算法的伪代码（算法 1）如下所示，其逐步描述如下。我们首先讨论算法的一些预处理步骤。每个玩家 i 的初始策略可以如下。

生成每个 playeri 的策略后，我们使用等式（11）评估惩罚函数值，并使用等式（5）评估所有服务器的可用处理速率，即 。我们提供一个数值示例以使这些预处理步骤清晰。

示例 4。考虑示例 1 中给出的系统和 (w1; w2) = (0.7, 0.3)。我们首先根据等式（5）确定 player1 和 2 的策略。这些策略是，

并且两个玩家的服务器的可用处理速率是 (;;) = (4, 8, 12) 和 (;;) = (3; 6; 9)。惩罚值是 f1 = 0.015; f2 = 0.029。

算法 1 的描述：算法的一般阶段如下。

(1) 策略生成阶段。在步骤（3-6）中，生成了一些策略。步骤 3 中获得的策略 是通过生成 n 个随机数并将它们规范化，使得它们的总和为 1。现在检查策略的可行性。我们可以看到，等式约束（等式（14））将得到满足。另一方面，可能违反不等式约束（等式（15））。因此，我们需要一个修复机制使其可行。

策略修复（满足不等式约束等式（15））：如果任何负载分数 vk_ij 违反约束等式（15），则将该 vk_ij 修正为 0.99 倍的 /λi，其余值（即，vk_ij - 0.99 * /λi）按比例分配给其他负载分数。按比例我们指的是按服务器的处理速率比例。

现在，在步骤（5）中，使用等式（11）确定玩家 i 的惩罚值 fi(vk_i, x-i)。以下示例说明了策略生成阶段。

示例 5。在示例 4 中，对于 NP = 3，我们想找出 player 1 的一组策略。通过执行算法 1 的第 2 行，我们得到一个策略 (v1_11; v1_12; v1_13) = (0.70, 0.03, 0.27)，满足等式约束。策略的负载分数违反不等式约束，因为 v1_11 > λ1（即，8.4）大于 （即，8）。因此，通过应用策略修复方案，策略变得可行。可行的策略是 (v1_11; v1_12; v1_13) = (0.33, 0.18, 0.49)，惩罚值为 0.19。

(2) 策略更新阶段：在步骤（7-14）中，策略生成阶段生成的策略集合使用重组程序进行更新。

重组程序。对于一个策略 vk_i，生成一个新策略 uk_i 如下。我们随机选择两个策略，比如 vl_i 和 vp_i，从策略生成阶段获得的策略集合中。然后我们比较 vl_i 和 vp_i 的惩罚值；惩罚值较小的称为赢家。让 vl_i 成为赢家。然后生成策略 uk_i 为：

其中 r1 是一个介于 0 和 1 之间的随机数，id 是从集合 N 中随机选择的一个数字，即 id ∈ N。

uk_i 检查约束违规。它可能违反等式和不等式约束。为了使其可行，两种约束违规都得到修复。不等式通过使用上一阶段提到的方案修复。为了修复等式约束，我们建议一个修复方案。

策略修复（满足等式约束等式（14））。一个策略 uk_i 违反等式约束有两种情况：当 和当。为了修复等式约束对于 uk_i，首先评估违规量 k，即 。然后，每个负载分数被修改为：

满足等式约束后，我们转向检查不等式约束。修复违规约束（如果有违反的话），uk_i 的惩罚值被评估。如果 uk_i 的惩罚值小于 vk_i，uk_i 替换 vk_i。这完整的阶段在示例 6 中说明。

示例 6。在示例 5 中，考虑 player 1 的 3 个策略集合 (v1_11; v1_12; v1_13) = (0.33, 0.18, 0.49)，(v2_11; v2_12; v2_13) = (0.05, 0.10, 0.85)，和 (v3_11; v3_12; v3_13) = (0.07, 0.52, 0.41)。3 个策略的惩罚值分别为 fi_1 = 0.569, fi_2 = 0.127 和 f1_3 = 0.072。让我们为策略 1 生成一个新策略。由于策略 3 的惩罚小于策略 2 的惩罚，因此选择策略 3 作为赢家。让 id = 2，那么策略 u1_1 为：(u1_11; u1_12; u1_13) = (0.33, 0.48, 0.42)。接下来我们可以看到 u1_1 违反等式约束，因为 d1 = 0.23。修复等式约束后，我们得到：(u1_11; u1_12; u1_13) = (0.27, 0.39, 0.34)。现在，我们发现这个策略满足不等式约束。u1_1 的惩罚值为 0.063，小于 0.569。因此，我们得到一个新策略，(v1_11; v1_12; v1_13) = (0.27, 0.39, 0.34)。

(3) 最优策略选择阶段。在步骤（15-19）中选择一个惩罚值最小的策略。

引理 1。通过算法 1 实现的玩家 i 的响应是由最佳响应 给出的最优负载平衡策略。

证明。算法1从玩家i的初始策略xi开始，即按照公式(16)中给出的比例分配公式进行评估。

在步骤3-6中，生成一个新策略列表（例如，S）。在步骤7-14中，从S中获得一组新的策略S0，使得|S|=|S0|，并且S0中的每个元素都比S中对应的元素具有更好的惩罚。在第15步之后，选择S0中最佳的策略（例如y）。在第16步，将y的惩罚与xi的惩罚进行比较，并选择最小值。

此外，从第15步到第18步，很明显玩家i要么获得比之前更好的策略（即初始策略），要么保持相同的惩罚状态，但绝不会恶化。因此，在算法1中，对于每个玩家i，选择具有最小惩罚函数值的策略作为玩家i的最佳响应。这一点结束了证明。

备注8（算法1的计算复杂性）。算法1中涉及的基本操作的计算复杂性如下：初始化可行策略集（从第3步到第6步）需要O(NPn)，其中n是服务器的数量。更新策略集（从第7步到第13步）的复杂性为O(NPn)。从更新的策略集中选择最佳策略（从第15步到第18步）需要O(NP)。因此，算法1的总体计算复杂性为O(NP*n) ≈ O(n^2)，其中NP=cn，c≥3。

5.2 用于计算纳什均衡的分布式负载平衡算法（DLBA）

由于所有玩家都被认为是自私的，并且试图最小化自身的不适感而忽视其他玩家，因此自然而然地考虑了一个分布式方法，在这种方法中，每个玩家可以更新其策略以最小化其惩罚函数。因此，我们设计了一个分布式负载平衡算法（DLBA），其中每个玩家通过计算针对其他玩家给定策略的最佳响应来完善其策略。玩家按顺序更新其策略，如图4所示。DLBA的伪代码（算法2）如下所示。

除了第3和第4节提到的符号外，我们还使用以下定义的一些符号。

算法2的描述：为了实现算法2，我们假设所有玩家都连接在图4中显示的单向环中。算法由调用启动的一个玩家初始化。在第一次迭代中，玩家计算其最佳响应可以是任意的。迭代被定义为一系列最佳响应计算，其中每个玩家正好一次。此外，一旦确定了第一次迭代中遵循的顺序，那么对于每个后续的迭代，它将保持不变。发起玩家i通过固定其他策略来计算其最佳响应（使用算法1），并为了评估其最佳响应，发起玩家i执行以下操作。玩家i从其逆时针邻居接收消息。假设接收到的消息是终止消息（即标志位STOP）。在这种情况下，玩家i将终止消息传递给其顺时针邻居，并声明最初分配的策略为其最佳响应。如果玩家i从其逆时针邻居接收到的消息不是终止消息（即标志位CONTINUE），则玩家i通过观察各个运行队列长度来评估每个服务器的可用处理速率（步骤28-30），并计算最佳响应（步骤31）、惩罚值和范数。然后，它将更新的范数发送给其顺时针邻居。最后，当发起玩家从其逆时针邻居接收到消息时，迭代被认为已完成。此外，玩家的最佳响应计算将持续进行多次迭代，然后算法将收敛到均衡状态，然后终止。

备注9（算法2的计算复杂性）。算法2一次迭代的消息复杂性如下。为了了解服务器运行队列的状态，玩家需要2条消息：一条从玩家到服务器的消息，另一条从服务器到玩家的消息。以这种方式，每个玩家需要2n条消息才能获取所有服务器的可用处理速率。此外，要将其更新的范数值与顺时针邻居共享，每个玩家需要一条消息。因此，在每次迭代中，所有玩家需要2mn+m条消息，其中m和n分别是玩家和服务器数量。因此，算法2的消息复杂度为O(mn)。算法2的时间复杂度如下。算法的额外开销主要集中在计算游戏的最佳响应策略概要（NE），即每个玩家确定的最佳响应策略的组合。因此，考虑到外部循环（第9行到第36行），算法2的计算复杂度为O(mn^2)。因此，算法2是一个多项式时间算法，其开销对于实际应用是可以接受的。

备注10。根据[4]、[6]、[8]、[12]、[36]的说法，对于算法2的收敛性没有理论证明是不可能的。然而，Orda等人在[37]、[38]中研究了并行网络中路由问题的分布式负载平衡算法的收敛性。在[37]、[38]中，作者已经研究了两个玩家两个服务器游戏的收敛性，并明确指出“对两个玩家游戏获得的结果不容易推广到更普遍的情况”。然而，在我们的算法中，每次迭代中一个玩家都在更新其策略，并且系统的状态（即服务器的可用处理速率）在不断变化。更准确地说，为了达到稳定状态，即NE，每个玩家都在迭代中完善其策略。当没有玩家能够通过改变其策略进一步最小化其惩罚函数值时，我们期望NE已经实现。

在6.3.1节中，我们模拟了我们提出的DLBA算法，实验结果验证了我们提出的算法的收敛性与现有算法[4]、[6]、[8]、[12]、[36]类似。

6 实验结果

在本节中，我们首先评估了所提出的DLBA算法在不同类型的分布式系统中的效率，然后我们通过比较分析DLBA与其他三种负载平衡方案的性能。

6.1 性能指标

为了对不同算法得到的解的质量进行定量测量，我们使用了三个性能指标。这些指标的描述如下：(i)公平度指数（FI）。它度量了玩家期望响应时间的公平程度。FI定义为：FI(R)=，其中R是向量R=(R1; ... ;Rm)，其中Ri是玩家i的期望响应时间。FI的值在0和1之间。当FI=1时，每个玩家的响应时间相同。(ii)全局响应时间（GRT）。它度量了系统作为整体的预期响应时间。它定义为：GRT=，这里是系统中的总作业到达率，即=。(iii)百分比负载不平衡（PLI）。它度量了玩家将负载均匀分配给服务器的程度。PLI的评估方式为：PLI=，其中表示服务器的最大利用率， 表示服务器的平均利用率。理想情况下，如果每个系统都被均匀利用，那么这个指标应该评估为零。

6.2 模拟参数

我们的算法只需要两个控制参数：（i）每个玩家的NP和（ii）可接受容差的阈值。在本文中进行的所有实验中，这些参数的值是固定的，即对于每个玩家，NP设置为2n，"=10^-4。对于每次实验，我们对我们的算法进行20次独立运行，然后对每次运行的结果进行平均，以得到最终的结果。

6.3 性能评估

在本节中，我们模拟了我们提出的DLBA算法，并提供了数字结果来展示DLBA的有效性。

6.3.1 收敛分析

为了展示DLBA的收敛行为，我们考虑了一个由10个服务器和10个调度器构成的异构系统。10个服务器的处理速率在表3中给出。对于每个玩家，其作业到达率i由i=fi×TT确定，其中TT由TT=rrTT/∑_(j=1)^mj计算得出。这里rT rT表示系统的总利用率。在图5中，我们展示了所提出算法的收敛过程的两个不同实例。图5a显示了不同服务器的利用率百分比与迭代次数的关系。具体而言，图5a展示了3个服务器（server1、server5和server10）的迭代趋势。就处理速率而言，这些选定的服务器分别属于三个不同的组别：（i）高速服务器-server10、（ii）中速服务器-server5和（iii）较慢服务器-server1。从图5a可以看出，最初，高速服务器（即server10）的利用率随着迭代次数的增加而增加，而相对较慢的服务器（server5和server1）的利用率则随着迭代次数的增加而减少。在第1次迭代后，每个服务器的利用率随着迭代次数的增加而减少。然而，在一些迭代后（第7次迭代后），所有服务器都变得稳定，这意味着算法已经收敛。图5b展示了不同玩家的惩罚函数值的迭代趋势。本图显示了5个不同玩家（player1、3、5、7和9）的惩罚值趋势。玩家的作业到达率如下：1=29.4 jobs/sec，3=22.05 jobs/sec，5=11.03 jobs/sec，7=7.35 jobs/sec，9=3.68 jobs/sec。从图5b中可以看出，随着迭代次数的增加，具有最高作业大小的玩家（player1）的惩罚函数值增加，而其他玩家的惩罚函数值减少。在第7次迭代后，每个玩家的惩罚值达到了稳定点。换句话说，玩家不能通过单方面改变其策略来进一步最小化其惩罚值。因此，该算法已经达到了NE。

6.3.2 权重偏好的影响

在此实验中，我们研究了权重向量w1和w2对我们提出的算法性能的影响。我们选择了五种不同的权重组合（w1, w2）：（1, 0）、（0.7, 0.3）、（0.5, 0.5）、（0.3, 0.7）和（0, 1）。此实验的系统配置如表3和表4所示。系统利用率rrTT设为0.7（即70%）。 在表5中显示了不同权重组合下的不同性能指标的数值。从表5中可以观察到，公平度指数（FI）和全局响应时间（GRT）的值随着w1的减小（或w2的增加）而增加。相反，百分比负载不平衡（PLI）的值增加。其背后的原因是随着w1的减小（或w2的增加），算法更关注服务器的公平利用，并且对玩家的预期响应时间关注较少。

备注11。选择合适的权重组合对算法的性能有影响。在实践中无法通过经验来确定最优的权重组合。事实上，找到最优的权重组合是本文范围之外的一个新的优化问题。然而，对于w1=0:7和w2=0:3的DLBA的结果是接近最优的。因此，在所有未来的实验中，我们将考虑这组权重因子的值。

6.4 性能比较

在这组实验中，我们对比了DLBA与三种现有的负载平衡方案：全局优化方案（GOS）[9]、非合作方案（NCS）[4]和基于Q-learning的非合作方案（QNCS）[13]。我们选择GOS是因为它被认为是确定全局响应时间的基准方案之一。因此，将DLBA与GOS进行比较可以评判DLBA在全局响应时间方面的有效性。选择NCS是因为它是玩家的最优方案，基于非合作博弈概念。选择QNCS是因为它是一种基于非合作博弈设置的最新方法。QNCS的参数与原始工作[13]中的参数相同。

我们考虑了一个由10个玩家和25个服务器组成的异构系统。玩家的配置如表4所示，服务器的配置如表6所示。系统利用率rrTT设为0.7（即70%），权重为（0.7，0.3）。由算法产生的不同指标值在表7中给出。

从表7中可以观察到，在FI和PLI数值方面，DLBA的表现优于其他三种方法。DLBA提供的GRT数值比NCS和QNCS少，比GOS多约2%。另一方面，DLBA提供的PLI数值比NCS少91%，比QNCS少88%，比GOS少31%。其原因在于，在DLBA方法中，除了最小化玩家的响应时间外，还最小化了服务器利用率方面的变化。换句话说，与GOS、NCS和QNCS不同，DLBA方法既不会使较慢的服务器利用率不足，也不会使较快的服务器负担过重。

因此，从表7中可以推断，与其他方法不同，DLBA保证了每个玩家的响应时间相等，并且服务器之间的负载不平衡最小化。另一方面，在GRT数值方面，明显可以看出，DLBA方法的公平性是以增加系统响应时间为代价的。因此，DLBA比其他方法更好，因为它在3个指标中有2个表现更好。

6.4.1 系统利用率的影响

在这个实验中，研究了系统利用率对负载平衡方案的影响。一个异构系统包括10个玩家，考虑了25台服务器进行实验。玩家和服务器的配置分别在表4和表6中。系统利用率的数值从0.1变化到0.9（即10%到90%）。权重组合为（w1; w2）=（0.7; 0.3）。

算法得到的不同性能指标的数值记录在表8中。从表8中可以观察到，DLBA和NCS的FI数值随着系统利用率的增加而增加，而GOS的FI数值随着利用率增加而减少。所有算法的GRT数值随着利用率增加而增加。此外，就PLI而言，DLBA产生了最佳结果。简而言之，可以推断，无论系统利用率如何，DLBA方法都能在响应时间和服务器利用率之间保持适当的权衡。

6.4.2 系统异构性的影响

在分布式系统中，异构性是以服务器的处理速度来定义的。分布式系统的异构性水平是根据速度偏斜度来决定的，速度偏斜度是服务器最大和最小处理速度的比值。因此，系统的异构性与速度偏斜度成正比，即速度偏斜度较高的系统具有较高的异构性水平。

在实验的这一部分，我们研究了系统异构性对不同负载平衡方案的影响。在这方面，我们考虑了具有不同异构性水平的不同系统。我们考虑了一个包含100台服务器和100名玩家的系统。玩家和服务器的配置分别在表9和表10中。服务器被分类为三个不同的组（见表10）：（i）更快的组-由服务器1至25组成，（ii）中等组-由服务器26至75组成，（iii）较慢的组-由服务器76-100组成。表10的配置解释如下。在表10中，第1列表示服务器，第2到5列表示不同的系统。表10的第二行表示不同系统的速度偏斜度。例如，（a）第二列的第一次出现，即4，表示系统1的速度偏斜度；（b）第二列的第二次出现，即10，表示在系统1中，服务器1至25的处理速度为10；（c）第二列的第三次出现表示，在系统1中，服务器26至75的处理速度为20；（d）第二列的第四次出现表示，在系统1中，服务器76至100的处理速度为40。

从表11中可以再次观察到，对于DBLA而言，其FI始终接近1，而PLI也始终最佳（最低）。然而，在低速度偏斜度的情况下，GOS产生了最佳结果。当系统变得更加倾斜时，DBLA的响应时间下降得更快。例如，在偏斜度=64时，DBLA的GRT比GOS高15%，比NCS和QNCS分别少6%和21%；而在偏斜度=100时，DBLA的GRT比GOS少22%，比NCS和QNCS分别少29%和35%。此外，就PLI而言，DBLA在各个偏斜度数值方面都优于其他三种方法。因此，我们可以认为，在高水平的偏斜度情况下使用DBLA可以实现更好的系统性能。

6.4.3 系统规模的影响

在这组实验中，我们研究了不同系统上不同负载平衡方案的性能。为此，我们改变了服务器数量，但保持玩家数量不变。我们考虑了5种不同类型的系统，它们的配置在表12中给出。对于所有5个系统，玩家数量（m）都是100，作业到达分数如表9所示。在每个系统中，服务器数量不同，但每个系统的速度偏斜度都相同，即10。系统利用率 r = 70%，权重组合为（w1; w2）=（0.7; 0.3）。

在这个实验中，系统数量从70变化到1120。例如，第一个系统有70台服务器，速度偏斜度为10。在第二个系统中，服务器数量是第一个系统中服务器数量的两倍，速度偏斜度为10。因此，在这个实验中，所有考虑的系统都具有相同的速度偏斜度。

从表13中可以看出，无论系统规模如何，每种方法得到的公平性数值都是相同的。从表13中可以看出，DLBA的性能在公平性方面比GOS，NCS和QNCS更好，其FI的数值非常接近于1（几乎等于1），而GOS和NCS的公平性则远离1。此外，还可以从表13中看出，DLBA在GRT方面的性能劣于GOS，但优于NCS和QNCS。然而，同时也可以从表13中看出，DLBA在负载均衡的公平分配方面要远远优于GOS，NCS和QNCS，即在PLI数值方面。

可以清楚地从表13中观察到，对于每个系统（不考虑其大小），DLBA都得到相同的结果。总之，可以推断，DLBA在系统规模方面提供了更好的可伸缩性，同时保持了玩家响应时间和服务器有效利用之间的权衡。

7 结论

在本文中，我们研究了具有两个相互冲突目标的负载平衡问题：（i）最小化用户的预期响应时间，以及（ii）最小化服务器之间的负载不平衡。为了量化由用户引起的服务器之间的负载不平衡，提出了一个称为公平性方差的新参数。为了保持两个目标之间的权衡，我们将公平性方差与用户的预期响应时间整合，并将这个整合的目标作为一个新目标。接下来，我们将问题建模为一个非合作博弈。为了计算纳什均衡，提出了一个分布式负载平衡算法（DLBA）。通过对合成原型分布式系统进行实证研究，评估了DLBA的有效性。实验结果表明，DLBA在维持服务器公平利用的同时提供了系统最佳性能。此外，为了评估DLBA的相对性能，我们将其与现有的三种负载平衡算法（GOS、NCS和QNCS）进行了基准测试。对比研究结果表明，DLBA在服务器公平利用方面优于其他算法，并产生了可比较的系统性能。总之，可以推断，我们提出的DLBA是一种有效的方法，可以在负载平衡问题的两个相互冲突的目标之间保持适当的权衡。

这项工作的一个直接延伸可以朝着两个不同的方向进行。首先，为了解决具有相互冲突目标的负载平衡问题，研究动态（按需）负载平衡将是有趣的，该方法可以动态调整计算节点的工作负载，以应对计算环境的波动。其次，考虑到实际重要性，可以考虑在公式中考虑能源成本、通信延迟和服务器可用性等因素。