Routing and load balancing: why hashing fails and what replaces it路由與負載平衡：為何雜湊會失效，以及取代它的做法

8.1What a switch does with a packet交換器如何處理一個封包

A leaf has many uplinks to many spines. For each packet, the switch must pick one. The standard method is ECMP (equal-cost multi-path): the switch hashes the packet's five-tuple (source and destination address, source and destination port, protocol) and uses the hash to choose an uplink. All packets of one flow get the same hash, so they take the same path and arrive in order. With millions of small flows, the hashes spread evenly. With tens of elephant flows, they do not. Two 400G flows that hash to the same uplink must share it, and each gets 200G; this is a collision. The GPUs on the other side wait for the slower one.

一個 leaf 有很多條上行鏈路通往很多 spine。每個封包交換器都得挑一條。標準方法是 ECMP（等價多路徑）：交換器對封包的五元組（來源與目的位址、來源與目的埠、協定）做雜湊，用雜湊值挑選上行鏈路。同一條流的所有封包雜湊值相同，所以走同一條路、依序到達。有數百萬條小流時，雜湊會分得很均勻；只有幾十條大象流時就不會。兩條 400G 的流雜湊到同一條上行鏈路就必須共用，各得 200G；這就是碰撞（collision）。另一端的 GPU 得等比較慢的那一條。

Two lookups, not one. When a packet arrives, the switch reads the destination IP address and looks it up in the forwarding table. In a Clos network the result for a remote rack is not a single port. It is a group of equal-cost next hops: every uplink leads to a spine, and every spine can reach the destination in the same number of hops. The group is called an ECMP group, for equal-cost multi-path. The switch must now pick one member. It cannot pick at random per packet, for a reason explained below, and it does not know how busy each uplink is. So it computes a hash: a fixed function of a few header fields that returns a number, and it takes that number modulo the group size to select the uplink. The same header always gives the same uplink.

兩次查表，不是一次。封包抵達時，交換器讀出目的 IP 位址，在轉送表中查詢。在 Clos 網路裡，查到遠端機櫃的結果不是單一個埠，而是一組等價的下一跳：每一條上行鏈路都通往一台 spine，而每一台 spine 都能以相同的跳數到達目的地。這一組叫做 ECMP group（等價多路徑群組）。交換器現在必須挑出其中一個成員。它不能逐封包隨機挑（原因在下面說明），也不知道每條上行鏈路有多忙。所以它計算一個雜湊：對少數幾個標頭欄位套用一個固定函數得到一個數字，再把這個數字對群組大小取餘數來選出上行鏈路。同樣的標頭永遠得到同樣的上行鏈路。

The five-tuple, and the one field that varies. The fields are the source IP address, the destination IP address, the protocol number, the source port and the destination port. Together they are called the five-tuple. In a web data center these fields take millions of values. In a RoCEv2 training cluster they do not. The source and destination addresses name two NICs, and a job has one connection pattern between them. The protocol is UDP, because RoCEv2 carries RDMA inside UDP/IP. The destination UDP port is fixed at 4791, the port registered for RoCEv2. The only field left is the UDP source port, which the sending NIC chooses when it creates a connection. The RDMA connection itself is called a queue pair (QP), and the QP number travels in the RoCE base transport header, inside the UDP payload, where a standard hash does not look. So the switch sees one flow per QP, and the number of distinct source ports is the entropy the hash has to work with. The Meta RoCE paper calls this low entropy, and it measured the cause: an AllReduce on 128 GPUs opens about 4 QPs per GPU, an AlltoAll about 15 (Table 2). Meta's answer, described in Section 8.3, has two halves: QP scaling, in which NCCL opens several QPs per connection, and E-ECMP, in which the switches also hash the destination QP number.

五元組，以及唯一會變的欄位。這些欄位是來源 IP 位址、目的 IP 位址、協定編號、來源埠與目的埠，合稱五元組。在網頁資料中心裡這些欄位有數百萬種值；在 RoCEv2 訓練叢集裡沒有。來源與目的位址指的是兩張 NIC，而一個任務在它們之間只有一種連線模式。協定是 UDP，因為 RoCEv2 把 RDMA 包在 UDP/IP 裡。目的 UDP 埠固定為 4791，即 RoCEv2 登錄的埠號。只剩下 UDP 來源埠，由發送端 NIC 在建立連線時選定。RDMA 連線本身叫做 queue pair（QP），QP 編號放在 RoCE 基本傳輸標頭裡，位於 UDP 載荷之內，標準雜湊不會看那裡。所以交換器看到的是每個 QP 一條流，而不同來源埠的數量就是雜湊能運用的全部熵。Meta RoCE 論文稱之為低熵，並量出了原因：128 顆 GPU 上一次 AllReduce 每顆 GPU 約開 4 個 QP，AlltoAll 約 15 個（Table 2）。Meta 的對策（第 8.3 節）分兩半：QP scaling，讓 NCCL 為每條連線開多個 QP；以及 E-ECMP，讓交換器也對目的 QP 編號做雜湊。

Figure 8.1 follows one header through a leaf switch.

圖 8.1 追蹤一個標頭穿過 leaf 交換器的過程。

Why every packet of a flow must take the same path. A RoCE NIC of the kind deployed in 2024 recovers from a missing packet with go-back-N: when a packet arrives whose sequence number is higher than expected, the receiver discards it and asks the sender to resend everything from the gap onward. The NIC cannot tell a packet that was lost from a packet that took a slower path and is still in flight. If a switch moved a flow from one uplink to another in the middle of a message, the packets on the new, faster path could overtake the packets on the old path. The receiver would see a gap, discard good data and trigger a retransmission of a full bandwidth-delay product, about 1.1 MB at 400 Gb/s and 22 µs of round trip. Per-flow hashing avoids this by construction: the header does not change, so the uplink does not change. The cost is that the switch gives up the ability to react. Once two flows have landed on one uplink, they stay there for the life of the connection, which in training means for the whole job.

為何一條流的每個封包必須走同一條路。2024 年部署的那類 RoCE NIC 以 go-back-N 從封包遺失中恢復：當一個序號高於預期的封包到達，接收端把它丟棄，並要求發送端從缺口開始重送之後的一切。NIC 無法分辨「遺失的封包」與「走了較慢路徑、還在路上的封包」。如果交換器在一則訊息中途把一條流從一條上行鏈路移到另一條，新路徑較快的封包可能超越舊路徑上的封包。接收端會看到缺口、丟掉好的資料，並觸發整整一個頻寬延遲乘積的重傳——在 400 Gb/s 與 22 µs 往返下約 1.1 MB。逐流雜湊從構造上避免了這件事：標頭不變，上行鏈路就不變。代價是交換器放棄了反應的能力。兩條流一旦落在同一條上行鏈路，就會在連線存續期間一直留在那裡——在訓練裡，這表示整個任務的時間。

Panel 8.1 computes what one reroute costs.

面板 8.1 算出一次改路徑的代價。

Hash polarization across tiers. A packet that leaves the leaf is hashed again at the spine, and in a three-tier network a third time at the core. If every tier applies the same function to the same five fields, a pair of flows that collided at the first tier gives identical hash values at the second and collides again. The HPN paper (§2.2) calls this hash polarization and reports that it caused several production incidents before HPN was built. Vendors mitigate it by seeding the hash differently on each switch, so the function is not literally identical, but the number of distinct inputs is still small, and a small number of inputs cannot be spread evenly by any function. Alibaba measured the effect directly: during a GPT-3 175B job, the two ToR ports toward one NIC carried loads that differed by a factor of three, and the queue on the busy port sat at 267 KB while the other sat at 3 KB (HPN Figure 13a).

跨層的雜湊極化。離開 leaf 的封包在 spine 會再被雜湊一次，在三層網路裡則在核心層被雜湊第三次。若每一層都對同樣五個欄位套用同樣的函數，在第一層碰撞的一對流在第二層會得到相同的雜湊值，再碰撞一次。HPN 論文（§2.2）稱之為雜湊極化（hash polarization），並報告它在 HPN 建成前造成了多起生產事故。廠商用在每台交換器設定不同種子來緩解，所以函數並非完全相同，但不同輸入的數量仍然很少，而任何函數都無法把少量輸入分得均勻。阿里直接量到了這個效應：GPT-3 175B 任務期間，通往同一張 NIC 的兩個 ToR 埠負載相差三倍，忙的那個埠佇列停在 267 KB，另一個停在 3 KB（HPN Figure 13a）。

Figure 8.2 shows the effect on two flows in a three-tier network.

圖 8.2 畫出這個效應在三層網路中對兩條流的影響。

8.2The arithmetic of collisions碰撞的算術

Balls in bins. Treat each flow as a ball and each uplink as a bin. A good hash sends each ball to a bin chosen uniformly and independently. With $f$ flows and $L$ uplinks, the probability that no two flows share an uplink is the product of the chances that each new flow avoids every uplink already taken:

球與箱子。把每條流看成一顆球、每條上行鏈路看成一個箱子。好的雜湊把每顆球送進一個均勻且獨立選出的箱子。有 $f$ 條流與 $L$ 條上行鏈路時，沒有任何兩條流共用一條上行鏈路的機率，是每條新加入的流避開所有已被占用的上行鏈路的機率之乘積：

The first flow can go anywhere. The second must avoid one uplink out of $L$, the third must avoid two, and so on. For 16 uplinks, one question per row:

第一條流可以去任何地方。第二條必須避開 $L$ 條中的一條，第三條必須避開兩條，以此類推。以 16 條上行鏈路計算，逐列如下：

With only 4 flows, one job in three already has at least one shared uplink; at 8 flows the chance of no collision is 0.12, and at 16 flows about one in a million. The exponential approximation is the birthday-problem form: collisions become likely once $f$ is near $\sqrt{2L}$, which for 16 uplinks is about 6 flows.

只有 4 條流時，每三個任務就有一個至少有一條上行鏈路被共用；8 條流時無碰撞的機率是 0.12，16 條流時約百萬分之一。指數近似就是生日問題的形式：一旦 $f$ 接近 $\sqrt{2L}$，碰撞就變得很可能——16 條上行鏈路時約為 6 條流。

Figure 8.3 plots the product for 1 to 16 flows.

圖 8.3 畫出 1 到 16 條流時的乘積。

From collision to slowdown. A collision is not the number that matters. What matters is the maximum load: the number of flows on the busiest uplink. Every flow on that uplink runs at $1/m$ of its rate when $m$ flows share it, and a collective finishes when its slowest flow finishes, so the job slows by the ratio of the maximum load to the ideal load. The ideal load is $f/L$ flows per uplink when flows are many, or one full link per flow when they are few. There is no closed form for the expected maximum, but two limits are worth remembering. When ${f = L}$, the expected maximum grows like $\ln L / \ln \ln L$; for 16 flows on 16 uplinks the simulation gives 3.1, so the busiest link carries three flows and the job runs at one third of its ideal speed. When $f$ is much larger than $L$, the load on each uplink is approximately normal with mean $f/L$ and standard deviation $\sqrt{f/L}$, and the busiest of 16 such uplinks sits about 1.8 standard deviations above the mean. For 1,000 flows on 16 uplinks, one question per row:

從碰撞到減速。碰撞本身不是重要的數字。重要的是最大負載：最忙那條上行鏈路上的流數。$m$ 條流共用一條上行鏈路時，每條流只以 $1/m$ 的速率運行，而集體通訊要等最慢的流完成才結束，所以任務減速的倍數等於最大負載對理想負載的比值。流很多時理想負載是每條上行鏈路 $f/L$ 條流；流很少時則是每條流獨占一條鏈路。期望最大值沒有封閉解，但兩個極限值得記住。當 ${f = L}$，期望最大值的成長像 $\ln L / \ln \ln L$；16 條流在 16 條上行鏈路上模擬得到 3.1，所以最忙的鏈路承載三條流，任務以理想速度的三分之一運行。當 $f$ 遠大於 $L$，每條上行鏈路的負載近似常態分布，平均值 $f/L$、標準差 $\sqrt{f/L}$，而 16 條這樣的上行鏈路中最忙的一條大約落在平均值上方 1.8 個標準差。1,000 條流在 16 條上行鏈路上時，逐列計算如下：

So the busiest uplink carries about 77 flows, 1.23 times the average, which matches the 1.2× that the Meta paper reports for the same simulation.

所以最忙的上行鏈路承載約 77 條流，是平均值的 1.23 倍，與 Meta 論文對同一個模擬報告的 1.2 倍相符。

Figure 8.4 shows why the busiest uplink sets the pace.

圖 8.4 說明為何最忙的上行鏈路決定速度。

Animation 8.1 plays the hash and then the transfer for 4, 8 or 16 flows on 16 uplinks; Rehash gives the flows new source ports.

動畫 8.1 先播放雜湊、再播放傳輸，流數可選 4、8 或 16 條，上行鏈路 16 條；「重新雜湊」給每條流新的來源埠。

Why web traffic averages out and training does not. The relative spread of the load is

為何網頁流量會平均掉、訓練不會。負載的相對離散度是

It shrinks as the number of flows grows. A web server behind the same leaf has thousands of flows, each a small fraction of a link, so $f/L$ is in the hundreds and the busiest uplink is within a few percent of the average. A training rack with 16 GPUs and 4 QPs each has 64 flows on 16 uplinks, each flow a quarter of a NIC, so $f/L$ is 4 and the busiest uplink carries about twice the average. Microsoft met the same arithmetic in 2016, before AI clusters existed: an RDMA test across 1,152 servers reached 3.0 Tb/s with zero drops, but that was 60% of the 5.12 Tb/s capacity, and the paper names ECMP hash collisions, not PFC, as the ceiling (Microsoft RoCE §5). RDMA flows were few and large even then.

它隨流數增加而縮小。同一台 leaf 後面的網頁伺服器有數千條流，每條只占鏈路的一小部分，所以 $f/L$ 是幾百，最忙的上行鏈路與平均值只差幾個百分點。一個有 16 顆 GPU、每顆 4 個 QP 的訓練機櫃，在 16 條上行鏈路上有 64 條流，每條流是一張 NIC 的四分之一，所以 $f/L$ 是 4，最忙的上行鏈路承載約兩倍的平均值。微軟在 2016 年、AI 叢集出現之前就遇到同樣的算術：跨 1,152 台伺服器的 RDMA 測試達到 3.0 Tb/s、零丟包，但那只是 5.12 Tb/s 容量的 60%，論文點名 ECMP 雜湊碰撞、而非 PFC 是上限（Microsoft RoCE §5）。那時 RDMA 的流就已經又少又大。

The 32-flow row is the Meta default: one host of 8 GPUs under a 16-uplink rack switch, 4 QPs per GPU as in Table 2 of the paper. Each flow carries a quarter of a 400 Gb/s NIC, so an uplink with 4.8 flows is asked for 1.21 links of bandwidth, and the job runs 21% slower than it should. Raise the QPs to 16 and the expected maximum rises to 13.4 flows of one sixteenth each, which is 0.84 of a link: no uplink is oversubscribed and the slowdown disappears. That is the whole mechanism of QP scaling in one row, and Panel 8.2 lets you repeat the experiment.

32 條流那一列是 Meta 的預設情況：一台 8 顆 GPU 的主機掛在 16 條上行鏈路的機櫃交換器下，每顆 GPU 4 個 QP，如論文 Table 2。每條流承載一張 400 Gb/s NIC 的四分之一，所以有 4.8 條流的上行鏈路被要求 1.21 條鏈路的頻寬，任務比應有的慢 21%。把 QP 提高到 16，期望最大值升到 13.4 條各占十六分之一的流，即 0.84 條鏈路：沒有上行鏈路超載，減速消失。這一列就是 QP scaling 的全部機制，面板 8.2 讓你重做這個實驗。

8.3Meta's five stages, and how each one failedMeta 的五個階段，以及各自如何失敗

Section 4 of the Meta RoCE paper is a four-year history of routing the same flows across the same Clos. Each stage fixed the failure of the one before and exposed a new one. The table gives the stages; the paragraphs give the mechanism behind each failure.

Meta RoCE 論文的 §4 是在同一個 Clos 上為同樣的流選路的四年歷史。每個階段修正前一個階段的失敗，又暴露新的失敗。表格列出各階段；段落說明每個失敗背後的機制。

Stage 2: path pinning, and why a perfect plan broke. A rack training switch (RTSW) at Meta has 16 downlinks, one per GPU across two hosts, and 16 uplinks at 1:1. Each downlink index is a slice. Path pinning replaced the hash with a rule: a flow toward destination slice $k$ leaves the source RTSW on uplink $k$. If every rack is fully allocated to one job, each destination slice receives the same traffic, so each uplink carries exactly one slice's share and the spread is perfect: no probability at all. The rule fails as soon as the assumption fails. Suppose $k$ of the 8 destination racks that a source rack talks to have only one of their two hosts in the job. Those racks have active slices 0–7 only, so the flows toward them use uplinks 0–7 only. The total demand does not change, because the source GPUs still have the same gradients to send; it is redistributed over fewer uplinks. Uplinks 0–7 now carry ${16/(16 - k)}$ of a link while uplinks 8–15 carry ${(8 - k) \times 2/(16 - k)}$. With ${k = 4}$ the busy uplinks are at 1.33 links and the job runs 33% slower; with ${k = 8}$ they are at 2.0 and half the uplinks are idle. The paper measured "up to more than 30%", which is this formula with partial racks in the range it saw in production. The second failure was independent: when an uplink or a spine failed, the flows pinned to it fell back to ECMP and landed on top of the pinned flows of other slices, so one failure created collisions where the plan had none.

第二階段：路徑固定，以及為何完美的計畫會壞掉。Meta 的機櫃訓練交換器（RTSW）有 16 條下行鏈路——兩台主機各 8 顆 GPU、每顆一條——以及 1:1 的 16 條上行鏈路。每個下行索引是一個 slice。路徑固定用一條規則取代雜湊：通往目的 slice $k$ 的流從來源 RTSW 的上行鏈路 $k$ 出去。如果每個機櫃都完整分配給同一個任務，每個目的 slice 收到相同的流量，所以每條上行鏈路恰好承載一個 slice 的份額，分配完美，完全沒有機率成分。假設一失效，規則就失效。假設來源機櫃會對話的 8 個目的機櫃中，有 $k$ 個只有兩台主機之一在任務裡。這些機櫃只有 slice 0–7 在用，所以通往它們的流只使用上行鏈路 0–7。總需求沒有變，因為來源 GPU 仍有同樣的梯度要送；它只是被重新分配到更少的上行鏈路上。上行鏈路 0–7 現在承載 ${16/(16 - k)}$ 條鏈路的量，上行鏈路 8–15 承載 ${(8 - k) \times 2/(16 - k)}$。${k = 4}$ 時忙的上行鏈路在 1.33 條鏈路，任務慢 33%；${k = 8}$ 時在 2.0，一半的上行鏈路閒置。論文量到的是「最多超過 30%」，也就是這個公式在生產環境所見的部分分配範圍下的結果。第二個失敗是獨立的：當一條上行或一台 spine 故障，固定在它上面的流退回 ECMP，落在其他 slice 的固定流之上，於是一次故障在原本沒有碰撞的計畫裡製造了碰撞。

Figure 8.5 draws the rule and its failure for ${k = 4}$.

圖 8.5 畫出這條規則，以及它在 ${k = 4}$ 時如何失效。

Stage 3: pay for headroom. Doubling the uplinks does not change the hash. It changes what a collision costs. With 32 uplinks of 400 Gb/s behind 16 GPUs, the ideal load per uplink is half a link, so an uplink can carry twice its fair share before any flow slows down. In the terms of Panel 8.2: one host of 8 GPUs at 4 QPs, which loses about 21% on 16 uplinks, loses nothing on 32; a full rack of 16 GPUs at 4 QPs still loses about 35% on 32 uplinks, and nothing once the QPs go to 16. Headroom and entropy multiply; neither alone is enough for a full rack. The authors call 1:2 an expensive mitigation, and the final design settled at 1:1.125, which is enough spare capacity to survive two failed uplinks per rack without slowing a job, at a small fraction of the cost of 1:2 (§6.2). Under-subscription is the honest baseline for every other method in this chapter: a scheme is only worth deploying if it costs less than the links it saves.

第三階段：花錢買餘裕。上行加倍並不改變雜湊。它改變的是碰撞的代價。16 顆 GPU 後面有 32 條 400 Gb/s 的上行鏈路時，每條上行的理想負載是半條鏈路，所以一條上行可以承載公平份額的兩倍，才會有流變慢。用面板 8.2 的話說：一台 8 顆 GPU 的主機在 4 個 QP 下，在 16 條上行損失約 21%，在 32 條上行毫無損失；一個 16 顆 GPU 的滿載機櫃在 4 個 QP 下，在 32 條上行仍損失約 35%，QP 提高到 16 之後才沒有損失。餘裕與熵是相乘的；對滿載的機櫃，單靠任何一個都不夠。作者稱 1:2 為昂貴的緩解，最終設計定在 1:1.125——足以在每個機櫃兩條上行故障時不拖慢任務，成本只是 1:2 的一小部分（§6.2）。欠額認購是本章其他每一種方法的誠實基線：一個方案只有在成本低於它省下的鏈路時才值得部署。

Stage 4: E-ECMP and QP scaling, two halves of one change. On the switch side, Meta used the ASIC's user-defined-field feature to read the 24-bit destination QP number from the RoCE base transport header, past the UDP header, and add it to the hash input. On its own this does nothing: one connection has one QP, so the new field is as constant as the old ones. The library side supplies the variation. QP scaling in NCCL opens several QPs per logical connection, so the same pair of GPUs appears to the switch as several flows. Meta tried two ways to use them. Splitting each message across the QPs produced smaller messages and more acknowledgments; posting whole messages to the QPs in round-robin order kept message sizes intact and won. The result was up to 40% faster AllReduce than plain ECMP. Ranking jobs ran with 4 QPs per connection, LLM jobs with 16, and the Llama 3 405B cluster, which used the same design, reports 16 flows per GPU pair. The paper's simulation shows the limit of the method: moving from 4 to 32 QPs lifted the worst case from 20% to 52% of the theoretical optimum, but the mean stayed about 40% below it. That is the $\sqrt{L/f}$ spread of Section 8.2: eight times more flows shrink the relative spread by only ${\sqrt{8} \approx 2.8}$, and each extra QP costs NIC state and connection setup time.

第四階段：E-ECMP 與 QP scaling，一個改動的兩半。交換器端，Meta 用 ASIC 的使用者自定義欄位功能，從 UDP 標頭之後的 RoCE 基本傳輸標頭讀出 24 位元的目的 QP 編號，加進雜湊輸入。單獨這麼做沒有用：一條連線只有一個 QP，新欄位和舊欄位一樣是常數。變化由函式庫端供應。NCCL 的 QP scaling 為每條邏輯連線開數個 QP，於是同一對 GPU 在交換器眼中變成數條流。Meta 試了兩種用法。把每則訊息切到各 QP 會產生更小的訊息與更多的確認；把整則訊息輪流投到各 QP 則保持訊息大小不變，勝出。結果是 AllReduce 比一般 ECMP 最多快 40%。排序任務每條連線用 4 個 QP，LLM 任務用 16 個，而採用同一設計的 Llama 3 405B 叢集報告每對 GPU 16 條流。論文的模擬顯示這個方法的極限：從 4 個 QP 增加到 32 個，把最差情況從理論最佳值的 20% 拉到 52%，但平均值仍比最佳值低約 40%。這就是 第 8.2 節 的 $\sqrt{L/f}$ 離散度：八倍的流只把相對離散度縮小 ${\sqrt{8} \approx 2.8}$ 倍，而每多一個 QP 都要付出 NIC 狀態與建立連線的時間。

Figure 8.6 compares the two ways to use the QPs.

圖 8.6 比較使用這些 QP 的兩種方式。

Animation 8.2 sends the four messages of Figure 8.6 both ways.

動畫 8.2 用兩種方式送出圖 8.6 的四則訊息。

Stage 5: traffic engineering, a planner instead of dice. A central controller that knows every flow of every job can assign paths so that no uplink is overloaded, which is the bin-packing problem the hash was approximating. On a 16-uplink test the utilization of individual uplinks under E-ECMP swung between 40% and 90%; under TE it held near 80%. On 128 GPUs TE beat E-ECMP by 5–10% for AllReduce and AlltoAll. Meta deployed it inside AI Zones and stopped there. A controller must recompute when a link fails, a job starts or a job ends, and across a data center those events are continuous; 5–10% did not justify that operational cost. The paper's closing proposal is flowlet switching: a switch is allowed to move a flow to another uplink only during a gap in its packet stream that is longer than a threshold. If the threshold exceeds the delay difference between the old and new paths, the last packet on the old path arrives before the first packet on the new one, and nothing is reordered. With a 256–512 µs threshold Meta measured fewer than one reordered packet per second. Training traffic, which is on and off at millisecond scale, has plenty of such gaps, which is why the authors expect flowlets to match TE at lower cost. Panel 8.5 lets you test the threshold against the path skew.

第五階段：流量工程，用規劃者取代骰子。知道每個任務每一條流的中央控制器可以指派路徑，讓沒有任何上行鏈路過載——這就是雜湊在近似求解的裝箱問題。在 16 條上行鏈路的測試中，E-ECMP 下各上行鏈路的使用率在 40% 到 90% 之間擺盪；TE 下維持在 80% 附近。在 128 顆 GPU 上，TE 的 AllReduce 與 AlltoAll 比 E-ECMP 快 5–10%。Meta 把它部署在 AI Zone 內就停了。控制器必須在鏈路故障、任務開始或結束時重新計算，而在整個資料中心裡這些事件是連續不斷的；5–10% 不足以抵償這個營運成本。論文結尾的提案是 flowlet switching：只有在一條流的封包串流出現超過某個門檻的空檔時，交換器才允許把它移到另一條上行鏈路。如果門檻超過新舊路徑的延遲差，舊路徑上最後一個封包會比新路徑上第一個封包先到，就不會有任何亂序。以 256–512 µs 的門檻，Meta 量到每秒亂序的封包少於一個。訓練流量以毫秒尺度開開關關，有大量這種空檔，這就是作者預期 flowlet 能以更低成本達到 TE 效果的原因。面板 8.5 讓你拿門檻去對路徑偏差做測試。

8.4Alibaba's answer: remove the choiceAlibaba 的對策：拿掉選擇

The choice that dual-ToR created. In HPN every NIC has two 200 Gb/s ports on two different rack switches. Traffic coming down toward that NIC from any of the 60 aggregation switches must converge on one of the two ToRs, and in a normal Clos the aggregation switch decides by hashing. Two ports, a few flows: the hash is as unfair as Section 8.2 predicts, and the measured result was a 3× load difference between the two ports toward one NIC, with queues of 267 KB and 3 KB (HPN Figure 13a). The imbalance repeated at each tier, which is the polarization of Section 8.1.

Dual-ToR 製造出的選擇。在 HPN 裡每張 NIC 有兩個 200 Gb/s 的埠接在兩台不同的機櫃交換器上。從 60 台聚合交換器中任何一台往下流向那張 NIC 的流量，必須收斂到兩台 ToR 之一，而在一般的 Clos 裡由聚合交換器以雜湊決定。兩個埠、幾條流：雜湊就如 第 8.2 節 所預測的那樣不公平，量到的結果是通往同一張 NIC 的兩個埠負載相差 3 倍，佇列分別是 267 KB 與 3 KB（HPN Figure 13a）。這個不平衡在每一層重複，就是 第 8.1 節 的極化。

Dual-plane: fix the path on entry. HPN splits the aggregation layer into two planes (the wiring and the measured port loads are drawn in Section 6.5). The first ToR of every pair connects all 60 of its uplinks to the 60 aggregation switches of plane 1; the second ToR connects only to plane 2. A packet that enters a plane-1 ToR can reach the destination only through plane 1 and only at the destination's plane-1 ToR. There is no hash at the aggregation layer because there is exactly one next hop toward any destination. The paper's own phrase is that once a flow enters a ToR, its path through the pod is completely determined. After deployment the two ports toward a NIC carried equal load, the average ToR queue fell to 20 KB, a 91.8% reduction, and an ablation attributes up to 71.6% of the cross-segment gain to dual-plane alone (HPN §6.1). Note what this did not do: it did not add entropy or improve the hash. It removed one of the two places where a hash was taken, and with it one of the two chances to collide.

Dual-plane：在進入時就固定路徑。HPN 把聚合層切成兩個平面（接線與量到的埠負載畫在第 6.5 節）。每一對 ToR 的第一台把它全部 60 條上行接到平面 1 的 60 台聚合交換器；第二台只接平面 2。進入平面 1 ToR 的封包只能經由平面 1 到達目的地，而且只能到達目的地的平面 1 ToR。聚合層沒有雜湊，因為朝任何目的地都恰好只有一個下一跳。論文自己的說法是：一條流進入 ToR 後，它穿越 pod 的路徑就完全確定。部署後朝一張 NIC 的兩個埠負載相等，ToR 平均佇列降到 20 KB，減少 91.8%，消融實驗把跨 segment 效能提升中最多 71.6% 單獨歸因於 dual-plane（HPN §6.1）。注意它沒有做的事：它沒有增加熵，也沒有改良雜湊。它拿掉了兩個做雜湊的地方之一，連帶拿掉兩次碰撞機會之一。

The choice that remains, moved to the host. Inside a plane the source ToR still has 60 uplinks. A host with 16 flows toward one destination segment faces 16 balls in 60 bins, and the formula of Section 8.2 gives an 11% chance that no two share an uplink; the expected busiest uplink carries about two flows. HPN does not leave this to the hash. The host runs RePaC, a tool that reproduces the exact hash each switch computes, so it can predict which uplink any five-tuple will take. The host then chooses UDP source ports whose paths are pairwise disjoint and opens one RDMA connection per path. The search is cheap precisely because of dual-plane: only the 60 links of one ToR need to be considered, which Table 1 of the paper puts at one to two orders of magnitude less work than the same search in a three-tier network, where every combination of three hash decisions would have to be checked. The second host-side mechanism acts per message. The collective library keeps, for each connection, a counter of the bytes posted in work-queue elements (WQEs) that have not yet completed. Each new message goes on the connection with the smallest counter. A congested path drains slowly, so its counter stays high and it is avoided; a clear path drains fast and attracts the next message. With four AllReduce jobs running at once on 512 GPUs, the combination raised collective performance by up to 34.7% (HPN §6.1). The ordering constraint of Section 8.1 is respected because each message still travels on one connection; only the choice between connections is dynamic.

剩下的選擇，移到主機。在一個平面內，來源 ToR 仍有 60 條上行鏈路。一台主機朝某個目的 segment 有 16 條流，面對的是 16 顆球、60 個箱子，第 8.2 節 的公式給出 11% 的機率沒有任何兩條共用一條上行；期望最忙的上行鏈路約承載兩條流。HPN 不把這件事交給雜湊。主機執行 RePaC，一個能重現每台交換器精確雜湊計算的工具，因此能預測任何五元組會走哪一條上行。主機接著選出路徑兩兩不相交的 UDP 來源埠，並為每條路徑開一條 RDMA 連線。這個搜尋便宜正是因為 dual-plane：只需考慮一台 ToR 的 60 條鏈路，論文 Table 1 說這比在三層網路中做同樣的搜尋少一到兩個數量級的工作量——那裡每一組三次雜湊決策的組合都得檢查。第二個主機端機制逐訊息運作。集體通訊函式庫為每條連線維護一個計數器，記錄已提交到工作佇列元素（WQE）但尚未完成的位元組數。每則新訊息送到計數器最小的連線。壅塞的路徑排空得慢，計數器居高不下，就會被避開；暢通的路徑排空得快，吸引下一則訊息。在 512 顆 GPU 上同時跑四個 AllReduce 任務時，兩者合起來讓集體通訊效能提升最多 34.7%（HPN §6.1）。第 8.1 節 的順序限制仍被遵守，因為每則訊息仍在一條連線上傳送；只有連線之間的選擇是動態的。

Figure 8.7 shows the per-message rule.

圖 8.7 畫出逐訊息的規則。

Panel 8.4 compares the hash with disjoint paths on one ToR.

面板 8.4 在一台 ToR 上比較雜湊與不相交路徑。

The core tier: a table instead of a hash. Between pods, HPN keeps the dual-plane split and replaces the hash with a static per-port rule: traffic for pod $i$ that arrives on port $j$ always leaves on port $k$. The mapping is chosen once so that the pod-to-pod traffic is spread by construction, and the switch falls back to hashing only when port $k$ has failed (HPN §7). This is the same idea as Meta's path pinning, with one difference that explains why it worked for Alibaba: the scheduler sends only pipeline traffic across pods, about 6 MB per step against 5.5 GB for data parallelism in the paper's GPT-3 example, so a bad mapping costs little, and the mapping is by physical port rather than by job allocation, so partial racks do not change it.

核心層：用表格取代雜湊。在 pod 之間，HPN 保留 dual-plane 的切分，並用靜態的每埠規則取代雜湊：從埠 $j$ 進來、往 pod $i$ 的流量一律從埠 $k$ 出去。這個對應只選一次，使 pod 間流量依構造分散，只有在埠 $k$ 故障時交換器才退回雜湊（HPN §7）。這和 Meta 的路徑固定是同一個想法，但有一個差異解釋了它為何對阿里有效：排程器只讓管線流量跨 pod——論文的 GPT-3 例子中每步約 6 MB，相對於資料平行的 5.5 GB——所以不好的對應代價很小；而且對應是依物理埠而非依任務分配，所以部分分配的機櫃不會改變它。

8.5Per-packet load balancing: spraying and its price逐封包負載平衡：噴灑與它的代價

The mechanism. Every method so far balances flows. Packet spraying balances packets: the switch sends consecutive packets of one flow to different uplinks, round-robin or at random. The arithmetic of Section 8.2 now works in your favor. A 1 MB message is about 256 packets of 4 KB; sprayed over 16 uplinks, each uplink receives about 16 of them, and the relative spread $\sqrt{L/f}$ is ${\sqrt{16/256} = 0.25}$ per message and far smaller over a whole step. Collisions do not disappear, but they last one packet instead of one job.

機制。到目前為止的每種方法平衡的都是流。封包噴灑平衡的是封包：交換器把同一條流的連續封包送到不同的上行鏈路，輪流或隨機。第 8.2 節 的算術現在對你有利。一則 1 MB 的訊息約是 256 個 4 KB 的封包；噴灑到 16 條上行鏈路，每條約收到 16 個，相對離散度 $\sqrt{L/f}$ 在每則訊息是 ${\sqrt{16/256} = 0.25}$，在整個訓練步上則小得多。碰撞沒有消失，但只持續一個封包而非一個任務。

The price: packets arrive out of order. Two uplinks lead to two spines with different queue depths. If path B is 20 µs slower than path A, every packet sent on A during those 20 µs overtakes the packet on B. At 400 Gb/s a 4 KB packet takes about 82 ns to serialize, so 20 µs is about 250 packets of displacement. A go-back-N NIC treats each of them as a loss (Section 8.1). Spraying is therefore impossible with the NICs of the 2024 papers; it requires a NIC that accepts out-of-order packets, and IRN shows how little that costs when done right. The IRN receiver keeps every packet that arrives, sends a NACK that names the cumulative acknowledgment and the sequence number just received, and the sender uses a bitmap of acknowledged packets to retransmit only the real gaps. For RDMA writes the destination address travels in every packet, so each packet is placed directly into application memory as it arrives: no reorder buffer at all, a few bits of bitmap per packet instead of about 1 KB of buffered payload. Across its simulations IRN added 3–10% to the NIC's cache and a few percent of an FPGA. A NIC that instead holds out-of-order packets in a buffer needs roughly ${\text{skew} \times \text{line rate}}$ of memory: ${20\,\mu\text{s} \times 50\GBs} = 1\,\text{MB}$ per NIC at 400 Gb/s, and ten times that at 200 µs of skew. Panel 8.5 computes this occupancy for you.

代價：封包亂序到達。兩條上行鏈路通往兩台佇列深度不同的 spine。若路徑 B 比路徑 A 慢 20 µs，那 20 µs 內送上 A 的每個封包都會超越 B 上的封包。在 400 Gb/s 下一個 4 KB 封包序列化約需 82 ns，所以 20 µs 大約是 250 個封包的位移。Go-back-N 的 NIC 把其中每一個都當成遺失（第 8.1 節）。因此用 2024 年論文中的 NIC 不可能做噴灑；它需要能接受亂序封包的 NIC，而 IRN 示範了做得對時代價有多小。IRN 的接收端保留每一個到達的封包，送出標明累積確認與剛收到序號的 NACK，發送端則用一張已確認封包的位圖只重傳真正的缺口。對 RDMA 寫入，目的位址隨每個封包一起傳，所以每個封包到達時直接放進應用程式記憶體：完全不需要重排緩衝區，每個封包只需位圖的幾個位元，而非約 1 KB 的緩衝載荷。在它的模擬中 IRN 為 NIC 快取增加 3–10%、FPGA 的幾個百分點。反過來，把亂序封包暫存在緩衝區的 NIC 大約需要 ${\text{偏差} \times \text{線速}}$ 的記憶體：400 Gb/s 下每張 NIC 需要 ${20\,\mu\text{s} \times 50\GBs} = 1\,\text{MB}$，偏差到 200 µs 就是 10 倍。面板 8.5 替你算出這個占用量。

Figure 8.8 shows the first packets of a sprayed flow.

圖 8.8 畫出一條被噴灑的流的前幾個封包。

Animation 8.3 sprays one flow over two paths and lets you choose the receiving NIC.

動畫 8.3 把一條流噴灑到兩條路徑上，並讓你選擇接收端的 NIC。

Adaptive routing on InfiniBand, with a hedge. InfiniBand switches have offered adaptive routing for years: the switch may pick the output port for a packet or a flowlet from the current queue occupancies, and the NICs on that fabric tolerate the resulting reordering for RDMA writes. This is one reason InfiniBand clusters report fewer elephant-flow incidents, and the Llama 3 paper notes that the smaller Llama 3 models trained on an InfiniBand fabric while the 405B model trained on RoCE. We have no production paper with numbers for adaptive routing on training traffic to cite here, so treat this paragraph as context, not evidence.

InfiniBand 上的自適應路由，附帶保留。InfiniBand 交換器多年來都提供自適應路由：交換器可以依當下的佇列占用量為一個封包或一個 flowlet 挑選輸出埠，而該網路上的 NIC 對 RDMA 寫入能容忍因此產生的亂序。這是 InfiniBand 叢集較少回報大象流事故的原因之一，Llama 3 論文也提到較小的 Llama 3 模型在 InfiniBand 網路上訓練，405B 模型則在 RoCE 上。我們手上沒有一篇針對訓練流量的自適應路由給出數字的生產環境論文可引，所以請把這一段當作脈絡，而非證據。

Ultra Ethernet, with a hedge. The Ultra Ethernet Transport specification, as published, builds IRN's two ideas into the transport: packets of one message may be sprayed across many paths, the receiver accepts them in any order, and loss is repaired by selective retransmission rather than go-back-N, so a lossless fabric with PFC is no longer required. The Meta RoCE digest notes that Meta's 2026 SIGCOMM paper describes such a transport for clusters beyond 100K GPUs. Switch-side alternatives exist as well: ConWeave (SIGCOMM 2023) reorders packets inside the destination ToR so that an unmodified NIC never sees them out of order, at the cost of buffer in the switch. The direction of all of this: balance packets, not flows, and pay for it at the endpoint.

Ultra Ethernet，附帶保留。已公開的 Ultra Ethernet 傳輸層規格把 IRN 的兩個想法直接做進傳輸層：一則訊息的封包可以噴灑到許多路徑，接收端以任何順序接受它們，遺失以選擇性重傳而非 go-back-N 修復，因此不再需要有 PFC 的無損網路。Meta RoCE 導讀提到 Meta 2026 年的 SIGCOMM 論文為十萬顆以上 GPU 的叢集描述了這樣的傳輸層。交換器端的替代方案也存在：ConWeave（SIGCOMM 2023）在目的 ToR 內重排封包，讓未修改的 NIC 永遠不會看到亂序，代價是交換器內的緩衝。所有這些的方向是：平衡封包而非流，並在端點付出代價。

When spraying is unnecessary. (Section 6.4 draws HPN's same-rail wiring.) HPN's authors say plainly why they did not use flowlet switching or packet spraying: those were unavailable or unproven at their scale, and a host-side transport change is impossible when the RDMA transport lives in NIC hardware. But there is a structural reason too. In a rail-optimized segment, traffic between GPU $k$ on two hosts crosses exactly one switch; there is no uplink choice and nothing to spray. Dual-plane removes the choice at the aggregation layer. The scheduler keeps everything except pipeline traffic inside a pod. What remains is the 60-way choice at the source ToR, which RePaC resolves with disjoint paths. A network that has already removed the choices does not need a mechanism to make the choices well. Spraying earns its cost where choices cannot be removed: many-tier fabrics, mixed tenants, and all-to-all traffic from mixture-of-experts models that crosses rails by nature.

何時不需要噴灑。（第 6.4 節畫出 HPN 同 rail 的接線。）HPN 的作者直說了為何不用 flowlet switching 或封包噴灑：那些在他們的規模上不可得或未經驗證，而當 RDMA 傳輸層在 NIC 硬體裡時，主機端的傳輸層改動也不可能。但還有一個結構性的理由。在 rail-optimized 的 segment 裡，兩台主機的 GPU $k$ 之間的流量恰好只跨一台交換器；沒有上行選擇，沒有東西可噴灑。Dual-plane 拿掉聚合層的選擇。排程器把除了管線流量以外的一切留在 pod 內。剩下的是來源 ToR 的 60 選 1，由 RePaC 以不相交路徑解決。一個已經拿掉選擇的網路，不需要一個把選擇做好的機制。噴灑在選擇無法拿掉的地方才值回代價：多層網路、混合租戶，以及混合專家模型本質上會跨 rail 的 all-to-all 流量。

8.6Entropy you can control, and entropy you cannot能控制的熵與不能控制的熵

The levers. Four knobs raise the number of distinct inputs the hash sees, and each has a cost. Flows per GPU pair: Llama 3 used 16, which with E-ECMP was enough to run 24K GPUs without DCQCN; each flow is a QP with its own NIC state and its own share of the bytes in flight. QPs per connection: Meta's 4 for ranking and 16 for LLMs; round-robin of whole messages, never splitting, to keep message sizes and acknowledgment counts intact. Hash inputs: E-ECMP adds the destination QP, which only helps if the switch can read past the UDP header and the library varies the QP. UDP source port: the NIC assigns it per QP, and it must stay fixed for the life of the QP, or the switch would reorder the flow; rotating it per message is a reorder generator, not a load balancer. Flowlet gap: a switch-side knob, 256–512 µs at Meta, safe only when it exceeds the worst path skew. Every one of these makes a collision less likely. None makes it impossible, which is what the Section 8.2 formula says: $P(\text{no collision})$ is a product of terms below one.

槓桿。四個旋鈕能增加雜湊看到的不同輸入數量，每一個都有代價。每對 GPU 的流數：Llama 3 用 16，搭配 E-ECMP 足以讓 24K 顆 GPU 不用 DCQCN 運行；每條流是一個 QP，有自己的 NIC 狀態與自己那份在途位元組。每條連線的 QP 數：Meta 排序任務 4、LLM 16；整則訊息輪流投遞、絕不切分，以保持訊息大小與確認數量不變。雜湊輸入：E-ECMP 加入目的 QP，只有在交換器能讀 UDP 標頭之後的內容、且函式庫會變化 QP 時才有幫助。UDP 來源埠：由 NIC 為每個 QP 指派，而且在 QP 存續期間必須固定，否則交換器會讓這條流亂序；逐訊息輪換它是亂序產生器，不是負載平衡器。Flowlet 空檔：交換器端的旋鈕，Meta 用 256–512 µs，只有在超過最糟的路徑偏差時才安全。這些每一個都讓碰撞更不可能。沒有一個讓它不可能，這正是 第 8.2 節 公式說的：$P(\text{無碰撞})$ 是一串小於一的項的乘積。

What no knob reaches: synchronized bursts. Web traffic is balanced over time as well as over links; a hot uplink cools when some of its flows end. Training flows start together, at the microsecond the backward pass finishes, and end together. The hash is sampled once per job, when QPs are created, and the sample is then used for every step for days. There is no averaging over time. HPN's Figure 2, reproduced in Section 5.6, shows the shape: every NIC on a host jumps to its full 400 Gb/s and back in lockstep. The tenant cannot change this; it is what synchronous data parallelism means. Deep spine buffers absorb the first microseconds of a burst, which is why Meta could run without DCQCN, but a buffer delays a collision; it does not remove it.

沒有旋鈕碰得到的東西：同步的突發。網頁流量不只在鏈路之間平衡，也在時間上平衡；一條熱的上行鏈路會在部分流結束時冷下來。訓練的流一起開始——在反向傳播結束的那一微秒——也一起結束。雜湊只在任務建立 QP 時抽樣一次，然後這個樣本在接下來數天的每一步都被使用。沒有時間上的平均。HPN 的 Figure 2（見第 5.6 節）畫出了形狀：主機上每張 NIC 同步跳到滿額 400 Gb/s 再回落。租戶改變不了這件事；這就是同步資料平行的意思。深的 spine 緩衝吸收突發最初的幾微秒，這就是 Meta 能不用 DCQCN 的原因，但緩衝延後碰撞，不能消除碰撞。

The strongest lever is placement. The one way to make a collision impossible is to make sure the flow never reaches a point where a choice is made. Rail-optimized wiring does this for same-rail traffic: one switch, no uplink. Dual-plane does it for the aggregation layer. Meta's scheduler learns where each server sits and assigns ranks so that the cut between AI Zones carries the least traffic (a minimum-cut placement), and HPN's scheduler sends only pipeline traffic, 6 MB per step, across pods. In each case the heavy collectives, tensor-parallel AllReduce and data-parallel AllReduce, run where the path is fixed, and the light traffic runs where it is hashed. Compared with QP scaling, which shrinks the relative spread by the square root of the flow count, placement removes the spread entirely for the traffic that matters. When you size a network, do this first; then compute $f/L$ for the traffic that is left, and only then decide whether more QPs, a controller, flowlets or spraying is worth its cost.

最強的槓桿是配置。讓碰撞不可能的唯一方法，是確保流永遠不會到達一個需要做選擇的地方。Rail-optimized 接線對同 rail 流量做到了這點：一台交換器、沒有上行。Dual-plane 對聚合層做到了這點。Meta 的排程器學習每台伺服器的位置並指派 rank，讓 AI Zone 之間的切割承載最少流量（最小割配置）；HPN 的排程器只讓每步 6 MB 的管線流量跨 pod。在每個案例裡，重的集體通訊——張量平行的 AllReduce 與資料平行的 AllReduce——都跑在路徑固定的地方，輕的流量跑在被雜湊的地方。相較於以流數平方根縮小相對離散度的 QP scaling，配置對真正重要的流量把離散度整個拿掉。設計網路時先做這件事；然後對剩下的流量計算 $f/L$，最後才決定更多的 QP、控制器、flowlet 或噴灑是否值得它們的代價。

1. Remove choices first. Place heavy collectives on paths with no hash: same rail, same plane, same pod. (HPN §5–§7, Meta §3.3.)先拿掉選擇。把重的集體通訊放在沒有雜湊的路徑上：同 rail、同 plane、同 pod。（HPN §5–§7、Meta §3.3。）
2. Count what is left. For each leaf, flows $f$ that cross a choice and uplinks $L$. If $\sqrt{L/f}$ is above about 0.3, expect the busiest uplink to run 1.5× or more above average (Panel 8.2).算算剩下的。對每台 leaf，算會遇到選擇的流數 $f$ 與上行鏈路數 $L$。若 $\sqrt{L/f}$ 高於約 0.3，預期最忙的上行鏈路比平均高 1.5 倍以上（面板 8.2）。
3. Buy entropy where it is cheap. 16 QPs per connection with E-ECMP cost NIC state, not hardware (Meta §4.2, Llama 3 §3.3).在便宜的地方買熵。每條連線 16 個 QP 搭配 E-ECMP 花的是 NIC 狀態，不是硬體（Meta §4.2、Llama 3 §3.3）。
4. Buy headroom where entropy fails. 1:1.125 covers two failed uplinks; 1:2 hides everything at twice the cost (Meta §6.2).在熵失效的地方買餘裕。1:1.125 涵蓋兩條上行故障；1:2 以兩倍成本掩蓋一切（Meta §6.2）。
5. Go per-packet only with a tolerant NIC. Spraying without IRN-style recovery turns every skew into a go-back-N retransmission (IRN §3, Panel 5).只有在 NIC 能容忍時才走逐封包。沒有 IRN 式恢復的噴灑，會把每一次偏差變成一次 go-back-N 重傳（IRN §3、面板 5）。

Panel 8.6 applies steps 1 to 4 to one full Meta rack.

面板 8.6 把步驟 1 到 4 套用在一個滿載的 Meta 機櫃上。

Guided readings for this chapter本章相關的論文導讀