Transcript Buffer Aggregation

Oasis: Anycast for Any Service
Michael J. Freedman
Karthik Lakshminarayanan
David Mazières
in NSDI 2006
Presented by:
Sailesh Kumar
Overview

Why Anycast?
» Availability, Load balancing, Performance

How to Implement Anycast?
» Replica selection problem

Oasis
» Replica Selection for many Services (amortized cost)
» Use Geographic Coordinates
» Fast Response Time
» Accurate Results

Architecture of Oasis
» How it works?
» Design choices


Evaluation
Discussion
‹#› - Sailesh Kumar - 7/7/2015
Anycast/Replica Selection

Data/Service replication is very common in Internet
» CDNs (e.g. Akamai, Coral)
» Distributed web mirrors,
» DNS servers
» Distributed (DHT based) storage/file systems

What is the
state today?
‹#› - Sailesh Kumar - 7/7/2015
Anycast is the Solution
mycdn
?
Animation taken from Freedman NSDI’06 slide

Anycast aids in selecting the replica which is
» Near the client
» Less loaded
» IP Anycast does not provide comprehensive selection policies
‹#› - Sailesh Kumar - 7/7/2015
Traditional Approach

Round-robin and DNS based techniques
» spread load but do nothing for network locality

Use On-demand probing
» probe client from multiple vantage points
» Usually accurate
» Significant probing required, can incur long latencies
» Many probing to a client can trigger intrusion-detection alarms

Such probing is needed for every service
» Access IBM (Akamai will probe you)
» Access Google video (you are again probed)
» Access a high volume website (you again need to be probed)
‹#› - Sailesh Kumar - 7/7/2015
Introducing Oasis

A single Anycast Solution for many services
» Amortize costs of probing

Perform probing off-line (probe the entire Internet)
» Faster response

Use geographic coordinates
» Geographic coordinates of IP prefixes are relatively stable
» Better than virtual coordinates
» Results may be more accurate

Provide flexible Anycast policies
» Balance between
– Bandwidth
– Accuracy
– Latency
‹#› - Sailesh Kumar - 7/7/2015
Oasis Architecture

A two-tier architecture
» A reliable core of hosts
» Replicas belonging to different services
» Replicas run Oasis specific code to
– Report their liveness and load information
– assist core nodes in network measurements

There are two primary ways clients access Oasis
» DNS redirection
» HTTP redirection
‹#› - Sailesh Kumar - 7/7/2015
DNS Redirection
mycdn
OASIS core
2
1
Client
Resolver
Animation taken from Freedman NSDI’06 slide


Client issues DNS request for a service using Oasis
OASIS will redirect the client to the nearest replica
‹#› - Sailesh Kumar - 7/7/2015
HTTP Redirection
mycdn
OASIS core
3
1
2
Client
Animation taken from Freedman NSDI’06 slide



Client issues HTTP request for the service
Service invokes Oasis code and contacts Oasis core
With Oasis info, client is redirected to better replica
‹#› - Sailesh Kumar - 7/7/2015
How Oasis resolves Anycast requests?

Core node maps client IP address to network bucket
» Network bucket consists of IP address prefixes

IP prefix is mapped to a location, say x (coordinates)
» Geographic coordinates of IP prefixes are stable

Replica whose location is closest to x is returned

Optionally, liveness
and load of replicas
can also determine
replica selection
‹#› - Sailesh Kumar - 7/7/2015
Mapping IP prefix to geographic coords?


First step is to map IP addresses a.b.c.d to the
nearest IP prefix say a.b.c.0/24
For the prefix, measurement is done by the replica
» Replicas form an overlay
» They traceroute to the IP prefix and registers the RTT
» If replica x has minimum RTT to prefix y, then the prefix y’s
geographic coordinates becomes the coords. of replica x
IP prefix (y)
proximity
( Latx, Lngx, RTT distance )
location
accuracy
Such address aggregation reduces the amount of probing
‹#› - Sailesh Kumar - 7/7/2015
How to find replica nearest to prefix?
Animation taken from Freedman NSDI’06 slide
“Probe 18.0.0.0/8”
18.168.0.23

Two-pronged approach
18.0.0.0/8
» Find closest replica proxy with less probing
» Use closest replica’s geo-coords + error RTT as location
‹#› - Sailesh Kumar - 7/7/2015
How to find replica nearest to prefix?
Animation taken from Freedman NSDI’06 slide
18.168.0.23
[ Meridian 05 ]

Two-pronged approach
» Find closest replica proxy with less probing
» Use closest replica’s geo-coords + error RTT as location
‹#› - Sailesh Kumar - 7/7/2015
How to find replica nearest to prefix?
Animation taken from Freedman NSDI’06 slide
18.168.0.23
18.0.0.0/8[: Meridian
(42N,71W), 6.0
05ms
]

Two-pronged approach
» Find closest replica proxy with less probing
» Use closest replica’s geo-coords + error RTT as location

Probing of prefixes are done very infrequently (once a week)
‹#› - Sailesh Kumar - 7/7/2015
How Oasis maintains its database?





For every service, there is a rendezvous core node
(via consistent hashing, H(serv))
Whenever replicas join, leave, change state, they
notify its rendezvous node, also notify abt. liveness
Rendezvous gossip liveness to other core nodes
Every replica also sends keepalives to its nearest
core Oasis node
Nodes in the core keeps their data structures weakly
consistent via gossiping
» Uses incarnation numbers to indicate the latest info
» Uses consistent hashing to distribute load across nodes

DNS is one of the services provided by Oasis
» Thus, first step in resolving any Anycast request is to provide
the nearest core node to the client
‹#› - Sailesh Kumar - 7/7/2015
Operation of Oasis?

A client queries OASIS for hostname coralcdn.nyuld.net:
»
»
The client queries the DNS root servers, finds OASIS core node I
Core lookup: Node I finds other core nodes near the client:
–
–
–
–
»
»
I maps client’s IP address to IP prefix, and then prefix to location coords.
I queries the rendezvous node for service dns, H(dns). Call this node SI.
SI responds with the best-suited OASIS node for the specified
coordinates.
I returns this set of DNS replicas to the client. Let this set include node J.
The client resends the Anycast request to J.
Replica lookup: Core node J finds
replicas near the client:
– J extracts the request’s service
name and maps the client’s IP
address to coordinates.
– J queries rendezvous node
for service coralcdn, call this SJ.
– SJ responds with the best
coralcdn replicas, which J
returns to the client.
‹#› - Sailesh Kumar - 7/7/2015
Evaluation




Replicas on 250 PlanetLab nodes around the world
Oasis core on 37 nodes
Meridian: Uses on-demand probing (geographic coordinates)
Vivaldi: Uses on-demand probing (virtual coordinates)
‹#› - Sailesh Kumar - 7/7/2015
‹#› - Sailesh Kumar - 7/7/2015
Evaluation
‹#› - Sailesh Kumar - 7/7/2015
Evaluation
‹#› - Sailesh Kumar - 7/7/2015
Evaluation
Deployment till Date
‹#› - Sailesh Kumar - 7/7/2015
Discussion

Is it OK to incorporate Anycast capability within the IP protocol?
»
»
If yes, then we do not need Oasis like infrastructure
However, like multicast, feature rich anycast may not be efficiently
incorporated within the IP protocol

Is Oasis much different from what Akamai may already be
doing?

One of the motivations behind Oasis is Intrusion-detection
alerts
»

What happens if prefixes are not as geographically stable?
»

Such a motivation appears unconvincing, as there are many other
ways to work around this problem
Will they become less stable in mobile context?
What is your general opinion about Oasis
»
To me the results appear surprisingly good
‹#› - Sailesh Kumar - 7/7/2015