对冲乐视下跌:组播拥塞控制的算法

组播中的拥塞控制

概念
通过网络进行的数据和信息传输已经成为现代商业社会重要而又不可缺少的组成部分和赖以生存的基础。近年来，随着信息技术的迅猛发展，网络应用大量增加，使得原来已经存在的庞大的数据传输量成倍地增长。

在已经被Internet普遍采用的工作方式中，数据传输一般通过单路广播和广播两种方式进行。其中，单路广播方式是传统的点对点数据传输，在发送方和每一接收方需要单独的数据通道，从一台服务器送出的每个数据包只能传送给一个客户机，现已为绝大部分数据传输业务所采用。广播方式则允许一个主机将同样的信息发送到同一网络内的所有其他主机。

面对已经庞大而且还在不断增加的数据传输业务，这两种方式越来越凸显出自身的缺陷。依照原有的单路广播方式，如果Internet中有1000个用户希望获得同一个数据包的拷贝，那么每个用户必须分别对信息源节点服务器发送单独的请求，而信息源节点服务器必须向每个用户发送它们自己申请的数据包拷贝。这种巨大的冗余代价首先是负担过于沉重的服务器的响应时间很长；其次是管理人员被迫购买不必要的硬件和带宽，来保证一定的服务质量，资源和成本极大浪费。在目前的情况下，无论如何改善硬件基础条件，单路广播也无法完成将数据分发给分布在Internet上的数十万台计算机的传输业务。而囿于自身独有的性质，单路广播难以满足现今灵活而多样的业务要求，企业网络规模的扩大也使得单路广播方式应用的空间更为狭窄。

基于以上情况，人们一直在寻找一种更符合商业运作模式、更为灵活的数据传输方式。由于从一个主机向多个主机或者从多个主机向多个主机发送同一信息的业务已经在现有的业务总量中占据了相当大的比例，因此人们提出了组播的概念。在最初提出的对组播的要求和设想中包括：组播应该把网络纳入信息传输过程；组播在完成多点到多点或一点到多点的数据传输业务时的性能应比传统传输方式有较大的提高；组播应该具有较广的业务范围。

1988年，斯坦福大学就是依照上述的一些设想实现了第一次多路通话。1989年，组播的详细说明问世。这份说明虽在至今的十余年中经过多次修改，但一部分根本的原则始终得以坚持和完善。其中最根本的一点在于:组播依托于IP协议完成;IP组播强制网络在数据传递树的分叉处进行信息包复制，而不是由信息源节点多次重复地发送同样的信息包。这也正是组播的精髓所在。1992年，IETF定义和发布了一个组播的网络标准，用于建立组播主干网 (MBONE),即在Internet上运行的单路广播和组播综合网络。两年后，这个主干网就已经初具规模。这个平台构建在原有的Internet设备上，由支持IP组播的子网和路由器组成，同时允许组播通信量通过无组播能力的Internet部分，从而在整个Internet范围内对组播开放。1995年，Cisco和Lucent开始销售支持组播的路由器和交换机。一年后，依赖组播的应用产品开始上市。在十余年的开发和研究中，组播已经成为人们关注的一个焦点。

基本认识

组播拥塞控制问题的重要性随着组播日益广泛的应用需求而变得越来越重要。发生在组播中的拥塞既对拥塞控制协议的设计提出了新挑战，同时也提供了一个对已经存在的控制方法与观点进行重新认识的机会。组播虽然是应用在Internet上的，但其拥塞控制仍然依赖于TCP/IP协议。传统的TCP拥塞控制和IP拥塞控制对组播的拥塞控制仍然具有较大的参考价值,传统算法和理念也是组播拥塞控制的出发点和技术基础。

发生在不同环境中的组播对服务的要求千差万别，单独的某一个拥塞控制算法根本不能完全适应其需求。

大多数进行拥塞控制研究的专家都是沿着这样的方向前进的：在源节点端采用基于速率的拥塞处理机制；在公平性标准方面则尽量实现与TCP拥塞控制的兼容，从而适应TCP拥塞控制算法。不过，将基于速率控制的算法用于源节点端已经遇到了很大的阻力。按照这种方法，为了响应拥塞发生，源节点端需要立即接收到所有接收者状态的反馈信息。然而，由于组播涉及大量的接收者，所以从接收者直接发往源节点端更新信息的过程会非常复杂,而且代价非常昂贵。

端对端数据传输业务的拥塞控制

端对端的数据传输与单路广播是完全不同的两个概念。端对端的数据传输是所有数据传输业务的基础。

在端对端业务的拥塞控制中发挥重要作用的两个因素是控制参数和控制算法。控制参数指的是对流入网络的数据流进行管制的指标。例如，如果选定窗口的大小为控制参数，那么控制策略就是将待发的数据量保持在允许的窗口范围之内。控制算法则是确定控制参数的算法。在TCP拥塞控制中，控制参数是窗口的大小，控制算法则由慢启动和拥塞避免两个算法组成。

从拥塞控制的角度看，在一个组播过程中，其接收者资格既可以是固定的，也可以是变化的。当一个组播过程的接收者资格完全固定时，无论网络的拥塞状况如何，所有的接收者都必须自始至终地保留在组播接收组中。在这种情况下，拥塞控制的核心就在于源节点端的流量控制规则。源节点遵照这一规则对所有的接收路径作出相同的反应，这就意味着，流量控制参数由所有接收者中最慢的一个决定。

当一个组播的接收者资格可变时，拥塞控制由流量控制策略和接收者资格确定联合完成。一方面，某些特殊的应用提出了特定的数据要求;另一方面，接收者的数量要尽量多，在这两方面要求之间应建立一个尽量好的平衡。最原始的方法就是将接受速率最慢的接收者的资格取消，但这种方法显然会带来网络的不稳定，没有从根本上解决问题。还有一种相对好一些的方法，就是把组播接收者按照接收速率分成若干个子群，每个子群依照各自的、不同的速率接收数据：速度比较慢的那些子群将花费更多的时间完成数据接收；如果是实时通信，那么这些子群接收到的数据质量将降低。使用这种方法时，数据文件或数据流必须依照适当的编码和封装技术组织起来，以适应不同接收速率子群的需要。

在端对端的业务中，差错控制与拥塞控制关系密切。这是由于对数据包丢失的探测和报告对两者都是有用的。另外，差错控制的方法会影响数据的编码和组织方法。基于这些原因，在端对端业务中的差错控制与拥塞控制往往集成设计在同一个协议中。

上述的拥塞控制策略可以由组播的源节点和接收者分担，而且确定每一方承担的任务的标准和方法也是多样的。在单路广播中，源节点与接收者之间的任务分割不是很重要。不过，将一些已经被大量采用的策略进行改进，增加接收者在拥塞控制中承担的任务，可以提高这些策略的适应性和生命力。

在组播中，不同业务在各自的源节点和接收者之间分布和组织数据的方式非常重要。协议的鲁棒性依赖于进程内部控制信息的准确交换，而当接收方的数量增加时，协议的可扩展性很大程度也依赖于此。组播所特有的一些性质可以确定进程间业务组织的一部分特性，如接收方资格是否固定、源节点是否对每个接收端的进程都进行记录等。

组播控制算法有一个非常重要的性能指标——可扩展能力。它是指在控制算法的性能开始退化之前，接收群能容纳的最大的规模。这个指标是有限的，原因有两个:大的接收群会增大拥塞控制的复杂度，拥塞控制采用的算法也对接收群中接收方的数量提出了要求。从更深的层次来看，可扩展能力与控制算法的公平性以及拥塞避免属性有着密切的关系。

组播拥塞控制的焦点问题

1．控制参数的选择

可供选择的参数包括传输速率和窗口容量。

（1）基于传输速率的控制策略。最简单的形式就是保持源节点以低于设定值的恒定的速率向网络发出数据流。而另一种策略是保持数据发送的平均速率低于设定值，同时增加第二个参数,对突发的数据流进行控制。对于单路广播和组播，基于速率的拥塞控制的含义与实施过程是完全相同的。

（2）基于窗口的控制策略 在单路广播中，基于窗口的控制策略将未确认的数据包的总长度控制在设定的窗口容量以下。对于组播，窗口的含义以及这种控制策略的实施在很大程度上将变得更为复杂。然而，这种复杂性也为基于窗口的策略作出针对组播的改进提供了机会。

在一个源节点对多个接收者的组播过程中，源节点的发送速率是相同的，而不同的接收者窗口的容量却是不同的。依据控制论的观点，相对于同一个系统和过程，控制参数越多，控制效果就越好。基于此，在组播的过程中，一般都选择窗口容量作为控制参数。

在基于窗口的组播控制策略中，为避免发生不必要的资源节点浪费，得到尽可能好的传输效果，每个接收者的窗口容量要分别设定;广播过程中，控制算法必须对每个接收方未确认的数据包数量分别进行监视和控制。这正是这种控制策略的代价所在。

基于窗口的组播拥塞控制策略的复杂度随着接收者数量的增加呈线性增长。它引发了比较严重的扩展性的问题。

2．控制参数的公平性

拥塞控制的参数选定之后，需要采用某个特定的算法，求出网络拥塞状态相应的参数取值。当控制策略的公平性主要体现为控制算法时，它就会受到参数选择的影响。

如果某一控制策略在每个进程中达到平衡时待确认数据包的平均数量与其回路响应时间无关，而仅仅依赖于数据丢失率，那么称这种策略具有与窗口相关的公平性。相应地，如果某一控制策略具有与速率相关的公平性，那么进程中待确认的数据包平均数量由回路响应时间决定。

这里定义的公平性与控制参数的选择没有必然的联系。不论是基于窗口的控制策略还是基于速率的，这两种公平性都可以通过选择不同的控制算法达到。这里定义的两种公平性并不是对一种算法公平性的完美概括。此外，定义上述公平性的依据是算法达到平衡时的性能，并不是算法在进程中的平均性能。

通过分析基于窗口与基于速率两种控制策略的控制过程，人们发现，在控制参数、算法回路响应时间以及算法的公平性指标三者之间存在着特定的联系:要通过基于速率的控制策略达到基于窗口的公平性，或者要通过基于窗口的控制策略达到基于速率的公平性，都必须知道回路响应时间。

3．由接收者驱动的拥塞控制

相对于单路广播，组播有4个主要的特点：

(1)当接收者的数量增加时，对系统进行拥塞控制的复杂度会随之增加。如果拥塞控制一部分特定的工作由源节点来完成，那么源节点有限的处理能力将限制控制算法的扩展性。

(2)并不是所有的拥塞控制措施都是针对源节点的。如果控制策略要求某一个接收者退出接收群，那么这些措施只能由接收方自身来完成。

(3)在大规模的组播系统中，重发丢失的数据包并不总由源节点来完成。

(4)在很多组播应用中，接收方的数量和身份并不为源节点所知。

由以上分析可以得出这样的结论:组播中拥塞控制的任务应该尽可能地向接收方一侧转移。也就是说，每个接收者自主地确定自己的控制参数阈值,这就是对“接收者驱动的拥塞控制”的通俗理解。显然，根据这种方法，每个接收者都必须探测自己路径上的数据丢失,以确定自身控制参数阈值。此外，如果控制算法需要使用回路响应时间，那么探测和记录这个时间的工作也要由接收者自己来完成。

一旦接收者确定了各自的参数阈值，那么必要的反馈必须马上提交给源节点。在基于速率的控制策略中，由接收者发送回源节点的反馈就是它的阈值速率，这样，整个系统的传输速率可以用加法求出。如果采用的是基于窗口的控制策略，那么源节点的窗口容量也可以通过一定的优化算法从各接收者提供的反馈中更精确地确定出来。

1999年，贝尔实验室的3名研究人员提出了一种主要由接收方执行的拥塞控制策略。他们对组播的环境进行了一定的限制和规定，然后得到结论:这种策略的可扩展性可以在很大范围内得到保证。这项成果把可扩展性与控制参数以及算法公平性联系起来，已经成为近来组播拥塞控制的出发点。

组播面临的挑战

组播拥塞控制面临的最大挑战仍然是扩展性问题。在组播树中，为了响应拥塞发生，源节点需要立即接收到所有接收者状态的反馈信息。然而，由于组播涉及大量的接收者，因此从接收者直接发往源节点更新信息的过程会非常复杂且昂贵。

组播中拥塞控制的另一挑战是持续拥塞效应的隔离问题。由于TCP拥塞控制在树的任意一部分接到拥塞指示时都会减少发送速率，因此一个组播树会影响Internet中许多不同的部分。虽然这种方式在不同数据流之间有一定公平性，但会在同一个Multicast组中的不同接收者之间导致不公平，特别是对那些实际上并没有拥塞的接收者来说降低传输速率不公平。对可扩展的可靠Multicast来讲，解决以上挑战的主要思路在于建立合理分层的来自接收者的反馈信息的发布方式;克服估计Multicast Tree中阈值确定困难的问题;建立重传窗口规范,恢复数据流，防止恢复阶段又发生拥塞等。

针对这些问题，有人提出了一种在Multicast上的MTCP(Multicast TCP)拥塞控制，其扩展性和公平性试验的仿真结果较好，为解决这一问题提供了可参考的方向。但是，无论如何，源节点只有一个，它不可能满足所有接收方的相同的业务要求。重要指标的选择和保证措施便成为这种情况下最重要的一项工作