多点通信的路由问题

多媒体技术的发展导致了大量新业务的涌现，而最近在带宽和处理能力上的进展更为会议电视、分布式处理等多点通信业务提供了技术支持。点到点通信作为当前通信的主要形式，将难以适应以视听多媒体业务为核心的业务发展，而多点通信（ＭＣ）将成为下一代通信的主要业务形式。在这一点上，基于Ｉｎｔｅｒｎｅｔ发展起来的美国Ｍｂｏｎｅ网已经走在了前面。最近发展起来的广域网技术，如ＳＭＤＳ与ＡＴＭ也已明确了多点通信将作为网络承载业务的一部分。

     多点通信简单地说，就是点到多点的通信形式，即多个信宿同时接收一个信源发送的相同信息，这是网络中大量业务存在点到多点通信需求的必然结果。从传送方式看，点到点方式是一对一，广播方式是将分组发向所有可能的成员，而多点通信则是将一个分组发向成员中的某个子集，可以视为点到点方式和广播方式的综合，另一方面也可以将点到点方式和广播方式看作是多点通信的特殊情况。

     在传统的点到点网络支持能力下，多点间通过分别寻址，在信源和每一个信宿间分别建立最短路由，分别复制和发送数据，从而实现多点通信，这种方法导致网络中传送大量不必要分组，浪费了网络资源，增大了分组时延。由于在过去只有很少的网络应用涉及多个用户，而且多数应用中带宽要求较小，因此在上述简单的ＭＣ寻址方式条件下，网络带宽尚能满足要求。随着多媒体实时应用业务的出现，分组的规模、业务的特征和服务质量要求都发生了巨大的变化，为此有必要寻求网络层对多点通信能力的支持，在新的路由算法下满足实时应用的要求。

１ 多点通信路由算法

１．１ 路由算法的优化准则

     实现ＭＣ路由最普遍的方法是构造树型路由结构，在树上实现有效ＭＣ路由有两个原因：（１）数据以并行方式沿着树枝发送到不同的信宿；（２）需要传送的复制分组最少，而且复制只在树杈处进行。

    在确定树的ＭＣ路由算法中，可以采用不同的优化准则。一个目标是提供端到端最小延迟，这对于实时会议等多媒体应用来说是至关重要的；另一个优化目标是尽可能有效地利用网络资源，这个目标包括两个方面：（１）总的链路占用带宽最小；（２）链路带宽的占用尽可能分散，以避免链路拥塞。

     一个有效路由算法的目标是构造一棵覆盖组成员的树。下面在树的模型下，结合不同优化准则对各种路由算法进行分析和比较。

１．２ 多点通信的路由算法

１．２．１ 多点通信路由算法的分类

      一般来说，多点树可以分为两类：（１）最短路径树（ＳＰＴ），即以单个信源为根，其它信宿作为树叶或中间节点，通过建立信源与每一个信宿之间的最短路径，然后合并共享路径而成。从理论上讲，采用ＳＰＴ，业务将分散到不同的链路，利于网络业务流量均衡。（２）共享树（ＳＴ），每一组中只有一棵树，供同组中多个信源共同使用，这棵树覆盖所有组成员，因此可以实现多点到多点通信。显然，构造ＳＴ有多种方式，后面将分别介绍。

１．２．２ 多点通信的几种基本路由算法

１．２．２．１ 最短路径树算法

     构造最短路径树存在多种算法，目前在Ｉｎｔｅｒｎｅｔ上常用的算法有以下两种。

（１）反向路径正向发送（ＲＰＦ）

     ＲＰＦ是已经在ＩＰ多点通信中广泛应用的一种路由算法，算法如下：当节点接收到一个分组之后，检查接收到分组的端口是否是该节点到分组信源最短路由的端口。若是，则该节点向除该端口之外的所有端转发此分组；否则，抛弃分组。ＲＰＦ假定信道是对称的，按照最小延迟原则构造一棵生成树。

     由于ＲＰＦ属于广播算法，为了使它适应组通信，进行了两点改进：根据信源建立路由器与链路的“父子”关系，只有父路由器能向子链路发送该信源的分组，以消除同一链路上的重复分组问题；从树上“剪掉”下行链路不存在接收节点的路由器，消除由于ＲＰＦ的广播特性使特定组业务对与该组无关的路由器和子网产生的影响。ＲＰＦ是一种快速分布式动态算法，易于实现，但应用于非对称链路网络时性能较差，因此不适用于广域网以及组员稀疏的情况。

（２）Ｄｉｊｋｓｔｒａ算法

     Ｄｉｊｋｓｔｒａ算法的基本想法是每一次将距离信源最近的节点加入到树上，构造一棵生成树，然后将非成员树叶删除。该算法要求信源具备所有信宿的地址信息。Ｄｉｊｋｓｔｒａ算法实现简单，但集中执行，需要全网拓扑信息，耗时长，大量信源同时发送数据时ＣＰＵ负载较重。

１．２．２．２ 共享树的实现 ——中心树（ＣＢＴ）

     ＣＢＴ是一种典型的共享树，是一棵以所有接收节点的拓扑中心为根的优化树，可以由所有发送节点共享。它是在树的特性与实现复杂程度这一对矛盾间取得的折衷。ＣＢＴ不具有广播特性，只有某个节点明确发出加入某个组的请求后，该组ＭＣ数据才发向该节点，避免了ＲＰＦ类型算法在广域网上运行时，大量无效分组扩散，适用于接收者分布稀疏的情况。

     ＣＢＴ树的构造过程包括：

（１）选定一个固定点作为组的中心。如果需要满足更好的容错或延迟性能，可以同时选择多个中心，其它组成员通过最短路由与中心建立连接，构成一棵以中心为根的树；

（２）若某节点想成为组成员，则向中心发送加入消息；

（３）组外成员向组内成员发送ＭＣ分组时，先按照最短路由将分组发向树的中心，直到分组到达树上的某个路由器，然后再按照组内分组处理和传送，因此ＣＢＴ满足了组外成员与组内成员通信要求。

     如何为ＣＢＴ选择一个最优的中心是一个ＮＰＣ问题，一种简单的算法是在接收成员之间选择中心。ＣＢＴ的另一个问题是中心失败将导致树的分裂，解决的算法参见参考文献２。

ＣＢＴ与ＳＰＴ性能的分析和比较如下：

.当选择组成员之一为中心时，ＣＢＴ延迟比ＳＰＴ略大，而树的代价比ＳＰＴ略小；

.总的来说，若一个组中有大量成员，而每个成员的数据发送速率较低时，ＣＢＴ可以取得较好的性能，而ＳＰＴ则更适合于高速信源的情况；

.在ＣＢＴ中节点需要保存的状态信息较少；

.在流量集中问题上，ＣＢＴ的性能明显比ＳＰＴ差；

.ＳＰＴ的路由表规模是ＣＢＴ的Ｎ倍，Ｎ是组中发送节点数量。

１．２．３ 网络中的Ｓｔｅｉｎｅｒ问题（ＳＰＮ）

     Ｓｔｅｉｎｅｒ问题是指在无向图中，参照网络的边上所定义的代价，在总代价最小的约束下，寻找一个树来覆盖组的所有成员。ＳＰＮ属于图论中的ＮＰＣ问题，即最优算法无法在多项式时间内完成，因此，在路由问题上，一种普遍的寻径策略是寻找实际性能较优的树而非最优树，目的是降低算法难度，而在性能上又逼近理想算法。启发式算法有很多，由于构造最小生成树（ＭＳＴ）相对简单，因此许多算法是将ＳＰＮ问题降低为ＭＳＴ进行的，其中ＫＭＢ算法因简捷有效而著名。２ 多点通信路由协议

      实际应用中的ＭＣ路由协议有ＤＶＭＲＰ、ＭＯＳＰＦ、ＰＩＭ等，其中ＤＶＭＲＰ和ＭＯＳＰＦ是由Ｉｎｔｅｒｎｅｔ上的点到点路由协议——路由选择信息协议（ＲＩＰ）与开放式最短路径优先（ＯＳＰＦ）派生出来的，用于构造ＳＰＴ；ＰＩＭ协议则将ＳＰＴ、共享树结合起来。

２．１ 距离向量ＭＣ路由协议（ＤＶＭＲＰ）

     ＤＶＭＲＰ是Ｍｂｏｎｅ上广泛运用的多点路由协议，它是ＲＩＰ的扩展。两者都采用距离向量算法，不同的是：ＲＩＰ直接根据指向信宿的路由表前向发送数据，而ＤＶＭＲＰ则采用ＲＰＦ算法实现数据的转发。此外，在Ｍｂｏｎｅ上采用了隧道技术，使多点通信得以在支持ＭＣ的子网岛之间实现。

     ＤＶＭＲＰ中存在的问题是大量路由控制分组定期在网络中的扩散。由于Ｍｂｏｎｅ的飞速发展，这种开销限制了网络规模的发展。而分层ＤＶＭＲＰ按照区域分割的方式对Ｍｂｏｎｅ进行多层管理，区域之内ＭＣ可以按照任何协议进行，区域之间ＭＣ由边界路由器在ＤＶＭ-ＲＰ协议下进行。由于采用ＭＣ协议的层次叠加，减少了路由控制信息开销。

２．２ ＭＣ开放式最短路径优先（ＭＯＳＰＦ）

     ＭＯＳＰＦ是利用点到点的链路状态数据库，以ＯＳＰＦ Ｖ２为基础的ＭＣ路由协议。由于ＯＳＰＦ应用Ｄｉｊｋｓｔｒａ算法进行路由选择，因此每个节点都要保存全网的拓扑信息。所有节点对全网的看法是一致的，因而不需要发送任何控制分组，节点就可以根据全网链路状态表计算组中每个信源的ＳＰＴ，因此，链路利用率比ＤＶＭＲＰ高。为了减少计算量，ＭＯＳＰＦ可以按需执行算法，缺点是对第一个分组带来较大时延。

     以上ＭＣ协议都依赖于点到点路由协议，无法适应广域互联网间多点通信，并且定期扩散大量路由控制信息，限制了组的规模。

２．３ 独立于点到点协议的多点通信（ＰＩＭ）

     ＰＩＭ的出发点是在广域网范围内同时支持共享树与ＳＰＴ，并能够完成两者之间的灵活转换，因而集中了两者的优点又同时避免了它们的缺点，在组员密集时以广播形式传送数据，然后删除不存在接收节点的分支；而当组员分布稀疏时，构造共享树传送，避免分组的广播开销。ＰＩＭ有两种模式：稀疏模式（ＳＭ）和密集模式（ＤＭ）。

     ＰＩＭ－ＤＭ的含义是，在组所覆盖的区域中，具有该组成员的子网数量在子网总数中占有很高的比例。ＰＩＭ－ＤＭ基本上与ＤＶＭＲＰ相同，属于数据驱动型协议，路由算法构成ＳＰＴ，但协议只是直接使用点到点路由算法给出的路由表发送数据，因而独立于点到点协议。

     ＰＩＭ－ＳＭ的含义是：（１）拥有组成员的子网数量远远小于Ｉｎｔｅｒ-ｎｅｔ中网络数量；（２）组所覆盖的网络资源不足。在ＰＩＭ－ＳＭ模式中，接收节点通过向指定点（ＲＰｓ）发送明确的加入消息加入组中，数据发送节点通过ＲＰｓ公布自身的存在，而接收节点通过ＲＰｓ获知新的发送节点的存在，然后数据在以ＲＰｓ为根的共享树中流动。

     ＰＩＭ－ＳＭ与ＣＢＴ的区别在于它可以从共享树向ＳＰＴ转变。这种转变是由接收者申请与发送节点建立最短路由完成的。对于ＰＩＭ，需要考虑的问题包括：ＳＭ／ＤＭ在广域网上的协同工作、ＲＰｓ的选择、ＳＴ与ＳＰＴ之间转化的准则。

     总的来说，ＤＶＭＲＰ、ＰＩＭ与ＣＢＴ适用于Ｉｎｔｅｒｎｅｔ上数据报的应用环境。在一个会话过程中，ＭＣ分组的路由可能发生变化，此时算法的简捷性比树的代价更重要；另一方面，基于Ｓｔｅｉｎｅｒ树的启发式算法更适合于ＡＴＭ的虚电路环境，这种情况下优化树的代价更具有吸引力。

２．４ ＡＴＭ网络条件下对多点路由的支持协议

     当前ＡＴＭ标准尚未对组地址进行规范，信源必须知道所有组成员的地址，建立点到多点虚通道（ＶＣ），成员的加入和离开也由信源管理，因而点到多点ＶＣ不能提供对大多数组通信的灵活支持。

     ＡＴＭ论坛给出了两种支持ＭＣ的建议模式：ＶＣ网格（ＶＣ ｍｅｓｈ）模式是建立从信源到组中所有成员的点到多点ＶＣ，如果发生成员的加入和离开，则更新ＶＣ；ＭＣ服务器（ＭＣＳ）模式指选择一个服务器作为中介，组内每个信源与ＭＣＳ建立点到点ＶＣ连接，由ＭＣＳ向一个组中的所有信宿建立点到多点ＶＣ。ＭＣＳ接收组中所有信源的数据，交织之后发送到相应点到多点ＶＣ上。交织产生的不同信源的分组区分问题可以使用适配层信息解决。ＶＣ网格的通量性能比ＭＣＳ好，延迟小，但ＭＣＳ更适合于对组成员的动态控制管理。

      另外一种模式ＳＭＡＲＴ采用了共享ＡＴＭ多点树，该协议通过对组业务支持一至多个ＡＴＭ虚通道连接（ＶＣＣ），构造多点树实现多点到多点通信，组成员间通过循环方式控制成员对ＶＣＣ的接入，保证同一时刻只有一个信源向一个ＶＣＣ发送数据，因此不存在数据交织，缺点是需要交换和终端节点同时参与数据传送控制。

３ 多点通信在Ｉｎｔｅｒｎｅｔ上 的应用

３．１ Ｉｎｔｅｒｎｅｔ子网内多点通信的支持方式

     多点通信组地址即ＩＰ地址空间的Ｄ类部分，地址范围为：２２４～２３９．Ｘ．Ｘ．Ｘ，其中Ｘ可以选择０～２５５之间的任意数字，２２４．０．０．Ｘ保留作路由和其他低层协议使用。每一个组都有一个唯一的组地址。全部组地址分为两类：一类是永久地址，一般只用作信令管理；另一类是暂时性地址，它的数量与可能的组数量相比只占很小的比例，因此，需要对组地址采用复用技术，应用进程开始时选择一个空闲的组地址，而进程结束之后将地址放回。这要求采用一个对用户透明的动态组地址分配和释放机制来避免可能发生的地址冲突。Ｉｎｔｅｒｎｅｔ没有严格规定组地址的分配方式，对于通信局限在本地网中的情况，不同网络中的组地址可以相同；对于跨越不同物理网络的组地址，最好的方式是中央管理，统一分配。

     为加入跨越物理网络的多点通信，主机必须事先通知本地多点通信网关有关自己加入组的情况，然后各网关再互相交换各自的组信息，以建立多点通信路由。ＭＣ网关与参与多点通信的主机之间交换组员信息的协议为网间网组管理协议（ＩＧＭＰ）。网关通过ＩＧＭＰ实现组查询／报告机制：ＩＰ主机使用ＩＧＭＰ向直接相连的ＭＣ网关报告自身加入组的情况。

３．２ Ｉｎｔｅｒｎｅｔ中的多点路由协议

    如前所述，ＤＶＭＲＰ是Ｍｂｏｎｅ上广泛运用的多点路由协议。根据ＤＶＭＲＰ协议，ＭＣ网关之间互通组成员状态信息，以及网关之间路径的开销。对每一个组，ＭＣ网关都在物理连接图的基础上构成一棵树，根据这棵树进行多点通信。ＤＶＭＲＰ利用ＩＧＭＰ报文传送路径信息，但加入了新的报文类型，允许ＭＣ网关像主机一样，参与组员状态信息交换。主机并不参与ＤＶＭＲＰ协议。一个ＭＣ网关宣布其属于某个组，意味着其所在的子网上至少有一个主机参与了该组。另外，在ＭＣ网关之间交换的信息中，还包含描述寻径信息（包括路径开销和距离制式）的报文。

３．３ ＭＣ在Ｍｂｏｎｅ网上的应用

     当前ＭＣ应用最广泛的增长是在Ｍｂｏｎｅ网上的应用。Ｍｂｏｎｅ网创建于１９９２年，到１９９５年已经发展到２５００个子网，其发展速度是惊人的。Ｍｂｏｎｅ是运行在Ｉｎｔｅｒｎｅｔ之上的一个虚网络，由支持ＭＣ路由功能的路由器和支持ＭＣ能力的网络（子网岛）组成的ＭＣ骨干网。在每一个岛上，有一个支持ＭＣ的主机，这些主机通过点到点的隧道相互连接，采用ＤＶＭＲＰ协议实现数据的多点发送，从而实现子网岛之间的多点通信。路由协议的进一步改进是采用等级ＤＶＭ-ＲＰ。为了提高效率，Ｍｂｏｎｅ在传输层采用ＵＤＰ协议。ＭＣ在Ｍｂｏｎｅ上的实际应用包括主机上提供的实时视听会议、软件刷新的传播、股票信息发布等多种业务。

４ 多点多媒体通信对路由提出的新问题

     多点业务采用树型结构路由的主要动机是通过链路共享以使传送代价最小，对于高速业务，这一目标尤为重要。但在实时多媒体业务中，带宽和延迟要求以及媒体异质性使得路由实现更为复杂。下面根据多媒体业务的需求，结合业务特性分析路由算法的几个发展方向。

４．１ 在线ＭＣ问题

     在线ＭＣ问题是指在成员的加入和离开之后的ＭＣ树更新问题。随着组成员的动态变更，原有树的性能会逐渐恶化。解决在线ＭＣ问题有两种方法：

（１）成员变更之后，对整个组重新确定路由，这将对组中原有成员间的通信产生干扰。当组动态快速变化时，该方法是不实用的，改进的方法是对树进行局部优化。

（２）成员变化之后对树采取最小的变化。如有一种ＧＲＥＥＤＹ算法，成员的加入通过建立节点到树的最短路由完成；成员离开时仅删除相应的叶节点。如果产生一个非成员树叶，则删除该节点，直到不存在非成员树叶。

４．２ 有界Ｓｔｅｉｎｅｒ算法

     有界Ｓｔｅｉｎｅｒ算法是指在限制了某些参数（如时延）范围的情况下，寻找代价最小的树。在很多情况下，适用于交互式多媒体业务的优良ＭＣ路由难以单独用延迟或代价参数刻画，如在满足媒体间松散同步条件下使代价最小，这种多点路由的性能就由两个因素决定：（１）信源到每一个信宿路径上的端到端延迟有界；（２）多点树的代价最小。为了满足各种不同业务的ＱＯＳ要求，探讨有界Ｓｔｅｉｎｅｒ算法将是多点路由适用于多媒体业务发展的一个重要方向。

４．３ 适应多媒体业务流的异质性及编码算法的多点路由算法

     多媒体业务采用了各种编码技术，因此可以应用适当的路由算法，在保证业务质量的同时，提高网络资源的应用效率，比如：图像编码一般采用了分层编码技术，分辨率不同的图像成分包含在不同的帧中，因此可以在终端视频质量要求不同的情况下，将低分辨率分组发送到所有组成员，而高分辨率分组只向需要的节点发送。路由算法首先为高能力终端构造一棵优化分布树，然后将需要低品质图像的节点嫁接到树上，这样网络资源的利用效率更高。

     对于多媒体业务，信源存在多个媒体流。由于不同媒体流ＱＯＳ要求不同，因此可以对不同媒体流构造不同的ＳＰＴ以满足各自媒体的性能要求；通过对不同树的分别管理，能够有效利用资源，保证业务质量，并可以优化链路负载特性，简化接入控制，但如何选路以达到各树之间的平衡是有待研究的问题。

５ 结论

     多点树的构造是网络支持多媒体业务的必要组成部分，ＭＣ路由是进行网络资源管理，满足应用ＱＯＳ要求的有效工具。优良的路由算法通过减少连接代价，达到充分利用网络资源的目的。

     由于下层网络的异质性，各种路由算法和协议的实现，尤其在广域网上的实现存在很大的困难，同时ＡＴＭ很可能作为将来Ｉｎｔｅｒｎｅｔ的底层承载网络，因此如何在ＡＴＭ网上实现ＭＣ也是一个需要探讨的领域。总之，多点通信是多媒体通信发展的一个重要方向，在网络层实现多点通信存在多方面的问题需要更深层次的研究。

参考文献

１ Ｃｈｒｉｓｔｏｐｈｅ Ｄｉｏｔ，ｅｔ ａｌ． Ｍｕｌｔｉｐｏｉｎｔ Ｃｏｍｍｕｎｉｃａｔｉｏｎ：Ａ Ｓｕｒｖｅｒｙ ｏｆ Ｐｒｏｔｏｃｏｌｓ，Ｆｕｎｃｔｉｏｎｓ，ａｎｄ Ｍｅｃｈａｎｉｓｍｓ．ＩＥＥＥ Ｊ ｏｎ Ｓｅｌ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎ ，Ａｐｒｉｌ １９９７，１５（３）：２７７～２９０

２ Ｄ Ｇ Ｔｈａｌｅｒ，ｅｔ ａｌ．Ｄｉｓｔｒｉｂｕｔｅｄ Ｃｅｎｔｅｒ－Ｌｏｃａｔｉｏｎ Ａｌｇｏ-ｒｉｔｈｍｓ．ＩＥＥＥ Ｊ ｏｎ Ｓｅｌ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎ，Ａｐｒ １９９７，１５（３）：２９１～３０３

３ Ｐ Ｗｉｎｔｅｒ．Ｓｔｅｉｎｅｒ ｐｒｏｂｌｅｍ ｉｎ ｎｅｔｗｏｒｋｓ：Ａ ｓｕｒｖｅｙ．ＩＥＥＥ Ｎｅｔｗｏｒｋｓ，１９８７，１７（２）：１２９～１６７

４ Ｓ Ｄｅｅｒｉｎｇ，Ｃ Ｐａｒｔｉｄｇｅ，ａｎｄ Ｄ Ｗａｉｔｚｍａｎ．Ｄｉｓｔａｎｃｅ Ｖｅｃｔｏｒ ＭＣ Ｒｏｕｔｉｎｇ Ｐｒｏｔｏｃｏｌ，ＲＦＣ １０７５，Ｎｏｖ  １９８８

５ ＡＴＭ ｕｓｅｒ－ｎｅｔｗｏｒｋ ｉｎｔｅｒｆａｃｅ ｖｅｒｓｉｏｎ ３．１ ｓｐｅｃｉｆｉｃａ-ｔｉｏｎ．ＡＴＭ Ｆｏｒｕｍ，１９９４

６ Ｂｅｒｎａｒｄ Ｍ Ｗａｘｍａｎ．Ｒｏｕｔｉｎｇ ｏｆ ｍｕｌｔｉｐｏｉｎｔ ｃｏｎｎｅｃ-ｔｉｏｎｓ．ＩＥＥＥ Ｊ ｏｎ Ｓｅｌ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎ，Ｄｅｃ １９８８，６（９）：１６１７～１６２２

（收稿日期：１９９８－０５－０８）

[摘要] 多点通信是网络支持多媒体业务的关键技术之一。文章在讨论多点通信路由算法的基础上，分析了几种实际应用的路由协议。之后介绍了多点通信在Ｉｎ-ｔｅｒｎｅｔ上的应用，并结合多媒体业务的发展指出了路由算法的几个发展方向。

[关键词] 多点通信 路由 最短路径树 共享树

[Abstract] Ｍｕｌｔｉｐｏｉｎｔ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｉｓ ｂｅｃｏｍｉｎｇ ａ ｋｅｙ ｒｅｑｕｉｒｅｍｅｎｔ ｏｆ ｎｅｔｗｏｒｋｓ ｓｕｐｐｏｒｔｉｎｇ ｍｕｌｔｉｍｅｄｉａ ａｐｐｌｉｃａｔｉｏｎｓ．Ｃｏｎｓｉｄｅｒｉｎｇ ｄｉｆｆｅｒｅｎｔ ｃｒｉｔｅｒｉａ，ＭＣ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ａｎａｌｙｚｅｄ，ａｎｄ ｓｅｖｅｒａｌ ｐｒｏｔｏ-ｃｏｌｓ ｉｎ ｐｒａｃｔｉｃｅ ａｒｅ ｇｉｖｅｎ．Ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ＭＣ ｉｎ Ｉｎｔｅｒｎｅｔ ｉｓ ａｌｓｏ ｉｎｔｒｏｄｕｃｅｄ．Ｆｉｎａｌｌｙ，ｂａｓｅｄ ｏｎ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｍｕｌｔｉｍｅｄｉａ ｓｅｒｖｉｃｅ，ｓｅｖｅｒａｌ ｄｅｖｅｌｏｐｍｅｎｔｓ ｏｆ ＭＣ ａｌｇｏｒｉｔｈｍ ａｒｅ ａｎａｌｙｚｅｄ．

[Keywords] Ｍｕｌｔｉｃａｓｔ Ｒｏｕｔｅ ＳＰＴ ＳＴ