PaperlayerView exact revision on arXiv

Source-linked AI summary

Homa: A Receiver-Driven Low-Latency Transport Protocol Using Network Priorities (Complete Version)

Behnam Montazeri, Yilong Li, Mohammad Alizadeh, John Ousterhout

arXiv:1803.09615v2cs.NI

TL;DR

Existing transports are poorly matched to tiny datacenter messages, whose tail latency remains far above hardware potential under high load. Homa combines receiver-managed in-network priorities, receiver-driven flow control, blind short-message transmission, and controlled overcommitment, achieving very low latency while supporting large messages and high utilization. Its applicability depends on its assumed operating environment, and the paper specifically notes limited suitability for wide-area networks.

  • Problem

    Existing transport protocols do not provide near-hardware tail latency for tiny messages under high network load, despite datacenter hardware supporting microsecond communication.

  • Method

    Homa combines in-network priorities dynamically allocated by receivers with receiver-driven control, blind transmission of short messages, message-based scheduling, and controlled downlink overcommitment.

  • Results

    99th percentile round-trip latency is less than 15 µs for small messages at 80% load on 10 Gbps links, including competition from large messages.

  • Takeaways & Limitations

    Homa provides nearly optimal short-message latency across varied workloads while also improving large-message performance and sustaining higher network loads than several alternatives.

  • Takeaways & Limitations

    Homa may not achieve its reported performance when its operating-environment assumptions are unmet and is unlikely to work well in wide-area networks.

Abstract

from arXiv · show

Homa is a new transport protocol for datacenter networks. It provides exceptionally low latency, especially for workloads with a high volume of very short messages, and it also supports large messages and high network utilization. Homa uses in-network priority queues to ensure low latency for short messages; priority allocation is managed dynamically by each receiver and integrated with a receiver-driven flow control mechanism. Homa also uses controlled overcommitment of receiver downlinks to ensure efficient bandwidth utilization at high load. Our implementation of Homa delivers 99th percentile round-trip times less than 15μs for short messages on a 10 Gbps network running at 80% load. These latencies are almost 100x lower than the best published measurements of an implementation. In simulations, Homa's latency is roughly equal to pFabric and significantly better than pHost, PIAS, and NDP for almost all message sizes and workloads. Homa can also sustain higher network loads than pFabric, pHost, or PIAS.

1 Introduction

Homa addresses the gap between datacenter hardware’s microsecond latency potential and existing transports’ much higher tail latency for tiny messages under load. It combines receiver-managed priorities, receiver-driven control, controlled overcommitment, and message-oriented operation to improve short- and large-message performance.

  • Motivation: Existing transports provide short-message latency far above datacenter hardware’s potential, especially under high network loads.Modern hardware can support round-trip times of 5 µs or less, but request-response applications commonly use messages of a few hundred bytes or less.
  • Motivation: No practical existing solution was known to provide tail latencies of 100 µs or less for short messages at high network load.Prior designs often treated 100 Kbyte messages as small and measured latency in milliseconds rather than microseconds.
  • Results: 99th percentile round-trip latency is less than 15 µs for small messages at 80% load on 10 Gbps links, including competition from large messages.Across message sizes and workloads, Homa remains within 2–3.5x of minimum unloaded-network latency at 80% load.
  • Mechanisms: Dynamic receiver priorities integrated with receiver-driven flow control reduce tail latency by 2–16x versus previous receiver-driven approaches.Compared with PIAS, Homa’s closer approximation to SRPT reduces tail latency by 0–3x.
  • Mechanisms: Controlled overcommitment lets Homa sustain network loads 2–33% higher than pFabric, PIAS, pHost, and NDP while limiting short-message queuing.The receiver permits a few senders to transmit simultaneously, improving bandwidth efficiency.
  • Mechanisms: Message-based operation eliminates sender head-of-line blocking, reducing tail latency by 100x versus streaming transports such as TCP.Homa is also connectionless, uses no explicit acknowledgments, and provides at-least-once semantics.

2 Motivation and Key Ideas

Homa is motivated by the difficulty of achieving near-hardware tail latency for tiny messages at high load. Its design combines blind transmission, receiver-managed priorities, receiver-driven control, controlled overcommitment, and message-based scheduling to balance latency and utilization.

  • Motivation and goal: Homa targets the lowest possible 99th percentile message latency for short messages at high network load on current hardware.The focus is application-relevant message latency rather than packet latency.
  • Workloads: Prior workloads and evaluations emphasized very large messages, with Web Search treating messages shorter than 100 Kbytes as short.For that workload, messages longer than 1 Mbyte account for 95% of transmitted bytes.
  • Motivation and goal: NDP’s eight-packet queue limit still adds roughly 10 µs at 10 Gbps and increases a 200-byte message’s completion time by 5x.Queueing remains significant when raw network latency is only a few microseconds.
  • Key ideas: Homa derives four principles: blind transmission of short messages, in-network priorities, dynamic receiver allocation with receiver-driven control, and controlled downlink overcommitment.The paper argues that combining all four is crucial for the lowest latency at high load.
  • Protocol design: Homa transmits RTTbytes immediately, then sends scheduled packets only after receiver instruction; RTTbytes is about 10 KB at 10 Gbps.This covers the round-trip interval while the receiver returns scheduling information.
  • Trade-offs: Homa’s blind transmissions necessarily create buffering, so its design limits rather than eliminates the latency cost of queue buildup.The protocol uses message-based transmission to prevent sender head-of-line blocking from delaying short messages.
  • Priority allocation: Dynamic receiver priorities use exact inbound-message information for longer messages and recent workload information for blind short messages.This approach eliminates almost all preemption lag for messages larger than RTTbytes and reduces tail latency versus static allocation.
  • Downlink utilization: Controlled overcommitment grants several senders simultaneously, creating limited receiver-side queuing while improving utilization and message latency at high load.It addresses wasted bandwidth when senders receive grants for multiple destinations.

3 Homa Design

Homa is a complete, connectionless, receiver-driven, message-oriented transport substrate for datacenter RPCs. It uses four packet types and supports independent message delivery, at-least-once semantics, and future socket-like stream interfaces.

  • Protocol overview: Homa uses DATA, GRANT, RESEND, and BUSY packets to implement its receiver-driven transport.GRANTs authorize transmission up to an offset and specify priority; RESEND requests retransmission, while BUSY prevents timeouts during delayed responses.
  • RPCs, not connections: Homa is connectionless and identifies each RPC with a globally unique client-generated RPCid.Server state depends on active RPCs rather than the total number of clients.
  • Message orientation: Homa treats messages independently rather than as a byte stream, avoiding head-of-line blocking between short and long messages.The paper reports that streaming transports such as TCP increase short-message tail latency by 100x.
  • RPC semantics: Homa uses RPC responses as acknowledgments, reducing packet overhead, and implements at-least-once rather than at-most-once semantics.One-way messages can be simulated with an immediate empty response.
  • Scope: Traditional applications are not directly supported by a socket-like byte-stream interface, which the authors leave for future work.Homa was designed for applications where RPC is a natural fit.

3.2 Basic sender behavior

Homa splits each message into immediately transmitted unscheduled bytes and receiver-requested scheduled bytes. The sender prioritizes packets by each message’s remaining size while giving control packets precedence over DATA.

  • Messages begin with an unscheduled portion of RTTbytes bytes, followed by a scheduled portion.Unscheduled bytes are sent immediately; scheduled bytes require explicit GRANT packets from the receiver.
  • The receiver determines DATA-packet priorities, which are used for transmission on final receiver downlinks.
  • The sender transmits ready DATA packets for the message with the fewest remaining bytes first.Sender-side scheduling ignores DATA priorities, which target the receivers’ final downlinks.
  • Control packets such as GRANTs and RESENDs take priority over DATA packets.

3.3 Flow control

Homa places flow control and priority assignment at the receiver, using grants to regulate incoming data and priorities to approximate SRPT. Its design bounds per-message buffering, supports packet reordering and multipath routing, and uses controlled overcommitment to avoid idle downlinks.

  • Flow control: The receiver normally sends a GRANT whenever a DATA packet arrives, maintaining RTTbytes of granted-but-not-received data.Each grant authorizes transmission through a chosen message offset.
  • Flow control: Each incoming message can occupy at most RTTbytes of buffer space in the receiver’s top-of-rack switch.Delayed DATA packets also delay subsequent GRANTs, preserving this bound.
  • Flow control: Receivers may stop granting some messages under overcommitment limits, then resume them as completed messages free grant opportunities.
  • Flow control: Homa collates out-of-order DATA packets by their offsets, enabling per-packet multipath routing to reduce core congestion.
  • Priority assignment: Receivers dynamically assign DATA priorities to approximate SRPT, using traffic patterns for unscheduled packets and GRANTs for scheduled packets.Priority information for unscheduled packets is disseminated to senders by piggybacking it on other packets.
  • Priority assignment: Unscheduled priorities are allocated so each level carries about the same number of bytes, with the available levels divided according to unscheduled traffic.In Figure 4, about 80% of bytes are unscheduled, so 6 of 8 priority levels are allocated to unscheduled packets.
  • Priority assignment: Scheduled priorities are specified in GRANT packets, allowing allocation to adapt to the precise set of messages being received.This is described as a closer SRPT approximation than sender-based historical allocation such as PIAS.
  • Overcommitment: Granting only one sender at a time can leave a receiver’s downlink idle even when another message could use it.Figure 6 illustrates this when sender-side message choices conflict with the receiver’s selected grant.

3.5 Overcommitment

Homa uses controlled overcommitment to keep receiver downlinks busy when senders may not respond immediately to grants. More active messages improve utilization but increase buffering and round-robin scheduling.

  • Active messages: A receiver’s active messages are those for which it is willing to send grants; inactive messages receive no further transmission until reactivated.Withholding grants stops a message after previously granted data arrives.
  • Design trade-offs: Keeping every incoming message active causes high buffer occupancy and round-robin scheduling, increasing tail latency.This is the approach used by TCP and most other existing protocols.
  • Single-message activation: Allowing only one active message limited Homa to about 63% network bandwidth under workload W4, regardless of offered load.Senders did not always respond immediately to grants, leaving downlink bandwidth unused.
  • Controlled overcommitment: Overcommitment grants multiple senders simultaneously so another sender can use the downlink if one fails to respond.If several respond, priority scheduling sends the shortest message first while other packets buffer in the TOR.
  • Controlled overcommitment: The degree of overcommitment is the maximum number of simultaneously active messages on a receiver.Higher degrees reduce wasted bandwidth but consume up to RTTbytes per active message and can increase average completion time through round-robin scheduling.
  • Policy choice: Homa currently grants at most one message per scheduled priority level, though fixed or adaptive overcommitment policies are also plausible.The current policy produced high network utilization in simulations.
  • Design trade-offs: Homa adds enough buffering to maintain link utilization and uses priorities to prevent that buffering from harming latency.This trade-off motivates controlled rather than eliminated buffering.

3.6 Incast

Homa addresses incast with receiver-side detection and reduced unscheduled responses, while its buffer efficiency supports unpredictable simultaneous arrivals. Its receiver-driven loss recovery avoids explicit acknowledgments and handles failures through timeouts and retries.

  • Incast control: Outstanding RPC thresholds flag impending incasts and cause servers to limit unscheduled response bytes to a few hundred bytes.This lets Homa reduce the burst of response traffic produced by many concurrent RPCs.
  • Incast control: Efficient buffer use allows Homa to support hundreds of simultaneous arrivals without packet loss when incasts occur unpredictably.The design relies on such tightly synchronized unpredictable requests being unlikely, but provides buffer capacity if they occur.
  • Incast context: Lower datacenter latency is expected to reduce incast because requests complete before many outstanding RPCs accumulate.RAMCloud reads take about 5µs round trip, and responses often begin arriving after only 3–4 requests are issued.
  • Loss handling: Homa expects packet loss to be rare because network corruption and buffer overflows are both uncommon in modern datacenter networks.Its loss handling is therefore optimized for efficiency without loss and simplicity when losses occur.
  • Loss handling: Receivers detect losses with timeouts, eliminating explicit acknowledgments and removing half the packets required for simple RPCs.A timeout after a few milliseconds triggers recovery actions such as RESENDs.
  • Loss handling: Clients retry unanswered RESENDs several times before aborting the RPC and returning an error to higher-level software.This provides a bounded failure path when the server or network remains unavailable.

3.8 At-least-once semantics

Homa permits RPC re-execution instead of enforcing at-most-once execution, simplifying transport state management. Higher-level software must tolerate or filter duplicate executions when needed.

  • Semantics: Homa permits RPCs to execute more than once, including an arbitrary number of executions after an error.This differs from traditional at-most-once RPC semantics.
  • Semantics: Discarding RPC state after the final response packet can cause a later RESEND to trigger re-execution of a request.Homa lacks connection state and receives no acknowledgment confirming response delivery.
  • Rationale: Re-execution simplifies implementation and lets servers discard inactive-client state, while transport-level duplicate suppression is insufficient for many datacenter applications.Replicated storage systems may still need application-level handling when a replica crashes during a request.
  • Rationale: Higher-level software must tolerate redundant executions or filter duplicates with application-specific or general-purpose mechanisms such as RIFL.A thin TCP-like layer can discard duplicate data and preserve order.

4 Implementation

Homa was implemented as a DPDK-based RAMCloud transport using NIC polling, with an additional mechanism to bound NIC transmit-queue buildup. The implementation omitted online message-length measurement, instead precomputing priorities from benchmark workloads.

  • Implementation: Homa was implemented in RAMCloud using DPDK to bypass the kernel and communicate directly with the NIC.The implementation detects incoming packets with polling rather than interrupts, within a software stack whose RPC overhead is typically 1–2µs.
  • Implementation: The implementation does not measure incoming message lengths on the fly; priorities were precomputed from benchmark workload knowledge.This is the stated implementation limitation relative to the complete protocol description.
  • Queue management: Homa limits NIC transmit-queue buildup so high-priority packets do not wait behind previously queued lower-priority packets.The sender estimates untransmitted NIC bytes and hands off a packet only when the resulting queue is at most two full-size packets.
  • Evaluation hardware: The hardware measurements used an Infiniband cluster for Infiniband performance and CloudLab for all other measurements.Figure 7 distinguishes the hardware configuration by measurement type.

5 Evaluation

Homa achieves low tail latency across diverse workloads and message sizes, while its priority, SRPT, and controlled-overcommitment mechanisms explain its advantages over other transports. The evaluation also identifies important comparison boundaries and remaining large-message outliers.

  • Implementation Measurements: 14 µs 99th-percentile latency for 100-byte echo RPCs at 80% network load, versus 4.7 µs unloaded.Across three loads, the 99th-percentile latency was about 14 µs; Homa’s tail slowdown remained 2–3.5 across broad RPC sizes and workloads.
  • Implementation Measurements: 5–15x higher tail latency in Basic than Homa, caused by receiver-downlink queuing that Homa’s priorities nearly eliminate.Basic is receiver-driven but lacks priorities and limits on overcommitment.
  • Implementation Measurements: 100x lower tail latency than streaming transports such as TCP, because message-based transmission avoids sender head-of-line blocking.InfRC’s single-connection mode showed tail latencies about 1000x higher than Homa for small messages; multiple connections still did not approach Homa without priorities.
  • Simulations: 99th-percentile slowdown for the shortest 50% of messages never exceeds 2.2 at 80% load, matching pFabric across workloads.pHost and PIAS show considerably higher slowdown in this tail-latency evaluation, while receiver-driven control alone is insufficient: priorities and overcommitment reduce latency by 30–50%.
  • Simulations: 27% of receiver bandwidth was wasted by NDP at 70% load, and simulations could not run above 73% load.NDP’s no-overcommitment rate control, fair-share scheduling, and unprioritized sender queues produce additional queuing and head-of-line blocking.
  • Simulations: Tail latency is almost entirely due to link-level preemption lag, while Homa sustains higher loads than pFabric, pHost, NDP, or PIAS.Homa still wastes bandwidth when its limited scheduled priority levels are occupied by nonresponding senders, leaving the downlink idle.

6 Limitations

Homa's reported performance depends on datacenter-specific operating assumptions, including where congestion occurs, how implementations share links, and the predictability of incasts. The paper also cautions that its 10 Gbps configuration may not directly represent future faster networks.

  • Homa is designed for datacenter networks and may not work well in wide-area networks.
  • Homa assumes congestion occurs primarily at host downlinks, with per-packet spraying and sufficient aggregate core capacity.Oversubscription is acceptable when aggregate bandwidth prevents significant congestion.
  • Multiple independent Homa implementations sharing one host-TOR link may make conflicting overcommitment and priority decisions.Homa assumes a single implementation is aware of all traffic on each host-TOR link.
  • Homa handles predictable severe incasts effectively, but unpredictable incasts larger than several hundred messages cause packet loss and degraded performance.Typical switch buffer capacities support unpredictable incasts of several hundred messages.
  • At higher link speeds, increasing RTTbytes changes the fraction of unscheduled traffic and makes multiple priority levels more important.The paper's configuration and measurements were based on 10 Gbps links.

7 Related Work

Prior datacenter transport proposals generally do not combine in-network priorities, receiver-driven scheduling, and efficient operation under high load. Homa addresses these gaps while avoiding some hardware, connection-scaling, and centralized-scheduling constraints of existing approaches.

  • Existing proposals do not combine the features needed for low latency for short messages under load.
  • Without in-network priorities, prior systems cannot achieve the rapid preemption needed by short messages.The passage contrasts rate control, deadline awareness, and slow rate-based preemption with switch priorities.
  • PIAS performs worse than SRPT for most message sizes and workloads, while QJUMP and Karuna require manually or globally calculated priorities.
  • pFabric achieves near-optimal latencies using fine-grained switch priority queues, but those features are unavailable in existing switches.
  • pHost and NDP use static two-level priorities and no overcommitment, limiting short-message latency and high-load operation.NDP's fair-share scheduling also produces high tail latencies.
  • Connection-oriented streaming can cause head-of-line blocking or impractically many connections at datacenter scale.
  • Central scheduling such as Fastpass adds too much communication latency for short messages and is challenging to scale to large clusters.

8 Conclusion

Homa combines discrete messages, receiver-driven control, in-network priorities, controlled downlink overcommitment, and a connectionless design. These features deliver nearly optimal short-message latency across workloads, while remaining delays are attributed mainly to missing hardware packet preemption.

  • Homa uses discrete RPC messages, hybrid in-network priorities approximating SRPT, receiver-driven management, controlled downlink overcommitment, and no explicit acknowledgments.It is also connectionless rather than stream-oriented.
  • Homa achieves nearly optimal latency for short messages across varied workloads, even at high network loads.Tail latencies remain within a small factor of the hardware limit.
  • Remaining delays are almost entirely due to the absence of link-level packet preemption in current networks.The conclusion states that there is little room for improvement in the protocol itself.
  • Homa can be implemented without changes to networking hardware and is presented as a platform for low-latency datacenter applications.
Loading 1803.09615v2…