[SIGCOMM 2018] Sonata: Query-Driven Streaming Network Telemetry

Abstract

Sonata：一個具有expressiveness和scalability且能協調各節點分析網路流量的網路遙測系統
- expressiveness：能夠支援多樣化的query
Sonata可以動態精簡每個查詢(query)，以確保可用資源只會集中在滿足查詢的流量上

1 Introduction

現有的遙測系統要嘛只支援有限的遙測功能，要嘛就必須隨著流量和查詢的增加而跟著增加大量的處理和存儲成本
- 所以現有的遙測系統常在expressiveness和scalability之間進行取捨
  - 依賴stream processor的遙測系統通常具有expressiveness但不具scalaibility
  - 依賴programmable switch的遙測系統則與上者相反
此論文試圖結合兩者優點，因為兩者都使用了相似的處理方式：對pipeline中的structured data進行一連串有序的處理，使輸出只剩我們想看到的資料
Sonata做出了下列改變：
- Unified query interface
  - 設計一query interface來統一programmable switch和stream processor的parsing及compute capability
  - 讓network operators可以對任意的packet fields的組合apply dataflows operators (如map, reduce, filter等)
- Query partitioning based on data-plane constraints
  - 設計一演算法，由query planner決定將query分配給switch及stream processor
- Dynamic query refinement based on query and workload
  - 設計一動態精簡演算法來忽視大部分的流量，只注重在滿足query的的流量
- Modular and extensible software architecture
  - 可擴充以支援任意packet fields

2 Unified Query Interface

Sonata使用programmable switch來scale query execution，讓stream processor負責那些data-plane沒有足夠資源可處理或是switch無法處理的operation (如payload processing跟floating-point arthmetic)

2.1 Dataflow Queries on Tuples

Extensible tuple abstraction
- packet header原本就帶有許多key-value的tuples，這種結構很適合tuple-based abstraction
- 但operators也可能會下一些不是base on IP packet header的field的query，像是application protocol之類的
- 只要這些field能夠被switch或stream processor提取、解析出來，Sonata允許operators自行擴充tuple interface來包含這些field
Expressive dataflow operators
Limitations
- 無法支援需要reassembling a byte stream的query
- 目前只能將query compile到一個單一的switch，而非複數個switches

2.2 Example Network Telemetry Queries

3個example
- 第1個：整個query可以直接在data plane執行
- 第2個：需要join 2個sub-queries
- 第3個：需要parsing packet payloads
第1個例子－Computing aggregate statistics over a subset of traffic
- 欲偵測SYN flood attack，需檢查每個packet的TCP flag以及dest IP address，檢查dest IP address可以直接化為計算”到每個相同的dest IP address的總packet數”
- 此query可直接在switch上運行
第2個例子－Joining the results of two queries
- 欲偵測Slowloris attack，必須先篩選目前擁有許多TCP連線的機器，再從這些機器之中檢查這些TCP連線是不是都只占用很小的traffic
  - Slowloris attack：一種DoS，與攻擊目標建立許多TCP連線，每個連線為了確保不被關掉都會保持傳輸極小的TCP traffic，直到TCP連線多到攻擊目標不堪負荷
- 此query擁有2個sub-queries：
  - 計算unique connection的數量
  - 分別計算給每個機器傳送了多少byte
- 此query因牽涉join及除法，所以不可直接在switch上運行
- Sonata的query planner會將該query拆分，能給switch做的丟給switch做，比較複雜switch處理不來的丟給stream processor做
第3個例子－Processing packet payloads
- 欲偵測某個透過telnet連線進行傳播的malware，假設該malware的特點是當它成功login到機器中，它所執行的一連串shell command之中會包含一關鍵字”zorro”，則必須先檢查所有機器中走telnet protocol且大小相近的packet，將這些packet拆開檢查是否含有關鍵字”zorro”
- 此query擁有2個sub-queries：
  - 將收到大小相近的telnet packet且數量超過設定的threshold個數的機器挑出來
  - 將上個sub-query的結果join起來並從中挑出packet中含有”zorro”關鍵字的機器
- 此query因牽涉join及parsing packet payloads，所以不可直接在switch上運行
- Sonata的query planner會將該query拆分，能給switch做的丟給switch做，比較複雜switch處理不來的丟給stream processor做

3 Query Partitioning

3.1 Data Reduction on the Switch

Sonata的核心觀點之一便是利用programmable switches來降低stream processor的負擔
- 相較傳統switch，protocol-independent switch architecture (PISA) switch提供可程式化的parsing、可自訂的packet-processing pipeline等功能，都讓switch能處理更多query

3.1.1 Abstract Packet Processing Model

在PISA switch中會有一個可重複設定的parser對incoming packet建立一個packet header vector (PHV)
- PHV不只含有標準的packet header也可包含自定義的metadata
之後PHV會經過複數個固定數量的physical stages
- 每個stage裡面會有一個match-action unit (MAU)
- 每個stage裡面可能有多個match-action table (由MAU implement)
每當PHV裡面有field match到MAU裡的rule，則MAU會對該PHV執行一系列對應到該rule的action
- 這些action可以是stateful或stateless，stateful會利用register memory來保存state
最後由deparser將修改後的PHV組合回packet裡再送到output port

3.1.2 Compiling Each Operator

要編譯dataflow queries到PISA switch中需要將dataflow operator形式的DAG轉為match-action形式的DAG
Sonata的query planner會將所有input queries劃分成一組可在switch上執行跟一組一定要在stream processor上執行的dataflow operator
以下是一些可轉換成在switch上執行的dataflow operator
- Filter
- Map
- Reduce
- Distinct
- Join

3.1.3 Compiling Dataflow Queries

data-plane mapping必須滿足以下條件
- Preserving packet forwarding decisions
  - Switch只會另存原本packet的header fields到metadata fields，然後再對那些metadata做操作而不會改變原本的packet內容
- Reporting intermediate results to the stream processor
  - switch會在每個packet的metadata中多加一個只有1-bit叫report的欄位
  - 當query有將packet送給stream processor的需求時就會mark report欄位
  - 當整個pipeline結束時這個欄位是1，switch就會馬上把intermediate result送給stream processor
- Detecting and mitigating hash collision
  - 偵測collision
    - switch會在執行stateful (需要存資料到switch register)的操作前(像是reduce、distinct)將原本的key(？)存下來
  - 減少collision
    - switch會開許多register給stateful operation，每個register有多個entries，每個register也使用不同的hash function
    - 把要store的key丟去給某register的hash function後如果發現有collision，就找下一個register
    - 若有register都找過一遍，仍有collision，該packet會直接送給stream processor處理

3.2 Data-Plane Resource Constraints

PISA switch有resource上的限制，這是Sonata的query planner必須考慮到的事情
以下是一些會需要考慮resource限制的狀況
- Parser
  - 當每個packet需要提取的欄位增多，parse的cost就會增加
  - 這個cost可以透過需要extract多少bit跟parsing tree的深度來量化
- Actions
  - 多數的stream processor可以平行地執行複數個query
  - PISA switch則是將packet轉換為PHV後再將PHV送到pipelined stage裡對一個PHV同時進行一堆操作
  - 這也表示了PISA switch其實也可以平行地執行複數個query
  - 但是一個stage中能對query執行的action數量有限，這也限制了query能被執行的數量
- Registers
  - 當packet跟query數量越來越多，stateful operation所需的memory也會跟著增加
  - 在PISA switch中stateful operation只能access physical stage中available的register memory
  - 每個stage的register memory也是有限的
- Stages
  - 在給定的stage中若沒有足夠的資源可執行query，則該query必須送到後面(？)的stage執行

3.3 Computing Query Partitioning Plans

大概在講說Sonata的query planner會試圖解一個由integer linear program組成的公式來最小化要送到stream processor的packet數量
會使用歷史trace過的packet當”training data”，來計算每個register需要開多少entry、需要總共多少個register

對某些query或workload來說，將部分的dataflow operator交給switch來做並不能降低多少stream processor的workload
在上述情況下，Sonata會動態地refine input queries

Identifying refinement keys
- 由一個具有hierarchical structure的欄位組成，並作為stateful operation的key
- 之所以要用有hierarchical structure的欄位是因為可以分成不同精細度
- 例如IP：netmask為255.0.0.0(/8)的精細度較不精確(粒度較粗)，netmask為255.255.0.0(/16)的精細度較精確(粒度較細)
- 例如domain name：越接近根域名(.)的精細度越不精確(粒度較粗)，越接近完整域名(www.nctu.edu.tw.)的精細度越精確(粒度較細)
Enumerating refinement levels
- 決定剛剛找的key的refinement levels $R={r_1, r_2, \dots, r_n}$，$r_1$顆粒最粗
Augmenting input queries
- 以fig4為例，Sonata先篩出dIP/8中超過threshold的packet，再從這些packet中篩出dIP/16超過threshold的packet
- 這樣可以降低每個query中所需的resource避免將過多query送給stream processor導致stream processor loading過重
- 但是這方法會導致需要計算較多次的sum，會有額外的delay