Abstract

1. Question?

网络存在故障，已有的解决办法都是在拥塞出现后，采取行动，是一种后手的行为，加上大型网络传播的延迟，故障的恢复需要大量时间。

作者提出了积极的故障处理办法，尤其是，TE应该在网络中传播流量，以便只要故障总数最多为k（可配置范围），就不会发生拥塞。此保证应适用于任意组合的故障。方法称为前向故障校正（FFC）

2. Method?

FFC

两个挑战：最小化吞吐量损失和计算可伸缩性

FFC Overview and Challenge

  1. FFC for control plane faults

    控制平面FFC保证只要发生配置故障的交换机数量最多为k，就不会发生拥塞。

    正常情况下，网络会因为配置失败产生拥塞

    image-20201009153846174

    讲配置修改为：这样第一个网络可以容忍k=2,第二个网络k=1.

    a）的网络缺点是网络吞吐量低于没有故障和FFC时的吞吐量。但是，如果没有流量需求（或网络拓扑）的进一步变化，此吞吐量开销将是暂时的，比如可以在s2和s3配置好之后，将s1到s4的流量提高到10。即使是暂时的吞吐量降低，也是FFC提供的鲁棒性的开销。

    image-20201009153952523

  2. FFC for data plane faults

    数据平面FFC保证了多达k条链路或交换机发生故障时，重新缩放后不会发生拥塞。

    考虑下面的情况：

    image-20201009154532269

    上图出现链路失败时，重新分配后，会导致网络的拥塞。

    但是按照下图的分配方法，任意一条链路失败后，不会发送网络拥塞

    image-20201009154541378

    缺点：

    ​ 像控制平面FFC一样，数据平面FFC也会降低吞吐量。但是，控制平面的FFC仅在更新网络时承担开销，但数据平面FFC的开销却是持久的。两种情况的区别在于，当链路或交换机发生故障时，网络容量会减少。为了避免发生故障后发生拥塞，我们必须保留备用容量来吸收发生故障的元素所承载的流量。

  3. Applying FFC

    不同的需要对应不同的网络配置，k的选择，需要进去取舍。

  4. Challenges and overview of techniques

    第一， The first is the scalability with which robust traffic distributions can be computed.

    ​ 可伸缩性，可用来计算可靠的流量分布。

    第二，We must meet the computational challenge while meeting the second challenge of minimizing the loss in network throughput.

    ​ 满足计算挑战，同时还要满足使网络吞吐量损失最小化的第二个挑战。

    解决办法：

    • 交通量和传播条件作为线性约束条件（公式时精确的，但是又很多限制）
    • 将约束转换为所谓的“bounded M-sum”问题。此类问题中的所有约束都可以减少为对最大（或最小）M个变量的单个约束。
    • 最后，借助排序网络，我们使用有效的线性表达式对这些变量进行编码。
    • 结果是具有O（kn）约束的FFC公式。

    两个设置：

    1. 故障的影响易于建模。如果交换机配置失败，它将保留其旧配置；如果链路失败，则入口交换机将确定性地重新调整流量。这种简单性使我们能够使用有效的线性约束来捕获FFC施加的条件。
    2. 虽然故障很常见，但故障率（即发生故障的元件比例）很低。因此，足以防止少量故障（k）。解决k的高值将需要大量计算并且会产生高吞吐量开销

3. Answer?

3.1 Basic FFC Formulation

3.1.1 Basic TE (without FFC)

​ 输入是图G =（V，E），其中V和E是交换机集以及交换机之间的有向链接。

image-20201009181529820

​ The TE problem can be solved based on path-constrained multicommodity flow problem ：

image-20201010083835104

等式2表示没有链接应该过载，等式3指出，流在其所有隧道中的分配总和不应小于其分配速率。等式4指出分配给流的速率不应超过需求，并且所有变量均为非负数。

3.1.2 Modeling control plane faults

  1. 控制面板错误：

    FFC的目标是计算新配置$( { b_f},{a_{f,t}} )$以便只要$k_c$或者更少的交换机无法更新他们的旧配置$( { b_f^{‘}},{a_{f,t}^{’}} )$就不会发生拥塞。

    令$λ_v= 1$表示至少有一个以v作为入口开关的流配置失败；$ λ_v= 0$表示从v开始的所有流都配置成功。网络中控制平面故障的个别情况可以用表示每个开关状态的向量$λ= [λ_v| v∈V]$表示。因此FFC对于$k_c$个失败是具有鲁棒性的就要求网络在情况合集$Λ_{kc}= {λ|\sum_{v∈V}\ {λ_v}≤ k_c}$下没有过载的链路。可以被捕获为：

    123

    $\hat{a}_{v,e} $表示是在没有配置错误的情况下可以从v开始的流到达链路e的总流量也就是：

    image-20201011163648041

    S[t,v]表示隧道t的源交换机是否为v。

    $\hat{\beta}_{v,e} $表示是发生故障（λv= 1）时链路e中从v开始的流（flow)的流量(trafic)上限。即：

    image-20201011163706163

    $\beta_{f,t}$，当$f$发生故障时，$f$流在隧道t上的流量的上限，由于我们假设速率限制器的更新成功，因此可以将$\beta_{f,t}$建模为：

1231

$w’_{f，t}$表示流f在旧配置下隧道t的分配权重（已知）

但是上式约束很多，解决几乎不可能。

3.1.3 Modeling data plane faults

​ 对于数据平面故障，FFC的目标是计算流量分配，以便即使在最多$k_e$链路失败和最多$k_v$交换机失败后也不会发生拥塞。

需要保证，发生的故障的链路不是连接在发生故障的交换机上。

建模：

  1. $\mu_e=1$代表链路e发送了错误 $\eta_v=1$代表交换机v发送了错误

  2. 数据平面故障的情况可以表示为${\mu,\eta}$ ，其中向量$\mu=[\mu_e|e \in E],\eta=[\eta_v|v \in V]$.那么对于最多$k_e$链路失败和最多$k_v$交换机失败后也具有鲁棒性的TE要求在下面的硬件条件：$U_{k_e,k_v}= { (\mu,\eta)|\sum_e \mu_e\leq k_e,\sum_v \eta_v \leq k_v }$。

  3. 数据错误，入口交换机重新调整流量时，它们会改变网络上的流量分布，即将流量从受影响的隧道移到剩余的隧道中。给定故障情况${\mu,\eta}$，我们知道每个流$f$的剩余隧道$T^{\mu, \eta}_f$，这些隧道不穿越任何故障的链路或交换机。FFC要求f的剩余隧道能够保持其分配的速率。即满足：

    image-20201011163919417

    这个表明，当流$f$的$T^{\mu, \eta}_f = \phi$时，$b_f=0$

    上式保证了没有链路会过载。

    LEMMA 1: 满足约束公式2–4,9在故障情况（µ，η）的TE配置$（{a_{f，t}，b_f }）$在所有入口交换机重新缩放后不会导致链路过载。

    证明：

    当发生数据平面故障情况（µ，η）时，流$f$在剩余隧道$t\in T^{\mu,\eta}_f$上的业务负载为：

    image-20201011164411420

    在链路$e$上的总流量负载为：

    image-20201011164542058

    得证。

    Robust tunnel layout

    3.1.3 Efficiently solving FFC constraints

    为了轻松解决大量FFC约束，我们将它们转换为“有界M-sum”问题，然后使用分类网络对转换后的问题进行编码。

    image-20201011165405226

    1. Transformation to bounded M-sum
    2. Encoding for largest (or smallest) M variables
    3. Throughput and computational overhead
    3.1.4 Encoding for largest (or smallest) M variables

最终的结果，效果很明显：

  1. ffc的开销可以忽略不记
  2. 数据丢失减少了7-300倍
  3. 对于不同优先级的网络，可以在保证网络总吞吐量损失忽略不计的情况下，可以保护高优先级流量免受几乎所有损失。

Introduction

1.为什么研究这个课题?

2.目前这个课题研究到了哪个阶段?

3.作者的理论基于哪些假设?

  1. 具有TE的网络，假设基于隧道的转发。一个或多个隧道（tunnel）在每个入口-出口交换机对之间传输流量。我们称此流量(traffic)为流量(flow)。在入口交换机上配置的相对权重决定了如何在隧道之间分配流量。

  2. Impact of data plane faults

    当链路或者交换机失效时，会影响所以通过它的通道，检测到之后，入口交换机会根据配置的权重将流量重新缩放到其余隧道。设一个流有3条权重为（0.5,0.3,0.2）的隧道。当第三条隧道发生故障时，权重（0.5 0.8,0.3 0.8,0）用于拆分流量。

    ​ 举例子：

    image-20201009124937857

    实际网络中的测试：

    image-20201009130211633

  3. Impact of control plane faults

    说明在配置交换机的过程的延迟或失败是如何导致拥塞的。

    举例说明：

    image-20201009125758340

    实际网络

    image-20201009130222759

    所以网络的流量控制改变需要按照步骤进行，上图中，步骤为：

    ​ 1）更新s2和s3处的流量分配比率； 2）如果成功，则更新流率s1→s4。这样，如果s2（或s3）更新失败，将不会发生拥塞。但是，配置失败将使网络更新停止，因为在步骤1结束之前，步骤2无法继续进行。它们还会降低吞吐量，因为如果步骤1失败，则流s1→s4无法启动。

  4. Slow reaction to faults

Conclusion

1.文章的缺陷

2.关于该课题，作者的构思?