基于卡尔曼滤波的流量预测机制

贾 濡， 潘沭铭

(1.中国电子科学研究院，北京 100041;2.中国人民解放军66736部队， 北京 100144)

0 引 言

以IP为“细腰”的传统互联网存在着植根于原始设计思想的静态、僵化机制问题，造成网络资源利用率不合理、用户体验不佳等问题。

智慧协同网络(Smart Identifier NETwork/SINET)作为一种面向未来需求的全新型网络架构，集众家之所长，借鉴 “控制与数据分离”及“以信息内容为中心”的思想，采用基于标识的路由机制，并引入行为描述信息来实现内嵌于网络架构中的智慧性，使网络能够从根本上支持资源动态适配，实现网络资源优化利用。智慧协同网络核心思想是实现网络资源的优化适配，而“网络流量预测”则是实现资源适配的一种有效方法。本论文针对“如何实现网络流量预测”这一问题开展研究。

本论文在前期智慧协同网络研究基础上，设计实现流量预测机制，主要内容如下：第二章介绍了智慧协同网络当前研究进展以及本文研究相关的技术基础；第三章介绍了流量感知获取方法；第四章提出了基于卡尔曼滤波的流量预测算法；第五章在SINET原型系统中实现并验证了该流量预测结果的准确性；第六章对本文进行了总结。

1 研究背景

1.1 智慧协同网络当前研究进展

智慧协同网络当前主要研究成果及进展如下:

文献[1][2]分析了基于TCP/IP协议的传统互联网体系架构存在三种植根于原始设计思想的紧耦合，即：资源与位置紧耦合、控制与数据紧耦合、身份与位置紧耦合，并详细阐述了为彻底解决这三项紧耦合问题而设计的智慧协同网络体系架构，其“三层两域”架构模型纵向划分为智慧服务层、资源适配层和网络组件层，横向则采取划实体域及行为域的划分方法。

文献[3]进一步设计了智慧服务层中服务注册与解析机制，在“实体域”中使用服务标识来标记服务，“行为域”中引入服务行为描述信息(SBD/Service Behavior Description)述支持灵活的自定义设置，实现了用户、网络及服务三方信息交互，即除了承载服务需求信息外，还可以传递用户需求信息，从而使得网络能够通过追踪SBD信息，获知个体用户需求信息；文献[4]则针对网络组件层做进一步详细阐述。

文献[5]-[7]提出了智慧协同网络路由机制，其分为域间路由和域内路由，域间统一采用基于域间路径标识(PID/Path ID)的路由机制，域内路由机制由各自治域自主决定，相互独立，互不影响。为了实现与现有互联网的兼容及过渡，域内可采用IPv4、IPv6、MPLS等传统方式，也可采用类似域间的基于标识的路由机制。此外，为了提高安全性，文献[8][9]设计了不同的协商机制和变换周期来设置邻域之间的路径选择。

文献[10]则是将研究重点放在网络的“原生智慧性”上，设计了基于状态感知的域内资源适配机制，基于流量感知的域内智慧路径分配方法，以及网络能耗和协作缓存优化方法。本文的流量预测机制便是以文献[10]的研究成果作为研究基础开展。

1.2 本文研究基础

智慧协同网络融合了软件定义网络/SDN[11]“控制与数据分离”的思想，以及信息中心网络/ICN[12]“以信息内容为中心”的思想。它将网络划分为实体域及行为域，其实体域利用服务、组件、路径等实体标识来实现SD-ICN (Software Defined- Information Centric Networking)[12]机制的运行，而行为域则是基于行为描述信息来支持网络执行“智慧型”的资源适配，通过实体域与行为域的协同运行，将智慧性内嵌于网络架构，使网络能够从根本上支持资源动态适配，在构建网络的同时赋予网络“自我调节以适应变化”的能力。

智慧协同网络采用控制层与数据层分离的设计，如图1所示：

控制层：SINET资源适配层及以上，实现类似SDN控制器的功能，主要能实体是资源管理器RM(Resource Manager)；

数据层：网络组件层，实现类似SDN交换机的数据转发功能，主要功能实体是转发组件FN(Fowording Node)。此外，转发组件还能够支持数据层的网络状态感知、缓存、节能休眠等功能[11]；

资源适配层RM对网络组件层FN的指挥，是通智慧协同控制协议[10]实现的，该协议是在OpenFlow[12]协议上改进而来，同样能够支持网络状态感知功能。

图1 智慧协同网络架构模型

2 流量感知获取机制

由于智慧协同网络是一种以信息为中心(ICN)的网络，所有的资源信息都以“服务”的形式存在，与所有ICN网络设计一样，智慧协同网络中所有转发组件只有在收到服务请求后才能回送服务，而不会主动向包括RM在内的其他节点推送数据。所以，智慧协同网络中转发组件要向资源管理器汇报其收集到的流量信息时，只能通过请求的通信过程实现，因此，我们设计了如图2所示的流量感知信息获取机制，使转发组件实时监测链路的流量信息，并由本域的资源管理器集中获取全局的流量信息。

图2 感知获取消息格式

感知获取消息的设计基于SINET架构中请求消息(GET)和数据消息(Data)[10]，具体包括三种感知获取消息: GFH(Get-Fetch-Hello)、GFR(Get-Fetch-Request)和DFU(Data-Fetch-Update)，详细协议消息各字段详见文献[10]，本节只阐述与本文研究相关的字段。

在智慧协同网络自治域中，当链路状态出现变化时触发流量感知信息获取机制。资源管理器RM利用感知获取消息获取边界转发节点维护的流量信息，具体的交互过程如图3所示。

图3 感知信息的交互过程

RM可与FN之间互相通信感知获取消息实现对链路流量的感知。各转发组件R1、R2、R3、R4、R5分布式的感知自身状态，并将统计信息周期性的发送到RM上。以此来感知各FN之间的链路状态。

FN感知模块时刻监控端口状态，当端口的状态发生变化时，向RM发送GFH消息通知其某端口链路状态发生变化。该消息采用服务请求消息格式封装。即分类字段为0，NID字段填充汇报状态的FN，SID字段填充2表明其服务类型为状态通告GFH消息，SBD字段的填充内容为处于变化状态的组件端口或数据链路；

当RM收到GFH消息后，依据GFH消息封装的NID来发送GFR消息，同样采用服务请求消息格式封装，NID字段填充RM的NID，SID字段填充3，表明其服务类型为变化状态请求GFH消息；

当对应NID的网络组件收到GFR消息后，向RM返回DFU消息。此消息采用Data包格式封装，即分类字段为1，NID字段填充RM的NID，SID字段填充3，SBD字段部分填充所感知的流量信息。

基于以上感知机制的运行，RM可以方便的获得全局实时流量大小。RM可以据此做出流量传输路径的规划。

3 基于卡尔曼滤波的流量预测算法

基于卡尔曼滤波的流量预测机制依赖于资源管理器RM从边界转发组件FN获取流量信息。本节介绍了用于实现流量预测的卡尔曼滤波算法。

卡尔曼滤波(Kalman filtering)算法[13]是一种利用线性系统状态方程，通过系统输入输出观测数据，对系统状态进行最优估计的算法。该算法提供了一种以“最小化平方误差的均值[14]”进行优化的有效计算方法来估计一个过程的状态。

基于卡尔曼滤波的流量预测过程伪代码如下。

算法：基于卡尔曼滤波的流量预测评估算法

1: 定义卡尔曼滤波状态的数据结构

typedefstruct{

floatx; /*state*/

floatA; /*x(n)=A*x(n-1)+u(n),u(n)～N(0,q) */

floatH; /*z(n)=H*x(n)+w(n),w(n)～N(0,r) */

floatq; /*预测过程噪声协方差*/

floatr; /*测量噪声协方差 */

floatp; /* 估计误差协方差 */

floatgain;

}kalman1_state

2: 初始化

void kalman1_init (kalman1_state *state, float init_x, float init_p){

state->x = init_x;

state->p = init_p;

state->A = 1;

state->H = 1;

state->q = 2e2;//10e-6;

/*预测过程噪声协方差*/

state->r = 5e2;//10e-5;

/*测量噪声协方差*/

}

/* 1维卡尔曼滤波

/* @输入

state - Klaman filter structure /*卡尔曼滤波器结构*/

z_measure - Measure value /*估计值*/

/* @输出 * @返回值

Estimated result /*评估结果*/

3:floatkalman1_filter(kalman1_state*state,float_measure)

/* 预测 */

{state->x=state->A*state->x;

state->p=state->A*state->A*state->p+state->q;

/*p(n|n-1)=A^2*p(n-1|n-1)+q*/

/*测量*/

state->gain=state->p*state->H/

(state->p*state->H*state->H+state->r);

state->x=state->x+state->gain* (z_measurestate->H*state->x);

state->p= (1 -state->gain*state->H) *state->p;

returnstate->x;}

4: If component perception result has been update then:

/*流量感知模块中的流量信息有更新时 */

5: Update the inter-domain traffic metric which based on PIDs at current moment donate as M(k);

/*更新基于PID的实时域间流量矩阵 M(k) */

6: If the Kalman state is zero then:/*若状态值为0*/

7: Initialize the current traffic metric asλ(0|0)

/*初始化当前流量矩阵λ(0|0)*/

8: Initialize a priori estimate error covariance as P(0|0);

/*初始化当前的估计误差协方差P */

9: Predict next state’s trafficλ(1|0)=A*λ(0|0);

/* 预测下一状态流量*/

10: Predict next state’s a priori estimate error covariance

P(1|0)= A* P(0|0)*AT+Q;

/*初始化先验估计误差协方差预测下一个状态的流量*/

11: Initialize a priori estimate error covariance as

Predict next state’s trafficλ(1|0)=A*λ(0|0);

12: Predict next state’s a priori estimate error covariance

P(1|0)=A*P(0|0)*AT+Q;

/*预测下一状态先验估计误差协方差*/

13: Else the Kalman state is note zero;

14: Correct the Kalman Gain

Kg(k|k)=P(k|k-1)*H/(H*P(k|k-1)*HT+R)；

15: Correct link traffic at current moment

λ(k|k)=λ(k|k-1)+Kg(k|k)*(M(k)+H*λ(k|k-1))

/*调整当前时刻链路流量*/

16: Correct the a priori estimate error covariance:

P(k|k)= (1- Kg(k|k)* H ) * P(k|k-1);

/*修正先验估计误差协方差*/

17: Predict next state’s trafficλ(k+1|k)=A*λ(k|k)

18: Predict next state’s a priori estimate error covariance:

P(k+1|k)= A* P(k|k)*AT+Q ;

/*预测下一状态流量先验估计误差协方差*/

19: Else component perception result has not been update;

/*流量感知模块中的流量信息没有更新时 */

20: Return NULL;

21: End

4 系统测试

为了验证基于卡尔曼滤波的流量预测的准确性，本节在智慧协同网络SINET原型系统上完成了基于卡尔曼滤波的流量预测机制的实现，并测试了预测结果的准确性。

网络拓扑结构如图4所示。RM、FN、Client。server均采用linux 2.6.29.5操作系统，并运行智慧协同控制协议， Client及server基于CLICK[15]软件实现服务请求/数据包的收发[16]。

图4 原型系统拓扑

在智慧协同网络SINET原型系统上运行智慧协同控制协议[10]，用以支持资源管理器和转发组件间通信控制，同时资源管理器和转发组件间运行[10]中设计的智慧协同控制协议来实现数据转发层感知信息传递机制。在此基础上，利用流量感知机制以及流量预测机制实现智慧协同网络下遇见路径PID上的实时流量预测。

经测试，RM和FN之间的流量预测机制能够正常运行，通信流程符合设计方案，验证了基于卡尔曼滤波算法的流量预测机制在智慧协同网络中的可行性。

图5及图6所示为PID1、PID2标识链路上实际流量及预测流量实时对比。待系统运行稳定后，将FN4及FN5网卡上的实际流量与预测机制测算流量进行对比。从图5及图6可以看出预测流量与实际流量基本保持变化同步。

图5 PID1链路实际及预测流量对比

图6 PID2链路实际及预测流量对比

图7 PID1、PID2链路预测及实际流量误差对比

如图7所示为PID1、PID2标识链路上实际流量及预测流量实时误差情况，60分钟内两路共60个取样时间点中只有3个时刻误差超过20%，剔除掉异常点后的平均误差为5%。

当前软件定义网络中典型流量实时测算机制为OpenTM[17]机制，该方法在运行OpenFlow协议的SDN网络中，选取部分转发节点路由器，搜集其中流量统计，引接局部流信息至集中控制器controller)，然后测算局部网络流量矩阵。其误差情况与本文提出机制相当[18]。

综上所述，利用卡尔曼滤波算法预测出的PID1、PID2链路流量准确程度与当前软件定义网络中典型流量实时测算机制OpenTM[17]相当，即智慧协同网络架构下的流量预测机制可行。

5 结 语

本文针对“智慧协同网络控制层如何根据实时流量信息进行流量预测”开展研究。首先，介绍了基于感知获取消息的流量感知获取机制；然后以感知信息为输入，利用卡尔曼滤波算法计算下一状态的流量情况；其次，在SINET原型系统中实现流量预测机制，将预测流量与网卡上记录的实际流量作取样对比测试。测试结果分析可知：预测流量与实际流量平均误差约为5%，与现有SDN架构下典型流量测算机制准确性相当，并通过原型系统实现验证了该流量预测方法在智慧协同网络架构下的可行性。