| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Inference and Labeling of Metric-Induced Network Topologies
November 2005 (vol. 16 no. 11)
pp. 1053-1065
Abstract—The development and deployment of distributed network-aware applications and services require the ability to compile and maintain a model of the underlying network resources with respect to one or more characteristic properties of interest. To be manageable, such models must be compact; and to be general-purpose, should enable a representation of properties along temporal, spatial, and measurement resolution dimensions. In this paper, we propose MINT—a general framework for the construction of such metric-induced models using end-to-end measurements. We present the basic theoretical underpinnings of MINT for a broad class of performance metrics, and describe Periscope, a Linux embodiment of MINT constructions. We instantiate MINT and Periscope for a specific metric of interest—namely, packet loss rates—and present results of simulations and Internet measurements that confirm the effectiveness and robustness of our constructions over a wide range of network conditions.
[1] 1053 A. Adams, T. Bu, R. Cáceres, N. Duffield, T. Friedman, J. Horowitz, F.L. Presti, S. Moon, V. Paxson, and D. Towsley, “The Use of End-to-End Multicast Measurements for Characterizing Internal Network Behavior,” IEEE Comm. Magazine, May 2000.[2] M. Allman and V. Paxson, “On Estimating End-to-End Network Path Properties,” Proc. ACM SIGCOMM, 1999.[3] A. Bestavros, J. Byers, and K. Harfoush, “Inference and Labeling of Metric-Induced Network Topologies,” Proc. IEEE Infocom, June 2002.[4] J.C. Bolot, “End-to-End Packet Delay and Loss Behavior in the Internet,” Proc. ACM SIGCOMM, pp. 289-298, Sept. 1993.[5] T. Bu, N. Duffield, F. LoPresti, and D. Towsley, “Network Tomography on General Topology,” Proc. ACM SIGMETRICS, June 2002.[6] R. Cáceres, N.G. Duffield, J. Horowitz, D. Towsley, and T. Bu, “Multicast Based Inference of Network-Internal Characteristics: Accuracy of Packet-Loss Estimation,” Proc. IEEE Infocom, Mar. 1999.[7] R. Cáceres, N.G. Duffield, S.B. Moon, and D. Towsley, “Inference of Internal Loss Rates in the MBone,” Proc. IEEE Global Internet (Globecom) Conf., 1999.[8] R. Caceres, N. Duffield, and T. Friedman, “Impromptu Measurement Infrastructures Using RTP,” Proc. IEEE Infocom, June 2002.[9] R. Carter and M.E. Crovella, “Measuring Bottleneck Link Speed in Packet Switched Networks,” Proc. PERFORMANCE '96, Int'l Conf. Performance Theory, Measurement and Evaluation of Computer and Comm. Systems, Oct. 1996.[10] M. Coates and R. Nowak, “Network Loss Inference Using Unicast End-to-End Measurement,” Proc. ITC Conf. IP Traffic, Modeling and Management, Sept. 2000.[11] N. Duffield, J. Horowitz, F. LoPresti, and D. Towsley, “Multicast Topology Inference from Measured End-to-End Loss,” IEEE Trans. Information Theory, vol. 48, no. 1, Jan. 2002.[12] N. Duffield, J. Horowitz, D. Towsley, W. Wei, and T. Friedman, “Multicast-Based Loss Inference with Missing Data,” IEEE J. Selected Areas of Comm., vol. 20, no. 4, May 2002.[13] N. Duffield, F.L. Presti, V. Paxson, and D. Towsley, “Inferring Link Loss Using Striped Unicast Probes,” Proc. IEEE Infocom, Apr. 2001.[14] N. Duffield, J. Horowitz, and F.L. Presti, “Adaptive Multicast Topology Inference,” Proc. IEEE Infocom, Apr. 2001.[15] N. Duffield, J. Horowitz, F.L. Presti, and D. Towsley, “Network Delay Tomography from End-to-End Unicast Measurements,” Proc. Int'l Workshop Digital Comm., Sept. 2001.[16] R. Govindan and A. Reddy, “An Analysis of Internet Inter-Domain Routing and Route Stability,” Proc. IEEE Infocom, Apr. 1997.[17] T. Griffin and G. Wilfong, “An Analysis of BGP Convergence Properties,” Proc. ACM SIGCOMM, pp. 277-288, Sept. 1999.[18] K. Harfoush, “A Framework and Toolkit for the Effective Measurement and Representation of Internet Internal Characteristics,” PhD dissertation, Boston Univ., Aug. 2002.[19] K. Harfoush, A. Bestavros, and J. Byers, “Robust Identification of Shared Losses Using End-to-End Unicast Probes,” Proc. Eighth IEEE Int'l Conf. Network Protocols (ICNP), Nov. 2000.[20] “PeriScope: An Active Probing API,” Proc. 2002 Passive and Active Measurement Workshop, PAM '02, Mar. 2002.[21] “Measuring Bottleneck Bandwidth of Targeted Path Segments,” Proc. IEEE Infocom, Apr. 2003.[22] “IPMA: Internet Performance Measurement and Analysis,” http://www.merit.eduipma, 2005.[23] V. Jacobson, “Pathchar: A Tool to Infer Characteristics of Internet Paths,” ftp://ftp.ee.lbl.govpathchar, 2005.[24] S. Keshav, “Congestion Control in Computer Networks,” PhD dissertation, Univ. of California at Berkeley, Sept. 1991.[25] K. Lai and M. Baker, “Measuring Link Bandwidths Using a Deterministic Model of Packet Delay,” Proc. ACM SIGCOMM, Aug. 2000.[26] “Nettimer: A Tool for Measuring Bottleneck Link Bandwidth,” Proc. USENIX Symp. Internet Technologies and Systems, Mar. 2001.[27] F. LoPresti, N. Duffield, J. Horowitz, and D. Towsley, “Multicast-Based Inference of Network-Internal Delay Distributions,” IEEE/ACM Trans. Networking, vol. 10, no. 6, Dec. 2002.[28] “Mtrace: Tracing Multicast Path between a Source and a Receiver,” ftp://ftp.parc.xerox.com/pub/netsearchipmulti , 2005.[29] “ns: Network Simulator,” http://www.isi.edu/nsnamns/, 2005.[30] V. Padmanabhan, “Addressing the Challenges of Web Data Transport,” PhD dissertation, Univ. of California at Berkeley, Sept. 1998.[31] J.-J. Pansiot and D. Grad, “On Routes and Multicast Trees in the Internet,” Computer Comm. Rev., vol. 28, no. 1, pp. 41-50, Jan. 1998.[32] V. Paxson, “Measurements and Analysis of End-to-End Internet Dynamics,” PhD dissertation, UC Berkeley and Lawrence Berkeley Laboratory, 1997.[33] S. Ratnasamy and S. McCanne, “Inference of Multicast Routing Trees and Bottleneck Bandwidths Using End-to-End Measurements,” Proc. IEEE Infocom, pp. 353-360, Mar. 1999.[34] D. Rubenstein, J. Kurose, and D. Towsley, “Detecting Shared Congestion of Flows via End-to-End Measurement,” IEEE/ACM Trans. Networking, vol. 10, no. 3, June 2002.[35] S. Seshan, M. Stemm, and R. Katz, “SPAND: Shared Passive Network Performance Discovery,” Proc. Usenix Symp. Internet Technologies and Systems (USITS), Dec. 1997.[36] M. Yajnik, S. Moon, J. Kurose, and D. Towsley, “Measurement and Modeling of the Temporal Dependence in Packet Loss,” Proc. IEEE Infocom, pp. 345-352, Mar. 1999.
Index Terms:
End-to-end measurement, packet-pair probing, Bayesian probing, Internet tomography, performance evaluation.
Citation:
Azer Bestavros, John W. Byers, Khaled A. Harfoush, "Inference and Labeling of Metric-Induced Network Topologies," IEEE Transactions on Parallel and Distributed Systems, vol. 16, no. 11, pp. 1053-1065, Nov. 2005, doi:10.1109/TPDS.2005.138
