MTU CS 6461 - On the Number of Distributed Measurement Points for Network Tomography (6 pages)

Previewing pages 1, 2 of 6 page document View the full content.
View Full Document

On the Number of Distributed Measurement Points for Network Tomography



Previewing pages 1, 2 of actual document.

View the full content.
View Full Document
View Full Document

On the Number of Distributed Measurement Points for Network Tomography

64 views

Lecture Notes


Pages:
6
School:
Michigan Tech
Course:
Cs 6461 - Advanced Computer Networks f 3
Advanced Computer Networks f 3 Documents

Unformatted text preview:

On the Number of Distributed Measurement Points for Network Tomography Joseph D Horton Alejandro Lo pez Ortiz Faculty of Computer Science University of New Brunswick Fredericton NB E3B 5A3 Canada School of Computer Science University of Waterloo Waterloo Ont N2L 3G1 Canada jdh unb ca alopez o uwaterloo ca ABSTRACT Internet topology information is only made available in aggregate form by standard routing protocols Connectivity information and latency characteristics must therefore be inferred using indirect techniques In this paper we consider measurements using a distributed set of measurement points or beacons We show that computing the minimum number of required beacons on a network under a BGPlike routing policy is NP hard and at best log n approximable In the worst case at least n 1 3 and at most n 1 3 beacons are required for a network with n nodes We then introduce some observations that allow us to propose a relatively small candidate set of beacons for the current Internet topology The set proposed has properties with relevant applications for all paths routing on the public Internet and performance based routing Routing decisions and content distribution networks web caches require proper connectivity and latency information so as to direct traffic in an optimal fashion The family of internet protocols collect and distribute only a limited amount of information on the topology connectivity and state of the network Hence the information of interest be it latency topology or connectivity has to be inferred from experimental measurements Gathering connectivity information through indirect measurements is known as Internet tomography 15 37 14 In this work we consider the problem of determining the topology of the Internet under the assumption that a distributed set of measurement points sometimes called beacons running special software is deployed at key sites across the entire Internet This has emerged as one of the strategies of choice for measuring the state



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view On the Number of Distributed Measurement Points for Network Tomography and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view On the Number of Distributed Measurement Points for Network Tomography and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?