[Paper Notes] Andromeda: Performance, Isolation, and Velocity at Scale in Cloud Network Virtualization

06 Jul, 2025

NSDI'18, by Google

TL;DR: In Andromeda, each NIC queue has one busy-polling userspace thread. For every packet it does one hash lookup, grabs a pre-computed action, edits headers, and transmits—no locks, syscalls, or kernel path—so common VM-to-VM traffic crosses the host in ~0.3 µs, while heavyweight features are off-loaded to helper threads (coprocessor).

1 Problem / Motivation

Cloud VMs demand hardware-like bandwidth (<100 µs p99) yet must share hosts with thousands of other tenants.
2012-era stack (UDP tap inside the VMM → Linux kernel) hit CPU, latency and feature ceilings at ~2 Gb/s per core and offered no in-cloud firewalls, LB, or NAT.
Need a design that gives performance, rich middlebox functions, isolation and easy global live-migration—all while being deployable on commodity servers/NICs.

2 Key Idea

“Compile everything once, run packets in one tight loop.”

Decouple control vs. data
- Control plane (Fabric-Manager, VMCs, vswitchd) computes per-flow policy once on a miss.
- Dataplane (Fast Path engine) consists of a set of packet processing push/pull elements (just think of a unit of task, e.g. routing, fan-in/out, flow monitoring/debugging).
OS-bypass, busy-polling userspace dataplane (Andromeda 2.0)
- Maps all guest pages, copies directly between guest rings and NIC.
- One core = one RX/TX queue, zero locks, zero syscalls in steady state.
Flow Table (FT) + Action Table
- Single hash on 3-tuple (falls back to 5-tuple only when needed) → dense flow-index.
- Action entry holds: header-rewrite template, dst vPort (quick forwarding decision), bitmap of micro-stages (additional processing like coprocessor).
Stage Bitmaps
- Fast-Path stages (<50 cycles): encap, VLAN, tiny firewall port-mask, conntrack bump.
- Coprocessor stages: heavy ACLs, IPSec, shaping—handled by helper thread/SmartNIC.

3 Control Plane Architecture

┌─────────────────────────────────────────────────────────────────────────────┐
│  ☁ Tenant API  (UI / gcloud / Terraform)                                   │
└───────────────┬─────────────────────────────────────────────────────────────┘
                │ 1  declarative intent: “Create VPC X, subnet Y, firewall Z”
▼
┌────────────────────  Global fabric manager  ────────────────────────────────┐
│ **Fabric-Manager (FM)**                                                     │
│ • Stores tenant/network objects in a Paxos-replicated datastore             │
│ • Runs the *compiler* that turns high-level objects into **abstract port &  │
│   flow specs** (no physical locations yet)                                  │
└───────────────┬─────────────────────────────────────────────────────────────┘
                │ 2  pushes abstract specs + host/VM inventory
▼
┌──────────── Cluster-scope control layer (tens of servers) ──────────────────┐
│ **VMCs – “Virtual Machine Controllers”**                                    │
│ • Cluster is sharded by VM-UUID hash; each shard has a *primary* VMC        │
│ • On startup subscribes to “its” slice of VM hosts via FM                   │
│ • When a host switch connects, VMC reads its *actual* OpenFlow tables,      │
│   diffs against desired state, then issues incremental updates              │
│ • All control logic (LB backend pick, NAT port allocation, hairpin rule     │
│   creation on live-migration) happens here **once per flow miss**           │
│ • Replicated with leader election; shard can migrate without host impact    │
└───────────────┬─────────────────────────────────────────────────────────────┘
                │ 3  RPC (gRPC) carrying high-level OpenFlow commands
▼
┌───────────── Thin stateless proxy layer – “always up” ──────────────────────┐
│ **OpenFlow Front Ends (OFEs)**                                              │
│ • One per VM host (usually on an out-of-band mgmt VM)                       │
│ • Terminates TLS from the switch, multiplexes to the correct VMC            │
│ • Keeps a persistent TCP channel so the data-plane never notices            │
└───────────────┬─────────────────────────────────────────────────────────────┘
                │ 4  OpenFlow messages (add-flow / modify-flow / pkt-in …)
▼
┌────────────── Host-local control agents ────────────────────────────────────┐
│ **vswitchd** (in VMM)                                                       │
│ • Owns the **Flow Table (FT) & Action Table**                               │
│ • Installs results computed by VMC                                          │
│ • Handles the very first packet of a new 5-tuple (flow miss)                │
│ **Flow-Miss Coprocessor**                                                   │
│ • Shuttles that miss up to vswitchd without blocking the Fast Path          │
└───────────────┬─────────────────────────────────────────────────────────────┘
                │ 5  shared-memory ring to…
▼
┌────────────────  Userspace Fast-Path engine  ───────────────────────────────┐
│ Busy-polling, lock-free dataplane (∼300 ns / pkt)                           │
└─────────────────────────────────────────────────────────────────────────────┘

Layer Comparison:

Layer	Scope	What state it keeps	Why it exists
FM	whole planet	tenant objects, ACLs, routes, VM inventory	Authoritative source of truth; slow-changing, strongly consistent
VMC	single cluster (≈10 k hosts)	desired flow entries for its shard, plus lightweight conn-track	Absorbs churn (VM boots, migrations) and compiles intent into concrete OpenFlow
OFE	single host	almost none (just in-flight msgs)	Provides a stable TCP endpoint so switches survive VMC restarts/re-shards
vswitchd	per host	hot FT / actions cache, minified firewall masks	Keeps control logic off the dataplane core; still far lighter than FM/VMC
Fast Path	per core	nothing persistent	Raw performance; executes pre-baked “recipes” with no locks/syscalls

4 Data Plane Architecture

                ┌────────────  TCP/IP guests  ────────────┐
   VM memory    │ virtio-net rings (shared pages)         │
                └────────────┬────────────────────────────┘
                             │ kick / MSI-X
          only I/O           ▼
  ┌ VMM (qemu-kvm helper) ──────────────┐
  │ • Owns virtio rings & injects ints  │
  │ • Very thin after A-2.0             │
  └────────────┬────────────────────────┘  SPSC shared-mem rings
               │ pkt-desc (+ tiny hdr)    
               ▼
  ┌────────────┴────────────┐   one per RX/TX queue pair, cpu-pinned
  │  **Fast-Path engine**   │   (DPDK-style busy poll)
  │  • hugepage mempool     │
  │  • parses L2/L3 once    │
  │  • FT hash → flowIndex  │
  │  • Action[flowIndex]:   │→ optional enqueue to
  │         − header tmpl   │  Coprocessor ring(s)
  │         − dst vPort     │
  │         − fastStageBits │
  │         − coproBits     │
  └──────┬───────────┬──────┘
         │           │
         │           └────────── missed? → Flow-Miss Coprocessor
         │                             (shared queue, non-blocking)
         │                                     │
         ▼                                     ▼
   NIC DMA                                 vswitchd (control daemon)

Data Structure

Object	Stored in	Lifetime	Purpose
FT hash table	hugepage RAM, per engine	per-flow	3- or 5-tuple → dense flowIndex
Action array	same	per-flow	header template, dst port, fastStageBits, coproBits
Stage bitmaps	per action	const	encode micro-ops (< 50 cycles) or Coprocessor hand-off
SPSC rings	shared memory	long-lived	VMM ↔ FastPath, FastPath ↔ Copro

Packet Lifetime

RX DMA lands in NIC queue → FastPath core polls.
Parses outer/inner hdrs, forms 3-tuple → FT lookup.
- miss? → recompute 5-tuple → retry.
- double-miss? → enqueue to Flow-Miss Coprocessor.
Hit → fetch Action:
- apply header rewrite & encap template.
- if fastStageBits≠0 run inlined micro-functions (VLAN_PUSH, FW_PORTMASK, CONNTRACK_INC, …).
- if coproBits≠0 push pointer to Coprocessor ring.
Transmit to dst vPort (host-local virtio queue) or physical NIC TX.
For TX from VM the path is symmetric (virtio → FastPath → NIC).

Per-packet cost in common VM↔VM overlay case ≈ 300 ns (one cacheline).

5 Middlebox Functions

On a flow miss vswitchd runs the expensive stuff once (full firewall rules, VIP backend pick, NAT port alloc) and writes the result into the action entry.
Common VM↔VM flows → bitmap = 0 → no per-packet penalty.
For stateful firewall: if rules say “always allow”, bitmap stays clear; else a tiny port-range check & optional conntrack counter are enabled.

6 Live-Migration Trick

During routing-table blackout the source host installs a hairpin flow: any packets still sent to old location are tunneled to the destination host.
Once the fabric converges, hairpin is removed—zero loss to the VM.

7 Why It Matters

Performance – p99 latency < 100 µs, 10 + Gb/s per core; scales with NIC queues not CPU sockets.
Economics – saves hardware middleboxes; host CPU per Gb cut by ≥ 5× vs. 2012 design.
Feature velocity – new middlebox logic dropped into control-plane compilers, not datapath rewrites.
Isolation – per-flow actions + conn-track keep tenants from interfering.
Global operations – hairpin flows ± controller partitioning allow cross-cluster live migration.