CDN

Summary

• DHT
  • DHT Details
• CDN as an Overlay Network
  • Overlay Networks in General
• DHTs and CDNs
  • Traditional Approach
    • Greedy Approach Leads to Metadata Server Overload
    • Origin Server Overload
    • Greedy Approach Leads to Tree Saturation
• Key Based Routing
  • Coral Key Base Routing
• Coral Sloppy DHT
• Coral In Action

DHT

Distrubted Hash Table

<key, value> = hash of content and node_id where content is stored

For DHT, $\text{key } \simeq \text{ node id}$

So if content was stored in node 80, and the hash == 149, we would store <149, 80> in node 150

DHT Details

Namespaces:

• key space
  • hash of content
• Node space
  • Hash of ip addr

APIs

• putkey(key, value)
• getkey(key) value

CDN as an Overlay Network

Overlay Networks in General

Examples:

• OS
  • IP Network is an overlay on lan
    • IP addr over Mac addr
• App
  • CDN
    • Node id over IP

DHTs and CDNs

Placement

• Put <Key, Value>
  • <content hash, node where content is stored>

Retrieval of value given key

• get ->

Traditional Approach

Place <key, value> in node n, where n ~ key

retrieve: given key, goto node n (closest to k)

Greedy Approach Leads to Metadata Server Overload

Nothing is stopping the hashes from all going to the same nodes

Origin Server Overload

Nothing is stopping the content from all going to the same node

Central authority could mirror content and redirect requests, but that is not simple

Greedy Approach Leads to Tree Saturation

Place <key, value> in node n, where n ~ key is a hint, not absolute

Coral DHT

• Get/Put Satisfied by nodes different from n ~ key -> sloppy DHT

Rationale

• avoid tree saturation
• spread metadata overload

How?

• Novel key-based routing
  • XOR distance between src + dst

Key Based Routing

Greedy intuition is to get as close to the dest in node_id

• That node may know how to get to the dst node
• “me first” approach

Coral Key Base Routing

Each hop go to some node about halfway to dst

In actuality, if the halfway point isn’t there, you go to the next closer one to the dst

After you make multiple hops, you learn the path traveled and add it to you routing table

Coral Sloppy DHT

Primitives

• Put (Key, Value)
  • value = node id of proxy with content for key
  • Announcing willingness to serve as a proxy

Full

• Max l content providers for up to key k
  • Spatial

Loaded

• Max b request rate for key k
  • Temporal

If any step along the way is Full or Loaded, assume the rest is Full or Loaded and place kv pair on last successful node

Coral In Action

Even though an individual request may increase latency, the tradeoff is that multiple servers can dynamically become proxies which lowers the demand of the origin server