浅析Internet区分服务中组播技术

安 军

（ 铜仁学院 物理与电子科学系，贵州 铜仁 554300 ）

浅析Internet区分服务中组播技术

安 军

（ 铜仁学院 物理与电子科学系，贵州 铜仁 554300 ）

本文主要研究Internet 区分服务体系提供服务质量保证问题，分析了端到端服务质量体系结构、组播技术，以及区分服务中存在着一些问题，以此，结合网络编码技术，本文提了基于网络编码的最大流单源组播路由算法。

QoS； 区分服务； 组播； 网络编码

随着网络技术与多媒体技术的迅速发展，人们越来越期望网络能提供某种程度的服务质量（Quality of Services，QoS）保证，即为端到端的服务提供高吞吐量、低延时和低错误率等。为了提供QoS保证，人们提出各种方案：改变网络流量结构、增加特定流量的互连带宽或降低其它流量的带宽、提高特定流量的优先级或降低其它流量的优先级、依服务类型进行管理和分配资源、端到端的资源预留、节点控制、整网或局部网络控制、IP组播技术等等。

其中，组播技术是单个发送者对应多个接收者的一种网络通信，它通过向多个接收方传送单信息流方式，可以减少具有多个接收方同时收听或查看相同资源情况下的网络通信流量。IP组播技术有效地解决了单点发送多点接收的问题，实现了IP网络中点到多点的高效数据传送。在组播网络中，即使用户数量成倍增长，主干带宽也不需要随之增加，同样的信息不用重复多次复制发送，大大节约了网络资源、降低了网络负载，从而实现网络资源的高效利用。更重要的是，它可以利用网络的组播特性方便地提供一些新的增值业务，满足用户的多媒体业务需求。

另一方面，Internet工程任务组（Internet Engineering Task Force，IETF）提出的区分服务（differentiated services，DiffServ）模型，具有良好的可扩展性和简单性，成为最有可能在下一代网络（Next Generation Network，NGN）主干中实施的QoS模型。区分服务模型的基本思想是在网络的入口处为数据包标记一个码点（code point），码点用于指示数据包在网络转发路径的中间节点上应该被处理的方式。这样对每个数据包进行的复杂处理被推到了网络边缘，核心网的主要任务只是根据数据包首部的码点对其采用相应的转发措施。

区分服务体系结构提供了一种可扩展的QoS解决方案，从直观上看DiffServ可以满足用户对不同服务质量的需求，而组播传输则提供了一种节约网络资源的有效方法，二者的集成成为必然趋势。但是由于传统的IP组播模型和DiffServ体系结构之间存在着一些基本结构上的冲突，导致二者的集成并不是简单的叠加就可以完成的。在区分服务中实现多播还存在一些问题：如被忽视的预留子树NRS、异构组播组问题、服务类间的公平性、共享树的流量监控等[1]。

综上所述，本文以“区分服务中组播技术”为研究主题，主要研究了以下内容：（1）区分服务中组播技术分析；（2）网络编码技术；（3）区分服务基于网络编码的最大流单源多播路由。

1．区分服务中组播技术分析

在下一代Internet中，越来越多的应用将会需要网络提供一定的服务质量以及进行组播传输；因为区分服务体系结构提供了一种可扩展的QoS 解决方案，而多播传输则提供了一种节约网络资源的有效方法，二者的集成成为必然趋势。

2．1．区分服务中组播技术

随着网络技术与多媒体技术的迅速发展，涌现了大量的实时多媒体应用，它们对网络带宽的需求量比较大，同时对延时、延时抖动等服务质量也有了严格的要求。IETF提出的区分服务模型通过合理利用有限的网络资源来保证用户申请的服务质量，并且以其较好的可扩展性成为了最有可能在下一代网络主干中实施的QoS模型，采用组播传输技术可以实现网络资源的高效利用，因此二者之间的互补结合便成为一个有效的多媒体应用的QoS解决方案。然而，由于基本结构上的冲突，二者的简单集成存在着非预留资源子树（Neglected Reservation Subtree，NRS）、可扩展性、异构性、服务类间的公平性、共享树的流量监控、以及组播路由等问题。

2．2．区分服务中组播路由

DiffServ采用聚合的机制将具有相同特性的若干业务流聚合起来，为整个聚合流提供服务，而不再面向单个业务流。也就是说在DiffServ网络边界路由器上保持每流状态，核心路由器只负责数据包的转发而不保持状态信息。区分服务实质上是在边界路由器将流量按订购级别分类，然后由核心路由器进行存储转发，其属于单播问题。随着多媒体技术的发展，会存在越来越多的由单源节点向多节点发送数据的需求，即某分组在边界路由器被标记服务级别后，在核心域要转发到多个目的结点，但由于区分服务核心路由器只负责数据包的转发而不保持状态信息，因此，区分服务中结合组播技术为网络提供QoS服务存在两个方面的问题：寻找组播路由和如何针对不同的服务需求提供不同的QoS服务。

2．区分服务中基于网络编码的最大流单源组播路由

网络编码是一种能显著提升组播传输性能的通信机制。在组播网络中部署和实施网络编码，必须建立传输路由和确定编码模式。对于后者，许多学者提出了有效的解决方法，而对于路由问题的研究则相对较少。由于网络编码自身固有的特点，基于网络编码的组播传输与传统的IP组播在建立传输路由的方式上有所不同。但结合网络编码技术可以为区分服务中结合组播技术实现QoS服务提供解决方案，鉴于此，本文在这里介绍一种区分服务中基于最大流的网络编码组播路由算法。

2．1．网络编码技术

网络编码（Network Coding，NC）是一种融合编码和路由的信息交换技术。网络编码是信息传输理论研究领域上的最新研究成果，它彻底改变了通信网络中信息处理和传输的方式。其核心思想是在组播通信中允许节点对传输的信息进行操作和处理，而不再限于传统的存储和转发。

网络编码在提高网络吞吐量、改善负载均衡、减小传输延迟、节省节点能耗、增强网络通用性能等方面均显示出其优越性。在组播网络中部署和实现网络系统编码，必须建立传输路由和确定编码模式。[1]在传统存储转发的路由方法基础上，通过允许对接收的多个数据包进行编码信息融合，增加单次传输的信息量，提高网络整体性能。组播网络中的某些节点附加额外的编码操作能使组播源与组播成员间达到最大流最小割的组播速率。网络编码的工作原理是把不同的信息转化成位数更小的“痕迹”，然后在目标节点进行演绎还原，这样就不必反复传输或者复制全部信息了。痕迹可以在多个中间节点间的多条路径上反复传递，然后再被送往最终的目的端点。它不需要额外的容量和路由，只需把信息的痕迹转换成位流即可。

2．2．单播路由和组播路由

2．2．1．单播路由

单播路由是通过路由器将到网络上某一位置的信息从源主机转发到目的主机的传输数据过程。然而在路由路径的选择过程中，路由算法的选择和设计是至关重要的。在路由选择方面的算法很多，下面介绍其中比较有代表性的一种。

Dijkstra算法是一种比较经典的单播路由算法，下面是它的设计基本过程：

（1）路由器建立一张网络图，并且确定源节点和目的节点，在这个例子里我们设为V1和V2。然后路由器建立一个矩阵，称为“邻接矩阵”。在这个矩阵中，各矩阵元素表示权值。例如，[i,j]是节点Vi与Vj之间的链路权值。如果节点Vi与Vj之间没有链路直接相连，它们的权值设为“无穷大”。

（2）路由器为网路中的每一个节点建立一组状态记录。此记录包括三个字段：前序字段——表示当前节点之前的节点。长度字段——表示从源节点到当前节点的权值之和。标号字段——表示节点的状态。每个节点都处于一个状态模式：“永久”或“暂时”。

（3）路由器初始化（所有节点的）状态记录集参数，将它们的长度设为“无穷大”，标号设为“暂时”。

（4）路由器设置一个T节点。例如，如果设V1是源T节点，路由器将V1的标号更改为“永久”。当一个标号更改为“永久”后，它将不再改变。一个T节点仅仅是一个代理而已。

（5）路由器更新与源T节点直接相连的所有暂时性节点的状态记录集。

（6）路由器在所有的暂时性节点中选择距离V1的权值最低的节点。这个节点将是新的T节点。

（7）如果这个节点不是V2（目的节点），路由器则返回到步骤5。

（8）如果节点是V2，路由器则向前回溯，将它的前序节点从状态记录集中提取出来，如此循环，直到提取到V1为止。这个节点列表便是从V1到V2的最佳路由。

2．2．2．组播路由

组播路由就是寻找从源结点到一组目的节点的一棵树，信息沿着此树传送到所有的接收者。成组的组播则是寻找一组树的集合，每一棵树对应一个节点的组播路由。通过组播路由，有组播功能的路由器互相交换多播组成员身份信息，以便通过互连网络作出智能化组播转发决定。实现组播通信的最普遍方法是构造树型路由，这是因为树型路由有以下两个优点：（1）分组以并行方式沿树枝到达不同的接收者；（2）分组的复制仅在分叉处进行，使得网络中所传送的分组数最少。

目前在构建多播树的算法中，主要有泛洪（Flooding）、生成树（Spanning Tree，ST）、最短路径树（Shortest Path Tree,SPT）、最小生成树（Minimum Spanning Tree，MST）、最大带宽树（Maximum Bandwidth Tree，MBT）、反向路径广播（Reverse Path Broadcasting，RPB）、反向路径多播（Reverse Path Multicasting，RPM）和核心树（Core-Based Tree，CBT）等算法。

3．3．基于网络编码的最大流单源组播路由

基于网络编码的最大流单源组播路由采用网络编码技术实现最大流，以提高网络利用效率，其主要是因为单源组播路由问题实际上就是一个发送端对应多个接收端的数据传输路径问题。在参考文献[3]中指出网络编码能够实现的组播最大流等于信源至各信宿之间的最大流的最小值，即h=minf(S,t)，其中f(S,t)为信源S与信宿t∈T之间的最大流。组播的最大流也称为组播的理论传输容量（Multicast Capacity）。在传统基于存储和转发的IP组播中，组播的理论容量往往是无法实现的。但是如果采用合适的线性网络编码（Linear Network Coding，LNC），总能实现组播的最大流。因此，基于网络编码的最大流单源组播路由采用网络编码技术实现最大流。

3．3．1．算法思想

基于网络编码的最大流单源组播路由主要设计目标是在保证网络带宽共享公平性的同时提高资源利用率。其主要设计思想是：（1）找出基于“最大流网络编码算法”的关键节点。（2）对区分服务中不同QoS需求的服务分类，在关键节点处，根据不同的QoS需求确定是否实施编码策略。

从网络编码组播的工作原理可以看出，要实现网络编码组播的最大流，必须保证各信宿节点能够收到h个编码信息T，而且这些编码信息对应的编码向量应该是线性独立的，否则信宿节点无法还原出原始信息。[2]在网络编码组播的传输路径上，存在两类节点：（1）包含一个输入链路的节点，称为路由节点（Routing nodes）；（2）包含多个输入链路的节点，称为关键节点（Key nodes）。在寻找出的路径节点上，执行编码构造算法，如随机网络编码，便构成了实际的网络编码组播通信系统。因为关键节点是指包含多个输入链路的节点，所以关键节点必定是重合链路的端节点，在重合链路的端节点上，如果采用传统存储和转发的路由方法，节点的多个输入信息只能顺序地发送，这样必定会造成信息发送的延迟，降低组播网络的吞吐量或者丢失某些信息。而如果在关键节点使用网络编码，则可将全部的输入信息通过线性组合的方式合并，在信宿节点中通过译码操作加以区分，最终恢复原始的信息，从而实现组播理论容量。

另一方面，在利用网络编码技术解决网络传输效率问题中，并不需要在每一个结点上都要使用网络编码技术，而只需要定义传输路径上的关键。利用算法找出各路径上的关键节点，然后结合区分服务体系组播技术的实现问题，只在关键节点处实现网络编码技术。在已知源节点和目的节点间所有可行路径的前提下，关键是通过计算源和目的间的最短路径获得最短路径通过条数最多的节点。显然这些节点是发生局部拥塞和高负载的最可能的地方。为了避免拥塞的情况发生，就需要控制关键节点上某一时刻的流量分配，从而减轻关键节点的压力。而对于其它的节点，因为这些节点仅含有一条输入链路，编码操作并不能提升网络的性能，这类节点无需执行网络编码操作。所以，当且仅当是关键节点时，才需执行网络编码操作。

3．3．2．算法分析与描述

（1）网络路径的初始化。确认在物理上与之相连的路由器并获得它们的IP地址。将每个路由器视为一个结点，当一个路由器开始工作后，标记各路由器的工作状态。

（2）关键节点的寻找。参考文献[4]中给出了寻找关键节点的方法，即我们可以运用一种基于等位簇的多路径路由算法KNMRA找出基于“最大流网络编码算法”的关键节点。

（3）QoS需求的服务分类。在区分服务中根据不同QoS需求的进行服务分类，找出一种适合于区分服务网络的多播路由算法。

（4）使用一个合适的算法，确定网络中两个节点之间的最佳路由。确定区分服务中组播条件下可实现的最终关键节点。

（5）在最终关键节点处实现网络编码技术。

4．结论

本文在区分服务体系结构下，介绍了一种基于网络编码的最大流单源组播路由算法，分析了该方案的特点，然后说明了该方案的基本设计思想。通过对区分服务中不同QoS需求的服务分类，在关键节点处，实施不同的编码策略，根据不同的QoS需求确定是否实施编码策略，从而实现了基于网络编码的最大流单源组播路由，最终有效地提高了网络数据传输效率。

[1] 高茜，罗军舟．区分服务网络中IP多播:问题与解决方案[J]．计算机研究与发展，2005，42（5）：823-829．

[2] 刘正蓝．QoS研究综述[D]．浙江大学博士学位论文，2004，2[7]：5-24．

[3] 陶少国，黄佳庆，杨宗凯，程文青，Rami S.Youail．基于最大流的网络编码组组播路由算法[J]．计算机科学，2008，35（6）：107-109．

[4] 郭 磊，汪斌强，陈庶樵．一种面向关键节点的多路径路由算法[J]．计算机工程与应用，2008，44（26）：119-121．

[5] 谢希仁．计算机网络(第五版)[M]．电子工业出版社，2007：164-166．

[6] 郭建勇，赵振东，戚银城，李洁．解决IP 服务质量的综合方案及其应用[J]．电力系统通信，2004，（6）：35-42．

[7] 王立梅．支持QoS 的组播策略研究[J]．中国科技信息，2008，5：106-108．

[8] 黄程波，周 杰，张 凌．区分服务网络端到端服务质量保证的组播方案[J]．计算机工程，2006，42，（4）：39-41．

[9] 杨林，郑刚，胡小惠．网络编码的研究进展[J]．计算机研究与发展，2008，45（3）：400-407．

[10] 高茜，万小燕．一种适合于区分服务网络的多播路由算法[J]．计算机应用，2009，29（2）：507-510．

[11] 朱慧玲，杭大明，马正新，曹志刚，李安国．Qos路由选择：问题与解决方法综述[J]．电子学报，2000，（1）：109-116．

[12] 林闯，单志广，盛立杰，吴建平．Internet区分服务及其几个热点问题的研究[J]．计算机学报，2000，23（4）：419-433．

Abstract:In this paper, the author mainly studied that differentiated Internet services quality guarantee systems, and architecture of end to end service quality. Multicast technology and some problems in differentiated services are also analysised. Combined with network coding technology, the largest single-source multicast routing algorithm based on network coding is put forward in this article.

Key words:QOS; differentiated services; multicast; network coding

（责任编辑 王婷婷）

Analysis of Multicast in Differentiated Internet Services

AN Jun
( Department of Physics and Electronic Science, Tongren University, Tongren, Guizhou 554300, China )

TP393.07

A

1673-9639 (2010) 05-0141-04

2010-09-01

安 军（1974-），男，贵州德江人，铜仁学院物理与电子科学系讲师。主要研究：电视视频制作和计算机网络。