| Remy拥塞控制系统最全介绍 | 您所在的位置：网站首页 › remy是什么意思中文 › Remy拥塞控制系统最全介绍 |
Remy拥塞控制系统最全介绍
|
一. 人工设计算法时代：常用网络拥塞控制算法
1. 什么是拥塞控制
把网络比喻成现实中的道路交通，那拥塞控制就是负责使道路不至于陷入堵车状态的交警和红绿灯等，当某些道路进入了堵车状态时，交警就关闭此堵车道路的进入路口，将车流引导至不堵车的道路。不过首先得强调的是：拥塞控制是面向可靠传输的，即一般所说的TCP（Transmission Control protocol)可靠传输。因为如果丢包都无所谓，那就没有必要花费资源来进行拥塞控制了。所以我们可以把拥塞控制总结为： 可靠的数据传输需要保证网络流量的畅通，我们通过某些算法和策略（交警或红绿灯）使得网络传输的流量在网络的负载范围（道路交通可通行的车流量）之内，从而避免数据包的丢失 2. 为什么要拥塞控制前面已经提到，拥塞控制面向的是像TCP类的可靠传输协议。这里就要考虑为什么非可靠的传输协议就不需要拥塞控制了吗？是的，非可靠的传输协议对数据完整性需求要低于可靠的传输协议，考虑下面这种场景： TCP拥塞控制使用的是拥塞避免（network congestion-avoidance）的方法，即计算机根据网络反馈的信息，自行判断网络的拥塞状态。如果状态变化，则改变当前数据包的发送速率，一般是使用additive increase/multiplicative decrease (AIMD) 的方法来改变当前滑动窗口的大小，以改变发送速率。其他类似的方法有慢启动（slow start）和拥塞窗口（congestion window）等。下面我们主要介绍下前两种常用的方法： AIMD: AIMD是一个闭环控制算法，即计算机通过获取网络状态信息，然后把状态信息加入到当前算法的输入，得出一个输出的动作，在拥塞控制中这个动作就是调整发送窗口的大小。像下图中就是通过反馈前移或者后移窗口。 slow start slow start是网络数据发送端的发送策略：如果网络不出现拥塞我们将依次增加发送的速率，直到网络出现拥塞的信号，我们再调整发送的速率。像下图中的Reno算法：
发送端首先指数增加其拥塞窗口的大小，直到窗口大小等于初始ssthresh值。停止指数增长在窗口大小大于ssthreash值时，我们使用拥塞避免机制，减少拥塞窗口的增加速度，直到网络中出现ACK超时如果出现超时，我们重新开始慢启动机制，同时调整ssthresh的值，再重复1，2步骤，当状态趋向稳定后，再进行闭环调节  人们刚开始设计拥塞控制算法时，考虑的都是把所有的工作交给发送端计算机自己去做，即发送端自身捕获网络状态并采取行动，这一类的算法称为端到端拥塞控制算法（End-to-end），其代表算法有Cubic, TCP Vegas, Reno等等。下面是端到端的控制模型:sender通过接收网络状态信息，改变发送策略。 
4. 路由器加入游戏
当单个发送端的拥塞控制算法达到其性能瓶颈时，人们开始考虑，是否可以将网路中的其他设备加入到这场拥塞控制的游戏中？至此，基于路由器协助的拥塞控制算法开始出现，这类算法有两种实现方式： 路由器直接向发送端发送报文，告知网络拥塞情况；路由器更改数据段中的某个标志，来提示网络中的拥塞情况，然后数据将这个标志携带到目的主机，再由目的主机根据这个标志，向发送端发送报文，告知拥塞情况（被包含在确认报文中）；常用的算法有ECN,VCP,RED等，下面是路由器协助算法的一个模型，此时能获取网路状态的不仅仅是发送端的机器了： 历史上大多数成功的人都是能乘上时代的风潮而一展宏图的弄潮儿 在介绍Remy前，我们先了解下当时的时代背景。2012年，作为古老的玛雅文明预测的时代重启元年，虽然预言中的世界末日并没有到来，但也发生了一些影响巨大的事。在人工智能领域，随着数据量和算力的激增，深度的神经网络在语音识别和图像分类领域取得了巨大的成功，使人工智能掀起了新一轮的浪潮。 工欲善其事，必先利其器 1. 传统算法的局限新事物的产生，必定是旧事物不再能满足当今人们某些方面的需求。随着互联网的迅速发展，各种网络结构开始出现。在某些如无线局域网，数据中心网络和蜂窝无线网络等网络各种参数变化比较大的网络状况下，传统的TCP网络拥塞控制算法表现得比较糟糕。 就像下图所示，设计好的一套算法无法满足多样的网络环境： 既然人工设计的算法存在着局限，那么是否可以由机器自己去生成算法。其实这就是一种机器学习的思路，要是在当今2020年，万物皆可学习的时代，你没有这个想法才会让人感到奇怪。但在2013年，人工智能刚火的时期，能提出这么个方案并执行出来并不容易。Remy的设计可以分为四个部分： 先验假设模型 我们假定网络中状态是符合马尔可夫过程的，即网络中未来的状态仅于现在状态有关，比如说可以取网络中的三个状态作为马尔可夫链的输入：瓶颈链路速度( C )，传播时延( D )以及链路复用程度( N )。以此来推断网络未来的状态演化。 流量模型 在流量模型方面，作者简单的以铃型链路开关的开关模型为例子。即网络中发送端发送和不发送数据服从随机过程。“开”动作服从指数分布，“关”动作服从经验分布  目标函数  目标函数公式中的𝛼代表一个平衡系数，x代表机器的吞吐量。是每个终端机利用网络状态信息计算出当前的一个目标函数值，即U(x)，一般来说U(x)越大越好。𝛼取不同的值表示目标函数值考虑x的不同的权重。𝛼取不同值时函数考虑因素如下图： 
例如：取𝛼=1时，就是仅考虑x吞吐量而不考虑其他的参数。这样目标函数的值就只和x有关。这样每个终端机的目的就是尽可能最大化自己的分数，而手段就是通过提高自己的吞吐量。但对TCP这样的尽力而为的网络来说，各个终端一味的增加自己的吞吐量可能导致网络系统奔溃。为了权衡个体与总体，公平与效率，作者提出了改进的目标函数： 现在开始正式介绍算法，但介绍之前还得了解下两个知识点： 1. 发送端的状态（RemyCC memory） ACK响应时间的加权指数移动平均（ack_ewma）TCP发送时间的加权指数平均（send_ewma）最近响应时间和最小响应时间的比率（rtt_ratio） 2.发送端动作（Action） 当前拥塞窗口的乘数（m）当前拥塞窗口的加数（b）连续发送数据包的间隔（r） 3.映射关系（Mapping the memory to an action）
 样本网络中训练算法 把上一步骤中找到最常用的规则作为本轮的迭代的memory，然后依次调整action中的m,b,r值，调整的步骤依据以现有的值，每个参数依次增加或减少100次。例如r=0.01，那下一轮调整的值为r+0.01或者r-0.01；再下一轮就是r+0.08或r-0.08。作者按8的指数规则对参数进行调整100次。三个参数就总共调整1003次，然后每次依据返回的网络状态计算目标函数值，直到求出当前memory状态下的最优action后，将memory和action组合加入Rule table。至此，一条规则生成！  重复全局迭代 重复步骤1，2。直到找不到epoch=0时的最常用规则后将epoch迭代次数加1。在和设定的迭代轮数k比较，若epoch为k的倍数，则算法生成完成。否则，进入下一轮迭代。这里的k是权衡当前网络结构和性能提升后的网络结构对算法的影响。映射表的泛化 最后，Remy生成了一张Rule table，此时算法生成完成。但为了提升泛化性能，作者将一个action对应的memory在三维空间中泛化为距离当前memory值最小的矩形中的8个点，其规则遵循第二步中的8的倍数增减规则。  上面就是Remy生成算法的全过程。通过在ns-2网络中仿真，通过大量的数据拟合来生成一种应对当前网络结构的拥塞控制算法。
四. 先驱者的短板：Remy的一些不足
在介绍Remy的一些不足时，我们先总结一下Remy的一些特点： Remy是一种端到端的拥塞控制系统，其通过网络中的一些参数计算拥塞控制窗口以及发送时间来，调整发送状态进行网络拥塞。Remy算法并不是线性的这种方法通过网络中的一些预示未来的参数来对评价一个算法的好坏，并针对一种模型来找到一个最好的算法。作者认为这个模型能在更大范围的网络取得成功，如果其能获得更准确的先验网络状态。Remy中主机虽然不一直保存一个开的状态，但其也和TCP一样采用慢启动策略下面由实验介绍对Remy进行评价： 作者在ns-2网络平台进行仿真，并将其生成的算法与以往的算法进行对比。仿真结果显示Remy生成的算法在许多情况要比以前的算法更好。我们在下面选取部分实验进行分析说明。 首先，在铃型链路中进行仿真，可以看出不管是在链路吞吐量或者是延时上，Remy生成的算法要好于以往的算法： 在2012这个新一轮人工智能发展的起点，MIT的研究人员顺势而为推出了Remy。这次机器学习在拥塞控制领域的新尝试，使其成功登顶了计算机领域的顶会—SIGCOMM。再次像我们展示了创新性对科研成就的巨大影响，虽然这个系统有时代的局限，存在一些未解决的问题，但不影响其地位。 参考文献[1]. Winstein, Keith , and H. Balakrishnan . “TCP ex Machina: Computer-Generated Congestion Control.” Proceedings of the ACM SIGCOMM 2013 conference on SIGCOMM ACM, 2013. |
当两方进行视频通话时，网络的拥塞一般会导致视频的卡顿。但当网络恢复正常时我们可以重新传输这些丢失的信息，不会造成信息的不一致，一般我们也是这么做的。 但对TCP传输的信息来说，每一部分消息相互联系构成一个整体的信息。每一个部分都是不可或缺的，如果传输过程中因为网路的拥挤导致发送的部分信息丢失，接收端将无法推测出发送端的信息内容。像我们常用的邮箱，当一个邮件中的某些数据包丢失时，邮件内容就可能出现乱码，此时就有必要进行拥塞控制。 
MIT的研究团队乘着这阵浪潮，在计算机顶级会议SIGCOMM上提出了第一个机器学习用于网络拥塞控制的新系统—Remy，开创了机器学习应用于拥塞控制的先河。
探究其原因，主要是计算机中得拥塞控制算法都是由人设计的。算法设计师利用自己对网络环境已有的经验，对具体的网络状态设计出不同的算法策略。这样有两个隐患：
在这个函数中，我们不再只考虑吞吐量，而是也考虑链路延时。但是目标函数原则还是不变，尽可能提高自己的函数值。所以Remy的目的就是找出能实现大家的值的算法究竟是什么。β和𝛼一样，𝛿表示吞吐量和时延的重要程度。 至此，前期准备工作算是基本完成了，下图为Remy的模型： 
Remy通过建立一张主机的memory与action对应的表，来定义网络在memory状态下需要进行的动作。可以将其理解为计算机中生成了一张规则表，来指导发送端进行拥塞控制动作。 
下面我们讨论Remy如何生成这么一张Rule table：具体流程图如下： 
整个流程可以简化为三个部分：
但是在蜂窝无线网络等网络链路状态变化过于大的系统中，Remy的算法在部分性能上不如其他的算法 
最后还介绍下先验假设情况不同的情况下，Remy的性能在不同参数情况下的表现。由下图可知，先验知识越准确，性能表现越好。 
从上面的实验结果可以看出Remy在部分情况下的性能表现并不是很好，这里的原因主要有两个【本文地址】