系統域網絡基于消減策略網絡斷層掃描方法*

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

?

系統域網絡基于消減策略網絡斷層掃描方法*

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

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

Received 2015-04，Accepted 2015-06.

CNKI網絡優先出版：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

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

關鍵詞：性能測量；網絡斷層掃描；鏈路消減；系統域網絡

1　引言

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

（1）網絡規模日益龐大

系統域網絡規模日益龐大，以天河2為例[2]，其互連計算節點數能達到10K以上的量級，而交換節點接近K的量級。數據中心的規模也日益擴大，服務器規模已經達到10K～100K的量級。

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

系統域內的服務節點和網絡節點都處于同一管理域內，網絡管理者能夠全面有效監測整個網絡狀態，實現對服務節點和網絡節點集中的管理控制。

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

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

（4）網絡故障率指數增加

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

（5）細粒度的網絡測量和診斷需求

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

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

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

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

2　相關研究

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

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

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

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

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

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

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

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

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

MINC[17[18]。

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

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

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

3.1相關定義

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

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

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

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

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

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

3.2拓撲邏輯化原則

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

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

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

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

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

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

3.3鏈路的簡約機制

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

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

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

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

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

3.4NTRS方法

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

NTRS方法具體描述如下：

步驟1物理拓撲邏輯化。

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

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

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

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

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

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

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

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

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

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

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

步驟3推測鏈路性能參數。

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

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

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

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

（4）建立似然函數：

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

（6）設置性能參數θ的初值θ（0），迭代求解θ，直到達到一個穩定值θ。

4　性能分析與評估

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

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

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

Table 1 Link attributes表1　鏈路屬性

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

仿真實驗及分析如下：

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

對于圖3中的拓撲，實驗將測量得到的統計結果在NS2下采用MPLE算法對鏈路丟包率進行推測，并通過產生的trace文件計算得到鏈路實際的丟包率。對于圖3中的拓撲，根據測量的統計結果首先計算各條鏈路丟包率的協方差，并選擇協方差最小的一個，將其對應鏈路的丟包率近似取為0，再在NS2下采用MPLE算法對剩余鏈路的丟包率進行推測，并分析產生的trace文件，計算得到鏈路實際的丟包率。圖4和圖5分別給出在180 s內，鏈路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算法推測的結果也接近于真實值，因為本實驗采取的是組播的測量方式，測量結果相關度高，推測過程引入的誤差較小。可以看出，兩種方式獲取的鏈路性能參數相近，即擁有同樣的測量效果，但是NTRS方法所涉及的未知性能參數明顯減少，推測的復雜度也很大程度上得到了降低。通過比較，反映出NTRS方法較直接使用推理算法進行推測的斷層掃描方法具有不錯的優越性。

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

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

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

5　結束語

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

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

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，Friedman 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年于國防科學技術大學獲得博士學位，現為國防科學技術大學副教授，主要研究領域為網絡測量，數據中心網絡技術等。發表學術論文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年于國防科學技術大學獲得博士學位，現為國防科學技術大學副教授，主要研究領域為數據中心網絡資源管理。發表學術論文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—），男，陜西寶雞人，國防科學技術大學博士研究生，主要研究領域為數據中心網絡資源管理。

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