網(wǎng)絡(luò)流量有效監(jiān)測(cè)點(diǎn)的設(shè)置模型及求解算法研究
Model and Algorithm Research for Seeking Efficient Monitor-Nodes Measuring Network Traffic
-
摘要: 網(wǎng)絡(luò)流量監(jiān)測(cè)點(diǎn)問題可以抽象為圖的最小弱頂點(diǎn)覆蓋問題，而求解最小弱頂點(diǎn)覆蓋問題是一個(gè)NP難題。該文利用圖論中關(guān)聯(lián)矩陣的概念，提出了一個(gè)近似算法, 并分析了算法的復(fù)雜性。在此基礎(chǔ)上將該算法拓展到頂點(diǎn)加權(quán)情況下圖的弱頂點(diǎn)覆蓋問題。理論分析和仿真實(shí)驗(yàn)表明，比較現(xiàn)有的算法，新的算法能夠發(fā)現(xiàn)更小的弱頂點(diǎn)覆蓋集，且具有更好的可擴(kuò)展性。Abstract: The problem of seeking monitor-nodes for measuring the network traffic is regarded as the problem of finding out the minimum weak vertex cover of a graph which is NP-hard. An approximation algorithm is proposed in this paper based on the concept of incidence matrix in Graph. Also the complexity of the algorithm is analyzed. Furthermore, the algorithm is expanded to seek the minimum weak vertex cover for a graph that has weights on the nodes. The theoretical analysis and the simulation results show that the novel algorithm is more scalable than the traditional algorithms, and can find smaller weak vertex cover.
-
Breitbart Y, Chan Chee-Yong, Garofalakis M, Rastogi R, Silberschatz A. Efficiently Monitoring Bandwidth and Latency in IP Networks. Proceedings of IEEE INFOCOM 2001, Anchorage, Alaska, April 2001, vol.2: 933－942.[2]劉湘輝, 殷建平, 唐樂樂, 趙建民. 網(wǎng)絡(luò)流量的有效測(cè)量方法分析. 軟件學(xué)報(bào), 2003, 14(2)：300－304.[3]Vazirani V V. Approximation Algorithms. Berlin, Springer-Verlag, 2001: 93－129.[4]Caceres R, Duffield N G, Feldmann A, et al.. Measurement and analysis of IP network usage and behavior. IEEE Commun-ications Magazine, 2000, 38(5): 144－151.[5]Waxman B M. Routing of multipoint connections[J].IEEE J. on Selected Areas in Communications.1988, 6(9):1617- -
計(jì)量
- 文章訪問數(shù): 2271
- HTML全文瀏覽量: 120
- PDF下載量: 1241
- 被引次數(shù): 0
下載:
