Skip to main content

Preface

本次的論文發表於 SIGCOMM 2017, 可以在這邊找到網路上的文章。於 SIGCOMM 2017中，其所屬於的 section 是 Programmable Devices，所以可以料想到本文內容會跟 Programmable Devices 有些關係。果不其然的內容中有提到 P4, NetFPGA，處此之外，本篇內容也提到了 DPDK, Clos Network, MPTCP, DCTCP, incast 等，必須說本篇文章包含了內容實在廣泛，所以要花不少時間去釐清每個元件，才可以了解到本篇論文的內容。

由於本篇論文長達 14 頁,本來也有想過作了簡單的總結就好，大概講述一下想要做到什麼事情，怎麼做到之類的就好。 但是後來想一想，今天會有新東西誕生，勢必就是要解決舊東西的限制。 如果在學習之於，不但能夠學習新知識，更可以強化自己對於舊知識的概念，何樂而不為?

因此本篇一開始就先針對本文做一個簡單的介紹，直接瞭解到本論文希望做什麼，達到什麼目的，為什麼要這樣做。 有興趣的人可以在慢慢往下翻，畢竟內容實在有夠長..XD

簡介

本論文所發生的場景是在 Data Center內，不適用於一般的網際網路，主要是因為網際網路充滿太多未知性與無法掌控的裝置，譬如每條 Link 的頻寬, Switch 的設定等。有這些未知的情況下，無法設計一個好的運作模式來滿足 Low Latency 與 High Throughut 的需求。因此環境都只考慮 Data Center。

本論文提出了 NDP (New Datacenter Protocol Architecture) 這個概念，其具體目標，評比對象以及實作方法如下。

本文希望能夠達到的需求有

  1. 對於 short-flow 能夠有盡量低的 latency
  2. 對於 long-flow 能夠有盡量高的 throughput
  3. 對於一個高度負載的網路中，能夠充分利用整個網路拓墣上的 Link 來傳輸封包 (high network capacity)
  4. 能夠將 incast 情況對網路造成的影響降到最小

本文評比對象有

  1. DCTCP (Data Center TCP)
  2. MPTCP (Multi Path TCP)
  3. DCQCN (Data Center QCN)

    DCQCN is a congestion control protocol for large scale RDMA networks, developed jointly by Microsoft and Mellanox.

本文實作方法

  1. 透過 DPDK 打造 NDP Application (拋棄 TCP, 重新打造 L4 Protocol)
  2. 於 NetFPGA SUME上面實作 NDP 相關功能，作為一個 Hardware Switch
  3. 於 P4上面實作 NDP 相關功能，作為一個 Software Switch

看到這邊如果對於上述的內容感到興趣的話，就可以開始往下看了!

Abstract

近年來 Data Center 蓬勃發展，為了能夠在內部提供更良好的網路效能，不論是低延遲或是高產出，網路架構從早期的三層式架構(Fat tree)逐漸都轉換成 Clos Network，然而傳統的 TCP 協定在設計上並不是針對 Data Cetner來設計的，因此其設計原理導致其不能滿足需求。 因此本論文提出了 NDP (new data-center transport architecture)，其能夠提供 short transfer接近完美的傳輸時間，同時對於廣泛的應用情況，如 incast 下亦能夠提供很高的傳輸效能。 NDP架構下， switch 採用非常小的 buffer來存放封包，當 buffer 滿載時，不同於傳統的將封包丟掉，NDP採取的是截斷封包的內容(payload)，只保留該封包的標頭檔，並且將此封包設定為高優度優先轉送。這種作法讓收端能夠有更完整關於送端的資訊，能夠動態的調整傳送速率。 本論文將 NDP 的概念實作於 Software switch, Hardware Switch 以及一般的 NDP application。這中間使用的技術與硬體分別包含了 DPDK、P4 以及 NetFPGA。 最後本論文進行了一系列效能評比，於大規模的模擬中證明了NDP能夠為整個 data center 提供低延遲與高輸出的特性。

Introduction

隨者 Data Center 爆炸性的成長，為了滿足其內部傳輸的需求(低延遲/高輸出)，有各式各樣的新方法或是舊有技術的改進用來滿足上述需求。譬如 TCP 改進的 DCTPC、本來就存在已久的 MPTCP 甚至是 RDMA (RoCE)。 若對 RDMA/RoCE 想要更瞭解，可以參考下列連結。RDMA Introduction (一) 再 RDMA 的網路環境中，為了減少封包遺失對整體傳輸造成的傳輸，都會希望能夠將整個網路傳輸打造成 lossless 的環境，為了達成這個方法，可以採用 Ethernet Flow Control， Explicit Congestion Notification(ECN) 或是 Priority Flow Control(PFC)。然而在 SIGCOMM 2016 微軟發了一篇 paper 再講 RDMA + PFC 的問題。其表明雖然 PFC 可以用來控制傳送封包的速率，藉此達到 lossless 的網路環境，但是一旦整體網路處於高度壅塞的情況時，資料封包與 PFC 控制封包的爭奪會使得整體網路沒有辦法繼續提供低延遲的優點，最後給出了一個結論 “how to achieve low network latency and high network throughput at the same time for RDMA is still an open problem.“

在這篇論文內，作者提出了一個不同與以往思維的新協定 NDP 來滿足上述的要求。 NDP 不同於 TCP，不需要先透過三方交握來進行連線才可以傳輸封包，同時也避免掉 TCP slow start 的機制，可以連線一開始就採用全速的方式去傳送封包。 此外， NDP 採用了 per-packet multipath 而不是 per-connection multipath 的方式同時透過 NDP 協定的方式避免掉同條連線中封包順序亂掉(Out of order)所產生的問題。 對於 NDP switch來說，採用了類似 CP(Cut Payload) 的機制，當switch 的緩衝區滿載的情況下，對於接下來收到的封包不會直接丟掉，而是會將其 Payload 給移除，並且設定高優先度的方式將其標頭檔盡可能快速的傳送到目的地，讓接收段能夠有資訊瞭解到當前網路與發送端的狀態。 透過 CP 的機制可以對 metadata 達到近乎 lossless 的狀況，不過對於 data 來說則沒有辦法。不過因為 NDP 本身協定設計的方式，封包掉落所產生的影響並不會像 TCP 一樣有如此嚴重的影響。

Design Space

對於內部使用的 Data center 來說，其網路流量大部分都是屬於 Request/Reply,這種類似 RPC 方式的流量。這意味者以網路使用率來看其實不會一直處在滿載的狀況，但是對連線接收端的應用程式(譬如 server)來說，其所收處理的網路流量可能是大資料的傳輸，也可能是簡單資料的短暫連線。對於短暫連線來說，最大的重點就是低延遲，盡可能快的傳輸回去。 為了處理這個問題，今日有滿多的應用程式決定採取 reuse TCP 連線來處理多個 request，藉此方式減少 TCP 三方交握所產生的延遲。 然而，是否存在一種架構，不論當前整個網路系統是否處於高流量負載，該架構能夠讓應用程式不需要重複使用連線，讓每個 request 都是一條全新連線，同時又能夠接近完美的延遲(意味者不會像 TCP 都要先經過三方交握才可以開始傳資料)。 於是乎 NDP 的設計發想就出現了，為了達到上述的要求，首先必須要重新思考，當前網路架構中，是什麼因素阻礙了上述要求，這些阻礙要如何克服。 因此接下來的章節會講述這些因素。

End-to-end Service Demans​

本文列出了四個 data center 內應用程式要追求的特性。

Location Independence​

一個分散式的應用程式其運行於data center內的任一機器上都不應該要影響應用程式本身的功能。由於目前都採用 clos network 的方式來設計網路拓樸，所以整個網路拓樸方面應該是能夠提供足夠的流量來使用，而不會變成一個理由或是瓶頸使得應用程式必須要選擇特定的機器才可以運行。

Low Latency​

雖然 Clos Network 的架構能夠提供足夠的頻寬給拓墣中內的服務器，對於流量的負載平衡能提供良好的效果，但是對於短暫連線來說，並沒有辦法提供低延遲的能力。 作者認為雖然能夠提供高流量輸出是一個很重要的議題，但是能夠提供低延遲的能力則是更重要且優先度更高。

Incast​

Incast 這個專有名詞的介紹可以參考Data Centers and TCP Incast - Georgia Tech - Network Congestion，簡單來說就是同時間有大量的request進到data center內，這些request都會產生對應的reply然後這些reply連線同時間一起進入到 switch內，這會使得 switch 的緩衝區立刻滿載沒辦法繼續承受封包，導致部分的 TCP 連線需要降速重送。 作者認為一個好的網路架構遇到這種問題時，應該要能夠保護背後的應用程式連線，讓這些連線應該要盡可能地維持低延遲性。

Priority​

這邊特性老實說有點難以想像，我盡力的就我所瞭解的去解釋。 假設今天有一個應用程式，同時會發送不同的 request 到後端去處理，而這些 request 所產生的 reply 本身是有依賴的關係。 所以假如這多個 reply 沒有依照當初發送 request 的順序回來的話，在應用程式端這邊就必須要特別去處理，譬如說不要同時送多個request，不過這樣就沒有更好的效能表現。 因此對於應用程式來說，若本身能夠有一個優先度的機制，能夠決定那些封包要先處理，就可以解決上述的問題，而讓應用程式本身就可以更自由的去處理。

Transport Protocol​

目前 data center 內部採用的 Transport Protocol 雖然可以處理上述應用程式的問題，但是為了處理那些問題，反而會失去下列特性。 而 NDP 本身在設計時，希望能夠在滿足上述應用程式的需求，同時又保有下列的特性。

Zero-RTT connection setup​

目前主流的 TCP 協定再傳送資料前，必須要先進行一次三項交握，這意味者當 data 送出去前，至少要先花費 RTT*3 的等待時間。 對於低延遲的應用程式來說，希望能夠達到 RTT*0，至少 RTT*1 的等待時間就能夠將資料送出，這意味者對 NDP 來說，在資料發送前，整個連線不需要有三方交握類似的行為，才可以一開始就直接送出資料。

Fast start​

Data Center 不同於網際網路的地方在於網路拓樸中的每個 Switch/Link 都是自己掌握的。 所以 TCP 採用的 Slow Start 其實對於 Data Center 來說是沒有效率的，畢竟一開始就可以知道可用頻寬多少，不需要如同面對網際網路般的悲觀，慢慢地調整 Window Size，而是可以一開始就樂觀的傳送最大單位，在根據狀況進行微調。 若採取這種機制，則應用程式可以使用更快的速度去傳送封包。

Per-packet ECMP​

在 Clos Network 中，錯綜複雜的連結狀態提供了 Per-flow ECMP 一個很好發揮的場所，可以讓不同的連線走不同的路徑，藉此提高整體網路使用率。 然而如果今天 Hash 的結果相同的話，其實是有機會讓不同連線走相同的路徑，即使其他路徑當前都是閒置的。 若採取 MPTCP 這種變化型的 TCP 來處理的話，該協定本身的設計可以解決上述的問題，但是對於短暫流量或是延遲性來說，卻沒有很好的效果。 為了解決這個問題，如果可以將 Per-flow ECMP 轉換成 Per-Packet ECMP。因此 NDP 本身協定的設計就是以 Per-Packet ECMP 為主。

Reorder-tolerant handshake​

假設我們已經擁有了 Zero RTT 以及 Per-packet ECMP 兩種特性，擇一條新連線的封包可能就會發生 Out of order 的情況，收送順序不同的狀況下，若對於 TCP 來說，就會觸發壅塞控制的機制進而導致降速。 因此 NDP 在設計時，必須要能夠處理這種狀況，可以在不依賴封包到達先後順序下去處理。

Optimized for Incast​

即使整個 data center 的網路環境，如頻寬等資訊一開始就已經可以掌握， incast 的問題還是難以處理，畢竟網路中變化太多，也許有某些應用程式就突然同時大量產生封包，這些封包同時間到達 switch 就可能導致封包被丟棄。 因此 NDP 本身在設計時，也希望能夠解決這個問題。

Switch Service Model​

在一個 data center內，除了應用程式特定，傳輸層協議(Transport Protocol)之外，還有一個性質也是很重要的，這個性質與上述兩個性質關係緊密，一起影響整個網路的運作，這個性質就是 Switch Service Model。 作者認為這性質中，最重要的就是當 switch port 發生阻塞時會怎麼處理，這個性質會完全影響到傳輸層協定以及壅塞控制演算法(Congestion control algorithms)的設計，甚至是傳輸相關的概念，如 per-packet ECMP 都會被影響到。 作者提到，目前有很多種預防壅塞機制，譬如 Loss as a congestion，Duplicate or selective Acks等，其中 Duplicate or selective Acks 會主動去觸發重送，這種技巧對於長時間連線來說是好的，但是對於需要低延遲的短暫連線來說是不好的，主要是這些重送都會經過一個 RTO(Retransmission timeouts)，這個時間的長短都會產生一些負面的影響，因此也不是一個萬用的解法。

ECN(Explicit Congestion Notification) 的出現幫助壅塞狀況提供了不少改進，譬如 DCTCP (data center TCP 就採用了這個技術來輔助。這個技術對於長時間的流量來說，能夠有效的減少封包遺失的數量，然而對短暫流量來說卻沒有太大的幫助，因為短暫流量太短暫了，根本來不及去接收 ECN的封包並處理。在現實情況中，switch本身會採用一個較大的緩衝區來處理資料封包以及ECN封包，這種設計對於 incast 的現象能夠有效地減緩封包被丟棄的情形。但是也因為緩衝區太大，每個封包在 Switch 內待的時間就會更長，因此重送機制的時間就會被拉長，導致低延遲性就會破功。 除此之外，對於 Lossless Ethernet 的傳輸來說，則是會透過 802.3X 的 Pause Frame 亦或是 802.1 Qbb 的 PFC (Priority Flow Control)。這類技術都是透過控制封包阻止送端停送封包，降低封包遺失的數量。然後這些就有技術也不是十全十美，以 PFC 來說，在一個高度乘載的網路拓樸中，有可能會有兩條不同的連線根據Hash導向走向相同，同時這兩個連線最初的設定是相同的優先度，則有可能會因為一條連線的壅塞進而導致其他連線也被影響到。 上述這些壅塞機制的設計除了 ECN 之外，其餘的對於 Per-packet ECMP 都沒有能夠提供良好的效果。 最後，提到了一種稱為 CP (Cut Payload) 的做法，這種機制就是當壅塞發生時，不丟棄整個封包，而只是丟棄封包的資料，而保留封包的標頭檔，對於一個常見的TCP封包來說，大概就是 (XX:14XX)的感覺。當應用程式端收到只有標頭檔，沒有資料的封包，就可以知道這個當前線路有壅塞的情況，可以進行對應的處理。 這種情況下，就可以避免減少 RTO 對於重送造成的時間延遲。 然而這種設計也有兩個問題(畢竟CP是1994提出的論文)

  1. 整個 Switch 採取FIFO的機制，所以這些被砍掉資料的封包，也是要慢慢等待switch將封包處理完畢才可以往外轉送，這邊就會大幅增加這些封包的RTT時間
  2. 這個設計是基於 single-path 傳輸，沒有考慮到多條路徑傳輸，不論是 per-packet 或是 per-flow 的ECMP。

在看完了以上這麼多段落後，大概可以歸納出作者心目中的完美協定，簡單複習一下

  1. 對於短暫流量能夠提供低延遲，低延遲，低延遲
  2. 對於長時間流量盡量能夠提供高流量輸出
  3. per-packet ECMP
  4. 遇到 incast 等情況也能夠繼續保持低延遲

因此接下來的章節，就會講述 NDP 到底如何實作並且盡可能地有提供上述性質。

Design

為了滿足上述的條件，NDP 在設計時就決定整個設計要包含完整架構，包含了 1.switch的行為 2.routing 3.全新的 Transport協定

基本上可以使用下圖做一個概括性的統整，透過全新設計的 NDP 架構，能夠滿足該圖中的每個特性。 接下來會簡單介紹每個區塊大致上要做的事情。後面的章節才會詳細敘述其設計方法。

對於 Clos Network 拓樸來說，因為網路內擁有多條錯綜複雜的連結，因此整體網路的頻寬是足夠的。這對於想要執行 Load-Balanced 的應用來說是綽綽有餘的，然而為了避免流量都流經相同的路徑導致某些路徑上面有大量的流量進而導致封包掉落並且對於延遲性與流量輸出都有影響。因此必須要採取必要的措施將連線給打散到不同的路徑之中。 此外，對於短暫連線來說，per-packet的ECMP相對於 per-flow來說更有意義，但是per-packet的ECMP必定會遇到封包順序不同產生的 out of order情況。 為了滿足短流量低延遲的效果，發送端不能利去探測當前網路的頻寬來決定傳送速度，必須要在第一個封包就將資料送出，也就是所謂的 Zero RTT。 對於 switch 來說，要達到低延遲，則緩衝區不能夠太大，否則封包待在緩衝區內的時間過長，就會導致該封包要花更長的時間才能夠被送過去。 在小緩衝去的前提下，封包數量一多則緩衝區就會馬上爆滿。當封包掉落同時加上因為 per-packet ECMP 所產生的封包順序錯亂問題 (out of order)，這會使得收送端(receiver)會非常難去處理這些問題，無法辨別當前沒有收到封包到底是什麼原因。 若想要完整的避免封包遺失，則 switch 的緩衝區就要夠大，譬如採取 pause frame，亦或是 PFC這類型 lossless network。 然而這類技術都會因為當前連線產生的壅塞判斷去影響網路中其他連線，這就會使得某些連線沒有辦法達到低延遲的效果。 所以NDP設計的理念是一種介於 loss 與 lossless 的概念。 最後，採取的 Packet Trimming，其設計理念與 Cuy Payload 極為相似，此種情況下， switch 採用小緩衝區，當接收端發現封包只有標頭沒有內容時，就可以判斷當前網路有壅塞發生。為了可以讓重送時間盡可能的快，對於這些被截斷內容的封包， switch 應該要盡可能的快讓該類型的封包送出去。 這類型的封包到達接收端後，會讓接收端有資訊可以知道當前那些應用的封包到達，藉由這些資訊加上一個完整的封包池(receiver-pulled pool)，接收端就可以精準地控制那些封包要優先處理。

NDP Switch Service Model​

前述有提到過 Cut Payload 的技術，透過把資料丟掉，單純送標頭檔給對方。 這邊不丟掉封包的原因是希望能夠通知 接收端 端關於封包的訊息，讓 接收端 端可以要求 送端 重送。這整體所消耗的時間會比接收端依賴　Retransmission Timeout 來的還要短。 然而。本文作者發現到，若採用最原生的 Cut Payload 實作其實會引發下列問題，因此要將其改良以解決這些問題。

直接以下圖來解釋，在一個 9KB jumbograms 的情況下，去探討應用程式之間的 goodput， goodput 與 throughput 的差異是 goodput 代表的是應用程式真正接收到的封包量，不包含協定標頭檔以及重送封包所造成的流量。

圖中紅線的部分代表的是 原生 CP 實作，而藍線的部分代表則是 NDP 的實作。 X 軸代表的是網路中有多少條連結上面被大量被切斷的封包(被砍掉內容，只剩下標頭檔)。 Y 軸代表的是在當前網路下，應用程式真正收到的 goodput 佔理想值多少百分比。(最高100%)。

圖中實線代表的是所有應用程式的平均goodput，而虛線代表的是10%最差應用程式們的平均goodput。 這邊先來看原生CP的效果，可以明顯看到實線的部分，會因為流量愈多，而使得整體的 goodput 就大幾乎呈線性下線。 而對於虛線來說，整個幾乎慘不忍睹，代表後半部分的應用程式根本沒有辦法擁有好的傳輸量。

除了上述模擬結果外，原生CP還有一個問題是採取 FIFO 的機制來收送一般封包與被切斷後的封包，這意味者 CP 想要讓 收端盡快地知道有封包要重送，但是這些被截斷的封包又要等待 switch 內的緩衝區都被消耗掉才有機會被送出，其實這一來一回對於整體的是會造成一些損傷的。

為了解決上述原生CP 帶來的問題， NDP 提出三大改革

  1. NDP Switch 維護兩個佇列緩衝區，低優先度的用於資料傳輸，高優先度的用於被截斷封包的傳輸，ACKS 以及 NACKS。 2. 作者認為這個設計聽起來有點詭異，看起來好像反而會讓資料封包更晚送出去，但是經過實驗證明，高優先度的封包到達接收端並且通知送端要重送封包時，通常 switch 低優先度緩衝去的封包都還沒有全部處理完畢。

  2. 高優先度跟低優先的佇列緩衝區彼此之間採取的是 10:1 的輪流機制，每送十個高優先度的封包，就送一個低優先度的封包，這可以讓要重送的封包盡早通知到接收端

  3. 為了打亂網路中平衡狀態(強者恆強，弱者恆弱)，每當低優先度的佇列滿載且遇到新封包時，這時候 Switch 有兩個行為會採用(機率分別是 50%)。

    • 將新到的封包截斷，送到高優先度佇列
    • 將低優先度最後面的封包截斷，送到高優先度佇立，而剛進來的封包就送到低優先度佇列

  4. 藉由上述兩種行為，作者說可以打亂網路的平衡，這點可以由圖2的虛線看到，在 NDP 的環境中，即使是效能最差 10% 應用程式的 goodput 跟平均也是差不多的。

Routing​

前述已經提到， NDP 想要完成 per-packet ECMP而非 per-flow ECMP，於是作者在這邊提出了兩大類做法

  1. 讓 switch 本身隨機當前封包該怎傳送
  2. 讓 送端 決定當前封包該怎傳送

根據作者自己的實驗證明，讓送端去選擇封包該怎轉送會比讓 switch 去隨機轉送封包來得更有效率，同時因為 switch 本身不用去思考怎該怎轉送封包，每個封包處理的速度可以更快速，因此 switch 的緩衝區可以設置的更小，對於低延遲的特性有更好的支持。 NDP 認為，由於本文的環境是在 data center 內，網路拓樸的狀況都是可以事先知道的，譬如從送端到接收端共有那些路徑可以走。 因此 NDP 的實作方式是 送端事先要先瞭解到送端之間有哪些路徑可以走，然後每遇到一個封包，就挑一個路徑出來發送，下一個封包就送剩下的路徑們中間隨機挑一條去發送，當所有的路徑都已經走過一次後，就全部重新來過。 這樣的做法達到兩個優點 1) 藉由分散封包到所有路徑去傳送，能夠提升網路整體的使用率，並且減少某條網路成為瓶頸的可能性。 2) 每次挑選時都透過類似隨機的方式，可避免多個應用程式會走到相同的走法導致網路出現太規律的走法，進而導致使用率不佳或是某些路徑過於壅塞。

至於，關於 讓送端決定當前封包該怎傳送 怎麼實作，作者提出了三種方法。

  1. source-route:
    • 作者沒解釋，不確定其實作方式。
  2. label-switch:
    • 事先規劃好那些 label 走那些路徑，然後送端幫封包上 label
  3. destination addresses:
    • 根據目的端的位置來選擇，假如目的端有多個 IP 地址，則每個地址都可能有不同的走法。

Transport Protocol​

接下來作者要詳細介紹整個 NDP Transport protocol 的設計。

NDP 在設計 Transport 協定時是基於 receiver-driven 的理念去設計的。希望藉由這個設計能夠跟之前提過的各式各樣技術結合，如 multipath forwarding、 packet trimming 以及 short switch queues。藉由與這些技術結合，NDP 想要提供1)低延遲2)高產出的效能。

作者這邊提到，TCP因為早期設計給網際網路使用，所以設計理念是悲觀的，因為不知道整個網路上每個節點的狀況，盡可能的小心去使用。譬如所謂的 slow start、三方交握等原則。 此外，對於 TCP 來說，當今天若同時發生網路壅塞掉封包或是多重路徑路由所導致封包的順序不一致，這些情況會讓 TCP 無法分辨到底發生什麼事情，於是最後只好要求送端重傳，這行為無形間就降低了整體的傳送速率。

然而對 NDP 來說就不一樣，由於是在 data center 內，能夠事先知道整個網路節點的各情況，因此 NDP 希望採取的是樂觀的設計理念，包含了

  1. 第一個 RTT 就送資料，不等三方交握
  2. 一開始就根據當前線路的最大乘載量去設定傳送速率，假設都沒有其他流量使用。
  3. 不依賴順序的協定內容

NDP 採用了截斷封包的方式，透過標頭檔的內容告訴接收端到底哪些封包需要重送，這使得接收端有更明確的知識知道網路發生什麼情況，因此封包到達的先後順序就顯得不重要。

接下來使用下圖來解釋截斷封包的運作模式。

假設今天從 SRC 要傳送九個封包到達 DST，當封包到達 DST 上層的 switch(TOR) 時，因為 switch 的資料緩衝區(低優先度佇列)只能承受八個封包。所以第九個封包就被截斷了(時間點為 T(trim)) 接下來透過不同優先度的佇列的設計，被截斷的封包可以在 T(header)的時間就馬上到達 DST， DST 在看到標頭檔後就馬上學習到第九個封包需要重送，因此馬上送個資訊回到送端。 此資訊到達送端的時間點為 T(rtx)，同時間 switch 還在處理剛剛的八個封包，大概處理到第二個左右。 當送端將第九個封包送到 switch 時，這時候 switch 處理到第六個左右，因此資料緩衝區不但有空間可以容納地九個封包，同時這過程中也沒有任何處於閒置的況狀，可以說是將緩衝區的使用率盡可能的提升。

所以到這邊為止，我們已經可以知道截斷封包能夠告訴收端哪些封包需要重送。 作者認為藉由上述的特性與 Zero RTT 的結合，認為讓送端去決定當收到一筆資料(Zero RTT)後送端要傳送多少封包是最佳的選擇。

接下來分成兩部份去介紹，第一部分介紹其設計理念及原則，第二部分則是詳細介紹步驟

  1. 當送端一開始用全速去傳送封包後，接下來就會停止傳送封包
  2. 等待 接收端 發送請求要求 送端 繼續送封包
  3. 接收端可以根據當前本身收送封包的速率(譬如對外連結上有多條連線導致每條連線都沒有辦法用到最高速度)，因此會由 接收端 去決定 送端 當前要送多 快。
  4. 不論是重送的封包，抑或是全新的資料封包，接收端都可以要求送端去傳送。
  5. 接收端 採用 Pull 的概念來達到控制 送端 的傳送速率，接收端 會維護一個 Pull 佇列，供所有連線一起使用。
  6. Pull 佇列內放置的是 Pull 封包，該封包要標示屬於哪個連線，以及一個計數，而該計數則是 per-sender的，用來記錄當前發送過多少個 Pull 封包。
  7. Pll 佇列預設會公平的去處理每個連線所對應的 Pull 封包，不過可以根據連線優先度調整其傳送的 Pull 封包數量，藉此提高對應送端的傳送速率。

詳細描述每個步驟行為如下

  1. 連線開始時，送端一開始就用全速將封包送往 接收端，這些封包都會包含類似 TCP的序號。
  2. 若接收端收到的是被截斷的封包，會立刻傳送 NACK 給送端，要求其將準備重送封包(還不需要重送)
  3. 若接收端收到的是資料封包，會立刻傳送 ACK 給 送端，通知其該封包已接收到(清除舊有資料，準備新封包，此時也還不會傳送)
  4. 當 接收端 收到封包(資料或是截斷封包)，都會馬上加入一個 Pull 封包到其 Pull 佇列中。
  5. 當 送端 收到由 接收端所發送的 Pull 封包時，會根據 Pull 封包內的計數來決定當下要傳送多少封包(可以是重送封包，也可以是新封包)
  6. 當 送端 將所有封包都傳送完畢後，就會將最後一個封包打上標誌，當 接收端 看到此標誌時就知道對應的 送端 已經沒有封包要送了，就將其對應的 Pull 風包給移除，避免下次產生不必要的請求傳輸。
  7. 若送端 之後又有資料想要傳輸，則必須主動傳輸給 接收端，而不會透過 接收端的 Pull 封包來取得。

根據作者本身的實驗數據，其相關設定如下

  1. switch 的資料緩衝區只有八個封包
  2. MTU 設定為 9K (jumbograms)，
  3. switch 能力為 10Gb/s
  4. 環境為 FatTree

在此環境下，每個封包完整處理的時間為 7.2µs，若考慮到優先佇列的使用，最差情況下的處理時間是 400µs，此數據相對於一般來說其實是非常小的。 因此在 NDP 的環境中，RTO (Retransmission timeout) 可以設計得更小。

回過來看先前提過的問題， NDP 要如何在 incast 的狀況下有良好表現? 假設一開始有很多個 送端，每個都用全速傳輸。可以想像得到的是會有很多封包都被截斷，接者每個對應的 接收端 都可以採用 Pull 的概念控制對應 送端的傳送速率，就可以讓每個送端的傳送速率總和能夠符合 switch 的處理速度，藉此能夠讓被截斷的封包數量降到最小，甚至沒有。

Coping with Reordering​

根據 Per-packet 多重路徑路由，對於送端/接收端來說，資料封包，Pull 封包， ACK 以及 NACK 在收到的時候是非常有機率是順序錯亂的。雖然 NDP 一開始的設計是不用擔心這個情況的。 不過作者提下有提了一個情境是關於 Pull 的問題，這邊實在講得太難讓人理解，我看了好久，思索許久，還是無法理解到底在說什麼。 所以決定暫時放棄這個段落。

The First RTT​

NDP 為了達到能夠在第一個封包就直接送資料而不採用 TCP 的三項交握後送資料，必須要處理三個問題

  1. 避免遇到大量相通 Source IP 的垃圾封包影響

    (因為 TCP有連線認證，沒有連線的 TCP 封包不會被處理，避免被大量垃圾影響)

  2. 避免同樣一條連線在 連線建立方面不小心處理多次
  3. 處理在 第一個 RTT 之間經由多重路徑路由造成順序錯亂的資料封包

目前已知採用 First RTT 的實作，如 T/TCP 以及 TFO (TCP Fast Open)都有一些相關機制，譬如採用 Token 或是 Connection ID 來處理上述問題，但是沒有一個實作能夠同時處理三個問題。

  1. 這個問題 NDP 不想處理，認為可以透過 Hypervisor/NIC 之類的方式預防

    逃避問題?

  2. 在 送端/接收端 兩邊都設計了 time-wait 的狀態。

    這邊也看不太懂，到底要怎麼透過這個狀態處理此問題。估計不是重點，敘述很少。

  3. 由於 per-packet ECMP 的關係，第一個到達接收端的封包往往不是第一個送出的封包，為了處理這個問題，送端第一次送出的封包都會帶有一個SYN的標誌以及該封包是第一次送出封包中的第幾個。藉由這個資訊就可以讓任何一個第一次送出中的任一個封包來建立連線。

Robustness Optimizations​

假如網路一切都順順利利的運行，上述 NDP 的實作其實運作得非常良好，然而好景不常，網路常常會出問題，譬如 switch 或是 link 會損毀。 這種情況下， NDP 要怎麼處理這些問題來繼續保持其提供的低延遲與高輸出的特性。 常見的問題有

  1. switch, link 損毀導致封包不通
  2. link 出問題，突然降速，譬如從 10Gbs 降速成 1Gbs

作者表示，傳統的 single-path TCP 對於這些問題都沒有很好的處理方式，會讓整體的效能大幅度下降。 NDP 處理的方式就是採用大量的 Counter，去記住每條連線上面關於 ACK 以及 NACK 的數量，同時透過 per-packet 多重路由的方式來傳送封包。 因此 送端 會定期檢查，若當下所有可傳送路徑中，有某些路由上面的 counter 數值異常，代表可能出現問題，不論是降速抑或是網路不通。 此時就會將有問題的路由先從候選清單中排除，避免封包走到有問題的路由去。 作者表示，傳統的作法大部分都依賴路由協定去偵測問題並且動態修改路由表，這些雖然有效，但是要花費太多時間去處理，因此效果不彰。

Rteurn-to-Sender​

前述提過，採用 Cut Payload 的機制能夠有效的解決 incast 的網路問題，然而當 incast 的封包過多時， switch 上面的兩個佇列(高/低優先度)都可能會被塞滿，在這種情況下封包就會被丟棄了。 舉例來說，高優先度佇列可以存放1125 * 64-byte的封包量，而低優先度佇列只能存放 8 * 9K-bye 的封包量。假設 送端發送了一個封包過去，卻遲遲沒有等到回應，在經過 RTO 的時間後，就會重送封包。 根據前述的實驗， 最大的 RTT 時間是 400µs，因此作者認為最大的 RTO 設定為 1ms 即可。 然而根據 10Gbs　的傳輸能力來開，要處理1125 * 64B 的封包大概需要 8ms，這意味者重送的封包是可以在佇列被消耗完畢前送達到 switch，可以保障不會有 switch 處於閒置的狀態進而提高整體使用率。

為了追求極致的作者認為，在某些情況下，譬如高優先度的封包或是資料量極小的封包 當所有的佇列都滿的情況下，這時候 switch 就會採取神秘的作法，將封包的 source IP 以及 destination IP 給反轉，然後將該 header 迅速送回給 送端，告訴送端說你有封包要掉了，快重送。 然後這種機制只有在某些特殊情況下，可能網路當下有些問題之類的，作者想要加快更快的處理速度避免等待 RTO來處理

下圖是根據模擬環境得到的數據圖，該模擬環境如下

  1. 432 機器
  2. FatTree

該Y軸採用的是 CDF(cumulative distribution function)，X 軸紀錄的是當送端送出第一個封包到達其收到第一個ACK所花的時間。 此數值包含所有的 delay，也包含重送所導致的花費。

  1. Permutation 顯示的是 432-node 中每個node都會往下一個 node 來進行連線，故會有 431 條連線
  2. Random 顯示的是 432-node 中每個node都會隨機找一個 node 來進行連線，故會有 431 條連線 上述這兩種 case 都表現不錯，能夠完整的用滿整個 FatTree 的網路頻寬，同時平均的 delay 大概落在 100ms。

而接下來 Incast 的情況則是挑選100 node 同時間對同一個 node 進行發送的實驗，變異數則是每個連線的傳輸大小。 可以觀察到的，當傳送數量只有 135KB 時，整體的效能是比較差的。 原因是每個連線都能透過第一次的RTT就將所有的封包傳送出去，這情況導致大量的封包被截斷甚至超過緩衝區的數量。同時大概只有 25%% 左右的標頭檔被最佳化給送回給 送端去加速處理。 以 delay 來看，最後一個封包花了 11,055µs 去傳送。

假設今天整體傳送量更大，到達了 1350KB，雖然第一個封包傳輸的行為會跟 135KB 的實驗一致，但是後續 NDP 的設計能夠讓整體後續的處理更為平順以及更穩，所以其平均的處理時間大概只有 95µs。

Congestion Control​

作者表示， NDP 本身沒有任何 Congestion Control，因為 Congestion Control 本身是為了下列兩個目的而誕生的。

  1. Avoiding congestion collapse
  2. fairness

而 NDP 本身實作的特性已經完全避免掉上述的問題，所以根本沒有必要去實作沒必要的 Congestion Control。

NDP 的設計下，每個連線一開始都樂觀地採用全速發送，同時因為協議設計的關係，接收端擁有大量關於當前連線的資訊，透過 pull 佇列的設計能夠讓每條連線平均的使用當前網路流量。 不過作者也有提到，由於接收端可以決定送端傳送封包的速率，因此若有些連線被標註是高優先度的，則可以使用比一般連線更多的流量。這種情況下就是故意造成不公平的，因此也不是大問題。

Limitation of NDP​

接下來的章節中，作者透過實驗證明了在各種流量模式中，NDP 提供的效果非常接近於 Clos 網路架構理論上的效能。 在非對證的網路架構中，例如 BCube、 Jellyfish， NDP 的表現會稍微差一點，主要是當前網路壅塞時，送端會將封包透過不同距離的路徑來傳輸封包(就不是ECMP了)。於這種情況下，若採用 sender-based per-path 的多重路由就會有良好的效果。

有一篇paper在講述上述的問題 C. Raiciu, S. Barre, C. Pluntke, A. Greenhalgh, D. Wischik, and M. Handley. Improving datacenter performance and robustness with Multipath TCP. In Proc. ACM SIGCOMM, Aug. 2011.

對於一個超級高度負載的網路中心來說，當封包數量過多的時候，會發生送端發生的封包一直處於被截斷的情況，然而雖然表現不好，但是跟目前已知的協定，譬如 DCTCP 比起來， NDP 的效能還是勝出。

最後的問題就是 環境部屬問題， 只要當哪一天 P4 交換機能夠廣泛的部屬在 data center 中的時候，要部屬 NDP 就是很簡單的事情。此外，如何跟現有的 TCP 連線共存也是一個問題，因為 NDP 目前會吃掉該網路的流量導致 TCP 幾乎沒有辦法使用，因此在 P4 交換機端應該要有辦法去處理相關的問題。

Summary

到這邊為止，已經可以大概知道 NDP 的設計思維，接下來就要探討其如何實作以及其實驗效能。 不過必須說，只有Paper而缺少投影片或是影片的情況下，很多敘述都要靠想像力去思考到底怎實作，花了不少時間在思考，甚至有些情境還想不出來到底是什麼，只能憑感覺去想像。當然，這個會有這些問題其實是因為自己知道的東西還不夠多，所以變成很多作者認為是基本概念的東西，對我來說都要重新思考學習，才會導致自己思考不夠完善。 只好繼續多念書多加強自己了