The observable part of a network

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The observable part of a network

Full text

Pdf (1.16 MB)

Source

IEEE/ACM Transactions on Networking (TON) archive
Volume 17 , Issue 1 (February 2009) table of contents

Pages 93-105

Year of Publication: 2009

ISSN:1063-6692

Authors

Piet Van Mieghem	Delft University of Technology, Delft, The Netherlands
Huijuan Wang	Delft University of Technology, Delft, The Netherlands

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 109, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TNET.2008.925089

ABSTRACT

The union of all shortest path trees GUspt is the maximally observable part of a network when traffic follows shortest paths. Overlay networks such as peer to peer networks or virtual private networks can be regarded as a subgraph of GUspt. We investigate properties of GUspt in different underlying topologies with regular i.i.d. link weights. In particular, we show that the overlay GUspt in an Erdös-Rényi random graph Gp (N) is a connected GPc (N) where Pc ∼ log N/N is the critical link density, an observation with potential for ad-hoc networks.

Shortest paths and, thus also the overlay GUspt, can be controlled by link weights. By tuning the power exponent α of polynomial link weights in different underlying graphs, the phase transitions in the structure of GUspt are shown by simulations to follow a same universal curve FT (α) = Pr[GUspt is a tree]. The existence of a controllable phase transition in networks may allow network operators to steer and balance flows in their network. The structure of GUspt in terms of the extreme value index α is further examined together with its spectrum, the eigenvalues of the corresponding adjacency matrix of GUspt.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stephanos Androutsellis-Theotokis , Diomidis Spinellis, A survey of peer-to-peer content distribution technologies, ACM Computing Surveys (CSUR), v.36 n.4, p.335-371, December 2004 [doi>10.1145/1041680.1041681]
	2	A. Ganesh, L. Massoulie, and D. Towsley, "The effect of network topology on the spread of epidemics," in Proc. IEEE INFOCOM 2005, Mar. 2005, vol. 2, pp. 1455-1466.
	3	L. Zhao, K. Park, and Y.-C. Lai, Phys. Rev., vol. E 70, no. 035101, 2004.
	4	T. Watanabe, Y. Higashi, and A. Nakamura, "An approach to robust network construction from graph augmentation problems," in Proc. 1990 IEEE Int. Symp. Circuits Syst. (ISCAS), May 1990, vol. 4, pp. 2861-2864.
	5	P. Van Mieghem and S. M. Magdalena, Phys. Rev., vol. E 72, no. 056138, 2005.
	6	A. Lakhina, J. Byers, M. Crovella, and P. Xie, "Sampling biases in IP topology measurements," in Proc. IEEE INFOCOM 2003, Mar.-Apr. 2003, vol. 1, pp. 332-341.
	7	A. Clauset and C. Moore, Phys. Rev. Lett., vol. 94, no. 018701, 2005.
	8	Dimitris Achlioptas , Aaron Clauset , David Kempe , Cristopher Moore, On the bias of traceroute sampling: or, power-law degree distributions in regular graphs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060693]
	9	Piet Van Mieghem, Performance Analysis of Communications Networks and Systems, Cambridge University Press, New York, NY, 2005
	10	N. Biggs, Algebraic Graph Theory, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 1996.
	11	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	12	Piet Van Mieghem, Data Communications Networking, Purdue University Press, 2006
	13	Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
	14	P. Van Mieghem, G. Hooghiemstra, and R. W. van der Hofstad, "A scaling law for the hopcount," Delft Univ. Technol., Delft, The Netherlands, report2000125, 2000.
	15	Remco Van Der Hofstad , Gerard Hooghiemstra , Piet Van Mieghem, FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH, Probability in the Engineering and Informational Sciences, v.15 n.2, p.225-237, April 2001 [doi>10.1017/S026996480115206X]
	16	B. Bollobas, Random Graphs, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 2001.
	17	G. Chartrand and R. O. Ortrud, Applied and Algorithmic Graph Theory. New York: McGraw-Hill, 1992.
	18	Gary Chartrand , Linda Lesniak, Graphs & digraphs (2nd ed.), Wadsworth Publ. Co., Belmont, CA, 1986
	19	R. Albert and A. Barabasi, "Emergence of scaling in random networks," Science, vol. 286, pp. 509-512, 1999.
	20	P. Van Mieghem and S. van Langen, Phys. Rev., vol. E71, no. 056113, 2005.
	21	E. W. Dijkstra, "A note on two problems in connection with graphs," Num. Math., vol. 1, pp. 269-271, 1959.
	22	William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
	23	J. J. Binney, N. J. Dowrick, A. J. Fisher, and M. E. J. Newman, The Theory of Critical Phenomena: An Introduction to the Renormalization Group. Oxford, U.K.: Clarendon, 1992.
	24	S. N. Dorogovtsev, A. V. Goltsev, J. F. F. Mendes, and A. N. Samukhin, Phys. Rev., vol. E 68, no. 046109, 2003.
	25	L. He, X. Liu, and G. Strang, "Trees with Cantor eigenvalue distribution," Stud. Appl. Math., vol. 110, pp. 123-123, 2003.
	26	Danica Vukadinovic , Polly Huang , Thomas Erlebach, On the Spectrum and Structure of Internet Topology Graphs, Proceedings of the Second International Workshop on Innovative Internet Computing Systems, p.83-95, June 20-22, 2002
	27	D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs. Berlin, Germany: VEB Deutscher Verlag der Wissenschaften, 1980.
	28	E. D. van Dam and W. H. Haemers, "Which graphs are determined by their spectrum?," Linear Algebra and its Applicat., vol. 373, pp. 241-272, 2003.
	29	E. Wigner, "On the distribution of the roots of certain symmetric matrices," Ann. Math., vol. 67, pp. 325-327, 1958.
	30	I. J. Farkas, I. Deréyi, A.-L. Barabási, and T. Vicsek, Phys. Rev., vol. E 64, no. 026704, 2001.
	31	Miguel Castro , Manuel Costa , Antony Rowstron, Should we build Gnutella on a structured overlay?, ACM SIGCOMM Computer Communication Review, v.34 n.1, January 2004 [doi>10.1145/972374.972397]
	32	R. Hekmat and P. Van Mieghem, "Study of connectivity in wireless ad-hoc networks with an improved radio model," in Proc. 2nd Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'04), Cambridge, U.K., Mar. 24-26, 2004, pp. 142-151.
	33	RIPE Test Traffic Measurements. RIPE NCC, Amsterdam, The Netherlands [Online]. Available: http://www.ripe.net/ripencc/mem-services/ ttm/
	34	M. Janic, F. Kuipers, X. Zhou, and P. Van Mieghem, "Implications for QoS provisioning based on traceroute measurements," in Proc. 3nd Int. Workshop on Quality of Future Internet Services (QofIS2002), Zurich, Switzerland, Oct. 16-18, 2002, pp. 3-14.
	35	Milena Janic , Piet Van Mieghem, On properties of multicast routing trees: Research Articles, International Journal of Communication Systems, v.19 n.1, p.95-114, February 2006 [doi>10.1002/dac.v19:1]
	36	M. Drmota and H.-K. Hwang, "Profiles of random trees: Correlation and width of random recursive trees and binary search trees," Adv. Appl. Probabil., vol. 37, pp. 321-341, 2005.
	37	Remco van der Hofstad , Gerard Hooghiemstra , Piet Van Mieghem, On the covariance of the level sizes in random recursive trees, Random Structures & Algorithms, v.20 n.4, p.519-539, July 2002 [doi>10.1002/rsa.10030]