快速光交换条件下的时隙分配方法

摘要

本发明公开了一种快速光交换条件下的时隙分配方法，主要解决现有云计算数据中心快速光交换的时隙分配计算复杂度高的问题。其实现步骤为：1)通过控制器网络的流量需求，得到流量矩阵；2)利用流量矩阵求出基本状态B₀和可用状态集S；3)使用可用状态集S对应的有限种交换机的状态，对流量矩阵A进行分解，并求出各交换机状态的持续时间；4)流量矩阵分解完成后，输出交换机状态和持续时间。本发明降低了快速光交换条件下时隙分配的计算复杂度，提高了链路利用率，可用于在光电混合和全光数据中心对时隙的分配。

主权项

一种快速光交换条件下的时隙分配方法，包括：1)通过控制器与n个架顶交换机ToR之间进行通信，得到网络的流量需求用a_i,j其中i和j的取值范围均为1,2,...,n；2)根据网络的流量需求a_i,j得到n阶流量矩阵A；3)根据流量矩阵A计算得到交换机的基本状态B₀和该基本状态B₀的可用状态集S：3a)按字典序搜索流量矩阵A的最大流量，若流量矩阵A中有多个位置流量值相等且最大，则选择最后搜索到的位置作为最大流量，并对该位置赋值为1，对该位置对应行和列的其余位置都赋值为0；3b)重复3a)，直到把流量矩阵A变成一个初始的置换矩阵K₀，K₀即为A对应的交换机的基本状态B₀；3c)对初始的置换矩阵K₀进行一次行变换或列变换，依次得到个变换后的置换矩阵K₁,K₂,...,K_n(n‑1)/2，变换后的置换矩阵K₁,K₂,...,K_n(n‑1)/2和初始的置换矩阵K₀一起构成的集合即基本状态B₀对应的可用状态集S；4)利用可用状态集S对流量矩阵A进行分解；4a)创建二维数组C，使得C的每一行C₀,C₁,...,C_n(n‑1)/2分别表示一种交换机的状态，用c_k,t表示C中第k行第t列的数值，即c_k,t＝r表示交换机的第k‑1种状态B_k‑1的第t行第r列的位置为1，B_k‑1的第t行其余位置为0；4b)对于流量矩阵A，用a_i,j表示流量矩阵A中第i行第j列的流量值，对C的第一行C₁进行初始化，并用C₁表示交换机的基本状态B₀，按从左至右的顺序搜索C的第一行C₁，找到C₁中数值等于j的位置，记该位置为第一行的第t₀列，即c_1,t0的值等于j；4c)确定交换机的状态，初始化计数器count等于1，对C的第count+1行C_count+1初始化，使其等于C的第一行C₁，然后将C中第count+1行第j列的数值c_count+1,j和第count+1行第t₀列的数值互换，得到C的第count+1行C_count+1，即对应于交换机状态B_count；4d)求解交换机状态B_count的持续时间，用一个长度为n的一维数组G来存储持续时间，一维数组G中第i位置的数值用g_i表示，即g_i表示交换机状态B_i的持续时间；4e)根据流量矩阵A中第i行第j列的流量a_i,j和流量矩阵A中第t₀行第c_1,i列的流量得到交换机状态B_count的持续时间用g_count：$g_{count}=max\{a_{i,j},a_{t_0,c_{1,i}}\},$其中c_1,i表示C中第一行第i列的数值；4f)交换机状态B_count的持续时间g_count求出后，将交换机状态B_count和交换机状态的持续时间g_count输出，且给count加1；5)判断分解过程是否完成，即判断是否成立，若成立，则完成时隙分配；若不成立，则执行步骤6)；6)判断count≥n是否成立，如果成立，则计算得到新的流量矩阵返回步骤3)，若不成立，返回步骤4)。