一种端到端的分布式流量分配算法

摘要

一种端到端的分布式流量分配算法，涉及网络流量分配领域，本发明包括以下步骤：步骤1：建立非凸优化问题；步骤2：经过选择合适的变量，将非凸优化问题转化为一族等价的凸优化问题；步骤3：提出完全分布式的最优的流量分配算法。本发明为优化非凹效用函数的、完全分布式的、基于优化控制的方法，有着提高网络安全性、降低通讯代价等优点，而且可以节省很大的计算量。

说明书

技术领域

本发明涉及网络流量分配领域，尤其涉及一种端到端的分布式流量分配算法。

背景技术

近年来，随着IP视频服务在互联网应用中占据主导地位，满足用户对于视频应用服务等互联网应用日益增长的需求成为了未来互联网的发展方向。IP视频应用的受欢迎程度越来越高，这给网络带宽资源的配置带来了巨大压力。例如，根据2016年6月1日发布的《思科未来网络发展业务趋势白皮书》，2020年IP视频流将会占据整个消费者网络流量的82％，相比于2015年的70％有较大提升；而且，该白皮书预测IP视频流将会在2015至2020年之间增长三倍。因此，未来网络的发展趋势就是，既要处理好日益增长的视频应用需求，还要给视频应用等其他互联网应用用户提供高品质的服务。然而，现有的端到端的数据率分配方案(例如基于窗口的传输控制协议和拥堵控制机制，即TCP协议)和网络流量工程方案(例如基于流的等成本多路径负载均衡机制，即ECMP协议)均无法提供这样的服务。

现有的TCP协议和ECMP协议存在如下缺陷：

1、视频内容可能被用不同的解码频率解码或者用不同个数的解码层解码，而且解码的频率越高或者解码层数越多，用户对服务质量的满意度越高。因此，用来描述用户对服务质量满意程度的效用函数是关于解码率的阶梯状函数。因为这样的效用函数是非凹的，所以优化这样的效用函数有本质上的难度。然而，目前可用的端到端的传输机制如TCP协议仅能优化凹的效用函数，因而并不能优化非凹的效用函数，也就不能提供用户较高的服务质量。

2、目前网络中常常出现“大象流”现象，“大象流”现象是指：网络中极少的带宽承载着较大比例的流量传输任务，而剩余的带宽处于闲置状态。传统的ECMP协议因为不是基于优化的方法，所以很有可能导致了“大象流”现象。

3、因为缺乏理论支撑，现有的端到端的和网络流量工程机制将会如何影响用户对于视频应用服务和其他应用服务的满意程度，甚至是如何影响整个网络的稳定性，都是未知的。

因此，开发可以优化非凹效用函数的、完全分布式的、基于优化控制的方法是非常必要的。

发明内容

本发明的目的在于解决现有技术中的上述问题，提供一种端到端的分布式流量分配算法，该算法为优化非凹效用函数的、完全分布式的、基于优化控制的方法，有着提高网络安全性、降低通讯代价等优点，而且可以节省很大的计算量。

为达到上述目的，本发明采用如下技术方案：

一种端到端的分布式流量分配算法，包括以下步骤：

步骤1：建立基于用户满意程度的非凸优化问题；

步骤2：经过选择合适的变量，将非凸优化问题转化为一族等价的优化问题；

步骤3：提出完全分布式的最优的流量分配算法。

在步骤1中，建立基于用户满意程度的非凸优化问题的方法为：

subject to

1_s,lx_s,l≤c_l,l∈L_s,s∈S(26)

Fx＝0(27)

(x_s,r_s)∈X_s,s∈S(29)

该优化问题的效用函数为：

其中，α和ι分别为给定的正整数，j∈{0,1,2,...,α}，s为发送流量的节点，r_s为节点s发出的所有流量的和；给定节点s，分数阶函数以r_s作为自变量，以集合{p_s,0,...,p_s,j-1,p_s,j,p_s,j+1,...,p_s,α}中元素作为相应阶数对应的参数，的阶数为j/ι，其相应参数为p_s,j，表征发送流量节点s相关的用户满意程度；是求和运算的记号，表示令变量j从0增长到α，将对应的函数值相加；同样，∑_s∈S也是求和运算的记号，表示令变量s不重复地遍历集合S中的值，将对应的函数值相加；b为传输流量的节点；d为流量的终点；l为传输流量的链路；e_l(b)是与节点b经链路l相连的节点；为由节点s发出的，以节点d为终点，经链路l传输的流量；为由节点b传输的，以节点d为终点，经链路l传输的流量；为由节点e_l(b)传输的，以节点d为终点，经链路l传输的流量；S为由所有发送流量节点s构成的集合；为由所有传输流量的节点b构成的集合；L_b是与节点b相连接的链路l的集合；L_s是与节点s相连接的链路l的集合；c_l为链路l所能承载流量的带宽；x_s,l为由节点s发出的，经链路l传输的总流量；x_b,l为节点b经链路l传输的总流量；x_s为由所有节点s发出的流量构成的向量，即x_b是由所有节点b传输的流量构成的列向量，即向量右上角的T表示对向量x_b,l做转置运算；x是由所有流量构成的列向量，即自变量r是由所有变量r_s构成的列向量，即1_s,l、和均是以正整数1为元素的横向量，它们的元素个数分别与列向量x_s,l、x_b,l和x_el(b),l的元素个数相同；F为类邻接矩阵；是节点b用来传输以d为终点的流量的所有链路l构成的集合；D_b为由节点b传输的所有流量的终点d构成的集合；D_s,l是节点s经链路l传输的所有流量的终点d构成的集合；ξ_s和ζ_s为常数，分别是r_s的下界和上界；和R₊分别表示维数为和1的正整数空间，|D_s,l|是向量D_s,l的维数；

条件(1)和(2)表示链路承载能力的限制，链路l传输的流量不能超过它的承载能力；条件(3)表示在传输过程中节点不能丢失流量的限制，流入每个节点的流量应该等于流出该节点的流量；条件(4)表示传输节点b传输的流量是非负的；条件(5)表示节点s发出的流量是非负的，并且发出的总流量是有上下界的；条件(6)给出集合X_s的定义。

步骤2的方法如下：

选取变量将y_s假设为随机变量并令y_s对于测度μ_s的第j个动量矩记为m_s,j，即其中j∈{0,1,2,...,α}，利用泛函分析理论，将非凸优化问题转化为如下一族优化问题：

subject to

m_s,0＝1,s∈S(32)

M_s(0,α,m_s)≥0,s∈S(33)

β_sM_s(0,α-2,m_s)-M_s(0,α,m_s)≥0(34)

1_s,lx_s,l≤c_l,l∈L_s,s∈S(37)

Fx＝0(38)

(x_s,r_s)∈X_s,s∈S(40)

该优化问题的效用函数为：

其中，给定节点s，函数是以横向量为参数并且以列向量为变量的线性函数；自变量m是由所有转矩变量m_s构成的列向量，即常数β_s是节点s发送流量之和的已知上界；M_s是如下式的Hankel矩阵：是一个给定序列，k,h是序列中元素的记号；步骤2中出现的其他记号均与步骤1中相应的记号定义相同；条件(8)、(9)和(10)保证测度μ_s的存在性；条件(11)保证等式成立；这一族优化问题等价于原非凸优化问题，并且当参数α≤ι，该族优化问题为凸优化问题。

在步骤3中，利用ADMM算法可得到如下的完全分布式流量分配方法：

算法1：

初始值：{τ_s}_s∈S,γ

1)开始

2)初始化变量值

3)x⁰,m⁰,r⁰,λ⁰

4)引入记号

5)引入记号

6)当迭代次数k+1时，按如下方式更新与发送流量节点s相关的变量值

7)同时按如下方式更新与传输流量节点b相关的变量值

8)每个发送流量节点s∈S通过链路L_s传输流量

9)每个传输流量节点通过链路l∈L_b传输流量

10)按如下方式更新与链路l∈L_b，相关的惩罚参数

11)更新记号

12)更新记号

13)每个节点s∈S通过链路L_s传输信息

14)每个节点通过链路l∈L_b传输信息

x⁰,m⁰,r⁰,λ⁰为变量x，m，r，λ的选定的迭代初始值；和均为向量x⁰中的元素；变量右上角的记号k均代表第k次迭代得到的变量值；同样，变量右上角的记号k+1均代表第k+1次迭代得到的变量值；运算符号←表示将箭头右端的值赋值给箭头左端变量；A_s是每个节点s∈S局部限制条件构成的集合，即

变量的定义如下：

其中，和均是为了避免引起混淆而引入的记号，它们与记号l均是代表用来传输流量的链路；是指以节点d为终点的流量流入节点b所经过的链路构成的集合；是指节点b用来传输以d为终点的流量的所有链路构成的集合；是指以节点d为终点的流量流入节点e_l(b)所经过的链路构成的集合；是指以节点e_l(b)用来传输以d为终点的流量的所有链路构成的集合；分别是为了存储变量的值而引入的记号；是指节点b通过链路l传输的所有流量的终点构成的集合；

是以为元素的列向量，其中，

变量的定义如下：

其中，是指以节点e_l(s)用来传输以d为终点的流量的所有链路构成的集合，e_l(s)是与节点s由链路l相连的节点；分别是为了存储变量的值而引入的记号；D_s,l是指节点s通过链路l发送的所有流量的终点构成的集合；

记号分别代表将变量向空间A_s、R₊做投影运算；待确定的步长参数序列{τ_s}_s∈S,和步长参数γ由如下方式确定：

当给定通讯网络和凸优化问题，其中该凸优化问题的决策变量为(x,m,r)，假定算法1迭代初值为(x⁰,m⁰,r⁰),迭代产生的序列为{x^k,m^k,r^k}_k∈N，其中，x^k,m^k,r^k表示第k次迭代产生的变量值，N代表由所有自然数构成的集合。若令迭代步长参数{τ_s}_s∈S,和γ满足如下不等式：

其中，m_l是通过链路l∈L_b传输的所有流量的终点个数；{υ_s}和分别满足以下不等式：

其中，是指与节点s相连的，用来传输以节点d为终点的流量的所有链路l构成的集合；是指以节点d为终点的流量流入节点e_l(s)所经过的链路l构成的集合，e_l(s)是与节点s由链路l相连的节点；是指以节点e_l(s)用来传输以d为终点的流量的所有链路l构成的集合；是指以节点d为终点的流量流入节点所经过的链路l构成的集合；是指以节点用来传输以d为终点的流量的所有链路l构成的集合；运算符号|·|代表了取相应集合中元素个数；

那么迭代序列{x^k,m^k,r^k}_k∈N将收敛到问题中最大化效用函数的一个解，算法1的收敛速率是O(1/k)，其中k为迭代次数。

在算法1中，对任意给定的步长参数γ>0，每个发送流量的节点s∈S自己决定它的局部步长参数τ_s>0。同时，每个发送流量的节点s∈S也将参数变量m_s,r_s和ps作为它的局部隐私信息，不需要和网络中的其他节点共享。此外，每个发送流量的节点s∈S还要引入辅助变量z_s，用来存储变量x_s的值，从而使得设计的流量分配算法是完全分布式的。假设每个发送流量的节点s∈S已知与它连通的所有链路L_s，并且已知这些链路的流量承载能力信息。此外，为了更新流量，每个发送流量的节点s∈S还要已知式(18)中给出的集合A_s的结构。

类似地，每个传输流量的节点也是利用局部信息决定它的步长参数假设每个传输流量的节点已知与它相连的链路L_b，并且仅需已知部分链路的流量承载能力，即对于每个d∈D_b，它仅需知道集合中链路的流量承载能力。此外，给定节点对每条链路l∈L_b，变量λ_b,l是非负的数值变量，代表了链路l的代价参数。

类似于发送流量的节点，每个传输流量的节点也需要引入辅助变量z_b,l,l∈L_b，用来存储变量x_b,l的值，从而使得设计的流量分配算法是完全分布式的。

算法1中，所有变量的右上角标代表了迭代次数。具体地，在第k次迭代时，算法1中包括如下操作：在第6步，所有的发送流量节点同时更新它们理想的发送数据率，该步骤是每个发送流量节点通过利用它的局部信息求解一个简单的半正定规划问题完成的；在第7步中，所有的传输流量的节点同时更新它们理想的发送数据率，同样，该步骤也是每个传输流量的节点利用它的局部信息完成的；在第10步中，对每个传输流量的节点每条链路l∈L_b更新它相应的代价变量λ_b,l，这一步操作可以在该链路连接的一个或者两个节点上计算。具体地，当考虑通讯量的情况下，那么该代价变量可以在两个节点上同时计算，否则仅需在一个节点上计算之后传输给另外一个节点。

综上所述，算法1是一个完全分布式的流量分配算法。这体现在所有的运算都是在每个节点上局部进行的，并且计算时用到的信息也都是它能用到的局部信息，而没有用到任何全局信息。

算法1中，每个路由器仅需要利用每个数据单元中存储的终点信息做出分配决策，如果不同类型的流量(指流量有不同的发送节点/终点对)到达同一个传输流量节点，那么这个传输流量的节点仅根据流量包中存储的终点信息做出决策，而不需要根据存储的发送节点/终点对信息进行决策。当一个通讯网络中有N个发送流量的节点和M个终点，若每个发送流量的节点会向所有的终点发送数据率，那么网络中就会存在N×M种类型的流量，在用算法1进行流量分配时，每个传输流量的节点仅至多需要更新M个数据率变量，相比于按流量类型更新数据率的算法相比，显然会降低计算代价。

相对于现有技术，本发明技术方案取得的有益效果是：

1、本发明将用户对视频服务等互联网应用的满意程度建模为关于数据率的非凹函数，将互联网中带宽资源的优化分配问题建模为非凸的优化问题，并提出了一种分布式的资源分配算法。该算法可用于在非连通通讯模式下的分组交换网络，可解决多个终端之间的分组传输问题，并且该算法可以使每个路由器仅利用局部信息独立决定数据单元的个数，而不需要利用任何全局信息，因而，该算法是完全分布式的。

2、相比于中心式算法，本发明的完全分布式算法有着提高网络安全性、降低通讯代价等优点。

3、每个路由器仅利用每个数据单元中的目的节点信息决定传输策略，相比于其他算法，可以节省很大的计算量。

4、本发明可以保证用户的满意程度以O(1/k)的速度收敛到最优值。

附图说明

图1为8组不同的发送流量节点/终端节点和8个传输流量节点之间连接关系的通讯拓扑图；

图2为理想情况下，利用算法1和基因算法得到的效用函数值比较图；

图3为理想情况下，利用算法1得到的发送流量节点/终点对s₁/d₃,s₄/d₂,s₈/d₃之间流量的变化轨迹图；

图4为出现链路断开情况下，利用算法1和基因算法得到的目标函数值；

图5为出现链路断开情况下，利用算法1得到的发送流量节点/终点对s₁/d₃,s₄/d₂,s₈/d₃之间流量的变化轨迹图。

具体实施方式

为了使本发明所要解决的技术问题、技术方案及有益效果更加清楚，以下结合附图和实施例，对本发明做进一步详细说明。

图1为网络模型，该模型允许每个发送流量的节点利用多条路径传输流量。在图1中显示了节点分类和每条链路带宽。本实施例设有8组不同的发送流量节点/终端节点对，即s₁/d₃,s₂/d₂,s₃/d₃,s₄/d₂,s₅/d₅,s₆/d₅,s₇/d₇,s₈/d₃，这些流量的传输路径如表1所示。例如，根据表1中第一行b₁和第一列d₂所对应的为b₂,b₇，表示节点b₁将以节点d₂为终点的流量传输给节点b₂和b₇。

表1

b₁b₂b₃b₄b₅b₆b₇b₈d₂b₂,b₇b₇,b₈--d₂-b₅b₅,b₇d₃b₂,b₇b₇,b₈b₄d₃--b₈b₃,b₄d₅b₇b₁,b₇,b₈b₄,b₈b₈b₇d₅b₆b₅,b₇d₇b₂,b₇d₇----b₂,b₈b₂

本实施例的目标效用函数为U_si(r_si)为类似于阶梯状的非凹的效用函数，这种函数可以恰当地描述用户在视频流服务应用中的满意程度，因此本实施例中考虑采用该效用函数，并且每种节点发送流量的上下限分别是ξ_si＝0.1,ζ_si＝3,i＝1,...,8。

上述目标效用函数并不是如式(7)所示的多项式型函数，故需要用多项式型函数逼近上述目标效用函数，从而得到参数向量P_si,i＝1,...,8。采用平方和逼近的方法，以下的仿真结果是针对于参数α＝ι＝6的情形。

在仿真中，考虑解决以上述多项式函数为目标效用函数，以式(1)～(6)为限制条件的全局优化问题。为了对比算法1的仿真效果，采用基因算法求解上述优化问题，并将基因算法得到的效用函数最优值作为标准结果。

算法1中迭代步长的选择满足不等式(21)和(22)。图2为理想情况下(没有链路断开情况下)，利用算法1和基因算法得到的效用函数值比较图，算法1得到的结果用点折线表示，对应记号为DFRDA Algorithm；基因算法得到的结果用实线表示，对应记号为GeneticAlgorithm；可以看到算法1得到的效用函数值逐渐收敛到标准值(通过基因算法得到的)。这说明了尽管算法1是一种分布式的计算方法，它仅能得到局部信息进行计算，但是算法1仍然可以得到中心式算法(基因算法)一样的最优值。

图3为理想情况下(没有链路断开情况下)，利用算法1得到的发送流量节点/终点对s₁/d₃,s₄/d₂,s₈/d₃之间流量的变化轨迹图，可以看到这些数据率满足了上下限有界的限制条件。

由于网络中常常会有某些链路突然断开或突然建立连接的现象发生，这需要流量分配算法快速地重新分配流量并将效用函数值优化到新的最优值，因此流量分配算法必须具有较高的鲁棒性。

为了考察算法1的鲁棒性，本发明在130次迭代时，将节点b₇和b₈间的链路断开，因为所有的发送流量节点都需要用该链路完成流量的传输，所以将b₇和b₈间的链路断开实验。此时，通过检查不等式(21)和(22)可以得到，算法1的迭代步长参数仍然满足上述不等式，故可仍选用这些参数进行仿真。

图4为出现链路断开情况下，利用算法1和基因算法得到的效用函数值，算法1得到的结果用点折线表示，对应记号为DFRDA Algorithm；基因算法得到的结果用实线表示，对应记号为Genetic Algorithm；图4中显示了算法1在出现链路断开后可以快速响应，重新分配流量，从而使效用函数值收敛到新的最优值，该最优值由基因算法得到。

图5显示了发送流量节点/终点对s₁/d₃,s₄/d₂,s₈/d₃之间流量的变化轨迹。同样可以看到算法1在链路断开后可以快速响应，将流量进行重新分配。