黃　杰，陳　琳，王斌鋒國防科學技術大學計算機學院，長沙410073

?

系統(tǒng)域網(wǎng)絡基于消減策略網(wǎng)絡斷層掃描方法*

黃杰＋，陳琳，王斌鋒
國防科學技術大學計算機學院，長沙410073

* The National Natural Science Foundation of China under Grant No. 61379148（國家自然科學基金）.

Received 2015-04，Accepted 2015-06.

CNKI網(wǎng)絡優(yōu)先出版：2015-06-12，http://www.cnki.net/kcms/detail/11.5602.TP.20150612.1122.001.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10（01）-0065-09

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel:＋86-10-89056056

摘要：系統(tǒng)域網(wǎng)絡是高性能計算機、數(shù)據(jù)中心的重要組成部分，當前系統(tǒng)域網(wǎng)絡存在網(wǎng)絡規(guī)模龐大，內(nèi)部鏈路繁多，網(wǎng)絡流量行為復雜和各種應用對網(wǎng)絡性能狀況敏感度高等特點，致使采用傳統(tǒng)網(wǎng)絡斷層掃描方法進行性能測量的計算復雜度呈指數(shù)級增長。針對上述問題提出了一種基于消減策略的網(wǎng)絡斷層掃描方法（network tomography based on reduction strategy，NTRS）。該方法提出了預處理原則對實際物理拓撲進行策略約束，充分利用內(nèi)部鏈路已知的性能信息縮小性能測量網(wǎng)絡區(qū)域和關鍵鏈路覆蓋，依據(jù)測量結果計算鏈路性能協(xié)方差，篩除性能狀況較好的鏈路集合，實現(xiàn)鏈路數(shù)量的有效約簡，進而很大程度上提高了網(wǎng)絡診斷的準確性。通過模擬實驗驗證了NTRS方法的有效性，實驗結果表明該方法能縮小鏈路性能參數(shù)的測量規(guī)模，降低計算的復雜度。

關鍵詞：性能測量；網(wǎng)絡斷層掃描；鏈路消減；系統(tǒng)域網(wǎng)絡

1　引言

系統(tǒng)域網(wǎng)絡是目前高性能計算機、數(shù)據(jù)中心的重要組成部分，通過互連將計算節(jié)點、存儲節(jié)點和網(wǎng)絡設備整合成為集成服務環(huán)境，其中InfiniBand高速互連網(wǎng)絡就是一種典型的系統(tǒng)域網(wǎng)絡[1]。系統(tǒng)域網(wǎng)絡目前已經(jīng)得到廣泛應用，其主要有以下特點：

（1）網(wǎng)絡規(guī)模日益龐大

系統(tǒng)域網(wǎng)絡規(guī)模日益龐大，以天河2為例[2]，其互連計算節(jié)點數(shù)能達到10K以上的量級，而交換節(jié)點接近K的量級。數(shù)據(jù)中心的規(guī)模也日益擴大，服務器規(guī)模已經(jīng)達到10K～100K的量級。

（2）相對封閉，集中管理

系統(tǒng)域內(nèi)的服務節(jié)點和網(wǎng)絡節(jié)點都處于同一管理域內(nèi)，網(wǎng)絡管理者能夠全面有效監(jiān)測整個網(wǎng)絡狀態(tài)，實現(xiàn)對服務節(jié)點和網(wǎng)絡節(jié)點集中的管理控制。

（3）流量行為復雜，擁塞加劇

在高性能計算機集群或者數(shù)據(jù)中心網(wǎng)絡中，傳統(tǒng)的MPI（message passing interface）和日益興起的大數(shù)據(jù)應用有較強的流量突發(fā)性，如常見的柵欄同步many-to-one模式會導致Incast問題，Hadoop會產(chǎn)生all-to-all的流量等。文件系統(tǒng)、虛擬機遷移等應用會產(chǎn)生非常大的數(shù)據(jù)傳輸量，給網(wǎng)絡帶來嚴重的負載，網(wǎng)絡中的流量行為變得日益復雜。

（4）網(wǎng)絡故障率指數(shù)增加

長期的實踐表明，系統(tǒng)故障率隨著系統(tǒng)節(jié)點數(shù)快速增加，N表示節(jié)點數(shù)，α表示單點可靠性比率，則系統(tǒng)故障率p＝1?αN。例如，從服務節(jié)點故障的角度看，若服務單點可靠性為99.99%，按照10K級的規(guī)模計算，則系統(tǒng)故障率為63%，若單點可靠性為99.9%，則系統(tǒng)故障率幾乎達到100%。

（5）細粒度的網(wǎng)絡測量和診斷需求

系統(tǒng)域網(wǎng)絡運行的應用通常對網(wǎng)絡性能要求嚴格，需要管理者能更加實時、精確地掌握全網(wǎng)態(tài)勢和端到端的通信性能，在網(wǎng)絡性能下降后及時發(fā)現(xiàn)和定位故障和網(wǎng)絡擁塞，實現(xiàn)一個快速的故障診斷方案[3]。

因此，對于系統(tǒng)域網(wǎng)絡，如何通過有效的測量手段發(fā)現(xiàn)網(wǎng)絡實時運行狀態(tài)，當網(wǎng)絡發(fā)生性能故障時，又如何快速發(fā)現(xiàn)并診斷故障，保持和提高網(wǎng)絡運行的健壯性，保障網(wǎng)絡上關鍵任務的成功完成非常重要[4]。

網(wǎng)絡斷層掃描（network tomography，NT）[5]在網(wǎng)絡邊界上進行端到端的測量，通過測量端到端的通信行為來推斷網(wǎng)絡內(nèi)部性能，無需內(nèi)部網(wǎng)絡的協(xié)作，從而降低了測量所帶來的網(wǎng)絡負載，并可實現(xiàn)與被測網(wǎng)絡內(nèi)部結構和協(xié)議無關的測量，使得網(wǎng)絡斷層掃描成為目前主要的網(wǎng)絡測量手段之一[6-8]。但是隨著系統(tǒng)域網(wǎng)絡規(guī)模日益龐大，內(nèi)部鏈路繁多，使用網(wǎng)絡斷層掃描技術的測量方法的計算復雜度也隨之變大，推測結果的準確性也難以估計。本文通過對實際物理拓撲的策略約束和對鏈路已知性能信息的挖掘，有效縮小了系統(tǒng)域網(wǎng)絡內(nèi)部鏈路的規(guī)模，降低了網(wǎng)絡斷層掃描線性數(shù)學模型的計算復雜度，保證了網(wǎng)絡鏈路診斷的快速和準確性[9-10]。

本文的主要貢獻如下：通過建立多項預處理原則，對實際物理拓撲進行策略約束，充分利用內(nèi)部鏈路已知的性能信息，縮小性能測量網(wǎng)絡區(qū)域和關鍵鏈路覆蓋等；還能依據(jù)測量結果，通過計算鏈路性能協(xié)方差，篩除性能狀況較好的鏈路集合，實現(xiàn)鏈路數(shù)量的有效約簡。在此基礎上，提出了基于消減策略的網(wǎng)絡斷層掃描方法，提高了網(wǎng)絡鏈路診斷的準確性，并減少了計算的復雜性。

2　相關研究

基于NT的網(wǎng)絡測量技術將網(wǎng)絡測量分成兩個階段：（1）數(shù)據(jù)測量階段，建立測量模型，在網(wǎng)絡邊界上采集測量數(shù)據(jù)，在測量方式上，可以采用主動測量、被動測量或者二者的混合；（2）數(shù)據(jù)分析階段，建立統(tǒng)計分析模型，運用統(tǒng)計學理論對測量數(shù)據(jù)進行分析，推斷出網(wǎng)絡性能和拓撲。

通過有效的數(shù)據(jù)測量，獲取到端到端的測量數(shù)據(jù)，建立的數(shù)學模型理論上可以是多樣的，但在通常情況下，該問題被粗略地近似為線性模型[11-12]。

式（1）中y是端到端測量所得到的數(shù)據(jù)向量，如丟包率、時延等；A是二進制路由矩陣，表示網(wǎng)絡的拓撲結構，A中元素為1時表示測量路徑經(jīng)過某條鏈路，否則為0；θ代表未知參數(shù)向量，對應內(nèi)部鏈路級的丟包、時延等；ε表示由θ引入的隨機噪聲，也可能是測量時附加的噪聲。在某些情況下，為了簡化，常忽略噪聲ε，并用待估參數(shù)θ的向量函數(shù)X代替式（1）的θ，線性模型變?yōu)椋?/p>

基于式（1）和式（2）的線性模型，推測內(nèi)部鏈路級的性能參數(shù)可以抽象為：已知路由矩陣A，端到端的測量結果y以及某種合理的噪聲分布ε，就可以通過求解線性方程組的方法，解得未知參數(shù)向量。

圖1所示為由節(jié)點組成的樹狀拓撲，假設節(jié)點0為數(shù)據(jù)包發(fā)送端，節(jié)點1為網(wǎng)絡內(nèi)部節(jié)點，節(jié)點2和節(jié)點3為數(shù)據(jù)包的接收端，并記節(jié)點0和節(jié)點1之間的連接為鏈路1，同理定義鏈路2和鏈路3。為了使用斷層掃描技術推測3條鏈路的丟包率，選擇測量路徑“0—1—2”和“0—1—3”，記為P1和P2。由節(jié)點0向節(jié)點2和節(jié)點3分別發(fā)送探測報文，并測得兩條路徑端到端的丟包率L1和L2。根據(jù)測量路徑P1和P2，路由矩陣A可以表示為：

Fig.1 Tree topology of nodes圖1　節(jié)點組成的樹狀拓撲圖

記3條鏈路成功率的對數(shù)分別為θ1、θ2和θ3，測量路徑P1和P2成功率為y1和y2，其中y1＝1?L1，y2＝1?L2，則線性模型為：

因為路由矩陣A不是滿秩的，所以式（4）不存在唯一的解，無法求得3條鏈路的丟包率。為了獲得θ1、θ2和θ3，需要采用一定的方法增加路由矩陣信息，增加端到端的測量數(shù)據(jù)。如果節(jié)點0發(fā)往節(jié)點2的探測包和節(jié)點0發(fā)往節(jié)點3的探測包之間存在相關性，則可對A和y進行補充。假設y2|3表示同時在節(jié)點2、節(jié)點3收到的探測報文相對于節(jié)點3收到的探測報文的比例，y2|3＝θ2，類似地定義y3|2，則補充后的方程為：

基于兩方面的考慮：一是為了達到良好的效率和準確性，所采用的推斷分析理論需要在計算復雜度與推斷準確性之間保持平衡；二是建立的線性模型存在差異，如噪聲ε所服從的分布可能是高斯、泊松、二項式及多項式等其中的任何一種，因此對鏈路級性能參數(shù)的推測即線性模型的求解，采用的推理算法通常有多種，包括極大似然估計法（maximum likelihood estimation，MLE）[13]、期望最大值算法[14]（expectation maximum，EM）、最大概似估計[15]（maximum pseudo likelihood estimation，MPLE）和Bayesian[16]推斷方法等。

MINC[17[18]。

在推測鏈路的丟包率方面，Duffield和Caceres等人依據(jù)多播探測包的特點，提出了一種自頂向下的鏈路丟包率估測方法[19]；Bu等人對網(wǎng)絡拓撲進行抽象，提出了基于最小方差加權平均（minimum variance weighted average，MVWA）和基于EM算法的鏈路丟包率估測方法[20]。

在推測時延方面，Hero和Shih使用有限混合模型對鏈路時延分布進行建模，提出了一種基于單播測量的鏈路時延估測方法[21]；針對非平穩(wěn)網(wǎng)絡環(huán)境下的鏈路時延估測，Coates等人提出了基于序貫蒙特卡羅（sequential monte carlo，SMC）的鏈路時延估測方法[22]。

3　基于消減策略的斷層掃描方法

3.1相關定義

對于大規(guī)模系統(tǒng)域網(wǎng)絡而言，網(wǎng)絡內(nèi)部鏈路繁多且鏈接關系復雜，導致所建立的斷層掃描線性數(shù)學模型規(guī)模巨大，不僅使未知鏈路性能參數(shù)的推測復雜度增加，而且使最終的推測性能結果準確率下降。為了清晰準確地描述系統(tǒng)域網(wǎng)絡性能測量問題，給出了相關的定義和約束假設。

定義1網(wǎng)絡S：由節(jié)點和鏈路構成且任意兩節(jié)點間存在網(wǎng)絡路徑，表示為S＝（N，E），其中N＝{H，V}為節(jié)點集合，E＝{e0，e1，…}為鏈路集合，H＝{h0，h1，…}為端節(jié)點集合，V＝{v0，v1，…}為中間節(jié)點集合。

定義2測量路徑pij：表示探測包從源節(jié)點hi到目的節(jié)點hj所經(jīng)過的網(wǎng)絡路徑，記為pij＝（em，…，ek，…，en），其中i≠j，m≠n，ek為測量路徑pij上的一條鏈路。

定義3測量路徑集合P：表示參與網(wǎng)絡性能測量的測量路徑pij的集合，且測量路徑集合P的子集表示一次性能測量所涉及的測量路徑集合。

定義4路由矩陣Am×n：對于路由矩陣A列向量的維數(shù)m，表示參與性能測量的測量路徑數(shù)量；對于路由矩陣A行向量的維數(shù)n，表示參與性能測量的鏈路數(shù)量；對于路由矩陣A第i行第j列的元素aij，取值或為0或為1，表示測量路徑pi（pi∈P）是否經(jīng)過鏈路ej（ej∈E）。

定義5網(wǎng)絡切割：對于網(wǎng)絡S，T為預設的較小數(shù)值，通常根據(jù)經(jīng)驗設置T的數(shù)值。假設網(wǎng)絡S可以分成n個子網(wǎng)，記為Si（i∈[0，n?1]），且對于任意i，j∈[0，n?1]，Si和Sj（i≠j）之間存在m條鏈路，鏈路的平均流量值分別為t1，t2，…，tm，如果有＜T，則網(wǎng)絡S可以切割。

3.2拓撲邏輯化原則

在實際的物理網(wǎng)絡中，設備之間的鏈接往往比較復雜，內(nèi)部鏈路繁多，如果直接針對其使用斷層掃描方法推測網(wǎng)絡內(nèi)部鏈路的性能參數(shù)，工作量巨大，是不現(xiàn)實的，也是沒有必要的，而且如果不采取有效的措施，推測結果的準確性會隨著問題規(guī)模的擴大而逐漸降低。因此，為了增強斷層掃描方法實施的可行性，同時也是為了提高推測結果的準確性，針對物理網(wǎng)絡的簡化即邏輯抽象過程是必不可少的。根據(jù)一定的拓撲邏輯化原則，對物理網(wǎng)絡的部分鏈路進行合并或者刪除，最終獲得性能測量所需要的有效邏輯拓撲。因而，對拓撲邏輯化原則的確定至關重要，直接決定了抽象得到的邏輯拓撲能否反映物理網(wǎng)絡的真實性能狀況。

原則1合并一致的物理鏈路。對于物理鏈路ei和ej，如果有網(wǎng)絡設備V將兩者連接，并且設備V沒有其他物理鏈路或其他物理鏈路可以忽略，則稱ei和ej為一致的物理鏈路。同理，一致物理鏈路的定義也可以推廣到多條物理鏈路。在物理網(wǎng)絡的邏輯化抽象過程中，一致的物理鏈路可以合并成一條邏輯鏈路，最終獲取的性能參數(shù)是合并的幾條物理鏈路整體的性能狀況。

原則2充分利用內(nèi)部鏈路已知的性能信息。對于實際的物理網(wǎng)絡拓撲，獲取內(nèi)部鏈路性能參數(shù)的方式有多種。充分利用鏈路的已知性能信息，對物理網(wǎng)絡的部分鏈路，采用合理的方式提前獲取鏈路的性能參數(shù)，使這些鏈路的性能參數(shù)成為已知值，從而減小了未知性能參數(shù)的鏈路數(shù)目，降低了斷層掃描線性數(shù)學模型的求解復雜度。一般可以采用實際測量和參考歷史經(jīng)驗值的方法。有些鏈路容易部署測量工具且所花費的代價較低，此時就可以使用實際測量的方法獲取性能參數(shù)；有些鏈路經(jīng)過多次測量后，發(fā)現(xiàn)其性能參數(shù)并未發(fā)生大的變化，這種情況下就可以以歷史經(jīng)驗值作為該鏈路的性能參數(shù)。

原則3縮小性能測量網(wǎng)絡區(qū)域。對網(wǎng)絡進行性能測量的目的是為了及時了解網(wǎng)絡的運行狀態(tài)，發(fā)現(xiàn)網(wǎng)絡存在的性能瓶頸或故障點。又因為實際的物理網(wǎng)絡總是可以劃分成多個小網(wǎng)絡區(qū)域，所以假如某個網(wǎng)絡區(qū)域已經(jīng)確定性能狀況正常，則測量網(wǎng)絡就不需要包括該網(wǎng)絡區(qū)域。假設在性能測量之前已經(jīng)確定網(wǎng)絡區(qū)域性能正常，則對該網(wǎng)絡區(qū)域中鏈路無需進行測量，從而縮小了要測量網(wǎng)絡的規(guī)模。

原則4關鍵鏈路覆蓋。在實際的物理網(wǎng)絡中，內(nèi)部鏈路繁多，各條鏈路在整個網(wǎng)絡的運行過程中所發(fā)揮的作用也不盡相同，有些鏈路承載著多個網(wǎng)絡區(qū)域之間的流量傳輸，而有些鏈路只是負責傳輸其所連端節(jié)點的數(shù)據(jù)，因此不同的鏈路對網(wǎng)絡整體性能狀況的影響也不同。在探究網(wǎng)絡的整體性能狀況時，為了避免測量問題的復雜性，應首先從物理網(wǎng)絡中抽象出覆蓋關鍵鏈路的邏輯拓撲，而對非關鍵鏈路暫時不予考慮。在獲取關鍵鏈路性能參數(shù)后，如果確定關鍵鏈路無故障，再對非關鍵鏈路進行性能測量，此時關鍵鏈路的性能參數(shù)是已知條件。

針對具體的物理網(wǎng)絡，按照上述的拓撲邏輯化原則，能夠達到簡化測量網(wǎng)絡，減小未知性能參數(shù)鏈路的數(shù)目，降低斷層掃描線性數(shù)學模型復雜度的目的。

3.3鏈路的簡約機制

通過物理網(wǎng)絡的拓撲邏輯抽象，很大程度上縮小了推斷網(wǎng)絡內(nèi)部性能參數(shù)的問題規(guī)模。但是就所抽象出的邏輯拓撲而言，網(wǎng)絡內(nèi)部鏈路依然繁多，需要推測的未知性能參數(shù)數(shù)量仍然很大。為了進一步減少性能參數(shù)推測的工作量，降低斷層掃描線性數(shù)學模型求解的復雜度，繼續(xù)探究對斷層掃描問題簡化的方法很有必要。對于網(wǎng)絡中的部分鏈路，其性能參數(shù)只是略微偏于正常值，如果將這部分鏈路的性能參數(shù)近似取為正常的歷史經(jīng)驗值，就可以增加斷層掃描線性數(shù)學模型的已知信息，提高推測未知性能參數(shù)的效率。

對于網(wǎng)絡拓撲N（V，E），其中V和E分別為節(jié)點集和邊集。如果將邊集E分為K和U兩部分，其中K為E中已知鏈路參數(shù)的邊集，U為E除去K剩余的邊集。記Y為端到端的性能測量數(shù)據(jù)，Au為U中的邊在路由矩陣A中所對應的列向量，Ak為K中的邊在路由矩陣A中所對應的列向量，Xu為U中的邊所對應的未知性能參數(shù)，Xk為K中的邊所對應的未知性能參數(shù)。

因為在建立線性方程組時已經(jīng)通過采用合適的測量方式使路由矩陣A滿秩，且路由矩陣A列向量的減小是隨著未知性能參數(shù)的減小而進行的，所以矩陣Au必定滿秩，上述線性方程組可解，即U中的邊所對應的鏈路性能參數(shù)可推測出來。假設網(wǎng)絡N在性能測量之前，鏈路e2表現(xiàn)正常，其性能參數(shù)可以近似取歷史經(jīng)驗值。如式（6）所示，路由矩陣的第二列表示e2在多條測量路徑中的參與情況，θ2表示e2對應的性能參數(shù)，如果θ2已知，則可以從路由矩陣中去除e2對應的列向量，從未知性能參數(shù)向量中去除θ2，并從測量結果中減去鏈路e2所影響的部分，式（6）變?yōu)槿缡剑?）所示：

其中路由矩陣的列向量數(shù)目減1，未知性能參數(shù)的數(shù)目減1，測量數(shù)據(jù)也發(fā)生相應變化。

因此，選擇合適的K集合較為關鍵。如果某條鏈路的性能表現(xiàn)正常，則其性能參數(shù)就可以近似取為歷史經(jīng)驗值，并可將該鏈路加入到集合K中。與此同時，集合K中元素數(shù)量的選定也同樣重要。如果K中元素數(shù)量較大，則推測結果會產(chǎn)生很大的誤差；如果K中元素數(shù)量較小，則不能達到降低問題復雜度的目的。內(nèi)部鏈路丟包率或者時延的方差Xk是一個非遞減的函數(shù)，即鏈路越擁塞，丟包率或者時延的方差越大，因而可以通過對鏈路丟包率或者時延方差的排序來選擇K集合中的元素。通過對多次端到端性能測量結果（丟包率或者時延）的分析，能夠計算出所有鏈路丟包率的方差或者時延的方差，并可以對這些數(shù)據(jù)進行排序，得QL＝＜e1，e2，…，en＞。為了選擇出集合K中的元素，首先需要確定K集合中元素的數(shù)目num（通常是總鏈路的一定比例），而后從QL隊列中選取方差較小的num條鏈路組成K。從邊集E中除去K得到的集合U，就是經(jīng)過簡約處理后實際真正需要推測性能參數(shù)的鏈路集合。

3.4NTRS方法

基于消減策略的斷層掃描方法NTRS是在原有斷層掃描方法基礎上的改進，其主要思想是：首先根據(jù)拓撲邏輯化原則，對要測量的目標網(wǎng)絡進行抽象并得到對應的邏輯拓撲；其次進行鏈路簡約處理，挖掘鏈路的已知性能信息，使未知性能參數(shù)的鏈路規(guī)模降低，從而建立線性數(shù)學模型，并應用一定的推理算法，推測內(nèi)部鏈路未知的性能參數(shù)。

NTRS方法具體描述如下：

步驟1物理拓撲邏輯化。

假設需要性能測量的物理網(wǎng)絡為S（V，E），ei和ej為物理網(wǎng)絡S邊集E中任意的兩條邊。從物理拓撲邏輯抽象得到的邏輯網(wǎng)絡為S′（V′，E′），ek為物理網(wǎng)絡S′邊集E′中的一條邊。

（1）如果ei和ej為一致性鏈路，合并ei和ej為ek；

（2）如果S的某條鏈路ei性能參數(shù)可以通過實測或者歷史經(jīng)驗值獲得，則ei不屬于E′；

（3）如果存在某網(wǎng)絡區(qū)域N（VN，EN），已知N區(qū)域網(wǎng)絡性能狀況正常，則對EN中的鏈路ei，ei不屬于E′；

（4）對于S，如果不存在（1）、（2）和（3）中的任何一種情況，則表示已經(jīng)獲得邏輯拓撲S′。

步驟2邏輯拓撲鏈路的簡約處理。

假設鏈路簡約處理的邏輯拓撲為S′，端到端的性能測量數(shù)據(jù)為Y，且網(wǎng)絡內(nèi)部鏈路所需推測的性能參數(shù)為丟包率。該步驟主要完成對部分鏈路性能參數(shù)的近似處理，對于丟包率而言，就是尋找丟包率可以近似為0的鏈路。

（1）通過對多次端到端測量數(shù)據(jù)的處理，計算每條鏈路丟包率的協(xié)方差；

（2）對鏈路丟包率的協(xié)方差排序，得到一個對應的鏈路序列Qe；

（3）從Qe鏈路序列中選取K條丟包率協(xié)方差較低的鏈路，記為＜e1，e2，…，ek＞；

（4）將＜e1，e2，…，ek＞中每條鏈路的丟包率值近似取為0，則未知丟包率的鏈路數(shù)目減少K。

步驟3推測鏈路性能參數(shù)。

經(jīng)過步驟1和步驟2，網(wǎng)絡斷層掃描技術所建立的線性數(shù)學模型的復雜度大幅降低，進而對網(wǎng)絡內(nèi)部未知鏈路性能參數(shù)進行推測。

（1）將對網(wǎng)絡內(nèi)部未知性能參數(shù)的推測問題分解成若干簡單的子問題，即對路由矩陣A進行劃分，劃分為若干組，每組由一對或多對行向量構成，用S表示所有可能子問題的集合；

（2）針對每個子問題s∈S，建立子線性數(shù)學模型Ys＝AsXs；

（3）依據(jù)子線性數(shù)學模型，得到每個子問題對應的邊緣似然函數(shù)fs;θs）；

（4）建立似然函數(shù)：

（5）計算對數(shù)似然函數(shù)的數(shù)學期望值，并求解期望值最大時的極值點，得到θ（l＋1）＝Q（θ′，θl）；

（6）設置性能參數(shù)θ的初值θ（0），迭代求解θ，直到達到一個穩(wěn)定值θ。

4　性能分析與評估

假設網(wǎng)絡拓撲已知，且在性能測量過程中保持不變。本文實驗具體采用的拓撲結構如圖2所示，總共由10個節(jié)點和9條鏈路組成，其中1個數(shù)據(jù)發(fā)送節(jié)點（節(jié)點0），4個中間節(jié)點（節(jié)點1～4），5個接收節(jié)點（節(jié)點5～9），不同的鏈路由其所連接的下端節(jié)點號標識。拓撲圖中的每個節(jié)點都被用來模擬真實網(wǎng)絡中不同的設備，節(jié)點0和節(jié)點5～9用來模擬端設備，節(jié)點1～4用來模擬路由器。對于拓撲圖中的每個節(jié)點都需要設置一定大小的緩沖區(qū)，特別是中間節(jié)點1～4。通常情況下，在真實網(wǎng)絡環(huán)境中主要采用兩種擁塞避免策略：DropTail和RED（random early detection）。

Fig.2 Experimental topology圖2　實驗拓撲結構圖

前者在隊列長度達到最大值的情況下，采用丟棄新到分組的策略，而后者隨機選擇丟棄數(shù)據(jù)包。在實驗中測量流量采用UDP傳輸，丟包策略選擇DropTail方式。如表1所示，對實驗拓撲圖中的鏈路屬性進行了描述。

Table 1 Link attributes表1　鏈路屬性

另外，為了使網(wǎng)絡中傳輸合適的數(shù)據(jù)流量，需要在某些節(jié)點上建立相應的協(xié)議代理，包括指定端設備的協(xié)議綁定及通信業(yè)務量模型。TCP流量通過建立TCP代理以及配對的接收代理TCP SINK來實現(xiàn)。UDP流量的實現(xiàn)由UDP代理及接收代理Null配合實現(xiàn)。

仿真實驗及分析如下：

根據(jù)NTRS方法，對實驗拓撲圖進行邏輯抽象處理，將鏈路4和鏈路7合并為鏈路47，并假設網(wǎng)絡區(qū)域A中的鏈路性能參數(shù)（丟包率）可預先測得，則所得邏輯拓撲如圖3所示。本實驗采取發(fā)送組播探測報文的方式進行測量，由節(jié)點0作為源節(jié)點，其余端節(jié)點作為接收節(jié)點，并通過TCP生成了背景流量。整個仿真過程持續(xù)180 s，測量流量通過UDPAgent發(fā)送，每隔30 s進行一次統(tǒng)計，其他鏈路設置與表1一致。

對于圖3中的拓撲，實驗將測量得到的統(tǒng)計結果在NS2下采用MPLE算法對鏈路丟包率進行推測，并通過產(chǎn)生的trace文件計算得到鏈路實際的丟包率。對于圖3中的拓撲，根據(jù)測量的統(tǒng)計結果首先計算各條鏈路丟包率的協(xié)方差，并選擇協(xié)方差最小的一個，將其對應鏈路的丟包率近似取為0，再在NS2下采用MPLE算法對剩余鏈路的丟包率進行推測，并分析產(chǎn)生的trace文件，計算得到鏈路實際的丟包率。圖4和圖5分別給出在180 s內(nèi)，鏈路3和8在不同測量技術下所獲得的鏈路丟包率及真實丟包率的對比圖。

Fig.3 Abstract logical experimental topology map圖3　實驗拓撲圖的邏輯抽象

Fig.4 Comparison of three kinds of packet loss rate in Link 3圖4　鏈路3的3種丟包率對比圖

從圖4和圖5可以看出，鏈路真實的丟包率在7.5%左右，通過NTRS方法推測得到的鏈路丟包率接近于真實的丟包率，直接使用MPLE算法推測的結果也接近于真實值，因為本實驗采取的是組播的測量方式，測量結果相關度高，推測過程引入的誤差較小?？梢钥闯?，兩種方式獲取的鏈路性能參數(shù)相近，即擁有同樣的測量效果，但是NTRS方法所涉及的未知性能參數(shù)明顯減少，推測的復雜度也很大程度上得到了降低。通過比較，反映出NTRS方法較直接使用推理算法進行推測的斷層掃描方法具有不錯的優(yōu)越性。

Fig.5 Comparison of three kinds of packet loss rate in Link 8圖5　鏈路8的3種丟包率對比圖

實驗計算了90 s時各鏈路的推測丟包率與真實丟包率之間的相對誤差，具體如圖6所示。通過計算兩種不同測量方法所得鏈路丟包率與真實丟包率之間的相對誤差，MPLE方法和NTRS方法雖然都存在誤差，但誤差都在合理區(qū)間內(nèi)，且兩種測量方式有近似的測量效果。NTRS方法通過對實際物理拓撲的邏輯處理以及鏈路已知性能信息的挖掘，降低了測量鏈路的數(shù)量，進而降低了推測和計算的復雜度，適合于規(guī)模較大的網(wǎng)絡環(huán)境。

Fig.6　Relative error of packet loss rate in 90 s圖6　90 s時各鏈路丟包率相對誤差

5　結束語

本文針對系統(tǒng)域網(wǎng)絡趨向于大型化且內(nèi)部鏈路繁多的情況，提出了基于消減策略的斷層掃描方法NTRS，通過對實際物理拓撲的邏輯處理以及鏈路已知性能信息的挖掘，縮小了鏈路性能參數(shù)的推測規(guī)模，降低了斷層掃描線性數(shù)學模型的計算復雜度，保證了網(wǎng)絡鏈路診斷的快速和準確性，并通過模擬實驗驗證了NTRS方法的有效性。

為了提高推測性能參數(shù)的高效性，對斷層掃描線性數(shù)學模型的求解優(yōu)化也很重要，這部分工作將在下一步進行重點研究。

References:

[1] Infiniband Trade Association. Infiniband architecture specification Volume 1 Release 1.2.1[S]. Nov 2007.

[2] Dongarra J. Visit to the National University for Defense Technology Changsha，China[R/OL].（2013-06-03）[2015-02-12]. http://www.netlib.org/utk/people /JackDongarra/PAPERS/ tianhe-2-dongarra-report.pdf.

[3] Gill P，Jain N，Nagappan N. Understanding network failures in data centers: measurement，analysis，and implications[C]// Proceedings of the 2011 ACM SIGCOMM Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications，Toronto，Canada，Aug 15-19，2011. New York，USA:ACM，2011.

[4] Song H H，Qiu Lili，Zhang Yin. NetQuest: a flexible framework for large-scale network measurement[J]. IEEE/ACM Transactions on Networking，2009，17（1）: 106-119.

[5] Song Tao，Wang Xun，Su Yansen.Anovel approach to identify protein coding domains by sampling binary profiles from genome[J]. Journal of Computational and Theoretical Nanoscience，2014，11（1）: 147-152.

[6] Firooz M H，Roy S. Network tomography via compressed sensing[C]//Proceedings of the 2010 IEEE Global Telecommunications Conference，Miami，USA，Dec 6-10，2010. Piscataway，USA: IEEE，2010: 1-5.

[7] Gu Yu，Jiang Guofei，Singh V，et al. Optimal probing for unicast network delay tomography[C]//Proceedings of the 29th IEEE International Conference on Computer Communications，San Diego，USA，Mar 15-19，2010. Piscataway，USA: IEEE，2010.

[8] Arya V，Duffield N G，Veitch D. Multicast inference of temporal loss characteristics[J]. Performance Evaluation，2007，64（9/12）: 1169-1180.

[9] Zhu Weiping. An efficient loss rate estimator in multicast tomography and its validity[C]//Proceedings of the 3rd IEEE International Conference on Communication Software and Networks，Xi’an，China，May 27-29，2011. Piscataway，USA: IEEE，2011: 90-94.

[10] Adams A，Bu T，F(xiàn)riedman T，et al. The use of end-to-endmulticast measurements for characterizing internal network behavior[J]. IEEE Communications Magazine，2000.

[11] Castro R，Coates M，Liang G，et al. Network tomography: recent developments[J]. Statistical Science，2004，19（3）: 499-517.

[12] MINC: multicast-based inference of network-internal characteristics[EB/OL]. [2015-02-12]. http://gaia.cs.umass.edu/minc/.

[13] Fakhrabadi M，Khani N，Pedrammehr S，et al. Prediction of buckling instability of perfect and defective carbon nanotubes[J]. Journal of Computational and Theoretical Nanoscience，2014，11（11）: 2356-2369.

[14] Shih M F，Hero A O. Unicast-based inference of network link delay distributions with finite mixture models[J]. IEEE Transactions on Signal Processing，2003，51（8）: 2219-2228.

[15] Chua D B，Kolaczyk E D，Crovella M. Efficient monitoring of end-to-end network properties[C]//Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies，Mar 13-17，2005. Piscataway，USA: IEEE，2005: 1701-1711.

[16] Nguyen H X，Thiran P. Network loss inference with second order statistics of end-to-end flows[C]//Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement，San Diego，USA，Oct 24-26，2007. New York，USA: ACM， 2007.

[17] Coates M J，Nowak R D. Network tomography for internal delay estimation[C]//Proceedings of the 2001 IEEE International Conference on Acoustics，Speech，and Signal Processing，Salt Lake City，USA，May 7-11，2001. Piscataway，USA: IEEE，2001: 3409-3412.

[18] Tsang A，Coates M，Nowak R. Passive network tomography using EM algorithms[C]//Proceedings of the 2001 IEEE International Conference on Acoustics，Speech，and Signal Processing，Salt Lake City，USA，May 7-11，2001. Piscataway，USA: IEEE，2001: 1469-1472.

[19] Caceres R，Duffield N G，Horowitz J，et al. Multicast-based inference of network-internal loss characteristics[J]. IEEE Transactions on Information Theory，1999，45（7）: 2462-2480.

[20] Bu T，Duffield N，Presti F L，et al. Network tomography on general topologies.[J]. ACM Sigmetrics Performance Evaluation Review，2002，30（1）: 21-30.

[21] Shih M F，Hero A O I. Unicast-based inference of network link delay distributions with finite mixture models[J]. IEEE Transactions on Signal Processing，2003，51（8）: 2219-2228.

[22] Coates M J，Nowak R D. Sequential Monte Carlo inference of internal delays in nonstationary communication networks[J]. IEEETransactions on Signal Processing，2001，50（2）: 366-376.

HUANG Jie was born in 1976. He received the Ph.D. degree from National University of Defense Technology in 2005. Now he is an associate professor at National University of Defense Technology. His research interests include network measurement and data center network technology，etc.

黃杰（1976—），男，陜西西安人，2005年于國防科學技術大學獲得博士學位，現(xiàn)為國防科學技術大學副教授，主要研究領域為網(wǎng)絡測量，數(shù)據(jù)中心網(wǎng)絡技術等。發(fā)表學術論文20多篇，承擔國家自然科學基金項目1項、湖南省自然科學基金項目1項。

CHEN Lin was born in 1976. She received the Ph.D. degree from National University of Defense Technology in 2005. Now she is an associate professor at National University of Defense Technology. Her research interest is data center network resource management technology.

陳琳（1976—），女，福建隴海人，2005年于國防科學技術大學獲得博士學位，現(xiàn)為國防科學技術大學副教授，主要研究領域為數(shù)據(jù)中心網(wǎng)絡資源管理。發(fā)表學術論文20多篇，主持湖南省自然科學基金項目1項、承擔國家自然科學基金項目1項。

WANG Binfeng was born in 1989. He is a Ph.D. candidate at National University of Defense Technology. His research interest is data center network resource management technology.

王斌鋒（1989—），男，陜西寶雞人，國防科學技術大學博士研究生，主要研究領域為數(shù)據(jù)中心網(wǎng)絡資源管理。

Network Tomography Based on Reduction Strategy in System Area Network*

HUANG Jie＋，CHEN Lin，WANG Binfeng
School of Computer，National University of Defense Technology，Changsha 410073，China ＋Corresponding author: E-mail: agnes_nudt@qq.com

HUANG Jie，CHEN Lin，WANG Binfeng. Network tomography based on reduction strategy in system area network. Journal of Frontiers of Computer Science and Technology，2016，10（1）：65-73.

Abstract:System area network is the important component of high performance computer and data center. The current system area network has the characteristics of larger-scale network，more internal links，more complex behavior of network traffic，higher sensitivity of applications on network performance and so on. Those problems cause that the computational complexity of the performance measurement is exponential growth of the traditional network tomography. To address this problem，this paper proposes a new method of network tomography called NTRS（network tomography based on reduction strategy）. This method proposes a number of pre-treatment principles to optimize the measurement topology and these principles include merging the consistent physical links，making full use of the known performance information of internal links，narrowing the scope of the performance measuring area and covering the key links. According to the results of measurement，this method screens for link collection with better performance to achieve an effective reduction of the measuring links through computing the covariance of performance parameters for internal links in light of end-to-end performance measurement data. And the method largely improves the accuracy of performance measurement and the link diagnosis speed. Finally，this paper validates the effectiveness of NTRS by simulation，the results show that NTRS can decrease the number of the link performance parameters needed to measure and reduce the computational complexity.

Key words:performance measurement; network tomography; link reduction; system area network

文獻標志碼：A

中圖分類號：TN915

doi:10.3778/j.issn.1673-9418.1505012