利用Overlay为因特网提供QOS服务.doc

利用Overlay为因特网提供QOS服务
湖南大学计算机网络技术研究室
IntServ和DiffServ以及其他的QOS架构都必须满足两个关键条件。一是沿途的路由器在队列调度和缓冲器管理方面为QOS提供支持；二是各ISP支持各种QOS架构。然而，事实证明，这两个条件往往很难得到满足。尽管在因特网方面作了大量的研究工作，但到目前为止，因特网在很大程度上仍然只能提供“尽力而为”服务。
近些年来，研究人员提出了Overlay Network的方案。Overlay Network架构有利于扩展两类应用：一是难以在IP层部署的业务；二是所需的信息难以从IP层获得的应用。Overlay Network的典型应用有应用层组播、Web content分布式网络、Risilient Overlay Network
(RONS)等。为了给这类应用提供新的发展空间，Overlay Network也必须与IP一样，为这些业务提供QOS支持。
首先我们来看看第三方QOS供应商(Third-party QOS Provider)模型。该模型由供应商向传统的ISP购买网络访问权，然后在不同路由域中布置一些节点。这些节点组成一个Overlay Network。供应商利用这个Overlay Network为顾客提供增强型网络服务。比如，某些组织利用Overlay在VPN中提供增强型网络服务。
本文描述了一个称为OverQOS的系统。OverQOS系统表明Overlay Network完全能够向顾客提供某些形式的QOS。它的一个重要的方面就是在OverQOS节点布置QOS机器，而不允许在OverQOS节点之间对数据或IP路由控制平台进行任何形式的改变。
在IP QOS中，IP路由器负责控制分组缓冲区和输出链路带宽，并且能够直接调度这些资源。而OverQOS节点既不控制带宽，也不控制底层IP路径的丢包率。每个OverQOS路由处理一个流聚集(Flow Aggregate)，通过一个链接两个OverQOS路由的虚拟链路以某个公平的速率进行聚集传输。接着通过控制虚拟链路中每一流的速率以实现聚集中各流的资源分配。
聚集中的各允许流按比例分享资源，但并不在丢包率和速率方面做任何保障。为此，OverQOS引入了一个叫Controlled Loss Virtual Link(CLVL)的概念。只要聚集速率不超过某个特定的值，聚集丢包率就将保持在一个很小的范围内。

OverQOS架构
OverQOS架构如图1所示。虚拟链路(Virtual Link)是单向的，流传输只能从某个

OverQOS节点入口进入，在从该节点的出口出来。Bundle 是虚拟链路中加载了应用数据分组的数据流。
一条虚拟链路的参数有两个：链路容量b和丢包率p。b表示在OverQOS节点入口发送到虚拟链路的最大速率；而p表示在虚拟链路中由于拥塞产生的分组丢失的概率。在实际使用中，我们把b当做是流传输加权的标准，并通过与底层网络的管理者(ISP)通过协商达成协议以获得链路容量。b的设定可以采用N-TCP管道(N-TCP pipe)。其中N表示所获带宽是虚拟链路中单TCP连接吞吐量的N倍。N值的大小可以与OverQOS 提供商或ISP协商，或者通过增减bundle中流的数量来实现。
OverQOS节点的实现机制设计存在三个限制条件：
◆ OverQOS节点常常跨越多个路由域和AS；
◆ OverQOS节点常常不与拥塞链路直接相连接；
◆ 一般来说，OverQOS bundle中不包括某些穿越两个OverQOS节点间拥塞链路的流。
因此，OverQOS需要应付传输过程中随时间变化的错综复杂的网络条件，提高bundle的服务质量。
OverQOS有两点基本的设计原则：一是丢包控制，二是聚集资源管理。通过丢包控制，无论网络环境如何变化，OverQOS都可以获得一个下限QOS服务。而把多个流聚集成为bundle，OverQOS就能对其中的单流实施资源分配。

CLVL(Controlled-Loss Virtual Link)
为了使OverQOS能够提供比“尽力而为”更好的服务，我们提出了一个称之为CLVL(Controlled-Loss Virtual Link)的概念，用来衡量bundle的服务。不管底层的带宽b和丢包率p如何变化，CLVL站在bundle的角度，设定了一段时间内的丢失率p。CLVL通过这一思想把bundle的丢失率和IP层的丢包率区分开。
CLVL控制虚拟链路丢包率的方法之一是在bundle中加入冗余分组。FEC(Forward Error Correction)和ARQ(Automatic Repeat Request)就是用来实现这一思想的。ARQ比FEC的带宽需求较低，但由于OverQOS节点间的RTT和重传机制，ARQ比FEC需要更多的时间。
OverQOS节点之间的传输包括两种，一种是bundle流传输，另一种是用来实现丢失恢复的冗余传输。设r表示达到目标丢包率q所需的冗余量，bundle流的有效带宽为c=b(1-r)。
CLVL服务模式的特征是：只要节点入口的bundle到达率不超过c，则虚拟链路的丢包率不超过q。

聚集资源控制
CLVL(Controlled-Loss Virtual Link)提供的服务不基于单流而基于bundle聚集，这样做有两个优点：
◆ 入口节点能控制聚集资源在bundle中各流的分配；
◆ 基于聚集应用FEC控制丢包率比基于单流更加高效。时间窗口中分组的数量越大，FEC的开销越小。
入口节点对bundle传输的控制粒度有两层。一层是基于bundle，一层基于bundle中
的单流。在这两层中，入口节点既能控制发送率，又能控制丢包率。入口节点首先确定虚拟链路底层参数，即b和q；接着确定达到目标丢包率q所需的冗余度r并估算有效带宽c；最后，入口节点把 bundle的有效带宽c在各流中进行分配。如果入口输入的传输量大于c，多出的部分就在入口节点抛弃。而丢包率是根据服务配置分布到bundle的各流中。

使用OverQOS的理由
下面我们讨论下面的一个问题：OverQOS的增强型服务(enhanced service)会不会给某些OverQOS流带来负面影响呢？如果这个问题有了肯定的答案，那我们使用OverQOS就有了极好的理由。
进一步说，OverQOS有没有满足以下条件：
◆ 任何使用OverQOS的用户不会获得比“尽力而为”环境下的因特网更差的服务。否则就没有使用OverQOS的动力了；
◆ OverQOS不能惩罚“尽力而为”传输。理想情况下，我们希望无论有多少OverQOS流，“尽力而为”流能得到与以前一样的吞吐量。这样，ISPs才不会抵制OverQOS传输。
假设有n个流穿过一个拥塞链路，我们考虑两种情况。第一种情况是所有流都是“尽
力而为”数据流；第二种情况是有m流属于CLVL，其它n-m个数据流属于“尽力而为”流。再假设“尽力而为”流都是TCP流。我们不妨认为第一种情况下的每个单流都得到与TCP相当的吞吐量，那么条件二就可以这样描述：无论链路中有多少CLVL流，各背景流所获得的吞吐量都不能小于其TCP-equivalent吞吐量。因此，CLVL的聚集带宽b不能大于m个CLVL流的TCP-equivalent吞吐量之和。这就意味着如果有某个CLVL流获得的带宽超过了其TCP-equivalent吞吐量，则至少有另外一个CLVL流的带宽小于其TCP-equivalent吞吐量。但这显然违反了条件一，既然用户获得的CLVL流带宽小于TCP-equivalent吞吐量，那用户完全可能通过切换到“尽力而为”环境下的因特网而获得更好的服务。
然而，事实并非如此。在上面的讨论中我们将用户的服务和流的吞吐量等同起来。而实际上，用户感兴趣的并不只是优化单流的吞吐量。我们举三个例子，以说明OverQOS如何在满足上述两个条件的前提下为用户提供增强型服务。
拿吞吐量交换丢包率 对于某些用户而言，满足小的丢包率比优化吞吐量更为重要。例如：假如一个流的TCP-equivalent吞吐量为100kbps，那么，一位使用Voice-over-IP应用的用户能得到64 kbps的吞吐量，同时获得小于0.1%的丢包率那就很不错了。使用OverQOS就是这样。在冗余传输中利用单聚集FEC比使用单流FEC能够节省额外开销。
重新分配带宽 许多用户都希望能控制自己的聚集传输。例如一位使用多流的用户有时想以降低某些不重要流的吞吐量为代价来提高重要流的吞吐量。假设某位用户在同一CLVL中拥有两个流，其TCP-equivalent吞吐量各为0.5Mbps。在这种情况下，这位用户能够根据需要在这两个流之间重新分配总量为1Mbps的带宽。这个功能可以通过等级链路共享实现。但在当前的因特网中，这个功能是无法实现的。
临时性重新分配带宽 有时用户想减少短流的执行时间，但不影响长流的执行时间。由于大多数网页都仅仅由几个分组构成，因此这类服务将大大改善网页的浏览进程。为了阐述这类服务的灵活性，我们来看看图2。在一个带宽为1Mbps的CLVL中，共有五个流：长流1个，传输量为200Kb；短流四个，传输量各为50 Kb。长流从0时刻开始传输，四个短流分别从0,0.1,0.2,0.3时刻开始传输。图2(a)所示的是CLVL各流平等分享带宽的情况。当入口节点采用FIFO调度器，所有流使用相同的拥塞控制方案，且具有相同的RTT时，就会发生这种情况。其结果是：长流在0.4sec内完成传输，而所有的短流传输均在0.1sec内完成。图2(b)显示的是入口节点使用单流调度算法，给予短流3/4的有效带宽。结果每个短流都在0.066sec内完成了传输任务。而更为重要的是这种改进又不会影响长流的传输，长流仍然在0.4sec内完成了传输。
综上所述，OverQOS的确能够给用户提供比“尽力而为”更好的服务，而且不会不正当地影响背景传输。
需要注意的是，在实践中，经常会发生违反条件二的情况。在某种条件下，ISP可能更愿意把更多的带宽分配给OverQOS提供商。例如：ISP可以降低传输单比特的价格，减少背景流的吞吐量；而相应地调整提供给OverQOS带宽的价格。OverQOS提供商给用户提供高质量的服务，但以较高的价格收取费用。

CLVL实现
这一部分我们描述两种构建CLVL的方法。一种是纯粹基于FEC的方案；另一种是FEC和ARQ相结合的混合型方案。CLVL的目标是使bundle丢失率q<是难以预测的，我们把统计边界q定义为在一个较长时间内观察得到的平均丢失率。
纯粹的基于ARQ的方案是很容易构建的。在可靠传输(q=0)中，除非发送方收到接收方的确认信号，否则分组就重新传输。要达到一个非零的丢失率q，在时间段中重传丢失分组就足够了。表示包括间歇期在内的平均丢包率。
FEC-based CLVL的构建 在基于FEC的方案中，我们把时间划分成时间窗口，时间窗口是编码/解码单元。假设erasure码(如Reed-Solomon)由(n,k)描述，在这里，k表示在窗口内到达入口节点的分组数目；n-k表示增加的冗余分组数目。冗余因数r定义为r=(n-k)/n。FEC问题就是确定最小的冗余因数r，这样，目标丢失率q就达到了。
分组丢失是无法预测的，因此算法必须要能够处理突发性的丢包率和相关分组丢失。由于q值有时会比p小一至两个数量级，因此我们没有必要在时间窗口内等待接收方关于突发性丢失率的反馈。而且突发性时间段往往与从接收方获得反馈的时间相当。我们没有试图去预测下一次突发分组的发生及其量级，而是采取一种保守方法：在时间窗口内针对过去发生的突发分组计算出分组丢失系数的统计边界，然后设定这个边界的冗余因数。计算表明由突发性分组所导致的网络丢包率边界小于q。
进一步说，假设f(p)表示丢包率p的PDF，其中的p值是由编码/解码窗口测量而来的。对于一个给定的目标丢包率q，可以计算出一个最小的r，计算公式如下：。计算r需要f(p)。OverQOS出口节点在每个窗口中计算出bundle的丢失率p，然后把它发送给入口节点。接着，入口节点使用这些样本构建历史记录，并使用这些历史记录估算出f(p)。
实验证明，上述算法需要2/q个丢失样本才能较为准确地估算出r。由于使用过去2/q个样本就能得到历史记录，我们只需保持一个较短时间内的静态特征就可以了。
FEC+ARC-based CLVL的构建 基于FEC的方案相对容易实现，但当丢包率具有突发性时需要较大开销。为了减少这个开销，我们提出了一个基于前者的扩展方案—FEC/ARC混合方案。
由于丢失恢复的延迟限制，重传次数设定值不超过1。我们把分组分入各个窗口，并在第一个往返时间内的窗口加入一个冗余因数r1。在第二个往返时间内，窗口不能被代替，入口节点就以冗余因数r2重发丢失分组。
下面我们来估算一下r1和r2。在前面所述的f(p)模型中，两个往返时间后分组丢失率的预期值为G(r1)*G(r2),其中的  (2)。

预期的开销O可以简单表示为r1+G(r1)(1+r2)。这里就有一个优化问题。给定一个目标丢失率q，确定冗余因数r1和r2，使预期开销O最小，并满足条件：。
实际上，在丢包率分布上，最优的选择是r1=0。这就意味着最好不要在第一个往返时间使用FEC，而仅仅利用FEC进行分组重传。
图3是FEC+ARQ方案和纯FEC及纯ARQ方案的额外开销特性对比。我们注意到两点：第一，FEC+ARQ方案的额外开销比纯FEC方案要小得多，这是因为FEC+ARQ方案中运用FEC仅仅是用于分组重传，而需重传的分组只占分组总量的很小一部分；第二，当时，FEC+ARQ算法的开销值减至纯ARQ算法的开销水平，此时，r1=r2=0，这是因为每一丢失分组重传次数为一次，但这已经足以达到目标丢包率≤。
尽管FEC+ARQ比纯FEC更加有效，但它需要更长的恢复时间。在纯FEC算法中，其最坏情况下的恢复时间为W，W是编码/解码窗口的时间长度。在FEC+ARQ算法中丢失恢复时间为RTT+W1+W2，这里的RTT入口节点和出口节点之间的往返时间，W1和W2是第一往返时间和第二往返时间的窗口大小。图3的模拟中，RTT、W和W1分别设为100ms。W2的值取决于窗口中的重传分组的数目(最差值：W2=W1；平均值：W2=Pavg×W1)。

CLVL实例
在本节中，我们讨论了三个OverQOS使用CLVL提供端到端流服务的具体实例。这三个实例分别是：单流带宽区分、统计性带宽保障、explicit-rate端到端拥塞控制算法。这三个实例分别代表了入口节点在竞争流中分配CLVL有效带宽c的不同途径。
速率区分带宽分配 带宽分配的一种简单方法就是在各流中按照一定的比例分配。我们可以像DiffServ那样把OverQOS流分成不同的等级，然后在各等级OverQOS流间按比例分配带宽。图4将CLVL传输划分成三个不同的等级。在模拟实验中，bundle带宽使用DRR调度原则按1：2：3的比例进行分配。我们的链路带宽为10Mbps，其中有6Mbps左右用于背景传输。该实验是在两个OverQOS节点之间的带宽区分，但可以扩展到整个Overlay Network。
速率统计和丢失保障 OverQOS能够提供速率统计和丢失保障，这对于流媒体传输是很有帮助的。

如果在入口节点处到达速率小于c，那么入口节点不会丢失任何分组。由于c值本身也在随时间变化，因此不能保证入口节点处一直没有分组丢失。但如果 c的分布能够模型化，我们就能得到一个估计值cmin ，使得P(c< cmin)的值很小。只要底层的c分布一固定下来，cmin就相对稳定了。假如cmin为非零值，入口节点就可以预先得知接纳流的带宽设置，使网络带宽需求小于cmin。由于流到达速率小于c的概率很大，因此CLVL既能为这些流提供统计丢失率保障，也能提供统计带宽保障(这里的流指的是QOS流)。当然我们需要在入口Overlay节点布置接纳控制模块用以在QOS流中分配带宽cmin。而且这些流仅仅在cmin稳定时才能被接纳，当cmin变化时，能够通过重新协商而被接纳。有效带宽的剩余部份能够在bundle的其它流中分配。
下面我们使用一个简单的模拟服务模型来阐述一下CLVL的容量问题。假设两个Overlay节点之间有一虚拟链路，运行CLVL bundle，目标丢失率为0.1%,N-TCP管道，其中N=10。虚拟链路的瓶颈为10Mbps，其中包含有50个长TCP流。下面来观察c值的情况，由于P(c<0.5Mbps)可以忽略不计，入口节点的cmin=0.5Mbps。bundle入口节点实施DDR调度。Bundle包括3个流：(1)一个需要0.5Mbps带宽保障的QOS流；(2)一个3Mbps的CBR流；(3)一个TCP流。流2和流3都是可用带宽流。
图5是三个流的平均带宽与时间的关系。流1获得了0.02%的丢失率，比网络的丢包率2.44%小了两个数量级。Bundle中的TCP流比常规的TCP流获得了更多的带宽，它的端到端丢包率要更小些。如果TCP流超时，流2就能够获得更多的带宽。以上需求都不需要IP路由器的支持，都是由Overlay节点负责施行。

明确速率拥塞控制 与CLVL序号绑定在一起的端到端路径需要新的无须IP路由器支持的端到端拥塞控制算法。最简单的情况是所有端到端流都流经同一个CLVL。由于入口节点能够及时地了解任一点的带宽值c，因此它能决定如何在bundle的当前各流之间分配带宽。并且确保分配给每个流i的ci满足两个条件：(1) ai表示流I的到达速率；(2)。然后通过反馈每个流的信息，使终端主机能以ci速率发送分组，这样就不至于造成更大的丢包率。这个算法可以扩展到多CLVL的情况。

讨论
下面我们来讨论OverQOS设计中几个重要的问题：Overlay的优点、Controlled Loss的作用和扩展性等。
为什么使用Overlay 比起改变IP架构的方案来，Overlay显然易于布置。更为重要的是，Overlay没有采用传统的ISP方案，而是授权给第三方实体，由第三方实体给用户提供增强型通讯服务。类似地，企业可以利用OverQOS建立自己的VPN。
OverQOS中提供优质服务的关键是CLVL抽象。CLVL能提供单流带宽区分、统计速率保证、实施无须IP路由器支持的拥塞控制算法。CLVL有两条重要性质：(1)能控制丢失率；(2)传输聚集。
Controlled-loss CLVL能够以减小bundle的吞吐量为代价，达到预期的丢包率。在这一点上，CLVL与其他类似的QOS机制不同(其他的QOS机制提供一个固定的带宽，但没有任何丢包承诺)。提供Controlled Loss抽象有两个好处：
◆ 在没有任何形式的接纳控制的情况下，Controlled Loss抽象为入口路由器分配bundle资源提供了更为灵活的机制。如果有效带宽下降，入口节点可以选择性地保护重要流，而舍弃次重要流的分组。
◆ 通常情况下，bundle的丢失率比底层的丢包率小得多。我们可以轻易地在bundle中为流布置新的明确速率拥塞控制算法。
可扩展性 可扩展性是OverQOS一个重要的问题。下面我们从以下几个方面来考虑这个问题：状态的数量、FEC开销和OverQOS bundle的数目。
传统提供精粒度服务的方案需要实施单流缓冲区管理、队列调度和接纳控制。对于一个很大的bundle，维持和管理每一流的状态信息显然是不可行的。我们可以采用IP层提供因特网QOS的可扩展技术解决这个问题，如：基于端到端的接纳控制，动态分组状态(DPS)信息等。
FEC开销由两个部分组成：通信开销和处理开销。通信开销可以用bundle速率衡量。实验表明，冗余传输比值是随着bundle速率的增加而下降的。原因在于同一窗口中分组发送的数量随着bundle速率的增加而增加。在未调频的情况下，866MHz Pentium Ⅲ 能处理200Mbps的FEC传输。另外，分组的按序到达完全可以用流水线、高带宽的FEC ASIC技术实现。
实际上，我们希望出现多OverQOS网络共存的局面。在这种情况下，就存在着这样一个重要的问题：如果出现多CLVL共享同一拥塞链路时会有什么效果？这个问题是大家共同关注的。我们的模拟实验结果显示N-TCP抽象允许任意多个CLVL无缝共存。另外，模拟实验结果还表明：使用N-TCP的bundle对于背景TCP传输而言是完全公平的。

参考文献：
[1] Lakshminayanan Subramanian, Ion Stoica, Hari Balakrishnan ,Randy H.Katz. OverQOS:Offering Internet QOS using Overlay.