Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Design for Optimizability: Traffic Management of a Future Internet Read chapter Read first chapter

2010 | OriginalPaper | Chapter

14. Algebraic Approaches for Scalable End-to-End Monitoring and Diagnosis

Authors : Yao Zhao, Yan Chen

Published in: Algorithms for Next Generation Networks

Publisher: Springer London

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The rigidity of the Internet architecture led to flourish in the research of end-to-end based systems. In this chapter, we describe a linear algebra-based end-to-end monitoring and diagnosis system. We first propose a tomography-based overlay monitoring system (TOM). Given n end hosts, TOM selectively monitors a basis set of O(nlogn) paths out of all n(n − 1) end-to-end paths. Any end-to-end path can be written as a unique linear combination of paths in the basis set. Consequently, by monitoring loss rates for the paths in the basis set, TOM infers loss rates for all end-to-end paths. Furthermore, leveraging on the scalable measurements from the TOM system, we propose the Least-biased End-to-End Network Diagnosis (in short, LEND) system. We define a minimal identifiable link sequence (MILS) as a link sequence of minimal length whose properties can be uniquely identified from end-to-end measurements. LEND applies an algebraic approach to find out the MILSes and infers the properties of the MILSes efficiently. This also means LEND system achieves the finest diagnosis granularity under the least biased statistical assumptions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter In-Network Monitoring
next chapter Network Coding and Its Applications in Communication Networks
Literature
1.
Adams, A., et al.: The use of end-to-end multicast measurements for characterizing internal network behavior. In: IEEE Communications (May, 2000)
2.
3.
Anagnostakis, K., Greenwald, M., Ryger, R.: cing: Measuring network-internal delays using only existing infrastructure. In: IEEE INFOCOM (2003)
4.
Anderson, E., et al.: LAPACK Users’ Guide, third edn. Society for Industrial and Applied Mathematics, Philadelphia, PA (1999)CrossRef
5.
Bu, T., Duffield, N., Presti, F., Towsley, D.: Network tomography on general topologies. In: ACM SIGMETRICS (2002)
6.
Caceres, R., Duffield, N., Horowitz, J., Towsley, D.: Multicast-based inference of network-internal loss characteristics. IEEE Transactions in Information Theory 45 (1999)
7.
Caceres, R., Duffield, N., Horowitz, J., Towsley, D., Bu, T.: Multicast-based inference of network-internal characteristics: Accuracy of packet loss estimation. In: IEEE INFOCOM (1999)
8.
Chen, Y., Bindel, D., Katz, R.H.: Tomography-based overlay network monitoring. In: ACM SIGCOMM Internet Measurement Conference (IMC) (2003)
9.
Chen, Y., Bindel, D., Song, H., Katz, R.H.: An algebraic approach to practical and scalable overlay network monitoring. In: ACM SIGCOMM (2004)
10.
Chen, Y., Lim, K., Overton, C., Katz, R.H.: On the stability of network distance estimation. In: ACM SIGMETRICS Performance Evaluation Review (PER) (Sep. 2002)
11.
Chua, D.B., Kolaczyk, E.D., Crovella, M.: Efficient monitoring of end-to-end network properties. In: IEEE INFOCOM (2005)
12.
Coates, M., Hero, A., Nowak, R., Yu, B.: Internet Tomography. IEEE Signal Processing Magazine 19(3), 47–65 (2002)CrossRef
13.
Demmel, J.: Applied Numerical Linear Algebra. SIAM (1997)
14.
Duffield, N.: Simple network performance tomography. In: ACM SIGCOMM Internet Measurement Conference (IMC) (2003)
15.
Duffield, N., Horowitz, J., Towsley, D., Wei, W., Friedman, T.: Multicast-based loss inference with missing data. IEEE Journal of Selected Areas of Communications 20(4) (2002)
16.
Duffield, N., Presti, F., Paxson, V., Towsley, D.: Inferring link loss using striped unicast probes. In: IEEE INFOCOM (2001)
17.
Floyd, S., Jacobson, V.: Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking 1(4) (1993)
18.
Francis, P., et al.: IDMaps: A global Internet host distance estimation service. IEEE/ACM Trans. on Networking (2001)
19.
Golub, G., Loan, C.V.: Matrix Computations. The Johns Hopkins University Press (1989)
20.
Govindan, R., Tangmunarunkit, H.: Heuristics for Internet map discovery. In: IEEE INFOCOM (2000)
21.
Mahajan, R., Spring, N., Wetherall, D., Anderson, T.: User-level internet path diagnosis. In: ACM SOSP (2003)
22.
Medina, A., Matta, I., Byers, J.: On the origin of power laws in Internet topologies. In: ACM Computer Communication Review (2000)
23.
Ng, T.S.E., Zhang, H.: Predicting Internet network distance with coordinates-based approaches. In: Proc.of IEEE INFOCOM (2002)
24.
Ozmutlu, H.C., et al.: Managing end-to-end network performance via optimized monitoring strategies. Journal of Network and System Management 10(1) (2002)
25.
Padmanabhan, V., Qiu, L., Wang, H.: Server-based inference of Internet link lossiness. In: IEEE INFOCOM (2003)
26.
27.
R.A.Brualdi, Pothen, A., Friedland, S.: The sparse basis problem and multilinear algebra. SIAM Journal of Matrix Analysis and Applications 16, 1–20 (1995)MathSciNetMATHCrossRef
28.
Ratnasamy, S., et al.: Topologically-aware overlay construction and server selection. In: Proc. of IEEE INFOCOM (2002)
29.
Shavitt, Y., Sun, X., Wool, A., Yener, B.: Computing the unmeasured: An algebraic approach to Internet mapping. In: IEEE INFOCOM (2001)
30.
Song, H., Qiu, L., Zhang, Y.: Netquest: A flexible framework for lange-scale netork measurement. In: ACM SIGMETRICS (June 2006)
31.
Tang, C., McKinley, P.: On the cost-quality tradeoff in topology-aware overlay path probing. In: IEEE ICNP (2003)
32.
Zhang, Y., et al.: On the constancy of Internet path properties. In: Proc. of SIGCOMM IMW (2001)
33.
Zhao, Y., Chen, Y.: A suite of schemes for user-level network diagnosis without infrastructure. In: IEEE INFOCOM (2007)
34.
Zhao, Y., Chen, Y., Bindel, D.: Towards unbiased end-to-end network diagnosis. In: ACM SIGCOMM (2006)
Metadata
Title
Algebraic Approaches for Scalable End-to-End Monitoring and Diagnosis
Authors
Yao Zhao
Yan Chen
Copyright Year
2010
Publisher
Springer London
Book
Algorithms for Next Generation Networks

Print ISBN: 978-1-84882-764-6

Electronic ISBN: 978-1-84882-765-3

Copyright Year: 2010

DOI
https://doi.org/10.1007/978-1-84882-765-3_14

Premium Partner

    Image Credits