一种基于Clos网络交换结构的贯序匹配调度算法

摘要

一种基于Clos网络交换结构的贯序匹配调度算法，涉及网络交换调度算法领域。其步骤为：步骤1：输入模块的m个输出端口向每个中间模块的相应的输出端口发出请求消息，步骤2：每个中间模块的输出端口选定一个发出请求消息的虚拟输出组并向其发出允许消息，步骤3：每个中间模块的输入端口选定一个该中间模块的输出端口并放行该输出端口发出的允许消息，步骤4：完成从虚拟输出队列到输出端口的通道建立过程，步骤5：发送信元并更新指针，重复执行步骤4、步骤5直至所有信元都被发送或者所有的允许消息都已被接受。本发明所述的调度算法采用直通式匹配，整个匹配过程一次完成，同时采取多对多的“请求－允许－接受”方式，最大程度利用了调度机会。

主权项

1.一种基于Clos网络交换结构的贯序匹配调度算法，所说的Clos网络交换结构至少包括一个交换机机架及设置在机架上的线卡和背板，每个线卡上的前端芯片包括k个输入模块IM和k个输出模块OM，背板上的后端芯片包括m个中间模块CM，每个输入模块IM均具有m个输出端口，每个中间模块CM均具有k个输入端口和k个输出端口，其特征在于：所说的贯序匹配调度算法步骤为：步骤1：请求阶段，每个包含非空虚拟输出队列VOQ的虚拟输出组VOG，根据信元最终要送达的输出模块OM，通过其所在的输入模块IM的m个输出端口向每个中间模块CM的相应的输出端口发出请求消息，步骤2：允许阶段，每个中间模块CM的输出端口根据输出端口指针LoC Pointer的位置选定一个发出请求消息的虚拟输出组VOG并向其发出允许消息，步骤3：过滤阶段，判断是否发生通行竞争，如没有则直接放行相应输出端口发出的允许消息，如发生通行竞争，则每个中间模块CM的输入端口根据输入端口指针LiC Pointer的位置选定一个该中间模块CM的输出端口并放行该输出端口发出的允许消息，步骤4：接受阶段，每个收到允许消息的虚拟输出组VOG，通过VOG内部指针VOGInnerPointer选定一个非空虚拟输出队列VOQ，再根据VOG外部指针VOGExternPointer的位置选定一个发出允许消息的中间模块CM的输出端口，虚拟输出组VOG向该输出端口发送接受消息以完成从虚拟输出队列VOQ到该输出端口的通道建立过程，步骤5：指针更新阶段，非空虚拟输出队列VOQ通过虚拟输出组VOG发送一个信元，依次更新VOG内部指针VOGInnerPointer、VOG外部指针VOGExternPointer、中间模块CM的输入端口指针LiCPointer和中间模块CM的输出端口指针LoCPointer，重复步骤4、步骤5直至所有非空虚拟输出队列VOQ的信元都被发送或者所有的允许消息都已被接受。