網絡測量中的一種優化路徑算法
2009-01-01 00:00:00戴飛軍時云峰劉飛羅平
計算機應用研究 2009年1期
（1.江南計算技術研究所， 江蘇 無錫 214083； 2.清華大學 計算機科學與技術系， 北京 100084）
摘 要：為了了解網絡行為、更多地掌握網絡流量情況和盡量多地測量信息，網絡測量已成為重要的手段之一。從分析主動網絡測量存在現狀入手，結合測量模型研究分析，提出了一種優化路徑算法，即二分步算法， 并給出了一種二分步近似算法，從而大大降低了測量代價。
關鍵詞：主動測量; 網絡測量; 分布式; 路徑算法; 二分步算法
中圖分類號：TP393.06 文獻標志碼：A
文章編號：10013695(2009)01008804
Path optimizing algorithms in network measurement
DAI Feijun1， SHI Yunfeng2， LIU Fei1， LUO Ping2
(1.Jiangnan Institute of Computing Technology， Wuxi Jiangsu 214083， China; 2.Dept. of Computer Science Technology ， Tsinghua University， Beijing 100084， China)
Abstract:In order to understand network behaviors and master more information of network traffic and measurement，network measurement has become an important method. Beginning with the analysis of actuality of active network measurement，and combining with the research and analysis of measured models， this paper presented a path optimizing algorithm “2step algorithm”，and brought out a 2step approximate algorithm， which greatly reduced the measuring cost.
Key words：active measurement; network measurement; distributed; path algorithm; 2step algorithm
近些年來，由于Internet呈爆炸性地增長，人們會經常遇到網絡擁塞和服務質量低等問題，因此加強網絡管理已成為當務之急。而了解網絡行為，更多地掌握網絡流量情況和盡量多地測量信息，網絡測量無異成為重要的手段之一，因此網絡流量的測量與分析一直為人們所關注。我國網絡的發展起步較晚，20世紀90年代初才引入Internet，大規模的快速發展于90年代末，近年來隨著 Internet 網絡的發展，我國已成為世界上Internet用戶第二的國家。隨著網絡流量的成倍增加，需要解決流量的監測、預測和網絡規劃的問題。我國的一些大的ISP和網絡規劃及運營商也在進行網絡流量測量、網絡行為、性能分析這方面的工作，正逐步縮小與國外的差距。
網絡測量分為主動測量和被動測量兩種方式。主動測量是通過主動產生流量直接測量網絡的屬性，但是會對被測網絡流量的性能產生負面的影響。因此，主動測量系統開發需要仔細考慮對網絡實際傳輸流量的影響。被動測量完全取決于被測網絡中目前已有的流量，其最大優點是在測量期間不影響被測網絡的流量，但會引起測量、分析、存儲等資源短缺的問題。
1 主動測量方法和面臨問題
主動測量方式是通過向目標鏈路或目標節點發送探測包來測量鏈路或端到端的延遲、帶寬和丟包率等網絡性能參數。主動測量主要有兩種，一是可以引起網絡部件的特殊響應(如ping、Traceroute等工具)，另一種是用于觀測網絡的性能(如Treno等工具)。主動測量給網絡增加潛在的荷載負擔，特別是如果沒有仔細設計使得該方法產生的流量最小，那么附加的流量會擾亂網絡，影響分析結果。例如為了測量在IP 網絡中瓶頸鏈路的帶寬，定期地向網絡發送巨大的TCP 傳輸，由此產生的附加流量可能會引起不良效應，并使測量的網絡吞吐量低于實際瓶頸鏈路的帶寬。主動測量至少需要多個網絡部件以某種形式的參與，如使用ping 估計主機A到主機B的RTT（往返時延），需要主機B響應ICMP請求信息。網絡拓撲結構的變化需要使用主動測量技術，CAIDA開發的Skitter 動態測量工具可用于動態發現和繪制全球Internet 拓撲。另外主動測量技術可以探測網絡的具體問題，如發現許多Internet 端到端的延遲分布具有重尾特征等。
主動測量方式通過發送測量包來獲取網絡性能數據。它可以獲知用戶感興趣的端到端的網絡狀況和網絡行為，通常不需要多個節點之間的協作，因此具有靈活方便、可操作性強等優點。例如，用ping命令可以獲得回路延遲和丟包率等性能參數；用Traceroute工具可以獲得網絡路由信息。主動測量通過分析探測數據包和響應數據包來獲得相應的性能參數，不會捕獲網絡中現有的流量，因此不會對網絡用戶信息的隱私和安全造成威脅。在研究者進行大規模網絡測量的初期或滿足網絡用戶日常的測量需求時，主動測量是一種快速有效的方式。
基于主動測量的網絡透視是當前研究的一個熱點，有CAIDA和Usvrycor等許多基于主動測量的研究項目，開展針對Internet特性的研究和網絡測量、分析、可視化工具的研發，同時也有不少針對網絡測量框架的研究，幫助ISP監控網絡性能，為用戶提供更好的服務。主動測量的代價主要包括部署代價和測量代價兩個部分。有大量的文章研究如何部署盡量少的測量站去獲取全網的性能參數。Bejearno和Walz分別提出了基于一個測量站(或稱為網絡操作中心)的測量解決方案。為了檢測不在路由樹上的鏈路，測量站利用IP源路由選項來指定探測包的路由路徑。但是基于安全考慮，路由器一般禁止IP源路由選項，所以單點測量并非普遍適用的測量方案；另外從收集代價來考慮，單點測量可能會引起測量站節點或相鄰鏈路的過載。目前更多的研究是集中于部署多個測量站的分布式測量方案。
為了測量和監測網絡流量和鏈路帶寬，這些測量工具周期性地查詢和收集網絡數據報文和流量數據。但是頻繁的查詢會嚴重影響路由器的性能，測量工具發送的大量主動探測包也會產生額外的網絡流量，影響網絡的性能。以帶寬測量工具Pathhcar為例，盡管Pahthcar操作簡便、測量準確，而且只需要在測量節點(下文也稱測量站)安裝測量軟件就能準確地測量出每條鏈路的帶寬，但是使用Phathcar進行測量需要消耗大量的網絡帶寬。測量站與目標鏈路之間的距離越大，探測包消耗的鏈路帶寬就會越多。采用分布式主動測量方式進行帶寬測量可以減小測量站與目標鏈路之間的距離，從而有效地減小測量過程對網絡帶寬的影響，降低測量代價。使用測量工具測量鏈路帶寬和延遲時，必須考慮到這些測量工具只能測量包含于測量站的路由樹中的鏈路。為了測量網絡中所有的鏈路，就必須分布式地安裝多個測量站。為了以盡量小的測量代價獲取網絡的全局性能視圖，分布式測量框架就成為主動測量鏈路帶寬和延遲的理想測量模型。確定了測量站以后，需要確定優化的測量分配方案，使得測量網絡中所有鏈路的總測量代價最小。
2 網絡測量的一種優化路徑算法
2.1 一個測量分配實例
下面用網絡實例來分析測量分配的優化問題。為簡單起見，設定網絡如圖1所示。該網絡中包含五個節點，六條鏈路。網絡路由協議采用最短路徑樹協議。從圖1中不難看出，無論選用哪個節點作為測量站，其路由樹都無法覆蓋所有的鏈路。為了方便起見，圖2給出了所有節點的路由樹。
從圖2的路由樹可以看出，任何單獨一個節點都無法覆蓋所有的路由。為了測量所有的鏈路，必須部署多個測量站。同時顯然可見，要構成覆蓋整個網絡的測試站集，至少需要兩個節點。
假設以路由節點a和d為測量站，用兩種方法進行測量計算測量代價。a)先從點a進行測量，并測量a所能測量的所有路徑，然后從d開始測量剩余路徑；b)先從d進行測量，并測量d所能測量的所有路徑，然后從a開始測量剩余路徑。
采用方案a)，從節點a發送的探測包集有m(a，c)=2，m(a，b)=2，m(a，d)=4，m(a，e)=4；從節點d發送的探測包集有m(d，b)=3，m(d，e)=1。所以探測代價之和為16。
采用方案b)，從節點d發送的探測包集有m(d，b)=3，m(d，e)=1，m(d，c)=2，m(d，a)=4；從節點a發送的探測包集有m(a，c)=2，m(a，e)=4，m(a，b)=2。所以探測代價之和為18。
現在的問題是：是否存在其他方法使得總測量代價更小？這就是本文下面要研究的問題，將給出一種二分步算法和二分步近似算法，結果表明該方法得到的總測量代價比這兩種方案要小。
2.2 基本概念
用無向圖G=（V， E）表示被測網絡，其中集合V={v1，v2，…}表示路由器節點，集合E={e1，e2，…}表示鏈路集合。圖中任意兩節點s、t之間的路徑被稱為路由路徑P(s，t)。如果t=s，則表示為P(s，s)。假設路由路徑遵循標準的路由轉發策略，也就是說每個路由節點都根據IP包的目的地址進行轉發，且遵循最優路徑選擇（最小代價選擇）。
為每個路由路徑P(s，t)賦值一個正整數C(s，t)，它表示路由路徑P(s，t)的路由代價。例如圖2中P(a，c)對應的路由代價C(a，c)=2，P(a，d)對應的路由代價C(a，d)=C(a，c)+C(c，d)=4。在下面的分析中，假設所有的路由路徑都是對稱的，即任意兩個節點s、t之間的路由路徑P(s，t)= P(t，s)。
為每個路由路徑P(s，t)賦值一個正整數D(s，t)。D(s，t)表示路由路徑P(s，t)中節點s和t之間的距離向量，規定相鄰兩個節點的距離向量為1，每經過圖中的一個路由節點，距離向量加1。假設WV，則稱U={u｜u∈V， uW，且w∈W，D(w，u)=1}是W的鄰接點，記做Adj（G，W）。
從圖G（V， E）的任一頂點s出發，構造覆蓋所有頂點的路由路徑可以得到一棵以s為根的路由樹T(s)。假設以s為根的一棵路由樹存在一條經過路由節點t的路由路徑P(s，u)，即P(s，u)=P(s，t)+P(t，u)，節點t滿足D(t，u)=1，則稱P(s，t)是P(s，u)基于路由樹T(s)的次路由路徑，定義P(s， t)為P(s， u)的次路徑。
在對網絡進行主動測量時需要設置測量點，每個測量點稱為一個測量站，所有測量站的集合成為測量站集S={s1，s2，…}。
在主動測量中從頂點s到頂點t發送的數據包成為探測包，表示為m(s，t)。假設對每條邊進行測試需要發送兩個包，如以a為測量站，對邊鏈路ce進行測試，需要發送m（a，c）、m（a，e）。對一個被測網絡進行測量所需的最小探測包集合表示為M={m(s，v)｜s∈S，v∈V}。在對一個網絡進行測量時，到當前為止從s發送的所有探測包的集合表示為Ms。
在給定測量站集S={s1，s2，…}的基礎上，測試代價表示為cost（S）=∑m(s，v)∈M C(s，v)。
假設對v∈V，s∈S滿足P（s，v）存在，且P(s，u)為P（s，v）的次路徑，且m(s，v)∈Ms，則聯合路由代價C′(s，v)定義為
C′(s，v）=C(s，u)+C(u，v) m(s，u)Ms
C(s，v) m(s，u)∈Ms
2.3 二分步算法
在文獻[1] 中給出了測量分配問題的整數規劃形式，如果用xs，u表示m(s，u)是否屬于M，ys，u，v表示邊(u，v)是否屬于T(s)，則優化目標表示為
min ∑m(s，u)∈MC(s，u)
滿足的約束條件如下：
對(u，v)∈E，∑s∈Sxs，uxs，vys，u，v≥1;
對u∈V，s∈S，xs，u∈{0，1}；
對u∈V，s∈S，ys，u，v∈{0，1}。
并證明了在此基礎上的測量分配最優化問題是個NP難問題。既然該測量分配問題是NP難的，這就意味著至今尚未找到能在多項式時間內求得一個最優解的算法。就此問題將給出兩種算法，即二分步算法和二分步近似算法。
1）二分步算法
假設該網絡對應的無向圖為G（V， E），令E′=，V′=S，M′=。設路由樹T（i）=（VT， ET），并根據S={s1，s2，…，sm}中每個元素構造路由樹集合{T(s1)，T(s2)，…，T(sm)}。
a)對u∈Adj(G， V′)，如果存在以路由樹T(si) ( i∈[1，n])為圖的路由路徑P(si， u)，則得到P(si，u)；如果存在相應的次路由路徑P(si，u′)，則進一步求得到P(si，u′)。當i取值變化時，可得到一個由路由路徑和次路由路徑組成的集合{( P(s1， u)，P(s1，u′))，(P(s2，u)，P(s2，u′))，…}。
b)求sk，滿足C′(sk，u)=min(C′(s1，u)，C′(s2，u)，…)。
c)將定點u加入到集合V′，將邊u′u加入到集合E′，將m(sk，u)加入到集合M′，如果m(sk，u′)M′，則將m(sk，u′)加入到M′。
d)如果V′=V則轉e），否則返回a)。
e）如果E′=E，則轉j），否則轉f)。
f）對e∈E，且eE′，記e的兩個定點為w1和w2，如果存在路由樹T(si) ( i∈[1，n])，滿足e∈T(si)，則可求得路由路徑P(si，w1)和P(si，w2)。其中P(si，w1)和P(si，w2)中必有一個是另一個的次路由路徑。當i取值變化時，可得到一個由路由路徑組成的集合{(P(s1，w1)，P(s1，w2))，(P(s2，w1)，(P(s2，w2))，…}。
g)求sk，滿足C′(sk，w)=min(C′(s1，w1)， C′(s1，w2)，C′(s2，w1)，C′(s2，w2)，…)。其中w∈{w1，w2}。若路由路徑P(sk，w)對應的次路由路徑存在，則記做P(sk，w′)。其中w′∈{w1，w2}。
h)將邊e加入到E′，且將m(sk，w)加入到M′，如果m(sk，w′) M′，則將m(sk，w′)加入到M′。
i)如果E′=E，則轉j），否則返回f)。
j)結束。
從上面可知算法分為兩部分，其中a）~e）為從測量站集通過最短路徑覆蓋所有節點，即將無向圖G上的所有節點V和測量站集S中的節點連接起來；f）~j）是處理剩余的邊。
該算法的主要思想首先是由測量站集S出發，在其所在路由樹上利用最短路徑原則覆蓋所有節點，當覆蓋完成時最多存在｜S｜個相互獨立的連通圖。假設此時連通圖中所有邊的集合為E′，則｜E′｜個邊被連接起來，其中｜E′｜=（｜V｜-1-（｜S｜-1））=｜V｜-｜S｜，對這些邊平均僅需測量一個點即可。
接下來處理剩余的邊E″，｜E″｜≤(C2｜V｜-｜E′｜)=(C2｜V｜-｜V｜+｜S｜)。由于每個邊有兩個點（假設為節點u、v）確定，每個點按照從測量站集S出發的最短路徑進行計算即可。由于節點u、v所確定的邊（u， v）可能不在同一個路由樹上，只要在計算最短路徑前判斷邊(u，v)是否都在某個路由樹T(si)上即可。
定理 在二分步算法中，假設存在邊（u，v）和 (v， w)均屬于T(s1)，且C(s1，u)＜C(s1，v)＜C(s1，w)，x∈{u，v}，y∈{v，w}，則邊(v， w)被測量站s1測量，且邊（u，v）不被s1測量的充分必要條件是下面的條件均成立：
a）si∈S(i≠1)，滿足C(si，x)＜C(s1，u)， 且邊(u，v)∈T(si)。
b）sj∈S(j≠1)，如果C(sj，y)＜C(s1，u)，則邊(v，w)T(sj)。
證明 假設網絡連接如圖3所示。
（1）充分性證明
因為si∈S(i≠1)，滿足C(si，x)＜C(s1，u)，且邊(u，v)∈T(si)，所以邊(u，v)被測量站si測量，邊（u，v）不被s1測量。
因為sj∈S(j≠1)，如果C(sj，y)＜C(s1，u)，則邊(v，w)T(sj)，所以邊(v，w)必然被s1測量。
(2)必要性證明
由于邊（u，v）不被s1測量，必然si∈S(i≠1)，滿足C(si，x)＜C(s1，u)，且邊(u，v)∈T(si)，否則邊（u，v）將不被s1測量。
由于邊（v，w）被s1測量，對于sj∈S(j≠1)，若C(sj，y)＜C(s1，u)，則邊(v，w)T(sj)，否則將與邊（v，w）被s1測量矛盾。
推論 在二分步算法中，假設存在邊（u，v）∈T(s1)，且C(s1，u)＜C(s1，v)，如果m(s1，v)∈Ms1，則m(s1，u)Ms1的充分必要條件是：
a）si∈S(i≠1)，滿足C(si，x)＜C(s1，u)，且邊(u，v)∈T(si)。
b）sj∈S(j≠1)，如果C(sj，y)＜C(s1，u)，則邊(v，w)T(sj)。
證明 假設在T(s1)上存在點w，滿足P(s1，v)是P(s1，w)的次路由路徑。由于m(s1，v)∈Ms1，邊(u，v)被測量站s1所測量，或邊(v，w) 被測量站s1所測量，或兩個邊均被s1所測量。
如果邊(u，w)被s1所測量，則必有m(s1，u)∈Ms1。如果邊(v，w)被s1所測量，根據上述定理可知邊(u，v)必然被s1測量，除非上述a)b)均被滿足。如果兩個邊均被s1所測量，根據上面論述必有m(s1，u)∈Ms1。如果在T(s1)上不存在點w，滿足P(s1，v)是P(s1，w)的次路由路徑，則邊（u，v）必被s1所測量，所以有m(s1，u)∈Ms1仍然成立，證畢。
根據上述推論可知，如果邊(u，v)∈T(s1)，m(s1，v)∈Ms1，只要a）b）不同時被滿足，則m(s1，u)∈Ms1，此時C′（s，v）= C（s，v），因此在這種情況下可用C（s，v）代替C′（s，v）進行計算。如果滿足a）b），則可以近似地用C（s，v）代替C′（s，v）進行計算，此時僅僅在對路由樹T(s1)上的邊(v，w)（w為T(s1)上v的下一節點）衡量時出現偏差，差值大小為C′(s，w)-C(s，w)=C(s，v)。其實上述條件還是很難滿足的，只有當類似如圖4，5網絡結構出現時才會滿足上述條件。
2）二分步近似算法
假設該網絡對應的無向圖為G（V， E），令E′=，V′=S，M′=。設路由樹T（i）=（VT， ET），并根據S={s1，s2，…，sm}中每個元素構造路由樹集合{T(s1)，T(s2)，…，T(sm)}。
a)對u∈Adj(G， V′)，如果存在以路由樹T(si) (i∈[1，n])為圖的路由路徑P(si ， u)，則得到P(si， u)。當i取值變化時，可得到集合{P(s1，u)，(P(s2，u)，…}。
b)求sk，滿足C(sk， u)=min(C(s1，u)，C(s2，u)，…)。
c)將點u加入到集合V′，將邊(u′，u)加入到集合E′（其中P（sk， u′）為P（sk， u）的次路由路徑），將m(sk，u)加入到集合M′。
d）如果V′=V則轉e），否則返回a)。
e）如果E′=E，則轉j），否則轉f)。
f）對e∈E，且eE′，記e的兩個定點為w1，w2，如果存在路由樹T(si) (i∈[1，n])，滿足e∈T(si)，則求得路由路徑P(si，w1)，P(si，w2)。當i取值變化時，可得到一個集合{P(s1，w1)，P(s1，w2)，P(s2，w1)，P(s2，w2)，…}。
g）求sk，滿足C(sk，w)=min(C(s1，w1)，C(s1，w2)，C(s2，w1)，C(s2，w2)，…)。其中w∈{w1，w2}。
h)將邊e加入到E′，將m(sk，w)加入到M′。
j)如果E′=E，則轉j），否則返回f）。
k）結束
在該優化算法中拋棄了聯合路由代價和次路由路徑的概念，使算法更簡潔。
2.4 算法對比
以2.1節的實例為例。如果以S={a，d}為測量站，則利用上面的二分步算法發送探測包的次序依次是：m(d，e)=1，m(a，b)=2，m(a，c)=2， 此時所有節點都已經完成連接，其測量代價為5。完成的測量圖如圖6所示。
處理剩余的邊為m(d，b)=3，m(d，c)=2，m(a，e)=4，所以得到探測代價為14。可見比2.1節所提出的兩種方案對網絡造成的影響要小。
3 結束語
本文研究了分布式主動測量模型，主動測量的代價包括測量站部署代價和測量代價兩個部分。測量站的數量和位置確定下來以后，為了減少測量代價就需要設計優化的測量分配方案，也就是要確定每條鏈路由哪個測量站來負責測量。由于測量分配問題是NP難問題，目前還沒有很好的方法求解。就此問題本文給出了一個相對比較優化的算法，即二分步算法，并根據這個算法的特點又給出了一個近似算法，使之在計算中更加簡單。
參考文獻：
[1]蔡志平.基于主動和被動測量的網絡測量技術模型和算法研究[J]. 長沙：國防科學技術大學，2005.
［2］牛燕華，任新華，畢經平. Internet網絡測量方式綜述[J]. 計算機應用與軟件，2006，23（7）：1113.
[3]陳鶯，陳曉民. IP網絡測量技術的實現與應用[J]. 電信技術，2003(2):1821.
[4]仇小鋒，陳鳴.基于網絡測量系統的SYN flooding攻擊防御機制[J]. 電信學報，2004，20(1):1217.
[5]李霞，任益芳.網絡測量分析[J]. 科技信息，2006（8）：125128.
[6]呂軍，李星.網絡測量分析及研究綜述[J]. 計算機工程與應用，2003，39（24）：1922，44.
[7]潘飛，高嶺.網絡測量及其關鍵技術[J]. 計算機技術與發展，2006，16（7）：99101.
[8]李麗，周文業，夏春和. 網絡測量技術研究[J]. 科技導報，2006，24(5):9093.
