孔 玲，趙永祥

（北京交通大學 電子信息工程學院，北京 100044）

為了滿足國家執(zhí)法機構的有關要求和用戶提出的需求，運營商和設備制造商在通訊網絡中引入了合法監(jiān)聽技術。

合法監(jiān)聽技術主要通過國家的授權執(zhí)法機構根據用戶的監(jiān)聽標識向通訊網絡中的各網元進行布控，然后各布控網元收集該用戶的相關通訊信息和通訊內容，并上報給執(zhí)法機構，執(zhí)法機構再在反饋的消息中選擇需要的信息進行分析和利用，這樣不但可以保證用戶信息的保密性又滿足了國家執(zhí)法機構對通訊信息的可控性和可知性的要求[1~2]。

監(jiān)控網絡中的流量對確保網絡正常運行至關重要, 有報告指出，網絡中的流量幾乎每兩年增加一倍[3]。這無疑大大增加了每個監(jiān)聽設備的任務量。現考慮用多核路由器實現監(jiān)聽功能，網絡中每條流經過路由器最終到達目的端，把每個路由器看成一個監(jiān)控點，由于一條流可能流經多個路由器和流量到達的隨機性，如何在網絡中分配每個路由器的監(jiān)聽任務，避免有的節(jié)點超負荷工作，而有的節(jié)點長期處于空閑狀態(tài)，成為我們研究的重點。

1 相關研究

一般情況，在流級別的基礎上，有兩種原則來決定哪個節(jié)點來執(zhí)行監(jiān)控任務。

1.1 先到原則

把數據流最先到達的節(jié)點作為監(jiān)控該條流的監(jiān)控點，如圖1中，f low1最先經過moni tor 0（以下簡稱m0），那么就讓m0監(jiān)控f l ow1，m1，m2空閑。這樣做的好處是節(jié)省了決定的時間，然而帶來的弊端也是明顯的，若很多條流到達的第1個節(jié)點均是m0，勢必導致m0任務超重，而其他節(jié)點卻空閑的情況。

1.2 最閑原則

分析數據流所經過的所有節(jié)點，選擇一個當前負載最小的節(jié)點來監(jiān)控該條流。這樣的分配方式只是簡單的平衡了各節(jié)點的負載，但由于流量的隨機性，采用此方法并不理想。同樣，在圖1中，f low1的速率為10 packet/s，在m0 ，m1，m2均空閑的前提下，隨機選擇m0監(jiān)聽f low1，則m0的負載變?yōu)?0。f low2的速率為1 000 packet/s，此時m0的負載為10，而m1，m3，m4，m6均為0，那么在后面4個節(jié)點中隨機選擇m1監(jiān)聽f low2，則m1的負載變?yōu)? 000。從整個網絡來看，f low1都經過m0，m1，但這2個節(jié)點的負載卻相差很大，并沒有到達很好的均衡負載的目的。

圖1 數據流分別以不同速率流經監(jiān)控節(jié)點

以上2種原則，都是在流級的基礎上分配任務的，但是實際網絡中流量分布不均勻，即使流分配均勻了，這些方法分配在不同節(jié)點上的監(jiān)聽負載是不均勻的。例如，3個流，速率分別為1 000，10，10，這3個流分別分配給3個節(jié)點監(jiān)聽。那么負責第1個流的節(jié)點負載要遠遠大于其它2個節(jié)點。根據這個特點，本文提出均值法，一種在分組的基礎上分配監(jiān)聽任務的算法，使每個節(jié)點的負載盡可能均衡。

2 算法闡述

2.1 基本思想

首先假定數據流經過的最后1個節(jié)點監(jiān)聽該流，從流量最大的數據流開始，總流量除以節(jié)點總個數所得到的平均值就是該流路上每個節(jié)點所應承擔的負載量，把假定在最后一個節(jié)點上的任務往前分擔給流路上的其他節(jié)點。按此原則依次迭代優(yōu)化每條數據流。還是在圖1中，f low1，f low2的流量分別是10 packet/s，1 000 packet/s，那么首先優(yōu)化f low2，在該流路上，均值為1 000/5=200，則應把假定在m5上的負載平分給前面的節(jié)點，使該流路的上每個節(jié)點的任務量均為200。接著優(yōu)化f low1，由于m0 ，m1的負載變?yōu)?00，均比m2的負載10大，所以無需再把m2上的負載分擔給m0，m1。作上述處理后，避免了最閑原則中，f low1都經過m0，m1，但這兩個節(jié)點的負載卻相差很大的情況，從整個網絡來看，盡管不同數據流之間的流量差異度很大，節(jié)點間的負載卻沒有相差很多。

2.2 均值法算法

（1）在初始化中都假設讓數據流經過的最后一個節(jié)點監(jiān)聽該流，這樣做的目的是確保每條流都有一個節(jié)點對其監(jiān)聽。

（2）首先找出網絡中流量最大的數據流，將其最后一個節(jié)點的任務量往前分配給該流路上的其余節(jié)點。接著找出流量次大的數據流，做同樣操作。

（3）由于知道數據流經過的節(jié)點數，就可以通過平均計算得出該條流上每個節(jié)點應該承擔的監(jiān)聽量；若流路上最后一個節(jié)點的任務量比前面節(jié)點的都小，該流路不做處理；若最后一個節(jié)點的上游某節(jié)點的監(jiān)聽任務量比計算出的均值還大，代表該上游節(jié)點本身任務已經很重，不適合分擔其任務，此時不考慮該上游節(jié)點，重新計算均值；若最后一個節(jié)點的任務量比計算出來的均值大，代表該節(jié)點的負載很重，不適合分擔該流路的監(jiān)聽任務，把最初假設給它的任務量重新均分到它上游的其余節(jié)點。

（4）依次迭代，直至把網絡中的所有數據流都做上述處理。

均值法是在分組的基礎上平衡數據流上各個節(jié)點的負載，一個節(jié)點不再是唯一的監(jiān)聽某條數據流的節(jié)點，其他節(jié)點空閑，而是該數據流所流經的所有節(jié)點都監(jiān)聽該條流，只不過每個節(jié)點所分配到的任務量不同。

3 實驗仿真

以圖1 為網絡模型，假定f low1，f low2，fow3的流量分別是300 packet/s，600 packet/s，1 200 packet/s，按3種算法得出網絡中各個節(jié)點的負載如圖2。

從圖2中可以看出，先到原則下節(jié)點0和1處于忙碌狀態(tài)，而其余節(jié)點均空閑。最閑原則也存在同樣問題，9個監(jiān)聽節(jié)點有6個處于空閑狀態(tài)。由這兩種算法得到的各節(jié)點的負載非常不均衡。而采用均值法的曲線最為平緩，雖然網絡中各個節(jié)點的負載不完全一樣，但相互間的差異度不大，很好地避免了某些節(jié)點分配到的監(jiān)聽任務超載，而另一些節(jié)點卻輕載的現象。

圖2 流量預先假定時3種算法的節(jié)點負載分布圖

下面以實際的網絡拓撲圖為例，分析一種更普遍的情況。

圖3為澳洲骨干網絡拓撲圖，以此為基礎，從中選取7個點組成的網絡結構作為仿真模型，如圖4。

圖4 網絡結構圖

圖4中任意2個節(jié)點間存在一條數據流，則應有21條流，其中f low =f i j(1≤i＜j,i＜j)。隨機輸入21個值在0到1 000的隨機數代表21條數據流的流量，按3種算法得到網絡中各節(jié)點的負載如表1。

表1 網絡中各節(jié)點的負載

圖5 流量隨機到達時3種算法的負載分布圖

從圖5中可以清晰看出，當流量隨機到達時，采用先到原則和最閑原則進行流量分配，圖中的曲線波動劇烈，在先到原則中，節(jié)點3負載高達2 800，而節(jié)點7負載為0。網絡中各節(jié)點的負載量相差很大；而采用均值法，圖中的曲線波動不大，各節(jié)點的負載均在1 500左右，節(jié)點間的負載得到了有效的平衡，避免了按前2個算法出現的某些節(jié)點超負荷忙碌，而某些節(jié)點長期處于空閑狀態(tài)的情況。節(jié)點3、4作為網絡的中心節(jié)點，負載相對其它邊緣節(jié)點略高，屬正?，F象。一般而言，數據流經過的節(jié)點越多，網絡中節(jié)點連接越緊密，均值法達到的均衡效果越好。

4 結束語

均值法首先假定每條數據流流經的最后一個節(jié)點監(jiān)聽該流，找出流量最大的數據流，再把該流最后一個節(jié)點的負載往它所監(jiān)聽的流路上的其他節(jié)點上分擔，依次迭代，最終達到網絡中所有節(jié)點的負載均衡。該算法經過仿真，與另外2種方法比較，顯示出了很好的均衡性能。接下來的工作重點是在更為復雜的網絡拓撲環(huán)境下，考慮節(jié)點有可能發(fā)生故障，在這樣的前提下驗證均值法的性能，增加其容錯功能。

[1] 王斌斌. WiMax網絡中合法監(jiān)聽業(yè)務的實現[D]. 上海：復旦大學軟件學院，2008.

[2] 魏 亮. 淺析網絡與信息安全應用需求和研究現狀[EB/OL].http://www.edu.cn/20060703/3198117.Shtm l.2007-07-03.

[3] Cisco Systems.Approaching the zettabyte era. [EB/OL].http://www.cisco.com/en/US/solutions/collateral/ns341/ns525/ns537/ns705/ns827/white_paper_cll-481374.pdf”.June 2008.