George Riley

The coarsest approximation of the structure of a complex network, such as the Internet, is a simple undirected unweighted graph. This approximation, however, loses too much detail. In reality, objects represented by vertices and edges in such a graph possess some non-trivial internal structure that varies across and differentiates among distinct types of links or nodes. In this work, we abstract such additional information as network annotations. We introduce a network topology modeling framework that treats annotations as an extended correlation profile of a network. Assuming we have this profile measured for a given network, we present an algorithm to rescale it in order to construct networks of varying size that still reproduce the original measured annotation profile. Using this methodology, we accurately capture the network properties essential for realistic simulations of network applications and protocols, or any other simulations involving complex network topologies, including modeling and simulation of network evolution. We apply our approach to the Autonomous System (AS) topology of the Internet annotated with business relationships between ASs. This topology captures the large-scale structure of the Internet. In depth understanding of this structure and tools to model it are cornerstones of research on future Internet architectures and designs. We find that our techniques are able to accurately capture the structure of annotation correlations within this topology, thus reproducing a number of its important properties in synthetically-generated random graphs.

The complexity and dynamics of Border Gateway Protocol (BGP), the only inter-domain routing protocol available for the Internet, is driving the need for efficient, scalable, realistic and meaningful network simulations. To properly simulate the behavior of BGP as currently deployed, one requires both a realistic topology and a realistic model of BGP. Although a large number of topology generators are available, they have limitations in either their scalability or in the ability to model AS relationships. In this work, we describe the methodology employed to efficiently construct meaningful large scale simulations of the order of a several thousand autonomous systems using parallel and distributed simulations thereby leveraging the power of multiprocessors and clusters of workstations. Using the Georgia Tech Network Simulator (GTNetS) as the framework, we simulate a realistic topology constructed from the BGP routing table updates collected by RouteViews and further incorporate the policy constraints based on the autonomous systems relationships inferred by the Cooperative Association for Internet Data Analysis (CAIDA). Our BGP model (called BGP++) found in GTNetS is built from the open source Zebra BGP implementation, which is deployed in a number of existing Internet Autonomous Systems. Using BGP++ and our topology generation methods, we show how the simulations can be used to study the effect of using BGP anycasting at DNS root servers on the several BGP metrics, including convergence time and churn.

Research on performance, robustness, and evolution of the global Internet is fundamentally handicapped without accurate and thorough knowledge of the nature and structure of the contractual relationships between Autonomous Systems (ASs). In this work we introduce novel heuristics for inferring AS relationships. Our heuristics improve upon previous works in several technical aspects, which we outline in detail and demonstrate with several examples. Seeking to increase the value and reliability of our inference results, we then focus on validation of inferred AS relationships. We perform a survey with ASs' network administrators to collect information on the actual connectivity and policies of the surveyed ASs. Based on the survey results, we find that our new AS relationship inference techniques achieve high levels of accuracy: we correctly infer 96.5% customer to provider (c2p), 82.8% peer to peer (p2p), and 90.3% sibling to sibling (s2s) relationships. We then cross-compare the reported AS connectivity with the AS connectivity data contained in BGP tables. We find that BGP tables miss up to 86.2% of the true adjacencies of the surveyed ASs. The majority of the missing links are of the p2p type, which highlights the limitations of present measuring techniques to capture links of this type. Finally, to make our results easily accessible and practically useful for the community, we open an AS relationship repository where we archive, on a weekly basis, and make publicly available the complete Internet AS-level topology annotated with AS relationship information for every pair of AS neighbors.

The Intel Mote is a new sensor node platform with improved radio bandwidth and reliability due to the usage of Bluetooth radio. The connection-oriented nature of Bluetooth raises the issues of effective multi-hop network (scatternet) formation and maintenance that network and routing layer must address on top of the TinyOS abstractions. The hop distance and wireless link quality pose major challenges to multi-hop network performance, especially the connection-oriented networks such as Bluetooth scatternet. In this paper, we present a metric-based scatternet formation algorithm for the Intel Mote, which can optimize the Bluetooth network formation from the hop distance and link quality perspectives. In addition, a smart repair mechanism is proposed to deal with link/node failure and recover the network connectivity promptly with low overhead. The experiments with the Intel Mote platform demonstrate the effectiveness of the optimizations, which make the platform more powerful

The Intel Mote is a new sensor node platform with improved radio bandwidth and reliability due to the usage of Bluetooth radio. The connection-oriented nature of Bluetooth raises the issues of effective multi-hop network (scatternet) formation and maintenance that network and routing layer must address on top of the TinyOS abstractions. The hop distance and wireless link quality pose major challenges to multi-hop network performance, especially the connection-oriented networks such as Bluetooth scatternet. In this paper, we present a metric-based scatternet formation algorithm for the Intel Mote, which can optimize the Bluetooth network formation from the hop distance and link quality perspectives. In addition, a smart repair mechanism is proposed to deal with link/node failure and recover the network connectivity promptly with low overhead. The experiments with the Intel Mote platform demonstrate the effectiveness of the optimizations, which make the platform more powerful

Although the Internet AS-level topology has been extensively studied over the past few years, little is known about the details of the AS taxonomy. An AS "node" can represent a wide variety of organizations, e.g., large ISP, or small private business, university, with vastly different network characteristics, external connectivity patterns, network growth tendencies, and other properties that we can hardly neglect while working on veracious Internet representations in simulation environments. In this paper, we introduce a radically new approach based on machine learning techniques to map all the ASes in the Internet into a natural AS taxonomy. We successfully classify 95.3% of ASes with expected accuracy of 78.1%. We release to the community the AS-level topology dataset augmented with: 1) the AS taxonomy information and 2) the set of AS attributes we used to classify ASes. We believe that this dataset will serve as an invaluable addition to further understanding of the structure and evolution of the Internet.