Simplify ISP Traffic Engineering with Content Distribution
Dive into the world of NCDNs and CDN management to optimize routing, enhance content placement, and improve user experience. Explore the interaction between routing and content placement, different NCDN schemes, and research questions around unplanned vs. planned strategies and joint optimization.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Distributing Content Simplifies ISP Traffic Engineering Abhigyan Sharma* Arun Venkataramani* Ramesh Sitaraman*~ *University of Massachusetts Amherst ~Akamai Technologies 1
Tripartite view of content delivery Content providers NCDNs deployed in 30+ ISPs globally CDN NCDN NCDN NCDN Networks
NCDN Management Traffic Engineering Content Distribution NCDN Mgmt. Optimize routing to remove congestion hotspots Optimize content placement & request redirection to improve user-perceived performance 3
NCDN Routing Placement Interaction 0.25 Mbps B C 0.5 Mbps 0.25 Mbps 1.25 Mbps 4 Mbps Traffic labeled with flow value 8 Mbps Link labeled with capacity 1.5 Mbps A D 0.75 Mbps Demand = 1 Mbps Demand = 0.5 Mbps Maximum link utilization (MLU) = 0.75/1.5 = 0.5 4
NCDN Routing Placement Interaction B C 0.5 Mbps Content placement flexibility reduces network costs and enables simpler routing 0.5 Mbps 1 Mbps 4 Mbps Traffic labeled with flow value 8 Mbps Link labeled with capacity 1.5 Mbps A D Demand = 1 Mbps Demand = 0.5 Mbps Maximum link utilization (MLU) = 1/8 = 0.125 5
NCDN Schemes Classification NCDN Management Content Distribution Traffic Engineering Unplanned (e.g. LRU Caching) Planned (history- based) Planned (e.g. OSPF weight tuning) Unplanned (static routing) Joint Optimization 6
Research Questions How do simple unplanned schemes perform? Is joint optimization better than other schemes? What matters more: placement or routing? 7
Outline Network CDN NCDN Model & Joint Optimization Datasets: Akamai Traces & ISP Topologies Results Related Work 8
NCDN Model Origin servers NCDN POP Backbone router Content servers Backbone router at exit nodes Downstream end-users 9
NCDN Model Origin servers NCDN POP Backbone router Content servers Backbone router at exit nodes Downstream end-users 10
NCDN Model Origin servers NCDN POP Backbone router Content servers Backbone router at exit nodes Downstream end-users 11
NCDN Model Origin servers Resource constraints POP storage ISP backbone link capacity Downstream end-users 12
NCDN Joint Optimization Hardness Theorem 1: Opt-NCDN is NP-Complete even in the special case where all objects have unit size, all demands, link capacities and storage capacities have binary values. Approximability Theorem 2: Opt-NCDN is inapproximable within a factor for any > 1 unless P = NP. 13
MIP for Joint Optimization Objective: Minimize NCDN-cost (MLU or latency) Constraints: For all node: total size of content < Storage capacity For all (content, node): demand must be served from POPs or origin Output variables: Placement: Binary variable iXY indicates whether content X is stored at node Y Redirection Routing 14
Outline Network CDN NCDN Model & Joint Optimization Datasets: Akamai Traces & ISP Topologies Results Related Work 15
Datasets Akamai traces Traffic types On-demand video & download How measured? Instrument client software, e.g., media player plugin Data Content URL, content provider, lat-long, timestamp, bytes downloaded, file size Volume 7.79 m users, 28.2 m requests, 1455 TB data ISP topologies Networks Tier-1 US ISP & Abilene Data POP lat-long, link capacities Mapping: Akamai trace ISP topology Map request to geographically closest ISP POP 16
Outline Network CDN NCDN Model & Joint Optimization Datasets: Akamai Traces & ISP Topologies Results Schemes Evaluated Network Cost Latency Cost Network Cost: Planned vs. Unplanned Routing Related Work 17
Schemes Evaluated Scheme Routing + placement + redirection OSPF with link-weight = 1/link-capacity + LRU caching + redirect to closest hop count node UNPLANNED Realistic joint optimization Once per day with yesterday scontent demand Ideal joint optimization Once per day with current day s content demand JOINT- OPTIMIZATION ORACLE 18
Network Cost Tier-1 ISP Topology, Entertainment Trace 1 0.8 Normalized MLU 0.6 Joint Optimization Unplanned Oracle 3x 0.4 0.2 18% 0 0 2 4 Storage Ratio 19
Latency Cost Latency Cost = E2E propagation delay + Link utilization dependent delay Tier-1 ISP Topology, Entertainment Trace 10 Content placement matters tremendously in NCDNs Latency Cost 1 Joint Optimization Unplanned Oracle 0.1 28% 0.01 0 1 2 3 4 Storage ratio 20
Network Cost: Planned vs. Unplanned Routing Unplanned placement, unplanned routing vs. Unplanned placement, planned routing Tier-1 ISP topology, all traces Traditional TE gives small cost reduction in NCDNs 20 Max MLU Reduction (%) 10% or less 10 0 -10 News Entertainment Download 21
Related Work ISP-CDN joint optimization of routing & redirection (with fixed placement) [Xie 08, Jiang 09, Frank 12] Optimize placement (with fixed routing) for VoD content [Applegate 10] Location diversity even with random placement significantly enhances traditional TE [Sharma 11] 22
Conclusions Keep it simple Joint optimization performs worse than simple unplanned Little room for improvement over simple unplanned Content placement matters more than routing in Network CDNs 23
