Network discovery using incomplete measurements

Resolving characteristics of the Internet from empirical measurements is important in the development of new protocols, traffic engineering, advertising, and troubleshooting. Internet measurement campaigns commonly involve heavy network load probes that are usually non-adaptive and incomplete, and thus directly reveal only a fraction of the underlying network characteristics. This dissertation addresses the open problem of Internet characteristic discovery in an incomplete measurement regime. Using partially observed measurements, we specifically focus on the problems of Internet topology discovery, inferring the geographic location of Internet resources, and network anomaly detection.;The first problem addressed in this work is the inference of topological characteristics of the Internet from three distinct forms of incomplete measurements. Initial work demonstrates how Passive Measurements, potentially-incomplete passively observed characteristics of the network, can be used to infer topological structure, such as clustering and shared path lengths. The second form of missing measurements come in the form of a set of traceroute probes, where we obtain partial knowledge of route lengths between routers in the network. Using a novel statistical methodology, we show how unobserved links between routers can be detected. Finally, we develop a novel targeted delay-based tomographic methodology, which resolves the tree topology of a network with a methodology that only requires a number of directed measurements within a poly-logarithmic factor of derived lower bounds.;The second component of this dissertation focuses on two critical networking problems -- geographic location interference of Internet resources and network anomaly detection. In terms of geographic location inference, our methodology exploits a set of landmarks in the network with known geographic location and targeted latency probes to avoid erroneous measurements caused by non-line-of-sight routing of long network paths. The use of a novel embedding algorithm allows for the inferred geolocation of end hosts to be clustered in areas of large population density without explicitly defined population data. Finally, we examine detecting unforeseen anomalous events in a network. Using a limited training set of labeled anomalies, our new anomaly detection framework extracts signal characteristics of anomalous events and detects their occurrence across observed network-wide measurements.