CN114614940B - 一种90°旋转的用户带宽分配方法及电子设备 - Google Patents

Abstract

本发明公开了一种90°旋转的用户带宽分配方法及电子设备，在用户带宽请求已知和光链路的频谱、重构时间有限的前提下，最大化网络的吞吐量；该方法考虑了光链路的频谱容量约束和光链路的重构时间约束；该方法考虑了光链路的时间频谱积约束；该方法考虑了用户带宽请求不重叠约束，该约束考虑了90°旋转，且保证带宽请求是个矩形。本发明可以极大地提高网络吞吐量，可以提高终端用户服务体检及云服务提供商的经济收益。

Description

一种90°旋转的用户带宽分配方法及电子设备

技术领域

本发明属于通信技术领域，涉及一种带宽分配方法及系统，具体涉及一种针对在基于正交频分复用(orthogonal frequency division multiplexing，OFDM)数据中心光网络中，为用户的带宽请求提供90°旋转的带宽分配方法及电子设备，可以提高网络的吞吐量。

背景技术

由于数据密集型业务在数据中心中的大规模应用，这些业务的数据传输需要巨大的带宽，对数据中心的带宽提出了严峻的挑战。目前，电交换技术广泛地应用于商业数据中心中，但是电交换技术的传输速率存在瓶颈，无法满足数据中心内部的巨大带宽需求。

为了应对数据中心的带宽需求，光交换技术可以实现巨大的传输速率，是一种理想传输技术。近些年来，工业界和学术界提出了一些数据中心光网络架构，包括c-through,FSCOI,OSA等，高吞吐量是这些网络架构所追求的目标。尽管FSCOI和OSA等采用了波分复用技术(wavelength division multiplexing，WDM)技术来提高网络容量，但是由于WDM的频谱间隔的粒度是固定不变的，导致了频谱没有被充分利用及网络容量利用效率过低的问题。

正交频分复用技术(orthogonal frequency division multiplexing，OFDM)可以解决WDM的不足，能够为用户(企业组织、云服务提供商、政府部门等)提供细粒度、按需的带宽分配。因此，在数据中心光网络的架构中，OFDM是一种十分理想的技术选择。

和骨干网一样，在基于OFDM的数据中心光网络中，光路是用户所分配的带宽资源，具有固定的预留带宽和可持续时间。一旦可持续时间结束，数据中心光网络就停止对该用户提供带宽。但是，为了应对流量的变化，数据中心光网络需要周期性地重构网络，即根据流量来调整网络拓扑。重构网络的周期称为重构时间，也就是光链路的生存时间，所以光链路具有频谱和时间两个资源维度。这些用户的带宽请求(具有频谱和时间两个维度)都是已知的，如何分配用户带宽才能最大化网络吞吐量，是亟需解决的问题。

为了解决这个问题，一些学者提出了对应的用户带宽分配方法，这类方法是一种0/1整数规划的方法，目标是最大化网络吞吐量，也就是最大化每一个重构周期的网络吞吐量。然而，该方法可以进一步地改进。数据中心光网络对用户的带宽的分配，就是分配其频谱和时间，也就是满足该用户的数据量，数据量等于时间和频谱的乘积，简称为时间频谱积。保持用户的数据量不变，改变其频谱和时间，可以使资源分配更加灵活、提高网络吞吐量。但是，由于数据量是固定的，频谱和时间都是变量，该方法是一种带有平方项的非线性方法，很难求解。

发明内容

在基于OFDM数据光网络中，为了利用频谱和时间的灵活性，本发明提出了一种90°旋转的用户带宽分配方法及电子设备，即90°旋转的用户带宽请求，用户的频谱请求考虑在光链路的时间维度，用户的时间请求考虑在光链路的频谱维度。

本发明的方法所采用的技术方案是：一种90°旋转的用户带宽分配方法，在用户带宽请求已知和光链路的频谱、重构时间有限的前提下，最大化网络的吞吐量；

定义G(V,L,T,S)为基于OFDM的数据中心光网络。V是光网络节点的集合，L是光链路的集合。光链路的资源具有时间和频谱两个维度，T是光链路的重构时间；S是光链路的频谱容量；光链路的容量，即时间频谱积为T*S。

定义用户请求的集合为其中D_ij＝{D_ij}，D_ij＝＜T_ij,S_ij＞是用户的带宽请求，D_ij是共享光链路l_ij的请求集合。D_ij表示从源节点V_i到目的节点V_j的带宽请求，这两者之间的路由就是光链路l_ij，其带宽请求是一个矩形，需要的时隙数量和频隙数量分别为T_ij和S_ij，时间频谱积为T_ij*S_ij。

定义D_ij′＝＜T_ij′,S_ij′＞是用户带宽请求，需要的时隙数量和频隙数量分别为T_ij′和S_ij′，它是D_ij中不同于D_ij的用户带宽请求。

数据中心光网络的优化目标为最大网络吞吐量，即其中r_ij是一个布尔变量，当r_ij＝1表示D_ij被服务，即D_ij被分配时隙和频隙；否则D_ij＝0表示D_ij没有被服务。

数据中心光网络优化受到光链路重构时间约束、光链路频谱容量约束、光链路时间频谱积约束和请求不重叠约束，其中请求不重叠约束考虑请求90°旋转，保证请求是个矩形。

光链路重构时间约束为t_ij+T_ij≤T,表示D_ij被分配的时隙不能超过光链路的重构时间。其中，t_ij是一个整数变量，表示D_ij被分配时隙的开始时隙，t_ij+T_ij表示其截止时隙。

光链路频谱容量约束为s_ij+S_ij≤S,表示D_ij被分配的频隙不能超过光链路的频谱容量。其中，s_ij是一个整数变量，表示D_ij被分配频隙的开始频隙，s_ij+S_ij表示其截止频隙。

光链路时间频谱积约束为意味着对于许多用户请求共享光链路l_ij时，其中一些能被分配时、频资源，这些用户请求的时间频谱积之和，必须不大于该光链路的时间频谱积。

用户请求不重叠约束如下，该约束考虑了请求90°旋转，保证了请求是个矩形：

M＝max(T,S)是一个极大数，用来满足约束条件；c_ij,mn是一个0/1布尔变量，当D_ij和D_mn共享一条光链路l_ij时，c_ij,mn＝1，此时D_ij′＝D_mn；否则c_ij,mn＝0。α_ij,mn和β_ij,mn都是0/1布尔变量，(α_ij,mn,β_ij,mn)代表D_ij和D_mn在时间和频谱维度的相对位置。z_ij是一个0/1布尔变量，当z_ij＝0时表示D_ij没有90°旋转；当z_ij＝1时表示D_ij进行了90°旋转。

当c_ij,mn≠1时，即D_ij和D_mn不共享同一光链路l_ij时，公式(1)-(4)恒成立，即D_ij和D_mn都是矩形且不会重叠；否则，当c_ij,mn＝1时，即D_ij和D_mn共享同一光链路l_ij时，公式(1)-(4)被激活，即将c_ij,mn＝1带入公式(1)-(4)，则规约成：

当D_ij和D_ij′中的任意一个没有被服务时(r_ij≠1或r_ij′≠1)，公式(5)-(8)恒成立，即D_ij和D_ij′都是矩形且不会重叠；当D_ij和D_ij′都被服务时(r_ij＝r_ij′＝1)，公式(5)-(8)被激活，即将r_ij＝1和r_ij′＝1带入公式(5)-(8)，则规约成：

当z_ij＝0和z_ij′＝0时，D_ij和D_ij′没有90°旋转，公式(9)-(12)被激活且规约成：

当z_ij＝1和z_ij′＝1时，D_ij和D_ij′进行了90°旋转，公式(9)-(12)被激活且规约成：

(α_ij,i′j′,β_ij,i′j′)的值有四种可能，分别为(0,0)、(0,1)、(1,0)和(1,1)，可以控制D_ij和D_ij′在时间或频谱的相对位置，保证他们在时间或频谱的维度不相交。对于(α_ij,i′j′,β_ij,i′j′)的取值，无论D_ij和D_ij′是否进行了90°旋转，在公式(13)-(16)中，只有一个被激活且进一步规约；在公式(17)-(20)中，只有一个被激活且进一步规约。

在D_ij和D_ij′没有进行90°旋转的情况下，当(α_ij,i′j′,β_ij,i′j′)＝(1,0)时，公式(15)被激活，规约成t_ij+T_ij-t_ij′≤0，保证D_ij和D_ij′在时间维度不相交，即D_ij的截止时隙不大于D_ij′的开始时隙，称之为请求不相交约束。该约束还保证了D_ij占用了T_ij个连续的时隙；进而，由于公式(13)恒成立，保证了D_ij占用了S_ij个连续的频隙，所以请求D_ij是个时、频长度为T_ij和S_ij的矩形。同理(α_ij,i′j′,β_ij,i′j′)＝(0,0)激活了公式(13)，保证了D_ij和D_ij′在频谱维度不相交，且D_ij占用了S_ij个连续的频隙。(α_ij,i′j′,β_ij,i′j′)＝(0,1)激活了公式(14)，保证了D_ij和D_ij′在频谱维度不相交，且D_ij′占用了S_ij′个连续的频隙。(α_ij,i′j′,β_ij,i′j′)＝(1,1)激活了公式(16)，保证了D_ij和D_ij′在时间维度不相交，且D_ij′占用了T_ij′个连续的时隙。

在D_ij和D_ij′进行了90°旋转的情况下，当(α_ij,i′j′,β_ij,i′j′)＝(1,0)时，公式(19)被激活，规约成t_ij+S_ij-t_ij′≤0，保证D_ij和D_ij′在时间维度不相交，也保证了D_ij占用了S_ij个连续的时隙；进而，由于公式(17)恒成立，保证了D_ij占用了T_ij个连续的频隙，所以请求D_ij进行了90°旋转，是一个时、频长度为S_ij和T_ij的矩形。同理(α_ij,i′j′,β_ij,i′j′)＝(0,0)激活了公式(17)，保证了D_ij和D_ij′在频谱维度不相交，且D_ij占用了T_ij个连续的频隙。(α_ij,i′j′,β_ij,i′j′)＝(0,1)激活了公式(18)，保证了D_ij和D_ij′在频谱维度不相交，且D_ij′占用了T_ij′个连续的频隙。(α_ij,i′j′,β_ij,i′j′)＝(1,1)激活了公式(20)，保证了D_ij和D_ij′在时间维度不相交，且D_ij′占用了S_ij′个连续的时隙。

将该整数线性的数学模型输入到Cplex、Gurobi等数学优化软件中，这些软件自带的最优算法可以在满足约束条件的前提下，得到最优解，即最大化网络吞吐量。

本发明还提供了一种电子设备，包括：

一个或多个处理器；

存储装置，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器实现90°旋转的用户带宽分配方法。

将该整数线性的数学模型输入到Cplex、Gurobi等数学优化软件中，这些软件自带的最优算法可以在满足约束条件的前提下，得到最优解，即最大化网络吞吐量。

本发明考虑了光链路的频谱容量约束和光链路的重构时间约束，考虑了光链路的时间频谱积约束，考虑了用户带宽请求不重叠约束，该约束考虑了90°旋转，且保证带宽请求是个矩形，在用户的数据量不变的前提下，通过90°旋转来改变其对频谱和时间的需求，可以使资源分配更加灵活，提高网络吞吐量，也可以提高终端用户服务体检及云服务提供商的经济收益。

附图说明

图1为本发明实施例的90°旋转的带宽分配方法示意图。

具体实施方式

为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施例对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解释本发明，并不用于限定本发明。

请见图1，本发明提供的一种90°旋转的用户带宽分配方法，在用户带宽请求已知和光链路的频谱、重构时间有限的前提下，最大化网络的吞吐量；

本实施例中，光网络由网元节点A、B和光链路l_AB组成。光链路l_AB的重构时间为4个时隙，频谱容量为4个频隙，光链路的时间频谱积为4*4＝16。

本实施例中，有四个用户的带宽请求，表示该用户需要2个时隙和4个频隙，资源分配的源节点为A，目的节点为B；其它3个用户的带宽请求分别为和/>

本实施例中，在Gurobi优化软件上输入该数学模型，优化目标为最大化网络吞吐量，约束条件为光链路的频谱容量约束、光链路的重构时间约束；用户的带宽请求不重叠约束，该约束保证了带宽请求是个矩形、考虑了90°旋转，该优化软件内置的优化算法可以解决该问题并得到最优解。最优解为和/>被服务了(被分配了时间、频谱资源)，这些请求都是矩形且不重叠；由于光链路的容量限制，/>没有被分配资源，网络吞吐量为和/>的时间频谱积之和，即2*4+3*2+1*2＝16，接下来是具体的结果。

本实施例中，和/>都共享了光链路l_AB，所以c_AB,A′B′都等于1。

本实施例中，不需要90°旋转就可以被服务，即z_AB＝0、r_AB＝1，被分配的时隙数为2，其开始时隙t_AB＝0，即为第0号时隙，截止时隙为第2号时隙；被分配的频隙数为4，开始频隙s_AB＝0，即为第0号频隙，截止频隙为第4号频隙。

本实施例中，需要90°旋转才能被服务，即z_AB＝1、r_AB＝1，被分配的时隙数为2，其开始时隙t_AB＝2，即为第2号时隙，截止时隙为第4号时隙；被分配的频隙数为3，开始频隙s_AB＝0，即为第0号频隙，截止频隙为第3号频隙。

本实施例中，没有被服务，即r_AB＝0。

本实施例中，需要90°旋转才能被服务，即z_AB＝1、r_AB＝1，被分配的时隙数为2，其开始时隙t_AB＝2，即为第2号时隙，截止时隙为第4号时隙；被分配的频隙数为1，开始频隙为s_AB＝3，即为第3号频隙，截止频隙为第4号频隙。

本实施例中，假设和/>则D_AB不需要90°旋转，(α_AB,A′B′,β_AB,A′B′)＝(1,0)能激活公式(15)且规约成t_AB+T_AB-t_AB′≤0，由于t_AB＝0，t_AB′＝2，T_AB＝2，该公式成立且保证了D_AB占用的时隙数为T_AB＝2。

本实施例中，假设和/>则D_AB不需要90°旋转，(α_AB,A′B′,β_AB,A′B′)＝(1,0)能激活公式(15)且规约成t_AB+T_AB-t_AB′≤0，由于t_AB＝0，t_AB′＝2，T_AB＝2，该公式成立且保证了D_AB占用的时隙数为T_AB＝2。

本实施例中，假设和/>则D_AB需要90°旋转，(α_AB,A′B′,β_AB,A′B′)＝(1,0)能激活公式(19)且规约成s_AB+T_AB-s_AB′≤0，由于s_AB＝0，s_AB′＝3，T_AB＝3，该公式成立且保证了D_AB占用的频隙数为T_AB＝3。

应当理解的是，上述针对较佳实施例的描述较为详细，并不能因此而认为是对本发明专利保护范围的限制，本领域的普通技术人员在本发明的启示下，在不脱离本发明权利要求所保护的范围情况下，还可以做出替换或变形，均落入本发明的保护范围之内，本发明的请求保护范围应以所附权利要求为准。

Claims (2)

1.一种90°旋转的用户带宽分配方法，其特征在于：在用户带宽请求已知和光链路的频谱、重构时间有限的前提下，最大化网络的吞吐量；

定义G(V,L,T,S)为基于OFDM的数据中心光网络；其中，V是光网络节点的集合，L是光链路的集合；光链路的资源具有时间和频谱两个维度，T是光链路的重构时间；S是光链路的频谱容量；光链路的容量，即时间频谱积为T*S；

定义用户请求的集合为其中D_ij＝{D_ij}，D_ij＝<T_ij,S_ij>是用户的带宽请求，D_ij是共享光链路l_ij的请求集合；D_ij表示从源节点V_i到目的节点V_j的带宽请求，这两者之间的路由就是光链路l_ij，其带宽请求是一个矩形，需要的时隙数量和频隙数量分别为T_ij和S_ij，时间频谱积为T_ij*S_ij；

定义D_ij′＝<T_ij′,S_ij′>是用户带宽请求，需要的时隙数量和频隙数量分别为T_ij′和S_ij′，它是D_ij中不同于D_ij的用户带宽请求；

所述数据中心光网络的优化目标为最大网络吞吐量，即其中r_ij是一个布尔变量，当r_ij＝1表示D_ij被服务，即D_ij被分配时隙和频隙；否则D_ij＝0表示D_ij没有被服务；

所述数据中心光网络优化受到光链路重构时间约束、光链路频谱容量约束、光链路时间频谱积约束和请求不重叠约束，其中请求不重叠约束考虑请求90°旋转，保证请求是个矩形；

光链路重构时间约束为表示D_ij被分配的时隙不能超过光链路的重构时间；其中，t_ij是一个整数变量，表示D_ij被分配时隙的开始时隙，t_ij+T_ij表示其截止时隙；

光链路频谱容量约束为表示D_ij被分配的频隙不能超过光链路的频谱容量；其中，s_ij是一个整数变量，表示D_ij被分配频隙的开始频隙，s_ij+S_ij表示其截止频隙；

光链路时间频谱积约束为意味着对于若干用户请求共享光链路l_ij时，其中一些能被分配时、频资源，这些用户请求的时间频谱积之和，必须不大于该光链路的时间频谱积；

用户请求不重叠约束如下，该约束考虑请求90°旋转，保证请求是个矩形：

M＝max(T,S)是一个极大数，用来满足约束条件；c_ij,mn是一个0/1布尔变量，当D_ij和D_mn共享一条光链路l_ij时，c_ij,mn＝1，此时D_ij′＝D_mn，否则c_ij,mn＝0；α_ij,mn和β_ij,mn都是0/1布尔变量，(α_ij,mn,β_ij,mn)代表D_ij和D_mn在时间和频谱维度的相对位置；z_ij是一个0/1布尔变量，当z_ij＝0时表示D_ij没有90°旋转，当z_ij＝1时表示D_ij进行了90°旋转；

当c_ij,mn≠1时，即D_ij和D_mn不共享同一光链路l_ij时，公式(1)-(4)恒成立，即D_ij和D_mn都是矩形且不会重叠；否则，当c_ij,mn＝1时，即D_ij和D_mn共享同一光链路l_ij时，公式(1)-(4)被激活，即将c_ij,mn＝1带入公式(1)-(4)，则规约成：

当D_ij和D_ij′中的任意一个没有被服务时，即r_ij≠1或r_ij′≠1，公式(5)-(8)恒成立，即D_ij和D_ij′都是矩形且不会重叠；当D_ij和D_ij′都被服务时，即r_ij＝r_ij′＝1，公式(5)-(8)被激活，即将r_ij＝1和r_ij′＝1带入公式(5)-(8)，则规约成：

当z_ij＝0和z_ij′＝0时，D_ij和D_ij′没有90°旋转，公式(9)-(12)被激活且规约成：

当z_ij＝1和z_ij′＝1时，D_ij和D_ij′进行了90°旋转，公式(9)-(12)被激活且规约成：

(α_ij,i′j′,β_ij,i′j′)的值有四种可能，分别为(0,0)、(0,1)、(1,0)和(1,1)，控制D_ij和D_ij′在时间或频谱的相对位置，保证他们在时间或频谱的维度不相交；对于(α_ij,i′j′,β_ij,i′j′)的取值，无论D_ij和D_ij′是否进行了90°旋转，在公式(13)-(16)中，只有一个被激活且进一步规约；在公式(17)-(20)中，只有一个被激活且进一步规约；

在D_ij和D_ij′没有进行90°旋转的情况下，公式(13)、(15)保证D_ij占用了S_ij个连续的频隙和T_ij个连续的时隙，即D_ij是个矩形，且在频谱和时间维度和D_ij′都不相交；公式(14)、(16)保证D_ij′占用了S_ij′个连续的频隙和T_ij′个连续的时隙，即D_ij′是个矩形，且在频谱和时间维度和D_ij都不相交；

在D_ij和D_ij′进行了90°旋转的情况下，公式(17)、(19)保证D_ij占用了T_ij个连续的频隙和S_ij个连续的时隙，即D_ij是个矩形，且在频谱和时间维度和D_ij′都不相交；公式(18)、(20)保证D_ij′占用了T_ij′个连续的频隙和S_ij′个连续的时隙，即D_ij′是个矩形，且在频谱和时间维度和D_ij都不相交；

在满足约束条件的前提下，得到最优解，即最大化网络吞吐量。

2.一种电子设备，其特征在于，包括：

一个或多个处理器；

存储装置，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器实现如权利要求1所述的90°旋转的用户带宽分配方法。