黃　杰，陳　琳，王斌鋒國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，長(zhǎng)沙410073

?

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

黃杰＋，陳琳，王斌鋒
國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，長(zhǎng)沙410073

* The National Natural Science Foundation of China under Grant No. 61379148（國(guó)家自然科學(xué)基金）.

Received 2015-04，Accepted 2015-06.

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

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

1　引言

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

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

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

（2）相對(duì)封閉，集中管理

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

（3）流量行為復(fù)雜，擁塞加劇

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

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

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

（5）細(xì)粒度的網(wǎng)絡(luò)測(cè)量和診斷需求

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

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

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

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

2　相關(guān)研究

基于NT的網(wǎng)絡(luò)測(cè)量技術(shù)將網(wǎng)絡(luò)測(cè)量分成兩個(gè)階段：（1）數(shù)據(jù)測(cè)量階段，建立測(cè)量模型，在網(wǎng)絡(luò)邊界上采集測(cè)量數(shù)據(jù)，在測(cè)量方式上，可以采用主動(dòng)測(cè)量、被動(dòng)測(cè)量或者二者的混合；（2）數(shù)據(jù)分析階段，建立統(tǒng)計(jì)分析模型，運(yùn)用統(tǒng)計(jì)學(xué)理論對(duì)測(cè)量數(shù)據(jù)進(jìn)行分析，推斷出網(wǎng)絡(luò)性能和拓?fù)洹?/p>

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

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

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

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

Fig.1 Tree topology of nodes圖1　節(jié)點(diǎn)組成的樹(shù)狀拓?fù)鋱D

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

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

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

MINC[17[18]。

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

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

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

3.1相關(guān)定義

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

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

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

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

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

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

3.2拓?fù)溥壿嫽瓌t

在實(shí)際的物理網(wǎng)絡(luò)中，設(shè)備之間的鏈接往往比較復(fù)雜，內(nèi)部鏈路繁多，如果直接針對(duì)其使用斷層掃描方法推測(cè)網(wǎng)絡(luò)內(nèi)部鏈路的性能參數(shù)，工作量巨大，是不現(xiàn)實(shí)的，也是沒(méi)有必要的，而且如果不采取有效的措施，推測(cè)結(jié)果的準(zhǔn)確性會(huì)隨著問(wèn)題規(guī)模的擴(kuò)大而逐漸降低。因此，為了增強(qiáng)斷層掃描方法實(shí)施的可行性，同時(shí)也是為了提高推測(cè)結(jié)果的準(zhǔn)確性，針對(duì)物理網(wǎng)絡(luò)的簡(jiǎn)化即邏輯抽象過(guò)程是必不可少的。根據(jù)一定的拓?fù)溥壿嫽瓌t，對(duì)物理網(wǎng)絡(luò)的部分鏈路進(jìn)行合并或者刪除，最終獲得性能測(cè)量所需要的有效邏輯拓?fù)?。因而，?duì)拓?fù)溥壿嫽瓌t的確定至關(guān)重要，直接決定了抽象得到的邏輯拓?fù)淠芊穹从澄锢砭W(wǎng)絡(luò)的真實(shí)性能狀況。

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

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

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

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

針對(duì)具體的物理網(wǎng)絡(luò)，按照上述的拓?fù)溥壿嫽瓌t，能夠達(dá)到簡(jiǎn)化測(cè)量網(wǎng)絡(luò)，減小未知性能參數(shù)鏈路的數(shù)目，降低斷層掃描線(xiàn)性數(shù)學(xué)模型復(fù)雜度的目的。

3.3鏈路的簡(jiǎn)約機(jī)制

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

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

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

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

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

3.4NTRS方法

基于消減策略的斷層掃描方法NTRS是在原有斷層掃描方法基礎(chǔ)上的改進(jìn)，其主要思想是：首先根據(jù)拓?fù)溥壿嫽瓌t，對(duì)要測(cè)量的目標(biāo)網(wǎng)絡(luò)進(jìn)行抽象并得到對(duì)應(yīng)的邏輯拓?fù)?；其次進(jìn)行鏈路簡(jiǎn)約處理，挖掘鏈路的已知性能信息，使未知性能參數(shù)的鏈路規(guī)模降低，從而建立線(xiàn)性數(shù)學(xué)模型，并應(yīng)用一定的推理算法，推測(cè)內(nèi)部鏈路未知的性能參數(shù)。

NTRS方法具體描述如下：

步驟1物理拓?fù)溥壿嫽?/p>

假設(shè)需要性能測(cè)量的物理網(wǎng)絡(luò)為S（V，E），ei和ej為物理網(wǎng)絡(luò)S邊集E中任意的兩條邊。從物理拓?fù)溥壿嫵橄蟮玫降倪壿嬀W(wǎng)絡(luò)為S′（V′，E′），ek為物理網(wǎng)絡(luò)S′邊集E′中的一條邊。

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

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

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

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

步驟2邏輯拓?fù)滏溌返暮?jiǎn)約處理。

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

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

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

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

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

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

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

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

（2）針對(duì)每個(gè)子問(wèn)題s∈S，建立子線(xiàn)性數(shù)學(xué)模型Ys＝AsXs；

（3）依據(jù)子線(xiàn)性數(shù)學(xué)模型，得到每個(gè)子問(wèn)題對(duì)應(yīng)的邊緣似然函數(shù)fs;θs）；

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

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

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

4　性能分析與評(píng)估

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

Fig.2 Experimental topology圖2　實(shí)驗(yàn)拓?fù)浣Y(jié)構(gòu)圖

前者在隊(duì)列長(zhǎng)度達(dá)到最大值的情況下，采用丟棄新到分組的策略，而后者隨機(jī)選擇丟棄數(shù)據(jù)包。在實(shí)驗(yàn)中測(cè)量流量采用UDP傳輸，丟包策略選擇DropTail方式。如表1所示，對(duì)實(shí)驗(yàn)拓?fù)鋱D中的鏈路屬性進(jìn)行了描述。

Table 1 Link attributes表1　鏈路屬性

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

仿真實(shí)驗(yàn)及分析如下：

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

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

Fig.3 Abstract logical experimental topology map圖3　實(shí)驗(yàn)拓?fù)鋱D的邏輯抽象

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

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

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

實(shí)驗(yàn)計(jì)算了90 s時(shí)各鏈路的推測(cè)丟包率與真實(shí)丟包率之間的相對(duì)誤差，具體如圖6所示。通過(guò)計(jì)算兩種不同測(cè)量方法所得鏈路丟包率與真實(shí)丟包率之間的相對(duì)誤差，MPLE方法和NTRS方法雖然都存在誤差，但誤差都在合理區(qū)間內(nèi)，且兩種測(cè)量方式有近似的測(cè)量效果。NTRS方法通過(guò)對(duì)實(shí)際物理拓?fù)涞倪壿嬏幚硪约版溌芬阎阅苄畔⒌耐诰颍档土藴y(cè)量鏈路的數(shù)量，進(jìn)而降低了推測(cè)和計(jì)算的復(fù)雜度，適合于規(guī)模較大的網(wǎng)絡(luò)環(huán)境。

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

5　結(jié)束語(yǔ)

本文針對(duì)系統(tǒng)域網(wǎng)絡(luò)趨向于大型化且內(nèi)部鏈路繁多的情況，提出了基于消減策略的斷層掃描方法NTRS，通過(guò)對(duì)實(shí)際物理拓?fù)涞倪壿嬏幚硪约版溌芬阎阅苄畔⒌耐诰?，縮小了鏈路性能參數(shù)的推測(cè)規(guī)模，降低了斷層掃描線(xiàn)性數(shù)學(xué)模型的計(jì)算復(fù)雜度，保證了網(wǎng)絡(luò)鏈路診斷的快速和準(zhǔn)確性，并通過(guò)模擬實(shí)驗(yàn)驗(yàn)證了NTRS方法的有效性。

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

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年于國(guó)防科學(xué)技術(shù)大學(xué)獲得博士學(xué)位，現(xiàn)為國(guó)防科學(xué)技術(shù)大學(xué)副教授，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)測(cè)量，數(shù)據(jù)中心網(wǎng)絡(luò)技術(shù)等。發(fā)表學(xué)術(shù)論文20多篇，承擔(dān)國(guó)家自然科學(xué)基金項(xiàng)目1項(xiàng)、湖南省自然科學(xué)基金項(xiàng)目1項(xiàng)。

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年于國(guó)防科學(xué)技術(shù)大學(xué)獲得博士學(xué)位，現(xiàn)為國(guó)防科學(xué)技術(shù)大學(xué)副教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)中心網(wǎng)絡(luò)資源管理。發(fā)表學(xué)術(shù)論文20多篇，主持湖南省自然科學(xué)基金項(xiàng)目1項(xiàng)、承擔(dān)國(guó)家自然科學(xué)基金項(xiàng)目1項(xiàng)。

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—），男，陜西寶雞人，國(guó)防科學(xué)技術(shù)大學(xué)博士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)中心網(wǎng)絡(luò)資源管理。

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

文獻(xiàn)標(biāo)志碼：A

中圖分類(lèi)號(hào)：TN915

doi:10.3778/j.issn.1673-9418.1505012