Mixed reality (MR) telepresence provides a shared common 3D space for networked users to enjoy real-time immersive experiences with natural interactivity and movement. Due to its high hardware and compute demands, a large-scale cloud-edge MR solution is necessary for achieving critical mass adoption, where users engage in the MR environment using low-cost cameras at the edge and complex 3D world processing is offloaded to the cloud servers. However, cloud-edge MR solutions have distinct challenges such as concurrent multiple camera support, unpredictable compute demands, and CPU/GPU contention. In this paper, we present PointPresence, an edge-compute framework for large-scale MR applications. PointPresence is deployed at an edge node, such as an O-RAN RIC or a local enterprise server, and provides low-latency MR experiences to a large number of users by incorporating intelligent camera selection for compute reduction, reactive pipeline design for adaptation to compute demand changes, and context-aware GPU sharing. Our comprehensive evaluation on an MR testbed shows that PointPresence reduces end-to-end latency by up to 3.5× and improves end user perceived visual quality by 30%.

Remote Direct Memory Access (RDMA) has been widely adopted in modern data centers thanks to its high-throughput, low-latency data transfer capability and reduced CPU overhead. However, traditional network-flow-based monitoring is poor at interpreting RDMA communication and hence inadequate for gaining insights. In this paper, we present INSERT, an end-to-end RDMA telemetry system that enables seamless visibility into RDMA communication from the network layer all the way to the application layer. To this end, INSERT combines (i) eBPF-based transparent RDMA tracing on end-hosts and (ii) stateful RDMA network telemetry on programmable data plane. We implement RDMA network telemetry on programmable SmartNICs, where we address practical challenges for maintaining fine-grained state on massively-parallel packet processing pipelines. We demonstrate that INSERT can perform reasonably accurate telemetry at line-rate for different types of RDMA traffic even in the presence of out-of-order packets, and finally showcase two practical use cases that can benefit from it.

While the fast adoption of RDMA in data centers has been primarily driven by its performance benefits, more and more attention is being paid to its security implication, especially with mounting security risks associated with lateral communication within data centers. However, since RDMA is implemented as NIC’s fixed function, it is challenging to incorporate any new security feature in RDMA. In this paper, we propose Zeta, a zero-trust security addon for RoCEv2, which enables network-independent, fine-grained zero-trust security control for RDMA. It does not require any change in RDMA’s ASIC implementation or application-level interfaces. To this end, Zeta leverages modern SmartNIC’s versatility to perform zero-trust policy control on RDMA packets within a SmartNIC in a cryptographically secure fashion. From its prototype implementation and evaluation based on real-word applications, we show that, while cryptographic verification of Zeta introduces 1.5 ms session startup latency, the overhead of end-to-end application performance is marginal (e.g., less than 1% throughput and 5% latency penalty).

In the new industrial Internet, a wide variety of industrial applications are expected to rely on high-performance data communication between a multitude of sensors and actuators that are deployed on a large scale. Publish-subscribe-based communication model is well-suited to handle such large-scale data gathering and dissemination among data sources and sinks. To support publish-subscribe-based data delivery, the newly standardized Segmented Routing over IPv6 (SRv6) can provide non-disruptive network programming primitives for building and maintaining network-efficient, shareable data distribution trees within the network. We study optimal algorithms for setting up different types of multicasting in the SRv6-capable network. In particular, we show, both theoretically and experimentally, that splitting multicast streams into multiple sub-streams, as well as using end-to-end application-layer coding without any network participation can provide significant benefits in terms of multicast throughput compared to traditional single stream multicasting.

It is commonly assumed that the end-to-end networking performance of edge offloading is purely dictated by that of the network connectivity between end devices and edge computing facilities, where ongoing innovation in 5G/6G networking can help. However, with the growing complexity of edge-offloaded computation and dynamic load balancing requirements, an offloaded task often goes through a multi-stage pipeline that spans across multiple compute nodes and proxies interconnected via a dedicated network fabric within a given edge computing facility. As the latest hardware-accelerated transport technologies such as RDMA and GPUDirect RDMA are adopted to build such network fabric, there is a need for good understanding of the full potential of these technologies in the context of computation offload and the effect of different factors such as GPU scheduling and characteristics of computation on the net performance gain achievable by these technologies. This paper unveils detailed insights into the latency overhead in typical machine learning (ML)-based computation pipelines and analyzes the potential benefits of adopting hardware-accelerated communication. To this end, we build a model-serving framework that supports various communication mechanisms. Using the framework, we identify performance bottlenecks in state-of-the-art model-serving pipelines and show how hardware-accelerated communication can alleviate them. For example, we show that GPUDirect RDMA can save 15-50% of model-serving latency, which amounts to 70–160 ms.

State-disaggregated Network Function Virtualization (NFV) architectures decouple NF states from packet processing logic to achieve elasticity and resilience in stateful NFs. However, the existing state disaggregation approaches suffer from either poor NF performance due to frequent remote state access or potential inconsistencies in state updates when multiple NF instances concurrently access shared states. Moreover, they do not properly support state rejuvenation/expiration which is required for resource scalability of stateful NF operations. This paper presents a new state-disaggregated NFV system called RESCue that addresses these problems. RESCue handles remote state access differently for shared and private states. For efficient and consistent access of shared states, it leverages a lightweight custom control message protocol between NFs and a centralized state server. For private state access, it adopts a remote-paging-based interface to avoid introducing expensive blocking remote access within the critical path of NF packet processing. Finally, it utilizes non-blocking operations for state rejuvenation/expiration handling to minimize its performance overhead. Our evaluation of a RESCue prototype shows that it can handle NF scaling and failure recovery well, while supporting consistent state updates and state rejuvenation/expiration without compromising performance.

Modern data centers are witnessing fast-growing east-west traffic on their network infrastructure due to the highly distributed data center applications. Motivated by the heterogeneity of such application workloads, we propose in this article an extensible network management architecture calledMAGNetwhich enables application-aware intra-data center networking. The crux ofMAGNetis the smart endpoint residing within end-hosts, which is empowered by machine learning combined with lightweight workload tracing to detect workload identities and enable workload-dependent packet tagging. The centralized management plane interface ofMAGNetallows network functions to interpret packet tags and perform application-aware packet processing. We demonstrate the feasibility of the architecture via prototype implementation and extensive use case evaluation. Our experiments show that the smart endpoint can fingerprint many real-world applications with 99 percent accuracy only at 1–2 percent additional CPU, and that application-aware data plane can potentially bring substantial benefits in terms of security (e.g., via identity-based microsegmentation), CPU usage (e.g., for intrusion detection) and network latency (e.g., via TCP stack customization).

Due to the recent "work from home" trend, recent years have seen a growing research interest in understanding existing commercial videoconferencing systems in terms of their performance and architecture. One important question left unanswered that we tackle in this paper is: what is the performance of videoconferencing in the wild? Answering this generic question is challenging because it requires, ideally, a world-wide testbed composed of diverse devices (mobile, desktop), operating systems (Windows, MacOS, Linux) and network accesses (mobile and WiFi). In this paper, we present such a testbed that we develop to evaluate videoconferencing performance in the wild via automation for Android and Chromium-based browsers. We deploy our testbed via 85 distinct devices worldwide and collect performance metrics from 58 hours' worth of more than 2,000 videoconferencing sessions from 37 unique countries in the world. This, to the best of our knowledge, is the largest collection of videoconferencing performance data in the wild.

Performance troubleshooting is notoriously difficult for distributed microservices-based applications. A typical root-cause diagnosis for performance anomaly by an analyst starts by narrowing down the scope of slow services, investigates into high-level performance metrics or available logs in the slow components, and finally drills down to an actual cause. This process can be long, tedious, and sometimes aimless due to the lack of domain knowledge and the sheer number of possible culprits. This paper introduces a new machine-learning-driven performance analysis system called LongTale that automates the troubleshooting process for latency-related performance anomalies to facilitate the root cause diagnosis and explanation. LongTale builds on existing application-layer tracing in two significant aspects. First, it stitches application-layer traces with corresponding system stack traces, which enables more informative root-cause analysis. Second, it utilizes a novel machine-learning-driven analysis that feeds on the combined data to automatically uncover the most likely contributing factor(s) for given performance slowdown. We demonstrate how LongTale can be utilized in different scenarios, including abnormal long-tail latency explanation and performance interference analysis.

Since the outbreak of the COVID-19 pandemic, videoconferencing has become the default mode of communication in our daily lives at homes, workplaces and schools, and it is likely to remain an important part of our lives in the post-pandemic world. Despite its significance, there has not been any systematic study characterizing the user-perceived performance of existing videoconferencing systems other than anecdotal reports. In this paper, we present a detailed measurement study that compares three major videoconferencing systems: Zoom, Webex and Google Meet. Our study is based on 62 hours’ worth of more than 1.1K videoconferencing sessions, which were created with a mix of emulated videoconferencing clients deployed in the cloud, as well as real mobile devices running from a residential network over two separate periods with nine months apart. We find that the existing videoconferencing systems vary in terms of geographic scope and resource provisioning strategies, which in turns determine streaming lag experienced by users. We also observe that streaming rate can change under different conditions (e.g., available bandwidth, number of users in a session, mobile device status), which affects user-perceived streaming quality. Beyond these findings, our measurement methodology enables reproducible benchmark analysis for any types of comparative or longitudinal study on available videoconferencing systems.

Since the outbreak of the COVID-19 pandemic, videoconferencing has become the default mode of communication in our daily lives at homes, workplaces and schools, and it is likely to remain an important part of our lives in the post-pandemic world. Despite its significance, there has not been any systematic study characterizing the user-perceived performance of existing videoconferencing systems other than anecdotal reports. In this paper, we present a detailed measurement study that compares three major videoconferencing systems: Zoom, Webex and Google Meet. Our study is based on 48 hours' worth of more than 700 videoconferencing sessions, which were created with a mix of emulated videoconferencing clients deployed in the cloud, as well as real mobile devices running from a residential network. We find that the existing videoconferencing systems vary in terms of geographic scope, which in turns determines streaming lag experienced by users. We also observe that streaming rate can change under different conditions (e.g., number of users in a session, mobile device status, etc), which affects user-perceived streaming quality. Beyond these findings, our measurement methodology can enable reproducible benchmark analysis for any types of comparative or longitudinal study on available videoconferencing systems.

Application aware data centers promise various benefits for data center management, in terms of resource provisioning, power estimation, network management, security protection, etc. However, the emerging microservices make it challenging for data center operators to accurately identify what applications are deployed by tenants, due to their highly dynamic and heterogeneous nature. In this paper, we address the problem of fingerprinting microservices in a unified, efficient, accurate and non-intrusive fashion. To this end, we characterize the runtime behaviors of microservices using eBPF-based lightweight system call tracing. To accurately fingerprint a diverse set of microservices based on their system call activities, we utilize the machine learning approach which combines Bayesian learning and LSTM autoencoders. We demonstrate that our approach can fingerprint many real-world microservices with 99% accuracy, using 1-2% additional CPU resource, and can detect the presence of previously unseen microservices with near perfect accuracy.

This paper proposes Muppet, an edge-based multi-protocol architecture for large-scale Internet of Things (IoT) deployment and service automation. The crux of Muppet is a P4-based switch that inserts itself in between communicating IoT devices that can use different protocols. The switches are networked over IP to support wide area deployment and managed using centralized SDN control for scalability. Muppet provides many of the benefits of both native peer-to-peer and widely used cloud-centric approaches while avoiding their drawbacks. For example, Muppet offers low-latency and low-energy benefits of the peer-to-peer approach, while enabling wide-area, cross-protocol automation similar to the cloud-based solutions. We describe the P4 design and prototype realization of the switch using two very popular, but widely disparate, IoT protocols, namely, Bluetooth low energy and Zigbee. Through experiments, we show that Muppet is as efficient as peer-to-peer in terms of delay and energy usage, and scalable and programmable as cloud-based solutions. We illustrate its utility through practical use cases.

Increasingly, smart Network Interface Cards (sNICs) are being used in data centers to offload networking functions (NFs) from host processors thereby making these processors available for tenant applications. Modern sNICs have fully programmable, energy-efficient multi-core processors on which many packet processing functions, including a full-blown programmable switch, can run. However, having multiple switch instances deployed across the host hypervisor and the attached sNICs makes controlling them difficult and data plane operations more complex.

Stream processing pipelines operated by current big data streaming frameworks present two problems. First, the pipelines are not flexible, controllable, and programmable enough to accommodate dynamic streaming application needs. Second, the application-level data routing over the pipelines do not exhibit optimal performance for increasingly common one-to-many communication. To address these problems, we propose an SDN-based real-time big data streaming framework called Typhoon, that tightly integrates SDN functionality into a real-time stream framework. By partially offloading application-layer data routing and control to the network layer via SDN interfaces and protocols, Typhoon provides on-the-fly programmability of both the application and network layers, and achieve high-performance data routing. In addition, Typhoon SDN controller exposes cross-layer information, from both the application and the network, to SDN control plane applications to extend the framework's functionality. We introduce several SDN control plane applications to illustrate these benefits.

Bluetooth Low Energy (BLE) is a personal area wireless network technology that is of increasing importance for emerging Internet of Things (IoT) deployments. By design, BLE supports short-range, single-hop communication between a pair of BLE devices. As such, native BLE does not allow network-based policy control or in-network functions for service enhancement. These limitations are impediments to any large-scale BLE based IoT deployment (e.g., in hospital environments), where such sophisticated network-based visibility and control may be required. Relying on cloud-based solutions to meet these requirements has many known shortcomings. This paper proposes an SDN-based architecture for enabling wide area IoT deployments using BLE devices at the edge. We introduce a programmable BLE service switch (BLESS) that is transparently inserted between two communicating BLE devices. BLESS can be programmed at the service layer by a central controller to enable flexible, policy-based switching, as well as various in-network operations in BLE networks. We describe the design of BLESS, its implementation using P4 and OVS, and illustrate its utility through practical use cases.

In a vision-based 3D indoor localization system, conducting localization of user's device at a high frame rate is important to support real-time augment reality applications. However, vision-based 3D localization typically involves 2D keypoint detection and 2D-3D matching processes, which are in general too computationally intensive to be carried out at a high frame rate (e.g., 30 fps) on commodity hardware such as laptops or smartphones. In order to reduce per-frame computation time for 3D localization, we present a new method that distributes required computation over space and time, by splitting a video frame region into multiple sub-blocks, and processing only a sub-block in a rotating sequence at each video frame. The proposed method is general enough that it can be applied to any keypoint detection and 2D-3D matching schemes. We apply the method in a prototype 3D indoor localization system, and evaluate its performance in a 120m long indoor hallway environment using 5,200 video frames of 640x480 (VGA) resolution and a commodity laptop. When SIFT-based keypoint detection is used, our method reduces average and maximum computation time per frame by a factor of 10 and 7 respectively, with a marginal increase of positioning error (e.g., 0.17 m). This improvement enables the frame processing rate to increase from 3.2 fps to 23.3 fps.

In this paper, we study a two-user interference channel with a causal relay, where the relay's transmit symbol depends not only on its past received symbols, but also on its present received symbol. This is an appropriate model for studying amplify-and-forward type relaying when the bandwidth delay-spread product is much smaller than one. For the discrete memoryless interference channel with a causal relay, we derive a genie-aided outer bound. For the Gaussian interference channel with a causal relay, we define strong and very strong interference conditions and propose an outer bound for each case. We also propose an achievable scheme based on instantaneous amplify-and-forward (AF) relaying for the Gaussian interference channel with a causal relay and so it achieves capacity under some conditions. Our result extends the previous result by El Gamal, Hassanpour, and Mammen on the optimality of instantaneous AF relaying for the Gaussian relay channel with a causal relay to that of the Gaussian interference channel with a causal relay under strong and very strong interference.

We study a minimum delay routing problem in the context of distributed networks with and without partial load information. Even though a general minimum delay routing problem is NP hard, assuming uniformly distributed K source-destination (SD) pairs at random, we provide a lower bound on the average delay and demonstrate by simulation that it is tight for a certain classes of regularly deployed networks. We also show that some routing in a distributed manner is enough to achieve asymptotically optimal load balancing with high probability as K tends to infinity. In order to set such routing, however, each SD pair should know global load information, which is unrealistic for most networks. We propose novel predetermined path routing algorithms in which each SD pair chooses its routing path only among a set of predetermined paths. We then propose an efficient way of distributed construction for predetermined paths that are able to distribute traffic over a network. Our predetermined path routing algorithms work in a fully distributed manner with very limited load information or without any load information. In various network models, we demonstrate by simulation that the delay of the predetermined path routing algorithms quickly converges to that of the distributed routing with global load information.

Live broadcast over a peer-to-peer (P2P) network imposes a unique set of challenges to a digital rights management (DRM) system. Highly correlated service request arrivals at the start of a live event require peak-load provisioning if clients acquire licenses at playback time. Distributing the license management load across a P2P network requires the digital rights management system to ensure the integrity of both digital rights, the protection of client privacy and, at the same time, system scalability. In this paper we describe the requirements imposed on a digital rights management system in distributing live broadcast over a P2P network and present our design of such a system to meet the above challenges. We discuss the system's operation under a number of threat models and how to extend the system to further improve scalability and support network digital video recording (DVR). We close the paper after presenting some scalability results collected from a production P2P live broadcast network using our DRM design.

Live broadcast over a P2P (peer-to-peer) network imposes a unique set of challenges to a digital rights management system. Highly correlated service request arrivals at the start of a live event require peak-load provisioning if clients acquire licenses at playback time. Distributing the license management load across a P2P network requires the digital rights management system to ensure the integrity of both digital rights, the protection of client privacy and, at the same time, system scalability. In this paper we describe the requirements imposed on a digital rights management system in distributing live broadcast over a P2P network and present our design of such a system to meet the above challenges. We discuss the system's operation under a number of threat models and how to extend the system to further improve scalability. We close the paper after presenting some scalability results collected from a production P2P live broadcast network using our DRM design.

Large-scale data processing needs of enterprises today are primarily met with distributed and parallel computing in data centers. MapReduce has emerged as an important programming model for these environments. Since today's data centers run many MapReduce jobs in parallel, it is important to find a good scheduling algorithm that can optimize the completion times of these jobs. While several recent papers focused on optimizing the scheduler, there exists very little theoretical understanding of the scheduling problem in the context of MapReduce. In this paper, we seek to address this problem by first presenting a simplified abstraction of the MapReduce scheduling problem, and then formulate the scheduling problem as an optimization problem.We devise various online and offline algorithms to arrive at a good ordering of jobs to minimize the overall job completion times. Since optimal solutions are hard to compute (NP-hard), we propose approximation algorithms that work within a factor of 3 of the optimal. Using simulations, we also compare our online algorithm with standard scheduling strategies such as FIFO, Shortest Job First and show that our algorithm consistently outperforms these across different job distributions.

A number of commercial peer-to-peer (P2P) systems for live streaming have been introduced in recent years. The behavior of these popular systems has been extensively studied in several measurement papers. Due to the proprietary nature of these commercial systems, however, these studies have to rely on a “black-box” approach, where packet traces are collected from a single or a limited number of measurement points, to infer various properties of traffic on the control and data planes. Although such studies are useful to compare different systems from the end-user's perspective, it is difficult to intuitively understand the observed properties without fully reverse-engineering the underlying systems. In this paper, we describe the network architecture of Zattoo, one of the largest production live streaming providers in Europe at the time of writing, and present a large-scale measurement study of Zattoo using data collected by the provider. To highlight, we found that even when the Zattoo system was heavily loaded with as high as 20 000 concurrent users on a single overlay, the median channel join delay remained less than 2-5 s, and that, for a majority of users, the streamed signal lags over-the-air broadcast signal by no more than 3 s.

Television transmitted over IP (IPTV) presents numerous opportunities for users as well as service providers, and has attracted significant interest from business and research communities in recent years. Among the emerging IPTV delivery architectures, the peer-to-peer based delivery mechanism is considered attractive due to the relative ease of service deployment. However, the question of how well P2PTV applications would support a growing number of users has not been fully investigated so far. In this paper, we try to address this question by studying scalability and efficiency factors in a typical P2P based live streaming network. Through the use of the data provided by a production P2PTV system, we carry out simulations whose results show that there are still hurdles to overcome before P2P based live streaming could become widely used.

A number of commercial peer-to-peer systems for live streaming, such as PPLive, Joost, LiveStation, SOPCast, TVants, etc. have been introduced in recent years. The behavior of these popular systems has been extensively studied in several measurement papers. Due to the proprietary nature of these commercial systems, however, these studies have to rely on a "black-box" approach, where packet traces are collected from a single or a limited number of measurement points, to infer various properties of traffic on the control and data planes. Although such studies are useful to compare different systems from end-user's perspective, it is difficult to intuitively understand the observed properties without fully reverse-engineering the underlying systems. Our paper presents a large-scale measurement study of Zattoo, one of the largest production live streaming providers in Europe, using data collected by the provider. To highlight, we found that even when the Zattoo system was heavily loaded with as high as 20,000 concurrent users on a single overlay, the median channel join delay remained less than 2 to 5 seconds, and that, for a majority of users, the streamed signal lags over-the-air broadcast signal by no more than 3 seconds. To motivate the measurement study, we also present a description of the Zattoo network architecture.

A P2PTV system allows users to watch live video streams redistributed by other users via a peer-to-peer (P2P) network. In an ideal world, each peer in a P2P network would be able to redistribute more bytes than it receives. A P2PTV system built from such peers can support a virtually unlimited number of peers; with only a single copy of content stream injected into the network, it can redistribute the content to all peers. Two factors in the development of the Internet prevented the realization of this scenario: the deployment of asymmetric access networks and the adoption of NAT boxes. For real-time live streaming, such peer asymmetry and incompatibility is a limiting factor on the P2P network scalability. We first develop a basic formal analysis of the effect of bandwidth asymmetry on P2P network scalability. Then we present several characteristics of peer asymmetry as measured on the Zattoo P2PTV network. Our simulation results, driven by the measured peer characteristics, confirm that we cannot rely on P2P network alone to distribute live streaming content on today's Internet.

Abstract — Internet connectivity at the AS level, defined in terms of pairwise logical peering relationships, is constantly evolving. This evolution is largely a response to economic, political, and technological changes that impact the way ASs conduct their business. We present a new framework for modeling this evolutionary process by identifying a set of criteria that ASs consider either in establishing a new peering relationship or in reassessing an existing relationship. The proposed framework is intended to capture key elements in the decision processes underlying the formation of these relationships. We present two decision processes that are executed by an AS, depending on its role in a given peering decision, as a customer or a peer of another AS. When acting as a peer, a key feature of the AS’s corresponding decision model is its reliance on realistic inter-AS traffic demands. To reflect the enormous heterogeneity among customer or peer ASs, our decision models are flexible enough to accommodate a wide range of AS-specific objectives. We demonstrate the potential of this new framework by considering different decision models in various realistic “what if ” experiment scenarios. We implement these decision models to generate and study the evolution of the resulting AS graphs over time, and compare them against observed historical evolutionary features of the Internet at the AS level. I.

We call end-hosts behind network address translator (NAT) gateways or firewalls guarded hosts, and otherwise open hosts. In this paper, we empirically measure the prevalence of guarded hosts in two popular peer-to-peer file sharing systems, eDonkey and Gnutella, and study the characteristics of their shared files. By performing passive and active probes, we found that about 25-36% of eDonkey and Gnutella users reside on guarded hosts and that the ratio of files shared by guarded hosts is also non-trivial. When discounting guarded hosts, we found that a popular file's availability, i.e., the number of copies available for download, decreases by 25-30%. Our measurement study testifies to the significant impact guarded hosts may have on the performance of current peer-to-peer file sharing systems, and points to a need to consider their presence when designing next generation peer-to-peer systems.

C. Faloutsos et al. (see Proc. ACM SIGCOMM, 1999) found that the inter autonomous system (AS) topology exhibits a power-law vertex degree distribution. This result was quite unexpected in the networking community and stirred significant interest in exploring the possible causes of this phenomenon. The work of A.-L. Barabasi and R. Albert (see Science, p.509-512, 1999) and its application to network topology generation in the work of A. Medina et al. (see Proc. MASCOTS, 2001) have explored a promising class of models that yield strict power-law vertex degree distributions. We re-examine the BGP (border gateway protocol) measurements that form the basis for the results reported by Faloutsos et al. We find that by their very nature (i.e., being strictly BGP-based), the data provides a very incomplete picture of Internet connectivity at the AS level. The AS connectivity maps constructed from this data (original maps) typically miss 20-50% or even more of the physical links in AS maps constructed using additional sources (extended maps). Subsequently, we find that while the vertex degree distributions resulting from the extended maps are heavy-tailed, they deviate significantly from a strict power law. Finally, we show that available historical data does not support the connectivity-based dynamics assumed by Barabasi and Albert. Together, our results suggest that the Internet topology at the AS level may well have developed over time following a very different set of growth processes than those proposed by Barabasi and Albert.

For the past two years,there has been a significant increase in research activities related to studying and modeling the Internet's topology, especially at the level of autonomous systems (ASs). A closer look at the measurements that form the basis for all these studies reveals that the data sets used consist of the BGP routing tables collected by the Oregon route server (henceforth, the Oregon route-views) [1]. So far, there has been anecdotal evidence and an intuitive understanding among researchers in the field that BGP-derived AS connectivity is not complete. However, as far as we know, there has been no systematic study on quantifying the completeness of currently known AS-level Internet topologies. Our main objective in this paper is to quantify the completeness of Internet AS maps constructed from the Oregon route-views and to attempt to capture more representative AS-level Internet topology. One of the main contributions of this paper is in developing a methodology that enables quantitative investigations into issues related to the (in)completeness of BGP-derived AS maps.