剖析网络测量：Counting and Measuring Network Traffic
全文共18000字，講解了網絡測量和計數中的多方面知識：網絡測量的意義、網絡測量的手段分類、網絡測量在實現上的挑戰、以及解決這些挑戰所用到的技術和協同方案等等。
參考書籍有：《Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices (2nd Edition)》
本博文首發于博客園：https://www.cnblogs.com/grapefruit-cat/
本文作者：grapefruit-cat ，轉載需在文章頭部標明出處。
1 前言
在現實中要對某些任務做出優化，必定要先進行一定的測量。只有進行了對性能的測量量化，你才能知道任務的瓶頸在哪，才能對相應執行位置做出好的優化。不要在未做測量的情況下帶著主觀臆斷去做優化！！
Premature optimization is the root of all evil. ——D. E. Knuth.
這個原則在計算機網絡里面同樣適用。對一個特定網絡的流量使用軟件或者硬件工具進行測量，不僅可以描述這個網絡的特征，而且可以在測試出網絡的運行狀態，如在流量不穩定或者流量過多時采取相應的優化措施，從而更好地設計網絡。
2 為什么需要網絡測量？
從架構視角上看，網絡測量可以描述出當前網絡的流量狀態，可以得到當前網絡的拓撲信息和性能信息，還可以對一個具體的協議的運行結果進行觀測，這就使得當一個新的想法出現時，可以將網絡測量當成一種實驗的手段，來摸索出新想法的性能表現。
而從提供服務的視角來看，網絡測量可以根據測量出的流量特征（如用了什么類型的流量、用了多少）向客戶計費；可以檢查網絡的QoS并觀測診斷解決存在的問題；可以為以后增添升級設備做好開銷預算。
舉一個例子，在服務提供商網絡中，數據包計數和流量日志記錄為以下任務的優化提供了數據支撐：
- 容量規劃（Capacity Planning）: 互聯網服務提供商(ISP)需要確定流量矩陣，即他們所連接的所有源子網和目的子網之間的流量信息。這些得到的信息可以在短時間尺度(例如，幾個小時)內使用，通過重新配置光交換機（optical switches）來執行流量工程（traffic engineering）;它也可以用于較長的時間尺度(例如，幾個月)來升級鏈路容量。
- 計費工作（Accounting）：ISP與客戶和對等體（peer）之間實現了復雜的服務水平協議(service level agreements，SLAS)。基于總體流量（即單純的傳輸數據量）的簡單計費可以由單個計數器輕松監控得出；然而，更復雜的基于流量類型的協議需要給每個流量類型安排一個計數器，這樣才能根據流量類型來進行分級計費。數據包計數器也可以用在ISP之間的互聯對等關系上。假設ISP-A目前正在通過ISP-B向ISP-C發送數據包，并且正在考慮與B直接連接(對等互聯)，那么A進行計費的合理方法是統計到達B對應網絡前綴的流量。（ISP-C 并沒有直接參與到對等互聯關系中，而僅僅是通過 ISP-B 來間接地與 ISP-A 通信。因此，針對ISP-C 的流量并不會作為對等互聯計費的一部分。）
- 流量分析（Traffic Analysis）：網絡的管理者們通常需要時刻留意著不同種類流量的表現。例如測量到點對點流量激增，就需要對其做出一定的速率限制；再例如ICMP消息類型的流量激增意味著有可能發生了Smurf攻擊。
3 網絡測量的分類
從測量目標去分類，可以把網絡測量分為以下三類：
-
端到端性能測量：通過主動測量方式來測量網絡中各個節點之間的性能指標，如網頁下載的平均時間、TCP批量吞吐量等。
-
狀態測量：主要集中在對網絡拓撲、配置、路由等的測量，如當前活躍的路由、活躍的拓撲部分、鏈路的誤碼率等。
-
流量測量：主要集中在對數據包和數據流的測量，以及對鏈路的統計信息，如鏈路使用率、流量矩陣、需求矩陣等。
從測量方式去分類，可以劃分為主動測量和被動測量兩大類。定義上，主動測量方式通過向目標鏈路或目標節點主動發送數據包，來測量鏈路或端到端的延遲、帶寬和丟包率等網絡性能參數，這種方式比較精確但往往會對網絡性能總體產生影響；而被動測量方式通過接入網絡的測量探針被動地嗅探網絡流量，通過記錄和統計網絡鏈路或節點上業務流量的信息來分析網絡性能。兩種測量都可以在控制平面和數據平面上運行，在同一類平面上兩種測量得到的結果種類均相同，即在控制平面上可以得到網絡的拓撲、配置以及路由信息，在數據平面上可以得到端到端性能信息、鏈路統計信息以及數據包和數據流的特征信息。
從測量對象來分類可以分為數據包測量和數據流測量。
下面將從兩種測量對象出發作闡述。
4 包測量
包測量是一種被動測量方式，通過被動地在一或多個鏈路上收集數據包，記錄包中各層的路徑信息。它的測量范圍主要集中在記錄用戶行為的細粒度信息，被動地監測網絡基礎設施的運行，描述當前流量特征和診斷相關問題。下圖描述了包測量的中心監測器測量鏈路時，在不同的網絡拓撲中所處的測量位置：
4.1 測量獲得的元數據
包測量在開始時需要根據我們測量的需求，對測量的流量進行元數據提取——而不是對單個包包含的所有信息都進行提取分析。我們需要根據一定的標準對數據包進行不同方面的測量分析，具體的分析標準可舉例如下：
- 對數據包的IP做特定分析，如需要測量某個特定站點來的流量時，需要區分出特定的IP或IP前綴；
- 對數據包的運行協議做特定分析，如區分為TCP、UDP或ICMP包；
- 對數據包的端口號做特定分析，某些特定的端口上運行著特定的協議，如HTTP、DNS、BGP等。
對于如何拿到這些元數據信息，我們可以通過接收數據包時截取頭部字段的字節來完成這份工作，這頭部的前n個字節往往能夠實現對數據包種類的區分。以下展示了一些不同協議的頭部字段字節范圍：
| 頭部種類 | 字節長度 |
|---|---|
| Ethernet MAC | 14 |
| IP header | 20或36(IPv6) |
| IP+UDP | 28或44 |
| IP+TCP | 40或56 |
| 應用層信息 | 整個數據包（應用層頭部+overload） |
在對數據包頭部包含的信息做分析提取元數據時，不同協議類型的頭部字段分析的重點也不同。
對于IP頭部信息的測量，對源地址和目標地址的測量可以獲取哪一個服務器或哪一個站點在當前是流量較高、熱門的；對兩個特定地址之間吞吐量的測量可以對性能問題進行檢測和診斷；對途經路由器的數據包時延分布情況的測量，可以識別出典型的延遲和異常情況；測量大小字段可以獲取數據包大小的流向分布情況，可以得到路由器工作負載模型；如果測量出鏈路上某些特定方向的流量激增，那么就可以將該信息用于重新分配鏈路容量和重新配置處理隊列。
而在TCP頭部信息中，源端口和目的端口的測量記錄可以推斷出當前熱門的應用；對TCP序列號或ACK編號以及數據包時間戳的測量可以得到當前傳輸中無序或丟失的數據包有哪些，可以得到丟包率、吞吐量和延遲信息；對每個TCP連接的傳輸的數據包數或字節數的測量可以得到批量傳輸的頻率；對來自客戶端的SYN數據包測量，則可以知道當前失敗的請求數量，以及可以檢測出是否存在Dos攻擊；對來自客戶端的FIN或RST數據包，可以得到由客戶端中止的Web傳輸的頻率，以及推斷出相關應用程序的行為。
而在應用層信息的測量中需要對整個數據包內容分析，對不同的應用層頭部，如HTTP請求和響應報頭、SMTP命令和響應信息、DNS查詢和響應信息、OSPF/BGP消息等，可以做不同的測量；而對應用層overload的測量主要集中在附帶信息上，如請求的HTTP資源有什么，RPC中的key-value cache操作有哪些，RPC中的pub-sub消息分布等。但要注意的是這些測量在當下加密通信中變得越來越困難。
5 流測量
與包測量以單個數據包為監測單位不同，流測量以”屬于同一組“數據包為單位，多個同一組的數據包被劃分到一個數據流中去測量。
對”屬于同一組“的劃分標準，同樣可以使用數據包中的頭部字段信息。與包測量的流量選取相似，我們可以根據源地址和目的地址、源端口和目的端口、運行協議類型、ToS種類等進行劃分。除了數據包本身附帶的信息，我們還可以使用路由器上數據包的出入端口信息來進行流劃分。另外，數據包還需要根據時間進行劃分。同一組的數據包即同一個數據流在時間尺度上不能距離太遠，即使是在信息上劃分為同一組的數據包，也可能因為時間上的相差而劃分到不同的數據流中。
5.1 為什么做數據流的抽象？
數據流劃分的意義在于讓測量的對象更加接近于“應用程序級別“的交互單元，采用數據流作為測量的基本單位可以更好地反映應用程序的實際行為和需求。
與數據包相比，數據流可以更好地描述應用程序的交互過程。例如，在視頻流媒體應用中，一個數據流可能由多個數據包組成，這些數據包共同構成了一個連續的視頻幀或音頻樣本。如果僅考慮單個數據包，則無法完整地描述視頻或音頻流的特征。
此外，數據流也反映了應用程序之間的交互關系。例如，一個Web頁面可以由多個HTTP請求和響應數據流構成，并且這些數據流在應用程序之間的交互中扮演著重要角色。通過對數據流進行分析和測量，我們可以更好地理解應用程序之間的交互方式并評估網絡性能。
此外，以數據流為測量單位還可以針對轉發或訪問控制對路由器進行優化。如采用IP-over-ATM技術的流交換范式可以利用其緩存結果對路由器進行轉發或訪問控制決策上的優化，再如Netflow技術可以聚合通過路由器的流量信息。
5.2 測量獲得的元數據
我們從流測量提取元數據的過程展開論述。首先流測量要對接收到的數據包做一定的劃分，如上面所述，劃分可以依靠讀取數據包頭部字段信息來完成，主要讀取的信息有源地址和目標地址、端口號、其他 IP 和 TCP/UDP 標頭字段（如協議字段、ToS字段等）。劃分出數據包子集（準數據流）后，便對整個子集的一些信息做一定的聚合，生成流記錄信息，如準數據流的開始和結束時間（第一個和最后一個數據包的時間），流中的總字節數和數據包數量，TCP 標志位序列信息等，這種對整個流的數據特征測量可以幫助我們分析網絡流量趨勢和周期性變化，以及預測未來流量的可能方向。
除了數據流中來自數據包“自身”的信息以外，還需要測量該數據流的路由信息。常見的路由信息有數據包在路由器交換結構中的轉發方向，即數據包的出入端口；還需要記錄其源子網和目的子網的信息，這個可以通過記錄源和目的IP地址前綴來實現。
流測量獲取的信息和包測量有一些異同之處。在基本信息的獲取上面，它們兩者都可以計算收到數據包的平均大小，可以獲取不同IP地址、端口號、協議的混合的流量信息，但在按時間尺度測量流量方面，除了兩者都能完成的中長期時間尺度上測量之外，包測量還可以測量出短期時間尺度上網絡流量的突發激增。另外在運輸層的測量上，兩者都能測量出特定連接中傳輸的總數據量大小，但包測量因其以單個包做測量的特性，能夠測量出數據傳輸中的亂序率或丟包率。
5.3 流測量的底層實現
5.3.1 在何處生成流記錄？
流測量生成流記錄的過程在哪里實現是一個需要多方考慮的問題。如果由路由器中的CPU負責流記錄生成，那么就有可能影響到路由器的路由性能；如果由路由器端口處的線卡負責生成，雖然能夠更有效地支持測量，但線卡的適用性和可擴展性受制于其設備兼容性，需要額外的部署和維護成本；除了CPU和線卡，我們還可以利用在數據流途徑路由上的數據包監視器來生成流記錄。
我們來看一些流測量的底層支持機制。
5.3.2 硬件機制 Flow Cache
Flow Cache是一種基于硬件的緩存機制，可以在網絡節點上緩存每個數據流的元數據，例如源 IP 地址、目標 IP 地址、端口號、協議類型、數據包數量等。這些元數據可以用于識別特定類型的數據流，如視頻、音頻、文件傳輸等等，并確定它們在網絡中的來源和目的地。同時， Flow Cache 還可以記錄數據流的持續時間、流量大小和延遲等流特征。
Flow Cache的固件可以使用TCAM或SRAM等方式來實現，而緩存操作依賴于Flow Cache中的控制器（Flow Cache Controller ）來實現。Flow Cache Controller 是一個獨立的組件，它負責管理整個 Flow Cache 的生命周期，包括緩存的創建、維護和刪除等操作。
當一個新的數據包到來時，Flow Cache Controller會根據源和目的地以及端口號三者計算出一個鍵值（key），并將其作為創建或更新緩存中流條目（entry）的依據—— Flow Cache Controller會檢查該 Flow 是否已經存在于緩存中，并根據配置的緩存規則判斷是否需要緩存該 Flow。如果需要緩存，則會計算出該 Flow 的元數據存儲位置并將其存儲到緩存中。圖示為Controller 計算鍵值和索引到緩存條目。
在計算元數據存儲位置時，Flow Cache Controller 會考慮多種因素，如存儲設備的容量、負載均衡、數據安全性等因素，以保證緩存的高效性和可靠性。同時，它還會監控緩存的使用情況，自動調整緩存策略和存儲位置，以最大化緩存的利用率和效果。
當Flow Cache條目達到一些條件如超時、映射沖突的時候，就需要對條目進行刪除或替換。超時是指緩存中的數據流條目在一段時間內沒有被訪問。Flow Cache Controller 會對數據進行周期性排序，對于超時的數據流，即最近未接收到數據包的流，會被Controller自動清除。當緩存被填滿時，Controller會根據一定的算法，如LRU、隨機選擇等，去用新的條目替換掉算法計算映射到的舊條目。
5.4 流測量的開銷
流測量的開銷主要集中在兩個方面：對每個數據包的處理和對每個數據流的處理。
對數據包的處理開銷主要集中在Controller計算鍵值和索引到緩存條目上。在數據流中如果數據包的平均大小較小，那么測量處理的速度就可能會跟不上當前鏈路的傳輸速率——當存在許多大小較小的數據包時，測量就必須捕獲和分析更多數量的數據包才能獲取與大數據包相同的信息量，這會增加處理開銷，對存儲的要求也更高（要求讀寫更快），從而影響測量的性能。
對數據流的處理開銷則主要集中在Controller創建和替換條目上。這主要由數據流的多少來決定。如果數據流中包含的數據包數量較少，那么總體上的流數量就會較大，接收分析數據流的工作量就會加大，這同樣影響測量的性能。
6 網絡測量的挑戰性
你可能會認為測量工作是一件非常平凡且簡單的事情——即使它很必要。但是對于高速運轉的網絡來說，網絡流量測量是一個很困難的問題。
6.1 為什么測量很困難？
首先我們要知道，網絡協議提供的信息有時候并不完全符合我們作為用戶的需求，例如traceroute工具記錄路由路線，它是依賴于數據包的TTL來鑒別路由信息的——而TTL的本意是告訴網絡路由器該數據包在網絡中的時間是否太長而應被丟棄。顯然，數據包承載的信息并沒有明確告訴我們該包的路由信息，我們不得不通過其它的手段來獲得我們想要的信息。對于網絡測量也是如此，網絡并沒有給我們直接提供明確的測量特征，但我們可以用對不同種類數據包計數的方式去巧妙地獲得流量測量信息。
然而，數據包計數并不簡單。要想做到精確的網絡流量測量，需要精妙的計數器。傳統路由器只提供運行SNMP協議的接口計數器，這類計數器很容易物理上實現——由于一個路由器接口僅僅只有幾個計數器（如字節計數器、錯誤計數器等），如此少的數量可以很輕松地用芯片的寄存器來做到。但傳統的計數器只能用于很粗糙的計費（accounting）計算，無法做到按流量類型計算的計費，如對收費更高的實時流量的區分，以及對途徑不同等級的ISP的區分。所以我們需要精妙的具有過濾功能的計數器。
舉一個例子，我們可以通過簡單的辨認網絡地址前綴的方式來實現過濾計數，但物理上支持基于前綴的計數會有不少的開銷：
- 考慮到即使是當前的路由器也支持500000個前綴，未來的路由器可能達到1000000個前綴，那么一個路由器就需要支持上百萬個實時計數器；
- 每個數據包在路由時都要被不同的計數器進行信息記錄，一個數據包可能對應多個流和多個前綴；
- 隨著鏈路速率不斷上升，如從最初以太網標準的10Mbps升至現在的400 Gbps以太網標準，如此高的數據包接收速率意味著計數器的讀寫速度也要相應提高；
- 計數器的高讀寫速度意味著達到計數值溢出的時間將變得更短，需要將32位寬度的計數器升級為64位。
要保證高速讀寫，計數器的存儲介質就需要使用昂貴的SRAM或TCAM；但單單對于這一種支持前綴計數的計數器來說，一百萬個64位計數器就意味著要使用64Mbit的內存，這代價是不可接受的。所以在當下的主要問題就集中在如何保證計數器高速運行的同時減少計數器的處理量以及所需要的存儲開銷。
下面我們來介紹一些對這類問題的優化方法，主要從減少存儲開銷和減少處理量兩方面展開。
6.2 減少存儲開銷
6.2.1 DRAM Backing Storage
我們先集中討論數據包計數的具體問題。實現數據包計數存儲的最簡單方法下圖所示。圖示中有100萬個基于目的地前綴進行區分的64位計數器，每一個都使用SRAM來實現，當數據包到達時，相應的計數器將值遞增。
整整64Mbit的SRAM！如此大容量的SRAM非常昂貴的。我們不禁想到，真的有必要使用如此大容量而昂貴的介質去做計數嗎？能不能使用DRAM替代SRAM？但如果有一個數據包每8ns到達一次，我們就必須通過SRAM計數器來處理這個數據包，而不能使用DRAM——因為DRAM延遲高達40ns。顯然SRAM在處理需要快速響應的任務時的速度是DRAM遠遠比不上的，然而從直覺上來說，使用完整的64位SRAM是一種顯而易見的浪費。
但我們往往可以通過快慢結合的方式來解決這種矛盾的問題。DRAM和SRAM的最佳硬件特性可以結合起來使用，在價格上，DRAM至少比SRAM便宜四倍甚至十倍，但在速度上，DRAM速度較慢。這與計算機中的內存層次結構非常類似（Cache-內存-硬盤 結構）。這種類比表明，DRAM和SRAM可以組合使用，提供既廉價又快速的解決方案。我們可以使用DRAM作為SRAM的備份存儲器（Backing Storage）。
觀察一下，如果路由器為N個計數器的每個計數器都配置一個64位的DRAM，并再分配一個較小的寬度（例如12位）的SRAM，那么只要每個SRAM計數器在溢出之前能夠將自身的值刷新到DRAM，那么計數就是準確的。這會大大減少SRAM的使用開銷！該方案上圖所示。然而，這需要一個好的算法來決定何時以及如何刷新SRAM計數器。
假設計數器允許每經k次SRAM訪問就刷新一次到DRAM。那么我們需要選擇足夠大的k，使得k次的SRAM訪問時間對應1次DRAM訪問時間。也就是說，k是DRAM訪問速度與SRAM訪問速度的比值。那么如何決定所需的最小SRAM寬度呢？D.Shah等人在論文Maintaining statistics counters in router line cards中指出，在“pick-a-counter-to-flush”的算法框架下，“條件最優”的計數器刷新管理算法，是每次刷新都應選擇刷新當前數值最大的SRAM計數器。通過這種算法，SRAM計數器的寬度c可以明顯小于DRAM計數器的寬度M，準確來說有以下的量化關系：
\[2^c \approx \frac{log{\ k(N-1)}}{log\ {(k/k-1})} \]其中N為計數器數量，k為計數器SRAM刷新頻率，c為SRAM寬度。
注意到當k值較大時，分母的影響可以被忽略，那么\(c\)的值就與\(log (log\ kN)\)掛鉤。舉一個例子，當數據到達速率為每8ns到達一次時，對于一百萬級別的N，在3個64位的DRAM的幫助下，僅僅需要空間消耗為8 Mbit、訪問速度為2.5μs的SRAM，DRAM的訪問速度也只需要達到51.2μs。此時k的值為\(51.2/2.5\approx21\)。如果不使用DRAM，也就是用最笨的辦法來實現SRAM計數器，那么就需要使用高達192Mbit的SRAM！
但是還有一個問題需要解決：如何找出當前計數值最大的SRAM計數器。在2000年Bhagwan和Lin描述了一種流水線堆結構的實現，該結構可以在硬件復雜性和空間上以相當高的代價確定最大的值。它們的堆結構需要每個計數器的配置一個大小高達\(log_2N\)的指針，用以識別當前需要刷新的計數器。在N高達百萬的量級下，這種指針反而會破壞我們將所需的SRAM位數從64減少到10的整體目標。
每個堆值都配置一個指針，這似乎很難避免。一方面，計數器必須位于固定的位置，以便在數據包到達時進行更新，但堆中的值必須不斷移動以維護堆屬性。另一方面，當最大值到達堆的頂部時，必須將其與計數器索引相關聯，以便將索引對應計數器SRAM刷新到DRAM中。還要注意的是，堆中所有值的存儲，包括指針和值，都必須在存儲在SRAM中以提高訪問速度。Ramabhadran和Varghese在2003年提出的一種LR算法優化了這個問題（Efficient implementation of a statistics counter architecture），它可以達到相同的SRAM計數器寬度，并使用位圖去維護所有高于刷新頻數k的計數器。
從表面上看，整個方法與通常使用的內存層次結構類似，其中較快的SRAM充當較慢的DRAM的緩存。然而，與傳統的單一緩存方式不同，這種設計確保了最壞情況下的性能而不是預期的情況下的性能，即在任何情況下都能提供一定程度的性能保證，而不僅僅是在常見情況下。不同之處還有，傳統的緩存只存儲一些頻繁訪問的數據，而不是全部數據；而計數器緩存則會為所有接收到的數據存儲條目，但會試圖去減少每個條目所占用的存儲空間，以便在內存有限的情況下盡可能多地存儲數據。
6.2.2 隨機計數
使用DRAM作為備份存儲器可以大幅度減少存儲開銷，但減少的SRAM計數器寬度會換來更多的處理量和復雜性。那么我們的第二種方法就是用結果的準確性和確定性來換取計數器寬度的減少，即“精度換開銷”。
精確的統計數據通常過于昂貴且難以獲得，而許多問題的近似答案是可以接受的，如流量大小的分布、出現頻率前N的流等，對于這些信息，其實只需要記錄一個近似的值就足夠了。
隨機計數的基本思想為：對一個寬度為b的計數器，其記錄值最大上限為\(2^b\)，即如果按照傳統的確定性的方式計數，一個b位的計數器最多只能計數\(2^b\)次；但如果引入隨機計數，假設一個計數器被選中后進行計數的概率為\(1/c\)，那么它的計數次數最高可以達到\(2^b*c\)次。計數上限整整高了c倍！
為什么隨機計數也能獲得相對正確的結果？這是因為在隨機計數的基本思想中，標準結果與實際結果的標準差（即計數器誤差的期望值）大致為幾個c的大小，其中c對于計數器值來說是非常小的。即在基本的隨機計數方法中，當計數器值遠大于計數概率c時，標準差會變得很小。也就是說，如果計數器的值足夠大，則誤差會相對較小且可控，從而使得估計的結果更加精確可靠。因此，這種方法可以在保證一定精度的同時，降低算法的復雜度和內存需求。對此R. Morris提出的隨機計數思想也是如此，他注意到，越高的計數值可以容忍計數結果中越高的誤差絕對值。例如，如果標準差等于計數器值，則真實值可能在計數器確定的值的一半到兩倍之間。允許誤差隨著計數器值的增加而縮放，反過來可以使用更小的計數器寬度，即要實現\(2^b\)的計數上限，只需要k的計數器寬度，使得\(2^b=2^k*c\)。
對于計數概率c的確定，Morris的理論將c的值設定為一個不確定的值——c將會隨著計數器當前值x變動。而c與x的關系可以用下式表示：
\[c=\frac{1}{2^x} \]這樣計數誤差的范圍會隨著計數器值的大小而變動。而計數器值x可以表示出結果的近似值，近似值為\(2^x\)（要注意，計數器值并不等于結果數值！）。因此，對同樣的結果上限值MAX，采用隨機計數后，計數器的寬度k僅僅為\(log\ (log MAX)\)。關系式梳理如下：
\[2^k=x,\ 2^x = MAX \]6.2.3 閾值聚合（Threshold Aggregation）
前面講的都是如何將計數器的寬度減少，接下來我們需要關注的是如何將計數器的數量減少。我們可以使用計數器閾值聚合的方法。
愛因斯坦有一句這樣的話，“Not everything that is counted counts, and not everything that can be counted .”
不是所有的值都是值得保留的。計數也是如此，計數是為了得到滿足我們需求的值，在這過程中難免會有一些額外的值被計算進來，要保存這些值就需要額外的計數器。所以我們有必要拋棄掉這些用途不大的額外值，此時閾值聚合計數技術就派上用場了。
在傳統的計數器中，每個計數器通常都需要單獨存儲，并且可能需要占用大量的內存空間。而且當計數器數量非常大時，對這些計數器進行處理和分析的時間和資源成本也會顯著增加。閾值聚合是一種常見的減少計數器的方法。該技術主要通過將原始計數器的值進行聚合來實現減少計數器的目的，從而降低計算和存儲成本。
閾值聚合可以用于在流測量中對”大象“流和”老鼠“流的區分上。在我們日常生活中，我們會開通各種的流量套餐，每種流量套餐有它自己的流量額度——所用流量低于這個額度時按照套餐計費，高于這個額度時則動態計費，這個額度就是一個閾值。另外，對于一個關心著路由流量熱點或網絡是否正在被攻擊ISP運營商來說，大象流顯然比老鼠流更值得留意。
（大象流是通過網絡鏈路進行大量的，持續的傳遞數據的過程；而老鼠流是通過網絡鏈路進行少量的，短時間的數據傳遞過程。具體區分的臨界點，不同的場景是不一樣的。參見定義：Elephant flow和Mouse flow）
下面來結合上圖來簡單解釋一下閾值聚合。圖中展示了一種最簡單的閾值聚合方式：將高于或等于特定閾值的計數器值保存下來，其它的計數器值扔掉。閾值可以選取一個與總流量大小有關的值，如總流量大小的0.1%，這個值就可以作為區分大象流和老鼠流的標準，留下了的計數器值就代表了當前存在的大象流。假如網絡中最多只有1000個大象流，我們只需要使用1000個計數器就能完成流測量！
但是很明顯我們發現了一個悖論問題：閾值聚合可以減少計數器數量，但要應用閾值聚合，就必須先對所有輸入的數據流進行計數器計數。這就違背了我們開始減少存儲開銷的意愿。所以怎樣才能做到，既不用跟蹤所有的流，也能辨別出大象流呢？下面我們來看一種依賴于流哈希的方法。圖中為對多個流進行并行哈希映射并判斷是否為需要的流：
計算識別大象流的核心在于多個哈希層（圖中的stage）的并行協作。其中，一個哈希桶由多個計數器組成，每當有數據包到達時，Controller會根據哈希函數來計算該包的索引鍵值，并將其存進相應的計數器中。也就是說，一個計數器記錄著一個流的信息。
首先讓我們考慮僅僅存在一個哈希層的情形。當一個屬于數據流F的數據包到達時，Controller將其計算并索引到相應的計數器，并將數據包的大小添加到計數器值中；當數據流F發送的字節數大于閾值T時，對應F流的計數器的值也就超出了閾值，那么我們就意識到這是一個屬于大象流的計數器，就可以將該流的數據送進流內存做進一步的分析處理。
但單個哈希層有一個明顯的缺陷：由于我們需要減少計數器數量，所以哈希層中的計數器數量是少于所有流的數量的，那么不同的流就有可能哈希到同一個計數器中。這會導致兩種測量上的誤差：老鼠流會哈希到屬于大象流的計數器中，或多個老鼠流哈希到同一個計數器而導致計數值高于閾值，使得Controller認為這是一個大象流。
所以我們使用并行的多個哈希層來做流哈希映射，不同的哈希層使用不同的哈希函數。對一個數據包，只有其哈希到各層的計數器值都大于閾值，才能認為這是一個大象流，才可以將流數據送進流內存中。如圖所示，假設對于一個屬于數據流F的數據包到達Controller，它在不同哈希層分別被哈希到3，1，7這三個計數器中，只有Controller判斷三個計數器值都大于閾值時，流F的數據才會被送到流內存中。
我們繼續做一個簡單的分析。假設有一條100 MB/s的鏈路，流的數量為100,000，我們希望在1秒的測量間隔內識別鏈路傳輸量1%以上的流量，即流量大小為1MB以上的流。如果按照傳統方式，我們至少需要100,000個計數器。但現在，假設每個哈希層有1000個計數器，閾值為1MB。讓我們來計算一下，一個流發送了100KB大小的數據并被識別送到流內存的概率是多少。
要使該流成功在一個哈希層中被識別出，即該流的計數器需要達到閾值，那么該計數器中在該流輸入前的值，即其他流哈希到該計數器的總和，需要達到1 MB-100KB=900KB。而在每個哈希層的1000個桶中，至多有99.9MB/900KB=111個這樣的準備達到閾值的桶。因此流在一個哈希層被識別成功的可能性至多為11.1%。而對于四個并行的哈希層，不大于100KB的小流量通過所有哈希層的概率是一個非常小的值，其最大值為\(1.52*10^{-4}\)。
這種閾值聚合方案的可拓展性極高。如果流的數量增加到100萬，我們只需添加第五個哈希層即可獲得相同的效果。因此，處理10萬個流需要大約4000個計數器和大約100個存儲單元的流內存；而處理100萬個流僅僅需要大約5000個計數器和相同大小的流存儲器。這僅僅是一個對數級別的增長速度。另外，在數據包到達時，每個哈希層會做一次讀取和一次寫入。如果哈希層足夠少，即使在高速情況下，這種訪問次數是可以負擔得起的——因為哈希層的訪問可以并行執行。
6.3 減少處理量
到目前為止，我們已經在數據包計數方面做出了存儲開銷的優化。但是，除了單純的計數以外，我們還需要對數據包中的日志信息進行處理分析——數據包日志有助于分析人員對網絡運行模式和受到的網絡攻擊進行回顧性分析。
在網絡中，有一些通用的流量測量分析系統，如Cisco的NetFlow技術，在極細粒度下（對于數據流的粒度，每個流由單獨的一條TCP或UDP連接標識），它可以分析并報告每個流記錄。但要注意的是，存儲數據包日志所需的大量內存需要使用DRAM來實現（流內存，并非計數器的存儲結構）——顯然，如果在每次數據包到達時寫入DRAM，這個寫入速度對于傳輸鏈路的高速率來說是不可行的，就像對于計數器不能單純使用DRAM計數一樣。由此，最基礎的NetFlow技術面臨著兩個問題：
- 處理流信息開銷上：更新DRAM會降低轉發速率。
- 收集報告信息開銷上：NetFlow生成的數據量太大，可能超過收集服務器或其網絡連接的處理能力?；ANetFlow技術的信息丟失率甚至可以高達90%。
兩個問題都與處理量過大密切相關。所以為了減少處理量，Cisco建議在使用NetFlow技術時，需要搭配采樣技術去使用。
6.3.1 采樣技術
我們先來直觀地感受一下NetFlow中采樣技術帶來的好處：
上圖為對數據包進行流采樣的過程。如圖，應用了采樣技術后，只有采樣的數據包才會更新DRAM流緩存。例如，對16個數據包中的I或1000個數據包的1個進行采樣，這是被允許而且是較為常見的。采樣的優點在于，如每16個數據包到達時，DRAM最多寫入1個數據包，這使得DRAM的訪問時間可以比數據包到達時間慢16倍。但要注意的是，抽樣在估計中引入了相當大的不準確性，不過對于長時間的測量（誤差平均值）以及應用程序不需要精確的數據，這種不準確性無關緊要。
下面我們來系統地闡述采樣技術。
我們之前進行流測量的方式，是對所有的數據包都進行處理和記錄然后根據元數據生成流記錄。但是，處理和記錄每個數據包會占用大量的計算和存儲資源，從而影響網絡性能并增加成本。特別是在高速網絡環境下，需要處理可能非常巨大，這使得準確測量和分析網絡流量的代價變得非常高昂。所以我們引入了采樣技術。
采樣技術在生成數據流記錄之前就對數據包進行采樣。它首先通過隨機采樣（1-out-of-n）的方式對數據包采樣，然后再基于采樣的數據包構建流記錄。這樣可以有效減輕網絡測量的計算和存儲開銷，避免在另外n-1個數據包上產生額外的計算和存儲開銷，同時避免為許多小型的數據流創建流記錄，從而提高記錄效率并降低存儲成本。
當前的采樣技術有幾種比較先進的處理方式：
不維護流狀態
在設備不維護任何流狀態的情況下，對流的隨機子集中的數據包進行采樣。
在此前的處理中，我們需要用計數器將流分別劃分出來，再將流數據送到流內存中進行處理。我們可以對此做優化：在設備中不維護任何流狀態，即丟棄流計數的步驟，直接對數據包進行流劃分后采樣。為了實現這一過程，可以對每個數據包的五元組（源IP地址、目標IP地址、協議類型、源端口、目標端口）進行哈希處理，并對哈希結果符合某種條件的數據包進行抽樣。這樣可以達到在不維護流狀態的情況下，對隨機一部分流量采樣的目的（相當于假定了符合某種條件的數據包屬于同一個流）。
軌跡采樣 Trajectory Sampling
軌跡采樣可以確保數據包在多跳路由器之間得到一致的采樣處理。
在采樣過程中，對多個路由器來說，即使經過它們的流是一樣的，但對流的采樣卻是相互獨立不受影響的——這會導致路由器之前的采樣結果有差異！如果我們有對路徑效應分析的需求，那么這種差異是不能接受的。管理人員可以使用軌跡采樣來查看路徑效應，例如數據包循環、數據包丟失和多個最短路徑，這些效應可能無法使用普通采樣的NetFlow進行區分。
所以我們引入了軌跡采樣技術。軌跡采樣的主要思想是讓數據流路徑上的路由器使用一個公共的哈希函數做出相關的包采樣決策。上圖顯示了進入路由器線卡的數據包的處理過程。對于每個數據包，都使用一個哈希函數h，通過將數據包的哈希值與指定的范圍進行比較，來決定是否對數據包進行采樣。如果對包進行采樣，則使用包上的第二個哈希函數g再次哈希，并進行日志存儲。
軌跡采樣有兩個要注意的地方：
- 如何確保路由器使用相同的哈希函數？
- 數據包里面的內容在傳輸過程中是會變化的，如何確保哈希函數的輸入相同？
對第一個問題，我們可以讓管理人員去配置路由器，以確保路由器使用相同的g和h哈希函數；對第二個問題，對于要進行哈希的數據包頭部字段，我們只選擇傳輸過程中不變的字段來計算哈希值。例如，可以選擇使用五元組（源IP地址、目的IP地址、協議類型、源端口和目標端口）與IP標識符或者五元組加上TCP標志作為哈希函數的輸入。
軌跡采樣和NetFlow正常采樣有兩個差異：
- 使用哈希函數而不是隨機數來決定何時對數據包進行采樣；
- 對不變的數據包內容使用第二個哈希函數，可以更緊湊地表示數據包頭部信息。
布隆過濾器（Bloom Filter）
我們可以只抽樣每個數據流的第一個數據包進行分析，而不對整個數據流進行分析。
使用Bloom Filter是一種實現這種數據采樣技術的方法。Bloom Filter是一種基于哈希函數的快速、空間效率高的數據結構，用于判斷某個元素是否存在于一個集合中。它使用位數組（BitSet）標記某個元素是否出現過，而不需要存儲元素本身。
具體地說，Bloom Filter包括一個位數組和多個哈希函數。將要檢查是否存在的元素通過多個哈希函數分別映射到位數組的不同位置上，并將對應的位設置為1。當檢查新元素是否存在時，將該元素經過相同的哈希函數計算得到的位進行比較，若所有位均為1，則認為該元素存在于集合中，否則認為不存在。哈希函數的設計可以使誤判率控制在可接受范圍內。
Bloom Filter的設計原理與上文閾值聚合中并行哈希層的思想類似。如上圖，假設一個Bloom Filter中有三個哈希函數\(h1\)，\(h2\)，\(h3\)，那么它會將輸入的值，如x，計算得到\(h1(x)=1\)，\(h2(x)=4\)，\(h3(x)=9\)，然后將BitSet的1，4，9位設置為1——這樣就將輸入值x映射到BitSet中的3個二進制位了。之后檢查x是否已被記錄只需要計算出對應的二進制位并檢查是否全為1即可。要注意的是，當輸入值計算得到的二進制位全為1時，實際上是不能100%的肯定該輸入值已被Bloom Filter記錄過的，因為有可能該輸入值的所有位都剛好是被其他輸入值設置為1）這種將劃分錯誤的情況，稱為誤判（wrong position）。計算誤判率的公式為：
\[P\approx(1-e^{\frac{-nk}{m}})^k \]其中插入Bloom Filter中的元素數目為n，BitSet位數為m，哈希函數的數目為k。從上式可以看出，當BitSet位數m增大或插入Bloom Filter中的元素數目n減小時，均可以使得誤判率P下降。
在這種情況下，我們可以將正在傳輸的所有數據流的ID存儲在Bloom Filter中。然后，當接收到新的數據包時，我們可以使用Bloom Filter查看該數據包所屬的數據流是否已經被分析過，如果已經被分析過，則將其丟棄；否則，將其作為該數據流的第一個數據包進行分析。這樣可以減少需要分析的數據包數量，從而提高網絡流量分析的效率。
7 協同方案
本節要解決的具體問題有關協同方案（concerted schemes）。例如，ISP希望收集客戶發送的流量統計信息，并根據流量類型和目的地向客戶收費，一方面，這需要解決如何將Accounting正確進行的問題，另一方面，解決方案運行的開銷要在可承受范圍內。要想在整個網絡中進行這般操作，就需要一個全面的協同的方案。
前文在講述采樣技術的過程中，我們從只需要單個本地路由器支持的單點方案轉向了軌跡采樣這樣的協同方案——這要求多個路由器的合作來提取更多有用的信息。協同方案可以在不同的時間尺度（例如，路由計算，轉發）上涉及網絡系統的所有方面（例如，協議，路由器）。
我們接下來將看到兩個使用協同方案的示例，分別為 Juniper networks 提出的DCU Accounting方案，以及協同思想進行流量矩陣計算。
7.1 Destination Class Usage
我們先來看一個單點Accounting帶來的反面例子：
如圖為一個小型的 ISP 網絡，假設ISP Z希望以一個價格a向客戶A收取通過ISP X流出的所有流量的費用，并以另一個價格b向客戶A收取通過ISP Y流出的所有流量的費用。這樣的話，一種最笨的解決方案是讓 路由器R1 為發送到每個前綴的流量維護一個單獨的計數器。在圖中，R1至少需要維護10,000+20,000 = 30000個前綴計數器！這不僅使實現更加復雜，而且也與用戶需求不符，因為用戶最終將這30000個前綴聚合成僅僅兩個資費類別。此外，如果路由變化頻繁，每個ISP的前綴數量可能會快速變化而丟失，這就需要不斷更新用于映射的Controller。
Juniper Networks公司給出了一個漂亮的協同計費方案：DCU計費（destination class usage，目標類使用 ） ！
“DCU 通過執行 IP 目標地址查找來對來自客戶的數據包進行計數，并且可以跟蹤來自客戶邊緣且發往提供商核心路由器上特定前綴的流量?！?/p>
DCU由兩個部分組成，分別為硬件實現和協議制定：
-
使用類計數器（Class Counters）。Class Counters是網絡路由器中的一種計數器，用于記錄每個流包含的數據包數量。在路由器的轉發表中，每個條目都有一個16位的類ID，每個類ID中的1個bit表示一個類別。當數據包傳輸時，如果它與某個前綴匹配，并且具有關聯的類ID，則與該類別對應的位的計數器會遞增。
類計數器支持最多16個不同的類別，但單個數據包可以導致多個類計數器的遞增。因此，這種方法能夠更精確地記錄每個流量的使用情況。同時，該解決方案也符合硬件設計實際情況，因為16個計數器與一個計數器相比并沒有顯著增加處理難度，并且可以在芯片上維護這些計數器以實現并行遞增，從而提高效率。這種計數器通常被用于ISP等場景中，用于實現更精細化的計費策略和QoS（服務質量）控制。
-
路由支持（Routing Support）：為了解決前綴變動的問題（這會導致Controller不斷將每個前綴映射到不同的類中），DCU方案借助路由協議來解決。其想法是，來自ISP X的所有前綴都被賦予一種顏色（可以使用簡單的路由策略過濾器進行控制），而來自ISP Y的前綴則被賦予另一種顏色。因此，當像上圖R1這樣的路由器收到帶有顏色c的前綴P的路由信息時，它會自動將前綴P映射到類c中。這個路由協議上的小改變可以極大地減少Controller的工作量。
Juniper Networks還有其他方案，包括使用基于分組分類器的計數器和基于MPLS隧道的計數器。這些方案比DCU計費稍微靈活一些，因為它們可以在確定數據包的類時考慮數據包的源地址。但是這些方案因為缺乏路由支持，所以不具備DCU計費的管理擴展性。
7.2 計算流量矩陣
雖然DCU解決方案僅對Accounting有用，但它的一些基本思想可以幫助解決流量矩陣問題。流量矩陣問題是許多互聯網服務提供商非常感興趣的問題。
7.2.1 流量矩陣的意義
流量矩陣（Traffic Matrix）是指在網絡中各個節點之間的流量量化信息。它記錄了從源節點到目標節點的流量量級或流量比例。流量矩陣可以根據不同的時間尺度（從幾小時到幾個月）進行測量和分析。
我們繼續利用 7.1 圖中的ISP網絡來介紹，來自ISP Z中的路由器的一些鏈路會到達屬于其他ISP (如E2, E3)或客戶(如E1, E4, E5)的路由器，我們稱這種聯系為external links；指向從外部指向ISP內部路由器的external links稱為input links，而從ISP指向外部路由器的external links稱為output links。
流量矩陣列舉了網絡中每對input和output links之間發送的流量(在某個任意時間段，例如一整天)。例如，在 7.1 圖中，流量矩陣可以告訴ISP Z的管理者，custom A 白天有60mbps的流量input，其中有20mbps作為output通往 ISP X 的peer-link E2上，剩余的40mbps由link E5作為output通往custom B。
對于網絡運營商來說，流量矩陣是必不可少的。它們可用于：
- 做出更優的路由決策：通過分析流量矩陣，ISP可以了解當前網絡中的流量分布情況，并根據需要調整路由設置，例如可以通過改變OSPF權重或建立MPLS隧道來解決次優路由問題)；
- 用于了解何時建立
circuit switch，以用于避免hot spot產生（為hot spot流量分配專用的物理路徑，避免與其他流量競爭網絡資源，使得hot spot流量可以在專用路徑上獨立傳輸） - 用于網絡診斷，了解網絡堵塞的原因；
- 以及用于網絡規劃（了解不同鏈路的負載情況，從而決定是否需要升級或調整特定鏈路的帶寬或容量，以滿足未來的流量需求)。
流量矩陣很好！但是現在存在一個問題：傳統路由器只提供單個聚合計數器（即 SNMP link byte counter），而從聚合計數器獲得的值去推斷流量矩陣是有大問題的。
為什么 SNMP link byte counter 不能用來推斷流量矩陣？
聚合計數器： SNMP link byte counter 提供的是對整個鏈路上所有流量的聚合計數（字節流量的總數）。它無法提供對特定流量對（例如源IP地址和目標IP地址）的細分計數。
稀疏網絡：許多網絡都是稀疏的，即只有少數幾個external link。在這種情況下， SNMP link byte counter 的數量可能與鏈接數量（即已知量數量）相當。缺乏足夠的計數器使得推斷流量矩陣變得更加困難。
變量數量：流量矩陣中可能存在大量的 input/output link pair，而 SNMP link byte counter 的數量相對較少。在已知流量路由的情況下，我們會產生O(V)個方程和O(V^2)個變量，其中V是external link的數量。這樣的方程數量不足以解決所有的變量。例如假設有3個external link，T_xy為由E_x到E_y的流量，方程右側為external link 流量計數值：
\[T_{12}+T_{13}+T_{21}+T_{31}= Traffic\ \ E1\\ T_{21}+T_{23}+T_{12}+T_{32}= Traffic\ \ E2\\ T_{31}+T_{32}+T_{13}+T_{32}= Traffic\ \ E3 \]明顯該方程無法求解。
對于存在的流量矩陣推斷難題，我們接下來將介紹三種協同方案。
7.2.2 網絡層析
Internet tomography（互聯網層析成像）是一種利用從端點數據中獲取的信息來研究網絡內部特征的方法。它類似于醫學中的CT（計算機斷層掃描）技術，旨在通過檢查來自"邊緣節點"（即數據的起源和請求節點）的信息來繪制數據在互聯網中的路徑，方法核心在于多信息源和統計推斷。
在推斷流量矩陣時，由于SNMP計數器的特性導致不可能進行確定性的推斷，所以需要采用統計推斷的方法（盡管存在一定的誤差）。Internet tomography利用統計學和概率模型來推斷流量矩陣中的未知變量，它基于多處協同觀察到的數據和一些假設的流量分布模型（如 Gaussian Distribution 高斯分布， 或 Gravity Model 重力模型），使用統計學原理（如maximum likelihood，最大似然估計）或優化技術（如quadratic programming，二次規劃）來推斷流量矩陣中的變量值。
Internet tomography 的最大優點是它不需要改造現有的路由器（它通過在網絡中部署測量設備，如探針，來觀察流量數據，而不需要對路由器進行任何修改或添加額外的硬件），而且在路由器中實施成本較低（利用現有設備，無需額外測量節點）。
這種方法的缺點在于：
- 推斷結果的潛在誤差：誤差可能高達20%！見Robust Traffic Matrix Estimation with Imperfect Information: Making Use of Multiple Data Sources）
- 對路由錯誤的敏感性：如果存在單個鏈路故障或路由錯誤，推斷結果可能會出現50%的偏差（如一個鏈路斷開而沒有被發現，明面上拓撲結構照舊）
- 對網絡拓撲的敏感性：網絡拓撲的變化或結構的復雜性可能導致推斷結果的不準確性。
7.2.3 per-prefix 計數器
前文中介紹的DCU計費方案其實可以算是一個用來解決流量矩陣問題的基于路由器實現和路由協議變化的系統解決方案，DCU體現了現代路由器的設計思想。而這節內容延續這種協同工作思想，繼續介紹一種用于流量矩陣計算的路由器計數器設計——per-prefix計數器。
在使用per-prefix計數器的方案中，每個輸入line card都有一個轉發引擎（forwarding engine），其中包含轉發前綴表的副本。假設轉發前綴表中的每個前綴 P 都有一個關聯的計數器，那么每個前綴與 P 匹配的數據包在進入line card時，都會使計數器增加相應的字節數。最后，通過匯總 input link 尾端路由器中的per-prefix計數器，就可以構建流量矩陣。為了實現這一點，該方法必須有一定的關鍵信息支持：包括路由協議（如OSPF）計算的路由信息和前綴路由與 output link 之間的映射關系。
我們來舉一個例子：在7.1的圖中，如果R1在來自鏈路E1的流量上使用per-prefix計數器，那么就可以對來自ISP X的10,000個前綴對應的計數器求和，從而找到Customer A和ISP X之間的流量關系。
這種方案的一個優點是它提供了堪稱完美的流量矩陣！第二個優點是它可以用于像DCU那樣的基于目的地址的差異性流量計費。但也存在兩個缺點：一方面是在實施上維護 per-prefix計數器 的復雜性。傳統路由器中缺乏這樣的設計，支持這種方案意味著需要對傳統路由器進行改進或引入新的路由器實現。另一方面，由于協同工作，需要從每個路由器收集和合成大量數據以形成流量矩陣，這可能需要大量的帶寬和存儲資源，并且需要高效的數據處理和分析算法來處理這些大規模的數據集。
7.2.4 類計數器
class counter（類計數器）在我們介紹DCU章節中已經有所提及，這節我們繼續介紹它在流量矩陣計算中的使用。
我們可以將每個前綴通過轉發表映射到一個小的類別ID，該ID通常為8至14位（256至16,384個類別）。當一個輸入數據包與前綴P匹配時，P的轉發條目將數據包映射到一個類計數器，并對該計數器進行遞增操作。對于多達10,000個計數器，類別計數器可以輕松存儲在轉發ASIC的片上SRAM中，從而允許在內部并行進行遞增操作和其他功能。
在前文的DCU Accounting中，DCU建議路由器使用策略過濾器按計費類別為路由進行分類著色，并使用路由協議傳遞這些顏色分類信息，這些分類信息可以用來在每個路由器上自動設置類別id。對于流量矩陣計算，可以使用類似的思想，根據矩陣等價類對路由進行著色。
矩陣等價類：所有源自同一 external link 或網絡的前綴都屬于同一個類別。
那么原理知道了，類計數器是怎樣使用在流量矩陣計算中的呢？
我們知道，許多ISP在主要城市設有PoP，這就需要計算聚合的PoP到PoP流量矩陣。通過將不同的PoP分配到不同的類別中，可以直接依靠類別計數器來計算和分析PoP到PoP之間的流量矩陣，這樣可以更加方便地獲取和處理與特定PoP相關的流量信息，而無需對完整的 路由器--路由器矩陣 進行聚合。例如，在7.1圖中，R4和R5可能屬于同一個PoP，那么E4和E5就可以被映射到同一個類別中。
根據2003年的測量數據，類別計數器的數量大大減少——使用150個計數器就足以處理最大的ISP的情況。這意味著通過合理的分類和計數器使用，可以在保證高效性能的前提下，減少需要處理的計數器數量，從而降低了系統的復雜性和資源消耗。
8 被動測量的例子：Sting
到目前為止，前文都專注于涉及對路由器實現（如計數器）和其他子系統（如路由協議）進行更改的路由器測量問題。但是這類方案需要多個路由器供應商進行合作，由于更改需要與現有的網絡設備和協議進行兼容，所以使用這類方案會面臨著逐步部署的困難。與之相比，被動測量側重于通過 “欺騙網絡” 來獲得有用的測量數據，而無需改變網絡內部結構。被動測量的基本思想是克服互聯網協議套件所提供的測量支持的缺乏。
假設你不再是一個ISP，而是某個公司的網絡管理員。一家新興的 ISP 聲稱可以提供比你現在使用的 ISP 更好的服務。那么你肯定想測試一番來驗證他們說的真假！為了驗證，你將輪流使用兩個 ISP ，從你的站點到全國各地的各種Web服務器進行端到端的性能測量。
標準解決方案是使用基于發送ICMP消息的Ping和Traceroute等工具。但是這些工具存在一個問題：ISP 經常過濾或限制此類消息（你可以自己試試看，ISP 會隱藏它們的路由節點，避免你搞到它們的網絡拓撲）。為了克服這個限制，Stefan Savage發明的Sting 工具提出了一個繞過這個限制的想法：
將測量數據包偽裝成TCP數據包，互聯網服務提供商和Web服務器無法丟棄或限制此類數據包（因為在它們眼里這不屬于垃圾數據）——這意味著通過利用TCP協議的各種機制，Sting工具能夠提供更多的測量*度。
我們先來看如何確定源和遠程Web服務器之間丟包概率。
確定丟包概率有助于了解大多數流量在網絡上是不是僅僅為單向傳輸。對于Ping工具，即使Ping沒有受到速率限制，它也只是提供了雙向丟包概率的綜合信息。而Sting工具提出了一種從源到遠程Web服務器確定丟包概率的算法：
-
data seeding階段：首先通過與服務器建立正常的TCP連接，并按順序向服務器發送N個數據包。此階段忽略了Acknoledgement，因為我們關注的是測量，而不是數據傳輸； -
hole filling階段：接下來，發送一個帶有比data seeding階段中最后一個發送的數據包序列號大1的數據包。如果收到Acknoledgement，說明一切正常，沒有丟失任何數據包。如果沒有，在進行足夠的重傳之后，接收方會回復已經按順序接收到的最大序列號X。發送方現在只發送與 X+1 相對應的段。最終，接收方會發送一個更新的Acknoledgement，其中包含下一個按順序接收到的最大序列號。接收方會填充下一個"hole"，并繼續進行，直到填充完所有的"hole"。在第二階段結束時，發送方準確地知道在第一階段中丟失了哪些數據包，并可以計算出丟包率。
計算反向丟包率更加具有挑戰性，因為接收方的TCP可能會將確認信息批量發送，而不是對每個數據包進行單獨的確認。然而由于Sting工具并不遵守真正意義上的TCP連接，那么就可以通過改變工具的行為來欺騙接收方：Sting在第一階段發送亂序的數據包，而不是按順序發送，以引誘接收方提供更準確的確認信息。通過這種方式，Sting能夠繞過接收方TCP的批量確認機制，獲得所需的信息以計算反向丟包率。
（這聽起來和hacker做的事情沒有什么區別……但這就是Sting的思想所在，"Stop thinking of a protocol as a protocol"！）
9 一些幫助理解的鏈接
- Capacity planning - Wikipedia
- Teletraffic engineering - Wikipedia
- Smurf attack - Wikipedia
- 什么是SNMP？為什么需要SNMP？
總結
以上是生活随笔為你收集整理的剖析网络测量：Counting and Measuring Network Traffic的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： markdown语法
- 下一篇： 文心一言 VS 讯飞星火 VS chat