λ网络中一种分布式速率分配算法*

2018-12-05孙士国

沈阳工业大学学报 2018年6期

孙士国

(华北科技学院基础部，河北三河 065201)

光传输的发展极大地推动了可用网络带宽的快速增加，如密集波分复用使得每根光纤能携带成百上千个λ(即波长).专用光路、高速交换和高速路由能使中心网络具有足够的带宽，这些容量可用来建立高速共享的、基于路由的互联网和专用的光纤网络，以及基于新的动态配置技术的动态专用网络，通常称这些高速专用网络为“λ网络”.在λ网络中，可以基于需求来构建专用高速光路，以提供充足的、专用的端到端带宽.

提供端到端高性能通信是有线、无线和卫星网络研究中的一个长期性的挑战课题.文献[1]介绍了超密集波分复用(ultra-dense wavelength division multiplexed passive optical network，UDWDM-PON)的方案、结构、原理、集成设想和升级方式等，UDWDM-PON可以在C波段密集排到1 000个下行波长和1 000个上行波长，支持1 000个用户，每个用户独立使用一对波长，并具有每个用户接入带宽10 Gbit/s的潜力；文献[2]阐述了分层图模型的概念，提出波长可变光网络中的动态路由和波长分配算法(routing & wavelength assignment，RWA)，在提高波长资源利用率的同时，降低网络阻塞率；文献[3]为了解决时分复用无源光网络的低带宽、高延时，以及波分复用无源光网络的高成本、低利用率的问题，提出一种新型时分波分混合复用无源光网络系统.利用马赫曾德尔干涉光开关阵列和高速铌酸锂马赫曾德尔调制器，可灵活、快速地为不同光网络单元传递数据包，减少了光调制器的使用数量，降低了系统成本.

常用的传输协议TCP被设计用作共享低带宽网络，因此，该协议在高速环境下不能很好地对带宽和延迟增加作出响应，而且由于采用“和式增加、积式减少”(additive increase and multiplicative decrease，AIMD)控制算法，需要用较长时间来恢复数据包丢失和获得高的带宽.已有学者提出多种策略来改进标准的TCP，以实现大延时网络中快速高效的传输.文献[4]保持了TCP控制策略，但改进了TCP协议栈的实现；文献[5]采用了并行连接；部分学者提出了一些高性能TCP控制策略来提高TCP在共享和分组交换网络中的性能(如高速TCP和BIC-TCP[6])；基于时延的(如FAST-TCP[7])和基于速率的(如RBUDP和GTP[8])数据传输协议采用TCP来改进其数据包丢失.

1 问题构建

1.1 λ网络建模

本文令G表示一个λ网络，具有有限的节点集合V和有效会话集合K；用VS和VR分别表示源节点和目的节点集合；多个会话可以在相同的源节点或目的节点上开始或结束.

考虑一个离散时间模型，把时间分为相等长度的时隙.令每个会话k∈K有一个期望(峰值)速率Mk；令xk(t)为时隙t中会话k的瞬时速率，则x(t)=(x1(t)，x2(t)，…，xK(t))为时隙t中全部有效会话的速率向量；令每个源节点和目的节点v∈V有容量Cv，当v分别属于VS或VR时，Cv或者是节点v的发送容量，或者是节点v的接收容量；令Kv表示节点v参与的会话集合.在本文模型中，节点v或者是一个源节点，或者是一个目的节点，但不能同时二者都是.因此，G(V，C，K，M)就可以用来描述λ网络中的速率分配问题.

1.2 速率分配问题

λ网络中速率分配的关键就是如何高效、公平地在有效会话之间的每个源节点和目的节点分配容量.

速率分配算法应当充分利用每个源端和目的端的容量，同时保持可行.可行就是要求每个源端和目的端的会话总速率不超过其容量，而且每个会话速率不超过其期望速率.因此，对于每个节点v∈V，则有

(1)

同时对于每个会话k∈K，则有

xk≤Mk

(2)

即可认为一个速率向量x是可行的.

(∃p∈K)yp≻xp⟹(∃q∈K)yq≻xqxp

(3)

x(t+1)=f(x(t+1))

(4)

式中，f(·)为更新函数.函数f(·)可能依赖于会话期望速率、每个源端和目的端的状态等.对于一个运行良好的网络来说，速率分配算法也应当是稳定且收敛的.

2 分布式速率分配算法

2.1 分布式速率分配与自适应

(5)

(6)

(7)

2.2 源端和目的端算法

如果当前会话速率小于目标速率，就调节其接近目标速率xf，表达式为

(8)

式中：α为步长调节因子，0<α<1；xf为目标速率，其表达式为

(9)

xf的每次迭代更新反映了剩余容量的变化.当全部未确定会话的最小会话速率大于目标速率xf时，就把剩余容量平均分配给全部会话，即把目标速率分配给每个会话，表达式为

(10)

通常，总是先使具有更低期望速率的会话的速率最大化.首先考虑具有最小速率的会话，只要速率最小，就让其速率增加，只有当其被对等节点或期望速率限制，或达到了目标速率时，才停止增加.

源节点算法采用类似于目的节点算法的方式计算源节点的预期速率.在时隙t+1，会话k∈K的实际发送速率是会话k的期望速率、目的节点预期速率和源节点期望速率中的最小值.

x(t+1)=x*

(11)

对于任意初始速率向量x(0)(时刻t=0)，速率向量x在有限步数收敛到最终速率向量x*，即存在时刻t0>0，且对任意时隙t>t0，则有

x(t)=x*

(12)

除初始状态(t=0)外，在时隙t≥1时，任何节点v∈V上的最大总速率不超过(1+α)Cv，则有

(13)

3 算法性能仿真及结果分析

本文对所提算法的性能在具有不同期望速率、流量模式和动态期望速率变化的网络拓扑中进行仿真，仿真在NS-2仿真软件环境中进行.

(14)

可见，在平衡状态下，D=0.

3.1 一个目的节点和多个源节点

图1为具有5个源节点和1个目的节点的网络拓扑结构.每个源节点的会话终止于单一的目的节点.5个会话分配的速率(归一化值)分别为0.1、0.2、0.3、0.4和0.5，每个源节点和目的节点的容量(归一化值)为1.分布式算法采用的参数为α=0.1和β=0.1，这时会话的期望速率和接收节点存在瓶颈.

图1 1个目的节点和5个源节点的拓扑结构Fig.1 Topological structure of one destination node and five source nodes

设在t=0时，全部会话的初始速率为(0，0，0，0，0)，且有不同的期望速率.全部会话和目的节点上的总速率随时间的变化轨迹如图2所示.由图2可知，在20个时隙内，全部会话都收敛到平衡速率；在t=50时，会话1的期望速率从0.1开始增加到1，分布式算法对这种变化迅速做出响应，而且会话速率在短时间内收敛到一个新的平衡速率分配，同时每个会话获得相同的速率0.2；在t=100、150、200、250时，终止会话5、4、3、2.由仿真结果可知，剩余会话速率能够快速适应变化，填补空出的容量，并收敛到一个新的平衡速率分配.表1列出了各种时隙内的平衡速率分配.

图2 5个会话速率变化轨迹Fig.2 Rate change trajectories for five sessions 表1 5个会话的平衡速率和目的节点速率Tab.1 Equilibrium rates of five sessions and rate of destination node

会话0～5051～100101～150151～200201～250251～300会话10.100.20.270.50.81会话20.200.20.200.20.20会话30.230.20.270.300会话40.230.20.27000会话50.230.20000目的节点1.001.01.001.01.01

为了说明分布式算法参数α和β对收敛性的影响，采用图1的会话拓扑结构.图3为D随时间的变化关系曲线.图3a中，α从0.05变化到0.2，β=0.1固定不变；图3b中，β从0.05变化到0.2，α=0.1固定不变.

图3 参数α和β对收敛性的影响Fig.3 Effect of parameters α and β on convergence

由图3可知，较大的α值可以使算法更快收敛，一个大的α值在某些情况下可以得到更高的过冲；较大的β值也有助于系统快速收敛接近平衡点，但不如α值影响明显.

3.2 多个目的节点和多个源节点

考虑3个源节点和3个目的节点的网络拓扑结构.每个源节点和目的节点都参与3个连接会话，如图4所示.图4中，各个C值分别为各个节点容量(归一化值).可以看到，源节点2的容量比其他节点要小，全部会话都有相同的期望速率(归一化值)1；全部会话开始于t=0，初始速率分别为0.02、0.04、0.06、0.08、0.10、0.12、0.14、0.16、0.18，参数α=0.1，β=0.1.图5为每个会话和每个源节点上的总速率随时间的变化关系曲线.