基于用户体验评价模型的最优路由选择算法

计算机应用 ›› 2012, Vol. 32 ›› Issue (10): 2683-2688.DOI: 10.3724/SP.J.1087.2012.02683

• 网络与通信 • 下一篇

基于用户体验评价模型的最优路由选择算法

张大陆¹,曹孝晶²,胡治国²,³

1. 同济大学,电子信息与工程学院,计算机系
2. 同济大学计算机科学与技术系
3. 65583部队

收稿日期:2012-04-18 修回日期:2012-06-11 发布日期:2012-10-23 出版日期:2012-10-01
通讯作者: 曹孝晶
作者简介:张大陆(1949-),男,山东莱阳人,教授,博士生导师,主要研究方向:计算机网络、P2P技术、语义Web;曹孝晶(1988-),男,上海人,硕士研究生,主要研究方向:QoE路由算法;胡治国(1977-),男,山西灵石人,博士研究生,主要研究方向: 网络性能评估。
基金资助:
国家自然科学基金资助项目

Optimal routing algorithm based on user experience estimation model

ZHANG Da-lu¹,CAO Xiao-jing¹,HU Zhi-guo¹,²

1. Department of Computer Science and Technology, Tongji University
2. The No. 65583 Army, Liaoyang Liaoning 111000

Received:2012-04-18 Revised:2012-06-11 Online:2012-10-23 Published:2012-10-01
Contact: CAO Xiao-jing

摘要/Abstract

摘要： 网络视音频业务的兴起使网络运营商和服务提供商更加关注视音频的用户体验（QoE）,而传统的路由算法只能保证所选路径的服务质量（QoS）参数,如延迟、抖动等满足QoS约束的需求,并不能直接反映QoE的信息,从而不能保证所选路径满足QoE需求。基于QoE评价模型,给出以QoE为目标的最优路由选择算法。通过分析QoE表征参数与传统QoS参数的关系,利用QoE表征参数可分解性和QoE表征值非递减性两个性质,给出多项式时间复杂度为O(V log V+E)的QoE_DSP算法。实验和分析表明,该算法能保证所得路径满足QoE需求,同时具有良好的计算扩展性。

关键词: 用户体验路由算法, 最优路由, 参数分解, 用户体验模型

Abstract: As a fast-growing contributor to Internet service, online videos make ISPs and video providers pay more attention to the Quality of user Experience (QoE). The existing routing algorithms could only guarantee that parameters of path such as delay and jitter, in accordance with the demands of Quality of Service (QoS) restriction. However, they are not able to reflect the QoE-related information directly. As a result, these kinds of algorithms cannot meet the demand of showing QoE. This paper proposed a QoE-optimal routing algorithm called QoE_DSP, based on QoE estimation model. By taking advantage of two properties of QoE parameter, decomposability and nondecreasing characteristics from the analysis on relationship between QoE and QoS, the authors designed QoE_DSP, which owned a polynomial time complexity of (V log V+E). According to the experiments and results analysis, this algorithm can guarantee the selected path meets the demand of QoE, while it also has a strong computational scalability.

Key words: Quality of user Experience （QoE） routing algorithm, optimal routing, parameter decomposition, Quality of user Experience (QoE) model

张大陆曹孝晶胡治国. 基于用户体验评价模型的最优路由选择算法[J]. 计算机应用, 2012, 32(10): 2683-2688.

ZHANG Da-lu CAO Xiao-jing HU Zhi-guo. Optimal routing algorithm based on user experience estimation model[J]. Journal of Computer Applications, 2012, 32(10): 2683-2688.

参考文献

［1］张大陆, 张起强. IP网络中视频流QoE评价模型［J］. 计算机工程与应用, 2012,48(3):83-87. ［2］ WANG ZHENG, CROWCROFT J. Quality-of-service routing for supporting multimedia applications［J］. IEEE Journal on Selected Areas in Communications, 1996,14(7):148-154. ［3］赵海雁, 陈立潮. 多约束条件下最短路径QoS路由算法［J］. 华北工学院学报, 2004,25(1):49-51. ［4］ KORKMAZ T, KRUNZ M. A randomized algorithm for finding a path subject to multiple QoS constraints［C］// GLOBECOM99: Global Telecommunications Conference. Piscataway, NJ:IEEE, 1999:1694-1698. ［5］ CHEN SHIGANG, NAHRSTEDT K. On finding multi-constrained paths[C]// ICC98: Proceedings of the 1998 IEEE International Conference on Communications. Atlanta:IEEE, 1998:874-879. ［6］ COSTA L H M K, FDIDA S, DUARTE O C M B. A scalable algorithm for link-state QoS-based routing with three metrics［C］// ICC 2001: IEEE International Conference on Communications. Helsinki:IEEE, 2001:2603-2607. ［7］ JAFFE J M. Algorithms for finding paths with multiple constraints［J］. Networks, 1984,14(1): 95-116. ［8］ ANDREW L L H, KUSUMA A A N A. Generalised analysis of a QoS-aware routing algorithm［EB/OL］.[2012-01-05].http://www.caia.swin.edu.au/cv/landrew/pubs/qos_gc98.pdf. ［9］ IWATA A, IZMAILOV R, LEE D-S,et al. ATM routing algorithms with multiple QoS requirements for multimedia internetworking［J］. IEICE Transactions on Communications, 1996,E79-B(8):999-1006. ［10］ CUI YONG, XU KE, WU JIANPING, et al. Precomputation for finding paths with two additive weights［C］// ICC03:IEEE International Conference on Communications. [S.l.]:IEEE, 2003:636-640. ［11］ XIAO WENDONG, SOONG B H, LAW C L,et al. Evaluation of heuristic path selection algorithm for multi-constrained QoS routing［C］// IEEE International Conference on Networking, Sensing and Control. [S.l.]:IEEE, 2004:112-116. ［12］ de NEVE H, van IEGHEM P. TAMCRA: A tunable accuracy multiple constraints routing algorithm［J］. Computer Communications, 2000,23(7):667-679. ［13］ van MIEGHEM P, KUIPERS F A. Hop-by-hop quality of service routing［J］. Computer Networks, 2001,37(3/4):407-423. ［14］ van MIEGHEM P, KUIPERS F A. Concepts of exact QoS routing algorithms［J］. IEEE/ACM Transactions on Networking,2004,12(5):851-864. ［15］ AHUJA R K, MAGNANTI T L, ORLIN J B. Network flows: Theory, algorithms, and applications［M］. Upper Saddle River,NJ,USA: Prentice Hall, 1993. ［16］ PINSON M, WOLF S. An objective method for combining multiple subjective data sets［EB/OL］.[2012-01-10].http://wenku.baidu.com/view/1f9a591f59eef8c75fbfb3f8.html?from=related. ［17］ WANG BIN, HOU J C. Multicast routing and its QoS extension: Problems, algorithms, and protocols［J］. IEEE Network,2000,14(1):22-36. ［18］ KORKMAZ T, KRUNZ M. Multi-constrained optimal path selection［C］// INFOCOM01: Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Anchorage:IEEE,2001:834-843. ［19］ ANDERSEN R, CHUANG F, SEN A, et al. On disjoint path pairs with wavelength continuity constraint in WDM networks［C］// INFOCOM04:Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies. Anchorage:IEEE, 2004:524-535.

相关文章 0

编辑推荐

Metrics