通信网负载均衡仿真建模的探索

张晨光，陆晓萌

1.嘉善广播电视台，浙江嘉兴 314100

2.爱立信公司，上海 200136

第一次接触互连网是1997 年，当时在许多地方，互连网的主要用途还只是是收发电子邮件。现在互联网的用途已经不仅于此了。根据中国互连网信息中心2011 年的数据，80.9%用户的常用网络服务是即时通讯。其他服务（比如，高清可视电话，网上高清电影等）都因网络带宽的限制而无法实现。中国用户对互连网最不满意的地方就是速度太慢，特别是对于某些没有自己线路的运营商来说，提高网络传输质量，尤为重要。

提高网络通过量的办法有两种。第一种是增加网络带宽，提高交换设备的处理速度；第二种是采用新技术，使负载尽可能地分流到各条路径上，以便充分利用网络资源。

1 仿真的过程

网络仿真是当今检验新技术的一种常用方法。它使用代码与内存来构建网络的各个单元，这些单元的参数可以按照仿真需要设置。尤其重要的是仿真可以节约运行时间，在几天内仿真几年甚至几十年中可能发生的问题。我的主要任务是理论上论述负载平衡的可行性，并把负载平衡加入到仿真器中。

为了解释仿真器的运行方式，作者按照仿真时间顺序介绍一次最简化的仿真过程。

1）建立网络拓扑；

2）建立设置文件；

3）启动仿真器；

4）带宽和拓扑传向路由发生器；

5）每个源在随机时间点产生流量；

6）流量到达目的地以后被自动消除；

7）缓存状态、流量延时信息等被存入数据文件。

2 仿真器内核的基本构成

仿真器内核是由CNCL 库编写的，而作者重点编写的路由发生器是由LEDA 库编写的，之所以使用两个不同的C++库，是因为它们各有特点，然而使用不同的库在联合编译是会有一些问题。

CNCL 库是由德国Aachen 工业大学通信网教研室开发的C++库，这个库主要用于通信网软件的开发。它比较适合构造仿真器，因为它有产生随机数、事件驱动和统计等功能。

LEDA 是一个提供图形数据类型和算法的C++类库。LEDA提供了各种数据类型和算法。LEDA 提供了各种数据类型和算法。

2.1 网络拓扑的建立

使用网络教研室已有的Java 界面Simgui，可以画所需的网络拓扑。Simgui 提供了源、节点、目的地和缓冲等单元，这些单元的参数可以修改。把这些单元按照拓扑结构连接起来，就组成了一张图。这张图可以通过Export 命令存为*.cfg 文件最简单的一个*.cfg 文件如下：

在实际的参数设置中，可以直接在*.cfg 文件中修改。

图1 表示用LEDA 库建立的节点模型与用CNCL 库建立的节点模型的关系。

图1

3 路由发生器的实现

3.1 连接权重的计算

大部分的主干网使用传统的IP 路由协议，比如OSPF。这些协议都基于SPF 的。而SPF 的目标就是计算网络两个节点之间费用最小的路径。这个费用一般是这两个节点之间所有连接的权重(weight)之和,所以一个关键的问题是如何确定每一个连接的权重。

作者选择较为直观的可用带宽。可用带宽是指网络带宽减去正在使用和已经预定的带宽。各个连接的权重与可用带宽一般成反比。可用带宽越大，权重越小，新流量选择这一连接的可能性就越大。具体的计算方法是：

当-∞ ＜available_bandwidth ＜1bps 时

weight =2*CAPACITY-CAPACITY*available_bandwidth

当1bps ＜available_bandwidth ＜+∞时

weight =CAPACITY/ available_bandwidth

其中CAPACITY 是一个可以改变的常量，一般选择各个的连接带宽的公倍数，但是不应太大，以保证每条连接的初始值是一个较小的正整数。对于整个网络而言每分钟产生成千上万的流量，这些流量都会对网络的状况发生影响，从而使可用带宽不断发生变化。

3.2 最佳路径的建立和取消

每个连接的权重确定以后，下一个任务就是使用这些权重计算每一个流量要求的最佳路径。这种最佳路径的计算一般使用Dijkstra 算法。

从源到目的地的最优路径找到以后，路由发生器的下面的任务就是通知在最优路径上的所有节点为这一流量请求预留网络资源。按照正在使用和预留的带宽计算每个连接的可用带宽，并把结果存到一个连接数组中。同时，按照可用带宽计算各个连接的权重，以备新流量出现时，计算新的最优路径时使用。

这样，用户的流量就从源经过各个指定的中间节点向目的地传递。经过一定的延时以后，这一流量到达目的地。目的地检查这一流量的序列号，然后通知路由发生器这一流量已经结束。路由发生器采取相应的措施，释放占用的网络资源和某些被占用内存。

3.3 路由发生器与仿真器内核的接口

首先仿真器内核根据*.cfg 设置文件，建立各个源、节点和目的地，同时调用路由发生器的方法new_node(long obj_name,Rsobject *obj)，按照图1 的方式在路由发生器内部建立各个源、节点和目的地对象。然后，设置器开始把各个源、节点和目的地按照*.cfg 中关于网络拓扑的描述，建立基于CNCL 的库的各个连接，同时调用路由发生器的方法new_edge(long obj_from, long output_port, long obj_to, long input_port, double bandwidth)建立各个连接，并把节点的端口号通知路由发生器，以备将来使用。

当某个源对象有流量要求时，它就调用路由发生器的方法create_path, 为它计算最优路径，通知最优路径上所有节点为这一流量预留带宽。并为这一流量编号，根据这一统一编号，可以在路由发生器中找到这个流量的带宽和最优路径上所有节点的指针。当流量到达目的地以后，仿真器内核调用路由发生器的remove_path(long flow_number)。路由发生器利用这个统一编号读出带宽大小，从一个列表中依次读出最优路径上的节点，并通知各个节点释放已经占用的带宽。路由发生器除了与仿真器内核有接口外，还有一些用于统计仿真数据的接口函数、输出最优路径到文件和标准输出的接口函数等。

3.4 源的实现

源模型主要是描述各个用户的行为。每个用户在何时发送一个流量、流量的大小以及流量的持续时间都是随机的。如何产生统一的负载模型呢？下面介绍一种在本仿真器中使用的方法。

CNCL 数据库提供了较好的随机数类。先介绍一个基础随机数产生器Fibonacci。它是由一个称为种子（SEED）的整数作为启动数，不同的SEED 产生不同的随机序列。随机序列中的随机数是确定的，也就是说，只要SEED 不变，第一次启动时与第二次启动时产生的随机数序列完全一致。随机数应该尽可能地随机，以便正确反映现实世界。但是，用算法实现的随机数只能是伪随机数。也就是说它的随机序列具有一定的周期，第二个周期的随机数与第一个周期的随机数完全一致。一种好的随机数产生器应该在不过多占用内存的前提下，尽可能地使这种周期变大。Fibonacci 随机数产生器的周期是N=（2^32-1）*2^96。这一周期足够大，足以反映负载的随机性。

由此整个仿真器的工作方式以及数据的统计设计已经基本完成，可以在计算机上进行实际仿真，得出相应的实验结果，分析该结果可用对网络中的负载均衡有更加进一步的了解。

[1]Daniel O.Awduche, Angela Chiu, Anwar Elwalid, Indra Widjaja, Xipeng Xiao, A Framework for Internet Traffic Engineering, INTERNET-DRAFT, May 2000.

[2]Eric C.Rosen, Arun Viswanathan, RossCallon, Multi-protocol Label Switching Architecture, Internet Draft, August 1999.

[3]宛延闺.C++语言和面向对象程序设计.清华大学出版社，1997.

[4]刘红.应用于MPLS网络负载均衡的启发式自适应遗传算法研究，2003.