Address Resolution Protocol (ARP)

The Address Resolution Protocol is a link-layer-adjacent protocol that maps a network-layer address (an IPv4 address) to a link-layer address (a 48-bit Ethernet MAC address), for hosts that share the same physical or virtual broadcast domain. ARP is defined for IPv4 by RFC 826; it operates below IP in the sense that IP relies on it, but it is encapsulated directly inside an Ethernet frame (EtherType `0x0806`), not inside an IP packet. This placement is important: ARP messages have no IP header, so they cannot be routed — they are inherently confined to one Ethernet segment. The central data structure ARP maintains on every host is the ARP cache (also called the ARP table): a set of entries, each a triple `(IP address, MAC address, timestamp/state)`. When a host's IP layer needs to send a packet to a destination on the same subnet, it consults this cache first. A cache hit costs nothing beyond a table lookup. A cache miss triggers the resolution protocol proper: a broadcast ARP request frame asking "who has IP address X? tell me at MAC address Y," followed (if some host owns X) by a unicast ARP reply frame carrying that host's MAC address. The querying host then inserts the new mapping into its cache before proceeding. Two refinements matter for a precise understanding. First, gratuitous ARP: a host can broadcast an ARP request for its own IP address, primarily to announce "I am here with this MAC," update other hosts' caches proactively (e.g., after a failover or IP reassignment), and detect IP address conflicts (if a reply comes back, someone else already claims that IP). Second, proxy ARP: a router can answer ARP requests on behalf of hosts on a different subnet, effectively pretending to be the destination at the link layer while actually forwarding packets onward — a technique now largely superseded by proper routing and VLAN configuration, but still useful for legacy address-hiding.

The protocol logic has two symmetric halves: what a host does when it needs to resolve an address (the requester), and what a host does when it receives a request that names its own IP (the responder). Every host runs both halves simultaneously.

ARP packet format (for Ethernet/IPv4, the common case):

The whole ARP message is wrapped in an Ethernet frame whose destination MAC is `FF:FF:FF:FF:FF:FF` (broadcast) for a request, and the requester's unicast MAC for a reply.

Step-by-step resolution algorithm: 1. Host A's IP layer wants to send a packet to IP address T, determined (via the subnet mask) to be on the same LAN. 2. A checks its ARP cache for an entry keyed on T. 3. If found and not expired: use the cached MAC as the Ethernet destination address, hand the frame to the link layer, done — no network traffic generated. 4. If not found (cache miss): A constructs an ARP request with `SPA = A's IP`, `SHA = A's MAC`, `TPA = T`, `THA = 0`, and broadcasts it on the LAN. 5. Every host on the LAN receives the broadcast frame (this is the cost of resolution) and inspects TPA. 6. Any host that is not the owner of T silently discards the request (but see the cache-learning aside below). 7. The host that does own IP address T constructs an ARP reply with `SPA = T`, `SHA = its own MAC`, `TPA = A's IP`, `THA = A's MAC`, and sends it unicast back to A. 8. A receives the reply, inserts `(T, replier's MAC)` into its cache with a fresh timestamp, and now sends the originally queued packet(s). 9. Cache entries expire after a timeout (commonly on the order of minutes, e.g., 60–240 seconds in many OS defaults, sometimes up to 20 minutes) to accommodate NIC replacements, IP reassignment, or virtual machine migration. A useful optimization many implementations perform at step 5–6: even hosts that are not the target may opportunistically cache the sender's `(SPA, SHA)` mapping from the request, since it's provided for free and likely to be useful soon (A is about to become a communication partner for others too). ``` // Executed by every host; state = local ARP cache (map: IP -> (MAC, timestamp)) function SEND_IP_PACKET(destIP, payload): if destIP is on local subnet: targetIP = destIP else: targetIP = nextHopRouterIP // resolve router's MAC, not destIP's entry = ARP_CACHE.lookup(targetIP) if entry exists and not expired(entry): macDest = entry.mac send_ethernet_frame(macDest, payload) return // cache miss: must resolve queue_packet_pending(targetIP, payload) // hold packet until resolved if not already_waiting_for(targetIP): request = build_ARP_request( SHA = myMAC, SPA = myIP, THA = 0, TPA = targetIP) broadcast_ethernet_frame(request) start_retransmit_timer(targetIP) // resend if no reply in time function ON_RECEIVE_ARP_PACKET(pkt): // Opportunistic learning: cache the sender's mapping regardless of role ARP_CACHE.insert_or_refresh(pkt.SPA, pkt.SHA, now()) if pkt.OPER == REQUEST: if pkt.TPA == myIP: reply = build_ARP_reply( SHA = myMAC, SPA = myIP, THA = pkt.SHA, TPA = pkt.SPA) send_ethernet_frame(dest = pkt.SHA, reply) // unicast // else: not addressed to me, discard after opportunistic caching else if pkt.OPER == REPLY: if pkt.TPA == myIP: ARP_CACHE.insert_or_refresh(pkt.SPA, pkt.SHA, now()) for each queuedPacket in pending_for(pkt.SPA): send_ethernet_frame(pkt.SHA, queuedPacket) clear_pending(pkt.SPA) cancel_retransmit_timer(pkt.SPA) function CACHE_MAINTENANCE_TICK(): // runs periodically, e.g. every few seconds for each entry in ARP_CACHE: if now() - entry.timestamp > CACHE_TIMEOUT: ARP_CACHE.remove(entry) ``` Edge cases the pseudocode must handle correctly:

• Retransmission and packet queuing: while waiting for a reply, further packets to the same destination must not each trigger a new broadcast; they queue behind the single outstanding request.
• No answer (host T is down): after a bounded number of retries the IP layer gives up and reports "destination unreachable" upward — ARP itself has no notion of failure beyond a timeout.
• Duplicate replies / conflicting mappings: if two replies name different MACs for the same IP (a misconfiguration or an attack), most implementations overwrite with the most recent, which is exactly the property ARP-spoofing defenses must guard against.
• Gratuitous ARP: when `SPA == TPA` in a request, every receiving host should refresh (or insert) that mapping in its cache immediately, without needing a reply.

Message and time complexity. In the worst case (cold cache), resolving one address costs exactly one broadcast frame plus one unicast reply — O(1) messages, independent of subnet size, because a single broadcast reaches all N hosts simultaneously in one physical transmission rather than N unicast probes. The per-host processing cost of a request is O(1): a single equality check `pkt.TPA == myIP`. Across a LAN of N hosts, the aggregate work triggered by one ARP request is O(N) (every host must at least inspect and discard/accept the frame), but this is inherent to broadcast media and is the same cost any broadcast-based discovery protocol pays.

Space complexity. The ARP cache holds at most one entry per distinct IP address ever contacted recently, so cache size is O(k) where k is the number of active local correspondents, bounded in practice by subnet size (at most ~254 hosts in a /24) and by the cache timeout, which evicts stale entries. This is far cheaper than a full static table requiring O(N) preconfigured entries maintained by hand on every host.

Amortized cost. Because resolved mappings are cached, the amortized number of broadcasts per packet sent tends toward zero: if a host exchanges M packets with the same neighbor before the cache entry expires, only 1 of those M packet-sends incurs a broadcast, giving amortized broadcast cost O(1/M) per packet. The timeout value is a tunable tradeoff: longer timeouts amortize better but risk staleness (e.g., after a NIC swap or DHCP lease change to a different device); shorter timeouts track topology changes faster but broadcast more often.

Correctness argument. The essential invariant ARP must maintain is: > If host A's cache contains `(T, m)`, then at some point in the (bounded) past, the host currently or then owning IP T identified its MAC address as m. This invariant is established as a base case by the request/reply exchange (step 7–8 above): a reply for T can only be generated by the process bound to IP address T on some host (assuming no misconfiguration or spoofing), so the mapping inserted at A is, at insertion time, accurate. The invariant can later be violated only by external changes — T's owner changes MAC (NIC replacement), T is reassigned to a different host, or a malicious host lies in a reply — which is precisely why the cache carries a timestamp and an eviction policy: correctness is only guaranteed to hold within the timeout window, not indefinitely. This is a deliberate soft-state design, the same pattern used in DNS TTLs and routing-protocol keepalives: rather than requiring active invalidation on every topology change (which needs a reliable, ordered notification channel), the protocol lets stale information decay on its own and re-verifies lazily on the next miss.

Honest tradeoff. ARP's request phase is a broadcast, so it does not scale to arbitrarily large flat networks — every request interrupts every host on the segment, which is one of the reasons real networks are partitioned into smaller broadcast domains using Virtual LANs (VLANs) rather than left as one giant flat LAN. ARP also performs no authentication whatsoever: any host can claim to own any IP address in a reply, and other hosts will accept and cache it, trading security for simplicity — the root cause of ARP spoofing/poisoning attacks discussed below.

Consider a small LAN, subnet `10.0.0.0/24`, with three hosts already up:

Alice's ARP cache starts empty. Alice's application calls `send("10.0.0.9", "hello")`.

Notice two subtleties this trace surfaces: Carol never sent a reply (correct — she is not the target) yet still benefited by caching Alice's mapping for free, and Bob's reply is unicast (not broadcast) since Bob already knows exactly whom to answer, which is the asymmetry that keeps ARP's reply traffic light even though the request is heavy.

ARP was designed to solve a problem that appeared as soon as Ethernet LANs began running the fledgling Internet Protocol suite in the early 1980s: two independently designed addressing schemes needed a bridge, and that bridge had to be dynamic because Ethernet cards, unlike phone numbers, could be swapped or reassigned freely.

Every IPv4 device on an Ethernet or Wi-Fi LAN — laptops, phones, IoT devices, servers, printers, routers — runs ARP continuously and invisibly; it is invoked before essentially any first packet on a new local connection. Operating systems expose the cache directly (`arp -a` on Windows and macOS, `ip neigh` on Linux), and network engineers inspect it routinely when diagnosing "can ping the gateway but not this other host" problems. Managed switches implement Dynamic ARP Inspection (DAI), which validates ARP replies against a trusted binding table (often built from DHCP snooping) to block spoofed replies — a direct security patch for ARP's lack of authentication. Load balancers and high-availability clusters use gratuitous ARP to redirect traffic to a standby node instantly after a failover, updating every peer's cache without waiting for natural expiry. Hypervisors send gratuitous ARP after live-migrating a virtual machine to a new physical host, so the rest of the LAN updates its cache to point at the new location. And because ARP broadcasts are confined to one broadcast domain, network designers deliberately shrink that domain with Virtual LANs (VLANs) to limit both ARP broadcast overhead and the blast radius of a spoofing attack — the natural next layer of local-network design built directly on top of what ARP does at the link layer.

Ask the tutor: How would ARP behavior change on a network segmented by VLANs versus one flat broadcast domain?