王 黎，張潤生

（中國電子科技集團公司第五十四研究所，石家莊 050081）

Technology Study

基于最大似然的網(wǎng)絡拓撲推斷技術研究（一）

王 黎，張潤生

（中國電子科技集團公司第五十四研究所，石家莊 050081）

本文針對基于主動探測的網(wǎng)絡拓撲推斷問題，提出了基于廣義似然比的拓撲推斷技術，仿真結果表明，該算法有較高的拓撲推斷精度。

網(wǎng)絡分析；拓撲結構；拓撲推斷；最大似然

1 引言

本文以網(wǎng)絡拓撲探測為出發(fā)點，將網(wǎng)絡限定為規(guī)模較小的IP網(wǎng)絡，假設探測節(jié)點已接入目標網(wǎng)絡，探討此情景下基于最大似然的網(wǎng)絡拓撲推斷問題。提出了一種基于子樹序貫合并的網(wǎng)絡拓撲推斷算法，首先將每個葉子節(jié)點都作為一顆子樹，由最大似然算法估計各個子樹之間的相關性，取其中相關性最大的兩顆子樹；然后應用廣義似然比假設檢驗算法來判斷兩子樹的合并方式并對其進行合并；接著對合并后的子樹集合重復以上過程直至子樹集合中只有一顆樹為止。該算法使用似然比方法合并子樹，無需設置懲罰參數(shù)，具有更高的穩(wěn)健性。

2 拓撲推斷模型

樹狀網(wǎng)絡拓撲可建模為有向邏輯樹[8，9]T，令T=(V,E)，V為樹中的頂點集合，對應于網(wǎng)絡中的主機、路由器等，V由根節(jié)點s、葉子節(jié)點集合D（其葉子節(jié)點個數(shù)為Nr=|D|）以及內(nèi)部節(jié)點集合I構成；E為邊集合，對應于網(wǎng)絡中的通信鏈路。令樹根節(jié)點s為源節(jié)點，樹的葉子節(jié)點集合D為接收節(jié)點。令U=sUD為端節(jié)點，易得U中所有節(jié)點的度都為1（假設每個端節(jié)點僅與一個路由器相連）。該邏輯樹[10]中除根節(jié)點之外的所有非葉子節(jié)點均至少有兩個孩子節(jié)點，除根節(jié)點之外的所有節(jié)點v∈IUD均有惟一的父節(jié)點f(v)；令(f(v),v)，f(v)，v∈V表示v與其父節(jié)點之間的鏈路；令(s,v)為根節(jié)點s與節(jié)點v之間的鏈路；令a(i,j),i≠j,i,j∈D為節(jié)點對{i,j}最深（距根節(jié)點最遠）的公共父節(jié)點，可見a(i,j)為源節(jié)點s到節(jié)點對{i,j}的分支節(jié)點；令p(i,j)為{(s,i),(s,j)}的共享鏈路，即P(i,j)=(s,a(i,j))。

定義葉子節(jié)點的相關性為γij=￥(P(i,j))，￥(P(i,j))表示節(jié)點對{i,j}共享鏈路上的某種性能的度量（排隊時延方差、丟包率方差等），滿足￥(P(i,j))∝P(i,j)，可見拓撲樹中葉子節(jié)點對的共享鏈路越長，相關性越大。葉子節(jié)點相關性滿足以下條件[8]：

（1）單調(diào)性：如果P(i,j)是P(k,l)的子鏈路，其中，i,j,k,l∈D且i≠j,k≠l，則有γij＜γkl。

（2）一致性：如果P(i,j)與P(k,l)為相同鏈路，即a(i,j)=a(k,l)，其中，i,j,k,l∈D且i≠j,k≠l，則γij=γkl。

定理1：集合A={γij,a(i,j)=p;i,j∈D;i≠j}與集合B={γik,a(i,k)=q;i,k∈D;i≠k}中元素數(shù)值相等的充要條件是內(nèi)部節(jié)點p和節(jié)點q為樹狀拓撲中的同一內(nèi)部節(jié)點，即p=q。

證明：由于集合A中元素都是具有相同父節(jié)點的葉子節(jié)點之間的相關性，因此A中各個元素數(shù)值相等，同理B中各個元素的數(shù)值也相等，因此要證明A與B中各個元素的數(shù)值都相等，只需證明γij=γik即可。首先證明充分性，p=q即a(i,j)=a(i,k)表明由源節(jié)點s到節(jié)點對{i,j}的共享鏈路(s,a(i,j)與s到節(jié)點對{i,k}的共享鏈路(s,a(i,k))為同一鏈路，又由于節(jié)點相關性的大小由節(jié)點對的共享鏈路長度決定，因此可得γij=γik。再證明必要性，反證法，假設γij=γik，p≠q，即a(i,j)≠a(i,k)，由于p，q分別為源節(jié)點s到{i,j}和{i,k}的分支節(jié)點，那么p，q都位于鏈路(s,i)上，又由于p≠q，則鏈路(s,p)的長度不等于鏈路(s,q)的長度，即由源節(jié)點s到節(jié)點對{i,j}的共享鏈路(s,a(i,j))的長度與s到節(jié)點對{i,k}的共享鏈路(s,a(i,k))的長度不相等，那么可得節(jié)點對{i,j}的相關性不等于節(jié)點對{i,k}的相關性，即γij≠γik，與假設γij=γik矛盾，因此若γij=γik必有p=q，證畢。

圖1 樹狀拓撲示意圖

性質(zhì)1[8]：在節(jié)點相關性測量過程中網(wǎng)絡的統(tǒng)計特性平穩(wěn)的條件下，根據(jù)葉子節(jié)點相關性的一致性

推論1：內(nèi)部節(jié)點p和節(jié)點q為樹狀拓撲中的同一內(nèi)部節(jié)點（即p=q）的充分條件是

證明：易得M→∞，Nnorm→∞時，

由推論1可得，我們可以通過檢驗集合A與B的均值是否相等來判斷拓撲中內(nèi)部節(jié)點p和q是否為同一節(jié)點，本文算法正是基于這一思想來判斷子樹的合并方式。

3 基于似然比的子樹合并的拓撲推斷算法

本節(jié)基于廣義似然比檢測通過對子樹序貫合并來推斷樹狀拓撲。文獻[6，9]應用了節(jié)點合并的方法推斷拓撲，但其找到最相關子樹之后都按照二叉樹來合并，這顯然與真實情況相去甚遠。本算法的創(chuàng)新之處在于：分析了最相關子樹的各種可能的合并方式；提出了基于廣義似然比檢測的子樹合并方式判定方法。

3.1 子樹合并

3.1.1 尋找最相關子樹

首先給出子樹相關性的定義，任取兩顆子樹Ti，Tj，二者的葉子節(jié)點集合分別為U和V，葉子節(jié)點個數(shù)分別為K，L，則子樹Ti與Tj之間的相關性定義為

式中，γkl為子樹Ti中的葉子節(jié)點k與子樹Tj中的葉子節(jié)點l的相關性。

定理2：如果序貫合并過程中每次選擇的兩棵子樹{Ti,Tj}均為最相關子樹，則每次子樹合并的合并點（兩樹合并的接觸點）在合并后的樹中僅可能體現(xiàn)為原子樹的根節(jié)點或者原子樹根節(jié)點的父節(jié)點。其中合并點是為合并兩顆子樹而創(chuàng)建的新節(jié)點，如圖2中節(jié)點q。

證明：反證法，不失一般性，我們假設兩子樹的合并點為左子樹Ti根節(jié)點的孩子節(jié)點，如圖2所示，實線表示左子樹Ti，虛線表示右子樹Tj，兩子樹合并點為q，則q為左子樹根節(jié)點i的孩子節(jié)點，那么此時從源節(jié)點s到節(jié)點i的鏈路長度要小于從源節(jié)點s到節(jié)點q的鏈路長度，則可得（1）：子樹b與子樹j的相關性大于子樹a和子樹b的相關性；而又由于序貫合并過程中每次選擇的子樹對{i,j}均為最相關子樹，則可得（2）：子樹b與子樹j的相關性小于子樹a和子樹b的相關性。顯然（1）與（2）矛盾，因此如果滿足序貫合并過程中每次選擇的子樹對{i,j}均為最相關子樹，則每次子樹合并的合并點必為子樹的根節(jié)點或者子樹根節(jié)點的父節(jié)點，而不可能是兩棵子樹根節(jié)點的孩子節(jié)點。

圖2 子樹合并示意圖

給定子樹集合{Tl,l=1,…L}，任取其中兩顆子樹Ti，Tj，二者的葉子節(jié)點集合分別為U和V。子樹Ti所有葉子節(jié)點與Tj所有葉子節(jié)點之間的相關性集合為Γ＝｛γuv，u∈U，v∈V }，u，v分別為子樹Ti與Tj的葉子節(jié)點。由于對于任意u和v，在其待推斷的真實拓撲中具有相同的最深父節(jié)點，所以由定理1得，集合Γ中所有元素都有相同的數(shù)值，定義這個數(shù)值為子樹之間的相關性γij。根據(jù)性質(zhì)1，我們可以認為子樹Ti任意葉子節(jié)點u與Tj的任意葉子節(jié)點v之間的相關性采樣值，n=1,…,N，都服從相同的高斯分布N(γij,σ2)，因此可根據(jù)（1）式估計Ti，Tj的相關性

3.1.2 子樹合并方式

在找到最相關子樹對之后，需要判定子樹的合并方式。兩個子樹的合并可分為三種情況，1）葉子節(jié)點數(shù)目均為1的兩子樹合并；2）葉子節(jié)點個數(shù)為1的子樹與葉子節(jié)點數(shù)不為1的子樹的合并；3）兩個葉子節(jié)點數(shù)目都不為1的子樹的合并。

由定理2可得，在情況1）中子樹的合并方式僅有一種，如圖3所示；情況2）中子樹有四種可能的合并方式如圖4所示；情況3）中子樹也有四種可能的合并方式，如圖5所示。圖中葉子節(jié)點數(shù)不為1的子樹由有兩個葉子節(jié)點的樹代表，實線表示左子樹，虛線表示右子樹。

圖3 情況1的合并方式

圖4 情況2的合并方式

圖5 情況3的合并方式

設左右子樹的根節(jié)點分別為i和j，合并點為q，我們只需確定i，j，q中哪些點為相同的節(jié)點，即可推斷出子樹以哪一種方式合并。對于情況1）只有一種合并方式；對于情況2）只需判斷節(jié)點數(shù)不為1的子樹的根節(jié)點是否與合并點q為相同的節(jié)點即可；對于情況3）我們需要判斷兩個子樹的根節(jié)點是否與合并點q為相同的節(jié)點。例如在情況3）的a方式（圖5）中i，j，q三個節(jié)點為不同的節(jié)點；b中i，q兩點為相同節(jié)點，j為獨立的節(jié)點；c中j，q為相同的節(jié)點，i為獨立的節(jié)點；d中i，j，q三個節(jié)點為相同的節(jié)點。表1給出了情況3）子樹合并與i，j，q節(jié)點之間關系的映射。

表1 合并方式映射關系

接下來，我們只需確定i，j，q三個節(jié)點的關系即可判定出子樹合并方式。由于序貫合并過程中滿足每次選擇的子樹對{i,j}均為最相關子樹，則結合定理2，可得合并點q的等價定義：設左右子樹的葉子節(jié)點集合分別為K，L，?k∈K，?l∈L，滿足a(k,l)=q。則可得節(jié)點q對應的葉子節(jié)點相關性集合為C=｛,a(k,l)＝q；k∈K；l∈L}。i,j對應的葉子節(jié)點相關性集合分別為A=｛,a(m,n)＝i；m,n∈K;m≠n}，B=｛,a(u,v)＝j；u,v∈L;u≠v}。由推論1，我們可知，通過比較集合A，B，C的均值即可判定i，j，q三個節(jié)點的關系，進而根據(jù)表1中的映射關系獲得子樹的合并方式。

我們采用廣義似然比的方法比較集合A，B，C的均值。

由于對于原始待推斷樹狀拓撲，其葉子節(jié)點之間相關性的相對大小關系是確定的（因為要滿足單調(diào)性和一致性），那么在理想情況下葉子節(jié)點相關性的測量值的相對大小也滿足此確定關系，因此，只要保證推斷出的樹狀拓撲中由葉子節(jié)點共享鏈路長度表征的葉子節(jié)點相關性的相對大小關系，與實際中測得的葉子節(jié)點相關性的測量值的相對大小關系一致，即可認為推斷出的拓撲就是待推斷的拓撲。分析我們的推斷過程，由于使用最相關子樹合并，因此在推斷過程中保證了相關性測量值較大的葉子節(jié)點之間的共享鏈路長度大于相關性測量值較小的葉子節(jié)點之間的共享鏈路長度，且合并過程中使用了合適的合并方式，保證了共享鏈路長度相等的葉子節(jié)點有相同的公共父節(jié)點，那么我們可得由最相關子樹合并方法推斷出的保留了葉子節(jié)點相關性的相對大小關系，其推斷出的拓撲就是原始拓撲。（未完待續(xù)）

[1] DONNET D,FRIEDMAN T.Internet topology discovery:a survey[J].IEEE Communications Surveys and Tutorials,2007,9(4):2-15.

[2] ZHANG X,CHRIS P.A survey on selective routing topology inference through active probing[J].IEEE Communications Surveys &Tutorials,2012,14(4):1129-1141.

[3] 姜譽，方濱興，胡銘曾．．大型ISP網(wǎng)絡拓撲多點測量及其特征分析實例[J]．軟件學報，2005,16(5):846-856

[4] COATES M,HERO A III,NOWAK R,YU B.Internet tomography[J].IEEE Signal Process Magazine,2002,19(3):47-65.

[5] 趙洪華，陳鳴．基于網(wǎng)絡層析成像技術的拓撲推斷[J]．軟件學報，2010,21(1):133-146

[6] DUFFIELD N,PRESTI F.Network tomography from measured end-to-end delay covariance[J].IEEE/ACM Transactions on Networking,2004,12(6):978-992.

[7] 李勇軍，蔡皖東，王偉．基于端到端報文丟失的網(wǎng)絡拓撲推測算法研究[J]．通信學報，2007,28(10):85-91

[8] SHIH M F,HERO A.Hierarchical inference of unicast network topologies based on end to end measurements[J].IEEE Transactions on Signal Processing,2007,55(5):1708-1718.

[9] CASTRO R,COATES M.,NOWAK R.Likelihood based hierarchical clustering[J].IEEE Transactons on Signal Processing,2004,52(8):2308-2321.

[10] NI J,XIE H,TATIKONDA S.Efficient and dynamic routing topology inference from end-to-end measurements[J].IEEE/ACM Transactions on Networking,2010,18(1):123-135.

[11] ERIKSSON B,DASARATHY G,BARFORD P.Efficient network tomography for internet topology discovery[J].IEEE/ACM Transactions on Networking,2012,20(3):931-943.

[12] FEI G,HU G.Improving maximum-likelihood-based topology inference by sequentially inserting leaf nodes[J].IET Communications,2011,5(15):2221-2230.

[13] 費高雷．基于單播端到端測量的網(wǎng)絡性能參數(shù)估計方法研究[D]．成都：電子科技大學博士學位論文，2012

[14] 楊京禮，姜守達，魏長安，孫超．一種高效的單播網(wǎng)絡自適應拓撲推測算法[J]．電子學報，2013,41(10):1888-1894

[15] HENRY S,JOHN W W.Probability,Statistics,and random processes for engineers(fourth edtion)[M].New Jersey:Pearson Education Inc,2011.

[16] 現(xiàn)代數(shù)學手冊．隨機數(shù)學卷[M]．武漢：華中科技大學出版社，2000

[17] 周勇，馬昀蓓，謝尚宇，王曉靖．理工科概率統(tǒng)計（原書第8版）[M]．北京：機械工業(yè)出版社，2009

[18] 饒云華，曹陽，楊艷，吳銳．基于Pareto分布的IP骨干節(jié)點輸入通信量模型[J]．計算機科學，2006,33(3):27-28

10.3969/J.ISSN.1672-7274.2016.05.011

TN911 文獻標示碼：A

1672-7274（2016）05-0036-04