一種基于端到端測量構造網(wǎng)絡性能拓撲的方法

摘 要：分析了分布式應用與網(wǎng)絡性能拓撲結構的關系，以及利用端到端測量進行拓撲劃分的可行性和實用性；然后通過測量瓶頸鏈路的方法對節(jié)點進行分組劃分以縮小集合節(jié)點個數(shù)，再具體分析利用性能相關性探測節(jié)點集合的樹型拓撲結構；最后通過實驗模擬檢驗了這一拓撲探測方法。

關鍵詞：拓撲結構；性能測量；瓶頸帶寬

中圖法分類號：TP393.06文獻標識碼：A

文章編號：1001—3695(2007)02—0313—03

傳統(tǒng)的分布式計算平臺(如集群)具有高性能網(wǎng)絡連接和可靠性保證。而在異構、層次性的大規(guī)模分布式網(wǎng)絡中，網(wǎng)絡性能成為分布式應用的一個重要瓶頸。分布式應用系統(tǒng)，通常具有特殊的通信模式，其性能在很大程度上依賴于網(wǎng)絡的結構特性。因此，對于分布式應用，不僅需要獲得節(jié)點對之間的帶寬、時延、丟包率等性能參數(shù)，還需要知道各個節(jié)點之間的相互連接關系。獲得這些信息，可以預測節(jié)點集合之間的通信性能，使得應用在調(diào)度決策中不會作出錯誤的決定，如將通信頻繁地應用部署到節(jié)點之間網(wǎng)絡性能良好的節(jié)點集合中去，優(yōu)化服務的部署。常用的網(wǎng)絡拓撲測量方法是分析來自網(wǎng)絡內(nèi)部資源的數(shù)據(jù)(BGP路由表、ICMP)， 生成網(wǎng)絡拓撲或性能的報告[1]。這種方法是基于路由器或路由器協(xié)作的，它適合于在大時間尺度上進行宏觀分析，但不適合小時間粒度的場合。目前端到端拓撲探測的研究[2]主要針對連接一個發(fā)送者與多個接收者之間的樹型拓撲，利用終端節(jié)點之間性能相關性(時延/丟包相關性)來推測與某種性能(如時延、丟包率)相關的邏輯拓撲。本文的目的在于通過端到端的測量方法探測對分布式應用產(chǎn)生重要影響的網(wǎng)絡性能拓撲結構。

1 性能拓撲結構探測

分布式應用所需要的網(wǎng)絡信息主要突出以下兩點：①性能測量值，如帶寬、時延和丟包率（端到端的），反映分布式應用通信效率問題;②拓撲結構，能夠展示資源之間的相互連接關系，也能夠反映出數(shù)據(jù)傳輸是否具有共享路徑的問題。

網(wǎng)絡性能劃分方法的一個基本原則是，要使劃分到同一個集合中的邊緣節(jié)點具有相同的特性，包括集合成員之間的帶寬特性一致和集合成員對外帶寬特性一致。與此同時，集合成員之間的連接關系也必須進行探測，因為在多數(shù)據(jù)傳輸時，共享路徑也明顯影響著應用系統(tǒng)的性能。

利用端到端的網(wǎng)絡測量探測性能拓撲結構是較為實用的方法。端到端的性能測量可以使用現(xiàn)有的各種成熟的測量方法和測量工具，而不需要特殊的配置和權限。文獻[3]中研究各種性能測量工具時顯示，選擇正確測量工具有利于提高測量精度；文獻[4]的研究也指出在應用層能夠?qū)τ行掃M行準確建模。

網(wǎng)絡性能的分布通常具有相對集中性。各個學校、部門等內(nèi)部網(wǎng)絡性能相對較高（如帶寬、丟包率、時延），而區(qū)域與區(qū)域之間的網(wǎng)絡性能相對較差。網(wǎng)絡性能也往往具有相關性，如端到端時延等于各路徑時延之和，是隨路徑單調(diào)遞增(至少不減)的函數(shù)。在本文中，首先利用對瓶頸帶寬的測量高效地將一個一般網(wǎng)絡劃分成若干個子集合，并且滿足某些最優(yōu)目標，如測量點最少；然后再通過性能相關性探測各個子集合，構造出完整網(wǎng)絡性能拓撲結構。

1.1 測量瓶頸鏈路分組劃分

盡早自動對集合進行劃分，有利于減少測量次數(shù)提高探測準確度。當一個集合外節(jié)點與集合內(nèi)節(jié)點之間帶寬性能小于集合內(nèi)帶寬性能時，就可以將這個節(jié)點排出劃分到該集合之內(nèi)；當一個集合外節(jié)點與某一個集合內(nèi)節(jié)點之間的帶寬性能大于集合內(nèi)帶寬性能時，就可以將該集合內(nèi)節(jié)點脫離該集合。

網(wǎng)絡測量工作組織[5](Network Measurements Working Group，NMWG)參考文檔顯示，端到端網(wǎng)絡帶寬相關的幾個常用特性為吞吐量、批量數(shù)據(jù)傳輸能力、帶寬容量和有效帶寬。從這些特性中派生出兩個最常用的網(wǎng)絡特性，即瓶頸帶寬和帶寬利用率。瓶頸帶寬與端到端帶寬容量是等價的，而帶寬利用率為已用帶寬與帶寬容量的比值。它們之間的關系進一步表示如下：設H為路徑P上的跳數(shù)(鏈路數(shù))，C_i為鏈路i的帶寬容量，C0為發(fā)送者的傳輸能力，那么該路徑的帶寬容量為

批量數(shù)據(jù)傳輸能力(Bulk-Transfer Capability，BTC)為網(wǎng)絡在一定時間內(nèi)，持續(xù)TCP傳輸?shù)耐掏铝俊嶒烇@示，BTC測量結果會比實際有效帶寬高出20%—30%。但是，BTC反映的是應用在實際運行過程中所能獲得的最大帶寬，它能夠最大程度地反映分布式應用在實際運行過程中網(wǎng)絡的性能情況。利用端到端的分布式測量判斷多條路徑中存在瓶頸帶寬[6]。具體過程如圖1所示，三個節(jié)點由路由器相連，選擇其中兩個（S₁，S₂）為數(shù)據(jù)源，一個數(shù)據(jù)接收者D。兩個數(shù)據(jù)源到數(shù)據(jù)接收者的路徑上存在共享路徑。在測量和推論中使用如下兩個規(guī)則：

規(guī)則1 如果S₁—D路徑上的帶寬大于S₂—D路徑上的帶寬，S₂—D之間的瓶頸鏈路必須在非共享部分。

規(guī)則2 兩條路徑的帶寬相同。最大的可能性就是瓶頸鏈路存在于它們的共享路徑部分。注意到，這種規(guī)則可能會得出錯誤的結論。如果兩者的瓶頸鏈路存在于非共享部分且相等，那么測量出來的結果也會一樣。此時，可以重新選擇數(shù)據(jù)源和數(shù)據(jù)接收者，并使用規(guī)則1和規(guī)則2進行判斷。

采用分布式動態(tài)機制，節(jié)點可以任意加入或退出分布式系統(tǒng)。對于每一個節(jié)點，其初始帶寬門限值為0，并屬于只含有節(jié)點本身的集合。隨著各個節(jié)點之間的動態(tài)發(fā)現(xiàn)和兩兩調(diào)度測量，每一個節(jié)點能夠獨立進行分組劃分。如下算法詳細地說明了在進行帶寬測量之后分組劃分的情況。

1.2 分析性能相關性拓撲探測

測量瓶頸鏈路不可以將帶寬性能相同的節(jié)點排出集合。如圖2所示，若A，B與C節(jié)點之間的帶寬相同，將可能存在兩種組合情況，或者成為A，B的兄弟節(jié)點，或者與A，B父節(jié)點結合。因此，在帶寬性能相同的集合中，需要進一步分析。利用網(wǎng)絡性能相關性，可以判斷出哪些節(jié)點之間存在高度聯(lián)系，共享同一個路由節(jié)點。

該性質(zhì)可以分析潛在的拓撲結構。如圖2所示，對于任何節(jié)點i∈R/{A，B}相關系數(shù)θ_A，B將會大于θ_i，A。說明在邏輯拓撲結構中，A和B節(jié)點具有同一個父節(jié)點。利用這一性質(zhì)，就可以采用自底向上的合并算法分析出完整的拓撲結構[2]。對發(fā)送者S，設LS為相關接收者按各自測得的丟包率從大到小排序。通常的想法是，若兩個接收者共享的路徑越多，相應的丟包率也就接近，這兩個接收者就應該屬于同一個父節(jié)點。這種推測，假設了各個路徑丟包率是接近的。若r₁-r₂具有高的丟包率，那么就可以明顯看出A和B之間具有相同的較高的丟包率；若r₁-r₂具有較低的丟包率，而r₁-C之間的丟包率又較高，那么得出的結論可能就是A，C之間的丟包率與A，B之間的丟包率相同。

對于每一個邊緣節(jié)點都存在從該節(jié)點角度出發(fā)的一個樹型結構。若節(jié)點之間的路由對稱，那么可以認為不同節(jié)點看到的拓撲結構等價。假設在一定時間內(nèi)，各條路徑上的丟包率存在空間獨立性，那么在同一拓撲結構下，可以得出不同角度的性能分布情況。

不同接收者之間因為有共享路徑而存在相關性，而相關性的大小取決于實際路徑的具體情況，具有隨機性。事實上，上述測量只有S到r₁這段路徑被三個接收者所共享，若r₁到C之間的丟包率較高，就只能顯示出相對較低的相關性。反過來，若以C作為發(fā)送者，那么C與r1之間這段路徑的丟包率就可以表示S，A和B三者之間較高的相關性。

如圖3所示，各個路徑標注了相應的丟包率，對于各個節(jié)點，可以用各條路徑丟包率乘積表示其丟包率（為表示方便，乘積越小最終丟包率越大）。從每一個節(jié)點的角度出發(fā)，得出不同性能視圖。從圖3(d)可以看出，以C節(jié)點為根節(jié)點，其他節(jié)點所得出的丟包率最大，表示其他節(jié)點之間存在一條相關性較大的路徑，因此首先將C節(jié)點單獨劃分出來。

2 試驗

這一節(jié)，用OMNeT++[7]模擬工具，實現(xiàn)以上拓撲探測方法。在試驗中，探測流量由邊緣節(jié)點發(fā)出。與此同時隨機產(chǎn)生流量（FTP，Telnet）造成排隊時延模擬實際環(huán)境。為了分析本文中所使用方法的效率，模擬了在不同節(jié)點個數(shù)條件下性能拓撲發(fā)現(xiàn)的情況，統(tǒng)計其測量次數(shù)，以及測量時相互干擾的程度。結果顯示，優(yōu)先進行分組劃分能夠在很大程度上減少測量次數(shù)，單一化第二步進行相關性測量節(jié)點集合的性能參數(shù)，提高測量準確度。但是，利用測量瓶頸帶寬排出非集合節(jié)點算法中，非集合節(jié)點被排出的先后具有隨機性。因為在實際分布式應用系統(tǒng)中，節(jié)點加入或離開是動態(tài)的，對于每一個節(jié)點它所發(fā)現(xiàn)的相鄰節(jié)點先后存在任意性。圖4顯示了生成樹型拓撲結構時性能參數(shù)值的相關性情況。若發(fā)送數(shù)據(jù)包增加，相應接收者的丟包樣例數(shù)也相應增加，意味著不同接收者之間代表共享路徑的相關性逼近它的真實值。同時也顯示出，不同節(jié)點數(shù)情況下，隨著丟包樣例的增加，探測到真實網(wǎng)絡拓撲結構的概率是收斂的。圖5為利用OMNeT++工具生成的拓撲結構。

3 結論

網(wǎng)絡性能往往是分布式應用的一個重要瓶頸。不但節(jié)點之間帶寬、時延、丟包率等單一的性能值對應用產(chǎn)生影響，全局網(wǎng)絡性能分布對應用的優(yōu)化部署，性能預測也起到重要作用。考慮到實際測量中所用到具體測量技術及效率問題，本文提出以瓶頸帶寬進行集合劃分以及網(wǎng)絡性能相關性對節(jié)點樹型結構劃分結合使用的方法，盡早排出非集合節(jié)點，減少了測量次數(shù)；利用網(wǎng)絡性能相關性，可以對網(wǎng)絡內(nèi)部結構進一步劃分，降低對網(wǎng)絡性能的消耗。

如何有效地利用兩種劃分方法在實際操作過程中還存在一定問題。性能相關性拓撲劃分是在節(jié)點之間有效帶寬性能穩(wěn)定的前提條件下的進一步劃分。如何準確地判斷網(wǎng)絡穩(wěn)定性，及時進行下一步劃分操作問題還有待進一步研究。

本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。