负载均衡技术在合法监听中的应用

孔 玲，赵永祥

（北京交通大学 电子信息工程学院，北京 100044）

为了满足国家执法机构的有关要求和用户提出的需求，运营商和设备制造商在通讯网络中引入了合法监听技术。

合法监听技术主要通过国家的授权执法机构根据用户的监听标识向通讯网络中的各网元进行布控，然后各布控网元收集该用户的相关通讯信息和通讯内容，并上报给执法机构，执法机构再在反馈的消息中选择需要的信息进行分析和利用，这样不但可以保证用户信息的保密性又满足了国家执法机构对通讯信息的可控性和可知性的要求[1~2]。

监控网络中的流量对确保网络正常运行至关重要, 有报告指出，网络中的流量几乎每两年增加一倍[3]。这无疑大大增加了每个监听设备的任务量。现考虑用多核路由器实现监听功能，网络中每条流经过路由器最终到达目的端，把每个路由器看成一个监控点，由于一条流可能流经多个路由器和流量到达的随机性，如何在网络中分配每个路由器的监听任务，避免有的节点超负荷工作，而有的节点长期处于空闲状态，成为我们研究的重点。

1 相关研究

一般情况，在流级别的基础上，有两种原则来决定哪个节点来执行监控任务。

1.1 先到原则

把数据流最先到达的节点作为监控该条流的监控点，如图1中，f low1最先经过moni tor 0（以下简称m0），那么就让m0监控f l ow1，m1，m2空闲。这样做的好处是节省了决定的时间，然而带来的弊端也是明显的，若很多条流到达的第1个节点均是m0，势必导致m0任务超重，而其他节点却空闲的情况。

1.2 最闲原则

分析数据流所经过的所有节点，选择一个当前负载最小的节点来监控该条流。这样的分配方式只是简单的平衡了各节点的负载，但由于流量的随机性，采用此方法并不理想。同样，在图1中，f low1的速率为10 packet/s，在m0 ，m1，m2均空闲的前提下，随机选择m0监听f low1，则m0的负载变为10。f low2的速率为1 000 packet/s，此时m0的负载为10，而m1，m3，m4，m6均为0，那么在后面4个节点中随机选择m1监听f low2，则m1的负载变为1 000。从整个网络来看，f low1都经过m0，m1，但这2个节点的负载却相差很大，并没有到达很好的均衡负载的目的。

图1 数据流分别以不同速率流经监控节点

以上2种原则，都是在流级的基础上分配任务的，但是实际网络中流量分布不均匀，即使流分配均匀了，这些方法分配在不同节点上的监听负载是不均匀的。例如，3个流，速率分别为1 000，10，10，这3个流分别分配给3个节点监听。那么负责第1个流的节点负载要远远大于其它2个节点。根据这个特点，本文提出均值法，一种在分组的基础上分配监听任务的算法，使每个节点的负载尽可能均衡。

2 算法阐述

2.1 基本思想

首先假定数据流经过的最后1个节点监听该流，从流量最大的数据流开始，总流量除以节点总个数所得到的平均值就是该流路上每个节点所应承担的负载量，把假定在最后一个节点上的任务往前分担给流路上的其他节点。按此原则依次迭代优化每条数据流。还是在图1中，f low1，f low2的流量分别是10 packet/s，1 000 packet/s，那么首先优化f low2，在该流路上，均值为1 000/5=200，则应把假定在m5上的负载平分给前面的节点，使该流路的上每个节点的任务量均为200。接着优化f low1，由于m0 ，m1的负载变为200，均比m2的负载10大，所以无需再把m2上的负载分担给m0，m1。作上述处理后，避免了最闲原则中，f low1都经过m0，m1，但这两个节点的负载却相差很大的情况，从整个网络来看，尽管不同数据流之间的流量差异度很大，节点间的负载却没有相差很多。

2.2 均值法算法

（1）在初始化中都假设让数据流经过的最后一个节点监听该流，这样做的目的是确保每条流都有一个节点对其监听。

（2）首先找出网络中流量最大的数据流，将其最后一个节点的任务量往前分配给该流路上的其余节点。接着找出流量次大的数据流，做同样操作。

（3）由于知道数据流经过的节点数，就可以通过平均计算得出该条流上每个节点应该承担的监听量；若流路上最后一个节点的任务量比前面节点的都小，该流路不做处理；若最后一个节点的上游某节点的监听任务量比计算出的均值还大，代表该上游节点本身任务已经很重，不适合分担其任务，此时不考虑该上游节点，重新计算均值；若最后一个节点的任务量比计算出来的均值大，代表该节点的负载很重，不适合分担该流路的监听任务，把最初假设给它的任务量重新均分到它上游的其余节点。

（4）依次迭代，直至把网络中的所有数据流都做上述处理。

均值法是在分组的基础上平衡数据流上各个节点的负载，一个节点不再是唯一的监听某条数据流的节点，其他节点空闲，而是该数据流所流经的所有节点都监听该条流，只不过每个节点所分配到的任务量不同。

3 实验仿真

以图1 为网络模型，假定f low1，f low2，fow3的流量分别是300 packet/s，600 packet/s，1 200 packet/s，按3种算法得出网络中各个节点的负载如图2。

从图2中可以看出，先到原则下节点0和1处于忙碌状态，而其余节点均空闲。最闲原则也存在同样问题，9个监听节点有6个处于空闲状态。由这两种算法得到的各节点的负载非常不均衡。而采用均值法的曲线最为平缓，虽然网络中各个节点的负载不完全一样，但相互间的差异度不大，很好地避免了某些节点分配到的监听任务超载，而另一些节点却轻载的现象。

图2 流量预先假定时3种算法的节点负载分布图

下面以实际的网络拓扑图为例，分析一种更普遍的情况。

图3为澳洲骨干网络拓扑图，以此为基础，从中选取7个点组成的网络结构作为仿真模型，如图4。

图4 网络结构图

图4中任意2个节点间存在一条数据流，则应有21条流，其中f low =f i j(1≤i＜j,i＜j)。随机输入21个值在0到1 000的随机数代表21条数据流的流量，按3种算法得到网络中各节点的负载如表1。

表1 网络中各节点的负载

图5 流量随机到达时3种算法的负载分布图

从图5中可以清晰看出，当流量随机到达时，采用先到原则和最闲原则进行流量分配，图中的曲线波动剧烈，在先到原则中，节点3负载高达2 800，而节点7负载为0。网络中各节点的负载量相差很大；而采用均值法，图中的曲线波动不大，各节点的负载均在1 500左右，节点间的负载得到了有效的平衡，避免了按前2个算法出现的某些节点超负荷忙碌，而某些节点长期处于空闲状态的情况。节点3、4作为网络的中心节点，负载相对其它边缘节点略高，属正常现象。一般而言，数据流经过的节点越多，网络中节点连接越紧密，均值法达到的均衡效果越好。

4 结束语

均值法首先假定每条数据流流经的最后一个节点监听该流，找出流量最大的数据流，再把该流最后一个节点的负载往它所监听的流路上的其他节点上分担，依次迭代，最终达到网络中所有节点的负载均衡。该算法经过仿真，与另外2种方法比较，显示出了很好的均衡性能。接下来的工作重点是在更为复杂的网络拓扑环境下，考虑节点有可能发生故障，在这样的前提下验证均值法的性能，增加其容错功能。

[1] 王斌斌. WiMax网络中合法监听业务的实现[D]. 上海：复旦大学软件学院，2008.

[2] 魏 亮. 浅析网络与信息安全应用需求和研究现状[EB/OL].http://www.edu.cn/20060703/3198117.Shtm l.2007-07-03.

[3] Cisco Systems.Approaching the zettabyte era. [EB/OL].http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white_paper_cll-481374.pdf”.June 2008.