We present a case study about the spatial indexing and regional classification of billions of geographic coordinates from geo-tagged social network data using Hierarchical Triangular Mesh (HTM) implemented for Microsoft SQL Server. Due to the lack of certain features of the HTM library, we use it in conjunction with the GIS functions of SQL Server to significantly increase the efficiency of pre-filtering of spatial filter and join queries. For example, we implemented a new algorithm to compute the HTM tessellation of complex geographic regions and precomputed the intersections of HTM triangles and geographic regions for faster false-positive filtering. With full control over the index structure, HTM-based pre-filtering of simple containment searches outperforms SQL Server spatial indices by a factor of ten and HTM-based spatial joins run about a hundred times faster.

The localization of Internet hosts opens space for a wide scope of applications, from targeted, location aware content provision to localizing illegal content. In this paper we present a novel probabilistic approach, called Spotter, for estimating the geographic position of Internet devices with remarkable precision. While the existing methods use landmark specific calibration for building their internal models we show that the delay-distance data follow a generic distribution for each landmark. Hence, instead of describing the delay-distance space in a landmark specific manner our proposed method handles all the calibration points together and derives a common delay-distance model. This fundamental discovery indicates that, in contrast to prior techniques, Spotter is less prone to measurement errors and other anomalies such as indirect routing. To demonstrate the robustness and the accuracy of Spotter we test the performance on PlanetLab nodes as well as on a more realistic reference set collected by CAIDA explicitly for geolocation comparison purposes. To the best of our knowledge, we are the first to use this novel ground truth containing over 23000 network routers with their geographic locations.

The geographic layout of the physical Internet inherently determines important network properties and traffic characteristics. To give insight into the geography of the Internet, we examine the spatial properties of the topology and routing. To represent the network we conducted a geographically dispersed traceroute campaign, and embedded the extracted topology into the geographic space by applying a novel IP geolocalization service, called Spotter. In this paper we present the frequency analysis of link lengths, quantify path circuitousness and explore the symmetry of end-to-end Internet routes.

This paper presents operational experience of large-scale unicast network tomography, that samples a part of the European Internet. In the paper we describe in detail the ETOMIC measurement platform that was used to conduct the experiments, and its potential in future scaled-up measurements. The main results of the paper are maps showing various spatial and temporal structure in the characteristics of queueing delay corresponding to the resolved part of the European Internet. These maps reveal that the average queueing delay on different network segments spans more than two orders of magnitude. At the most loaded time of day we find that the distribution of average queueing delays among the different segments follows closely a log-normal distribution.

Synchronization in networks with different topologies is studied. We show that for a large class of oscillators there exist two classes of networks; class-A: networks for which the condition of stable synchronous state is sigmagamma2> a, and class-B: networks for which this condition reads gammaN/gamma21= 02les... les gammaNare the eigenvalues of the Laplacian matrix, where N is the order of the graph. Synchronization in networks whose topology is described by classical random graphs and power-law random graphs when N rarr infin is investigated in detail

The central result of this paper is an analytic formula describing the packet loss probability in a buffer as a function of the length of the buffer and the probability of external packet loss. This formula makes it possible to calculate the total loss along a multi-buffer, multi-link route. Also, new types of congestion window distributions are discovered when the packet loss in the buffer is large. These are different from the usual Gaussian type single humped distributions and can help to develop a qualitative classification of window distributions.

We analyze a model of a heavily utilized bottleneck buffer in this paper. We show that the nature of traffic leaving the buffer is determined by the buffer length/number of TCP ratio. If this ratio is above a critical value, TCP can stay in the congestion avoidance phase and it can generate periodic traffic after a transient period. If the ratio is below a critical value then the congestion window dynamics becomes chaotic or stochastic. We demonstrate that the traffic shows self-similar properties in this chaotic phase, which is determined by the exponential backoff mechanism.