Internet中拓扑可视化和时延的研究及其在DNMAI中的实现
|
摘要
随着互联网日益广泛的应用，对网络测量的研究变得越来越重要。论文设计和实现了一种具有良好的可扩展性的分布式网络测量和分析基础架构DNMAI，能够较好地完成对网络性能的测量和分析。文中给出了DNMAI的结构和各功能模块，以及DNMAI的具体实施方式和DNMAI的优点。
论文在DNMAI中实现了端到端时延的测量。在DNMAI中，采用可变数据包长度和数据包类型的测量方法以及采用从数据包的发送端和接收端同时发送数据包的双向测量方式来对端到端时延进行测量。
论文还提出了一种基于A*寻路算法的新的拓扑可视化算法。通过分析研究和实际测试，该可视化算法能够满足拓扑可视化的实时性要求，而且可对含环路的网络进行分析，对于网络拓扑的可视化具有很强的普适性和高效性。
As the applications of Internet become more and more widely, the research on measurement of network performance has been more and more important. This paper designed and implemented the Distributed Network Measurement and Analysis Infrastructure, DNMAI, an infrastructure with good extensibility. DNMAI can measure and analyze network performance preferably. This paper introduced detailedly the infrastructure of DNMAI, implement of DNMAI and advantage of DNMAI.
This paper implemented end to end delay measurement in DNMAI. In the delay measurement, the packet size and the packet type have changed, the packet can be sent from sender and receiver simultaneously.
This paper gives a network topology visualization algorithm based on A* algorithm. Through the topology visualization program has been tested in operational networks, it is reality that this algorithm can meet the real-time requirement of network topology visualization, and solve the problem of loop caused by single topology visualization algorithm, therefore, it's preferably suitable for the research on complicated network topology.
论文在DNMAI中实现了端到端时延的测量。在DNMAI中，采用可变数据包长度和数据包类型的测量方法以及采用从数据包的发送端和接收端同时发送数据包的双向测量方式来对端到端时延进行测量。
论文还提出了一种基于A*寻路算法的新的拓扑可视化算法。通过分析研究和实际测试，该可视化算法能够满足拓扑可视化的实时性要求，而且可对含环路的网络进行分析，对于网络拓扑的可视化具有很强的普适性和高效性。
As the applications of Internet become more and more widely, the research on measurement of network performance has been more and more important. This paper designed and implemented the Distributed Network Measurement and Analysis Infrastructure, DNMAI, an infrastructure with good extensibility. DNMAI can measure and analyze network performance preferably. This paper introduced detailedly the infrastructure of DNMAI, implement of DNMAI and advantage of DNMAI.
This paper implemented end to end delay measurement in DNMAI. In the delay measurement, the packet size and the packet type have changed, the packet can be sent from sender and receiver simultaneously.
This paper gives a network topology visualization algorithm based on A* algorithm. Through the topology visualization program has been tested in operational networks, it is reality that this algorithm can meet the real-time requirement of network topology visualization, and solve the problem of loop caused by single topology visualization algorithm, therefore, it's preferably suitable for the research on complicated network topology.
引文
[1] NLANR. Towards a systemic understanding of the Internet organism: a framework for the creation of a Network Analysis Infrastructure. http://moat.nlanr.net/NAI/. 1998, May 10。
[2] Mark Crovella, Christoph Lindemann, Martin Reiser . Internet performance modeling: the state of the art at the turn of the century, Performance Evaluation. 2000, Sep 29, 42 (2-3). pp 91-107。
[3] Andrew Adams, Jamshid Mahdavi, Matthew Mathis, et. al. Creating a Scalable Architecture for Internet Measurement. http://www.isoc.org/inet98/proceedings/6g/6g_1.htm. 2001, Nov 28。
[4] A. Adams, J. Mahdavi, M. Mathis, et. al.. Creating a Scalable Architecture for Internet Measurement. Proc. of INET98, Geneva. 1998, July。
[5] Vem Paxson, Andrew Adams, Mat Mathis. Experiences with NIMI. Proc. of Passive & Active Measurement. 2000。
[6] 张黎明．网络测量探针定制机制及探针执行环境研究．北京航空航天大学学位论文．2004，2。
[7] 朱畅华，裴昌幸，李建东，彭爱华，肖海云．分布式网络测量与分析基础设施(DNMAI)研究与实现．北京邮电大学学报．2004，3，增．pp 25-31。
[8] 朱畅华，裴昌幸，李建东，彭爱华，肖海云．分布式网络测量与分析基础设施(DNMAI)研究与实现．中国通信学会信息网络2003年会论文集．2003，9，北京．pp 100-106。
[9] plotpaths http://www.caida.org/tools/visualization/plotpaths/
[10] Project Argus-Network topology discovery, monitoring, history, and visualization. http://www.cs.cornell.edu/boom/1999sp/projects/Network%20Topology/topology.html
[11] CS395T: Scientific Visualization http://www.cs.utexas.edu/users/bajaj/vizlecl. htm
[12] Position Paper on Visualization Research Challenges http://visual, nlm. nih. gov/evc/meetings/vrc2OO4/position_papers/m oorhead.pdf
[13] Visualization in network topology optimization http://portal.acm.org/citation.cfm?id=131231 ISBN:0-89791-472-4.
[14] 凌军，曹阳，李莉，黄天锡，顾瑜青基于ARP和SNMP的网络拓扑自动发现算法。武汉大学学报，2001 No．1。
[15] 康华，周明全，房鼎益基于SNMP协议的网络拓扑发现和显示 微机发展 2003 No．7。
[16] 肖海云，裴昌幸，陈南，易运晖基于ICMP和UDP的互联网拓扑发现和可视化研究。西安电子科技大学学报，2003 No．7 PP：29-33．
[17] 劳虎．无废话XML．http://2tigers.net/．2003。
[18] Chee-Yong Chan, Pascal Felber, Minos Garofalakis, et. al.. Efficient filtering of XML documents with XPath expressions. http://citeseer.ist.psu.edu/chan02efficient.html. 2002。
[19] C.-Y. Chan, M. Garofalakis, R. Rastogi. Scalable filtering of XML data for Web services. http://www.bell-labs.com/user/minos/Papers/ic03.pdf。
[20] Yuri Breitbart, Chee-Yong Chan, Minos Garofalakis, Rajeev Rastogi, Avi Silberschatz. Efficiently Monitoring Bandwidth and Latency in IP Networks. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. 2001 vol.2 PP:933-942.
[21] Durresi, A.; Babic, G.; Jain, R.; Measurement of ATM frame latency. 25th Annual IEEE Conference. 2000 PP:614-619.
[22] Eden, A.N.; Job, B.W.; Mudge, T.; Web latency reduction via client-side prefetching. 2000 IEEE International Symposium. 2000 PP: 193-200.
[23] Tianshuang Qiu; Xuan Kong; Kaufrnan, B. Estimation of latency changes of evoked potentials with adaptive phase spectral time delay estimation. Proceedings of the 19thAnnual International Conference of the IEEE. 1997 PP:1522-1525.
[24] 潘乔，裴昌幸，陈南：基于GPS的端到端时延测量方法设计方案．计算机与网络 2003 No．6 PP．134-136．
[25] 何坚强，张焕春，经亚枝：分布式实时控制系统的网络调度研究．西南交通大学学报 2005 No．4 PP：501-504。
[26] 黄晓璐，闵应骅，吴起，网络流量的半马尔可夫模型 计算机学报 2005 No．10 PP：1593-1600．
[27] V. Paxson, End-to-end Internet packet dynamics[J], IEEE/ACM Trans. on Networking, 1999, 7(3), 277-292.
[28] Kouhei Fujimoto, Shingo Ata, Masayuki Murata, "Statistical Analysis of Packet delays in the Internet and Its Application to Playout Control for Streaming Applications" [J], IEICE Trans. On Communications, VoI.E00-B, N0.6, June 2001
[29] Hiroyuki Ohsaki, Masayyuki Murata, Hideo Miyahara, "Modeling End-to-End Packet Delay Dynamics of the Internet using System Identification", Proceedings of Seventeenth International Teletraffic Congress[C], December 2001
[30] Leping Huang, Kaoru Sezaki, "End-to-End Internet Delay Dynamics", 6th Asia-Pacific Conference on Communications (APCC) [C], TSR-15-200006, 2000.11 D
[31] A. Mukherjee, On the dynamics and significance of low frequency components of internet load[J]. Journal of Internetworking: Research and Experience, 5(4):163-205, Dec. 1994.
[32] Qiong Li, David L. Mills, "Jitter Based Delay Boundary Predication of Wide-Area Networks" [J], IEEE/ACM Transactions on Networking ,Vol.9,No.5, Oct. 2001 pp.578-590
[33] Jacobson, V., Berkeley TCP Evolution from 4.3-Tahoe to 4.3-Reno, Proceeding of the Eighteenth Internet Engineering Task Force[C], p.365, University of British Columbia, Vancouver, B.C., 1990
[34] Leping HUANG, Kaoru, SEZAKI, "An Analysis of One-Way Delay using phase plot", IEICE Society Conference 2000[C], B-11-18,Japan, September, 2000
[35] J. C. Bolot, "End-to-End packet delay and loss Behavior in the Internet", In Proceeding ofACM SIGCOMM'93 [C], pp.289-298
[36] Qiong Li, David L. Mills, On the Long-range Dependence of Packet Round-trip Delays in Internet, In IEEE International Conference on Communications (ICC'98) [C], pages 1185-1191, 1998
[37] D. Bertsekas, R. Gallager, Data Networks, Englewood Cliffs, NJ: Prentice-Hall, 1987
[38] S. B. Moon, P. Skelly, D. Towsley, Estimation and removal of clock skew from network delay measurements, Proceedings of 1999 IEEE 1NFOCOM[C], New York, NY, 1999, 227-234
[39] 梁英，王琰．启发式的网络拓扑图生成算法的构造及实现．沈阳工业学院学报．2002，3，21(1)．pp 76-80。
[40] 孟月萍，谭燕秋．计算机网络拓扑图构造技术．河北建筑科技学院学报．1998，3，15(1)．pp 58-61。
[41] 岳昆，王晓玲，周傲英．Web服务核心支撑技术：研究综述．Journal of Software．2004，March，15(3)．pp 428-442。
[42] 杨家海，李星，吴建平．一种基于Web／Java的网络管理系统模型与实现．清华大学学报(自然科学版)．2000，40(5)．pp 118-121。
[43] 小鹰．Windows Sockets网络编程．http://www.vckbase.com/．
[44] 谭浩强，C程序设计．清华大学出版社 1991年7月第一版 PP：157-214。
[45] 钱能，C++程序设计教程．清华大学出版社 1999年4月第一版 PP：204-228 312-314 349-378。
[46] Douglas E. Comer, Internetworking With TCP/IP Vol Ⅰ: Principles, Protocols, and Architectures. 电子工业出版社 2001年5月。
[47] A Van Moffaert ,D De Vleesehauwer, J Janssen. Tuning the VoIP Gateways to Transport International Voice Calls over a Best - Effort IP Backbone [A]. Proceedings of the 9th IFIP Conference on Performance Modelling and Evaluation of ATM&IP Networks2001 [C] .Budapest : IFIP ,2001.
[48] 肖海云，分布式网络测量与分析基础架构(DNMAI)的研究与实现(导师：裴昌幸)，西安电子科技大学硕士学位论文，2005年4月。
[49] 朱畅华，IP网络测量和业务性能研究(导师：裴昌幸)，西安电子科技大学博士学位论文，2005年1月。
[50] 李建东，信息网络理论基础[M]，西安电子科技大学出版社，2001年6月。
[51] 施光燕，董加礼，最优化方法[M]，高等教育出版社，1999年9月
[2] Mark Crovella, Christoph Lindemann, Martin Reiser . Internet performance modeling: the state of the art at the turn of the century, Performance Evaluation. 2000, Sep 29, 42 (2-3). pp 91-107。
[3] Andrew Adams, Jamshid Mahdavi, Matthew Mathis, et. al. Creating a Scalable Architecture for Internet Measurement. http://www.isoc.org/inet98/proceedings/6g/6g_1.htm. 2001, Nov 28。
[4] A. Adams, J. Mahdavi, M. Mathis, et. al.. Creating a Scalable Architecture for Internet Measurement. Proc. of INET98, Geneva. 1998, July。
[5] Vem Paxson, Andrew Adams, Mat Mathis. Experiences with NIMI. Proc. of Passive & Active Measurement. 2000。
[6] 张黎明．网络测量探针定制机制及探针执行环境研究．北京航空航天大学学位论文．2004，2。
[7] 朱畅华，裴昌幸，李建东，彭爱华，肖海云．分布式网络测量与分析基础设施(DNMAI)研究与实现．北京邮电大学学报．2004，3，增．pp 25-31。
[8] 朱畅华，裴昌幸，李建东，彭爱华，肖海云．分布式网络测量与分析基础设施(DNMAI)研究与实现．中国通信学会信息网络2003年会论文集．2003，9，北京．pp 100-106。
[9] plotpaths http://www.caida.org/tools/visualization/plotpaths/
[10] Project Argus-Network topology discovery, monitoring, history, and visualization. http://www.cs.cornell.edu/boom/1999sp/projects/Network%20Topology/topology.html
[11] CS395T: Scientific Visualization http://www.cs.utexas.edu/users/bajaj/vizlecl. htm
[12] Position Paper on Visualization Research Challenges http://visual, nlm. nih. gov/evc/meetings/vrc2OO4/position_papers/m oorhead.pdf
[13] Visualization in network topology optimization http://portal.acm.org/citation.cfm?id=131231 ISBN:0-89791-472-4.
[14] 凌军，曹阳，李莉，黄天锡，顾瑜青基于ARP和SNMP的网络拓扑自动发现算法。武汉大学学报，2001 No．1。
[15] 康华，周明全，房鼎益基于SNMP协议的网络拓扑发现和显示 微机发展 2003 No．7。
[16] 肖海云，裴昌幸，陈南，易运晖基于ICMP和UDP的互联网拓扑发现和可视化研究。西安电子科技大学学报，2003 No．7 PP：29-33．
[17] 劳虎．无废话XML．http://2tigers.net/．2003。
[18] Chee-Yong Chan, Pascal Felber, Minos Garofalakis, et. al.. Efficient filtering of XML documents with XPath expressions. http://citeseer.ist.psu.edu/chan02efficient.html. 2002。
[19] C.-Y. Chan, M. Garofalakis, R. Rastogi. Scalable filtering of XML data for Web services. http://www.bell-labs.com/user/minos/Papers/ic03.pdf。
[20] Yuri Breitbart, Chee-Yong Chan, Minos Garofalakis, Rajeev Rastogi, Avi Silberschatz. Efficiently Monitoring Bandwidth and Latency in IP Networks. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. 2001 vol.2 PP:933-942.
[21] Durresi, A.; Babic, G.; Jain, R.; Measurement of ATM frame latency. 25th Annual IEEE Conference. 2000 PP:614-619.
[22] Eden, A.N.; Job, B.W.; Mudge, T.; Web latency reduction via client-side prefetching. 2000 IEEE International Symposium. 2000 PP: 193-200.
[23] Tianshuang Qiu; Xuan Kong; Kaufrnan, B. Estimation of latency changes of evoked potentials with adaptive phase spectral time delay estimation. Proceedings of the 19thAnnual International Conference of the IEEE. 1997 PP:1522-1525.
[24] 潘乔，裴昌幸，陈南：基于GPS的端到端时延测量方法设计方案．计算机与网络 2003 No．6 PP．134-136．
[25] 何坚强，张焕春，经亚枝：分布式实时控制系统的网络调度研究．西南交通大学学报 2005 No．4 PP：501-504。
[26] 黄晓璐，闵应骅，吴起，网络流量的半马尔可夫模型 计算机学报 2005 No．10 PP：1593-1600．
[27] V. Paxson, End-to-end Internet packet dynamics[J], IEEE/ACM Trans. on Networking, 1999, 7(3), 277-292.
[28] Kouhei Fujimoto, Shingo Ata, Masayuki Murata, "Statistical Analysis of Packet delays in the Internet and Its Application to Playout Control for Streaming Applications" [J], IEICE Trans. On Communications, VoI.E00-B, N0.6, June 2001
[29] Hiroyuki Ohsaki, Masayyuki Murata, Hideo Miyahara, "Modeling End-to-End Packet Delay Dynamics of the Internet using System Identification", Proceedings of Seventeenth International Teletraffic Congress[C], December 2001
[30] Leping Huang, Kaoru Sezaki, "End-to-End Internet Delay Dynamics", 6th Asia-Pacific Conference on Communications (APCC) [C], TSR-15-200006, 2000.11 D
[31] A. Mukherjee, On the dynamics and significance of low frequency components of internet load[J]. Journal of Internetworking: Research and Experience, 5(4):163-205, Dec. 1994.
[32] Qiong Li, David L. Mills, "Jitter Based Delay Boundary Predication of Wide-Area Networks" [J], IEEE/ACM Transactions on Networking ,Vol.9,No.5, Oct. 2001 pp.578-590
[33] Jacobson, V., Berkeley TCP Evolution from 4.3-Tahoe to 4.3-Reno, Proceeding of the Eighteenth Internet Engineering Task Force[C], p.365, University of British Columbia, Vancouver, B.C., 1990
[34] Leping HUANG, Kaoru, SEZAKI, "An Analysis of One-Way Delay using phase plot", IEICE Society Conference 2000[C], B-11-18,Japan, September, 2000
[35] J. C. Bolot, "End-to-End packet delay and loss Behavior in the Internet", In Proceeding ofACM SIGCOMM'93 [C], pp.289-298
[36] Qiong Li, David L. Mills, On the Long-range Dependence of Packet Round-trip Delays in Internet, In IEEE International Conference on Communications (ICC'98) [C], pages 1185-1191, 1998
[37] D. Bertsekas, R. Gallager, Data Networks, Englewood Cliffs, NJ: Prentice-Hall, 1987
[38] S. B. Moon, P. Skelly, D. Towsley, Estimation and removal of clock skew from network delay measurements, Proceedings of 1999 IEEE 1NFOCOM[C], New York, NY, 1999, 227-234
[39] 梁英，王琰．启发式的网络拓扑图生成算法的构造及实现．沈阳工业学院学报．2002，3，21(1)．pp 76-80。
[40] 孟月萍，谭燕秋．计算机网络拓扑图构造技术．河北建筑科技学院学报．1998，3，15(1)．pp 58-61。
[41] 岳昆，王晓玲，周傲英．Web服务核心支撑技术：研究综述．Journal of Software．2004，March，15(3)．pp 428-442。
[42] 杨家海，李星，吴建平．一种基于Web／Java的网络管理系统模型与实现．清华大学学报(自然科学版)．2000，40(5)．pp 118-121。
[43] 小鹰．Windows Sockets网络编程．http://www.vckbase.com/．
[44] 谭浩强，C程序设计．清华大学出版社 1991年7月第一版 PP：157-214。
[45] 钱能，C++程序设计教程．清华大学出版社 1999年4月第一版 PP：204-228 312-314 349-378。
[46] Douglas E. Comer, Internetworking With TCP/IP Vol Ⅰ: Principles, Protocols, and Architectures. 电子工业出版社 2001年5月。
[47] A Van Moffaert ,D De Vleesehauwer, J Janssen. Tuning the VoIP Gateways to Transport International Voice Calls over a Best - Effort IP Backbone [A]. Proceedings of the 9th IFIP Conference on Performance Modelling and Evaluation of ATM&IP Networks2001 [C] .Budapest : IFIP ,2001.
[48] 肖海云，分布式网络测量与分析基础架构(DNMAI)的研究与实现(导师：裴昌幸)，西安电子科技大学硕士学位论文，2005年4月。
[49] 朱畅华，IP网络测量和业务性能研究(导师：裴昌幸)，西安电子科技大学博士学位论文，2005年1月。
[50] 李建东，信息网络理论基础[M]，西安电子科技大学出版社，2001年6月。
[51] 施光燕，董加礼，最优化方法[M]，高等教育出版社，1999年9月