Overlay Endpoint Resolution and Its Caches

Forwarding inside an overlay is a lookup on a key that the network above never sees. The key is the virtual network identifier together with the inner destination, and the value is the underlay address of the endpoint that can deliver to it. Every design decision in an overlay control plane is ultimately about who computes this mapping, where it is stored, and how long a stored copy is allowed to be wrong.

The shape of the key

For a Layer 2 overlay, the inner destination is a MAC address. For a Layer 3 overlay it is an IP prefix, or an IP address, or a pair of them when the overlay routes between subnets. The virtual network identifier is part of the key because the same MAC or the same private address can exist in several tenants at once; without it, two tenants’ tables would collide.

The distinction between a MAC-keyed and a prefix-keyed table is not cosmetic. A MAC table is flat and its size is the number of guests the host must reach, which for a virtual network spanning a thousand hosts is a thousand entries per host. A prefix table is hierarchical and its size is the number of distinct prefixes, which is much smaller when guests are addressed in contiguous blocks. An overlay that carries only IP traffic can therefore use a table that is an order of magnitude smaller, at the cost of losing the ability to deliver non-IP frames and of requiring the inner hosts to be addressed in a way that aggregates.

The value side has more variation than the key side. A minimal mapping is just the remote endpoint’s underlay address. A realistic one also carries the encapsulation type, the remote VNI when it differs from the local one, a sequence number for detecting a newer announcement, and a flag distinguishing a locally learned entry from a distributed one. Implementations that omit the sequence number cannot order two announcements for the same key, and the resulting behaviour on a migration is to keep whichever arrived last, which is not the same as whichever is newest.

Where the table lives, and why it is per-host

The mapping is held at the endpoint, not in the fabric. This follows from the previous split: the underlay forwards on the outer address and has no reason to inspect the inner one, so the only place the two can be related is the endpoint that performs the encapsulation.

Holding it at the endpoint has three consequences. The first is that the total state is the sum over hosts of the mappings each host needs, which for a densely connected overlay is close to the square of the endpoint count. A fabric of a thousand endpoints where every endpoint must reach every other holds a million entries in aggregate, though only a thousand per host. The second is that the state is not authoritative anywhere; there is no single table that says where a given MAC is, only a thousand local opinions that must agree. The third is that a host’s table can be lost without affecting any other host, which makes restarts cheap and makes disagreement easy.

Some designs add a central mapping service that endpoints query, which converts the distributed opinion into an authoritative answer. That reduces the table size at each endpoint and makes the answer consistent, but it introduces a dependency: an endpoint that cannot reach the service cannot resolve a new destination, and the service becomes a scaling and availability problem of its own. The trade is between local autonomy and global consistency, and it is the same trade that appears in every distributed lookup system.

Caching, and the two kinds of staleness

Whatever computes the mapping, it is cached at the endpoint because the computation is expensive relative to a packet. A cache entry can be wrong in two ways, and they are not equally bad.

A missing entry costs a lookup. The endpoint must consult the control plane or flood, and the packet is either delayed or dropped for one round trip. The system recovers as soon as the answer arrives, and the cost is bounded and visible. Where the control plane is BGP, defined in RFC 4271, the endpoint cannot query it directly: BGP is a push protocol, so a route arrives when a peer sends it, and a missing route cannot be turned into a request for that route.

A stale entry costs correctness. The endpoint forwards confidently to a host that has since lost the destination, and the packet is delivered to a machine that either drops it or, worse, has already given the address to a different guest in the same virtual network. The second case is the serious one: the packet is well-formed, the destination accepts it, and traffic intended for one guest reaches another. Nothing in the packet indicates the error, because the packet is correct in every field.

That asymmetry is why every cache needs an invalidation path and why the invalidation path is more important than the fill path. The fill path only affects the first packet; the invalidation path affects every packet after a change.

The mechanisms available are few. An entry can expire after a fixed interval, which bounds staleness by the interval and costs a re-resolution at the boundary. An entry can be withdrawn by the control plane when the destination moves, which is exact but depends on the withdrawal being sent and received. An entry can be validated on use by comparing a sequence number, which catches a newer announcement but not a silent departure. An entry can be flushed when the endpoint’s session with the control plane resets, which bounds staleness by session lifetime.

The last is the most underappreciated. A control-plane session that resets does not necessarily mean the mappings changed, but treating a reset as a reason to discard everything is safe in the direction that matters: it converts a possible stale entry into a missing entry, and missing is the recoverable failure. The cost is a burst of re-resolution after every session flap, which is acceptable if the session is stable and unacceptable if it is not.

What a resolution actually returns

A resolution is not a single address in a realistic design. It returns an ordered set of candidates, because the destination may be reachable through more than one endpoint: a guest that has migrated recently may still be reachable at the old host through a forwarding rule, and an endpoint may have more than one underlay address for redundancy.

The ordering rule matters for the same reason the invalidation rule does. If the candidates are tried in announcement order, a stale candidate at the front delays every packet until it fails. If they are tried in preference order with the newest first, the common case is one attempt. Where the two orders conflict, the sequence number should dominate, because it is the only field that distinguishes a newer announcement from an older one.

The resolution also has to state whether the answer permits flooding. A control plane that distributes complete information can say that an unknown destination does not exist, and the endpoint should drop. A control plane that distributes partial information cannot say that, and the endpoint must flood. The distinction has to be explicit in the interface, because an endpoint that floods when it was told the destination does not exist reintroduces exactly the amplification the control plane was meant to remove. Flood and learn versus a BGP EVPN control plane sets out the cost curve that this decision moves an endpoint along.

Failure modes worth naming

A resolution loop is possible when the mapping for a destination points at an endpoint that resolves the same destination back to the first. This happens when two hosts both announce the same MAC, which is a configuration error but a common one during a migration that was performed by hand. The packets oscillate until a hop limit or an outer TTL stops them, and the outer TTL is the only limit that applies, since the inner TTL is not decremented by the tunnel.

A mapping that is correct but unreachable is the second failure. The endpoint knows where the destination is and encapsulates toward it, but the underlay has no route to that endpoint address, or the path is broken. The packet is dropped by the underlay and the endpoint has no feedback, because the underlay’s ICMP error goes to the endpoint’s own address and, as described in tunnel encapsulation overhead and path MTU, correlating it back to an inner flow requires state the endpoint may not have. The symptom is a destination that resolves, encapsulates, and never answers.

The third is cache poisoning by a forged announcement. Because the control plane is a routing protocol, its security is the security of the BGP session, and a session that is not authenticated can inject a mapping that redirects traffic for a MAC to an endpoint under another party’s control. The overlay inherits BGP’s threat model along with its scalability, and the mitigations are the ones BGP already has: session authentication, prefix and route-target filtering, and limiting which peers may announce which virtual networks.

The fourth is the interaction between the mapping cache and the ARP or neighbour cache in the guest. A guest that has a stale ARP entry sends frames to a MAC that has moved, and the endpoint’s mapping for that MAC may be correct while the guest’s belief about which MAC owns which IP is wrong. The two caches age on independent timers, and there is no mechanism that synchronizes them. This is why a migration procedure usually includes a gratuitous announcement from the moved guest, which updates the guests’ ARP caches without waiting for either timer.