Managing End-to-End Network Performance via Optimized Monitoring Strategies
Tóm tắt
To predict the delay between a source and a destination as well as to identify anomalies in a network, it is useful to continuously monitor the network by sending probes between all sources and destinations. Some of the problems of such probing strategies are: (1) there is a very large amount of information to analyze in real time; and (2) the probes themselves could add to the congestion. Therefore it is of prime importance to reduce the number of probes drastically and yet be able to reasonably predict delays and identify anomalies. In this paper we formulate a graph-theoretic problem called the Constrained Coverage Problem to optimally select a subset to traceroute-type probes to monitor networks where the topology is known. To solve this problem, we develop a heuristic algorithm called the Constrained Coverage Heuristic (CCH) algorithm, which works in polynomial time, as an alternative to the standard exponential-time integer programming solution available in commercial software. The application of the Constrained Coverage Problem to randomly generated topologies yielded an 88.1% reduction in the number of monitored traceroute-type probes on average. In other words, networks can be successfully monitored using only 11.9% of all possible probes. For these examples, the polynomial time CCH algorithm performed remarkably well in comparison to the standard exponential time integer programming algorithm and obtained the optimal (in 24 of 30 examples) or near optimal (second best solution in the remaining examples) solutions in a comparatively negligible amount of time.
Tài liệu tham khảo
R. Govindan and A. Reddy, An analysis of internet inter-domain topology and routing stability, An analysis of internet inter-domain topology and routing stability, Proceedings of the 16th IEEE INFOCOM' 097 Annual Joint Conference of the IEEE Computer and Communications Societies, 2, pp. 850–857, 1997.
V. Paxson, End-to-end routing behavior in the Internet, IEEE/ACM Transactions on Networking, Vol. 5, No. 4, pp. 601–615, 1997.
V. Paxson and S. Floyd, Wide-area traffic: The failure of Poisson modeling, IEEE/ACM Transactions on Networking, Vol. 3, No. 3, pp. 226–244, 1995.
K. Thompson, G. J. Miller, and R. Wilder, Wide-area Internet traffic patterns and characteristics, IEEE Network Magazine, Vol. 11, No. 6, pp. 10–23, 1997.
N. Jamison, et al., VBNS: not your father's Internet, IEEE Spectrum, Vol. 35, No. 7, pp. 38–46, 1998.
K. Varadhan, D. Estrin, and S. Floyd, Impact of network dynamics on end-to-end protocols: Case studies in TCP and reliable multicast, Third IEEE Symposium on Computers and Communications, ISCC'98, pp. 147–153, 1998.
R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: Theory, Algorithms, and Applications, Prentice Hall, New York, 1993.
H. C. Ozmutlu, N. Gautam, and R. Barton, Zone recovery methodology for probe-subset selection in end-to-end network monitoring, submitted to NOMS'02.
G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, J.Wiley, New York, 1988.
M. S. Bazara, J. J. Jarvis, and H. D. Sherali, Linear Programming and Network Flows, Second Edition, J. Wiley, New York, 1990.
http://www.vbns.net/
H. C. Ozmutlu, N. Gautam, and R. Barton, Random-hop approach for network topology generation, submitted to IEEE/ACM Transactions on Networking, 2001.
A. L. Barabasi and R. Albert, Emergence of scaling in random networks, Science Vol. 286, pp. 509–512, 1999.
D. J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness, Princeton University Press, 1999.
http://www.ngnet3.net/
http://www.ucaid.edu/abilene/
http://www.advanced.org/