LTE核心网络中协作式视频缓存研究
|
摘要
作为向下一代移动通信网络(4G)过渡中的代表性设计,3GPP LTE技术近年来得到了迅猛的发展,在世界范围内拥有了广泛的部署。伴随着新型移动网络的完善带来的无线带宽和数据速率的大幅度提高,面向移动用户的在线视频业务也得到了爆炸性的增长。据Cisco2012年白皮书预计,在未来的五年中,移动网络中视频相关的流量将增长16倍,并将占据整个移动通信网络流量的66%以上。
3GPP LTE核心网络不同于前几代通信网络,对语音和数据传输服务都采用全数据包交换的方式,通过内部的GTP协议提供用户终端设备与数据网络之间的连接。然而,在这种简单的“中继”式的传输中,所有的数据请求需要经过整个LTE网络的层次结构到达Internet,这样不仅带来巨大的网络延迟,而且会产生额外的跨网费用。尤其是对于数据量要求很大的视频服务来说,这样的延迟和跨网费用都将是难以承受的。显然,将高访问量的视频缓存在离用户更近的核心网络中,将会在提高用户体验的同时大大降低移动网络提供商的运营成本。而进一步的分析表明,LTE核心网络的中层服务网关通常是由处理能力强大的服务器组成,具备进行视频缓存的硬件条件。本文基于这样的观点,对LTE核心网络中的协作式视频缓存问题进行了研究,主要内容和创新点总结如下：
1.提出了一种LTE核心网络中的最优化的视频存储算法。针对移动通信网络中视频点播业务中被请求对象的访问特点进行建模,该模型从缓存的原始目的出发,以最大化本地文件命中率为优化目标,以降低核心网络中可能需要的协作式请求数据量。证明了该优化模型为NP难解问题。通过进一步分析视频文件的特点,采用一种贪心式的搜索算法,尽可能搜索优化的文件存储解决方案。最后通过松弛模型问题变量得出优化问题的理论上界,作为评价贪心算法的标准尺度。仿真实验表明,本文提出的存储算法与理论上界之间的差距在1%～3%之间。
2.分析比较了视频缓存系统中已有的几种协作式请求调度机制,提出了一种分布式的基于数据流式、流量感知的协作式请求调度算法；并在此基础上,进一步研究了多源多路径网络环境下的协作式请求问题,提出了一种集中式、具有理论近似度的协作式数据流路由算法。现有的文献和系统中,协作式传输大多采用静态的、基于文件传输的内部传输方式。本文针对这种将网内节点看做FTP服务器/客户端方式的传输模式,进行仿真实验研究,并提出了一种基于数据流的协作式请求调度算法。比较对文件式非流量感知、文件式流量感知、数据流式非流量感知、数据流式流量感知四种可能的传输方案的优缺点进行系统性研究分析比较,对本文研究中采用的传输方式进行评估。LTE协作式视频缓存中,每个未命中请求可能有多个可选用网内服务源,而每个网内服务源有多条到达指定节点的路径。路由问题包括了选定服务源以及选定路由路径两个基本子问题。本文进而针对这样的路由问题进行建模,得到统一的优化模型,并且提出了一种具有理论近似度的多项式时间路由算法。该算法适用于多源多路径的应用场景,并且具有较低的算法复杂度。
3.提出了一种联合自适应视频速率的协作式视频路由算法。实际视频传输中,为了降低用户等待和用户体验延迟,高负荷的应用场景下,视频服务器可以通过可伸缩视频、自适应速率等技术手段来降低网络中的流量需求。针对这样的实际应用背景,本文研究了一种联合自适应速率的技术的协作式请求传输模型,该模型以最大化用户累计效用为优化目标。本文证明了模型化的问题是NP难解问题,进而提出了一种快速的两阶段求解算法,该算法与已有的算法相比,具有很大优势,并且能够支持更高的网络负载。
4.提出了一种简单的、在现有路由器中可以实现的路由协议。根据理论上路由算法得出的服务源和选定路径的数据流路由结果,结合现有实际应用中的路由器的工作要求,提出了一种基于逐跳前传(hop-by-hop forwarding)的路由协议。该协议根据路由流量的比例结果(proportional)建立路由表数据库,并且将相应的路由表发放到对应的路由器中。在提出的路由协议中,每个路由器根据收到数据流的源地址和目的地址,决定将收到的数据流按比例发送到下一跳的路由器。提出的路由协议可以很容易的在绝大多数已有路由器中实现,并且兼容未来的新型软件定义的网络(software defined networks),如OpenFlow.
5.研究并实现了LTE核心网络中的一个视频缓存子系统。以LTE核心网络原型项目OpenEPC为基础,详细讨论和分析了现有的3GPP LTE系统的系统架构和传输协议,提出了一种与现有标准兼容的视频缓存子系统设计,并且在大型核心网络实验平台OpenEPC上实现该视频缓存子系统的原型。
As a representative design of Next Generation Mobile Networks (4G),3GPP LTE has been actively investigated and improved, as well as been widely deployed all around the world in recent years. Along with higher bandwidth and faster data rate provided by4G, online video service are experiencing explosive growth. It is predicted by Cisco White Paper2012, that video-related traffic over the mobile networks will increase16-fold in the next five years, and will take66%of the overall mobile traffic.
Different from the former generation of mobile networks, the core network of3GPP LTE employs full IP-packet switching for both voice service and data service, connecting end users with the data networks via the internal protocol of GTP. However, in such "relay" transmission, all requests need to pass the whole core network structure in order to get served. This will bring in unbearable delay and extra network expense, especially for video service with high data-rate requirement. Apparently, video caching, which brings video clips close to the end users, can dramatically improve the Quality of Experience (QoE) as well as save operating expense. We notice that in the hierarchical structure of the LTE core network, serving gateways have strong computing power, providing possibility for in-network video caching. Based on these observations, this work targets the video caching problem in LTE core networks, proposing a collaborative video caching solution, which further includes the following parts:
1. Rearch on video placement for in-network video caching. The placement problem is built together with the characteristics of online video requests, aiming to maximize the aggregate hit ratio so as to reduce the amount of traffic incurred by collaborative requests. The formulated problem is proved to be NP-hard and a fast greedy algorithm is developed for it. Using the distributions of online video clips, the proposed algorithm reaches1%～3%of optimal in all cases simulated.
2. Research on the collaborative video transmission in LTE core network-s with video caching. Different manners of video transmission in collaborative caching systems are extensively investigated. An approximate algorithm with provable approximate ratio for in-network request routing. In most existing work-s, collaborative requests are considered as static, file-based transmission. This paper studies and compares different approaches of collaborative request schedul-ing, including file-based non-traffic-aware mode, file-based traffic-aware mode, flow-based non-traffic-aware mode and flow-based traffic-aware model. Further investigation over collaborative requests includes server selection and in-network routing. The joint problem is modeled in an optimization framework, and a low complexity algorithm is proposed for it with provable approximation ratio.
3. Research on collaborative request routing with joint video adaptation. In practice, video servers use video adaptation techniques, such as scalable video coding and adaptive rate video, to reduce the data rate of each request, so that keep feasible in-network traffic, especially in scenarios with heavy load. This paper aims to maximize the overall user utility while keeping the maximum link congestion under a given upper bound. However, such an optimization problem is proved to be NP-hard. Then a fast algorithm is proposed for it, which outperforms existing solutions and supports much more traffic load.
4. A realistic routing protocol is also investigated. According to output of the routing algorithm proposed, a routing protocol is developed in this paper with a hop-by-hop forwarding design. The coordinator computes a flow-splitting database using the proportional flow results from the routing algorithm, and dis-tributes a flow-splitting table to each router. The routers then split each incoming flows according to corresponding flow-splitting table. This protocol is compatible to most existing routers and also supports in further software defined networks, such as OpenFlow.
5. Implementation of a prototype caching system of LTE core network. Ex-isting architectures and protocols in3GPP LTE are extensively studied, and a compatible video caching subsystem is then developed, which is further imple-mented within the open core network prototype of OpenEPC.
3GPP LTE核心网络不同于前几代通信网络,对语音和数据传输服务都采用全数据包交换的方式,通过内部的GTP协议提供用户终端设备与数据网络之间的连接。然而,在这种简单的“中继”式的传输中,所有的数据请求需要经过整个LTE网络的层次结构到达Internet,这样不仅带来巨大的网络延迟,而且会产生额外的跨网费用。尤其是对于数据量要求很大的视频服务来说,这样的延迟和跨网费用都将是难以承受的。显然,将高访问量的视频缓存在离用户更近的核心网络中,将会在提高用户体验的同时大大降低移动网络提供商的运营成本。而进一步的分析表明,LTE核心网络的中层服务网关通常是由处理能力强大的服务器组成,具备进行视频缓存的硬件条件。本文基于这样的观点,对LTE核心网络中的协作式视频缓存问题进行了研究,主要内容和创新点总结如下：
1.提出了一种LTE核心网络中的最优化的视频存储算法。针对移动通信网络中视频点播业务中被请求对象的访问特点进行建模,该模型从缓存的原始目的出发,以最大化本地文件命中率为优化目标,以降低核心网络中可能需要的协作式请求数据量。证明了该优化模型为NP难解问题。通过进一步分析视频文件的特点,采用一种贪心式的搜索算法,尽可能搜索优化的文件存储解决方案。最后通过松弛模型问题变量得出优化问题的理论上界,作为评价贪心算法的标准尺度。仿真实验表明,本文提出的存储算法与理论上界之间的差距在1%～3%之间。
2.分析比较了视频缓存系统中已有的几种协作式请求调度机制,提出了一种分布式的基于数据流式、流量感知的协作式请求调度算法；并在此基础上,进一步研究了多源多路径网络环境下的协作式请求问题,提出了一种集中式、具有理论近似度的协作式数据流路由算法。现有的文献和系统中,协作式传输大多采用静态的、基于文件传输的内部传输方式。本文针对这种将网内节点看做FTP服务器/客户端方式的传输模式,进行仿真实验研究,并提出了一种基于数据流的协作式请求调度算法。比较对文件式非流量感知、文件式流量感知、数据流式非流量感知、数据流式流量感知四种可能的传输方案的优缺点进行系统性研究分析比较,对本文研究中采用的传输方式进行评估。LTE协作式视频缓存中,每个未命中请求可能有多个可选用网内服务源,而每个网内服务源有多条到达指定节点的路径。路由问题包括了选定服务源以及选定路由路径两个基本子问题。本文进而针对这样的路由问题进行建模,得到统一的优化模型,并且提出了一种具有理论近似度的多项式时间路由算法。该算法适用于多源多路径的应用场景,并且具有较低的算法复杂度。
3.提出了一种联合自适应视频速率的协作式视频路由算法。实际视频传输中,为了降低用户等待和用户体验延迟,高负荷的应用场景下,视频服务器可以通过可伸缩视频、自适应速率等技术手段来降低网络中的流量需求。针对这样的实际应用背景,本文研究了一种联合自适应速率的技术的协作式请求传输模型,该模型以最大化用户累计效用为优化目标。本文证明了模型化的问题是NP难解问题,进而提出了一种快速的两阶段求解算法,该算法与已有的算法相比,具有很大优势,并且能够支持更高的网络负载。
4.提出了一种简单的、在现有路由器中可以实现的路由协议。根据理论上路由算法得出的服务源和选定路径的数据流路由结果,结合现有实际应用中的路由器的工作要求,提出了一种基于逐跳前传(hop-by-hop forwarding)的路由协议。该协议根据路由流量的比例结果(proportional)建立路由表数据库,并且将相应的路由表发放到对应的路由器中。在提出的路由协议中,每个路由器根据收到数据流的源地址和目的地址,决定将收到的数据流按比例发送到下一跳的路由器。提出的路由协议可以很容易的在绝大多数已有路由器中实现,并且兼容未来的新型软件定义的网络(software defined networks),如OpenFlow.
5.研究并实现了LTE核心网络中的一个视频缓存子系统。以LTE核心网络原型项目OpenEPC为基础,详细讨论和分析了现有的3GPP LTE系统的系统架构和传输协议,提出了一种与现有标准兼容的视频缓存子系统设计,并且在大型核心网络实验平台OpenEPC上实现该视频缓存子系统的原型。
As a representative design of Next Generation Mobile Networks (4G),3GPP LTE has been actively investigated and improved, as well as been widely deployed all around the world in recent years. Along with higher bandwidth and faster data rate provided by4G, online video service are experiencing explosive growth. It is predicted by Cisco White Paper2012, that video-related traffic over the mobile networks will increase16-fold in the next five years, and will take66%of the overall mobile traffic.
Different from the former generation of mobile networks, the core network of3GPP LTE employs full IP-packet switching for both voice service and data service, connecting end users with the data networks via the internal protocol of GTP. However, in such "relay" transmission, all requests need to pass the whole core network structure in order to get served. This will bring in unbearable delay and extra network expense, especially for video service with high data-rate requirement. Apparently, video caching, which brings video clips close to the end users, can dramatically improve the Quality of Experience (QoE) as well as save operating expense. We notice that in the hierarchical structure of the LTE core network, serving gateways have strong computing power, providing possibility for in-network video caching. Based on these observations, this work targets the video caching problem in LTE core networks, proposing a collaborative video caching solution, which further includes the following parts:
1. Rearch on video placement for in-network video caching. The placement problem is built together with the characteristics of online video requests, aiming to maximize the aggregate hit ratio so as to reduce the amount of traffic incurred by collaborative requests. The formulated problem is proved to be NP-hard and a fast greedy algorithm is developed for it. Using the distributions of online video clips, the proposed algorithm reaches1%～3%of optimal in all cases simulated.
2. Research on the collaborative video transmission in LTE core network-s with video caching. Different manners of video transmission in collaborative caching systems are extensively investigated. An approximate algorithm with provable approximate ratio for in-network request routing. In most existing work-s, collaborative requests are considered as static, file-based transmission. This paper studies and compares different approaches of collaborative request schedul-ing, including file-based non-traffic-aware mode, file-based traffic-aware mode, flow-based non-traffic-aware mode and flow-based traffic-aware model. Further investigation over collaborative requests includes server selection and in-network routing. The joint problem is modeled in an optimization framework, and a low complexity algorithm is proposed for it with provable approximation ratio.
3. Research on collaborative request routing with joint video adaptation. In practice, video servers use video adaptation techniques, such as scalable video coding and adaptive rate video, to reduce the data rate of each request, so that keep feasible in-network traffic, especially in scenarios with heavy load. This paper aims to maximize the overall user utility while keeping the maximum link congestion under a given upper bound. However, such an optimization problem is proved to be NP-hard. Then a fast algorithm is proposed for it, which outperforms existing solutions and supports much more traffic load.
4. A realistic routing protocol is also investigated. According to output of the routing algorithm proposed, a routing protocol is developed in this paper with a hop-by-hop forwarding design. The coordinator computes a flow-splitting database using the proportional flow results from the routing algorithm, and dis-tributes a flow-splitting table to each router. The routers then split each incoming flows according to corresponding flow-splitting table. This protocol is compatible to most existing routers and also supports in further software defined networks, such as OpenFlow.
5. Implementation of a prototype caching system of LTE core network. Ex-isting architectures and protocols in3GPP LTE are extensively studied, and a compatible video caching subsystem is then developed, which is further imple-mented within the open core network prototype of OpenEPC.
引文
[1]Fehske A, Fettweis G, Malmodin J, et al. The global footprint of mobile communications:The ecological and economic perspective. Communications Magazine, IEEE,2011,49(8):55-62.
[2]3GPP LTE. http://www.3gpp.org.
[3]Cisco Whitepaper 2012. http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white-paper-c11-520862.html.
[4]LTE World. http://www.lteworld.org.
[5]Cha M, Kwak H, Rodriguez P, et al. I tube, you tube, everybody tubes:analyzing the world's largest user generated content video system. Proceedings of Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. ACM,2007.1-14.
[6]Cheng X, Dale C, Liu J. Statistics and social network of youtube videos. Proceedings of Quality of Service,2008. IWQoS 2008.16th International Workshop on. Ieee,2008.229-238.
[7]Gill P, Arlitt M, Li Z, et al. Youtube traffic characterization:a view from the edge. Proceedings of Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. ACM,2007.15-28.
[8]Zink M, Suh K, Gu Y, et al. Watch global, cache local:YouTube network traffic at a campus network-measurements and implications. Proceeding of the 15th SPIE/ACM Multimedia Comput-ing and Networking (MMCN08),2008..
[9]Radha H M, Schaar M, Chen Y. The MPEG-4 fine-grained scalable video coding method for multimedia streaming over IP. Multimedia, IEEE Transactions on,2001,3(1):53-68.
[10]Chang S, Vetro A. Video adaptation:concepts, technologies, and open issues. Proceedings of the IEEE,2005,93(1):148-158.
[11]Androutsellis-Theotokis S, Spinellis D. A survey of peer-to-peer content distribution technologies. ACM Computing Surveys (CSUR),2004,36(4):335-371.
[12]Borst S, Gupta V, Walid A. Distributed caching algorithms for content distribution networks. Proceedings of INFOCOM,2010 Proceedings IEEE. IEEE,2010.1-9.
[13]Applegate D, Archer A, Gopalakrishnan V, et al. Optimal content placement for a large-scale VoD system. Proceedings of Proceedings of the 6th International COnference. ACM,2010.4.
[14]IBM ILOG CPLEX Optimizer. http://www.fermentas.com/techinfo/nucleicacids/maplambda.htm.
[15]Xie H, Shi G, Wang P. TECC:Towards Collaborative In-network Caching Guided by Traffic Engineering. Proceedings of INFOCOM'12. IEEE,2012.
[16]Roughgarden T, Tardos E. How bad is selfish routing? Journal of the ACM (JACM),2002, 49(2):236-259.
[17]Chun B G, Chaudhuri K, Wee H, et al. Selfish caching in distributed systems:a game-theoretic analysis. Proceedings of Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. ACM,2004.21-30.
[18]Ouorou A, Mahey P, Vial J P. A survey of algorithms for convex multicommodity flow problems. Management Science,2000,46(1):126-147.
[19]Garg N, Konemann J. Faster and simpler algorithms for multicommodity flow and other fraction-al packing problems. Proceedings of Foundations of Computer Science,1998. Proceedings.39th Annual Symposium on. IEEE,1998.300-309.
[20]Fleischer L. Approximating fractional multicommodity flow independent of the number of com-modities. Proceedings of Foundations of Computer Science,1999.40th Annual Symposium on. IEEE,1999.24-31.
[21]Karakostas G. Faster approximation schemes for fractional multicommodity flow problems. Pro-ceedings of Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics,2002.166-173.
[22]DiPalantino D, Johari R. Traffic engineering vs. content distribution:A game theoretic perspective. Proceedings of INFOCOM 2009, IEEE. IEEE,2009.540-548.
[23]Jiang W, Zhang-Shen R, Rexford J, et al. Cooperative content distribution and traffic engineering in an ISP network. Proceedings of Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems. ACM,2009.239-250.
[24]Google Data API. https://developers.google.com/gdata.
[25]Karp R. Reducibility among combinatorial problems.50 Years of Integer Programming 1958-2008, 2010.219-241.
[26]Romeijn H, Morales D. A class of greedy algorithms for the generalized assignment problem. Discrete Applied Mathematics,2000,103(1):209-235.
[27]lp-solve. http://lpsolve.sourceforge.net.
[28]Jiang W, Zhang-Shen R, Rexford J, et al. Cooperative content distribution and traffic engineering. Proceedings of Proceedings of the 3rd international workshop on Economics of networked systems. ACM,2008.7-12.
[29]Chang S, Vetro A. Video adaptation:concepts, technologies, and open issues. Proceedings of the IEEE,2005,93(1):148-158.
[30]Su A, Choffnes D, Kuzmanovic A, et al. Drafting behind Akamai (travelocity-based detouring). COMPUTER COMMUNICATION REVIEW,2006,36(4):435.
[31]Deb S, Jaiswal S, Nagaraj K. Real-time video multicast in WiMAX networks. Proceedings of IN-FOCOM 2008. The 27th Conference on Computer Communications. IEEE. IEEE,2008.1579-1587.
[32]Squid, http://www.squid.org.
[33]Adamic L. Zipf, power-laws, and pareto-a ranking tutorial. Xerox Palo Alto Research Center, Palo Alto, CA,2000..
[34]Aggarwal C, Malkin P, Schloss R, et al. Collaborative caching of a requested object by a lower level node as a function of the caching status of the object at a higher level node, July 13,1999. US Patent 5,924,116.
[35]Aggarwal C, Malkin P, Schloss R, et al. Collaborative caching of a requested object by a lower level node as a function of the caching status of the object at a higher level node, July 13,1999. US Patent 5,924,116.
[36]Ahuja R, Magnanti T, Orlin J. Network Flows. Prentice Hall,1993.
[37]Baev I, Rajaraman R, Swamy C. Approximation algorithms for data placement problems. SIAM Journal on Computing,2010,38(4):1411.
[38]Bertsekas D P, Bertsekas D P. Nonlinear Programming.2nd ed., Athena Scientific, September, 1999.
[39]Beurket J, Malkin P, Rubin W, et al. Method for collaborative transformation and caching of web objects in a proxy network, September 19,2000. US Patent 6,122,666.
[40]Beurket J, Malkin P, Rubin W, et al. Method for collaborative transformation and caching of web objects in a proxy network, September 19,2000. US Patent 6,122,666.
[41]Bienstock D. Potential function methods for approximately solving linear programming problems: theory and practice, volume 53. Kluwer Academic Pub,2002.
[42]Borst S, Gupta V, Walid A. Distributed caching algorithms for content distribution networks. Proceedings of INFOCOM,2010 Proceedings IEEE. IEEE,2010.1-9.
[43]Boyd S, Vandenberghe L. Convex optimization. Cambridge Univ Pr,2004.
[44]Breslau L, Cao P, Fan L, et al. Web caching and Zipf-like distributions:Evidence and implications. Proceedings of INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 1. IEEE,1999.126-134.
[45]Buchholz S, Buchholz T. Replica placement in adaptive content distribution networks. Proceedings of Proceedings of the 2004 ACM symposium on Applied computing. ACM,2004.1705-1710.
[46]Cain B, Spatscheck O, Nair R, et al. Known content network (CN) request-routing mechanisms. 2003..
[47]Cattrysse D, Van Wassenhove L. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research,1992,60(3):260-272.
[48]Chekuri C, Khanna S. A PTAS for the multiple knapsack problem. Proceedings of Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics,2000.213-222.
[49]Chen J, Sundaram R, Marathe M, et al. The confluent capacity of the Internet:congestion vs. dila-tion. Proceedings of Distributed Computing Systems,2006. ICDCS 2006.26th IEEE International Conference on. IEEE,2006.5-5.
[50]Chun B, Chaudhuri K, Wee H, et al. Selfish caching in distributed systems:a game-theoretic analysis. Proceedings of Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. ACM,2004.21-30.
[51]Cohen R, Katzir L, Raz D. An efficient approximation for the generalized assignment problem. Information Processing Letters,2006,100(4):162-166.
[52]Dahlman E.3G evolution:HSPA and LTE for mobile broadband. Academic Press,2008.
[53]Deb S, Jaiswal S, Nagaraj K. Real-time video multicast in WiMAX networks. Proceedings of IN-FOCOM 2008. The 27th Conference on Computer Communications. IEEE. IEEE,2008.1579-1587.
[54]De Maio A, Roveda C. An all zero-one algorithm for a certain class of transportation problems. Operations Research,1971.1406-1418.
[55]Dobrian F, Awan A, Joseph D, et al. Understanding the impact of video quality on user engagement. SIGCOMM-Computer Communication Review,2011,41(4):362.
[56]Dutta P, Seetharam A, Arya V, et al. On managing quality of experience of multiple video streams in wireless networks. Proceedings of INFOCOM,2012 Proceedings IEEE. IEEE,2012.1242-1250.
[57]Fernandess Y, Malkhi D. On collaborative content distribution using multi-message gossip. Journal of Parallel and Distributed Computing,2007,67(12):1232-1239.
[58]Gadde S, Chase J, Rabinovich M. Web caching and content distribution:A view from the interior. Computer Communications,2001,24(2):222-231.
[59]Garg N, Konemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing,2007,37:630.
[60]He J, Zhang H, Zhao B, et al. Joint Server Selection and Traffic Engineering in Collaborative VoD Systems. Technical report, NEC Labs America, http://home.ustc.edu.cn/myname/papers/rout-ing.pdf, June 2012.
[61]He J, Zhang H, Zhao B, et al. Joint Server Selection and Traffic Engineering in Col-laborative Content Distribution Networks. Technical report, NEC Labs America, http-s://www.dropbox.com/s/dc343qn96qoxs4p/routing.pdf, June 2012.
[62]He J, Zhang H, Zhao B, et al. A Collaborative Framework for In-network Video Caching in Mobile Networks. Proceedings of Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2013 10th Annual IEEE Communications Society Conference on. IEEE,2013.
[63]He J, Zhao X, Zhao B. Joint Request Routing and Video Adaptation in Collaborative VoD Systems. Proceedings of Wireless Communications and Networking Conference,2013. WCNC.2013 IEEE. IEEE,2013.1496-1501.
[64]He J, Zhao X, Zhao B. A fast, simple and near-optimal content placement scheme for a large-scale VoD system. Proceedings of Communication Systems (ICCS),2012 IEEE International Conference on. IEEE,2012.378-382.
[65]Hindi H. A tutorial on convex optimization Ⅱ:Duality and interior point methods. Proceedings of American Control Conference,2006. Ieee,2006.11-pp.
[66]Huang C, Li J, Ross K. Can internet video-on-demand be profitable? ACM SIGCOMM Computer Communication Review,2007,37(4):133-144.
[67]Jacquet P, Muhlethaler P, Clausen T, et al. Optimized link state routing protocol for ad hoc networks. Proceedings of Multi Topic Conference,2001. IEEE INMIC 2001. Technology for the 21st Century. Proceedings. IEEE International. IEEE,2001.62-68.
[68]Johnson D, Garey M. Computers and Intractability:A Guide to the Theory of NP-completeness. Freeman&Co, San Francisco,1979..
[69]Kangasharju J, Roberts J, Ross K. Object replication strategies in content distribution networks. Computer Communications,2002,25(4):376-383.
[70]Krishnamurthy B, Wills C, Zhang Y. On the use and performance of content distribution networks. Proceedings of Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement. ACM, 2001.169-182.
[71]Marsten R, Subramanian R, Saltzman M, et al. Interior point methods for linear programming: Just call Newton, Lagrange, and Fiacco and McCormick! Interfaces,1990.105-116.
[72]Martello S, Toth P. Knapsack problems:algorithms and computer implementations. John Wiley & Sons, Inc.,1990.
[73]McKeown N, Anderson T, Balakrishnan H, et al. OpenFlow:enabling innovation in campus networks. Proceedings of ACM SIGCOMM Computer Communication Review, volume 38(2):69.74, April 2008.
[74]Michel S, Nguyen K, Rosenstein A, et al. Adaptive web caching:Towards a new global caching architecture. Computer Networks and ISDN systems,1998,30(22-23):2169-2177.
[75]Murthy M. A bulk transportation problem. Opsearch,1976,13:143-53.
[76]Ninan A, Kulkarni P, Shenoy P, et al. Cooperative leases:Scalable consistency maintenance in content distribution networks. Proceedings of Proceedings of the 11th international conference on World Wide Web. ACM,2002.1-12.
[77]Ouorou A, Mahey P, Vial J. A survey of algorithms for convex multicommodity flow problems. Management Science,2000.126-147.
[78]Ouorou A, Mahey P, Vial J. A survey of algorithms for convex multicommodity flow problems. Management Science,2000.126-147.
[79]Padmanabhan V, Wang H, Chou P, et al. Distributing streaming media content using coopera-tive networking. Proceedings of Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video. ACM,2002.177-186.
[80]Plotkin S, Shmoys D, Tardos E. Fast approximation algorithms for fractional packing and covering problems. Proceedings of Foundations of Computer Science,1991. Proceedings.,32nd Annual Symposium on. IEEE,1991.495-504.
[81]Purusotham S, Sundara Murthy M. An Exact Algorithm for Multi-Product Bulk Transportation Problem. International Journal,2011,3.
[82]Qiu L, Padmanabhan V, Voelker G. On the placement of web server replicas. Proceedings of INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 3. IEEE,2001.1587-1596.
[83]Rodriguez P, Spanner C, Biersack E. Analysis of web caching architectures:hierarchical and distributed caching. Networking, IEEE/ACM Transactions on,2001,9(4):404-418.
[84]Shavitt Y. Routing through networks with hierarchical topology aggregation. Journal of High Speed Networks,1998,7:57-73.
[85]Srinivasan V, Thompson G. An algorithm for assigning uses to sources in a special class of trans-portation problems. Operations Research,1973.284-295.
[86]Su A, Choffnes D, Kuzmanovic A, et al. Drafting behind Akamai (travelocity-based detouring). Pro-ceedings of ACM SIGCOMM Computer Communication Review, volume 36. ACM,2006.435-446.
[87]Su A, Choffnes D, Kuzmanovic A, et al. Drafting behind Akamai (travelocity-based detouring). COMPUTER COMMUNICATION REVIEW,2006,36(4):435.
[88]Verma D. Content distribution networks. Wiley Online Library,2002.
[89]Wang M, Li G, Feng J, et al. Understanding User Generated Content Characteristics:A Hot-Event Perspective.2011..
[90]Widmer J, Denda R, Mauve M. A survey on TCP-friendly congestion control. Network, IEEE, 2001,15(3):28-37.
[91]Wu M, Shu W. Scheduling for interactive operations in parallel video servers. Proceedings of Multimedia Computing and Systems'97. Proceedings., IEEE International Conference on. IEEE, 1997.178-185.
[92]Xie H, Shi G, Wang P. TECC:Towards collaborative in-network caching guided by traffic engi-neering. Proceedings of INFOCOM,2012 Proceedings IEEE. IEEE,2012.2546-2550.
[93]Xie H, Yang Y R, Krishnamurthy A, et al. P4p:provider portal for applications. Proceedings of Proceedings of the ACM SIGCOMM 2008 conference on Data communication, New York, NY, USA:ACM,2008.351-362.
[94]OpenFlow. http://www.openflow.org.
[95]TCP Congestion Control Protocol, rfc5681. http://tools.ietf.org/html/rfc5681.
[96]Youtube. http://www.youtube.com.
[2]3GPP LTE. http://www.3gpp.org.
[3]Cisco Whitepaper 2012. http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white-paper-c11-520862.html.
[4]LTE World. http://www.lteworld.org.
[5]Cha M, Kwak H, Rodriguez P, et al. I tube, you tube, everybody tubes:analyzing the world's largest user generated content video system. Proceedings of Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. ACM,2007.1-14.
[6]Cheng X, Dale C, Liu J. Statistics and social network of youtube videos. Proceedings of Quality of Service,2008. IWQoS 2008.16th International Workshop on. Ieee,2008.229-238.
[7]Gill P, Arlitt M, Li Z, et al. Youtube traffic characterization:a view from the edge. Proceedings of Proceedings of the 7th ACM SIGCOMM conference on Internet measurement. ACM,2007.15-28.
[8]Zink M, Suh K, Gu Y, et al. Watch global, cache local:YouTube network traffic at a campus network-measurements and implications. Proceeding of the 15th SPIE/ACM Multimedia Comput-ing and Networking (MMCN08),2008..
[9]Radha H M, Schaar M, Chen Y. The MPEG-4 fine-grained scalable video coding method for multimedia streaming over IP. Multimedia, IEEE Transactions on,2001,3(1):53-68.
[10]Chang S, Vetro A. Video adaptation:concepts, technologies, and open issues. Proceedings of the IEEE,2005,93(1):148-158.
[11]Androutsellis-Theotokis S, Spinellis D. A survey of peer-to-peer content distribution technologies. ACM Computing Surveys (CSUR),2004,36(4):335-371.
[12]Borst S, Gupta V, Walid A. Distributed caching algorithms for content distribution networks. Proceedings of INFOCOM,2010 Proceedings IEEE. IEEE,2010.1-9.
[13]Applegate D, Archer A, Gopalakrishnan V, et al. Optimal content placement for a large-scale VoD system. Proceedings of Proceedings of the 6th International COnference. ACM,2010.4.
[14]IBM ILOG CPLEX Optimizer. http://www.fermentas.com/techinfo/nucleicacids/maplambda.htm.
[15]Xie H, Shi G, Wang P. TECC:Towards Collaborative In-network Caching Guided by Traffic Engineering. Proceedings of INFOCOM'12. IEEE,2012.
[16]Roughgarden T, Tardos E. How bad is selfish routing? Journal of the ACM (JACM),2002, 49(2):236-259.
[17]Chun B G, Chaudhuri K, Wee H, et al. Selfish caching in distributed systems:a game-theoretic analysis. Proceedings of Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. ACM,2004.21-30.
[18]Ouorou A, Mahey P, Vial J P. A survey of algorithms for convex multicommodity flow problems. Management Science,2000,46(1):126-147.
[19]Garg N, Konemann J. Faster and simpler algorithms for multicommodity flow and other fraction-al packing problems. Proceedings of Foundations of Computer Science,1998. Proceedings.39th Annual Symposium on. IEEE,1998.300-309.
[20]Fleischer L. Approximating fractional multicommodity flow independent of the number of com-modities. Proceedings of Foundations of Computer Science,1999.40th Annual Symposium on. IEEE,1999.24-31.
[21]Karakostas G. Faster approximation schemes for fractional multicommodity flow problems. Pro-ceedings of Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics,2002.166-173.
[22]DiPalantino D, Johari R. Traffic engineering vs. content distribution:A game theoretic perspective. Proceedings of INFOCOM 2009, IEEE. IEEE,2009.540-548.
[23]Jiang W, Zhang-Shen R, Rexford J, et al. Cooperative content distribution and traffic engineering in an ISP network. Proceedings of Proceedings of the eleventh international joint conference on Measurement and modeling of computer systems. ACM,2009.239-250.
[24]Google Data API. https://developers.google.com/gdata.
[25]Karp R. Reducibility among combinatorial problems.50 Years of Integer Programming 1958-2008, 2010.219-241.
[26]Romeijn H, Morales D. A class of greedy algorithms for the generalized assignment problem. Discrete Applied Mathematics,2000,103(1):209-235.
[27]lp-solve. http://lpsolve.sourceforge.net.
[28]Jiang W, Zhang-Shen R, Rexford J, et al. Cooperative content distribution and traffic engineering. Proceedings of Proceedings of the 3rd international workshop on Economics of networked systems. ACM,2008.7-12.
[29]Chang S, Vetro A. Video adaptation:concepts, technologies, and open issues. Proceedings of the IEEE,2005,93(1):148-158.
[30]Su A, Choffnes D, Kuzmanovic A, et al. Drafting behind Akamai (travelocity-based detouring). COMPUTER COMMUNICATION REVIEW,2006,36(4):435.
[31]Deb S, Jaiswal S, Nagaraj K. Real-time video multicast in WiMAX networks. Proceedings of IN-FOCOM 2008. The 27th Conference on Computer Communications. IEEE. IEEE,2008.1579-1587.
[32]Squid, http://www.squid.org.
[33]Adamic L. Zipf, power-laws, and pareto-a ranking tutorial. Xerox Palo Alto Research Center, Palo Alto, CA,2000..
[34]Aggarwal C, Malkin P, Schloss R, et al. Collaborative caching of a requested object by a lower level node as a function of the caching status of the object at a higher level node, July 13,1999. US Patent 5,924,116.
[35]Aggarwal C, Malkin P, Schloss R, et al. Collaborative caching of a requested object by a lower level node as a function of the caching status of the object at a higher level node, July 13,1999. US Patent 5,924,116.
[36]Ahuja R, Magnanti T, Orlin J. Network Flows. Prentice Hall,1993.
[37]Baev I, Rajaraman R, Swamy C. Approximation algorithms for data placement problems. SIAM Journal on Computing,2010,38(4):1411.
[38]Bertsekas D P, Bertsekas D P. Nonlinear Programming.2nd ed., Athena Scientific, September, 1999.
[39]Beurket J, Malkin P, Rubin W, et al. Method for collaborative transformation and caching of web objects in a proxy network, September 19,2000. US Patent 6,122,666.
[40]Beurket J, Malkin P, Rubin W, et al. Method for collaborative transformation and caching of web objects in a proxy network, September 19,2000. US Patent 6,122,666.
[41]Bienstock D. Potential function methods for approximately solving linear programming problems: theory and practice, volume 53. Kluwer Academic Pub,2002.
[42]Borst S, Gupta V, Walid A. Distributed caching algorithms for content distribution networks. Proceedings of INFOCOM,2010 Proceedings IEEE. IEEE,2010.1-9.
[43]Boyd S, Vandenberghe L. Convex optimization. Cambridge Univ Pr,2004.
[44]Breslau L, Cao P, Fan L, et al. Web caching and Zipf-like distributions:Evidence and implications. Proceedings of INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 1. IEEE,1999.126-134.
[45]Buchholz S, Buchholz T. Replica placement in adaptive content distribution networks. Proceedings of Proceedings of the 2004 ACM symposium on Applied computing. ACM,2004.1705-1710.
[46]Cain B, Spatscheck O, Nair R, et al. Known content network (CN) request-routing mechanisms. 2003..
[47]Cattrysse D, Van Wassenhove L. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research,1992,60(3):260-272.
[48]Chekuri C, Khanna S. A PTAS for the multiple knapsack problem. Proceedings of Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics,2000.213-222.
[49]Chen J, Sundaram R, Marathe M, et al. The confluent capacity of the Internet:congestion vs. dila-tion. Proceedings of Distributed Computing Systems,2006. ICDCS 2006.26th IEEE International Conference on. IEEE,2006.5-5.
[50]Chun B, Chaudhuri K, Wee H, et al. Selfish caching in distributed systems:a game-theoretic analysis. Proceedings of Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. ACM,2004.21-30.
[51]Cohen R, Katzir L, Raz D. An efficient approximation for the generalized assignment problem. Information Processing Letters,2006,100(4):162-166.
[52]Dahlman E.3G evolution:HSPA and LTE for mobile broadband. Academic Press,2008.
[53]Deb S, Jaiswal S, Nagaraj K. Real-time video multicast in WiMAX networks. Proceedings of IN-FOCOM 2008. The 27th Conference on Computer Communications. IEEE. IEEE,2008.1579-1587.
[54]De Maio A, Roveda C. An all zero-one algorithm for a certain class of transportation problems. Operations Research,1971.1406-1418.
[55]Dobrian F, Awan A, Joseph D, et al. Understanding the impact of video quality on user engagement. SIGCOMM-Computer Communication Review,2011,41(4):362.
[56]Dutta P, Seetharam A, Arya V, et al. On managing quality of experience of multiple video streams in wireless networks. Proceedings of INFOCOM,2012 Proceedings IEEE. IEEE,2012.1242-1250.
[57]Fernandess Y, Malkhi D. On collaborative content distribution using multi-message gossip. Journal of Parallel and Distributed Computing,2007,67(12):1232-1239.
[58]Gadde S, Chase J, Rabinovich M. Web caching and content distribution:A view from the interior. Computer Communications,2001,24(2):222-231.
[59]Garg N, Konemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing,2007,37:630.
[60]He J, Zhang H, Zhao B, et al. Joint Server Selection and Traffic Engineering in Collaborative VoD Systems. Technical report, NEC Labs America, http://home.ustc.edu.cn/myname/papers/rout-ing.pdf, June 2012.
[61]He J, Zhang H, Zhao B, et al. Joint Server Selection and Traffic Engineering in Col-laborative Content Distribution Networks. Technical report, NEC Labs America, http-s://www.dropbox.com/s/dc343qn96qoxs4p/routing.pdf, June 2012.
[62]He J, Zhang H, Zhao B, et al. A Collaborative Framework for In-network Video Caching in Mobile Networks. Proceedings of Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2013 10th Annual IEEE Communications Society Conference on. IEEE,2013.
[63]He J, Zhao X, Zhao B. Joint Request Routing and Video Adaptation in Collaborative VoD Systems. Proceedings of Wireless Communications and Networking Conference,2013. WCNC.2013 IEEE. IEEE,2013.1496-1501.
[64]He J, Zhao X, Zhao B. A fast, simple and near-optimal content placement scheme for a large-scale VoD system. Proceedings of Communication Systems (ICCS),2012 IEEE International Conference on. IEEE,2012.378-382.
[65]Hindi H. A tutorial on convex optimization Ⅱ:Duality and interior point methods. Proceedings of American Control Conference,2006. Ieee,2006.11-pp.
[66]Huang C, Li J, Ross K. Can internet video-on-demand be profitable? ACM SIGCOMM Computer Communication Review,2007,37(4):133-144.
[67]Jacquet P, Muhlethaler P, Clausen T, et al. Optimized link state routing protocol for ad hoc networks. Proceedings of Multi Topic Conference,2001. IEEE INMIC 2001. Technology for the 21st Century. Proceedings. IEEE International. IEEE,2001.62-68.
[68]Johnson D, Garey M. Computers and Intractability:A Guide to the Theory of NP-completeness. Freeman&Co, San Francisco,1979..
[69]Kangasharju J, Roberts J, Ross K. Object replication strategies in content distribution networks. Computer Communications,2002,25(4):376-383.
[70]Krishnamurthy B, Wills C, Zhang Y. On the use and performance of content distribution networks. Proceedings of Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement. ACM, 2001.169-182.
[71]Marsten R, Subramanian R, Saltzman M, et al. Interior point methods for linear programming: Just call Newton, Lagrange, and Fiacco and McCormick! Interfaces,1990.105-116.
[72]Martello S, Toth P. Knapsack problems:algorithms and computer implementations. John Wiley & Sons, Inc.,1990.
[73]McKeown N, Anderson T, Balakrishnan H, et al. OpenFlow:enabling innovation in campus networks. Proceedings of ACM SIGCOMM Computer Communication Review, volume 38(2):69.74, April 2008.
[74]Michel S, Nguyen K, Rosenstein A, et al. Adaptive web caching:Towards a new global caching architecture. Computer Networks and ISDN systems,1998,30(22-23):2169-2177.
[75]Murthy M. A bulk transportation problem. Opsearch,1976,13:143-53.
[76]Ninan A, Kulkarni P, Shenoy P, et al. Cooperative leases:Scalable consistency maintenance in content distribution networks. Proceedings of Proceedings of the 11th international conference on World Wide Web. ACM,2002.1-12.
[77]Ouorou A, Mahey P, Vial J. A survey of algorithms for convex multicommodity flow problems. Management Science,2000.126-147.
[78]Ouorou A, Mahey P, Vial J. A survey of algorithms for convex multicommodity flow problems. Management Science,2000.126-147.
[79]Padmanabhan V, Wang H, Chou P, et al. Distributing streaming media content using coopera-tive networking. Proceedings of Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video. ACM,2002.177-186.
[80]Plotkin S, Shmoys D, Tardos E. Fast approximation algorithms for fractional packing and covering problems. Proceedings of Foundations of Computer Science,1991. Proceedings.,32nd Annual Symposium on. IEEE,1991.495-504.
[81]Purusotham S, Sundara Murthy M. An Exact Algorithm for Multi-Product Bulk Transportation Problem. International Journal,2011,3.
[82]Qiu L, Padmanabhan V, Voelker G. On the placement of web server replicas. Proceedings of INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, volume 3. IEEE,2001.1587-1596.
[83]Rodriguez P, Spanner C, Biersack E. Analysis of web caching architectures:hierarchical and distributed caching. Networking, IEEE/ACM Transactions on,2001,9(4):404-418.
[84]Shavitt Y. Routing through networks with hierarchical topology aggregation. Journal of High Speed Networks,1998,7:57-73.
[85]Srinivasan V, Thompson G. An algorithm for assigning uses to sources in a special class of trans-portation problems. Operations Research,1973.284-295.
[86]Su A, Choffnes D, Kuzmanovic A, et al. Drafting behind Akamai (travelocity-based detouring). Pro-ceedings of ACM SIGCOMM Computer Communication Review, volume 36. ACM,2006.435-446.
[87]Su A, Choffnes D, Kuzmanovic A, et al. Drafting behind Akamai (travelocity-based detouring). COMPUTER COMMUNICATION REVIEW,2006,36(4):435.
[88]Verma D. Content distribution networks. Wiley Online Library,2002.
[89]Wang M, Li G, Feng J, et al. Understanding User Generated Content Characteristics:A Hot-Event Perspective.2011..
[90]Widmer J, Denda R, Mauve M. A survey on TCP-friendly congestion control. Network, IEEE, 2001,15(3):28-37.
[91]Wu M, Shu W. Scheduling for interactive operations in parallel video servers. Proceedings of Multimedia Computing and Systems'97. Proceedings., IEEE International Conference on. IEEE, 1997.178-185.
[92]Xie H, Shi G, Wang P. TECC:Towards collaborative in-network caching guided by traffic engi-neering. Proceedings of INFOCOM,2012 Proceedings IEEE. IEEE,2012.2546-2550.
[93]Xie H, Yang Y R, Krishnamurthy A, et al. P4p:provider portal for applications. Proceedings of Proceedings of the ACM SIGCOMM 2008 conference on Data communication, New York, NY, USA:ACM,2008.351-362.
[94]OpenFlow. http://www.openflow.org.
[95]TCP Congestion Control Protocol, rfc5681. http://tools.ietf.org/html/rfc5681.
[96]Youtube. http://www.youtube.com.