一种以缓解HOL Blocking为目标的动态组播入队算法

摘要

本发明公布了一种以缓解HOL Blocking为目标的动态组播入队算法，该发明属于CICQ结构分组交换机中单组播混合业务下的分组调度技术领域。本发明的目的是缓解CICQ交换机下分组调度中的组播HOLBlocking问题。本发明首先划分了两种类型的HOL Blocking，分别为基于传输需求的HOL Blocking和基于Work‑Conserving的HOL Blocking。根据到达组播分组去向与当前CICQ交换机交叉缓存状态之间的关系，首先考虑基于Work‑Conserving的HOL Blocking，其次考虑基于传输需求的HOL Blocking，提出了新的组播入队方案MDA算法。与典型的组播入队算法比较，本发明提供的算法具有更低的平均分组时延。

主权项

一种以缓解HOL Blocking为目标的动态组播入队算法Vector算法是一种已有的组播入队方案，其算法过程为：从N维向量空间定义k个特征向量v₁,v₂,…,v_k分别对应k个组播队列，每个特征向量的每个元素的值为0或1，且每两个特征向量相互正交；对于到达的组播分组，按照其去向定义去向向量D_a；若到该分组去向包含输出端口j，则D_a[j]＝1,否则D_a[j]＝0。在v₁,v₂,…,v_k中找出与D_a距离最短的特征向量，则到达分组进入该特征向量对应的组播队列；本发明提供一种以缓解HOL Blocking为目标的动态组播入队算法，其特征是：当输入端口i有组播分组到达时，按如下步骤选择组播虚拟队列入队：第1步计算输入端口i当前最短组播队列的长度；第2步若最短组播队列长度大于1，则按照Vector算法入队；否则进入第3步；第3步若到达分组去往的某个输出端口对应的交叉缓存最多有一个非空，该分组进入输入端口i中队列长度最短的组播队列，若存在多个长度相同的最短队列，选择头分组权重最大的队列入队，头分组权重计算方法为：0.5×该分组到达交换机时扇出数的平方/该分组当前扇出数×该组播分组等待时间；否则，进入第4步；第4步若输入调度完成后输入端口i有分组可以在下一时隙传输到交叉缓存，该分组采用与第3步相同的方法进入队列长度最短的组播队列；否则按照Vector算法入队。