展开查看详情
1.Algorithmic Nuggets in Content Delivery Presenter: Sikder Huq Algorithmic Nuggets in Content Delivery 1
2.Content distribution networks challenge : how to distribute web contents to hundreds of thousands of simultaneous users? option 1: single, large “mega-server” single point of failure point of network congestion long path to distant clients multiple copies of content sent over outgoing links ….quite simply: this solution doesn ’ t scale 2- 2 Algorithmic Nuggets in Content Delivery
3.Content distribution networks challenge : how to distribute web contents to hundreds of thousands of simultaneous users? option 2: store/serve multiple copies of videos at multiple geographically distributed sites (CDN) enter deep: push CDN servers deep into many access networks close to users used by Akamai, 1700 locations, 170K+ edge servers bring home: smaller number (10’s) of larger clusters in POPs near (but not within) access networks used by Limelight Algorithmic Nuggets in Content Delivery 2- 3
4.Content Distribution Networks (CDNs) … … … … … … subscriber requests content from CDN CDN: stores copies of content at CDN nodes e.g. Netflix stores copies of MadMen where’s Madmen? manifest file directed to nearby copy, retrieves content may choose different copy if network path congested Algorithmic Nuggets in Content Delivery 4
5.Content Distribution Networks (CDNs) … … … … … … Internet host-host communication as a service challenges : coping with a congested Internet from which CDN node to retrieve content? viewer behavior in presence of congestion? what content to place in which CDN node? “over the top” Algorithmic Nuggets in Content Delivery 5
6.CDN content access: a closer look Bob (client) requests video http://netcinema.com / 6Y7B23V video stored in CDN at http://KingCDN.com/NetC6y&B23V netcinema.com KingCDN.com 1 1. Bob gets URL for video http://netcinema.com/6Y7B23V from netcinema.com web page 2 2. resolve http://netcinema.com/6Y7B23V via Bob’s local DNS netcinema’s authoratative DNS 3 3. netcinema’s DNS returns URL http://KingCDN.com/NetC6y&B 23V 4 4&5. Resolve http://KingCDN.com/NetC6y&B23 via KingCDN’s authoritative DNS, which returns IP address of KingCDN server with video 5 6. request video from KINGCDN server, streamed via HTTP KingCDN authoritative DNS Bob’s local DNS server Algorithmic Nuggets in Content Delivery 6
7.Case study: Netflix 1 1. Bob manages Netflix account Netflix registration, accounting servers Amazon cloud CDN server 2 2. Bob browses Netflix video 3 3. Manifest file returned for requested video 4. Streaming upload copies of multiple versions of video to CDN servers CDN server CDN server Algorithmic Nuggets in Content Delivery 7
8.Embedded Image Delivery (e.g., Yahoo!) <html> <head> <title>Welcome to xyz.com!</title> </head> <body> < img src =“ < img src =“ <h1>Welcome to our Web site!</h1> <a href =“page2.html”>Click here to enter</a> </body> </html> http://www.xyz.com/logos/logo.gif”> http://www.xyz.com/ jpgs /navbar1.jpg”> Embedded URLs are Converted to ARLs (Akamai) ak Algorithmic Nuggets in Content Delivery 8
9.CDN objectives High reliability Fast and consistent service Low cost Algorithmic Nuggets in Content Delivery 9
10.Algorithms used in CDN Stable marriage with tree constraints Global/cluster level load balancing Consistent hashing Local/server level load balancing Bloom filters To decide what contents to cache in servers Overlay routing To route contents from origin to edge servers Leader election For fault-tolerant decision-making Algorithmic Nuggets in Content Delivery 10 Survey paper: Algorithmic Nuggets in Content Delivery Authors: Bruce Maggs and Ramesh Sitaraman (Thanks to the authors for sending me slides on request)
11.In this talk… Stable marriage with tree constraints Global/cluster level load balancing Consistent hashing Local/server level load balancing Bloom filters To decide what contents to cache in servers Overlay routing To route contents from origin to edge servers Leader election For fault-tolerant decision-making Algorithmic Nuggets in Content Delivery 11
12.Hashing Algorithmic Nuggets in Content Delivery 12 E.g., h(x) = (((a x + b) mod P) mod |B|) , where P is prime, P > |U| a,b chosen uniformly at random from Z P x is a serial number Universe U of all possible objects, set B of buckets. object: set of web objects with same serial number bucket: web server Hash function h: U B Assigns objects to buckets
13.Difficulty changing number of buckets Algorithmic Nuggets in Content Delivery 13 f(d) = d + 1 mod 5 5 7 10 11 27 29 36 38 40 43 4 3 2 1 0 bucket object f(d) = d + 1 mod 4
14.A ring based hash space (consistent hashing ) Consistent Hashing 14 K B C J D L E G F I H A Object a H(a) Hash function Served by D Object b H(b) Hash function Served by G Algorithmic Nuggets in Content Delivery
15.Consistent Hashing Algorithmic Nuggets in Content Delivery 15 Idea: Map both objects and buckets to unit circle. Object Bucket/server Assign object to next bucket on circle in clockwise order. new bucket
16.Properties of Consistent Hashing Algorithmic Nuggets in Content Delivery 16 Monotonicity: When a bucket is added/removed, the only objects affected are those that are/were mapped to the bucket. Balance: Objects are assigned to buckets “ randomly”. -- can be improved by mapping each bucket to multiple places on unit circle (virtual nodes) Load: Objects are assigned to buckets evenly, even over a set of views. Spread: An object should be mapped to a small number of buckets over a set of views.
17.Multiple presence of a server in hash space 3 servers: A , B and C Each server has 4 positions in the ring Why? Load-balancing for server addition/removal Heterogeneity Virtual nodes C1 C3 C2 C4 B4 A2 A1 B1 A3 B3 A4 B2 Hash space of server A 17 Distributed Load Balancing in Key-Value Networked Caches
18.Actual low level load-balancing algorithm Algorithmic Nuggets in Content Delivery 18 a212: 10.10.10.1 10.10.10.4 10.10.10.3 10.10.10.2 a213: 10.10.10.3 10.10.10.4 10.10.10.2 10.10.10.1 a214: 10.10.10.1 10.10.10.2 10.10.10.3 10.10.10.4 a215: 10.10.10.2 10.10.10.1 10.10.10.4 10.10.10.3 random permutations of servers Why? To spread load for one serial number.
19.Leader Election Example All low-level name servers for a cluster compute the hash table. One is elected leader and distributes its table to the others. Algorithmic Nuggets in Content Delivery 19
20.Stable Marriages Algorithmic Nuggets in Content Delivery 20 Assignment of men and women Each man ranks each woman and vice versa Marriage stable if no pair ( m,w ) unmatched where m prefers w to his “wife” and w prefers m to her “husband” 3 2 4 2
21.Residents-Hospitals Extension Residents-Hospitals results + algorithm extends to case in which hospital j can accept c(j) residents In use since 1951 by National Intern Matching Program Algorithmic Nuggets in Content Delivery 21
22.Multi-Dimensional Load Not a single constraining resource! Can be: Bandwidth CPU usage (e.g. key signing for https) Disk usage (e.g. for cache misses, auction sites) Memory (e.g. EdgeJava ) Threads (e.g. EdgeJava ) Number of licenses in RealAudio Algorithmic Nuggets in Content Delivery 22
23.Stable Allocations With Tree Constraints [G ’00]: resources 1,…,k Supply item j has rooted tree T(j) of constraints V(T(j))={1,…,k} Every node v of T has capacity c( j,v ) Demand item i has basic resource b( i ) and demand d( i ) When x units mapped to supply j, uses x units of each resource on path in T(j) from b( i ) to root of T(j) Stability as before Algorithmic Nuggets in Content Delivery 23
24.Instance of Problem Demand items: (groups of IPs, rule for mapping) m=hundreds of thousands Supply items: cluster of servers n=thousands (Incomplete) preference lists for demands based on performance + contract rules (Implicit) preference lists for supplies based on alternate choices, contract rules, … Tree of constraints model various resource constraints Algorithmic Nuggets in Content Delivery 24
25.Algorithm for Tree Constraints Algorithmic Nuggets in Content Delivery 25 [9,9] [0,9] [7,9] [2,9] [7,9] [9,9] 2 3 Demand items request unassigned demands in order of preference When demand i requests x units from j, repeat: Find lowest (in tree) tight constraint, say node v Dispose demands (up to x) of lower preference than i and using resources in subtree rooted at v Demand = 2 3 5 5 8 [0,8] [0,9] [0,6] [0,12] [0,5] [0,7] [load,cap] [2,6] [2,9] [2,12] [3,5] [5,12] [5,7] [10,12] 2 [2,8] [4,9] [12,12] [0,6] [2,9] [10,12] 4 [4,9] [12,12] [4,8] 1 [1,7] [5,9] [8,12] 8 [8,8] [8,9] [12,12]
26.Acknowledgement 26 Algorithmic Nuggets in Content Delivery Many of the slides are taken from the following sources: Computer Networking – A Top-Down Approach (Kurose and Ross) Slides on Key Algorithms in Content Delivery System by professor Maggs
27.Thanks for your attention! Questions? 27 Algorithmic Nuggets in Content Delivery Presenter: Sikder Huq PhD Candidate (Computer Science) The University of Iowa e-mail: sikderrezwanul-huq@uiowa.edu
