Clos网络中的组播路由算法

录入：edatop.com 点击：

1.2Clos网络组播算法介绍

Clos网络中的组播算法性能主要受扇出机制的影响，这样我们就根据扇出策略的不同将组播算法分为以下几种。

输入级扇出算法(IFMA)[7]是基于输入级扇出的算法，其主要思想是通过将一个扇出值为f的组播请求转化成f个单播请求，然后按照单播请求的路由算法进行路由，这样在Clos网络中每个组播请求只在输入级进行扇出，这样可以将组播业务理解为多个相互独立的单播业务，这样就可以利用单播算法中的成熟算法。如图1中的输入端口0到输出端口0、输出端口4和输出端口8的组播业务采用输入级扇出方式，在输入模块IM1中完成所有的扇出，分别经过中间模块CM1、CM2和CM3到不同的目的模块。

Clos网络中的组播路由算法

最迟扇出算法(LFMA)[6] 是基于中间级扇出的算法，该算法的思想是只有在必须进行扇出时才进行扇出，即先在输出级扇出再在中间级扇出。因此对于每一个组播请求只使用一个中间模块，如图1中输入端口2中的请求(2：{1，3，7})，只使用了一个中间模块CM4。

这两种扇出机制都存在着自身的局限性，但是又有很强的互补性，因此将两种扇出相结合的思想就应运而出。在三级Clos网络中，内部阻塞的产生主要是由于级间链路的竞争，如果没有第三级扇出，那么每个组播请求在一个输出模块的每个输出端口都要占用一个从中间级到输出级的链路，否则只需要一个链路。同样，如果中间级没有扇出，那么每一个子请求都要占用一条输入模块到中间模块之间的链路，这样就会出现外部阻塞。各种扇出机制各有优缺点，可以结合使用。在在输入级和输出级同时扇出的机制中又可以根据不同的分配方式分为切分扇出算法及先中间级后输入级算法两种。

切割扇出算法(SFMA)[8]是把目的输出模块进行分组，分组数g为扇出值F 和切割值s 的比值向上取整，然后在进行路由时在第一级就进行扇出，即需要在第二级选择g 个可用的中间交换单元，然后再在第二级和中间级扇出机制一样进行同样的处理。如图1中输入端口3的请求，如果按照切割算法理解的话其扇出值F 为3，切割值s为2，分为两组，一组通过中间模块CM1路由，另一组通过中间模块CM2路由。

最后一种算法是中间级优先扇出算法(CMFFMA)[9-10]，利用尽量少的中间模块完成扇出，即首先选择一个可以建立尽量多扇出的中间单元，建立其到输出模块的连接。如果到全部输出模块的连接均建立完成则路由成功，否则将余下的尚未完成的连接继续按照上一步的方法处理，利用其他中间级单元的扇出能力完成扇出。例如在图1中，由于没有一个中间模块能够满足输入端口3的所有扇出请求，因此通过CM1 建立其中的两条，然后再通过CM2建立剩余的连接。

通过以上对扇出的分析，我们可以得到采用先中间级后输入级算法的扇出机制是最优的。与切割扇出机制相比，它少了盲目性，多了预先检测性，可以在第一级进行有目的扇出；与最迟扇出机制相比，它又有很强的灵活性。

1.3Clos网络组播算法仿真

(1)仿真条件

采用OPNET软件对不同的组播算法进行仿真，仿真中的请求是按照占用-空闲源模式产生，即每个输入端口有占用和空闲两种状态，占用状态表示该输入端口当前存在一个链接，每种状态的持续时间均服从指数分布，如果1/μ表示占用的平均时间，1/λ表示空闲的持续时间，那么在以输入端的状态判断，网络中的负载，如果用f表示组播的平均扇出，Pptp表示业务中单播的比率，那么网络中的实际负载ρ=(Pptp+(1-Pptp)×f)×ρI。每个组播的扇出值按指数分布产生。

2)仿真结果

在具有组播业务的Clos网络中网络的阻塞率主要受组播业务的扇出值、组播比例和中间模块数的影响，下面就分别进行仿真分析。

图2是4种不同的算法在C(16, 16, 16)网络规模、0.8负载以及单播比例为0.5时的阻塞率随扇出值变化的曲线图。

从图2中可以看出随着扇出值的增加阻塞率会有所增加，但是当扇出值达到一定值时，阻塞率将趋于稳定，这是因为在负载固定、输出级有扇出的情况下，随着扇出值的增加请求数量会减少。同时由于输出级具有扇出功能，而输出级的模块数固定，所以当扇出值超出一定值后扇出的目的模块数不会有太多的变化，因此在扇出值大于一定范围后，阻塞则趋于稳定。在这几种算法里CMFFMA的阻塞率最低，因为他的扇出顺序是先输出级、再中间级、最后输入级，这样可以最低限度地节约网络中的链路资源，避免阻塞发生。

图3为C(16,16,16)的Clos网络在负载为0.8时的阻塞率随单播比例变化的仿真结果。

从图3中可以看出随着单播比例的增加IFMA算法、SFMA和LFMA算法的阻塞率单调下降，而CMFFMA算法的阻塞率随着单播比例的变化成抛物线状，这是因为这两种算法适宜于组播请求的建立，能够最大程度的利用已有的空闲资源，因此在单播比例较低时网络的阻塞率比较低，但是随着单播比例的增加阻塞率会逐渐增加，当到达一定的比例时阻塞率又随着单播比例的增加而下降，直到单播比例为1时，以上几种算法的阻塞率均达到一个固定值。

图4为C(16,16,16)规模的Clos网络在0.8的负载，平均扇出值为8时及单播比例为0.5时各种算法的阻塞率随中间模块数的变化曲线。

从图4中可以看出随着中间模块数的增加，不同算法的阻塞率下降的速度不同，其中LFMA算法和IFMA算法的下降最缓慢，其他两种算法的下降速度很快；而且在中间模块数远小于严格无阻塞所需要的中间模块数的情况下，Clos网络的阻塞率可以下降到很低。

从以上分析可知IFMA算法的阻塞率在所有算法中是最高的，这是因为该算法采用输入级扇出，组播业务的扇出均要在输入级实现，这样会造成很高的外部阻塞，而且占用的第一级链路数与第二级链路数相等。

图5为IFMA算法的阻塞率随中间模块数的变化趋势，网络规模为C(16, m, 16)，平均扇出值为8，负载为0.8，全组播业务。

图5中可以看出内部阻塞率较小，故网络的整体阻塞率主要由外部阻塞率决定。

上面分析了在单、组播业务混合的情况下网络的整体阻塞率，但是由于单播和组播业务的不同，其阻塞率不尽相同，图6为不同算法随单播比例变化对组播业务阻塞率的影响。从图6中可以看出随着单播比例的增加，组播业务的阻塞率单调递增。其中，CMFFMA算法的阻塞率最低，这是由于其更好的利用了网络中的空闲链路资源；IFMA算法采用输入级扇出，所以单播比例的增加并没有影响其可用的链路资源的减少，因此阻塞率的增长最慢。