[SIGCOMM 2020] OmniMon: Re-architecting Network Telemetry with Resource Efficiency and Full Accuracy

Abstract

現有的network telemetry技術通常會需要在resource efficiency和full accuracy之間做取捨
OmniMon試圖讓end-host、switch、controller之間合作來達成flow-level的network telemetry並同時保證resource efficiency和full accuracy

1 Introduction

network telemetry的性能開銷必須遠小於正常封包在routing、NAT、firewall做處理時所需資源(即network telemetry所佔資源不可影響正常封包之處理)
達成resource efficiency並不表示當network scale變大時資源使用量不變，而是不管scale變大變小都要確保資源的開銷遠小於正常的network operation
per-flow monitoring (如Trumpet、Cisco Tetration)通常可以達到error-free的測量，但是可能會使用過多的資源
coarse-grained monitoring (如SNMP、sFlow、NetFlow)則與前者完全相反
許多telemetry system會盡量避免上述兩個極端，而在之中取得平衡，像是
- 使用設計過的合適的algorithm在達成high resource efficiency的同時保證只有一定量的error
- 採用event matching的技術只focus在自己感興趣的traffic
OmniMon為了解決以上困境，提出重新設計network entities之間的合作關係，期望可以兼具resource efficiency跟accuracy
- 近期也有人提出重新設計所有network entity之間的合作關係來改善現有network中的一些缺點，但他們重點並不放在改善resource-accuracy之間的關係，而是放在像是in-network visibility這樣的領域上
OmniMon採用split-and-merge的方式來做到re-architect network telemetry
- split：OmniMon將network telemetry分解為部分操作，並將這些分解開的操作安排給不同entity
- merge：OmniMon協調所有entity以協作執行部分操作
OmniMon包含兩個可靠性保證：consistency、accountability
- consistency：提出了一種具有network-wide epoch同步機制的混合模型
- accountability：針對每個switch、每個flow的丟包推斷制定了一個線性方程組，並通過考慮數據中心網絡的特性來確保在常見情況下存在唯一解

2 Background and Motivation

2.1 Resource and Accuracy Requirements

通過封包的某些欄位之組合而成的flowkey (這邊的key是指鍵值)來識別flow
在每個epoch (固定時間長度)之間以value的形式測量flow-level的統計訊息
resource efficiency：因為OmniMon是專門設計給data-center-scale的系統，所以預期有多個end-host、switch、controller，這些entity必須滿足相應的資源限制，以維持整體封包的轉發性能
- end-host：使用軟體(kernel & user space)在network-edge做運算，擁有足夠的memory，以及可適應多種不同的telemetry方法，但缺少in-network visibility
- switch：high forwarding throughput、low processing latency，但是memory不多而且programmability有限
- controller：擁有global network view，可由多台server組合而成以擴充其CPU及memory資源，但network bandwidth有限
full accuracy：保證completeness和correctness，completeness是指在每個epoch中所有entity的traffic (flow)要能被追蹤；correctness指的是無誤地追蹤每個flow中的flowkey和value
- performance evaluation：嘗試各種telemetry方法並自行衡量correctness跟performance
- anomaly detection：需要所有traffic的per-epoch的統計資料才能保證對anomaly行為即時反應
- network diagnosis：像是sudden high packet loss之類的performance degradation的現象常見於實際環境，原因可能是系統設定有誤亦或是硬體出現故障，這需要per-switch和per-flow的統計資料才能定位及修復問題

2.2 Motivation

動機1：flow tracking跟resource management的緊密關係
- 現有的telemetry方法通常是只交給end-host或switch其中一方去做
  - 交給end-host雖然memory夠，但throughput可能不夠快且缺少in-network visibility
  - 交給switch雖然有high forwarding throughput、low processing latency，但是memory可能不夠
- 要能做到追蹤所有flow要花上不少memory
- 若要降低所佔用的memory勢必會有一些flow無法追蹤從而犧牲一些accuracy
動機2：network-wide合作有限
- 雖說現有的一些方法提供了switch&controller或switch&end-host之間的合作，但無法保證full accuracy
- 有些entity的資源有限，造成full accuracy的破口

3 OmniMon Design

3.1 Design Overview

要讓不同類型的entiity合作並不容易，因為他們之間的可用資源及in-network visibility都不一樣
為了達成entity之間的合作，團隊認為必須回答下列3個問題
- 對於所有不同的entity，要如何分派或指定telemetry operation給他們？
- 不同entity之間該如何協調？
- 當遇到不可靠的event發生時，如何達成可靠的協調？
- (以上為開放式問題，論文並未在該章節回答這些問題)
團隊假設採用OmniMon的系統擁有以下特性
- admin對於所有entity都有apply configs的權限
- controller知道每個封包的processing policy (如routing table、ACL等)
- 只考慮實際會進入network的封包，像是會被end-host drop掉的封包就不列入考量，因為這會牽扯到end host的network stack，但這並非本論文所要探討的
- 封包格式是可以擴充的，傳輸中可以在封包的unused field嵌入新的資訊

3.2 Split-and-Merge Telemetry

OmniMon主要有4個operation
- Flowkey tracking
  - OmniMon會記錄下network中所有active flow
  - 當一個新的flow被建立，OmniMon會在每個作為source的end-host中開一個hash table來記錄flowkey，並在flow結束時從table中刪除
  - flow的結束是利用TCP的FIN/RST以及過長的idle time (如30min)來決定
- Value updates
  - end-host跟switch都必須維護多個slot，每個slot擁有多個counter，並根據epoch對slot進行分組
  - end-host因為較多memory，所以可以對每個flow開一個專用的slot，且針對incoming跟outgoing的封包分別開設ingress及egress slots
  - switch因memory有限，所以多個flow會共用一個slot，每個slot的counter是由多個flow的value所組合的，之後在collective analysis進行還原
- Flow mapping
  - In end-host
    - 使用一個叫host index的欄位紀錄flow跟slot之間的mapping
    - 當source end-host要用flowkey追蹤新的flow時(他會先計算出host index，表示flowkey在hash table中的entry point)，然後把host index跟該flow的egress slot做關聯
    - 將host index跟epoch資訊包進封包後才送出
    - destination end-host收到封包後會提取host index跟epoch資訊，並將他們與ingress slot關聯
  - In switch
    - 使用一個叫switch index的欄位紀錄flow跟slot之間的mapping
    - switch index是由controller跟source end-host合作產生的
    - 具體作法是controller為每個可能mapping到switch的slot的flow分配唯一的switch index，然後給每個end-host預先分配一些不相交的switch index
    - source end-host要建新flow時就會從預先分配到的switch index中選一個switch index並連同epoch資訊包進封包後才送出
    - 這樣的作法不但利用了controller對network的宏觀減輕了switch slot中的hash collision，也讓end-host可以快速選擇switch slot而不用每次都先問過controller
- Collective analysis
  - 對於每個epoch，controller都會從end-host和switch收集hash table (flowkey)跟slot (value)的資料
  - flowkey被存在source end-host的hash table，所以直接拿到flowkey後就可以做為host index從slot中獲得per-flow value
  - 至於switch上的per-flow value，則要透過end-host那邊拿到的flowkey跟value才能還原
    - 如果沒有packet loss，switch中的slot就是所有對應到該slot的flow的集合體(例如在slot中所存的value可能是per-flow value的總和)
    - 如果有packet loss則要透過packet loss inference來還原

3.3 Consistency and Accountability

Consistency：在沒有global clock的情況下，OmniMon必須讓所有entity處於相同的epoch，才能保證per-epoch的application的正確性；另外，在傳輸過程中也必須讓每個封包的始終在同個epoch被monitor，才能保證collective analysis能正確關聯per-flow value
Accountability：發生packet loss時，OmniMon要能正確推論出per-switch、per-flow的packet loss，這對network diagnosis很重要

4 Consistency

4.1 Challenge

目前現有的方法有分為strong consistency跟weak consistency，但都不適合OmniMon，原因以下會說
- Strong consistency：此方法會強制所有entity對齊他們每個epoch的boundary。雖可以保證每個entity同一時間都會處於同個epoch，但是要在switch上實現過於複雜，而且為了同步常需要傳送額外封包
- Weak consistency：此方法透過每個entity的local clock以及封包內容來更新epoch，詳細做法為平時由local clock更新epoch，但當有封包的epoch比自己的epoch新的時候立即更新自己的epoch，反之，當自己的epoch比封包的夾帶的新的時候會主動改寫封包的epoch。此方法會導致封包在上個entity可能還屬於epoch 1但跑到下個entity時就變成epoch 2

4.2 Hybrid Consistency

OmniMon採用hybrid方式，大部分時候是strong consistency，只有偶爾會有短暫的時間切到weak consistency
Design overview
- 主要還是靠每個end-host的local clock更新自己的epoch
- 每個封包也會記錄自己處於哪個epoch，當end-host發現該封包夾帶的epoch比自己還新的時候就會立即更新自己的epoch
- 另外，當end-host因local clock而更新自己的epoch時，它會傳送通知給controller，controller也會透過out-of-band message告訴所有end-host要更新epoch
- 這樣一來，雖然像上圖那樣epoch改朝換代時host之間還是可能會有短暫的不同步，但這個time difference大概是2倍的controller&end-host之間的路徑時間，可以保證非常短
- 即便再短都有可能像上圖那樣發生封包C從h1傳到h2時已經換成新的epoch了，但是與weak consistency不同的是h2不會改寫封包C夾帶的epoch，這樣就能保證封包C在h1、h2都是被算在epoch 1內
Algorithm

Distributed controller
- 當scale越來越大，可能會需要複數個controller，每個controller都下轄一些end-host，這時會找一台controller當root其他controller為leaf
- 當end-host透過local clock更新epoch，會先通知負責它自己的leaf controller，然後leaf controller再通知root controller，root controller收到後廣播給所有leaf controller，最後所有leaf controller會通知所有自己所負責的end-host

5 Accountability

OmniMon所使用的loss inference跟傳統的network tomography有關
但是後者因為受限於in-network visibility，所以通常只專注於解決end-host端的packet loss，而且也只專注在最小化accuracy loss
與傳統方式不同的是，OmniMon擁有network-wide的視野且瞄準的是達到full accuracy

5.1 Problem

已知
- $n$：lossy flow的數量($f_1,\cdots,f_n$)
- $m$：switch的數量($s_1,\cdots,s_m$)
- $k_t$：lossy flow map到switch $s_t$的slot的數量
未知
- $x_i$：per-switch且per-flow的packet loss數量
  - $x_1,\cdots,x_n$是$f_1,\cdots,f_n$在$s_1$的packet loss
方程式
- 如上圖之linear equation
- 以矩陣表達的話為$A\cdot \vec x=\vec b$，其中
  - $A=\begin{bmatrix}M_1&0&\cdots&0\0&M_2&\cdots&0\\vdots&\vdots&\ddots&\vdots\0&0&\cdots&M_m\I&I&\cdots&I\end{bmatrix}$
    - if $f_j(1\le j\le n)$有經過$s_t$且map到$s_t$的slot $i$，$M_t(i,j)=1$，else $M_t(i,j)=0$
  - $\vec x=\begin{bmatrix}x_1\x_2\\vdots\x_{mn}\end{bmatrix}$
問題
- 不幸的是，僅依照上面的方程式找解有可能找到多重解而非唯一解

5.2 Collaborative Flow Mapping

Traffic locality
- 現今的data center會採用strong traffic locality，盡量讓flow在1個機櫃內或1個叢集內跑，這樣一來lossy flow只會經過少數的switch，如此一來就能將$\vec x$裡面的很多variable設成0
Loss sparsity
- 在整個data center中，packet loss的發生其實很稀疏，這歸功於近期的congestion control和failure mitigation mechanism大量抑制了packet loss的發生
- 在1個local region中packet loss可能只會發生在1個switch中，這樣也有助於我們對local lossy flow推測其$\vec x$裡面的variable
盡可能提高matrix $A$的rank
- 例如：將1個flow map到同一個switch中2個以上(含)的slot

上篇[SIGCOMM 2020] BeauCoup: Answering Many Network Traffic Queries, One Memory Update at a Time

下篇[SIGCOMM 2020] MasQ: RDMA for Virtual Private Cloud