[NSDI 2020] Expanding across time to deliver bandwidth efficiency and low latency

Abstract

Opera是一個動態調整的網路
- 使用跟expander-graph-based一樣的multi-hop forwarding，能夠使latency-sensitive traffic快速被送達
- 同時為bulk flows提供time-varying的direct forwarding的線路以及接近最佳化的頻寬
- 由一層packet-switched ToR (leaf)以及一層reconfigurable circuit-switched (spine)組成
不同於以往做法，Opera不需額外的separate electrical network、active circuit scheduling(?)

datacenter供應商長期以來喜歡採用over-subscribed network架構，雖然有提供all-to-all connectivity，但是實際上佔用了network capacity與bandwidth
雖然目前已經有一些方法可以動態調整link capacity試圖達成更好的performance，但有些方法會造成大量的delay
可調整的網路(reconfigurable network)通常都試圖為end points提供direct link來減少”bandwidth tax”
- bandwidth tax：原本透過direct link就能送達的封包多走了k個link (多跳k個hop)，k乘以封包大小即為bandwidth tax
- 尤其是”bulk flow” (大型flow)，這類的flow通常completion time取決於整個傳輸路徑中的available capacity而不是propagation delay (小型flow則剛好相反)
Opera保證每對end point之間每隔一段時間就會被分配到一條direct link
Opera能夠自行決定
- 馬上把封包傳出去(適用於能接受一定程度bandwidth tax的小型flow)
- 將封包暫存，等到有direct link被建立時再傳封包出去(適用於不能接受bandwidth tax的大型flow)

使用folded-Clos topologies
會有多層switch，每層都要提供足夠多的packet switch以及他們之間的link確保有足夠的capacity可以支持server之間任何mixture communication
可把達成上述條件的network視為一個大型switch

雖然上述的”big switch”設計非常理想，也擁有足夠彈性來支援各種服務，但在network scale很大時並不容易建立
事實上，根據報告，目前現有的一些大型datacenter也沒有配置完整的folded-Clos topologies。另外，有研究顯示隨著link rate超過400Gb/s，現有的packet-switching技術可能無法跟上
Over-subscribed Fat Trees
- routing仍然可保留direct，雖不會增加bandwidth tax，但會降低不同機櫃間end host的network capacity
Expander topologies
- 沒有in-network switch，封包必須在多個ToR之間hop才能抵達目的地，會增加bandwidth tax
Reconfigurable topologies
- 動態建立end-to-end的路徑

Opera由一層packet-switched ToR (leaf)以及一層reconfigurable circuit-switched (spine)組成
Expansion for short path
- Expander topology非常適合用在latency-sensitive的flow (小型flow)
- 有良好的fault-tolerance
Reconfigurability to avoid bandwidth tax
- reconfigurabe circuit switch能夠為任兩個機櫃提供direct one-hop path，適合用在bulk flow (大型flow)
- 每經過一個cycle time，每個ToR都會被連到其他的ToR

雖然分段進行reconfigure能保證continuous connectivity但不保證complete connectivity
Opera必須同時保證
- multi-hop path在任何時候都存在於各機櫃之間(即在任何時候都能透過multi-hop連到任一機櫃)
- direct path每隔一段時間都必須存在於任兩機櫃之間(即每隔一段時間A機櫃都有條direct path可連到B機櫃)

要產生$N$-rack的topo先將整個完整的graph隨機分成$N$個不相交的matching(如上面的Example，共有8個matching，同樣的in-port在每個matching中連到的out-port各不相同)
然後將這$N$個matching隨機分配給$u$個circuit switch，使每個circuit switch分配到$N/u$個matching
最後隨機分配每個cycle中switch改變matching的順序
這些動作都是在設計網路時(網路還沒上線運作)就已經做好，所以不會在網路上線後佔用時間去計算這些東西

因為有時要等direct path出現的時間可能是整個cycle的time，所以只讓特大的flow(大到可以平攤delay時間)走direct path，其餘走indirect path

須達成下列條件
- ToR們必須知道circuit switch何時reconfigure
- ToR們必須在circuit switch reconfigure時同時更新自己的forwarding table
- end host只能在知道ToR有direct connect到destination時送出bulk traffic(避免traffic把ToR的queue擠爆)
由於每個ToR的uplink都直接連到其中一台circuit switch，所以ToR可以透過偵測連在某個link上的transceiver的signal strength做到re-synchronize(?)
ToR也可利用IEEE 1588 (PTP)，該技術(或方法?)可以在1µs間synchronize switch
low-latency traffic可以直接送出流量，bulk traffic必須等相連的ToR進行輪詢(poll)才送出

每次新的circuit被configure後，ToR們都會互傳”hello” messages (包含他所知道的link錯誤訊息)，如果在一定時間內沒收到對方傳來的message就判定該條link有問題
最慢在2次cycle後所有ToR就能知道誰與誰之間的link有問題

在Opera中那些無法忍受”等待direct path出現”所需時間的traffic通通歸類為low-latency
所以low-latency與bulk traffic的分界線會取決於Opera的circuit switch多久會改變一次matching (cycle speed)
下列2個因素很大程度影響了cycle speed
- Circuit amortization
  - 可以將delay平攤增加成1-3ms的flow可視為bulk flow
- End-to-end delay
  - 如果有封包在傳輸途中遭遇到circuit topology剛好改變很可能導致封包進到loop或被傳到更遠的地方，但丟掉重傳又會造成極大delay
  - 設計一time period由end-to-end delay under worst-case queuing $\epsilon$加上reconfiguration delay $r$所組成，並稱其為”topology slice”，任何在slice期間發送的封包都不會經由circuit route