使用改进K-SVD的网络多媒体业务QoS类识别

王再见 董育宁 汤萍萍 杨凌云 张 晖



使用改进K-SVD的网络多媒体业务QoS类识别

王再见*①董育宁②汤萍萍①②杨凌云①②张 晖②

①(安徽师范大学物理与电子信息学院 芜湖 241000)②(南京邮电大学通信与信息工程学院 南京 210003)

该文基于网络多媒体业务QoS(Quality of Service)特征特点，提出网络业务QoS类识别算法。探索了新的多媒体业务QoS类划分模式，在QoS分类的基础上，可以通过将具有相同或相似QoS需求特征的业务流聚集生成聚集流。聚集流划分使用较少的QoS特征，借助聚集流可以在合理的粒度上区分多媒体业务。该文从QoS特征出发分析了聚集流识别的特点，利用网络多媒体业务典型QoS特征的稀疏性，使用改进K-SVD(Kernel Singular Value Decomposition)进行字典学习，实现网络多媒体业务QoS类识别。实验结果表明，该文算法比现有方法具有更高的QoS类识别准确性。

异构网络；网络多媒体；QoS；稀疏表示；业务流识别；字典训练

1 引言

目前典型的网络业务识别包括：基于贝叶斯网络[14]、基于HMM (Hidden Markov Model)[15]和基于支持向量机(Support Vector Machine, SVM)[16]的业务识别算法。上述业务流识别/分类算法针对特定的业务或协议，不适合基于QoS类的区分。受启发于文献[17,18]，本文提出一种基于模版的K-SVD 网络多媒体业务QoS类识别算法。算法采用K-SVD高效地解决优化问题，在字典学习过程中利用稀疏码(Sparse Coding -SC)学习字典，降低特征的维度，提高识别准确度。

本文其余的内容安排如下：第2节深入分析QoS典型特征，并选择新的特征，第3节给出新的QoS类定义，第4节详细描述基于修正K-SVD的网络业务QoS类识别框架，第5节是实验结果和分析，最后是结论。

2 典型业务QoS相关特征分析与选择

由于目前尚未发现将不同多媒体业务按QoS类别划分的数据库，本文使用Wireshark[19]在校园环境中捕获目前网络中流行的多媒体业务作为基本数据集，结合统计工具针对不同特性展开深入分析。部分特征统计信息如表1所示。

为了更直观地理解，本文选取归化后的上行/下行链路带宽对数值显示在图1中(其中横坐标是下行链路归化带宽对数，纵坐标是下行链路归化带宽对数)。由图1可见，整个点的分布可明显地划分为6个区域。分析表明，区域1由广播/多播视频会议、可视电话和在线视频组成，它们采用广播或多播模式；区域2由BBC 和CCTV网站视频组成，它们采用HTTP模式传输视频内容；区域3由Xunlei、 BitTorrent 和Emule组成，它们基于P2P模式提供分享视频服务，不过上行数据较少，下行数据较大，从本地站点看，似乎类似于支付少量费用的交易行为；区域4由Sopcast, TVAnt, Skype, VoD, PPlive, Coolstreaming, SinaLive, PPStream 和PPMate业务组成，它们也采用P2P模式，与区域3中的业务相比，上行数据较大，从行为上看，像以物易物的交易行为；区域5由ICQ, QQ 和MSN组成，这类型业务共同的特点是具有很强的交互性；区域6由多种在线游戏组成，这类业务的上/下行业务数据量都很小(在启动前业务已预装了很多数据，比如电子地图等)，游戏中玩家主要是提交指令，大量的计算由游戏服务器和本地客户机完成。

3 多媒体业务的QoS类定义

尽管目前存在的典型多媒体业务数量庞大，由图1中不同区域的业务分布，似乎可以依据相似的QoS特征划分为数目较少的QoS类别。本文依据在图1中6个区域，概括地划分为6类：广播视频 (Broadcast Video, BDV)、网页视频(Web Video, WV)、购买型视频(Trade Style Video, TSV)、以物易物型视频(Barter Style Video, BSV)、交互视频(Interactive Video, IV)和游戏类(Game Class, GC)。

这6种QoS类上/下行归化速率值分布如图2所示，其相应的对应关系见表2。由图2(a)可见6种QoS类上/下行归化速率值跨度较大，为了显示得更加清晰，我们将其中几个距离较近的QoS类分布用子图画出。由图2(b)可见，BDV与WV距离明显。图2(c)为TSV, BSV和IV 3个类别的上/下行归化速率值分布示意图，由图可见3类业务分布区域相对集中。图2(d)为WV, TSV和GC 3个类别的上/下行归化速率值分布示意图，GC类别区分明显，WV和TSV虽相距较近，但也有差异。

图1 所有业务上/下行归化速率对数值分布

表1 Youku video部分统计信息示例

图2 6种QoS类上/下行归化速率值分布

表2新QoS类定义

区域聚集流类具体业务例子下行速率上行速率其它描述 1广播视频(BDV)广播视频会议、可视电话、在线视频等业务中小上/下行速率分布较密集、比值较小 2网页视频(WV)BBC, CCTV等网页视频业务大较小上/下行速率分布的跨度最大、比值较小 3购买型视频(TSV)Xunlei, BitTorrent, Emule, Fileguri电驴等视频业务较大中上/下行速率分布的跨度较大，比值居中 4以物易物型视频(BSV)电视蚂蚁、Sopcast, Skype, PPStream, PPlive, PPMate等视频业务较大大上行速率分布的跨度最大，下行速率较稳定，上/下行速率的比值分散 5交互视频(IV)QQ, MSN等视频业务中中上/下行速率分布较密集，上/下行速率值相近 6游戏类(GC)多人网络交互游戏等业务小小上/下行速率分布较分散，上/下行速率值都较小

BDV类所属业务上/下行速率的特点是分布较集中，产生的数据总量不大。WV类业务常由HTTP服务器提供，通过嵌入在网页中的对象浏览。该模式下每个链接仅仅处理一个请求。由于用户请求业务是只需要少量的指令，且不用向别的用户提供业务内容，HTTP服务器收到请求后持续传输视频内容，内容越大传输的就越多。网页视频用户只要传输少量请求信息，服务器就会源源不断地发送视频内容，类似视频常常是电影、电视剧等，数据量较大，由于该类视频容量差异较大，所以对下行速率需求的跨度较大。

TSV类业务常常同时启动多个TCP链接，同时为多个P2P节点双向传输数据。多个任务常常同时执行，有较长的传输时间。该类业务常采用P2P模式，在下载资源的同时上传自身资源，不过上传的数据较少。BSV 类业务具有典型的P2P实时业务特征，此类业务节点在接收数据的同时也向其它节点提供数据。该类业务能通过使用变速率方式保证QoS以满足用户体验质量。IV类业务用户交互过程中等待时间不易过长，业务对延迟时间敏感。数据是双向对称传输，上/下行速率斜率的变化范围很小，反映该类型业务特征分布稳定。

GC 类业务既可能采用C/S模式也可能采用混合P2P模式，不同类型的业务虽然特征不尽相同，但在上/下行速率需求上具有一致性。该类由于大量计算由服务器和本地客户端完成，服务器只是向玩家提供计算结果，而玩家只需向服务器传输指令和要求，大量场景和视频画面在本地生成，需要传输的数据量较少。

4 基于修正K-SVD的网络业务QoS类识别框架

基于修正K-SVD的网络业务QoS类识别算法流程可划分为两个模块(图3)：特征处理模块和稀疏表示模块。

(1)特征处理模块：

(a)获取训练数据集合。捕获流行的23种多媒体业务作为基本数据集。

(b)特征提取。本文基于Wireshark获取DSCP (DiffServ Code Point)值、包到达绝/相对时间、源/目的IP地址、源/目的端口、协议、包大小、累积字节数和包详细描述等60种属性，并针对采集到的数据进行预处理。选取对应特征出现的最大值归化相应特征的全部数据，用统计后的相对值区分不同业务类型，具体的归化公式如式(1)：

这里， ,为数据集业务总数，取值为1时表示上行数据，取值为2时表示下行数据，为业务的实际取值，为其归化后的取值。

(c)尺度不变特征变换(Scale-Invariant Feature Transform, SIFT)。为了降低网络噪声对QoS参数取值的影响，本文对提取后的特征用SIFT描述子刻画，本质是在不同的尺度空间上查找特征关键点，并计算出方向。实现步骤如下：(i)尺度空间极值检测；(ii)确定每个候选位置和尺度；(iii)基于局部的梯度方向，分配给每个关键点位置一个或多个方向；(iv)在每个关键点周围的邻域内，在选定的尺度上测量局部的梯度，并将这些梯度变换成一种表示，允许比较大的局部形状的变形。

基于文献[5]，QoS类的稀疏表示问题可以通过求解下面用于字典重构的新目标函数完成。

(3)基于修正K-SVD的网络业务QoS类识别步骤如下：

步骤1 依据聚类结果，针对每个模板业务类别，选取同类别聚集流业务共同作为模版集；

步骤2 基于文献[5]，以模板业务作为检测业务，通过径向基函数(Radial Basis Function-RBF)，计算检测业务和参考集业务的相似度；

步骤3 基于文献[5]，生成业务的最终表示以用于分类；

步骤4 用线性SVM作为分类器进行识别。

5 实验结果与分析

表3实验配置参数

模板集大小字典大小稀疏度 2010018

由图4可见，本文方法在所有方法中识别准确率最好。这是由于Naïve Bayes, HMM和SVM方法需要学习，其识别性能受学习阶段的训练数据集影响，过于依赖特定的特征，造成相同QoS类别中的不同业务识别效果并不一样[17]。K-NN算法是一种在分类过程中实现学习的监督分类方法，虽然没有单独的学习阶段，但由于该算法只计算“最近的”邻居样本，在分类过程中识别性能同样受训练集样本影响，尤其当某一业务类别的样本量很大时，数量并不能影响运行结果。而在QoS类区分中，属于不同QoS类的业务可能使用相同的协议，如BDV、TSV和BSV都可能采用P2P模式；且属于相同QoS类别的业务也可能采用不同的协议，如GC既可以使用P2P也可以用C/S模式。网络动态本质更加剧了业务QoS特征的波动，给准确依赖特定模式识别业务所属QoS类别造成困难。不同业务识别误差的存在降低了Naïve Bayes, HMM, SVM和K-NN在识别QoS 类时的整体效果。例如，BitTorrent和eDonkey都属于TSV类别，但是Naïve Bayes对BitTorrent有更好的识别效果，而识别eDonkey业务的效果较差；SVM虽然对BitTorrent和eDonkey业务有好的识别效果，但识别PPlive业务的效果较差；HMM可以较好地识别PPStream，但是识别Sopcast的效果不佳。类似的情况在K-NN中同样存在。

当上述典型算法用于区分QoS类时，识别效果差的业务会降低算法整体的识别效果。如IV中业务的特征分布较为集中，所以识别准确度较高，但由于典型分类方法常把其看作其它类型的P2P业务(如BSV中的业务)，部分降低了区分准确度；GC类业务在5种分类方法中都有较高的识别准确度，这是由于游戏业务在上/下行速率需求特征上与其它5类业务的区别较大。也从侧面证明游戏类业务应该单独划分为一个QoS类别。本文方法所选取的上/下行速率较好地反映了多媒体业务QoS的本质特征，满足QoS类区分的4个基本要求，有利于提高多媒体业务QoS类区分性能。

图5-图7给出了5种方法在6种QoS类型业务在精确率、召回率和F1-测度值指标上的对比。由图5中可见，本文方法在精确率上明显高于其它4种典型区分方法，这是由于本文算法选取的特征具有较好的鲁棒性，降低了网络动态性所带来的特征分散性所造成的影响，提高了区分的精确性。这在BDV, TSV, BSV和WV业务的区分中尤为明显。而典型业务区分方法由于对特征分布的变化考虑不足，造成误判，增大FP(False Positives)值，从而导致精确性降低。比如，区分WV和TSV业务时，则有较多WV业务被区分为TSV业务，同时也有TSV业务被区分为WV业务。同理，本文方法在召回率(图6)上也有较明显的改善，综合了精确率和召回率的结果F1-测度值也较高，这也说明实验结果比较理想。尤其值得注意的是，虽然5种分类方法对GC类业务识别精确率一致，但Naïve Bayes, HMM, SVM 和K-NN方法中，部分QoS区分特征过于分散的业务被区分为其它种类业务，导致在召回率和F1-测度值指标上低于本文方法。

图4 业务识别方法在识别准确度上的对比

图5 5种方法在精确率指标上的对比

图6 5种方法在召回率指标上的对比

图7 5种方法在F1-测度值指标上的对比

6 结论

本文首先分析了目前典型QoS模型和业务识别方法中使用的区分特征，介绍了典型多媒体业务QoS特征研究的最新进展和典型业务流识别算法，研究了多媒体业务典型QoS特征的稀疏性。依据新选择QoS特征的显著差异定义了新的QoS类，并与现有QoS分类进行了对比。然后从QoS特征出发分析了网络业务QoS类识别的特点，结合多媒体业务典型QoS特征的局部性所带来的稀疏性，针对聚集流的区分，基于模版改进K-SVD进行字典学习，完成业务的稀疏表示，实现准确高效的QoS类识别。最后给出了与典型识别方法的对比结果。

[1] 王再见, 董育宁, 张晖, 等. 一种异构网络多媒体业务QoS类弹性映射方法[J]. 电子与信息学报, 2013, 35(3): 709-714. doi: 10.3724/SP.J.1146.2012.00890.

WANG Zaijian, DONG Yuning, ZHANG Hui,. An elastic QoS class mapping method for multimedia traffic in heterogeneous wireless networks[J].&, 2013, 35(3): 709-714. doi: 10.3724/ SP.J.1146.2012.00890.

[2] 王再见, 董育宁, 张晖, 等. 一种基于改进隐马尔可夫的多媒体业务分类算法[J]. 电子与信息学报, 2015, 37(2): 499-503. doi: 10.11999/JEIT140340.

WANG Zaijian, DONG Yuning, ZHANG Hui,. A multimedia traffic classification method based on improved hidden Markov model[J].&, 2015, 37(2): 499-503. doi: 10.11999 /JEIT140340.

[3] 董育宁, 王再见, 房曙光, 等. 多媒体通信业务流识别与分类方法综述[J]. 南京邮电大学学报(自然科学版), 2013, 33(3): 35-44.

DONG Yuning, WANG Zaijian, FANG Shuguang,. Survey of methods for traffic identification and classification in multimedia communications[J].(), 2013, 33(3): 35-44.

[4] WANG Zaijian, DONG Yuning, and WANG Xinheng. A dynamic service class mapping scheme for different QoS domains using flow aggregation[J]., 2015, 9(4): 1299-1310. doi: 10.1109/JSYST.2014.2351825.

[5] WANG Zaijian, DONG Yuning, SHI Haixian,. Internet video traffic classification using QoS features[C]. 2016 the International Workshop on Computing, Networking and Communications (CNC), Hawaii, USA, 2016: 1-6. doi: 10.1109/ICCNC.2016.7440599.

[6] MUHAMMAD M, GIAMBENE G, and COLA T. QoS Support in SGD-based high throughput satellite networks[J]., 2016, 15(12): 847-849. doi: 10.1109/TWC.2016.2615618.

[7] KAZEMI R, BOLOURSAZ M, SEYED M E,. Capacity bounds and detection schemes for data over voice[J]., 2016, 65(11): 8964-8977. doi: 10.1109/TVT.2016.2519926.

[8] PRASETYA S, RAHMAT B, and SUSANTO E. Quality of service improvement with 802.11e EDCA scheme using enhanced adaptive contention window algorithm[C]. 2015 IEEE International Conference on Communication, Networks and Satellite (COMNESTAT), Bandung, Indonesia, 2015: 80-85. doi: 10.1109/COMNETSAT.2015.7434292.

[9] FENG Kaiten, SU Wunci, and CHEN Chunyu. Comprehensive performance analysis and sleep window determination for IEEE 802.16 broadband wireless networks [J]., 2016, 15(1): 74-91. doi: 10.1109/TMC.2015.2409881.

[10] SUZNJEVIC M and MATIJASEVIC M. Trends in evolution of the network traffic of massively multiplayer online role-playing games[C]. 2015 13th International Conference on Telecommunications (ConTEL), Pirsa, Australia, 2015: 1-8. doi: 10.1109/ConTEL.2015.7231199.

[11] MARKOVICH N and KRIEGER U. Statistical analysis and modeling of peer-to-peer multimedia traffic[J]. LNCS, 2011, 5233: 70-97. doi: https://doi.org/10.1007/978-3-642-02742- 0_4.

[12] LIU Feng and LI Zhitang. A measurement and modeling study of P2P IPTV applications[C]. 2008 International Conference on Computational Intelligence and Security, CIS,08, Suzhou, China, 2008: 114-119. doi: 10.1109/CIS.2008. 112.

[13] FARAHBAKHSH R, CRESPI N, CUEVAS Á,. Understanding the evolution of multimedia content in the internet through bittorrent glasses[J]., 2013, 27(6): 80-88. doi: 10.1109/MNET.2013.6678931.

[14] ZHANG Jun, CHEN Chao, XIANG Yang,. Internet traffic classification by aggregating correlated Naive Bayes predictions[J]., 2013, 8(1): 5-15. doi: 10.1109/TIFS.2012. 2223675.

[15] MAHESHWARI S, MAHAPATRA S, KUMAR C,. A joint parametric prediction model for wireless internet traffic using Hidden Markov Model[J]., 2013, 19(6): 1171-1185. doi: 10.1007/s11276-012- 0525-1.

[16] JING Ning, YANG Ming, CHENG Shaoyin,. An efficient SVM-based method for multi-class network traffic classification[C]. 2011 IEEE 30th International Performance Computing and Communications Conference (IPCCC), Orland, Florida, USA, 2011: 1-8. doi: 10.1109/PCCC.2011. 6108074.

[17] FINSTERBUSCH M, RICHTER C, ROCHA E,. Asurvey of payload-based traffic classification approaches[J].&, 2014, 16(2): 1135-1156. doi: 10.1109/SURV.2013.100613.00161.

[18] LI Qun, ZHANG Honggang, GUO Jun,. Reference-based scheme combined with K-SVD for scene image categorization [J]., 2013, 20(1): 67-70. doi: 10.1109/LSP.2012.2228852.

[19] GOLD S. Hacking on the hoof[J]., 2012, 7(3): 80-83. doi: 10.1049/et.2012.0313.

[20] XU Yanbo, SIOHAN O, SIMCHA D,. Exemplar-based large vocabulary speech recognition using k-nearest neighbors[C]. 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Queensland, Australia, 2015: 5167-5171. doi: 10.1109/ICASSP.2015.7178956.

[21] ZHANG Jun, CHEN Chao, XIANG Yang,. Classification of correlated Internet traffic flows[C]. 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), Liverpool, England, UK, 2012: 490-496. doi: 10.1109/TrustCom.2012. 105.

王再见： 男，1980年生，博士，副教授，研究方向为无线多媒体通信、异构网络端到端QoS保证技术、多媒体大数据.

董育宁： 男，1955年生，博士生导师，教授，研究方向为多媒体通信与信息处理.

汤萍萍： 女，1981年生，博士生，讲师，研究方向为多媒体通信与信息处理.

Network Multimedia QoS Class Recognition Based on Improved K-SVD

WANG Zaijian①DONG Yuning②TANG Pingping①②YANG Lingyun①②ZHANG Hui②

①(,,241000,)②(,,210003,)

According to QoS characteristics of network multimedia service, this paper proposes a algorithm of network multimedia QoS class recognition. This paper studies new multimedia traffic QoS class division mode. According to new QoS classes defined, Flow Aggregation (FA) can be formed by gathering multimedia traffic flows with similar QoS characteristics. Network multimedia QoS class recognition prefers fewer QoS features by FA, and it is possible to divide network multimedia traffics in suitable granularity based on FA. This paper analyzes the property of FA recognition from QoS perspective, uses improved K-SVD (Kernel Singular Value Decomposition) to learn dictionary by using the sparse representation of typical QoS characteristics of network multimedia traffics, and presents a network multimedia QoS class recognition method. Experiment results show that the proposed recognition method can achieve more accurate QoS class recognition than previous methods.

Heterogeneous networks; Network multimedia traffic; Quality of Service (QoS); Sparse representation; Traffic recognition; Dictionary learning

TP393

A

1009-5896(2017)12-3023-07

10.11999/JEIT170133

2017-02-17；

2017-10-01；

2017-10-27

通信作者：王再见 wangzaijian@ustc.edu

国家自然科学基金(61401004,61271233, 61471203), 2016年安徽省高校领军人才引进与培育计划项目(gxfxZD2016013)，安徽师范大学博士科研启动基金(2016XJJ129)

: The National Natural Science Foundation of China (61401004, 61271233, 61471203), The Plan of Introduction and Cultivation of University Leading Talents in Anhui (gxfxZD2016013), The Startup Project of Anhui Normal University Doctor Scientific Research (2016XJJ129)

1)http://skype.gmw.cn/

2)http://iptv.cntv.cn/

3)PPLive是一款互联网上视频直播的P2P网络电视

4)PPStream是集P2P直播点播于一身的网络电视软件

5)http://www.sopcast.cn/

6)http://tvants.en.softonic.com/

7)http://www.cntv.cn/

8)http://www.bittorrent.com/

9)http://www.qq.com/

10)http://dl.xunlei.com/

11)http://www.sopcast.cn/