P2P覆盖网络中流媒体分布式优化方案

P2P覆盖网络中流媒体分布式优化方案译文原文：DistributedOptimizationofMediaFlowsinPeer-to-PeerOverlayNetworks论文原作者：AntoniosArgyriou&JacobChakareskiP2P打破了传统Client/Server(C/S)模式，在网络中，每一个节点的地位都是对等的。每一个节点既充当服务器为其他节点提供服务，同时也享用其他节点提供的服务。P2P网络非中心化的特点，即网络中的资源和服务分散在所有结点上，信息的传输和服务的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。带来了其在可扩展性、健壮性等方面的优势。P2P网络中随着用户的增加，其资源和服务能力也在同步的扩充，因此理论上其可扩展性几乎可以认为是无限的。同时在P2P网络中将计算任务或存储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算和存储能力。同时，因为资源分布在多个节点，更好的实现了整个网络的负载均衡。与传统的系统相比起来，P2P技术具有巨大的优势，它已经被广泛的应用到例如文件内容共享（例如，电驴，比特精灵等），协同处理，即时通讯等等方面。随着在线视频产业在互联网上的飞速发展，基于P2P的流媒体应用，例如PPlive，PPStream，QQlive等应用在互联网上迅速流行开来。在大规模的P2P视频点播和直播服务中还有很多可以突破的技术，本文提出一个分布式的流媒体优化方案。这里考虑的问题是，在非结构化的P2P覆盖网络中最优的流媒体失真问题。通过公式将这个问题表示为一个分布式的速率分配问题，并且用一个传统的分解技术来解决这个问题，以便全网设备的媒体失真率达到最小化。通过对等端之间的信息交互来保证本地速率分配代价的时效性。流媒体数据包同样附带着包含受解码器影响和自身大小影响的率失真信息。这个做法带来的好处就是对等端可以不用再计算最优速度分配而转换为简单的允许转发或丢弃行为的轻量级实现。而且，模拟结果也表明，当我们的流媒体算法中加入媒体数据包的精确的率失真特性描述时，将会带来显著的质量效益。P2P网络已经成为一种替代IP组播实现以点对多的媒体分发的解决方案。P2P网络从根本上说是一个由协作端之间的单一会话组成的覆盖网络。对等端的主要任务就是扮演一个代理的角色，缓存一部分接收到数据包，这些数据包将会被转发到网络中其他的对等端。这种交付模式的一个主要好处就是它提供了一种可扩展的方式来分发点播或直播的视频给大量的接受者，而系统的容量将会随着对等端的增多而增大。大规模的点播和直播的P2P多媒体流取得了巨大的成功。这个系统的性能曲线主要取决于覆盖结构和维持算法.或许影响P2P网络最重要的问题就是P2P覆盖网络的结构受到参与端行为的动态影响。因此，如果覆盖网络被组织成一棵树，那么带宽的波动和失效的对等端如果靠近根节点的话将会造成缓冲区向下溢出，而影响到大规模的下游节点。为了减轻这些问题带来的影响，一个基于网格的P2P网络覆盖协议允许无需来自常规网络覆盖结构里的明确支持的对等端之间的数据传播。通过这个方法，一个对等端可以一边接受数据一边随机的选取目标端的一个子集来推送接收到的媒体数据包。如图，我们简单的假设媒体在网络中的分发情况，节点P4必须最大限度的同时保证转发给客户端C1和C2的数据包的质量。这个传输过程优于现行的数据传输在于它提供一个高度可靠的数据分发。然而我们不能简单将这种交付方法用于点播的媒体流，因为它可能无法实时交付。另外一个缺点就是允许相邻对等端直接的传输，对于高带宽视频流应用程序来说，大量的数据副本将会造成一个很大的开支。尽管有大量对P2P流媒体的研究，但是大部分已有的工程都将焦点放在不同的应用层流交付模型上的性能上。尽管这个很重要，但是通讯模型和覆盖层维护算法已经被独立的开发和研究而且已经推广开来。说得更具体一点就是，现在缺少一个考虑到个别媒体数据包对整体P2P流媒体影响的通用框架。在本文中，我们在这个方向上迈出一小步，应用一个采用率失真优化的数据包调度和独立于覆盖层结构的媒体流的分布式流媒体优化方法。率失真优化流算法已经被成功的应用到更加高端的应用中，因此他们提供了另一个在像P2P覆盖网络这样更加普遍的通讯模型中研究多媒体分发的方案。在主流的P2P流媒体项目中，流媒体仅仅考虑到类似最大可接受的延迟，最小带宽，以及最小的丢包率这样一个抽象的服务质量需求。然而有明显影响的单个媒体数据包解码的质量却没有被考虑进来。不同的媒体数据包对他们的解码率失真性能有着不同的重要的作用。直到最近，才有一些研究工作关注到这个方向。例如，在参考文献[6]里面，作者同样考虑到了在P2P工程中的率失真优化流，但是他们关注先进的以及描述多样的编码方案。我们相信考虑到不同媒体数据包的率失真的特点是一个很重要的概念，因为它允许在不同的覆盖拓扑结构上对媒体流的质量进行细粒度的评估。为了避免我们的计划被限制在特定的拓扑结构中，我们假设一个基于网格的P2P传输模型，参与的对等端来自随机的连接定向的网格（即非结构化的网络覆盖）。两个对等端之间的连接是单向的，这就意味着数据是从父节点交付给子节点的。每一个端在网络覆盖结构中都有多个父节点和子节点。我们假设一个对等端可以从一个中央服务器获取当前活跃节点的列表。说具体一点就是，这个引导服务器维护一个所有参与的对等端的列表并且为新参与的对等端提供所有参与者的子集。每一个参与的对等端都要为在同一个层中转发的媒体流提供一个向前的子集。把这种覆盖拓扑结构建模为一个有向无环图G={N,A}，其中N表示所有的覆盖层节点，A表示连接对等端的的连接方向。我们定义M为目前正在交付的媒体流数，同样，定义Am为对等端之间用来转发媒体流m的连接方向。图[1]显示了一个简单的有两个正在转发的媒体流的拓扑结构。我们在数据包的级别来考虑媒体流，因为如果没被解码的话不同的媒体数据包对视频的质量有不同的影响。我们定义一个来自媒体流的媒体数据包m的索引为km。类似相关的工程,率失真信息被包含在它的数据包里，包括它的大小R（km）和对重建视频时造成失真（被定义为ΔD(km)）。在实际中的ΔD(km)，是率失真的MSE（均方差）增长的总和，如果数据包没有在规定的最后期限内交付的话将会影响到视频流。如图，每一个对等端同时为传入的流媒体维持多个缓存区域，媒体数据包的转发取决于速率分配算法。我们提出这个方法的目的是为每个被对等端转发的媒体流计算最优化的带宽分配。这是一个分布式的速率分配问题，它可以被公式化为一个约束优化的实用功能。在对上述问题正式定义之前，我们先来引进需要的符号：D(i,j)m(r(i,j)m)表示与当流m∈μi以速度r(i,j)m在对等端ij之间被转发时相关联的失真率。μi表示在对等端i引入的媒体流组。那么，全部通过链接(i,j)转发的流的总失真率就可以表示为：（1）其中γm是一个很重要的因素，在执行速度分配给向外转发的link(i,j)时候，对等端i可以被分配给媒体流m。这个权重因子表示流m在交付需求方面的重要性。它将间接影响到分配给特殊流的速度。（2）这个表达式表示通过link(i,j)发送的流的整体速度。其中r(i,j)m表示分配给流m∈μi的速度。使用前面表达式来表示总失真率是在特殊的对等端间链接里引进的，我们可以用如下的表达式表示所有对等端和所有媒体流的平均媒体失真率：（3）我们把网络失真率DN减小到最小的话可用的带宽R(i,j)在每一个连接路径link(i,j)∈A就不会溢出。因此，我们考虑的优化的问题可以写成：（4）接下来，我们为解决这个问题提供一个分布式的解决方案：现在我们的目标是以最小的协调和信息传递来让每一个对等端参与解决这个最优化问题。由于RD（率失真）曲线是凹的而且是两次可微的，我们可以直接应用拉格朗日对偶性来解决先前的这个约束优化问题。此外，这个实用程序功能是可分的而且两次分解之后可以推导出来一个分布式的解决方案。我们可以对约束优化问题（4）应用拉格朗日对偶性运算，并且得到以下局部的拉格朗日式子：（5）在这个公式中，Λ(i,j)0表示在端i上，link(i,j)的拉格朗日乘数。那么对偶函数被定义为：（6）其中Λ是每一个对等端的拉格朗日乘数向量。因此，这个对偶问题是：（7）现在，拉格朗日乘数表示每一个被选择的速率分配的代价。我们知道，现在，如果Λ*是对偶问题的最优解决方案的话，r*(i,j)(Λ*)就是我们定义在（4）里面的最原始的问题的最优解决方案。此外，这个拉格朗日乘数将原来的问题分解成为了对于每一个对等端可以独立优化的独立的流速率分配问题。尤其是，每一个对等端i必须解决最优的速率分配问题：（8）现在，对偶算法的收敛就是分布式流量控制问题的最优解已经被一个凸面的效用函数证实了。为了计算每一个对等端节点i的拉格朗日乘数Λ(i,j)，我们采用梯度法;（9）来计算Λ(i,j)，在每次速率分配后执行。现在看看在一个节点的多个流的速率分配。在一个新的优化水平里，我们将会计算一个端节点分享给传出流的最优速率分配。这么做是基于转发的流的重要性并通过梯度因素λm=δDm(R)/δR反映出来。这个因素体现了在媒体流m的数据传输速率以及信号失真率之间的权衡。特别的，在对我们选择的流m运行的率失真曲线Dm(R)它保持γmδDm(R)/δR≈Λ(i,j)。与此相关的对应在曲线上的率值就是应该被分配给从对等端i到对等端j以路径link(i,j)转发的最优速率。现在，我们把这个最优值记为r*(i,j)m。那么，整体转发速率就是：（10）由于一个媒体流已经分配了它的传出速率r*m(i,j)，所以一个对等端可以轻易的将这个速率制定给每一个独立的数据包，数据包包含的媒体流没有任何下一步的优化步骤。现在，对失真率的描述信息被包含在每一个独立的数据包。由于每一个数据包k被ΔD(km)和ΔR(km)标记，一个对等端可以轻易的计算出每一个数据包的梯度ΔD(km)/ΔR(km)。此外，由于连接路径的拉格朗日乘数Λ(i,j)已经可以从每一个对等端的本地获取，因此梯度ΔD/ΔR比Λ(i,j)更优的数据包将会被转发，否则将会直接被从本地缓存里丢弃而不会被继续在覆盖层里转发了。因此，每个对等端的问题被还原为简单的通过比较通过比较由他们的失真率描述信息表示的他们的相对重要性，来决定转发或是丢弃数据包。最后，我们通过比较参与对等端不同的数据包调度算法得到的模拟结果。我们执行了数据包级的ns-2网络仿真器的一部分算法。对等端之间的数据传送我们使用了TCP的选择确认协议。我们通过不同的上传容量来测试对等端，为了表示不同区域的用户的非对称的最后的访问路径，我们假设他们的下载速度高8倍。关于建立覆盖网络，主要的原则我们已经在第二节中解释了。说得更加具体一点就是，每一个对等端向中心服务器请求一个它可以获取内容的五个对等端的列表。这个列表被用来平均的分配传入的请求。因此，没有什么特别的覆盖网络维护算法。我们比较了一个最早的截止日期第一的调度算法和一个采用无特别调度技术的贪婪算法。而不是使用实际的视频数据，我们创建了人工的预格式化的视频内容.这种人造数据单位的形式类似于等距离的视频的帧序列，同时他们也有相互依赖的特性。采用这种模拟的办法的主要优点在于它允许我们将焦点精确的放在潜在流优化算法上面，这也是本文的重点。框架由通过它们对接受者的重要性来分层组织的数据单元组成，所有的数据单元有相同的大小，设置为200bytes。与质量的增长相联系的数据单元被定义为质量单元。例如，符合相同内部编码的框架的单位有一个10的失真率。每一个对等端的成功准时收到媒体数据单位的质量都被统计下来。最后，预格式化数据的帧速率被设置为30帧每秒，同时，初始的向前翻滚延时为4秒。A，结果对于我们的评估，我们实验了在一个包含50个覆盖节点和两个转发流的静态网络中采用推荐的流系统。在图[3]a中，我们给出了在试验中测试的覆盖层中所有的客户端的平均质量。