一种消除链路拥塞的骨干网络流量调度方法

摘要

本发明公开了一种消除链路拥塞的骨干网络流量调度方法，通过将原路由的拥塞部分转移到该拥塞部分的代替路径上，从而绕过拥塞链路。在具体针对某条拥塞链路，该拥塞链路上的一些流量会因为太大而找不到合适的备选路径，算法此时会暂时跳过这一条流量，处理下一条流量；当算法遍历完一遍该条拥塞链路上的流量，并且将能迁移出去的流量都迁移之后，链路的拥塞状态还未消除，算法就会对链路上剩余的所有汇聚流进行拆分，将一条较大的汇聚流拆分成几条较小的汇聚流，但最多达到拆分的最大条数限制，这样增加流量找到备选路径的几率，实现了拥塞链路的调整。

权利要求

1.一种消除链路拥塞的骨干网络流量调度方法，其特征在于，包括以下步骤：

(1)、根据网络反馈的拥塞链路信息，形成拥塞链路列表，遍历拥塞链路列表中的每条拥塞链路c_linkk，k＝1,2,…，再执行步骤(2)；

(2)、对拥塞链路c_linkk进行处理；

(2.1)、设置拥塞链路c_linkk的拆分粒度g，并初始化为0；

(2.2)、将拥塞链路c_linkk上的所有流量按从大到小排序，形成流量列表；

(2.3)遍历流量列表中的每条流量flowi，i＝1,2,…，再执行步骤(3)(3)、通过对交换机流表项的count字段进行统计，获知流量flowi的大小为sizeflow_i；再从路由信息数据库中检索，获取流量flowi的原路由路径为route_pathflow_i；

设置流量flowi的延伸链路link_extendflow_i，用S、T表示延伸链路的源节点和目的节点；设置延伸链路集合extend_link_setflow_i；

(3.1)将流量flowi的延伸链路link_extendflow_i初始化为拥塞链路；将延伸链路集合extend_link_setflow_i初始化为拥塞链路；

(3.2)在S、T之间寻找跳数小于预设的jump_limit、可用带宽大于该流量flowi的大小sizeflow_i、且不经过延伸链路集合extend_link_setflow_i的所有链路作为备选路径，从而得到备选路径列表；再判断该备选路径列表是否为空，如果为空，则执行步骤(3.3)；如果非空，则执行步骤(3.5)；

(3.3)、判断延伸链路集合extend_link_setflow_i是否包含了流量flowi的原路由路径route_pathflow_i中的所有链路，如果包含，则执行步骤(6)；否则执行步骤(3.4)；

(3.4)、从流量flowi的原路由路径route_pathflow_i减去延伸链路集合extend_link_setflow_i得到一个新链路集合，再从该新链路集合中选出利用率最高的链路linkmost_used，并将利用率最高的链路linkmost_used到拥塞链路的这段路径设置为新延伸链路，新延伸链路的源节点和目的节点设置为S'、T'，最后将利用率最高的链路linkmost_used加入延伸链路集合extend_link_setflow_i集合中，再执行步骤(3.2)；

(3.5)、从备选路径列表中选出可用带宽最大的备选路径pathmax_volumn，将流量flowi在延伸链路上的这段路由改为pathmax_volumn，并将流量flowi从拥塞链路的流量列表中删除，执行步骤(4)；

(4)、判断拥塞链路c_linkk上的拥塞是否消除，如果拥塞已经消除，则执行步骤(5)；否则执行步骤(6)；

(5)、判断拥塞链路列表中所有的拥塞链路是否完成遍历，如果是，则结束处理；否则c_linkk+1，再执行步骤(2)；

(6)、判断流量列表中所有流量是否遍历完成，如果没有遍历结束，则flowi+1，再执行步骤(3)；如果遍历结束，则执行步骤(7)；

(7)、判断拆分粒度g是否小于等于预设的拆分粒度上限gmax，如果满足，则执行步骤(8)，否则执行步骤(5)；

(8)、处理流量列表中的剩余流量；

(8.1)、遍历流量列表中的某一条剩余流量，查看其源、目的IP地址，选取范围较大的地址addresswide；

(8.2)、将addresswide地址划分成2split_index个网段并将该条剩余流量按照这些地址拆分成2split_index条细流；

(8.3)、在骨干网络边缘交换机的netflow采集器中设置，统计出这2split_index条流量的大小，并用这2split_index条流量替换流量列表中该条剩余流量；判断流量列表的剩余流量是否遍历完毕，如果遍历完毕，执行步骤(8.4)，否则执行步骤(8.1)；

(8.4)、拆分粒度g＝g+1，执行步骤(2.2)。

2.根据权利要求1所述的一种消除链路拥塞的骨干网络流量调度方法，其特征在于，所述的拥塞链路列表中包括：链路名称、链路编号、链路已用带宽、链路利用率和链路总带宽。

说明书

一种消除链路拥塞的骨干网络流量调度方法

技术领域

[0001] 本发明属于网络通信技术领域，更为具体地讲，涉及一种消除链路拥塞的骨干网络流量调度方法统。

背景技术

[0002] 随着计算机网络线路类型以及网络产品和技术的发展，在骨干网上进行流量控制的技术主要是DifferServ方式。

[0003] DifferServ方式即区分服务方式，区分服务方式具有无连接的特性，主要通过缓冲管理和优先级调度机制来实现，无需进行QoS协商和保留带宽等控制。由于IP网络的发展仍然是基于无连接的，区分服务方式与之相适应，更适合在大型IP网络中应用。

[0004] 在DiffServ方式中，业务流被划分为不同的区分服务类，一个的业务流的区分服务类是由IP包头中区分不同服务的字段(Different Service Code Point,DSCP)所表示。在实施DiffServ网络中，每一节点路由都会根据数据包的DSCP字段执行相应的PHB(Per Hop Behavior)行为，目前IETF已定义了三个标准的PHB:

[0005] 1.快速转发(Expedited Forwarding)：能够充分满足流量对带宽、延迟与丢包的要求，严格保证所承诺的QoS，主要用于低时延、抖动和丢包率的业务。

[0006] 2.保证转发(Assured Forwarding)：能够容忍流量速率在一定范围的波动，在没有超过最大网络带宽时可以保证数据转发，一旦发生网络阻塞，将根据不同的丢弃级别丢弃报文。

[0007] 3.尽力服务(Best Effort)：不提供任何的QoS保证，主要应用于对时延、抖动和丢包不敏感的业务。

[0008] 可以看出，DiffServ方式包含的业务级别，信息状态的数量少，因此具有较好的扩展性，目前是业界认同的IP骨干网QoS解决方案。

[0009] 骨干网流量控制方案总体来说技术比较简单，但是却不够灵活，虽然可以保证一些关键业务的传输质量，但是随着骨干网上业务流量类型的增加，也逐渐显现出一些不足，主要表现在以下几点：

[0010] 1.不能全局协调

[0011] 在传统IP网中，每个节点独立的执行流量控制策略，这是一种单节点，单链路的控制方式。当出现某些链路过载时，不能主动使用其他链路进行路由，而是选择丢包。这样即使其他路由有空闲的带宽资源，拥塞路由的流量也不会分担到空闲路由上，导致网络带宽资源没有充分利用。

[0012] 2.不能精细化控制

[0013] 在传统IP骨干网中，通常由聚合掩码表项匹配进行路由，在每个路由器上不能知道所有IP流的信息，不能主动的对汇聚流进行拆分，控制汇聚流中IP流的具体路由方式。例如，当两个节点之间需要4G的流量，而没有一条路径存在4G的剩余带宽，则这时会宣告请求失败，但其实可以将流量拆分为几条小流量需求的汇聚流，分别在多条路由上得到流量满足。

发明内容

[0014] 本发明的目的在于克服现有技术的不足，提供一种消除链路拥塞的骨干网络流量调度方法，对骨干网络流量实现全局协调，具有流控响应更快、流控目标更准确、拥塞缓解成功率更高等优点。

[0015] 为实现上述发明目的，本发明为一种消除链路拥塞的骨干网络流量调度方法，其特征在于，包括以下步骤：

[0016] (1)、根据网络反馈的拥塞链路信息，形成拥塞链路列表，遍历拥塞链路列表中的每条拥塞链路c_linkk，k＝1,2,…，再执行步骤(2)；

[0017] (2)、对拥塞链路c_linkk进行处理；

[0018] (2.1)、设置拥塞链路c_linkk的拆分粒度g，并初始化为0；

[0019] (2.2)、将拥塞链路c_linkk上的所有流量按从大到小排序，形成流量列表；

[0020] (2.3)遍历流量列表中的每条流量flowi，i＝1,2,...，再执行步骤(3)[0021] (3)、通过对交换机流表项的count字段进行统计，获知流量flowi的大小为sizeflow_i；再从路由信息数据库中检索，获取流量flowi的原路由路径为route_pathflow_i；

[0022] 设置流量flowi的延伸链路link_extendflow_i，用S、T表示延伸链路的源节点和目的节点；设置延伸链路集合extend_link_setflow_i；

[0023] (3.1)将流量flowi的延伸链路link_extendflow_i初始化为拥塞链路；将延伸链路集合extend_link_setflow_i初始化为拥塞链路；

[0024] (3.2)在S、T之间寻找跳数小于预设的jump_limit、可用带宽大于该流量flowi的大小sizeflow_i、且不经过延伸链路集合extend_link_setflow_i的所有链路作为备选路径，从而得到备选路径列表；再判断该备选路径列表是否为空，如果为空，则执行步骤(3.3)；如果非空，则执行步骤(3.5)；

[0025] (3.3)、判断延伸链路集合extend_link_setflow_i是否包含了流量flowi的原路由路径route_pathflow_i中的所有链路，如果包含，则执行步骤(6)；否则执行步骤(3.4)；

[0026] (3.4)、从流量flowi的原路由路径route_pathflow_i减去延伸链路集合extend_link_setflow_i得到一个新链路集合，再从该新链路集合中选出利用率最高的链路linkmost_used，并将利用率最高的链路linkmost_used到拥塞链路的这段路径设置为新延伸链路，新延伸链路的源节点和目的节点设置为S、T，最后将利用率最高的链路linkmost_used加入延伸链路集合extend_link_setflow_i集合中，再执行步骤(3.2)；

[0027] (3.5)、从备选路径列表中选出可用带宽最大的备选路径pathmax_volumn，将流量flowi在延伸链路上的这段路由改为pathmax_volumn，并将流量flowi从拥塞链路的流量列表中删除，执行步骤(4)；

[0028] (4)、判断拥塞链路c_linkk上的拥塞是否消除，如果拥塞已经消除，则执行步骤(5)；否则执行步骤(6)；

[0029] (5)、判断拥塞链路列表中所有的拥塞链路是否完成遍历，如果是，则结束处理；否则c_linkk+1，再执行步骤(2)；

[0030] (6)、判断流量列表中所有流量是否遍历完成，如果没有遍历结束，则flowi+1，再执行步骤(3)；如果遍历结束，则执行步骤(7)；

[0031] (7)、判断拆分粒度g是否小于等于预设的拆分粒度上限gmax，如果满足，则执行步骤(8)，否则执行步骤(5)；

[0032] (8)、处理流量列表中的剩余流量；

[0033] (8.1)、遍历流量列表中的某一条剩余流量，查看其源、目的IP地址，选取范围较大的地址addresswide；

[0034] (8 .2) 、将a dd re ss wid e 地址 划分成 2s pl it _i nd ex 个网 段并将该条剩余流量按照这些地址拆分成2split_index条细流；

[0035] (8.3、在骨干网络边缘交换机的netflow采集器中设置，统计出这2split_index条流量的大小，并用这2split_index条流量替换流量列表中该条剩余流量；判断流量列表的剩余流量是否遍历完毕，如果遍历完毕，执行步骤(8.4)，否则执行步骤(8.1)

[0036] (8.4)、拆分粒度g＝g+1，执行步骤(2.2)。

[0037] 本发明的发明目的是这样实现的：

[0038] 本发明一种消除链路拥塞的骨干网络流量调度方法，通过将原路由的拥塞部分转移到该拥塞部分的代替路径上，从而绕过拥塞链路。在具体针对某条拥塞链路，该拥塞链路上的一些流量会因为太大而找不到合适的备选路径，算法此时会暂时跳过这一条流量，处理下一条流量；当算法遍历完一遍该条拥塞链路上的流量，并且将能迁移出去的流量都迁移之后，链路的拥塞状态还未消除，算法就会对链路上剩余的所有汇聚流进行拆分，将一条较大的汇聚流拆分成几条较小的汇聚流，但最多达到拆分的最大条数限制，这样增加流量找到备选路径的几率，实现了拥塞链路的调整。

[0039] 同时，本发明一种消除链路拥塞的骨干网络流量调度方法还具有以下有益效果：

[0040] (1)、相较于传统的ECMP在固定路径之间进行流量均衡，本发明根据网络的拥塞情况，灵活选取网络拥塞部分的备选路径，对拥塞进行绕行，针对局部拥塞处理能力强。

[0041] (2)流量迁移时，多数情况直接对网络中的汇聚流进行调整，特殊情况下需要对汇聚流进行拆分，通过netflow的方式，获取较细粒度流量信息。算法整体对流信息粒度要求不高。

[0042] (3)在处理链路拥塞的时候，只需知道网络局部的流量和链路信息，所需信息少，收敛速度快，适应联通度高、信息量大的骨干网。

附图说明

[0043] 图1是本发明一种消除链路拥塞的骨干网络架构图；

[0044] 图2表示拥塞链路DG附近链路的利用率和可用带宽；

[0045] 图3是流量以DG为延伸链路寻找备选路径的示意图；

[0046] 图4是流量将“延伸链路”段的路由改道为备选路径后的流量状态图。

具体实施方式

[0047] 下面结合附图对本发明的具体实施方式进行描述，以便本领域的技术人员更好地理解本发明。需要特别提醒注意的是，在以下的描述中，当已知功能和设计的详细描述也许会淡化本发明的主要内容时，这些描述在这里将被忽略。

[0048] 实施例

[0049] 图1是本发明一种消除链路拥塞的骨干网络架构图。

[0050] 在本实施例中，如图1所示，在任意一个骨干网络中，字母代表网络节点，网络节点间被叉掉的链路代表拥塞链路，每个网络节点对应的网段如表1所示；

[0051] 表1是网络节点对应的网段；

[0052]网络节点 网段
A 10.0.0.0/8
B 20.0.0.0/8
C 30.0.0.0/8
D 40.0.0.0/8
E 50.0.0.0/8
F 50.0.0.0/8
G 70.0.0.0/8
H 80.0.0.0/8
I 90.0.0.0/8

[0053] 表1

[0054] 下面结合图1，对本发明一种消除链路拥塞的骨干网络流量调度方法进行详细说明，具体包括以下步骤：

[0055] S1、根据网络反馈的拥塞链路信息，形成拥塞链路列表，如表2所示，在拥塞链路表中包括：链路名称、链路编号、链路已用带宽、链路利用率和链路总带宽；遍历拥塞链路列表中的每条拥塞链路c_linkk，k＝1,2,...，再执行步骤S2；在本实施例中，有CF和DG两条拥塞链路；

[0056] 表2是拥塞链路表；

[0057]

[0058] 表2

[0059] S2、对拥塞链路c_linkk进行处理；

[0060] S2.1、设置拥塞链路c_linkk的拆分粒度g，并初始化为0；

[0061] S2.2、将拥塞链路c_linkk上的所有流量按从大到小排序，形成流量列表；

[0062] 在本实施例中，以拥塞链路DG为例，形成表3所示的流量列表；

[0063]

[0064]

[0065] 表3

[0066] S2.3、遍历流量列表中的每条流量flowi，i＝1,2,...，再执行步骤S3；

[0067] S3、通过对交换机流表项的count字段进行统计，获知流量flowi的大小为sizeflow_i；再从路由信息数据库中检索，获取流量flowi的原路由路径为route_pathflow_i；

[0068] 设置流量flowi的延伸链路link_extendflow_i，用S、T表示延伸链路的源节点和目的节点；设置延伸链路集合extend_link_setflow_i；

[0069] S3.1将流量flowi的延伸链路link_extendflow_i初始化为拥塞链路；将延伸链路集合extend_link_setflow_i初始化为拥塞链路；

[0070] 在本实施例中，以表格3中的流量flow15为例，通过初始化设置后，形成表4所示的初始化数据表。

[0071]流量编号 flow15
大小size 100
原路由路径route_path {A->C,C->D,D->G,G->H}
延伸链路link_extend D->G
S、T D、G
延伸链路集合extend_link_set {D->G}

[0072] 表4

[0073] S3.2在S、T之间寻找跳数小于预设的jump_limit、可用带宽大于该流量flowi的大小sizeflow_i、且不经过延伸链路集合extend_link_setflow_i的所有链路作为备选路径，从而得到备选路径列表；再判断该备选路径列表是否为空，如果为空，则执行步骤S3.3；如果非空，则执行步骤S3.5；

[0074] 在本实施例中，以flow15的初始化数据为例，如图2所示，拥塞链路DG附近链路的利用率和可用带宽的状况，虚线表示flow15在拓扑中原来的流经路径，以此为基础，flow15以DG为延伸链路，找到了延伸链路的备选路径D->E->G，形成了备选路径列表。列出表5所示的延伸链路的备选路径；

[0075]路径编号 路径包含链路
path1 {D->E,E->G}
… …

[0076] 表5

[0077] S3.3、判断延伸链路集合extend_link_setflow_i是否包含了流量flowi的原路由路径route_pathflow_i中的所有链路，如果包含，则执行步骤S6；否则执行步骤S3.4；

[0078] S3.4、从流量flowi的原路由路径route_pathflow_i减去延伸链路集合extend_link_setflow_i得到一个新链路集合，再从该新链路集合中选出利用率最高的链路linkmost_used，并将利用率最高的链路linkmost_used到拥塞链路的这段路径设置为新延伸链路，新延伸链路的源节点和目的节点设置为S、T，最后将利用率最高的链路linkmost_used加入延伸链路集合extend_link_setflow_i集合中，再执行步骤S3.2；

[0079] S3.5、从备选路径列表中选出可用带宽最大的备选路径pathmax_volumn，将流量flowi在延伸链路上的这段路由改为pathmax_volumn，并将流量flowi从拥塞链路的流量列表中删除，执行步骤S4；

[0080] 在本实施例中，如图3所示，flow15在以DG为延伸链路的迭代中，找到的满足条件的备选路径D->E->G。

[0081] S4、判断拥塞链路c_linkk上的拥塞是否消除，如果拥塞已经消除，则执行步骤S5；否则执行步骤S6；

[0082] 在本实施例中，如图4所示，flow15将“延伸链路”段的路由改道备选路径后的流量状态，和相关链路的利用率。从图4中可以看出被迁出流量的拥塞链路利用率从原来的92％下降到90％，备选路径上的链路的利用率则是有所提升。表明流量从拥塞部分转移到了空闲部分。

[0083] S5、判断拥塞链路列表中所有的拥塞链路是否完成遍历，如果是，则结束处理；否则c_linkk+1，再执行步骤S2；

[0084] S6、判断流量列表中所有流量是否遍历完成，如果没有遍历结束，则flowi+1，再执行步骤S3；如果遍历结束，则执行步骤S7；

[0085] S7、判断拆分粒度g是否小于等于预设的拆分粒度上限gmax，如果满足，则执行步骤S8，否则执行步骤S5；

[0086] S8、对流量列表中的每一条剩余流量进行处理；

[0087] S8.1、遍历流量列表中的某一条剩余流量，查看其源、目的IP地址，选取范围较大的地址addresswide；

[0088] S 8 .2 、将a d d r es s w id e 地 址 划分 成 2 sp l i t_ i n de x 个 网 段并将该条剩余流量按照这些地址拆分成2split_index条细流；

[0089] S8.3、在骨干网络边缘交换机的netflow采集器中设置，统计出这2split_index条流量的大小，并用这2split_index条流量替换流量列表中该条剩余流量；判断流量列表的剩余流量是否遍历完毕，如果遍历完毕，执行步骤S8.4，否则执行步骤S8.1；

[0090] S8.4、拆分粒度g＝g+1，执行步骤S2.2。

[0091] 尽管上面对本发明说明性的具体实施方式进行了描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。