一种基于复色的并行交换调度方法

摘要

本发明针对大规模高速交换网络中的业务调度问题，公开了一种基于复色的并行交换调度方法，采用批量调度的方式，引入复色的概念，利用复色最优、分布式以及可并行化的特点，在无需知道交换网络全局信息的前提下，完成对交换系统的业务调度，快速而有效地得到最优的调度方案，使得交换网络中的带宽得到最大化的利用，获得接近100％的吞吐能力。该算法的计算复杂度为O(log²N)。

主权项

一种基于复色的并行交换调度方法，其特征在于：该方法包括如下步骤：步骤1，N×N交换网络，N个输入端口和N个输出端口，每个输入端口均存在输入缓存队列，在每个时隙每个输入端口最多只能发送一个数据信元，同时每个输出端口最多只能接收一个数据信元，一个时隙周期f为一帧，根据第k个帧的数据信元信息，将N×N的交换网络抽象对应为二分图的数学模型G_k＝(V∪U,E)，其中，顶点v_i∈V表示输入端口i，顶点u_j∈U表示输出端口j，边e_m(v_i,u_j)∈E表示从输入端口i去往输出端口j的第m个数据信元，i,j＝1,2,…,N，将需要调度的发送时隙抽象对应为颜色集C＝{c₁,c₂,…,c_Δ}，其中Δ为所有顶点的最大顶点度；步骤2，将二分图中所有的边e_m(v_i,u_j)∈E分裂成一对链结，再由各自相连的顶点对其分别着色，保证每个顶点所相连的链结都是不同颜色；通过在顶点上执行链结颜色交换操作，最终得到一个着色方案，使得满足同一条边上的两条链结的颜色是相同的且连接同一顶点的所有边的颜色是不同的两个要求；步骤3，数据信元的传输：根据步骤2得到的着色方案，按照颜色所对应的时隙，依次建立对应输入输出端口的通信信道，发送相应数据包。