论文部分内容阅读
随着计算机和通信网络技术的飞速发展,网络的规模越来越大,结构越来越复杂,应用越来越丰富,同时,网络的管理越来越困难。在网络管理中,人们意识到对一些重要的问题需要进行专门的研究,比如,网络流量的预测问题、网络拥塞及流量调控问题、网络故障诊断问题等。这些问题的有效解决,可以大大提高网络运行效率,改善网络质量和用户体验。因此,这类问题成为网络运营商和相关学术领域研究者共同关注的热点问题。 本文主要研究了网络流量预测问题、网络流量调控优化问题,以及基于日志挖掘的网络故障定位问题。围绕这三个问题,完成的主要研究工作及相关成果如下: 1.对于网络流量预测问题,本文将网络流量序列看作是随时间变化的信号序列,首次将经验模式分解(Empirical Mode Decomposition,EMD)方法用于流量预测,提出了EMD-MMP流量预测算法。首先将网络流量序列分解为一系列从高频到低频的本征模函数(Intrinsic Mode Functions,IMF)分量,然后对各分量分别进行预测。针对高频分量频率高、波动快、随机性强的特征,运用线性时间序列中的自回归滑动平均(Auto-Regressive and Moving Average,ARMA)方法设计了预测算法。为了降低过高频率分量的随机性,算法中采用了对若干个高频分量进行累加的方法。同时,针对低频分量波动平缓、变化趋势比较明显的特征,采用支持向量回归机(Support Vector Regression,SVR)方法进行预测。最后将各分量的预测结果累加获得原始流量的预测结果。通过使用网络流量数据进行仿真实验,验证了EMD-MMP算法的有效性和在预测精度方面的优越性。 2.对网络流量调控优化问题,按可分流情形和不可分流情形,分别建立了以传输费用最小为目标的最优化模型。对于可分流情形,建立了带多个时间段的多商品流线性规划模型,该模型可直接使用单纯形法或内点法等求解;而对于不可分流的情形,建立了非线性整数优化模型,对该模型进行了复杂度分析,并给出了一种基于优先贪婪策略的最大流量路径选择算法(PG-MFRS)来求解问题的近似解。仿真结果表明此算法具有复杂度低,易于计算的特点,并且求得的近似解具有较高的精度。 3.针对大规模网络路由日志的故障定位与关键信息提取问题,提出了一种类别-频率比(CFR)算法来确定故障时间点。该算法首先将原始日志进行预处理,得到规范型日志,然后运用N-Gram方法将日志转化为向量,运用层次聚类思想将日志分类,从而得到日志事件矩阵,并计算出CFR值来确定出可疑的故障时间点。为了进一步对故障进行确认,提出一种基于Top-m均值的kNN-TM算法用于提取关键日志消息;对于具有关联模式的日志,设计了一种基于频繁项挖掘的算法来提取频繁日志模式。将所提取的关键日志消息和频繁日志模式联合使用,可用于确定故障时间和进行根因分析。对故障日志数据的仿真计算表明所提出的上述系列算法有很高的准确度,可大大提高故障处理效率。