基于數據流的實時網絡流量分析系統設計與實現

摘要:以建立一個強壯的#65380;實時的網絡流量分析系統為目標，設計了一個基于數據流的網絡流量管理系統#65377;實現了一個能夠準實時監視網絡運行狀況的網絡管理系統#65377;試驗和試運行表明該系統取得了較好的效果#65377;

關鍵詞:網絡性能分析; 網絡管理; 數據流

中圖分類號:TP393.07

文獻標志碼:A

文章編號:1001-3695(2007)10-0295-03

監視和分析流量的使用模式對于網絡管理非常重要#65377;在容量規劃時，網絡管理員需要了解哪些鏈路經常負載較大，以采取適當的措施，降低這些鏈路的壓力#65377;在病毒分析時，網絡管理員需要知道哪些端口發送的數據發生了較大變化#65377;在入侵檢測時，需要知道哪些主機發起了大量連接#65377;在路由優化時，需要實時地監視網絡流量，以合理優化路由，平衡負載#65377;

隨著網絡規模的擴大，網絡帶寬的增加，收集大量的網絡流量數據越來越困難#65377;在主干的ISP鏈路上，詳細的流量記錄一天就可以到達10 GB[1]，這些流量記錄數據還需要網絡進行傳輸，給網絡帶來額外的負擔#65377;這些流量數據為了不影響網絡性能通常采用UDP進行傳輸，如NetFlow和sFlow，數據的到達時間有很大的抖動;更為嚴重的是在網絡擁塞的情況下，UDP報文的丟棄率高達90%[2]#65377;大多數時候，網絡管理并不需要很精確的數據#65377;盡管傳統的基于數據庫的網絡管理技術能夠提供較為精確的結果，也可以提供歷史記錄，但是很難滿足實時的網絡管理#65377;

類似IP網絡流量分析的應用還有電話呼叫記錄#65380;金融證券管理等#65377;這類應用有如下特點:

a)數據源連續產生的數據以流形式傳遞，大多無須保存，完整存儲的代價太大#65377;連續查詢在定義好的時間間隔實時響應#65377;

b)數據通常以不穩定速率傳遞，傳來的數據有時是無用的#65377;

c)許多聚集查詢可能需要近似解答#65377;

d)查詢大多數情況下是預先給定的#65377;

為了解決這些問題，數據流已經成為數據庫研究領域的熱點#65377;目前有不少的學術性項目，均處于原型階段#65377;具有代表性的有斯坦福大學的Stream[3]#65380;伯克力大學的電信電話流TelegrahpCQ，以及分布式網絡監控系統Gigascope#65377;但是基于數據流的網絡管理系統目前仍然較為少見#65377;本文把數據流技術和傳統的網絡管理技術相結合，取得了較好的應用效果#65377;

在管理大型數據庫集群系統的數據交換網絡時發現，Oracle數據庫對網絡的服務質量要求非常苛刻#65377;實踐表明，如果某條鏈路發生擁塞或者斷開的時間超過1 min，Oracle數據庫為了保證數據的一致性，不得不停止服務，這就造成大量數據丟失#65377;筆者首先基于傳統的網絡管理系統設計方案，將sFlow和SNMP數據存入數據庫，然后再進行分析#65377;發現在采樣間隔小于5 s時，系統頻繁地讀寫數據庫導致系統無法迅速處理這些采樣數據，而將這些性能數據報文丟棄#65377;為了能夠實時地監控各個集群節點間的網絡狀況，筆者基于數據流技術重新開發了一套網絡管理系統——NetWatcher#65377;

1.2相關算法

由于數據流處理應用的廣泛性，目前已經成為數據庫研究的熱點，各種算法也不斷提出#65377;算法的關鍵在于設計一個遠小于數據集規模的結構，從而可以在內存中處理數據#65377;相對于數據流的規模而言，這種名為概要數據結構(synopsis data structure)的規模至多應該是次線性的#65377;數據流處理的常用技術除了傳統的二分查找#65380;貪婪算法#65380;線性規劃等方法，還有抽樣(sampling)#65380;分組測試(group test)#65380;樹(tree method)#65380;強近似(robust approximation)#65380;直方圖(exponential histograms)#65380;草圖(sketch)算法[4]等#65377;

從網絡管理應用的角度，根據算法的目的將這些算法分為如下三類:

a)尋求最大流算法，指發送了大量數據報文或者Byte的流#65377;最主要的算法有文獻[5~7]中提到的#65377;文獻[5]中介紹的sample and hold以及multistage算法實現非常簡單，可以使用硬件實現#65377;A.C.Gilbert提出了sketch算法，也可以用來尋求最大流#65377;

b)不同流計數算法代表的有文獻[8，9]中提到的#65377;文獻[8]中的算法是基于記錄出現的概率來估計記錄的數目，小概率的記錄出現則意味著記錄數目較大#65377;文獻[9]則提出了一系列的位圖算法來對網絡中的流數目進行估計#65377;文獻[1]中的Lp sketch在p→0時，也可以用來對流進行計數#65377;

c)在尋求變化較大的流的算法比較有代表性的有文獻[10~12]中提到的#65377;其中文獻[10，11]中的算法是尋求相對變化的算法#65377;G.Cormode在文獻[12]中利用組合分組測試(combinatorial group test)方法提出了一個尋求各種變化(包括絕對變化#65380;相對變化和方差變化)的框架#65377;

2NetWatcher網絡管理系統

2.1NetWatcher 系統結構

NetWatcher用于實時監控大型數據庫集群系統的互聯網絡數據流量#65377;在鏈路出現故障或者流量過大時能夠及時地反映給管理員#65377;所管理的數據庫集群系統由四臺Force10 E600高性能交換機將10個cluster連接起來，每個cluster包含6個計算節點#65380;18個磁盤控制器和1個磁帶庫;cluster內部通過私有網絡連接#65377;系統還提供了一套備份網絡，因此需要管理的接口總數達500個#65377;

系統最初將采集的性能數據(包括SNMP數據#65380;sFlow數據和軟件探針主動測量的鏈路狀態數據)存入專用的Oracle數據庫，然后再進行分析#65377;這樣能夠對歷史數據進行很好的分析#65377;在故障分析時能夠提供大量的信息#65377;但是這種結構不能應付實時監控網絡的要求，特別是在測量間隔時間小于5 s時，多次讀寫數據庫給數據庫造成了巨大的壓力，而且這些性能數據均是通過UDP進行傳輸的#65377;如果不能及時處理這些數據，將會導致大量的測試數據丟失#65377;仔細分析NetWatcher系統后發現，如果將實時分析模塊處理成數據流的形式，將更加有利于網絡管理實時了解網絡運行狀態#65377;

2.2NetWatcher結構

系統結構如圖1所示#65377;數據采集模塊負責將交換機送來的sFlow數據和SNMP以及探針主動測量的結果解碼;數據預處理模塊對數據進行篩選，同時將這些數據統一處理成數據流的格式，有選擇地寫入數據庫，然后將這些統一的數據格式送往實時處理模塊，根據需要選擇適當的算法進行分析#65377;具體的分析方法在2.3節中介紹#65377;處理的結果送至報告生成模塊，同時將處理的結果送到圖形繪制模塊，提示網絡管理員應該注意哪些接口#65380;節點的流量#65377;

2.3基于數據流的流量分析算法

在數據預處理模塊，將所有采集的數據處理成(流標志，有效數據)數據流形式#65377;對于SNMP數據，利用網絡拓撲生成模塊(圖1中未畫出)的接口統一編號，使用集合{接口統一編號，OID}作為標志，有效數據為OID對應的數值#65377;對于sFlow數據，使用集合{源IP地址，目標IP地址，源端口，目標端口}作為標志，有效數據為數據包個數和Byte數#65377;在NetWatcher中，探針主要用來測量鏈路的延時和丟包率，使用{源節點編號，目的節點編號}#65377;這里沒有采用IP地址，因為主機的數目固定并且有編號，有效數據為鏈路雙向延時和主動測量的丟包率#65377;

根據需要處理的類型，數據類型被處理成兩種模型，即時間序列模型和收銀機模型#65377;將SNMP數據和sFlow數據處理成收銀機模型，將探針數據作為時間序列模型#65377;

采用分組測試的方法來分析sFlow數據，找到在每個測量周期內速率超過預定閾值的流#65377;分組測試算法有下列優點:算法的誤差的上界可以預先給定;算法的空間消耗可以預先估算，而且非常少;每次更新訪問內存的次數少;不會漏報超過閾值的流#65377;

算法描述如下:

a)讀取sFlow數據報文，解析報文中的各個采樣數據，將采樣數據處理成(i，p)格式的數據流形式，同時要將數據乘以采樣率[13](total_packets/total_samples=rate)#65377;

b)對于報文中的每項(i，p)根據d個相互獨立的hash函數H1…d∶{i}->{1…(10/)}映射到不同的計數器，將計數器的值加上p#65377;

c)如果i對應的計數器均超過了閾值×C×t(C為鏈路容量，t為采樣時間)，則報告該流#65377;

每到一個新的項，算法需要更新的計數器個數為d，消耗的空間為d×(10/)×s(s為每個計數器的大小)#65377;在NetWatcher運行時，筆者設定d=4，=1%，每個計數器采用4 Byte，算法消耗的內存為16 KB#65377;

2.4試驗及運行結果

系統在發現超過閾值的流量并不需要等到測量周期結束#65377;如果測量周期為5 s，鏈路為100 MB，閾值為1%，則每個計數器的閾值為5 MB#65377;如果有某一條流以速率2 Mbps發送數據，則在2.5 s時就會被發現，而且流的速率越大，越容易被迅速發現#65377;

由于多個流共享計數器，可能會導致系統報告一些本來沒有超過閾值的流，但是這種概率非常小#65377;詳細的分析可以參見文獻[5]#65377;可以初步分析一下，在前面的例子中，如果有一個100 kbps的流要被誤報為超過閾值，則在該流對應的一個計數器中，其他的與該流hash到相同的計數器的流必須要貢獻5 MB-500 KB=4 500 KB，最多有495 500/4 500=110個這樣的計數器#65377;因此該流通過計數器的閾值的概率是11%，而要通過四個這樣的計數器，概率為1.5×10-4#65377;

為了與原有的基于數據庫的系統進行對比，同時運行了兩套系統#65377;流量的加載采用ssh腳本在各個節點間傳送1.4 GB的文件，用服務器節點管理器同時啟動這些腳本#65377;管理系統均運行在普通的PC機上(Intel Pentium 4 3.0 GHz CPU，內存為512 MB，原有系統的Oracle數據庫獨立運行在HP DL360服務器上，系統通過100 Mbps鏈路連接在Force10 E600 交換機上，sFlow的采樣率為128 bps)#65377;圖2描述了采用數據流的測量系統和基于數據庫的測量系統在處理sFlow數據，發現占用帶寬較大的流時丟棄報文的比較(sFlow pollinterval=50)#65377;說明基于數據流的測量系統能夠更快地處理sFlow的采樣數據#65377;

對于SNMP數據和探針數據，不需要采用組合測試這些近似算法#65377;因為這些數據的到達速度較慢，其數目不是特別多而且相對穩定，可以為每個接口的每個統計指標單獨分配一個計數器，更為精確地處理這些數據#65377;

系統能夠對使用交換機連接的大型數據庫系統的連接網絡進行準實時的SNMP數據和sFlow數據初步分析，為網絡管理員了解網絡實時運行情況提供了較為準確的信息，增強了數據庫系統的穩定性#65377;

3結束語

為了能夠滿足網絡管理員對于網絡實時監控的需求，需要建立一個能夠進行實時網絡流量分析的工具#65377;本文以建立一個實時的網絡流量分析工具為目標，分析了各種實時流量分析算法，并且給出了一種基于數據流技術的網絡流量管理方法，為實時監控網絡流量提供了一條新的思路#65377;系統在實際運行中，有很多參數需要動態確定，需要使用一些算法來動態調整以適應具體的運行環境#65377;sFlow或者NetFlow數據是采用采樣的機制，如何減少因采樣帶來的誤差還需要分析#65377;另外，目前數據流處理算法能夠提供的信息遠遠不如離線分析工具提供的信息豐富，特別是sFlow或NetFlow數據中本身包含很多信息，這將是下一步的研究工作和目標#65377;

參考文獻:

[1]GILBERT A C， KOTIDIS Y， MUTHUKRISHNAN S， et al. QuickSAND: quick summary and analysis of network data[R].[S.l.]: DIMACS， 2001:43-45.

[2]FELDMANN A， GREENBERG A G， LUND C， et al. Deriving traffic demands for operational IP networks: methodology and experience[C]//Proc of ACM SIGCOMM’00. 2000:257-270.

[3]BABU S， WIDOM J. Continuous queries over data streams[R].[S.l.]: Stanford University， Database Group， 2001.

[4]MUTHUKRISHNAN S. Data streams: algorithms and applications[C]//Proc of the 14th Annual ACMSIAM Symposium on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics， 2003.

[5]ESTAN C， VARGHESE G. New directions in traffic measurement and accounting[C]//Proc of the 4th ACM SIGCOMM of Computer Communication Review. 2002:323-338.

[6]CORMODE G， MUTHUKRISHNAN S. An improved data stream summary: the countmin sketch and its applications[J]. Journal of Algorithms，2004(3):214220.

[7]KARP R， PAPADIMITRIOU C， SHENKER S. A simple algorithm for finding frequent elements in sets and bags[J]. ACM Transactions on Database Systems， 2003， 28(1):51-55.

[8]FLAJOLET P， MARTIN G N. Probabilistic counting algorithms for data base applications [J]. Journal of Computer and System Sciences， 1985，31(2):182-209.

[9]ESTAN C， VARGHESE G， FISK M. Bitmap algorithms for counting active flows on high speed links， Technical Report CS20030738[R].[S.l.]: UCSD， 2003:114.

[10]CHARIKAR M， CHEN K， FARACHCOLTON M. Finding frequent items in data streams[C]//Proc of Symposium on Principles of Database System(PODS). 2002:116.

[11]HENZINGER M. Algorithmic challenges in search engines[J]. Internet Mathematics， 2001，1(1):115126.

[12]CORMODE G， MUTHUKRISHAN S. What’s new: finding significant differences in network data streams[J]. ACM INFOCOM， 2004，33(1):112.

[13]PHAAL P， PANCHEN S， McKEE N. A method for monitoring traffic in switched and routed networks[EB/OL].(2005).http://www.rfcarchive.org/getrfc.php?rfc=3176.

[14]ESTAN C. Internet traffic measurement: what’s going on in my network[D]. San Diego: University of California， 2003.

[15]KEYS K， MOORE D， ESTAN C. A robust system for accurate realtime summaries of Internet traffic[C]//Proc of SIGMETRICS. 2005:610.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”