Clos网络中的组播路由算法

摘要：对于三级Clos网络，扇出机制会影响Clos网络的阻塞率、算法的时间复杂度及网络成本，因此选择好的扇出方式能充分发挥网络的组播能力。根据输出级扇出、中间级扇出、输入级扇出等不同的扇出机制分类，可将组播算法分为输入级扇出算法(IFMA)、最迟扇出算法(LFMA)、切割扇出算法(SFMA)、中间级优先扇出算法(CMFFMA)。在对4种算法仿真比较的基础上，文章提出针对不同的业务采用不同的处理方法的路由方案，对于固定扇出业务可采用CMFFMA算法进行路由，针对递增业务采用先输出级、再中间级、最后输入级扇出的策略，可有效地降低阻塞率。

关键词：Clos网络；组播；路由算法；扇出

Abstract:Fan-outmechanismwouldaffect the blocking probability of the three-stage Clos network, the time complexity of the algorithm and network costs. Good fan-out approach can give full play to the multicast capacity of the network. According to the output-stage fan-out, middle-stage fan-out, and input-stage fan-out mechanisms, multicast algorithms include Input Fan-out Multicast Algorithm (IFMA), Lazy Fan-out Multicast Algorithm (LFMA), Split Fan-out Multicast Algorithm (SFMA), and Central Module First Fan-out Multicast Algorithm (CMFFMA). Comparing the analyses of these four algorithms, this article proposes a routing scheme in which different businesses use different algorithms. Bundled traffic can adopt CMFFMA, and incremental traffic can route from output-stage through middle-stage to input-stage fan-out. Therefore, the blocking probability can be effectively reduced.

Keywords:Closnetwork;multicast; routing algorithm; fan out

随着宽带技术的不断发展，视频点播、远程教学、新闻发布、网络电视等业务成为新一轮运营竞争的焦点，它们的特点是，信息由一个服务器向大量的客户端发布。组播技术非常适合这类业务，并具有如下优点：服务器不必知道某个客户端是否存在，它只负责按多播地址将媒体流发送出去，即使有成千上万个客户端，也仅发送一份即可；客户端如果希望接收某媒体流服务器的数据，只需加入该媒体流服务器播放数据使用的组播组即可[1]。

目前智能光网络的发展要求节点设备的交叉矩阵具有容量高、快速的端口配置和组播支持能力，组播业务根据目的节点数的不同，可以分为单播、组播和广播3种类型[2]。单播是指待转发的消息在传送网中要求实现点对点的传输，广播业务是指在传送网中把待转发的一个消息从源节点转发到传送网的全部输出端口上，而组播业务是则把消息转发到传送网中的一组输出端口上。从广义上来讲，单播和广播是组播的一个特例。

根据组播请求的多个目的输出端口的产生时间，可以把组播分为两类[3]：第一类是固定扇出业务，所有的目的输出端口是在请求一开始就确定；第二类是递增业务，它的目的端口递增，是不确定的。

1  Clos网络的组播业务

为了支持网络中的组播业务，网络中的核心设备交换设备也应当具有组播功能。Clos网络自提出以来[4]由于其低成本、易大规模实现，在交换设备中得到了广泛的应用。

图1为一个对称的三级Clos网络，用n表示输入输出模块的端口数量，N表示总的输入端口数，f表示扇出值，m表示中间模块的数量，r表示输入和输出模块的数量，则一个三级Clos网络可以表示为C(n, m, r)。如果用Ip表示输入端口，Pi表示输出端口，那么一个组播请求可表示为(Ip：P1，P2……Pk)。对称的三级Clos网络在任意级有扇出功能的组播严格无阻塞的条件为m≥min{(n -1)f +n,(N -1)f,N }[5]，而且对于任意一个组播严格无阻塞网络，需要的开关数最少为O(N 2)[6]，但是在实际应用中并不需要达到严格无阻塞就可以有很好的性能。

1.1Clos网络扇出机制

对于三级Clos网络，不同的扇出机制不但影响Clos网络的阻塞率，而且影响算法的时间复杂度及网络成本，因此选择好的扇出方式才能充分发挥网络的组播能力。以下将对Clos网络各级扇出的性能特点进行分析。

(1)输出级扇出

输出级扇出指输出级模块具有扇出功能，如果输出级具有扇出功能，那么对于同一个业务源到一个输出模块中的多个输出端口只需要经过一个中间模块，否则有多少输出端口就需要经过多少个中间模块，在三级Clos网络中路由分配主要就是中间级模块的分配，因此必须降低对中间级模块的需求，而第三级扇出可以降低对中间级模块的要求，所以采用第三级扇出可以有效的降低阻塞率，这样我们就可以将一个组播请求由原来的端口表示(Ip：{P1，P2……Pk})转化成模块表示(I：{O1，O2   Ok})，其中I表示输入模块，Oi表示输出模块。

(2)中间级扇出

中间级扇出指中间级的模块具有扇出功能。假如第一级没有扇出功能，那么所有组播分支只能在一个中间级模块进行扇出，因此只有那些满足所有扇出要求的中间交换单元才可以成功建立连接。所以在组播请求的扇出值很大的情况下，网络的阻塞概率将会急剧上升，但是由于只使用一个中间模块，可以避免外部阻塞的发生。

(3)输入级扇出

输入级扇出指输入级模块具有扇出功能，可以从一个输入端口到达不同的中间级模块。如果第三级有扇出的话，那么组播请求要到达几个输出级模块，就需要占用几个中间级模块。对于输入级扇出可以将组播分解成不同的单播请求进行处理，这样可以利用单播中成熟的算法来进行处理，实现简单，而且可以降低内部阻塞率。但是由于每个组播请求只在第一级扇出，因此需要大量的中间模块，容易出现外部阻塞问题。

作者：石增增 顾华玺 王长山   来源：通信世界网