Homa: A Receiver-Driven Low-Latency Transport Protocol Using Network Priorities

https://people.csail.mit.edu/alizadeh/papers/homa-sigcomm18.pdf

Abstract

• Homa: new transport protocol for DC networks

• Provides low latency, especially for workloads with a high volume of very short messages, and it also supports large messages and high network utilization

Introduction

• Existing transport protocols are ill-suited to these conditions, so the latency they provide for short messages is far higher than the hardware potential, particularly under high network loads

• Homo

  • Favors small messages

  • But also improves the performance of large messages in comparison to TCP-like approaches based on fair sharing

• Two innovations

  • Aggressive use of priority queues provided by modern network switches

    • Assigns priorities dynamically on receivers, and it integrates the priorities with a receiver-driven flow control mechanism

  • Controller over-commitment: a receiver allows a few senders to transmit simultaneously

    • Utilizing the bandwidth efficiently

• Unusual features

  • Message-based architecture rather than a streaming approach

    • Eliminates head-of-line blocking at senders and reduces tail latency

  • Connectionless

  • No explicit ack

  • At-least-once semantics

• Metric: tail message latency (99th percentile): most important metric for datacenter application

Motivation and Key ideas

Motivation

• NIC and software stack advances

• All prior work has focused on workloads with very large messages

• Existing DC transport design cannot achieve the lowest possible latency for tiny messages at high network load

Design space

• Key design principles

  • Transmit short messages blindly

  • Using in-network priorities

  • Allocate priorities dynamically at receivers in conjunction with receiver-driven rate control

  • Controlled over-commitments of receiver downlinks

• Focus on message latency (instead of packet latency), since it reflects application performance

• Key

  • There is no time to schedule every packet

    • Short messages are transmitted blindly, without considering potential congestion

  • Buffering is a necessary evil

    • Latency penalty of buffering

  • In-network priorities are a must

    • Assign packet priorities so that short messages bypass queued packets for longer messages

  • Making best use of limited priorities requires receiver control

    • In order to produce the best approximation of SRPT with only a small number of priority levels

  • Receivers must allocate priorities dynamically

    • Two mechanisms:

      • For messages larger than RTTbytes, the receiver communicates a priority for each packet to its sender dynamically based on the exact set of inbound messages

      • For short messages that sent blindly, the sender cannot know about other messages inbound for the receiver

  • Receivers must overcommit their downlink in a controlled manner

    • Intentionally overcimmit their downlinks by granting simultaneously to a small number of senders

  • Senders need SRPT also